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