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