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;
ARMBlockPlacement()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
getAnalysisUsage(AnalysisUsage & AU) const49 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.addRequired<MachineLoopInfoWrapperPass>();
51 MachineFunctionPass::getAnalysisUsage(AU);
52 }
53 };
54
55 } // namespace llvm
56
createARMBlockPlacementPass()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
findWLSInBlock(MachineBasicBlock * MBB)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.
findWLS(MachineLoop * ML)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.
revertWhileToDoLoop(MachineInstr * WLS)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.
fixBackwardsWLS(MachineLoop * ML)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
processPostOrderLoops(MachineLoop * ML)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
runOnMachineFunction(MachineFunction & MF)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<MachineLoopInfoWrapperPass>().getLI();
221 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
222 BBUtils = std::make_unique<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
blockIsBefore(MachineBasicBlock * BB,MachineBasicBlock * Other)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
moveBasicBlock(MachineBasicBlock * BB,MachineBasicBlock * Before)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