LLVM 19.0.0git
Macros | Functions | Variables
JumpThreading.cpp File Reference
#include "llvm/Transforms/Scalar/JumpThreading.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "jump-threading"
 

Functions

 STATISTIC (NumThreads, "Number of jumps threaded")
 
 STATISTIC (NumFolds, "Number of terminators folded")
 
 STATISTIC (NumDupes, "Number of branch blocks duplicated to eliminate phi")
 
static void updatePredecessorProfileMetadata (PHINode *PN, BasicBlock *BB)
 
static bool replaceFoldableUses (Instruction *Cond, Value *ToVal, BasicBlock *KnownAtEndOfBB)
 
static unsigned getJumpThreadDuplicationCost (const TargetTransformInfo *TTI, BasicBlock *BB, Instruction *StopAt, unsigned Threshold)
 Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction to thread across it.
 
static ConstantgetKnownConstant (Value *Val, ConstantPreference Preference)
 getKnownConstant - Helper method to determine if we can thread over a terminator with the given value as its condition, and if so what value to use for that.
 
static unsigned getBestDestForJumpOnUndef (BasicBlock *BB)
 GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump, decide which block is best to revector to.
 
static bool hasAddressTakenAndUsed (BasicBlock *BB)
 
static bool isOpDefinedInBlock (Value *Op, BasicBlock *BB)
 Return true if Op is an instruction defined in the given block.
 
static BasicBlockfindMostPopularDest (BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)
 findMostPopularDest - The specified list contains multiple possible threadable destinations.
 
static void addPHINodeEntriesForMappedBlock (BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, DenseMap< Instruction *, Value * > &ValueMap)
 addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.
 

Variables

