Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/BreakFalseDeps.cpp
Line
Count
Source (jump to first uncovered line)
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
16.3k
  BreakFalseDeps() : MachineFunctionPass(ID) {
52
16.3k
    initializeBreakFalseDepsPass(*PassRegistry::getPassRegistry());
53
16.3k
  }
54
55
16.2k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
56
16.2k
    AU.setPreservesAll();
57
16.2k
    AU.addRequired<ReachingDefAnalysis>();
58
16.2k
    MachineFunctionPass::getAnalysisUsage(AU);
59
16.2k
  }
60
61
  bool runOnMachineFunction(MachineFunction &MF) override;
62
63
16.2k
  MachineFunctionProperties getRequiredProperties() const override {
64
16.2k
    return MachineFunctionProperties().set(
65
16.2k
      MachineFunctionProperties::Property::NoVRegs);
66
16.2k
  }
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
15.9k
INITIALIZE_PASS_BEGIN(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
102
15.9k
INITIALIZE_PASS_DEPENDENCY(ReachingDefAnalysis)
103
15.9k
INITIALIZE_PASS_END(BreakFalseDeps, DEBUG_TYPE, "BreakFalseDeps", false, false)
104
105
16.3k
FunctionPass *llvm::createBreakFalseDeps() { return new BreakFalseDeps(); }
106
107
bool BreakFalseDeps::pickBestRegisterForUndef(MachineInstr *MI, unsigned OpIdx,
108
2.30k
  unsigned Pref) {
109
2.30k
  MachineOperand &MO = MI->getOperand(OpIdx);
110
2.30k
  assert(MO.isUndef() && "Expected undef machine operand");
111
2.30k
112
2.30k
  unsigned OriginalReg = MO.getReg();
113
2.30k
114
2.30k
  // Update only undef operands that have reg units that are mapped to one root.
115
4.60k
  for (MCRegUnitIterator Unit(OriginalReg, TRI); Unit.isValid(); 
++Unit2.30k
) {
116
2.30k
    unsigned NumRoots = 0;
117
4.60k
    for (MCRegUnitRootIterator Root(*Unit, TRI); Root.isValid(); 
++Root2.30k
) {
118
2.30k
      NumRoots++;
119
2.30k
      if (NumRoots > 1)
120
0
        return false;
121
2.30k
    }
122
2.30k
  }
123
2.30k
124
2.30k
  // Get the undef operand's register class
125
2.30k
  const TargetRegisterClass *OpRC =
126
2.30k
    TII->getRegClass(MI->getDesc(), OpIdx, TRI, *MF);
127
2.30k
128
2.30k
  // If the instruction has a true dependency, we can hide the false depdency
129
2.30k
  // behind it.
130
7.63k
  for (MachineOperand &CurrMO : MI->operands()) {
131
7.63k
    if (!CurrMO.isReg() || 
CurrMO.isDef()7.27k
||
CurrMO.isUndef()4.96k
||
132
7.63k
      
!OpRC->contains(CurrMO.getReg())2.66k
)
133
7.06k
      continue;
134
574
    // We found a true dependency - replace the undef register with the true
135
574
    // dependency.
136
574
    MO.setReg(CurrMO.getReg());
137
574
    return true;
138
574
  }
139
2.30k
140
2.30k
  // Go over all registers in the register class and find the register with
141
2.30k
  // max clearance or clearance higher than Pref.
142
2.30k
  unsigned MaxClearance = 0;
143
1.73k
  unsigned MaxClearanceReg = OriginalReg;
144
1.73k
  ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(OpRC);
145
7.04k
  for (MCPhysReg Reg : Order) {
146
7.04k
    unsigned Clearance = RDA->getClearance(MI, Reg);
147
7.04k
    if (Clearance <= MaxClearance)
148
3.46k
      continue;
149
3.57k
    MaxClearance = Clearance;
150
3.57k
    MaxClearanceReg = Reg;
151
3.57k
152
3.57k
    if (MaxClearance > Pref)
153
1.71k
      break;
154
3.57k
  }
155
1.73k
156
1.73k
  // Update the operand if we found a register with better clearance.
157
1.73k
  if (MaxClearanceReg != OriginalReg)
158
1.46k
    MO.setReg(MaxClearanceReg);
159
1.73k
160
1.73k
  return false;
161
2.30k
}
162
163
bool BreakFalseDeps::shouldBreakDependence(MachineInstr *MI, unsigned OpIdx,
164
3.29k
                                           unsigned Pref) {
165
3.29k
  unsigned reg = MI->getOperand(OpIdx).getReg();
166
3.29k
  unsigned Clearance = RDA->getClearance(MI, reg);
167
3.29k
  LLVM_DEBUG(dbgs() << "Clearance: " << Clearance << ", want " << Pref);
168
3.29k
169
3.29k
  if (Pref > Clearance) {
170
742
    LLVM_DEBUG(dbgs() << ": Break dependency.\n");
171
742
    return true;
172
742
  }
173
2.54k
  LLVM_DEBUG(dbgs() << ": OK .\n");
174
2.54k
  return false;
175
2.54k
}
176
177
3.26M
void BreakFalseDeps::processDefs(MachineInstr *MI) {
178
3.26M
  assert(!MI->isDebugInstr() && "Won't process debug values");
179
3.26M
180
3.26M
  // Break dependence on undef uses. Do this before updating LiveRegs below.
181
3.26M
  unsigned OpNum;
182
3.26M
  unsigned Pref = TII->getUndefRegClearance(*MI, OpNum, TRI);
183
3.26M
  if (Pref) {
184
2.30k
    bool HadTrueDependency = pickBestRegisterForUndef(MI, OpNum, Pref);
185
2.30k
    // We don't need to bother trying to break a dependency if this
186
2.30k
    // instruction has a true dependency on that register through another
187
2.30k
    // operand - we'll have to wait for it to be available regardless.
188
2.30k
    if (!HadTrueDependency && 
shouldBreakDependence(MI, OpNum, Pref)1.73k
)
189
14
      UndefReads.push_back(std::make_pair(MI, OpNum));
190
2.30k
  }
191
3.26M
192
3.26M
  const MCInstrDesc &MCID = MI->getDesc();
193
3.26M
  for (unsigned i = 0,
194
3.26M
    e = MI->isVariadic() ? 
MI->getNumOperands()194k
:
MCID.getNumDefs()3.07M
;
195
5.68M
    i != e; 
++i2.41M
) {
196
2.41M
    MachineOperand &MO = MI->getOperand(i);
197
2.41M
    if (!MO.isReg() || 
!MO.getReg()2.27M
)
198
176k
      continue;
199
2.23M
    if (MO.isUse())
200
238k
      continue;
201
2.00M
    // Check clearance before partial register updates.
202
2.00M
    unsigned Pref = TII->getPartialRegUpdateClearance(*MI, i, TRI);
203
2.00M
    if (Pref && 
shouldBreakDependence(MI, i, Pref)1.56k
)
204
728
      TII->breakPartialRegDependency(*MI, i, TRI);
205
2.00M
  }
206
3.26M
}
207
208
495k
void BreakFalseDeps::processUndefReads(MachineBasicBlock *MBB) {
209
495k
  if (UndefReads.empty())
210
495k
    return;
211
13
212
13
  // Collect this block's live out register units.
213
13
  LiveRegSet.init(*TRI);
214
13
  // We do not need to care about pristine registers as they are just preserved
215
13
  // but not actually used in the function.
216
13
  LiveRegSet.addLiveOutsNoPristines(*MBB);
217
13
218
13
  MachineInstr *UndefMI = UndefReads.back().first;
219
13
  unsigned OpIdx = UndefReads.back().second;
220
13
221
128
  for (MachineInstr &I : make_range(MBB->rbegin(), MBB->rend())) {
222
128
    // Update liveness, including the current instruction's defs.
223
128
    LiveRegSet.stepBackward(I);
224
128
225
128
    if (UndefMI == &I) {
226
14
      if (!LiveRegSet.contains(UndefMI->getOperand(OpIdx).getReg()))
227
13
        TII->breakPartialRegDependency(*UndefMI, OpIdx, TRI);
228
14
229
14
      UndefReads.pop_back();
230
14
      if (UndefReads.empty())
231
14
        return;
232
0
233
0
      UndefMI = UndefReads.back().first;
234
0
      OpIdx = UndefReads.back().second;
235
0
    }
236
128
  }
237
13
}
238
239
495k
void BreakFalseDeps::processBasicBlock(MachineBasicBlock *MBB) {
240
495k
  UndefReads.clear();
241
495k
  // If this block is not done, it makes little sense to make any decisions
242
495k
  // based on clearance information. We need to make a second pass anyway,
243
495k
  // and by then we'll have better information, so we can avoid doing the work
244
495k
  // to try and break dependencies now.
245
3.27M
  for (MachineInstr &MI : *MBB) {
246
3.27M
    if (!MI.isDebugInstr())
247
3.26M
      processDefs(&MI);
248
3.27M
  }
249
495k
  processUndefReads(MBB);
250
495k
}
251
252
160k
bool BreakFalseDeps::runOnMachineFunction(MachineFunction &mf) {
253
160k
  if (skipFunction(mf.getFunction()))
254
207
    return false;
255
160k
  MF = &mf;
256
160k
  TII = MF->getSubtarget().getInstrInfo();
257
160k
  TRI = MF->getSubtarget().getRegisterInfo();
258
160k
  RDA = &getAnalysis<ReachingDefAnalysis>();
259
160k
260
160k
  RegClassInfo.runOnMachineFunction(mf);
261
160k
262
160k
  LLVM_DEBUG(dbgs() << "********** BREAK FALSE DEPENDENCIES **********\n");
263
160k
264
160k
  // Traverse the basic blocks.
265
495k
  for (MachineBasicBlock &MBB : mf) {
266
495k
    processBasicBlock(&MBB);
267
495k
  }
268
160k
269
160k
  return false;
270
160k
}