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"
34 // A command-line option to disable this pass. Note that this produces output
35 // which is not valid WebAssembly, though it may be more convenient for writing
36 // LLVM unit tests with.
37 static cl::opt<bool> DisableWebAssemblyExplicitLocals(
38 "disable-wasm-explicit-locals", cl::ReallyHidden,
39 cl::desc("WebAssembly: Disable emission of get_local/set_local."),
43 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
44 StringRef getPassName() const override {
45 return "WebAssembly Explicit Locals";
48 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.addPreserved<MachineBlockFrequencyInfo>();
51 MachineFunctionPass::getAnalysisUsage(AU);
54 bool runOnMachineFunction(MachineFunction &MF) override;
57 static char ID; // Pass identification, replacement for typeid
58 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
60 } // end anonymous namespace
62 char WebAssemblyExplicitLocals::ID = 0;
63 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
64 return new WebAssemblyExplicitLocals();
67 /// Return a local id number for the given register, assigning it a new one
68 /// if it doesn't yet have one.
69 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
70 unsigned &CurLocal, unsigned Reg) {
71 auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
74 return P.first->second;
77 /// Get the appropriate drop opcode for the given register class.
78 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
79 if (RC == &WebAssembly::I32RegClass)
80 return WebAssembly::DROP_I32;
81 if (RC == &WebAssembly::I64RegClass)
82 return WebAssembly::DROP_I64;
83 if (RC == &WebAssembly::F32RegClass)
84 return WebAssembly::DROP_F32;
85 if (RC == &WebAssembly::F64RegClass)
86 return WebAssembly::DROP_F64;
87 if (RC == &WebAssembly::V128RegClass)
88 return WebAssembly::DROP_V128;
89 llvm_unreachable("Unexpected register class");
92 /// Get the appropriate get_local opcode for the given register class.
93 static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
94 if (RC == &WebAssembly::I32RegClass)
95 return WebAssembly::GET_LOCAL_I32;
96 if (RC == &WebAssembly::I64RegClass)
97 return WebAssembly::GET_LOCAL_I64;
98 if (RC == &WebAssembly::F32RegClass)
99 return WebAssembly::GET_LOCAL_F32;
100 if (RC == &WebAssembly::F64RegClass)
101 return WebAssembly::GET_LOCAL_F64;
102 if (RC == &WebAssembly::V128RegClass)
103 return WebAssembly::GET_LOCAL_V128;
104 llvm_unreachable("Unexpected register class");
107 /// Get the appropriate set_local opcode for the given register class.
108 static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
109 if (RC == &WebAssembly::I32RegClass)
110 return WebAssembly::SET_LOCAL_I32;
111 if (RC == &WebAssembly::I64RegClass)
112 return WebAssembly::SET_LOCAL_I64;
113 if (RC == &WebAssembly::F32RegClass)
114 return WebAssembly::SET_LOCAL_F32;
115 if (RC == &WebAssembly::F64RegClass)
116 return WebAssembly::SET_LOCAL_F64;
117 if (RC == &WebAssembly::V128RegClass)
118 return WebAssembly::SET_LOCAL_V128;
119 llvm_unreachable("Unexpected register class");
122 /// Get the appropriate tee_local opcode for the given register class.
123 static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
124 if (RC == &WebAssembly::I32RegClass)
125 return WebAssembly::TEE_LOCAL_I32;
126 if (RC == &WebAssembly::I64RegClass)
127 return WebAssembly::TEE_LOCAL_I64;
128 if (RC == &WebAssembly::F32RegClass)
129 return WebAssembly::TEE_LOCAL_F32;
130 if (RC == &WebAssembly::F64RegClass)
131 return WebAssembly::TEE_LOCAL_F64;
132 if (RC == &WebAssembly::V128RegClass)
133 return WebAssembly::TEE_LOCAL_V128;
134 llvm_unreachable("Unexpected register class");
137 /// Get the type associated with the given register class.
138 static MVT typeForRegClass(const TargetRegisterClass *RC) {
139 if (RC == &WebAssembly::I32RegClass)
141 if (RC == &WebAssembly::I64RegClass)
143 if (RC == &WebAssembly::F32RegClass)
145 if (RC == &WebAssembly::F64RegClass)
147 llvm_unreachable("unrecognized register class");
150 /// Given a MachineOperand of a stackified vreg, return the instruction at the
151 /// start of the expression tree.
152 static MachineInstr *FindStartOfTree(MachineOperand &MO,
153 MachineRegisterInfo &MRI,
154 WebAssemblyFunctionInfo &MFI) {
155 unsigned Reg = MO.getReg();
156 assert(MFI.isVRegStackified(Reg));
157 MachineInstr *Def = MRI.getVRegDef(Reg);
159 // Find the first stackified use and proceed from there.
160 for (MachineOperand &DefMO : Def->explicit_uses()) {
163 return FindStartOfTree(DefMO, MRI, MFI);
166 // If there were no stackified uses, we've reached the start.
170 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
171 DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
172 "********** Function: "
173 << MF.getName() << '\n');
175 // Disable this pass if directed to do so.
176 if (DisableWebAssemblyExplicitLocals)
179 // Disable this pass if we aren't doing direct wasm object emission.
180 if (MF.getSubtarget<WebAssemblySubtarget>()
181 .getTargetTriple().isOSBinFormatELF())
184 bool Changed = false;
185 MachineRegisterInfo &MRI = MF.getRegInfo();
186 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
187 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
189 // Map non-stackified virtual registers to their local ids.
190 DenseMap<unsigned, unsigned> Reg2Local;
192 // Handle ARGUMENTS first to ensure that they get the designated numbers.
193 for (MachineBasicBlock::iterator I = MF.begin()->begin(),
194 E = MF.begin()->end();
196 MachineInstr &MI = *I++;
197 if (!WebAssembly::isArgument(MI))
199 unsigned Reg = MI.getOperand(0).getReg();
200 assert(!MFI.isVRegStackified(Reg));
201 Reg2Local[Reg] = MI.getOperand(1).getImm();
202 MI.eraseFromParent();
206 // Start assigning local numbers after the last parameter.
207 unsigned CurLocal = MFI.getParams().size();
209 // Precompute the set of registers that are unused, so that we can insert
210 // drops to their defs.
211 BitVector UseEmpty(MRI.getNumVirtRegs());
212 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i < e; ++i)
213 UseEmpty[i] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(i));
215 // Visit each instruction in the function.
216 for (MachineBasicBlock &MBB : MF) {
217 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
218 MachineInstr &MI = *I++;
219 assert(!WebAssembly::isArgument(MI));
221 if (MI.isDebugValue() || MI.isLabel())
224 // Replace tee instructions with tee_local. The difference is that tee
225 // instructins have two defs, while tee_local instructions have one def
226 // and an index of a local to write to.
227 if (WebAssembly::isTee(MI)) {
228 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
229 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
230 unsigned OldReg = MI.getOperand(2).getReg();
231 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
233 // Stackify the input if it isn't stackified yet.
234 if (!MFI.isVRegStackified(OldReg)) {
235 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
236 unsigned NewReg = MRI.createVirtualRegister(RC);
237 unsigned Opc = getGetLocalOpcode(RC);
238 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
240 MI.getOperand(2).setReg(NewReg);
241 MFI.stackifyVReg(NewReg);
244 // Replace the TEE with a TEE_LOCAL.
246 getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
247 unsigned Opc = getTeeLocalOpcode(RC);
248 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
249 MI.getOperand(0).getReg())
251 .addReg(MI.getOperand(2).getReg());
253 MI.eraseFromParent();
258 // Insert set_locals for any defs that aren't stackified yet. Currently
259 // we handle at most one def.
260 assert(MI.getDesc().getNumDefs() <= 1);
261 if (MI.getDesc().getNumDefs() == 1) {
262 unsigned OldReg = MI.getOperand(0).getReg();
263 if (!MFI.isVRegStackified(OldReg)) {
264 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
265 unsigned NewReg = MRI.createVirtualRegister(RC);
266 auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
267 if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
268 MI.eraseFromParent();
272 if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
273 unsigned Opc = getDropOpcode(RC);
274 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
277 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
278 unsigned Opc = getSetLocalOpcode(RC);
279 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
283 MI.getOperand(0).setReg(NewReg);
284 MFI.stackifyVReg(NewReg);
289 // Insert get_locals for any uses that aren't stackified yet.
290 MachineInstr *InsertPt = &MI;
291 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
295 unsigned OldReg = MO.getReg();
297 // Inline asm may have a def in the middle of the operands. Our contract
298 // with inline asm register operands is to provide local indices as
301 assert(MI.getOpcode() == TargetOpcode::INLINEASM);
302 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
303 MRI.removeRegOperandFromUseList(&MO);
304 MO = MachineOperand::CreateImm(LocalId);
308 // If we see a stackified register, prepare to insert subsequent
309 // get_locals before the start of its tree.
310 if (MFI.isVRegStackified(OldReg)) {
311 InsertPt = FindStartOfTree(MO, MRI, MFI);
315 // Our contract with inline asm register operands is to provide local
316 // indices as immediates.
317 if (MI.getOpcode() == TargetOpcode::INLINEASM) {
318 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
319 MRI.removeRegOperandFromUseList(&MO);
320 MO = MachineOperand::CreateImm(LocalId);
324 // Insert a get_local.
325 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
326 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
327 unsigned NewReg = MRI.createVirtualRegister(RC);
328 unsigned Opc = getGetLocalOpcode(RC);
330 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
333 MFI.stackifyVReg(NewReg);
337 // Coalesce and eliminate COPY instructions.
338 if (WebAssembly::isCopy(MI)) {
339 MRI.replaceRegWith(MI.getOperand(1).getReg(),
340 MI.getOperand(0).getReg());
341 MI.eraseFromParent();
347 // Define the locals.
348 // TODO: Sort the locals for better compression.
349 MFI.setNumLocals(CurLocal - MFI.getParams().size());
350 for (size_t i = 0, e = MRI.getNumVirtRegs(); i < e; ++i) {
351 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
352 auto I = Reg2Local.find(Reg);
353 if (I == Reg2Local.end() || I->second < MFI.getParams().size())
356 MFI.setLocal(I->second - MFI.getParams().size(),
357 typeForRegClass(MRI.getRegClass(Reg)));
362 // Assert that all registers have been stackified at this point.
363 for (const MachineBasicBlock &MBB : MF) {
364 for (const MachineInstr &MI : MBB) {
365 if (MI.isDebugValue() || MI.isLabel())
367 for (const MachineOperand &MO : MI.explicit_operands()) {
369 (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
370 MFI.isVRegStackified(MO.getReg())) &&
371 "WebAssemblyExplicitLocals failed to stackify a register operand");