LLVM 17.0.0git
BreakFalseDeps.cpp
Go to the documentation of this file.
1//==- llvm/CodeGen/BreakFalseDeps.cpp - Break False Dependency Fix -*- C++ -*==//
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/// \file Break False Dependency pass.
10///
11/// Some instructions have false dependencies which cause unnecessary stalls.
12/// For example, instructions may write part of a register and implicitly
13/// need to read the other parts of the register. This may cause unwanted
14/// stalls preventing otherwise unrelated instructions from executing in
15/// parallel in an out-of-order CPU.
16/// This pass is aimed at identifying and avoiding these dependencies.
17//
18//===----------------------------------------------------------------------===//
19
26#include "llvm/MC/MCInstrDesc.h"
27#include "llvm/MC/MCRegister.h"
29#include "llvm/Support/Debug.h"
30
31using namespace llvm;
32
33namespace llvm {
34
36private:
38 const TargetInstrInfo *TII;
39 const TargetRegisterInfo *TRI;
40 RegisterClassInfo RegClassInfo;
41
42 /// List of undefined register reads in this block in forward order.
43 std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
44
45 /// Storage for register unit liveness.
47
49
50public:
51 static char ID; // Pass identification, replacement for typeid
52
55 }
56
57 void getAnalysisUsage(AnalysisUsage &AU) const override {
58 AU.setPreservesAll();
61 }
62
63 bool runOnMachineFunction(MachineFunction &MF) override;
64
68 }
69
70private:
71 /// Process he given basic block.
72 void processBasicBlock(MachineBasicBlock *MBB);
73
74 /// Update def-ages for registers defined by MI.
75 /// Also break dependencies on partial defs and undef uses.
76 void processDefs(MachineInstr *MI);
77
78 /// Helps avoid false dependencies on undef registers by updating the
79 /// machine instructions' undef operand to use a register that the instruction
80 /// is truly dependent on, or use a register with clearance higher than Pref.
81 /// Returns true if it was able to find a true dependency, thus not requiring
82 /// a dependency breaking instruction regardless of clearance.
83 bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
84 unsigned Pref);
85
86 /// Return true to if it makes sense to break dependence on a partial
87 /// def or undef use.
88 bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);
89
90 /// Break false dependencies on undefined register reads.
91 /// Walk the block backward computing precise liveness. This is expensive, so
92 /// we only do it on demand. Note that the occurrence of undefined register
93 /// reads that should be broken is very rare, but when they occur we may have
94 /// many in a single block.
95 void processUndefReads(MachineBasicBlock *);
96};
97
98} // namespace llvm
99
100#define DEBUG_TYPE "break-false-deps"
101
102char BreakFalseDeps::ID = 0;
103INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
106
108
109bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
110 unsigned Pref) {
111
112 // We can't change tied operands.
113 if (MI->isRegTiedToDefOperand(OpIdx))
114 return false;
115
116 MachineOperand &MO = MI->getOperand(OpIdx);
117 assert(MO.isUndef() && "Expected undef machine operand");
118
119 // We can't change registers that aren't renamable.
120 if (!MO.isRenamable())
121 return false;
122
123 MCRegister OriginalReg = MO.getReg().asMCReg();
124
125 // Update only undef operands that have reg units that are mapped to one root.
126 for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) {
127 unsigned NumRoots = 0;
128 for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) {
129 NumRoots++;
130 if (NumRoots > 1)
131 return false;
132 }
133 }
134
135 // Get the undef operand's register class
136 const TargetRegisterClass *OpRC =
137 TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
138 assert(OpRC && "Not a valid register class");
139
140 // If the instruction has a true dependency, we can hide the false depdency
141 // behind it.
142 for (MachineOperand &CurrMO : MI->operands()) {
143 if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
144 !OpRC->contains(CurrMO.getReg()))
145 continue;
146 // We found a true dependency - replace the undef register with the true
147 // dependency.
148 MO.setReg(CurrMO.getReg());
149 return true;
150 }
151
152 // Go over all registers in the register class and find the register with
153 // max clearance or clearance higher than Pref.
154 unsigned MaxClearance = 0;
155 unsigned MaxClearanceReg = OriginalReg;
156 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
157 for (MCPhysReg Reg : Order) {
158 unsigned Clearance = RDA->getClearance(MI, Reg);
159 if (Clearance <= MaxClearance)
160 continue;
161 MaxClearance = Clearance;
162 MaxClearanceReg = Reg;
163
164 if (MaxClearance > Pref)
165 break;
166 }
167
168 // Update the operand if we found a register with better clearance.
169 if (MaxClearanceReg != OriginalReg)
170 MO.setReg(MaxClearanceReg);
171
172 return false;
173}
174
175bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
176 unsigned Pref) {
177 MCRegister Reg = MI->getOperand(OpIdx).getReg().asMCReg();
178 unsigned Clearance = RDA->getClearance(MI, Reg);
179 LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
180
181 if (Pref > Clearance) {
182 LLVM_DEBUG(dbgs() << ": Break dependency.\n");
183 return true;
184 }
185 LLVM_DEBUG(dbgs() << ": OK .\n");
186 return false;
187}
188
189void BreakFalseDeps::processDefs(MachineInstr *MI) {
190 assert(!MI->isDebugInstr() && "Won't process debug values");
191
192 const MCInstrDesc &MCID = MI->getDesc();
193
194 // Break dependence on undef uses. Do this before updating LiveRegs below.
195 // This can remove a false dependence with no additional instructions.
196 for (unsigned i = MCID.getNumDefs(), e = MCID.getNumOperands(); i != e; ++i) {
197 MachineOperand &MO = MI->getOperand(i);
198 if (!MO.isReg() || !MO.getReg() || !MO.isUse() || !MO.isUndef())
199 continue;
200
201 unsigned Pref = TII->getUndefRegClearance(*MI, i, TRI);
202 if (Pref) {
203 bool HadTrueDependency = pickBestRegisterForUndef(MI, i, Pref);
204 // We don't need to bother trying to break a dependency if this
205 // instruction has a true dependency on that register through another
206 // operand - we'll have to wait for it to be available regardless.
207 if (!HadTrueDependency && shouldBreakDependence(MI, i, Pref))
208 UndefReads.push_back(std::make_pair(MI, i));
209 }
210 }
211
212 // The code below allows the target to create a new instruction to break the
213 // dependence. That opposes the goal of minimizing size, so bail out now.
214 if (MF->getFunction().hasMinSize())
215 return;
216
217 for (unsigned i = 0,
218 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
219 i != e; ++i) {
220 MachineOperand &MO = MI->getOperand(i);
221 if (!MO.isReg() || !MO.getReg())
222 continue;
223 if (MO.isUse())
224 continue;
225 // Check clearance before partial register updates.
226 unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
227 if (Pref && shouldBreakDependence(MI, i, Pref))
228 TII->breakPartialRegDependency(*MI, i, TRI);
229 }
230}
231
232void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
233 if (UndefReads.empty())
234 return;
235
236 // The code below allows the target to create a new instruction to break the
237 // dependence. That opposes the goal of minimizing size, so bail out now.
238 if (MF->getFunction().hasMinSize())
239 return;
240
241 // Collect this block's live out register units.
242 LiveRegSet.init(*TRI);
243 // We do not need to care about pristine registers as they are just preserved
244 // but not actually used in the function.
245 LiveRegSet.addLiveOutsNoPristines(*MBB);
246
247 MachineInstr *UndefMI = UndefReads.back().first;
248 unsigned OpIdx = UndefReads.back().second;
249
250 for (MachineInstr &I : llvm::reverse(*MBB)) {
251 // Update liveness, including the current instruction's defs.
252 LiveRegSet.stepBackward(I);
253
254 if (UndefMI == &I) {
255 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
256 TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
257
258 UndefReads.pop_back();
259 if (UndefReads.empty())
260 return;
261
262 UndefMI = UndefReads.back().first;
263 OpIdx = UndefReads.back().second;
264 }
265 }
266}
267
268void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
269 UndefReads.clear();
270 // If this block is not done, it makes little sense to make any decisions
271 // based on clearance information. We need to make a second pass anyway,
272 // and by then we'll have better information, so we can avoid doing the work
273 // to try and break dependencies now.
274 for (MachineInstr &MI : *MBB) {
275 if (!MI.isDebugInstr())
276 processDefs(&MI);
277 }
278 processUndefReads(MBB);
279}
280
282 if (skipFunction(mf.getFunction()))
283 return false;
284 MF = &mf;
285 TII = MF->getSubtarget().getInstrInfo();
286 TRI = MF->getSubtarget().getRegisterInfo();
287 RDA = &getAnalysis<ReachingDefAnalysis>();
288
289 RegClassInfo.runOnMachineFunction(mf);
290
291 LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
292
293 // Traverse the basic blocks.
294 for (MachineBasicBlock &MBB : mf) {
295 processBasicBlock(&MBB);
296 }
297
298 return false;
299}
MachineBasicBlock & MBB
#define DEBUG_TYPE
#define LLVM_DEBUG(X)
Definition: Debug.h:101
IRTranslator LLVM IR MI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define I(x, y, z)
Definition: MD5.cpp:58
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFunctionProperties getRequiredProperties() const override
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:174
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:641
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
A set of live virtual registers and physical register units.
LaneBitmask contains(Register Reg) const
void init(const MachineRegisterInfo &MRI)
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:237
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:247
MCRegUnitRootIterator enumerates the root registers of a register unit.
bool isValid() const
Check if the iterator is at the end of the list.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
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.
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:68
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
bool isRenamable() const
isRenamable - Returns true if this register may be renamed, i.e.
Register getReg() const
getReg - Returns the register number.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class provides the reaching def analysis.
int getClearance(MachineInstr *MI, MCRegister PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
TargetInstrInfo - Interface to description of machine instruction set.
virtual unsigned getPartialRegUpdateClearance(const MachineInstr &MI, unsigned OpNum, const TargetRegisterInfo *TRI) const
Returns the preferred minimum clearance before an instruction with an unwanted partial register updat...
virtual unsigned getUndefRegClearance(const MachineInstr &MI, unsigned OpNum, const TargetRegisterInfo *TRI) const
Return the minimum clearance before an instruction that reads an unused register.
virtual void breakPartialRegDependency(MachineInstr &MI, unsigned OpNum, const TargetRegisterInfo *TRI) const
Insert a dependency-breaking instruction before MI to eliminate an unwanted dependency on OpNum.
virtual const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum,...
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void initializeBreakFalseDepsPass(PassRegistry &)
FunctionPass * createBreakFalseDeps()
Creates Break False Dependencies pass.