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 if (skipFunction(MF.getFunction())) 62 return false; 63 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget()); 64 if (!ST.hasLOB()) 65 return false; 66 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n"); 67 MLI = &getAnalysis<MachineLoopInfo>(); 68 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo()); 69 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF)); 70 MF.RenumberBlocks(); 71 BBUtils->computeAllBlockSizes(); 72 BBUtils->adjustBBOffsetsAfter(&MF.front()); 73 bool Changed = false; 74 75 // Find loops with a backwards branching WLS. 76 // This requires looping over the loops in the function, checking each 77 // preheader for a WLS and if its target is before the preheader. If moving 78 // the target block wouldn't produce another backwards WLS or a new forwards 79 // LE branch then move the target block after the preheader. 80 for (auto *ML : *MLI) { 81 MachineBasicBlock *Preheader = ML->getLoopPredecessor(); 82 83 for (auto &Terminator : Preheader->terminators()) { 84 if (Terminator.getOpcode() != ARM::t2WhileLoopStart) 85 continue; 86 MachineBasicBlock *LoopExit = Terminator.getOperand(1).getMBB(); 87 // We don't want to move the function's entry block. 88 if (!LoopExit->getPrevNode()) 89 continue; 90 if (blockIsBefore(Preheader, LoopExit)) 91 continue; 92 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from " 93 << Preheader->getFullName() << " to " 94 << LoopExit->getFullName() << "\n"); 95 96 // Make sure that moving the target block doesn't cause any of its WLSs 97 // that were previously not backwards to become backwards 98 bool CanMove = true; 99 for (auto &LoopExitTerminator : LoopExit->terminators()) { 100 if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStart) 101 continue; 102 // An example loop structure where the LoopExit can't be moved, since 103 // bb1's WLS will become backwards once it's moved after bb3 bb1: - 104 // LoopExit 105 // WLS bb2 - LoopExit2 106 // bb2: 107 // ... 108 // bb3: - Preheader 109 // WLS bb1 110 // bb4: - Header 111 MachineBasicBlock *LoopExit2 = 112 LoopExitTerminator.getOperand(1).getMBB(); 113 // If the WLS from LoopExit to LoopExit2 is already backwards then 114 // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is 115 // after the Preheader then moving will keep it as a forward branch, so 116 // it can be moved. If LoopExit2 is between the Preheader and LoopExit 117 // then moving LoopExit will make it a backwards branch, so it can't be 118 // moved since we'd fix one and introduce one backwards branch. 119 // TODO: Analyse the blocks to make a decision if it would be worth 120 // moving LoopExit even if LoopExit2 is between the Preheader and 121 // LoopExit. 122 if (!blockIsBefore(LoopExit2, LoopExit) && 123 (LoopExit2 == Preheader || blockIsBefore(LoopExit2, Preheader))) { 124 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 125 << "Can't move the target block as it would " 126 "introduce a new backwards WLS branch\n"); 127 CanMove = false; 128 break; 129 } 130 } 131 132 if (CanMove) { 133 // Make sure no LEs become forwards. 134 // An example loop structure where the LoopExit can't be moved, since 135 // bb2's LE will become forwards once bb1 is moved after bb3. 136 // bb1: - LoopExit 137 // bb2: 138 // LE bb1 - Terminator 139 // bb3: - Preheader 140 // WLS bb1 141 // bb4: - Header 142 for (auto It = LoopExit->getIterator(); It != Preheader->getIterator(); 143 It++) { 144 MachineBasicBlock *MBB = &*It; 145 for (auto &Terminator : MBB->terminators()) { 146 if (Terminator.getOpcode() != ARM::t2LoopEnd && 147 Terminator.getOpcode() != ARM::t2LoopEndDec) 148 continue; 149 MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB(); 150 // The LE will become forwards branching if it branches to LoopExit 151 // which isn't allowed by the architecture, so we should avoid 152 // introducing these. 153 // TODO: Analyse the blocks to make a decision if it would be worth 154 // moving LoopExit even if we'd introduce a forwards LE 155 if (LETarget == LoopExit) { 156 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 157 << "Can't move the target block as it would " 158 "introduce a new forwards LE branch\n"); 159 CanMove = false; 160 break; 161 } 162 } 163 } 164 165 if (!CanMove) 166 break; 167 } 168 169 if (CanMove) { 170 moveBasicBlock(LoopExit, Preheader); 171 Changed = true; 172 break; 173 } 174 } 175 } 176 177 return Changed; 178 } 179 180 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 181 MachineBasicBlock *Other) { 182 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 183 } 184 185 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 186 MachineBasicBlock *After) { 187 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after " 188 << After->getName() << "\n"); 189 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 190 assert(BBPrevious && "Cannot move the function entry basic block"); 191 MachineBasicBlock *AfterNext = After->getNextNode(); 192 MachineBasicBlock *BBNext = BB->getNextNode(); 193 194 BB->moveAfter(After); 195 196 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { 197 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " 198 << From->getName() << " to " << To->getName() << "\n"); 199 assert(From->isSuccessor(To) && 200 "'To' is expected to be a successor of 'From'"); 201 MachineInstr &Terminator = *(--From->terminators().end()); 202 if (!Terminator.isUnconditionalBranch()) { 203 // The BB doesn't have an unconditional branch so it relied on 204 // fall-through. Fix by adding an unconditional branch to the moved BB. 205 unsigned BrOpc = 206 BBUtils->isBBInRange(&Terminator, To, 254) ? ARM::tB : ARM::t2B; 207 MachineInstrBuilder MIB = 208 BuildMI(From, Terminator.getDebugLoc(), TII->get(BrOpc)); 209 MIB.addMBB(To); 210 MIB.addImm(ARMCC::CondCodes::AL); 211 MIB.addReg(ARM::NoRegister); 212 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 213 << From->getName() << " to " << To->getName() << ": " 214 << *MIB.getInstr()); 215 } 216 }; 217 218 // Fix fall-through to the moved BB from the one that used to be before it. 219 if (BBPrevious->isSuccessor(BB)) 220 FixFallthrough(BBPrevious, BB); 221 // Fix fall through from the destination BB to the one that used to follow. 222 if (AfterNext && After->isSuccessor(AfterNext)) 223 FixFallthrough(After, AfterNext); 224 // Fix fall through from the moved BB to the one that used to follow. 225 if (BBNext && BB->isSuccessor(BBNext)) 226 FixFallthrough(BB, BBNext); 227 228 BBUtils->adjustBBOffsetsAfter(After); 229 } 230