MachinePipeliner.cpp File Reference (original) (raw)

Go to the source code of this file.

Namespaces
namespace	false

Macros
#define	DEBUG_TYPE "pipeliner"

Functions
	STATISTIC (NumTrytoPipeline, "Number of loops that we attempt to pipeline")
	STATISTIC (NumPipelined, "Number of loops software pipelined")
	STATISTIC (NumNodeOrderIssues, "Number of node order issues found")
	STATISTIC (NumFailBranch, "Pipeliner abort due to unknown branch")
	STATISTIC (NumFailLoop, "Pipeliner abort due to unsupported loop")
	STATISTIC (NumFailPreheader, "Pipeliner abort due to missing preheader")
	STATISTIC (NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large")
	STATISTIC (NumFailZeroMII, "Pipeliner abort due to zero MII")
	STATISTIC (NumFailNoSchedule, "Pipeliner abort due to no schedule found")
	STATISTIC (NumFailZeroStage, "Pipeliner abort due to zero stage")
	STATISTIC (NumFailLargeMaxStage, "Pipeliner abort due to too many stages")
	STATISTIC (NumFailTooManyStores, "Pipeliner abort due to too many stores")
	INITIALIZE_PASS_BEGIN (MachinePipeliner, DEBUG_TYPE, "Modulo Software Pipelining", false, false) INITIALIZE_PASS_END(MachinePipeliner
static bool	hasPHICycleDFS (unsigned Reg, const DenseMap< unsigned, SmallVector< unsigned, 2 > > &PhiDeps, SmallSet< unsigned, 8 > &Visited, SmallSet< unsigned, 8 > &RecStack)
	Depth-first search to detect cycles among PHI dependencies.
static bool	hasPHICycle (const MachineBasicBlock *LoopHeader, const MachineRegisterInfo &MRI)
static void	getPhiRegs (MachineInstr &Phi, MachineBasicBlock *Loop, Register &InitVal, Register &LoopVal)
	Return the register values for the operands of a Phi instruction.
static Register	getLoopPhiReg (const MachineInstr &Phi, const MachineBasicBlock *LoopBB)
	Return the Phi register value that comes the loop block.
static bool	isSuccOrder (SUnit SUa, SUnit SUb)
	Return true if SUb can be reached from SUa following the chain edges.
static bool	hasLoopCarriedMemDep (const SUnitWithMemInfo &Src, const SUnitWithMemInfo &Dst, BatchAAResults &BAA, const TargetInstrInfo TII, const TargetRegisterInfo TRI, const SwingSchedulerDAG *SSD, bool PerformCheapCheck)
	Returns true if there is a loop-carried order dependency from Src to Dst.
static void	computeScheduledInsts (const SwingSchedulerDAG SSD, SMSchedule &Schedule, std::vector< MachineInstr > &OrderedInsts, DenseMap< MachineInstr *, unsigned > &Stages)
	Create an instruction stream that represents a single iteration and stage of each instruction.
static bool	pred_L (SetVector< SUnit * > &NodeOrder, SmallSetVector< SUnit , 8 > &Preds, SwingSchedulerDDG DDG, const NodeSet *S=nullptr)
	Compute the Pred_L(O) set, as defined in the paper.
static bool	succ_L (SetVector< SUnit * > &NodeOrder, SmallSetVector< SUnit , 8 > &Succs, SwingSchedulerDDG DDG, const NodeSet *S=nullptr)
	Compute the Succ_L(O) set, as defined in the paper.
static bool	computePath (SUnit Cur, SetVector< SUnit > &Path, SetVector< SUnit * > &DestNodes, SetVector< SUnit * > &Exclude, SmallPtrSet< SUnit , 8 > &Visited, SwingSchedulerDDG DDG)
	Return true if there is a path from the specified node to any of the nodes in DestNodes.
static void	computeLiveOuts (MachineFunction &MF, RegPressureTracker &RPTracker, NodeSet &NS)
	Compute the live-out registers for the instructions in a node-set.
static bool	isIntersect (SmallSetVector< SUnit , 8 > &Set1, const NodeSet &Set2, SmallSetVector< SUnit , 8 > &Result)
	Return true if Set1 contains elements in Set2.
static Register	findUniqueOperandDefinedInLoop (const MachineInstr &MI)
static bool	findLoopIncrementValue (const MachineOperand &Op, int &Value)
	When Op is a value that is incremented recursively in a loop and there is a unique instruction that increments it, returns true and sets Value.
static SUnit *	multipleIterations (SUnit SU, SwingSchedulerDAG DAG)
	If an instruction has a use that spans multiple iterations, then return true.

Variables
static cl::opt< bool >	EnableSWP ("enable-pipeliner", cl::Hidden, cl::init(true), cl::desc("Enable Software Pipelining"))
	A command line option to turn software pipelining on or off.
static cl::opt< bool >	EnableSWPOptSize ("enable-pipeliner-opt-size", cl::desc("Enable SWP at Os."), cl::Hidden, cl::init(false))
	A command line option to enable SWP at -Os.
static cl::opt< int >	SwpMaxMii ("pipeliner-max-mii", cl::desc("Size limit for the MII."), cl::Hidden, cl::init(27))
	A command line argument to limit minimum initial interval for pipelining.
static cl::opt< int >	SwpForceII ("pipeliner-force-ii", cl::desc("Force pipeliner to use specified II."), cl::Hidden, cl::init(-1))
	A command line argument to force pipeliner to use specified initial interval.
static cl::opt< int >	SwpMaxStages ("pipeliner-max-stages", cl::desc("Maximum stages allowed in the generated scheduled."), cl::Hidden, cl::init(3))
	A command line argument to limit the number of stages in the pipeline.
static cl::opt< bool >	SwpPruneDeps ("pipeliner-prune-deps", cl::desc("Prune dependences between unrelated Phi nodes."), cl::Hidden, cl::init(true))
	A command line option to disable the pruning of chain dependences due to an unrelated Phi.
static cl::opt< bool >	SwpPruneLoopCarried ("pipeliner-prune-loop-carried", cl::desc("Prune loop carried order dependences."), cl::Hidden, cl::init(true))
	A command line option to disable the pruning of loop carried order dependences.
static cl::opt< int >	SwpLoopLimit ("pipeliner-max", cl::Hidden, cl::init(-1))
static cl::opt< bool >	SwpIgnoreRecMII ("pipeliner-ignore-recmii", cl::ReallyHidden, cl::desc("Ignore RecMII"))
static cl::opt< bool >	SwpShowResMask ("pipeliner-show-mask", cl::Hidden, cl::init(false))
static cl::opt< bool >	SwpDebugResource ("pipeliner-dbg-res", cl::Hidden, cl::init(false))
static cl::opt< bool >	EmitTestAnnotations ("pipeliner-annotate-for-testing", cl::Hidden, cl::init(false), cl::desc("Instead of emitting the pipelined code, annotate instructions " "with the generated schedule for feeding into the " "-modulo-schedule-test pass"))
static cl::opt< bool >	ExperimentalCodeGen ("pipeliner-experimental-cg", cl::Hidden, cl::init(false), cl::desc("Use the experimental peeling code generator for software pipelining"))
static cl::opt< int >	SwpIISearchRange ("pipeliner-ii-search-range", cl::desc("Range to search for II"), cl::Hidden, cl::init(10))
static cl::opt< bool >	LimitRegPressure ("pipeliner-register-pressure", cl::Hidden, cl::init(false), cl::desc("Limit register pressure of scheduled loop"))
static cl::opt< int >	RegPressureMargin ("pipeliner-register-pressure-margin", cl::Hidden, cl::init(5), cl::desc("Margin representing the unused percentage of " "the register pressure limit"))
static cl::opt< bool >	MVECodeGen ("pipeliner-mve-cg", cl::Hidden, cl::init(false), cl::desc("Use the MVE code generator for software pipelining"))
static cl::opt< unsigned >	SwpMaxNumStores ("pipeliner-max-num-stores", cl::desc("Maximum number of stores allwed in the target loop."), cl::Hidden, cl::init(200))
	A command line argument to limit the number of store instructions in the target basic block.
static cl::opt< WindowSchedulingFlag >	WindowSchedulingOption ("window-sched", cl::Hidden, cl::init(WindowSchedulingFlag::WS_On), cl::desc("Set how to use window scheduling algorithm."), cl::values(clEnumValN(WindowSchedulingFlag::WS_Off, "off", "Turn off window algorithm."), clEnumValN(WindowSchedulingFlag::WS_On, "on", "Use window algorithm after SMS algorithm fails."), clEnumValN(WindowSchedulingFlag::WS_Force, "force", "Use window algorithm instead of SMS algorithm.")))
	A command line argument to set the window scheduling option.
	DEBUG_TYPE
Modulo Software	Pipelining
Modulo Software	false

◆ DEBUG_TYPE

#define DEBUG_TYPE "pipeliner"

◆ computeLiveOuts()

Compute the live-out registers for the instructions in a node-set.

The live-out registers are those that are defined in the node-set, but not used. Except for use operands of Phis.

Definition at line 2331 of file MachinePipeliner.cpp.

References llvm::RegPressureTracker::addLiveRegs(), llvm::MachineInstr::all_defs(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::SUnit::getInstr(), llvm::LaneBitmask::getNone(), llvm::MachineFunction::getRegInfo(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), MI, MRI, Reg, TRI, and Uses.

◆ computePath()

◆ computeScheduledInsts()

Create an instruction stream that represents a single iteration and stage of each instruction.

This function differs from SMSchedule::finalizeSchedule in that this doesn't have any side-effect to SwingSchedulerDAG. That is, this function is an approximation of SMSchedule::finalizeSchedule with all non-const operations removed.

Definition at line 1405 of file MachinePipeliner.cpp.

References llvm::SMSchedule::getFinalCycle(), llvm::SMSchedule::getFirstCycle(), llvm::SMSchedule::getInitiationInterval(), llvm::SUnit::getInstr(), llvm::SMSchedule::getInstructions(), llvm::SMSchedule::getMaxStageCount(), MI, llvm::SMSchedule::reorderInstructions(), llvm::reverse(), and llvm::SMSchedule::stageScheduled().

◆ findLoopIncrementValue()

When Op is a value that is incremented recursively in a loop and there is a unique instruction that increments it, returns true and sets Value.

Definition at line 2900 of file MachinePipeliner.cpp.

References findUniqueOperandDefinedInLoop(), llvm::TargetSubtargetInfo::getInstrInfo(), getLoopPhiReg(), llvm::MachineBasicBlock::getParent(), llvm::MachineOperand::getReg(), llvm::MachineFunction::getRegInfo(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), llvm::Increment, llvm::Register::isValid(), llvm::Register::isVirtual(), MRI, llvm::Offset, TII, and TRI.

◆ findUniqueOperandDefinedInLoop()

◆ getLoopPhiReg()

◆ getPhiRegs()

◆ hasLoopCarriedMemDep()

◆ hasPHICycle()

Definition at line 516 of file MachinePipeliner.cpp.

References hasPHICycleDFS(), I, MI, MRI, llvm::MachineBasicBlock::phis(), Reg, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

◆ hasPHICycleDFS()

Depth-first search to detect cycles among PHI dependencies.

Returns true if a cycle is detected within the PHI-only subgraph.

Definition at line 490 of file MachinePipeliner.cpp.

References llvm::SmallSet< T, N, C >::count(), llvm::SmallSet< T, N, C >::erase(), hasPHICycleDFS(), llvm::SmallSet< T, N, C >::insert(), and Reg.

Referenced by hasPHICycle(), and hasPHICycleDFS().

◆ INITIALIZE_PASS_BEGIN()

◆ isIntersect()

◆ isSuccOrder()

◆ multipleIterations()

◆ pred_L()

Compute the Pred_L(O) set, as defined in the paper.

The set is defined as the predecessors of the elements of NodeOrder that are not also in NodeOrder.

Definition at line 2230 of file MachinePipeliner.cpp.

References llvm::SetVector< T, Vector, Set, N >::clear(), llvm::SetVector< T, Vector, Set, N >::empty(), llvm::SwingSchedulerDDG::getInEdges(), llvm::SwingSchedulerDDG::getOutEdges(), llvm::SetVector< T, Vector, Set, N >::insert(), and llvm::NodeOrder.

◆ STATISTIC() [1/12]

STATISTIC	(	NumFailBranch	,
"Pipeliner abort due to unknown branch"	)

◆ STATISTIC() [2/12]

STATISTIC	(	NumFailLargeMaxMII	,
"Pipeliner abort due to MaxMII too large"	)

◆ STATISTIC() [3/12]

STATISTIC	(	NumFailLargeMaxStage	,
"Pipeliner abort due to too many stages"	)

◆ STATISTIC() [4/12]

STATISTIC	(	NumFailLoop	,
"Pipeliner abort due to unsupported loop"	)

◆ STATISTIC() [5/12]

STATISTIC	(	NumFailNoSchedule	,
"Pipeliner abort due to no schedule found"	)

◆ STATISTIC() [6/12]

STATISTIC	(	NumFailPreheader	,
"Pipeliner abort due to missing preheader"	)

◆ STATISTIC() [7/12]

STATISTIC	(	NumFailTooManyStores	,
"Pipeliner abort due to too many stores"	)

◆ STATISTIC() [8/12]

STATISTIC	(	NumFailZeroMII	,
"Pipeliner abort due to zero MII"	)

◆ STATISTIC() [9/12]

STATISTIC	(	NumFailZeroStage	,
"Pipeliner abort due to zero stage"	)

◆ STATISTIC() [10/12]

STATISTIC	(	NumNodeOrderIssues	,
"Number of node order issues found"	)

◆ STATISTIC() [11/12]

STATISTIC	(	NumPipelined	,
"Number of loops software pipelined"	)

◆ STATISTIC() [12/12]

STATISTIC	(	NumTrytoPipeline	,
"Number of loops that we attempt to pipeline"	)

◆ succ_L()

Compute the Succ_L(O) set, as defined in the paper.

The set is defined as the successors of the elements of NodeOrder that are not also in NodeOrder.

Definition at line 2266 of file MachinePipeliner.cpp.

◆ DEBUG_TYPE

◆ EmitTestAnnotations

cl::opt< bool > EmitTestAnnotations("pipeliner-annotate-for-testing", cl::Hidden, cl::init(false), cl::desc("Instead of emitting the pipelined code, annotate instructions " "with the generated schedule for feeding into the " "-modulo-schedule-test pass")) ( "pipeliner-annotate-for-testing" , cl::Hidden , cl::init(false) , cl::desc("Instead of emitting the pipelined code, annotate instructions " "with the generated schedule for feeding into the " "-modulo-schedule-test pass") )

static

◆ EnableSWP

cl::opt< bool > EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true), cl::desc("Enable Software Pipelining")) ( "enable-pipeliner" , cl::Hidden , cl::init(true) , cl::desc("Enable Software Pipelining") )	static

◆ EnableSWPOptSize

cl::opt< bool > EnableSWPOptSize("enable-pipeliner-opt-size", cl::desc("Enable SWP at Os."), cl::Hidden, cl::init(false)) ( "enable-pipeliner-opt-size" , cl::desc("Enable SWP at Os.") , cl::Hidden , cl::init(false) )	static

◆ ExperimentalCodeGen

cl::opt< bool > ExperimentalCodeGen("pipeliner-experimental-cg", cl::Hidden, cl::init(false), cl::desc( "Use the experimental peeling code generator for software pipelining")) ( "pipeliner-experimental-cg" , cl::Hidden , cl::init(false) , cl::desc( "Use the experimental peeling code generator for software pipelining") )	static

◆ false

◆ LimitRegPressure

cl::opt< bool > LimitRegPressure("pipeliner-register-pressure", cl::Hidden, cl::init(false), cl::desc("Limit register pressure of scheduled loop")) ( "pipeliner-register-pressure" , cl::Hidden , cl::init(false) , cl::desc("Limit register pressure of scheduled loop") )	static

◆ MVECodeGen

cl::opt< bool > MVECodeGen("pipeliner-mve-cg", cl::Hidden, cl::init(false), cl::desc("Use the MVE code generator for software pipelining")) ( "pipeliner-mve-cg" , cl::Hidden , cl::init(false) , cl::desc("Use the MVE code generator for software pipelining") )	static

◆ Pipelining

Modulo Software Pipelining

◆ RegPressureMargin

cl::opt< int > RegPressureMargin("pipeliner-register-pressure-margin", cl::Hidden, cl::init(5), cl::desc("Margin representing the unused percentage of " "the register pressure limit")) ( "pipeliner-register-pressure-margin" , cl::Hidden , cl::init(5) , cl::desc("Margin representing the unused percentage of " "the register pressure limit") )	static

◆ SwpDebugResource

cl::opt< bool > SwpDebugResource("pipeliner-dbg-res", cl::Hidden, cl::init(false)) ( "pipeliner-dbg-res" , cl::Hidden , cl::init(false) )	static

◆ SwpForceII

cl::opt< int > SwpForceII("pipeliner-force-ii", cl::desc("Force pipeliner to use specified II."), cl::Hidden, cl::init(-1)) ( "pipeliner-force-ii" , cl::desc("Force pipeliner to use specified II.") , cl::Hidden , cl::init(-1) )	static

A command line argument to force pipeliner to use specified initial interval.

◆ SwpIgnoreRecMII

cl::opt< bool > SwpIgnoreRecMII("pipeliner-ignore-recmii", cl::ReallyHidden, cl::desc("Ignore RecMII")) ( "pipeliner-ignore-recmii" , cl::ReallyHidden , cl::desc("Ignore RecMII") )	static

◆ SwpIISearchRange

cl::opt< int > SwpIISearchRange("pipeliner-ii-search-range", cl::desc("Range to search for II"), cl::Hidden, cl::init(10)) ( "pipeliner-ii-search-range" , cl::desc("Range to search for II") , cl::Hidden , cl::init(10) )	static

◆ SwpLoopLimit

cl::opt< int > SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1)) ( "pipeliner-max" , cl::Hidden , cl::init(-1) )	static

