LLVM 19.0.0git
Namespaces | Macros | Functions | Variables
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/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>

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_UNUSEDoperator<< (raw_ostream &OS, const CHRStats &Stats)
 
static raw_ostreamoperator<< (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 InstructiongetBranchInsertPoint (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< boolDisableCHR ("disable-chr", cl::init(false), cl::Hidden, cl::desc("Disable CHR for all functions"))
 
static cl::opt< boolForceCHR ("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< unsignedCHRMergeThreshold ("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< unsignedCHRDupThreshsold ("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 49 of file ControlHeightReduction.cpp.

◆ DEBUG_TYPE

#define DEBUG_TYPE   "chr"

Definition at line 47 of file ControlHeightReduction.cpp.

Function Documentation

◆ assertBranchOrSelectConditionHoisted()

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

Definition at line 1639 of file ControlHeightReduction.cpp.

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

◆ assertCHRRegionsHaveBiasedBranchOrSelect()

static void LLVM_ATTRIBUTE_UNUSED assertCHRRegionsHaveBiasedBranchOrSelect ( CHRScope *  Scope)
static

Definition at line 1618 of file ControlHeightReduction.cpp.

References assert().

◆ 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 611 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

◆ checkBiasedSelect()

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

◆ checkHoistValue()

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

◆ CHRScopeSorter()

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

Definition at line 1419 of file ControlHeightReduction.cpp.

◆ dumpIR()

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

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

◆ extractBranchProbabilities()

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

◆ getBaseValues()

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

Definition at line 490 of file ControlHeightReduction.cpp.

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

Referenced by getBaseValues(), and shouldSplit().

◆ getBranchInsertPoint()

static Instruction * getBranchInsertPoint ( RegInfo RI)
static

◆ getCHRBiasThreshold()

static BranchProbability getCHRBiasThreshold ( )
static

◆ getCHRConditionValuesForRegion()

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

◆ getSelectsInScope()

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

◆ hasAtLeastTwoBiasedBranches()

static bool hasAtLeastTwoBiasedBranches ( CHRScope *  Scope)
static

Definition at line 1314 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

◆ hoistScopeConditions()

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

Definition at line 1480 of file ControlHeightReduction.cpp.

References hoistValue().

◆ hoistValue()

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

◆ insertTrivialPHIs()

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

◆ isHoistable()

static bool isHoistable ( Instruction I,
DominatorTree DT 
)
static

◆ isHoistableInstructionType()

static bool isHoistableInstructionType ( Instruction I)
static

Definition at line 469 of file ControlHeightReduction.cpp.

References I.

Referenced by hoistValue(), and isHoistable().

◆ negateICmpIfUsedByBranchOrSelectOnly()

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

◆ operator<<() [1/2]

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

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

References OS, and Stats.

◆ parseCHRFilterFiles()

static void parseCHRFilterFiles ( )
static

◆ shouldApply()

static bool shouldApply ( Function F,
ProfileSummaryInfo PSI 
)
static

◆ shouldSplit()

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

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

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