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