#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/PassManager.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <set>
#include <sstream>

Include dependency graph for ControlHeightReduction.cpp:

Namespaces
	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE "chr"

#define	CHR_DEBUG(X) LLVM_DEBUG(X)

Functions
static void	parseCHRFilterFiles ()

static raw_ostream LLVM_ATTRIBUTE_UNUSED &	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 LLVM_ATTRIBUTE_UNUSED	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	checkMDProf (MDNode *MD, 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 LLVM_ATTRIBUTE_UNUSED	assertCHRRegionsHaveBiasedBranchOrSelect (CHRScope *Scope)

static void LLVM_ATTRIBUTE_UNUSED	assertBranchOrSelectConditionHoisted (CHRScope Scope, BasicBlock PreEntryBlock)

static void LLVM_ATTRIBUTE_UNUSED	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 ) LLVM_DEBUG(X)

Definition at line 48 of file ControlHeightReduction.cpp.

◆ DEBUG_TYPE

#define DEBUG_TYPE "chr"

Definition at line 46 of file ControlHeightReduction.cpp.

Function Documentation

◆ assertBranchOrSelectConditionHoisted()

static void LLVM_ATTRIBUTE_UNUSED assertBranchOrSelectConditionHoisted	(	CHRScope *	Scope,
		BasicBlock *	PreEntryBlock
	)

static

Definition at line 1646 of file ControlHeightReduction.cpp.

References assert(), CHR_DEBUG, llvm::dbgs(), I, llvm::RISCVFenceField::R, and SI.

◆ assertCHRRegionsHaveBiasedBranchOrSelect()

static void LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect ( CHRScope * Scope )

static

Definition at line 1625 of file ControlHeightReduction.cpp.

References assert(), and SI.

◆ checkBias()

template<typename K , typename S , typename M >

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

static

Definition at line 616 of file ControlHeightReduction.cpp.

References getCHRBiasThreshold().

Referenced by checkBiasedBranch(), and checkBiasedSelect().

◆ checkBiasedBranch()

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

static

Definition at line 634 of file ControlHeightReduction.cpp.

References assert(), checkBias(), checkMDProf(), CHR_DEBUG, llvm::dbgs(), llvm::Instruction::getMetadata(), llvm::BranchInst::getSuccessor(), llvm::BranchInst::isConditional(), llvm::RISCVFenceField::R, and std::swap().

◆ checkBiasedSelect()

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

static

Definition at line 665 of file ControlHeightReduction.cpp.

References checkBias(), checkMDProf(), CHR_DEBUG, llvm::dbgs(), and SI.

◆ checkHoistValue()

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

static

Definition at line 525 of file ControlHeightReduction.cpp.

Referenced by shouldSplit().

◆ checkMDProf()

static bool checkMDProf	(	MDNode *	MD,
		BranchProbability &	TrueProb,
		BranchProbability &	FalseProb
	)

static

Definition at line 579 of file ControlHeightReduction.cpp.

References assert(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), llvm::MDString::getString(), llvm::ConstantInt::getValue(), and llvm::APInt::getZExtValue().

Referenced by checkBiasedBranch(), and checkBiasedSelect().

◆ CHRScopeSorter()

static bool CHRScopeSorter	(	CHRScope *	Scope1,
		CHRScope *	Scope2
	)

static

Definition at line 1426 of file ControlHeightReduction.cpp.

◆ dumpIR()

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

static

Definition at line 428 of file ControlHeightReduction.cpp.

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

◆ dumpScopes()

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

static

Definition at line 1997 of file ControlHeightReduction.cpp.

References llvm::dbgs().

◆ getBaseValues()

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

static

Definition at line 489 of file ControlHeightReduction.cpp.

References I, isHoistable(), and move.

Referenced by shouldSplit().

◆ getBranchInsertPoint()

static Instruction* getBranchInsertPoint ( RegInfo & RI )

static

Definition at line 685 of file ControlHeightReduction.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::contains(), llvm::BasicBlock::getTerminator(), I, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), llvm::RISCVFenceField::R, and SI.

◆ getCHRBiasThreshold()

static BranchProbability getCHRBiasThreshold ( )

static

