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/ADT/DepthFirstIterator.h"
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/TargetInstrInfo.h"
26#include "llvm/InitializePasses.h"
27#include "llvm/MC/MCInstrDesc.h"
28#include "llvm/MC/MCRegister.h"
29#include "llvm/MC/MCRegisterInfo.h"
30#include "llvm/Support/Debug.h"
31
32using namespace llvm;
33
34namespace {
35
36class BreakFalseDeps : public MachineFunctionPass {
37private:
38 MachineFunction *MF = nullptr;
39 const TargetInstrInfo *TII = nullptr;
40 const TargetRegisterInfo *TRI = nullptr;
41 RegisterClassInfo RegClassInfo;
42
43 /// List of undefined register reads in this block in forward order.
44 std::vector<std::pair<MachineInstr *, unsigned>> UndefReads;
45
46 /// Storage for register unit liveness.
47 LivePhysRegs LiveRegSet;
48
49 ReachingDefInfo *RDI = nullptr;
50
51public:
52 static char ID; // Pass identification, replacement for typeid
53
54 BreakFalseDeps() : MachineFunctionPass(ID) {}
55
56 void getAnalysisUsage(AnalysisUsage &AU) const override {
57 AU.setPreservesAll();
58 AU.addRequired<ReachingDefInfoWrapperPass>();
59 MachineFunctionPass::getAnalysisUsage(AU);
60 }
61
62 bool runOnMachineFunction(MachineFunction &MF) override;
63
64 MachineFunctionProperties getRequiredProperties() const override {
65 return MachineFunctionProperties().setNoVRegs();
66 }
67
68private:
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
97
98#define DEBUG_TYPE "break-false-deps"
99
100char BreakFalseDeps::ID = 0;
101INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
102INITIALIZE_PASS_DEPENDENCY(ReachingDefInfoWrapperPass)
103INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
104
105FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }
106
107bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
108 unsigned Pref) {
109
110 // We can't change tied operands.
111 if (MI->isRegTiedToDefOperand(UseOpIdx: OpIdx))
112 return false;
113
114 MachineOperand &MO = MI->getOperand(i: 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 MCRegister OriginalReg = MO.getReg().asMCReg();
122
123 // Update only undef operands that have reg units that are mapped to one root.
124 for (MCRegUnit Unit : TRI->regunits(Reg: OriginalReg)) {
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 = TII->getRegClass(MCID: MI->getDesc(), OpNum: OpIdx);
135 assert(OpRC && "Not a valid register class");
136
137 // If the instruction has a true dependency, we can hide the false depdency
138 // behind it.
139 for (MachineOperand &CurrMO : MI->all_uses()) {
140 if (CurrMO.isUndef() || !OpRC->contains(Reg: CurrMO.getReg()))
141 continue;
142 // We found a true dependency - replace the undef register with the true
143 // dependency.
144 MO.setReg(CurrMO.getReg());
145 return true;
146 }
147
148 // Go over all registers in the register class and find the register with
149 // max clearance or clearance higher than Pref.
150 unsigned MaxClearance = 0;
151 unsigned MaxClearanceReg = OriginalReg;
152 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(RC: OpRC);
153 for (MCPhysReg Reg : Order) {
154 unsigned Clearance = RDI->getClearance(MI, Reg);
155 if (Clearance <= MaxClearance)
156 continue;
157 MaxClearance = Clearance;
158 MaxClearanceReg = Reg;
159
160 if (MaxClearance > Pref)
161 break;
162 }
163
164 // Update the operand if we found a register with better clearance.
165 if (MaxClearanceReg != OriginalReg)
166 MO.setReg(MaxClearanceReg);
167
168 return false;
169}
170
171bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
172 unsigned Pref) {
173 MCRegister Reg = MI->getOperand(i: OpIdx).getReg().asMCReg();
174 unsigned Clearance = RDI->getClearance(MI, Reg);
175 LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
176
177 if (Pref > Clearance) {
178 LLVM_DEBUG(dbgs() << ": Break dependency.\n");
179 return true;
180 }
181 LLVM_DEBUG(dbgs() << ": OK .\n");
182 return false;
183}
184
185void BreakFalseDeps::processDefs(MachineInstr *MI) {
186 assert(!MI->isDebugInstr() && "Won't process debug values");
187
188 const MCInstrDesc &MCID = MI->getDesc();
189
190 // Break dependence on undef uses. Do this before updating LiveRegs below.
191 // This can remove a false dependence with no additional instructions.
192 for (unsigned i = MCID.getNumDefs(), e = MCID.getNumOperands(); i != e; ++i) {
193 MachineOperand &MO = MI->getOperand(i);
194 if (!MO.isReg() || !MO.getReg() || !MO.isUse() || !MO.isUndef())
195 continue;
196
197 unsigned Pref = TII->getUndefRegClearance(MI: *MI, OpNum: i, TRI);
198 if (Pref) {
199 bool HadTrueDependency = pickBestRegisterForUndef(MI, OpIdx: i, Pref);
200 // We don't need to bother trying to break a dependency if this
201 // instruction has a true dependency on that register through another
202 // operand - we'll have to wait for it to be available regardless.
203 if (!HadTrueDependency && shouldBreakDependence(MI, OpIdx: i, Pref))
204 UndefReads.push_back(x: std::make_pair(x&: MI, y&: i));
205 }
206 }
207
208 // The code below allows the target to create a new instruction to break the
209 // dependence. That opposes the goal of minimizing size, so bail out now.
210 if (MF->getFunction().hasMinSize())
211 return;
212
213 for (unsigned i = 0,
214 e = MI->isVariadic() ? MI->getNumOperands() : MCID.getNumDefs();
215 i != e; ++i) {
216 MachineOperand &MO = MI->getOperand(i);
217 if (!MO.isReg() || !MO.getReg())
218 continue;
219 if (MO.isUse())
220 continue;
221 // Check clearance before partial register updates.
222 unsigned Pref = TII->getPartialRegUpdateClearance(MI: *MI, OpNum: i, TRI);
223 if (Pref && shouldBreakDependence(MI, OpIdx: i, Pref))
224 TII->breakPartialRegDependency(MI&: *MI, OpNum: i, TRI);
225 }
226}
227
228void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
229 if (UndefReads.empty())
230 return;
231
232 // The code below allows the target to create a new instruction to break the
233 // dependence. That opposes the goal of minimizing size, so bail out now.
234 if (MF->getFunction().hasMinSize())
235 return;
236
237 // Collect this block's live out register units.
238 LiveRegSet.init(TRI: *TRI);
239 // We do not need to care about pristine registers as they are just preserved
240 // but not actually used in the function.
241 LiveRegSet.addLiveOutsNoPristines(MBB: *MBB);
242
243 MachineInstr *UndefMI = UndefReads.back().first;
244 unsigned OpIdx = UndefReads.back().second;
245
246 for (MachineInstr &I : llvm::reverse(C&: *MBB)) {
247 // Update liveness, including the current instruction's defs.
248 LiveRegSet.stepBackward(MI: I);
249
250 if (UndefMI == &I) {
251 if (!LiveRegSet.contains(Reg: UndefMI->getOperand(i: OpIdx).getReg()))
252 TII->breakPartialRegDependency(MI&: *UndefMI, OpNum: OpIdx, TRI);
253
254 UndefReads.pop_back();
255 if (UndefReads.empty())
256 return;
257
258 UndefMI = UndefReads.back().first;
259 OpIdx = UndefReads.back().second;
260 }
261 }
262}
263
264void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
265 UndefReads.clear();
266 // If this block is not done, it makes little sense to make any decisions
267 // based on clearance information. We need to make a second pass anyway,
268 // and by then we'll have better information, so we can avoid doing the work
269 // to try and break dependencies now.
270 for (MachineInstr &MI : *MBB) {
271 if (!MI.isDebugInstr())
272 processDefs(MI: &MI);
273 }
274 processUndefReads(MBB);
275}
276
277bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {
278 if (skipFunction(F: mf.getFunction()))
279 return false;
280 MF = &mf;
281 TII = MF->getSubtarget().getInstrInfo();
282 TRI = MF->getSubtarget().getRegisterInfo();
283 RDI = &getAnalysis<ReachingDefInfoWrapperPass>().getRDI();
284
285 RegClassInfo.runOnMachineFunction(MF: mf, /*Rev=*/true);
286
287 LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
288
289 // Skip Dead blocks due to ReachingDefAnalysis has no idea about instructions
290 // in them.
291 df_iterator_default_set<MachineBasicBlock *> Reachable;
292 for (MachineBasicBlock *MBB : depth_first_ext(G: &mf, S&: Reachable))
293 (void)MBB /* Mark all reachable blocks */;
294
295 // Traverse the basic blocks.
296 for (MachineBasicBlock &MBB : mf)
297 if (Reachable.count(Ptr: &MBB))
298 processBasicBlock(MBB: &MBB);
299
300 return false;
301}
302