#include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringSet.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <optional>
#include <set>
#include <sstream>

Macros
#define	DEBUG_TYPE "chr"
#define	CHR_DEBUG(X)

Functions
static void	parseCHRFilterFiles ()
static raw_ostream &	operator<< (raw_ostream &OS, const CHRStats &Stats)
static raw_ostream &	operator<< (raw_ostream &OS, const CHRScope &Scope)
static bool	shouldApply (Function &F, ProfileSummaryInfo &PSI)
static void	dumpIR (Function &F, const char Label, CHRStats Stats)
static bool	isHoistableInstructionType (Instruction *I)
static bool	isHoistable (Instruction *I, DominatorTree &DT)
static const std::set< Value * > &	getBaseValues (Value V, DominatorTree &DT, DenseMap< Value , std::set< Value * > > &Visited)
static bool	checkHoistValue (Value V, Instruction InsertPoint, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables, DenseSet< Instruction * > HoistStops, DenseMap< Instruction , bool > &Visited)
static bool	extractBranchProbabilities (Instruction *I, BranchProbability &TrueProb, BranchProbability &FalseProb)
static BranchProbability	getCHRBiasThreshold ()
template<typename K, typename S, typename M>
static bool	checkBias (K *Key, BranchProbability TrueProb, BranchProbability FalseProb, S &TrueSet, S &FalseSet, M &BiasMap)
static bool	checkBiasedBranch (BranchInst BI, Region R, DenseSet< Region * > &TrueBiasedRegionsGlobal, DenseSet< Region * > &FalseBiasedRegionsGlobal, DenseMap< Region *, BranchProbability > &BranchBiasMap)
static bool	checkBiasedSelect (SelectInst SI, Region R, DenseSet< SelectInst * > &TrueBiasedSelectsGlobal, DenseSet< SelectInst * > &FalseBiasedSelectsGlobal, DenseMap< SelectInst *, BranchProbability > &SelectBiasMap)
static Instruction *	getBranchInsertPoint (RegInfo &RI)
static DenseSet< Value * >	getCHRConditionValuesForRegion (RegInfo &RI)
static bool	shouldSplit (Instruction InsertPoint, DenseSet< Value > &PrevConditionValues, DenseSet< Value * > &ConditionValues, DominatorTree &DT, DenseSet< Instruction * > &Unhoistables)
static void	getSelectsInScope (CHRScope Scope, DenseSet< Instruction > &Output)
static bool	hasAtLeastTwoBiasedBranches (CHRScope *Scope)
static bool	CHRScopeSorter (CHRScope Scope1, CHRScope Scope2)
static void	hoistValue (Value V, Instruction HoistPoint, Region R, HoistStopMapTy &HoistStopMap, DenseSet< Instruction > &HoistedSet, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)
static void	hoistScopeConditions (CHRScope Scope, Instruction HoistPoint, DenseSet< PHINode * > &TrivialPHIs, DominatorTree &DT)
static bool	negateICmpIfUsedByBranchOrSelectOnly (ICmpInst ICmp, Instruction ExcludedUser, CHRScope *Scope)
static void	insertTrivialPHIs (CHRScope Scope, BasicBlock EntryBlock, BasicBlock ExitBlock, DenseSet< PHINode > &TrivialPHIs)
static void	assertCHRRegionsHaveBiasedBranchOrSelect (CHRScope *Scope)
static void	assertBranchOrSelectConditionHoisted (CHRScope Scope, BasicBlock PreEntryBlock)
static void	dumpScopes (SmallVectorImpl< CHRScope * > &Scopes, const char *Label)

