WebAssemblyRegColoring.cpp revision 292941
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/// \brief 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/LiveIntervalAnalysis.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" 28using namespace llvm; 29 30#define DEBUG_TYPE "wasm-reg-coloring" 31 32namespace { 33class WebAssemblyRegColoring final : public MachineFunctionPass { 34public: 35 static char ID; // Pass identification, replacement for typeid 36 WebAssemblyRegColoring() : MachineFunctionPass(ID) {} 37 38 const char *getPassName() const override { 39 return "WebAssembly Register Coloring"; 40 } 41 42 void getAnalysisUsage(AnalysisUsage &AU) const override { 43 AU.setPreservesCFG(); 44 AU.addRequired<LiveIntervals>(); 45 AU.addRequired<MachineBlockFrequencyInfo>(); 46 AU.addPreserved<MachineBlockFrequencyInfo>(); 47 AU.addPreservedID(MachineDominatorsID); 48 MachineFunctionPass::getAnalysisUsage(AU); 49 } 50 51 bool runOnMachineFunction(MachineFunction &MF) override; 52 53private: 54}; 55} // end anonymous namespace 56 57char WebAssemblyRegColoring::ID = 0; 58FunctionPass *llvm::createWebAssemblyRegColoring() { 59 return new WebAssemblyRegColoring(); 60} 61 62// Compute the total spill weight for VReg. 63static float computeWeight(const MachineRegisterInfo *MRI, 64 const MachineBlockFrequencyInfo *MBFI, 65 unsigned VReg) { 66 float weight = 0.0f; 67 for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg)) 68 weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI, 69 MO.getParent()); 70 return weight; 71} 72 73bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) { 74 DEBUG({ 75 dbgs() << "********** Register Coloring **********\n" 76 << "********** Function: " << MF.getName() << '\n'; 77 }); 78 79 // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual 80 // registers could be modified before the longjmp is executed, resulting in 81 // the wrong value being used afterwards. (See <rdar://problem/8007500>.) 82 // TODO: Does WebAssembly need to care about setjmp for register coloring? 83 if (MF.exposesReturnsTwice()) 84 return false; 85 86 MachineRegisterInfo *MRI = &MF.getRegInfo(); 87 LiveIntervals *Liveness = &getAnalysis<LiveIntervals>(); 88 const MachineBlockFrequencyInfo *MBFI = 89 &getAnalysis<MachineBlockFrequencyInfo>(); 90 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 91 92 // Gather all register intervals into a list and sort them. 93 unsigned NumVRegs = MRI->getNumVirtRegs(); 94 SmallVector<LiveInterval *, 0> SortedIntervals; 95 SortedIntervals.reserve(NumVRegs); 96 97 DEBUG(dbgs() << "Interesting register intervals:\n"); 98 for (unsigned i = 0; i < NumVRegs; ++i) { 99 unsigned VReg = TargetRegisterInfo::index2VirtReg(i); 100 if (MFI.isVRegStackified(VReg)) 101 continue; 102 // Skip unused registers, which can use $discard. 103 if (MRI->use_empty(VReg)) 104 continue; 105 106 LiveInterval *LI = &Liveness->getInterval(VReg); 107 assert(LI->weight == 0.0f); 108 LI->weight = computeWeight(MRI, MBFI, VReg); 109 DEBUG(LI->dump()); 110 SortedIntervals.push_back(LI); 111 } 112 DEBUG(dbgs() << '\n'); 113 114 // Sort them to put arguments first (since we don't want to rename live-in 115 // registers), by weight next, and then by position. 116 // TODO: Investigate more intelligent sorting heuristics. For starters, we 117 // should try to coalesce adjacent live intervals before non-adjacent ones. 118 std::sort(SortedIntervals.begin(), SortedIntervals.end(), 119 [MRI](LiveInterval *LHS, LiveInterval *RHS) { 120 if (MRI->isLiveIn(LHS->reg) != MRI->isLiveIn(RHS->reg)) 121 return MRI->isLiveIn(LHS->reg); 122 if (LHS->weight != RHS->weight) 123 return LHS->weight > RHS->weight; 124 if (LHS->empty() || RHS->empty()) 125 return !LHS->empty() && RHS->empty(); 126 return *LHS < *RHS; 127 }); 128 129 DEBUG(dbgs() << "Coloring register intervals:\n"); 130 SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u); 131 SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments( 132 SortedIntervals.size()); 133 BitVector UsedColors(SortedIntervals.size()); 134 bool Changed = false; 135 for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) { 136 LiveInterval *LI = SortedIntervals[i]; 137 unsigned Old = LI->reg; 138 size_t Color = i; 139 const TargetRegisterClass *RC = MRI->getRegClass(Old); 140 141 // Check if it's possible to reuse any of the used colors. 142 if (!MRI->isLiveIn(Old)) 143 for (int C(UsedColors.find_first()); C != -1; 144 C = UsedColors.find_next(C)) { 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 DEBUG(dbgs() << "Assigning vreg" 161 << TargetRegisterInfo::virtReg2Index(LI->reg) << " to vreg" 162 << TargetRegisterInfo::virtReg2Index(New) << "\n"); 163 } 164 if (!Changed) 165 return false; 166 167 // Rewrite register operands. 168 for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) { 169 unsigned Old = SortedIntervals[i]->reg; 170 unsigned New = SlotMapping[i]; 171 if (Old != New) 172 MRI->replaceRegWith(Old, New); 173 } 174 return true; 175} 176