SimplifyCFG.cpp File Reference

#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
#include <functional>
#include <set>
#include <map>

Include dependency graph for SimplifyCFG.cpp:

Go to the source code of this file.

Defines
#define	DEBUG_TYPE   "simplifycfg"
Functions
	STATISTIC (NumSpeculations,"Number of speculative executed instructions")
static bool	SafeToMergeTerminators (TerminatorInst *SI1, TerminatorInst *SI2)
static void	AddPredecessorToBlock (BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred)
static bool	CanPropagatePredecessorsForPHIs (BasicBlock *BB, BasicBlock *Succ)
static bool	TryToSimplifyUncondBranchFromEmptyBlock (BasicBlock *BB, BasicBlock *Succ)
static Value *	GetIfCondition (BasicBlock *BB, BasicBlock *&IfTrue, BasicBlock *&IfFalse)
static bool	DominatesMergePoint (Value *V, BasicBlock *BB, std::set< Instruction * > *AggressiveInsts)
static Value *	GatherConstantSetEQs (Value *V, std::vector< ConstantInt * > &Values)
static Value *	GatherConstantSetNEs (Value *V, std::vector< ConstantInt * > &Values)
static bool	GatherValueComparisons (Instruction *Cond, Value *&CompVal, std::vector< ConstantInt * > &Values)
static void	EraseTerminatorInstAndDCECond (TerminatorInst *TI)
static Value *	isValueEqualityComparison (TerminatorInst *TI)
static BasicBlock *	GetValueEqualityComparisonCases (TerminatorInst *TI, std::vector< std::pair< ConstantInt *, BasicBlock * > > &Cases)
static void	EliminateBlockCases (BasicBlock *BB, std::vector< std::pair< ConstantInt *, BasicBlock * > > &Cases)
static bool	ValuesOverlap (std::vector< std::pair< ConstantInt *, BasicBlock * > > &C1, std::vector< std::pair< ConstantInt *, BasicBlock * > > &C2)
static bool	SimplifyEqualityComparisonWithOnlyPredecessor (TerminatorInst *TI, BasicBlock *Pred)
static bool	FoldValueComparisonIntoPredecessors (TerminatorInst *TI)
static bool	HoistThenElseCodeToIf (BranchInst *BI)
static bool	SpeculativelyExecuteBB (BranchInst *BI, BasicBlock *BB1)
static bool	BlockIsSimpleEnoughToThreadThrough (BasicBlock *BB)
static bool	FoldCondBranchOnPHI (BranchInst *BI)
static bool	FoldTwoEntryPHINode (PHINode *PN)
static bool	SimplifyCondBranchToTwoReturns (BranchInst *BI)
static bool	FoldBranchToCommonDest (BranchInst *BI)
static bool	SimplifyCondBranchToCondBranch (BranchInst *PBI, BranchInst *BI)
bool	llvm::SimplifyCFG (BasicBlock *BB)

---

Define Documentation

#define DEBUG_TYPE   "simplifycfg"

Definition at line 14 of file SimplifyCFG.cpp.

---

Function Documentation

static void AddPredecessorToBlock	(	BasicBlock *	Succ,
		BasicBlock *	NewPred,
		BasicBlock *	ExistPred
	)			[static]

AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block. The values that will be flowing into the PHI nodes will be the same as those coming in from ExistPred, an existing predecessor of Succ.

Definition at line 65 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), llvm::dyn_cast(), llvm::PHINode::getIncomingValueForBlock(), llvm::succ_begin(), and llvm::succ_end().

Referenced by FoldBranchToCommonDest(), FoldValueComparisonIntoPredecessors(), and HoistThenElseCodeToIf().

static bool BlockIsSimpleEnoughToThreadThrough

(

BasicBlock *

BB

)

[static]

BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch across this block.

Definition at line 1081 of file SimplifyCFG.cpp.

References BBI, llvm::BasicBlock::begin(), E, llvm::Instruction::getParent(), and llvm::BasicBlock::getTerminator().

Referenced by FoldCondBranchOnPHI(), and SimplifyCondBranchToCondBranch().

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 82 of file SimplifyCFG.cpp.

References BBI, llvm::BasicBlock::begin(), DOUT, llvm::dyn_cast(), E, llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getNameStart(), llvm::BasicBlock::getSinglePredecessor(), PI, llvm::pred_begin(), llvm::pred_end(), llvm::succ_begin(), and Val.

Referenced by TryToSimplifyUncondBranchFromEmptyBlock().

static bool DominatesMergePoint	(	Value *	V,
		BasicBlock *	BB,
		std::set< Instruction * > *	AggressiveInsts
	)			[static]

DominatesMergePoint - If we have a merge point of an "if condition" as accepted above, return true if the specified value dominates the block. We don't handle the true generality of domination here, just a special case which works well enough for us.

