#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()

static 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 430 of file ShrinkWrap.cpp.

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

◆ FindIDom()

template<typename ListOfBBs , typename DominanceAnalysis >

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

static

Helper function to find the immediate (post) dominator.

Definition at line 387 of file ShrinkWrap.cpp.

References llvm::Block.

◆ giveUpWithRemarks()

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

static

Definition at line 807 of file ShrinkWrap.cpp.

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

◆ hasDirtyPred()

static 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 408 of file ShrinkWrap.cpp.

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

◆ INITIALIZE_PASS_BEGIN()

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

◆ isAnalyzableBB()

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

static

Definition at line 395 of file ShrinkWrap.cpp.

References llvm::HexagonInstrInfo::analyzeBranch(), Cond, TBB, and TII.

◆ isSaveReachableThroughClean()

static 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 444 of file ShrinkWrap.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::SmallVectorBase< Size_T >::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()

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

static

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

Definition at line 417 of file ShrinkWrap.cpp.

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

Referenced by collectBlocksReachableByDirty().

◆ rollbackRestoreSplit()

static 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 533 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()

static 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 490 of file ShrinkWrap.cpp.

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

◆ updateTerminator()

static 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 469 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 301 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 301 of file ShrinkWrap.cpp.

◆ Pass

Shrink Wrap Pass

Definition at line 301 of file ShrinkWrap.cpp.

Referenced by llvm::PassManager< Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, LPMUpdater & >::runSinglePass().

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