LLVM  15.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/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:

Go to the source code of this file.

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_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 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 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< bool > ForceCHR ("force-chr", cl::init(false), cl::Hidden, cl::desc("Apply CHR for all functions"))
 
static cl::opt< doubleCHRBiasThreshold ("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 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 1672 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 1651 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 642 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

Definition at line 691 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

◆ checkMDProf()

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

◆ CHRScopeSorter()

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

Definition at line 1452 of file ControlHeightReduction.cpp.

◆ dumpIR()

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

Definition at line 454 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 2002 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 515 of file ControlHeightReduction.cpp.

References I, isHoistable(), and move.

Referenced by shouldSplit().

◆ getBranchInsertPoint()

static Instruction* getBranchInsertPoint ( RegInfo RI)
static

◆ getCHRBiasThreshold()

static BranchProbability getCHRBiasThreshold ( )
static

Definition at line 632 of file ControlHeightReduction.cpp.

References CHRBiasThreshold.

Referenced by checkBias().

◆ getCHRConditionValuesForRegion()

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

◆ getSelectsInScope()

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

Definition at line 1138 of file ControlHeightReduction.cpp.

References SI.

◆ hasAtLeastTwoBiasedBranches()

static bool hasAtLeastTwoBiasedBranches ( CHRScope *  Scope)
static

Definition at line 1347 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

◆ hoistScopeConditions()

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

Definition at line 1513 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

◆ 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

◆ isHoistable()

static bool isHoistable ( Instruction I,
DominatorTree DT 
)
static

◆ isHoistableInstructionType()

static bool isHoistableInstructionType ( Instruction I)
static

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

◆ operator<<() [2/2]

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

Definition at line 428 of file ControlHeightReduction.cpp.

References 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

◆ chr

chr

Definition at line 138 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 70 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

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

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ false

Reduce control height in the hot false

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