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
24using namespace llvm;
25
26#define DEBUG_TYPE "arm-block-placement"
27#define DEBUG_PREFIX "ARM Block Placement: "
28
29namespace llvm {
30class ARMBlockPlacement : public MachineFunctionPass {
31private:
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
38public:
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<MachineLoopInfoWrapperPass>();
51 MachineFunctionPass::getAnalysisUsage(AU);
52 }
53};
54
55} // namespace llvm
56
57FunctionPass *llvm::createARMBlockPlacementPass() {
58 return new ARMBlockPlacement();
59}
60
61char ARMBlockPlacement::ID = 0;
62
63INITIALIZE_PASS(ARMBlockPlacement, DEBUG_TYPE, "ARM block placement", false,
64 false)
65
66static MachineInstr *findWLSInBlock(MachineBasicBlock *MBB) {
67 for (auto &Terminator : MBB->terminators()) {
68 if (isWhileLoopStart(MI: 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.
76static MachineInstr *findWLS(MachineLoop *ML) {
77 MachineBasicBlock *Predecessor = ML->getLoopPredecessor();
78 if (!Predecessor)
79 return nullptr;
80 MachineInstr *WlsInstr = findWLSInBlock(MBB: Predecessor);
81 if (WlsInstr)
82 return WlsInstr;
83 if (Predecessor->pred_size() == 1)
84 return findWLSInBlock(MBB: *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.
90bool 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(i: 1).setIsKill(false);
108 if (WLS->getOpcode() == ARM::t2WhileLoopStartTP)
109 WLS->getOperand(i: 2).setIsKill(false);
110
111 // Create the new block
112 MachineBasicBlock *NewBlock = Preheader->getParent()->CreateMachineBasicBlock(
113 BB: Preheader->getBasicBlock());
114 Preheader->getParent()->insert(MBBI: ++Preheader->getIterator(), MBB: NewBlock);
115 // Move the Br to it
116 Br->removeFromParent();
117 NewBlock->insert(I: NewBlock->end(), MI: Br);
118 // And setup the successors correctly.
119 Preheader->replaceSuccessor(Old: Br->getOperand(i: 0).getMBB(), New: NewBlock);
120 NewBlock->addSuccessor(Succ: Br->getOperand(i: 0).getMBB());
121
122 // Create a new DLS to replace the WLS
123 MachineInstrBuilder MIB =
124 BuildMI(BB&: *NewBlock, I: Br, MIMD: WLS->getDebugLoc(),
125 MCID: TII->get(Opcode: WLS->getOpcode() == ARM::t2WhileLoopStartTP
126 ? ARM::t2DoLoopStartTP
127 : ARM::t2DoLoopStart));
128 MIB.add(MO: WLS->getOperand(i: 0));
129 MIB.add(MO: WLS->getOperand(i: 1));
130 if (WLS->getOpcode() == ARM::t2WhileLoopStartTP)
131 MIB.add(MO: WLS->getOperand(i: 2));
132
133 LLVM_DEBUG(dbgs() << DEBUG_PREFIX
134 << "Reverting While Loop to Do Loop: " << *WLS << "\n");
135
136 RevertWhileLoopStartLR(MI: WLS, TII, BrOpc: ARM::t2Bcc, UseCmp: true);
137
138 LivePhysRegs LiveRegs;
139 computeAndAddLiveIns(LiveRegs, MBB&: *NewBlock);
140
141 Preheader->getParent()->RenumberBlocks();
142 BBUtils->computeAllBlockSizes();
143 BBUtils->adjustBBOffsetsAfter(MBB: 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.
154bool 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(MI: *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(BB: Predecessor, Other: 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(MI: Terminator))
186 continue;
187 MachineBasicBlock *WLSTarget = getWhileLoopStartTargetBB(MI: 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(Elt: WlsInstr);
195 return false;
196 }
197 }
198 }
199
200 moveBasicBlock(BB: Predecessor, Before: 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
206bool ARMBlockPlacement::processPostOrderLoops(MachineLoop *ML) {
207 bool Changed = false;
208 for (auto *InnerML : *ML)
209 Changed |= processPostOrderLoops(ML: InnerML);
210 return Changed | fixBackwardsWLS(ML);
211}
212
213bool ARMBlockPlacement::runOnMachineFunction(MachineFunction &MF) {
214 if (skipFunction(F: 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>(args&: MF);
223 MF.RenumberBlocks();
224 BBUtils->computeAllBlockSizes();
225 BBUtils->adjustBBOffsetsAfter(MBB: &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(WLS: WlsInstr);
236
237 return Changed;
238}
239
240bool ARMBlockPlacement::blockIsBefore(MachineBasicBlock *BB,
241 MachineBasicBlock *Other) {
242 return BBUtils->getOffsetOf(MBB: Other) > BBUtils->getOffsetOf(MBB: BB);
243}
244
245// Moves a BasicBlock before another, without changing the control flow
246void 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(NewAfter: 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(MI: Terminator) &&
270 (isUncondBranchOpcode(Opc: Terminator.getOpcode()) ||
271 isIndirectBranchOpcode(Opc: Terminator.getOpcode()) ||
272 isJumpTableBranchOpcode(Opc: 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(BB: From, MIMD: Terminator.getDebugLoc(), MCID: TII->get(Opcode: ARM::t2B));
279 MIB.addMBB(MBB: To);
280 MIB.addImm(Val: ARMCC::CondCodes::AL);
281 MIB.addReg(RegNo: 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(MBB: 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(MBB: 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(MBB: BBNext))
295 FixFallthrough(BB, BBNext);
296
297 F->RenumberBlocks();
298 BBUtils->computeAllBlockSizes();
299 BBUtils->adjustBBOffsetsAfter(MBB: BB);
300}
301