LLVM  10.0.0svn
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 exmaple, instructions that only 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 depepndencies when
17 /// possible.
18 //
19 //===----------------------------------------------------------------------===//
20 
27 
28 
29 using namespace llvm;
30 
31 namespace llvm {
32 
34 private:
35  MachineFunction *MF;
36  const TargetInstrInfo *TII;
37  const TargetRegisterInfo *TRI;
38  RegisterClassInfo RegClassInfo;
39 
40  /// List of undefined register reads in this block in forward order.
41  std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
42 
43  /// Storage for register unit liveness.
45 
47 
48 public:
49  static char ID; // Pass identification, replacement for typeid
50 
53  }
54 
55  void getAnalysisUsage(AnalysisUsage &AU) const override {
56  AU.setPreservesAll();
59  }
60 
61  bool runOnMachineFunction(MachineFunction &MF) override;
62 
66  }
67 
68 private:
69  /// Process he given basic block.
70  void processBasicBlock(MachineBasicBlock *MBB);
71 
72  /// Update def-ages for registers defined by MI.
73  /// Also break dependencies on partial defs and undef uses.
74  void processDefs(MachineInstr *MI);
75 
76  /// Helps avoid false dependencies on undef registers by updating the
77  /// machine instructions' undef operand to use a register that the instruction
78  /// is truly dependent on, or use a register with clearance higher than Pref.
79  /// Returns true if it was able to find a true dependency, thus not requiring
80  /// a dependency breaking instruction regardless of clearance.
81  bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
82  unsigned Pref);
83 
84  /// Return true to if it makes sense to break dependence on a partial
85  /// def or undef use.
86  bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);
87 
88  /// Break false dependencies on undefined register reads.
89  /// Walk the block backward computing precise liveness. This is expensive, so
90  /// we only do it on demand. Note that the occurrence of undefined register
91  /// reads that should be broken is very rare, but when they occur we may have
92  /// many in a single block.
93  void processUndefReads(MachineBasicBlock *);
94 };
95 
96 } // namespace llvm
97 
98 #define DEBUG_TYPE "break-false-deps"
99 
100 char BreakFalseDeps::ID = 0;
101 INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
103 INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
104 
106 
107 bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
108  unsigned Pref) {
109  MachineOperand &MO = MI->getOperand(OpIdx);
110  assert(MO.isUndef() && "Expected undef machine operand");
111 
112  unsigned OriginalReg = MO.getReg();
113 
114  // Update only undef operands that have reg units that are mapped to one root.
115  for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) {
116  unsigned NumRoots = 0;
117  for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) {
118  NumRoots++;
119  if (NumRoots > 1)
120  return false;
121  }
122  }
123 
124  // Get the undef operand's register class
125  const TargetRegisterClass *OpRC =
126  TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
127 
128  // If the instruction has a true dependency, we can hide the false depdency
129  // behind it.
130  for (MachineOperand &CurrMO : MI->operands()) {
131  if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
132  !OpRC->contains(CurrMO.getReg()))
133  continue;
134  // We found a true dependency - replace the undef register with the true
135  // dependency.
136  MO.setReg(CurrMO.getReg());
137  return true;
138  }
139 
140  // Go over all registers in the register class and find the register with
141  // max clearance or clearance higher than Pref.
142  unsigned MaxClearance = 0;
143  unsigned MaxClearanceReg = OriginalReg;
144  ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
145  for (MCPhysReg Reg : Order) {
146  unsigned Clearance = RDA->getClearance(MI, Reg);
147  if (Clearance <= MaxClearance)
148  continue;
149  MaxClearance = Clearance;
150  MaxClearanceReg = Reg;
151 
152  if (MaxClearance > Pref)
153  break;
154  }
155 
156  // Update the operand if we found a register with better clearance.
157  if (MaxClearanceReg != OriginalReg)
158  MO.setReg(MaxClearanceReg);
159 
160  return false;
161 }
162 
163 bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
164  unsigned Pref) {
165  unsigned reg = MI->getOperand(OpIdx).getReg();
166  unsigned Clearance = RDA->getClearance(MI, reg);
167  LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
168 
169  if (Pref > Clearance) {
170  LLVM_DEBUG(dbgs() << ": Break dependency.\n");
171  return true;
172  }
173  LLVM_DEBUG(dbgs() << ": OK .\n");
174  return false;
175 }
176 
177 void BreakFalseDeps::processDefs(MachineInstr *MI) {
178  assert(!MI->isDebugInstr() && "Won't process debug values");
179 
180  // Break dependence on undef uses. Do this before updating LiveRegs below.
181  unsigned OpNum;
182  unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
183  if (Pref) {
184  bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
185  // We don't need to bother trying to break a dependency if this
186  // instruction has a true dependency on that register through another
187  // operand - we'll have to wait for it to be available regardless.
188  if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
189  UndefReads.push_back(std::make_pair(MI, OpNum));
190  }
191 
192  const MCInstrDesc &MCID = MI->getDesc();
193  for (unsigned i = 0,
194  e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
195  i != e; ++i) {
196  MachineOperand &MO = MI->getOperand(i);
197  if (!MO.isReg() || !MO.getReg())
198  continue;
199  if (MO.isUse())
200  continue;
201  // Check clearance before partial register updates.
202  unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
203  if (Pref && shouldBreakDependence(MI, i, Pref))
204  TII->breakPartialRegDependency(*MI, i, TRI);
205  }
206 }
207 
208 void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
209  if (UndefReads.empty())
210  return;
211 
212  // Collect this block's live out register units.
213  LiveRegSet.init(*TRI);
214  // We do not need to care about pristine registers as they are just preserved
215  // but not actually used in the function.
216  LiveRegSet.addLiveOutsNoPristines(*MBB);
217 
218  MachineInstr *UndefMI = UndefReads.back().first;
219  unsigned OpIdx = UndefReads.back().second;
220 
221  for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
222  // Update liveness, including the current instruction's defs.
223  LiveRegSet.stepBackward(I);
224 
225  if (UndefMI == &I) {
226  if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
227  TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
228 
229  UndefReads.pop_back();
230  if (UndefReads.empty())
231  return;
232 
233  UndefMI = UndefReads.back().first;
234  OpIdx = UndefReads.back().second;
235  }
236  }
237 }
238 
239 void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
240  UndefReads.clear();
241  // If this block is not done, it makes little sense to make any decisions
242  // based on clearance information. We need to make a second pass anyway,
243  // and by then we'll have better information, so we can avoid doing the work
244  // to try and break dependencies now.
245  for (MachineInstr &MI : *MBB) {
246  if (!MI.isDebugInstr())
247  processDefs(&MI);
248  }
249  processUndefReads(MBB);
250 }
251 
253  if (skipFunction(mf.getFunction()))
254  return false;
255  MF = &mf;
256  TII = MF->getSubtarget().getInstrInfo();
257  TRI = MF->getSubtarget().getRegisterInfo();
258  RDA = &getAnalysis<ReachingDefAnalysis>();
259 
260  RegClassInfo.runOnMachineFunction(mf);
261 
262  LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
263 
264  // Traverse the basic blocks.
265  for (MachineBasicBlock &MBB : mf) {
266  processBasicBlock(&MBB);
267  }
268 
269  return false;
270 }
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
#define DEBUG_TYPE
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool contains(unsigned Reg) const
Return true if the specified register is included in this register class.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:164
unsigned Reg
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:461
This class provides the reaching def analysis.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
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...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
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...
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:408
MCRegUnitRootIterator enumerates the root registers of a register unit.
LaneBitmask contains(unsigned Reg) const
virtual const TargetInstrInfo * getInstrInfo() const
reverse_iterator rend()
reverse_iterator rbegin()
void initializeBreakFalseDepsPass(PassRegistry &)
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
void init(const MachineRegisterInfo &MRI)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
FunctionPass * createBreakFalseDeps()
Creates Break False Dependencies pass.
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
A set of live virtual registers and physical register units.
MachineFunctionProperties getRequiredProperties() const override
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
bool isDebugInstr() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MachineOperand class - Representation of each machine instruction operand.
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:47
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:226
bool isVariadic(QueryType Type=IgnoreBundle) const
Return true if this instruction can have a variable number of operands.
Definition: MachineInstr.h:609
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void setPreservesAll()
Set by analyses that do not transform their input at all.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:64
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...
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
int getClearance(MachineInstr *MI, MCPhysReg PhysReg)
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:166
bool isValid() const
Check if the iterator is at the end of the list.
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
Properties which a MachineFunction may have at a given point in time.
virtual unsigned getUndefRegClearance(const MachineInstr &MI, unsigned &OpNum, const TargetRegisterInfo *TRI) const
Return the minimum clearance before an instruction that reads an unused register. ...