◆ SwpMaxMii

cl::opt< int > SwpMaxMii("pipeliner-max-mii", cl::desc("Size limit for the MII."), cl::Hidden, cl::init(27)) ( "pipeliner-max-mii" , cl::desc("Size limit for the MII.") , cl::Hidden , cl::init(27) )	static

◆ SwpMaxNumStores

cl::opt< unsigned > SwpMaxNumStores("pipeliner-max-num-stores", cl::desc("Maximum number of stores allwed in the target loop."), cl::Hidden, cl::init(200)) ( "pipeliner-max-num-stores" , cl::desc("Maximum number of stores allwed in the target loop.") , cl::Hidden , cl::init(200) )	static

A command line argument to limit the number of store instructions in the target basic block.

◆ SwpMaxStages

cl::opt< int > SwpMaxStages("pipeliner-max-stages", cl::desc("Maximum stages allowed in the generated scheduled."), cl::Hidden, cl::init(3)) ( "pipeliner-max-stages" , cl::desc("Maximum stages allowed in the generated scheduled.") , cl::Hidden , cl::init(3) )	static

◆ SwpPruneDeps

cl::opt< bool > SwpPruneDeps("pipeliner-prune-deps", cl::desc("Prune dependences between unrelated Phi nodes."), cl::Hidden, cl::init(true)) ( "pipeliner-prune-deps" , cl::desc("Prune dependences between unrelated Phi nodes.") , cl::Hidden , cl::init(true) )	static