static cl::opt< unsignedBBDuplicateThreshold ("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
 
static cl::opt< unsignedImplicationSearchThreshold ("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden)
 
static cl::opt< unsignedPhiDuplicateThreshold ("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden)
 
static cl::opt< boolThreadAcrossLoopHeaders ("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden)
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "jump-threading"

Definition at line 82 of file JumpThreading.cpp.

Function Documentation

◆ addPHINodeEntriesForMappedBlock()

static void addPHINodeEntriesForMappedBlock ( BasicBlock PHIBB,
BasicBlock OldPred,
BasicBlock NewPred,
DenseMap< Instruction *, Value * > &  ValueMap 
)
static

addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.

If it has PHI nodes, add entries for NewPred using the entries from OldPred (suitably mapped).

Definition at line 1876 of file JumpThreading.cpp.

References llvm::ValueMap< KeyT, ValueT, Config >::end(), llvm::ValueMap< KeyT, ValueT, Config >::find(), I, IV, and llvm::BasicBlock::phis().

Referenced by llvm::JumpThreadingPass::threadEdge(), and llvm::JumpThreadingPass::threadThroughTwoBasicBlocks().

◆ findMostPopularDest()

static BasicBlock * findMostPopularDest ( BasicBlock BB,
const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &  PredToDestList 
)
static

findMostPopularDest - The specified list contains multiple possible threadable destinations.

Pick the one that occurs the most frequently in the list.

Definition at line 1478 of file JumpThreading.cpp.

References assert(), llvm::max_element(), and llvm::successors().

Referenced by llvm::JumpThreadingPass::processThreadableEdges().

◆ getBestDestForJumpOnUndef()

static unsigned getBestDestForJumpOnUndef ( BasicBlock BB)
static

GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump, decide which block is best to revector to.

Since we can pick an arbitrary destination, we pick the successor with the fewest predecessors. This should reduce the in-degree of the others.

Definition at line 930 of file JumpThreading.cpp.

References llvm::Instruction::getNumSuccessors(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), and llvm::pred_size().

Referenced by llvm::JumpThreadingPass::processBlock(), and llvm::JumpThreadingPass::processThreadableEdges().

◆ getJumpThreadDuplicationCost()

static unsigned getJumpThreadDuplicationCost ( const TargetTransformInfo TTI,
BasicBlock BB,
Instruction StopAt,
unsigned  Threshold 
)
static

Return the cost of duplicating a piece of this block from first non-phi and before StopAt instruction to thread across it.

Stop scanning the block when exceeding the threshold. If duplication is impossible, returns ~0U.

Ignore PHI nodes, these will be flattened when duplication happens.

Definition at line 427 of file JumpThreading.cpp.

References assert(), llvm::TargetTransformInfo::getInstructionCost(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), I, PhiDuplicateThreshold, Size, llvm::TargetTransformInfo::TCC_Free, and llvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced by llvm::JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(), llvm::JumpThreadingPass::maybethreadThroughTwoBasicBlocks(), llvm::JumpThreadingPass::threadGuard(), and llvm::JumpThreadingPass::tryThreadEdge().

◆ getKnownConstant()

static Constant * getKnownConstant ( Value Val,
ConstantPreference  Preference 
)
static

getKnownConstant - Helper method to determine if we can thread over a terminator with the given value as its condition, and if so what value to use for that.

What kind of value this is depends on whether we want an integer or a block address, but an undef is always accepted. Returns null if Val is null or not an appropriate constant.

Definition at line 539 of file JumpThreading.cpp.

References llvm::Value::stripPointerCasts(), and llvm::jumpthreading::WantBlockAddress.

Referenced by llvm::JumpThreadingPass::computeValueKnownInPredecessorsImpl(), and llvm::JumpThreadingPass::processBlock().

◆ hasAddressTakenAndUsed()

static bool hasAddressTakenAndUsed ( BasicBlock BB)
static

◆ isOpDefinedInBlock()

static bool isOpDefinedInBlock ( Value Op,
BasicBlock BB 
)
static

Return true if Op is an instruction defined in the given block.

Definition at line 1225 of file JumpThreading.cpp.

Referenced by llvm::JumpThreadingPass::simplifyPartiallyRedundantLoad().

◆ replaceFoldableUses()

static bool replaceFoldableUses ( Instruction Cond,
Value ToVal,
BasicBlock KnownAtEndOfBB 
)
static

◆ STATISTIC() [1/3]

STATISTIC ( NumDupes  ,
"Number of branch blocks duplicated to eliminate phi"   
)

◆ STATISTIC() [2/3]

STATISTIC ( NumFolds  ,
"Number of terminators folded"   
)

◆ STATISTIC() [3/3]

STATISTIC ( NumThreads  ,
"Number of jumps threaded"   
)

◆ updatePredecessorProfileMetadata()

static void updatePredecessorProfileMetadata ( PHINode PN,
BasicBlock BB 
)
static

Variable Documentation

◆ BBDuplicateThreshold

cl::opt< unsigned > BBDuplicateThreshold("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden) ( "jump-threading-threshold"  ,
cl::desc("Max block size to duplicate for jump threading")  ,
cl::init(6)  ,
cl::Hidden   
)
static

◆ ImplicationSearchThreshold

cl::opt< unsigned > ImplicationSearchThreshold("jump-threading-implication-search-threshold", cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition"), cl::init(3), cl::Hidden) ( "jump-threading-implication-search-threshold"  ,
cl::desc("The number of predecessors to search for a stronger " "condition to use to thread over a weaker condition")  ,
cl::init(3)  ,
cl::Hidden   
)
static

◆ PhiDuplicateThreshold

cl::opt< unsigned > PhiDuplicateThreshold("jump-threading-phi-threshold", cl::desc("Max PHIs in BB to duplicate for jump threading"), cl::init(76), cl::Hidden) ( "jump-threading-phi-threshold"  ,
cl::desc("Max PHIs in BB to duplicate for jump threading")  ,
cl::init(76)  ,
cl::Hidden   
)
static

◆ ThreadAcrossLoopHeaders

cl::opt< bool > ThreadAcrossLoopHeaders("jump-threading-across-loop-headers", cl::desc("Allow JumpThreading to thread across loop headers, for testing"), cl::init(false), cl::Hidden) ( "jump-threading-across-loop-headers"  ,
cl::desc("Allow JumpThreading to thread across loop headers, for testing")  ,
cl::init(false)  ,
cl::Hidden   
)
static