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/LivePhysRegs.h" 20 #include "llvm/CodeGen/MachineFunctionPass.h" 21 #include "llvm/CodeGen/MachineInstrBuilder.h" 22 #include "llvm/CodeGen/MachineLoopInfo.h" 23 24 using namespace llvm; 25 26 #define DEBUG_TYPE "arm-block-placement" 27 #define DEBUG_PREFIX "ARM Block Placement: " 28 29 namespace llvm { 30 class ARMBlockPlacement : public MachineFunctionPass { 31 private: 32 const ARMBaseInstrInfo *TII; 33 std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr; 34 MachineLoopInfo *MLI = nullptr; 35 // A list of WLS instructions that need to be reverted to DLS. 36 SmallVector<MachineInstr *> RevertedWhileLoops; 37 38 public: 39 static char ID; ARMBlockPlacement()40 ARMBlockPlacement() : MachineFunctionPass(ID) {} 41 42 bool runOnMachineFunction(MachineFunction &MF) override; 43 void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before); 44 bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other); 45 bool fixBackwardsWLS(MachineLoop *ML); 46 bool processPostOrderLoops(MachineLoop *ML); 47 bool revertWhileToDoLoop(MachineInstr *WLS); 48 getAnalysisUsage(AnalysisUsage & AU) const49 void getAnalysisUsage(AnalysisUsage &AU) const override { 50 AU.addRequired<MachineLoopInfoWrapperPass>(); 51 MachineFunctionPass::getAnalysisUsage(AU); 52 } 53 }; 54 55 } // namespace llvm 56 createARMBlockPlacementPass()57 FunctionPass *llvm::createARMBlockPlacementPass() { 58 return new ARMBlockPlacement(); 59 } 60 61 char ARMBlockPlacement::ID = 0; 62 63 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false, 64 false) 65 findWLSInBlock(MachineBasicBlock * MBB)66 static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) { 67 for (auto &Terminator : MBB->terminators()) { 68 if (isWhileLoopStart(Terminator)) 69 return &Terminator; 70 } 71 return nullptr; 72 } 73 74 /// Find WhileLoopStart in the loop predecessor BB or otherwise in its only 75 /// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair. findWLS(MachineLoop * ML)76 static MachineInstr *findWLS(MachineLoop *ML) { 77 MachineBasicBlock *Predecessor = ML->getLoopPredecessor(); 78 if (!Predecessor) 79 return nullptr; 80 MachineInstr *WlsInstr = findWLSInBlock(Predecessor); 81 if (WlsInstr) 82 return WlsInstr; 83 if (Predecessor->pred_size() == 1) 84 return findWLSInBlock(*Predecessor->pred_begin()); 85 return nullptr; 86 } 87 88 // Revert a WhileLoopStart to an equivalent DoLoopStart and branch. Note that 89 // because of the branches this requires an extra block to be created. revertWhileToDoLoop(MachineInstr * WLS)90 bool ARMBlockPlacement::revertWhileToDoLoop(MachineInstr *WLS) { 91 // lr = t2WhileLoopStartTP r0, r1, TgtBB 92 // t2Br Ph 93 // -> 94 // cmp r0, 0 95 // brcc TgtBB 96 // block2: 97 // LR = t2DoLoopStartTP r0, r1 98 // t2Br Ph 99 MachineBasicBlock *Preheader = WLS->getParent(); 100 assert(WLS != &Preheader->back()); 101 assert(WLS->getNextNode() == &Preheader->back()); 102 MachineInstr *Br = &Preheader->back(); 103 assert(Br->getOpcode() == ARM::t2B); 104 assert(Br->getOperand(1).getImm() == 14); 105 106 // Clear the kill flags, as the cmp/bcc will no longer kill any operands. 107 WLS->getOperand(1).setIsKill(false); 108 if (WLS->getOpcode() == ARM::t2WhileLoopStartTP) 109 WLS->getOperand(2).setIsKill(false); 110 111 // Create the new block 112 MachineBasicBlock *NewBlock = Preheader->getParent()->CreateMachineBasicBlock( 113 Preheader->getBasicBlock()); 114 Preheader->getParent()->insert(++Preheader->getIterator(), NewBlock); 115 // Move the Br to it 116 Br->removeFromParent(); 117 NewBlock->insert(NewBlock->end(), Br); 118 // And setup the successors correctly. 119 Preheader->replaceSuccessor(Br->getOperand(0).getMBB(), NewBlock); 120 NewBlock->addSuccessor(Br->getOperand(0).getMBB()); 121 122 // Create a new DLS to replace the WLS 123 MachineInstrBuilder MIB = 124 BuildMI(*NewBlock, Br, WLS->getDebugLoc(), 125 TII->get(WLS->getOpcode() == ARM::t2WhileLoopStartTP 126 ? ARM::t2DoLoopStartTP 127 : ARM::t2DoLoopStart)); 128 MIB.add(WLS->getOperand(0)); 129 MIB.add(WLS->getOperand(1)); 130 if (WLS->getOpcode() == ARM::t2WhileLoopStartTP) 131 MIB.add(WLS->getOperand(2)); 132 133 LLVM_DEBUG(dbgs() << DEBUG_PREFIX 134 << "Reverting While Loop to Do Loop: " << *WLS << "\n"); 135 136 RevertWhileLoopStartLR(WLS, TII, ARM::t2Bcc, true); 137 138 LivePhysRegs LiveRegs; 139 computeAndAddLiveIns(LiveRegs, *NewBlock); 140 141 Preheader->getParent()->RenumberBlocks(); 142 BBUtils->computeAllBlockSizes(); 143 BBUtils->adjustBBOffsetsAfter(Preheader); 144 145 return true; 146 } 147 148 /// Checks if loop has a backwards branching WLS, and if possible, fixes it. 149 /// This requires checking the predecessor (ie. preheader or it's predecessor) 150 /// for a WLS and if its loopExit/target is before it. 151 /// If moving the predecessor won't convert a WLS (to the predecessor) from 152 /// a forward to a backward branching WLS, then move the predecessor block 153 /// to before the loopExit/target. fixBackwardsWLS(MachineLoop * ML)154 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) { 155 MachineInstr *WlsInstr = findWLS(ML); 156 if (!WlsInstr) 157 return false; 158 159 MachineBasicBlock *Predecessor = WlsInstr->getParent(); 160 MachineBasicBlock *LoopExit = getWhileLoopStartTargetBB(*WlsInstr); 161 162 // We don't want to move Preheader to before the function's entry block. 163 if (!LoopExit->getPrevNode()) 164 return false; 165 if (blockIsBefore(Predecessor, LoopExit)) 166 return false; 167 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from " 168 << Predecessor->getFullName() << " to " 169 << LoopExit->getFullName() << "\n"); 170 171 // Make sure no forward branching WLSs to the Predecessor become backwards 172 // branching. An example loop structure where the Predecessor can't be moved, 173 // since bb2's WLS will become forwards once bb3 is moved before/above bb1. 174 // 175 // bb1: - LoopExit 176 // bb2: 177 // WLS bb3 178 // bb3: - Predecessor 179 // WLS bb1 180 // bb4: - Header 181 for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator(); 182 ++It) { 183 MachineBasicBlock *MBB = &*It; 184 for (auto &Terminator : MBB->terminators()) { 185 if (!isWhileLoopStart(Terminator)) 186 continue; 187 MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(Terminator); 188 // TODO: Analyse the blocks to make a decision if it would be worth 189 // moving Preheader even if we'd introduce a backwards WLS 190 if (WLSTarget == Predecessor) { 191 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Can't move Predecessor block as " 192 << "it would convert a WLS from forward to a " 193 << "backwards branching WLS\n"); 194 RevertedWhileLoops.push_back(WlsInstr); 195 return false; 196 } 197 } 198 } 199 200 moveBasicBlock(Predecessor, LoopExit); 201 return true; 202 } 203 204 /// Updates ordering (of WLS BB and their loopExits) in inner loops first 205 /// Returns true if any change was made in any of the loops processPostOrderLoops(MachineLoop * ML)206 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) { 207 bool Changed = false; 208 for (auto *InnerML : *ML) 209 Changed |= processPostOrderLoops(InnerML); 210 return Changed | fixBackwardsWLS(ML); 211 } 212 runOnMachineFunction(MachineFunction & MF)213 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) { 214 if (skipFunction(MF.getFunction())) 215 return false; 216 const ARMSubtarget &ST = MF.getSubtarget<ARMSubtarget>(); 217 if (!ST.hasLOB()) 218 return false; 219 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n"); 220 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI(); 221 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo()); 222 BBUtils = std::make_unique<ARMBasicBlockUtils>(MF); 223 MF.RenumberBlocks(); 224 BBUtils->computeAllBlockSizes(); 225 BBUtils->adjustBBOffsetsAfter(&MF.front()); 226 bool Changed = false; 227 RevertedWhileLoops.clear(); 228 229 // Find loops with a backwards branching WLS and fix if possible. 230 for (auto *ML : *MLI) 231 Changed |= processPostOrderLoops(ML); 232 233 // Revert any While loops still out of range to DLS loops. 234 for (auto *WlsInstr : RevertedWhileLoops) 235 Changed |= revertWhileToDoLoop(WlsInstr); 236 237 return Changed; 238 } 239 blockIsBefore(MachineBasicBlock * BB,MachineBasicBlock * Other)240 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB, 241 MachineBasicBlock *Other) { 242 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB); 243 } 244 245 // Moves a BasicBlock before another, without changing the control flow moveBasicBlock(MachineBasicBlock * BB,MachineBasicBlock * Before)246 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB, 247 MachineBasicBlock *Before) { 248 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before " 249 << Before->getName() << "\n"); 250 MachineBasicBlock *BBPrevious = BB->getPrevNode(); 251 assert(BBPrevious && "Cannot move the function entry basic block"); 252 MachineBasicBlock *BBNext = BB->getNextNode(); 253 254 MachineBasicBlock *BeforePrev = Before->getPrevNode(); 255 assert(BeforePrev && 256 "Cannot move the given block to before the function entry block"); 257 MachineFunction *F = BB->getParent(); 258 BB->moveBefore(Before); 259 260 // Since only the blocks are to be moved around (but the control flow must 261 // not change), if there were any fall-throughs (to/from adjacent blocks), 262 // replace with unconditional branch to the fall through block. 263 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) { 264 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from " 265 << From->getName() << " to " << To->getName() << "\n"); 266 assert(From->isSuccessor(To) && 267 "'To' is expected to be a successor of 'From'"); 268 MachineInstr &Terminator = *(--From->terminators().end()); 269 if (!TII->isPredicated(Terminator) && 270 (isUncondBranchOpcode(Terminator.getOpcode()) || 271 isIndirectBranchOpcode(Terminator.getOpcode()) || 272 isJumpTableBranchOpcode(Terminator.getOpcode()) || 273 Terminator.isReturn())) 274 return; 275 // The BB doesn't have an unconditional branch so it relied on 276 // fall-through. Fix by adding an unconditional branch to the moved BB. 277 MachineInstrBuilder MIB = 278 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B)); 279 MIB.addMBB(To); 280 MIB.addImm(ARMCC::CondCodes::AL); 281 MIB.addReg(ARM::NoRegister); 282 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from " 283 << From->getName() << " to " << To->getName() << ": " 284 << *MIB.getInstr()); 285 }; 286 287 // Fix fall-through to the moved BB from the one that used to be before it. 288 if (BBPrevious->isSuccessor(BB)) 289 FixFallthrough(BBPrevious, BB); 290 // Fix fall through from the destination BB to the one that used to before it. 291 if (BeforePrev->isSuccessor(Before)) 292 FixFallthrough(BeforePrev, Before); 293 // Fix fall through from the moved BB to the one that used to follow. 294 if (BBNext && BB->isSuccessor(BBNext)) 295 FixFallthrough(BB, BBNext); 296 297 F->RenumberBlocks(); 298 BBUtils->computeAllBlockSizes(); 299 BBUtils->adjustBBOffsetsAfter(BB); 300 } 301