1 //===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file converts any remaining registers into WebAssembly locals.
11 ///
12 /// After register stackification and register coloring, convert non-stackified
13 /// registers into locals, inserting explicit local.get and local.set
14 /// instructions.
15 ///
16 //===----------------------------------------------------------------------===//
17
18 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
19 #include "WebAssembly.h"
20 #include "WebAssemblyDebugValueManager.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 namespace {
35 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
getPassName() const36 StringRef getPassName() const override {
37 return "WebAssembly Explicit Locals";
38 }
39
getAnalysisUsage(AnalysisUsage & AU) const40 void getAnalysisUsage(AnalysisUsage &AU) const override {
41 AU.setPreservesCFG();
42 AU.addPreserved<MachineBlockFrequencyInfoWrapperPass>();
43 MachineFunctionPass::getAnalysisUsage(AU);
44 }
45
46 bool runOnMachineFunction(MachineFunction &MF) override;
47
48 public:
49 static char ID; // Pass identification, replacement for typeid
WebAssemblyExplicitLocals()50 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
51 };
52 } // end anonymous namespace
53
54 char WebAssemblyExplicitLocals::ID = 0;
55 INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
56 "Convert registers to WebAssembly locals", false, false)
57
createWebAssemblyExplicitLocals()58 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
59 return new WebAssemblyExplicitLocals();
60 }
61
checkFrameBase(WebAssemblyFunctionInfo & MFI,unsigned Local,unsigned Reg)62 static void checkFrameBase(WebAssemblyFunctionInfo &MFI, unsigned Local,
63 unsigned Reg) {
64 // Mark a local for the frame base vreg.
65 if (MFI.isFrameBaseVirtual() && Reg == MFI.getFrameBaseVreg()) {
66 LLVM_DEBUG({
67 dbgs() << "Allocating local " << Local << "for VReg "
68 << Register::virtReg2Index(Reg) << '\n';
69 });
70 MFI.setFrameBaseLocal(Local);
71 }
72 }
73
74 /// Return a local id number for the given register, assigning it a new one
75 /// if it doesn't yet have one.
getLocalId(DenseMap<unsigned,unsigned> & Reg2Local,WebAssemblyFunctionInfo & MFI,unsigned & CurLocal,unsigned Reg)76 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
77 WebAssemblyFunctionInfo &MFI, unsigned &CurLocal,
78 unsigned Reg) {
79 auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
80 if (P.second) {
81 checkFrameBase(MFI, CurLocal, Reg);
82 ++CurLocal;
83 }
84 return P.first->second;
85 }
86
87 /// Get the appropriate drop opcode for the given register class.
getDropOpcode(const TargetRegisterClass * RC)88 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
89 if (RC == &WebAssembly::I32RegClass)
90 return WebAssembly::DROP_I32;
91 if (RC == &WebAssembly::I64RegClass)
92 return WebAssembly::DROP_I64;
93 if (RC == &WebAssembly::F32RegClass)
94 return WebAssembly::DROP_F32;
95 if (RC == &WebAssembly::F64RegClass)
96 return WebAssembly::DROP_F64;
97 if (RC == &WebAssembly::V128RegClass)
98 return WebAssembly::DROP_V128;
99 if (RC == &WebAssembly::FUNCREFRegClass)
100 return WebAssembly::DROP_FUNCREF;
101 if (RC == &WebAssembly::EXTERNREFRegClass)
102 return WebAssembly::DROP_EXTERNREF;
103 if (RC == &WebAssembly::EXNREFRegClass)
104 return WebAssembly::DROP_EXNREF;
105 llvm_unreachable("Unexpected register class");
106 }
107
108 /// Get the appropriate local.get opcode for the given register class.
getLocalGetOpcode(const TargetRegisterClass * RC)109 static unsigned getLocalGetOpcode(const TargetRegisterClass *RC) {
110 if (RC == &WebAssembly::I32RegClass)
111 return WebAssembly::LOCAL_GET_I32;
112 if (RC == &WebAssembly::I64RegClass)
113 return WebAssembly::LOCAL_GET_I64;
114 if (RC == &WebAssembly::F32RegClass)
115 return WebAssembly::LOCAL_GET_F32;
116 if (RC == &WebAssembly::F64RegClass)
117 return WebAssembly::LOCAL_GET_F64;
118 if (RC == &WebAssembly::V128RegClass)
119 return WebAssembly::LOCAL_GET_V128;
120 if (RC == &WebAssembly::FUNCREFRegClass)
121 return WebAssembly::LOCAL_GET_FUNCREF;
122 if (RC == &WebAssembly::EXTERNREFRegClass)
123 return WebAssembly::LOCAL_GET_EXTERNREF;
124 if (RC == &WebAssembly::EXNREFRegClass)
125 return WebAssembly::LOCAL_GET_EXNREF;
126 llvm_unreachable("Unexpected register class");
127 }
128
129 /// Get the appropriate local.set opcode for the given register class.
getLocalSetOpcode(const TargetRegisterClass * RC)130 static unsigned getLocalSetOpcode(const TargetRegisterClass *RC) {
131 if (RC == &WebAssembly::I32RegClass)
132 return WebAssembly::LOCAL_SET_I32;
133 if (RC == &WebAssembly::I64RegClass)
134 return WebAssembly::LOCAL_SET_I64;
135 if (RC == &WebAssembly::F32RegClass)
136 return WebAssembly::LOCAL_SET_F32;
137 if (RC == &WebAssembly::F64RegClass)
138 return WebAssembly::LOCAL_SET_F64;
139 if (RC == &WebAssembly::V128RegClass)
140 return WebAssembly::LOCAL_SET_V128;
141 if (RC == &WebAssembly::FUNCREFRegClass)
142 return WebAssembly::LOCAL_SET_FUNCREF;
143 if (RC == &WebAssembly::EXTERNREFRegClass)
144 return WebAssembly::LOCAL_SET_EXTERNREF;
145 if (RC == &WebAssembly::EXNREFRegClass)
146 return WebAssembly::LOCAL_SET_EXNREF;
147 llvm_unreachable("Unexpected register class");
148 }
149
150 /// Get the appropriate local.tee opcode for the given register class.
getLocalTeeOpcode(const TargetRegisterClass * RC)151 static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC) {
152 if (RC == &WebAssembly::I32RegClass)
153 return WebAssembly::LOCAL_TEE_I32;
154 if (RC == &WebAssembly::I64RegClass)
155 return WebAssembly::LOCAL_TEE_I64;
156 if (RC == &WebAssembly::F32RegClass)
157 return WebAssembly::LOCAL_TEE_F32;
158 if (RC == &WebAssembly::F64RegClass)
159 return WebAssembly::LOCAL_TEE_F64;
160 if (RC == &WebAssembly::V128RegClass)
161 return WebAssembly::LOCAL_TEE_V128;
162 if (RC == &WebAssembly::FUNCREFRegClass)
163 return WebAssembly::LOCAL_TEE_FUNCREF;
164 if (RC == &WebAssembly::EXTERNREFRegClass)
165 return WebAssembly::LOCAL_TEE_EXTERNREF;
166 if (RC == &WebAssembly::EXNREFRegClass)
167 return WebAssembly::LOCAL_TEE_EXNREF;
168 llvm_unreachable("Unexpected register class");
169 }
170
171 /// Get the type associated with the given register class.
typeForRegClass(const TargetRegisterClass * RC)172 static MVT typeForRegClass(const TargetRegisterClass *RC) {
173 if (RC == &WebAssembly::I32RegClass)
174 return MVT::i32;
175 if (RC == &WebAssembly::I64RegClass)
176 return MVT::i64;
177 if (RC == &WebAssembly::F32RegClass)
178 return MVT::f32;
179 if (RC == &WebAssembly::F64RegClass)
180 return MVT::f64;
181 if (RC == &WebAssembly::V128RegClass)
182 return MVT::v16i8;
183 if (RC == &WebAssembly::FUNCREFRegClass)
184 return MVT::funcref;
185 if (RC == &WebAssembly::EXTERNREFRegClass)
186 return MVT::externref;
187 if (RC == &WebAssembly::EXNREFRegClass)
188 return MVT::exnref;
189 llvm_unreachable("unrecognized register class");
190 }
191
192 /// Given a MachineOperand of a stackified vreg, return the instruction at the
193 /// start of the expression tree.
findStartOfTree(MachineOperand & MO,MachineRegisterInfo & MRI,const WebAssemblyFunctionInfo & MFI)194 static MachineInstr *findStartOfTree(MachineOperand &MO,
195 MachineRegisterInfo &MRI,
196 const WebAssemblyFunctionInfo &MFI) {
197 Register Reg = MO.getReg();
198 assert(MFI.isVRegStackified(Reg));
199 MachineInstr *Def = MRI.getVRegDef(Reg);
200
201 // If this instruction has any non-stackified defs, it is the start
202 for (auto DefReg : Def->defs()) {
203 if (!MFI.isVRegStackified(DefReg.getReg())) {
204 return Def;
205 }
206 }
207
208 // Find the first stackified use and proceed from there.
209 for (MachineOperand &DefMO : Def->explicit_uses()) {
210 if (!DefMO.isReg())
211 continue;
212 return findStartOfTree(DefMO, MRI, MFI);
213 }
214
215 // If there were no stackified uses, we've reached the start.
216 return Def;
217 }
218
runOnMachineFunction(MachineFunction & MF)219 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
220 LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
221 "********** Function: "
222 << MF.getName() << '\n');
223
224 bool Changed = false;
225 MachineRegisterInfo &MRI = MF.getRegInfo();
226 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
227 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
228
229 // Map non-stackified virtual registers to their local ids.
230 DenseMap<unsigned, unsigned> Reg2Local;
231
232 // Handle ARGUMENTS first to ensure that they get the designated numbers.
233 for (MachineBasicBlock::iterator I = MF.begin()->begin(),
234 E = MF.begin()->end();
235 I != E;) {
236 MachineInstr &MI = *I++;
237 if (!WebAssembly::isArgument(MI.getOpcode()))
238 break;
239 Register Reg = MI.getOperand(0).getReg();
240 assert(!MFI.isVRegStackified(Reg));
241 auto Local = static_cast<unsigned>(MI.getOperand(1).getImm());
242 Reg2Local[Reg] = Local;
243 checkFrameBase(MFI, Local, Reg);
244
245 // Update debug value to point to the local before removing.
246 WebAssemblyDebugValueManager(&MI).replaceWithLocal(Local);
247
248 MI.eraseFromParent();
249 Changed = true;
250 }
251
252 // Start assigning local numbers after the last parameter and after any
253 // already-assigned locals.
254 unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
255 CurLocal += static_cast<unsigned>(MFI.getLocals().size());
256
257 // Precompute the set of registers that are unused, so that we can insert
258 // drops to their defs.
259 BitVector UseEmpty(MRI.getNumVirtRegs());
260 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
261 UseEmpty[I] = MRI.use_empty(Register::index2VirtReg(I));
262
263 // Visit each instruction in the function.
264 for (MachineBasicBlock &MBB : MF) {
265 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) {
266 assert(!WebAssembly::isArgument(MI.getOpcode()));
267
268 if (MI.isDebugInstr() || MI.isLabel())
269 continue;
270
271 if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
272 MI.eraseFromParent();
273 Changed = true;
274 continue;
275 }
276
277 // Replace tee instructions with local.tee. The difference is that tee
278 // instructions have two defs, while local.tee instructions have one def
279 // and an index of a local to write to.
280 //
281 // - Before:
282 // TeeReg, Reg = TEE DefReg
283 // INST ..., TeeReg, ...
284 // INST ..., Reg, ...
285 // INST ..., Reg, ...
286 // * DefReg: may or may not be stackified
287 // * Reg: not stackified
288 // * TeeReg: stackified
289 //
290 // - After (when DefReg was already stackified):
291 // TeeReg = LOCAL_TEE LocalId1, DefReg
292 // INST ..., TeeReg, ...
293 // INST ..., Reg, ...
294 // INST ..., Reg, ...
295 // * Reg: mapped to LocalId1
296 // * TeeReg: stackified
297 //
298 // - After (when DefReg was not already stackified):
299 // NewReg = LOCAL_GET LocalId1
300 // TeeReg = LOCAL_TEE LocalId2, NewReg
301 // INST ..., TeeReg, ...
302 // INST ..., Reg, ...
303 // INST ..., Reg, ...
304 // * DefReg: mapped to LocalId1
305 // * Reg: mapped to LocalId2
306 // * TeeReg: stackified
307 if (WebAssembly::isTee(MI.getOpcode())) {
308 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
309 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
310 Register DefReg = MI.getOperand(2).getReg();
311 const TargetRegisterClass *RC = MRI.getRegClass(DefReg);
312
313 // Stackify the input if it isn't stackified yet.
314 if (!MFI.isVRegStackified(DefReg)) {
315 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, DefReg);
316 Register NewReg = MRI.createVirtualRegister(RC);
317 unsigned Opc = getLocalGetOpcode(RC);
318 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
319 .addImm(LocalId);
320 MI.getOperand(2).setReg(NewReg);
321 MFI.stackifyVReg(MRI, NewReg);
322 }
323
324 // Replace the TEE with a LOCAL_TEE.
325 unsigned LocalId =
326 getLocalId(Reg2Local, MFI, CurLocal, MI.getOperand(1).getReg());
327 unsigned Opc = getLocalTeeOpcode(RC);
328 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
329 MI.getOperand(0).getReg())
330 .addImm(LocalId)
331 .addReg(MI.getOperand(2).getReg());
332
333 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
334
335 MI.eraseFromParent();
336 Changed = true;
337 continue;
338 }
339
340 // Insert local.sets for any defs that aren't stackified yet.
341 for (auto &Def : MI.defs()) {
342 Register OldReg = Def.getReg();
343 if (!MFI.isVRegStackified(OldReg)) {
344 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
345 Register NewReg = MRI.createVirtualRegister(RC);
346 auto InsertPt = std::next(MI.getIterator());
347 if (UseEmpty[Register::virtReg2Index(OldReg)]) {
348 unsigned Opc = getDropOpcode(RC);
349 MachineInstr *Drop =
350 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
351 .addReg(NewReg);
352 // After the drop instruction, this reg operand will not be used
353 Drop->getOperand(0).setIsKill();
354 if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg())
355 MFI.clearFrameBaseVreg();
356 } else {
357 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
358 unsigned Opc = getLocalSetOpcode(RC);
359
360 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
361
362 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
363 .addImm(LocalId)
364 .addReg(NewReg);
365 }
366 // This register operand of the original instruction is now being used
367 // by the inserted drop or local.set instruction, so make it not dead
368 // yet.
369 Def.setReg(NewReg);
370 Def.setIsDead(false);
371 MFI.stackifyVReg(MRI, NewReg);
372 Changed = true;
373 }
374 }
375
376 // Insert local.gets for any uses that aren't stackified yet.
377 MachineInstr *InsertPt = &MI;
378 for (MachineOperand &MO : reverse(MI.explicit_uses())) {
379 if (!MO.isReg())
380 continue;
381
382 Register OldReg = MO.getReg();
383
384 // Inline asm may have a def in the middle of the operands. Our contract
385 // with inline asm register operands is to provide local indices as
386 // immediates.
387 if (MO.isDef()) {
388 assert(MI.isInlineAsm());
389 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
390 // If this register operand is tied to another operand, we can't
391 // change it to an immediate. Untie it first.
392 MI.untieRegOperand(MO.getOperandNo());
393 MO.ChangeToImmediate(LocalId);
394 continue;
395 }
396
397 // If we see a stackified register, prepare to insert subsequent
398 // local.gets before the start of its tree.
399 if (MFI.isVRegStackified(OldReg)) {
400 InsertPt = findStartOfTree(MO, MRI, MFI);
401 continue;
402 }
403
404 // Our contract with inline asm register operands is to provide local
405 // indices as immediates.
406 if (MI.isInlineAsm()) {
407 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
408 // Untie it first if this reg operand is tied to another operand.
409 MI.untieRegOperand(MO.getOperandNo());
410 MO.ChangeToImmediate(LocalId);
411 continue;
412 }
413
414 // Insert a local.get.
415 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
416 const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
417 Register NewReg = MRI.createVirtualRegister(RC);
418 unsigned Opc = getLocalGetOpcode(RC);
419 // Use a InsertPt as our DebugLoc, since MI may be discontinuous from
420 // the where this local is being inserted, causing non-linear stepping
421 // in the debugger or function entry points where variables aren't live
422 // yet. Alternative is previous instruction, but that is strictly worse
423 // since it can point at the previous statement.
424 // See crbug.com/1251909, crbug.com/1249745
425 InsertPt = BuildMI(MBB, InsertPt, InsertPt->getDebugLoc(),
426 TII->get(Opc), NewReg).addImm(LocalId);
427 MO.setReg(NewReg);
428 MFI.stackifyVReg(MRI, NewReg);
429 Changed = true;
430 }
431
432 // Coalesce and eliminate COPY instructions.
433 if (WebAssembly::isCopy(MI.getOpcode())) {
434 MRI.replaceRegWith(MI.getOperand(1).getReg(),
435 MI.getOperand(0).getReg());
436 MI.eraseFromParent();
437 Changed = true;
438 }
439 }
440 }
441
442 // Define the locals.
443 // TODO: Sort the locals for better compression.
444 MFI.setNumLocals(CurLocal - MFI.getParams().size());
445 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
446 Register Reg = Register::index2VirtReg(I);
447 auto RL = Reg2Local.find(Reg);
448 if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
449 continue;
450
451 MFI.setLocal(RL->second - MFI.getParams().size(),
452 typeForRegClass(MRI.getRegClass(Reg)));
453 Changed = true;
454 }
455
456 #ifndef NDEBUG
457 // Assert that all registers have been stackified at this point.
458 for (const MachineBasicBlock &MBB : MF) {
459 for (const MachineInstr &MI : MBB) {
460 if (MI.isDebugInstr() || MI.isLabel())
461 continue;
462 for (const MachineOperand &MO : MI.explicit_operands()) {
463 assert(
464 (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
465 MFI.isVRegStackified(MO.getReg())) &&
466 "WebAssemblyExplicitLocals failed to stackify a register operand");
467 }
468 }
469 }
470 #endif
471
472 return Changed;
473 }
474