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