If AggressiveInsts is non-null, and if V does not dominate BB, we check to see if V (which must be an instruction) is cheap to compute and is non-trapping. If both are true, the instruction is inserted into the set and true is returned.

Definition at line 359 of file SimplifyCFG.cpp.

References Add(), And(), llvm::BasicBlock::begin(), llvm::CallingConv::C, llvm::dyn_cast(), FCmp, llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::Type::isFPOrFPVector(), Load, LShr, llvm::User::op_begin(), llvm::User::op_end(), llvm::APIntOps::Or(), and llvm::APIntOps::Xor().

Referenced by FoldTwoEntryPHINode().

static void EliminateBlockCases	(	BasicBlock *	BB,
		std::vector< std::pair< ConstantInt *, BasicBlock * > > &	Cases
	)			[static]

EliminateBlockCases - Given a vector of bb/value pairs, remove any entries in the list that match the specified block.

Definition at line 557 of file SimplifyCFG.cpp.

References second.

Referenced by SimplifyEqualityComparisonWithOnlyPredecessor().

static void EraseTerminatorInstAndDCECond

(

TerminatorInst *

TI

)

[static]

Definition at line 498 of file SimplifyCFG.cpp.

References llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), and llvm::RecursivelyDeleteTriviallyDeadInstructions().

Referenced by FoldValueComparisonIntoPredecessors(), HoistThenElseCodeToIf(), llvm::SimplifyCFG(), SimplifyCondBranchToTwoReturns(), and SimplifyEqualityComparisonWithOnlyPredecessor().

static bool FoldBranchToCommonDest

(

BranchInst *

BI

)

[static]

FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, and if a predecessor branches to us and one of our successors, fold the setcc into the predecessor and use logical operations to pick the right destination.

Definition at line 1412 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), And(), BB, llvm::Instruction::clone(), DOUT, llvm::dyn_cast(), E, llvm::BasicBlock::front(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::hasOneUse(), llvm::BranchInst::isUnconditional(), llvm::APIntOps::Or(), PI, llvm::pred_begin(), llvm::pred_end(), SafeToMergeTerminators(), llvm::BranchInst::setCondition(), llvm::Value::setName(), llvm::BranchInst::setSuccessor(), and llvm::Value::takeName().

Referenced by llvm::SimplifyCFG().

static bool FoldCondBranchOnPHI

(

BranchInst *

BI

)

[static]

FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value that is defined in the same block as the branch and if any PHI entries are constants, thread edges corresponding to that entry to be branches to their ultimate destination.

Definition at line 1108 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), BB, BBI, llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::CallingConv::C, llvm::ConstantFoldInstruction(), llvm::dyn_cast(), llvm::FoldSingleEntryPHINodes(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::TerminatorInst::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getType(), llvm::ConstantInt::getZExtValue(), llvm::Value::hasOneUse(), llvm::User::op_begin(), llvm::User::op_end(), PI, llvm::BasicBlock::removePredecessor(), llvm::Value::setName(), llvm::TerminatorInst::setSuccessor(), and V.

Referenced by llvm::SimplifyCFG().

static bool FoldTwoEntryPHINode

(

PHINode *

PN

)

[static]

FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.

Definition at line 1206 of file SimplifyCFG.cpp.

References BB, llvm::BasicBlock::begin(), DominatesMergePoint(), DOUT, GetIfCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), Pred, llvm::pred_begin(), llvm::Value::replaceAllUsesWith(), and llvm::Value::takeName().

Referenced by llvm::SimplifyCFG().

static bool FoldValueComparisonIntoPredecessors

(

TerminatorInst *

TI

)

[static]

FoldValueComparisonIntoPredecessors - The specified terminator is a value equality comparison instruction (either a switch or a branch on "X == c"). See if any of the predecessors of the terminator block are value comparisons on the same value. If so, and if safe to do so, fold them together.

Definition at line 721 of file SimplifyCFG.cpp.

References llvm::SwitchInst::addCase(), AddPredecessorToBlock(), llvm::SmallVectorImpl< T >::back(), BB, Changed, E, llvm::SmallVectorImpl< T >::empty(), EraseTerminatorInstAndDCECond(), first, llvm::SwitchInst::getNumSuccessors(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::SwitchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), GetValueEqualityComparisonCases(), isValueEqualityComparison(), llvm::SmallVectorImpl< T >::pop_back(), Pred, llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorImpl< T >::push_back(), llvm::BasicBlock::removePredecessor(), SafeToMergeTerminators(), second, llvm::SwitchInst::setSuccessor(), llvm::BasicBlock::size(), llvm::SmallVectorImpl< T >::size(), and std::swap().

