#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/DIBuilder.h"
#include "llvm/DebugInfo.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalAlias.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"

Include dependency graph for Local.cpp:

Typedefs
typedef SmallVector < BasicBlock *, 16 >	PredBlockVector

typedef DenseMap< BasicBlock , Value >	IncomingValueMap

Functions
	STATISTIC (NumRemoved,"Number of unreachable basic blocks removed")

static bool	areAllUsesEqual (Instruction *I)

static bool	CanMergeValues (Value First, Value Second)

static bool	CanPropagatePredecessorsForPHIs (BasicBlock BB, BasicBlock Succ)

static Value *	selectIncomingValueForBlock (Value OldVal, BasicBlock BB, IncomingValueMap &IncomingValues)
	Determines the value to use as the phi node input for a block. More...

static void	gatherIncomingValuesToPhi (PHINode *PN, IncomingValueMap &IncomingValues)
	Create a map from block to value for the operands of a given phi. More...

static void	replaceUndefValuesInPhi (PHINode *PN, const IncomingValueMap &IncomingValues)
	Replace the incoming undef values to a phi with the values from a block-to-value map. More...

static void	redirectValuesFromPredecessorsToPhi (BasicBlock BB, const PredBlockVector &BBPreds, PHINode PN)
	Replace a value flowing from a block to a phi with potentially multiple instances of that value flowing from the block's predecessors to the phi. More...

static unsigned	enforceKnownAlignment (Value V, unsigned Align, unsigned PrefAlign, const DataLayout TD)

static bool	LdStHasDebugValue (DIVariable &DIVar, Instruction *I)
	See if there is a dbg.value intrinsic for DIVar before I. More...

static void	changeToUnreachable (Instruction *I, bool UseLLVMTrap)

static void	changeToCall (InvokeInst *II)
	changeToCall - Convert the specified invoke into a normal call. More...

static bool	markAliveBlocks (BasicBlock BB, SmallPtrSet< BasicBlock , 128 > &Reachable)

Typedef Documentation

typedef DenseMap<BasicBlock *, Value *> IncomingValueMap

Definition at line 588 of file Local.cpp.

typedef SmallVector<BasicBlock *, 16> PredBlockVector

Definition at line 587 of file Local.cpp.

Function Documentation

static bool areAllUsesEqual ( Instruction * I )

static

areAllUsesEqual - Check whether the uses of a value are all the same. This is similar to Instruction::hasOneUse() except this will also return true when there are no uses or multiple uses that all refer to the same value.

Definition at line 354 of file Local.cpp.

References llvm::Value::use_begin(), and llvm::Value::use_end().

Referenced by llvm::RecursivelyDeleteDeadPHINode().

static bool CanMergeValues	(	Value *	First,
		Value *	Second
	)

static

CanMergeValues - Return true if we can choose one of these values to use in place of the other. Note that we will always choose the non-undef value to keep.

Definition at line 523 of file Local.cpp.

Referenced by CanPropagatePredecessorsForPHIs().

static bool CanPropagatePredecessorsForPHIs	(	BasicBlock *	BB,
		BasicBlock *	Succ
	)

static

CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ, into Succ.

Assumption: Succ is the single successor for BB.

Definition at line 532 of file Local.cpp.

