#include "llvm/CodeGen/ShrinkWrap.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/CodeGen/TargetFrameLowering.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Function.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
#include <memory>

Macros
#define	DEBUG_TYPE "shrink-wrap"

Functions
	STATISTIC (NumFunc, "Number of functions")
	STATISTIC (NumCandidates, "Number of shrink-wrapping candidates")
	STATISTIC (NumCandidatesDropped, "Number of shrink-wrapping candidates dropped because of frequency")
	INITIALIZE_PASS_BEGIN (ShrinkWrapLegacy, DEBUG_TYPE, "Shrink Wrap Pass", false, false) INITIALIZE_PASS_END(ShrinkWrapLegacy
template<typename ListOfBBs, typename DominanceAnalysis>
static MachineBasicBlock *	FindIDom (MachineBasicBlock &Block, ListOfBBs BBs, DominanceAnalysis &Dom, bool Strict=true)
	Helper function to find the immediate (post) dominator.
static bool	isAnalyzableBB (const TargetInstrInfo &TII, MachineBasicBlock &Entry)
static bool	hasDirtyPred (const DenseSet< const MachineBasicBlock * > &ReachableByDirty, const MachineBasicBlock &MBB)
	Determines if any predecessor of MBB is on the path from block that has use or def of CSRs/FI to MBB.
static void	markAllReachable (DenseSet< const MachineBasicBlock * > &Visited, const MachineBasicBlock &MBB)
	Derives the list of all the basic blocks reachable from MBB.
static void	collectBlocksReachableByDirty (const DenseSet< const MachineBasicBlock * > &DirtyBBs, DenseSet< const MachineBasicBlock * > &ReachableByDirty)
	Collect blocks reachable by use or def of CSRs/FI.
static bool	isSaveReachableThroughClean (const MachineBasicBlock SavePoint, ArrayRef< MachineBasicBlock > CleanPreds)
static void	updateTerminator (MachineBasicBlock BBToUpdate, MachineBasicBlock NMBB, const TargetInstrInfo *TII)
	This function updates the branches post restore point split.
static MachineBasicBlock *	tryToSplitRestore (MachineBasicBlock MBB, ArrayRef< MachineBasicBlock > DirtyPreds, const TargetInstrInfo *TII)
	This function splits the restore point and returns new restore point/BB.
static void	rollbackRestoreSplit (MachineFunction &MF, MachineBasicBlock NMBB, MachineBasicBlock MBB, ArrayRef< MachineBasicBlock * > DirtyPreds, const TargetInstrInfo *TII)
	This function undoes the restore point split done earlier.
static bool	giveUpWithRemarks (MachineOptimizationRemarkEmitter ORE, StringRef RemarkName, StringRef RemarkMessage, const DiagnosticLocation &Loc, const MachineBasicBlock MBB)

Variables
static cl::opt< cl::boolOrDefault >	EnableShrinkWrapOpt ("enable-shrink-wrap", cl::Hidden, cl::desc("enable the shrink-wrapping pass"))
static cl::opt< bool >	EnablePostShrinkWrapOpt ("enable-shrink-wrap-region-split", cl::init(true), cl::Hidden, cl::desc("enable splitting of the restore block if possible"))
	DEBUG_TYPE
Shrink Wrap	Pass
Shrink Wrap	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "shrink-wrap"

Definition at line 91 of file ShrinkWrap.cpp.

Function Documentation

◆ collectBlocksReachableByDirty()

void collectBlocksReachableByDirty	(	const DenseSet< const MachineBasicBlock * > &	DirtyBBs,
		DenseSet< const MachineBasicBlock * > &	ReachableByDirty )

static

Collect blocks reachable by use or def of CSRs/FI.

Definition at line 428 of file ShrinkWrap.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), markAllReachable(), and MBB.

◆ FindIDom()

template<typename ListOfBBs, typename DominanceAnalysis>

MachineBasicBlock * FindIDom	(	MachineBasicBlock &	Block,
		ListOfBBs	BBs,
		DominanceAnalysis &	Dom,
		bool	Strict = true )

static

Helper function to find the immediate (post) dominator.

Definition at line 385 of file ShrinkWrap.cpp.

References llvm::Block, and llvm::iterator_range().

◆ giveUpWithRemarks()

bool giveUpWithRemarks	(	MachineOptimizationRemarkEmitter *	ORE,
		StringRef	RemarkName,
		StringRef	RemarkMessage,
		const DiagnosticLocation &	Loc,
		const MachineBasicBlock *	MBB )

static

Definition at line 815 of file ShrinkWrap.cpp.

References llvm::dbgs(), DEBUG_TYPE, llvm::MachineOptimizationRemarkEmitter::emit(), LLVM_DEBUG, and MBB.

◆ hasDirtyPred()

bool hasDirtyPred	(	const DenseSet< const MachineBasicBlock * > &	ReachableByDirty,
		const MachineBasicBlock &	MBB )

static

Determines if any predecessor of MBB is on the path from block that has use or def of CSRs/FI to MBB.

ReachableByDirty: All blocks reachable from block that has use or def of CSR/FI.

Definition at line 406 of file ShrinkWrap.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), and MBB.

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	ShrinkWrapLegacy	,
		DEBUG_TYPE	,
		"Shrink Wrap Pass"	,
		false	,
		false	)

References DEBUG_TYPE, and INITIALIZE_PASS_DEPENDENCY.

◆ isAnalyzableBB()

bool isAnalyzableBB	(	const TargetInstrInfo &	TII,
		MachineBasicBlock &	Entry )

static

Definition at line 393 of file ShrinkWrap.cpp.

References Cond, TBB, and TII.

◆ isSaveReachableThroughClean()

