#include "llvm/Transforms/Scalar/JumpThreading.h"
#include "ScalarOptions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.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>

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

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 ScalarOptions &Opts, 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 Constant *	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.
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 BasicBlock *	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.
static void	remapSourceAtoms (ValueToValueMapTy &VM, BasicBlock::iterator Begin, BasicBlock::iterator End)

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "jump-threading"

Definition at line 82 of file JumpThreading.cpp.

Function Documentation

◆ addPHINodeEntriesForMappedBlock()

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 line 1880 of file JumpThreading.cpp.

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

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

◆ findMostPopularDest()

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 1465 of file JumpThreading.cpp.

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

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

◆ getBestDestForJumpOnUndef()

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 899 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()

unsigned getJumpThreadDuplicationCost	(	const ScalarOptions &	Opts,
		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 408 of file JumpThreading.cpp.

References assert(), llvm::dyn_cast(), llvm::BasicBlock::getTerminator(), I, llvm::isa(), Size, llvm::StopAt, 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()

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 519 of file JumpThreading.cpp.

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

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