WebAssemblyRegStackify.cpp File Reference

This file implements a register stacking pass. More...

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblyDebugValueManager.h"
#include "WebAssemblyMachineFunctionInfo.h"
#include "WebAssemblySubtarget.h"
#include "WebAssemblyUtilities.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineModuleInfoImpls.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

Include dependency graph for WebAssemblyRegStackify.cpp:

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "wasm-reg-stackify"

Functions
	INITIALIZE_PASS (WebAssemblyRegStackify, DEBUG_TYPE, "Reorder instructions to use the WebAssembly value stack", false, false) FunctionPass *llvm
static void	ImposeStackOrdering (MachineInstr *MI)
static void	ConvertImplicitDefToConstZero (MachineInstr *MI, MachineRegisterInfo &MRI, const TargetInstrInfo *TII, MachineFunction &MF, LiveIntervals &LIS)
static void	QueryCallee (const MachineInstr &MI, unsigned CalleeOpNo, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
static void	Query (const MachineInstr &MI, AliasAnalysis &AA, bool &Read, bool &Write, bool &Effects, bool &StackPointer)
static bool	ShouldRematerialize (const MachineInstr &Def, AliasAnalysis &AA, const WebAssemblyInstrInfo *TII)
static MachineInstr *	GetVRegDef (unsigned Reg, const MachineInstr *Insert, const MachineRegisterInfo &MRI, const LiveIntervals &LIS)
static bool	HasOneUse (unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI, MachineDominatorTree &MDT, LiveIntervals &LIS)
static bool	IsSafeToMove (const MachineInstr *Def, const MachineInstr *Insert, AliasAnalysis &AA, const MachineRegisterInfo &MRI)
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. More...
static unsigned	GetTeeOpcode (const TargetRegisterClass *RC)
	Get the appropriate tee opcode for the given register class. More...
static void	ShrinkToUses (LiveInterval &LI, LiveIntervals &LIS)
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 down and nest it with the current instruction. More...
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. More...
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 def down, nest it with the current instruction, and insert a tee to satisfy the rest of the uses. More...

Detailed Description

This file implements a register stacking pass.

This pass reorders instructions to put register uses and defs in an order such that they form single-use expression trees. Registers fitting this form are then marked as "stackified", meaning references to them are replaced by "push" and "pop" from the value stack.

This is primarily a code size optimization, since temporary values on the value stack don't need to be named.

Definition in file WebAssemblyRegStackify.cpp.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "wasm-reg-stackify"

Definition at line 42 of file WebAssemblyRegStackify.cpp.

Function Documentation

ConvertImplicitDefToConstZero()

static void ConvertImplicitDefToConstZero ( MachineInstr *  MI, MachineRegisterInfo &  MRI, const TargetInstrInfo *  TII, MachineFunction &  MF, LiveIntervals &  LIS  )

static

Definition at line 99 of file WebAssemblyRegStackify.cpp.

References llvm::MachineInstr::addOperand(), assert(), llvm::BuildMI(), llvm::MachineOperand::CreateFPImm(), llvm::MachineOperand::CreateImm(), llvm::MachineOperand::CreateReg(), llvm::MachineRegisterInfo::createVirtualRegister(), llvm::MCInstrInfo::get(), llvm::Function::getContext(), llvm::MachineInstr::getDebugLoc(), llvm::Type::getDoubleTy(), llvm::Type::getFloatTy(), llvm::MachineFunction::getFunction(), llvm::Constant::getNullValue(), llvm::MachineInstr::getOpcode(), llvm::MachineInstr::getOperand(), llvm::MachineInstr::getParent(), llvm::MachineOperand::getReg(), llvm::MachineRegisterInfo::getRegClass(), llvm::LiveIntervals::InsertMachineInstrInMaps(), llvm_unreachable, MI, and llvm::MachineInstr::setDesc().

Referenced by MoveAndTeeForMultiUse().

GetTeeOpcode()

static unsigned GetTeeOpcode ( const TargetRegisterClass *  RC )

static

Get the appropriate tee opcode for the given register class.

Definition at line 448 of file WebAssemblyRegStackify.cpp.

References llvm_unreachable.

Referenced by MoveAndTeeForMultiUse().

GetVRegDef()

static MachineInstr* GetVRegDef ( unsigned  Reg, const MachineInstr *  Insert, const MachineRegisterInfo &  MRI, const LiveIntervals &  LIS  )

static

Definition at line 270 of file WebAssemblyRegStackify.cpp.

References llvm::tgtok::Def, llvm::LiveIntervals::getInstructionFromIndex(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::MachineRegisterInfo::getUniqueVRegDef(), and llvm::LiveRange::getVNInfoBefore().

Referenced by MoveAndTeeForMultiUse().

HasOneUse()

static bool HasOneUse ( unsigned  Reg, MachineInstr *  Def, MachineRegisterInfo &  MRI, MachineDominatorTree &  MDT, LiveIntervals &  LIS  )

static

Definition at line 288 of file WebAssemblyRegStackify.cpp.

References assert(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::SlotIndex::getRegSlot(), llvm::LiveRange::getVNInfoAt(), llvm::MachineRegisterInfo::hasOneUse(), I, llvm::LiveRange::Query(), and llvm::MachineRegisterInfo::use_nodbg_operands().

Referenced by MoveAndTeeForMultiUse().

ImposeStackOrdering()

static void ImposeStackOrdering ( MachineInstr *  MI )

static

Definition at line 83 of file WebAssemblyRegStackify.cpp.

References llvm::MachineInstr::addOperand(), llvm::MachineOperand::CreateReg(), llvm::MachineInstr::definesRegister(), and llvm::MachineInstr::readsRegister().

Referenced by MoveAndTeeForMultiUse(), MoveForSingleUse(), and RematerializeCheapDef().

INITIALIZE_PASS()

INITIALIZE_PASS	(	WebAssemblyRegStackify	,
		DEBUG_TYPE	,
		"Reorder instructions to use the WebAssembly value stack"	,
		false	,
		false
	)

Definition at line 72 of file WebAssemblyRegStackify.cpp.

IsSafeToMove()

static bool IsSafeToMove ( const MachineInstr *  Def, const MachineInstr *  Insert, AliasAnalysis &  AA, const MachineRegisterInfo &  MRI  )

static

Definition at line 317 of file WebAssemblyRegStackify.cpp.

References assert(), D, llvm::MachineInstr::definesRegister(), llvm::MachineInstr::getParent(), llvm::MachineRegisterInfo::hasOneDef(), I, llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::MachineRegisterInfo::isPhysRegModified(), llvm::MachineInstr::operands(), Query(), llvm::MachineInstr::readsRegister(), and Reg.

Referenced by MoveAndTeeForMultiUse().

MoveAndTeeForMultiUse()

static MachineInstr* MoveAndTeeForMultiUse ( unsigned  Reg, MachineOperand &  Op, MachineInstr *  Def, MachineBasicBlock &  MBB, MachineInstr *  Insert, LiveIntervals &  LIS, WebAssemblyFunctionInfo &  MFI, MachineRegisterInfo &  MRI, const WebAssemblyInstrInfo *  TII  )

static

A multiple-use def in the same block with no intervening memory or register dependencies; move the def down, nest it with the current instruction, and insert a tee to satisfy the rest of the uses.

As an illustration, rewrite this:

Reg = INST ... // Def INST ..., Reg, ... // Insert INST ..., Reg, ... INST ..., Reg, ...

to this:

DefReg = INST ... // Def (to become the new Insert) TeeReg, Reg = TEE_... DefReg INST ..., TeeReg, ... // Insert INST ..., Reg, ... INST ..., Reg, ...

with DefReg and TeeReg stackified. This eliminates a local.get from the resulting code.

Definition at line 585 of file WebAssemblyRegStackify.cpp.

References llvm::MachineInstrBuilder::addReg(), assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::iterator_range< IteratorT >::begin(), llvm::BuildMI(), llvm::TargetInstrInfo::CommuteAnyOperandIndex, ConvertImplicitDefToConstZero(), llvm::LiveIntervals::createAndComputeVirtRegInterval(), llvm::MachineRegisterInfo::createVirtualRegister(), llvm::dbgs(), llvm::tgtok::Def, llvm::VNInfo::def, llvm::RegState::Define, llvm::drop_begin(), llvm::MachineInstr::dump(), llvm::SmallVectorBase::empty(), llvm::iterator_range< IteratorT >::end(), llvm::MachineInstr::explicit_uses(), llvm::LiveRange::FindSegmentContaining(), llvm::MachineInstr::getDebugLoc(), llvm::MachineFunction::getInfo(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MachineFunction::getName(), llvm::MachineInstr::getOpcode(), llvm::MachineInstr::getOperand(), llvm::MachineInstr::getParent(), llvm::MachineOperand::getReg(), llvm::MachineRegisterInfo::getRegClass(), llvm::MachineFunction::getRegInfo(), llvm::SlotIndex::getRegSlot(), llvm::MachineInstrBundleIterator< Ty, IsReverse >::getReverse(), llvm::MachineFunction::getSubtarget(), GetTeeOpcode(), llvm::getUndefRegState(), llvm::LiveRange::getVNInfoAt(), GetVRegDef(), llvm::LiveIntervals::handleMove(), HasOneUse(), I, ImposeStackOrdering(), llvm::ISD::INLINEASM, llvm::LiveIntervals::InsertMachineInstrInMaps(), llvm::WebAssembly::isArgument(), llvm::MachineOperand::isDead(), llvm::MachineOperand::isImplicit(), llvm::TargetRegisterInfo::isPhysicalRegister(), llvm::MachineOperand::isReg(), IsSafeToMove(), llvm::MachineOperand::isUse(), llvm::WebAssemblyFunctionInfo::isVRegStackified(), LLVM_DEBUG, MI, MoveForSingleUse(), MRI, OneUseDominatesOtherUses(), llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), Reg, RematerializeCheapDef(), llvm::reverse(), llvm::MachineOperand::setReg(), ShouldRematerialize(), ShrinkToUses(), llvm::MachineBasicBlock::splice(), llvm::WebAssemblyFunctionInfo::stackifyVReg(), TII, and TRI.

MoveForSingleUse()

static MachineInstr* MoveForSingleUse ( unsigned  Reg, MachineOperand &  Op, MachineInstr *  Def, MachineBasicBlock &  MBB, MachineInstr *  Insert, LiveIntervals &  LIS, WebAssemblyFunctionInfo &  MFI, MachineRegisterInfo &  MRI  )

static

A single-use def in the same block with no intervening memory or register dependencies; move the def down and nest it with the current instruction.

Definition at line 472 of file WebAssemblyRegStackify.cpp.

References llvm::LiveIntervals::createAndComputeVirtRegInterval(), llvm::MachineRegisterInfo::createVirtualRegister(), llvm::dbgs(), llvm::tgtok::Def, llvm::MachineInstr::dump(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getParent(), llvm::MachineRegisterInfo::getRegClass(), llvm::SlotIndex::getRegSlot(), llvm::LiveIntervals::handleMove(), llvm::MachineRegisterInfo::hasOneDef(), llvm::MachineRegisterInfo::hasOneUse(), ImposeStackOrdering(), LLVM_DEBUG, llvm::LiveRange::removeSegment(), llvm::MachineOperand::setReg(), llvm::MachineBasicBlock::splice(), and llvm::WebAssemblyFunctionInfo::stackifyVReg().

Referenced by MoveAndTeeForMultiUse().

OneUseDominatesOtherUses()

static bool OneUseDominatesOtherUses ( unsigned  Reg, const MachineOperand &  OneUse, const MachineBasicBlock &  MBB, const MachineRegisterInfo &  MRI, const MachineDominatorTree &  MDT, LiveIntervals &  LIS, WebAssemblyFunctionInfo &  MFI  )

static

Test whether OneUse, a use of Reg, dominates all of Reg's other uses.

Definition at line 389 of file WebAssemblyRegStackify.cpp.

References assert(), llvm::MachineDominatorTree::dominates(), llvm::MachineInstr::getDesc(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::MCInstrDesc::getNumDefs(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getParent(), llvm::MachineInstr::getParent(), llvm::MachineOperand::getReg(), llvm::LiveRange::getVNInfoBefore(), llvm::MachineRegisterInfo::hasOneNonDBGUse(), llvm::MachineOperand::isReg(), llvm::TargetRegisterInfo::isVirtualRegister(), llvm::WebAssemblyFunctionInfo::isVRegStackified(), llvm::MachineRegisterInfo::use_nodbg_begin(), and llvm::MachineRegisterInfo::use_nodbg_operands().

Referenced by MoveAndTeeForMultiUse().

Query()

static void Query ( const MachineInstr &  MI, AliasAnalysis &  AA, bool &  Read, bool &  Write, bool &  Effects, bool &  StackPointer  )

static

Definition at line 171 of file WebAssemblyRegStackify.cpp.

References assert(), llvm::WebAssembly::getCalleeOpNo(), llvm::MachineInstr::getOpcode(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getSymbolName(), llvm::MachineInstr::hasOrderedMemoryRef(), llvm::MachineInstr::hasUnmodeledSideEffects(), llvm::MachineInstr::isCall(), llvm::MachineInstr::isDebugInstr(), llvm::MachineInstr::isDereferenceableInvariantLoad(), llvm::MachineInstr::isPosition(), llvm::MachineInstr::isTerminator(), llvm::MachineInstr::mayLoad(), llvm::MachineInstr::mayStore(), and QueryCallee().

Referenced by llvm::AArch64LegalizerInfo::AArch64LegalizerInfo(), llvm::LegalityPredicates::all(), llvm::AMDGPULegalizerInfo::AMDGPULegalizerInfo(), llvm::LegalityPredicates::atomicOrderingAtLeastOrStrongerThan(), llvm::LegalizeMutations::changeTo(), llvm::LegalizeRuleSet::clampMaxNumElements(), llvm::LegalizeRuleSet::clampMinNumElements(), llvm::computeKnownBits(), computeKnownBitsFromAssume(), llvm::ComputeNumSignBits(), computeNumSignBitsVectorConstant(), llvm::LegalizeRuleSet::fallback(), getBitWidth(), llvm::isKnownNegative(), llvm::isKnownNonEqual(), llvm::isKnownNonZero(), llvm::isKnownToBeAPowerOfTwo(), llvm::isOnlyUsedInZeroEqualityComparison(), IsSafeToMove(), llvm::LegalityPredicates::isScalar(), llvm::orc::LambdaSymbolResolver< GetResponsibilitySetFn, LookupFn >::lookup(), llvm::orc::LegacyLookupFnResolver< LegacyLookupFn >::lookup(), llvm::MaskedValueIsZero(), llvm::LegalizeRuleSet::maxScalarIf(), llvm::LegalityPredicates::memSizeInBytesNotPow2(), llvm::LegalizeRuleSet::minScalarSameAs(), llvm::LegalizeMutations::moreElementsToNextPow2(), llvm::LegalizerInfo::moreToWiderTypesAndLessToWidest(), llvm::LegalityPredicates::narrowerThan(), llvm::LegalityPredicates::numElementsNotPow2(), safeCxtI(), llvm::LegalityPredicates::sizeNotPow2(), llvm::LegalizationArtifactCombiner::tryCombineInstruction(), llvm::LegalityPredicates::typeInSet(), llvm::LegalityPredicates::typeIs(), llvm::LegalityPredicates::typePairAndMemSizeInSet(), llvm::LegalityPredicates::typePairInSet(), llvm::LegalizeMutations::widenScalarToNextPow2(), and llvm::LegalityPredicates::widerThan().

QueryCallee()

static void QueryCallee ( const MachineInstr &  MI, unsigned  CalleeOpNo, bool &  Read, bool &  Write, bool &  Effects, bool &  StackPointer  )

static

Definition at line 139 of file WebAssemblyRegStackify.cpp.

References F(), llvm::MachineOperand::getGlobal(), llvm::MachineInstr::getOperand(), and llvm::MachineOperand::isGlobal().

Referenced by Query().

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  )

static

A trivially cloneable instruction; clone it and nest the new copy with the current instruction.

Definition at line 517 of file WebAssemblyRegStackify.cpp.

References llvm::LiveIntervals::createAndComputeVirtRegInterval(), llvm::MachineRegisterInfo::createVirtualRegister(), llvm::dbgs(), llvm::MachineInstr::dump(), llvm::MachineInstr::eraseFromParent(), llvm::SlotIndex::getDeadSlot(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::MachineOperand::getParent(), llvm::MachineRegisterInfo::getRegClass(), llvm::SlotIndex::getRegSlot(), ImposeStackOrdering(), llvm::LiveIntervals::InsertMachineInstrInMaps(), IsDead, llvm::LiveRange::liveAt(), LLVM_DEBUG, llvm::LiveIntervals::removeInterval(), llvm::LiveIntervals::RemoveMachineInstrFromMaps(), llvm::LiveIntervals::removePhysRegDefAt(), llvm::MachineOperand::setReg(), ShrinkToUses(), llvm::WebAssemblyFunctionInfo::stackifyVReg(), and llvm::MachineRegisterInfo::use_empty().

Referenced by MoveAndTeeForMultiUse().

ShouldRematerialize()

static bool ShouldRematerialize ( const MachineInstr &  Def, AliasAnalysis &  AA, const WebAssemblyInstrInfo *  TII  )

static

Definition at line 262 of file WebAssemblyRegStackify.cpp.

References llvm::MachineInstr::isAsCheapAsAMove().

Referenced by MoveAndTeeForMultiUse().

ShrinkToUses()

static void ShrinkToUses ( LiveInterval &  LI, LiveIntervals &  LIS  )

static

Definition at line 463 of file WebAssemblyRegStackify.cpp.

References llvm::LiveIntervals::shrinkToUses(), and llvm::LiveIntervals::splitSeparateComponents().

Referenced by MoveAndTeeForMultiUse(), and RematerializeCheapDef().