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 *Before); 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 predecessor (ie. preheader or it's predecessor) 86 /// for a WLS and if its loopExit/target is before it. 87 /// If moving the predecessor won't convert a WLS (to the predecessor) from 88 /// a forward to a backward branching WLS, then move the predecessor block 89 /// to before the loopExit/target. 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 98 // We don't want to move Preheader to before the function's entry block. 99 if (!LoopExit->getPrevNode()) 100 return false; 101 if (blockIsBefore(Predecessor, LoopExit)) 102 return false; 103 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from " 104 << Predecessor->getFullName() << " to " 105 << LoopExit->getFullName() << "\n"); 106 107 // Make sure no forward branching WLSs to the Predecessor become backwards 108 // branching. An example loop structure where the Predecessor can't be moved, 109 // since bb2's WLS will become forwards once bb3 is moved before/above bb1. 110 // 111 // bb1: - LoopExit 112 // bb2: 113 // WLS bb3 114 // bb3: - Predecessor 115 // WLS bb1 116 // bb4: - Header 117 for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator(); 118 ++It) { 119 MachineBasicBlock *MBB = &*It; 120 for (auto &Terminator : MBB->terminators()) { 121 if (Terminator.getOpcode() != ARM::t2WhileLoopStartLR) 122 continue; 123 MachineBasicBlock *WLSTarget = Terminator.getOperand(2).getMBB(); 124 // TODO: Analyse the blocks to make a decision if it would be worth 125 // moving Preheader even if we'd introduce a backwards WLS 126 if (WLSTarget == Predecessor) { 127 LLVM_DEBUG( 128 dbgs() << DEBUG_PREFIX 129 << "Can't move Predecessor" 130 "block as it would convert a WLS from forward to a " 131 "backwards branching WLS\n"); 132 return false; 133 } 134 } 135 } 136 137 moveBasicBlock(Predecessor, LoopExit); 138 return true; 139 } 140 141 /// Updates ordering (of WLS BB and their loopExits) in inner loops first 142 /// Returns true if any change was made in any of the loops 143 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) { 144 bool Changed = false; 145 for (auto *InnerML : *ML) 146 Changed |= processPostOrderLoops(InnerML); 147 return Changed | fixBackwardsWLS(ML); 148 } 149 150 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) { 151 if (skipFunction(MF.getFunction())) 152 return false; 153 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget()); 154 if (!ST.hasLOB()) 155 return false; 156 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n"); 157 MLI = &getAnalysis<MachineLoopInfo>(); 158 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo()); 159 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF)); 160 MF.RenumberBlocks(); 161 BBUtils->computeAllBlockSizes(); 162 BBUtils->adjustBBOffsetsAfter(&MF.front()); 163 bool Changed = false; 164 165 // Find loops with a backwards branching WLS and fix if possible. 166 for (auto *ML : *MLI) 167 Changed |= processPostOrderLoops(ML); 168 169 return Changed; 170 } 171 172 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 173 MachineBasicBlock *Other) { 174 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 175 } 176 177 // Moves a BasicBlock before another, without changing the control flow 178 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 179 MachineBasicBlock *Before) { 180 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before " 181 << Before->getName() << "\n"); 182 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 183 assert(BBPrevious && "Cannot move the function entry basic block"); 184 MachineBasicBlock *BBNext = BB->getNextNode(); 185 186 MachineBasicBlock *BeforePrev = Before->getPrevNode(); 187 assert(BeforePrev && 188 "Cannot move the given block to before the function entry block"); 189 MachineFunction *F = BB->getParent(); 190 BB->moveBefore(Before); 191 192 // Since only the blocks are to be moved around (but the control flow must 193 // not change), if there were any fall-throughs (to/from adjacent blocks), 194 // replace with unconditional branch to the fall through block. 195 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { 196 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " 197 << From->getName() << " to " << To->getName() << "\n"); 198 assert(From->isSuccessor(To) && 199 "'To' is expected to be a successor of 'From'"); 200 MachineInstr &Terminator = *(--From->terminators().end()); 201 if (!Terminator.isUnconditionalBranch()) { 202 // The BB doesn't have an unconditional branch so it relied on 203 // fall-through. Fix by adding an unconditional branch to the moved BB. 204 MachineInstrBuilder MIB = 205 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B)); 206 MIB.addMBB(To); 207 MIB.addImm(ARMCC::CondCodes::AL); 208 MIB.addReg(ARM::NoRegister); 209 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 210 << From->getName() << " to " << To->getName() << ": " 211 << *MIB.getInstr()); 212 } 213 }; 214 215 // Fix fall-through to the moved BB from the one that used to be before it. 216 if (BBPrevious->isSuccessor(BB)) 217 FixFallthrough(BBPrevious, BB); 218 // Fix fall through from the destination BB to the one that used to before it. 219 if (BeforePrev->isSuccessor(Before)) 220 FixFallthrough(BeforePrev, Before); 221 // Fix fall through from the moved BB to the one that used to follow. 222 if (BBNext && BB->isSuccessor(BBNext)) 223 FixFallthrough(BB, BBNext); 224 225 F->RenumberBlocks(); 226 BBUtils->computeAllBlockSizes(); 227 BBUtils->adjustBBOffsetsAfter(&F->front()); 228 } 229