LLVM API Documentation

Defines | Functions | Variables
SimplifyCFG.cpp File Reference
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalVariable.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.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/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <map>
#include <set>
Include dependency graph for SimplifyCFG.cpp:

Go to the source code of this file.

Defines

#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 (NumSinkCommons,"Number of common instructions sunk down to the end block")
 STATISTIC (NumSpeculations,"Number of speculative executed instructions")
static bool SafeToMergeTerminators (TerminatorInst *SI1, TerminatorInst *SI2)
static bool isProfitableToFoldUnconditional (BranchInst *SI1, BranchInst *SI2, Instruction *Cond, SmallVectorImpl< PHINode * > &PhiNodes)
static void AddPredecessorToBlock (BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred)
static unsigned ComputeSpeculationCost (const User *I, const DataLayout *DL)
static bool DominatesMergePoint (Value *V, BasicBlock *BB, SmallPtrSetImpl< Instruction * > *AggressiveInsts, unsigned &CostRemaining, const DataLayout *DL)
static ConstantIntGetConstantInt (Value *V, const DataLayout *DL)
static void EraseTerminatorInstAndDCECond (TerminatorInst *TI)
static void EliminateBlockCases (BasicBlock *BB, std::vector< ValueEqualityComparisonCase > &Cases)
static bool ValuesOverlap (std::vector< ValueEqualityComparisonCase > &C1, std::vector< ValueEqualityComparisonCase > &C2)
static int ConstantIntSortPredicate (ConstantInt *const *P1, ConstantInt *const *P2)
static bool HasBranchWeights (const Instruction *I)
static void GetBranchWeights (TerminatorInst *TI, SmallVectorImpl< uint64_t > &Weights)
static void FitWeights (MutableArrayRef< uint64_t > Weights)
 Keep halving the weights until all can fit in uint32_t.
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.
static bool HoistThenElseCodeToIf (BranchInst *BI, const DataLayout *DL)
static bool SinkThenElseCodeToEnd (BranchInst *BI1)
static ValueisSafeToSpeculateStore (Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB)
 Determine if we can hoist sink a sole store instruction out of a conditional block.
static bool SpeculativelyExecuteBB (BranchInst *BI, BasicBlock *ThenBB, const DataLayout *DL)
 Speculate a conditional basic block flattening the CFG.
