LLVM  8.0.0svn
WebAssemblyExplicitLocals.cpp
Go to the documentation of this file.
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 
20 #include "WebAssembly.h"
22 #include "WebAssemblySubtarget.h"
23 #include "WebAssemblyUtilities.h"
27 #include "llvm/CodeGen/Passes.h"
28 #include "llvm/Support/Debug.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.
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  StringRef getPassName() const override {
47  return "WebAssembly Explicit Locals";
48  }
49 
50  void getAnalysisUsage(AnalysisUsage &AU) const override {
51  AU.setPreservesCFG();
54  }
55 
56  bool runOnMachineFunction(MachineFunction &MF) override;
57 
58 public:
59  static char ID; // Pass identification, replacement for typeid
60  WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
61 };
62 } // end anonymous namespace
63 
65 INITIALIZE_PASS(WebAssemblyExplicitLocals, DEBUG_TYPE,
66  "Convert registers to WebAssembly locals", false, false)
67 
69  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 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
75  unsigned &CurLocal, unsigned Reg) {
76  auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
77  if (P.second)
78  ++CurLocal;
79  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  if (RC == &WebAssembly::I32RegClass)
85  return WebAssembly::DROP_I32;
86  if (RC == &WebAssembly::I64RegClass)
87  return WebAssembly::DROP_I64;
88  if (RC == &WebAssembly::F32RegClass)
89  return WebAssembly::DROP_F32;
90  if (RC == &WebAssembly::F64RegClass)
91  return WebAssembly::DROP_F64;
92  if (RC == &WebAssembly::V128RegClass)
93  return WebAssembly::DROP_V128;
94  if (RC == &WebAssembly::EXCEPT_REFRegClass)
95  return WebAssembly::DROP_EXCEPT_REF;
96  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  if (RC == &WebAssembly::I32RegClass)
102  return WebAssembly::GET_LOCAL_I32;
103  if (RC == &WebAssembly::I64RegClass)
104  return WebAssembly::GET_LOCAL_I64;
105  if (RC == &WebAssembly::F32RegClass)
106  return WebAssembly::GET_LOCAL_F32;
107  if (RC == &WebAssembly::F64RegClass)
108  return WebAssembly::GET_LOCAL_F64;
109  if (RC == &WebAssembly::V128RegClass)
110  return WebAssembly::GET_LOCAL_V128;
111  if (RC == &WebAssembly::EXCEPT_REFRegClass)
112  return WebAssembly::GET_LOCAL_EXCEPT_REF;
113  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  if (RC == &WebAssembly::I32RegClass)
119  return WebAssembly::SET_LOCAL_I32;
120  if (RC == &WebAssembly::I64RegClass)
121  return WebAssembly::SET_LOCAL_I64;
122  if (RC == &WebAssembly::F32RegClass)
123  return WebAssembly::SET_LOCAL_F32;
124  if (RC == &WebAssembly::F64RegClass)
125  return WebAssembly::SET_LOCAL_F64;
126  if (RC == &WebAssembly::V128RegClass)
127  return WebAssembly::SET_LOCAL_V128;
128  if (RC == &WebAssembly::EXCEPT_REFRegClass)
129  return WebAssembly::SET_LOCAL_EXCEPT_REF;
130  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  if (RC == &WebAssembly::I32RegClass)
136  return WebAssembly::TEE_LOCAL_I32;
137  if (RC == &WebAssembly::I64RegClass)
138  return WebAssembly::TEE_LOCAL_I64;
139  if (RC == &WebAssembly::F32RegClass)
140  return WebAssembly::TEE_LOCAL_F32;
141  if (RC == &WebAssembly::F64RegClass)
142  return WebAssembly::TEE_LOCAL_F64;
143  if (RC == &WebAssembly::V128RegClass)
144  return WebAssembly::TEE_LOCAL_V128;
145  if (RC == &WebAssembly::EXCEPT_REFRegClass)
146  return WebAssembly::TEE_LOCAL_EXCEPT_REF;
147  llvm_unreachable("Unexpected register class");
148 }
149 
150 /// Get the type associated with the given register class.
152  if (RC == &WebAssembly::I32RegClass)
153  return MVT::i32;
154  if (RC == &WebAssembly::I64RegClass)
155  return MVT::i64;
156  if (RC == &WebAssembly::F32RegClass)
157  return MVT::f32;
158  if (RC == &WebAssembly::F64RegClass)
159  return MVT::f64;
160  if (RC == &WebAssembly::EXCEPT_REFRegClass)
161  return MVT::ExceptRef;
162  llvm_unreachable("unrecognized register class");
163 }
164 
165 /// Given a MachineOperand of a stackified vreg, return the instruction at the
166 /// start of the expression tree.
170  unsigned Reg = MO.getReg();
171  assert(MFI.isVRegStackified(Reg));
172  MachineInstr *Def = MRI.getVRegDef(Reg);
173 
174  // Find the first stackified use and proceed from there.
175  for (MachineOperand &DefMO : Def->explicit_uses()) {
176  if (!DefMO.isReg())
177  continue;
178  return findStartOfTree(DefMO, MRI, MFI);
179  }
180 
181  // If there were no stackified uses, we've reached the start.
182  return Def;
183 }
184 
185 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
186  LLVM_DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
187  "********** Function: "
188  << MF.getName() << '\n');
189 
190  // Disable this pass if directed to do so.
192  return false;
193 
194  bool Changed = false;
197  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
198 
199  // Map non-stackified virtual registers to their local ids.
201 
202  // Handle ARGUMENTS first to ensure that they get the designated numbers.
203  for (MachineBasicBlock::iterator I = MF.begin()->begin(),
204  E = MF.begin()->end();
205  I != E;) {
206  MachineInstr &MI = *I++;
207  if (!WebAssembly::isArgument(MI))
208  break;
209  unsigned Reg = MI.getOperand(0).getReg();
210  assert(!MFI.isVRegStackified(Reg));
211  Reg2Local[Reg] = static_cast<unsigned>(MI.getOperand(1).getImm());
212  MI.eraseFromParent();
213  Changed = true;
214  }
215 
216  // Start assigning local numbers after the last parameter.
217  unsigned CurLocal = static_cast<unsigned>(MFI.getParams().size());
218 
219  // Precompute the set of registers that are unused, so that we can insert
220  // drops to their defs.
221  BitVector UseEmpty(MRI.getNumVirtRegs());
222  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
224 
225  // Visit each instruction in the function.
226  for (MachineBasicBlock &MBB : MF) {
227  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
228  MachineInstr &MI = *I++;
230 
231  if (MI.isDebugInstr() || MI.isLabel())
232  continue;
233 
234  // Replace tee instructions with tee_local. The difference is that tee
235  // instructins have two defs, while tee_local instructions have one def
236  // and an index of a local to write to.
237  if (WebAssembly::isTee(MI)) {
239  assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
240  unsigned OldReg = MI.getOperand(2).getReg();
241  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
242 
243  // Stackify the input if it isn't stackified yet.
244  if (!MFI.isVRegStackified(OldReg)) {
245  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
246  unsigned NewReg = MRI.createVirtualRegister(RC);
247  unsigned Opc = getGetLocalOpcode(RC);
248  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
249  .addImm(LocalId);
250  MI.getOperand(2).setReg(NewReg);
251  MFI.stackifyVReg(NewReg);
252  }
253 
254  // Replace the TEE with a TEE_LOCAL.
255  unsigned LocalId =
256  getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
257  unsigned Opc = getTeeLocalOpcode(RC);
258  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
259  MI.getOperand(0).getReg())
260  .addImm(LocalId)
261  .addReg(MI.getOperand(2).getReg());
262 
263  MI.eraseFromParent();
264  Changed = true;
265  continue;
266  }
267 
268  // Insert set_locals for any defs that aren't stackified yet. Currently
269  // we handle at most one def.
270  assert(MI.getDesc().getNumDefs() <= 1);
271  if (MI.getDesc().getNumDefs() == 1) {
272  unsigned OldReg = MI.getOperand(0).getReg();
273  if (!MFI.isVRegStackified(OldReg)) {
274  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
275  unsigned NewReg = MRI.createVirtualRegister(RC);
276  auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
277  if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
278  MI.eraseFromParent();
279  Changed = true;
280  continue;
281  }
282  if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
283  unsigned Opc = getDropOpcode(RC);
284  MachineInstr *Drop =
285  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
286  .addReg(NewReg);
287  // After the drop instruction, this reg operand will not be used
288  Drop->getOperand(0).setIsKill();
289  } else {
290  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
291  unsigned Opc = getSetLocalOpcode(RC);
292  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
293  .addImm(LocalId)
294  .addReg(NewReg);
295  }
296  MI.getOperand(0).setReg(NewReg);
297  // This register operand is now being used by the inserted drop
298  // instruction, so make it undead.
299  MI.getOperand(0).setIsDead(false);
300  MFI.stackifyVReg(NewReg);
301  Changed = true;
302  }
303  }
304 
305  // Insert get_locals for any uses that aren't stackified yet.
306  MachineInstr *InsertPt = &MI;
307  for (MachineOperand &MO : reverse(MI.explicit_uses())) {
308  if (!MO.isReg())
309  continue;
310 
311  unsigned OldReg = MO.getReg();
312 
313  // Inline asm may have a def in the middle of the operands. Our contract
314  // with inline asm register operands is to provide local indices as
315  // immediates.
316  if (MO.isDef()) {
318  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
319  // If this register operand is tied to another operand, we can't
320  // change it to an immediate. Untie it first.
321  MI.untieRegOperand(MI.getOperandNo(&MO));
322  MO.ChangeToImmediate(LocalId);
323  continue;
324  }
325 
326  // If we see a stackified register, prepare to insert subsequent
327  // get_locals before the start of its tree.
328  if (MFI.isVRegStackified(OldReg)) {
329  InsertPt = findStartOfTree(MO, MRI, MFI);
330  continue;
331  }
332 
333  // Our contract with inline asm register operands is to provide local
334  // indices as immediates.
335  if (MI.getOpcode() == TargetOpcode::INLINEASM) {
336  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
337  // Untie it first if this reg operand is tied to another operand.
338  MI.untieRegOperand(MI.getOperandNo(&MO));
339  MO.ChangeToImmediate(LocalId);
340  continue;
341  }
342 
343  // Insert a get_local.
344  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
345  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
346  unsigned NewReg = MRI.createVirtualRegister(RC);
347  unsigned Opc = getGetLocalOpcode(RC);
348  InsertPt =
349  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
350  .addImm(LocalId);
351  MO.setReg(NewReg);
352  MFI.stackifyVReg(NewReg);
353  Changed = true;
354  }
355 
356  // Coalesce and eliminate COPY instructions.
357  if (WebAssembly::isCopy(MI)) {
358  MRI.replaceRegWith(MI.getOperand(1).getReg(),
359  MI.getOperand(0).getReg());
360  MI.eraseFromParent();
361  Changed = true;
362  }
363  }
364  }
365 
366  // Define the locals.
367  // TODO: Sort the locals for better compression.
368  MFI.setNumLocals(CurLocal - MFI.getParams().size());
369  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I) {
371  auto RL = Reg2Local.find(Reg);
372  if (RL == Reg2Local.end() || RL->second < MFI.getParams().size())
373  continue;
374 
375  MFI.setLocal(RL->second - MFI.getParams().size(),
376  typeForRegClass(MRI.getRegClass(Reg)));
377  Changed = true;
378  }
379 
380 #ifndef NDEBUG
381  // Assert that all registers have been stackified at this point.
382  for (const MachineBasicBlock &MBB : MF) {
383  for (const MachineInstr &MI : MBB) {
384  if (MI.isDebugInstr() || MI.isLabel())
385  continue;
386  for (const MachineOperand &MO : MI.explicit_operands()) {
387  assert(
388  (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
389  MFI.isVRegStackified(MO.getReg())) &&
390  "WebAssemblyExplicitLocals failed to stackify a register operand");
391  }
392  }
393  }
394 #endif
395 
396  return Changed;
397 }
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:986
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static unsigned index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:383
unsigned getReg() const
getReg - Returns the register number.
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:509
unsigned Reg
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
void setIsDead(bool Val=true)
static unsigned getSetLocalOpcode(const TargetRegisterClass *RC)
Get the appropriate set_local opcode for the given register class.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
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:409
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:627
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:251
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:406
void untieRegOperand(unsigned OpIdx)
Break any tie involving OpIdx.
bool isCopy(const MachineInstr &MI)
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
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:410
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...
static unsigned getGetLocalOpcode(const TargetRegisterClass *RC)
Get the appropriate get_local opcode for the given register class.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
bool isDebugInstr() const
Definition: MachineInstr.h:999
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
iterator_range< mop_iterator > explicit_uses()
Definition: MachineInstr.h:499
void setIsKill(bool Val=true)
This file declares the WebAssembly-specific subclass of TargetSubtarget.
bool isTee(const MachineInstr &MI)
bool isArgument(const MachineInstr &MI)
MachineOperand class - Representation of each machine instruction operand.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:225
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
int64_t getImm() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC)
Get the appropriate tee_local opcode for the given register class.
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.
void setReg(unsigned Reg)
Change the register this operand corresponds to.
#define I(x, y, z)
Definition: MD5.cpp:58
This file declares WebAssembly-specific per-machine-function information.
iterator end()
Definition: DenseMap.h:79
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
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:49
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))
#define LLVM_DEBUG(X)
Definition: Debug.h:123
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:414
FunctionPass * createWebAssemblyExplicitLocals()
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...