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

	INITIALIZE_PASS_BEGIN (ControlHeightReductionLegacyPass, "chr", "Reduce control height in the hot paths", false, false) INITIALIZE_PASS_END(ControlHeightReductionLegacyPass

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 >	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 StringSet	CHRModules

static StringSet	CHRFunctions

	chr

Reduce control height in the hot	paths

Reduce control height in the hot	false

Macro Definition Documentation

◆ CHR_DEBUG

#define CHR_DEBUG ( X ) LLVM_DEBUG(X)

Definition at line 47 of file ControlHeightReduction.cpp.

◆ DEBUG_TYPE

#define DEBUG_TYPE "chr"

Definition at line 45 of file ControlHeightReduction.cpp.

Function Documentation

◆ assertBranchOrSelectConditionHoisted()

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

static

Definition at line 1659 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 1638 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 641 of file ControlHeightReduction.cpp.

References getCHRBiasThreshold(), and Threshold.

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 659 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 690 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 550 of file ControlHeightReduction.cpp.

Referenced by shouldSplit().

◆ checkMDProf()

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

static

Definition at line 604 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 1439 of file ControlHeightReduction.cpp.

◆ dumpIR()

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

static

Definition at line 453 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 1990 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 514 of file ControlHeightReduction.cpp.

References I, isHoistable(), and move.

Referenced by shouldSplit().

◆ getBranchInsertPoint()

static Instruction* getBranchInsertPoint ( RegInfo & RI )

static

Definition at line 710 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 631 of file ControlHeightReduction.cpp.

References CHRBiasThreshold.

Referenced by checkBias().

◆ getCHRConditionValuesForRegion()

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

static

Definition at line 1044 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 1125 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 1334 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

◆ hoistScopeConditions()

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

static

Definition at line 1500 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 1452 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().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	ControlHeightReductionLegacyPass	,
		"chr"	,
		"Reduce control height in the hot paths"	,
		false	,
		false
	)

◆ insertTrivialPHIs()

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

static

Definition at line 1575 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 502 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 493 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 1526 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 434 of file ControlHeightReduction.cpp.

◆ operator<<() [2/2]

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

inlinestatic

Definition at line 427 of file ControlHeightReduction.cpp.

References Stats.

◆ parseCHRFilterFiles()

static void parseCHRFilterFiles ( )

static

Definition at line 71 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 439 of file ControlHeightReduction.cpp.

References assert(), CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::StringMap< ValueTy, AllocatorTy >::count(), F, ForceCHR, llvm::ProfileSummaryInfo::hasProfileSummary(), 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 1063 of file ControlHeightReduction.cpp.

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

Variable Documentation

◆ chr

chr

Definition at line 137 of file ControlHeightReduction.cpp.

◆ 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().

◆ 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 69 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 68 of file ControlHeightReduction.cpp.

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ false

Reduce control height in the hot false

Definition at line 139 of file ControlHeightReduction.cpp.

◆ ForceCHR

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

static

Referenced by shouldApply().

◆ paths

Reduce control height in the hot paths

Definition at line 138 of file ControlHeightReduction.cpp.

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

◆ INITIALIZE_PASS_BEGIN()

◆ insertTrivialPHIs()

◆ isHoistable()

◆ isHoistableInstructionType()

◆ negateICmpIfUsedByBranchOrSelectOnly()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ parseCHRFilterFiles()

◆ shouldApply()

◆ shouldSplit()

Variable Documentation

◆ chr

◆ CHRBiasThreshold

◆ CHRFunctionList

◆ CHRFunctions

◆ CHRMergeThreshold

◆ CHRModuleList

◆ CHRModules

◆ false

◆ ForceCHR

◆ paths