Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/WebAssembly/WebAssemblyRegColoring.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- WebAssemblyRegColoring.cpp - Register coloring --------------------===//
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
10
/// This file implements a virtual register coloring pass.
11
///
12
/// WebAssembly doesn't have a fixed number of registers, but it is still
13
/// desirable to minimize the total number of registers used in each function.
14
///
15
/// This code is modeled after lib/CodeGen/StackSlotColoring.cpp.
16
///
17
//===----------------------------------------------------------------------===//
18
19
#include "WebAssembly.h"
20
#include "WebAssemblyMachineFunctionInfo.h"
21
#include "llvm/CodeGen/LiveIntervals.h"
22
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
23
#include "llvm/CodeGen/MachineRegisterInfo.h"
24
#include "llvm/CodeGen/Passes.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/raw_ostream.h"
27
using namespace llvm;
28
29
#define DEBUG_TYPE "wasm-reg-coloring"
30
31
namespace {
32
class WebAssemblyRegColoring final : public MachineFunctionPass {
33
public:
34
  static char ID; // Pass identification, replacement for typeid
35
413
  WebAssemblyRegColoring() : MachineFunctionPass(ID) {}
36
37
4.72k
  StringRef getPassName() const override {
38
4.72k
    return "WebAssembly Register Coloring";
39
4.72k
  }
40
41
413
  void getAnalysisUsage(AnalysisUsage &AU) const override {
42
413
    AU.setPreservesCFG();
43
413
    AU.addRequired<LiveIntervals>();
44
413
    AU.addRequired<MachineBlockFrequencyInfo>();
45
413
    AU.addPreserved<MachineBlockFrequencyInfo>();
46
413
    AU.addPreservedID(MachineDominatorsID);
47
413
    MachineFunctionPass::getAnalysisUsage(AU);
48
413
  }
49
50
  bool runOnMachineFunction(MachineFunction &MF) override;
51
52
private:
53
};
54
} // end anonymous namespace
55
56
char WebAssemblyRegColoring::ID = 0;
57
INITIALIZE_PASS(WebAssemblyRegColoring, DEBUG_TYPE,
58
                "Minimize number of registers used", false, false)
59
60
413
FunctionPass *llvm::createWebAssemblyRegColoring() {
61
413
  return new WebAssemblyRegColoring();
62
413
}
63
64
// Compute the total spill weight for VReg.
65
static float computeWeight(const MachineRegisterInfo *MRI,
66
                           const MachineBlockFrequencyInfo *MBFI,
67
11.8k
                           unsigned VReg) {
68
11.8k
  float Weight = 0.0f;
69
11.8k
  for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg))
70
29.9k
    Weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI,
71
29.9k
                                            *MO.getParent());
72
11.8k
  return Weight;
