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 bool fixBackwardsWLS(MachineLoop *ML); 42 bool processPostOrderLoops(MachineLoop *ML); 43 44 void getAnalysisUsage(AnalysisUsage &AU) const override { 45 AU.setPreservesCFG(); 46 AU.addRequired<MachineLoopInfo>(); 47 MachineFunctionPass::getAnalysisUsage(AU); 48 } 49 }; 50 51 } // namespace llvm 52 53 FunctionPass *llvm::createARMBlockPlacementPass() { 54 return new ARMBlockPlacement(); 55 } 56 57 char ARMBlockPlacement::ID = 0; 58 59 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false, 60 false) 61 62 static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) { 63 for (auto &Terminator : MBB->terminators()) { 64 if (Terminator.getOpcode() == ARM::t2WhileLoopStartLR) 65 return &Terminator; 66 } 67 return nullptr; 68 } 69 70 /// Find t2WhileLoopStartLR in the loop predecessor BB or otherwise in its only 71 /// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair. 72 static MachineInstr *findWLS(MachineLoop *ML) { 73 MachineBasicBlock *Predecessor = ML->getLoopPredecessor(); 74 if (!Predecessor) 75 return nullptr; 76 MachineInstr *WlsInstr = findWLSInBlock(Predecessor); 77 if (WlsInstr) 78 return WlsInstr; 79 if (Predecessor->pred_size() == 1) 80 return findWLSInBlock(*Predecessor->pred_begin()); 81 return nullptr; 82 } 83 84 /// Checks if loop has a backwards branching WLS, and if possible, fixes it. 85 /// This requires checking the preheader (or it's predecessor) for a WLS and if 86 /// its target is before it. 87 /// If moving the target block wouldn't produce another backwards WLS or a new 88 /// forwards LE branch, then move the target block after the preheader (or it's 89 /// predecessor). 90 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) { 91 MachineInstr *WlsInstr = findWLS(ML); 92 if (!WlsInstr) 93 return false; 94 95 MachineBasicBlock *Predecessor = WlsInstr->getParent(); 96 MachineBasicBlock *LoopExit = WlsInstr->getOperand(2).getMBB(); 97 // We don't want to move the function's entry block. 98 if (!LoopExit->getPrevNode()) 99 return false; 100 if (blockIsBefore(Predecessor, LoopExit)) 101 return false; 102 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from " 103 << Predecessor->getFullName() << " to " 104 << LoopExit->getFullName() << "\n"); 105 106 // Make sure that moving the target block doesn't cause any of its WLSs 107 // that were previously not backwards to become backwards 108 bool CanMove = true; 109 MachineInstr *WlsInLoopExit = findWLSInBlock(LoopExit); 110 if (WlsInLoopExit) { 111 // An example loop structure where the LoopExit can't be moved, since 112 // bb1's WLS will become backwards once it's moved after bb3 113 // bb1: - LoopExit 114 // WLS bb2 115 // bb2: - LoopExit2 116 // ... 117 // bb3: - Predecessor 118 // WLS bb1 119 // bb4: - Header 120 MachineBasicBlock *LoopExit2 = WlsInLoopExit->getOperand(2).getMBB(); 121 // If the WLS from LoopExit to LoopExit2 is already backwards then 122 // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is 123 // after the Predecessor then moving will keep it as a forward branch, so it 124 // can be moved. If LoopExit2 is between the Predecessor and LoopExit then 125 // moving LoopExit will make it a backwards branch, so it can't be moved 126 // since we'd fix one and introduce one backwards branch. 127 // TODO: Analyse the blocks to make a decision if it would be worth 128 // moving LoopExit even if LoopExit2 is between the Predecessor and 129 // LoopExit. 130 if (!blockIsBefore(LoopExit2, LoopExit) && 131 (LoopExit2 == Predecessor || blockIsBefore(LoopExit2, Predecessor))) { 132 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 133 << "Can't move the target block as it would " 134 "introduce a new backwards WLS branch\n"); 135 CanMove = false; 136 } 137 } 138 139 if (CanMove) { 140 // Make sure no LEs become forwards. 141 // An example loop structure where the LoopExit can't be moved, since 142 // bb2's LE will become forwards once bb1 is moved after bb3. 143 // bb1: - LoopExit 144 // bb2: 145 // LE bb1 - Terminator 146 // bb3: - Predecessor 147 // WLS bb1 148 // bb4: - Header 149 for (auto It = LoopExit->getIterator(); It != Predecessor->getIterator(); 150 It++) { 151 MachineBasicBlock *MBB = &*It; 152 for (auto &Terminator : MBB->terminators()) { 153 if (Terminator.getOpcode() != ARM::t2LoopEnd && 154 Terminator.getOpcode() != ARM::t2LoopEndDec) 155 continue; 156 MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB(); 157 // The LE will become forwards branching if it branches to LoopExit 158 // which isn't allowed by the architecture, so we should avoid 159 // introducing these. 160 // TODO: Analyse the blocks to make a decision if it would be worth 161 // moving LoopExit even if we'd introduce a forwards LE 162 if (LETarget == LoopExit) { 163 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 164 << "Can't move the target block as it would " 165 "introduce a new forwards LE branch\n"); 166 CanMove = false; 167 break; 168 } 169 } 170 } 171 } 172 173 if (CanMove) 174 moveBasicBlock(LoopExit, Predecessor); 175 176 return CanMove; 177 } 178 179 /// Updates ordering (of WLS BB and their loopExits) in inner loops first 180 /// Returns true if any change was made in any of the loops 181 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) { 182 bool Changed = false; 183 for (auto *InnerML : *ML) 184 Changed |= processPostOrderLoops(InnerML); 185 return Changed | fixBackwardsWLS(ML); 186 } 187 188 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) { 189 if (skipFunction(MF.getFunction())) 190 return false; 191 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget()); 192 if (!ST.hasLOB()) 193 return false; 194 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n"); 195 MLI = &getAnalysis<MachineLoopInfo>(); 196 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo()); 197 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF)); 198 MF.RenumberBlocks(); 199 BBUtils->computeAllBlockSizes(); 200 BBUtils->adjustBBOffsetsAfter(&MF.front()); 201 bool Changed = false; 202 203 // Find loops with a backwards branching WLS and fix if possible. 204 for (auto *ML : *MLI) 205 Changed |= processPostOrderLoops(ML); 206 207 return Changed; 208 } 209 210 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 211 MachineBasicBlock *Other) { 212 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 213 } 214 215 /// Moves a given MBB to be positioned after another MBB while maintaining 216 /// existing control flow 217 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 218 MachineBasicBlock *After) { 219 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after " 220 << After->getName() << "\n"); 221 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 222 assert(BBPrevious && "Cannot move the function entry basic block"); 223 MachineBasicBlock *AfterNext = After->getNextNode(); 224 MachineBasicBlock *BBNext = BB->getNextNode(); 225 226 BB->moveAfter(After); 227 228 // Since only the blocks are to be moved around (but the control flow must 229 // not change), if there were any fall-throughs (to/from adjacent blocks), 230 // replace with unconditional branch to the fall through block. 231 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { 232 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " 233 << From->getName() << " to " << To->getName() << "\n"); 234 assert(From->isSuccessor(To) && 235 "'To' is expected to be a successor of 'From'"); 236 MachineInstr &Terminator = *(--From->terminators().end()); 237 if (!Terminator.isUnconditionalBranch()) { 238 // The BB doesn't have an unconditional branch so it relied on 239 // fall-through. Fix by adding an unconditional branch to the moved BB. 240 MachineInstrBuilder MIB = 241 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B)); 242 MIB.addMBB(To); 243 MIB.addImm(ARMCC::CondCodes::AL); 244 MIB.addReg(ARM::NoRegister); 245 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 246 << From->getName() << " to " << To->getName() << ": " 247 << *MIB.getInstr()); 248 } 249 }; 250 251 // Fix fall-through to the moved BB from the one that used to be before it. 252 if (BBPrevious->isSuccessor(BB)) 253 FixFallthrough(BBPrevious, BB); 254 // Fix fall through from the destination BB to the one that used to follow. 255 if (AfterNext && After->isSuccessor(AfterNext)) 256 FixFallthrough(After, AfterNext); 257 // Fix fall through from the moved BB to the one that used to follow. 258 if (BBNext && BB->isSuccessor(BBNext)) 259 FixFallthrough(BB, BBNext); 260 261 BBUtils->adjustBBOffsetsAfter(After); 262 } 263