References llvm::BasicBlock::begin(), CanMergeValues(), llvm::SmallPtrSet< PtrType, SmallSize >::count(), llvm::dbgs(), DEBUG, llvm::dyn_cast(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::BasicBlock::getSinglePredecessor(), I, llvm::pred_begin(), llvm::pred_end(), and llvm::succ_begin().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

static void changeToCall ( InvokeInst * II )

static

changeToCall - Convert the specified invoke into a normal call.

Definition at line 1149 of file Local.cpp.

References llvm::CallInst::Create(), llvm::BranchInst::Create(), llvm::Instruction::eraseFromParent(), llvm::InvokeInst::getAttributes(), llvm::InvokeInst::getCalledValue(), llvm::InvokeInst::getCallingConv(), llvm::Instruction::getDebugLoc(), llvm::InvokeInst::getNormalDest(), llvm::Instruction::getParent(), llvm::InvokeInst::getUnwindDest(), llvm::User::op_begin(), llvm::User::op_end(), llvm::BasicBlock::removePredecessor(), and llvm::Value::replaceAllUsesWith().

Referenced by markAliveBlocks().

static void changeToUnreachable	(	Instruction *	I,
		bool	UseLLVMTrap
	)

static

changeToUnreachable - Insert an unreachable instruction before the specified instruction, making it and the rest of the code in the block dead.

Definition at line 1122 of file Local.cpp.

References llvm::CallInst::Create(), llvm::BasicBlock::end(), llvm::iplist< NodeTy, Traits >::erase(), llvm::UndefValue::get(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::Intrinsic::getDeclaration(), llvm::BasicBlock::getInstList(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), I, llvm::BasicBlock::removePredecessor(), llvm::succ_begin(), llvm::succ_end(), and llvm::Intrinsic::trap.

Referenced by markAliveBlocks().

static unsigned enforceKnownAlignment	(	Value *	V,
		unsigned	Align,
		unsigned	PrefAlign,
		const DataLayout *	TD
	)

static

enforceKnownAlignment - If the specified pointer points to an object that we control, modify the object's alignment to PrefAlign. This isn't often possible though. If alignment is important, a more reliable approach is to simply align all global variables and allocation instructions to their preferred alignment from the beginning.

Definition at line 879 of file Local.cpp.

References Align(), llvm::DataLayout::exceedsNaturalStackAlignment(), and llvm::Value::stripPointerCasts().

Referenced by llvm::getOrEnforceKnownAlignment().

static void gatherIncomingValuesToPhi	(	PHINode *	PN,
		IncomingValueMap &	IncomingValues
	)

static

Create a map from block to value for the operands of a given phi.

Create a map from block to value for each non-undef value flowing into PN.

Parameters

PN	The phi we are collecting the map for.
IncomingValues	[out] The map from block to value for this phi.

Definition at line 627 of file Local.cpp.

References llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert().

Referenced by redirectValuesFromPredecessorsToPhi().

static bool LdStHasDebugValue	(	DIVariable &	DIVar,
		Instruction *	I
	)

static

See if there is a dbg.value intrinsic for DIVar before I.

===---------------------------------------------------------------——===// Dbg Intrinsic utilities

Definition at line 953 of file Local.cpp.

References llvm::iplist< NodeTy, Traits >::begin(), llvm::BasicBlock::getInstList(), llvm::User::getOperand(), and llvm::Instruction::getParent().

Referenced by llvm::ConvertDebugDeclareToDebugValue().

static bool markAliveBlocks	(	BasicBlock *	BB,
		SmallPtrSet< BasicBlock *, 128 > &	Reachable
	)

static

Definition at line 1166 of file Local.cpp.

References llvm::BasicBlock::begin(), changeToCall(), changeToUnreachable(), llvm::ConstantFoldTerminator(), llvm::BranchInst::Create(), llvm::SmallVectorBase::empty(), llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::getTerminator(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::succ_begin(), and llvm::succ_end().

Referenced by llvm::removeUnreachableBlocks().

static void redirectValuesFromPredecessorsToPhi	(	BasicBlock *	BB,
		const PredBlockVector &	BBPreds,
		PHINode *	PN
	)

static

Replace a value flowing from a block to a phi with potentially multiple instances of that value flowing from the block's predecessors to the phi.

Parameters

BB	The block with the value flowing into the phi.
BBPreds	The predecessors of BB.
PN	The phi that we are updating.

Definition at line 665 of file Local.cpp.

References llvm::PHINode::addIncoming(), gatherIncomingValuesToPhi(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), getParent(), llvm::PHINode::removeIncomingValue(), replaceUndefValuesInPhi(), selectIncomingValueForBlock(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

static void replaceUndefValuesInPhi	(	PHINode *	PN,
		const IncomingValueMap &	IncomingValues
	)

static

Replace the incoming undef values to a phi with the values from a block-to-value map.

Parameters

PN	The phi we are replacing the undefs in.
IncomingValues	A map from block to value.

Definition at line 643 of file Local.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), and llvm::PHINode::setIncomingValue().

Referenced by redirectValuesFromPredecessorsToPhi().

static Value* selectIncomingValueForBlock	(	Value *	OldVal,
		BasicBlock *	BB,
		IncomingValueMap &	IncomingValues
	)

static

Determines the value to use as the phi node input for a block.

Select between OldVal any value that we know flows from BB to a particular phi on the basis of which one (if either) is not undef. Update IncomingValues based on the selected value.

Parameters

OldVal	The value we are considering selecting.
BB	The block that the value flows in from.
IncomingValues	A map from block-to-value for other phi inputs that we have examined.

Returns: the selected value.

Definition at line 602 of file Local.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::count(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::find(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert().

Referenced by redirectValuesFromPredecessorsToPhi().

STATISTIC	(	NumRemoved	,
		"Number of unreachable basic blocks removed"
	)

Typedefs

Functions

Typedef Documentation

Function Documentation