LLVM  9.0.0svn
WebAssemblyRegStackify.cpp
Go to the documentation of this file.
1 //===-- WebAssemblyRegStackify.cpp - Register Stackification --------------===//
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 implements a register stacking pass.
11 ///
12 /// This pass reorders instructions to put register uses and defs in an order
13 /// such that they form single-use expression trees. Registers fitting this form
14 /// are then marked as "stackified", meaning references to them are replaced by
15 /// "push" and "pop" from the value stack.
16 ///
17 /// This is primarily a code size optimization, since temporary values on the
18 /// value stack don't need to be named.
19 ///
20 //===----------------------------------------------------------------------===//
21 
22 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
23 #include "WebAssembly.h"
26 #include "WebAssemblySubtarget.h"
27 #include "WebAssemblyUtilities.h"
28 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/Support/Debug.h"
39 using namespace llvm;
40 
41 #define DEBUG_TYPE "wasm-reg-stackify"
42 
43 namespace {
44 class WebAssemblyRegStackify final : public MachineFunctionPass {
45  StringRef getPassName() const override {
46  return "WebAssembly Register Stackify";
47  }
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
50  AU.setPreservesCFG();
60  }
61 
62  bool runOnMachineFunction(MachineFunction &MF) override;
63 
64 public:
65  static char ID; // Pass identification, replacement for typeid
66  WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
67 };
68 } // end anonymous namespace
69 
71 INITIALIZE_PASS(WebAssemblyRegStackify, DEBUG_TYPE,
72  "Reorder instructions to use the WebAssembly value stack",
73  false, false)
74 
76  return new WebAssemblyRegStackify();
77 }
78 
79 // Decorate the given instruction with implicit operands that enforce the
80 // expression stack ordering constraints for an instruction which is on
81 // the expression stack.
83  // Write the opaque VALUE_STACK register.
84  if (!MI->definesRegister(WebAssembly::VALUE_STACK))
85  MI->addOperand(MachineOperand::CreateReg(WebAssembly::VALUE_STACK,
86  /*isDef=*/true,
87  /*isImp=*/true));
88 
89  // Also read the opaque VALUE_STACK register.
90  if (!MI->readsRegister(WebAssembly::VALUE_STACK))
91  MI->addOperand(MachineOperand::CreateReg(WebAssembly::VALUE_STACK,
92  /*isDef=*/false,
93  /*isImp=*/true));
94 }
95 
96 // Convert an IMPLICIT_DEF instruction into an instruction which defines
97 // a constant zero value.
100  const TargetInstrInfo *TII,
101  MachineFunction &MF,
102  LiveIntervals &LIS) {
103  assert(MI->getOpcode() == TargetOpcode::IMPLICIT_DEF);
104 
105  const auto *RegClass = MRI.getRegClass(MI->getOperand(0).getReg());
106  if (RegClass == &WebAssembly::I32RegClass) {
107  MI->setDesc(TII->get(WebAssembly::CONST_I32));
109  } else if (RegClass == &WebAssembly::I64RegClass) {
110  MI->setDesc(TII->get(WebAssembly::CONST_I64));
112  } else if (RegClass == &WebAssembly::F32RegClass) {
113  MI->setDesc(TII->get(WebAssembly::CONST_F32));
114  auto *Val = cast<ConstantFP>(Constant::getNullValue(
117  } else if (RegClass == &WebAssembly::F64RegClass) {
118  MI->setDesc(TII->get(WebAssembly::CONST_F64));
119  auto *Val = cast<ConstantFP>(Constant::getNullValue(
122  } else if (RegClass == &WebAssembly::V128RegClass) {
123  unsigned TempReg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
124  MI->setDesc(TII->get(WebAssembly::SPLAT_v4i32));
125  MI->addOperand(MachineOperand::CreateReg(TempReg, false));
126  MachineInstr *Const = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
127  TII->get(WebAssembly::CONST_I32), TempReg)
128  .addImm(0);
129  LIS.InsertMachineInstrInMaps(*Const);
130  } else {
131  llvm_unreachable("Unexpected reg class");
132  }
133 }
134 
135 // Determine whether a call to the callee referenced by
136 // MI->getOperand(CalleeOpNo) reads memory, writes memory, and/or has side
137 // effects.
138 static void queryCallee(const MachineInstr &MI, unsigned CalleeOpNo, bool &Read,
139  bool &Write, bool &Effects, bool &StackPointer) {
140  // All calls can use the stack pointer.
141  StackPointer = true;
142 
143  const MachineOperand &MO = MI.getOperand(CalleeOpNo);
144  if (MO.isGlobal()) {
145  const Constant *GV = MO.getGlobal();
146  if (const auto *GA = dyn_cast<GlobalAlias>(GV))
147  if (!GA->isInterposable())
148  GV = GA->getAliasee();
149 
150  if (const auto *F = dyn_cast<Function>(GV)) {
151  if (!F->doesNotThrow())
152  Effects = true;
153  if (F->doesNotAccessMemory())
154  return;
155  if (F->onlyReadsMemory()) {
156  Read = true;
157  return;
158  }
159  }
160  }
161 
162  // Assume the worst.
163  Write = true;
164  Read = true;
165  Effects = true;
166 }
167 
168 // Determine whether MI reads memory, writes memory, has side effects,
169 // and/or uses the stack pointer value.
170 static void query(const MachineInstr &MI, AliasAnalysis &AA, bool &Read,
171  bool &Write, bool &Effects, bool &StackPointer) {
172  assert(!MI.isTerminator());
173 
174  if (MI.isDebugInstr() || MI.isPosition())
175  return;
176 
177  // Check for loads.
178  if (MI.mayLoad() && !MI.isDereferenceableInvariantLoad(&AA))
179  Read = true;
180 
181  // Check for stores.
182  if (MI.mayStore()) {
183  Write = true;
184  } else if (MI.hasOrderedMemoryRef()) {
185  switch (MI.getOpcode()) {
186  case WebAssembly::DIV_S_I32:
187  case WebAssembly::DIV_S_I64:
188  case WebAssembly::REM_S_I32:
189  case WebAssembly::REM_S_I64:
190  case WebAssembly::DIV_U_I32:
191  case WebAssembly::DIV_U_I64:
192  case WebAssembly::REM_U_I32:
193  case WebAssembly::REM_U_I64:
194  case WebAssembly::I32_TRUNC_S_F32:
195  case WebAssembly::I64_TRUNC_S_F32:
196  case WebAssembly::I32_TRUNC_S_F64:
197  case WebAssembly::I64_TRUNC_S_F64:
198  case WebAssembly::I32_TRUNC_U_F32:
199  case WebAssembly::I64_TRUNC_U_F32:
200  case WebAssembly::I32_TRUNC_U_F64:
201  case WebAssembly::I64_TRUNC_U_F64:
202  // These instruction have hasUnmodeledSideEffects() returning true
203  // because they trap on overflow and invalid so they can't be arbitrarily
204  // moved, however hasOrderedMemoryRef() interprets this plus their lack
205  // of memoperands as having a potential unknown memory reference.
206  break;
207  default:
208  // Record volatile accesses, unless it's a call, as calls are handled
209  // specially below.
210  if (!MI.isCall()) {
211  Write = true;
212  Effects = true;
213  }
214  break;
215  }
216  }
217 
218  // Check for side effects.
219  if (MI.hasUnmodeledSideEffects()) {
220  switch (MI.getOpcode()) {
221  case WebAssembly::DIV_S_I32:
222  case WebAssembly::DIV_S_I64:
223  case WebAssembly::REM_S_I32:
224  case WebAssembly::REM_S_I64:
225  case WebAssembly::DIV_U_I32:
226  case WebAssembly::DIV_U_I64:
227  case WebAssembly::REM_U_I32:
228  case WebAssembly::REM_U_I64:
229  case WebAssembly::I32_TRUNC_S_F32:
230  case WebAssembly::I64_TRUNC_S_F32:
231  case WebAssembly::I32_TRUNC_S_F64:
232  case WebAssembly::I64_TRUNC_S_F64:
233  case WebAssembly::I32_TRUNC_U_F32:
234  case WebAssembly::I64_TRUNC_U_F32:
235  case WebAssembly::I32_TRUNC_U_F64:
236  case WebAssembly::I64_TRUNC_U_F64:
237  // These instructions have hasUnmodeledSideEffects() returning true
238  // because they trap on overflow and invalid so they can't be arbitrarily
239  // moved, however in the specific case of register stackifying, it is safe
240  // to move them because overflow and invalid are Undefined Behavior.
241  break;
242  default:
243  Effects = true;
244  break;
245  }
246  }
247 
248  // Check for writes to __stack_pointer global.
249  if (MI.getOpcode() == WebAssembly::GLOBAL_SET_I32 &&
250  strcmp(MI.getOperand(0).getSymbolName(), "__stack_pointer") == 0)
251  StackPointer = true;
252 
253  // Analyze calls.
254  if (MI.isCall()) {
255  unsigned CalleeOpNo = WebAssembly::getCalleeOpNo(MI);
256  queryCallee(MI, CalleeOpNo, Read, Write, Effects, StackPointer);
257  }
258 }
259 
260 // Test whether Def is safe and profitable to rematerialize.
262  const WebAssemblyInstrInfo *TII) {
263  return Def.isAsCheapAsAMove() && TII->isTriviallyReMaterializable(Def, &AA);
264 }
265 
266 // Identify the definition for this register at this point. This is a
267 // generalization of MachineRegisterInfo::getUniqueVRegDef that uses
268 // LiveIntervals to handle complex cases.
269 static MachineInstr *getVRegDef(unsigned Reg, const MachineInstr *Insert,
270  const MachineRegisterInfo &MRI,
271  const LiveIntervals &LIS) {
272  // Most registers are in SSA form here so we try a quick MRI query first.
273  if (MachineInstr *Def = MRI.getUniqueVRegDef(Reg))
274  return Def;
275 
276  // MRI doesn't know what the Def is. Try asking LIS.
277  if (const VNInfo *ValNo = LIS.getInterval(Reg).getVNInfoBefore(
278  LIS.getInstructionIndex(*Insert)))
279  return LIS.getInstructionFromIndex(ValNo->def);
280 
281  return nullptr;
282 }
283 
284 // Test whether Reg, as defined at Def, has exactly one use. This is a
285 // generalization of MachineRegisterInfo::hasOneUse that uses LiveIntervals
286 // to handle complex cases.
288  MachineDominatorTree &MDT, LiveIntervals &LIS) {
289  // Most registers are in SSA form here so we try a quick MRI query first.
290  if (MRI.hasOneUse(Reg))
291  return true;
292 
293  bool HasOne = false;
294  const LiveInterval &LI = LIS.getInterval(Reg);
295  const VNInfo *DefVNI =
297  assert(DefVNI);
298  for (auto &I : MRI.use_nodbg_operands(Reg)) {
299  const auto &Result = LI.Query(LIS.getInstructionIndex(*I.getParent()));
300  if (Result.valueIn() == DefVNI) {
301  if (!Result.isKill())
302  return false;
303  if (HasOne)
304  return false;
305  HasOne = true;
306  }
307  }
308  return HasOne;
309 }
310 
311 // Test whether it's safe to move Def to just before Insert.
312 // TODO: Compute memory dependencies in a way that doesn't require always
313 // walking the block.
314 // TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
315 // more precise.
316 static bool isSafeToMove(const MachineInstr *Def, const MachineInstr *Insert,
317  AliasAnalysis &AA, const MachineRegisterInfo &MRI) {
318  assert(Def->getParent() == Insert->getParent());
319 
320  // 'catch' and 'extract_exception' should be the first instruction of a BB and
321  // cannot move.
322  if (Def->getOpcode() == WebAssembly::CATCH ||
323  Def->getOpcode() == WebAssembly::EXTRACT_EXCEPTION_I32) {
324  const MachineBasicBlock *MBB = Def->getParent();
325  auto NextI = std::next(MachineBasicBlock::const_iterator(Def));
326  for (auto E = MBB->end(); NextI != E && NextI->isDebugInstr(); ++NextI)
327  ;
328  if (NextI != Insert)
329  return false;
330  }
331 
332  // Check for register dependencies.
333  SmallVector<unsigned, 4> MutableRegisters;
334  for (const MachineOperand &MO : Def->operands()) {
335  if (!MO.isReg() || MO.isUndef())
336  continue;
337  unsigned Reg = MO.getReg();
338 
339  // If the register is dead here and at Insert, ignore it.
340  if (MO.isDead() && Insert->definesRegister(Reg) &&
341  !Insert->readsRegister(Reg))
342  continue;
343 
345  // Ignore ARGUMENTS; it's just used to keep the ARGUMENT_* instructions
346  // from moving down, and we've already checked for that.
347  if (Reg == WebAssembly::ARGUMENTS)
348  continue;
349  // If the physical register is never modified, ignore it.
350  if (!MRI.isPhysRegModified(Reg))
351  continue;
352  // Otherwise, it's a physical register with unknown liveness.
353  return false;
354  }
355 
356  // If one of the operands isn't in SSA form, it has different values at
357  // different times, and we need to make sure we don't move our use across
358  // a different def.
359  if (!MO.isDef() && !MRI.hasOneDef(Reg))
360  MutableRegisters.push_back(Reg);
361  }
362 
363  bool Read = false, Write = false, Effects = false, StackPointer = false;
364  query(*Def, AA, Read, Write, Effects, StackPointer);
365 
366  // If the instruction does not access memory and has no side effects, it has
367  // no additional dependencies.
368  bool HasMutableRegisters = !MutableRegisters.empty();
369  if (!Read && !Write && !Effects && !StackPointer && !HasMutableRegisters)
370  return true;
371 
372  // Scan through the intervening instructions between Def and Insert.
373  MachineBasicBlock::const_iterator D(Def), I(Insert);
374  for (--I; I != D; --I) {
375  bool InterveningRead = false;
376  bool InterveningWrite = false;
377  bool InterveningEffects = false;
378  bool InterveningStackPointer = false;
379  query(*I, AA, InterveningRead, InterveningWrite, InterveningEffects,
380  InterveningStackPointer);
381  if (Effects && InterveningEffects)
382  return false;
383  if (Read && InterveningWrite)
384  return false;
385  if (Write && (InterveningRead || InterveningWrite))
386  return false;
387  if (StackPointer && InterveningStackPointer)
388  return false;
389 
390  for (unsigned Reg : MutableRegisters)
391  for (const MachineOperand &MO : I->operands())
392  if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
393  return false;
394  }
395 
396  return true;
397 }
398 
399 /// Test whether OneUse, a use of Reg, dominates all of Reg's other uses.
400 static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse,
401  const MachineBasicBlock &MBB,
402  const MachineRegisterInfo &MRI,
403  const MachineDominatorTree &MDT,
404  LiveIntervals &LIS,
406  const LiveInterval &LI = LIS.getInterval(Reg);
407 
408  const MachineInstr *OneUseInst = OneUse.getParent();
409  VNInfo *OneUseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*OneUseInst));
410 
411  for (const MachineOperand &Use : MRI.use_nodbg_operands(Reg)) {
412  if (&Use == &OneUse)
413  continue;
414 
415  const MachineInstr *UseInst = Use.getParent();
416  VNInfo *UseVNI = LI.getVNInfoBefore(LIS.getInstructionIndex(*UseInst));
417 
418  if (UseVNI != OneUseVNI)
419  continue;
420 
421  if (UseInst == OneUseInst) {
422  // Another use in the same instruction. We need to ensure that the one
423  // selected use happens "before" it.
424  if (&OneUse > &Use)
425  return false;
426  } else {
427  // Test that the use is dominated by the one selected use.
428  while (!MDT.dominates(OneUseInst, UseInst)) {
429  // Actually, dominating is over-conservative. Test that the use would
430  // happen after the one selected use in the stack evaluation order.
431  //
432  // This is needed as a consequence of using implicit local.gets for
433  // uses and implicit local.sets for defs.
434  if (UseInst->getDesc().getNumDefs() == 0)
435  return false;
436  const MachineOperand &MO = UseInst->getOperand(0);
437  if (!MO.isReg())
438  return false;
439  unsigned DefReg = MO.getReg();
441  !MFI.isVRegStackified(DefReg))
442  return false;
443  assert(MRI.hasOneNonDBGUse(DefReg));
444  const MachineOperand &NewUse = *MRI.use_nodbg_begin(DefReg);
445  const MachineInstr *NewUseInst = NewUse.getParent();
446  if (NewUseInst == OneUseInst) {
447  if (&OneUse > &NewUse)
448  return false;
449  break;
450  }
451  UseInst = NewUseInst;
452  }
453  }
454  }
455  return true;
456 }
457 
458 /// Get the appropriate tee opcode for the given register class.
459 static unsigned getTeeOpcode(const TargetRegisterClass *RC) {
460  if (RC == &WebAssembly::I32RegClass)
461  return WebAssembly::TEE_I32;
462  if (RC == &WebAssembly::I64RegClass)
463  return WebAssembly::TEE_I64;
464  if (RC == &WebAssembly::F32RegClass)
465  return WebAssembly::TEE_F32;
466  if (RC == &WebAssembly::F64RegClass)
467  return WebAssembly::TEE_F64;
468  if (RC == &WebAssembly::V128RegClass)
469  return WebAssembly::TEE_V128;
470  llvm_unreachable("Unexpected register class");
471 }
472 
473 // Shrink LI to its uses, cleaning up LI.
474 static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS) {
475  if (LIS.shrinkToUses(&LI)) {
477  LIS.splitSeparateComponents(LI, SplitLIs);
478  }
479 }
480 
481 /// A single-use def in the same block with no intervening memory or register
482 /// dependencies; move the def down and nest it with the current instruction.
485  MachineInstr *Insert, LiveIntervals &LIS,
488  LLVM_DEBUG(dbgs() << "Move for single use: "; Def->dump());
489 
490  WebAssemblyDebugValueManager DefDIs(Def);
491  MBB.splice(Insert, &MBB, Def);
492  DefDIs.move(Insert);
493  LIS.handleMove(*Def);
494 
495  if (MRI.hasOneDef(Reg) && MRI.hasOneUse(Reg)) {
496  // No one else is using this register for anything so we can just stackify
497  // it in place.
498  MFI.stackifyVReg(Reg);
499  } else {
500  // The register may have unrelated uses or defs; create a new register for
501  // just our one def and use so that we can stackify it.
502  unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
503  Def->getOperand(0).setReg(NewReg);
504  Op.setReg(NewReg);
505 
506  // Tell LiveIntervals about the new register.
508 
509  // Tell LiveIntervals about the changes to the old register.
510  LiveInterval &LI = LIS.getInterval(Reg);
512  LIS.getInstructionIndex(*Op.getParent()).getRegSlot(),
513  /*RemoveDeadValNo=*/true);
514 
515  MFI.stackifyVReg(NewReg);
516 
517  DefDIs.updateReg(NewReg);
518 
519  LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
520  }
521 
522  imposeStackOrdering(Def);
523  return Def;
524 }
525 
526 /// A trivially cloneable instruction; clone it and nest the new copy with the
527 /// current instruction.
533  LLVM_DEBUG(dbgs() << "Rematerializing cheap def: "; Def.dump());
534  LLVM_DEBUG(dbgs() << " - for use in "; Op.getParent()->dump());
535 
536  WebAssemblyDebugValueManager DefDIs(&Def);
537 
538  unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(Reg));
539  TII->reMaterialize(MBB, Insert, NewReg, 0, Def, *TRI);
540  Op.setReg(NewReg);
541  MachineInstr *Clone = &*std::prev(Insert);
542  LIS.InsertMachineInstrInMaps(*Clone);
544  MFI.stackifyVReg(NewReg);
545  imposeStackOrdering(Clone);
546 
547  LLVM_DEBUG(dbgs() << " - Cloned to "; Clone->dump());
548 
549  // Shrink the interval.
550  bool IsDead = MRI.use_empty(Reg);
551  if (!IsDead) {
552  LiveInterval &LI = LIS.getInterval(Reg);
553  shrinkToUses(LI, LIS);
554  IsDead = !LI.liveAt(LIS.getInstructionIndex(Def).getDeadSlot());
555  }
556 
557  // If that was the last use of the original, delete the original.
558  // Move or clone corresponding DBG_VALUEs to the 'Insert' location.
559  if (IsDead) {
560  LLVM_DEBUG(dbgs() << " - Deleting original\n");
561  SlotIndex Idx = LIS.getInstructionIndex(Def).getRegSlot();
562  LIS.removePhysRegDefAt(WebAssembly::ARGUMENTS, Idx);
563  LIS.removeInterval(Reg);
565  Def.eraseFromParent();
566 
567  DefDIs.move(&*Insert);
568  DefDIs.updateReg(NewReg);
569  } else {
570  DefDIs.clone(&*Insert, NewReg);
571  }
572 
573  return Clone;
574 }
575 
576 /// A multiple-use def in the same block with no intervening memory or register
577 /// dependencies; move the def down, nest it with the current instruction, and
578 /// insert a tee to satisfy the rest of the uses. As an illustration, rewrite
579 /// this:
580 ///
581 /// Reg = INST ... // Def
582 /// INST ..., Reg, ... // Insert
583 /// INST ..., Reg, ...
584 /// INST ..., Reg, ...
585 ///
586 /// to this:
587 ///
588 /// DefReg = INST ... // Def (to become the new Insert)
589 /// TeeReg, Reg = TEE_... DefReg
590 /// INST ..., TeeReg, ... // Insert
591 /// INST ..., Reg, ...
592 /// INST ..., Reg, ...
593 ///
594 /// with DefReg and TeeReg stackified. This eliminates a local.get from the
595 /// resulting code.
600  LLVM_DEBUG(dbgs() << "Move and tee for multi-use:"; Def->dump());
601 
602  WebAssemblyDebugValueManager DefDIs(Def);
603 
604  // Move Def into place.
605  MBB.splice(Insert, &MBB, Def);
606  LIS.handleMove(*Def);
607 
608  // Create the Tee and attach the registers.
609  const auto *RegClass = MRI.getRegClass(Reg);
610  unsigned TeeReg = MRI.createVirtualRegister(RegClass);
611  unsigned DefReg = MRI.createVirtualRegister(RegClass);
612  MachineOperand &DefMO = Def->getOperand(0);
613  MachineInstr *Tee = BuildMI(MBB, Insert, Insert->getDebugLoc(),
614  TII->get(getTeeOpcode(RegClass)), TeeReg)
615  .addReg(Reg, RegState::Define)
616  .addReg(DefReg, getUndefRegState(DefMO.isDead()));
617  Op.setReg(TeeReg);
618  DefMO.setReg(DefReg);
619  SlotIndex TeeIdx = LIS.InsertMachineInstrInMaps(*Tee).getRegSlot();
620  SlotIndex DefIdx = LIS.getInstructionIndex(*Def).getRegSlot();
621 
622  DefDIs.move(Insert);
623 
624  // Tell LiveIntervals we moved the original vreg def from Def to Tee.
625  LiveInterval &LI = LIS.getInterval(Reg);
627  VNInfo *ValNo = LI.getVNInfoAt(DefIdx);
628  I->start = TeeIdx;
629  ValNo->def = TeeIdx;
630  shrinkToUses(LI, LIS);
631 
632  // Finish stackifying the new regs.
635  MFI.stackifyVReg(DefReg);
636  MFI.stackifyVReg(TeeReg);
637  imposeStackOrdering(Def);
638  imposeStackOrdering(Tee);
639 
640  DefDIs.clone(Tee, DefReg);
641  DefDIs.clone(Insert, TeeReg);
642 
643  LLVM_DEBUG(dbgs() << " - Replaced register: "; Def->dump());
644  LLVM_DEBUG(dbgs() << " - Tee instruction: "; Tee->dump());
645  return Def;
646 }
647 
648 namespace {
649 /// A stack for walking the tree of instructions being built, visiting the
650 /// MachineOperands in DFS order.
651 class TreeWalkerState {
652  using mop_iterator = MachineInstr::mop_iterator;
653  using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
654  using RangeTy = iterator_range<mop_reverse_iterator>;
655  SmallVector<RangeTy, 4> Worklist;
656 
657 public:
658  explicit TreeWalkerState(MachineInstr *Insert) {
659  const iterator_range<mop_iterator> &Range = Insert->explicit_uses();
660  if (Range.begin() != Range.end())
661  Worklist.push_back(reverse(Range));
662  }
663 
664  bool done() const { return Worklist.empty(); }
665 
666  MachineOperand &pop() {
667  RangeTy &Range = Worklist.back();
668  MachineOperand &Op = *Range.begin();
669  Range = drop_begin(Range, 1);
670  if (Range.begin() == Range.end())
671  Worklist.pop_back();
672  assert((Worklist.empty() ||
673  Worklist.back().begin() != Worklist.back().end()) &&
674  "Empty ranges shouldn't remain in the worklist");
675  return Op;
676  }
677 
678  /// Push Instr's operands onto the stack to be visited.
679  void pushOperands(MachineInstr *Instr) {
680  const iterator_range<mop_iterator> &Range(Instr->explicit_uses());
681  if (Range.begin() != Range.end())
682  Worklist.push_back(reverse(Range));
683  }
684 
685  /// Some of Instr's operands are on the top of the stack; remove them and
686  /// re-insert them starting from the beginning (because we've commuted them).
687  void resetTopOperands(MachineInstr *Instr) {
688  assert(hasRemainingOperands(Instr) &&
689  "Reseting operands should only be done when the instruction has "
690  "an operand still on the stack");
691  Worklist.back() = reverse(Instr->explicit_uses());
692  }
693 
694  /// Test whether Instr has operands remaining to be visited at the top of
695  /// the stack.
696  bool hasRemainingOperands(const MachineInstr *Instr) const {
697  if (Worklist.empty())
698  return false;
699  const RangeTy &Range = Worklist.back();
700  return Range.begin() != Range.end() && Range.begin()->getParent() == Instr;
701  }
702 
703  /// Test whether the given register is present on the stack, indicating an
704  /// operand in the tree that we haven't visited yet. Moving a definition of
705  /// Reg to a point in the tree after that would change its value.
706  ///
707  /// This is needed as a consequence of using implicit local.gets for
708  /// uses and implicit local.sets for defs.
709  bool isOnStack(unsigned Reg) const {
710  for (const RangeTy &Range : Worklist)
711  for (const MachineOperand &MO : Range)
712  if (MO.isReg() && MO.getReg() == Reg)
713  return true;
714  return false;
715  }
716 };
717 
718 /// State to keep track of whether commuting is in flight or whether it's been
719 /// tried for the current instruction and didn't work.
720 class CommutingState {
721  /// There are effectively three states: the initial state where we haven't
722  /// started commuting anything and we don't know anything yet, the tentative
723  /// state where we've commuted the operands of the current instruction and are
724  /// revisiting it, and the declined state where we've reverted the operands
725  /// back to their original order and will no longer commute it further.
726  bool TentativelyCommuting = false;
727  bool Declined = false;
728 
729  /// During the tentative state, these hold the operand indices of the commuted
730  /// operands.
731  unsigned Operand0, Operand1;
732 
733 public:
734  /// Stackification for an operand was not successful due to ordering
735  /// constraints. If possible, and if we haven't already tried it and declined
736  /// it, commute Insert's operands and prepare to revisit it.
737  void maybeCommute(MachineInstr *Insert, TreeWalkerState &TreeWalker,
738  const WebAssemblyInstrInfo *TII) {
739  if (TentativelyCommuting) {
740  assert(!Declined &&
741  "Don't decline commuting until you've finished trying it");
742  // Commuting didn't help. Revert it.
743  TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
744  TentativelyCommuting = false;
745  Declined = true;
746  } else if (!Declined && TreeWalker.hasRemainingOperands(Insert)) {
749  if (TII->findCommutedOpIndices(*Insert, Operand0, Operand1)) {
750  // Tentatively commute the operands and try again.
751  TII->commuteInstruction(*Insert, /*NewMI=*/false, Operand0, Operand1);
752  TreeWalker.resetTopOperands(Insert);
753  TentativelyCommuting = true;
754  Declined = false;
755  }
756  }
757  }
758 
759  /// Stackification for some operand was successful. Reset to the default
760  /// state.
761  void reset() {
762  TentativelyCommuting = false;
763  Declined = false;
764  }
765 };
766 } // end anonymous namespace
767 
768 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
769  LLVM_DEBUG(dbgs() << "********** Register Stackifying **********\n"
770  "********** Function: "
771  << MF.getName() << '\n');
772 
773  bool Changed = false;
776  const auto *TII = MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
777  const auto *TRI = MF.getSubtarget<WebAssemblySubtarget>().getRegisterInfo();
778  AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
779  auto &MDT = getAnalysis<MachineDominatorTree>();
780  auto &LIS = getAnalysis<LiveIntervals>();
781 
782  // Walk the instructions from the bottom up. Currently we don't look past
783  // block boundaries, and the blocks aren't ordered so the block visitation
784  // order isn't significant, but we may want to change this in the future.
785  for (MachineBasicBlock &MBB : MF) {
786  // Don't use a range-based for loop, because we modify the list as we're
787  // iterating over it and the end iterator may change.
788  for (auto MII = MBB.rbegin(); MII != MBB.rend(); ++MII) {
789  MachineInstr *Insert = &*MII;
790  // Don't nest anything inside an inline asm, because we don't have
791  // constraints for $push inputs.
792  if (Insert->isInlineAsm())
793  continue;
794 
795  // Ignore debugging intrinsics.
796  if (Insert->isDebugValue())
797  continue;
798 
799  // Iterate through the inputs in reverse order, since we'll be pulling
800  // operands off the stack in LIFO order.
801  CommutingState Commuting;
802  TreeWalkerState TreeWalker(Insert);
803  while (!TreeWalker.done()) {
804  MachineOperand &Op = TreeWalker.pop();
805 
806  // We're only interested in explicit virtual register operands.
807  if (!Op.isReg())
808  continue;
809 
810  unsigned Reg = Op.getReg();
811  assert(Op.isUse() && "explicit_uses() should only iterate over uses");
812  assert(!Op.isImplicit() &&
813  "explicit_uses() should only iterate over explicit operands");
815  continue;
816 
817  // Identify the definition for this register at this point.
818  MachineInstr *Def = getVRegDef(Reg, Insert, MRI, LIS);
819  if (!Def)
820  continue;
821 
822  // Don't nest an INLINE_ASM def into anything, because we don't have
823  // constraints for $pop outputs.
824  if (Def->isInlineAsm())
825  continue;
826 
827  // Argument instructions represent live-in registers and not real
828  // instructions.
829  if (WebAssembly::isArgument(*Def))
830  continue;
831 
832  // Currently catch's return value register cannot be stackified, because
833  // the wasm LLVM backend currently does not support live-in values
834  // entering blocks, which is a part of multi-value proposal.
835  //
836  // Once we support live-in values of wasm blocks, this can be:
837  // catch ; push except_ref value onto stack
838  // block except_ref -> i32
839  // br_on_exn $__cpp_exception ; pop the except_ref value
840  // end_block
841  //
842  // But because we don't support it yet, the catch instruction's dst
843  // register should be assigned to a local to be propagated across
844  // 'block' boundary now.
845  //
846  // TODO Fix this once we support the multi-value proposal.
847  if (Def->getOpcode() == WebAssembly::CATCH)
848  continue;
849 
850  // Decide which strategy to take. Prefer to move a single-use value
851  // over cloning it, and prefer cloning over introducing a tee.
852  // For moving, we require the def to be in the same block as the use;
853  // this makes things simpler (LiveIntervals' handleMove function only
854  // supports intra-block moves) and it's MachineSink's job to catch all
855  // the sinking opportunities anyway.
856  bool SameBlock = Def->getParent() == &MBB;
857  bool CanMove = SameBlock && isSafeToMove(Def, Insert, AA, MRI) &&
858  !TreeWalker.isOnStack(Reg);
859  if (CanMove && hasOneUse(Reg, Def, MRI, MDT, LIS)) {
860  Insert = moveForSingleUse(Reg, Op, Def, MBB, Insert, LIS, MFI, MRI);
861  } else if (shouldRematerialize(*Def, AA, TII)) {
862  Insert =
863  rematerializeCheapDef(Reg, Op, *Def, MBB, Insert->getIterator(),
864  LIS, MFI, MRI, TII, TRI);
865  } else if (CanMove &&
866  oneUseDominatesOtherUses(Reg, Op, MBB, MRI, MDT, LIS, MFI)) {
867  Insert = moveAndTeeForMultiUse(Reg, Op, Def, MBB, Insert, LIS, MFI,
868  MRI, TII);
869  } else {
870  // We failed to stackify the operand. If the problem was ordering
871  // constraints, Commuting may be able to help.
872  if (!CanMove && SameBlock)
873  Commuting.maybeCommute(Insert, TreeWalker, TII);
874  // Proceed to the next operand.
875  continue;
876  }
877 
878  // If the instruction we just stackified is an IMPLICIT_DEF, convert it
879  // to a constant 0 so that the def is explicit, and the push/pop
880  // correspondence is maintained.
881  if (Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
882  convertImplicitDefToConstZero(Insert, MRI, TII, MF, LIS);
883 
884  // We stackified an operand. Add the defining instruction's operands to
885  // the worklist stack now to continue to build an ever deeper tree.
886  Commuting.reset();
887  TreeWalker.pushOperands(Insert);
888  }
889 
890  // If we stackified any operands, skip over the tree to start looking for
891  // the next instruction we can build a tree on.
892  if (Insert != &*MII) {
893  imposeStackOrdering(&*MII);
894  MII = MachineBasicBlock::iterator(Insert).getReverse();
895  Changed = true;
896  }
897  }
898  }
899 
900  // If we used VALUE_STACK anywhere, add it to the live-in sets everywhere so
901  // that it never looks like a use-before-def.
902  if (Changed) {
903  MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK);
904  for (MachineBasicBlock &MBB : MF)
905  MBB.addLiveIn(WebAssembly::VALUE_STACK);
906  }
907 
908 #ifndef NDEBUG
909  // Verify that pushes and pops are performed in LIFO order.
911  for (MachineBasicBlock &MBB : MF) {
912  for (MachineInstr &MI : MBB) {
913  if (MI.isDebugInstr())
914  continue;
915  for (MachineOperand &MO : reverse(MI.explicit_operands())) {
916  if (!MO.isReg())
917  continue;
918  unsigned Reg = MO.getReg();
919 
920  if (MFI.isVRegStackified(Reg)) {
921  if (MO.isDef())
922  Stack.push_back(Reg);
923  else
924  assert(Stack.pop_back_val() == Reg &&
925  "Register stack pop should be paired with a push");
926  }
927  }
928  }
929  // TODO: Generalize this code to support keeping values on the stack across
930  // basic block boundaries.
931  assert(Stack.empty() &&
932  "Register stack pushes and pops should be balanced");
933  }
934 #endif
935 
936  return Changed;
937 }
static void convertImplicitDefToConstZero(MachineInstr *MI, MachineRegisterInfo &MRI, const TargetInstrInfo *TII, MachineFunction &MF, LiveIntervals &LIS)
static Type * getDoubleTy(LLVMContext &C)
Definition: Type.cpp:164
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:634
bool IsDead
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
SlotIndex def
The index of the defining instruction.
Definition: LiveInterval.h:60
void RemoveMachineInstrFromMaps(MachineInstr &MI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void removePhysRegDefAt(unsigned Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
Segments::iterator iterator
Definition: LiveInterval.h:207
bool isPhysRegModified(unsigned PhysReg, bool SkipNoReturnDef=false) const
Return true if the specified register is modified in this function.
void push_back(const T &Elt)
Definition: SmallVector.h:211
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:384
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:637
iterator_range< use_nodbg_iterator > use_nodbg_operands(unsigned Reg) const
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
bool isInlineAsm() const
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
unsigned const TargetRegisterInfo * TRI
F(f)
bool hasOneDef(unsigned RegNo) const
Return true if there is exactly one operand defining the specified register.
VNInfo - Value Number Information.
Definition: LiveInterval.h:52
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:460
use_nodbg_iterator use_nodbg_begin(unsigned RegNo) const
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
MachineOperand * mop_iterator
iterator/begin/end - Iterate over all operands of a machine instruction.
Definition: MachineInstr.h:451
static MachineOperand CreateReg(unsigned Reg, bool isDef, bool isImp=false, bool isKill=false, bool isDead=false, bool isUndef=false, bool isEarlyClobber=false, unsigned SubReg=0, bool isDebug=false, bool isInternalRead=false, bool isRenamable=false)
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
static void query(const MachineInstr &MI, AliasAnalysis &AA, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
FunctionPass * createWebAssemblyRegStackify()
AnalysisUsage & addRequired()
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
Definition: SlotIndexes.h:259
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
static Type * getFloatTy(LLVMContext &C)
Definition: Type.cpp:163
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:650
static bool oneUseDominatesOtherUses(unsigned Reg, const MachineOperand &OneUse, const MachineBasicBlock &MBB, const MachineRegisterInfo &MRI, const MachineDominatorTree &MDT, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI)
Test whether OneUse, a use of Reg, dominates all of Reg&#39;s other uses.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:410
const char * getSymbolName() const
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
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
SlotIndexes pass.
Definition: SlotIndexes.h:328
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:254
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
AnalysisUsage & addPreservedID(const void *ID)
static bool isSafeToMove(const MachineInstr *Def, const MachineInstr *Insert, AliasAnalysis &AA, const MachineRegisterInfo &MRI)
static bool shouldRematerialize(const MachineInstr &Def, AliasAnalysis &AA, const WebAssemblyInstrInfo *TII)
unsigned getUndefRegState(bool B)
bool isDereferenceableInvariantLoad(AliasAnalysis *AA) const
Return true if this load instruction never traps and points to a memory location whose value doesn&#39;t ...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
Definition: LiveInterval.h:528
TargetInstrInfo - Interface to description of machine instruction set.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
Definition: LiveInterval.h:408
This file contains the declaration of the WebAssembly-specific utility functions. ...
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
static const unsigned CommuteAnyOperandIndex
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:821
MachineInstrBundleIterator< MachineInstr > iterator
static unsigned getTeeOpcode(const TargetRegisterClass *RC)
Get the appropriate tee opcode for the given register class.
unsigned const MachineRegisterInfo * MRI
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.
void removeInterval(unsigned Reg)
Interval removal.
bool liveAt(SlotIndex index) const
Definition: LiveInterval.h:388
static MachineOperand CreateFPImm(const ConstantFP *CFP)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval *> &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
const GlobalValue * getGlobal() const
This file provides WebAssembly-specific target descriptions.
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
Represent the analysis usage information of a pass.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr *> *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses...
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
bool definesRegister(unsigned Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr fully defines the specified register.
self_iterator getIterator()
Definition: ilist_node.h:81
static void imposeStackOrdering(MachineInstr *MI)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:205
iterator_range< decltype(adl_begin(std::declval< T >)))> drop_begin(T &&t, int n)
bool isDebugInstr() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static MachineInstr * getVRegDef(unsigned Reg, const MachineInstr *Insert, const MachineRegisterInfo &MRI, const LiveIntervals &LIS)
iterator_range< mop_iterator > explicit_uses()
Definition: MachineInstr.h:500
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
This file declares the WebAssembly-specific subclass of TargetSubtarget.
Iterator for intrusive lists based on ilist_node.
void setDesc(const MCInstrDesc &tid)
Replace the instruction descriptor (thus opcode) of the current instruction with a new one...
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
bool isArgument(const MachineInstr &MI)
bool isDebugValue() const
MachineOperand class - Representation of each machine instruction operand.
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
bool hasOrderedMemoryRef() const
Return true if this instruction may have an ordered or volatile memory reference, or if the informati...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:301
LiveInterval & getInterval(unsigned Reg)
MachineInstr * getUniqueVRegDef(unsigned Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx...
Definition: LiveInterval.h:416
A range adaptor for a pair of iterators.
bool readsRegister(unsigned Reg, const TargetRegisterInfo *TRI=nullptr) const
Return true if the MachineInstr reads the specified register.
bool use_empty(unsigned RegNo) const
use_empty - Return true if there are no instructions using the specified register.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
#define DEBUG_TYPE
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
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:63
INITIALIZE_PASS(WebAssemblyRegStackify, DEBUG_TYPE, "Reorder instructions to use the WebAssembly value stack", false, false) FunctionPass *llvm
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
bool hasOneUse(unsigned RegNo) const
hasOneUse - Return true if there is exactly one instruction using the specified register.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
unsigned getCalleeOpNo(const MachineInstr &MI)
Returns the operand number of a callee, assuming the argument is a call instruction.
static bool hasOneUse(unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI, MachineDominatorTree &MDT, LiveIntervals &LIS)
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
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
static void queryCallee(const MachineInstr &MI, unsigned CalleeOpNo, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
This file declares WebAssembly-specific per-machine-function information.
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug instruction using the specified regis...
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:808
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isPosition() const
IteratorT begin() const
This file contains the declaration of the WebAssembly-specific manager for DebugValues associated wit...
static MachineInstr * rematerializeCheapDef(unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII, const WebAssemblyRegisterInfo *TRI)
A trivially cloneable instruction; clone it and nest the new copy with the current instruction...
static MachineInstr * moveAndTeeForMultiUse(unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII)
A multiple-use def in the same block with no intervening memory or register dependencies; move the de...
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none...
Definition: LiveInterval.h:423
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
IteratorT end() const
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool isAsCheapAsAMove(QueryType Type=AllInBundle) const
Returns true if this instruction has the same cost (or less) than a move instruction.
Definition: MachineInstr.h:918
unsigned createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block...
LiveInterval & createAndComputeVirtRegInterval(unsigned Reg)
bool isImplicit() const
static MachineInstr * moveForSingleUse(unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI)
A single-use def in the same block with no intervening memory or register dependencies; move the def ...