Referenced by llvm::SimplifyCFG().

static Value* GatherConstantSetEQs	(	Value *	V,
		std::vector< ConstantInt * > &	Values
	)			[static]

GatherConstantSetEQs - Given a potentially 'or'd together collection of icmp_eq instructions that compare a value against a constant, return the value being compared, and stick the constant into the Values vector.

Definition at line 432 of file SimplifyCFG.cpp.

References llvm::CallingConv::C, llvm::Instruction::getOpcode(), llvm::User::getOperand(), Inst, LHS, llvm::APIntOps::Or(), and RHS.

Referenced by GatherValueComparisons().

static Value* GatherConstantSetNEs	(	Value *	V,
		std::vector< ConstantInt * > &	Values
	)			[static]

GatherConstantSetNEs - Given a potentially 'and'd together collection of setne instructions that compare a value against a constant, return the value being compared, and stick the constant into the Values vector.

Definition at line 456 of file SimplifyCFG.cpp.

References And(), llvm::CallingConv::C, llvm::Instruction::getOpcode(), llvm::User::getOperand(), Inst, LHS, and RHS.

Referenced by GatherValueComparisons().

static bool GatherValueComparisons	(	Instruction *	Cond,
		Value *&	CompVal,
		std::vector< ConstantInt * > &	Values
	)			[static]

GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a bunch of comparisons of one value against constants, return the value and the constants being compared.

Definition at line 480 of file SimplifyCFG.cpp.

References And(), GatherConstantSetEQs(), GatherConstantSetNEs(), llvm::Instruction::getOpcode(), and llvm::APIntOps::Or().

Referenced by llvm::SimplifyCFG().

static Value* GetIfCondition	(	BasicBlock *	BB,
		BasicBlock *&	IfTrue,
		BasicBlock *&	IfFalse
	)			[static]

GetIfCondition - Given a basic block (BB) with two predecessors (and presumably PHI nodes in it), check to see if the merge at this block is due to an "if condition". If so, return the boolean condition that determines which entry into BB will be taken. Also, return by references the block that will be entered from if the condition is true, and the block that will be entered if the condition is false.

Definition at line 268 of file SimplifyCFG.cpp.

References llvm::BranchInst::getCondition(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isConditional(), llvm::pred_begin(), llvm::pred_end(), and std::swap().

Referenced by FoldTwoEntryPHINode().

static BasicBlock* GetValueEqualityComparisonCases	(	TerminatorInst *	TI,
		std::vector< std::pair< ConstantInt *, BasicBlock * > > &	Cases
	)			[static]

GetValueEqualityComparisonCases - Given a value comparison instruction, decode all of the 'cases' that it represents and return the 'default' block.

Definition at line 536 of file SimplifyCFG.cpp.

References llvm::BranchInst::getCondition(), and llvm::BranchInst::getSuccessor().

Referenced by FoldValueComparisonIntoPredecessors(), and SimplifyEqualityComparisonWithOnlyPredecessor().

static bool HoistThenElseCodeToIf

(

BranchInst *

BI

)

[static]

HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and BB2, hoist any common code in the two blocks up into the branch block. The caller of this function guarantees that BI's block dominates BB1 and BB2.

Definition at line 846 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), BBI, llvm::BasicBlock::begin(), llvm::Instruction::clone(), llvm::dyn_cast(), E, EraseTerminatorInstAndDCECond(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getOpcode(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::Value::getType(), llvm::Instruction::isIdenticalTo(), llvm::Value::replaceAllUsesWith(), llvm::PHINode::setIncomingValue(), llvm::succ_begin(), llvm::succ_end(), and llvm::Value::takeName().

Referenced by llvm::SimplifyCFG().

static Value* isValueEqualityComparison

(

TerminatorInst *

TI

)

[static]

isValueEqualityComparison - Return true if the specified terminator checks to see if a value is equal to constant integer value.

Definition at line 513 of file SimplifyCFG.cpp.

References llvm::pred_begin(), and llvm::pred_end().

Referenced by FoldValueComparisonIntoPredecessors(), llvm::SimplifyCFG(), and SimplifyEqualityComparisonWithOnlyPredecessor().

static bool SafeToMergeTerminators	(	TerminatorInst *	SI1,
		TerminatorInst *	SI2
	)			[static]

SafeToMergeTerminators - Return true if it is safe to merge these two terminator instructions together.

Definition at line 38 of file SimplifyCFG.cpp.

References BBI, llvm::SmallPtrSet< PtrType, SmallSize >::count(), E, llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getParent(), llvm::succ_begin(), and llvm::succ_end().

Referenced by FoldBranchToCommonDest(), and FoldValueComparisonIntoPredecessors().

static bool SimplifyCondBranchToCondBranch	(	BranchInst *	PBI,
		BranchInst *	BI
	)			[static]

SimplifyCondBranchToCondBranch - If we have a conditional branch as a predecessor of another block, this function tries to simplify it. We know that PBI and BI are both conditional branches, and BI is in one of the successor blocks of PBI - PBI branches to BI.

Definition at line 1512 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), BB, llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), DOUT, llvm::dyn_cast(), E, llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), II, llvm::BranchInst::isConditional(), PI, llvm::pred_begin(), llvm::pred_end(), llvm::BranchInst::setCondition(), llvm::PHINode::setIncomingValue(), llvm::BranchInst::setSuccessor(), and V.

