LLVM  14.0.0git
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/MapVector.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/Sequence.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/CaptureTracking.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/EHPersonalities.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.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/PseudoProbe.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/BranchProbability.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/SSAUpdater.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 (NumFoldValueComparisonIntoPredecessors, "Number of value comparisons folded into predecessor basic blocks")
 
 STATISTIC (NumFoldBranchToCommonDest, "Number of branches folded into predecessor basic block")
 
 STATISTIC (NumHoistCommonCode, "Number of common instruction 'blocks' hoisted up to the begin block")
 
 STATISTIC (NumHoistCommonInstrs, "Number of common instructions hoisted up to the begin block")
 
 STATISTIC (NumSinkCommonCode, "Number of common instruction 'blocks' sunk down to the end block")
 
 STATISTIC (NumSinkCommonInstrs, "Number of common instructions sunk down to the end block")
 
 STATISTIC (NumSpeculations, "Number of speculative executed instructions")
 
 STATISTIC (NumInvokes, "Number of invokes with empty resume blocks simplified into calls")
 
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 void AddPredecessorToBlock (BasicBlock *Succ, BasicBlock *NewPred, BasicBlock *ExistPred, MemorySSAUpdater *MSSAU=nullptr)
 Update PHI nodes in Succ to indicate that there will now be entries in it from the 'NewPred' block. More...
 
static InstructionCost 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, InstructionCost &Cost, InstructionCost Budget, 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 EraseTerminatorAndDCECond (Instruction *TI, MemorySSAUpdater *MSSAU=nullptr)
 
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 void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses (BasicBlock *BB, BasicBlock *PredBlock, ValueToValueMapTy &VMap)
 
static bool isSafeToHoistInvoke (BasicBlock *BB1, BasicBlock *BB2, Instruction *I1, Instruction *I2)
 
static bool passingValueIsAlwaysUndefined (Value *V, Instruction *I, bool PtrValueMayBeModified)
 Check if passing a value to an instruction will cause undefined behavior. More...
 
static bool isLifeTimeMarker (const Instruction *I)
 
static bool replacingOperandWithVariableIsCheap (const Instruction *I, int OpIdx)
 
static bool canSinkInstructions (ArrayRef< Instruction * > Insts, DenseMap< Instruction *, SmallVector< Value *, 4 >> &PHIOperands)
 
static bool sinkLastInstruction (ArrayRef< BasicBlock * > Blocks)
 
static bool SinkCommonCodeFromPredecessors (BasicBlock *BB, DomTreeUpdater *DTU)
 Check whether BB's predecessors end with unconditional branches. 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 validateAndCostRequiredSelects (BasicBlock *BB, BasicBlock *ThenBB, BasicBlock *EndBB, unsigned &SpeculatedInstructions, InstructionCost &Cost, const TargetTransformInfo &TTI)
 Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects. More...
 
static bool BlockIsSimpleEnoughToThreadThrough (BasicBlock *BB)
 Return true if we can thread a branch across this block. More...
 
