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 // Start assigning local numbers after the last parameter and after any
249 // already-assigned locals.
250 unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
251 CurLocal += static_cast<unsigned>(MFI.getLocals().size());
252
253 // ABI contract: the async context must always be available in local 0. If
254 // something else defines the register of the swiftasync argument too, for
255 // example a value that register coalescing merged with it, that register
256 // gets its own local.
257 Register SwiftAsyncReg = WebAssembly::getSwiftAsyncArgReg(MF);
258 bool CopySwiftAsyncArg = SwiftAsyncReg && !MRI.hasOneDef(RegNo: SwiftAsyncReg);
259
260 // Handle ARGUMENTS first to ensure that they get the designated numbers.
261 for (MachineBasicBlock::iterator I = MF.begin()->begin(),
262 E = MF.begin()->end();
263 I != E;) {
264 MachineInstr &MI = *I++;
265 if (!WebAssembly::isArgument(Opc: MI.getOpcode()))
266 break;
267 Register Reg = MI.getOperand(i: 0).getReg();
268 assert(!MFI.isVRegStackified(Reg));
269 auto Local = static_cast<unsigned>(MI.getOperand(i: 1).getImm());
270 if (Reg == SwiftAsyncReg && CopySwiftAsyncArg) {
271 const TargetRegisterClass *RC = MRI.getRegClass(Reg);
272 Register Tmp = MRI.createVirtualRegister(RegClass: RC);
273 BuildMI(BB&: *MI.getParent(), I&: MI, MIMD: DebugLoc(), MCID: TII->get(Opcode: getLocalGetOpcode(RC)),
274 DestReg: Tmp)
275 .addImm(Val: Local);
276 MFI.stackifyVReg(MRI, VReg: Tmp);
277 Local = CurLocal++;
278 BuildMI(BB&: *MI.getParent(), I&: MI, MIMD: DebugLoc(), MCID: TII->get(Opcode: getLocalSetOpcode(RC)))
279 .addImm(Val: Local)
280 .addReg(RegNo: Tmp);
281 }
282 Reg2Local[Reg] = Local;
283 checkFrameBase(MFI, Local, Reg);
284
285 // Update debug value to point to the local before removing.
286 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId: Local);
287
288 MI.eraseFromParent();
289 Changed = true;
290 }
291
292 // Precompute the set of registers that are unused, so that we can insert
293 // drops to their defs.
294 // And unstackify any stackified registers that don't have any uses, so that
295 // they can be dropped later. This can happen when transformations after
296 // RegStackify remove instructions using stackified registers.
297 BitVector UseEmpty(MRI.getNumVirtRegs());
298 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
299 Register Reg = Register::index2VirtReg(Index: I);
300 if (MRI.use_empty(RegNo: Reg)) {
301 UseEmpty[I] = true;
302 MFI.unstackifyVReg(VReg: Reg);
303 }
304 }
305
306 // Visit each instruction in the function.
307 for (MachineBasicBlock &MBB : MF) {
308 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: MBB)) {
309 assert(!WebAssembly::isArgument(MI.getOpcode()));
310
311 if (MI.isDebugInstr() || MI.isLabel())
312 continue;
313
314 if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
315 MI.eraseFromParent();
316 Changed = true;
317 continue;
318 }
319
320 // Replace tee instructions with local.tee. The difference is that tee
321 // instructions have two defs, while local.tee instructions have one def
322 // and an index of a local to write to.
323 //
324 // - Before:
325 // TeeReg, Reg = TEE DefReg
326 // INST ..., TeeReg, ...
327 // INST ..., Reg, ...
328 // INST ..., Reg, ...
329 // * DefReg: may or may not be stackified
330 // * Reg: not stackified
331 // * TeeReg: stackified
332 //
333 // - After (when DefReg was already stackified):
334 // TeeReg = LOCAL_TEE LocalId1, DefReg
335 // INST ..., TeeReg, ...
336 // INST ..., Reg, ...
337 // INST ..., Reg, ...
338 // * Reg: mapped to LocalId1
339 // * TeeReg: stackified
340 //
341 // - After (when DefReg was not already stackified):
342 // NewReg = LOCAL_GET LocalId1
343 // TeeReg = LOCAL_TEE LocalId2, NewReg
344 // INST ..., TeeReg, ...
345 // INST ..., Reg, ...
346 // INST ..., Reg, ...
347 // * DefReg: mapped to LocalId1
348 // * Reg: mapped to LocalId2
349 // * TeeReg: stackified
350 if (WebAssembly::isTee(Opc: MI.getOpcode())) {
351 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
352 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
353 Register DefReg = MI.getOperand(i: 2).getReg();
354 const TargetRegisterClass *RC = MRI.getRegClass(Reg: DefReg);
355
356 // Stackify the input if it isn't stackified yet.
357 if (!MFI.isVRegStackified(VReg: DefReg)) {
358 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: DefReg);
359 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
360 unsigned Opc = getLocalGetOpcode(RC);
361 BuildMI(BB&: MBB, I: &MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc), DestReg: NewReg)
362 .addImm(Val: LocalId);
363 MI.getOperand(i: 2).setReg(NewReg);
364 MFI.stackifyVReg(MRI, VReg: NewReg);
365 }
366
367 // Replace the TEE with a LOCAL_TEE.
368 unsigned LocalId =
369 getLocalId(Reg2Local, MFI, CurLocal, Reg: MI.getOperand(i: 1).getReg());
370 unsigned Opc = getLocalTeeOpcode(RC);
371 BuildMI(BB&: MBB, I: &MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc),
372 DestReg: MI.getOperand(i: 0).getReg())
373 .addImm(Val: LocalId)
374 .addReg(RegNo: MI.getOperand(i: 2).getReg());
375
376 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
377
378 MI.eraseFromParent();
379 Changed = true;
380 continue;
381 }
382
383 // Insert local.sets for any defs that aren't stackified yet.
384 for (auto &Def : MI.defs()) {
385 Register OldReg = Def.getReg();
386 if (!MFI.isVRegStackified(VReg: OldReg)) {
387 const TargetRegisterClass *RC = MRI.getRegClass(Reg: OldReg);
388 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
389 auto InsertPt = std::next(x: MI.getIterator());
390 // When libcalls are emitted for thread context, the frame base vreg
391 // has an implicit use in the DW_AT_frame_base debug info, so we
392 // should not remove it.
393 bool NeedsRegForDebug =
394 MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg() &&
395 MF.getFunction().getSubprogram() &&
396 MF.getSubtarget<WebAssemblySubtarget>().hasLibcallThreadContext();
397 if (UseEmpty[OldReg.virtRegIndex()] && !NeedsRegForDebug) {
398 unsigned Opc = getDropOpcode(RC);
399 BuildMI(BB&: MBB, I: InsertPt, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc))
400 .addReg(RegNo: NewReg);
401 if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg())
402 MFI.clearFrameBaseVreg();
403 } else {
404 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
405 unsigned Opc = getLocalSetOpcode(RC);
406
407 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
408
409 BuildMI(BB&: MBB, I: InsertPt, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc))
410 .addImm(Val: LocalId)
411 .addReg(RegNo: NewReg);
412 }
413 // This register operand of the original instruction is now being used
414 // by the inserted drop or local.set instruction, so make it not dead
415 // yet.
416 Def.setReg(NewReg);
417 Def.setIsDead(false);
418 MFI.stackifyVReg(MRI, VReg: NewReg);
419 Changed = true;
420 }
421 }
422
423 // Insert local.gets for any uses that aren't stackified yet.
424 MachineInstr *InsertPt = &MI;
425 for (MachineOperand &MO : reverse(C: MI.explicit_uses())) {
426 if (!MO.isReg())
427 continue;
428
429 Register OldReg = MO.getReg();
430
431 // Inline asm may have a def in the middle of the operands. Our contract
432 // with inline asm register operands is to provide local indices as
433 // immediates.
434 if (MO.isDef()) {
435 assert(MI.isInlineAsm());
436 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
437 // If this register operand is tied to another operand, we can't
438 // change it to an immediate. Untie it first.
439 MI.untieRegOperand(OpIdx: MO.getOperandNo());
440 MO.ChangeToImmediate(ImmVal: LocalId);
441 continue;
442 }
443
444 // If we see a stackified register, prepare to insert subsequent
445 // local.gets before the start of its tree.
446 if (MFI.isVRegStackified(VReg: OldReg)) {
447 InsertPt = findStartOfTree(MO, MRI, MFI);
448 continue;
449 }
450
451 // Our contract with inline asm register operands is to provide local
452 // indices as immediates.
453 if (MI.isInlineAsm()) {
454 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
455 // Untie it first if this reg operand is tied to another operand.
456 MI.untieRegOperand(OpIdx: MO.getOperandNo());
457 MO.ChangeToImmediate(ImmVal: LocalId);
458 continue;
459 }
460
461 // Insert a local.get.
462 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
463 const TargetRegisterClass *RC = MRI.getRegClass(Reg: OldReg);
464 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
465 unsigned Opc = getLocalGetOpcode(RC);
466 // Use a InsertPt as our DebugLoc, since MI may be discontinuous from
467 // the where this local is being inserted, causing non-linear stepping
468 // in the debugger or function entry points where variables aren't live
469 // yet. Alternative is previous instruction, but that is strictly worse
470 // since it can point at the previous statement.
471 // See crbug.com/1251909, crbug.com/1249745
472 InsertPt = BuildMI(BB&: MBB, I: InsertPt, MIMD: InsertPt->getDebugLoc(),
473 MCID: TII->get(Opcode: Opc), DestReg: NewReg).addImm(Val: LocalId);
474 MO.setReg(NewReg);
475 MFI.stackifyVReg(MRI, VReg: NewReg);
476 Changed = true;
477 }
478
479 // Coalesce and eliminate COPY instructions.
480 if (WebAssembly::isCopy(Opc: MI.getOpcode())) {
481 MRI.replaceRegWith(FromReg: MI.getOperand(i: 1).getReg(),
482 ToReg: MI.getOperand(i: 0).getReg());
483 MI.eraseFromParent();
484 Changed = true;
485 }
486 }
487 }
488
489 // Define the locals.
490 // TODO: Sort the locals for better compression.
491 MFI.setNumLocals(CurLocal - MFI.getParams().size());
492 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
493 Register Reg = Register::index2VirtReg(Index: I);
494 auto RL = Reg2Local.find(Val: Reg);
495 if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
496 continue;
497
498 MFI.setLocal(i: RL->second - MFI.getParams().size(),
499 VT: typeForRegClass(RC: MRI.getRegClass(Reg)));
500 Changed = true;
501 }
502
503#ifndef NDEBUG
504 // Assert that all registers have been stackified at this point.
505 for (const MachineBasicBlock &MBB : MF) {
506 for (const MachineInstr &MI : MBB) {
507 if (MI.isDebugInstr() || MI.isLabel())
508 continue;
509 for (const MachineOperand &MO : MI.explicit_operands()) {
510 assert(
511 (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
512 MFI.isVRegStackified(MO.getReg())) &&
513 "WebAssemblyExplicitLocals failed to stackify a register operand");
514 }
515 }
516 }
517#endif
518
519 return Changed;
520}
521
522bool WebAssemblyExplicitLocalsLegacy::runOnMachineFunction(
523 MachineFunction &MF) {
524 return explicitLocals(MF);
525}
526
527PreservedAnalyses
528WebAssemblyExplicitLocalsPass::run(MachineFunction &MF,
529 MachineFunctionAnalysisManager &MFAM) {
530 return explicitLocals(MF) ? getMachineFunctionPassPreservedAnalyses()
531 .preserveSet<CFGAnalyses>()
532 : PreservedAnalyses::all();
533}
534