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 "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineLoopInfo.h"
21 
22 using namespace llvm;
23 
24 #define DEBUG_TYPE "arm-block-placement"
25 #define DEBUG_PREFIX "ARM Block Placement: "
26 
27 namespace llvm {
28 class ARMBlockPlacement : public MachineFunctionPass {
29 private:
30   const ARMBaseInstrInfo *TII;
31   std::unique_ptr<ARMBasicBlockUtils> BBUtils = nullptr;
32   MachineLoopInfo *MLI = nullptr;
33 
34 public:
35   static char ID;
36   ARMBlockPlacement() : MachineFunctionPass(ID) {}
37 
38   bool runOnMachineFunction(MachineFunction &MF) override;
39   void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *After);
40   bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
41 
42   void getAnalysisUsage(AnalysisUsage &AU) const override {
43     AU.setPreservesCFG();
44     AU.addRequired<MachineLoopInfo>();
45     MachineFunctionPass::getAnalysisUsage(AU);
46   }
47 };
48 
49 } // namespace llvm
50 
51 FunctionPass *llvm::createARMBlockPlacementPass() {
52   return new ARMBlockPlacement();
53 }
54 
55 char ARMBlockPlacement::ID = 0;
56 
57 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
58                 false)
59 
60 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
61   if (skipFunction(MF.getFunction()))
62       return false;
63   const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
64   if (!ST.hasLOB())
65     return false;
66   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
67   MLI = &getAnalysis<MachineLoopInfo>();
68   TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
69   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
70   MF.RenumberBlocks();
71   BBUtils->computeAllBlockSizes();
72   BBUtils->adjustBBOffsetsAfter(&MF.front());
73   bool Changed = false;
74 
75   // Find loops with a backwards branching WLS.
76   // This requires looping over the loops in the function, checking each
77   // preheader for a WLS and if its target is before the preheader. If moving
78   // the target block wouldn't produce another backwards WLS or a new forwards
79   // LE branch then move the target block after the preheader.
80   for (auto *ML : *MLI) {
81     MachineBasicBlock *Preheader = ML->getLoopPredecessor();
82     if (!Preheader)
83       continue;
84 
85     for (auto &Terminator : Preheader->terminators()) {
86       if (Terminator.getOpcode() != ARM::t2WhileLoopStart)
87         continue;
88       MachineBasicBlock *LoopExit = Terminator.getOperand(1).getMBB();
89       // We don't want to move the function's entry block.
90       if (!LoopExit->getPrevNode())
91         continue;
92       if (blockIsBefore(Preheader, LoopExit))
93         continue;
94       LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
95                         << Preheader->getFullName() << " to "
96                         << LoopExit->getFullName() << "\n");
97 
98       // Make sure that moving the target block doesn't cause any of its WLSs
99       // that were previously not backwards to become backwards
100       bool CanMove = true;
101       for (auto &LoopExitTerminator : LoopExit->terminators()) {
102         if (LoopExitTerminator.getOpcode() != ARM::t2WhileLoopStart)
103           continue;
104         // An example loop structure where the LoopExit can't be moved, since
105         // bb1's WLS will become backwards once it's moved after bb3 bb1: -
106         // LoopExit
107         //      WLS bb2  - LoopExit2
108         // bb2:
109         //      ...
110         // bb3:          - Preheader
111         //      WLS bb1
112         // bb4:          - Header
113         MachineBasicBlock *LoopExit2 =
114             LoopExitTerminator.getOperand(1).getMBB();
115         // If the WLS from LoopExit to LoopExit2 is already backwards then
116         // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is
117         // after the Preheader then moving will keep it as a forward branch, so
118         // it can be moved. If LoopExit2 is between the Preheader and LoopExit
119         // then moving LoopExit will make it a backwards branch, so it can't be
120         // moved since we'd fix one and introduce one backwards branch.
121         // TODO: Analyse the blocks to make a decision if it would be worth
122         // moving LoopExit even if LoopExit2 is between the Preheader and
123         // LoopExit.
124         if (!blockIsBefore(LoopExit2, LoopExit) &&
125             (LoopExit2 == Preheader || blockIsBefore(LoopExit2, Preheader))) {
126           LLVM_DEBUG(dbgs() << DEBUG_PREFIX
127                             << "Can't move the target block as it would "
128                                "introduce a new backwards WLS branch\n");
129           CanMove = false;
130           break;
131         }
132       }
133 
134       if (CanMove) {
135         // Make sure no LEs become forwards.
136         // An example loop structure where the LoopExit can't be moved, since
137         // bb2's LE will become forwards once bb1 is moved after bb3.
138         // bb1:           - LoopExit
139         // bb2:
140         //      LE  bb1  - Terminator
141         // bb3:          - Preheader
142         //      WLS bb1
143         // bb4:          - Header
144         for (auto It = LoopExit->getIterator(); It != Preheader->getIterator();
145              It++) {
146           MachineBasicBlock *MBB = &*It;
147           for (auto &Terminator : MBB->terminators()) {
148             if (Terminator.getOpcode() != ARM::t2LoopEndDec)
149               continue;
150             MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB();
151             // The LE will become forwards branching if it branches to LoopExit
152             // which isn't allowed by the architecture, so we should avoid
153             // introducing these.
154             // TODO: Analyse the blocks to make a decision if it would be worth
155             // moving LoopExit even if we'd introduce a forwards LE
156             if (LETarget == LoopExit) {
157               LLVM_DEBUG(dbgs() << DEBUG_PREFIX
158                                 << "Can't move the target block as it would "
159                                    "introduce a new forwards LE branch\n");
160               CanMove = false;
161               break;
162             }
163           }
164         }
165 
166         if (!CanMove)
167           break;
168       }
169 
170       if (CanMove) {
171         moveBasicBlock(LoopExit, Preheader);
172         Changed = true;
173         break;
174       }
175     }
176   }
177 
178   return Changed;
179 }
180 
181 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
182                                       MachineBasicBlock *Other) {
183   return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
184 }
185 
186 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
187                                        MachineBasicBlock *After) {
188   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after "
189                     << After->getName() << "\n");
190   MachineBasicBlock *BBPrevious = BB->getPrevNode();
191   assert(BBPrevious && "Cannot move the function entry basic block");
192   MachineBasicBlock *AfterNext = After->getNextNode();
193   MachineBasicBlock *BBNext = BB->getNextNode();
194 
195   BB->moveAfter(After);
196 
197   auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
198     LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
199                       << From->getName() << " to " << To->getName() << "\n");
200     assert(From->isSuccessor(To) &&
201            "'To' is expected to be a successor of 'From'");
202     MachineInstr &Terminator = *(--From->terminators().end());
203     if (!Terminator.isUnconditionalBranch()) {
204       // The BB doesn't have an unconditional branch so it relied on
205       // fall-through. Fix by adding an unconditional branch to the moved BB.
206       MachineInstrBuilder MIB =
207           BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
208       MIB.addMBB(To);
209       MIB.addImm(ARMCC::CondCodes::AL);
210       MIB.addReg(ARM::NoRegister);
211       LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
212                         << From->getName() << " to " << To->getName() << ": "
213                         << *MIB.getInstr());
214     }
215   };
216 
217   // Fix fall-through to the moved BB from the one that used to be before it.
218   if (BBPrevious->isSuccessor(BB))
219     FixFallthrough(BBPrevious, BB);
220   // Fix fall through from the destination BB to the one that used to follow.
221   if (AfterNext && After->isSuccessor(AfterNext))
222     FixFallthrough(After, AfterNext);
223   // Fix fall through from the moved BB to the one that used to follow.
224   if (BBNext && BB->isSuccessor(BBNext))
225     FixFallthrough(BB, BBNext);
226 
227   BBUtils->adjustBBOffsetsAfter(After);
228 }
229