A reimplementation of ModuloScheduleExpander. More...

#include "llvm/CodeGen/ModuloSchedule.h"

Public Member Functions
	PeelingModuloScheduleExpander (MachineFunction &MF, ModuloSchedule &S, LiveIntervals *LIS)

void	expand ()

void	validateAgainstModuloScheduleExpander ()
	Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated by PeelingModuloScheduleExpander.

Protected Member Functions
void	rewriteKernel ()
	Converts BB from the original loop body to the rewritten, pipelined steady-state.

MachineBasicBlock *	peelKernel (LoopPeelDirection LPD)
	Peels one iteration of the rewritten kernel (BB) in the specified direction.

void	filterInstructions (MachineBasicBlock *MB, int MinStage)

void	moveStageBetweenBlocks (MachineBasicBlock DestBB, MachineBasicBlock SourceBB, unsigned Stage)

void	peelPrologAndEpilogs ()
	Peel the kernel forwards and backwards to produce prologs and epilogs, and stitch them together.

Register	getEquivalentRegisterIn (Register Reg, MachineBasicBlock *BB)
	All prolog and epilog blocks are clones of the kernel, so any produced register in one block has an corollary in all other blocks.

void	rewriteUsesOf (MachineInstr *MI)
	Change all users of MI, if MI is predicated out (LiveStages[MI->getParent()] == false).

void	fixupBranches ()
	Insert branches between prologs, kernel and epilogs.

MachineBasicBlock *	CreateLCSSAExitingBlock ()
	Create a poor-man's LCSSA by cloning only the PHIs from the kernel block to a block dominated by all prologs and epilogs.

unsigned	getStage (MachineInstr *MI)
	Helper to get the stage of an instruction in the schedule.

Register	getPhiCanonicalReg (MachineInstr CanonicalPhi, MachineInstr Phi)
	Helper function to find the right canonical register for a phi instruction coming from a peeled out prologue.

Protected Attributes
ModuloSchedule &	Schedule

MachineFunction &	MF

const TargetSubtargetInfo &	ST

MachineRegisterInfo &	MRI

const TargetInstrInfo *	TII = nullptr

LiveIntervals *	LIS = nullptr

MachineBasicBlock *	BB = nullptr
	The original loop block that gets rewritten in-place.

MachineBasicBlock *	Preheader = nullptr
	The original loop preheader.

SmallVector< MachineBasicBlock *, 4 >	Prologs
	All prolog and epilog blocks.

SmallVector< MachineBasicBlock *, 4 >	Epilogs

DenseMap< MachineBasicBlock *, BitVector >	LiveStages
	For every block, the stages that are produced.

DenseMap< MachineBasicBlock *, BitVector >	AvailableStages
	For every block, the stages that are available.

DenseMap< MachineInstr *, unsigned >	PhiNodeLoopIteration
	When peeling the epilogue keep track of the distance between the phi nodes and the kernel.

DenseMap< MachineInstr , MachineInstr >	CanonicalMIs
	CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.

DenseMap< std::pair< MachineBasicBlock , MachineInstr >, MachineInstr * >	BlockMIs

std::deque< MachineBasicBlock * >	PeeledFront
	State passed from peelKernel to peelPrologAndEpilogs().

std::deque< MachineBasicBlock * >	PeeledBack

SmallVector< MachineInstr *, 4 >	IllegalPhisToDelete
	Illegal phis that need to be deleted once we re-link stages.

std::unique_ptr< TargetInstrInfo::PipelinerLoopInfo >	LoopInfo
	Target loop info before kernel peeling.

Detailed Description

A reimplementation of ModuloScheduleExpander.

It works by generating a standalone kernel loop and peeling out the prologs and epilogs.

Definition at line 283 of file ModuloSchedule.h.

Constructor & Destructor Documentation

◆ PeelingModuloScheduleExpander()