static Optional< bool > FoldCondBranchOnPHIImpl (BranchInst *BI, DomTreeUpdater *DTU, 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 FoldCondBranchOnPHI (BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC)
 
static bool FoldTwoEntryPHINode (PHINode *PN, const TargetTransformInfo &TTI, DomTreeUpdater *DTU, const DataLayout &DL)
 Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it. More...
 
static ValuecreateLogicalOp (IRBuilderBase &Builder, Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="")
 
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 Optional< std::pair< Instruction::BinaryOps, bool > > shouldFoldCondBranchesToCommonDestination (BranchInst *BI, BranchInst *PBI, const TargetTransformInfo *TTI)
 Determine if the two branches share a common destination and deduce a glue that joins the branches' conditions to arrive at the common destination if that would be profitable. More...
 
static bool performBranchToCommonDestFolding (BranchInst *BI, BranchInst *PBI, DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU, const TargetTransformInfo *TTI)
 
static bool isVectorOp (Instruction &I)
 Return if an instruction's type or any of its operands' types are a vector type. 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, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
 
static bool mergeConditionalStores (BranchInst *PBI, BranchInst *QBI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
 
static bool tryWidenCondBranchToCondBranch (BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU)
 If the previous block ended with a widenable branch, determine if reusing the target block is profitable and legal. More...
 
static bool SimplifyCondBranchToCondBranch (BranchInst *PBI, BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI)
 If we have a conditional branch as a predecessor of another block, this function tries to simplify it. More...
 
static bool isCleanupBlockEmpty (iterator_range< BasicBlock::iterator > R)
 
static bool removeEmptyCleanup (CleanupReturnInst *RI, DomTreeUpdater *DTU)
 
static bool mergeCleanupPad (CleanupReturnInst *RI)
 
static bool CasesAreContiguous (SmallVectorImpl< ConstantInt * > &Cases)
 
static void createUnreachableSwitchDefault (SwitchInst *Switch, DomTreeUpdater *DTU)
 
static bool eliminateDeadSwitchCases (SwitchInst *SI, DomTreeUpdater *DTU, 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 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 ValueConvertTwoCaseSwitch (const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder)
 
static void RemoveSwitchAfterSelectConversion (SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU)
 
static bool switchToSelect (SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, 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 isTypeLegalForLookupTable (Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL)
 
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, DomTreeUpdater *DTU, 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, DomTreeUpdater *DTU)
 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, DomTreeUpdater *DTU)
 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< unsigned > TwoEntryPHINodeFoldingThreshold ("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
 
static cl::opt< bool > HoistCommon ("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
 
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"))
 
static cl::opt< intMaxSmallBlockSize ("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
 
static cl::opt< unsigned > BranchFoldThreshold ("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
 
static cl::opt< unsigned > BranchFoldToCommonDestVectorMultiplier ("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "simplifycfg"

Definition at line 94 of file SimplifyCFG.cpp.

Function Documentation

◆ AddPredecessorToBlock()

static void AddPredecessorToBlock ( BasicBlock Succ,
BasicBlock NewPred,
BasicBlock ExistPred,
MemorySSAUpdater MSSAU = nullptr 
)
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 330 of file SimplifyCFG.cpp.

References llvm::BasicBlock::phis().

Referenced by FoldCondBranchOnPHIImpl(), performBranchToCommonDestFolding(), SimplifyCondBranchToCondBranch(), and SwitchToLookupTable().

◆ allPredecessorsComeFromSameSource()

static BasicBlock* allPredecessorsComeFromSameSource ( BasicBlock BB)
static

Definition at line 6420 of file SimplifyCFG.cpp.

References BB, P, and llvm::predecessors().

◆ 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

Definition at line 4775 of file SimplifyCFG.cpp.

References llvm::array_pod_sort(), assert(), ConstantIntSortPredicate(), E, and I.

◆ CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses()

static void CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses ( BasicBlock BB,
BasicBlock PredBlock,
ValueToValueMapTy VMap 
)
static

◆ computeSpeculationCost()

static InstructionCost 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 344 of file SimplifyCFG.cpp.

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

Referenced by dominatesMergePoint(), and validateAndCostRequiredSelects().

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

References llvm::ConstantFoldCompareInstOperands(), llvm::ConstantFoldInstOperands(), DL, E, I, LookupConstant(), N, and llvm::MCID::Select.

Referenced by GetCaseResults().

◆ ConstantIntSortPredicate()

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

Definition at line 1012 of file SimplifyCFG.cpp.

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

Referenced by CasesAreContiguous().

◆ ConvertTwoCaseSwitch()

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

Definition at line 5326 of file SimplifyCFG.cpp.

References Builder.

Referenced by switchToSelect().

◆ createLogicalOp()

static Value* createLogicalOp ( IRBuilderBase Builder,
Instruction::BinaryOps  Opc,
Value LHS,
Value RHS,
const Twine Name = "" 
)
static

◆ createUnreachableSwitchDefault()

static void createUnreachableSwitchDefault ( SwitchInst Switch,
DomTreeUpdater DTU 
)
static

◆ dominatesMergePoint()

static bool dominatesMergePoint ( Value V,
BasicBlock BB,
SmallPtrSetImpl< Instruction * > &  AggressiveInsts,
InstructionCost Cost,
InstructionCost  Budget,
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 Budget 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, Cost is increased by the cost of V plus its non-dominating operands. If that cost is greater than Budget, false is returned and Cost is undefined.

Definition at line 368 of file SimplifyCFG.cpp.

References BB, computeSpeculationCost(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::Depth, llvm::SmallPtrSetImplBase::empty(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BranchInst::isConditional(), llvm::isSafeToSpeculativelyExecute(), llvm::InstructionCost::isValid(), MaxSpeculationDepth, 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 781 of file SimplifyCFG.cpp.

References BB, and llvm::erase_value().

◆ eliminateDeadSwitchCases()

static bool eliminateDeadSwitchCases ( SwitchInst SI,
DomTreeUpdater DTU,
AssumptionCache AC,
const DataLayout DL 
)
static

◆ ensureValueAvailableInSuccessor()

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

◆ EraseTerminatorAndDCECond()

static void EraseTerminatorAndDCECond ( Instruction TI,
MemorySSAUpdater MSSAU = nullptr 
)
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 2970 of file SimplifyCFG.cpp.

References llvm::Instruction::extractProfMetadata().

Referenced by performBranchToCommonDestFolding(), 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 5011 of file SimplifyCFG.cpp.

References assert(), BB, llvm::MCID::Branch, and llvm::BasicBlock::phis().

Referenced by ForwardSwitchConditionToPHI().

◆ findUniqueStoreInBlocks()

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

Definition at line 3297 of file SimplifyCFG.cpp.

References BB, I, S, and 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 1054 of file SimplifyCFG.cpp.

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

Referenced by performBranchToCommonDestFolding(), and SimplifyCondBranchToCondBranch().

◆ FoldCondBranchOnPHI()

static bool FoldCondBranchOnPHI ( BranchInst BI,
DomTreeUpdater DTU,
const DataLayout DL,
AssumptionCache AC 
)
static

Definition at line 2747 of file SimplifyCFG.cpp.

References DL, FoldCondBranchOnPHIImpl(), and llvm::None.

◆ FoldCondBranchOnPHIImpl()

static Optional<bool> FoldCondBranchOnPHIImpl ( BranchInst BI,
DomTreeUpdater DTU,
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 2623 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), llvm::DomTreeUpdater::applyUpdates(), BB, llvm::BasicBlock::begin(), BlockIsSimpleEnoughToThreadThrough(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, DL, llvm::numbers::e, llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), llvm::FoldSingleEntryPHINodes(), llvm::BranchInst::getCondition(), llvm::Instruction::getDebugLoc(), 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::DominatorTreeBase< BasicBlock, false >::Insert, llvm::Type::isIntegerTy(), N, llvm::None, llvm::AssumptionCache::registerAssumption(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setSuccessor(), and llvm::SimplifyInstruction().

Referenced by FoldCondBranchOnPHI().

◆ FoldTwoEntryPHINode()

static bool FoldTwoEntryPHINode ( PHINode PN,
const TargetTransformInfo TTI,
DomTreeUpdater DTU,
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 2761 of file SimplifyCFG.cpp.

References llvm::any_of(), llvm::DomTreeUpdater::applyUpdates(), assert(), BB, llvm::BasicBlock::begin(), llvm::PHINode::blocks(), Builder, llvm::copy_if(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, DL, dominatesMergePoint(), llvm::Instruction::eraseFromParent(), llvm::Instruction::extractProfMetadata(), llvm::tgtok::FalseVal, llvm::BranchProbability::getBranchProbability(), llvm::BranchProbability::getCompl(), llvm::BranchInst::getCondition(), llvm::Instruction::getFastMathFlags(), llvm::GetIfCondition(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Instruction::getMetadata(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::TargetTransformInfo::getPredictableBranchThreshold(), llvm::BranchInst::getSuccessor(), llvm::Value::getType(), llvm::BasicBlock::hasAddressTaken(), llvm::hoistAllInstructionsInto(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::Type::isIntegerTy(), LLVM_DEBUG, llvm::PatternMatch::m_AnyIntegralConstant(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_ImmConstant(), llvm::PatternMatch::m_Not(), llvm::PatternMatch::m_Select(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::Value::replaceAllUsesWith(), llvm::SimplifyInstruction(), llvm::Successor, llvm::successors(), std::swap(), llvm::Value::takeName(), llvm::TargetTransformInfo::TCC_Basic, llvm::tgtok::TrueVal, and TwoEntryPHINodeFoldingThreshold.

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

References llvm::count(), FindPHIForConditionForwarding(), Index, llvm::BasicBlock::phis(), llvm::PHINode::setIncomingValue(), and SI.

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

References assert(), llvm::numbers::e, llvm::BranchInst::getCondition(), llvm::Instruction::getMetadata(), llvm::MDNode::getNumOperands(), llvm::MDNode::getOperand(), llvm::CmpInst::getPredicate(), llvm::ConstantInt::getValue(), llvm::APInt::getZExtValue(), i, llvm::CmpInst::ICMP_EQ, and std::swap().

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

References ConstantFold(), ConstantPool, DL, llvm::Use::getUser(), I, llvm::BasicBlock::instructionsWithoutDebug(), LookupConstant(), SI, 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 440 of file SimplifyCFG.cpp.

References DL, llvm::ConstantInt::get(), llvm::ConstantExpr::getIntegerCast(), llvm::ConstantInt::getType(), llvm::Value::getType(), and llvm::Type::isPointerTy().

◆ HasBranchWeights()

static bool HasBranchWeights ( const Instruction I)
inlinestatic

Definition at line 1021 of file SimplifyCFG.cpp.

References llvm::MDNode::getOperand(), and I.

◆ 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

◆ isCleanupBlockEmpty()

static bool isCleanupBlockEmpty ( iterator_range< BasicBlock::iterator R)
static

Definition at line 4330 of file SimplifyCFG.cpp.

References I.

Referenced by removeEmptyCleanup().

◆ isLifeTimeMarker()

static bool isLifeTimeMarker ( const Instruction I)
static

Definition at line 1653 of file SimplifyCFG.cpp.

References I.

Referenced by canSinkInstructions().

◆ isSafeToHoistInvoke()

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

Definition at line 1387 of file SimplifyCFG.cpp.

References llvm::BasicBlock::phis(), and llvm::successors().

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

References llvm::StoreInst::getPointerOperand(), llvm::Value::getType(), llvm::getUnderlyingObject(), llvm::StoreInst::getValueOperand(), I, llvm::BasicBlock::instructionsWithoutDebug(), llvm::StoreInst::isSimple(), llvm::PointerMayBeCaptured(), llvm::reverse(), and SI.

◆ isSwitchDense()

static bool isSwitchDense ( ArrayRef< int64_t >  Values)
static

◆ isTypeLegalForLookupTable()

static bool isTypeLegalForLookupTable ( Type Ty,
const TargetTransformInfo TTI,
const DataLayout DL 
)
static

◆ isVectorOp()

static bool isVectorOp ( Instruction I)
static

Return if an instruction's type or any of its operands' types are a vector type.

Definition at line 3155 of file SimplifyCFG.cpp.

References llvm::any_of(), and I.

Referenced by llvm::FoldBranchToCommonDest().

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

Referenced by ConstantFold(), and GetCaseResults().

◆ MapCaseToResult()

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

Definition at line 5244 of file SimplifyCFG.cpp.

References I.

Referenced by InitializeUniqueCases().

◆ mergeCleanupPad()

static bool mergeCleanupPad ( CleanupReturnInst RI)
static

◆ mergeConditionalStores()

static bool mergeConditionalStores ( BranchInst PBI,
BranchInst QBI,
DomTreeUpdater DTU,
const DataLayout DL,
const TargetTransformInfo TTI 
)
static

◆ mergeConditionalStoreToAddress()

static bool mergeConditionalStoreToAddress ( BasicBlock PTB,
BasicBlock PFB,
BasicBlock QTB,
BasicBlock QFB,
BasicBlock PostBB,
Value Address,
bool  InvertPCond,
bool  InvertQCond,
DomTreeUpdater DTU,
const DataLayout DL,
const TargetTransformInfo TTI 
)
static

◆ passingValueIsAlwaysUndefined()

static bool passingValueIsAlwaysUndefined ( Value V,
Instruction I,
bool  PtrValueMayBeModified = false 
)
static

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

Definition at line 6541 of file SimplifyCFG.cpp.

References Arg, GEP, i, I, llvm::isGuaranteedToTransferExecutionToSuccessor(), llvm::NullPointerIsDefined(), and SI.

Referenced by removeUndefIntroducingPredecessor(), and validateAndCostRequiredSelects().

◆ performBranchToCommonDestFolding()

static bool performBranchToCommonDestFolding ( BranchInst BI,
BranchInst PBI,
DomTreeUpdater DTU,
MemorySSAUpdater MSSAU,
const TargetTransformInfo TTI 
)
static

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

References assert(), llvm::sampleprof::Base, Builder, llvm::countTrailingZeros(), DL, llvm::ConstantInt::get(), isSwitchDense(), llvm::min(), Shift, SI, and llvm::sort().

◆ removeEmptyCleanup()

static bool removeEmptyCleanup ( CleanupReturnInst RI,
DomTreeUpdater DTU 
)
static

◆ RemoveSwitchAfterSelectConversion()

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

◆ removeUndefIntroducingPredecessor()

static bool removeUndefIntroducingPredecessor ( BasicBlock BB,
DomTreeUpdater DTU 
)
static

◆ replacingOperandWithVariableIsCheap()

static bool replacingOperandWithVariableIsCheap ( const Instruction I,
int  OpIdx 
)
static

Definition at line 1668 of file SimplifyCFG.cpp.

References I.

Referenced by canSinkInstructions().

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

References assert(), 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::predecessors(), 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 298 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 llvm::FoldBranchToCommonDest().

◆ setBranchWeights() [1/2]

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

Definition at line 833 of file SimplifyCFG.cpp.

References assert(), llvm::MDBuilder::createBranchWeights(), I, and N.

◆ setBranchWeights() [2/2]

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

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

References DL, I, isTypeLegalForLookupTable(), SI, and UINT64_MAX.

Referenced by SwitchToLookupTable().

◆ shouldFoldCondBranchesToCommonDestination()

static Optional<std::pair<Instruction::BinaryOps, bool> > shouldFoldCondBranchesToCommonDestination ( BranchInst BI,
BranchInst PBI,
const TargetTransformInfo TTI 
)
static

◆ SimplifyCondBranchToCondBranch()

static bool SimplifyCondBranchToCondBranch ( BranchInst PBI,
BranchInst BI,
DomTreeUpdater DTU,
const DataLayout DL,
const TargetTransformInfo TTI 
)
static

◆ SinkCommonCodeFromPredecessors()

static bool SinkCommonCodeFromPredecessors ( BasicBlock BB,
DomTreeUpdater DTU 
)
static

◆ sinkLastInstruction()

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

◆ STATISTIC() [1/13]

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

◆ STATISTIC() [2/13]

STATISTIC ( NumFoldBranchToCommonDest  ,
"Number of branches folded into predecessor basic block  
)

◆ STATISTIC() [3/13]

STATISTIC ( NumFoldValueComparisonIntoPredecessors  ,
"Number of value comparisons folded into predecessor basic blocks"   
)

◆ STATISTIC() [4/13]

STATISTIC ( NumHoistCommonCode  ,
"Number of common instruction 'blocks' hoisted up to the begin block  
)

◆ STATISTIC() [5/13]

STATISTIC ( NumHoistCommonInstrs  ,
"Number of common instructions hoisted up to the begin block  
)

◆ STATISTIC() [6/13]

STATISTIC ( NumInvokes  ,
"Number of invokes with empty resume blocks simplified into calls  
)

◆ STATISTIC() [7/13]

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

◆ STATISTIC() [8/13]

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

◆ STATISTIC() [9/13]

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

◆ STATISTIC() [10/13]

STATISTIC ( NumSinkCommonCode  ,
"Number of common instruction 'blocks' sunk down to the end block  
)

◆ STATISTIC() [11/13]

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

◆ STATISTIC() [12/13]

STATISTIC ( NumSpeculations  ,
"Number of speculative executed instructions  
)

◆ STATISTIC() [13/13]

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

◆ SwitchToLookupTable()

static bool SwitchToLookupTable ( SwitchInst SI,
IRBuilder<> &  Builder,
DomTreeUpdater DTU,
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 5829 of file SimplifyCFG.cpp.

References AddPredecessorToBlock(), llvm::DomTreeUpdater::applyUpdates(), assert(), BB, Builder, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count(), llvm::BasicBlock::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, DL, llvm::numbers::e, E, llvm::ConstantInt::get(), GetCaseResults(), llvm::Module::getContext(), llvm::Function::getFnAttribute(), llvm::Type::getInt1Ty(), llvm::APInt::getLimitedValue(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), llvm::Type::getPrimitiveSizeInBits(), llvm::ConstantInt::getType(), llvm::ConstantInt::getValue(), llvm::Attribute::getValueAsBool(), i, I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Constant::isNullValue(), llvm::max(), Mod, llvm::NextPowerOf2(), llvm::BasicBlock::removePredecessor(), Results, reuseTableCompare(), llvm::Value::setName(), llvm::APInt::sgt(), ShouldBuildLookupTable(), llvm::TargetTransformInfo::shouldBuildLookupTables(), SI, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size(), llvm::APInt::slt(), UINT64_MAX, and llvm::Value::users().

◆ switchToSelect()

static bool switchToSelect ( SwitchInst SI,
IRBuilder<> &  Builder,
DomTreeUpdater DTU,
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 5403 of file SimplifyCFG.cpp.

References assert(), Builder, Cond, ConvertTwoCaseSwitch(), DL, InitializeUniqueCases(), RemoveSwitchAfterSelectConversion(), and SI.

◆ TryToMergeLandingPad()

static bool TryToMergeLandingPad ( LandingPadInst LPad,
BranchInst BI,
BasicBlock BB,
DomTreeUpdater DTU 
)
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 6303 of file SimplifyCFG.cpp.

References llvm::DomTreeUpdater::applyUpdates(), assert(), BB, llvm::BasicBlock::begin(), Builder, llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::Instruction::eraseFromParent(), llvm::InvokeInst::getNormalDest(), llvm::BasicBlock::getTerminator(), llvm::InvokeInst::getUnwindDest(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::Instruction::isIdenticalTo(), llvm::make_early_inc_range(), llvm::pred_begin(), llvm::pred_end(), llvm::predecessors(), llvm::BasicBlock::removePredecessor(), llvm::InvokeInst::setUnwindDest(), llvm::succ_begin(), and llvm::succ_end().

◆ tryWidenCondBranchToCondBranch()

static bool tryWidenCondBranchToCondBranch ( BranchInst PBI,
BranchInst BI,
DomTreeUpdater DTU 
)
static

◆ validateAndCostRequiredSelects()

static bool validateAndCostRequiredSelects ( BasicBlock BB,
BasicBlock ThenBB,
BasicBlock EndBB,
unsigned &  SpeculatedInstructions,
InstructionCost Cost,
const TargetTransformInfo TTI 
)
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 5099 of file SimplifyCFG.cpp.

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

References llvm::array_pod_sort(), C1, llvm::numbers::e, i, i1, std::swap(), llvm::NVPTX::PTXLdStInstCode::V2, and llvm::Value::Value().

Variable Documentation

◆ BranchFoldThreshold

cl::opt<unsigned> BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden, cl::init(2), cl::desc("Maximum cost of combining conditions when " "folding branches"))
static

◆ BranchFoldToCommonDestVectorMultiplier

cl::opt<unsigned> BranchFoldToCommonDestVectorMultiplier("simplifycfg-branch-fold-common-dest-vector-multiplier", cl::Hidden, cl::init(2), cl::desc("Multiplier to apply to threshold when determining whether or not " "to fold branch to common destination when vector operations are " "present"))
static

◆ HoistCommon

cl::opt<bool> HoistCommon("simplifycfg-hoist-common", cl::Hidden, cl::init(true), cl::desc("Hoist common instructions up to the parent block"))
static

◆ 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

◆ MaxSmallBlockSize

cl::opt<int> MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10), cl::desc("Max size of a block which is still considered " "small enough to thread through"))
static

◆ 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

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

◆ TwoEntryPHINodeFoldingThreshold

cl::opt<unsigned> TwoEntryPHINodeFoldingThreshold("two-entry-phi-node-folding-threshold", cl::Hidden, cl::init(4), cl::desc("Control the maximal total instruction cost that we are willing " "to speculatively execute to fold a 2-entry PHI node into a " "select (default = 4)"))
static

Referenced by FoldTwoEntryPHINode().