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/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/IR/GlobalAlias.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <iterator>

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, bool &Read, bool &Write, bool &Effects, bool &StackPointer)

static void	query (const MachineInstr &MI, bool &Read, bool &Write, bool &Effects, bool &StackPointer)

static bool	shouldRematerialize (const MachineInstr &Def, const WebAssemblyInstrInfo *TII)

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

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

static bool	isSafeToMove (const MachineOperand Def, const MachineOperand Use, const MachineInstr *Insert, const WebAssemblyFunctionInfo &MFI, 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.

static unsigned	getTeeOpcode (const TargetRegisterClass *RC)
	Get the appropriate tee opcode for the given register class.

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.

static MachineInstr *	getPrevNonDebugInst (MachineInstr *MI)

static MachineInstr *	rematerializeCheapDef (unsigned Reg, MachineOperand &Op, MachineInstr &Def, MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo TII, const WebAssemblyRegisterInfo TRI)
	A trivially cloneable instruction; clone it and nest the new copy with the current instruction.

static MachineInstr *	moveAndTeeForMultiUse (unsigned Reg, MachineOperand &Op, MachineInstr Def, MachineBasicBlock &MBB, MachineInstr Insert, LiveIntervals &LIS, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI, const WebAssemblyInstrInfo *TII)
	A multiple-use def in the same block with no intervening memory or register dependencies; move the def down, nest it with the current instruction, and insert a tee to satisfy the rest of the uses.

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 98 of file WebAssemblyRegStackify.cpp.

References assert(), llvm::MachineOperand::CreateFPImm(), llvm::MachineOperand::CreateImm(), llvm::Function::getContext(), llvm::Type::getDoubleTy(), llvm::Type::getFloatTy(), llvm::MachineFunction::getFunction(), llvm::Constant::getNullValue(), llvm_unreachable, MI, MRI, and TII.

◆ getPrevNonDebugInst()

static MachineInstr * getPrevNonDebugInst ( MachineInstr * MI )

static

Definition at line 563 of file WebAssemblyRegStackify.cpp.

References I, and MI.

Referenced by rematerializeCheapDef().

◆ getTeeOpcode()

static unsigned getTeeOpcode ( const TargetRegisterClass * RC )

static

Get the appropriate tee opcode for the given register class.

Definition at line 493 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 265 of file WebAssemblyRegStackify.cpp.

References llvm::LiveIntervals::getInstructionFromIndex(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::LiveRange::getVNInfoBefore(), and MRI.

◆ hasOneNonDBGUse()

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

static

Definition at line 283 of file WebAssemblyRegStackify.cpp.

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

◆ imposeStackOrdering()

static void imposeStackOrdering ( MachineInstr * MI )

static

Definition at line 82 of file WebAssemblyRegStackify.cpp.

References llvm::MachineOperand::CreateReg(), and MI.

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 71 of file WebAssemblyRegStackify.cpp.

◆ isSafeToMove()

static bool isSafeToMove	(	const MachineOperand *	Def,
		const MachineOperand *	Use,
		const MachineInstr *	Insert,
		const WebAssemblyFunctionInfo &	MFI,
		const MachineRegisterInfo &	MRI
	)

static

Definition at line 313 of file WebAssemblyRegStackify.cpp.

References assert(), D, llvm::MachineInstr::defs(), llvm::drop_begin(), llvm::SmallVectorBase< Size_T >::empty(), llvm::MachineBasicBlock::end(), llvm::MachineInstr::getOpcode(), llvm::MachineInstr::getParent(), I, llvm::WebAssembly::isCatch(), MBB, MRI, llvm::MachineInstr::operands(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), query(), llvm::Read, and llvm::Write.

◆ 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 635 of file WebAssemblyRegStackify.cpp.

References llvm::MachineInstrBuilder::addReg(), llvm::BuildMI(), llvm::WebAssemblyDebugValueManager::cloneSink(), llvm::LiveIntervals::createAndComputeVirtRegInterval(), llvm::dbgs(), llvm::VNInfo::def, llvm::RegState::Define, llvm::MachineInstr::dump(), llvm::LiveRange::FindSegmentContaining(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::SlotIndex::getRegSlot(), getTeeOpcode(), llvm::getUndefRegState(), llvm::LiveRange::getVNInfoAt(), llvm::LiveIntervals::handleMove(), I, imposeStackOrdering(), llvm::LiveIntervals::InsertMachineInstrInMaps(), llvm::MachineOperand::isDead(), LLVM_DEBUG, MBB, MRI, shrinkToUses(), llvm::WebAssemblyDebugValueManager::sink(), llvm::WebAssemblyFunctionInfo::stackifyVReg(), TII, and llvm::WebAssemblyDebugValueManager::updateReg().

◆ 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 523 of file WebAssemblyRegStackify.cpp.

References llvm::LiveIntervals::createAndComputeVirtRegInterval(), llvm::dbgs(), llvm::LiveIntervals::getInstructionIndex(), llvm::LiveIntervals::getInterval(), llvm::SlotIndex::getRegSlot(), llvm::LiveIntervals::handleMove(), imposeStackOrdering(), LLVM_DEBUG, MRI, llvm::LiveRange::removeSegment(), llvm::WebAssemblyDebugValueManager::sink(), llvm::WebAssemblyFunctionInfo::stackifyVReg(), and llvm::WebAssemblyDebugValueManager::updateReg().

◆ 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 435 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::MachineOperand::getReg(), llvm::LiveRange::getVNInfoBefore(), llvm::MachineOperand::isReg(), llvm::Register::isVirtual(), llvm::WebAssemblyFunctionInfo::isVRegStackified(), and MRI.

◆ query()

static void query	(	const MachineInstr &	MI,
		bool &	Read,
		bool &	Write,
		bool &	Effects,
		bool &	StackPointer
	)

static

Definition at line 166 of file WebAssemblyRegStackify.cpp.

References assert(), MI, queryCallee(), llvm::Read, and llvm::Write.

Referenced by isSafeToMove().

◆ queryCallee()

static void queryCallee	(	const MachineInstr &	MI,
		bool &	Read,
		bool &	Write,
		bool &	Effects,
		bool &	StackPointer
	)

static

Definition at line 134 of file WebAssemblyRegStackify.cpp.

References F, llvm::WebAssembly::getCalleeOp(), llvm::MachineOperand::getGlobal(), llvm::MachineOperand::isGlobal(), MI, llvm::Read, and llvm::Write.

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
	)