LLVM
15.0.0git
|
#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>
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_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 | 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 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 > | 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 StringSet | CHRModules |
static StringSet | CHRFunctions |
chr | |
Reduce control height in the hot | paths |
Reduce control height in the hot | false |
#define CHR_DEBUG | ( | X | ) | LLVM_DEBUG(X) |
Definition at line 48 of file ControlHeightReduction.cpp.
#define DEBUG_TYPE "chr" |
Definition at line 46 of file ControlHeightReduction.cpp.
|
static |
Definition at line 1672 of file ControlHeightReduction.cpp.
References assert(), CHR_DEBUG, llvm::dbgs(), I, llvm::RISCVFenceField::R, and SI.
|
static |
Definition at line 1651 of file ControlHeightReduction.cpp.
|
static |
Definition at line 642 of file ControlHeightReduction.cpp.
References getCHRBiasThreshold().
Referenced by checkBiasedBranch(), and checkBiasedSelect().
|
static |
Definition at line 660 of file ControlHeightReduction.cpp.
References assert(), checkBias(), checkMDProf(), CHR_DEBUG, llvm::dbgs(), llvm::Instruction::getMetadata(), llvm::BranchInst::getSuccessor(), llvm::BranchInst::isConditional(), llvm::RISCVFenceField::R, and std::swap().
|
static |
Definition at line 691 of file ControlHeightReduction.cpp.
References checkBias(), checkMDProf(), CHR_DEBUG, llvm::dbgs(), and SI.
|
static |
Definition at line 551 of file ControlHeightReduction.cpp.
References assert(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::begin(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), I, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), and isHoistable().
Referenced by shouldSplit().
|
static |
Definition at line 605 of file ControlHeightReduction.cpp.
References assert(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), llvm::MDString::getString(), llvm::ConstantInt::getValue(), and llvm::APInt::getZExtValue().
Referenced by checkBiasedBranch(), and checkBiasedSelect().
|
static |
Definition at line 1452 of file ControlHeightReduction.cpp.
|
static |
Definition at line 454 of file ControlHeightReduction.cpp.
References CHR_DEBUG, llvm::dbgs(), F, and Stats.
|
static |
Definition at line 2002 of file ControlHeightReduction.cpp.
References llvm::dbgs().
|
static |
Definition at line 515 of file ControlHeightReduction.cpp.
References I, isHoistable(), and move.
Referenced by shouldSplit().
|
static |
Definition at line 711 of file ControlHeightReduction.cpp.
References assert(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::contains(), llvm::BasicBlock::getTerminator(), I, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), llvm::RISCVFenceField::R, and SI.
|
static |
Definition at line 632 of file ControlHeightReduction.cpp.
References CHRBiasThreshold.
Referenced by checkBias().
Definition at line 1057 of file ControlHeightReduction.cpp.
References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and SI.
|
static |
Definition at line 1138 of file ControlHeightReduction.cpp.
References SI.
|
static |
Definition at line 1347 of file ControlHeightReduction.cpp.
References CHRMergeThreshold.
|
static |
Definition at line 1513 of file ControlHeightReduction.cpp.
References hoistValue(), llvm::RISCVFenceField::R, and SI.
|
static |
Definition at line 1465 of file ControlHeightReduction.cpp.
References assert(), CHR_DEBUG, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), I, llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), isHoistableInstructionType(), IT, and llvm::RISCVFenceField::R.
Referenced by hoistScopeConditions().
INITIALIZE_PASS_BEGIN | ( | ControlHeightReductionLegacyPass | , |
"chr" | , | ||
"Reduce control height in the hot paths" | , | ||
false | , | ||
false | |||
) |
|
static |
Definition at line 1588 of file ControlHeightReduction.cpp.
References llvm::PHINode::addIncoming(), BB, CHR_DEBUG, llvm::dbgs(), llvm::BasicBlock::front(), I, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), llvm::pred_size(), llvm::predecessors(), and Users.
|
static |
Definition at line 503 of file ControlHeightReduction.cpp.
References I, isHoistableInstructionType(), and llvm::isSafeToSpeculativelyExecute().
Referenced by checkHoistValue(), and getBaseValues().
|
static |
Definition at line 494 of file ControlHeightReduction.cpp.
References I.
Referenced by hoistValue(), and isHoistable().
|
static |
Definition at line 1539 of file ControlHeightReduction.cpp.
References assert(), llvm::CmpInst::getPredicate(), llvm_unreachable, llvm::CmpInst::setPredicate(), SI, and llvm::Value::users().
|
inlinestatic |
Definition at line 435 of file ControlHeightReduction.cpp.
|
inlinestatic |
Definition at line 428 of file ControlHeightReduction.cpp.
References Stats.
|
static |
Definition at line 72 of file ControlHeightReduction.cpp.
References CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::errs(), exit(), llvm::MemoryBuffer::getFile(), llvm::StringSet< AllocatorTy >::insert(), and llvm::StringRef::split().
Referenced by llvm::ControlHeightReductionPass::ControlHeightReductionPass().
|
static |
Definition at line 440 of file ControlHeightReduction.cpp.
References assert(), CHRFunctionList, CHRFunctions, CHRModuleList, CHRModules, llvm::StringMap< ValueTy, AllocatorTy >::count(), F, ForceCHR, llvm::ProfileSummaryInfo::hasProfileSummary(), and llvm::ProfileSummaryInfo::isFunctionEntryHot().
|
static |
Definition at line 1076 of file ControlHeightReduction.cpp.
References assert(), checkHoistValue(), CHR_DEBUG, llvm::dbgs(), and getBaseValues().
chr |
Definition at line 138 of file ControlHeightReduction.cpp.
|
static |
Referenced by getCHRBiasThreshold().
|
static |
Referenced by parseCHRFilterFiles(), and shouldApply().
|
static |
Definition at line 70 of file ControlHeightReduction.cpp.
Referenced by parseCHRFilterFiles(), and shouldApply().
|
static |
Referenced by hasAtLeastTwoBiasedBranches().
|
static |
Referenced by parseCHRFilterFiles(), and shouldApply().
|
static |
Definition at line 69 of file ControlHeightReduction.cpp.
Referenced by parseCHRFilterFiles(), and shouldApply().
Reduce control height in the hot false |
Definition at line 140 of file ControlHeightReduction.cpp.
|
static |
Referenced by shouldApply().
Reduce control height in the hot paths |
Definition at line 139 of file ControlHeightReduction.cpp.