WebAssemblyRegColoring.cpp revision 360660
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 "llvm/CodeGen/LiveIntervals.h" 22#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 23#include "llvm/CodeGen/MachineRegisterInfo.h" 24#include "llvm/CodeGen/Passes.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/raw_ostream.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(); 43 AU.addRequired<LiveIntervals>(); 44 AU.addRequired<MachineBlockFrequencyInfo>(); 45 AU.addPreserved<MachineBlockFrequencyInfo>(); 46 AU.addPreservedID(MachineDominatorsID); 47 MachineFunctionPass::getAnalysisUsage(AU); 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 60FunctionPass *llvm::createWebAssemblyRegColoring() { 61 return new WebAssemblyRegColoring(); 62} 63 64// Compute the total spill weight for VReg. 65static float computeWeight(const MachineRegisterInfo *MRI, 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) { 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 88 MachineRegisterInfo *MRI = &MF.getRegInfo(); 89 LiveIntervals *Liveness = &getAnalysis<LiveIntervals>(); 90 const MachineBlockFrequencyInfo *MBFI = 91 &getAnalysis<MachineBlockFrequencyInfo>(); 92 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 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 = TargetRegisterInfo::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->weight = 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); 132 SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments( 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 LLVM_DEBUG( 161 dbgs() << "Assigning vreg" << TargetRegisterInfo::virtReg2Index(LI->reg) 162 << " to vreg" << 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