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 "WebAssemblyUtilities.h"
22#include "llvm/CodeGen/LiveIntervals.h"
23#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
24#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
25#include "llvm/CodeGen/MachinePassManager.h"
26#include "llvm/CodeGen/MachineRegisterInfo.h"
27#include "llvm/CodeGen/Passes.h"
28#include "llvm/CodeGen/SlotIndexes.h"
29#include "llvm/IR/Analysis.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/raw_ostream.h"
32using namespace llvm;
33
34#define DEBUG_TYPE "wasm-reg-coloring"
35
36namespace {
37class WebAssemblyRegColoringLegacy final : public MachineFunctionPass {
38public:
39 static char ID; // Pass identification, replacement for typeid
40 WebAssemblyRegColoringLegacy() : MachineFunctionPass(ID) {}
41
42 StringRef getPassName() const override {
43 return "WebAssembly Register Coloring";
44 }
45
46 void getAnalysisUsage(AnalysisUsage &AU) const override {
47 AU.setPreservesCFG();
48 AU.addRequired<LiveIntervalsWrapperPass>();
49 AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
50 MachineFunctionPass::getAnalysisUsage(AU);
51 }
52
53 bool runOnMachineFunction(MachineFunction &MF) override;
54};
55} // end anonymous namespace
56
57char WebAssemblyRegColoringLegacy::ID = 0;
58INITIALIZE_PASS(WebAssemblyRegColoringLegacy, DEBUG_TYPE,
59 "Minimize number of registers used", false, false)
60
61FunctionPass *llvm::createWebAssemblyRegColoringLegacyPass() {
62 return new WebAssemblyRegColoringLegacy();
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(Reg: VReg))
71 Weight += LiveIntervals::getSpillWeight(isDef: MO.isDef(), isUse: MO.isUse(), MBFI,
72 MI: *MO.getParent());
73 return Weight;
74}
75
76// Create a map of "Register -> vector of <SlotIndex, DBG_VALUE>".
77// The SlotIndex is the slot index of the next non-debug instruction or the end
78// of a BB, because DBG_VALUE's don't have slot index themselves.
79// Adapted from RegisterCoalescer::buildVRegToDbgValueMap.
80static DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
81buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness) {
82 DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
83 DbgVRegToValues;
84 const SlotIndexes *Slots = Liveness->getSlotIndexes();
85 SmallVector<MachineInstr *, 8> ToInsert;
86
87 // After collecting a block of DBG_VALUEs into ToInsert, enter them into the
88 // map.
89 auto CloseNewDVRange = [&DbgVRegToValues, &ToInsert](SlotIndex Slot) {
90 for (auto *X : ToInsert) {
91 for (const auto &Op : X->debug_operands()) {
92 if (Op.isReg() && Op.getReg().isVirtual())
93 DbgVRegToValues[Op.getReg()].push_back(x: {Slot, X});
94 }
95 }
96
97 ToInsert.clear();
98 };
99
100 // Iterate over all instructions, collecting them into the ToInsert vector.
101 // Once a non-debug instruction is found, record the slot index of the
102 // collected DBG_VALUEs.
103 for (auto &MBB : MF) {
104 SlotIndex CurrentSlot = Slots->getMBBStartIdx(mbb: &MBB);
105
106 for (auto &MI : MBB) {
107 if (MI.isDebugValue()) {
108 if (any_of(Range: MI.debug_operands(), P: [](const MachineOperand &MO) {
109 return MO.isReg() && MO.getReg().isVirtual();
110 }))
111 ToInsert.push_back(Elt: &MI);
112 } else if (!MI.isDebugOrPseudoInstr()) {
113 CurrentSlot = Slots->getInstructionIndex(MI);
114 CloseNewDVRange(CurrentSlot);
115 }
116 }
117
118 // Close range of DBG_VALUEs at the end of blocks.
119 CloseNewDVRange(Slots->getMBBEndIdx(mbb: &MBB));
120 }
121
122 // Sort all DBG_VALUEs we've seen by slot number.
123 for (auto &Pair : DbgVRegToValues)
124 llvm::sort(C&: Pair.second);
125 return DbgVRegToValues;
126}
127
128// After register coalescing, some DBG_VALUEs will be invalid. Set them undef.
129// This function has to run before the actual coalescing, i.e., the register
130// changes.
131static void undefInvalidDbgValues(
132 const LiveIntervals *Liveness,
133 ArrayRef<SmallVector<LiveInterval *, 4>> Assignments,
134 DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
135 &DbgVRegToValues) {
136#ifndef NDEBUG
137 DenseSet<Register> SeenRegs;
138#endif
139 for (const auto &CoalescedIntervals : Assignments) {
140 if (CoalescedIntervals.empty())
141 continue;
142 for (LiveInterval *LI : CoalescedIntervals) {
143 Register Reg = LI->reg();
144#ifndef NDEBUG
145 // Ensure we don't process the same register twice
146 assert(SeenRegs.insert(Reg).second);
147#endif
148 auto RegMapIt = DbgVRegToValues.find(Val: Reg);
149 if (RegMapIt == DbgVRegToValues.end())
150 continue;
151 SlotIndex LastSlot;
152 bool LastUndefResult = false;
153 for (auto [Slot, DbgValue] : RegMapIt->second) {
154 // All consecutive DBG_VALUEs have the same slot because the slot
155 // indices they have is the one for the first non-debug instruction
156 // after it, because DBG_VALUEs don't have slot index themselves. Before
157 // doing live range queries, quickly check if the current DBG_VALUE has
158 // the same slot index as the previous one, in which case we should do
159 // the same. Note that RegMapIt->second, the vector of {SlotIndex,
160 // DBG_VALUE}, is sorted by SlotIndex, which is necessary for this
161 // check.
162 if (Slot == LastSlot) {
163 if (LastUndefResult) {
164 LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n");
165 DbgValue->setDebugValueUndef();
166 }
167 continue;
168 }
169 LastSlot = Slot;
170 LastUndefResult = false;
171 for (LiveInterval *OtherLI : CoalescedIntervals) {
172 if (LI == OtherLI)
173 continue;
174
175 // This DBG_VALUE has 'Reg' (the current LiveInterval's register) as
176 // its operand. If this DBG_VALUE's slot index is within other
177 // registers' live ranges, this DBG_VALUE should be undefed. For
178 // example, suppose %0 and %1 are to be coalesced into %0.
179 // ; %0's live range starts
180 // %0 = value_0
181 // DBG_VALUE %0, !"a", ... (a)
182 // DBG_VALUE %1, !"b", ... (b)
183 // use %0
184 // ; %0's live range ends
185 // ...
186 // ; %1's live range starts
187 // %1 = value_1
188 // DBG_VALUE %0, !"c", ... (c)
189 // DBG_VALUE %1, !"d", ... (d)
190 // use %1
191 // ; %1's live range ends
192 //
193 // In this code, (b) and (c) should be set to undef. After the two
194 // registers are coalesced, (b) will incorrectly say the variable
195 // "b"'s value is 'value_0', and (c) will also incorrectly say the
196 // variable "c"'s value is value_1. Note it doesn't actually matter
197 // which register they are coalesced into (%0 or %1); (b) and (c)
198 // should be set to undef as well if they are coalesced into %1.
199 //
200 // This happens DBG_VALUEs are not included when computing live
201 // ranges.
202 //
203 // Note that it is not possible for this DBG_VALUE to be
204 // simultaneously within 'Reg''s live range and one of other coalesced
205 // registers' live ranges because if their live ranges overlapped they
206 // would have not been selected as a coalescing candidate in the first
207 // place.
208 auto *SegmentIt = OtherLI->find(Pos: Slot);
209 if (SegmentIt != OtherLI->end() && SegmentIt->contains(I: Slot)) {
210 LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n");
211 DbgValue->setDebugValueUndef();
212 LastUndefResult = true;
213 break;
214 }
215 }
216 }
217 }
218 }
219}
220
221static bool regColoring(MachineFunction &MF, LiveIntervals *Liveness,
222 const MachineBlockFrequencyInfo *MBFI) {
223 LLVM_DEBUG({
224 dbgs() << "********** Register Coloring **********\n"
225 << "********** Function: " << MF.getName() << '\n';
226 });
227
228 MachineRegisterInfo *MRI = &MF.getRegInfo();
229 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
230
231 // We don't preserve SSA form.
232 MRI->leaveSSA();
233
234 // Gather all register intervals into a list and sort them.
235 unsigned NumVRegs = MRI->getNumVirtRegs();
236 SmallVector<LiveInterval *, 0> SortedIntervals;
237 SortedIntervals.reserve(N: NumVRegs);
238
239 // Record DBG_VALUEs and their SlotIndexes.
240 auto DbgVRegToValues = buildVRegToDbgValueMap(MF, Liveness);
241
242 LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");
243 for (unsigned I = 0; I < NumVRegs; ++I) {
244 Register VReg = Register::index2VirtReg(Index: I);
245 if (MFI.isVRegStackified(VReg))
246 continue;
247 // Skip unused registers, which can use $drop.
248 if (MRI->use_empty(RegNo: VReg))
249 continue;
250
251 LiveInterval *LI = &Liveness->getInterval(Reg: VReg);
252 assert(LI->weight() == 0.0f);
253 LI->setWeight(computeWeight(MRI, MBFI, VReg));
254 LLVM_DEBUG(LI->dump());
255 SortedIntervals.push_back(Elt: LI);
256 }
257 LLVM_DEBUG(dbgs() << '\n');
258
259 // Sort them to put arguments first (since we don't want to rename live-in
260 // registers), by weight next, and then by position.
261 // TODO: Investigate more intelligent sorting heuristics. For starters, we
262 // should try to coalesce adjacent live intervals before non-adjacent ones.
263 llvm::sort(C&: SortedIntervals, Comp: [MRI](LiveInterval *LHS, LiveInterval *RHS) {
264 if (MRI->isLiveIn(Reg: LHS->reg()) != MRI->isLiveIn(Reg: RHS->reg()))
265 return MRI->isLiveIn(Reg: LHS->reg());
266 if (LHS->weight() != RHS->weight())
267 return LHS->weight() > RHS->weight();
268 if (LHS->empty() || RHS->empty())
269 return !LHS->empty() && RHS->empty();
270 return *LHS < *RHS;
271 });
272
273 // ABI contract: the async context must always be available in local 0.
274 // Another value in the same register would make WebAssemblyExplicitLocals
275 // copy the argument to another local.
276 Register SwiftAsyncReg = WebAssembly::getSwiftAsyncArgReg(MF);
277
278 LLVM_DEBUG(dbgs() << "Coloring register intervals:\n");
279 SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u);
280 SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments(
281 SortedIntervals.size());
282 BitVector UsedColors(SortedIntervals.size());
283 bool Changed = false;
284 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
285 LiveInterval *LI = SortedIntervals[I];
286 Register Old = LI->reg();
287 size_t Color = I;
288 const TargetRegisterClass *RC = MRI->getRegClass(Reg: Old);
289
290 // Check if it's possible to reuse any of the used colors.
291 if (!MRI->isLiveIn(Reg: Old) && Old != SwiftAsyncReg)
292 for (unsigned C : UsedColors.set_bits()) {
293 if (MRI->getRegClass(Reg: SortedIntervals[C]->reg()) != RC ||
294 SortedIntervals[C]->reg() == SwiftAsyncReg)
295 continue;
296 for (LiveInterval *OtherLI : Assignments[C])
297 if (!OtherLI->empty() && OtherLI->overlaps(other: *LI))
298 goto continue_outer;
299 Color = C;
300 break;
301 continue_outer:;
302 }
303
304 Register New = SortedIntervals[Color]->reg();
305 SlotMapping[I] = New;
306 Changed |= Old != New;
307 UsedColors.set(Color);
308 Assignments[Color].push_back(Elt: LI);
309 // If we reassigned the stack pointer, update the debug frame base info.
310 if (Old != New && MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Old)
311 MFI.setFrameBaseVreg(New);
312 LLVM_DEBUG(dbgs() << "Assigning vreg " << printReg(LI->reg()) << " to vreg "
313 << printReg(New) << "\n");
314 }
315 if (!Changed)
316 return false;
317
318 // Set DBG_VALUEs that will be invalid after coalescing to undef.
319 undefInvalidDbgValues(Liveness, Assignments, DbgVRegToValues);
320
321 // Rewrite register operands.
322 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
323 Register Old = SortedIntervals[I]->reg();
324 unsigned New = SlotMapping[I];
325 if (Old != New)
326 MRI->replaceRegWith(FromReg: Old, ToReg: New);
327 }
328 return true;
329}
330
331bool WebAssemblyRegColoringLegacy::runOnMachineFunction(MachineFunction &MF) {
332 // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual
333 // registers could be modified before the longjmp is executed, resulting in
334 // the wrong value being used afterwards.
335 // TODO: Does WebAssembly need to care about setjmp for register coloring?
336 if (MF.exposesReturnsTwice())
337 return false;
338
339 LiveIntervals *Liveness = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
340 const MachineBlockFrequencyInfo *MBFI =
341 &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
342 return regColoring(MF, Liveness, MBFI);
343}
344
345PreservedAnalyses
346WebAssemblyRegColoringPass::run(MachineFunction &MF,
347 MachineFunctionAnalysisManager &MFAM) {
348 // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual
349 // registers could be modified before the longjmp is executed, resulting in
350 // the wrong value being used afterwards.
351 // TODO: Does WebAssembly need to care about setjmp for register coloring?
352 if (MF.exposesReturnsTwice())
353 return PreservedAnalyses::all();
354
355 LiveIntervals *Liveness = &MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF);
356 const MachineBlockFrequencyInfo *MBFI =
357 &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
358 return regColoring(MF, Liveness, MBFI)
359 ? getMachineFunctionPassPreservedAnalyses()
360 .preserveSet<CFGAnalyses>()
361 : PreservedAnalyses::all();
362}
363