42#define DEBUG_TYPE "wasm-reg-stackify"
47 return "WebAssembly Register Stackify";
70char WebAssemblyRegStackify::ID = 0;
72 "Reorder instructions to use the WebAssembly value stack",
76 return new WebAssemblyRegStackify();
84 if (!
MI->definesRegister(WebAssembly::VALUE_STACK))
90 if (!
MI->readsRegister(WebAssembly::VALUE_STACK))
103 assert(
MI->getOpcode() == TargetOpcode::IMPLICIT_DEF);
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));
117 }
else if (RegClass == &WebAssembly::F64RegClass) {
118 MI->setDesc(
TII->get(WebAssembly::CONST_F64));
122 }
else if (RegClass == &WebAssembly::V128RegClass) {
123 MI->setDesc(
TII->get(WebAssembly::CONST_V128_I64x2));
135 bool &Effects,
bool &StackPointer) {
142 if (
const auto *GA = dyn_cast<GlobalAlias>(GV))
143 if (!GA->isInterposable())
144 GV = GA->getAliasee();
146 if (
const auto *
F = dyn_cast<Function>(GV)) {
147 if (!
F->doesNotThrow())
149 if (
F->doesNotAccessMemory())
151 if (
F->onlyReadsMemory()) {
167 bool &Effects,
bool &StackPointer) {
170 if (
MI.isDebugInstr() ||
MI.isPosition())
174 if (
MI.mayLoad() && !
MI.isDereferenceableInvariantLoad())
180 }
else if (
MI.hasOrderedMemoryRef()) {
181 switch (
MI.getOpcode()) {
182 case WebAssembly::DIV_S_I32:
183 case WebAssembly::DIV_S_I64:
184 case WebAssembly::REM_S_I32:
185 case WebAssembly::REM_S_I64:
186 case WebAssembly::DIV_U_I32:
187 case WebAssembly::DIV_U_I64:
188 case WebAssembly::REM_U_I32:
189 case WebAssembly::REM_U_I64:
190 case WebAssembly::I32_TRUNC_S_F32:
191 case WebAssembly::I64_TRUNC_S_F32:
192 case WebAssembly::I32_TRUNC_S_F64:
193 case WebAssembly::I64_TRUNC_S_F64:
194 case WebAssembly::I32_TRUNC_U_F32:
195 case WebAssembly::I64_TRUNC_U_F32:
196 case WebAssembly::I32_TRUNC_U_F64:
197 case WebAssembly::I64_TRUNC_U_F64:
215 if (
MI.hasUnmodeledSideEffects()) {
216 switch (
MI.getOpcode()) {
217 case WebAssembly::DIV_S_I32:
218 case WebAssembly::DIV_S_I64:
219 case WebAssembly::REM_S_I32:
220 case WebAssembly::REM_S_I64:
221 case WebAssembly::DIV_U_I32:
222 case WebAssembly::DIV_U_I64:
223 case WebAssembly::REM_U_I32:
224 case WebAssembly::REM_U_I64:
225 case WebAssembly::I32_TRUNC_S_F32:
226 case WebAssembly::I64_TRUNC_S_F32:
227 case WebAssembly::I32_TRUNC_S_F64:
228 case WebAssembly::I64_TRUNC_S_F64:
229 case WebAssembly::I32_TRUNC_U_F32:
230 case WebAssembly::I64_TRUNC_U_F32:
231 case WebAssembly::I32_TRUNC_U_F64:
232 case WebAssembly::I64_TRUNC_U_F64:
245 if ((
MI.getOpcode() == WebAssembly::GLOBAL_SET_I32 ||
246 MI.getOpcode() == WebAssembly::GLOBAL_SET_I64) &&
247 strcmp(
MI.getOperand(0).getSymbolName(),
"__stack_pointer") == 0)
259 return Def.isAsCheapAsAMove() &&
TII->isTriviallyReMaterializable(Def);
286 if (
MRI.hasOneUse(Reg))
294 for (
auto &
I :
MRI.use_nodbg_operands(Reg)) {
296 if (Result.valueIn() == DefVNI) {
297 if (!Result.isKill())
332 if (Def != DefI->
defs().begin())
343 for (;
I !=
E; ++
I) {
344 for (
const auto &PriorUse :
I->uses()) {
345 if (&PriorUse ==
Use)
347 if (PriorUse.isReg() && SubsequentDef.getReg() == PriorUse.getReg())
356 for (
auto E =
MBB->
end(); NextI !=
E && NextI->isDebugInstr(); ++NextI)
369 if (!MO.isReg() || MO.isUndef())
374 if (MO.isDead() && Insert->definesRegister(Reg) &&
375 !Insert->readsRegister(Reg))
378 if (Reg.isPhysical()) {
381 if (Reg == WebAssembly::ARGUMENTS)
384 if (!
MRI.isPhysRegModified(Reg))
393 if (!MO.isDef() && !
MRI.hasOneDef(Reg))
397 bool Read =
false, Write =
false, Effects =
false, StackPointer =
false;
398 query(*DefI, Read, Write, Effects, StackPointer);
402 bool HasMutableRegisters = !MutableRegisters.
empty();
403 if (!Read && !Write && !Effects && !StackPointer && !HasMutableRegisters)
408 for (--
I;
I !=
D; --
I) {
409 bool InterveningRead =
false;
410 bool InterveningWrite =
false;
411 bool InterveningEffects =
false;
412 bool InterveningStackPointer =
false;
413 query(*
I, InterveningRead, InterveningWrite, InterveningEffects,
414 InterveningStackPointer);
415 if (Effects && InterveningEffects)
417 if (Read && InterveningWrite)
419 if (Write && (InterveningRead || InterveningWrite))
421 if (StackPointer && InterveningStackPointer)
424 for (
unsigned Reg : MutableRegisters)
426 if (MO.isReg() && MO.isDef() && MO.getReg() == Reg)
452 if (UseVNI != OneUseVNI)
455 if (UseInst == OneUseInst) {
462 while (!MDT.
dominates(OneUseInst, UseInst)) {
479 if (NewUseInst == OneUseInst) {
480 if (&OneUse > &NewUse)
484 UseInst = NewUseInst;
493 if (RC == &WebAssembly::I32RegClass)
494 return WebAssembly::TEE_I32;
495 if (RC == &WebAssembly::I64RegClass)
496 return WebAssembly::TEE_I64;
497 if (RC == &WebAssembly::F32RegClass)
498 return WebAssembly::TEE_F32;
499 if (RC == &WebAssembly::F64RegClass)
500 return WebAssembly::TEE_F64;
501 if (RC == &WebAssembly::V128RegClass)
502 return WebAssembly::TEE_V128;
503 if (RC == &WebAssembly::EXTERNREFRegClass)
504 return WebAssembly::TEE_EXTERNREF;
505 if (RC == &WebAssembly::FUNCREFRegClass)
506 return WebAssembly::TEE_FUNCREF;
532 if (
MRI.hasOneDef(Reg) &&
MRI.hasOneUse(Reg)) {
539 Register NewReg =
MRI.createVirtualRegister(
MRI.getRegClass(Reg));
540 Def->getOperand(0).setReg(NewReg);
575 Register NewReg =
MRI.createVirtualRegister(
MRI.getRegClass(Reg));
576 TII->reMaterialize(
MBB, Insert, NewReg, 0, Def, *
TRI);
602 Def.eraseFromParent();
604 DefDIs.
move(&*Insert);
607 DefDIs.
clone(&*Insert, NewReg);
646 const auto *RegClass =
MRI.getRegClass(Reg);
647 Register TeeReg =
MRI.createVirtualRegister(RegClass);
648 Register DefReg =
MRI.createVirtualRegister(RegClass);
677 DefDIs.
clone(Tee, DefReg);
678 DefDIs.
clone(Insert, TeeReg);
688class TreeWalkerState {
690 using mop_reverse_iterator = std::reverse_iterator<mop_iterator>;
701 bool done()
const {
return Worklist.
empty(); }
710 "Empty ranges shouldn't remain in the worklist");
724 assert(hasRemainingOperands(Instr) &&
725 "Reseting operands should only be done when the instruction has "
726 "an operand still on the stack");
732 bool hasRemainingOperands(
const MachineInstr *Instr)
const {
733 if (Worklist.
empty())
736 return !
Range.empty() &&
Range.begin()->getParent() == Instr;
745 bool isOnStack(
unsigned Reg)
const {
746 for (
const RangeTy &Range : Worklist)
748 if (MO.isReg() && MO.getReg() == Reg)
756class CommutingState {
762 bool TentativelyCommuting =
false;
763 bool Declined =
false;
767 unsigned Operand0, Operand1;
773 void maybeCommute(
MachineInstr *Insert, TreeWalkerState &TreeWalker,
775 if (TentativelyCommuting) {
777 "Don't decline commuting until you've finished trying it");
779 TII->commuteInstruction(*Insert,
false, Operand0, Operand1);
780 TentativelyCommuting =
false;
782 }
else if (!Declined && TreeWalker.hasRemainingOperands(Insert)) {
785 if (
TII->findCommutedOpIndices(*Insert, Operand0, Operand1)) {
787 TII->commuteInstruction(*Insert,
false, Operand0, Operand1);
788 TreeWalker.resetTopOperands(Insert);
789 TentativelyCommuting =
true;
798 TentativelyCommuting =
false;
804bool WebAssemblyRegStackify::runOnMachineFunction(
MachineFunction &MF) {
805 LLVM_DEBUG(
dbgs() <<
"********** Register Stackifying **********\n"
806 "********** Function: "
809 bool Changed =
false;
814 auto &MDT = getAnalysis<MachineDominatorTree>();
815 auto &LIS = getAnalysis<LiveIntervals>();
827 if (
Insert->isInlineAsm())
831 if (
Insert->isDebugValue())
836 CommutingState Commuting;
837 TreeWalkerState TreeWalker(Insert);
838 while (!TreeWalker.done()) {
846 assert(
Use.isUse() &&
"explicit_uses() should only iterate over uses");
848 "explicit_uses() should only iterate over explicit operands");
849 if (
Reg.isPhysical())
878 !TreeWalker.isOnStack(Reg);
898 if (!CanMove && SameBlock)
899 Commuting.maybeCommute(Insert, TreeWalker,
TII);
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())
913 Register DefReg = SubsequentDef->getReg();
916 if (DefReg !=
UseReg || !
MRI.hasOneUse(DefReg))
926 if (
Insert->getOpcode() == TargetOpcode::IMPLICIT_DEF)
932 TreeWalker.pushOperands(Insert);
937 if (Insert != &*MII) {
948 MF.getRegInfo().addLiveIn(WebAssembly::VALUE_STACK);
958 if (
MI.isDebugInstr())
966 "Register stack pop should be paired with a push");
973 Stack.push_back(MO.getReg());
979 "Register stack pushes and pops should be balanced");
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static Register UseReg(const MachineOperand &MO)
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file contains the declaration of the WebAssembly-specific manager for DebugValues associated wit...
This file provides WebAssembly-specific target descriptions.
This file declares WebAssembly-specific per-machine-function information.
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 unsigned getTeeOpcode(const TargetRegisterClass *RC)
Get the appropriate tee opcode for the given register class.
static bool hasOneUse(unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI, MachineDominatorTree &MDT, LiveIntervals &LIS)
static MachineInstr * getVRegDef(unsigned Reg, const MachineInstr *Insert, const MachineRegisterInfo &MRI, const LiveIntervals &LIS)
static void convertImplicitDefToConstZero(MachineInstr *MI, MachineRegisterInfo &MRI, const TargetInstrInfo *TII, MachineFunction &MF, LiveIntervals &LIS)
static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use, const MachineInstr *Insert, const WebAssemblyFunctionInfo &MFI, const MachineRegisterInfo &MRI)
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 ...
static void imposeStackOrdering(MachineInstr *MI)
static void query(const MachineInstr &MI, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
static void shrinkToUses(LiveInterval &LI, LiveIntervals &LIS)
static bool shouldRematerialize(const MachineInstr &Def, const WebAssemblyInstrInfo *TII)
static MachineInstr * moveAndTeeForMultiUse(unsigned Reg, MachineOperand &Op, MachineInstr *Def, MachineBasicBlock &MBB, MachineInstr *Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII)
A multiple-use def in the same block with no intervening memory or register dependencies; move the de...
static bool 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.
static void queryCallee(const MachineInstr &MI, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file contains the declaration of the WebAssembly-specific utility functions.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Represent the analysis usage information of a pass.
AnalysisUsage & addPreservedID(const void *ID)
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
This is an important base class in LLVM.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
FunctionPass class - This class is used to implement most global optimizations.
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
LiveInterval - This class represents the liveness of a register, or stack slot.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
SlotIndex InsertMachineInstrInMaps(MachineInstr &MI)
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void RemoveMachineInstrFromMaps(MachineInstr &MI)
LiveInterval & getInterval(Register Reg)
void removeInterval(Register Reg)
Interval removal.
bool shrinkToUses(LiveInterval *li, SmallVectorImpl< MachineInstr * > *dead=nullptr)
After removing some uses of a register, shrink its live range to just the remaining uses.
void removePhysRegDefAt(MCRegister Reg, SlotIndex Pos)
Remove value numbers and related live segments starting at position Pos that are part of any liverang...
void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl< LiveInterval * > &SplitLIs)
Split separate components in LiveInterval LI into separate intervals.
LiveInterval & createAndComputeVirtRegInterval(Register Reg)
bool liveAt(SlotIndex index) const
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none.
void removeSegment(SlotIndex Start, SlotIndex End, bool RemoveDeadValNo=false)
Remove the specified segment from this range.
VNInfo * getVNInfoAt(SlotIndex Idx) const
getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
static MCRegister from(unsigned Val)
Check the provided unsigned value is a valid MCRegister.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
reverse_iterator rbegin()
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 '...
MachineInstrBundleIterator< MachineInstr > iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
reverse_iterator getReverse() const
Get a reverse iterator to the same node.
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
iterator_range< mop_iterator > explicit_uses()
const MachineBasicBlock * getParent() const
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
iterator_range< mop_iterator > operands()
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
MachineOperand * mop_iterator
iterator/begin/end - Iterate over all operands of a machine instruction.
const MachineOperand & getOperand(unsigned i) const
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...
MachineOperand class - Representation of each machine instruction operand.
const GlobalValue * getGlobal() const
static MachineOperand CreateFPImm(const ConstantFP *CFP)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static MachineOperand CreateImm(int64_t Val)
bool isGlobal() const
isGlobal - Tests if this is a MO_GlobalAddress operand.
Register getReg() const
getReg - Returns the register number.
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)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Wrapper class representing virtual and physical registers.
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
SlotIndex - An opaque wrapper around machine indexes.
SlotIndex getDeadSlot() const
Returns the dead def kill slot for the current instruction.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
static const unsigned CommuteAnyOperandIndex
static Type * getDoubleTy(LLVMContext &C)
static Type * getFloatTy(LLVMContext &C)
A Use represents the edge between a Value definition and its users.
VNInfo - Value Number Information.
SlotIndex def
The index of the defining instruction.
iterator_range< use_iterator > uses()
void move(MachineInstr *Insert)
void updateReg(unsigned Reg)
void clone(MachineInstr *Insert, unsigned NewReg)
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
bool isVRegStackified(unsigned VReg) const
unsigned getFrameBaseVreg() const
void stackifyVReg(MachineRegisterInfo &MRI, unsigned VReg)
void clearFrameBaseVreg()
bool isFrameBaseVirtual() const
Iterator for intrusive lists based on ilist_node.
A range adaptor for a pair of iterators.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ Define
Register definition.
bool isArgument(unsigned Opc)
const MachineOperand & getCalleeOp(const MachineInstr &MI)
Returns the operand number of a callee, assuming the argument is a call instruction.
bool isCatch(unsigned Opc)
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
unsigned getUndefRegState(bool B)
char & LiveVariablesID
LiveVariables pass - This pass computes the set of blocks in which each variable is life and sets mac...
FunctionPass * createWebAssemblyRegStackify()