From e5484b43294ac41afe46851a066e1699daf5744f Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Mon, 16 Nov 2015 16:18:28 +0000 Subject: [PATCH] [WebAssembly] Prototype passes for register coloring and register stackifying. These passes are not yet enabled by default. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@253217 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Target/WebAssembly/CMakeLists.txt | 2 + lib/Target/WebAssembly/WebAssembly.h | 2 + .../WebAssemblyMachineFunctionInfo.h | 19 ++ .../WebAssembly/WebAssemblyRegColoring.cpp | 172 ++++++++++++++++++ .../WebAssembly/WebAssemblyRegStackify.cpp | 146 +++++++++++++++ 5 files changed, 341 insertions(+) create mode 100644 lib/Target/WebAssembly/WebAssemblyRegColoring.cpp create mode 100644 lib/Target/WebAssembly/WebAssemblyRegStackify.cpp diff --git a/lib/Target/WebAssembly/CMakeLists.txt b/lib/Target/WebAssembly/CMakeLists.txt index 47fa9c631ba..82f72269d0d 100644 --- a/lib/Target/WebAssembly/CMakeLists.txt +++ b/lib/Target/WebAssembly/CMakeLists.txt @@ -21,7 +21,9 @@ add_llvm_target(WebAssemblyCodeGen WebAssemblyMachineFunctionInfo.cpp WebAssemblyMCInstLower.cpp WebAssemblyRegisterInfo.cpp + WebAssemblyRegColoring.cpp WebAssemblyRegNumbering.cpp + WebAssemblyRegStackify.cpp WebAssemblySelectionDAGInfo.cpp WebAssemblySubtarget.cpp WebAssemblyTargetMachine.cpp diff --git a/lib/Target/WebAssembly/WebAssembly.h b/lib/Target/WebAssembly/WebAssembly.h index be6c20c1a7c..59856de9553 100644 --- a/lib/Target/WebAssembly/WebAssembly.h +++ b/lib/Target/WebAssembly/WebAssembly.h @@ -26,6 +26,8 @@ class FunctionPass; FunctionPass *createWebAssemblyISelDag(WebAssemblyTargetMachine &TM, CodeGenOpt::Level OptLevel); +FunctionPass *createWebAssemblyRegStackify(); +FunctionPass *createWebAssemblyRegColoring(); FunctionPass *createWebAssemblyCFGStackify(); FunctionPass *createWebAssemblyRegNumbering(); diff --git a/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h b/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h index 475dcc33d78..6e8b1dcb7a5 100644 --- a/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h +++ b/lib/Target/WebAssembly/WebAssemblyMachineFunctionInfo.h @@ -33,6 +33,14 @@ class WebAssemblyFunctionInfo final : public MachineFunctionInfo { /// A mapping from CodeGen vreg index to WebAssembly register number. std::vector WARegs; + /// A mapping from CodeGen vreg index to a boolean value indicating whether + /// the given register is considered to be "stackified", meaning it has been + /// determined or made to meet the stack requirements: + /// - single use (per path) + /// - single def (per path) + /// - defined and used in FIFO order with other stack registers + BitVector VRegStackified; + public: explicit WebAssemblyFunctionInfo(MachineFunction &MF) : MF(MF) {} ~WebAssemblyFunctionInfo() override; @@ -45,6 +53,17 @@ public: static const unsigned UnusedReg = -1u; + void stackifyVReg(unsigned VReg) { + if (TargetRegisterInfo::virtReg2Index(VReg) >= VRegStackified.size()) + VRegStackified.resize(TargetRegisterInfo::virtReg2Index(VReg) + 1); + VRegStackified.set(TargetRegisterInfo::virtReg2Index(VReg)); + } + bool isVRegStackified(unsigned VReg) const { + if (TargetRegisterInfo::virtReg2Index(VReg) >= VRegStackified.size()) + return false; + return VRegStackified.test(TargetRegisterInfo::virtReg2Index(VReg)); + } + void initWARegs(); void setWAReg(unsigned VReg, unsigned WAReg) { assert(WAReg != UnusedReg); diff --git a/lib/Target/WebAssembly/WebAssemblyRegColoring.cpp b/lib/Target/WebAssembly/WebAssemblyRegColoring.cpp new file mode 100644 index 00000000000..1cf9956a3e9 --- /dev/null +++ b/lib/Target/WebAssembly/WebAssemblyRegColoring.cpp @@ -0,0 +1,172 @@ +//===-- WebAssemblyRegColoring.cpp - Register coloring --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// \brief This file implements a virtual register coloring pass. +/// +/// WebAssembly doesn't have a fixed number of registers, but it is still +/// desirable to minimize the total number of registers used in each function. +/// +/// This code is modeled after lib/CodeGen/StackSlotColoring.cpp. +/// +//===----------------------------------------------------------------------===// + +#include "WebAssembly.h" +#include "WebAssemblyMachineFunctionInfo.h" +#include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +#define DEBUG_TYPE "wasm-reg-coloring" + +namespace { +class WebAssemblyRegColoring final : public MachineFunctionPass { +public: + static char ID; // Pass identification, replacement for typeid + WebAssemblyRegColoring() : MachineFunctionPass(ID) {} + + const char *getPassName() const override { + return "WebAssembly Register Coloring"; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreservedID(MachineDominatorsID); + MachineFunctionPass::getAnalysisUsage(AU); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + +private: +}; +} // end anonymous namespace + +char WebAssemblyRegColoring::ID = 0; +FunctionPass *llvm::createWebAssemblyRegColoring() { + return new WebAssemblyRegColoring(); +} + +// Compute the total spill weight for VReg. +static float computeWeight(const MachineRegisterInfo *MRI, + const MachineBlockFrequencyInfo *MBFI, + unsigned VReg) { + float weight = 0.0f; + for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg)) + weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI, + MO.getParent()); + return weight; +} + +bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) { + DEBUG({ + dbgs() << "********** Register Coloring **********\n" + << "********** Function: " << MF.getName() << '\n'; + }); + + // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual + // registers could be modified before the longjmp is executed, resulting in + // the wrong value being used afterwards. (See .) + // TODO: Does WebAssembly need to care about setjmp for register coloring? + if (MF.exposesReturnsTwice()) + return false; + + MachineRegisterInfo *MRI = &MF.getRegInfo(); + LiveIntervals *Liveness = &getAnalysis(); + const MachineBlockFrequencyInfo *MBFI = + &getAnalysis(); + WebAssemblyFunctionInfo &MFI = *MF.getInfo(); + + // Gather all register intervals into a list and sort them. + unsigned NumVRegs = MRI->getNumVirtRegs(); + SmallVector SortedIntervals; + SortedIntervals.reserve(NumVRegs); + + DEBUG(dbgs() << "Interesting register intervals:\n"); + for (unsigned i = 0; i < NumVRegs; ++i) { + unsigned VReg = TargetRegisterInfo::index2VirtReg(i); + if (MFI.isVRegStackified(VReg)) + continue; + + LiveInterval *LI = &Liveness->getInterval(VReg); + assert(LI->weight == 0.0f); + LI->weight = computeWeight(MRI, MBFI, VReg); + DEBUG(LI->dump()); + SortedIntervals.push_back(LI); + } + DEBUG(dbgs() << '\n'); + + // Sort them to put arguments first (since we don't want to rename live-in + // registers), by weight next, and then by position. + // TODO: Investigate more intelligent sorting heuristics. For starters, we + // should try to coalesce adjacent live intervals before non-adjacent ones. + std::sort(SortedIntervals.begin(), SortedIntervals.end(), + [MRI](LiveInterval *LHS, LiveInterval *RHS) { + if (MRI->isLiveIn(LHS->reg) != MRI->isLiveIn(RHS->reg)) + return MRI->isLiveIn(LHS->reg); + if (LHS->weight != RHS->weight) + return LHS->weight > RHS->weight; + if (LHS->empty() || RHS->empty()) + return !LHS->empty() && RHS->empty(); + return *LHS < *RHS; + }); + + DEBUG(dbgs() << "Coloring register intervals:\n"); + SmallVector SlotMapping(SortedIntervals.size(), -1u); + SmallVector, 16> Assignments( + SortedIntervals.size()); + BitVector UsedColors(SortedIntervals.size()); + bool Changed = false; + for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) { + LiveInterval *LI = SortedIntervals[i]; + unsigned Old = LI->reg; + size_t Color = i; + const TargetRegisterClass *RC = MRI->getRegClass(Old); + + // Check if it's possible to reuse any of the used colors. + if (!MRI->isLiveIn(Old)) + for (int C(UsedColors.find_first()); C != -1; + C = UsedColors.find_next(C)) { + if (MRI->getRegClass(SortedIntervals[C]->reg) != RC) + continue; + for (LiveInterval *OtherLI : Assignments[C]) + if (!OtherLI->empty() && OtherLI->overlaps(*LI)) + goto continue_outer; + Color = C; + break; + continue_outer:; + } + + unsigned New = SortedIntervals[Color]->reg; + SlotMapping[i] = New; + Changed |= Old != New; + UsedColors.set(Color); + Assignments[Color].push_back(LI); + DEBUG(dbgs() << "Assigning vreg" + << TargetRegisterInfo::virtReg2Index(LI->reg) << " to vreg" + << TargetRegisterInfo::virtReg2Index(New) << "\n"); + } + if (!Changed) + return false; + + // Rewrite register operands. + for (size_t i = 0, e = SortedIntervals.size(); i < e; ++i) { + unsigned Old = SortedIntervals[i]->reg; + unsigned New = SlotMapping[i]; + if (Old != New) + MRI->replaceRegWith(Old, New); + } + return true; +} diff --git a/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp b/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp new file mode 100644 index 00000000000..a159b4011e2 --- /dev/null +++ b/lib/Target/WebAssembly/WebAssemblyRegStackify.cpp @@ -0,0 +1,146 @@ +//===-- WebAssemblyRegStackify.cpp - Register Stackification --------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// \file +/// \brief This file implements a register stacking pass. +/// +/// This pass reorders instructions to put register uses and defs in an order +/// such that they form single-use expression trees. Registers fitting this form +/// are then marked as "stackified", meaning references to them are replaced by +/// "push" and "pop" from the stack. +/// +/// This is primarily a code size optimiation, since temporary values on the +/// expression don't need to be named. +/// +//===----------------------------------------------------------------------===// + +#include "WebAssembly.h" +#include "WebAssemblyMachineFunctionInfo.h" +#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +using namespace llvm; + +#define DEBUG_TYPE "wasm-reg-stackify" + +namespace { +class WebAssemblyRegStackify final : public MachineFunctionPass { + const char *getPassName() const override { + return "WebAssembly Register Stackify"; + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addPreserved(); + AU.addPreservedID(MachineDominatorsID); + MachineFunctionPass::getAnalysisUsage(AU); + } + + bool runOnMachineFunction(MachineFunction &MF) override; + +public: + static char ID; // Pass identification, replacement for typeid + WebAssemblyRegStackify() : MachineFunctionPass(ID) {} +}; +} // end anonymous namespace + +char WebAssemblyRegStackify::ID = 0; +FunctionPass *llvm::createWebAssemblyRegStackify() { + return new WebAssemblyRegStackify(); +} + +bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) { + DEBUG(dbgs() << "********** Register Stackifying **********\n" + "********** Function: " + << MF.getName() << '\n'); + + bool Changed = false; + MachineRegisterInfo &MRI = MF.getRegInfo(); + WebAssemblyFunctionInfo &MFI = *MF.getInfo(); + + // Walk the instructions from the bottom up. Currently we don't look past + // block boundaries, and the blocks aren't ordered so the block visitation + // order isn't significant, but we may want to change this in the future. + for (MachineBasicBlock &MBB : MF) { + for (MachineInstr &MI : reverse(MBB)) { + MachineInstr *Insert = &MI; + + // Don't nest anything inside a phi. + if (Insert->getOpcode() == TargetOpcode::PHI) + break; + + // Iterate through the inputs in reverse order, since we'll be pulling + // operands off the stack in FIFO order. + for (MachineOperand &Op : reverse(Insert->uses())) { + // We're only interested in explicit virtual register operands. + if (!Op.isReg() || Op.isImplicit()) + continue; + + unsigned Reg = Op.getReg(); + if (!TargetRegisterInfo::isVirtualRegister(Reg)) + continue; + + // Only consider registers with a single definition. + // TODO: Eventually we may relax this, to stackify phi transfers. + MachineInstr *Def = MRI.getVRegDef(Reg); + if (!Def) + continue; + + // There's no use in nesting implicit defs inside anything. + if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF) + continue; + + // Single-use expression trees require defs that have one use, or that + // they be trivially clonable. + // TODO: Eventually we'll relax this, to take advantage of set_local + // returning its result. + bool OneUse = MRI.hasOneUse(Reg); + if (!OneUse && !Def->isMoveImmediate()) + continue; + + // For now, be conservative and don't look across block boundaries, + // unless we have something trivially clonable. + // TODO: Be more aggressive. + if (Def->getParent() != &MBB && !Def->isMoveImmediate()) + continue; + + // For now, be simple and don't reorder loads, stores, or side effects. + // TODO: Be more aggressive. + if ((Def->mayLoad() || Def->mayStore() || + Def->hasUnmodeledSideEffects())) + continue; + + Changed = true; + if (OneUse) { + // Move the def down and nest it in the current instruction. + MBB.insert(MachineBasicBlock::instr_iterator(Insert), + Def->removeFromParent()); + MFI.stackifyVReg(Reg); + Insert = Def; + } else { + // Clone the def down and nest it in the current instruction. + MachineInstr *Clone = MF.CloneMachineInstr(Def); + unsigned OldReg = Def->getOperand(0).getReg(); + unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg)); + assert(Op.getReg() == OldReg); + assert(Clone->getOperand(0).getReg() == OldReg); + Op.setReg(NewReg); + Clone->getOperand(0).setReg(NewReg); + MBB.insert(MachineBasicBlock::instr_iterator(Insert), Clone); + MFI.stackifyVReg(Reg); + Insert = Clone; + } + } + } + } + + return Changed; +} -- 2.34.1