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