bool isSaveReachableThroughClean	(	const MachineBasicBlock *	SavePoint,
		ArrayRef< MachineBasicBlock * >	CleanPreds )

static

Returns: true if there is a clean path from SavePoint to the original Restore.

Definition at line 442 of file ShrinkWrap.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::MachineBasicBlock::pred_begin(), llvm::MachineBasicBlock::pred_end(), and llvm::MachineBasicBlock::pred_size().

◆ markAllReachable()

void markAllReachable	(	DenseSet< const MachineBasicBlock * > &	Visited,
		const MachineBasicBlock &	MBB )

static

Derives the list of all the basic blocks reachable from MBB.

Definition at line 415 of file ShrinkWrap.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), MBB, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::MachineBasicBlock::succ_begin(), and llvm::MachineBasicBlock::succ_end().

Referenced by collectBlocksReachableByDirty().

◆ rollbackRestoreSplit()

void rollbackRestoreSplit	(	MachineFunction &	MF,
		MachineBasicBlock *	NMBB,
		MachineBasicBlock *	MBB,
		ArrayRef< MachineBasicBlock * >	DirtyPreds,
		const TargetInstrInfo *	TII )

static

This function undoes the restore point split done earlier.

DirtyPreds: All predecessors of NMBB that are ReachableByDirty.

Restore point was split and the change needs to be unrolled. Make necessary changes to reset restore point from NMBB to MBB.

Definition at line 531 of file ShrinkWrap.cpp.

References llvm::MachineBasicBlock::begin(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::erase(), llvm::MachineBasicBlock::eraseFromParent(), llvm::SmallPtrSetImpl< PtrType >::insert(), MBB, llvm::MachineBasicBlock::removeSuccessor(), TII, and updateTerminator().

◆ STATISTIC() [1/3]

STATISTIC	(	NumCandidates	,
		"Number of shrink-wrapping candidates"	)

◆ STATISTIC() [2/3]

STATISTIC	(	NumCandidatesDropped	,
		"Number of shrink-wrapping candidates dropped because of frequency"	)

◆ STATISTIC() [3/3]

STATISTIC	(	NumFunc	,
		"Number of functions"	)

◆ tryToSplitRestore()

MachineBasicBlock * tryToSplitRestore	(	MachineBasicBlock *	MBB,
		ArrayRef< MachineBasicBlock * >	DirtyPreds,
		const TargetInstrInfo *	TII )

static

This function splits the restore point and returns new restore point/BB.

DirtyPreds: Predessors of MBB that are ReachableByDirty

Decision has been made to split the restore point. old restore point: MBB new restore point: NMBB This function makes the necessary block layout changes so that

NMBB points to MBB unconditionally
All dirtyPreds that previously pointed to MBB point to NMBB

Definition at line 488 of file ShrinkWrap.cpp.

References llvm::MachineBasicBlock::addLiveIn(), llvm::MachineBasicBlock::addSuccessor(), llvm::MachineFunction::CreateMachineBasicBlock(), llvm::dwarf_linker::DebugLoc, llvm::MachineFunction::end(), llvm::MachineFunction::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), MBB, TII, and updateTerminator().

◆ updateTerminator()

void updateTerminator	(	MachineBasicBlock *	BBToUpdate,
		MachineBasicBlock *	NMBB,
		const TargetInstrInfo *	TII )

static

This function updates the branches post restore point split.

Restore point has been split. Old restore point: MBB New restore point: NMBB Any basic block(say BBToUpdate) which had a fallthrough to MBB previously should

Fallthrough to NMBB iff NMBB is inserted immediately above MBB in the block layout OR
Branch unconditionally to NMBB iff NMBB is inserted at any other place.

Definition at line 467 of file ShrinkWrap.cpp.

References DL, llvm::MachineBasicBlock::findBranchDebugLoc(), llvm::MachineBasicBlock::isLayoutSuccessor(), and TII.

Referenced by rollbackRestoreSplit(), and tryToSplitRestore().

Variable Documentation

◆ DEBUG_TYPE

DEBUG_TYPE

Definition at line 299 of file ShrinkWrap.cpp.

◆ EnablePostShrinkWrapOpt

cl::opt< bool > EnablePostShrinkWrapOpt("enable-shrink-wrap-region-split", cl::init(true), cl::Hidden, cl::desc("enable splitting of the restore block if possible"))	(	"enable-shrink-wrap-region-split"	,
		cl::init(true)	,
		cl::Hidden	,
		cl::desc("enable splitting of the restore block if possible")	)

static

◆ EnableShrinkWrapOpt

cl::opt< cl::boolOrDefault > EnableShrinkWrapOpt("enable-shrink-wrap", cl::Hidden, cl::desc("enable the shrink-wrapping pass"))	(	"enable-shrink-wrap"	,
		cl::Hidden	,
		cl::desc("enable the shrink-wrapping pass")	)

static

◆ false

Shrink Wrap false

Definition at line 299 of file ShrinkWrap.cpp.

◆ Pass

Shrink Wrap Pass

Definition at line 299 of file ShrinkWrap.cpp.

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ collectBlocksReachableByDirty()

◆ FindIDom()

◆ giveUpWithRemarks()

◆ hasDirtyPred()

◆ INITIALIZE_PASS_BEGIN()

◆ isAnalyzableBB()

◆ isSaveReachableThroughClean()

◆ markAllReachable()

◆ rollbackRestoreSplit()

◆ STATISTIC() [1/3]

◆ STATISTIC() [2/3]

◆ STATISTIC() [3/3]

◆ tryToSplitRestore()

◆ updateTerminator()

Variable Documentation

◆ DEBUG_TYPE

◆ EnablePostShrinkWrapOpt

◆ EnableShrinkWrapOpt

◆ false

◆ Pass