1 //===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
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 /// This file converts any remaining registers into WebAssembly locals.
12 ///
13 /// After register stackification and register coloring, convert non-stackified
14 /// registers into locals, inserting explicit get_local and set_local
15 /// instructions.
16 ///
17 //===----------------------------------------------------------------------===//
18
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"
30 using namespace llvm;
31
32 #define DEBUG_TYPE "wasm-explicit-locals"
33
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."),
40 cl::init(false));
41
42 namespace {
43 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
getPassName() const44 StringRef getPassName() const override {
45 return "WebAssembly Explicit Locals";
46 }
47
getAnalysisUsage(AnalysisUsage & AU) const48 void getAnalysisUsage(AnalysisUsage &AU) const override {
49 AU.setPreservesCFG();
50 AU.addPreserved<MachineBlockFrequencyInfo>();
51 MachineFunctionPass::getAnalysisUsage(AU);
52 }
53
54 bool runOnMachineFunction(MachineFunction &MF) override;
55
56 public:
57 static char ID; // Pass identification, replacement for typeid
WebAssemblyExplicitLocals()58 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
59 };
60 } // end anonymous namespace
61
62 char WebAssemblyExplicitLocals::ID = 0;
63 INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
64 "Convert registers to WebAssembly locals", false, false)
65
createWebAssemblyExplicitLocals()66 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
67 return new WebAssemblyExplicitLocals();
68 }
69
70 /// Return a local id number for the given register, assigning it a new one
71 /// if it doesn't yet have one.
getLocalId(DenseMap<unsigned,unsigned> & Reg2Local,unsigned & CurLocal,unsigned Reg)72 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
73 unsigned &CurLocal, unsigned Reg) {
74 auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
75 if (P.second)
76 ++CurLocal;
77 return P.first->second;
78 }
79
80 /// Get the appropriate drop opcode for the given register class.
getDropOpcode(const TargetRegisterClass * RC)81 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
82 if (RC == &WebAssembly::I32RegClass)
83 return WebAssembly::DROP_I32;
84 if (RC == &WebAssembly::I64RegClass)
85 return WebAssembly::DROP_I64;
86 if (RC == &WebAssembly::F32RegClass)
87 return WebAssembly::DROP_F32;
88 if (RC == &WebAssembly::F64RegClass)
89 return WebAssembly::DROP_F64;
90 if (RC == &WebAssembly::V128RegClass)
91 return WebAssembly::DROP_V128;
92 if (RC == &WebAssembly::EXCEPT_REFRegClass)
93 return WebAssembly::DROP_EXCEPT_REF;
94 llvm_unreachable("Unexpected register class");
95 }
96
97 /// Get the appropriate get_local opcode for the given register class.
getGetLocalOpcode(const TargetRegisterClass * RC)98 static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
99 if (RC == &WebAssembly::I32RegClass)
100 return WebAssembly::GET_LOCAL_I32;
101 if (RC == &WebAssembly::I64RegClass)
102 return WebAssembly::GET_LOCAL_I64;
103 if (RC == &WebAssembly::F32RegClass)
104 return WebAssembly::GET_LOCAL_F32;
105 if (RC == &WebAssembly::F64RegClass)
106 return WebAssembly::GET_LOCAL_F64;
107 if (RC == &WebAssembly::V128RegClass)
108 return WebAssembly::GET_LOCAL_V128;
109 if (RC == &WebAssembly::EXCEPT_REFRegClass)
110 return WebAssembly::GET_LOCAL_EXCEPT_REF;
111 llvm_unreachable("Unexpected register class");
112 }
113
114 /// Get the appropriate set_local opcode for the given register class.
getSetLocalOpcode(const TargetRegisterClass * RC)115 static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
116 if (RC == &WebAssembly::I32RegClass)
117 return WebAssembly::SET_LOCAL_I32;
118 if (RC == &WebAssembly::I64RegClass)
119 return WebAssembly::SET_LOCAL_I64;
120 if (RC == &WebAssembly::F32RegClass)
121 return WebAssembly::SET_LOCAL_F32;
122 if (RC == &WebAssembly::F64RegClass)
123 return WebAssembly::SET_LOCAL_F64;
124 if (RC == &WebAssembly::V128RegClass)
125 return WebAssembly::SET_LOCAL_V128;
126 if (RC == &WebAssembly::EXCEPT_REFRegClass)
127 return WebAssembly::SET_LOCAL_EXCEPT_REF;
128 llvm_unreachable("Unexpected register class");
129 }
130
131 /// Get the appropriate tee_local opcode for the given register class.
getTeeLocalOpcode(const TargetRegisterClass * RC)132 static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
133 if (RC == &WebAssembly::I32RegClass)
134 return WebAssembly::TEE_LOCAL_I32;
135 if (RC == &WebAssembly::I64RegClass)
136 return WebAssembly::TEE_LOCAL_I64;
137 if (RC == &WebAssembly::F32RegClass)
138 return WebAssembly::TEE_LOCAL_F32;
139 if (RC == &WebAssembly::F64RegClass)
140 return WebAssembly::TEE_LOCAL_F64;
141 if (RC == &WebAssembly::V128RegClass)
142 return WebAssembly::TEE_LOCAL_V128;
143 if (RC == &WebAssembly::EXCEPT_REFRegClass)
144 return WebAssembly::TEE_LOCAL_EXCEPT_REF;
145 llvm_unreachable("Unexpected register class");
146 }
147
148 /// Get the type associated with the given register class.
typeForRegClass(const TargetRegisterClass * RC)149 static MVT typeForRegClass(const TargetRegisterClass *RC) {
150 if (RC == &WebAssembly::I32RegClass)
151 return MVT::i32;
152 if (RC == &WebAssembly::I64RegClass)
153 return MVT::i64;
154 if (RC == &WebAssembly::F32RegClass)
155 return MVT::f32;
156 if (RC == &WebAssembly::F64RegClass)
157 return MVT::f64;
158 if (RC == &WebAssembly::EXCEPT_REFRegClass)
159 return MVT::ExceptRef;
160 llvm_unreachable("unrecognized register class");
161 }
162
163 /// Given a MachineOperand of a stackified vreg, return the instruction at the
164 /// start of the expression tree.
FindStartOfTree(MachineOperand & MO,MachineRegisterInfo & MRI,WebAssemblyFunctionInfo & MFI)165 static MachineInstr *FindStartOfTree(MachineOperand &MO,
166 MachineRegisterInfo &MRI,
167 WebAssemblyFunctionInfo &MFI) {
168 unsigned Reg = MO.getReg();
169 assert(MFI.isVRegStackified(Reg));
170 MachineInstr *Def = MRI.getVRegDef(Reg);
171
172 // Find the first stackified use and proceed from there.
173 for (MachineOperand &DefMO : Def->explicit_uses()) {
174 if (!DefMO.isReg())
175 continue;
176 return FindStartOfTree(DefMO, MRI, MFI);
177 }
178
179 // If there were no stackified uses, we've reached the start.
180 return Def;
181 }
182
runOnMachineFunction(MachineFunction & MF)183 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
184 LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
185 "********** Function: "
186 << MF.getName() << '\n');
187
188 // Disable this pass if directed to do so.
189 if (DisableWebAssemblyExplicitLocals)
190 return false;
191
192 bool Changed = false;
193 MachineRegisterInfo &MRI = MF.getRegInfo();
194 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
195 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
196
197 // Map non-stackified virtual registers to their local ids.
198 DenseMap<unsigned, unsigned> Reg2Local;
199
200 // Handle ARGUMENTS first to ensure that they get the designated numbers.
201 for (MachineBasicBlock::iterator I = MF.begin()->begin(),
202 E = MF.begin()->end();
203 I != E;) {
204 MachineInstr &MI = *I++;
205 if (!WebAssembly::isArgument(MI))
206 break;
207 unsigned Reg = MI.getOperand(0).getReg();
208 assert(!MFI.isVRegStackified(Reg));
209 Reg2Local[Reg] = MI.getOperand(1).getImm();
210 MI.eraseFromParent();
211 Changed = true;
212 }
213
214 // Start assigning local numbers after the last parameter.
215 unsigned CurLocal = MFI.getParams().size();
216
217 // Precompute the set of registers that are unused, so that we can insert
218 // drops to their defs.
219 BitVector UseEmpty(MRI.getNumVirtRegs());
220 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i < e; ++i)
221 UseEmpty[i] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(i));
222
223 // Visit each instruction in the function.
224 for (MachineBasicBlock &MBB : MF) {
225 for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
226 MachineInstr &MI = *I++;
227 assert(!WebAssembly::isArgument(MI));
228
229 if (MI.isDebugInstr() || MI.isLabel())
230 continue;
231
232 // Replace tee instructions with tee_local. The difference is that tee
233 // instructins have two defs, while tee_local instructions have one def
234 // and an index of a local to write to.
235 if (WebAssembly::isTee(MI)) {
236 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
237 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
238 unsigned OldReg = MI.getOperand(2).getReg();
239 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
240
241 // Stackify the input if it isn't stackified yet.
242 if (!MFI.isVRegStackified(OldReg)) {
243 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
244 unsigned NewReg = MRI.createVirtualRegister(RC);
245 unsigned Opc = getGetLocalOpcode(RC);
246 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
247 .addImm(LocalId);
248 MI.getOperand(2).setReg(NewReg);
249 MFI.stackifyVReg(NewReg);
250 }
251
252 // Replace the TEE with a TEE_LOCAL.
253 unsigned LocalId =
254 getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
255 unsigned Opc = getTeeLocalOpcode(RC);
256 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
257 MI.getOperand(0).getReg())
258 .addImm(LocalId)
259 .addReg(MI.getOperand(2).getReg());
260
261 MI.eraseFromParent();
262 Changed = true;
263 continue;
264 }
265
266 // Insert set_locals for any defs that aren't stackified yet. Currently
267 // we handle at most one def.
268 assert(MI.getDesc().getNumDefs() <= 1);
269 if (MI.getDesc().getNumDefs() == 1) {
270 unsigned OldReg = MI.getOperand(0).getReg();
271 if (!MFI.isVRegStackified(OldReg)) {
272 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
273 unsigned NewReg = MRI.createVirtualRegister(RC);
274 auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
275 if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
276 MI.eraseFromParent();
277 Changed = true;
278 continue;
279 }
280 if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
281 unsigned Opc = getDropOpcode(RC);
282 MachineInstr *Drop =
283 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
284 .addReg(NewReg);
285 // After the drop instruction, this reg operand will not be used
286 Drop->getOperand(0).setIsKill();
287 } else {
288 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
289 unsigned Opc = getSetLocalOpcode(RC);
290 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
291 .addImm(LocalId)
292 .addReg(NewReg);
293 }
294 MI.getOperand(0).setReg(NewReg);
295 // This register operand is now being used by the inserted drop
296 // instruction, so make it undead.
297 MI.getOperand(0).setIsDead(false);
298 MFI.stackifyVReg(NewReg);
299 Changed = true;
300 }
301 }
302
303 // Insert get_locals for any uses that aren't stackified yet.
304 MachineInstr *InsertPt = &MI;
305 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
306 if (!MO.isReg())
307 continue;
308
309 unsigned OldReg = MO.getReg();
310
311 // Inline asm may have a def in the middle of the operands. Our contract
312 // with inline asm register operands is to provide local indices as
313 // immediates.
314 if (MO.isDef()) {
315 assert(MI.getOpcode() == TargetOpcode::INLINEASM);
316 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
317 MRI.removeRegOperandFromUseList(&MO);
318 MO = MachineOperand::CreateImm(LocalId);
319 continue;
320 }
321
322 // If we see a stackified register, prepare to insert subsequent
323 // get_locals before the start of its tree.
324 if (MFI.isVRegStackified(OldReg)) {
325 InsertPt = FindStartOfTree(MO, MRI, MFI);
326 continue;
327 }
328
329 // Our contract with inline asm register operands is to provide local
330 // indices as immediates.
331 if (MI.getOpcode() == TargetOpcode::INLINEASM) {
332 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
333 MRI.removeRegOperandFromUseList(&MO);
334 MO = MachineOperand::CreateImm(LocalId);
335 continue;
336 }
337
338 // Insert a get_local.
339 unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
340 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
341 unsigned NewReg = MRI.createVirtualRegister(RC);
342 unsigned Opc = getGetLocalOpcode(RC);
343 InsertPt =
344 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
345 .addImm(LocalId);
346 MO.setReg(NewReg);
347 MFI.stackifyVReg(NewReg);
348 Changed = true;
349 }
350
351 // Coalesce and eliminate COPY instructions.
352 if (WebAssembly::isCopy(MI)) {
353 MRI.replaceRegWith(MI.getOperand(1).getReg(),
354 MI.getOperand(0).getReg());
355 MI.eraseFromParent();
356 Changed = true;
357 }
358 }
359 }
360
361 // Define the locals.
362 // TODO: Sort the locals for better compression.
363 MFI.setNumLocals(CurLocal - MFI.getParams().size());
364 for (size_t i = 0, e = MRI.getNumVirtRegs(); i < e; ++i) {
365 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
366 auto I = Reg2Local.find(Reg);
367 if (I == Reg2Local.end() || I->second < MFI.getParams().size())
368 continue;
369
370 MFI.setLocal(I->second - MFI.getParams().size(),
371 typeForRegClass(MRI.getRegClass(Reg)));
372 Changed = true;
373 }
374
375 #ifndef NDEBUG
376 // Assert that all registers have been stackified at this point.
377 for (const MachineBasicBlock &MBB : MF) {
378 for (const MachineInstr &MI : MBB) {
379 if (MI.isDebugInstr() || MI.isLabel())
380 continue;
381 for (const MachineOperand &MO : MI.explicit_operands()) {
382 assert(
383 (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
384 MFI.isVRegStackified(MO.getReg())) &&
385 "WebAssemblyExplicitLocals failed to stackify a register operand");
386 }
387 }
388 }
389 #endif
390
391 return Changed;
392 }
393