Local.cpp File Reference

#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/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/GetElementPtrTypeIterator.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/IR/ValueHandle.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"

Include dependency graph for Local.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "local"
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.
static void	gatherIncomingValuesToPhi (PHINode *PN, IncomingValueMap &IncomingValues)
	Create a map from block to value for the operands of a given phi.
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.
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.
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.
static bool	isArray (AllocaInst *AI)
	Determine whether this alloca is either a VLA or an array.
static void	changeToUnreachable (Instruction *I, bool UseLLVMTrap)
static void	changeToCall (InvokeInst *II)
	changeToCall - Convert the specified invoke into a normal call.
static bool	markAliveBlocks (BasicBlock *BB, SmallPtrSetImpl< BasicBlock * > &Reachable)

---

Define Documentation

#define DEBUG_TYPE   "local"

Definition at line 46 of file Local.cpp.

---

Typedef Documentation

typedef DenseMap<BasicBlock *, Value *> IncomingValueMap

Definition at line 606 of file Local.cpp.

typedef SmallVector<BasicBlock *, 16> PredBlockVector

Definition at line 605 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 366 of file Local.cpp.

References llvm::Value::user_begin(), and llvm::Value::user_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 541 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 550 of file Local.cpp.

References llvm::BasicBlock::begin(), CanMergeValues(), llvm::SmallPtrSetImpl< PtrType >::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 1166 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 1139 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(), and llvm::succ_end().

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 896 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 645 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 isArray

(

AllocaInst *

AI

)

[static]

Determine whether this alloca is either a VLA or an array.

Definition at line 1041 of file Local.cpp.

References llvm::SequentialType::getElementType(), llvm::AllocaInst::getType(), llvm::AllocaInst::isArrayAllocation(), and llvm::Type::isArrayTy().

Referenced by llvm::LowerDbgDeclare().

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 975 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,
		SmallPtrSetImpl< BasicBlock * > &	Reachable
	)		[static]

Definition at line 1183 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::SmallPtrSetImpl< PtrType >::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 683 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 661 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 620 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"
	)