LLVM 19.0.0git
WebAssemblyRegColoring.cpp
Go to the documentation of this file.
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"
24#include "llvm/CodeGen/Passes.h"
25#include "llvm/Support/Debug.h"
27using namespace llvm;
28
29#define DEBUG_TYPE "wasm-reg-coloring"
30
31namespace {
32class WebAssemblyRegColoring final : public MachineFunctionPass {
33public:
34 static char ID; // Pass identification, replacement for typeid
35 WebAssemblyRegColoring() : MachineFunctionPass(ID) {}
36
37 StringRef getPassName() const override {
38 return "WebAssembly Register Coloring";
39 }
40
41 void getAnalysisUsage(AnalysisUsage &AU) const override {
42 AU.setPreservesCFG();
48 }
49
50 bool runOnMachineFunction(MachineFunction &MF) override;
51
52private:
53};
54} // end anonymous namespace
55
56char WebAssemblyRegColoring::ID = 0;
57INITIALIZE_PASS(WebAssemblyRegColoring, DEBUG_TYPE,
58 "Minimize number of registers used", false, false)
59
61 return new WebAssemblyRegColoring();
62}
63
64// Compute the total spill weight for VReg.
66 const MachineBlockFrequencyInfo *MBFI,
67 unsigned VReg) {
68 float Weight = 0.0f;
69 for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg))
70 Weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI,
71 *MO.getParent());
72 return Weight;
73}
74
75// Create a map of "Register -> vector of <SlotIndex, DBG_VALUE>".
76// The SlotIndex is the slot index of the next non-debug instruction or the end
77// of a BB, because DBG_VALUE's don't have slot index themselves.
78// Adapted from RegisterCoalescer::buildVRegToDbgValueMap.
82 DbgVRegToValues;
83 const SlotIndexes *Slots = Liveness->getSlotIndexes();
85
86 // After collecting a block of DBG_VALUEs into ToInsert, enter them into the
87 // map.
88 auto CloseNewDVRange = [&DbgVRegToValues, &ToInsert](SlotIndex Slot) {
89 for (auto *X : ToInsert) {
90 for (const auto &Op : X->debug_operands()) {
91 if (Op.isReg() && Op.getReg().isVirtual())
92 DbgVRegToValues[Op.getReg()].push_back({Slot, X});
93 }
94 }
95
96 ToInsert.clear();
97 };
98
99 // Iterate over all instructions, collecting them into the ToInsert vector.
100 // Once a non-debug instruction is found, record the slot index of the
101 // collected DBG_VALUEs.
102 for (auto &MBB : MF) {
103 SlotIndex CurrentSlot = Slots->getMBBStartIdx(&MBB);
104
105 for (auto &MI : MBB) {
106 if (MI.isDebugValue()) {
107 if (any_of(MI.debug_operands(), [](const MachineOperand &MO) {
108 return MO.isReg() && MO.getReg().isVirtual();
109 }))
110 ToInsert.push_back(&MI);
111 } else if (!MI.isDebugOrPseudoInstr()) {
112 CurrentSlot = Slots->getInstructionIndex(MI);
113 CloseNewDVRange(CurrentSlot);
114 }
115 }
116
117 // Close range of DBG_VALUEs at the end of blocks.
118 CloseNewDVRange(Slots->getMBBEndIdx(&MBB));
119 }
120
121 // Sort all DBG_VALUEs we've seen by slot number.
122 for (auto &Pair : DbgVRegToValues)
123 llvm::sort(Pair.second);
124 return DbgVRegToValues;
125}
126
127// After register coalescing, some DBG_VALUEs will be invalid. Set them undef.
128// This function has to run before the actual coalescing, i.e., the register
129// changes.
131 const LiveIntervals *Liveness,
132 const ArrayRef<SmallVector<LiveInterval *, 4>> &Assignments,
133 DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>>
134 &DbgVRegToValues) {
135#ifndef NDEBUG
136 DenseSet<Register> SeenRegs;
137#endif
138 for (size_t I = 0, E = Assignments.size(); I < E; ++I) {
139 const auto &CoalescedIntervals = Assignments[I];
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(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(Slot);
209 if (SegmentIt != OtherLI->end() && SegmentIt->contains(Slot)) {
210 LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n");
211 DbgValue->setDebugValueUndef();
212 LastUndefResult = true;
213 break;
214 }
215 }
216 }
217 }
218 }
219}
220
221bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {
222 LLVM_DEBUG({
223 dbgs() << "********** Register Coloring **********\n"
224 << "********** Function: " << MF.getName() << '\n';
225 });
226
227 // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual
228 // registers could be modified before the longjmp is executed, resulting in
229 // the wrong value being used afterwards.
230 // TODO: Does WebAssembly need to care about setjmp for register coloring?
231 if (MF.exposesReturnsTwice())
232 return false;
233
235 LiveIntervals *Liveness = &getAnalysis<LiveIntervals>();
236 const MachineBlockFrequencyInfo *MBFI =
237 &getAnalysis<MachineBlockFrequencyInfo>();
239
240 // We don't preserve SSA form.
241 MRI->leaveSSA();
242
243 // Gather all register intervals into a list and sort them.
244 unsigned NumVRegs = MRI->getNumVirtRegs();
245 SmallVector<LiveInterval *, 0> SortedIntervals;
246 SortedIntervals.reserve(NumVRegs);
247
248 // Record DBG_VALUEs and their SlotIndexes.
249 auto DbgVRegToValues = buildVRegToDbgValueMap(MF, Liveness);
250
251 LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");
252 for (unsigned I = 0; I < NumVRegs; ++I) {
254 if (MFI.isVRegStackified(VReg))
255 continue;
256 // Skip unused registers, which can use $drop.
257 if (MRI->use_empty(VReg))
258 continue;
259
260 LiveInterval *LI = &Liveness->getInterval(VReg);
261 assert(LI->weight() == 0.0f);
262 LI->setWeight(computeWeight(MRI, MBFI, VReg));
263 LLVM_DEBUG(LI->dump());
264 SortedIntervals.push_back(LI);
265 }
266 LLVM_DEBUG(dbgs() << '\n');
267
268 // Sort them to put arguments first (since we don't want to rename live-in
269 // registers), by weight next, and then by position.
270 // TODO: Investigate more intelligent sorting heuristics. For starters, we
271 // should try to coalesce adjacent live intervals before non-adjacent ones.
272 llvm::sort(SortedIntervals, [MRI](LiveInterval *LHS, LiveInterval *RHS) {
273 if (MRI->isLiveIn(LHS->reg()) != MRI->isLiveIn(RHS->reg()))
274 return MRI->isLiveIn(LHS->reg());
275 if (LHS->weight() != RHS->weight())
276 return LHS->weight() > RHS->weight();
277 if (LHS->empty() || RHS->empty())
278 return !LHS->empty() && RHS->empty();
279 return *LHS < *RHS;
280 });
281
282 LLVM_DEBUG(dbgs() << "Coloring register intervals:\n");
283 SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u);
285 SortedIntervals.size());
286 BitVector UsedColors(SortedIntervals.size());
287 bool Changed = false;
288 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
289 LiveInterval *LI = SortedIntervals[I];
290 Register Old = LI->reg();
291 size_t Color = I;
292 const TargetRegisterClass *RC = MRI->getRegClass(Old);
293
294 // Check if it's possible to reuse any of the used colors.
295 if (!MRI->isLiveIn(Old))
296 for (unsigned C : UsedColors.set_bits()) {
297 if (MRI->getRegClass(SortedIntervals[C]->reg()) != RC)
298 continue;
299 for (LiveInterval *OtherLI : Assignments[C])
300 if (!OtherLI->empty() && OtherLI->overlaps(*LI))
301 goto continue_outer;
302 Color = C;
303 break;
304 continue_outer:;
305 }
306
307 Register New = SortedIntervals[Color]->reg();
308 SlotMapping[I] = New;
309 Changed |= Old != New;
310 UsedColors.set(Color);
311 Assignments[Color].push_back(LI);
312 // If we reassigned the stack pointer, update the debug frame base info.
313 if (Old != New && MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Old)
314 MFI.setFrameBaseVreg(New);
315 LLVM_DEBUG(dbgs() << "Assigning vreg" << Register::virtReg2Index(LI->reg())
316 << " to vreg" << Register::virtReg2Index(New) << "\n");
317 }
318 if (!Changed)
319 return false;
320
321 // Set DBG_VALUEs that will be invalid after coalescing to undef.
322 undefInvalidDbgValues(Liveness, Assignments, DbgVRegToValues);
323
324 // Rewrite register operands.
325 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
326 Register Old = SortedIntervals[I]->reg();
327 unsigned New = SlotMapping[I];
328 if (Old != New)
329 MRI->replaceRegWith(Old, New);
330 }
331 return true;
332}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
if(VerifyEach)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file declares WebAssembly-specific per-machine-function information.
static DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness)
static float computeWeight(const MachineRegisterInfo *MRI, const MachineBlockFrequencyInfo *MBFI, unsigned VReg)
#define DEBUG_TYPE
static void undefInvalidDbgValues(const LiveIntervals *Liveness, const ArrayRef< SmallVector< LiveInterval *, 4 > > &Assignments, DenseMap< Register, std::vector< std::pair< SlotIndex, MachineInstr * > > > &DbgVRegToValues)
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Value * RHS
Value * LHS
Class recording the (high level) value of a variable.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:269
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
This class represents an Operation in the Expression.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:687
float weight() const
Definition: LiveInterval.h:719
Register reg() const
Definition: LiveInterval.h:718
void setWeight(float Value)
Definition: LiveInterval.h:721
SlotIndexes * getSlotIndexes() const
LiveInterval & getInterval(Register Reg)
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:68
SlotIndexes pass.
Definition: SlotIndexes.h:300
SlotIndex getMBBEndIdx(unsigned Num) const
Returns the last index in the given basic block number.
Definition: SlotIndexes.h:462
SlotIndex getInstructionIndex(const MachineInstr &MI, bool IgnoreBundle=false) const
Returns the base index for the given instruction.
Definition: SlotIndexes.h:371
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:452
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:676
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1738
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createWebAssemblyRegColoring()
This struct contains the mappings from the slot numbers to unnamed metadata nodes,...
Definition: SlotMapping.h:33