1 //===-- ARMBlockPlacement.cpp - ARM block placement pass ------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass re-arranges machine basic blocks to suit target requirements. 10 // Currently it only moves blocks to fix backwards WLS branches. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "ARM.h" 15 #include "ARMBaseInstrInfo.h" 16 #include "ARMBasicBlockInfo.h" 17 #include "ARMSubtarget.h" 18 #include "llvm/CodeGen/MachineFunctionPass.h" 19 #include "llvm/CodeGen/MachineInstrBuilder.h" 20 #include "llvm/CodeGen/MachineLoopInfo.h" 21 22 using namespace llvm; 23 24 #define DEBUG_TYPE "arm-block-placement" 25 #define DEBUG_PREFIX "ARM Block Placement: " 26 27 namespace llvm { 28 class ARMBlockPlacement : public MachineFunctionPass { 29 private: 30 const ARMBaseInstrInfo *TII; 31 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; 32 MachineLoopInfo *MLI = nullptr; 33 34 public: 35 static char ID; 36 ARMBlockPlacement() : MachineFunctionPass(ID) {} 37 38 bool runOnMachineFunction(MachineFunction &MF) override; 39 void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *After); 40 bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other); 41 42 void getAnalysisUsage(AnalysisUsage &AU) const override { 43 AU.setPreservesCFG(); 44 AU.addRequired<MachineLoopInfo>(); 45 MachineFunctionPass::getAnalysisUsage(AU); 46 } 47 }; 48 49 } // namespace llvm 50 51 FunctionPass *llvm::createARMBlockPlacementPass() { 52 return new ARMBlockPlacement(); 53 } 54 55 char ARMBlockPlacement::ID = 0; 56 57 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false, 58 false) 59 60 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) { 61 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget()); 62 if (!ST.hasLOB()) 63 return false; 64 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n"); 65 MLI = &getAnalysis<MachineLoopInfo>(); 66 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo()); 67 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF)); 68 MF.RenumberBlocks(); 69 BBUtils->computeAllBlockSizes(); 70 BBUtils->adjustBBOffsetsAfter(&MF.front()); 71 bool Changed = false; 72 73 // Find loops with a backwards branching WLS. 74 // This requires looping over the loops in the function, checking each 75 // preheader for a WLS and if its target is before the preheader. If moving 76 // the target block wouldn't produce another backwards WLS or a new forwards 77 // LE branch then move the target block after the preheader. 78 for (auto *ML : *MLI) { 79 MachineBasicBlock *Preheader = ML->getLoopPredecessor(); 80 81 for (auto &Terminator : Preheader->terminators()) { 82 if (Terminator.getOpcode() != ARM::t2WhileLoopStart) 83 continue; 84 MachineBasicBlock *LoopExit = Terminator.getOperand(1).getMBB(); 85 // We don't want to move the function's entry block. 86 if (!LoopExit->getPrevNode()) 87 continue; 88 if (blockIsBefore(Preheader, LoopExit)) 89 continue; 90 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from " 91 << Preheader->getFullName() << " to " 92 << LoopExit->getFullName() << "\n"); 93 94 // Make sure that moving the target block doesn't cause any of its WLSs 95 // that were previously not backwards to become backwards 96 bool CanMove = true; 97 for (auto &LoopExitTerminator : LoopExit->terminators()) { 98 if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStart) 99 continue; 100 // An example loop structure where the LoopExit can't be moved, since 101 // bb1's WLS will become backwards once it's moved after bb3 bb1: - 102 // LoopExit 103 // WLS bb2 - LoopExit2 104 // bb2: 105 // ... 106 // bb3: - Preheader 107 // WLS bb1 108 // bb4: - Header 109 MachineBasicBlock *LoopExit2 = 110 LoopExitTerminator.getOperand(1).getMBB(); 111 // If the WLS from LoopExit to LoopExit2 is already backwards then 112 // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is 113 // after the Preheader then moving will keep it as a forward branch, so 114 // it can be moved. If LoopExit2 is between the Preheader and LoopExit 115 // then moving LoopExit will make it a backwards branch, so it can't be 116 // moved since we'd fix one and introduce one backwards branch. 117 // TODO: Analyse the blocks to make a decision if it would be worth 118 // moving LoopExit even if LoopExit2 is between the Preheader and 119 // LoopExit. 120 if (!blockIsBefore(LoopExit2, LoopExit) && 121 (LoopExit2 == Preheader || blockIsBefore(LoopExit2, Preheader))) { 122 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 123 << "Can't move the target block as it would " 124 "introduce a new backwards WLS branch\n"); 125 CanMove = false; 126 break; 127 } 128 } 129 130 if (CanMove) { 131 // Make sure no LEs become forwards. 132 // An example loop structure where the LoopExit can't be moved, since 133 // bb2's LE will become forwards once bb1 is moved after bb3. 134 // bb1: - LoopExit 135 // bb2: 136 // LE bb1 - Terminator 137 // bb3: - Preheader 138 // WLS bb1 139 // bb4: - Header 140 for (auto It = LoopExit->getIterator(); It != Preheader->getIterator(); 141 It++) { 142 MachineBasicBlock *MBB = &*It; 143 for (auto &Terminator : MBB->terminators()) { 144 if (Terminator.getOpcode() != ARM::t2LoopEnd && 145 Terminator.getOpcode() != ARM::t2LoopEndDec) 146 continue; 147 MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB(); 148 // The LE will become forwards branching if it branches to LoopExit 149 // which isn't allowed by the architecture, so we should avoid 150 // introducing these. 151 // TODO: Analyse the blocks to make a decision if it would be worth 152 // moving LoopExit even if we'd introduce a forwards LE 153 if (LETarget == LoopExit) { 154 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 155 << "Can't move the target block as it would " 156 "introduce a new forwards LE branch\n"); 157 CanMove = false; 158 break; 159 } 160 } 161 } 162 163 if (!CanMove) 164 break; 165 } 166 167 if (CanMove) { 168 moveBasicBlock(LoopExit, Preheader); 169 Changed = true; 170 break; 171 } 172 } 173 } 174 175 return Changed; 176 } 177 178 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 179 MachineBasicBlock *Other) { 180 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 181 } 182 183 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 184 MachineBasicBlock *After) { 185 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after " 186 << After->getName() << "\n"); 187 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 188 assert(BBPrevious && "Cannot move the function entry basic block"); 189 MachineBasicBlock *AfterNext = After->getNextNode(); 190 MachineBasicBlock *BBNext = BB->getNextNode(); 191 192 BB->moveAfter(After); 193 194 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { 195 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " 196 << From->getName() << " to " << To->getName() << "\n"); 197 assert(From->isSuccessor(To) && 198 "'To' is expected to be a successor of 'From'"); 199 MachineInstr &Terminator = *(--From->terminators().end()); 200 if (!Terminator.isUnconditionalBranch()) { 201 // The BB doesn't have an unconditional branch so it relied on 202 // fall-through. Fix by adding an unconditional branch to the moved BB. 203 unsigned BrOpc = 204 BBUtils->isBBInRange(&Terminator, To, 254) ? ARM::tB : ARM::t2B; 205 MachineInstrBuilder MIB = 206 BuildMI(From, Terminator.getDebugLoc(), TII->get(BrOpc)); 207 MIB.addMBB(To); 208 MIB.addImm(ARMCC::CondCodes::AL); 209 MIB.addReg(ARM::NoRegister); 210 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 211 << From->getName() << " to " << To->getName() << ": " 212 << *MIB.getInstr()); 213 } 214 }; 215 216 // Fix fall-through to the moved BB from the one that used to be before it. 217 if (BBPrevious->isSuccessor(BB)) 218 FixFallthrough(BBPrevious, BB); 219 // Fix fall through from the destination BB to the one that used to follow. 220 if (AfterNext && After->isSuccessor(AfterNext)) 221 FixFallthrough(After, AfterNext); 222 // Fix fall through from the moved BB to the one that used to follow. 223 if (BBNext && BB->isSuccessor(BBNext)) 224 FixFallthrough(BB, BBNext); 225 226 BBUtils->adjustBBOffsetsAfter(After); 227 } 228