Home | History | Annotate | Download | only in WebAssembly 
      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"
     28 using namespace llvm;
     29 
     30 #define DEBUG_TYPE "wasm-reg-coloring"
     31 
     32 namespace {
     33 class WebAssemblyRegColoring final : public MachineFunctionPass {
     34 public:
     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 
     53 private:
     54 };
     55 } // end anonymous namespace
     56 
     57 char WebAssemblyRegColoring::ID = 0;
     58 FunctionPass *llvm::createWebAssemblyRegColoring() {
     59   return new WebAssemblyRegColoring();
     60 }
     61 
     62 // Compute the total spill weight for VReg.
     63 static 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 
     73 bool 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 $drop.
    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