Line data Source code
1 : //===-- WebAssemblyExplicitLocals.cpp - Make Locals Explicit --------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : ///
10 : /// \file
11 : /// This file converts any remaining registers into WebAssembly locals.
12 : ///
13 : /// After register stackification and register coloring, convert non-stackified
14 : /// registers into locals, inserting explicit get_local and set_local
15 : /// instructions.
16 : ///
17 : //===----------------------------------------------------------------------===//
18 :
19 : #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
20 : #include "WebAssembly.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 : // A command-line option to disable this pass, and keep implicit locals
35 : // for the purpose of testing with lit/llc ONLY.
36 : // This produces output which is not valid WebAssembly, and is not supported
37 : // by assemblers/disassemblers and other MC based tools.
38 : static cl::opt<bool> WasmDisableExplicitLocals(
39 : "wasm-disable-explicit-locals", cl::Hidden,
40 : cl::desc("WebAssembly: output implicit locals in"
41 : " instruction output for test purposes only."),
42 : cl::init(false));
43 :
44 : namespace {
45 : class WebAssemblyExplicitLocals final : public MachineFunctionPass {
46 306 : StringRef getPassName() const override {
47 306 : return "WebAssembly Explicit Locals";
48 : }
49 :
50 306 : void getAnalysisUsage(AnalysisUsage &AU) const override {
51 306 : AU.setPreservesCFG();
52 : AU.addPreserved<MachineBlockFrequencyInfo>();
53 306 : MachineFunctionPass::getAnalysisUsage(AU);
54 306 : }
55 :
56 : bool runOnMachineFunction(MachineFunction &MF) override;
57 :
58 : public:
59 : static char ID; // Pass identification, replacement for typeid
60 306 : WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
61 : };
62 : } // end anonymous namespace
63 :
64 : char WebAssemblyExplicitLocals::ID = 0;
65 199030 : INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
66 : "Convert registers to WebAssembly locals", false, false)
67 :
68 305 : FunctionPass *llvm::createWebAssemblyExplicitLocals() {
69 305 : return new WebAssemblyExplicitLocals();
70 : }
71 :
72 : /// Return a local id number for the given register, assigning it a new one
73 : /// if it doesn't yet have one.
74 2025 : static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
75 : unsigned &CurLocal, unsigned Reg) {
76 2025 : auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
77 2025 : if (P.second)
78 318 : ++CurLocal;
79 2025 : return P.first->second;
80 : }
81 :
82 : /// Get the appropriate drop opcode for the given register class.
83 : static unsigned getDropOpcode(const TargetRegisterClass *RC) {
84 99 : if (RC == &WebAssembly::I32RegClass)
85 : return WebAssembly::DROP_I32;
86 32 : if (RC == &WebAssembly::I64RegClass)
87 : return WebAssembly::DROP_I64;
88 23 : if (RC == &WebAssembly::F32RegClass)
89 : return WebAssembly::DROP_F32;
90 22 : if (RC == &WebAssembly::F64RegClass)
91 : return WebAssembly::DROP_F64;
92 21 : if (RC == &WebAssembly::V128RegClass)
93 : return WebAssembly::DROP_V128;
94 0 : if (RC == &WebAssembly::EXCEPT_REFRegClass)
95 : return WebAssembly::DROP_EXCEPT_REF;
96 0 : llvm_unreachable("Unexpected register class");
97 : }
98 :
99 : /// Get the appropriate get_local opcode for the given register class.
100 : static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
101 1635 : if (RC == &WebAssembly::I32RegClass)
102 : return WebAssembly::GET_LOCAL_I32;
103 818 : if (RC == &WebAssembly::I64RegClass)
104 : return WebAssembly::GET_LOCAL_I64;
105 539 : if (RC == &WebAssembly::F32RegClass)
106 : return WebAssembly::GET_LOCAL_F32;
107 452 : if (RC == &WebAssembly::F64RegClass)
108 : return WebAssembly::GET_LOCAL_F64;
109 360 : if (RC == &WebAssembly::V128RegClass)
110 : return WebAssembly::GET_LOCAL_V128;
111 0 : if (RC == &WebAssembly::EXCEPT_REFRegClass)
112 : return WebAssembly::GET_LOCAL_EXCEPT_REF;
113 0 : llvm_unreachable("Unexpected register class");
114 : }
115 :
116 : /// Get the appropriate set_local opcode for the given register class.
117 : static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
118 274 : if (RC == &WebAssembly::I32RegClass)
119 : return WebAssembly::SET_LOCAL_I32;
120 143 : if (RC == &WebAssembly::I64RegClass)
121 : return WebAssembly::SET_LOCAL_I64;
122 118 : if (RC == &WebAssembly::F32RegClass)
123 : return WebAssembly::SET_LOCAL_F32;
124 114 : if (RC == &WebAssembly::F64RegClass)
125 : return WebAssembly::SET_LOCAL_F64;
126 102 : if (RC == &WebAssembly::V128RegClass)
127 : return WebAssembly::SET_LOCAL_V128;
128 0 : if (RC == &WebAssembly::EXCEPT_REFRegClass)
129 : return WebAssembly::SET_LOCAL_EXCEPT_REF;
130 0 : llvm_unreachable("Unexpected register class");
131 : }
132 :
133 : /// Get the appropriate tee_local opcode for the given register class.
134 : static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
135 102 : if (RC == &WebAssembly::I32RegClass)
136 : return WebAssembly::TEE_LOCAL_I32;
137 8 : if (RC == &WebAssembly::I64RegClass)
138 : return WebAssembly::TEE_LOCAL_I64;
139 2 : if (RC == &WebAssembly::F32RegClass)
140 : return WebAssembly::TEE_LOCAL_F32;
141 2 : if (RC == &WebAssembly::F64RegClass)
142 : return WebAssembly::TEE_LOCAL_F64;
143 0 : if (RC == &WebAssembly::V128RegClass)
144 : return WebAssembly::TEE_LOCAL_V128;
145 0 : if (RC == &WebAssembly::EXCEPT_REFRegClass)
146 : return WebAssembly::TEE_LOCAL_EXCEPT_REF;
147 0 : llvm_unreachable("Unexpected register class");
148 : }
149 :
150 : /// Get the type associated with the given register class.
151 318 : static MVT typeForRegClass(const TargetRegisterClass *RC) {
152 318 : if (RC == &WebAssembly::I32RegClass)
153 178 : return MVT::i32;
154 140 : if (RC == &WebAssembly::I64RegClass)
155 25 : return MVT::i64;
156 115 : if (RC == &WebAssembly::F32RegClass)
157 4 : return MVT::f32;
158 111 : if (RC == &WebAssembly::F64RegClass)
159 9 : return MVT::f64;
160 102 : if (RC == &WebAssembly::V128RegClass)
161 102 : return MVT::v16i8;
162 0 : if (RC == &WebAssembly::EXCEPT_REFRegClass)
163 0 : return MVT::ExceptRef;
164 0 : llvm_unreachable("unrecognized register class");
165 : }
166 :
167 : /// Given a MachineOperand of a stackified vreg, return the instruction at the
168 : /// start of the expression tree.
169 1964 : static MachineInstr *findStartOfTree(MachineOperand &MO,
170 : MachineRegisterInfo &MRI,
171 : WebAssemblyFunctionInfo &MFI) {
172 3388 : unsigned Reg = MO.getReg();
173 : assert(MFI.isVRegStackified(Reg));
174 3388 : MachineInstr *Def = MRI.getVRegDef(Reg);
175 :
176 : // Find the first stackified use and proceed from there.
177 6101 : for (MachineOperand &DefMO : Def->explicit_uses()) {
178 4137 : if (!DefMO.isReg())
179 : continue;
180 1424 : return findStartOfTree(DefMO, MRI, MFI);
181 : }
182 :
183 : // If there were no stackified uses, we've reached the start.
184 : return Def;
185 : }
186 :
187 2984 : bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
188 : LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
189 : "********** Function: "
190 : << MF.getName() << '\n');
191 :
192 : // Disable this pass if directed to do so.
193 2984 : if (WasmDisableExplicitLocals)
194 : return false;
195 :
196 : bool Changed = false;
197 952 : MachineRegisterInfo &MRI = MF.getRegInfo();
198 : WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
199 952 : const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
200 :
201 : // Map non-stackified virtual registers to their local ids.
202 : DenseMap<unsigned, unsigned> Reg2Local;
203 :
204 : // Handle ARGUMENTS first to ensure that they get the designated numbers.
205 880 : for (MachineBasicBlock::iterator I = MF.begin()->begin(),
206 : E = MF.begin()->end();
207 1832 : I != E;) {
208 : MachineInstr &MI = *I++;
209 1830 : if (!WebAssembly::isArgument(MI))
210 : break;
211 880 : unsigned Reg = MI.getOperand(0).getReg();
212 : assert(!MFI.isVRegStackified(Reg));
213 880 : Reg2Local[Reg] = static_cast<unsigned>(MI.getOperand(1).getImm());
214 880 : MI.eraseFromParent();
215 : Changed = true;
216 : }
217 :
218 : // Start assigning local numbers after the last parameter.
219 1904 : unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
220 :
221 : // Precompute the set of registers that are unused, so that we can insert
222 : // drops to their defs.
223 952 : BitVector UseEmpty(MRI.getNumVirtRegs());
224 6598 : for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
225 : UseEmpty[I] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(I));
226 :
227 : // Visit each instruction in the function.
228 2041 : for (MachineBasicBlock &MBB : MF) {
229 5119 : for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
230 : MachineInstr &MI = *I++;
231 : assert(!WebAssembly::isArgument(MI));
232 :
233 : if (MI.isDebugInstr() || MI.isLabel())
234 : continue;
235 :
236 : // Replace tee instructions with tee_local. The difference is that tee
237 : // instructins have two defs, while tee_local instructions have one def
238 : // and an index of a local to write to.
239 3981 : if (WebAssembly::isTee(MI)) {
240 : assert(MFI.isVRegStackified(MI.getOperand(0).getReg()));
241 : assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
242 102 : unsigned OldReg = MI.getOperand(2).getReg();
243 : const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
244 :
245 : // Stackify the input if it isn't stackified yet.
246 102 : if (!MFI.isVRegStackified(OldReg)) {
247 0 : unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
248 0 : unsigned NewReg = MRI.createVirtualRegister(RC);
249 : unsigned Opc = getGetLocalOpcode(RC);
250 0 : BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
251 0 : .addImm(LocalId);
252 0 : MI.getOperand(2).setReg(NewReg);
253 0 : MFI.stackifyVReg(NewReg);
254 : }
255 :
256 : // Replace the TEE with a TEE_LOCAL.
257 : unsigned LocalId =
258 102 : getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
259 : unsigned Opc = getTeeLocalOpcode(RC);
260 102 : BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
261 102 : MI.getOperand(0).getReg())
262 102 : .addImm(LocalId)
263 102 : .addReg(MI.getOperand(2).getReg());
264 :
265 102 : MI.eraseFromParent();
266 : Changed = true;
267 102 : continue;
268 : }
269 :
270 : // Insert set_locals for any defs that aren't stackified yet. Currently
271 : // we handle at most one def.
272 : assert(MI.getDesc().getNumDefs() <= 1);
273 3879 : if (MI.getDesc().getNumDefs() == 1) {
274 2337 : unsigned OldReg = MI.getOperand(0).getReg();
275 2231 : if (!MFI.isVRegStackified(OldReg)) {
276 : const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
277 373 : unsigned NewReg = MRI.createVirtualRegister(RC);
278 373 : auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
279 746 : if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
280 0 : MI.eraseFromParent();
281 : Changed = true;
282 0 : continue;
283 : }
284 373 : if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
285 : unsigned Opc = getDropOpcode(RC);
286 : MachineInstr *Drop =
287 198 : BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
288 99 : .addReg(NewReg);
289 : // After the drop instruction, this reg operand will not be used
290 99 : Drop->getOperand(0).setIsKill();
291 : } else {
292 274 : unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
293 : unsigned Opc = getSetLocalOpcode(RC);
294 822 : BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
295 274 : .addImm(LocalId)
296 274 : .addReg(NewReg);
297 : }
298 373 : MI.getOperand(0).setReg(NewReg);
299 : // This register operand is now being used by the inserted drop
300 : // instruction, so make it undead.
301 373 : MI.getOperand(0).setIsDead(false);
302 373 : MFI.stackifyVReg(NewReg);
303 : Changed = true;
304 : }
305 : }
306 :
307 : // Insert get_locals for any uses that aren't stackified yet.
308 : MachineInstr *InsertPt = &MI;
309 9940 : for (MachineOperand &MO : reverse(MI.explicit_uses())) {
310 6061 : if (!MO.isReg())
311 : continue;
312 :
313 3613 : unsigned OldReg = MO.getReg();
314 :
315 : // Inline asm may have a def in the middle of the operands. Our contract
316 : // with inline asm register operands is to provide local indices as
317 : // immediates.
318 3613 : if (MO.isDef()) {
319 : assert(MI.getOpcode() == TargetOpcode::INLINEASM);
320 7 : unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
321 : // If this register operand is tied to another operand, we can't
322 : // change it to an immediate. Untie it first.
323 7 : MI.untieRegOperand(MI.getOperandNo(&MO));
324 7 : MO.ChangeToImmediate(LocalId);
325 7 : continue;
326 : }
327 :
328 : // If we see a stackified register, prepare to insert subsequent
329 : // get_locals before the start of its tree.
330 3569 : if (MFI.isVRegStackified(OldReg)) {
331 1964 : InsertPt = findStartOfTree(MO, MRI, MFI);
332 1964 : continue;
333 : }
334 :
335 : // Our contract with inline asm register operands is to provide local
336 : // indices as immediates.
337 3284 : if (MI.getOpcode() == TargetOpcode::INLINEASM) {
338 7 : unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
339 : // Untie it first if this reg operand is tied to another operand.
340 7 : MI.untieRegOperand(MI.getOperandNo(&MO));
341 7 : MO.ChangeToImmediate(LocalId);
342 7 : continue;
343 : }
344 :
345 : // Insert a get_local.
346 1635 : unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
347 : const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
348 1635 : unsigned NewReg = MRI.createVirtualRegister(RC);
349 : unsigned Opc = getGetLocalOpcode(RC);
350 : InsertPt =
351 1635 : BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
352 1635 : .addImm(LocalId);
353 1635 : MO.setReg(NewReg);
354 1635 : MFI.stackifyVReg(NewReg);
355 : Changed = true;
356 : }
357 :
358 : // Coalesce and eliminate COPY instructions.
359 3879 : if (WebAssembly::isCopy(MI)) {
360 39 : MRI.replaceRegWith(MI.getOperand(1).getReg(),
361 39 : MI.getOperand(0).getReg());
362 39 : MI.eraseFromParent();
363 : Changed = true;
364 : }
365 : }
366 : }
367 :
368 : // Define the locals.
369 : // TODO: Sort the locals for better compression.
370 1904 : MFI.setNumLocals(CurLocal - MFI.getParams().size());
371 8606 : for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
372 7654 : unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
373 7654 : auto RL = Reg2Local.find(Reg);
374 7654 : if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
375 7336 : continue;
376 :
377 636 : MFI.setLocal(RL->second - MFI.getParams().size(),
378 : typeForRegClass(MRI.getRegClass(Reg)));
379 : Changed = true;
380 : }
381 :
382 : #ifndef NDEBUG
383 : // Assert that all registers have been stackified at this point.
384 : for (const MachineBasicBlock &MBB : MF) {
385 : for (const MachineInstr &MI : MBB) {
386 : if (MI.isDebugInstr() || MI.isLabel())
387 : continue;
388 : for (const MachineOperand &MO : MI.explicit_operands()) {
389 : assert(
390 : (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
391 : MFI.isVRegStackified(MO.getReg())) &&
392 : "WebAssemblyExplicitLocals failed to stackify a register operand");
393 : }
394 : }
395 : }
396 : #endif
397 :
398 : return Changed;
399 : }
|
