Movatterモバイル変換

#include "llvm/Transforms/Scalar/JumpThreading.h"
#include "llvm/ADT/DenseMap.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 <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 branchblocks duplicated to eliminate phi")

static void	updatePredecessorProfileMetadata (PHINode PN,BasicBlock BB)

staticbool	replaceFoldableUses (Instruction Cond,Value ToVal,BasicBlock *KnownAtEndOfBB)

staticunsigned	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.

staticConstant *	getKnownConstant (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.

staticunsigned	getBestDestForJumpOnUndef (BasicBlock *BB)
	GetBestDestForBranchOnUndef - If we determine that the specified block ends in an undefined jump, decide which block is best to revector to.

staticbool	hasAddressTakenAndUsed (BasicBlock *BB)

staticbool	isOpDefinedInBlock (Value Op,BasicBlock BB)
	Return true if Op is an instruction defined in the given block.

staticBasicBlock *	findMostPopularDest (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,ValueToValueMapTy &ValueMap)
	addPHINodeEntriesForMappedBlock - We're adding 'NewPred' as a new predecessor to the PHIBB block.

Variables
staticcl::opt<unsigned >	BBDuplicateThreshold ("jump-threading-threshold",cl::desc("Maxblock size to duplicatefor jump threading"), cl::init(6), cl::Hidden)

staticcl::opt<unsigned >	ImplicationSearchThreshold ("jump-threading-implication-search-threshold",cl::desc("The number of predecessors to searchfor a stronger " "condition touse tothread over a weaker condition"), cl::init(3), cl::Hidden)

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

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

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "jump-threading"

Definition at line80 of fileJumpThreading.cpp.

Function Documentation

◆ addPHINodeEntriesForMappedBlock()

static void addPHINodeEntriesForMappedBlock	(	BasicBlock *	PHIBB,
		BasicBlock *	OldPred,
		BasicBlock *	NewPred,
		ValueToValueMapTy &	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 line1867 of fileJumpThreading.cpp.

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

Referenced byllvm::JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(),llvm::JumpThreadingPass::threadEdge(), andllvm::JumpThreadingPass::threadThroughTwoBasicBlocks().

◆ findMostPopularDest()

staticBasicBlock * 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 line1466 of fileJumpThreading.cpp.

Referencesassert(),llvm::max_element(), andllvm::successors().

Referenced byllvm::JumpThreadingPass::processThreadableEdges().

◆ getBestDestForJumpOnUndef()

staticunsigned getBestDestForJumpOnUndef

(

BasicBlock *

)

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 line918 of fileJumpThreading.cpp.

Referencesllvm::Instruction::getNumSuccessors(),llvm::Instruction::getSuccessor(),llvm::BasicBlock::getTerminator(), andllvm::pred_size().

Referenced byllvm::JumpThreadingPass::processBlock(), andllvm::JumpThreadingPass::processThreadableEdges().

◆ getJumpThreadDuplicationCost()

staticunsigned 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 line426 of fileJumpThreading.cpp.

Referencesassert(),llvm::TargetTransformInfo::getInstructionCost(),llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(),llvm::BasicBlock::getTerminator(),I,PhiDuplicateThreshold,Size,llvm::TargetTransformInfo::TCC_Free, andllvm::TargetTransformInfo::TCK_SizeAndLatency.

Referenced byllvm::JumpThreadingPass::duplicateCondBranchOnPHIIntoPred(),llvm::JumpThreadingPass::maybethreadThroughTwoBasicBlocks(),llvm::JumpThreadingPass::threadGuard(), andllvm::JumpThreadingPass::tryThreadEdge().

◆ getKnownConstant()

staticConstant * 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 line538 of fileJumpThreading.cpp.

Referencesllvm::Value::stripPointerCasts(), andllvm::jumpthreading::WantBlockAddress.

Referenced byllvm::JumpThreadingPass::computeValueKnownInPredecessorsImpl(), andllvm::JumpThreadingPass::processBlock().

◆ hasAddressTakenAndUsed()

staticbool hasAddressTakenAndUsed

(

BasicBlock *

)

static

Definition at line936 of fileJumpThreading.cpp.

Referencesllvm::BlockAddress::get(),llvm::BasicBlock::hasAddressTaken(),llvm::Constant::removeDeadConstantUsers(), andllvm::Value::use_empty().

Referenced byllvm::JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred().

◆ isOpDefinedInBlock()

staticbool isOpDefinedInBlock	(	Value *	Op,
		BasicBlock *	BB
	)

static

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

Definition at line1211 of fileJumpThreading.cpp.

Referenced byllvm::JumpThreadingPass::simplifyPartiallyRedundantLoad().

◆ replaceFoldableUses()

staticbool replaceFoldableUses	(	Instruction *	Cond,
		Value *	ToVal,
		BasicBlock *	KnownAtEndOfBB
	)

static

Definition at line392 of fileJumpThreading.cpp.

Referencesassert(),Cond,llvm::filterDbgVars(),llvm::Value::getType(),I,llvm::isGuaranteedToTransferExecutionToSuccessor(),llvm::replaceNonLocalUsesWith(), andllvm::reverse().

Referenced byllvm::JumpThreadingPass::processBlock(), andllvm::JumpThreadingPass::processThreadableEdges().

◆ STATISTIC()[1/3]

STATISTIC	(	NumDupes	,
		"Number of branchblocks 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

Definition at line147 of fileJumpThreading.cpp.

Referencesllvm::SmallPtrSetImpl< PtrType >::count(),llvm::extractBranchWeights(),llvm::BranchProbability::getBranchProbability(),llvm::BranchProbability::getCompl(),llvm::PHINode::getIncomingBlock(),llvm::PHINode::getIncomingValue(),llvm::BranchProbability::getNumerator(),llvm::PHINode::getNumIncomingValues(),llvm::BranchInst::getSuccessor(),llvm::BasicBlock::getTerminator(),llvm::Value::getType(),llvm::hasBranchWeightOrigin(),llvm::SmallPtrSetImpl< PtrType >::insert(),llvm::BranchInst::isConditional(),llvm::Type::isIntegerTy(),llvm::ConstantInt::isOne(), andllvm::setBranchWeights().

Referenced byllvm::JumpThreadingPass::processBlock().

Variable Documentation

◆ BBDuplicateThreshold

cl::opt<unsigned > BBDuplicateThreshold("jump-threading-threshold",cl::desc("Maxblock size to duplicatefor jump threading"), cl::init(6), cl::Hidden)	(	"jump-threading-threshold"	,
		cl::desc("Maxblock size to duplicatefor jump threading")	,
		cl::init(6)	,
		cl::Hidden
	)

static

Referenced byllvm::JumpThreadingPass::JumpThreadingPass(), andllvm::JumpThreadingPass::runImpl().

◆ ImplicationSearchThreshold

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

static

Referenced byllvm::JumpThreadingPass::processImpliedCondition().

◆ PhiDuplicateThreshold

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

static

Referenced bygetJumpThreadDuplicationCost().

◆ ThreadAcrossLoopHeaders

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

static

Referenced byllvm::JumpThreadingPass::runImpl().

Movatterモバイル変換

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ addPHINodeEntriesForMappedBlock()

◆ findMostPopularDest()

◆ getBestDestForJumpOnUndef()

◆ getJumpThreadDuplicationCost()

◆ getKnownConstant()

◆ hasAddressTakenAndUsed()

◆ isOpDefinedInBlock()

◆ replaceFoldableUses()

◆ STATISTIC()[1/3]

◆ STATISTIC()[2/3]

◆ STATISTIC()[3/3]

◆ updatePredecessorProfileMetadata()

Variable Documentation

◆ BBDuplicateThreshold

◆ ImplicationSearchThreshold

◆ PhiDuplicateThreshold

◆ ThreadAcrossLoopHeaders