LLVM  6.0.0svn
Macros | Functions | Variables
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/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.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/Analysis/ValueTracking.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/DebugInfo.h"
#include "llvm/IR/DerivedTypes.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/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/Local.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <set>
#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 (TerminatorInst *SI1, TerminatorInst *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 ConstantIntGetConstantInt (Value *V, const DataLayout &DL)
 Extract ConstantInt from value, looking through IntToPtr and PointerNullValue. More...
 
static void EraseTerminatorInstAndDCECond (TerminatorInst *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 int ConstantIntSortPredicate (ConstantInt *const *P1, ConstantInt *const *P2)
 
static bool HasBranchWeights (const Instruction *I)
 
static void GetBranchWeights (TerminatorInst *TI, SmallVectorImpl< uint64_t > &Weights)
 Get Weights of a given TerminatorInst, 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 SinkThenElseCodeToEnd (BranchInst *BI1)
 Given an unconditional branch that goes to BBEnd, check whether BBEnd has only two predecessors and the other predecessor ends with an unconditional branch. More...
 
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. 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 checkCSEInPredecessor (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 StoreInstfindUniqueStoreInBlocks (BasicBlock *BB1, BasicBlock *BB2)
 
static ValueensureValueAvailableInSuccessor (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)
 
static bool mergeConditionalStores (BranchInst *PBI, BranchInst *QBI)
 
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 (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 DataLayout &DL, const TargetTransformInfo &TTI, unsigned BonusInstThreshold, AssumptionCache *AC)
 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. More...
 
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 PHINodeFindPHIForConditionForwarding (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 ConstantLookupConstant (Value *V, const SmallDenseMap< Value *, Constant *> &ConstantPool)
 If V is a Constant, return it. More...
 
static ConstantConstantFold (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 void 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)
 
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, AssumptionCache *AC, 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)
 
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 BasicBlockallPredecessorsComeFromSameSource (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< unsignedPHINodeFoldingThreshold ("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< 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"))
 
static cl::opt< boolMergeCondStores ("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< boolMergeCondStoresAggressively ("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< boolSpeculateOneExpensiveInst ("speculate-one-expensive-inst", cl::Hidden, cl::init(true), cl::desc("Allow exactly one expensive instruction to be speculatively " "executed"))
 
static cl::opt< unsignedMaxSpeculationDepth ("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 82 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 283 of file SimplifyCFG.cpp.

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

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

◆ allPredecessorsComeFromSameSource()

static BasicBlock* allPredecessorsComeFromSameSource ( BasicBlock BB)
static

◆ BlockIsSimpleEnoughToThreadThrough()

static bool BlockIsSimpleEnoughToThreadThrough ( BasicBlock BB)
static

◆ canSinkInstructions()

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

◆ CasesAreContiguous()

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

◆ checkCSEInPredecessor()

static bool checkCSEInPredecessor ( 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 2460 of file SimplifyCFG.cpp.

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

Referenced by llvm::FoldBranchToCommonDest().

◆ 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 297 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 4511 of file SimplifyCFG.cpp.

References A, 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, isPodLike< T >::value >::push_back(), and llvm::MCID::Select.

Referenced by GetCaseResults().

◆ ConstantIntSortPredicate()

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

◆ ConvertTwoCaseSwitch()

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

◆ 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 321 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 734 of file SimplifyCFG.cpp.

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

Referenced by ValuesOverlap().

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

References assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::tgtok::Bits, llvm::SwitchInst::case_default(), llvm::SwitchInst::cases(), llvm::computeKnownBits(), llvm::ComputeNumSignBits(), llvm::countPopulation(), llvm::dbgs(), DEBUG, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), EraseTerminatorInstAndDCECond(), llvm::SwitchInst::findCaseValue(), llvm::BasicBlock::front(), GetBranchWeights(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), 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::LLVMContext::MD_prof, llvm::KnownBits::One, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::pop_back(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SwitchInst::removeCase(), llvm::SwitchInst::setDefaultDest(), llvm::Instruction::setMetadata(), llvm::SmallVectorTemplateCommon< T >::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

◆ EraseTerminatorInstAndDCECond()

static void EraseTerminatorInstAndDCECond ( TerminatorInst TI)
static

◆ 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 2478 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 4401 of file SimplifyCFG.cpp.

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

Referenced by ForwardSwitchConditionToPHI().

◆ findUniqueStoreInBlocks()

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

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

References llvm::SwitchInst::addCase(), AddPredecessorToBlock(), assert(), llvm::SmallVectorImpl< T >::assign(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::SmallVectorTemplateCommon< T >::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 >::end(), llvm::MutableArrayRef< T >::end(), EraseTerminatorInstAndDCECond(), 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::LLVMContext::MD_prof, llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::pop_back(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::BasicBlock::removePredecessor(), SafeToMergeTerminators(), llvm::Instruction::setDebugLoc(), llvm::IRBuilderBase::SetInsertPoint(), llvm::Instruction::setMetadata(), llvm::SwitchInst::setSuccessor(), llvm::SmallVectorTemplateCommon< T >::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 2107 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), llvm::any_of(), llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::CallInst::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::TerminatorInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::TerminatorInst::getSuccessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getType(), llvm::ConstantInt::getZExtValue(), llvm::Value::hasOneUse(), I, llvm::iplist_impl< IntrusiveListT, TraitsT >::insert(), llvm::CallInst::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::TerminatorInst::setSuccessor(), and llvm::SimplifyInstruction().

Referenced by allPredecessorsComeFromSameSource().

◆ FoldTwoEntryPHINode()

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

◆ 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.

Returns true if a change is made.

Definition at line 4434 of file SimplifyCFG.cpp.

References llvm::SwitchInst::cases(), E, FindPHIForConditionForwarding(), llvm::SwitchInst::getCondition(), I, llvm::PHINode::setIncomingValue(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by ReduceSwitchRange().

◆ GetBranchWeights()

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

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

References llvm::BasicBlock::begin(), C, ConstantFold(), llvm::ISD::ConstantPool, E, llvm::BasicBlock::end(), llvm::SwitchInst::getCondition(), llvm::Instruction::getParent(), llvm::Use::getUser(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), LookupConstant(), llvm::Value::uses(), and ValidLookupTableConstant().

Referenced by InitializeUniqueCases(), and SwitchToLookupTable().

◆ GetConstantInt()

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

◆ HasBranchWeights()

static bool HasBranchWeights ( const Instruction I)
inlinestatic

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

References AddPredecessorToBlock(), llvm::Instruction::andIRFlags(), llvm::BasicBlock::begin(), llvm::Instruction::clone(), llvm::combineMetadata(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dyn_cast(), EraseTerminatorInstAndDCECond(), llvm::BranchInst::getCondition(), llvm::Instruction::getDebugLoc(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::DILocation::getMergedLocation(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), 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::Type::isVoidTy(), 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(), llvm::Instruction::setDebugLoc(), llvm::PHINode::setIncomingValue(), 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 
)
static

◆ isProfitableToFoldUnconditional()

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

◆ isSafeToHoistInvoke()

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

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

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

Referenced by SpeculativelyExecuteBB().

◆ isSwitchDense()

static bool isSwitchDense ( ArrayRef< int64_t >  Values)
static

◆ 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 4499 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 void MapCaseToResult ( ConstantInt CaseVal,
SwitchCaseResultVectorTy &  UniqueResults,
Constant Result 
)
static

Definition at line 4621 of file SimplifyCFG.cpp.

Referenced by InitializeUniqueCases().

◆ mergeCleanupPad()

static bool mergeCleanupPad ( CleanupReturnInst RI)
static

◆ mergeConditionalStores()

static bool mergeConditionalStores ( BranchInst PBI,
BranchInst QBI 
)
static

◆ mergeConditionalStoreToAddress()

static bool mergeConditionalStoreToAddress ( BasicBlock PTB,
BasicBlock PFB,
BasicBlock QTB,
BasicBlock QFB,
BasicBlock PostBB,
Value Address,
bool  InvertPCond,
bool  InvertQCond 
)
static

◆ passingValueIsAlwaysUndefined()

static bool passingValueIsAlwaysUndefined ( Value V,
Instruction I 
)
static

◆ ReduceSwitchRange()

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

◆ removeEmptyCleanup()

static bool removeEmptyCleanup ( CleanupReturnInst RI)
static

◆ RemoveSwitchAfterSelectConversion()

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

◆ removeUndefIntroducingPredecessor()

static bool removeUndefIntroducingPredecessor ( BasicBlock BB)
static

◆ 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 5082 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 ( TerminatorInst SI1,
TerminatorInst SI2,
SmallSetVector< BasicBlock *, 4 > *  FailBlocks = nullptr 
)
static

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

Definition at line 211 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().

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

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

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

References llvm::SwitchInst::addCase(), llvm::PHINode::addIncoming(), AddPredecessorToBlock(), llvm::array_pod_sort(), assert(), 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(), DEBUG, llvm::dyn_cast(), E, llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::WebAssembly::End, llvm::iplist_impl< IntrusiveListT, TraitsT >::erase(), llvm::SmallVectorImpl< T >::erase(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::eraseFromParent(), EraseTerminatorInstAndDCECond(), llvm::BranchInst::getCondition(), llvm::Value::getContext(), 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::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert(), llvm::Type::isPointerTy(), llvm::pred_begin(), llvm::pred_empty(), llvm::pred_end(), llvm::BasicBlock::removePredecessor(), llvm::removeUnwindEdge(), llvm::IRBuilderBase::SetInsertPoint(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::BasicBlock::splitBasicBlock(), and std::swap().

Referenced by allPredecessorsComeFromSameSource().

◆ SimplifyCondBranchToCondBranch()

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

◆ SimplifyCondBranchToTwoReturns()

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

◆ SimplifyIndirectBrOnSelect()

static bool SimplifyIndirectBrOnSelect ( IndirectBrInst IBI,
SelectInst SI 
)
static

◆ SimplifySwitchOnSelect()

static bool SimplifySwitchOnSelect ( SwitchInst SI,
SelectInst Select 
)
static

◆ SimplifyTerminatorOnSelect()

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

◆ sinkLastInstruction()

static bool sinkLastInstruction ( ArrayRef< BasicBlock *>  Blocks)
static

◆ SinkThenElseCodeToEnd()

static bool SinkThenElseCodeToEnd ( BranchInst BI1)
static

Given an unconditional branch that goes to BBEnd, check whether BBEnd has only two predecessors and the other predecessor ends with an unconditional branch.

If it is true, sink any common code in the two predecessors to BBEnd.

Definition at line 1636 of file SimplifyCFG.cpp.

References assert(), B, canSinkInstructions(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), DEBUG, llvm::BranchInst::getSuccessor(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isSafeToSpeculativelyExecute(), llvm::BranchInst::isUnconditional(), llvm::predecessors(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), sinkLastInstruction(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::SplitBlockPredecessors(), and T.

Referenced by TryToMergeLandingPad().

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

References assert(), llvm::BasicBlock::begin(), llvm::ComputeSpeculationCost(), llvm::IRBuilder< T, Inserter >::CreateSelect(), llvm::dbgs(), DEBUG, llvm::Instruction::dropUnknownNonDebugMetadata(), llvm::dyn_cast(), E, llvm::BasicBlock::end(), llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), llvm::Instruction::getDebugLoc(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::DILocation::getMergedLocation(), llvm::Value::getName(), llvm::Value::getNumUses(), 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::Instruction::setDebugLoc(), llvm::PHINode::setIncomingValue(), 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 5149 of file SimplifyCFG.cpp.

References llvm::PHINode::addIncoming(), AddPredecessorToBlock(), assert(), llvm::SwitchInst::case_begin(), llvm::SwitchInst::case_end(), 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::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::Value::getName(), 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(), llvm::Value::hasOneUse(), I, llvm::max(), llvm::NextPowerOf2(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::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(), llvm::Instruction::user_back(), llvm::Value::user_begin(), and llvm::Value::users().

Referenced by ReduceSwitchRange().

◆ SwitchToSelect()

static bool SwitchToSelect ( SwitchInst SI,
IRBuilder<> &  Builder,
AssumptionCache AC,
const DataLayout DL,
const TargetTransformInfo TTI 
)
static

◆ 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 loose 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 5600 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::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::getUniqueSuccessor(), llvm::InvokeInst::getUnwindDest(), I, llvm::SmallSet< T, N, C >::insert(), llvm::Instruction::isIdenticalTo(), llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::InvokeInst::setUnwindDest(), llvm::SimplifyCFG(), SinkCommon, SinkThenElseCodeToEnd(), llvm::succ_begin(), llvm::succ_end(), llvm::TryToSimplifyUncondBranchFromEmptyBlock(), and TryToSimplifyUncondBranchWithICmpInIt().

◆ TryToSimplifyUncondBranchWithICmpInIt()

static bool TryToSimplifyUncondBranchWithICmpInIt ( ICmpInst ICI,
IRBuilder<> &  Builder,
const DataLayout DL,
const TargetTransformInfo TTI,
unsigned  BonusInstThreshold,
AssumptionCache AC 
)
static

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 3467 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(), GetBranchWeights(), llvm::SwitchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::SwitchInst::getDefaultDest(), llvm::ConstantInt::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(), llvm::ConstantInt::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(), SI, llvm::SimplifyCFG(), llvm::SimplifyInstruction(), std::swap(), and llvm::Instruction::user_back().

Referenced by TryToMergeLandingPad().

◆ TurnSwitchRangeIntoICmp()

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

◆ 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 4472 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

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

◆ 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

◆ 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

◆ 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 TryToMergeLandingPad().

◆ 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().