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 {
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 
48 public:
49   static char ID; // Pass identification, replacement for typeid
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 
58 FunctionPass *llvm::createWebAssemblyExplicitLocals() {
59   return new WebAssemblyExplicitLocals();
60 }
61 
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.
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.
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.
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::EXNREFRegClass)
121     return WebAssembly::LOCAL_GET_EXNREF;
122   if (RC == &WebAssembly::FUNCREFRegClass)
123     return WebAssembly::LOCAL_GET_FUNCREF;
124   if (RC == &WebAssembly::EXTERNREFRegClass)
125     return WebAssembly::LOCAL_GET_EXTERNREF;
126   llvm_unreachable("Unexpected register class");
127 }
128 
129 /// Get the appropriate local.set opcode for the given register class.
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::EXNREFRegClass)
142     return WebAssembly::LOCAL_SET_EXNREF;
143   if (RC == &WebAssembly::FUNCREFRegClass)
144     return WebAssembly::LOCAL_SET_FUNCREF;
145   if (RC == &WebAssembly::EXTERNREFRegClass)
146     return WebAssembly::LOCAL_SET_EXTERNREF;
147   llvm_unreachable("Unexpected register class");
148 }
149 
150 /// Get the appropriate local.tee opcode for the given register class.
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::EXNREFRegClass)
163     return WebAssembly::LOCAL_TEE_EXNREF;
164   if (RC == &WebAssembly::FUNCREFRegClass)
165     return WebAssembly::LOCAL_TEE_FUNCREF;
166   if (RC == &WebAssembly::EXTERNREFRegClass)
167     return WebAssembly::LOCAL_TEE_EXTERNREF;
168   llvm_unreachable("Unexpected register class");
169 }
170 
171 /// Get the type associated with the given register class.
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::EXNREFRegClass)
184     return MVT::exnref;
185   if (RC == &WebAssembly::FUNCREFRegClass)
186     return MVT::funcref;
187   if (RC == &WebAssembly::EXTERNREFRegClass)
188     return MVT::externref;
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.
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 
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.
253   unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
254 
255   // Precompute the set of registers that are unused, so that we can insert
256   // drops to their defs.
257   BitVector UseEmpty(MRI.getNumVirtRegs());
258   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
259     UseEmpty[I] = MRI.use_empty(Register::index2VirtReg(I));
260 
261   // Visit each instruction in the function.
262   for (MachineBasicBlock &MBB : MF) {
263     for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
264       MachineInstr &MI = *I++;
265       assert(!WebAssembly::isArgument(MI.getOpcode()));
266 
267       if (MI.isDebugInstr() || MI.isLabel())
268         continue;
269 
270       if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
271         MI.eraseFromParent();
272         Changed = true;
273         continue;
274       }
275 
276       // Replace tee instructions with local.tee. The difference is that tee
277       // instructions have two defs, while local.tee instructions have one def
278       // and an index of a local to write to.
279       if (WebAssembly::isTee(MI.getOpcode())) {
280         assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
281         assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
282         Register OldReg = MI.getOperand(2).getReg();
283         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
284 
285         // Stackify the input if it isn't stackified yet.
286         if (!MFI.isVRegStackified(OldReg)) {
287           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
288           Register NewReg = MRI.createVirtualRegister(RC);
289           unsigned Opc = getLocalGetOpcode(RC);
290           BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
291               .addImm(LocalId);
292           MI.getOperand(2).setReg(NewReg);
293           MFI.stackifyVReg(MRI, NewReg);
294         }
295 
296         // Replace the TEE with a LOCAL_TEE.
297         unsigned LocalId =
298             getLocalId(Reg2Local, MFI, CurLocal, MI.getOperand(1).getReg());
299         unsigned Opc = getLocalTeeOpcode(RC);
300         BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
301                 MI.getOperand(0).getReg())
302             .addImm(LocalId)
303             .addReg(MI.getOperand(2).getReg());
304 
305         WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
306 
307         MI.eraseFromParent();
308         Changed = true;
309         continue;
310       }
311 
312       // Insert local.sets for any defs that aren't stackified yet.
313       for (auto &Def : MI.defs()) {
314         Register OldReg = Def.getReg();
315         if (!MFI.isVRegStackified(OldReg)) {
316           const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
317           Register NewReg = MRI.createVirtualRegister(RC);
318           auto InsertPt = std::next(MI.getIterator());
319           if (UseEmpty[Register::virtReg2Index(OldReg)]) {
320             unsigned Opc = getDropOpcode(RC);
321             MachineInstr *Drop =
322                 BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
323                     .addReg(NewReg);
324             // After the drop instruction, this reg operand will not be used
325             Drop->getOperand(0).setIsKill();
326             if (MFI.isFrameBaseVirtual() && OldReg == MFI.getFrameBaseVreg())
327               MFI.clearFrameBaseVreg();
328           } else {
329             unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
330             unsigned Opc = getLocalSetOpcode(RC);
331 
332             WebAssemblyDebugValueManager(&MI).replaceWithLocal(LocalId);
333 
334             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
335                 .addImm(LocalId)
336                 .addReg(NewReg);
337           }
338           // This register operand of the original instruction is now being used
339           // by the inserted drop or local.set instruction, so make it not dead
340           // yet.
341           Def.setReg(NewReg);
342           Def.setIsDead(false);
343           MFI.stackifyVReg(MRI, NewReg);
344           Changed = true;
345         }
346       }
347 
348       // Insert local.gets for any uses that aren't stackified yet.
349       MachineInstr *InsertPt = &MI;
350       for (MachineOperand &MO : reverse(MI.explicit_uses())) {
351         if (!MO.isReg())
352           continue;
353 
354         Register OldReg = MO.getReg();
355 
356         // Inline asm may have a def in the middle of the operands. Our contract
357         // with inline asm register operands is to provide local indices as
358         // immediates.
359         if (MO.isDef()) {
360           assert(MI.isInlineAsm());
361           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
362           // If this register operand is tied to another operand, we can't
363           // change it to an immediate. Untie it first.
364           MI.untieRegOperand(MI.getOperandNo(&MO));
365           MO.ChangeToImmediate(LocalId);
366           continue;
367         }
368 
369         // If we see a stackified register, prepare to insert subsequent
370         // local.gets before the start of its tree.
371         if (MFI.isVRegStackified(OldReg)) {
372           InsertPt = findStartOfTree(MO, MRI, MFI);
373           continue;
374         }
375 
376         // Our contract with inline asm register operands is to provide local
377         // indices as immediates.
378         if (MI.isInlineAsm()) {
379           unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
380           // Untie it first if this reg operand is tied to another operand.
381           MI.untieRegOperand(MI.getOperandNo(&MO));
382           MO.ChangeToImmediate(LocalId);
383           continue;
384         }
385 
386         // Insert a local.get.
387         unsigned LocalId = getLocalId(Reg2Local, MFI, CurLocal, OldReg);
388         const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
389         Register NewReg = MRI.createVirtualRegister(RC);
390         unsigned Opc = getLocalGetOpcode(RC);
391         InsertPt =
392             BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
393                 .addImm(LocalId);
394         MO.setReg(NewReg);
395         MFI.stackifyVReg(MRI, NewReg);
396         Changed = true;
397       }
398 
399       // Coalesce and eliminate COPY instructions.
400       if (WebAssembly::isCopy(MI.getOpcode())) {
401         MRI.replaceRegWith(MI.getOperand(1).getReg(),
402                            MI.getOperand(0).getReg());
403         MI.eraseFromParent();
404         Changed = true;
405       }
406     }
407   }
408 
409   // Define the locals.
410   // TODO: Sort the locals for better compression.
411   MFI.setNumLocals(CurLocal - MFI.getParams().size());
412   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
413     unsigned Reg = Register::index2VirtReg(I);
414     auto RL = Reg2Local.find(Reg);
415     if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
416       continue;
417 
418     MFI.setLocal(RL->second - MFI.getParams().size(),
419                  typeForRegClass(MRI.getRegClass(Reg)));
420     Changed = true;
421   }
422 
423 #ifndef NDEBUG
424   // Assert that all registers have been stackified at this point.
425   for (const MachineBasicBlock &MBB : MF) {
426     for (const MachineInstr &MI : MBB) {
427       if (MI.isDebugInstr() || MI.isLabel())
428         continue;
429       for (const MachineOperand &MO : MI.explicit_operands()) {
430         assert(
431             (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
432              MFI.isVRegStackified(MO.getReg())) &&
433             "WebAssemblyExplicitLocals failed to stackify a register operand");
434       }
435     }
436   }
437 #endif
438 
439   return Changed;
440 }
441