ControlHeightReduction.cpp File Reference

#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/IR/ProfDataUtils.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 <optional>
#include <set>
#include <sstream>

Include dependency graph for ControlHeightReduction.cpp:

Go to the source code of this file.

Namespaces
namespace	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	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 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 50 of file ControlHeightReduction.cpp.

DEBUG_TYPE

#define DEBUG_TYPE   "chr"

Definition at line 48 of file ControlHeightReduction.cpp.

Function Documentation

assertBranchOrSelectConditionHoisted()

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

static

Definition at line 1640 of file ControlHeightReduction.cpp.

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

assertCHRRegionsHaveBiasedBranchOrSelect()

static void LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect ( CHRScope *  Scope )

static

Definition at line 1619 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 612 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 630 of file ControlHeightReduction.cpp.

References assert(), checkBias(), CHR_DEBUG, llvm::dbgs(), extractBranchProbabilities(), llvm::BranchInst::getSuccessor(), llvm::BranchInst::isConditional(), 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 660 of file ControlHeightReduction.cpp.

References checkBias(), CHR_DEBUG, llvm::dbgs(), extractBranchProbabilities(), 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 527 of file ControlHeightReduction.cpp.

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

Referenced by checkHoistValue(), and shouldSplit().

CHRScopeSorter()

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

static

Definition at line 1420 of file ControlHeightReduction.cpp.

dumpIR()

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

static

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

References llvm::dbgs().

extractBranchProbabilities()

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

static

Definition at line 581 of file ControlHeightReduction.cpp.

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

Referenced by checkBiasedBranch(), and checkBiasedSelect().

getBaseValues()

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

static

Definition at line 491 of file ControlHeightReduction.cpp.

References getBaseValues(), I, and isHoistable().

Referenced by getBaseValues(), and shouldSplit().

getBranchInsertPoint()

static Instruction * getBranchInsertPoint ( RegInfo &  RI )

static

Definition at line 679 of file ControlHeightReduction.cpp.

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

getCHRBiasThreshold()

static BranchProbability getCHRBiasThreshold ( )

static

Definition at line 602 of file ControlHeightReduction.cpp.

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

Referenced by checkBias().

getCHRConditionValuesForRegion()

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

static

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

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

Referenced by getSelectsInScope().

hasAtLeastTwoBiasedBranches()

static bool hasAtLeastTwoBiasedBranches ( CHRScope *  Scope )

static

Definition at line 1315 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

hoistScopeConditions()

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

static

Definition at line 1481 of file ControlHeightReduction.cpp.

References hoistValue(), 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 1433 of file ControlHeightReduction.cpp.

References assert(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), hoistValue(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), isHoistableInstructionType(), and IT.

Referenced by hoistScopeConditions(), and hoistValue().

insertTrivialPHIs()

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

static

Definition at line 1556 of file ControlHeightReduction.cpp.

References llvm::PHINode::addIncoming(), CHR_DEBUG, llvm::SetVector< T, Vector, Set >::contains(), llvm::PHINode::Create(), llvm::dbgs(), llvm::BasicBlock::front(), I, llvm::SetVector< T, Vector, Set >::insert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::pred_size(), llvm::predecessors(), and Users.

isHoistable()

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

static

Definition at line 479 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 470 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 1507 of file ControlHeightReduction.cpp.

References assert(), llvm::CmpInst::getInversePredicate(), 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 409 of file ControlHeightReduction.cpp.

References OS.

operator<<() [2/2]

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

inlinestatic

Definition at line 402 of file ControlHeightReduction.cpp.

References OS, and Stats.

parseCHRFilterFiles()

static void parseCHRFilterFiles ( )

static

Definition at line 81 of file ControlHeightReduction.cpp.

References CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::errs(), 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 414 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 1044 of file ControlHeightReduction.cpp.

References assert(), checkHoistValue(), CHR_DEBUG, llvm::dbgs(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::empty(), 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")) ( "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 79 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 78 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().