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