LLVM 17.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
75bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {
77 dbgs() << "********** Register Coloring **********\n"
78 << "********** Function: " << MF.getName() << '\n';
79 });
80
81 // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual
82 // registers could be modified before the longjmp is executed, resulting in
83 // the wrong value being used afterwards. (See <rdar://problem/8007500>.)
84 // TODO: Does WebAssembly need to care about setjmp for register coloring?
85 if (MF.exposesReturnsTwice())
86 return false;
87
89 LiveIntervals *Liveness = &getAnalysis<LiveIntervals>();
90 const MachineBlockFrequencyInfo *MBFI =
91 &getAnalysis<MachineBlockFrequencyInfo>();
93
94 // Gather all register intervals into a list and sort them.
95 unsigned NumVRegs = MRI->getNumVirtRegs();
96 SmallVector<LiveInterval *, 0> SortedIntervals;
97 SortedIntervals.reserve(NumVRegs);
98
99 LLVM_DEBUG(dbgs() << "Interesting register intervals:\n");
100 for (unsigned I = 0; I < NumVRegs; ++I) {
102 if (MFI.isVRegStackified(VReg))
103 continue;
104 // Skip unused registers, which can use $drop.
105 if (MRI->use_empty(VReg))
106 continue;
107
108 LiveInterval *LI = &Liveness->getInterval(VReg);
109 assert(LI->weight() == 0.0f);
110 LI->setWeight(computeWeight(MRI, MBFI, VReg));
111 LLVM_DEBUG(LI->dump());
112 SortedIntervals.push_back(LI);
113 }
114 LLVM_DEBUG(dbgs() << '\n');
115
116 // Sort them to put arguments first (since we don't want to rename live-in
117 // registers), by weight next, and then by position.
118 // TODO: Investigate more intelligent sorting heuristics. For starters, we
119 // should try to coalesce adjacent live intervals before non-adjacent ones.
120 llvm::sort(SortedIntervals, [MRI](LiveInterval *LHS, LiveInterval *RHS) {
121 if (MRI->isLiveIn(LHS->reg()) != MRI->isLiveIn(RHS->reg()))
122 return MRI->isLiveIn(LHS->reg());
123 if (LHS->weight() != RHS->weight())
124 return LHS->weight() > RHS->weight();
125 if (LHS->empty() || RHS->empty())
126 return !LHS->empty() && RHS->empty();
127 return *LHS < *RHS;
128 });
129
130 LLVM_DEBUG(dbgs() << "Coloring register intervals:\n");
131 SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u);
133 SortedIntervals.size());
134 BitVector UsedColors(SortedIntervals.size());
135 bool Changed = false;
136 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
137 LiveInterval *LI = SortedIntervals[I];
138 Register Old = LI->reg();
139 size_t Color = I;
140 const TargetRegisterClass *RC = MRI->getRegClass(Old);
141
142 // Check if it's possible to reuse any of the used colors.
143 if (!MRI->isLiveIn(Old))
144 for (unsigned C : UsedColors.set_bits()) {
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 Register New = SortedIntervals[Color]->reg();
156 SlotMapping[I] = New;
157 Changed |= Old != New;
158 UsedColors.set(Color);
159 Assignments[Color].push_back(LI);
160 // If we reassigned the stack pointer, update the debug frame base info.
161 if (Old != New && MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Old)
162 MFI.setFrameBaseVreg(New);
163 LLVM_DEBUG(dbgs() << "Assigning vreg" << Register::virtReg2Index(LI->reg())
164 << " to vreg" << Register::virtReg2Index(New) << "\n");
165 }
166 if (!Changed)
167 return false;
168
169 // Rewrite register operands.
170 for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) {
171 Register Old = SortedIntervals[I]->reg();
172 unsigned New = SlotMapping[I];
173 if (Old != New)
174 MRI->replaceRegWith(Old, New);
175 }
176 return true;
177}
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#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 float computeWeight(const MachineRegisterInfo *MRI, const MachineBlockFrequencyInfo *MBFI, unsigned VReg)
#define DEBUG_TYPE
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Value * RHS
Value * LHS
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:265
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
float weight() const
Definition: LiveInterval.h:718
Register reg() const
Definition: LiveInterval.h:717
void setWeight(float Value)
Definition: LiveInterval.h:720
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
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:667
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
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 ...
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.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1730
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:32