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