LLVM  14.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"
27 using namespace llvm;
28 
29 #define DEBUG_TYPE "wasm-reg-coloring"
30 
31 namespace {
32 class WebAssemblyRegColoring final : public MachineFunctionPass {
33 public:
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 
52 private:
53 };
54 } // end anonymous namespace
55 
57 INITIALIZE_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 bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) {
76  LLVM_DEBUG({
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) {
101  unsigned VReg = Register::index2VirtReg(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  unsigned 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  unsigned 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  unsigned Old = SortedIntervals[I]->reg();
172  unsigned New = SlotMapping[I];
173  if (Old != New)
174  MRI->replaceRegWith(Old, New);
175  }
176  return true;
177 }
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
WebAssembly.h
llvm::LiveRange::empty
bool empty() const
Definition: LiveInterval.h:374
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::LiveInterval::weight
float weight() const
Definition: LiveInterval.h:712
llvm::MachineFunction::exposesReturnsTwice
bool exposesReturnsTwice() const
exposesReturnsTwice - Returns true if the function calls setjmp or any other similar functions with a...
Definition: MachineFunction.h:688
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::WebAssemblyFunctionInfo::setFrameBaseVreg
void setFrameBaseVreg(unsigned Reg)
Definition: WebAssemblyMachineFunctionInfo.h:107
llvm::createWebAssemblyRegColoring
FunctionPass * createWebAssemblyRegColoring()
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:757
llvm::Register::index2VirtReg
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:636
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineFunction::getInfo
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
Definition: MachineFunction.h:724
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
DEBUG_TYPE
#define DEBUG_TYPE
Definition: WebAssemblyRegColoring.cpp:29
llvm::LiveInterval::dump
void dump() const
Definition: LiveInterval.cpp:1063
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineRegisterInfo::reg_nodbg_operands
iterator_range< reg_nodbg_iterator > reg_nodbg_operands(Register Reg) const
Definition: MachineRegisterInfo.h:337
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::BitVector
Definition: BitVector.h:74
llvm::LiveInterval
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:680
llvm::MachineRegisterInfo::use_empty
bool use_empty(Register RegNo) const
use_empty - Return true if there are no instructions using the specified register.
Definition: MachineRegisterInfo.h:506
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
Passes.h
llvm::SlotMapping
This struct contains the mappings from the slot numbers to unnamed metadata nodes,...
Definition: SlotMapping.h:32
LiveIntervals.h
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::WebAssemblyFunctionInfo::isVRegStackified
bool isVRegStackified(unsigned VReg) const
Definition: WebAssemblyMachineFunctionInfo.h:136
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:541
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::WebAssemblyFunctionInfo
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
Definition: WebAssemblyMachineFunctionInfo.h:33
WebAssemblyMachineFunctionInfo.h
llvm::LiveIntervals::getInterval
LiveInterval & getInterval(Register Reg)
Definition: LiveIntervals.h:114
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
computeWeight
static float computeWeight(const MachineRegisterInfo *MRI, const MachineBlockFrequencyInfo *MBFI, unsigned VReg)
Definition: WebAssemblyRegColoring.cpp:65
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
llvm::LiveInterval::setWeight
void setWeight(float Value)
Definition: LiveInterval.h:714
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::MachineRegisterInfo::replaceRegWith
void replaceRegWith(Register FromReg, Register ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
Definition: MachineRegisterInfo.cpp:380
INITIALIZE_PASS
INITIALIZE_PASS(WebAssemblyRegColoring, DEBUG_TYPE, "Minimize number of registers used", false, false) FunctionPass *llvm
Definition: WebAssemblyRegColoring.cpp:57
llvm::MachineRegisterInfo::isLiveIn
bool isLiveIn(Register Reg) const
Definition: MachineRegisterInfo.cpp:436
llvm::LiveIntervals::getSpillWeight
static float getSpillWeight(bool isDef, bool isUse, const MachineBlockFrequencyInfo *MBFI, const MachineInstr &MI)
Calculate the spill weight to assign to a single instruction.
Definition: LiveIntervals.cpp:868
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
llvm::WebAssemblyFunctionInfo::isFrameBaseVirtual
bool isFrameBaseVirtual() const
Definition: WebAssemblyMachineFunctionInfo.h:114
llvm::LiveIntervals
Definition: LiveIntervals.h:54
llvm::MachineDominatorsID
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:711
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::WebAssemblyFunctionInfo::getFrameBaseVreg
unsigned getFrameBaseVreg() const
Definition: WebAssemblyMachineFunctionInfo.h:108
llvm::Register::virtReg2Index
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
raw_ostream.h
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
MachineBlockFrequencyInfo.h
Debug.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37