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 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 
27 
28 using namespace llvm;
29 
30 namespace llvm {
31 
33 private:
34  MachineFunction *MF;
35  const TargetInstrInfo *TII;
36  const TargetRegisterInfo *TRI;
37  RegisterClassInfo RegClassInfo;
38 
39  /// List of undefined register reads in this block in forward order.
40  std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
41 
42  /// Storage for register unit liveness.
44 
46 
47 public:
48  static char ID; // Pass identification, replacement for typeid
49 
52  }
53 
54  void getAnalysisUsage(AnalysisUsage &AU) const override {
55  AU.setPreservesAll();
58  }
59 
60  bool runOnMachineFunction(MachineFunction &MF) override;
61 
65  }
66 
67 private:
68  /// Process he given basic block.
69  void processBasicBlock(MachineBasicBlock *MBB);
70 
71  /// Update def-ages for registers defined by MI.
72  /// Also break dependencies on partial defs and undef uses.
73  void processDefs(MachineInstr *MI);
74 
75  /// Helps avoid false dependencies on undef registers by updating the
76  /// machine instructions' undef operand to use a register that the instruction
77  /// is truly dependent on, or use a register with clearance higher than Pref.
78  /// Returns true if it was able to find a true dependency, thus not requiring
79  /// a dependency breaking instruction regardless of clearance.
80  bool pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
81  unsigned Pref);
82 
83  /// Return true to if it makes sense to break dependence on a partial
84  /// def or undef use.
85  bool shouldBreakDependence(MachineInstr *, unsigned OpIdx, unsigned Pref);
86 
87  /// Break false dependencies on undefined register reads.
88  /// Walk the block backward computing precise liveness. This is expensive, so
89  /// we only do it on demand. Note that the occurrence of undefined register
90  /// reads that should be broken is very rare, but when they occur we may have
91  /// many in a single block.
92  void processUndefReads(MachineBasicBlock *);
93 };
94 
95 } // namespace llvm
96 
97 #define DEBUG_TYPE "break-false-deps"
98 
99 char BreakFalseDeps::ID = 0;
100 INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
102 INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
103 
105 
106 bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
107  unsigned Pref) {
108  MachineOperand &MO = MI->getOperand(OpIdx);
109  assert(MO.isUndef() && "Expected undef machine operand");
110 
111  Register OriginalReg = MO.getReg();
112 
113  // Update only undef operands that have reg units that are mapped to one root.
114  for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) {
115  unsigned NumRoots = 0;
116  for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) {
117  NumRoots++;
118  if (NumRoots > 1)
119  return false;
120  }
121  }
122 
123  // Get the undef operand's register class
124  const TargetRegisterClass *OpRC =
125  TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
126 
127  // If the instruction has a true dependency, we can hide the false depdency
128  // behind it.
129  for (MachineOperand &CurrMO : MI->operands()) {
130  if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
131  !OpRC->contains(CurrMO.getReg()))
132  continue;
133  // We found a true dependency - replace the undef register with the true
134  // dependency.
135  MO.setReg(CurrMO.getReg());
136  return true;
137  }
138 
139  // Go over all registers in the register class and find the register with
140  // max clearance or clearance higher than Pref.
141  unsigned MaxClearance = 0;
142  unsigned MaxClearanceReg = OriginalReg;
143  ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
144  for (MCPhysReg Reg : Order) {
145  unsigned Clearance = RDA->getClearance(MI, Reg);
146  if (Clearance <= MaxClearance)
147  continue;
148  MaxClearance = Clearance;
149  MaxClearanceReg = Reg;
150 
151  if (MaxClearance > Pref)
152  break;
153  }
154 
155  // Update the operand if we found a register with better clearance.
156  if (MaxClearanceReg != OriginalReg)
157  MO.setReg(MaxClearanceReg);
158 
159  return false;
160 }
161 
162 bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
163  unsigned Pref) {
164  Register reg = MI->getOperand(OpIdx).getReg();
165  unsigned Clearance = RDA->getClearance(MI, reg);
166  LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
167 
168  if (Pref > Clearance) {
169  LLVM_DEBUG(dbgs() << ": Break dependency.\n");
170  return true;
171  }
172  LLVM_DEBUG(dbgs() << ": OK .\n");
173  return false;
174 }
175 
176 void BreakFalseDeps::processDefs(MachineInstr *MI) {
177  assert(!MI->isDebugInstr() && "Won't process debug values");
178 
179  // Break dependence on undef uses. Do this before updating LiveRegs below.
180  unsigned OpNum;
181  unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
182  if (Pref) {
183  bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
184  // We don't need to bother trying to break a dependency if this
185  // instruction has a true dependency on that register through another
186  // operand - we'll have to wait for it to be available regardless.
187  if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
188  UndefReads.push_back(std::make_pair(MI, OpNum));
189  }
190 
191  const MCInstrDesc &MCID = MI->getDesc();
192  for (unsigned i = 0,
193  e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
194  i != e; ++i) {
195  MachineOperand &MO = MI->getOperand(i);
196  if (!MO.isReg() || !MO.getReg())
197  continue;
198  if (MO.isUse())
199  continue;
200  // Check clearance before partial register updates.
201  unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
202  if (Pref && shouldBreakDependence(MI, i, Pref))
203  TII->breakPartialRegDependency(*MI, i, TRI);
204  }
205 }
206 
207 void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
208  if (UndefReads.empty())
209  return;
210 
211  // Collect this block's live out register units.
212  LiveRegSet.init(*TRI);
213  // We do not need to care about pristine registers as they are just preserved
214  // but not actually used in the function.
215  LiveRegSet.addLiveOutsNoPristines(*MBB);
216 
217  MachineInstr *UndefMI = UndefReads.back().first;
218  unsigned OpIdx = UndefReads.back().second;
219 
220  for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
221  // Update liveness, including the current instruction's defs.
222  LiveRegSet.stepBackward(I);
223 
224  if (UndefMI == &I) {
225  if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
226  TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
227 
228  UndefReads.pop_back();
229  if (UndefReads.empty())
230  return;
231 
232  UndefMI = UndefReads.back().first;
233  OpIdx = UndefReads.back().second;
234  }
235  }
236 }
237 
238 void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
239  UndefReads.clear();
240  // If this block is not done, it makes little sense to make any decisions
241  // based on clearance information. We need to make a second pass anyway,
242  // and by then we'll have better information, so we can avoid doing the work
243  // to try and break dependencies now.
244  for (MachineInstr &MI : *MBB) {
245  if (!MI.isDebugInstr())
246  processDefs(&MI);
247  }
248  processUndefReads(MBB);
249 }
250 
252  if (skipFunction(mf.getFunction()))
253  return false;
254  MF = &mf;
255  TII = MF->getSubtarget().getInstrInfo();
256  TRI = MF->getSubtarget().getRegisterInfo();
257  RDA = &getAnalysis<ReachingDefAnalysis>();
258 
259  RegClassInfo.runOnMachineFunction(mf);
260 
261  LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
262 
263  // Traverse the basic blocks.
264  for (MachineBasicBlock &MBB : mf) {
265  processBasicBlock(&MBB);
266  }
267 
268  return false;
269 }
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:178
unsigned Reg
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:477
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
void setReg(Register Reg)
Change the register this operand corresponds to.
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...
Definition: MCRegister.h:19
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:240
bool isVariadic(QueryType Type=IgnoreBundle) const
Return true if this instruction can have a variable number of operands.
Definition: MachineInstr.h:625
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...
#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.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
virtual unsigned getUndefRegClearance(const MachineInstr &MI, unsigned &OpNum, const TargetRegisterInfo *TRI) const
Return the minimum clearance before an instruction that reads an unused register. ...