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<MachineLoopInfo>();
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<MachineLoopInfo>();
221   TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
222   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new 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 }
301