LLVM  16.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 ()
 
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 > 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< 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 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 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 1646 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 1625 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 616 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 665 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 1426 of file ControlHeightReduction.cpp.

◆ dumpIR()

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

Definition at line 428 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 1997 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 489 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 606 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

◆ hasAtLeastTwoBiasedBranches()

static bool hasAtLeastTwoBiasedBranches ( CHRScope *  Scope)
static

Definition at line 1321 of file ControlHeightReduction.cpp.

References CHRMergeThreshold.

◆ hoistScopeConditions()

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

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

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

◆ operator<<() [2/2]

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

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

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

◆ CHRDupThreshsold

cl::opt<unsigned> CHRDupThreshsold("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"))
static

Referenced by parseCHRFilterFiles(), and shouldApply().

◆ CHRFunctions

StringSet CHRFunctions
static

Definition at line 77 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 76 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"))
static

Referenced by shouldApply().

◆ ForceCHR

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

Referenced by shouldApply().