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 
45   void getAnalysisUsage(AnalysisUsage &AU) const override {
46     AU.setPreservesCFG();
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 /// Checks if loop has a backwards branching WLS, and if possible, fixes it.
86 /// This requires checking the predecessor (ie. preheader or it's predecessor)
87 /// for a WLS and if its loopExit/target is before it.
88 /// If moving the predecessor won't convert a WLS (to the predecessor) from
89 /// a forward to a backward branching WLS, then move the predecessor block
90 /// to before the loopExit/target.
91 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) {
92   MachineInstr *WlsInstr = findWLS(ML);
93   if (!WlsInstr)
94     return false;
95 
96   MachineBasicBlock *Predecessor = WlsInstr->getParent();
97   MachineBasicBlock *LoopExit = getWhileLoopStartTargetBB(*WlsInstr);
98 
99   // We don't want to move Preheader to before the function's entry block.
100   if (!LoopExit->getPrevNode())
101     return false;
102   if (blockIsBefore(Predecessor, LoopExit))
103     return false;
104   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
105                     << Predecessor->getFullName() << " to "
106                     << LoopExit->getFullName() << "\n");
107 
108   // Make sure no forward branching WLSs to the Predecessor become backwards
109   // branching. An example loop structure where the Predecessor can't be moved,
110   // since bb2's WLS will become forwards once bb3 is moved before/above bb1.
111   //
112   // bb1:           - LoopExit
113   // bb2:
114   //      WLS  bb3
115   // bb3:          - Predecessor
116   //      WLS bb1
117   // bb4:          - Header
118   for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator();
119        ++It) {
120     MachineBasicBlock *MBB = &*It;
121     for (auto &Terminator : MBB->terminators()) {
122       if (!isWhileLoopStart(Terminator))
123         continue;
124       MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(Terminator);
125       // TODO: Analyse the blocks to make a decision if it would be worth
126       // moving Preheader even if we'd introduce a backwards WLS
127       if (WLSTarget == Predecessor) {
128         LLVM_DEBUG(
129             dbgs() << DEBUG_PREFIX
130                    << "Can't move Predecessor"
131                       "block as it would convert a WLS from forward to a "
132                       "backwards branching WLS\n");
133         return false;
134       }
135     }
136   }
137 
138   moveBasicBlock(Predecessor, LoopExit);
139   return true;
140 }
141 
142 /// Updates ordering (of WLS BB and their loopExits) in inner loops first
143 /// Returns true if any change was made in any of the loops
144 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
145   bool Changed = false;
146   for (auto *InnerML : *ML)
147     Changed |= processPostOrderLoops(InnerML);
148   return Changed | fixBackwardsWLS(ML);
149 }
150 
151 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
152   if (skipFunction(MF.getFunction()))
153     return false;
154   const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
155   if (!ST.hasLOB())
156     return false;
157   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
158   MLI = &getAnalysis<MachineLoopInfo>();
159   TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
160   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
161   MF.RenumberBlocks();
162   BBUtils->computeAllBlockSizes();
163   BBUtils->adjustBBOffsetsAfter(&MF.front());
164   bool Changed = false;
165 
166   // Find loops with a backwards branching WLS and fix if possible.
167   for (auto *ML : *MLI)
168     Changed |= processPostOrderLoops(ML);
169 
170   return Changed;
171 }
172 
173 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
174                                       MachineBasicBlock *Other) {
175   return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
176 }
177 
178 // Moves a BasicBlock before another, without changing the control flow
179 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
180                                        MachineBasicBlock *Before) {
181   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before "
182                     << Before->getName() << "\n");
183   MachineBasicBlock *BBPrevious = BB->getPrevNode();
184   assert(BBPrevious && "Cannot move the function entry basic block");
185   MachineBasicBlock *BBNext = BB->getNextNode();
186 
187   MachineBasicBlock *BeforePrev = Before->getPrevNode();
188   assert(BeforePrev &&
189          "Cannot move the given block to before the function entry block");
190   MachineFunction *F = BB->getParent();
191   BB->moveBefore(Before);
192 
193   // Since only the blocks are to be moved around (but the control flow must
194   // not change), if there were any fall-throughs (to/from adjacent blocks),
195   // replace with unconditional branch to the fall through block.
196   auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
197     LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
198                       << From->getName() << " to " << To->getName() << "\n");
199     assert(From->isSuccessor(To) &&
200            "'To' is expected to be a successor of 'From'");
201     MachineInstr &Terminator = *(--From->terminators().end());
202     if (!Terminator.isUnconditionalBranch()) {
203       // The BB doesn't have an unconditional branch so it relied on
204       // fall-through. Fix by adding an unconditional branch to the moved BB.
205       MachineInstrBuilder MIB =
206           BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
207       MIB.addMBB(To);
208       MIB.addImm(ARMCC::CondCodes::AL);
209       MIB.addReg(ARM::NoRegister);
210       LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
211                         << From->getName() << " to " << To->getName() << ": "
212                         << *MIB.getInstr());
213     }
214   };
215 
216   // Fix fall-through to the moved BB from the one that used to be before it.
217   if (BBPrevious->isSuccessor(BB))
218     FixFallthrough(BBPrevious, BB);
219   // Fix fall through from the destination BB to the one that used to before it.
220   if (BeforePrev->isSuccessor(Before))
221     FixFallthrough(BeforePrev, Before);
222   // Fix fall through from the moved BB to the one that used to follow.
223   if (BBNext && BB->isSuccessor(BBNext))
224     FixFallthrough(BB, BBNext);
225 
226   F->RenumberBlocks();
227   BBUtils->computeAllBlockSizes();
228   BBUtils->adjustBBOffsetsAfter(&F->front());
229 }
230