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<MachineBlockFrequencyInfo>();
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::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.
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 llvm_unreachable("Unexpected register class");
104}
105
106/// Get the appropriate local.get opcode for the given register class.
107static unsigned getLocalGetOpcode(const TargetRegisterClass *RC) {
108 if (RC == &WebAssembly::I32RegClass)
109 return WebAssembly::LOCAL_GET_I32;
110 if (RC == &WebAssembly::I64RegClass)
111 return WebAssembly::LOCAL_GET_I64;
112 if (RC == &WebAssembly::F32RegClass)
113 return WebAssembly::LOCAL_GET_F32;
114 if (RC == &WebAssembly::F64RegClass)
115 return WebAssembly::LOCAL_GET_F64;
116 if (RC == &WebAssembly::V128RegClass)
117 return WebAssembly::LOCAL_GET_V128;
118 if (RC == &WebAssembly::FUNCREFRegClass)
119 return WebAssembly::LOCAL_GET_FUNCREF;
120 if (RC == &WebAssembly::EXTERNREFRegClass)
121 return WebAssembly::LOCAL_GET_EXTERNREF;
122 llvm_unreachable("Unexpected register class");
123}
124
125/// Get the appropriate local.set opcode for the given register class.
126static unsigned getLocalSetOpcode(const TargetRegisterClass *RC) {
127 if (RC == &WebAssembly::I32RegClass)
128 return WebAssembly::LOCAL_SET_I32;
129 if (RC == &WebAssembly::I64RegClass)
130 return WebAssembly::LOCAL_SET_I64;
131 if (RC == &WebAssembly::F32RegClass)
132 return WebAssembly::LOCAL_SET_F32;
133 if (RC == &WebAssembly::F64RegClass)
134 return WebAssembly::LOCAL_SET_F64;
135 if (RC == &WebAssembly::V128RegClass)
136 return WebAssembly::LOCAL_SET_V128;
137 if (RC == &WebAssembly::FUNCREFRegClass)
138 return WebAssembly::LOCAL_SET_FUNCREF;
139 if (RC == &WebAssembly::EXTERNREFRegClass)
140 return WebAssembly::LOCAL_SET_EXTERNREF;
141 llvm_unreachable("Unexpected register class");
142}
143
144/// Get the appropriate local.tee opcode for the given register class.
145static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC) {
146 if (RC == &WebAssembly::I32RegClass)
147 return WebAssembly::LOCAL_TEE_I32;
148 if (RC == &WebAssembly::I64RegClass)
149 return WebAssembly::LOCAL_TEE_I64;
150 if (RC == &WebAssembly::F32RegClass)
151 return WebAssembly::LOCAL_TEE_F32;
152 if (RC == &WebAssembly::F64RegClass)
153 return WebAssembly::LOCAL_TEE_F64;
154 if (RC == &WebAssembly::V128RegClass)
155 return WebAssembly::LOCAL_TEE_V128;
156 if (RC == &WebAssembly::FUNCREFRegClass)
157 return WebAssembly::LOCAL_TEE_FUNCREF;
158 if (RC == &WebAssembly::EXTERNREFRegClass)
159 return WebAssembly::LOCAL_TEE_EXTERNREF;
160 llvm_unreachable("Unexpected register class");
161}
162
163/// Get the type associated with the given register class.
164static MVT typeForRegClass(const TargetRegisterClass *RC) {
165 if (RC == &WebAssembly::I32RegClass)
166 return MVT::i32;
167 if (RC == &WebAssembly::I64RegClass)
168 return MVT::i64;
169 if (RC == &WebAssembly::F32RegClass)
170 return MVT::f32;
171 if (RC == &WebAssembly::F64RegClass)
172 return MVT::f64;
173 if (RC == &WebAssembly::V128RegClass)
174 return MVT::v16i8;
175 if (RC == &WebAssembly::FUNCREFRegClass)
176 return MVT::funcref;
177 if (RC == &WebAssembly::EXTERNREFRegClass)
178 return MVT::externref;
179 llvm_unreachable("unrecognized register class");
180}
181
182/// Given a MachineOperand of a stackified vreg, return the instruction at the
183/// start of the expression tree.
184static MachineInstr *findStartOfTree(MachineOperand &MO,
185 MachineRegisterInfo &MRI,
186 const WebAssemblyFunctionInfo &MFI) {
187 Register Reg = MO.getReg();
188 assert(MFI.isVRegStackified(Reg));
189 MachineInstr *Def = MRI.getVRegDef(Reg);
190
191 // If this instruction has any non-stackified defs, it is the start
192 for (auto DefReg : Def->defs()) {
193 if (!MFI.isVRegStackified(VReg: DefReg.getReg())) {
194 return Def;
195 }
196 }
197
198 // Find the first stackified use and proceed from there.
199 for (MachineOperand &DefMO : Def->explicit_uses()) {
200 if (!DefMO.isReg())
201 continue;
202 return findStartOfTree(MO&: DefMO, MRI, MFI);
203 }
204
205 // If there were no stackified uses, we've reached the start.
206 return Def;
207}
208
209bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
210 LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
211 "********** Function: "
212 << MF.getName() << '\n');
213
214 bool Changed = false;
215 MachineRegisterInfo &MRI = MF.getRegInfo();
216 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
217 const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
218
219 // Map non-stackified virtual registers to their local ids.
220 DenseMap<unsigned, unsigned> Reg2Local;
221
222 // Handle ARGUMENTS first to ensure that they get the designated numbers.
223 for (MachineBasicBlock::iterator I = MF.begin()->begin(),
224 E = MF.begin()->end();
225 I != E;) {
226 MachineInstr &MI = *I++;
227 if (!WebAssembly::isArgument(Opc: MI.getOpcode()))
228 break;
229 Register Reg = MI.getOperand(i: 0).getReg();
230 assert(!MFI.isVRegStackified(Reg));
231 auto Local = static_cast<unsigned>(MI.getOperand(i: 1).getImm());
232 Reg2Local[Reg] = Local;
233 checkFrameBase(MFI, Local, Reg);
234
235 // Update debug value to point to the local before removing.
236 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId: Local);
237
238 MI.eraseFromParent();
239 Changed = true;
240 }
241
242 // Start assigning local numbers after the last parameter and after any
243 // already-assigned locals.
244 unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
245 CurLocal += static_cast<unsigned>(MFI.getLocals().size());
246
247 // Precompute the set of registers that are unused, so that we can insert
248 // drops to their defs.
249 BitVector UseEmpty(MRI.getNumVirtRegs());
250 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
251 UseEmpty[I] = MRI.use_empty(RegNo: Register::index2VirtReg(Index: I));
252
253 // Visit each instruction in the function.
254 for (MachineBasicBlock &MBB : MF) {
255 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: MBB)) {
256 assert(!WebAssembly::isArgument(MI.getOpcode()));
257
258 if (MI.isDebugInstr() || MI.isLabel())
259 continue;
260
261 if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
262 MI.eraseFromParent();
263 Changed = true;
264 continue;
265 }
266
267 // Replace tee instructions with local.tee. The difference is that tee
268 // instructions have two defs, while local.tee instructions have one def
269 // and an index of a local to write to.
270 //
271 // - Before:
272 // TeeReg, Reg = TEE DefReg
273 // INST ..., TeeReg, ...
274 // INST ..., Reg, ...
275 // INST ..., Reg, ...
276 // * DefReg: may or may not be stackified
277 // * Reg: not stackified
278 // * TeeReg: stackified
279 //
280 // - After (when DefReg was already stackified):
281 // TeeReg = LOCAL_TEE LocalId1, DefReg
282 // INST ..., TeeReg, ...
283 // INST ..., Reg, ...
284 // INST ..., Reg, ...
285 // * Reg: mapped to LocalId1
286 // * TeeReg: stackified
287 //
288 // - After (when DefReg was not already stackified):
289 // NewReg = LOCAL_GET LocalId1
290 // TeeReg = LOCAL_TEE LocalId2, NewReg
291 // INST ..., TeeReg, ...
292 // INST ..., Reg, ...
293 // INST ..., Reg, ...
294 // * DefReg: mapped to LocalId1
295 // * Reg: mapped to LocalId2
296 // * TeeReg: stackified
297 if (WebAssembly::isTee(Opc: MI.getOpcode())) {
298 assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
299 assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
300 Register DefReg = MI.getOperand(i: 2).getReg();
301 const TargetRegisterClass *RC = MRI.getRegClass(Reg: DefReg);
302
303 // Stackify the input if it isn't stackified yet.
304 if (!MFI.isVRegStackified(VReg: DefReg)) {
305 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: DefReg);
306 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
307 unsigned Opc = getLocalGetOpcode(RC);
308 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
309 .addImm(LocalId);
310 MI.getOperand(i: 2).setReg(NewReg);
311 MFI.stackifyVReg(MRI, VReg: NewReg);
312 }
313
314 // Replace the TEE with a LOCAL_TEE.
315 unsigned LocalId =
316 getLocalId(Reg2Local, MFI, CurLocal, Reg: MI.getOperand(i: 1).getReg());
317 unsigned Opc = getLocalTeeOpcode(RC);
318 BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
319 MI.getOperand(i: 0).getReg())
320 .addImm(LocalId)
321 .addReg(MI.getOperand(i: 2).getReg());
322
323 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
324
325 MI.eraseFromParent();
326 Changed = true;
327 continue;
328 }
329
330 // Insert local.sets for any defs that aren't stackified yet.
331 for (auto &Def : MI.defs()) {
332 Register OldReg = Def.getReg();
333 if (!MFI.isVRegStackified(VReg: OldReg)) {
334 const TargetRegisterClass *RC = MRI.getRegClass(Reg: OldReg);
335 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
336 auto InsertPt = std::next(x: MI.getIterator());
337 if (UseEmpty[Register::virtReg2Index(Reg: OldReg)]) {
338 unsigned Opc = getDropOpcode(RC);
339 MachineInstr *Drop =
340 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
341 .addReg(NewReg);
342 // After the drop instruction, this reg operand will not be used
343 Drop->getOperand(i: 0).setIsKill();
344 if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg())
345 MFI.clearFrameBaseVreg();
346 } else {
347 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
348 unsigned Opc = getLocalSetOpcode(RC);
349
350 WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
351
352 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
353 .addImm(LocalId)
354 .addReg(NewReg);
355 }
356 // This register operand of the original instruction is now being used
357 // by the inserted drop or local.set instruction, so make it not dead
358 // yet.
359 Def.setReg(NewReg);
360 Def.setIsDead(false);
361 MFI.stackifyVReg(MRI, VReg: NewReg);
362 Changed = true;
363 }
364 }
365
366 // Insert local.gets for any uses that aren't stackified yet.
367 MachineInstr *InsertPt = &MI;
368 for (MachineOperand &MO : reverse(C: MI.explicit_uses())) {
369 if (!MO.isReg())
370 continue;
371
372 Register OldReg = MO.getReg();
373
374 // Inline asm may have a def in the middle of the operands. Our contract
375 // with inline asm register operands is to provide local indices as
376 // immediates.
377 if (MO.isDef()) {
378 assert(MI.isInlineAsm());
379 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
380 // If this register operand is tied to another operand, we can't
381 // change it to an immediate. Untie it first.
382 MI.untieRegOperand(OpIdx: MO.getOperandNo());
383 MO.ChangeToImmediate(ImmVal: LocalId);
384 continue;
385 }
386
387 // If we see a stackified register, prepare to insert subsequent
388 // local.gets before the start of its tree.
389 if (MFI.isVRegStackified(VReg: OldReg)) {
390 InsertPt = findStartOfTree(MO, MRI, MFI);
391 continue;
392 }
393
394 // Our contract with inline asm register operands is to provide local
395 // indices as immediates.
396 if (MI.isInlineAsm()) {
397 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
398 // Untie it first if this reg operand is tied to another operand.
399 MI.untieRegOperand(OpIdx: MO.getOperandNo());
400 MO.ChangeToImmediate(ImmVal: LocalId);
401 continue;
402 }
403
404 // Insert a local.get.
405 unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, Reg: OldReg);
406 const TargetRegisterClass *RC = MRI.getRegClass(Reg: OldReg);
407 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
408 unsigned Opc = getLocalGetOpcode(RC);
409 // Use a InsertPt as our DebugLoc, since MI may be discontinuous from
410 // the where this local is being inserted, causing non-linear stepping
411 // in the debugger or function entry points where variables aren't live
412 // yet. Alternative is previous instruction, but that is strictly worse
413 // since it can point at the previous statement.
414 // See crbug.com/1251909, crbug.com/1249745
415 InsertPt = BuildMI(MBB, InsertPt, InsertPt->getDebugLoc(),
416 TII->get(Opc), NewReg).addImm(LocalId);
417 MO.setReg(NewReg);
418 MFI.stackifyVReg(MRI, VReg: NewReg);
419 Changed = true;
420 }
421
422 // Coalesce and eliminate COPY instructions.
423 if (WebAssembly::isCopy(Opc: MI.getOpcode())) {
424 MRI.replaceRegWith(FromReg: MI.getOperand(i: 1).getReg(),
425 ToReg: MI.getOperand(i: 0).getReg());
426 MI.eraseFromParent();
427 Changed = true;
428 }
429 }
430 }
431
432 // Define the locals.
433 // TODO: Sort the locals for better compression.
434 MFI.setNumLocals(CurLocal - MFI.getParams().size());
435 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
436 Register Reg = Register::index2VirtReg(Index: I);
437 auto RL = Reg2Local.find(Val: Reg);
438 if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
439 continue;
440
441 MFI.setLocal(i: RL->second - MFI.getParams().size(),
442 VT: typeForRegClass(RC: MRI.getRegClass(Reg)));
443 Changed = true;
444 }
445
446#ifndef NDEBUG
447 // Assert that all registers have been stackified at this point.
448 for (const MachineBasicBlock &MBB : MF) {
449 for (const MachineInstr &MI : MBB) {
450 if (MI.isDebugInstr() || MI.isLabel())
451 continue;
452 for (const MachineOperand &MO : MI.explicit_operands()) {
453 assert(
454 (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
455 MFI.isVRegStackified(MO.getReg())) &&
456 "WebAssemblyExplicitLocals failed to stackify a register operand");
457 }
458 }
459 }
460#endif
461
462 return Changed;
463}
464

source code of llvm/lib/Target/WebAssembly/WebAssemblyExplicitLocals.cpp