Definition at line 606 of file ControlHeightReduction.cpp.

References CHRBiasThreshold.

Referenced by checkBias().

◆ getCHRConditionValuesForRegion()

static DenseSet<Value *> getCHRConditionValuesForRegion ( RegInfo & RI )

static

Definition at line 1031 of file ControlHeightReduction.cpp.

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

◆ getSelectsInScope()

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

static

Definition at line 1112 of file ControlHeightReduction.cpp.

References llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), and SI.

◆ hasAtLeastTwoBiasedBranches()

static bool hasAtLeastTwoBiasedBranches ( CHRScope * Scope )

static

Definition at line 1321 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

◆ hoistScopeConditions()

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

static

Definition at line 1487 of file ControlHeightReduction.cpp.

References hoistValue(), llvm::RISCVFenceField::R, and SI.

◆ hoistValue()

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

static

Definition at line 1439 of file ControlHeightReduction.cpp.

References assert(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), I, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), isHoistableInstructionType(), IT, and llvm::RISCVFenceField::R.

Referenced by hoistScopeConditions().

◆ insertTrivialPHIs()

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

static

Definition at line 1562 of file ControlHeightReduction.cpp.

References llvm::PHINode::addIncoming(), BB, CHR_DEBUG, llvm::dbgs(), llvm::BasicBlock::front(), I, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), llvm::pred_size(), llvm::predecessors(), and Users.

◆ isHoistable()

static bool isHoistable	(	Instruction *	I,
		DominatorTree &	DT
	)

static

Definition at line 477 of file ControlHeightReduction.cpp.

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

Referenced by checkHoistValue(), and getBaseValues().

◆ isHoistableInstructionType()

static bool isHoistableInstructionType ( Instruction * I )

static

Definition at line 468 of file ControlHeightReduction.cpp.

References I.

Referenced by hoistValue(), and isHoistable().

◆ negateICmpIfUsedByBranchOrSelectOnly()

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

static

Definition at line 1513 of file ControlHeightReduction.cpp.

References assert(), llvm::CmpInst::getPredicate(), llvm_unreachable, llvm::CmpInst::setPredicate(), SI, and llvm::Value::users().

◆ operator<<() [1/2]

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

inlinestatic

Definition at line 407 of file ControlHeightReduction.cpp.

◆ operator<<() [2/2]

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

inlinestatic

Definition at line 400 of file ControlHeightReduction.cpp.

References Stats.

◆ parseCHRFilterFiles()

static void parseCHRFilterFiles ( )

static

Definition at line 79 of file ControlHeightReduction.cpp.

References CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::errs(), exit(), llvm::MemoryBuffer::getFile(), llvm::StringSet< AllocatorTy >::insert(), and llvm::StringRef::split().

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

◆ shouldApply()

static bool shouldApply	(	Function &	F,
		ProfileSummaryInfo &	PSI
	)

static

Definition at line 412 of file ControlHeightReduction.cpp.

References CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::StringMap< ValueTy, AllocatorTy >::count(), DisableCHR, F, ForceCHR, and llvm::ProfileSummaryInfo::isFunctionEntryHot().

◆ shouldSplit()

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

static

Definition at line 1050 of file ControlHeightReduction.cpp.

References assert(), checkHoistValue(), CHR_DEBUG, llvm::dbgs(), and getBaseValues().

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

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

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

static

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRFunctions

StringSet CHRFunctions

static

Definition at line 77 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"))

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

static

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRModules

StringSet CHRModules

static

Definition at line 76 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"))

static

Referenced by shouldApply().

◆ ForceCHR

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

static

Referenced by shouldApply().

Namespaces

Macros

Functions

Variables

Macro Definition Documentation

◆ CHR_DEBUG

◆ DEBUG_TYPE

Function Documentation

◆ assertBranchOrSelectConditionHoisted()

◆ assertCHRRegionsHaveBiasedBranchOrSelect()

◆ checkBias()

◆ checkBiasedBranch()

◆ checkBiasedSelect()

◆ checkHoistValue()

◆ checkMDProf()

◆ CHRScopeSorter()

◆ dumpIR()

◆ dumpScopes()

◆ 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