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"
30using namespace llvm;
31
32#define DEBUG_TYPE "wasm-explicit-locals"
33
34namespace {
35class WebAssemblyExplicitLocals final : public MachineFunctionPass {
36 StringRef getPassName() const override {
37 return "WebAssembly Explicit Locals";
38 }
39
40 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
48public:
49 static char ID; // Pass identification, replacement for typeid
50 WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
51};
52} // end anonymous namespace
53
54char WebAssemblyExplicitLocals::ID = 0;
55INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
56 "Convert registers to WebAssembly locals", false, false)
57
58FunctionPass *llvm::createWebAssemblyExplicitLocals() {
59 return new WebAssemblyExplicitLocals();
60}
61
62static 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(Reg).virtRegIndex() << '\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.
76static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
77 WebAssemblyFunctionInfo &MFI, unsigned &CurLocal,
78 unsigned Reg) {
79 auto P = Reg2Local.insert(KV: std::make_pair(x&: Reg, y&: CurLocal));
80 if (P.second) {
81 checkFrameBase(MFI, Local: CurLocal, Reg);
82 ++CurLocal;
83 }
84 return P.first->second;
85}
86
87/// Get the appropriate drop opcode for the given register class.
88static 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.
109static 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.
130static 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.
151static 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.
172static 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.
194static 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(VReg: 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(MO&: DefMO, MRI, MFI);
213 }
214
215 // If there were no stackified uses, we've reached the start.
216 return Def;
217}
218
219bool 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(Opc: MI.getOpcode()))
238 break;
239 Register Reg = MI.getOperand(i: 0).getReg();
240 assert(!MFI.isVRegStackified(Reg));
241 auto Local = static_cast<unsigned>(MI.getOperand(i: 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(LocalId: 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(RegNo: Register::index2VirtReg(Index: I));
262
263 // Visit each instruction in the function.
264 for (MachineBasicBlock &MBB : MF) {
265 for (MachineInstr &MI : llvm::make_early_inc_range(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(Opc: MI.getOpcode())) {
308 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
309 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
310 Register DefReg = MI.getOperand(i: 2).getReg();
311 const TargetRegisterClass *RC = MRI.getRegClass(Reg: DefReg);
312
313 // Stackify the input if it isn't stackified yet.
314 if (!MFI.isVRegStackified(VReg: DefReg)) {
315 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: DefReg);
316 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
317 unsigned Opc = getLocalGetOpcode(RC);
318 BuildMI(BB&: MBB, I: &MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc), DestReg: NewReg)
319 .addImm(Val: LocalId);
320 MI.getOperand(i: 2).setReg(NewReg);
321 MFI.stackifyVReg(MRI, VReg: NewReg);
322 }
323
324 // Replace the TEE with a LOCAL_TEE.
325 unsigned LocalId =
326 getLocalId(Reg2Local, MFI, CurLocal, Reg: MI.getOperand(i: 1).getReg());
327 unsigned Opc = getLocalTeeOpcode(RC);
328 BuildMI(BB&: MBB, I: &MI, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc),
329 DestReg: MI.getOperand(i: 0).getReg())
330 .addImm(Val: LocalId)
331 .addReg(RegNo: MI.getOperand(i: 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(VReg: OldReg)) {
344 const TargetRegisterClass *RC = MRI.getRegClass(Reg: OldReg);
345 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
346 auto InsertPt = std::next(x: MI.getIterator());
347 if (UseEmpty[OldReg.virtRegIndex()]) {
348 unsigned Opc = getDropOpcode(RC);
349 MachineInstr *Drop =
350 BuildMI(BB&: MBB, I: InsertPt, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc))
351 .addReg(RegNo: NewReg);
352 // After the drop instruction, this reg operand will not be used
353 Drop->getOperand(i: 0).setIsKill();
354 if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg())
355 MFI.clearFrameBaseVreg();
356 } else {
357 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
358 unsigned Opc = getLocalSetOpcode(RC);
359
360 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
361
362 BuildMI(BB&: MBB, I: InsertPt, MIMD: MI.getDebugLoc(), MCID: TII->get(Opcode: Opc))
363 .addImm(Val: LocalId)
364 .addReg(RegNo: 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, VReg: 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(C: 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, Reg: 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(OpIdx: MO.getOperandNo());
393 MO.ChangeToImmediate(ImmVal: 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(VReg: 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, Reg: OldReg);
408 // Untie it first if this reg operand is tied to another operand.
409 MI.untieRegOperand(OpIdx: MO.getOperandNo());
410 MO.ChangeToImmediate(ImmVal: LocalId);
411 continue;
412 }
413
414 // Insert a local.get.
415 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
416 const TargetRegisterClass *RC = MRI.getRegClass(Reg: OldReg);
417 Register NewReg = MRI.createVirtualRegister(RegClass: 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(BB&: MBB, I: InsertPt, MIMD: InsertPt->getDebugLoc(),
426 MCID: TII->get(Opcode: Opc), DestReg: NewReg).addImm(Val: LocalId);
427 MO.setReg(NewReg);
428 MFI.stackifyVReg(MRI, VReg: NewReg);
429 Changed = true;
430 }
431
432 // Coalesce and eliminate COPY instructions.
433 if (WebAssembly::isCopy(Opc: MI.getOpcode())) {
434 MRI.replaceRegWith(FromReg: MI.getOperand(i: 1).getReg(),
435 ToReg: MI.getOperand(i: 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(Index: I);
447 auto RL = Reg2Local.find(Val: Reg);
448 if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
449 continue;
450
451 MFI.setLocal(i: RL->second - MFI.getParams().size(),
452 VT: typeForRegClass(RC: 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