LLVM  10.0.0svn
WebAssemblyExplicitLocals.cpp
Go to the documentation of this file.
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 
19 #include "WebAssembly.h"
21 #include "WebAssemblySubtarget.h"
22 #include "WebAssemblyUtilities.h"
26 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/Support/Debug.h"
29 using namespace llvm;
30 
31 #define DEBUG_TYPE "wasm-explicit-locals"
32 
33 // A command-line option to disable this pass, and keep implicit locals
34 // for the purpose of testing with lit/llc ONLY.
35 // This produces output which is not valid WebAssembly, and is not supported
36 // by assemblers/disassemblers and other MC based tools.
38  "wasm-disable-explicit-locals", cl::Hidden,
39  cl::desc("WebAssembly: output implicit locals in"
40  " instruction output for test purposes only."),
41  cl::init(false));
42 
43 namespace {
44 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
45  StringRef getPassName() const override {
46  return "WebAssembly Explicit Locals";
47  }
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
50  AU.setPreservesCFG();
53  }
54 
55  bool runOnMachineFunction(MachineFunction &MF) override;
56 
57 public:
58  static char ID; // Pass identification, replacement for typeid
59  WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
60 };
61 } // end anonymous namespace
62 
64 INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
65  "Convert registers to WebAssembly locals", false, false)
66 
68  return new WebAssemblyExplicitLocals();
69 }
70 
71 /// Return a local id number for the given register, assigning it a new one
72 /// if it doesn't yet have one.
73 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
74  unsigned &CurLocal, unsigned Reg) {
75  auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
76  if (P.second)
77  ++CurLocal;
78  return P.first->second;
79 }
80 
81 /// Get the appropriate drop opcode for the given register class.
82 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
83  if (RC == &WebAssembly::I32RegClass)
84  return WebAssembly::DROP_I32;
85  if (RC == &WebAssembly::I64RegClass)
86  return WebAssembly::DROP_I64;
87  if (RC == &WebAssembly::F32RegClass)
88  return WebAssembly::DROP_F32;
89  if (RC == &WebAssembly::F64RegClass)
90  return WebAssembly::DROP_F64;
91  if (RC == &WebAssembly::V128RegClass)
92  return WebAssembly::DROP_V128;
93  if (RC == &WebAssembly::EXNREFRegClass)
94  return WebAssembly::DROP_EXNREF;
95  llvm_unreachable("Unexpected register class");
96 }
97 
98 /// Get the appropriate local.get opcode for the given register class.
99 static unsigned getLocalGetOpcode(const TargetRegisterClass *RC) {
100  if (RC == &WebAssembly::I32RegClass)
101  return WebAssembly::LOCAL_GET_I32;
102  if (RC == &WebAssembly::I64RegClass)
103  return WebAssembly::LOCAL_GET_I64;
104  if (RC == &WebAssembly::F32RegClass)
105  return WebAssembly::LOCAL_GET_F32;
106  if (RC == &WebAssembly::F64RegClass)
107  return WebAssembly::LOCAL_GET_F64;
108  if (RC == &WebAssembly::V128RegClass)
109  return WebAssembly::LOCAL_GET_V128;
110  if (RC == &WebAssembly::EXNREFRegClass)
111  return WebAssembly::LOCAL_GET_EXNREF;
112  llvm_unreachable("Unexpected register class");
113 }
114 
115 /// Get the appropriate local.set opcode for the given register class.
116 static unsigned getLocalSetOpcode(const TargetRegisterClass *RC) {
117  if (RC == &WebAssembly::I32RegClass)
118  return WebAssembly::LOCAL_SET_I32;
119  if (RC == &WebAssembly::I64RegClass)
120  return WebAssembly::LOCAL_SET_I64;
121  if (RC == &WebAssembly::F32RegClass)
122  return WebAssembly::LOCAL_SET_F32;
123  if (RC == &WebAssembly::F64RegClass)
124  return WebAssembly::LOCAL_SET_F64;
125  if (RC == &WebAssembly::V128RegClass)
126  return WebAssembly::LOCAL_SET_V128;
127  if (RC == &WebAssembly::EXNREFRegClass)
128  return WebAssembly::LOCAL_SET_EXNREF;
129  llvm_unreachable("Unexpected register class");
130 }
131 
132 /// Get the appropriate local.tee opcode for the given register class.
133 static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC) {
134  if (RC == &WebAssembly::I32RegClass)
135  return WebAssembly::LOCAL_TEE_I32;
136  if (RC == &WebAssembly::I64RegClass)
137  return WebAssembly::LOCAL_TEE_I64;
138  if (RC == &WebAssembly::F32RegClass)
139  return WebAssembly::LOCAL_TEE_F32;
140  if (RC == &WebAssembly::F64RegClass)
141  return WebAssembly::LOCAL_TEE_F64;
142  if (RC == &WebAssembly::V128RegClass)
143  return WebAssembly::LOCAL_TEE_V128;
144  if (RC == &WebAssembly::EXNREFRegClass)
145  return WebAssembly::LOCAL_TEE_EXNREF;
146  llvm_unreachable("Unexpected register class");
147 }
148 
149 /// Get the type associated with the given register class.
151  if (RC == &WebAssembly::I32RegClass)
152  return MVT::i32;
153  if (RC == &WebAssembly::I64RegClass)
154  return MVT::i64;
155  if (RC == &WebAssembly::F32RegClass)
156  return MVT::f32;
157  if (RC == &WebAssembly::F64RegClass)
158  return MVT::f64;
159  if (RC == &WebAssembly::V128RegClass)
160  return MVT::v16i8;
161  if (RC == &WebAssembly::EXNREFRegClass)
162  return MVT::exnref;
163  llvm_unreachable("unrecognized register class");
164 }
165 
166 /// Given a MachineOperand of a stackified vreg, return the instruction at the
167 /// start of the expression tree.
171  Register Reg = MO.getReg();
172  assert(MFI.isVRegStackified(Reg));
173  MachineInstr *Def = MRI.getVRegDef(Reg);
174 
175  // Find the first stackified use and proceed from there.
176  for (MachineOperand &DefMO : Def->explicit_uses()) {
177  if (!DefMO.isReg())
178  continue;
179  return findStartOfTree(DefMO, MRI, MFI);
180  }
181 
182  // If there were no stackified uses, we've reached the start.
183  return Def;
184 }
185 
186 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
187  LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
188  "********** Function: "
189  << MF.getName() << '\n');
190 
191  // Disable this pass if directed to do so.
193  return false;
194 
195  bool Changed = false;
198  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
199 
200  // Map non-stackified virtual registers to their local ids.
202 
203  // Handle ARGUMENTS first to ensure that they get the designated numbers.
204  for (MachineBasicBlock::iterator I = MF.begin()->begin(),
205  E = MF.begin()->end();
206  I != E;) {
207  MachineInstr &MI = *I++;
209  break;
210  Register Reg = MI.getOperand(0).getReg();
211  assert(!MFI.isVRegStackified(Reg));
212  Reg2Local[Reg] = static_cast<unsigned>(MI.getOperand(1).getImm());
213  MI.eraseFromParent();
214  Changed = true;
215  }
216 
217  // Start assigning local numbers after the last parameter.
218  unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
219 
220  // Precompute the set of registers that are unused, so that we can insert
221  // drops to their defs.
222  BitVector UseEmpty(MRI.getNumVirtRegs());
223  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
224  UseEmpty[I] = MRI.use_empty(Register::index2VirtReg(I));
225 
226  // Visit each instruction in the function.
227  for (MachineBasicBlock &MBB : MF) {
228  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
229  MachineInstr &MI = *I++;
231 
232  if (MI.isDebugInstr() || MI.isLabel())
233  continue;
234 
235  // Replace tee instructions with local.tee. The difference is that tee
236  // instructions have two defs, while local.tee instructions have one def
237  // and an index of a local to write to.
238  if (WebAssembly::isTee(MI.getOpcode())) {
240  assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
241  Register OldReg = MI.getOperand(2).getReg();
242  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
243 
244  // Stackify the input if it isn't stackified yet.
245  if (!MFI.isVRegStackified(OldReg)) {
246  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
247  Register NewReg = MRI.createVirtualRegister(RC);
248  unsigned Opc = getLocalGetOpcode(RC);
249  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
250  .addImm(LocalId);
251  MI.getOperand(2).setReg(NewReg);
252  MFI.stackifyVReg(NewReg);
253  }
254 
255  // Replace the TEE with a LOCAL_TEE.
256  unsigned LocalId =
257  getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
258  unsigned Opc = getLocalTeeOpcode(RC);
259  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
260  MI.getOperand(0).getReg())
261  .addImm(LocalId)
262  .addReg(MI.getOperand(2).getReg());
263 
264  MI.eraseFromParent();
265  Changed = true;
266  continue;
267  }
268 
269  // Insert local.sets for any defs that aren't stackified yet. Currently
270  // we handle at most one def.
271  assert(MI.getDesc().getNumDefs() <= 1);
272  if (MI.getDesc().getNumDefs() == 1) {
273  Register OldReg = MI.getOperand(0).getReg();
274  if (!MFI.isVRegStackified(OldReg)) {
275  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
276  Register NewReg = MRI.createVirtualRegister(RC);
277  auto InsertPt = std::next(MI.getIterator());
278  if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
279  MI.eraseFromParent();
280  Changed = true;
281  continue;
282  }
283  if (UseEmpty[Register::virtReg2Index(OldReg)]) {
284  unsigned Opc = getDropOpcode(RC);
285  MachineInstr *Drop =
286  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
287  .addReg(NewReg);
288  // After the drop instruction, this reg operand will not be used
289  Drop->getOperand(0).setIsKill();
290  } else {
291  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
292  unsigned Opc = getLocalSetOpcode(RC);
293  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
294  .addImm(LocalId)
295  .addReg(NewReg);
296  }
297  MI.getOperand(0).setReg(NewReg);
298  // This register operand of the original instruction is now being used
299  // by the inserted drop or local.set instruction, so make it not dead
300  // yet.
301  MI.getOperand(0).setIsDead(false);
302  MFI.stackifyVReg(NewReg);
303  Changed = true;
304  }
305  }
306 
307  // Insert local.gets for any uses that aren't stackified yet.
308  MachineInstr *InsertPt = &MI;
309  for (MachineOperand &MO : reverse(MI.explicit_uses())) {
310  if (!MO.isReg())
311  continue;
312 
313  Register 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  if (MO.isDef()) {
319  assert(MI.isInlineAsm());
320  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  MI.untieRegOperand(MI.getOperandNo(&MO));
324  MO.ChangeToImmediate(LocalId);
325  continue;
326  }
327 
328  // If we see a stackified register, prepare to insert subsequent
329  // local.gets before the start of its tree.
330  if (MFI.isVRegStackified(OldReg)) {
331  InsertPt = findStartOfTree(MO, MRI, MFI);
332  continue;
333  }
334 
335  // Our contract with inline asm register operands is to provide local
336  // indices as immediates.
337  if (MI.isInlineAsm()) {
338  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
339  // Untie it first if this reg operand is tied to another operand.
340  MI.untieRegOperand(MI.getOperandNo(&MO));
341  MO.ChangeToImmediate(LocalId);
342  continue;
343  }
344 
345  // Insert a local.get.
346  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
347  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
348  Register NewReg = MRI.createVirtualRegister(RC);
349  unsigned Opc = getLocalGetOpcode(RC);
350  InsertPt =
351  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
352  .addImm(LocalId);
353  MO.setReg(NewReg);
354  MFI.stackifyVReg(NewReg);
355  Changed = true;
356  }
357 
358  // Coalesce and eliminate COPY instructions.
359  if (WebAssembly::isCopy(MI.getOpcode())) {
360  MRI.replaceRegWith(MI.getOperand(1).getReg(),
361  MI.getOperand(0).getReg());
362  MI.eraseFromParent();
363  Changed = true;
364  }
365  }
366  }
367 
368  // Define the locals.
369  // TODO: Sort the locals for better compression.
370  MFI.setNumLocals(CurLocal - MFI.getParams().size());
371  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
372  unsigned Reg = Register::index2VirtReg(I);
373  auto RL = Reg2Local.find(Reg);
374  if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
375  continue;
376 
377  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 }
static unsigned getLocalId(DenseMap< unsigned, unsigned > &Reg2Local, unsigned &CurLocal, unsigned Reg)
Return a local id number for the given register, assigning it a new one if it doesn&#39;t yet have one...
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
bool isLabel() const
Returns true if the MachineInstr represents a label.
Definition: MachineInstr.h:999
bool isArgument(unsigned Opc)
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:76
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:385
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:511
unsigned Reg
static unsigned getLocalGetOpcode(const TargetRegisterClass *RC)
Get the appropriate local.get opcode for the given register class.
bool isInlineAsm() const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
bool isCopy(unsigned Opc)
void setIsDead(bool Val=true)
bool isTee(unsigned Opc)
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:83
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:273
static unsigned getDropOpcode(const TargetRegisterClass *RC)
Get the appropriate drop opcode for the given register class.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:408
void untieRegOperand(unsigned OpIdx)
Break any tie involving OpIdx.
void setReg(Register Reg)
Change the register this operand corresponds to.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
This file contains the declaration of the WebAssembly-specific utility functions. ...
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
unsigned const MachineRegisterInfo * MRI
#define DEBUG_TYPE
Machine Value Type.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides WebAssembly-specific target descriptions.
Represent the analysis usage information of a pass.
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
self_iterator getIterator()
Definition: ilist_node.h:81
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
bool isDebugInstr() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
iterator_range< mop_iterator > explicit_uses()
Definition: MachineInstr.h:501
void setIsKill(bool Val=true)
This file declares the WebAssembly-specific subclass of TargetSubtarget.
MachineOperand class - Representation of each machine instruction operand.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:240
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
int64_t getImm() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE, "Convert registers to WebAssembly locals", false, false) FunctionPass *llvm
bool use_empty(unsigned RegNo) const
use_empty - Return true if there are no instructions using the specified register.
static MachineInstr * findStartOfTree(MachineOperand &MO, MachineRegisterInfo &MRI, WebAssemblyFunctionInfo &MFI)
Given a MachineOperand of a stackified vreg, return the instruction at the start of the expression tr...
void replaceRegWith(unsigned FromReg, unsigned ToReg)
replaceRegWith - Replace all instances of FromReg with ToReg in the machine function.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static unsigned getLocalSetOpcode(const TargetRegisterClass *RC)
Get the appropriate local.set opcode for the given register class.
static unsigned getLocalTeeOpcode(const TargetRegisterClass *RC)
Get the appropriate local.tee opcode for the given register class.
#define I(x, y, z)
Definition: MD5.cpp:58
This file declares WebAssembly-specific per-machine-function information.
iterator end()
Definition: DenseMap.h:108
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MVT typeForRegClass(const TargetRegisterClass *RC)
Get the type associated with the given register class.
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
const std::vector< MVT > & getParams() const
static cl::opt< bool > WasmDisableExplicitLocals("wasm-disable-explicit-locals", cl::Hidden, cl::desc("WebAssembly: output implicit locals in" " instruction output for test purposes only."), cl::init(false))
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
FunctionPass * createWebAssemblyExplicitLocals()
Wrapper class representing virtual and physical registers.
Definition: Register.h:19