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;
ARMBlockPlacement()36 ARMBlockPlacement() : MachineFunctionPass(ID) {}
37
38 bool runOnMachineFunction(MachineFunction &MF) override;
39 void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before);
40 bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other);
41 bool fixBackwardsWLS(MachineLoop *ML);
42 bool processPostOrderLoops(MachineLoop *ML);
43
getAnalysisUsage(AnalysisUsage & AU) const44 void getAnalysisUsage(AnalysisUsage &AU) const override {
45 AU.setPreservesCFG();
46 AU.addRequired<MachineLoopInfo>();
47 MachineFunctionPass::getAnalysisUsage(AU);
48 }
49 };
50
51 } // namespace llvm
52
createARMBlockPlacementPass()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
findWLSInBlock(MachineBasicBlock * MBB)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.
findWLS(MachineLoop * ML)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 predecessor (ie. preheader or it's predecessor)
86 /// for a WLS and if its loopExit/target is before it.
87 /// If moving the predecessor won't convert a WLS (to the predecessor) from
88 /// a forward to a backward branching WLS, then move the predecessor block
89 /// to before the loopExit/target.
fixBackwardsWLS(MachineLoop * ML)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
98 // We don't want to move Preheader to before the function's entry block.
99 if (!LoopExit->getPrevNode())
100 return false;
101 if (blockIsBefore(Predecessor, LoopExit))
102 return false;
103 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Found a backwards WLS from "
104 << Predecessor->getFullName() << " to "
105 << LoopExit->getFullName() << "\n");
106
107 // Make sure no forward branching WLSs to the Predecessor become backwards
108 // branching. An example loop structure where the Predecessor can't be moved,
109 // since bb2's WLS will become forwards once bb3 is moved before/above bb1.
110 //
111 // bb1: - LoopExit
112 // bb2:
113 // WLS bb3
114 // bb3: - Predecessor
115 // WLS bb1
116 // bb4: - Header
117 for (auto It = ++LoopExit->getIterator(); It != Predecessor->getIterator();
118 ++It) {
119 MachineBasicBlock *MBB = &*It;
120 for (auto &Terminator : MBB->terminators()) {
121 if (Terminator.getOpcode() != ARM::t2WhileLoopStartLR)
122 continue;
123 MachineBasicBlock *WLSTarget = Terminator.getOperand(2).getMBB();
124 // TODO: Analyse the blocks to make a decision if it would be worth
125 // moving Preheader even if we'd introduce a backwards WLS
126 if (WLSTarget == Predecessor) {
127 LLVM_DEBUG(
128 dbgs() << DEBUG_PREFIX
129 << "Can't move Predecessor"
130 "block as it would convert a WLS from forward to a "
131 "backwards branching WLS\n");
132 return false;
133 }
134 }
135 }
136
137 moveBasicBlock(Predecessor, LoopExit);
138 return true;
139 }
140
141 /// Updates ordering (of WLS BB and their loopExits) in inner loops first
142 /// Returns true if any change was made in any of the loops
processPostOrderLoops(MachineLoop * ML)143 bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
144 bool Changed = false;
145 for (auto *InnerML : *ML)
146 Changed |= processPostOrderLoops(InnerML);
147 return Changed | fixBackwardsWLS(ML);
148 }
149
runOnMachineFunction(MachineFunction & MF)150 bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
151 if (skipFunction(MF.getFunction()))
152 return false;
153 const ARMSubtarget &ST = static_cast<const ARMSubtarget &>(MF.getSubtarget());
154 if (!ST.hasLOB())
155 return false;
156 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Running on " << MF.getName() << "\n");
157 MLI = &getAnalysis<MachineLoopInfo>();
158 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
159 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new ARMBasicBlockUtils(MF));
160 MF.RenumberBlocks();
161 BBUtils->computeAllBlockSizes();
162 BBUtils->adjustBBOffsetsAfter(&MF.front());
163 bool Changed = false;
164
165 // Find loops with a backwards branching WLS and fix if possible.
166 for (auto *ML : *MLI)
167 Changed |= processPostOrderLoops(ML);
168
169 return Changed;
170 }
171
blockIsBefore(MachineBasicBlock * BB,MachineBasicBlock * Other)172 bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
173 MachineBasicBlock *Other) {
174 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
175 }
176
177 // Moves a BasicBlock before another, without changing the control flow
moveBasicBlock(MachineBasicBlock * BB,MachineBasicBlock * Before)178 void ARMBlockPlacement::moveBasicBlock(MachineBasicBlock *BB,
179 MachineBasicBlock *Before) {
180 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Moving " << BB->getName() << " before "
181 << Before->getName() << "\n");
182 MachineBasicBlock *BBPrevious = BB->getPrevNode();
183 assert(BBPrevious && "Cannot move the function entry basic block");
184 MachineBasicBlock *BBNext = BB->getNextNode();
185
186 MachineBasicBlock *BeforePrev = Before->getPrevNode();
187 assert(BeforePrev &&
188 "Cannot move the given block to before the function entry block");
189 MachineFunction *F = BB->getParent();
190 BB->moveBefore(Before);
191
192 // Since only the blocks are to be moved around (but the control flow must
193 // not change), if there were any fall-throughs (to/from adjacent blocks),
194 // replace with unconditional branch to the fall through block.
195 auto FixFallthrough = [&](MachineBasicBlock *From, MachineBasicBlock *To) {
196 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Checking for fallthrough from "
197 << From->getName() << " to " << To->getName() << "\n");
198 assert(From->isSuccessor(To) &&
199 "'To' is expected to be a successor of 'From'");
200 MachineInstr &Terminator = *(--From->terminators().end());
201 if (!Terminator.isUnconditionalBranch()) {
202 // The BB doesn't have an unconditional branch so it relied on
203 // fall-through. Fix by adding an unconditional branch to the moved BB.
204 MachineInstrBuilder MIB =
205 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
206 MIB.addMBB(To);
207 MIB.addImm(ARMCC::CondCodes::AL);
208 MIB.addReg(ARM::NoRegister);
209 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Adding unconditional branch from "
210 << From->getName() << " to " << To->getName() << ": "
211 << *MIB.getInstr());
212 }
213 };
214
215 // Fix fall-through to the moved BB from the one that used to be before it.
216 if (BBPrevious->isSuccessor(BB))
217 FixFallthrough(BBPrevious, BB);
218 // Fix fall through from the destination BB to the one that used to before it.
219 if (BeforePrev->isSuccessor(Before))
220 FixFallthrough(BeforePrev, Before);
221 // Fix fall through from the moved BB to the one that used to follow.
222 if (BBNext && BB->isSuccessor(BBNext))
223 FixFallthrough(BB, BBNext);
224
225 F->RenumberBlocks();
226 BBUtils->computeAllBlockSizes();
227 BBUtils->adjustBBOffsetsAfter(&F->front());
228 }
229