static bool HasNoDuplicateCall (const BasicBlock *BB)
static bool BlockIsSimpleEnoughToThreadThrough (BasicBlock *BB)
static bool FoldCondBranchOnPHI (BranchInst *BI, const DataLayout *DL)
static bool FoldTwoEntryPHINode (PHINode *PN, const DataLayout *DL)
static bool SimplifyCondBranchToTwoReturns (BranchInst *BI, IRBuilder<> &Builder)
static bool ExtractBranchMetadata (BranchInst *BI, uint64_t &ProbTrue, uint64_t &ProbFalse)
static bool checkCSEInPredecessor (Instruction *Inst, BasicBlock *PB)
static bool SimplifyCondBranchToCondBranch (BranchInst *PBI, BranchInst *BI)
static bool SimplifyTerminatorOnSelect (TerminatorInst *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 TryToSimplifyUncondBranchWithICmpInIt (ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI, unsigned BonusInstThreshold, const DataLayout *DL, AssumptionTracker *AT)
static bool SimplifyBranchOnICmpChain (BranchInst *BI, const DataLayout *DL, IRBuilder<> &Builder)
static bool TurnSwitchRangeIntoICmp (SwitchInst *SI, IRBuilder<> &Builder)
static bool EliminateDeadSwitchCases (SwitchInst *SI, const DataLayout *DL, AssumptionTracker *AT)
static PHINodeFindPHIForConditionForwarding (ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex)
static bool ForwardSwitchConditionToPHI (SwitchInst *SI)
static bool ValidLookupTableConstant (Constant *C)
static ConstantLookupConstant (Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool)
static ConstantConstantFold (Instruction *I, const SmallDenseMap< Value *, Constant * > &ConstantPool, const DataLayout *DL)
static bool GetCaseResults (SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * > > &Res, const DataLayout *DL)
static void MapCaseToResult (ConstantInt *CaseVal, SwitchCaseResultVectorTy &UniqueResults, Constant *Result)
static bool InitializeUniqueCases (SwitchInst *SI, const DataLayout *DL, PHINode *&PHI, BasicBlock *&CommonDest, SwitchCaseResultVectorTy &UniqueResults, Constant *&DefaultResult)
static ValueConvertTwoCaseSwitch (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, AssumptionTracker *AT)
static bool ShouldBuildLookupTable (SwitchInst *SI, uint64_t TableSize, const TargetTransformInfo &TTI, const DataLayout *DL, const SmallDenseMap< PHINode *, Type * > &ResultTypes)
static bool SwitchToLookupTable (SwitchInst *SI, IRBuilder<> &Builder, const TargetTransformInfo &TTI, const DataLayout *DL)
static bool removeUndefIntroducingPredecessor (BasicBlock *BB)

Variables

static cl::opt< unsignedPHINodeFoldingThreshold ("phi-node-folding-threshold", cl::Hidden, cl::init(1), cl::desc("Control the amount of phi node folding to perform (default = 1)"))
static cl::opt< boolDupRet ("simplifycfg-dup-ret", cl::Hidden, cl::init(false), cl::desc("Duplicate return instructions into unconditional branches"))
static cl::opt< boolSinkCommon ("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block"))
static cl::opt< boolHoistCondStores ("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), cl::desc("Hoist conditional stores if an unconditional store precedes"))

Define Documentation

#define DEBUG_TYPE   "simplifycfg"

Definition at line 54 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 207 of file SimplifyCFG.cpp.

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

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

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

Definition at line 1682 of file SimplifyCFG.cpp.

References llvm::BasicBlock::begin(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), and llvm::Value::users().

Referenced by FoldCondBranchOnPHI(), and SimplifyCondBranchToCondBranch().

static bool checkCSEInPredecessor ( Instruction Inst,
BasicBlock PB 
) [static]

checkCSEInPredecessor - Return true if the given instruction is available in its predecessor block. If yes, the instruction will be removed.

Definition at line 2050 of file SimplifyCFG.cpp.

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

Referenced by llvm::FoldBranchToCommonDest().

static unsigned ComputeSpeculationCost ( const User I,
const DataLayout DL 
) [static]

ComputeSpeculationCost - Compute an abstract "cost" of speculating the given instruction, which is assumed to be safe to speculate. 1 means cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive.

Definition at line 220 of file SimplifyCFG.cpp.

References llvm::Add, llvm::APIntOps::And(), llvm::Call, ExtractElement(), llvm::ExtractValue, llvm::Operator::getOpcode(), llvm::InsertElement, llvm::isSafeToSpeculativelyExecute(), llvm::SPII::Load, llvm::LShr, llvm::APIntOps::Or(), llvm::MCID::Select, llvm::SExt, llvm::Sub, llvm::Trunc, and llvm::APIntOps::Xor().

Referenced by DominatesMergePoint(), and SpeculativelyExecuteBB().

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

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

References llvm::ARM_PROC::A, llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldInstOperands(), llvm::ISD::ConstantPool, llvm::User::getNumOperands(), llvm::Instruction::getOpcode(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Constant::isAllOnesValue(), llvm::Constant::isNullValue(), LookupConstant(), N, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::MCID::Select.

Referenced by GetCaseResults().

static int ConstantIntSortPredicate ( ConstantInt *const P1,
ConstantInt *const P2 
) [static]
static Value* ConvertTwoCaseSwitch ( const SwitchCaseResultVectorTy &  ResultVector,
Constant DefaultResult,
Value Condition,
IRBuilder<> &  Builder 
) [static]
static bool DominatesMergePoint ( Value V,
BasicBlock BB,
SmallPtrSetImpl< Instruction * > *  AggressiveInsts,
unsigned CostRemaining,
const DataLayout DL 
) [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) 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 274 of file SimplifyCFG.cpp.

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

Referenced by FoldTwoEntryPHINode().

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

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

Definition at line 601 of file SimplifyCFG.cpp.

References llvm::LibFunc::remove.

static bool EliminateDeadSwitchCases ( SwitchInst SI,
const DataLayout DL,
AssumptionTracker AT 
) [static]
static void EraseTerminatorInstAndDCECond ( TerminatorInst TI) [static]
static bool ExtractBranchMetadata ( BranchInst BI,
uint64_t &  ProbTrue,
uint64_t &  ProbFalse 
) [static]

ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the probabilities of the branch taking each edge. Fills in the two APInt parameters and return true, or returns false if no or invalid metadata was found.

Definition at line 2033 of file SimplifyCFG.cpp.

References llvm::dyn_cast(), llvm::Instruction::getMetadata(), llvm::ConstantInt::getValue(), llvm::APInt::getZExtValue(), llvm::BranchInst::isConditional(), and llvm::LLVMContext::MD_prof.

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

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

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

References llvm::BasicBlock::begin(), llvm::MCID::Branch, llvm::dyn_cast(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BranchInst::isUnconditional(), and llvm::TargetOpcode::PHI.

Referenced by ForwardSwitchConditionToPHI().

static void FitWeights ( MutableArrayRef< uint64_t >  Weights) [static]

Keep halving the weights until all can fit in uint32_t.

Definition at line 837 of file SimplifyCFG.cpp.

References llvm::MutableArrayRef< T >::begin(), llvm::countLeadingZeros(), and llvm::MutableArrayRef< T >::end().

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

static bool FoldCondBranchOnPHI ( BranchInst BI,
const DataLayout DL 
) [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 1709 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::dyn_cast(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT >, KeyT, ValueT, KeyInfoT >::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::TerminatorInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getType(), llvm::ConstantInt::getZExtValue(), HasNoDuplicateCall(), llvm::Value::hasOneUse(), llvm::iplist< NodeTy, Traits >::insert(), llvm::Type::isIntegerTy(), N, llvm::User::op_begin(), llvm::User::op_end(), llvm::BasicBlock::removePredecessor(), llvm::Value::setName(), llvm::TerminatorInst::setSuccessor(), and llvm::SimplifyInstruction().

static bool FoldTwoEntryPHINode ( PHINode PN,
const DataLayout DL 
) [static]
static bool ForwardSwitchConditionToPHI ( SwitchInst SI) [static]

ForwardSwitchConditionToPHI - 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. Returns true if a change is made.

Definition at line 3362 of file SimplifyCFG.cpp.

References llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), FindPHIForConditionForwarding(), llvm::SwitchInst::getCondition(), I, llvm::TargetOpcode::PHI, llvm::PHINode::setIncomingValue(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

static void GetBranchWeights ( TerminatorInst TI,
SmallVectorImpl< uint64_t > &  Weights 
) [static]
static bool GetCaseResults ( SwitchInst SI,
ConstantInt CaseVal,
BasicBlock CaseDest,
BasicBlock **  CommonDest,
SmallVectorImpl< std::pair< PHINode *, Constant * > > &  Res,
const DataLayout DL 
) [static]

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

References llvm::BasicBlock::begin(), ConstantFold(), llvm::ISD::ConstantPool, llvm::BasicBlock::end(), llvm::SwitchInst::getCondition(), llvm::Instruction::getParent(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT >, KeyT, ValueT, KeyInfoT >::insert(), LookupConstant(), llvm::TargetOpcode::PHI, and ValidLookupTableConstant().

Referenced by InitializeUniqueCases(), and SwitchToLookupTable().

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

GetConstantInt - Extract ConstantInt from value, looking through IntToPtr and PointerNullValue. Return NULL if value is not a constant int.

Definition at line 332 of file SimplifyCFG.cpp.

References llvm::WinEH::CE, llvm::dyn_cast(), llvm::ConstantInt::get(), llvm::ConstantExpr::getIntegerCast(), llvm::DataLayout::getIntPtrType(), llvm::ConstantInt::getType(), llvm::Value::getType(), llvm::IntToPtr, and llvm::Type::isPointerTy().

static bool HasBranchWeights ( const Instruction I) [inline, static]
static bool HasNoDuplicateCall ( const BasicBlock BB) [static]
Returns:
True if this block contains a CallInst with the NoDuplicate attribute.

Definition at line 1669 of file SimplifyCFG.cpp.

References llvm::BasicBlock::begin(), llvm::CallInst::cannotDuplicate(), llvm::dyn_cast(), llvm::BasicBlock::end(), and I.

Referenced by FoldCondBranchOnPHI().

static bool HoistThenElseCodeToIf ( BranchInst BI,
const DataLayout DL 
) [static]
static bool InitializeUniqueCases ( SwitchInst SI,
const DataLayout DL,
PHINode *&  PHI,
BasicBlock *&  CommonDest,
SwitchCaseResultVectorTy &  UniqueResults,
Constant *&  DefaultResult 
) [static]
static bool isProfitableToFoldUnconditional ( BranchInst SI1,
BranchInst SI2,
Instruction Cond,
SmallVectorImpl< PHINode * > &  PhiNodes 
) [static]

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

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

Referenced by llvm::FoldBranchToCommonDest().

static bool isSafeToHoistInvoke ( BasicBlock BB1,
BasicBlock BB2,
Instruction I1,
Instruction I2 
) [static]
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 1420 of file SimplifyCFG.cpp.

References llvm::dyn_cast(), llvm::StoreInst::getPointerOperand(), llvm::StoreInst::getValueOperand(), I, llvm::StoreInst::isSimple(), llvm::Instruction::mayHaveSideEffects(), llvm::BasicBlock::rbegin(), and llvm::BasicBlock::rend().

Referenced by SpeculativelyExecuteBB().

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

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

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

Referenced by ConstantFold(), and GetCaseResults().

static void MapCaseToResult ( ConstantInt CaseVal,
SwitchCaseResultVectorTy &  UniqueResults,
Constant Result 
) [static]

Definition at line 3530 of file SimplifyCFG.cpp.

Referenced by InitializeUniqueCases().

static bool passingValueIsAlwaysUndefined ( Value V,
Instruction I 
) [static]
static void RemoveSwitchAfterSelectConversion ( SwitchInst SI,
PHINode PHI,
Value SelectValue,
IRBuilder<> &  Builder 
) [static]
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 139 of file SimplifyCFG.cpp.

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

Referenced by llvm::FoldBranchToCommonDest().

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

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

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

Referenced by SwitchToLookupTable().

static bool SimplifyBranchOnICmpChain ( BranchInst BI,
const DataLayout DL,
IRBuilder<> &  Builder 
) [static]
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 2366 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), AddPredecessorToBlock(), llvm::StringRef::begin(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::WinEH::CE, llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateNot(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateOr(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateSelect(), llvm::dbgs(), DEBUG, llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T >::end(), ExtractBranchMetadata(), FitWeights(), llvm::ConstantInt::get(), llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), llvm::Value::getContext(), 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::LLVMContext::MD_prof, llvm::AArch64CC::NV, P, llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::BranchInst::setCondition(), llvm::Instruction::setMetadata(), and llvm::BranchInst::setSuccessor().

static bool SimplifyCondBranchToTwoReturns ( BranchInst BI,
IRBuilder<> &  Builder 
) [static]
static bool SimplifyIndirectBrOnSelect ( IndirectBrInst IBI,
SelectInst SI 
) [static]
static bool SimplifySwitchOnSelect ( SwitchInst SI,
SelectInst Select 
) [static]
static bool SimplifyTerminatorOnSelect ( TerminatorInst OldTerm,
Value Cond,
BasicBlock TrueBB,
BasicBlock FalseBB,
uint32_t  TrueWeight,
uint32_t  FalseWeight 
) [static]
static bool SinkThenElseCodeToEnd ( BranchInst BI1) [static]
static bool SpeculativelyExecuteBB ( BranchInst BI,
BasicBlock ThenBB,
const DataLayout DL 
) [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 1491 of file SimplifyCFG.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::begin(), llvm::BasicBlock::begin(), ComputeSpeculationCost(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateSelect(), llvm::dbgs(), DEBUG, llvm::dyn_cast(), llvm::BasicBlock::end(), llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::StoreInst::getValueOperand(), HoistCondStores, I, isSafeToSpeculateStore(), llvm::isSafeToSpeculativelyExecute(), llvm::Instruction::mayHaveSideEffects(), llvm::User::op_begin(), llvm::User::op_end(), passingValueIsAlwaysUndefined(), PHINodeFoldingThreshold, llvm::PHINode::setIncomingValue(), llvm::User::setOperand(), llvm::iplist< NodeTy, Traits >::splice(), and std::swap().

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 ( NumSinkCommons  ,
"Number of common instructions sunk down to the end block"   
)
STATISTIC ( NumSpeculations  ,
"Number of speculative executed instructions  
)
static bool SwitchToLookupTable ( SwitchInst SI,
IRBuilder<> &  Builder,
const TargetTransformInfo TTI,
const DataLayout DL 
) [static]

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

References AddPredecessorToBlock(), llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT >, KeyT, ValueT, KeyInfoT >::count(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateBr(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateCondBr(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateICmpULT(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateLShr(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateRet(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateSub(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateTrunc(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateZExtOrTrunc(), llvm::Instruction::eraseFromParent(), llvm::DataLayout::fitsInLegalInteger(), GetCaseResults(), llvm::SwitchInst::getCondition(), llvm::Module::getContext(), llvm::SwitchInst::getDefaultDest(), llvm::BasicBlock::getFirstNonPHIOrDbg(), 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::NextPowerOf2(), llvm::TargetOpcode::PHI, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::BasicBlock::removePredecessor(), llvm::IRBuilderBase::SetInsertPoint(), llvm::Value::setName(), llvm::APInt::sgt(), ShouldBuildLookupTable(), llvm::TargetTransformInfo::shouldBuildLookupTables(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT >, KeyT, ValueT, KeyInfoT >::size(), llvm::APInt::slt(), and UINT64_MAX.

static bool SwitchToSelect ( SwitchInst SI,
IRBuilder<> &  Builder,
const DataLayout DL,
AssumptionTracker AT 
) [static]

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

References ConvertTwoCaseSwitch(), llvm::SwitchInst::getCondition(), InitializeUniqueCases(), llvm::TargetOpcode::PHI, RemoveSwitchAfterSelectConversion(), and llvm::IRBuilderBase::SetInsertPoint().

static bool TryToSimplifyUncondBranchWithICmpInIt ( ICmpInst ICI,
IRBuilder<> &  Builder,
const TargetTransformInfo TTI,
unsigned  BonusInstThreshold,
const DataLayout DL,
AssumptionTracker AT 
) [static]

TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp instruction (a seteq/setne with a constant) as the only instruction in a block that ends with an uncond branch. We are looking for a very specific pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In this case, we merge the first two "or's of icmp" into a switch, but then the default value goes to an uncond block with a seteq in it, we get something like:

switch i8 A, label DEFAULT [ i8 1, label end i8 2, label end ] DEFAULT: tmp = icmp eq i8 A, 92 br label end end: ... = phi i1 [ true, entry ], [ tmp, DEFAULT ], [ true, entry ]

We prefer to split the edge to 'end' so that there is a true/false entry to the PHI, merging the third icmp into the switch.

Definition at line 2719 of file SimplifyCFG.cpp.

References llvm::SwitchInst::addCase(), llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), llvm::SwitchInst::case_default(), llvm::BasicBlock::Create(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateBr(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::SwitchInst::findCaseDest(), llvm::SwitchInst::findCaseValue(), llvm::BasicBlock::front(), GetBranchWeights(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::SwitchInst::getDefaultDest(), llvm::ConstantInt::getFalse(), getFalse(), llvm::SwitchInst::getNumCases(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::CmpInst::getPredicate(), llvm::BasicBlock::getSinglePredecessor(), llvm::TerminatorInst::getSuccessor(), llvm::BasicBlock::getTerminator(), getTrue(), HasBranchWeights(), llvm::Value::hasOneUse(), llvm::CmpInst::ICMP_EQ, llvm::LLVMContext::MD_prof, llvm::Value::replaceAllUsesWith(), llvm::IRBuilderBase::SetCurrentDebugLocation(), llvm::IRBuilderBase::SetInsertPoint(), llvm::Instruction::setMetadata(), llvm::User::setOperand(), llvm::SimplifyCFG(), llvm::SimplifyInstruction(), std::swap(), and llvm::Instruction::user_back().

static bool TurnSwitchRangeIntoICmp ( SwitchInst SI,
IRBuilder<> &  Builder 
) [static]
static bool ValidLookupTableConstant ( Constant C) [static]

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

Definition at line 3397 of file SimplifyCFG.cpp.

References llvm::CallingConv::C, llvm::WinEH::CE, llvm::Constant::isDLLImportDependent(), and llvm::Constant::isThreadDependent().

Referenced by GetCaseResults().

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

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

Definition at line 609 of file SimplifyCFG.cpp.

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


Variable Documentation

cl::opt<bool> DupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), cl::desc("Duplicate return instructions into unconditional branches")) [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]

Referenced by SpeculativelyExecuteBB().

cl::opt<unsigned> PHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1), cl::desc("Control the amount of phi node folding to perform (default = 1)")) [static]
cl::opt<bool> SinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), cl::desc("Sink common instructions down to the end block")) [static]