LLVM  6.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 /// \brief 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. Note that this produces output
35 // which is not valid WebAssembly, though it may be more convenient for writing
36 // LLVM unit tests with.
38  "disable-wasm-explicit-locals", cl::ReallyHidden,
39  cl::desc("WebAssembly: Disable emission of get_local/set_local."),
40  cl::init(false));
41 
42 namespace {
43 class WebAssemblyExplicitLocals final : public MachineFunctionPass {
44  StringRef getPassName() const override {
45  return "WebAssembly Explicit Locals";
46  }
47 
48  void getAnalysisUsage(AnalysisUsage &AU) const override {
49  AU.setPreservesCFG();
52  }
53 
54  bool runOnMachineFunction(MachineFunction &MF) override;
55 
56 public:
57  static char ID; // Pass identification, replacement for typeid
58  WebAssemblyExplicitLocals() : MachineFunctionPass(ID) {}
59 };
60 } // end anonymous namespace
61 
64  return new WebAssemblyExplicitLocals();
65 }
66 
67 /// Return a local id number for the given register, assigning it a new one
68 /// if it doesn't yet have one.
69 static unsigned getLocalId(DenseMap<unsigned, unsigned> &Reg2Local,
70  unsigned &CurLocal, unsigned Reg) {
71  auto P = Reg2Local.insert(std::make_pair(Reg, CurLocal));
72  if (P.second)
73  ++CurLocal;
74  return P.first->second;
75 }
76 
77 /// Get the appropriate drop opcode for the given register class.
78 static unsigned getDropOpcode(const TargetRegisterClass *RC) {
79  if (RC == &WebAssembly::I32RegClass)
80  return WebAssembly::DROP_I32;
81  if (RC == &WebAssembly::I64RegClass)
82  return WebAssembly::DROP_I64;
83  if (RC == &WebAssembly::F32RegClass)
84  return WebAssembly::DROP_F32;
85  if (RC == &WebAssembly::F64RegClass)
86  return WebAssembly::DROP_F64;
87  if (RC == &WebAssembly::V128RegClass)
88  return WebAssembly::DROP_V128;
89  llvm_unreachable("Unexpected register class");
90 }
91 
92 /// Get the appropriate get_local opcode for the given register class.
93 static unsigned getGetLocalOpcode(const TargetRegisterClass *RC) {
94  if (RC == &WebAssembly::I32RegClass)
95  return WebAssembly::GET_LOCAL_I32;
96  if (RC == &WebAssembly::I64RegClass)
97  return WebAssembly::GET_LOCAL_I64;
98  if (RC == &WebAssembly::F32RegClass)
99  return WebAssembly::GET_LOCAL_F32;
100  if (RC == &WebAssembly::F64RegClass)
101  return WebAssembly::GET_LOCAL_F64;
102  if (RC == &WebAssembly::V128RegClass)
103  return WebAssembly::GET_LOCAL_V128;
104  llvm_unreachable("Unexpected register class");
105 }
106 
107 /// Get the appropriate set_local opcode for the given register class.
108 static unsigned getSetLocalOpcode(const TargetRegisterClass *RC) {
109  if (RC == &WebAssembly::I32RegClass)
110  return WebAssembly::SET_LOCAL_I32;
111  if (RC == &WebAssembly::I64RegClass)
112  return WebAssembly::SET_LOCAL_I64;
113  if (RC == &WebAssembly::F32RegClass)
114  return WebAssembly::SET_LOCAL_F32;
115  if (RC == &WebAssembly::F64RegClass)
116  return WebAssembly::SET_LOCAL_F64;
117  if (RC == &WebAssembly::V128RegClass)
118  return WebAssembly::SET_LOCAL_V128;
119  llvm_unreachable("Unexpected register class");
120 }
121 
122 /// Get the appropriate tee_local opcode for the given register class.
123 static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC) {
124  if (RC == &WebAssembly::I32RegClass)
125  return WebAssembly::TEE_LOCAL_I32;
126  if (RC == &WebAssembly::I64RegClass)
127  return WebAssembly::TEE_LOCAL_I64;
128  if (RC == &WebAssembly::F32RegClass)
129  return WebAssembly::TEE_LOCAL_F32;
130  if (RC == &WebAssembly::F64RegClass)
131  return WebAssembly::TEE_LOCAL_F64;
132  if (RC == &WebAssembly::V128RegClass)
133  return WebAssembly::TEE_LOCAL_V128;
134  llvm_unreachable("Unexpected register class");
135 }
136 
137 /// Get the type associated with the given register class.
139  if (RC == &WebAssembly::I32RegClass)
140  return MVT::i32;
141  if (RC == &WebAssembly::I64RegClass)
142  return MVT::i64;
143  if (RC == &WebAssembly::F32RegClass)
144  return MVT::f32;
145  if (RC == &WebAssembly::F64RegClass)
146  return MVT::f64;
147  llvm_unreachable("unrecognized register class");
148 }
149 
150 /// Given a MachineOperand of a stackified vreg, return the instruction at the
151 /// start of the expression tree.
155  unsigned Reg = MO.getReg();
156  assert(MFI.isVRegStackified(Reg));
157  MachineInstr *Def = MRI.getVRegDef(Reg);
158 
159  // Find the first stackified use and proceed from there.
160  for (MachineOperand &DefMO : Def->explicit_uses()) {
161  if (!DefMO.isReg())
162  continue;
163  return FindStartOfTree(DefMO, MRI, MFI);
164  }
165 
166  // If there were no stackified uses, we've reached the start.
167  return Def;
168 }
169 
170 bool WebAssemblyExplicitLocals::runOnMachineFunction(MachineFunction &MF) {
171  DEBUG(dbgs() << "********** Make Locals Explicit **********\n"
172  "********** Function: "
173  << MF.getName() << '\n');
174 
175  // Disable this pass if directed to do so.
177  return false;
178 
179  // Disable this pass if we aren't doing direct wasm object emission.
182  return false;
183 
184  bool Changed = false;
187  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
188 
189  // Map non-stackified virtual registers to their local ids.
191 
192  // Handle ARGUMENTS first to ensure that they get the designated numbers.
193  for (MachineBasicBlock::iterator I = MF.begin()->begin(),
194  E = MF.begin()->end();
195  I != E;) {
196  MachineInstr &MI = *I++;
197  if (!WebAssembly::isArgument(MI))
198  break;
199  unsigned Reg = MI.getOperand(0).getReg();
200  assert(!MFI.isVRegStackified(Reg));
201  Reg2Local[Reg] = MI.getOperand(1).getImm();
202  MI.eraseFromParent();
203  Changed = true;
204  }
205 
206  // Start assigning local numbers after the last parameter.
207  unsigned CurLocal = MFI.getParams().size();
208 
209  // Precompute the set of registers that are unused, so that we can insert
210  // drops to their defs.
211  BitVector UseEmpty(MRI.getNumVirtRegs());
212  for (unsigned i = 0, e = MRI.getNumVirtRegs(); i < e; ++i)
213  UseEmpty[i] = MRI.use_empty(TargetRegisterInfo::index2VirtReg(i));
214 
215  // Visit each instruction in the function.
216  for (MachineBasicBlock &MBB : MF) {
217  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
218  MachineInstr &MI = *I++;
220 
221  if (MI.isDebugValue() || MI.isLabel())
222  continue;
223 
224  // Replace tee instructions with tee_local. The difference is that tee
225  // instructins have two defs, while tee_local instructions have one def
226  // and an index of a local to write to.
227  if (WebAssembly::isTee(MI)) {
229  assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
230  unsigned OldReg = MI.getOperand(2).getReg();
231  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
232 
233  // Stackify the input if it isn't stackified yet.
234  if (!MFI.isVRegStackified(OldReg)) {
235  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
236  unsigned NewReg = MRI.createVirtualRegister(RC);
237  unsigned Opc = getGetLocalOpcode(RC);
238  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
239  .addImm(LocalId);
240  MI.getOperand(2).setReg(NewReg);
241  MFI.stackifyVReg(NewReg);
242  }
243 
244  // Replace the TEE with a TEE_LOCAL.
245  unsigned LocalId =
246  getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
247  unsigned Opc = getTeeLocalOpcode(RC);
248  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
249  MI.getOperand(0).getReg())
250  .addImm(LocalId)
251  .addReg(MI.getOperand(2).getReg());
252 
253  MI.eraseFromParent();
254  Changed = true;
255  continue;
256  }
257 
258  // Insert set_locals for any defs that aren't stackified yet. Currently
259  // we handle at most one def.
260  assert(MI.getDesc().getNumDefs() <= 1);
261  if (MI.getDesc().getNumDefs() == 1) {
262  unsigned OldReg = MI.getOperand(0).getReg();
263  if (!MFI.isVRegStackified(OldReg)) {
264  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
265  unsigned NewReg = MRI.createVirtualRegister(RC);
266  auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
267  if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
268  MI.eraseFromParent();
269  Changed = true;
270  continue;
271  }
272  if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
273  unsigned Opc = getDropOpcode(RC);
274  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
275  .addReg(NewReg);
276  } else {
277  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
278  unsigned Opc = getSetLocalOpcode(RC);
279  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
280  .addImm(LocalId)
281  .addReg(NewReg);
282  }
283  MI.getOperand(0).setReg(NewReg);
284  MFI.stackifyVReg(NewReg);
285  Changed = true;
286  }
287  }
288 
289  // Insert get_locals for any uses that aren't stackified yet.
290  MachineInstr *InsertPt = &MI;
291  for (MachineOperand &MO : reverse(MI.explicit_uses())) {
292  if (!MO.isReg())
293  continue;
294 
295  unsigned OldReg = MO.getReg();
296 
297  // Inline asm may have a def in the middle of the operands. Our contract
298  // with inline asm register operands is to provide local indices as
299  // immediates.
300  if (MO.isDef()) {
302  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
304  MO = MachineOperand::CreateImm(LocalId);
305  continue;
306  }
307 
308  // If we see a stackified register, prepare to insert subsequent
309  // get_locals before the start of its tree.
310  if (MFI.isVRegStackified(OldReg)) {
311  InsertPt = FindStartOfTree(MO, MRI, MFI);
312  continue;
313  }
314 
315  // Our contract with inline asm register operands is to provide local
316  // indices as immediates.
317  if (MI.getOpcode() == TargetOpcode::INLINEASM) {
318  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
320  MO = MachineOperand::CreateImm(LocalId);
321  continue;
322  }
323 
324  // Insert a get_local.
325  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
326  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
327  unsigned NewReg = MRI.createVirtualRegister(RC);
328  unsigned Opc = getGetLocalOpcode(RC);
329  InsertPt =
330  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc), NewReg)
331  .addImm(LocalId);
332  MO.setReg(NewReg);
333  MFI.stackifyVReg(NewReg);
334  Changed = true;
335  }
336 
337  // Coalesce and eliminate COPY instructions.
338  if (WebAssembly::isCopy(MI)) {
339  MRI.replaceRegWith(MI.getOperand(1).getReg(),
340  MI.getOperand(0).getReg());
341  MI.eraseFromParent();
342  Changed = true;
343  }
344  }
345  }
346 
347  // Define the locals.
348  // TODO: Sort the locals for better compression.
349  MFI.setNumLocals(CurLocal - MFI.getParams().size());
350  for (size_t i = 0, e = MRI.getNumVirtRegs(); i < e; ++i) {
352  auto I = Reg2Local.find(Reg);
353  if (I == Reg2Local.end() || I->second < MFI.getParams().size())
354  continue;
355 
356  MFI.setLocal(I->second - MFI.getParams().size(),
357  typeForRegClass(MRI.getRegClass(Reg)));
358  Changed = true;
359  }
360 
361 #ifndef NDEBUG
362  // Assert that all registers have been stackified at this point.
363  for (const MachineBasicBlock &MBB : MF) {
364  for (const MachineInstr &MI : MBB) {
365  if (MI.isDebugValue() || MI.isLabel())
366  continue;
367  for (const MachineOperand &MO : MI.explicit_operands()) {
368  assert(
369  (!MO.isReg() || MRI.use_empty(MO.getReg()) ||
370  MFI.isVRegStackified(MO.getReg())) &&
371  "WebAssemblyExplicitLocals failed to stackify a register operand");
372  }
373  }
374  }
375 #endif
376 
377  return Changed;
378 }
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:805
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
void removeRegOperandFromUseList(MachineOperand *MO)
Remove MO from its use-def list.
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.
bool isOSBinFormatELF() const
Tests whether the OS uses the ELF binary format.
Definition: Triple.h:588
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
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:268
unsigned getReg() const
getReg - Returns the register number.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
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.
Reg
All possible values of the reg field in the ModR/M byte.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:634
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:232
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:287
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...
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:406
unsigned const MachineRegisterInfo * MRI
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.
const Triple & getTargetTriple() const
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.
static cl::opt< bool > DisableWebAssemblyExplicitLocals("disable-wasm-explicit-locals", cl::ReallyHidden, cl::desc("WebAssembly: Disable emission of get_local/set_local."), cl::init(false))
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
iterator_range< mop_iterator > explicit_uses()
Definition: MachineInstr.h:374
This file declares the WebAssembly-specific subclass of TargetSubtarget.
bool isTee(const MachineInstr &MI)
bool isArgument(const MachineInstr &MI)
bool isDebugValue() const
Definition: MachineInstr.h:816
MachineOperand class - Representation of each machine instruction operand.
FunctionPass * createWebAssemblyExplicitLocals()
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:285
int64_t getImm() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static unsigned getTeeLocalOpcode(const TargetRegisterClass *RC)
Get the appropriate tee_local opcode for the given register class.
bool use_empty(unsigned RegNo) const
use_empty - Return true if there are no instructions using the specified register.
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:59
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.
static MachineOperand CreateImm(int64_t Val)
#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())
#define DEBUG(X)
Definition: Debug.h:118
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
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295