Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/CalcSpillWeights.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CalcSpillWeights.cpp -----------------------------------------------===//
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
#include "llvm/CodeGen/CalcSpillWeights.h"
10
#include "llvm/ADT/SmallPtrSet.h"
11
#include "llvm/CodeGen/LiveInterval.h"
12
#include "llvm/CodeGen/LiveIntervals.h"
13
#include "llvm/CodeGen/MachineFunction.h"
14
#include "llvm/CodeGen/MachineInstr.h"
15
#include "llvm/CodeGen/MachineLoopInfo.h"
16
#include "llvm/CodeGen/MachineOperand.h"
17
#include "llvm/CodeGen/MachineRegisterInfo.h"
18
#include "llvm/CodeGen/TargetInstrInfo.h"
19
#include "llvm/CodeGen/TargetRegisterInfo.h"
20
#include "llvm/CodeGen/TargetSubtargetInfo.h"
21
#include "llvm/CodeGen/VirtRegMap.h"
22
#include "llvm/Support/Debug.h"
23
#include "llvm/Support/raw_ostream.h"
24
#include <cassert>
25
#include <tuple>
26
27
using namespace llvm;
28
29
#define DEBUG_TYPE "calcspillweights"
30
31
void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS,
32
                           MachineFunction &MF,
33
                           VirtRegMap *VRM,
34
                           const MachineLoopInfo &MLI,
35
                           const MachineBlockFrequencyInfo &MBFI,
36
484k
                           VirtRegAuxInfo::NormalizingFn norm) {
37
484k
  LLVM_DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
38
484k
                    << "********** Function: " << MF.getName() << '\n');
39
484k
40
484k
  MachineRegisterInfo &MRI = MF.getRegInfo();
41
484k
  VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm);
42
18.1M
  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; 
++i17.6M
) {
43
17.6M
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
44
17.6M
    if (MRI.reg_nodbg_empty(Reg))
45
10.1M
      continue;
46
7.50M
    VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg));
47
7.50M
  }
48
484k
}
49
50
// Return the preferred allocation register for reg, given a COPY instruction.
51
static unsigned copyHint(const MachineInstr *mi, unsigned reg,
52
                         const TargetRegisterInfo &tri,
53
6.40M
                         const MachineRegisterInfo &mri) {
54
6.40M
  unsigned sub, hreg, hsub;
55
6.40M
  if (mi->getOperand(0).getReg() == reg) {
56
2.45M
    sub = mi->getOperand(0).getSubReg();
57
2.45M
    hreg = mi->getOperand(1).getReg();
58
2.45M
    hsub = mi->getOperand(1).getSubReg();
59
3.95M
  } else {
60
3.95M
    sub = mi->getOperand(1).getSubReg();
61
3.95M
    hreg = mi->getOperand(0).getReg();
62
3.95M
    hsub = mi->getOperand(0).getSubReg();
63
3.95M
  }
64
6.40M
65
6.40M
  if (!hreg)
66
0
    return 0;
67
6.40M
68
6.40M
  if (TargetRegisterInfo::isVirtualRegister(hreg))
69
1.43M
    return sub == hsub ? 
hreg1.26M
:
0172k
;
70
4.97M
71
4.97M
  const TargetRegisterClass *rc = mri.getRegClass(reg);
72
4.97M
  unsigned CopiedPReg = (hsub ? 
tri.getSubReg(hreg, hsub)0
: hreg);
73
4.97M
  if (rc->contains(CopiedPReg))
74
4.80M
    return CopiedPReg;
75
169k
76
169k
  // Check if reg:sub matches so that a super register could be hinted.
77
169k
  if (sub)
78
143k
    return tri.getMatchingSuperReg(CopiedPReg, sub, rc);
79
25.8k
80
25.8k
  return 0;
81
25.8k
}
82
83
// Check if all values in LI are rematerializable
84
static bool isRematerializable(const LiveInterval &LI,
85
                               const LiveIntervals &LIS,
86
                               VirtRegMap *VRM,
87
5.56M
                               const TargetInstrInfo &TII) {
88
5.56M
  unsigned Reg = LI.reg;
89
5.56M
  unsigned Original = VRM ? VRM->getOriginal(Reg) : 
00
;
90
5.56M
  for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
91
6.97M
       I != E; 
++I1.41M
) {
92
5.83M
    const VNInfo *VNI = *I;
93
5.83M
    if (VNI->isUnused())
94
421
      continue;
95
5.83M
    if (VNI->isPHIDef())
96
199k
      return false;
97
5.63M
98
5.63M
    MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
99
5.63M
    assert(MI && "Dead valno in interval");
100
5.63M
101
5.63M
    // Trace copies introduced by live range splitting.  The inline
102
5.63M
    // spiller can rematerialize through these copies, so the spill
103
5.63M
    // weight must reflect this.
104
5.63M
    if (VRM) {
105
5.95M
      while (MI->isFullCopy()) {
106
1.91M
        // The copy destination must match the interval register.
107
1.91M
        if (MI->getOperand(0).getReg() != Reg)
108
2.46k
          return false;
109
1.91M
110
1.91M
        // Get the source register.
111
1.91M
        Reg = MI->getOperand(1).getReg();
112
1.91M
113
1.91M
        // If the original (pre-splitting) registers match this
114
1.91M
        // copy came from a split.
115
1.91M
        if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
116
1.91M
            
VRM->getOriginal(Reg) != Original471k
)
117
1.54M
          return false;
118
371k
119
371k
        // Follow the copy live-in value.
120
371k
        const LiveInterval &SrcLI = LIS.getInterval(Reg);
121
371k
        LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
122
371k
        VNI = SrcQ.valueIn();
123
371k
        assert(VNI && "Copy from non-existing value");
124
371k
        if (VNI->isPHIDef())
125
52.4k
          return false;
126
318k
        MI = LIS.getInstructionFromIndex(VNI->def);
127
318k
        assert(MI && "Dead valno in interval");
128
318k
      }
129
5.63M
    }
