ShrinkWrap.cpp File Reference

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

Go to the source code of this file.

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")
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"))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "shrink-wrap"

Definition at line 90 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 424 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 376 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 801 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 402 of file ShrinkWrap.cpp.

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

isAnalyzableBB()

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

static

Definition at line 389 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 438 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 411 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 527 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

1. NMBB points to MBB unconditionally
2. All dirtyPreds that previously pointed to MBB point to NMBB

Definition at line 484 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

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

Definition at line 463 of file ShrinkWrap.cpp.

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

Referenced by rollbackRestoreSplit(), and tryToSplitRestore().

Variable Documentation

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