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