130
5.63M
131
5.63M
    
if (4.03M
!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis())4.03M
)
132
2.62M
      return false;
133
4.03M
  }
134
5.56M
  
return true1.14M
;
135
5.56M
}
136
137
8.33M
void VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) {
138
8.33M
  float weight = weightCalcHelper(li);
139
8.33M
  // Check if unspillable.
140
8.33M
  if (weight < 0)
141
2.77M
    return;
142
5.55M
  li.weight = weight;
143
5.55M
}
144
145
float VirtRegAuxInfo::futureWeight(LiveInterval &li, SlotIndex start,
146
6.89k
                                   SlotIndex end) {
147
6.89k
  return weightCalcHelper(li, &start, &end);
148
6.89k
}
149
150
float VirtRegAuxInfo::weightCalcHelper(LiveInterval &li, SlotIndex *start,
151
8.33M
                                       SlotIndex *end) {
152
8.33M
  MachineRegisterInfo &mri = MF.getRegInfo();
153
8.33M
  const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
154
8.33M
  MachineBasicBlock *mbb = nullptr;
155
8.33M
  MachineLoop *loop = nullptr;
156
8.33M
  bool isExiting = false;
157
8.33M
  float totalWeight = 0;
158
8.33M
  unsigned numInstr = 0; // Number of instructions using li
159
8.33M
  SmallPtrSet<MachineInstr*, 8> visited;
160
8.33M
161
8.33M
  std::pair<unsigned, unsigned> TargetHint = mri.getRegAllocationHint(li.reg);
162
8.33M
163
8.33M
  // Don't recompute spill weight for an unspillable register.
164
8.33M
  bool Spillable = li.isSpillable();
165
8.33M
166
8.33M
  bool localSplitArtifact = start && 
end6.89k
;
167
8.33M
168
8.33M
  // Do not update future local split artifacts.
169
8.33M
  bool updateLI = !localSplitArtifact;
170
8.33M
171
8.33M
  if (localSplitArtifact) {
172
6.89k
    MachineBasicBlock *localMBB = LIS.getMBBFromIndex(*end);
173
6.89k
    assert(localMBB == LIS.getMBBFromIndex(*start) &&
174
6.89k
           "start and end are expected to be in the same basic block");
175
6.89k
176
6.89k
    // Local split artifact will have 2 additional copy instructions and they
177
6.89k
    // will be in the same BB.
178
6.89k
    // localLI = COPY other
179
6.89k
    // ...
180
6.89k
    // other   = COPY localLI
181
6.89k
    totalWeight += LiveIntervals::getSpillWeight(true, false, &MBFI, localMBB);
182
6.89k
    totalWeight += LiveIntervals::getSpillWeight(false, true, &MBFI, localMBB);
183
6.89k
184
6.89k
    numInstr += 2;
185
6.89k
  }
186
8.33M
187
8.33M
  // CopyHint is a sortable hint derived from a COPY instruction.
188
8.33M
  struct CopyHint {
189
8.33M
    unsigned Reg;
190
8.33M
    float Weight;
191
8.33M
    bool IsPhys;
192
8.33M
    CopyHint(unsigned R, float W, bool P) :
193
8.33M
      Reg(R), Weight(W), IsPhys(P) 
{}6.19M
194
8.33M
    bool operator<(const CopyHint &rhs) const {
195
6.03M
      // Always prefer any physreg hint.
196
6.03M
      if (IsPhys != rhs.IsPhys)
197
507k
        return (IsPhys && 
!rhs.IsPhys326k
);
198
5.52M
      if (Weight != rhs.Weight)
199
4.81M
        return (Weight > rhs.Weight);
200
709k
      return Reg < rhs.Reg; // Tie-breaker.
201
709k
    }
202
8.33M
  };
203
8.33M
  std::set<CopyHint> CopyHints;
204
8.33M
205
8.33M
  for (MachineRegisterInfo::reg_instr_iterator
206
8.33M
       I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
207
33.1M
       I != E; ) {
208
24.8M
    MachineInstr *mi = &*(I++);
209
24.8M
210
24.8M
    // For local split artifacts, we are interested only in instructions between
211
24.8M
    // the expected start and end of the range.
212
24.8M
    SlotIndex si = LIS.getInstructionIndex(*mi);
213
24.8M
    if (localSplitArtifact && 
(56.1k
(si < *start)56.1k
||
(si > *end)21.4k
))
214
55.6k
      continue;
215
24.7M
216
24.7M
    numInstr++;
217
24.7M
    if (
mi->isIdentityCopy()24.7M
|| mi->isImplicitDef() ||
mi->isDebugInstr()24.7M
)
218
3.74k
      continue;
219
24.7M
    if (!visited.insert(mi).second)
220
517k
      continue;
221
24.2M
222
24.2M
    float weight = 1.0f;
223
24.2M
    if (Spillable) {
224
24.2M
      // Get loop info for mi.
225
24.2M
      if (mi->getParent() != mbb) {
226
14.0M
        mbb = mi->getParent();
227
14.0M
        loop = Loops.getLoopFor(mbb);
228
14.0M
        isExiting = loop ? 
loop->isLoopExiting(mbb)4.29M
:
false9.78M
;
229
14.0M
      }
230
24.2M
231
24.2M
      // Calculate instr weight.
232
24.2M
      bool reads, writes;
233
24.2M
      std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
234
24.2M
      weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
235
24.2M
236
24.2M
      // Give extra weight to what looks like a loop induction variable update.
237
24.2M
      if (writes && 
isExiting9.72M
&&
LIS.isLiveOutOfMBB(li, mbb)1.17M
)
238
381k
        weight *= 3;
239
24.2M
240
24.2M
      totalWeight += weight;
241
24.2M
    }
242
24.2M
243
24.2M
    // Get allocation hints from copies.
244
24.2M
    if (!mi->isCopy())
245
17.8M
      continue;
246
6.40M
    unsigned hint = copyHint(mi, li.reg, tri, mri);
247
6.40M
    if (!hint)
248
200k
      continue;
249
6.20M
    // Force hweight onto the stack so that x86 doesn't add hidden precision,
250
6.20M
    // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
251
6.20M
    //
252
6.20M
    // FIXME: we probably shouldn't use floats at all.
253
6.20M
    volatile float hweight = Hint[hint] += weight;
254
6.20M
    if (TargetRegisterInfo::isVirtualRegister(hint) || 
mri.isAllocatable(hint)4.94M
)
255
6.19M
      CopyHints.insert(CopyHint(hint, hweight, tri.isPhysicalRegister(hint)));
256
6.20M
  }
257
8.33M
258
8.33M
  Hint.clear();
259
8.33M
260
8.33M
  // Pass all the sorted copy hints to mri.
261
8.33M
  if (updateLI && 
CopyHints.size()8.33M
) {
262
3.62M
    // Remove a generic hint if previously added by target.
263
3.62M
    if (TargetHint.first == 0 && 
TargetHint.second3.62M
)
264
1.20k
      mri.clearSimpleHint(li.reg);
265
3.62M
266
3.62M
    std::set<unsigned> HintedRegs;
267
6.18M
    for (auto &Hint : CopyHints) {
268
6.18M
      if (!HintedRegs.insert(Hint.Reg).second ||
269
6.18M
          
(4.25M
TargetHint.first != 04.25M
&&
Hint.Reg == TargetHint.second44
))
270
1.93M
        // Don't add the same reg twice or the target-type hint again.
271
1.93M
        continue;
272
4.25M
      mri.addRegAllocationHint(li.reg, Hint.Reg);
273
4.25M
    }
274
3.62M
275
3.62M
    // Weakly boost the spill weight of hinted registers.
276
3.62M
    totalWeight *= 1.01F;
277
3.62M
  }
278
8.33M
279
8.33M
  // If the live interval was already unspillable, leave it that way.
280
8.33M
  if (!Spillable)
281
2
    return -1.0;
282
8.33M
283
8.33M
  // Mark li as unspillable if all live ranges are tiny and the interval
284
8.33M
  // is not live at any reg mask.  If the interval is live at a reg mask
285
8.33M
  // spilling may be required.
286
8.33M
  if (updateLI && 
li.isZeroLength(LIS.getSlotIndexes())8.33M
&&
287
8.33M
      
!li.isLiveAtIndexes(LIS.getRegMaskSlots())2.77M
) {
288
2.77M
    li.markNotSpillable();
289
2.77M
    return -1.0;
290
2.77M
  }
291
5.56M
292
5.56M
  // If all of the definitions of the interval are re-materializable,
293
5.56M
  // it is a preferred candidate for spilling.
294
5.56M
  // FIXME: this gets much more complicated once we support non-trivial
295
5.56M
  // re-materialization.
296
5.56M
  if (isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo()))
297
1.14M
    totalWeight *= 0.5F;
298
5.56M
299
5.56M
  if (localSplitArtifact)
300
6.89k
    return normalize(totalWeight, start->distance(*end), numInstr);
301
5.55M
  return normalize(totalWeight, li.getSize(), numInstr);
302
5.55M
}