Variables
static cl::opt< bool >	DisableCHR ("disable-chr", cl::init(false), cl::Hidden, cl::desc("Disable CHR for all functions"))
static cl::opt< bool >	ForceCHR ("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))
static cl::opt< double >	CHRBiasThreshold ("chr-bias-threshold", cl::init(0.99), cl::Hidden, cl::desc("CHR considers a branch bias greater than this ratio as biased"))
static cl::opt< unsigned >	CHRMergeThreshold ("chr-merge-threshold", cl::init(2), cl::Hidden, cl::desc("CHR merges a group of N branches/selects where N >= this value"))
static cl::opt< std::string >	CHRModuleList ("chr-module-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of modules to apply CHR to"))
static cl::opt< std::string >	CHRFunctionList ("chr-function-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of functions to apply CHR to"))
static cl::opt< unsigned >	CHRDupThreshsold ("chr-dup-threshold", cl::init(3), cl::Hidden, cl::desc("Max number of duplications by CHR for a region"))
static StringSet	CHRModules
static StringSet	CHRFunctions

Macro Definition Documentation

◆ CHR_DEBUG

#define CHR_DEBUG ( X )

Value:

LLVM_DEBUG(X)

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition Debug.h:114

X

static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")

Definition at line 49 of file ControlHeightReduction.cpp.

Referenced by assertBranchOrSelectConditionHoisted(), checkBiasedBranch(), checkBiasedSelect(), checkHoistValue(), dumpIR(), hoistValue(), insertTrivialPHIs(), and shouldSplit().

◆ DEBUG_TYPE

#define DEBUG_TYPE "chr"

Definition at line 47 of file ControlHeightReduction.cpp.

Function Documentation

◆ assertBranchOrSelectConditionHoisted()

void assertBranchOrSelectConditionHoisted	(	CHRScope *	Scope,
		BasicBlock *	PreEntryBlock )

static

Definition at line 1647 of file ControlHeightReduction.cpp.

References assert(), llvm::cast(), CHR_DEBUG, llvm::dbgs(), llvm::dyn_cast(), and I.

◆ assertCHRRegionsHaveBiasedBranchOrSelect()

void assertCHRRegionsHaveBiasedBranchOrSelect ( CHRScope * Scope )

static

Definition at line 1625 of file ControlHeightReduction.cpp.

References assert().

◆ checkBias()

template<typename K, typename S, typename M>

bool checkBias	(	K *	Key,
		BranchProbability	TrueProb,
		BranchProbability	FalseProb,
		S &	TrueSet,
		S &	FalseSet,
		M &	BiasMap )

static

Definition at line 609 of file ControlHeightReduction.cpp.

References getCHRBiasThreshold(), and llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key.

Referenced by checkBiasedBranch(), and checkBiasedSelect().

◆ checkBiasedBranch()

bool checkBiasedBranch	(	BranchInst *	BI,
		Region *	R,
		DenseSet< Region * > &	TrueBiasedRegionsGlobal,
		DenseSet< Region * > &	FalseBiasedRegionsGlobal,
		DenseMap< Region *, BranchProbability > &	BranchBiasMap )

static

Definition at line 627 of file ControlHeightReduction.cpp.

References assert(), checkBias(), CHR_DEBUG, llvm::dbgs(), extractBranchProbabilities(), llvm::BranchInst::getSuccessor(), llvm::BranchInst::isConditional(), and std::swap().

◆ checkBiasedSelect()

bool checkBiasedSelect	(	SelectInst *	SI,
		Region *	R,
		DenseSet< SelectInst * > &	TrueBiasedSelectsGlobal,
		DenseSet< SelectInst * > &	FalseBiasedSelectsGlobal,
		DenseMap< SelectInst *, BranchProbability > &	SelectBiasMap )

static

Definition at line 657 of file ControlHeightReduction.cpp.

References checkBias(), CHR_DEBUG, llvm::dbgs(), and extractBranchProbabilities().

◆ checkHoistValue()

bool checkHoistValue	(	Value *	V,
		Instruction *	InsertPoint,
		DominatorTree &	DT,
		DenseSet< Instruction * > &	Unhoistables,
		DenseSet< Instruction * > *	HoistStops,
		DenseMap< Instruction *, bool > &	Visited )

