SimplifyCFG.cpp File Reference

#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/EHPersonalities.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.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/NoFolder.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "simplifycfg"

Functions
	STATISTIC (NumBitMaps, "Number of switch instructions turned into bitmaps")
	STATISTIC (NumLinearMaps, "Number of switch instructions turned into linear mapping")
	STATISTIC (NumLookupTables, "Number of switch instructions turned into lookup tables")
	STATISTIC (NumLookupTablesHoles, "Number of switch instructions turned into lookup tables (holes checked)")
	STATISTIC (NumTableCmpReuses, "Number of reused switch table lookup compares")
	STATISTIC (NumSinkCommons, "Number of common instructions sunk down to the end block")
	STATISTIC (NumSpeculations, "Number of speculative executed instructions")
static bool	SafeToMergeTerminators (Instruction *SI1, Instruction *SI2, SmallSetVector< BasicBlock *, 4 > *FailBlocks=nullptr)
	Return true if it is safe to merge these two terminator instructions together. More...
static bool	isProfitableToFoldUnconditional (BranchInst *SI1, BranchInst *SI2, Instruction *Cond, SmallVectorImpl< PHINode *> &PhiNodes)
	Return true if it is safe and profitable to merge these two terminator instructions together, where SI1 is an unconditional branch. More...
static void	AddPredecessorToBlock (BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred)
	Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block. More...
static unsigned	ComputeSpeculationCost (const User *I, const TargetTransformInfo &TTI)
	Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to speculate. More...
static bool	DominatesMergePoint (Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction *> &AggressiveInsts, unsigned &CostRemaining, const TargetTransformInfo &TTI, unsigned Depth=0)
	If we have a merge point of an "if condition" as accepted above, return true if the specified value dominates the block. More...
static ConstantInt *	GetConstantInt (Value *V, const DataLayout &DL)
	Extract ConstantInt from value, looking through IntToPtr and PointerNullValue. More...
