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::t2LoopEndDec) 149 continue; 150 MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB(); 151 // The LE will become forwards branching if it branches to LoopExit 152 // which isn't allowed by the architecture, so we should avoid 153 // introducing these. 154 // TODO: Analyse the blocks to make a decision if it would be worth 155 // moving LoopExit even if we'd introduce a forwards LE 156 if (LETarget == LoopExit) { 157 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 158 << "Can't move the target block as it would " 159 "introduce a new forwards LE branch\n"); 160 CanMove = false; 161 break; 162 } 163 } 164 } 165 166 if (!CanMove) 167 break; 168 } 169 170 if (CanMove) { 171 moveBasicBlock(LoopExit, Preheader); 172 Changed = true; 173 break; 174 } 175 } 176 } 177 178 return Changed; 179 } 180 181 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 182 MachineBasicBlock *Other) { 183 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 184 } 185 186 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 187 MachineBasicBlock *After) { 188 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after " 189 << After->getName() << "\n"); 190 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 191 assert(BBPrevious && "Cannot move the function entry basic block"); 192 MachineBasicBlock *AfterNext = After->getNextNode(); 193 MachineBasicBlock *BBNext = BB->getNextNode(); 194 195 BB->moveAfter(After); 196 197 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { 198 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " 199 << From->getName() << " to " << To->getName() << "\n"); 200 assert(From->isSuccessor(To) && 201 "'To' is expected to be a successor of 'From'"); 202 MachineInstr &Terminator = *(--From->terminators().end()); 203 if (!Terminator.isUnconditionalBranch()) { 204 // The BB doesn't have an unconditional branch so it relied on 205 // fall-through. Fix by adding an unconditional branch to the moved BB. 206 MachineInstrBuilder MIB = 207 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B)); 208 MIB.addMBB(To); 209 MIB.addImm(ARMCC::CondCodes::AL); 210 MIB.addReg(ARM::NoRegister); 211 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 212 << From->getName() << " to " << To->getName() << ": " 213 << *MIB.getInstr()); 214 } 215 }; 216 217 // Fix fall-through to the moved BB from the one that used to be before it. 218 if (BBPrevious->isSuccessor(BB)) 219 FixFallthrough(BBPrevious, BB); 220 // Fix fall through from the destination BB to the one that used to follow. 221 if (AfterNext && After->isSuccessor(AfterNext)) 222 FixFallthrough(After, AfterNext); 223 // Fix fall through from the moved BB to the one that used to follow. 224 if (BBNext && BB->isSuccessor(BBNext)) 225 FixFallthrough(BB, BBNext); 226 227 BBUtils->adjustBBOffsetsAfter(After); 228 } 229