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