Coverage Report

Created: 2019-02-20 00:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/CalcSpillWeights.h
Line
Count
Source
1
//===- lib/CodeGen/CalcSpillWeights.h ---------------------------*- 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
#ifndef LLVM_CODEGEN_CALCSPILLWEIGHTS_H
10
#define LLVM_CODEGEN_CALCSPILLWEIGHTS_H
11
12
#include "llvm/ADT/DenseMap.h"
13
#include "llvm/CodeGen/SlotIndexes.h"
14
15
namespace llvm {
16
17
class LiveInterval;
18
class LiveIntervals;
19
class MachineBlockFrequencyInfo;
20
class MachineFunction;
21
class MachineLoopInfo;
22
class VirtRegMap;
23
24
  /// Normalize the spill weight of a live interval
25
  ///
26
  /// The spill weight of a live interval is computed as:
27
  ///
28
  ///   (sum(use freq) + sum(def freq)) / (K + size)
29
  ///
30
  /// @param UseDefFreq Expected number of executed use and def instructions
31
  ///                   per function call. Derived from block frequencies.
32
  /// @param Size       Size of live interval as returnexd by getSize()
33
  /// @param NumInstr   Number of instructions using this live interval
34
  static inline float normalizeSpillWeight(float UseDefFreq, unsigned Size,
35
7.43M
                                           unsigned NumInstr) {
36
7.43M
    // The constant 25 instructions is added to avoid depending too much on
37
7.43M
    // accidental SlotIndex gaps for small intervals. The effect is that small
38
7.43M
    // intervals have a spill weight that is mostly proportional to the number
39
7.43M
    // of uses, while large intervals get a spill weight that is closer to a use
40
7.43M
    // density.
41
7.43M
    return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
42
7.43M
  }
Unexecuted instantiation: CalcSpillWeights.cpp:llvm::normalizeSpillWeight(float, unsigned int, unsigned int)
LiveRangeEdit.cpp:llvm::normalizeSpillWeight(float, unsigned int, unsigned int)
Line
Count
Source
35
418k
                                           unsigned NumInstr) {
36
418k
    // The constant 25 instructions is added to avoid depending too much on
37
418k
    // accidental SlotIndex gaps for small intervals. The effect is that small
38
418k
    // intervals have a spill weight that is mostly proportional to the number
39
418k
    // of uses, while large intervals get a spill weight that is closer to a use
40
418k
    // density.
41
418k
    return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
42
418k
  }
RegAllocBasic.cpp:llvm::normalizeSpillWeight(float, unsigned int, unsigned int)
Line
Count
Source
35
1.48k
                                           unsigned NumInstr) {
36
1.48k
    // The constant 25 instructions is added to avoid depending too much on
37
1.48k
    // accidental SlotIndex gaps for small intervals. The effect is that small
38
1.48k
    // intervals have a spill weight that is mostly proportional to the number
39
1.48k
    // of uses, while large intervals get a spill weight that is closer to a use
40
1.48k
    // density.
41
1.48k
    return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
42
1.48k
  }
RegAllocGreedy.cpp:llvm::normalizeSpillWeight(float, unsigned int, unsigned int)
Line
Count
Source
35
7.01M
                                           unsigned NumInstr) {
36
7.01M
    // The constant 25 instructions is added to avoid depending too much on
37
7.01M
    // accidental SlotIndex gaps for small intervals. The effect is that small
38
7.01M
    // intervals have a spill weight that is mostly proportional to the number
39
7.01M
    // of uses, while large intervals get a spill weight that is closer to a use
40
7.01M
    // density.
41
7.01M
    return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
42
7.01M
  }
RegAllocPBQP.cpp:llvm::normalizeSpillWeight(float, unsigned int, unsigned int)
Line
Count
Source
35
132
                                           unsigned NumInstr) {
36
132
    // The constant 25 instructions is added to avoid depending too much on
37
132
    // accidental SlotIndex gaps for small intervals. The effect is that small
38
132
    // intervals have a spill weight that is mostly proportional to the number
39
132
    // of uses, while large intervals get a spill weight that is closer to a use
40
132
    // density.
41
132
    return UseDefFreq / (Size + 25*SlotIndex::InstrDist);
42
132
  }
43
44
  /// Calculate auxiliary information for a virtual register such as its
45
  /// spill weight and allocation hint.
46
  class VirtRegAuxInfo {
47
  public:
48
    using NormalizingFn = float (*)(float, unsigned, unsigned);
49
50
  private:
51
    MachineFunction &MF;
52
    LiveIntervals &LIS;
53
    VirtRegMap *VRM;
54
    const MachineLoopInfo &Loops;
55
    const MachineBlockFrequencyInfo &MBFI;
56
    DenseMap<unsigned, float> Hint;
57
    NormalizingFn normalize;
58
59
  public:
60
    VirtRegAuxInfo(MachineFunction &mf, LiveIntervals &lis,
61
                   VirtRegMap *vrm, const MachineLoopInfo &loops,
62
                   const MachineBlockFrequencyInfo &mbfi,
63
                   NormalizingFn norm = normalizeSpillWeight)
64
968k
        : MF(mf), LIS(lis), VRM(vrm), Loops(loops), MBFI(mbfi), normalize(norm) {}
65
66
    /// (re)compute li's spill weight and allocation hint.
67
    void calculateSpillWeightAndHint(LiveInterval &li);
68
69
    /// Compute future expected spill weight of a split artifact of li
70
    /// that will span between start and end slot indexes.
71
    /// \param li     The live interval to be split.
72
    /// \param start  The expected begining of the split artifact. Instructions
73
    ///               before start will not affect the weight.
74
    /// \param end    The expected end of the split artifact. Instructions
75
    ///               after end will not affect the weight.
76
    /// \return The expected spill weight of the split artifact. Returns
77
    /// negative weight for unspillable li.
78
    float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end);
79
80
    /// Helper function for weight calculations.
81
    /// (Re)compute li's spill weight and allocation hint, or, for non null
82
    /// start and end - compute future expected spill weight of a split
83
    /// artifact of li that will span between start and end slot indexes.
84
    /// \param li     The live interval for which to compute the weight.
85
    /// \param start  The expected begining of the split artifact. Instructions
86
    ///               before start will not affect the weight. Relevant for
87
    ///               weight calculation of future split artifact.
88
    /// \param end    The expected end of the split artifact. Instructions
89
    ///               after end will not affect the weight. Relevant for
90
    ///               weight calculation of future split artifact.
91
    /// \return The spill weight. Returns negative weight for unspillable li.
92
    float weightCalcHelper(LiveInterval &li, SlotIndex *start = nullptr,
93
                           SlotIndex *end = nullptr);
94
  };
95
96
  /// Compute spill weights and allocation hints for all virtual register
97
  /// live intervals.
98
  void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF,
99
                                     VirtRegMap *VRM,
100
                                     const MachineLoopInfo &MLI,
101
                                     const MachineBlockFrequencyInfo &MBFI,
102
                                     VirtRegAuxInfo::NormalizingFn norm =
103
                                         normalizeSpillWeight);
104
105
} // end namespace llvm
106
107
#endif // LLVM_CODEGEN_CALCSPILLWEIGHTS_H