Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/CalcSpillWeights.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------------------------ CalcSpillWeights.cpp ------------------------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
10
#include "llvm/CodeGen/CalcSpillWeights.h"
11
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
12
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
13
#include "llvm/CodeGen/MachineFunction.h"
14
#include "llvm/CodeGen/MachineLoopInfo.h"
15
#include "llvm/CodeGen/MachineRegisterInfo.h"
16
#include "llvm/CodeGen/VirtRegMap.h"
17
#include "llvm/Support/Debug.h"
18
#include "llvm/Support/raw_ostream.h"
19
#include "llvm/Target/TargetInstrInfo.h"
20
#include "llvm/Target/TargetRegisterInfo.h"
21
#include "llvm/Target/TargetSubtargetInfo.h"
22
using namespace llvm;
23
24
#define DEBUG_TYPE "calcspillweights"
25
26
void llvm::calculateSpillWeightsAndHints(LiveIntervals &LIS,
27
                           MachineFunction &MF,
28
                           VirtRegMap *VRM,
29
                           const MachineLoopInfo &MLI,
30
                           const MachineBlockFrequencyInfo &MBFI,
31
587k
                           VirtRegAuxInfo::NormalizingFn norm) {
32
587k
  DEBUG(dbgs() << "********** Compute Spill Weights **********\n"
33
587k
               << "********** Function: " << MF.getName() << '\n');
34
587k
35
587k
  MachineRegisterInfo &MRI = MF.getRegInfo();
36
587k
  VirtRegAuxInfo VRAI(MF, LIS, VRM, MLI, MBFI, norm);
37
21.2M
  for (unsigned i = 0, e = MRI.getNumVirtRegs(); 
i != e21.2M
;
++i20.6M
) {
38
20.6M
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
39
20.6M
    if (MRI.reg_nodbg_empty(Reg))
40
10.9M
      continue;
41
9.66M
    VRAI.calculateSpillWeightAndHint(LIS.getInterval(Reg));
42
9.66M
  }
43
587k
}
44
45
// Return the preferred allocation register for reg, given a COPY instruction.
46
static unsigned copyHint(const MachineInstr *mi, unsigned reg,
47
                         const TargetRegisterInfo &tri,
48
8.81M
                         const MachineRegisterInfo &mri) {
49
8.81M
  unsigned sub, hreg, hsub;
50
8.81M
  if (
mi->getOperand(0).getReg() == reg8.81M
) {
51
3.25M
    sub = mi->getOperand(0).getSubReg();
52
3.25M
    hreg = mi->getOperand(1).getReg();
53
3.25M
    hsub = mi->getOperand(1).getSubReg();
54
8.81M
  } else {
55
5.56M
    sub = mi->getOperand(1).getSubReg();
56
5.56M
    hreg = mi->getOperand(0).getReg();
57
5.56M
    hsub = mi->getOperand(0).getSubReg();
58
5.56M
  }
59
8.81M
60
8.81M
  if (!hreg)
61
0
    return 0;
62
8.81M
63
8.81M
  
if (8.81M
TargetRegisterInfo::isVirtualRegister(hreg)8.81M
)
64
1.17M
    
return sub == hsub ? 1.17M
hreg1.06M
:
0114k
;
65
7.63M
66
7.63M
  const TargetRegisterClass *rc = mri.getRegClass(reg);
67
7.63M
68
7.63M
  // Only allow physreg hints in rc.
69
7.63M
  if (sub == 0)
70
7.45M
    
return rc->contains(hreg) ? 7.45M
hreg7.30M
:
0145k
;
71
185k
72
185k
  // reg:sub should match the physreg hreg.
73
185k
  return tri.getMatchingSuperReg(hreg, sub, rc);
74
185k
}
75
76
// Check if all values in LI are rematerializable
77
static bool isRematerializable(const LiveInterval &LI,
78
                               const LiveIntervals &LIS,
79
                               VirtRegMap *VRM,
80
7.02M
                               const TargetInstrInfo &TII) {
81
7.02M
  unsigned Reg = LI.reg;
82
7.02M
  unsigned Original = VRM ? 
VRM->getOriginal(Reg)7.02M
:
00
;
83
7.02M
  for (LiveInterval::const_vni_iterator I = LI.vni_begin(), E = LI.vni_end();
84
8.61M
       
I != E8.61M
;
++I1.58M
) {
85
7.28M
    const VNInfo *VNI = *I;
86
7.28M
    if (VNI->isUnused())
87
263
      continue;
88
7.28M
    
if (7.28M
VNI->isPHIDef()7.28M
)
89
148k
      return false;
90
7.13M
91
7.13M
    MachineInstr *MI = LIS.getInstructionFromIndex(VNI->def);
92
7.13M
    assert(MI && "Dead valno in interval");
93
7.13M
94
7.13M
    // Trace copies introduced by live range splitting.  The inline
95
7.13M
    // spiller can rematerialize through these copies, so the spill
96
7.13M
    // weight must reflect this.
97
7.13M
    if (
VRM7.13M
) {
98
7.39M
      while (
MI->isFullCopy()7.39M
) {
99
2.48M
        // The copy destination must match the interval register.
100
2.48M
        if (MI->getOperand(0).getReg() != Reg)
101
1.17k
          return false;
102
2.48M
103
2.48M
        // Get the source register.
104
2.48M
        Reg = MI->getOperand(1).getReg();
105
2.48M
106
2.48M
        // If the original (pre-splitting) registers match this
107
2.48M
        // copy came from a split.
108
2.48M
        if (!TargetRegisterInfo::isVirtualRegister(Reg) ||
109
402k
            VRM->getOriginal(Reg) != Original)
110
2.18M
          return false;
111
300k
112
300k
        // Follow the copy live-in value.
113
300k
        const LiveInterval &SrcLI = LIS.getInterval(Reg);
114
300k
        LiveQueryResult SrcQ = SrcLI.Query(VNI->def);
115
300k
        VNI = SrcQ.valueIn();
116
300k
        assert(VNI && "Copy from non-existing value");
117
300k
        if (VNI->isPHIDef())
118
42.5k
          return false;
119
258k
        MI = LIS.getInstructionFromIndex(VNI->def);
120
258k
        assert(MI && "Dead valno in interval");
121
258k
      }
122
7.13M
    }
123
7.13M
124
4.90M
    
if (4.90M
!TII.isTriviallyReMaterializable(*MI, LIS.getAliasAnalysis())4.90M
)
125
3.32M
      return false;
126
7.28M
  }
127
1.33M
  return true;
128
7.02M
}
129
130
void
131
10.3M
VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) {
132
10.3M
  MachineRegisterInfo &mri = MF.getRegInfo();
133
10.3M
  const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
134
10.3M
  MachineBasicBlock *mbb = nullptr;
135
10.3M
  MachineLoop *loop = nullptr;
136
10.3M
  bool isExiting = false;
137
10.3M
  float totalWeight = 0;
138
10.3M
  unsigned numInstr = 0; // Number of instructions using li
139
10.3M
  SmallPtrSet<MachineInstr*, 8> visited;
140
10.3M
141
10.3M
  // Find the best physreg hint and the best virtreg hint.
142
10.3M
  float bestPhys = 0, bestVirt = 0;
143
10.3M
  unsigned hintPhys = 0, hintVirt = 0;
144
10.3M
145
10.3M
  // Don't recompute a target specific hint.
146
10.3M
  bool noHint = mri.getRegAllocationHint(li.reg).first != 0;
147
10.3M
148
10.3M
  // Don't recompute spill weight for an unspillable register.
149
10.3M
  bool Spillable = li.isSpillable();
150
10.3M
151
10.3M
  for (MachineRegisterInfo::reg_instr_iterator
152
10.3M
       I = mri.reg_instr_begin(li.reg), E = mri.reg_instr_end();
153
41.4M
       
I != E41.4M
; ) {
154
31.0M
    MachineInstr *mi = &*(I++);
155
31.0M
    numInstr++;
156
31.0M
    if (
mi->isIdentityCopy() || 31.0M
mi->isImplicitDef()31.0M
||
mi->isDebugValue()31.0M
)
157
3.77k
      continue;
158
31.0M
    
if (31.0M
!visited.insert(mi).second31.0M
)
159
499k
      continue;
160
30.5M
161
30.5M
    float weight = 1.0f;
162
30.5M
    if (
Spillable30.5M
) {
163
30.5M
      // Get loop info for mi.
164
30.5M
      if (
mi->getParent() != mbb30.5M
) {
165
17.8M
        mbb = mi->getParent();
166
17.8M
        loop = Loops.getLoopFor(mbb);
167
17.8M
        isExiting = loop ? 
loop->isLoopExiting(mbb)6.06M
:
false11.7M
;
168
17.8M
      }
169
30.5M
170
30.5M
      // Calculate instr weight.
171
30.5M
      bool reads, writes;
172
30.5M
      std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
173
30.5M
      weight = LiveIntervals::getSpillWeight(writes, reads, &MBFI, *mi);
174
30.5M
175
30.5M
      // Give extra weight to what looks like a loop induction variable update.
176
30.5M
      if (
writes && 30.5M
isExiting11.8M
&&
LIS.isLiveOutOfMBB(li, mbb)1.57M
)
177
572k
        weight *= 3;
178
30.5M
179
30.5M
      totalWeight += weight;
180
30.5M
    }
181
30.5M
182
30.5M
    // Get allocation hints from copies.
183
30.5M
    if (
noHint || 30.5M
!mi->isCopy()30.5M
)
184
21.7M
      continue;
185
8.81M
    unsigned hint = copyHint(mi, li.reg, tri, mri);
186
8.81M
    if (!hint)
187
273k
      continue;
188
8.54M
    // Force hweight onto the stack so that x86 doesn't add hidden precision,
189
8.54M
    // making the comparison incorrectly pass (i.e., 1 > 1 == true??).
190
8.54M
    //
191
8.54M
    // FIXME: we probably shouldn't use floats at all.
192
8.54M
    volatile float hweight = Hint[hint] += weight;
193
8.54M
    if (
TargetRegisterInfo::isPhysicalRegister(hint)8.54M
) {
194
7.47M
      if (
hweight > bestPhys && 7.47M
mri.isAllocatable(hint)6.98M
) {
195
6.89M
        bestPhys = hweight;
196
6.89M
        hintPhys = hint;
197
6.89M
      }
198
8.54M
    } else {
199
1.06M
      if (
hweight > bestVirt1.06M
) {
200
916k
        bestVirt = hweight;
201
916k
        hintVirt = hint;
202
916k
      }
203
1.06M
    }
204
31.0M
  }
205
10.3M
206
10.3M
  Hint.clear();
207
10.3M
208
10.3M
  // Always prefer the physreg hint.
209
10.3M
  if (unsigned 
hint10.3M
= hintPhys ? hintPhys : hintVirt) {
210
4.83M
    mri.setRegAllocationHint(li.reg, 0, hint);
211
4.83M
    // Weakly boost the spill weight of hinted registers.
212
4.83M
    totalWeight *= 1.01F;
213
4.83M
  }
214
10.3M
215
10.3M
  // If the live interval was already unspillable, leave it that way.
216
10.3M
  if (!Spillable)
217
0
    return;
218
10.3M
219
10.3M
  // Mark li as unspillable if all live ranges are tiny and the interval
220
10.3M
  // is not live at any reg mask.  If the interval is live at a reg mask
221
10.3M
  // spilling may be required.
222
10.3M
  
if (10.3M
li.isZeroLength(LIS.getSlotIndexes()) &&
223
10.3M
      
!li.isLiveAtIndexes(LIS.getRegMaskSlots())3.27M
) {
224
3.27M
    li.markNotSpillable();
225
3.27M
    return;
226
3.27M
  }
227
7.02M
228
7.02M
  // If all of the definitions of the interval are re-materializable,
229
7.02M
  // it is a preferred candidate for spilling.
230
7.02M
  // FIXME: this gets much more complicated once we support non-trivial
231
7.02M
  // re-materialization.
232
7.02M
  
if (7.02M
isRematerializable(li, LIS, VRM, *MF.getSubtarget().getInstrInfo())7.02M
)
233
1.33M
    totalWeight *= 0.5F;
234
10.3M
235
10.3M
  li.weight = normalize(totalWeight, li.getSize(), numInstr);
236
10.3M
}