LLVM 19.0.0git
ARMBlockPlacement.cpp
Go to the documentation of this file.
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"
23
24using namespace llvm;
25
26#define DEBUG_TYPE "arm-block-placement"
27#define DEBUG_PREFIX "ARM Block Placement: "
28
29namespace llvm {
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;
41
42 bool runOnMachineFunction(MachineFunction &MF) override;
48
49 void getAnalysisUsage(AnalysisUsage &AU) const override {
52 }
53};
54
55} // namespace llvm
56
58 return new ARMBlockPlacement();
59}
60
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(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.
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.
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
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
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.
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
207 bool Changed = false;
208 for (auto *InnerML : *ML)
209 Changed |= processPostOrderLoops(InnerML);
210 return Changed | fixBackwardsWLS(ML);
211}
212
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<MachineLoopInfo>();
221 TII = static_cast<const ARMBaseInstrInfo *>(ST.getInstrInfo());
222 BBUtils = std::unique_ptr<ARMBasicBlockUtils>(new 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
242 return BBUtils->getOffsetOf(Other) > BBUtils->getOffsetOf(BB);
243}
244
245// Moves a BasicBlock before another, without changing the control flow
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.
278 BuildMI(From, Terminator.getDebugLoc(), TII->get(ARM::t2B));
279 MIB.addMBB(To);
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}
MachineBasicBlock & MBB
#define DEBUG_PREFIX
static MachineInstr * findWLS(MachineLoop *ML)
Find WhileLoopStart in the loop predecessor BB or otherwise in its only predecessor.
#define DEBUG_TYPE
BlockVerifier::State From
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define F(x, y, z)
Definition: MD5.cpp:55
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isPredicated(const MachineInstr &MI) const override
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool revertWhileToDoLoop(MachineInstr *WLS)
void moveBasicBlock(MachineBasicBlock *BB, MachineBasicBlock *Before)
bool fixBackwardsWLS(MachineLoop *ML)
Checks if loop has a backwards branching WLS, and if possible, fixes it.
bool blockIsBefore(MachineBasicBlock *BB, MachineBasicBlock *Other)
bool processPostOrderLoops(MachineLoop *ML)
Updates ordering (of WLS BB and their loopExits) in inner loops first Returns true if any change was ...
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:178
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
unsigned pred_size() const
void moveBefore(MachineBasicBlock *NewAfter)
Move 'this' block before or after the specified block.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
std::string getFullName() const
Return a formatted string to identify this block and its parent function.
iterator_range< iterator > terminators()
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Function & getFunction()
Return the LLVM function that this machine code represents.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void insert(iterator MBBI, MachineBasicBlock *MBB)
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly.
Representation of each machine instruction.
Definition: MachineInstr.h:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:543
MachineInstr * removeFromParent()
Unlink 'this' from the containing basic block, and return it without deleting it.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:326
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:553
int64_t getImm() const
MachineBasicBlock * getMBB() const
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
self_iterator getIterator()
Definition: ilist_node.h:109
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:316
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
static bool isIndirectBranchOpcode(int Opc)
static bool isJumpTableBranchOpcode(int Opc)
FunctionPass * createARMBlockPlacementPass()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void RevertWhileLoopStartLR(MachineInstr *MI, const TargetInstrInfo *TII, unsigned BrOpc=ARM::t2Bcc, bool UseCmp=false)
@ Other
Any other memory.
static bool isUncondBranchOpcode(int Opc)
MachineBasicBlock * getWhileLoopStartTargetBB(const MachineInstr &MI)
static bool isWhileLoopStart(const MachineInstr &MI)
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().