static void	EraseTerminatorAndDCECond (Instruction *TI)
static void	EliminateBlockCases (BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
	Given a vector of bb/value pairs, remove any entries in the list that match the specified block. More...
static bool	ValuesOverlap (std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
	Return true if there are any keys in C1 that exist in C2 as well. More...
static void	setBranchWeights (SwitchInst *SI, ArrayRef< uint32_t > Weights)
static void	setBranchWeights (Instruction *I, uint32_t TrueWeight, uint32_t FalseWeight)
static int	ConstantIntSortPredicate (ConstantInt *const *P1, ConstantInt *const *P2)
static bool	HasBranchWeights (const Instruction *I)
static void	GetBranchWeights (Instruction *TI, SmallVectorImpl< uint64_t > &Weights)
	Get Weights of a given terminator, the default weight is at the front of the vector. More...
static void	FitWeights (MutableArrayRef< uint64_t > Weights)
	Keep halving the weights until all can fit in uint32_t. More...
static bool	isSafeToHoistInvoke (BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
static bool	passingValueIsAlwaysUndefined (Value *V, Instruction *I)
	Check if passing a value to an instruction will cause undefined behavior. More...
static bool	HoistThenElseCodeToIf (BranchInst *BI, const TargetTransformInfo &TTI)
	Given a conditional branch that goes to BB1 and BB2, hoist any common code in the two blocks up into the branch block. More...
static bool	canSinkInstructions (ArrayRef< Instruction *> Insts, DenseMap< Instruction *, SmallVector< Value *, 4 >> &PHIOperands)
static bool	sinkLastInstruction (ArrayRef< BasicBlock *> Blocks)
static bool	SinkCommonCodeFromPredecessors (BasicBlock *BB)
	Check whether BB's predecessors end with unconditional branches. More...
static Value *	isSafeToSpeculateStore (Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
	Determine if we can hoist sink a sole store instruction out of a conditional block. More...
static bool	SpeculativelyExecuteBB (BranchInst *BI, BasicBlock *ThenBB, const TargetTransformInfo &TTI)
	Speculate a conditional basic block flattening the CFG. More...
static bool	BlockIsSimpleEnoughToThreadThrough (BasicBlock *BB)
	Return true if we can thread a branch across this block. More...
static bool	FoldCondBranchOnPHI (BranchInst *BI, const DataLayout &DL, AssumptionCache *AC)
	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. More...
static bool	FoldTwoEntryPHINode (PHINode *PN, const TargetTransformInfo &TTI, const DataLayout &DL)
	Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it. More...
static bool	SimplifyCondBranchToTwoReturns (BranchInst *BI, IRBuilder<> &Builder)
	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. More...
static bool	tryCSEWithPredecessor (Instruction *Inst, BasicBlock *PB)
	Return true if the given instruction is available in its predecessor block. More...
static bool	extractPredSuccWeights (BranchInst *PBI, BranchInst *BI, uint64_t &PredTrueWeight, uint64_t &PredFalseWeight, uint64_t &SuccTrueWeight, uint64_t &SuccFalseWeight)
	Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{True|False}Weight. More...
static StoreInst *	findUniqueStoreInBlocks (BasicBlock *BB1, BasicBlock *BB2)
static Value *	ensureValueAvailableInSuccessor (Value *V, BasicBlock *BB, Value *AlternativeV=nullptr)
static bool	mergeConditionalStoreToAddress (BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, const DataLayout &DL)
static bool	mergeConditionalStores (BranchInst *PBI, BranchInst *QBI, const DataLayout &DL)
static bool	SimplifyCondBranchToCondBranch (BranchInst *PBI, BranchInst *BI, const DataLayout &DL)
	If we have a conditional branch as a predecessor of another block, this function tries to simplify it. More...
static bool	SimplifyTerminatorOnSelect (Instruction *OldTerm, Value *Cond, BasicBlock *TrueBB, BasicBlock *FalseBB, uint32_t TrueWeight, uint32_t FalseWeight)
static bool	SimplifySwitchOnSelect (SwitchInst *SI, SelectInst *Select)
static bool	SimplifyIndirectBrOnSelect (IndirectBrInst *IBI, SelectInst *SI)
static bool	SimplifyBranchOnICmpChain (BranchInst *BI, IRBuilder<> &Builder, const DataLayout &DL)
	The specified branch is a conditional branch. More...
static bool	removeEmptyCleanup (CleanupReturnInst *RI)
static bool	mergeCleanupPad (CleanupReturnInst *RI)
static bool	CasesAreContiguous (SmallVectorImpl< ConstantInt *> &Cases)
static bool	TurnSwitchRangeIntoICmp (SwitchInst *SI, IRBuilder<> &Builder)
	Turn a switch with two reachable destinations into an integer range comparison and branch. More...
static bool	eliminateDeadSwitchCases (SwitchInst *SI, AssumptionCache *AC, const DataLayout &DL)
	Compute masked bits for the condition of a switch and use it to remove dead cases. More...
static PHINode *	FindPHIForConditionForwarding (ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
	If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i.e. More...
static bool	ForwardSwitchConditionToPHI (SwitchInst *SI)
	Try to forward the condition of a switch instruction to a phi node dominated by the switch, if that would mean that some of the destination blocks of the switch can be folded away. More...
static bool	ValidLookupTableConstant (Constant *C, const TargetTransformInfo &TTI)
	Return true if the backend will be able to handle initializing an array of constants like C. More...
static Constant *	LookupConstant (Value *V, const SmallDenseMap< Value *, Constant *> &ConstantPool)
	If V is a Constant, return it. More...
static Constant *	ConstantFold (Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant *> &ConstantPool)
	Try to fold instruction I into a constant. More...
static bool	GetCaseResults (SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant *>> &Res, const DataLayout &DL, const TargetTransformInfo &TTI)
	Try to determine the resulting constant values in phi nodes at the common destination basic block, *CommonDest, for one of the case destionations CaseDest corresponding to value CaseVal (0 for the default case), of a switch instruction SI. More...
static uintptr_t	MapCaseToResult (ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool	InitializeUniqueCases (SwitchInst *SI, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult, const DataLayout &DL, const TargetTransformInfo &TTI, uintptr_t MaxUniqueResults, uintptr_t MaxCasesPerResult)
static Value *	ConvertTwoCaseSwitch (const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
static void	RemoveSwitchAfterSelectConversion (SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder)
static bool	switchToSelect (SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
	If the switch is only used to initialize one or more phi nodes in a common successor block with only two different constant values, replace the switch with select. More...
static bool	ShouldBuildLookupTable (SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout &DL, const SmallDenseMap< PHINode *, Type *> &ResultTypes)
	Determine whether a lookup table should be built for this switch, based on the number of cases, size of the table, and the types of the results. More...
static void	reuseTableCompare (User *PhiUser, BasicBlock *PhiBlock, BranchInst *RangeCheckBranch, Constant *DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant *>> &Values)
	Try to reuse the switch table index compare. More...
static bool	SwitchToLookupTable (SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
	If the switch is only used to initialize one or more phi nodes in a common successor block with different constant values, replace the switch with lookup tables. More...
static bool	isSwitchDense (ArrayRef< int64_t > Values)
static bool	ReduceSwitchRange (SwitchInst *SI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI)
	Try to transform a switch that has "holes" in it to a contiguous sequence of cases. More...
static bool	TryToMergeLandingPad (LandingPadInst *LPad, BranchInst *BI, BasicBlock *BB)
	Given an block with only a single landing pad and a unconditional branch try to find another basic block which this one can be merged with. More...
static BasicBlock *	allPredecessorsComeFromSameSource (BasicBlock *BB)
static bool	removeUndefIntroducingPredecessor (BasicBlock *BB)
	If BB has an incoming value that will always trigger undefined behavior (eg. More...

Variables
static cl::opt< unsigned >	PHINodeFoldingThreshold ("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc("Control the amount of phi node folding to perform (default = 2)"))
static cl::opt< bool >	DupRet ("simplifycfg-dup-ret", cl::Hidden, cl::init(false), cl::desc("Duplicate return instructions into unconditional branches"))
static cl::opt< bool >	SinkCommon ("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static cl::opt< bool >	HoistCondStores ("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))
static cl::opt< bool >	MergeCondStores ("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))
static cl::opt< bool >	MergeCondStoresAggressively ("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))
static cl::opt< bool >	SpeculateOneExpensiveInst ("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
static cl::opt< unsigned >	MaxSpeculationDepth ("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "simplifycfg"

Definition at line 85 of file SimplifyCFG.cpp.

Function Documentation

AddPredecessorToBlock()

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

static

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

References llvm::BasicBlock::phis().

Referenced by FitWeights(), llvm::FoldBranchToCommonDest(), FoldCondBranchOnPHI(), HoistThenElseCodeToIf(), SimplifyBranchOnICmpChain(), SimplifyCondBranchToCondBranch(), and SwitchToLookupTable().

allPredecessorsComeFromSameSource()

static BasicBlock* allPredecessorsComeFromSameSource ( BasicBlock *  BB )

static

Definition at line 5804 of file SimplifyCFG.cpp.

References E, llvm::FoldBranchToCommonDest(), FoldCondBranchOnPHI(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::ConstantInt::getFalse(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::Instruction::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::Function::hasFnAttribute(), HoistThenElseCodeToIf(), I, llvm::BasicBlock::instructionsWithoutDebug(), llvm::BranchInst::isConditional(), llvm::isImpliedByDomCondition(), mergeConditionalStores(), MergeCondStores, llvm::Attribute::OptForFuzzing, P, llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::RecursivelyDeleteTriviallyDeadInstructions(), llvm::BranchInst::setCondition(), SimplifyBranchOnICmpChain(), SimplifyCondBranchToCondBranch(), and SpeculativelyExecuteBB().

BlockIsSimpleEnoughToThreadThrough()

static bool BlockIsSimpleEnoughToThreadThrough ( BasicBlock *  BB )

static

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

Definition at line 2130 of file SimplifyCFG.cpp.

References llvm::Instruction::getParent(), llvm::BasicBlock::instructionsWithoutDebug(), Size, and llvm::Value::users().

Referenced by FoldCondBranchOnPHI(), and SimplifyCondBranchToCondBranch().

canSinkInstructions()

static bool canSinkInstructions ( ArrayRef< Instruction *>  Insts, DenseMap< Instruction *, SmallVector< Value *, 4 >> &  PHIOperands  )

static

Definition at line 1432 of file SimplifyCFG.cpp.

References llvm::all_of(), llvm::any_of(), assert(), C, llvm::canReplaceOperandWithVariable(), llvm::dyn_cast(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::Value::hasOneUse(), I, llvm::Instruction::isEHPad(), llvm::CallInst::isInlineAsm(), llvm::Instruction::isSameOperationAs(), llvm::Type::isTokenTy(), and llvm::Value::user_begin().

Referenced by SinkCommonCodeFromPredecessors().

CasesAreContiguous()

static bool CasesAreContiguous ( SmallVectorImpl< ConstantInt *> &  Cases )

static

Definition at line 4264 of file SimplifyCFG.cpp.

References llvm::array_pod_sort(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), ConstantIntSortPredicate(), E, llvm::SmallVectorTemplateCommon< T >::end(), I, and llvm::SmallVectorBase::size().

Referenced by TurnSwitchRangeIntoICmp().

ComputeSpeculationCost()

static unsigned ComputeSpeculationCost ( const User *  I, const TargetTransformInfo &  TTI  )

static

Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to speculate.

TCC_Free means cheap, TCC_Basic means less cheap, and TCC_Expensive means prohibitively expensive.

Definition at line 304 of file SimplifyCFG.cpp.

References assert(), llvm::TargetTransformInfo::getUserCost(), and llvm::isSafeToSpeculativelyExecute().

ConstantFold()

static Constant* ConstantFold ( Instruction *  I, const DataLayout &  DL, const SmallDenseMap< Value *, Constant *> &  ConstantPool  )

static

Try to fold instruction I into a constant.

This works for simple instructions such as binary operations where both operands are constant or can be replaced by constants from the ConstantPool. Returns the resulting constant on success, 0 otherwise.

Definition at line 4599 of file SimplifyCFG.cpp.

References llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldInstOperands(), llvm::ISD::ConstantPool, E, llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Constant::isAllOnesValue(), llvm::Constant::isNullValue(), LookupConstant(), N, llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::MCID::Select.

Referenced by GetCaseResults().

ConstantIntSortPredicate()

static int ConstantIntSortPredicate ( ConstantInt *const *  P1, ConstantInt *const *  P2  )

static

Definition at line 956 of file SimplifyCFG.cpp.

References llvm::ConstantInt::getValue(), and llvm::APInt::ult().

Referenced by CasesAreContiguous(), and SimplifyBranchOnICmpChain().

ConvertTwoCaseSwitch()

static Value* ConvertTwoCaseSwitch ( const SwitchCaseResultVectorTy &  ResultVector, Constant *  DefaultResult, Value *  Condition, IRBuilder<> &  Builder  )

static

Definition at line 4786 of file SimplifyCFG.cpp.

References assert(), llvm::IRBuilder< T, Inserter >::CreateICmpEQ(), llvm::IRBuilder< T, Inserter >::CreateSelect(), first, and second.

Referenced by switchToSelect().

DominatesMergePoint()

static bool DominatesMergePoint ( Value *  V, BasicBlock *  BB, SmallPtrSetImpl< Instruction *> &  AggressiveInsts, unsigned &  CostRemaining, const TargetTransformInfo &  TTI, unsigned  Depth = 0  )

static

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) and its recursive operands that do not dominate BB have a combined cost lower than CostRemaining and are non-trapping. If both are true, the instruction is inserted into the set and true is returned.

The cost for most non-trapping instructions is defined as 1 except for Select whose cost is 2.

After this function returns, CostRemaining is decreased by the cost of V plus its non-dominating operands. If that cost is greater than CostRemaining, false is returned and CostRemaining is undefined.

Definition at line 328 of file SimplifyCFG.cpp.

References C, llvm::ComputeSpeculationCost(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::Depth, llvm::dyn_cast(), llvm::SmallPtrSetImplBase::empty(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BranchInst::isConditional(), llvm::isSafeToSpeculativelyExecute(), MaxSpeculationDepth, llvm::User::op_begin(), llvm::User::op_end(), and SpeculateOneExpensiveInst.

Referenced by FoldTwoEntryPHINode().

EliminateBlockCases()

static void EliminateBlockCases ( BasicBlock *  BB, std::vector< ValueEqualityComparisonCase > &  Cases  )

static

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

Definition at line 739 of file SimplifyCFG.cpp.

References llvm::sys::fs::remove().

Referenced by setBranchWeights().

eliminateDeadSwitchCases()

static bool eliminateDeadSwitchCases ( SwitchInst *  SI, AssumptionCache *  AC, const DataLayout &  DL  )

static

Compute masked bits for the condition of a switch and use it to remove dead cases.

Definition at line 4391 of file SimplifyCFG.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::tgtok::Bits, llvm::SwitchInst::case_default(), llvm::SwitchInst::cases(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::countPopulation(), llvm::dbgs(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), EraseTerminatorAndDCECond(), llvm::SwitchInst::findCaseValue(), llvm::BasicBlock::front(), GetBranchWeights(), llvm::SwitchInst::getCondition(), llvm::Value::getContext(), llvm::SwitchInst::getDefaultDest(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Type::getIntegerBitWidth(), llvm::APInt::getMinSignedBits(), llvm::SwitchInst::getNumCases(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), HasBranchWeights(), llvm::APInt::intersects(), llvm::APInt::isSubsetOf(), LLVM_DEBUG, llvm::KnownBits::One, llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SwitchInst::removeCase(), setBranchWeights(), llvm::SwitchInst::setDefaultDest(), llvm::SmallVectorBase::size(), llvm::SplitBlock(), llvm::SplitBlockPredecessors(), std::swap(), and llvm::KnownBits::Zero.

Referenced by ReduceSwitchRange().

ensureValueAvailableInSuccessor()

static Value* ensureValueAvailableInSuccessor ( Value *  V, BasicBlock *  BB, Value *  AlternativeV = nullptr  )

static

Definition at line 2859 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), llvm::PHINode::Create(), llvm::BasicBlock::front(), llvm::UndefValue::get(), llvm::PHINode::getIncomingValueForBlock(), getParent(), llvm::BasicBlock::getSingleSuccessor(), llvm::Value::getType(), llvm::BasicBlock::hasNPredecessors(), I, llvm::pred_begin(), and llvm::predecessors().

Referenced by mergeConditionalStoreToAddress().

EraseTerminatorAndDCECond()

static void EraseTerminatorAndDCECond ( Instruction *  TI )

static

Definition at line 673 of file SimplifyCFG.cpp.

References llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::BranchInst::getCondition(), GetConstantInt(), llvm::BranchInst::getSuccessor(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::RecursivelyDeleteTriviallyDeadInstructions(), and SI.

Referenced by eliminateDeadSwitchCases(), FitWeights(), llvm::FoldBranchToCommonDest(), HoistThenElseCodeToIf(), mergeCleanupPad(), ReduceSwitchRange(), setBranchWeights(), SimplifyBranchOnICmpChain(), SimplifyCondBranchToTwoReturns(), and SimplifyTerminatorOnSelect().

extractPredSuccWeights()

static bool extractPredSuccWeights ( BranchInst *  PBI, BranchInst *  BI, uint64_t &  PredTrueWeight, uint64_t &  PredFalseWeight, uint64_t &  SuccTrueWeight, uint64_t &  SuccFalseWeight  )

static

Return true if either PBI or BI has branch weight available, and store the weights in {Pred|Succ}{True|False}Weight.

If one of PBI and BI does not have branch weight, use 1:1 as its weight.

Definition at line 2519 of file SimplifyCFG.cpp.

References llvm::Instruction::extractProfMetadata().

Referenced by llvm::FoldBranchToCommonDest(), and SimplifyCondBranchToCondBranch().

FindPHIForConditionForwarding()

static PHINode* FindPHIForConditionForwarding ( ConstantInt *  CaseValue, BasicBlock *  BB, int *  PhiIndex  )

static

If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i.e.

it is empty and terminated by an unconditional branch), look at the phi node for BB in the successor block and see if the incoming value is equal to CaseValue. If so, return the phi node, and set PhiIndex to BB's index in the phi node.

Definition at line 4472 of file SimplifyCFG.cpp.

References assert(), llvm::MCID::Branch, llvm::dyn_cast(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isUnconditional(), and llvm::BasicBlock::phis().

Referenced by ForwardSwitchConditionToPHI().

findUniqueStoreInBlocks()

static StoreInst* findUniqueStoreInBlocks ( BasicBlock *  BB1, BasicBlock *  BB2  )

static

Definition at line 2842 of file SimplifyCFG.cpp.

References SI.

Referenced by mergeConditionalStoreToAddress().

FitWeights()

static void FitWeights ( MutableArrayRef< uint64_t >  Weights )

static

Keep halving the weights until all can fit in uint32_t.

Definition at line 998 of file SimplifyCFG.cpp.

References llvm::SwitchInst::addCase(), AddPredecessorToBlock(), assert(), llvm::SmallVectorImpl< T >::assign(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::MutableArrayRef< T >::begin(), llvm::countLeadingZeros(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::IRBuilder< T, Inserter >::CreatePtrToInt(), llvm::IRBuilder< T, Inserter >::CreateSwitch(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::MutableArrayRef< T >::end(), EraseTerminatorAndDCECond(), GetBranchWeights(), llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::SwitchInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::SwitchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), HasBranchWeights(), I, llvm::SmallVectorImpl< T >::insert(), llvm::Type::isPointerTy(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::BasicBlock::removePredecessor(), SafeToMergeTerminators(), setBranchWeights(), llvm::Instruction::setDebugLoc(), llvm::IRBuilderBase::SetInsertPoint(), llvm::SwitchInst::setSuccessor(), llvm::SmallVectorBase::size(), llvm::BasicBlock::size(), llvm::SplitBlockPredecessors(), and std::swap().

Referenced by llvm::FoldBranchToCommonDest(), and SimplifyCondBranchToCondBranch().

FoldCondBranchOnPHI()

static bool FoldCondBranchOnPHI ( BranchInst *  BI, const DataLayout &  DL, AssumptionCache *  AC  )

static

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

References AddPredecessorToBlock(), llvm::any_of(), llvm::Intrinsic::assume, llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::CallBase::cannotDuplicate(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::Value::deleteValue(), llvm::dyn_cast(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::FoldSingleEntryPHINodes(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Instruction::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getType(), llvm::ConstantInt::getZExtValue(), llvm::Value::hasOneUse(), I, llvm::iplist_impl< IntrusiveListT, TraitsT >::insert(), llvm::CallBase::isConvergent(), llvm::Type::isIntegerTy(), llvm::Instruction::mayHaveSideEffects(), N, llvm::User::op_begin(), llvm::User::op_end(), llvm::AssumptionCache::registerAssumption(), llvm::BasicBlock::removePredecessor(), llvm::Value::setName(), llvm::Instruction::setSuccessor(), and llvm::SimplifyInstruction().

Referenced by allPredecessorsComeFromSameSource().

FoldTwoEntryPHINode()

static bool FoldTwoEntryPHINode ( PHINode *  PN, const TargetTransformInfo &  TTI, const DataLayout &  DL  )

static

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

Definition at line 2273 of file SimplifyCFG.cpp.

References llvm::BasicBlock::begin(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dbgs(), DominatesMergePoint(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::GetIfCondition(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::Function::hasFnAttribute(), llvm::hoistAllInstructionsInto(), I, llvm::Type::isIntegerTy(), llvm::Instruction::isTerminator(), LLVM_DEBUG, llvm::Attribute::OptForFuzzing, PHINodeFoldingThreshold, llvm::pred_begin(), llvm::Value::replaceAllUsesWith(), llvm::IRBuilderBase::SetInsertPoint(), llvm::SimplifyInstruction(), llvm::Value::takeName(), and llvm::TargetTransformInfo::TCC_Basic.

Referenced by removeUndefIntroducingPredecessor().

ForwardSwitchConditionToPHI()

static bool ForwardSwitchConditionToPHI ( SwitchInst *  SI )

static

Try to forward the condition of a switch instruction to a phi node dominated by the switch, if that would mean that some of the destination blocks of the switch can be folded away.

Return true if a change is made.

Definition at line 4503 of file SimplifyCFG.cpp.

References llvm::SwitchInst::cases(), llvm::count(), FindPHIForConditionForwarding(), llvm::SwitchInst::getCondition(), llvm::Instruction::getParent(), llvm::BasicBlock::phis(), llvm::PHINode::setIncomingValue(), and llvm::SmallVectorBase::size().

Referenced by ReduceSwitchRange().

GetBranchWeights()

static void GetBranchWeights ( Instruction *  TI, SmallVectorImpl< uint64_t > &  Weights  )

static

Get Weights of a given terminator, the default weight is at the front of the vector.

If TI is a conditional eq, we need to swap the branch-weight metadata.

Definition at line 977 of file SimplifyCFG.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::Instruction::getMetadata(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), llvm::ConstantInt::getValue(), llvm::APInt::getZExtValue(), llvm::CmpInst::ICMP_EQ, llvm::LLVMContext::MD_prof, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorBase::size(), and std::swap().

Referenced by eliminateDeadSwitchCases(), FitWeights(), SimplifyIndirectBrOnSelect(), SimplifySwitchOnSelect(), and TurnSwitchRangeIntoICmp().

GetCaseResults()

static bool GetCaseResults ( SwitchInst *  SI, ConstantInt *  CaseVal, BasicBlock *  CaseDest, BasicBlock **  CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant *>> &  Res, const DataLayout &  DL, const TargetTransformInfo &  TTI  )

static

Try to determine the resulting constant values in phi nodes at the common destination basic block, *CommonDest, for one of the case destionations CaseDest corresponding to value CaseVal (0 for the default case), of a switch instruction SI.

Definition at line 4633 of file SimplifyCFG.cpp.

References C, ConstantFold(), llvm::ISD::ConstantPool, llvm::SwitchInst::getCondition(), llvm::Instruction::getNumSuccessors(), llvm::Instruction::getParent(), llvm::Instruction::getSuccessor(), llvm::Use::getUser(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::BasicBlock::instructionsWithoutDebug(), llvm::Instruction::isExceptionalTerminator(), llvm::Instruction::isTerminator(), LookupConstant(), llvm::Value::uses(), and ValidLookupTableConstant().

Referenced by InitializeUniqueCases(), and SwitchToLookupTable().

GetConstantInt()

static ConstantInt* GetConstantInt ( Value *  V, const DataLayout &  DL  )

static

Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.

Return NULL if value is not a constant int.

Definition at line 401 of file SimplifyCFG.cpp.

References C, llvm::dyn_cast(), llvm::SmallVectorBase::empty(), llvm::ConstantInt::get(), llvm::Value::getContext(), llvm::ConstantExpr::getIntegerCast(), llvm::DataLayout::getIntPtrType(), llvm::ConstantRange::getLower(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::ConstantRange::getUpper(), llvm::ConstantInt::getValue(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ConstantRange::inverse(), llvm::ConstantRange::isEmptySet(), llvm::Type::isPointerTy(), llvm::APInt::isPowerOf2(), llvm::ConstantRange::isSizeLargerThan(), llvm::PatternMatch::m_Add(), llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Value(), llvm::ConstantRange::makeAllowedICmpRegion(), llvm::BitmaskEnumDetail::Mask(), llvm::PatternMatch::match(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorTemplateBase< T >::push_back(), second, and llvm::ConstantRange::subtract().

Referenced by EraseTerminatorAndDCECond().

HasBranchWeights()

static bool HasBranchWeights ( const Instruction *  I )

inlinestatic

Definition at line 965 of file SimplifyCFG.cpp.

References llvm::Instruction::getMetadata(), llvm::MDNode::getOperand(), and llvm::LLVMContext::MD_prof.

Referenced by eliminateDeadSwitchCases(), FitWeights(), SimplifyIndirectBrOnSelect(), SimplifySwitchOnSelect(), and TurnSwitchRangeIntoICmp().

HoistThenElseCodeToIf()

static bool HoistThenElseCodeToIf ( BranchInst *  BI, const TargetTransformInfo &  TTI  )

static

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

References AddPredecessorToBlock(), llvm::Instruction::andIRFlags(), llvm::Instruction::applyMergedLocation(), assert(), llvm::BasicBlock::begin(), llvm::Instruction::clone(), llvm::combineMetadata(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dyn_cast(), EraseTerminatorAndDCECond(), llvm::BranchInst::getCondition(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::Value::getType(), llvm::iplist_impl< IntrusiveListT, TraitsT >::insert(), llvm::Instruction::isIdenticalToWhenDefined(), llvm::TargetTransformInfo::isProfitableToHoist(), isSafeToHoistInvoke(), llvm::isSafeToSpeculativelyExecute(), llvm::Instruction::isTerminator(), llvm::Type::isVoidTy(), llvm::LLVMContext::MD_access_group, llvm::LLVMContext::MD_align, llvm::LLVMContext::MD_dereferenceable, llvm::LLVMContext::MD_dereferenceable_or_null, llvm::LLVMContext::MD_fpmath, llvm::LLVMContext::MD_invariant_group, llvm::LLVMContext::MD_invariant_load, llvm::LLVMContext::MD_mem_parallel_loop_access, llvm::LLVMContext::MD_nonnull, llvm::LLVMContext::MD_range, llvm::LLVMContext::MD_tbaa, passingValueIsAlwaysUndefined(), llvm::Value::replaceAllUsesWith(), SI, llvm::iplist_impl< IntrusiveListT, TraitsT >::splice(), llvm::successors(), and llvm::Value::takeName().

Referenced by allPredecessorsComeFromSameSource().

InitializeUniqueCases()

static bool InitializeUniqueCases ( SwitchInst *  SI, PHINode *&  PHI, BasicBlock *&  CommonDest, SwitchCaseResultVectorTy &  UniqueResults, Constant *&  DefaultResult, const DataLayout &  DL, const TargetTransformInfo &  TTI, uintptr_t  MaxUniqueResults, uintptr_t  MaxCasesPerResult  )

static

Definition at line 4723 of file SimplifyCFG.cpp.

References llvm::SwitchInst::cases(), first, GetCaseResults(), llvm::SwitchInst::getDefaultDest(), llvm::BasicBlock::getFirstNonPHIOrDbg(), MapCaseToResult(), and Results.

Referenced by switchToSelect().

isProfitableToFoldUnconditional()

static bool isProfitableToFoldUnconditional ( BranchInst *  SI1, BranchInst *  SI2, Instruction *  Cond, SmallVectorImpl< PHINode *> &  PhiNodes  )

static

Return true if it is safe and profitable to merge these two terminator instructions together, where SI1 is an unconditional branch.

PhiNodes will store all PHI nodes in common successors.

Definition at line 254 of file SimplifyCFG.cpp.

References assert(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dyn_cast(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingValueForBlock(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BranchInst::isConditional(), llvm::BranchInst::isUnconditional(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::succ_begin(), llvm::succ_end(), and llvm::successors().

Referenced by llvm::FoldBranchToCommonDest().

isSafeToHoistInvoke()

static bool isSafeToHoistInvoke ( BasicBlock *  BB1, BasicBlock *  BB2, Instruction *  I1, Instruction *  I2  )

static

Definition at line 1227 of file SimplifyCFG.cpp.

References I, passingValueIsAlwaysUndefined(), and llvm::successors().

Referenced by HoistThenElseCodeToIf().

isSafeToSpeculateStore()

static Value* isSafeToSpeculateStore ( Instruction *  I, BasicBlock *  BrBB, BasicBlock *  StoreBB, BasicBlock *  EndBB  )

static

Determine if we can hoist sink a sole store instruction out of a conditional block.

We are looking for code like the following: BrBB: store i32 add, i32* arrayidx2 ... // No other stores or function calls (we could be calling a memory ... // function). cmp = icmp ult x, y br i1 cmp, label EndBB, label ThenBB ThenBB: store i32 add5, i32* arrayidx2 br label EndBB EndBB: ... We are going to transform this into: BrBB: store i32 add, i32* arrayidx2 ... // cmp = icmp ult x, y add.add5 = select i1 cmp, i32 add, add5 store i32 add.add5, i32* arrayidx2 ...

Returns

The pointer to the value of the previous store if the store can be hoisted into the predecessor block. 0 otherwise.

Definition at line 1865 of file SimplifyCFG.cpp.

References llvm::dyn_cast(), llvm::StoreInst::getPointerOperand(), I, llvm::BasicBlock::instructionsWithoutDebug(), llvm::StoreInst::isSimple(), llvm::reverse(), and SI.

Referenced by SpeculativelyExecuteBB().

isSwitchDense()

static bool isSwitchDense ( ArrayRef< int64_t >  Values )

static

Definition at line 5484 of file SimplifyCFG.cpp.

References llvm::ArrayRef< T >::back(), llvm::ArrayRef< T >::front(), and llvm::ArrayRef< T >::size().

Referenced by ReduceSwitchRange().

LookupConstant()

static Constant* LookupConstant ( Value *  V, const SmallDenseMap< Value *, Constant *> &  ConstantPool  )

static

If V is a Constant, return it.

Otherwise, try to look up its constant value in ConstantPool, returning 0 if it's not there.

Definition at line 4587 of file SimplifyCFG.cpp.

References C, and llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup().

Referenced by ConstantFold(), and GetCaseResults().

MapCaseToResult()

static uintptr_t MapCaseToResult ( ConstantInt *  CaseVal, SwitchCaseResultVectorTy &  UniqueResults, Constant *  Result  )

static

Definition at line 4704 of file SimplifyCFG.cpp.

Referenced by InitializeUniqueCases().

mergeCleanupPad()

static bool mergeCleanupPad ( CleanupReturnInst *  RI )

static

Definition at line 4014 of file SimplifyCFG.cpp.

References llvm::BasicBlock::begin(), llvm::classifyEHPersonality(), llvm::CoreCLR, llvm::BranchInst::Create(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::dbgs(), DupRet, llvm::dyn_cast(), E, llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::eraseFromParent(), EraseTerminatorAndDCECond(), llvm::FoldReturnIntoUncondBranch(), llvm::BasicBlock::front(), llvm::UndefValue::get(), llvm::CleanupReturnInst::getCleanupPad(), llvm::Value::getContext(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::Function::getPersonalityFn(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::CleanupReturnInst::getUnwindDest(), I, llvm::Instruction::isTerminator(), LLVM_DEBUG, P, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_empty(), llvm::pred_end(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T >::push_back(), removeEmptyCleanup(), llvm::BasicBlock::removePredecessor(), llvm::removeUnwindEdge(), llvm::Value::replaceAllUsesWith(), SI, SimplifyCondBranchToTwoReturns(), and llvm::SmallVectorBase::size().

mergeConditionalStores()

static bool mergeConditionalStores ( BranchInst *  PBI, BranchInst *  QBI, const DataLayout &  DL  )

static

Definition at line 3064 of file SimplifyCFG.cpp.

References llvm::Address, llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getSingleSuccessor(), llvm::BranchInst::getSuccessor(), llvm::Value::hasNUses(), llvm::SmallPtrSetImpl< PtrType >::insert(), mergeConditionalStoreToAddress(), P, llvm::set_intersect(), SI, and std::swap().

Referenced by allPredecessorsComeFromSameSource(), and SimplifyCondBranchToCondBranch().

mergeConditionalStoreToAddress()

static bool mergeConditionalStoreToAddress ( BasicBlock *  PTB, BasicBlock *  PFB, BasicBlock *  QTB, BasicBlock *  QFB, BasicBlock *  PostBB, Value *  Address, bool  InvertPCond, bool  InvertQCond, const DataLayout &  DL  )

static

Definition at line 2908 of file SimplifyCFG.cpp.

References E, llvm::BasicBlock::end(), ensureValueAvailableInSuccessor(), llvm::Instruction::eraseFromParent(), findUniqueStoreInBlocks(), llvm::Instruction::getAAMetadata(), llvm::DataLayout::getABITypeAlignment(), llvm::StoreInst::getAlignment(), llvm::BasicBlock::getFirstInsertionPt(), llvm::Operator::getOpcode(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::StoreInst::getValueOperand(), I, llvm::Type::isPointerTy(), llvm::Instruction::isTerminator(), llvm::StoreInst::isUnordered(), llvm::Instruction::mayReadOrWriteMemory(), MergeCondStoresAggressively, N, PHINodeFoldingThreshold, llvm::pred_begin(), llvm::pred_end(), llvm::Instruction::setAAMetadata(), llvm::StoreInst::setAlignment(), SI, llvm::SplitBlockAndInsertIfThen(), and llvm::SplitBlockPredecessors().

Referenced by mergeConditionalStores().

passingValueIsAlwaysUndefined()

static bool passingValueIsAlwaysUndefined ( Value *  V, Instruction *  I  )

static

Check if passing a value to an instruction will cause undefined behavior.

Definition at line 5919 of file SimplifyCFG.cpp.

References C, llvm::dyn_cast(), llvm::BasicBlock::end(), GEP, llvm::Instruction::getFunction(), llvm::Instruction::getParent(), I, llvm::Constant::isNullValue(), llvm::NullPointerIsDefined(), llvm::Value::use_empty(), and llvm::Value::user_begin().

Referenced by HoistThenElseCodeToIf(), isSafeToHoistInvoke(), removeUndefIntroducingPredecessor(), and SpeculativelyExecuteBB().

ReduceSwitchRange()

static bool ReduceSwitchRange ( SwitchInst *  SI, IRBuilder<> &  Builder, const DataLayout &  DL, const TargetTransformInfo &  TTI  )

static

Try to transform a switch that has "holes" in it to a contiguous sequence of cases.

A switch such as: switch(i) {case 5: case 9: case 13: case 17:} can be range-reduced to: switch ((i-5) / 4) {case 0: case 1: case 2: case 3:}.

This converts a sparse switch into a dense switch which allows better lowering and could also allow transforming into a lookup table.

Definition at line 5503 of file SimplifyCFG.cpp.

References C, llvm::SwitchInst::cases(), llvm::BranchInst::Create(), llvm::IRBuilder< T, Inserter >::CreateLShr(), llvm::IRBuilder< T, Inserter >::CreateOr(), llvm::IRBuilder< T, Inserter >::CreateShl(), llvm::IRBuilder< T, Inserter >::CreateSub(), eliminateDeadSwitchCases(), EraseTerminatorAndDCECond(), llvm::DataLayout::fitsInLegalInteger(), ForwardSwitchConditionToPHI(), llvm::ConstantInt::get(), llvm::IndirectBrInst::getAddress(), llvm::SwitchInst::getCondition(), llvm::Value::getContext(), llvm::IndirectBrInst::getDestination(), llvm::SwitchInst::getNumCases(), llvm::IndirectBrInst::getNumDestinations(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::Value::getType(), llvm::GreatestCommonDivisor64(), llvm::BasicBlock::hasAddressTaken(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BasicBlock::instructionsWithoutDebug(), llvm::isPowerOf2_64(), isSwitchDense(), llvm::Log2_64(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::IndirectBrInst::removeDestination(), llvm::BasicBlock::removePredecessor(), llvm::User::replaceUsesOfWith(), llvm::MCID::Select, llvm::IRBuilderBase::SetInsertPoint(), SI, SimplifyIndirectBrOnSelect(), SimplifySwitchOnSelect(), llvm::sort(), SwitchToLookupTable(), switchToSelect(), and TurnSwitchRangeIntoICmp().

removeEmptyCleanup()

static bool removeEmptyCleanup ( CleanupReturnInst *  RI )

static

Definition at line 3877 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), llvm::Intrinsic::dbg_declare, llvm::Intrinsic::dbg_label, llvm::Intrinsic::dbg_value, llvm::dyn_cast(), E, llvm::BasicBlock::eraseFromParent(), llvm::PHINode::getBasicBlockIndex(), llvm::CleanupReturnInst::getCleanupPad(), llvm::BasicBlock::getFirstNonPHI(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::IntrinsicInst::getIntrinsicID(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::CleanupReturnInst::getUnwindDest(), llvm::Value::hasOneUse(), I, llvm::ARM_PROC::IE, llvm::Intrinsic::lifetime_end, llvm::Instruction::moveBefore(), pred, llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::PHINode::removeIncomingValue(), llvm::removeUnwindEdge(), llvm::User::replaceUsesOfWith(), and llvm::Value::use_empty().

Referenced by mergeCleanupPad().

RemoveSwitchAfterSelectConversion()

static void RemoveSwitchAfterSelectConversion ( SwitchInst *  SI, PHINode *  PHI, Value *  SelectValue, IRBuilder<> &  Builder  )

static

Definition at line 4817 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::Instruction::eraseFromParent(), llvm::PHINode::getBasicBlockIndex(), llvm::SwitchInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::SwitchInst::getSuccessor(), llvm::PHINode::removeIncomingValue(), and llvm::BasicBlock::removePredecessor().

Referenced by switchToSelect().

removeUndefIntroducingPredecessor()

static bool removeUndefIntroducingPredecessor ( BasicBlock *  BB )

static

If BB has an incoming value that will always trigger undefined behavior (eg.

null pointer dereference), remove the branch leading here.

Definition at line 5972 of file SimplifyCFG.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::ConstantFoldTerminator(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::IRBuilder< T, Inserter >::CreateUnreachable(), llvm::dbgs(), llvm::DeleteDeadBlock(), llvm::EliminateDuplicatePHINodes(), llvm::Instruction::eraseFromParent(), FoldTwoEntryPHINode(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isUnconditional(), LLVM_DEBUG, llvm::MergeBlockIntoPredecessor(), passingValueIsAlwaysUndefined(), llvm::BasicBlock::phis(), llvm::pred_empty(), llvm::BasicBlock::removePredecessor(), llvm::IRBuilderBase::SetInsertPoint(), SinkCommon, and SinkCommonCodeFromPredecessors().

reuseTableCompare()

static void reuseTableCompare ( User *  PhiUser, BasicBlock *  PhiBlock, BranchInst *  RangeCheckBranch, Constant *  DefaultValue, const SmallVectorImpl< std::pair< ConstantInt *, Constant *>> &  Values  )

static

Try to reuse the switch table index compare.

Following pattern:

if (idx < tablesize)
   r = table[idx]; // table does not contain default_value
else
   r = default_value;
if (r != default_value)
   ...

Is optimized to:

cond = idx < tablesize;
if (cond)
   r = table[idx];
else
   r = default_value;
if (cond)
   ...

Jump threading will then eliminate the second if(cond).

Definition at line 5178 of file SimplifyCFG.cpp.

References assert(), llvm::dyn_cast(), E, llvm::ConstantInt::get(), llvm::BranchInst::getCondition(), llvm::ConstantInt::getFalse(), llvm::ConstantExpr::getICmp(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), llvm::BasicBlock::getUniquePredecessor(), llvm::pred_begin(), llvm::pred_end(), and llvm::Value::replaceAllUsesWith().

Referenced by SwitchToLookupTable().

SafeToMergeTerminators()

static bool SafeToMergeTerminators ( Instruction *  SI1, Instruction *  SI2, SmallSetVector< BasicBlock *, 4 > *  FailBlocks = nullptr  )

static

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

Definition at line 222 of file SimplifyCFG.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), Fail, llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getParent(), llvm::succ_begin(), llvm::succ_end(), and llvm::successors().

Referenced by FitWeights(), and llvm::FoldBranchToCommonDest().

setBranchWeights() [1/2]

static void setBranchWeights ( SwitchInst *  SI, ArrayRef< uint32_t >  Weights  )

static

Definition at line 780 of file SimplifyCFG.cpp.

References llvm::any_of(), llvm::BasicBlock::getContext(), llvm::Instruction::getParent(), llvm::LLVMContext::MD_prof, N, llvm::Instruction::setMetadata(), and llvm::RISCVFenceField::W.

Referenced by eliminateDeadSwitchCases(), FitWeights(), llvm::FoldBranchToCommonDest(), setBranchWeights(), SimplifyCondBranchToCondBranch(), SimplifyIndirectBrOnSelect(), SimplifyTerminatorOnSelect(), sumEdgeCount(), and TurnSwitchRangeIntoICmp().

setBranchWeights() [2/2]

static void setBranchWeights ( Instruction *  I, uint32_t  TrueWeight, uint32_t  FalseWeight  )

static

Definition at line 791 of file SimplifyCFG.cpp.

References assert(), llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::dbgs(), EliminateBlockCases(), EraseTerminatorAndDCECond(), llvm::BasicBlock::getContext(), llvm::Instruction::getMetadata(), llvm::SwitchInst::getNumCases(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getValue(), llvm::APInt::getZExtValue(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::LLVMContext::MD_prof, N, llvm::SwitchInst::removeCase(), llvm::BasicBlock::removePredecessor(), setBranchWeights(), llvm::Instruction::setMetadata(), SI, llvm::successors(), std::swap(), llvm::APInt::ult(), llvm::Value::Value(), and ValuesOverlap().

ShouldBuildLookupTable()

static bool ShouldBuildLookupTable ( SwitchInst *  SI, uint64_t  TableSize, const TargetTransformInfo &  TTI, const DataLayout &  DL, const SmallDenseMap< PHINode *, Type *> &  ResultTypes  )

static

Determine whether a lookup table should be built for this switch, based on the number of cases, size of the table, and the types of the results.

Definition at line 5118 of file SimplifyCFG.cpp.

References llvm::SwitchInst::getNumCases(), llvm::TargetTransformInfo::isTypeLegal(), and UINT64_MAX.

Referenced by SwitchToLookupTable().

SimplifyBranchOnICmpChain()

static bool SimplifyBranchOnICmpChain ( BranchInst *  BI, IRBuilder<> &  Builder, const DataLayout &  DL  )

static

The specified branch is a conditional branch.

Check to see if it is branching on an or/and chain of icmp instructions, and fold it into a switch instruction if so.

Definition at line 3651 of file SimplifyCFG.cpp.

References llvm::SwitchInst::addCase(), llvm::PHINode::addIncoming(), AddPredecessorToBlock(), llvm::array_pod_sort(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::BasicBlock::begin(), ConstantIntSortPredicate(), llvm::IRBuilder< T, Inserter >::CreateCondBr(), llvm::IRBuilder< T, Inserter >::CreatePtrToInt(), llvm::IRBuilder< T, Inserter >::CreateSwitch(), llvm::dbgs(), llvm::dyn_cast(), E, llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::Instruction::eraseFromParent(), EraseTerminatorAndDCECond(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getFirstNonPHI(), llvm::PHINode::getIncomingValueForBlock(), llvm::DataLayout::getIntPtrType(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getOpcode(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::ResumeInst::getValue(), llvm::Type::isPointerTy(), LLVM_DEBUG, llvm::IRBuilderBase::SetInsertPoint(), llvm::SmallVectorBase::size(), llvm::BasicBlock::splitBasicBlock(), and std::swap().

Referenced by allPredecessorsComeFromSameSource().

SimplifyCondBranchToCondBranch()

static bool SimplifyCondBranchToCondBranch ( BranchInst *  PBI, BranchInst *  BI, const DataLayout &  DL  )

static

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

References llvm::PHINode::addIncoming(), AddPredecessorToBlock(), assert(), llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), llvm::IRBuilder< T, Inserter >::CreateNot(), llvm::IRBuilder< T, Inserter >::CreateOr(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dbgs(), extractPredSuccWeights(), FitWeights(), llvm::StringRef::front(), llvm::ConstantInt::get(), llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Type::getInt1Ty(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isConditional(), LLVM_DEBUG, mergeConditionalStores(), MergeCondStores, P, llvm::BasicBlock::phis(), llvm::pred_begin(), llvm::pred_end(), setBranchWeights(), llvm::BranchInst::setCondition(), and llvm::BranchInst::setSuccessor().

Referenced by allPredecessorsComeFromSameSource().

SimplifyCondBranchToTwoReturns()

static bool SimplifyCondBranchToTwoReturns ( BranchInst *  BI, IRBuilder<> &  Builder  )

static

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

References assert(), llvm::IRBuilder< T, Inserter >::CreateRet(), llvm::IRBuilder< T, Inserter >::CreateRetVoid(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dbgs(), EraseTerminatorAndDCECond(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Instruction::getParent(), llvm::ReturnInst::getReturnValue(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isConditional(), llvm::Instruction::isTerminator(), LLVM_DEBUG, llvm::BasicBlock::removePredecessor(), and llvm::IRBuilderBase::SetInsertPoint().

Referenced by mergeCleanupPad().

SimplifyIndirectBrOnSelect()

static bool SimplifyIndirectBrOnSelect ( IndirectBrInst *  IBI, SelectInst *  SI  )

static

Definition at line 3512 of file SimplifyCFG.cpp.

References llvm::SwitchInst::addCase(), llvm::PHINode::addIncoming(), assert(), llvm::BasicBlock::begin(), llvm::SwitchInst::case_default(), llvm::BasicBlock::Create(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::SwitchInst::findCaseDest(), llvm::SwitchInst::findCaseValue(), llvm::BasicBlock::front(), llvm::BlockAddress::getBasicBlock(), GetBranchWeights(), llvm::SelectInst::getCondition(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::SwitchInst::getDefaultDest(), llvm::ConstantInt::getFalse(), llvm::SelectInst::getFalseValue(), llvm::SwitchInst::getNumCases(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::CmpInst::getPredicate(), llvm::BasicBlock::getSinglePredecessor(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getTrue(), llvm::SelectInst::getTrueValue(), HasBranchWeights(), llvm::Value::hasOneUse(), llvm::CmpInst::ICMP_EQ, llvm::Value::replaceAllUsesWith(), setBranchWeights(), llvm::IRBuilderBase::SetCurrentDebugLocation(), llvm::IRBuilderBase::SetInsertPoint(), llvm::User::setOperand(), SI, llvm::SimplifyInstruction(), SimplifyTerminatorOnSelect(), std::swap(), and llvm::Instruction::user_back().

Referenced by ReduceSwitchRange().

SimplifySwitchOnSelect()

static bool SimplifySwitchOnSelect ( SwitchInst *  SI, SelectInst *  Select  )

static

Definition at line 3476 of file SimplifyCFG.cpp.

References llvm::dyn_cast(), llvm::SwitchInst::findCaseValue(), GetBranchWeights(), llvm::SelectInst::getCondition(), llvm::SelectInst::getFalseValue(), llvm::SwitchInst::getNumCases(), llvm::SelectInst::getTrueValue(), HasBranchWeights(), SimplifyTerminatorOnSelect(), and llvm::SmallVectorBase::size().

Referenced by ReduceSwitchRange().

SimplifyTerminatorOnSelect()

static bool SimplifyTerminatorOnSelect ( Instruction *  OldTerm, Value *  Cond, BasicBlock *  TrueBB, BasicBlock *  FalseBB, uint32_t  TrueWeight, uint32_t  FalseWeight  )

static

Definition at line 3413 of file SimplifyCFG.cpp.

References llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::IRBuilder< T, Inserter >::CreateCondBr(), EraseTerminatorAndDCECond(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::Instruction::getParent(), llvm::BasicBlock::removePredecessor(), setBranchWeights(), llvm::IRBuilderBase::SetCurrentDebugLocation(), and llvm::successors().

Referenced by SimplifyIndirectBrOnSelect(), and SimplifySwitchOnSelect().

SinkCommonCodeFromPredecessors()

static bool SinkCommonCodeFromPredecessors ( BasicBlock *  BB )

static

Check whether BB's predecessors end with unconditional branches.

If it is true, sink any common code from the predecessors to BB. We also allow one predecessor to end with conditional branch (but no more than one).

Definition at line 1685 of file SimplifyCFG.cpp.

References B, canSinkInstructions(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isSafeToSpeculativelyExecute(), LLVM_DEBUG, llvm::predecessors(), llvm::SmallVectorTemplateBase< T >::push_back(), sinkLastInstruction(), llvm::SmallVectorBase::size(), llvm::SplitBlockPredecessors(), and T.

Referenced by removeUndefIntroducingPredecessor().

sinkLastInstruction()

static bool sinkLastInstruction ( ArrayRef< BasicBlock *>  Blocks )

static

Definition at line 1524 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), llvm::all_of(), llvm::Instruction::andIRFlags(), llvm::any_of(), llvm::Instruction::applyMergedLocation(), assert(), llvm::SmallVectorImpl< T >::clear(), llvm::combineMetadataForCSE(), llvm::PHINode::Create(), llvm::dyn_cast(), E, llvm::Instruction::eraseFromParent(), Fail, llvm::SmallVectorTemplateCommon< T >::front(), llvm::Instruction::getDebugLoc(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::User::getOperandUse(), llvm::Instruction::getParent(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getPrevNode(), llvm::Value::hasOneUse(), llvm::Instruction::moveBefore(), llvm::RISCVFenceField::O, llvm::operator*(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::Use::set(), llvm::SmallVectorBase::size(), and llvm::Value::user_begin().

Referenced by llvm::GVNExpression::Expression::dump(), and SinkCommonCodeFromPredecessors().

SpeculativelyExecuteBB()

static bool SpeculativelyExecuteBB ( BranchInst *  BI, BasicBlock *  ThenBB, const TargetTransformInfo &  TTI  )

static

Speculate a conditional basic block flattening the CFG.

Note that this is a very risky transform currently. Speculating instructions like this is most often not desirable. Instead, there is an MI pass which can do it with full awareness of the resource constraints. However, some cases are "obvious" and we should do directly. An example of this is speculating a single, reasonably cheap instruction.

There is only one distinct advantage to flattening the CFG at the IR level: it makes very common but simplistic optimizations such as are common in instcombine and the DAG combiner more powerful by removing CFG edges and modeling their effects with easier to reason about SSA value graphs.

An illustration of this transform is turning this IR:

BB:
  %cmp = icmp ult %x, %y
  br i1 %cmp, label %EndBB, label %ThenBB
ThenBB:
  %sub = sub %x, %y
  br label BB2
EndBB:
  %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ]
  ...

Into this IR:

BB:
  %cmp = icmp ult %x, %y
  %sub = sub %x, %y
  %cond = select i1 %cmp, 0, %sub
  ...

Returns

true if the conditional block is removed.

Definition at line 1937 of file SimplifyCFG.cpp.

References llvm::Instruction::applyMergedLocation(), assert(), llvm::BasicBlock::begin(), llvm::ComputeSpeculationCost(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dbgs(), llvm::Instruction::dropUnknownNonDebugMetadata(), llvm::dyn_cast(), E, llvm::BasicBlock::end(), llvm::Instruction::eraseFromParent(), llvm::BranchInst::getCondition(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::Instruction::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::StoreInst::getValueOperand(), llvm::Value::hasNUses(), HoistCondStores, I, isSafeToSpeculateStore(), llvm::isSafeToSpeculativelyExecute(), LLVM_DEBUG, llvm::Instruction::mayHaveSideEffects(), llvm::User::op_begin(), llvm::User::op_end(), passingValueIsAlwaysUndefined(), PHINodeFoldingThreshold, llvm::BasicBlock::phis(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::User::setOperand(), llvm::iplist_impl< IntrusiveListT, TraitsT >::splice(), std::swap(), and llvm::TargetTransformInfo::TCC_Basic.

Referenced by allPredecessorsComeFromSameSource().

STATISTIC() [1/7]

STATISTIC	(	NumBitMaps	,
		"Number of switch instructions turned into bitmaps"
	)

STATISTIC() [2/7]

STATISTIC	(	NumLinearMaps	,
		"Number of switch instructions turned into linear mapping"
	)

STATISTIC() [3/7]

STATISTIC	(	NumLookupTables	,
		"Number of switch instructions turned into lookup tables"
	)

STATISTIC() [4/7]

STATISTIC	(	NumLookupTablesHoles	,
		"Number of switch instructions turned into lookup tables (holes checked)"
	)

STATISTIC() [5/7]

STATISTIC	(	NumTableCmpReuses	,
		"Number of reused switch table lookup compares"
	)

STATISTIC() [6/7]

STATISTIC	(	NumSinkCommons	,
		"Number of common instructions sunk down to the end block"
	)

STATISTIC() [7/7]

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

SwitchToLookupTable()

static bool SwitchToLookupTable ( SwitchInst *  SI, IRBuilder<> &  Builder, const DataLayout &  DL, const TargetTransformInfo &  TTI  )

static

If the switch is only used to initialize one or more phi nodes in a common successor block with different constant values, replace the switch with lookup tables.

Definition at line 5244 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), assert(), llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), llvm::SwitchInst::cases(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::BasicBlock::Create(), llvm::IRBuilder< T, Inserter >::CreateBr(), llvm::IRBuilder< T, Inserter >::CreateCondBr(), llvm::IRBuilder< T, Inserter >::CreateICmpULT(), llvm::IRBuilder< T, Inserter >::CreateLShr(), llvm::IRBuilder< T, Inserter >::CreateRet(), llvm::IRBuilder< T, Inserter >::CreateSub(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), llvm::IRBuilder< T, Inserter >::CreateZExtOrTrunc(), E, llvm::empty(), llvm::Instruction::eraseFromParent(), llvm::ConstantInt::get(), GetCaseResults(), llvm::SwitchInst::getCondition(), llvm::Module::getContext(), llvm::SwitchInst::getDefaultDest(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Type::getInt1Ty(), llvm::APInt::getLimitedValue(), llvm::SwitchInst::getNumCases(), llvm::SwitchInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Type::getPrimitiveSizeInBits(), llvm::SwitchInst::getSuccessor(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), I, llvm::Constant::isNullValue(), llvm::max(), llvm::Mod, llvm::NextPowerOf2(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::BasicBlock::removePredecessor(), Results, reuseTableCompare(), llvm::IRBuilderBase::SetInsertPoint(), llvm::Value::setName(), llvm::APInt::sgt(), ShouldBuildLookupTable(), llvm::TargetTransformInfo::shouldBuildLookupTables(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::size(), llvm::APInt::slt(), UINT64_MAX, and llvm::Value::users().

Referenced by ReduceSwitchRange().

switchToSelect()

static bool switchToSelect ( SwitchInst *  SI, IRBuilder<> &  Builder, const DataLayout &  DL, const TargetTransformInfo &  TTI  )

static

If the switch is only used to initialize one or more phi nodes in a common successor block with only two different constant values, replace the switch with select.

Definition at line 4841 of file SimplifyCFG.cpp.

References assert(), ConvertTwoCaseSwitch(), llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateInBoundsGEP(), llvm::IRBuilder< T, Inserter >::CreateIntCast(), llvm::IRBuilder< T, Inserter >::CreateLoad(), llvm::IRBuilder< T, Inserter >::CreateLShr(), llvm::IRBuilder< T, Inserter >::CreateMul(), llvm::IRBuilder< T, Inserter >::CreateTrunc(), llvm::IRBuilder< T, Inserter >::CreateZExt(), llvm::IRBuilder< T, Inserter >::CreateZExtOrTrunc(), llvm::dyn_cast(), E, llvm::DataLayout::fitsInLegalInteger(), GEP, llvm::IntegerType::get(), llvm::ConstantInt::get(), llvm::ArrayType::get(), llvm::ConstantArray::get(), llvm::IntegerType::getBitWidth(), llvm::SwitchInst::getCondition(), llvm::Type::getContext(), llvm::Module::getContext(), llvm::IRBuilderBase::getInt32(), llvm::DataLayout::getPrefTypeAlignment(), llvm::Value::getType(), llvm::ConstantInt::getValue(), llvm::GlobalValue::Global, I, InitializeUniqueCases(), IT, Kind, llvm_unreachable, llvm::GlobalValue::PrivateLinkage, RemoveSwitchAfterSelectConversion(), llvm::IRBuilderBase::SetInsertPoint(), and llvm::APInt::zext().

Referenced by ReduceSwitchRange().

tryCSEWithPredecessor()

static bool tryCSEWithPredecessor ( Instruction *  Inst, BasicBlock *  PB  )

static

Return true if the given instruction is available in its predecessor block.

If yes, the instruction will be removed.

Definition at line 2501 of file SimplifyCFG.cpp.

References llvm::Instruction::eraseFromParent(), I, llvm::Instruction::isIdenticalTo(), and llvm::Value::replaceAllUsesWith().

Referenced by llvm::FoldBranchToCommonDest().

TryToMergeLandingPad()

static bool TryToMergeLandingPad ( LandingPadInst *  LPad, BranchInst *  BI, BasicBlock *  BB  )

static

Given an block with only a single landing pad and a unconditional branch try to find another basic block which this one can be merged with.

This handles cases where we have multiple invokes with unique landing pads, but a shared handler.

We specifically choose to not worry about merging non-empty blocks here. That is a PRE/scheduling problem and is best solved elsewhere. In practice, the optimizer produces empty landing pad blocks quite frequently when dealing with exception dense code. (see: instcombine, gvn, if-else sinking in this file)

This is primarily a code size optimization. We need to avoid performing any transform which might inhibit optimization (such as our ability to specialize a particular handler via tail commoning). We do this by not merging any blocks which require us to introduce a phi. Since the same values are flowing through both blocks, we don't lose any ability to specialize. If anything, we make such specialization more likely.

TODO - This transformation could remove entries from a phi in the target block when the inputs in the phi are the same for the two blocks being merged. In some cases, this could result in removal of the PHI entirely.

Definition at line 5698 of file SimplifyCFG.cpp.

References assert(), llvm::IRBuilder< T, Inserter >::CreateUnreachable(), llvm::dyn_cast(), E, llvm::Instruction::eraseFromParent(), llvm::FoldBranchToCommonDest(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::InvokeInst::getNormalDest(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::getUniqueSuccessor(), llvm::InvokeInst::getUnwindDest(), llvm::BasicBlock::hasNPredecessorsOrMore(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ICmpInst::isEquality(), llvm::Instruction::isIdenticalTo(), llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::InvokeInst::setUnwindDest(), llvm::succ_begin(), llvm::succ_end(), and llvm::TryToSimplifyUncondBranchFromEmptyBlock().

TurnSwitchRangeIntoICmp()

static bool TurnSwitchRangeIntoICmp ( SwitchInst *  SI, IRBuilder<> &  Builder  )

static

Turn a switch with two reachable destinations into an integer range comparison and branch.

Definition at line 4277 of file SimplifyCFG.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::SwitchInst::cases(), CasesAreContiguous(), llvm::IRBuilder< T, Inserter >::CreateAdd(), llvm::IRBuilder< T, Inserter >::CreateCondBr(), llvm::IRBuilder< T, Inserter >::CreateICmpULT(), E, llvm::SmallVectorBase::empty(), llvm::Instruction::eraseFromParent(), llvm::ConstantInt::get(), GetBranchWeights(), llvm::SwitchInst::getCondition(), llvm::Value::getContext(), llvm::SwitchInst::getDefaultDest(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Value::getName(), llvm::ConstantExpr::getNeg(), llvm::SwitchInst::getNumCases(), llvm::Instruction::getParent(), llvm::SwitchInst::getSuccessor(), llvm::ConstantInt::getTrue(), llvm::Value::getType(), HasBranchWeights(), I, llvm::Constant::isNullValue(), llvm::SmallVectorTemplateBase< T >::push_back(), setBranchWeights(), and llvm::SmallVectorBase::size().

Referenced by ReduceSwitchRange().

ValidLookupTableConstant()

static bool ValidLookupTableConstant ( Constant *  C, const TargetTransformInfo &  TTI  )

static

Return true if the backend will be able to handle initializing an array of constants like C.

Definition at line 4560 of file SimplifyCFG.cpp.

References C, llvm::Constant::isDLLImportDependent(), llvm::Constant::isThreadDependent(), and llvm::TargetTransformInfo::shouldBuildLookupTablesForConstant().

Referenced by GetCaseResults().

ValuesOverlap()

static bool ValuesOverlap ( std::vector< ValueEqualityComparisonCase > &  C1, std::vector< ValueEqualityComparisonCase > &  C2  )

static

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

Definition at line 745 of file SimplifyCFG.cpp.

References llvm::array_pod_sort(), std::swap(), llvm::NVPTX::PTXLdStInstCode::V2, and llvm::Value::Value().

Referenced by setBranchWeights().

Variable Documentation

DupRet

cl::opt<bool> DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), cl::desc("Duplicate return instructions into unconditional branches"))

static

Referenced by mergeCleanupPad().

HoistCondStores

cl::opt<bool> HoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))

static

Referenced by SpeculativelyExecuteBB().

MaxSpeculationDepth

cl::opt<unsigned> MaxSpeculationDepth("max-speculation-depth", cl::Hidden, cl::init(10), cl::desc("Limit maximum recursion depth when calculating costs of " "speculatively executed instructions"))

static

Referenced by DominatesMergePoint().

MergeCondStores

cl::opt<bool> MergeCondStores("simplifycfg-merge-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores even if an unconditional store does not " "precede - hoist multiple conditional stores into a single " "predicated store"))

static

Referenced by allPredecessorsComeFromSameSource(), and SimplifyCondBranchToCondBranch().

MergeCondStoresAggressively

cl::opt<bool> MergeCondStoresAggressively("simplifycfg-merge-cond-stores-aggressively", cl::Hidden, cl::init(false), cl::desc("When merging conditional stores, do so even if the resultant " "basic blocks are unlikely to be if-converted as a result"))

static

Referenced by mergeConditionalStoreToAddress().

PHINodeFoldingThreshold

cl::opt<unsigned> PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(2), cl::desc( "Control the amount of phi node folding to perform (default = 2)"))

static

Referenced by FoldTwoEntryPHINode(), mergeConditionalStoreToAddress(), and SpeculativelyExecuteBB().

SinkCommon

cl::opt<bool> SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))

static

Referenced by removeUndefIntroducingPredecessor(), and llvm::SimplifyCFGPass::run().

SpeculateOneExpensiveInst

cl::opt<bool> SpeculateOneExpensiveInst("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))

static

Referenced by DominatesMergePoint().