xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/BreakFalseDeps.cpp (revision 6966ac055c3b7a39266fb982493330df7a097997)
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 
21 #include "llvm/CodeGen/LivePhysRegs.h"
22 #include "llvm/CodeGen/MachineFunctionPass.h"
23 #include "llvm/CodeGen/ReachingDefAnalysis.h"
24 #include "llvm/CodeGen/RegisterClassInfo.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/TargetInstrInfo.h"
27 
28 
29 using namespace llvm;
30 
31 namespace llvm {
32 
33 class BreakFalseDeps : public MachineFunctionPass {
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.
44   LivePhysRegs LiveRegSet;
45 
46   ReachingDefAnalysis *RDA;
47 
48 public:
49   static char ID; // Pass identification, replacement for typeid
50 
51   BreakFalseDeps() : MachineFunctionPass(ID) {
52     initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry());
53   }
54 
55   void getAnalysisUsage(AnalysisUsage &AU) const override {
56     AU.setPreservesAll();
57     AU.addRequired<ReachingDefAnalysis>();
58     MachineFunctionPass::getAnalysisUsage(AU);
59   }
60 
61   bool runOnMachineFunction(MachineFunction &MF) override;
62 
63   MachineFunctionProperties getRequiredProperties() const override {
64     return MachineFunctionProperties().set(
65       MachineFunctionProperties::Property::NoVRegs);
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)
102 INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
103 INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
104 
105 FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }
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 
252 bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {
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 }
271