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