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