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 
25 #include "llvm/InitializePasses.h"
26 #include "llvm/MC/MCInstrDesc.h"
27 #include "llvm/MC/MCRegister.h"
28 #include "llvm/MC/MCRegisterInfo.h"
29 #include "llvm/Support/Debug.h"
30 
31 using namespace llvm;
32 
33 namespace llvm {
34 
36 private:
37  MachineFunction *MF;
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 
50 public:
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 
70 private:
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 
102 char BreakFalseDeps::ID = 0;
103 INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
106 
108 
109 bool 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 
175 bool 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 
189 void 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 
232 void 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 
268 void 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 }
i
i
Definition: README.txt:29
llvm::MCInstrDesc::getNumDefs
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:247
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::RegisterClassInfo::getOrder
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Definition: RegisterClassInfo.h:101
llvm::ReachingDefAnalysis
This class provides the reaching def analysis.
Definition: ReachingDefAnalysis.h:69
MCInstrDesc.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:95
llvm::FunctionPass::skipFunction
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:174
llvm::TargetInstrInfo::getUndefRegClearance
virtual unsigned getUndefRegClearance(const MachineInstr &MI, unsigned OpNum, const TargetRegisterInfo *TRI) const
Return the minimum clearance before an instruction that reads an unused register.
Definition: TargetInstrInfo.h:1805
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
RegisterClassInfo.h
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:127
llvm::BreakFalseDeps::getRequiredProperties
MachineFunctionProperties getRequiredProperties() const override
Definition: BreakFalseDeps.cpp:65
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:236
TargetInstrInfo.h
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:128
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::TargetInstrInfo::getPartialRegUpdateClearance
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...
Definition: TargetInstrInfo.h:1785
llvm::BreakFalseDeps
Definition: BreakFalseDeps.cpp:35
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineOperand::isRenamable
bool isRenamable() const
isRenamable - Returns true if this register may be renamed, i.e.
Definition: MachineOperand.cpp:119
llvm::TargetInstrInfo::getRegClass
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,...
Definition: TargetInstrInfo.cpp:46
llvm::TargetRegisterClass::contains
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
Definition: TargetRegisterInfo.h:96
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:376
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
false
Definition: StackSlotColoring.cpp:141
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:197
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
MCRegister.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MCRegUnitRootIterator::isValid
bool isValid() const
Check if the iterator is at the end of the list.
Definition: MCRegisterInfo.h:773
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:672
DEBUG_TYPE
#define DEBUG_TYPE
Definition: BreakFalseDeps.cpp:100
llvm::RegisterClassInfo::runOnMachineFunction
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
Definition: RegisterClassInfo.cpp:42
llvm::MachineOperand::isUndef
bool isUndef() const
Definition: MachineOperand.h:401
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:326
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BreakFalseDeps::BreakFalseDeps
BreakFalseDeps()
Definition: BreakFalseDeps.cpp:53
llvm::TargetInstrInfo::breakPartialRegDependency
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.
Definition: TargetInstrInfo.h:1828
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:31
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
MCRegisterInfo.h
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:29
llvm::LiveRegSet::init
void init(const MachineRegisterInfo &MRI)
Definition: RegisterPressure.cpp:225
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:366
llvm::Register::asMCReg
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
llvm::MachineFunction
Definition: MachineFunction.h:258
llvm::initializeBreakFalseDepsPass
void initializeBreakFalseDepsPass(PassRegistry &)
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::BreakFalseDeps::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: BreakFalseDeps.cpp:57
llvm::LiveRegSet
A set of live virtual registers and physical register units.
Definition: RegisterPressure.h:259
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::createBreakFalseDeps
FunctionPass * createBreakFalseDeps()
Creates Break False Dependencies pass.
Definition: BreakFalseDeps.cpp:107
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:638
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
ReachingDefAnalysis.h
llvm::BreakFalseDeps::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: BreakFalseDeps.cpp:281
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:680
llvm::MCRegUnitRootIterator
MCRegUnitRootIterator enumerates the root registers of a register unit.
Definition: MCRegisterInfo.h:754
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:56
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:484
llvm::Function::hasMinSize
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:641
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::ReachingDefAnalysis::getClearance
int getClearance(MachineInstr *MI, MCRegister PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
Definition: ReachingDefAnalysis.cpp:320
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
InitializePasses.h
llvm::MCInstrDesc::getNumOperands
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:237
Debug.h
llvm::LiveRegSet::contains
LaneBitmask contains(Register Reg) const
Definition: RegisterPressure.h:294
llvm::BreakFalseDeps::ID
static char ID
Definition: BreakFalseDeps.cpp:51
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
LivePhysRegs.h