llvm::PeelingModuloScheduleExpander::PeelingModuloScheduleExpander	(	MachineFunction &	MF,
		ModuloSchedule &	S,
		LiveIntervals *	LIS
	)

inline

Definition at line 285 of file ModuloSchedule.h.

Member Function Documentation

◆ CreateLCSSAExitingBlock()

MachineBasicBlock * PeelingModuloScheduleExpander::CreateLCSSAExitingBlock ( )

protected

Create a poor-man's LCSSA by cloning only the PHIs from the kernel block to a block dominated by all prologs and epilogs.

This allows us to treat the loop exiting block as any other kernel clone.

Definition at line 1863 of file ModuloSchedule.cpp.

References llvm::MachineInstrBuilder::addMBB(), llvm::MachineInstrBuilder::addReg(), llvm::MachineBasicBlock::addSuccessor(), llvm::TargetInstrInfo::analyzeBranch(), assert(), BB, BlockMIs, llvm::BuildMI(), CanonicalMIs, Cond, llvm::MachineFunction::CreateMachineBasicBlock(), llvm::MachineRegisterInfo::createVirtualRegister(), llvm::MCInstrInfo::get(), llvm::MachineBasicBlock::getBasicBlock(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::MachineBasicBlock::getParent(), llvm::MachineRegisterInfo::getRegClass(), llvm::MachineRegisterInfo::getTargetRegisterInfo(), llvm::MachineFunction::insert(), llvm::TargetInstrInfo::insertBranch(), llvm::TargetInstrInfo::insertUnconditionalBranch(), MF, MI, MRI, llvm::MachineBasicBlock::phis(), llvm::TargetInstrInfo::removeBranch(), llvm::MachineBasicBlock::replaceSuccessor(), llvm::MachineBasicBlock::succ_begin(), TBB, TII, llvm::MachineRegisterInfo::use_instructions(), and Uses.

Referenced by peelPrologAndEpilogs().

◆ expand()

void PeelingModuloScheduleExpander::expand ( )

Definition at line 2009 of file ModuloSchedule.cpp.

References llvm::TargetInstrInfo::analyzeLoopForPipelining(), assert(), BB, llvm::ModuloSchedule::dump(), fixupBranches(), llvm::ModuloSchedule::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::MachineLoop::getTopBlock(), LLVM_DEBUG, peelPrologAndEpilogs(), Preheader, rewriteKernel(), Schedule, and TII.

Referenced by llvm::SwingSchedulerDAG::schedule().

◆ filterInstructions()

void PeelingModuloScheduleExpander::filterInstructions	(	MachineBasicBlock *	MB,
		int	MinStage
	)

protected

Definition at line 1614 of file ModuloSchedule.cpp.

References assert(), llvm::SmallVectorImpl< T >::emplace_back(), getEquivalentRegisterIn(), llvm::MachineBasicBlock::getFirstInstrTerminator(), llvm::MachineBasicBlock::getFirstNonPHI(), llvm::MachineInstrBuilder::getReg(), getStage(), llvm::MachineRegisterInfo::getTargetRegisterInfo(), I, LIS, MI, MRI, llvm::LiveIntervals::RemoveMachineInstrFromMaps(), llvm::MachineRegisterInfo::use_instructions(), and UseMI.

Referenced by peelPrologAndEpilogs().

◆ fixupBranches()

void PeelingModuloScheduleExpander::fixupBranches ( )

protected

Insert branches between prologs, kernel and epilogs.

Definition at line 1957 of file ModuloSchedule.cpp.

References Cond, llvm::dbgs(), Epilog, Epilogs, llvm::ModuloSchedule::getNumStages(), llvm::TargetInstrInfo::insertBranch(), llvm::TargetInstrInfo::insertUnconditionalBranch(), LLVM_DEBUG, P, llvm::MachineBasicBlock::phis(), Prolog, Prologs, llvm::TargetInstrInfo::removeBranch(), Schedule, and TII.

Referenced by expand().

◆ getEquivalentRegisterIn()

Register PeelingModuloScheduleExpander::getEquivalentRegisterIn	(	Register	Reg,
		MachineBasicBlock *	BB
	)

protected

All prolog and epilog blocks are clones of the kernel, so any produced register in one block has an corollary in all other blocks.

Definition at line 1907 of file ModuloSchedule.cpp.

References BB, BlockMIs, CanonicalMIs, llvm::MachineRegisterInfo::getUniqueVRegDef(), MI, and MRI.

Referenced by filterInstructions(), peelPrologAndEpilogs(), and rewriteUsesOf().

◆ getPhiCanonicalReg()

Register PeelingModuloScheduleExpander::getPhiCanonicalReg	(	MachineInstr *	CanonicalPhi,
		MachineInstr *	Phi
	)

protected

Helper function to find the right canonical register for a phi instruction coming from a peeled out prologue.

Definition at line 1729 of file ModuloSchedule.cpp.

References assert(), llvm::MachineOperand::getMBB(), llvm::MachineInstr::getNumOperands(), llvm::MachineInstr::getOperand(), llvm::MachineInstr::getParent(), llvm::MachineOperand::getReg(), llvm::MachineRegisterInfo::getVRegDef(), I, llvm::MachineInstr::isPHI(), MRI, PhiNodeLoopIteration, and std::swap().

Referenced by peelPrologAndEpilogs().

◆ getStage()

unsigned llvm::PeelingModuloScheduleExpander::getStage ( MachineInstr * MI )

inlineprotected

Helper to get the stage of an instruction in the schedule.

Definition at line 361 of file ModuloSchedule.h.

References CanonicalMIs, llvm::ModuloSchedule::getStage(), MI, and Schedule.

Referenced by filterInstructions(), moveStageBetweenBlocks(), and rewriteUsesOf().

◆ moveStageBetweenBlocks()

void PeelingModuloScheduleExpander::moveStageBetweenBlocks	(	MachineBasicBlock *	DestBB,
		MachineBasicBlock *	SourceBB,
		unsigned	Stage
	)

protected

Definition at line 1643 of file ModuloSchedule.cpp.

References llvm::MachineInstrBuilder::addMBB(), llvm::MachineInstrBuilder::addReg(), assert(), BlockMIs, llvm::BuildMI(), CanonicalMIs, llvm::MachineFunction::CloneMachineInstr(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::MachineRegisterInfo::createVirtualRegister(), llvm::MachineBasicBlock::end(), llvm::MCInstrInfo::get(), llvm::MachineBasicBlock::getFirstNonPHI(), llvm::MachineInstr::getOperand(), llvm::MachineOperand::getReg(), llvm::MachineRegisterInfo::getRegClass(), getStage(), llvm::MachineRegisterInfo::getUniqueVRegDef(), llvm::MachineRegisterInfo::getVRegDef(), I, llvm::MachineBasicBlock::insert(), llvm::MachineOperand::isReg(), llvm::make_early_inc_range(), llvm::make_range(), MF, MI, MRI, P, PhiNodeLoopIteration, llvm::MachineBasicBlock::phis(), llvm::MachineBasicBlock::pred_begin(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::MachineRegisterInfo::replaceRegWith(), llvm::MachineOperand::setMBB(), llvm::MachineOperand::setReg(), and TII.

Referenced by peelPrologAndEpilogs().

◆ peelKernel()

MachineBasicBlock * PeelingModuloScheduleExpander::peelKernel ( LoopPeelDirection LPD )

protected

Peels one iteration of the rewritten kernel (BB) in the specified direction.

Definition at line 1598 of file ModuloSchedule.cpp.

References BB, llvm::MachineBasicBlock::begin(), BlockMIs, CanonicalMIs, I, llvm::LPD_Front, MRI, PeeledBack, PeeledFront, llvm::PeelSingleBlockLoop(), and TII.

Referenced by peelPrologAndEpilogs().

◆ peelPrologAndEpilogs()

void PeelingModuloScheduleExpander::peelPrologAndEpilogs ( )

protected

Peel the kernel forwards and backwards to produce prologs and epilogs, and stitch them together.

Definition at line 1746 of file ModuloSchedule.cpp.

References assert(), AvailableStages, B, BB, Blocks, CanonicalMIs, llvm::SmallVectorImpl< T >::clear(), llvm::copy(), CreateLCSSAExitingBlock(), llvm::MachineOperand::CreateMBB(), llvm::MachineOperand::CreateReg(), Epilogs, filterInstructions(), getEquivalentRegisterIn(), llvm::ModuloSchedule::getNumStages(), getPhiCanonicalReg(), llvm::MachineRegisterInfo::getUniqueVRegDef(), I, IllegalPhisToDelete, llvm::MachineInstr::isPHI(), LIS, LiveStages, llvm::LPD_Back, llvm::LPD_Front, MI, moveStageBetweenBlocks(), MRI, PeeledBack, PeeledFront, peelKernel(), PhiNodeLoopIteration, llvm::MachineBasicBlock::pred_begin(), Prologs, llvm::LiveIntervals::RemoveMachineInstrFromMaps(), llvm::reverse(), rewriteUsesOf(), and Schedule.

Referenced by expand(), and validateAgainstModuloScheduleExpander().

◆ rewriteKernel()

void PeelingModuloScheduleExpander::rewriteKernel ( )

protected

Converts BB from the original loop body to the rewritten, pipelined steady-state.

Definition at line 2004 of file ModuloSchedule.cpp.

References BB, llvm::ModuloSchedule::getLoop(), and Schedule.

Referenced by expand().

◆ rewriteUsesOf()

void PeelingModuloScheduleExpander::rewriteUsesOf ( MachineInstr * MI )

protected

Change all users of MI, if MI is predicated out (LiveStages[MI->getParent()] == false).

Definition at line 1914 of file ModuloSchedule.cpp.

References assert(), AvailableStages, llvm::SmallVectorImpl< T >::emplace_back(), getEquivalentRegisterIn(), llvm::MachineInstrBuilder::getReg(), llvm::MachineRegisterInfo::getRegClass(), getStage(), llvm::MachineRegisterInfo::getTargetRegisterInfo(), llvm::MachineRegisterInfo::getUniqueVRegDef(), IllegalPhisToDelete, LIS, LiveStages, MI, MRI, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LiveIntervals::RemoveMachineInstrFromMaps(), llvm::MachineRegisterInfo::replaceRegWith(), llvm::MachineRegisterInfo::setRegClass(), llvm::MachineRegisterInfo::use_instructions(), and UseMI.

Referenced by peelPrologAndEpilogs().

◆ validateAgainstModuloScheduleExpander()

void PeelingModuloScheduleExpander::validateAgainstModuloScheduleExpander ( )

Runs ModuloScheduleExpander and treats it as a golden input to validate aspects of the code generated by PeelingModuloScheduleExpander.

Definition at line 2021 of file ModuloSchedule.cpp.

References llvm::MachineBasicBlock::addSuccessor(), assert(), BB, llvm::MachineBasicBlock::begin(), llvm::ModuloScheduleExpander::cleanup(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::MachineBasicBlock::end(), llvm::errs(), llvm::ModuloScheduleExpander::expand(), llvm::Failed(), llvm::raw_ostream::flush(), llvm::MachineBasicBlock::getFirstNonPHI(), llvm::ModuloSchedule::getLoop(), llvm::LoopBase< BlockT, LoopT >::getLoopPreheader(), llvm::ModuloScheduleExpander::getRewrittenKernel(), llvm::MachineLoop::getTopBlock(), llvm::SmallPtrSetImpl< PtrType >::insert(), LIS, MF, MRI, OS, peelPrologAndEpilogs(), Preheader, llvm::ModuloSchedule::print(), llvm::MachineBasicBlock::print(), llvm::MachineBasicBlock::removeSuccessor(), llvm::report_fatal_error(), and Schedule.

Member Data Documentation

◆ AvailableStages

DenseMap<MachineBasicBlock *, BitVector> llvm::PeelingModuloScheduleExpander::AvailableStages

protected

For every block, the stages that are available.

A stage can be available but not produced (in the epilog) or produced but not available (in the prolog).

Definition at line 315 of file ModuloSchedule.h.

Referenced by peelPrologAndEpilogs(), and rewriteUsesOf().

◆ BB

MachineBasicBlock* llvm::PeelingModuloScheduleExpander::BB = nullptr

protected

The original loop block that gets rewritten in-place.

Definition at line 305 of file ModuloSchedule.h.

Referenced by CreateLCSSAExitingBlock(), expand(), getEquivalentRegisterIn(), peelKernel(), peelPrologAndEpilogs(), rewriteKernel(), and validateAgainstModuloScheduleExpander().

◆ BlockMIs

DenseMap<std::pair<MachineBasicBlock *, MachineInstr *>, MachineInstr *> llvm::PeelingModuloScheduleExpander::BlockMIs

protected

Definition at line 324 of file ModuloSchedule.h.

Referenced by CreateLCSSAExitingBlock(), getEquivalentRegisterIn(), moveStageBetweenBlocks(), and peelKernel().

◆ CanonicalMIs

DenseMap<MachineInstr *, MachineInstr *> llvm::PeelingModuloScheduleExpander::CanonicalMIs

protected

CanonicalMIs and BlockMIs form a bidirectional map between any of the loop kernel clones.

Definition at line 322 of file ModuloSchedule.h.

Referenced by CreateLCSSAExitingBlock(), getEquivalentRegisterIn(), getStage(), moveStageBetweenBlocks(), peelKernel(), and peelPrologAndEpilogs().

◆ Epilogs

SmallVector<MachineBasicBlock *, 4> llvm::PeelingModuloScheduleExpander::Epilogs

protected

Definition at line 309 of file ModuloSchedule.h.

Referenced by fixupBranches(), and peelPrologAndEpilogs().

◆ IllegalPhisToDelete

SmallVector<MachineInstr *, 4> llvm::PeelingModuloScheduleExpander::IllegalPhisToDelete

protected

Illegal phis that need to be deleted once we re-link stages.

Definition at line 329 of file ModuloSchedule.h.

Referenced by peelPrologAndEpilogs(), and rewriteUsesOf().

◆ LIS

LiveIntervals* llvm::PeelingModuloScheduleExpander::LIS = nullptr

protected

Definition at line 302 of file ModuloSchedule.h.

Referenced by filterInstructions(), peelPrologAndEpilogs(), rewriteUsesOf(), and validateAgainstModuloScheduleExpander().

◆ LiveStages

DenseMap<MachineBasicBlock *, BitVector> llvm::PeelingModuloScheduleExpander::LiveStages

protected

For every block, the stages that are produced.

Definition at line 311 of file ModuloSchedule.h.

Referenced by peelPrologAndEpilogs(), and rewriteUsesOf().

◆ LoopInfo

std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> llvm::PeelingModuloScheduleExpander::LoopInfo

protected

Target loop info before kernel peeling.

Definition at line 370 of file ModuloSchedule.h.

◆ MF

MachineFunction& llvm::PeelingModuloScheduleExpander::MF

protected

Definition at line 298 of file ModuloSchedule.h.

Referenced by CreateLCSSAExitingBlock(), moveStageBetweenBlocks(), and validateAgainstModuloScheduleExpander().

◆ MRI

MachineRegisterInfo& llvm::PeelingModuloScheduleExpander::MRI

protected

Definition at line 300 of file ModuloSchedule.h.

Referenced by CreateLCSSAExitingBlock(), filterInstructions(), getEquivalentRegisterIn(), getPhiCanonicalReg(), moveStageBetweenBlocks(), peelKernel(), peelPrologAndEpilogs(), rewriteUsesOf(), and validateAgainstModuloScheduleExpander().

◆ PeeledBack

std::deque<MachineBasicBlock *> llvm::PeelingModuloScheduleExpander::PeeledBack

protected

Definition at line 327 of file ModuloSchedule.h.

Referenced by peelKernel(), and peelPrologAndEpilogs().

◆ PeeledFront

std::deque<MachineBasicBlock *> llvm::PeelingModuloScheduleExpander::PeeledFront

protected

State passed from peelKernel to peelPrologAndEpilogs().

Definition at line 327 of file ModuloSchedule.h.

Referenced by peelKernel(), and peelPrologAndEpilogs().

◆ PhiNodeLoopIteration

DenseMap<MachineInstr *, unsigned> llvm::PeelingModuloScheduleExpander::PhiNodeLoopIteration

protected

When peeling the epilogue keep track of the distance between the phi nodes and the kernel.

Definition at line 318 of file ModuloSchedule.h.

Referenced by getPhiCanonicalReg(), moveStageBetweenBlocks(), and peelPrologAndEpilogs().

◆ Preheader

MachineBasicBlock* llvm::PeelingModuloScheduleExpander::Preheader = nullptr

protected

The original loop preheader.

Definition at line 307 of file ModuloSchedule.h.

Referenced by expand(), and validateAgainstModuloScheduleExpander().

◆ Prologs

SmallVector<MachineBasicBlock *, 4> llvm::PeelingModuloScheduleExpander::Prologs

protected

All prolog and epilog blocks.

Definition at line 309 of file ModuloSchedule.h.

Referenced by fixupBranches(), and peelPrologAndEpilogs().

◆ Schedule

ModuloSchedule& llvm::PeelingModuloScheduleExpander::Schedule

protected

Definition at line 297 of file ModuloSchedule.h.

Referenced by expand(), fixupBranches(), getStage(), peelPrologAndEpilogs(), rewriteKernel(), and validateAgainstModuloScheduleExpander().

◆ ST

const TargetSubtargetInfo& llvm::PeelingModuloScheduleExpander::ST

protected

Definition at line 299 of file ModuloSchedule.h.

◆ TII

const TargetInstrInfo* llvm::PeelingModuloScheduleExpander::TII = nullptr

protected

Definition at line 301 of file ModuloSchedule.h.

Referenced by CreateLCSSAExitingBlock(), expand(), fixupBranches(), moveStageBetweenBlocks(), and peelKernel().

The documentation for this class was generated from the following files:

include/llvm/CodeGen/ModuloSchedule.h
lib/CodeGen/ModuloSchedule.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PeelingModuloScheduleExpander()

Member Function Documentation

◆ CreateLCSSAExitingBlock()

◆ expand()

◆ filterInstructions()

◆ fixupBranches()

◆ getEquivalentRegisterIn()

◆ getPhiCanonicalReg()

◆ getStage()

◆ moveStageBetweenBlocks()

◆ peelKernel()

◆ peelPrologAndEpilogs()

◆ rewriteKernel()

◆ rewriteUsesOf()

◆ validateAgainstModuloScheduleExpander()

Member Data Documentation

◆ AvailableStages

◆ BB

◆ BlockMIs

◆ CanonicalMIs

◆ Epilogs

◆ IllegalPhisToDelete

◆ LIS

◆ LiveStages

◆ LoopInfo

◆ MF

◆ MRI

◆ PeeledBack

◆ PeeledFront

◆ PhiNodeLoopIteration

◆ Preheader

◆ Prologs

◆ Schedule

◆ ST

◆ TII