Referenced by llvm::SimplifyCFG().

static bool SimplifyCondBranchToTwoReturns

(

BranchInst *

BI

)

[static]

SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes to two returning blocks, try to merge them together into one return, introducing a select if the return values disagree.

Definition at line 1324 of file SimplifyCFG.cpp.

References BBI, llvm::BasicBlock::begin(), BrCond, DOUT, EraseTerminatorInstAndDCECond(), llvm::BranchInst::getCondition(), llvm::Instruction::getParent(), llvm::ReturnInst::getReturnValue(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isConditional(), and llvm::BasicBlock::removePredecessor().

Referenced by llvm::SimplifyCFG().

static bool SimplifyEqualityComparisonWithOnlyPredecessor	(	TerminatorInst *	TI,
		BasicBlock *	Pred
	)			[static]

SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a terminator instruction and its block is known to only have a single predecessor block, check to see if that predecessor is also a value comparison with the same value, and if that comparison determines the outcome of this comparison. If so, simplify TI. This does a very limited form of jump threading.

Definition at line 607 of file SimplifyCFG.cpp.

References DOUT, EliminateBlockCases(), EraseTerminatorInstAndDCECond(), first, llvm::SwitchInst::getCaseValue(), llvm::SwitchInst::getNumCases(), llvm::Instruction::getParent(), llvm::SwitchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), GetValueEqualityComparisonCases(), isValueEqualityComparison(), llvm::SwitchInst::removeCase(), llvm::BasicBlock::removePredecessor(), second, llvm::succ_begin(), llvm::succ_end(), and ValuesOverlap().

Referenced by llvm::SimplifyCFG().

static bool SpeculativelyExecuteBB	(	BranchInst *	BI,
		BasicBlock *	BB1
	)			[static]

SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 and an BB2 and the only successor of BB1 is BB2, hoist simple code (for now, restricted to a single instruction that's side effect free) from the BB1 into the branch block to speculatively execute it.

Definition at line 931 of file SimplifyCFG.cpp.

References Add(), And(), BBI, llvm::BasicBlock::begin(), BrCond, llvm::SmallPtrSet< PtrType, SmallSize >::count(), llvm::dyn_cast(), E, llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), FCmp, llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getOpcode(), getOpcode(), llvm::Instruction::getParent(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::SmallPtrSet< PtrType, SmallSize >::insert(), InsertPos, llvm::Type::isFloatingPoint(), llvm::Value::isUsedInBasicBlock(), LShr, llvm::User::op_begin(), llvm::User::op_end(), llvm::APIntOps::Or(), llvm::SmallVectorImpl< T >::push_back(), llvm::PHINode::setIncomingValue(), llvm::SmallVectorImpl< T >::size(), llvm::Value::use_begin(), llvm::Value::use_empty(), llvm::Value::use_end(), and llvm::APIntOps::Xor().

Referenced by llvm::SimplifyCFG().

STATISTIC	(	NumSpeculations	,
		"Number of speculative executed instructions"
	)

static bool TryToSimplifyUncondBranchFromEmptyBlock	(	BasicBlock *	BB,
		BasicBlock *	Succ
	)			[static]

TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional branch to Succ, and contains no instructions other than PHI nodes and the branch. If possible, eliminate BB.

Definition at line 178 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), CanPropagatePredecessorsForPHIs(), DOUT, llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::BasicBlock::getInstList(), llvm::PHINode::getNumIncomingValues(), llvm::Value::hasName(), llvm::pred_begin(), llvm::pred_end(), llvm::PHINode::removeIncomingValue(), llvm::SmallVectorImpl< T >::size(), and llvm::Value::takeName().

Referenced by llvm::SimplifyCFG().

static bool ValuesOverlap	(	std::vector< std::pair< ConstantInt *, BasicBlock * > > &	C1,
		std::vector< std::pair< ConstantInt *, BasicBlock * > > &	C2
	)			[static]

ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as well.

Definition at line 569 of file SimplifyCFG.cpp.

References C2, first, std::swap(), and V1.

Referenced by SimplifyEqualityComparisonWithOnlyPredecessor().