1 //===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file converts any remaining registers into WebAssembly locals.
13 /// After register stackification and register coloring, convert non-stackified
14 /// registers into locals, inserting explicit get_local and set_local
17 //===----------------------------------------------------------------------===//
19 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
20 #include "WebAssembly.h"
21 #include "WebAssemblyMachineFunctionInfo.h"
22 #include "WebAssemblySubtarget.h"
23 #include "WebAssemblyUtilities.h"
24 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
25 #include "llvm/CodeGen/MachineInstrBuilder.h"
26 #include "llvm/CodeGen/MachineRegisterInfo.h"
27 #include "llvm/CodeGen/Passes.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
32 #define DEBUG_TYPE "wasm-explicit-locals"
35 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
36 StringRef getPassName() const override {
37 return "WebAssembly Explicit Locals";
40 void getAnalysisUsage(AnalysisUsage &AU) const override {
42 AU.addPreserved<MachineBlockFrequencyInfo>();
43 MachineFunctionPass::getAnalysisUsage(AU);
46 bool runOnMachineFunction(MachineFunction &MF) override;
49 static char ID; // Pass identification, replacement for typeid
50 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
52 } // end anonymous namespace
54 char WebAssemblyExplicitLocals::ID = 0;
55 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
56 return new WebAssemblyExplicitLocals();
59 /// Return a local id number for the given register, assigning it a new one
60 /// if it doesn't yet have one.
61 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
62 unsigned &CurLocal, unsigned Reg) {
63 return Reg2Local.insert(std::make_pair(Reg, CurLocal++)).first->second;
66 /// Get the appropriate get_local opcode for the given register class.
67 static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
68 if (RC == &WebAssembly::I32RegClass)
69 return WebAssembly::GET_LOCAL_I32;
70 if (RC == &WebAssembly::I64RegClass)
71 return WebAssembly::GET_LOCAL_I64;
72 if (RC == &WebAssembly::F32RegClass)
73 return WebAssembly::GET_LOCAL_F32;
74 if (RC == &WebAssembly::F64RegClass)
75 return WebAssembly::GET_LOCAL_F64;
76 if (RC == &WebAssembly::V128RegClass)
77 return WebAssembly::GET_LOCAL_V128;
78 llvm_unreachable("Unexpected register class");
81 /// Get the appropriate set_local opcode for the given register class.
82 static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
83 if (RC == &WebAssembly::I32RegClass)
84 return WebAssembly::SET_LOCAL_I32;
85 if (RC == &WebAssembly::I64RegClass)
86 return WebAssembly::SET_LOCAL_I64;
87 if (RC == &WebAssembly::F32RegClass)
88 return WebAssembly::SET_LOCAL_F32;
89 if (RC == &WebAssembly::F64RegClass)
90 return WebAssembly::SET_LOCAL_F64;
91 if (RC == &WebAssembly::V128RegClass)
92 return WebAssembly::SET_LOCAL_V128;
93 llvm_unreachable("Unexpected register class");
96 /// Get the appropriate tee_local opcode for the given register class.
97 static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
98 if (RC == &WebAssembly::I32RegClass)
99 return WebAssembly::TEE_LOCAL_I32;
100 if (RC == &WebAssembly::I64RegClass)
101 return WebAssembly::TEE_LOCAL_I64;
102 if (RC == &WebAssembly::F32RegClass)
103 return WebAssembly::TEE_LOCAL_F32;
104 if (RC == &WebAssembly::F64RegClass)
105 return WebAssembly::TEE_LOCAL_F64;
106 if (RC == &WebAssembly::V128RegClass)
107 return WebAssembly::TEE_LOCAL_V128;
108 llvm_unreachable("Unexpected register class");
111 /// Get the type associated with the given register class.
112 static MVT typeForRegClass(const TargetRegisterClass *RC) {
113 if (RC == &WebAssembly::I32RegClass)
115 if (RC == &WebAssembly::I64RegClass)
117 if (RC == &WebAssembly::F32RegClass)
119 if (RC == &WebAssembly::F64RegClass)
121 llvm_unreachable("unrecognized register class");
124 /// Given a MachineOperand of a stackified vreg, return the instruction at the
125 /// start of the expression tree.
126 static MachineInstr *FindStartOfTree(MachineOperand &MO,
127 MachineRegisterInfo &MRI,
128 WebAssemblyFunctionInfo &MFI) {
129 unsigned Reg = MO.getReg();
130 assert(MFI.isVRegStackified(Reg));
131 MachineInstr *Def = MRI.getVRegDef(Reg);
133 // Find the first stackified use and proceed from there.
134 for (MachineOperand &DefMO : Def->explicit_uses()) {
137 return FindStartOfTree(DefMO, MRI, MFI);
140 // If there were no stackified uses, we've reached the start.
144 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
145 DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
146 "********** Function: "
147 << MF.getName() << '\n');
149 // Disable this pass if we aren't doing direct wasm object emission.
150 if (MF.getSubtarget<WebAssemblySubtarget>()
151 .getTargetTriple().isOSBinFormatELF())
154 bool Changed = false;
155 MachineRegisterInfo &MRI = MF.getRegInfo();
156 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
157 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
159 // Map non-stackified virtual registers to their local ids.
160 DenseMap<unsigned, unsigned> Reg2Local;
162 // Handle ARGUMENTS first to ensure that they get the designated numbers.
163 for (MachineBasicBlock::iterator I = MF.begin()->begin(),
164 E = MF.begin()->end();
166 MachineInstr &MI = *I++;
167 if (!WebAssembly::isArgument(MI))
169 unsigned Reg = MI.getOperand(0).getReg();
170 assert(!MFI.isVRegStackified(Reg));
171 Reg2Local[Reg] = MI.getOperand(1).getImm();
172 MI.eraseFromParent();
176 // Start assigning local numbers after the last parameter.
177 unsigned CurLocal = MFI.getParams().size();
179 // Visit each instruction in the function.
180 for (MachineBasicBlock &MBB : MF) {
181 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
182 MachineInstr &MI = *I++;
183 assert(!WebAssembly::isArgument(MI));
185 if (MI.isDebugValue() || MI.isLabel())
188 // Replace tee instructions with tee_local. The difference is that tee
189 // instructins have two defs, while tee_local instructions have one def
190 // and an index of a local to write to.
191 if (WebAssembly::isTee(MI)) {
192 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
193 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
194 unsigned OldReg = MI.getOperand(2).getReg();
195 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
197 // Stackify the input if it isn't stackified yet.
198 if (!MFI.isVRegStackified(OldReg)) {
199 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
200 unsigned NewReg = MRI.createVirtualRegister(RC);
201 unsigned Opc = getGetLocalOpcode(RC);
202 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
204 MI.getOperand(2).setReg(NewReg);
205 MFI.stackifyVReg(NewReg);
208 // Replace the TEE with a TEE_LOCAL.
210 getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
211 unsigned Opc = getTeeLocalOpcode(RC);
212 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
213 MI.getOperand(0).getReg())
215 .addReg(MI.getOperand(2).getReg());
217 MI.eraseFromParent();
222 // Insert set_locals for any defs that aren't stackified yet. Currently
223 // we handle at most one def.
224 assert(MI.getDesc().getNumDefs() <= 1);
225 if (MI.getDesc().getNumDefs() == 1) {
226 unsigned OldReg = MI.getOperand(0).getReg();
227 if (!MFI.isVRegStackified(OldReg) && !MRI.use_empty(OldReg)) {
228 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
229 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
230 unsigned NewReg = MRI.createVirtualRegister(RC);
231 auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
232 unsigned Opc = getSetLocalOpcode(RC);
233 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
236 MI.getOperand(0).setReg(NewReg);
237 MFI.stackifyVReg(NewReg);
242 // Insert get_locals for any uses that aren't stackified yet.
243 MachineInstr *InsertPt = &MI;
244 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
248 unsigned OldReg = MO.getReg();
250 // If we see a stackified register, prepare to insert subsequent
251 // get_locals before the start of its tree.
252 if (MFI.isVRegStackified(OldReg)) {
253 InsertPt = FindStartOfTree(MO, MRI, MFI);
257 // Insert a get_local.
258 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
259 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
260 unsigned NewReg = MRI.createVirtualRegister(RC);
261 unsigned Opc = getGetLocalOpcode(RC);
263 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
266 MFI.stackifyVReg(NewReg);
270 // Coalesce and eliminate COPY instructions.
271 if (WebAssembly::isCopy(MI)) {
272 MRI.replaceRegWith(MI.getOperand(1).getReg(),
273 MI.getOperand(0).getReg());
274 MI.eraseFromParent();
280 // Define the locals.
281 for (size_t i = 0, e = MRI.getNumVirtRegs(); i < e; ++i) {
282 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
283 auto I = Reg2Local.find(Reg);
284 if (I == Reg2Local.end() || I->second < MFI.getParams().size())
287 MFI.addLocal(typeForRegClass(MRI.getRegClass(Reg)));
292 // Assert that all registers have been stackified at this point.
293 for (const MachineBasicBlock &MBB : MF) {
294 for (const MachineInstr &MI : MBB) {
295 if (MI.isDebugValue() || MI.isLabel())
297 for (const MachineOperand &MO : MI.explicit_operands()) {
299 (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
300 MFI.isVRegStackified(MO.getReg())) &&
301 "WebAssemblyExplicitLocals failed to stackify a register operand");