Line data Source code
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"
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
36 298 : WebAssemblyRegColoring() : MachineFunctionPass(ID) {}
37 :
38 298 : StringRef getPassName() const override {
39 298 : return "WebAssembly Register Coloring";
40 : }
41 :
42 298 : void getAnalysisUsage(AnalysisUsage &AU) const override {
43 298 : AU.setPreservesCFG();
44 : AU.addRequired<LiveIntervals>();
45 : AU.addRequired<MachineBlockFrequencyInfo>();
46 : AU.addPreserved<MachineBlockFrequencyInfo>();
47 298 : AU.addPreservedID(MachineDominatorsID);
48 298 : MachineFunctionPass::getAnalysisUsage(AU);
49 298 : }
50 :
51 : bool runOnMachineFunction(MachineFunction &MF) override;
52 :
53 : private:
54 : };
55 : } // end anonymous namespace
56 :
57 : char WebAssemblyRegColoring::ID = 0;
58 199030 : INITIALIZE_PASS(WebAssemblyRegColoring, DEBUG_TYPE,
59 : "Minimize number of registers used", false, false)
60 :
61 298 : FunctionPass *llvm::createWebAssemblyRegColoring() {
62 298 : return new WebAssemblyRegColoring();
63 : }
64 :
65 : // Compute the total spill weight for VReg.
66 7335 : static float computeWeight(const MachineRegisterInfo *MRI,
67 : const MachineBlockFrequencyInfo *MBFI,
68 : unsigned VReg) {
69 : float weight = 0.0f;
70 25277 : for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg))
71 35884 : weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI,
72 17942 : *MO.getParent());
73 7335 : return weight;
74 : }
75 :
76 2891 : bool 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 2891 : if (MF.exposesReturnsTwice())
87 : return false;
88 :
89 2889 : MachineRegisterInfo *MRI = &MF.getRegInfo();
90 2889 : LiveIntervals *Liveness = &getAnalysis<LiveIntervals>();
91 : const MachineBlockFrequencyInfo *MBFI =
92 2889 : &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 2889 : SortedIntervals.reserve(NumVRegs);
99 :
100 : LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");
101 34945 : for (unsigned i = 0; i < NumVRegs; ++i) {
102 : unsigned VReg = TargetRegisterInfo::index2VirtReg(i);
103 31526 : if (MFI.isVRegStackified(VReg))
104 24721 : continue;
105 : // Skip unused registers, which can use $drop.
106 19477 : if (MRI->use_empty(VReg))
107 : continue;
108 :
109 7335 : LiveInterval *LI = &Liveness->getInterval(VReg);
110 : assert(LI->weight == 0.0f);
111 7335 : LI->weight = computeWeight(MRI, MBFI, VReg);
112 : LLVM_DEBUG(LI->dump());
113 7335 : 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 2889 : SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u);
133 : SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments(
134 5778 : SortedIntervals.size());
135 2889 : BitVector UsedColors(SortedIntervals.size());
136 : bool Changed = false;
137 10224 : for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) {
138 7335 : LiveInterval *LI = SortedIntervals[i];
139 7335 : 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 7335 : if (!MRI->isLiveIn(Old))
145 37700 : for (unsigned C : UsedColors.set_bits()) {
146 91470 : if (MRI->getRegClass(SortedIntervals[C]->reg) != RC)
147 : continue;
148 28535 : for (LiveInterval *OtherLI : Assignments[C])
149 56808 : if (!OtherLI->empty() && OtherLI->overlaps(*LI))
150 : goto continue_outer;
151 : Color = C;
152 : break;
153 30365 : continue_outer:;
154 : }
155 :
156 : unsigned New = SortedIntervals[Color]->reg;
157 7335 : SlotMapping[i] = New;
158 7335 : Changed |= Old != New;
159 7335 : UsedColors.set(Color);
160 7335 : 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 2889 : if (!Changed)
166 : return false;
167 :
168 : // Rewrite register operands.
169 623 : for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) {
170 541 : unsigned Old = SortedIntervals[i]->reg;
171 541 : unsigned New = SlotMapping[i];
172 541 : if (Old != New)
173 125 : MRI->replaceRegWith(Old, New);
174 : }
175 : return true;
176 : }
|
