JumpThreading.cpp File Reference

#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"

Include dependency graph for JumpThreading.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "jump-threading"
Enumerations
enum	ConstantPreference
Functions
	STATISTIC (NumThreads,"Number of jumps threaded")
	STATISTIC (NumFolds,"Number of terminators folded")
	STATISTIC (NumDupes,"Number of branch blocks duplicated to eliminate phi")
	INITIALIZE_PASS_BEGIN (JumpThreading,"jump-threading","Jump Threading", false, false) INITIALIZE_PASS_END(JumpThreading
static unsigned	getJumpThreadDuplicationCost (const BasicBlock *BB, unsigned Threshold)
static Constant *	getKnownConstant (Value *Val, ConstantPreference Preference)
static unsigned	GetBestDestForJumpOnUndef (BasicBlock *BB)
static bool	hasAddressTakenAndUsed (BasicBlock *BB)
static BasicBlock *	FindMostPopularDest (BasicBlock *BB, const SmallVectorImpl< std::pair< BasicBlock *, BasicBlock * > > &PredToDestList)
static void	AddPHINodeEntriesForMappedBlock (BasicBlock *PHIBB, BasicBlock *OldPred, BasicBlock *NewPred, DenseMap< Instruction *, Value * > &ValueMap)
Variables
static cl::opt< unsigned >	Threshold ("jump-threading-threshold", cl::desc("Max block size to duplicate for jump threading"), cl::init(6), cl::Hidden)
jump	threading
jump Jump	Threading
jump Jump	false

---

Define Documentation

#define DEBUG_TYPE   "jump-threading"

Definition at line 41 of file JumpThreading.cpp.

---

Enumeration Type Documentation

enum ConstantPreference

Definition at line 59 of file JumpThreading.cpp.

---

Function Documentation

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

References llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), llvm::dyn_cast(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::find(), and llvm::PHINode::getIncomingValueForBlock().

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

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::begin(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::clear(), llvm::SmallVectorBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::end(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::TerminatorInst::getNumSuccessors(), llvm::TerminatorInst::getSuccessor(), llvm::BasicBlock::getTerminator(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().

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

References llvm::TerminatorInst::getNumSuccessors(), llvm::TerminatorInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::pred_begin(), and llvm::pred_end().

static unsigned getJumpThreadDuplicationCost	(	const BasicBlock *	BB,
		unsigned	Threshold
	)		[static]

getJumpThreadDuplicationCost - Return the cost of duplicating this block to thread across it. Stop scanning the block when passing the threshold.

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

Definition at line 239 of file JumpThreading.cpp.

References llvm::BasicBlock::getFirstNonPHI(), and I.

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

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

static bool hasAddressTakenAndUsed

(

BasicBlock *

BB

)

[static]

Definition at line 647 of file JumpThreading.cpp.

References llvm::BlockAddress::get(), llvm::BasicBlock::hasAddressTaken(), llvm::Constant::removeDeadConstantUsers(), and llvm::Value::use_empty().

INITIALIZE_PASS_BEGIN	(	JumpThreading	,
		"jump-threading"	,
		"Jump Threading"	,
		false	,
		false
	)

STATISTIC	(	NumThreads	,
		"Number of jumps threaded"
	)

STATISTIC	(	NumFolds	,
		"Number of terminators folded"
	)

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

---

Variable Documentation

jump Jump false

Definition at line 146 of file JumpThreading.cpp.

jump threading

Definition at line 146 of file JumpThreading.cpp.

jump Jump Threading

Definition at line 146 of file JumpThreading.cpp.

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