static

Definition at line 524 of file ControlHeightReduction.cpp.

References assert(), checkHoistValue(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert_range(), and isHoistable().

Referenced by checkHoistValue(), and shouldSplit().

◆ CHRScopeSorter()

bool CHRScopeSorter	(	CHRScope *	Scope1,
		CHRScope *	Scope2 )

static

Definition at line 1409 of file ControlHeightReduction.cpp.

◆ dumpIR()

void dumpIR	(	Function &	F,
		const char *	Label,
		CHRStats *	Stats )

static

Definition at line 427 of file ControlHeightReduction.cpp.

References CHR_DEBUG, llvm::dbgs(), F, and Stats.

◆ dumpScopes()

void dumpScopes	(	SmallVectorImpl< CHRScope * > &	Scopes,
		const char *	Label )

static

Definition at line 2010 of file ControlHeightReduction.cpp.

References llvm::dbgs().

◆ extractBranchProbabilities()

bool extractBranchProbabilities	(	Instruction *	I,
		BranchProbability &	TrueProb,
		BranchProbability &	FalseProb )

static

Definition at line 578 of file ControlHeightReduction.cpp.

References assert(), llvm::extractBranchWeights(), llvm::BranchProbability::getBranchProbability(), and I.

Referenced by checkBiasedBranch(), and checkBiasedSelect().

◆ getBaseValues()

const std::set< Value * > & getBaseValues	(	Value *	V,
		DominatorTree &	DT,
		DenseMap< Value , std::set< Value > > &	Visited )

static

Definition at line 488 of file ControlHeightReduction.cpp.

References llvm::dyn_cast(), getBaseValues(), I, llvm::isa(), and isHoistable().

Referenced by getBaseValues(), and shouldSplit().

◆ getBranchInsertPoint()

Instruction * getBranchInsertPoint ( RegInfo & RI )

static

Definition at line 676 of file ControlHeightReduction.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::BasicBlock::getTerminator(), I, and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().

◆ getCHRBiasThreshold()

BranchProbability getCHRBiasThreshold ( )

static

Definition at line 599 of file ControlHeightReduction.cpp.

References CHRBiasThreshold, and llvm::BranchProbability::getBranchProbability().

Referenced by checkBias().

◆ getCHRConditionValuesForRegion()

DenseSet< Value * > getCHRConditionValuesForRegion ( RegInfo & RI )

static

Definition at line 1019 of file ControlHeightReduction.cpp.

References llvm::cast(), and llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert().

◆ getSelectsInScope()

void getSelectsInScope	(	CHRScope *	Scope,
		DenseSet< Instruction * > &	Output )

static

Definition at line 1100 of file ControlHeightReduction.cpp.

References getSelectsInScope(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert_range(), and llvm::Sub.

Referenced by getSelectsInScope().

◆ hasAtLeastTwoBiasedBranches()

bool hasAtLeastTwoBiasedBranches ( CHRScope * Scope )

static

Definition at line 1307 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

◆ hoistScopeConditions()

void hoistScopeConditions	(	CHRScope *	Scope,
		Instruction *	HoistPoint,
		DenseSet< PHINode * > &	TrivialPHIs,
		DominatorTree &	DT )

static

Definition at line 1470 of file ControlHeightReduction.cpp.

References llvm::cast(), and hoistValue().

◆ hoistValue()

void hoistValue	(	Value *	V,
		Instruction *	HoistPoint,
		Region *	R,
		HoistStopMapTy &	HoistStopMap,
		DenseSet< Instruction * > &	HoistedSet,
		DenseSet< PHINode * > &	TrivialPHIs,
		DominatorTree &	DT )

static

Definition at line 1422 of file ControlHeightReduction.cpp.

References assert(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::dyn_cast(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), hoistValue(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), isHoistableInstructionType(), and IT.

Referenced by hoistScopeConditions(), and hoistValue().

◆ insertTrivialPHIs()

void insertTrivialPHIs	(	CHRScope *	Scope,
		BasicBlock *	EntryBlock,
		BasicBlock *	ExitBlock,
		DenseSet< PHINode * > &	TrivialPHIs )

static

Definition at line 1545 of file ControlHeightReduction.cpp.

References AbstractManglingParser< Derived, Alloc >::NumOps, llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), CHR_DEBUG, llvm::SetVector< T, Vector, Set, N >::contains(), llvm::PHINode::Create(), llvm::dbgs(), llvm::dyn_cast(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SetVector< T, Vector, Set, N >::insert(), llvm::Instruction::insertBefore(), llvm::isa(), llvm::make_early_inc_range(), llvm::pred_size(), llvm::predecessors(), and Users.

◆ isHoistable()

bool isHoistable	(	Instruction *	I,
		DominatorTree &	DT )

static

Definition at line 476 of file ControlHeightReduction.cpp.

References I, isHoistableInstructionType(), and llvm::isSafeToSpeculativelyExecute().

Referenced by checkHoistValue(), and getBaseValues().

◆ isHoistableInstructionType()

bool isHoistableInstructionType ( Instruction * I )

static

Definition at line 467 of file ControlHeightReduction.cpp.

References I, and llvm::isa().

Referenced by hoistValue(), and isHoistable().

◆ negateICmpIfUsedByBranchOrSelectOnly()

bool negateICmpIfUsedByBranchOrSelectOnly	(	ICmpInst *	ICmp,
		Instruction *	ExcludedUser,
		CHRScope *	Scope )

static

Definition at line 1496 of file ControlHeightReduction.cpp.

References assert(), llvm::cast(), llvm::dyn_cast(), getCondition(), llvm::CmpInst::getInversePredicate(), llvm::CmpInst::getPredicate(), llvm::isa(), llvm_unreachable, llvm::CmpInst::setPredicate(), and llvm::Value::users().

◆ operator<<() [1/2]

raw_ostream & operator<<	(	raw_ostream &	OS,
		const CHRScope &	Scope )

inlinestatic

Definition at line 406 of file ControlHeightReduction.cpp.

◆ operator<<() [2/2]

raw_ostream & operator<<	(	raw_ostream &	OS,
		const CHRStats &	Stats )

inlinestatic

Definition at line 399 of file ControlHeightReduction.cpp.

References Stats.

◆ parseCHRFilterFiles()

void parseCHRFilterFiles ( )

static

Definition at line 80 of file ControlHeightReduction.cpp.

References CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::errs(), llvm::MemoryBuffer::getFile(), and llvm::StringRef::split().

Referenced by llvm::ControlHeightReductionPass::ControlHeightReductionPass().

◆ shouldApply()

bool shouldApply	(	Function &	F,
		ProfileSummaryInfo &	PSI )

static

Definition at line 411 of file ControlHeightReduction.cpp.

References CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, DisableCHR, F, ForceCHR, and llvm::ProfileSummaryInfo::isFunctionEntryHot().

◆ shouldSplit()

bool shouldSplit	(	Instruction *	InsertPoint,
		DenseSet< Value * > &	PrevConditionValues,
		DenseSet< Value * > &	ConditionValues,
		DominatorTree &	DT,
		DenseSet< Instruction * > &	Unhoistables )

static

Definition at line 1038 of file ControlHeightReduction.cpp.

References assert(), checkHoistValue(), CHR_DEBUG, llvm::dbgs(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), and getBaseValues().

Referenced by llvm::RISCVTTIImpl::getShuffleCost().

Variable Documentation

◆ CHRBiasThreshold

cl::opt< double > CHRBiasThreshold("chr-bias-threshold", cl::init(0.99), cl::Hidden, cl::desc("CHR considers a branch bias greater than this ratio as biased"))	(	"chr-bias-threshold"	,
		cl::init(0.99)	,
		cl::Hidden	,
		cl::desc("CHR considers a branch bias greater than this ratio as biased")	)

static

Referenced by getCHRBiasThreshold().

◆ CHRDupThreshsold

cl::opt< unsigned > CHRDupThreshsold("chr-dup-threshold", cl::init(3), cl::Hidden, cl::desc("Max number of duplications by CHR for a region"))	(	"chr-dup-threshold"	,
		cl::init(3)	,
		cl::Hidden	,
		cl::desc("Max number of duplications by CHR for a region")	)

static

◆ CHRFunctionList

cl::opt< std::string > CHRFunctionList("chr-function-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of functions to apply CHR to"))	(	"chr-function-list"	,
		cl::init("")	,
		cl::Hidden	,
		cl::desc("Specify file to retrieve the list of functions to apply CHR to")	)

static

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRFunctions

StringSet CHRFunctions

static

Definition at line 78 of file ControlHeightReduction.cpp.

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRMergeThreshold

cl::opt< unsigned > CHRMergeThreshold("chr-merge-threshold", cl::init(2), cl::Hidden, cl::desc("CHR merges a group of N branches/selects where N >= this value"))	(	"chr-merge-threshold"	,
		cl::init(2)	,
		cl::Hidden	,
		cl::desc("CHR merges a group of N branches/selects where N >= this value")	)

static

Referenced by hasAtLeastTwoBiasedBranches().

◆ CHRModuleList

cl::opt< std::string > CHRModuleList("chr-module-list", cl::init(""), cl::Hidden, cl::desc("Specify file to retrieve the list of modules to apply CHR to"))	(	"chr-module-list"	,
		cl::init("")	,
		cl::Hidden	,
		cl::desc("Specify file to retrieve the list of modules to apply CHR to")	)

static

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRModules

StringSet CHRModules

static

Definition at line 77 of file ControlHeightReduction.cpp.

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ DisableCHR

cl::opt< bool > DisableCHR("disable-chr", cl::init(false), cl::Hidden, cl::desc("Disable CHR for all functions"))	(	"disable-chr"	,
		cl::init(false)	,
		cl::Hidden	,
		cl::desc("Disable CHR for all functions")	)

static

Referenced by shouldApply().

◆ ForceCHR

cl::opt< bool > ForceCHR("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))	(	"force-chr"	,
		cl::init(false)	,
		cl::Hidden	,
		cl::desc("Apply CHR for all functions")	)

static

Referenced by shouldApply().

Macros

Functions

Variables

Macro Definition Documentation

◆ CHR_DEBUG

◆ DEBUG_TYPE

Function Documentation

◆ assertBranchOrSelectConditionHoisted()

◆ assertCHRRegionsHaveBiasedBranchOrSelect()

◆ checkBias()

◆ checkBiasedBranch()

◆ checkBiasedSelect()

◆ checkHoistValue()

◆ CHRScopeSorter()

◆ dumpIR()

◆ dumpScopes()

◆ extractBranchProbabilities()

◆ getBaseValues()

◆ getBranchInsertPoint()

◆ getCHRBiasThreshold()

◆ getCHRConditionValuesForRegion()

◆ getSelectsInScope()

◆ hasAtLeastTwoBiasedBranches()

◆ hoistScopeConditions()

◆ hoistValue()

◆ insertTrivialPHIs()

◆ isHoistable()

◆ isHoistableInstructionType()

◆ negateICmpIfUsedByBranchOrSelectOnly()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ parseCHRFilterFiles()

◆ shouldApply()

◆ shouldSplit()

Variable Documentation

◆ CHRBiasThreshold

◆ CHRDupThreshsold

◆ CHRFunctionList

◆ CHRFunctions

◆ CHRMergeThreshold

◆ CHRModuleList

◆ CHRModules

◆ DisableCHR

◆ ForceCHR