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 "MVETailPredUtils.h" 19 #include "llvm/CodeGen/MachineFunctionPass.h" 20 #include "llvm/CodeGen/MachineInstrBuilder.h" 21 #include "llvm/CodeGen/MachineLoopInfo.h" 22 23 using namespace llvm; 24 25 #define DEBUG_TYPE "arm-block-placement" 26 #define DEBUG_PREFIX "ARM Block Placement: " 27 28 namespace llvm { 29 class ARMBlockPlacement : public MachineFunctionPass { 30 private: 31 const ARMBaseInstrInfo *TII; 32 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; 33 MachineLoopInfo *MLI = nullptr; 34 35 public: 36 static char ID; 37 ARMBlockPlacement() : MachineFunctionPass(ID) {} 38 39 bool runOnMachineFunction(MachineFunction &MF) override; 40 void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before); 41 bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other); 42 bool fixBackwardsWLS(MachineLoop *ML); 43 bool processPostOrderLoops(MachineLoop *ML); 44 45 void getAnalysisUsage(AnalysisUsage &AU) const override { 46 AU.setPreservesCFG(); 47 AU.addRequired<MachineLoopInfo>(); 48 MachineFunctionPass::getAnalysisUsage(AU); 49 } 50 }; 51 52 } // namespace llvm 53 54 FunctionPass *llvm::createARMBlockPlacementPass() { 55 return new ARMBlockPlacement(); 56 } 57 58 char ARMBlockPlacement::ID = 0; 59 60 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false, 61 false) 62 63 static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) { 64 for (auto &Terminator : MBB->terminators()) { 65 if (isWhileLoopStart(Terminator)) 66 return &Terminator; 67 } 68 return nullptr; 69 } 70 71 /// Find WhileLoopStart in the loop predecessor BB or otherwise in its only 72 /// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair. 73 static MachineInstr *findWLS(MachineLoop *ML) { 74 MachineBasicBlock *Predecessor = ML->getLoopPredecessor(); 75 if (!Predecessor) 76 return nullptr; 77 MachineInstr *WlsInstr = findWLSInBlock(Predecessor); 78 if (WlsInstr) 79 return WlsInstr; 80 if (Predecessor->pred_size() == 1) 81 return findWLSInBlock(*Predecessor->pred_begin()); 82 return nullptr; 83 } 84 85 /// Checks if loop has a backwards branching WLS, and if possible, fixes it. 86 /// This requires checking the predecessor (ie. preheader or it's predecessor) 87 /// for a WLS and if its loopExit/target is before it. 88 /// If moving the predecessor won't convert a WLS (to the predecessor) from 89 /// a forward to a backward branching WLS, then move the predecessor block 90 /// to before the loopExit/target. 91 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) { 92 MachineInstr *WlsInstr = findWLS(ML); 93 if (!WlsInstr) 94 return false; 95 96 MachineBasicBlock *Predecessor = WlsInstr->getParent(); 97 MachineBasicBlock *LoopExit = getWhileLoopStartTargetBB(*WlsInstr); 98 99 // We don't want to move Preheader to before the function's entry block. 100 if (!LoopExit->getPrevNode()) 101 return false; 102 if (blockIsBefore(Predecessor, LoopExit)) 103 return false; 104 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from " 105 << Predecessor->getFullName() << " to " 106 << LoopExit->getFullName() << "\n"); 107 108 // Make sure no forward branching WLSs to the Predecessor become backwards 109 // branching. An example loop structure where the Predecessor can't be moved, 110 // since bb2's WLS will become forwards once bb3 is moved before/above bb1. 111 // 112 // bb1: - LoopExit 113 // bb2: 114 // WLS bb3 115 // bb3: - Predecessor 116 // WLS bb1 117 // bb4: - Header 118 for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator(); 119 ++It) { 120 MachineBasicBlock *MBB = &*It; 121 for (auto &Terminator : MBB->terminators()) { 122 if (!isWhileLoopStart(Terminator)) 123 continue; 124 MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(Terminator); 125 // TODO: Analyse the blocks to make a decision if it would be worth 126 // moving Preheader even if we'd introduce a backwards WLS 127 if (WLSTarget == Predecessor) { 128 LLVM_DEBUG( 129 dbgs() << DEBUG_PREFIX 130 << "Can't move Predecessor" 131 "block as it would convert a WLS from forward to a " 132 "backwards branching WLS\n"); 133 return false; 134 } 135 } 136 } 137 138 moveBasicBlock(Predecessor, LoopExit); 139 return true; 140 } 141 142 /// Updates ordering (of WLS BB and their loopExits) in inner loops first 143 /// Returns true if any change was made in any of the loops 144 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) { 145 bool Changed = false; 146 for (auto *InnerML : *ML) 147 Changed |= processPostOrderLoops(InnerML); 148 return Changed | fixBackwardsWLS(ML); 149 } 150 151 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) { 152 if (skipFunction(MF.getFunction())) 153 return false; 154 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget()); 155 if (!ST.hasLOB()) 156 return false; 157 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n"); 158 MLI = &getAnalysis<MachineLoopInfo>(); 159 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo()); 160 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF)); 161 MF.RenumberBlocks(); 162 BBUtils->computeAllBlockSizes(); 163 BBUtils->adjustBBOffsetsAfter(&MF.front()); 164 bool Changed = false; 165 166 // Find loops with a backwards branching WLS and fix if possible. 167 for (auto *ML : *MLI) 168 Changed |= processPostOrderLoops(ML); 169 170 return Changed; 171 } 172 173 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 174 MachineBasicBlock *Other) { 175 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 176 } 177 178 // Moves a BasicBlock before another, without changing the control flow 179 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 180 MachineBasicBlock *Before) { 181 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before " 182 << Before->getName() << "\n"); 183 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 184 assert(BBPrevious && "Cannot move the function entry basic block"); 185 MachineBasicBlock *BBNext = BB->getNextNode(); 186 187 MachineBasicBlock *BeforePrev = Before->getPrevNode(); 188 assert(BeforePrev && 189 "Cannot move the given block to before the function entry block"); 190 MachineFunction *F = BB->getParent(); 191 BB->moveBefore(Before); 192 193 // Since only the blocks are to be moved around (but the control flow must 194 // not change), if there were any fall-throughs (to/from adjacent blocks), 195 // replace with unconditional branch to the fall through block. 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 MachineInstrBuilder MIB = 206 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B)); 207 MIB.addMBB(To); 208 MIB.addImm(ARMCC::CondCodes::AL); 209 MIB.addReg(ARM::NoRegister); 210 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 211 << From->getName() << " to " << To->getName() << ": " 212 << *MIB.getInstr()); 213 } 214 }; 215 216 // Fix fall-through to the moved BB from the one that used to be before it. 217 if (BBPrevious->isSuccessor(BB)) 218 FixFallthrough(BBPrevious, BB); 219 // Fix fall through from the destination BB to the one that used to before it. 220 if (BeforePrev->isSuccessor(Before)) 221 FixFallthrough(BeforePrev, Before); 222 // Fix fall through from the moved BB to the one that used to follow. 223 if (BBNext && BB->isSuccessor(BBNext)) 224 FixFallthrough(BB, BBNext); 225 226 F->RenumberBlocks(); 227 BBUtils->computeAllBlockSizes(); 228 BBUtils->adjustBBOffsetsAfter(&F->front()); 229 } 230