301 lines · cpp
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-exception6//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 24using namespace llvm;25 26#define DEBUG_TYPE "arm-block-placement"27#define DEBUG_PREFIX "ARM Block Placement: "28 29namespace llvm {30class ARMBlockPlacement : public MachineFunctionPass {31private: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 38public:39 static char ID;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 49 void getAnalysisUsage(AnalysisUsage &AU) const override {50 AU.addRequired<MachineLoopInfoWrapperPass>();51 MachineFunctionPass::getAnalysisUsage(AU);52 }53};54 55} // namespace llvm56 57FunctionPass *llvm::createARMBlockPlacementPass() {58 return new ARMBlockPlacement();59}60 61char ARMBlockPlacement::ID = 0;62 63INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,64 false)65 66static 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 only75/// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair.76static 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 that89// because of the branches this requires an extra block to be created.90bool ARMBlockPlacement::revertWhileToDoLoop(MachineInstr *WLS) {91 // lr = t2WhileLoopStartTP r0, r1, TgtBB92 // t2Br Ph93 // ->94 // cmp r0, 095 // brcc TgtBB96 // block2:97 // LR = t2DoLoopStartTP r0, r198 // t2Br Ph99 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 block112 MachineBasicBlock *NewBlock = Preheader->getParent()->CreateMachineBasicBlock(113 Preheader->getBasicBlock());114 Preheader->getParent()->insert(++Preheader->getIterator(), NewBlock);115 // Move the Br to it116 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 WLS123 MachineInstrBuilder MIB =124 BuildMI(*NewBlock, Br, WLS->getDebugLoc(),125 TII->get(WLS->getOpcode() == ARM::t2WhileLoopStartTP126 ? ARM::t2DoLoopStartTP127 : 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_PREFIX134 << "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) from152/// a forward to a backward branching WLS, then move the predecessor block153/// to before the loopExit/target.154bool 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 backwards172 // 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: - LoopExit176 // bb2:177 // WLS bb3178 // bb3: - Predecessor179 // WLS bb1180 // bb4: - Header181 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 worth189 // moving Preheader even if we'd introduce a backwards WLS190 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 first205/// Returns true if any change was made in any of the loops206bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {207 bool Changed = false;208 for (auto *InnerML : *ML)209 Changed |= processPostOrderLoops(InnerML);210 return Changed | fixBackwardsWLS(ML);211}212 213bool 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 = 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 240bool 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 flow246void 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 must261 // 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 on276 // 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