#include "llvm/Transforms/Instrumentation/ControlHeightReduction.h"
#include "InstrumentationOptions.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/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 (const InstrumentationOptions &Opts, 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 (const InstrumentationOptions &Opts)
template<typename K, typename S, typename M>
static bool	checkBias (const InstrumentationOptions &Opts, K *Key, BranchProbability TrueProb, BranchProbability FalseProb, S &TrueSet, S &FalseSet, M &BiasMap)
static bool	checkBiasedBranch (const InstrumentationOptions &Opts, CondBrInst BI, Region R, DenseSet< Region * > &TrueBiasedRegionsGlobal, DenseSet< Region * > &FalseBiasedRegionsGlobal, DenseMap< Region *, BranchProbability > &BranchBiasMap)
static bool	checkBiasedSelect (const InstrumentationOptions &Opts, 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 (const InstrumentationOptions &Opts, 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 StringSet	CHRModules
static StringSet	CHRFunctions

Macro Definition Documentation

◆ CHR_DEBUG

#define CHR_DEBUG ( X )

Value:

LLVM_DEBUG(X)

X

#define X(NUM, ENUM, NAME)

Definition ELF.h:857

LLVM_DEBUG

#define LLVM_DEBUG(...)

Definition Debug.h:119

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 1637 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 1615 of file ControlHeightReduction.cpp.

References assert().

◆ checkBias()

template<typename K, typename S, typename M>

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

static

Definition at line 590 of file ControlHeightReduction.cpp.

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

Referenced by checkBiasedBranch(), and checkBiasedSelect().

◆ checkBiasedBranch()

bool checkBiasedBranch	(	const InstrumentationOptions &	Opts,
		CondBrInst *	BI,
		Region *	R,
		DenseSet< Region * > &	TrueBiasedRegionsGlobal,
		DenseSet< Region * > &	FalseBiasedRegionsGlobal,
		DenseMap< Region *, BranchProbability > &	BranchBiasMap )

static

Definition at line 609 of file ControlHeightReduction.cpp.

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

◆ checkBiasedSelect()

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

static

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

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

Referenced by checkHoistValue(), and shouldSplit().

◆ CHRScopeSorter()

bool CHRScopeSorter	(	CHRScope *	Scope1,
		CHRScope *	Scope2 )

static

Definition at line 1400 of file ControlHeightReduction.cpp.

◆ dumpIR()

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

static

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

References llvm::dbgs().

◆ extractBranchProbabilities()

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

static

Definition at line 558 of file ControlHeightReduction.cpp.

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

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 468 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 654 of file ControlHeightReduction.cpp.

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

◆ getCHRBiasThreshold()

BranchProbability getCHRBiasThreshold ( const InstrumentationOptions & Opts )

static

Definition at line 580 of file ControlHeightReduction.cpp.

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

Referenced by checkBias().

◆ getCHRConditionValuesForRegion()

DenseSet< Value * > getCHRConditionValuesForRegion ( RegInfo & RI )

static

Definition at line 1010 of file ControlHeightReduction.cpp.

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

◆ getSelectsInScope()

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

static

Definition at line 1091 of file ControlHeightReduction.cpp.

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

Referenced by getSelectsInScope().

◆ hasAtLeastTwoBiasedBranches()

bool hasAtLeastTwoBiasedBranches	(	const InstrumentationOptions &	Opts,
		CHRScope *	Scope )

static

Definition at line 1298 of file ControlHeightReduction.cpp.

◆ hoistScopeConditions()

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

static

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

References assert(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, MapTy >::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 >::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 1535 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 >::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 456 of file ControlHeightReduction.cpp.

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

Referenced by checkHoistValue(), and getBaseValues().

◆ isHoistableInstructionType()

bool isHoistableInstructionType ( Instruction * I )

static

Definition at line 447 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 1487 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::Instruction::users().

◆ operator<<() [1/2]

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

inlinestatic

Definition at line 385 of file ControlHeightReduction.cpp.

◆ operator<<() [2/2]

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

inlinestatic

Definition at line 378 of file ControlHeightReduction.cpp.

References Stats.

◆ parseCHRFilterFiles()

void parseCHRFilterFiles ( )

static

Definition at line 54 of file ControlHeightReduction.cpp.

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

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

◆ shouldApply()

bool shouldApply	(	const InstrumentationOptions &	Opts,
		Function &	F,
		ProfileSummaryInfo &	PSI )

static

Definition at line 390 of file ControlHeightReduction.cpp.

References CHRFunctions, CHRModules, F, and llvm::ProfileSummaryInfo::isFunctionEntryHot().

◆ shouldSplit()

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

static

Definition at line 1029 of file ControlHeightReduction.cpp.

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

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

Variable Documentation

◆ CHRFunctions

StringSet CHRFunctions

static

Definition at line 52 of file ControlHeightReduction.cpp.

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRModules

StringSet CHRModules

static

Definition at line 51 of file ControlHeightReduction.cpp.

Referenced by parseCHRFilterFiles(), and 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

◆ CHRFunctions

◆ CHRModules