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/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;
  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 llvm
  56
  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
  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.
  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.
  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.
 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
 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
 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
 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
 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 }