73
11.8k
}
74
75
4.31k
bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {
76
4.31k
  LLVM_DEBUG({
77
4.31k
    dbgs() << "********** Register Coloring **********\n"
78
4.31k
           << "********** Function: " << MF.getName() << '\n';
79
4.31k
  });
80
4.31k
81
4.31k
  // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual
82
4.31k
  // registers could be modified before the longjmp is executed, resulting in
83
4.31k
  // the wrong value being used afterwards. (See <rdar://problem/8007500>.)
84
4.31k
  // TODO: Does WebAssembly need to care about setjmp for register coloring?
85
4.31k
  if (MF.exposesReturnsTwice())
86
2
    return false;
87
4.31k
88
4.31k
  MachineRegisterInfo *MRI = &MF.getRegInfo();
89
4.31k
  LiveIntervals *Liveness = &getAnalysis<LiveIntervals>();
90
4.31k
  const MachineBlockFrequencyInfo *MBFI =
91
4.31k
      &getAnalysis<MachineBlockFrequencyInfo>();
92
4.31k
  WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
93
4.31k
94
4.31k
  // Gather all register intervals into a list and sort them.
95
4.31k
  unsigned NumVRegs = MRI->getNumVirtRegs();
96
4.31k
  SmallVector<LiveInterval *, 0> SortedIntervals;
97
4.31k
  SortedIntervals.reserve(NumVRegs);
98
4.31k
99
4.31k
  LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");
100
67.2k
  for (unsigned I = 0; I < NumVRegs; 
++I62.9k
) {
101
62.9k
    unsigned VReg = TargetRegisterInfo::index2VirtReg(I);
102
62.9k
    if (MFI.isVRegStackified(VReg))
103
27.1k
      continue;
104
35.8k
    // Skip unused registers, which can use $drop.
105
35.8k
    if (MRI->use_empty(VReg))
106
24.0k
      continue;
107
11.8k
108
11.8k
    LiveInterval *LI = &Liveness->getInterval(VReg);
109
11.8k
    assert(LI->weight == 0.0f);
110
11.8k
    LI->weight = computeWeight(MRI, MBFI, VReg);
111
11.8k
    LLVM_DEBUG(LI->dump());
112
11.8k
    SortedIntervals.push_back(LI);
113
11.8k
  }
114
4.31k
  LLVM_DEBUG(dbgs() << '\n');
115
4.31k
116
4.31k
  // Sort them to put arguments first (since we don't want to rename live-in
117
4.31k
  // registers), by weight next, and then by position.
118
4.31k
  // TODO: Investigate more intelligent sorting heuristics. For starters, we
119
4.31k
  // should try to coalesce adjacent live intervals before non-adjacent ones.
120
26.1k
  llvm::sort(SortedIntervals, [MRI](LiveInterval *LHS, LiveInterval *RHS) {
121
26.1k
    if (MRI->isLiveIn(LHS->reg) != MRI->isLiveIn(RHS->reg))
122
0
      return MRI->isLiveIn(LHS->reg);
123
26.1k
    if (LHS->weight != RHS->weight)
124
5.19k
      return LHS->weight > RHS->weight;
125
20.9k
    if (LHS->empty() || 
RHS->empty()20.9k
)
126
21
      return !LHS->empty() && 
RHS->empty()5
;
127
20.9k
    return *LHS < *RHS;
128
20.9k
  });
129
4.31k
130
4.31k
  LLVM_DEBUG(dbgs() << "Coloring register intervals:\n");
131
4.31k
  SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u);
132
4.31k
  SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments(
133
4.31k
      SortedIntervals.size());
134
4.31k
  BitVector UsedColors(SortedIntervals.size());
135
4.31k
  bool Changed = false;
136
16.1k
  for (size_t I = 0, E = SortedIntervals.size(); I < E; 
++I11.8k
) {
137
11.8k
    LiveInterval *LI = SortedIntervals[I];
138
11.8k
    unsigned Old = LI->reg;
139
11.8k
    size_t Color = I;
140
11.8k
    const TargetRegisterClass *RC = MRI->getRegClass(Old);
141
11.8k
142
11.8k
    // Check if it's possible to reuse any of the used colors.
143
11.8k
    if (!MRI->isLiveIn(Old))
144
47.8k
      
for (unsigned C : UsedColors.set_bits())11.8k
{
145
47.8k
        if (MRI->getRegClass(SortedIntervals[C]->reg) != RC)
146
3.66k
          continue;
147
44.1k
        for (LiveInterval *OtherLI : Assignments[C])
148
44.4k
          if (!OtherLI->empty() && 
OtherLI->overlaps(*LI)44.3k
)
149
43.8k
            goto continue_outer;
150
44.1k
        Color = C;
151
292
        break;
152
43.8k
      continue_outer:;
153
43.8k
      }
154
11.8k
155
11.8k
    unsigned New = SortedIntervals[Color]->reg;
156
11.8k
    SlotMapping[I] = New;
157
11.8k
    Changed |= Old != New;
158
11.8k
    UsedColors.set(Color);
159
11.8k
    Assignments[Color].push_back(LI);
160
11.8k
    LLVM_DEBUG(
161
11.8k
        dbgs() << "Assigning vreg" << TargetRegisterInfo::virtReg2Index(LI->reg)
162
11.8k
               << " to vreg" << TargetRegisterInfo::virtReg2Index(New) << "\n");
163
11.8k
  }
164
4.31k
  if (!Changed)
165
4.11k
    return false;
166
195
167
195
  // Rewrite register operands.
168
1.23k
  
for (size_t I = 0, E = SortedIntervals.size(); 195
I < E;
++I1.04k
) {
169
1.04k
    unsigned Old = SortedIntervals[I]->reg;
170
1.04k
    unsigned New = SlotMapping[I];
171
1.04k
    if (Old != New)
172
292
      MRI->replaceRegWith(Old, New);
173
1.04k
  }
174
195
  return true;
175
195
}