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::V128RegClass)
161  return MVT::v16i8;
162  if (RC == &WebAssembly::EXCEPT_REFRegClass)
163  return MVT::ExceptRef;
164  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.
172  unsigned Reg = MO.getReg();
173  assert(MFI.isVRegStackified(Reg));
174  MachineInstr *Def = MRI.getVRegDef(Reg);
175 
176  // Find the first stackified use and proceed from there.
177  for (MachineOperand &DefMO : Def->explicit_uses()) {
178  if (!DefMO.isReg())
179  continue;
180  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 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.
194  return false;
195 
196  bool Changed = false;
199  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
200 
201  // Map non-stackified virtual registers to their local ids.
203 
204  // Handle ARGUMENTS first to ensure that they get the designated numbers.
205  for (MachineBasicBlock::iterator I = MF.begin()->begin(),
206  E = MF.begin()->end();
207  I != E;) {
208  MachineInstr &MI = *I++;
209  if (!WebAssembly::isArgument(MI))
210  break;
211  unsigned Reg = MI.getOperand(0).getReg();
212  assert(!MFI.isVRegStackified(Reg));
213  Reg2Local[Reg] = static_cast<unsigned>(MI.getOperand(1).getImm());
214  MI.eraseFromParent();
215  Changed = true;
216  }
217 
218  // Start assigning local numbers after the last parameter.
219  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  BitVector UseEmpty(MRI.getNumVirtRegs());
224  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I < E; ++I)
226 
227  // Visit each instruction in the function.
228  for (MachineBasicBlock &MBB : MF) {
229  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); I != E;) {
230  MachineInstr &MI = *I++;
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  if (WebAssembly::isTee(MI)) {
241  assert(!MFI.isVRegStackified(MI.getOperand(1).getReg()));
242  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  if (!MFI.isVRegStackified(OldReg)) {
247  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
248  unsigned NewReg = MRI.createVirtualRegister(RC);
249  unsigned Opc = getGetLocalOpcode(RC);
250  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc), NewReg)
251  .addImm(LocalId);
252  MI.getOperand(2).setReg(NewReg);
253  MFI.stackifyVReg(NewReg);
254  }
255 
256  // Replace the TEE with a TEE_LOCAL.
257  unsigned LocalId =
258  getLocalId(Reg2Local, CurLocal, MI.getOperand(1).getReg());
259  unsigned Opc = getTeeLocalOpcode(RC);
260  BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(Opc),
261  MI.getOperand(0).getReg())
262  .addImm(LocalId)
263  .addReg(MI.getOperand(2).getReg());
264 
265  MI.eraseFromParent();
266  Changed = true;
267  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  if (MI.getDesc().getNumDefs() == 1) {
274  unsigned OldReg = MI.getOperand(0).getReg();
275  if (!MFI.isVRegStackified(OldReg)) {
276  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
277  unsigned NewReg = MRI.createVirtualRegister(RC);
278  auto InsertPt = std::next(MachineBasicBlock::iterator(&MI));
279  if (MI.getOpcode() == WebAssembly::IMPLICIT_DEF) {
280  MI.eraseFromParent();
281  Changed = true;
282  continue;
283  }
284  if (UseEmpty[TargetRegisterInfo::virtReg2Index(OldReg)]) {
285  unsigned Opc = getDropOpcode(RC);
286  MachineInstr *Drop =
287  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
288  .addReg(NewReg);
289  // After the drop instruction, this reg operand will not be used
290  Drop->getOperand(0).setIsKill();
291  } else {
292  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
293  unsigned Opc = getSetLocalOpcode(RC);
294  BuildMI(MBB, InsertPt, MI.getDebugLoc(), TII->get(Opc))
295  .addImm(LocalId)
296  .addReg(NewReg);
297  }
298  MI.getOperand(0).setReg(NewReg);
299  // This register operand is now being used by the inserted drop
300  // instruction, so make it undead.
301  MI.getOperand(0).setIsDead(false);
302  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  for (MachineOperand &MO : reverse(MI.explicit_uses())) {
310  if (!MO.isReg())
311  continue;
312 
313  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  if (MO.isDef()) {
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  // get_locals 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.getOpcode() == TargetOpcode::INLINEASM) {
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 get_local.
346  unsigned LocalId = getLocalId(Reg2Local, CurLocal, OldReg);
347  const TargetRegisterClass *RC = MRI.getRegClass(OldReg);
348  unsigned NewReg = MRI.createVirtualRegister(RC);
349  unsigned Opc = getGetLocalOpcode(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)) {
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) {
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: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.
This class represents lattice values for constants.
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: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:409
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:667
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:261
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: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:419
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:226
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:109
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...