xref: /llvm-project/llvm/lib/Target/ARM/ARMBlockPlacement.cpp (revision 465df35355ec30ab8c60ef1c0c156a6b22bda7d4)
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   bool fixBackwardsWLS(MachineLoop *ML);
42   bool processPostOrderLoops(MachineLoop *ML);
43 
44   void getAnalysisUsage(AnalysisUsage &AU) const override {
45     AU.setPreservesCFG();
46     AU.addRequired<MachineLoopInfo>();
47     MachineFunctionPass::getAnalysisUsage(AU);
48   }
49 };
50 
51 } // namespace llvm
52 
53 FunctionPass *llvm::createARMBlockPlacementPass() {
54   return new ARMBlockPlacement();
55 }
56 
57 char ARMBlockPlacement::ID = 0;
58 
59 INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
60                 false)
61 
62 static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) {
63   for (auto &Terminator : MBB->terminators()) {
64     if (Terminator.getOpcode() == ARM::t2WhileLoopStartLR)
65       return &Terminator;
66   }
67   return nullptr;
68 }
69 
70 /// Find t2WhileLoopStartLR in the loop predecessor BB or otherwise in its only
71 /// predecessor. If found, returns (BB, WLS Instr) pair, otherwise a null pair.
72 static MachineInstr *findWLS(MachineLoop *ML) {
73   MachineBasicBlock *Predecessor = ML->getLoopPredecessor();
74   if (!Predecessor)
75     return nullptr;
76   MachineInstr *WlsInstr = findWLSInBlock(Predecessor);
77   if (WlsInstr)
78     return WlsInstr;
79   if (Predecessor->pred_size() == 1)
80     return findWLSInBlock(*Predecessor->pred_begin());
81   return nullptr;
82 }
83 
84 /// Checks if loop has a backwards branching WLS, and if possible, fixes it.
85 /// This requires checking the preheader (or it's predecessor) for a WLS and if
86 /// its target is before it.
87 /// If moving the target block wouldn't produce another backwards WLS or a new
88 /// forwards LE branch, then move the target block after the preheader (or it's
89 /// predecessor).
90 bool ARMBlockPlacement::fixBackwardsWLS(MachineLoop *ML) {
91   MachineInstr *WlsInstr = findWLS(ML);
92   if (!WlsInstr)
93     return false;
94 
95   MachineBasicBlock *Predecessor = WlsInstr->getParent();
96   MachineBasicBlock *LoopExit = WlsInstr->getOperand(2).getMBB();
97   // We don't want to move the function's entry block.
98   if (!LoopExit->getPrevNode())
99     return false;
100   if (blockIsBefore(Predecessor, LoopExit))
101     return false;
102   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
103                     << Predecessor->getFullName() << " to "
104                     << LoopExit->getFullName() << "\n");
105 
106   // Make sure that moving the target block doesn't cause any of its WLSs
107   // that were previously not backwards to become backwards
108   bool CanMove = true;
109   MachineInstr *WlsInLoopExit = findWLSInBlock(LoopExit);
110   if (WlsInLoopExit) {
111     // An example loop structure where the LoopExit can't be moved, since
112     // bb1's WLS will become backwards once it's moved after bb3
113     // bb1:          - LoopExit
114     //      WLS bb2
115     // bb2:          - LoopExit2
116     //      ...
117     // bb3:          - Predecessor
118     //      WLS bb1
119     // bb4:          - Header
120     MachineBasicBlock *LoopExit2 = WlsInLoopExit->getOperand(2).getMBB();
121     // If the WLS from LoopExit to LoopExit2 is already backwards then
122     // moving LoopExit won't affect it, so it can be moved. If LoopExit2 is
123     // after the Predecessor then moving will keep it as a forward branch, so it
124     // can be moved. If LoopExit2 is between the Predecessor and LoopExit then
125     // moving LoopExit will make it a backwards branch, so it can't be moved
126     // since we'd fix one and introduce one backwards branch.
127     // TODO: Analyse the blocks to make a decision if it would be worth
128     // moving LoopExit even if LoopExit2 is between the Predecessor and
129     // LoopExit.
130     if (!blockIsBefore(LoopExit2, LoopExit) &&
131         (LoopExit2 == Predecessor || blockIsBefore(LoopExit2, Predecessor))) {
132       LLVM_DEBUG(dbgs() << DEBUG_PREFIX
133                         << "Can't move the target block as it would "
134                            "introduce a new backwards WLS branch\n");
135       CanMove = false;
136     }
137   }
138 
139   if (CanMove) {
140     // Make sure no LEs become forwards.
141     // An example loop structure where the LoopExit can't be moved, since
142     // bb2's LE will become forwards once bb1 is moved after bb3.
143     // bb1:           - LoopExit
144     // bb2:
145     //      LE  bb1  - Terminator
146     // bb3:          - Predecessor
147     //      WLS bb1
148     // bb4:          - Header
149     for (auto It = LoopExit->getIterator(); It != Predecessor->getIterator();
150          It++) {
151       MachineBasicBlock *MBB = &*It;
152       for (auto &Terminator : MBB->terminators()) {
153         if (Terminator.getOpcode() != ARM::t2LoopEnd &&
154             Terminator.getOpcode() != ARM::t2LoopEndDec)
155           continue;
156         MachineBasicBlock *LETarget = Terminator.getOperand(2).getMBB();
157         // The LE will become forwards branching if it branches to LoopExit
158         // which isn't allowed by the architecture, so we should avoid
159         // introducing these.
160         // TODO: Analyse the blocks to make a decision if it would be worth
161         // moving LoopExit even if we'd introduce a forwards LE
162         if (LETarget == LoopExit) {
163           LLVM_DEBUG(dbgs() << DEBUG_PREFIX
164                             << "Can't move the target block as it would "
165                                "introduce a new forwards LE branch\n");
166           CanMove = false;
167           break;
168         }
169       }
170     }
171   }
172 
173   if (CanMove)
174     moveBasicBlock(LoopExit, Predecessor);
175 
176   return CanMove;
177 }
178 
179 /// Updates ordering (of WLS BB and their loopExits) in inner loops first
180 /// Returns true if any change was made in any of the loops
181 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
182   bool Changed = false;
183   for (auto *InnerML : *ML)
184     Changed |= processPostOrderLoops(InnerML);
185   return Changed | fixBackwardsWLS(ML);
186 }
187 
188 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
189   if (skipFunction(MF.getFunction()))
190     return false;
191   const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
192   if (!ST.hasLOB())
193     return false;
194   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
195   MLI = &getAnalysis<MachineLoopInfo>();
196   TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
197   BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
198   MF.RenumberBlocks();
199   BBUtils->computeAllBlockSizes();
200   BBUtils->adjustBBOffsetsAfter(&MF.front());
201   bool Changed = false;
202 
203   // Find loops with a backwards branching WLS and fix if possible.
204   for (auto *ML : *MLI)
205     Changed |= processPostOrderLoops(ML);
206 
207   return Changed;
208 }
209 
210 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
211                                       MachineBasicBlock *Other) {
212   return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
213 }
214 
215 /// Moves a given MBB to be positioned after another MBB while maintaining
216 /// existing control flow
217 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
218                                        MachineBasicBlock *After) {
219   LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " after "
220                     << After->getName() << "\n");
221   MachineBasicBlock *BBPrevious = BB->getPrevNode();
222   assert(BBPrevious && "Cannot move the function entry basic block");
223   MachineBasicBlock *AfterNext = After->getNextNode();
224   MachineBasicBlock *BBNext = BB->getNextNode();
225 
226   BB->moveAfter(After);
227 
228   // Since only the blocks are to be moved around (but the control flow must
229   // not change), if there were any fall-throughs (to/from adjacent blocks),
230   // replace with unconditional branch to the fall through block.
231   auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
232     LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
233                       << From->getName() << " to " << To->getName() << "\n");
234     assert(From->isSuccessor(To) &&
235            "'To' is expected to be a successor of 'From'");
236     MachineInstr &Terminator = *(--From->terminators().end());
237     if (!Terminator.isUnconditionalBranch()) {
238       // The BB doesn't have an unconditional branch so it relied on
239       // fall-through. Fix by adding an unconditional branch to the moved BB.
240       MachineInstrBuilder MIB =
241           BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
242       MIB.addMBB(To);
243       MIB.addImm(ARMCC::CondCodes::AL);
244       MIB.addReg(ARM::NoRegister);
245       LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
246                         << From->getName() << " to " << To->getName() << ": "
247                         << *MIB.getInstr());
248     }
249   };
250 
251   // Fix fall-through to the moved BB from the one that used to be before it.
252   if (BBPrevious->isSuccessor(BB))
253     FixFallthrough(BBPrevious, BB);
254   // Fix fall through from the destination BB to the one that used to follow.
255   if (AfterNext && After->isSuccessor(AfterNext))
256     FixFallthrough(After, AfterNext);
257   // Fix fall through from the moved BB to the one that used to follow.
258   if (BBNext && BB->isSuccessor(BBNext))
259     FixFallthrough(BB, BBNext);
260 
261   BBUtils->adjustBBOffsetsAfter(After);
262 }
263