blob: 8619cbdcb5eed2bd703692fd4187d15e9afa29eb [file] [log] [blame]
//===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file converts any remaining registers into WebAssembly locals.
///
/// After register stackification and register coloring, convert non-stackified
/// registers into locals, inserting explicit get_local and set_local
/// instructions.
///
//===----------------------------------------------------------------------===//
#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblyMachineFunctionInfo.h"
#include "WebAssemblySubtarget.h"
#include "WebAssemblyUtilities.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.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-explicit-locals"
// A command-line option to disable this pass. Note that this produces output
// which is not valid WebAssembly, though it may be more convenient for writing
// LLVM unit tests with.
static cl::opt<bool> DisableWebAssemblyExplicitLocals(
"disable-wasm-explicit-locals", cl::ReallyHidden,
cl::desc("WebAssembly: Disable emission of get_local/set_local."),
cl::init(false));
namespace {
class WebAssemblyExplicitLocals final : public MachineFunctionPass {
StringRef getPassName() const override {
return "WebAssembly Explicit Locals";
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesCFG();
AU.addPreserved<MachineBlockFrequencyInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool runOnMachineFunction(MachineFunction &MF) override;
public:
static char ID; // Pass identification, replacement for typeid
WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
};
} // end anonymous namespace
char WebAssemblyExplicitLocals::ID = 0;
INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
"Convert registers to WebAssembly locals", false, false)
FunctionPass *llvm::createWebAssemblyExplicitLocals() {
return new WebAssemblyExplicitLocals();
}
/// Return a local id number for the given register, assigning it a new one
/// if it doesn't yet have one.
static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
unsigned &CurLocal, unsigned Reg) {
auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
if (P.second)
++CurLocal;
return P.first->second;
}
/// Get the appropriate drop opcode for the given register class.
static unsigned getDropOpcode(const TargetRegisterClass *RC) {
if (RC == &WebAssembly::I32RegClass)
return WebAssembly::DROP_I32;
if (RC == &WebAssembly::I64RegClass)
return WebAssembly::DROP_I64;
if (RC == &WebAssembly::F32RegClass)
return WebAssembly::DROP_F32;
if (RC == &WebAssembly::F64RegClass)
return WebAssembly::DROP_F64;
if (RC == &WebAssembly::V128RegClass)
return WebAssembly::DROP_V128;
if (RC == &WebAssembly::EXCEPT_REFRegClass)
return WebAssembly::DROP_EXCEPT_REF;
llvm_unreachable("Unexpected register class");
}
/// Get the appropriate get_local opcode for the given register class.
static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
if (RC == &WebAssembly::I32RegClass)
return WebAssembly::GET_LOCAL_I32;
if (RC == &WebAssembly::I64RegClass)
return WebAssembly::GET_LOCAL_I64;
if (RC == &WebAssembly::F32RegClass)
return WebAssembly::GET_LOCAL_F32;
if (RC == &WebAssembly::F64RegClass)
return WebAssembly::GET_LOCAL_F64;
if (RC == &WebAssembly::V128RegClass)
return WebAssembly::GET_LOCAL_V128;
if (RC == &WebAssembly::EXCEPT_REFRegClass)
return WebAssembly::GET_LOCAL_EXCEPT_REF;
llvm_unreachable("Unexpected register class");
}
/// Get the appropriate set_local opcode for the given register class.
static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
if (RC == &WebAssembly::I32RegClass)
return WebAssembly::SET_LOCAL_I32;
if (RC == &WebAssembly::I64RegClass)
return WebAssembly::SET_LOCAL_I64;
if (RC == &WebAssembly::F32RegClass)
return WebAssembly::SET_LOCAL_F32;
if (RC == &WebAssembly::F64RegClass)
return WebAssembly::SET_LOCAL_F64;
if (RC == &WebAssembly::V128RegClass)
return WebAssembly::SET_LOCAL_V128;
if (RC == &WebAssembly::EXCEPT_REFRegClass)
return WebAssembly::SET_LOCAL_EXCEPT_REF;
llvm_unreachable("Unexpected register class");
}
/// Get the appropriate tee_local opcode for the given register class.
static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
if (RC == &WebAssembly::I32RegClass)
return WebAssembly::TEE_LOCAL_I32;
if (RC == &WebAssembly::I64RegClass)
return WebAssembly::TEE_LOCAL_I64;
if (RC == &WebAssembly::F32RegClass)
return WebAssembly::TEE_LOCAL_F32;
if (RC == &WebAssembly::F64RegClass)
return WebAssembly::TEE_LOCAL_F64;
if (RC == &WebAssembly::V128RegClass)
return WebAssembly::TEE_LOCAL_V128;
if (RC == &WebAssembly::EXCEPT_REFRegClass)
return WebAssembly::TEE_LOCAL_EXCEPT_REF;
llvm_unreachable("Unexpected register class");
}
/// Get the type associated with the given register class.
static MVT typeForRegClass(const TargetRegisterClass *RC) {
if (RC == &WebAssembly::I32RegClass)
return MVT::i32;
if (RC == &WebAssembly::I64RegClass)
return MVT::i64;
if (RC == &WebAssembly::F32RegClass)
return MVT::f32;
if (RC == &WebAssembly::F64RegClass)
return MVT::f64;
if (RC == &WebAssembly::EXCEPT_REFRegClass)
return MVT::ExceptRef;
llvm_unreachable("unrecognized register class");
}
/// Given a MachineOperand of a stackified vreg, return the instruction at the
/// start of the expression tree.
static MachineInstr *FindStartOfTree(MachineOperand &MO,
MachineRegisterInfo &MRI,
WebAssemblyFunctionInfo &MFI) {
unsigned Reg = MO.getReg();
assert(MFI.isVRegStackified(Reg));
MachineInstr *Def = MRI.getVRegDef(Reg);
// Find the first stackified use and proceed from there.
for (MachineOperand &DefMO : Def->explicit_uses()) {
if (!DefMO.isReg())
continue;
return FindStartOfTree(DefMO, MRI, MFI);
}
// If there were no stackified uses, we've reached the start.
return Def;
}
bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
"********** Function: "
<< MF.getName() << '\n');
// Disable this pass if directed to do so.
if (DisableWebAssemblyExplicitLocals)
return false;
bool Changed = false;
MachineRegisterInfo &MRI = MF.getRegInfo();
WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
// Map non-stackified virtual registers to their local ids.
DenseMap<unsigned, unsigned> Reg2Local;
// Handle ARGUMENTS first to ensure that they get the designated numbers.
for (MachineBasicBlock::iterator I = MF.begin()->begin(),
E = MF.begin()->end();
I != E;) {
MachineInstr &MI = *I++;
if (!WebAssembly::isArgument(MI))
break;
unsigned Reg = MI.getOperand(0).getReg();
assert(!MFI.isVRegStackified(Reg));
Reg2Local[Reg] = MI.getOperand(1).getImm();
MI.eraseFromParent();
Changed = true;
}
// Start assigning local numbers after the last parameter.
unsigned CurLocal = MFI.getParams().size();
// Precompute the set of registers that are unused, so that we can insert
// drops to their defs.
BitVector UseEmpty(MRI.getNumVirtRegs());
for (unsigned i = 0, e = MRI.getNumVirtRegs(); i < e; ++i)
UseEmpty[i] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(i));
// Visit each instruction in the function.
for (MachineBasicBlock &MBB : MF) {
for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
MachineInstr &MI = *I++;
assert(!WebAssembly::isArgument(MI));
if (MI.isDebugInstr() || MI.isLabel())
continue;
// Replace tee instructions with tee_local. The difference is that tee
// instructins have two defs, while tee_local instructions have one def
// and an index of a local to write to.
if (WebAssembly::isTee(MI)) {
assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
unsigned OldReg = MI.getOperand(2).getReg();
const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
// Stackify the input if it isn't stackified yet.
if (!MFI.isVRegStackified(OldReg)) {
unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
unsigned NewReg = MRI.createVirtualRegister(RC);
unsigned Opc = getGetLocalOpcode(RC);
BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
.addImm(LocalId);
MI.getOperand(2).setReg(NewReg);
MFI.stackifyVReg(NewReg);
}
// Replace the TEE with a TEE_LOCAL.
unsigned LocalId =
getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
unsigned Opc = getTeeLocalOpcode(RC);
BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
MI.getOperand(0).getReg())
.addImm(LocalId)
.addReg(MI.getOperand(2).getReg());
MI.eraseFromParent();
Changed = true;
continue;
}
// Insert set_locals for any defs that aren't stackified yet. Currently
// we handle at most one def.
assert(MI.getDesc().getNumDefs() <= 1);
if (MI.getDesc().getNumDefs() == 1) {
unsigned OldReg = MI.getOperand(0).getReg();
if (!MFI.isVRegStackified(OldReg)) {
const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
unsigned NewReg = MRI.createVirtualRegister(RC);
auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
MI.eraseFromParent();
Changed = true;
continue;
}
if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
unsigned Opc = getDropOpcode(RC);
MachineInstr *Drop =
BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
.addReg(NewReg);
// After the drop instruction, this reg operand will not be used
Drop->getOperand(0).setIsKill();
} else {
unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
unsigned Opc = getSetLocalOpcode(RC);
BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
.addImm(LocalId)
.addReg(NewReg);
}
MI.getOperand(0).setReg(NewReg);
// This register operand is now being used by the inserted drop
// instruction, so make it undead.
MI.getOperand(0).setIsDead(false);
MFI.stackifyVReg(NewReg);
Changed = true;
}
}
// Insert get_locals for any uses that aren't stackified yet.
MachineInstr *InsertPt = &MI;
for (MachineOperand &MO : reverse(MI.explicit_uses())) {
if (!MO.isReg())
continue;
unsigned OldReg = MO.getReg();
// Inline asm may have a def in the middle of the operands. Our contract
// with inline asm register operands is to provide local indices as
// immediates.
if (MO.isDef()) {
assert(MI.getOpcode() == TargetOpcode::INLINEASM);
unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
MRI.removeRegOperandFromUseList(&MO);
MO = MachineOperand::CreateImm(LocalId);
continue;
}
// If we see a stackified register, prepare to insert subsequent
// get_locals before the start of its tree.
if (MFI.isVRegStackified(OldReg)) {
InsertPt = FindStartOfTree(MO, MRI, MFI);
continue;
}
// Our contract with inline asm register operands is to provide local
// indices as immediates.
if (MI.getOpcode() == TargetOpcode::INLINEASM) {
unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
MRI.removeRegOperandFromUseList(&MO);
MO = MachineOperand::CreateImm(LocalId);
continue;
}
// Insert a get_local.
unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
unsigned NewReg = MRI.createVirtualRegister(RC);
unsigned Opc = getGetLocalOpcode(RC);
InsertPt =
BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
.addImm(LocalId);
MO.setReg(NewReg);
MFI.stackifyVReg(NewReg);
Changed = true;
}
// Coalesce and eliminate COPY instructions.
if (WebAssembly::isCopy(MI)) {
MRI.replaceRegWith(MI.getOperand(1).getReg(),
MI.getOperand(0).getReg());
MI.eraseFromParent();
Changed = true;
}
}
}
// Define the locals.
// TODO: Sort the locals for better compression.
MFI.setNumLocals(CurLocal - MFI.getParams().size());
for (size_t i = 0, e = MRI.getNumVirtRegs(); i < e; ++i) {
unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
auto I = Reg2Local.find(Reg);
if (I == Reg2Local.end() || I->second < MFI.getParams().size())
continue;
MFI.setLocal(I->second - MFI.getParams().size(),
typeForRegClass(MRI.getRegClass(Reg)));
Changed = true;
}
#ifndef NDEBUG
// Assert that all registers have been stackified at this point.
for (const MachineBasicBlock &MBB : MF) {
for (const MachineInstr &MI : MBB) {
if (MI.isDebugInstr() || MI.isLabel())
continue;
for (const MachineOperand &MO : MI.explicit_operands()) {
assert(
(!MO.isReg() || MRI.use_empty(MO.getReg()) ||
MFI.isVRegStackified(MO.getReg())) &&
"WebAssemblyExplicitLocals failed to stackify a register operand");
}
}
}
#endif
return Changed;
}