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