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