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