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
20 #include "llvm/CodeGen/LivePhysRegs.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineRegisterInfo.h"
23 #include "llvm/CodeGen/ReachingDefAnalysis.h"
24 #include "llvm/CodeGen/RegisterClassInfo.h"
25 #include "llvm/CodeGen/TargetInstrInfo.h"
26 #include "llvm/InitializePasses.h"
27 #include "llvm/Support/Debug.h"
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
BreakFalseDeps()51 BreakFalseDeps() : MachineFunctionPass(ID) {
52 initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry());
53 }
54
getAnalysisUsage(AnalysisUsage & AU) const55 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
getRequiredProperties() const63 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)
INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)102 INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
103 INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
104
105 FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }
106
pickBestRegisterForUndef(MachineInstr * MI,unsigned OpIdx,unsigned Pref)107 bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
108 unsigned Pref) {
109
110 // We can't change tied operands.
111 if (MI->isRegTiedToDefOperand(OpIdx))
112 return false;
113
114 MachineOperand &MO = MI->getOperand(OpIdx);
115 assert(MO.isUndef() && "Expected undef machine operand");
116
117 // We can't change registers that aren't renamable.
118 if (!MO.isRenamable())
119 return false;
120
121 Register OriginalReg = MO.getReg();
122
123 // Update only undef operands that have reg units that are mapped to one root.
124 for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); ++Unit) {
125 unsigned NumRoots = 0;
126 for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); ++Root) {
127 NumRoots++;
128 if (NumRoots > 1)
129 return false;
130 }
131 }
132
133 // Get the undef operand's register class
134 const TargetRegisterClass *OpRC =
135 TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
136
137 // If the instruction has a true dependency, we can hide the false depdency
138 // behind it.
139 for (MachineOperand &CurrMO : MI->operands()) {
140 if (!CurrMO.isReg() || CurrMO.isDef() || CurrMO.isUndef() ||
141 !OpRC->contains(CurrMO.getReg()))
142 continue;
143 // We found a true dependency - replace the undef register with the true
144 // dependency.
145 MO.setReg(CurrMO.getReg());
146 return true;
147 }
148
149 // Go over all registers in the register class and find the register with
150 // max clearance or clearance higher than Pref.
151 unsigned MaxClearance = 0;
152 unsigned MaxClearanceReg = OriginalReg;
153 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
154 for (MCPhysReg Reg : Order) {
155 unsigned Clearance = RDA->getClearance(MI, Reg);
156 if (Clearance <= MaxClearance)
157 continue;
158 MaxClearance = Clearance;
159 MaxClearanceReg = Reg;
160
161 if (MaxClearance > Pref)
162 break;
163 }
164
165 // Update the operand if we found a register with better clearance.
166 if (MaxClearanceReg != OriginalReg)
167 MO.setReg(MaxClearanceReg);
168
169 return false;
170 }
171
shouldBreakDependence(MachineInstr * MI,unsigned OpIdx,unsigned Pref)172 bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
173 unsigned Pref) {
174 Register reg = MI->getOperand(OpIdx).getReg();
175 unsigned Clearance = RDA->getClearance(MI, reg);
176 LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
177
178 if (Pref > Clearance) {
179 LLVM_DEBUG(dbgs() << ": Break dependency.\n");
180 return true;
181 }
182 LLVM_DEBUG(dbgs() << ": OK .\n");
183 return false;
184 }
185
processDefs(MachineInstr * MI)186 void BreakFalseDeps::processDefs(MachineInstr *MI) {
187 assert(!MI->isDebugInstr() && "Won't process debug values");
188
189 // Break dependence on undef uses. Do this before updating LiveRegs below.
190 // This can remove a false dependence with no additional instructions.
191 unsigned OpNum;
192 unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
193 if (Pref) {
194 bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
195 // We don't need to bother trying to break a dependency if this
196 // instruction has a true dependency on that register through another
197 // operand - we'll have to wait for it to be available regardless.
198 if (!HadTrueDependency && shouldBreakDependence(MI, OpNum, Pref))
199 UndefReads.push_back(std::make_pair(MI, OpNum));
200 }
201
202 // The code below allows the target to create a new instruction to break the
203 // dependence. That opposes the goal of minimizing size, so bail out now.
204 if (MF->getFunction().hasMinSize())
205 return;
206
207 const MCInstrDesc &MCID = MI->getDesc();
208 for (unsigned i = 0,
209 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
210 i != e; ++i) {
211 MachineOperand &MO = MI->getOperand(i);
212 if (!MO.isReg() || !MO.getReg())
213 continue;
214 if (MO.isUse())
215 continue;
216 // Check clearance before partial register updates.
217 unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
218 if (Pref && shouldBreakDependence(MI, i, Pref))
219 TII->breakPartialRegDependency(*MI, i, TRI);
220 }
221 }
222
processUndefReads(MachineBasicBlock * MBB)223 void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
224 if (UndefReads.empty())
225 return;
226
227 // The code below allows the target to create a new instruction to break the
228 // dependence. That opposes the goal of minimizing size, so bail out now.
229 if (MF->getFunction().hasMinSize())
230 return;
231
232 // Collect this block's live out register units.
233 LiveRegSet.init(*TRI);
234 // We do not need to care about pristine registers as they are just preserved
235 // but not actually used in the function.
236 LiveRegSet.addLiveOutsNoPristines(*MBB);
237
238 MachineInstr *UndefMI = UndefReads.back().first;
239 unsigned OpIdx = UndefReads.back().second;
240
241 for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
242 // Update liveness, including the current instruction's defs.
243 LiveRegSet.stepBackward(I);
244
245 if (UndefMI == &I) {
246 if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
247 TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
248
249 UndefReads.pop_back();
250 if (UndefReads.empty())
251 return;
252
253 UndefMI = UndefReads.back().first;
254 OpIdx = UndefReads.back().second;
255 }
256 }
257 }
258
processBasicBlock(MachineBasicBlock * MBB)259 void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
260 UndefReads.clear();
261 // If this block is not done, it makes little sense to make any decisions
262 // based on clearance information. We need to make a second pass anyway,
263 // and by then we'll have better information, so we can avoid doing the work
264 // to try and break dependencies now.
265 for (MachineInstr &MI : *MBB) {
266 if (!MI.isDebugInstr())
267 processDefs(&MI);
268 }
269 processUndefReads(MBB);
270 }
271
runOnMachineFunction(MachineFunction & mf)272 bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {
273 if (skipFunction(mf.getFunction()))
274 return false;
275 MF = &mf;
276 TII = MF->getSubtarget().getInstrInfo();
277 TRI = MF->getSubtarget().getRegisterInfo();
278 RDA = &getAnalysis<ReachingDefAnalysis>();
279
280 RegClassInfo.runOnMachineFunction(mf);
281
282 LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
283
284 // Traverse the basic blocks.
285 for (MachineBasicBlock &MBB : mf) {
286 processBasicBlock(&MBB);
287 }
288
289 return false;
290 }
291