A command line option to disable the pruning of chain dependences due to an unrelated Phi.

◆ SwpPruneLoopCarried

cl::opt< bool > SwpPruneLoopCarried("pipeliner-prune-loop-carried", cl::desc("Prune loop carried order dependences."), cl::Hidden, cl::init(true)) ( "pipeliner-prune-loop-carried" , cl::desc("Prune loop carried order dependences.") , cl::Hidden , cl::init(true) )	static

◆ SwpShowResMask

cl::opt< bool > SwpShowResMask("pipeliner-show-mask", cl::Hidden, cl::init(false)) ( "pipeliner-show-mask" , cl::Hidden , cl::init(false) )	static

◆ WindowSchedulingOption

cl::opt< WindowSchedulingFlag > WindowSchedulingOption("window-sched", cl::Hidden, cl::init(WindowSchedulingFlag::WS_On), cl::desc("Set how to use window scheduling algorithm."), cl::values(clEnumValN(WindowSchedulingFlag::WS_Off, "off", "Turn off window algorithm."), clEnumValN(WindowSchedulingFlag::WS_On, "on", "Use window algorithm after SMS algorithm fails."), clEnumValN(WindowSchedulingFlag::WS_Force, "force", "Use window algorithm instead of SMS algorithm."))) ( "window-sched" , cl::Hidden , cl::init(WindowSchedulingFlag::WS_On) , cl::desc("Set how to use window scheduling algorithm.") , cl::values(clEnumValN(WindowSchedulingFlag::WS_Off, "off", "Turn off window algorithm."), clEnumValN(WindowSchedulingFlag::WS_On, "on", "Use window algorithm after SMS algorithm fails."), clEnumValN(WindowSchedulingFlag::WS_Force, "force", "Use window algorithm instead of SMS algorithm.")) )

static

A command line argument to set the window scheduling option.