LLVM
15.0.0git
|
#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/DomTreeUpdater.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/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/NoFolder.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/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/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") | |
STATISTIC (NumInvokesMerged, "Number of invokes that were merged together") | |
STATISTIC (NumInvokeSetsFormed, "Number of invoke sets that were formed") | |
static bool | IncomingValuesAreCompatible (BasicBlock *BB, ArrayRef< BasicBlock * > IncomingBlocks, SmallPtrSetImpl< Value * > *EquivalenceSet=nullptr) |
Return true if all the PHI nodes in the basic block BB receive compatible (identical) incoming values when coming from all of the predecessor blocks that are specified in IncomingBlocks . More... | |
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 ConstantInt * | GetConstantInt (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 void | MergeCompatibleInvokesImpl (ArrayRef< InvokeInst * > Invokes, DomTreeUpdater *DTU) |
static bool | MergeCompatibleInvokes (BasicBlock *BB, DomTreeUpdater *DTU) |
If this block is a landingpad exception handling block, categorize all the predecessor invoke s into sets, with all invoke s in each set being "mergeable" together, and then merge invokes in each set together. More... | |
static Value * | isSafeToSpeculateStore (Instruction *I, BasicBlock *BrBB, BasicBlock *StoreBB, BasicBlock *EndBB) |
Determine if we can hoist sink a sole store instruction out of a conditional block. More... | |
static bool | 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 ConstantInt * | getKnownValueOnEdge (Value *V, BasicBlock *From, BasicBlock *To) |
static Optional< bool > | FoldCondBranchOnValueKnownInPredecessorImpl (BranchInst *BI, DomTreeUpdater *DTU, const DataLayout &DL, AssumptionCache *AC) |
If we have a conditional branch on something for which we know the constant value in predecessors (e.g. More... | |
static bool | FoldCondBranchOnValueKnownInPredecessor (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 Value * | createLogicalOp (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 StoreInst * | findUniqueStoreInBlocks (BasicBlock *BB1, BasicBlock *BB2) |
static Value * | ensureValueAvailableInSuccessor (Value *V, BasicBlock *BB, Value *AlternativeV=nullptr) |
static bool | mergeConditionalStoreToAddress (BasicBlock *PTB, BasicBlock *PFB, BasicBlock *QTB, BasicBlock *QFB, BasicBlock *PostBB, Value *Address, bool InvertPCond, bool InvertQCond, 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 PHINode * | FindPHIForConditionForwarding (ConstantInt *CaseValue, BasicBlock *BB, int *PhiIndex) |
If BB would be eligible for simplification by TryToSimplifyUncondBranchFromEmptyBlock (i.e. More... | |
static bool | ForwardSwitchConditionToPHI (SwitchInst *SI) |
Try to forward the condition of a switch instruction to a phi node dominated by the switch, if that would mean that some of the destination blocks of the switch can be folded away. More... | |
static bool | ValidLookupTableConstant (Constant *C, const TargetTransformInfo &TTI) |
Return true if the backend will be able to handle initializing an array of constants like C. More... | |
static Constant * | LookupConstant (Value *V, const SmallDenseMap< Value *, Constant * > &ConstantPool) |
If V is a Constant, return it. More... | |
static Constant * | ConstantFold (Instruction *I, const DataLayout &DL, const SmallDenseMap< Value *, Constant * > &ConstantPool) |
Try to fold instruction I into a constant. More... | |
static bool | getCaseResults (SwitchInst *SI, ConstantInt *CaseVal, BasicBlock *CaseDest, BasicBlock **CommonDest, SmallVectorImpl< std::pair< PHINode *, Constant * >> &Res, const DataLayout &DL, const TargetTransformInfo &TTI) |
Try to determine the resulting constant values in phi nodes at the common destination basic block, *CommonDest, for one of the case destionations CaseDest corresponding to value CaseVal (0 for the default case), of a switch instruction SI. More... | |
static size_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) |
static Value * | foldSwitchToSelect (const SwitchCaseResultVectorTy &ResultVector, Constant *DefaultResult, Value *Condition, IRBuilder<> &Builder) |
static void | removeSwitchAfterSelectFold (SwitchInst *SI, PHINode *PHI, Value *SelectValue, IRBuilder<> &Builder, DomTreeUpdater *DTU) |
static bool | trySwitchToSelect (SwitchInst *SI, IRBuilder<> &Builder, DomTreeUpdater *DTU, const DataLayout &DL, const TargetTransformInfo &TTI) |
If a switch is only used to initialize one or more phi nodes in a common successor block with only two different constant values, try to replace the switch with a select. More... | |
static bool | isTypeLegalForLookupTable (Type *Ty, const TargetTransformInfo &TTI, const DataLayout &DL) |
static bool | isSwitchDense (uint64_t NumCases, uint64_t CaseRange) |
static bool | isSwitchDense (ArrayRef< int64_t > Values) |
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 | 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 BasicBlock * | allPredecessorsComeFromSameSource (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< 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 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")) |
static cl::opt< bool > | EnableMergeCompatibleInvokes ("simplifycfg-merge-compatible-invokes", cl::Hidden, cl::init(true), cl::desc("Allow SimplifyCFG to merge invokes together when appropriate")) |
static cl::opt< unsigned > | MaxSwitchCasesPerResult ("max-switch-cases-per-result", cl::Hidden, cl::init(16), cl::desc("Limit cases to analyze when converting a switch to select")) |
#define DEBUG_TYPE "simplifycfg" |
Definition at line 91 of file SimplifyCFG.cpp.
|
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 364 of file SimplifyCFG.cpp.
References llvm::BasicBlock::phis().
Referenced by FoldCondBranchOnValueKnownInPredecessorImpl(), performBranchToCommonDestFolding(), SimplifyCondBranchToCondBranch(), and SwitchToLookupTable().
|
static |
Definition at line 6787 of file SimplifyCFG.cpp.
References BB, P, and llvm::predecessors().
|
static |
Return true if we can thread a branch across this block.
Definition at line 2925 of file SimplifyCFG.cpp.
References llvm::all_of(), BB, llvm::Instruction::getParent(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), MaxSmallBlockSize, llvm::reverse(), and llvm::Check::Size.
Referenced by FoldCondBranchOnValueKnownInPredecessorImpl().
|
static |
Definition at line 1706 of file SimplifyCFG.cpp.
References llvm::all_of(), llvm::any_of(), assert(), Callee, llvm::canReplaceOperandWithVariable(), llvm::ArrayRef< T >::front(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::Instruction::getSuccessor(), llvm::BasicBlock::getTerminator(), I, isLifeTimeMarker(), replacingOperandWithVariableIsCheap(), llvm::Value::user_begin(), and llvm::Value::user_empty().
Referenced by SinkCommonCodeFromPredecessors().
|
static |
Definition at line 5108 of file SimplifyCFG.cpp.
References llvm::array_pod_sort(), assert(), ConstantIntSortPredicate(), E, and I.
|
static |
Definition at line 1095 of file SimplifyCFG.cpp.
References assert(), BB, llvm::Instruction::clone(), llvm::Instruction::dropUndefImplyingAttrsAndUnknownMetadata(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::BasicBlock::getTerminator(), llvm::make_early_inc_range(), llvm::RemapInstruction(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, llvm::Instruction::setDebugLoc(), and llvm::Value::takeName().
Referenced by performBranchToCommonDestFolding().
|
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 378 of file SimplifyCFG.cpp.
References assert(), llvm::TargetTransformInfo::getUserCost(), I, llvm::isSafeToSpeculativelyExecute(), and llvm::TargetTransformInfo::TCK_SizeAndLatency.
Referenced by dominatesMergePoint(), and validateAndCostRequiredSelects().
|
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 5478 of file SimplifyCFG.cpp.
References A, llvm::ConstantFoldInstOperands(), DL, E, I, LookupConstant(), N, and llvm::MCID::Select.
Referenced by getCaseResults().
|
static |
Definition at line 1044 of file SimplifyCFG.cpp.
Referenced by CasesAreContiguous().
|
static |
Definition at line 3340 of file SimplifyCFG.cpp.
References Builder, llvm::impliesPoison(), LHS, llvm_unreachable, and RHS.
Referenced by performBranchToCommonDestFolding(), and SimplifyCondBranchToCondBranch().
|
static |
Definition at line 5119 of file SimplifyCFG.cpp.
References llvm::DomTreeUpdater::applyUpdates(), BB, llvm::dbgs(), Insert, llvm::is_contained(), LLVM_DEBUG, and llvm::successors().
Referenced by eliminateDeadSwitchCases().
|
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 403 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().
|
static |
Given a vector of bb/value pairs, remove any entries in the list that match the specified block.
Definition at line 813 of file SimplifyCFG.cpp.
References BB, and llvm::erase_value().
|
static |
Compute masked bits for the condition of a switch and use it to remove dead cases.
Definition at line 5271 of file SimplifyCFG.cpp.
References llvm::DomTreeUpdater::applyUpdates(), assert(), llvm::computeKnownBits(), llvm::ComputeMaxSignificantBits(), Cond, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count(), llvm::countPopulation(), createUnreachableSwitchDefault(), llvm::dbgs(), DL, llvm::KnownBits::getBitWidth(), llvm::APInt::getMinSignedBits(), llvm::APInt::intersects(), llvm::APInt::isSubsetOf(), LLVM_DEBUG, llvm::KnownBits::One, llvm::SwitchInstProfUpdateWrapper::removeCase(), SI, llvm::Successor, and llvm::KnownBits::Zero.
|
static |
Definition at line 3693 of file SimplifyCFG.cpp.
References llvm::PHINode::addIncoming(), assert(), BB, llvm::BasicBlock::begin(), llvm::BasicBlock::front(), get, llvm::PHINode::getIncomingValueForBlock(), getParent(), llvm::Value::getType(), llvm::BasicBlock::hasNPredecessors(), I, llvm::pred_begin(), and llvm::predecessors().
Referenced by mergeConditionalStoreToAddress().
|
static |
Definition at line 746 of file SimplifyCFG.cpp.
References Cond, llvm::Instruction::eraseFromParent(), llvm::RecursivelyDeleteTriviallyDeadInstructions(), and SI.
|
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 3356 of file SimplifyCFG.cpp.
References llvm::Instruction::extractProfMetadata().
Referenced by performBranchToCommonDestFolding(), and SimplifyCondBranchToCondBranch().
|
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 5350 of file SimplifyCFG.cpp.
References assert(), BB, llvm::MCID::Branch, and llvm::BasicBlock::phis().
Referenced by ForwardSwitchConditionToPHI().
|
static |
Definition at line 3676 of file SimplifyCFG.cpp.
Referenced by mergeConditionalStoreToAddress().
|
static |
Keep halving the weights until all can fit in uint32_t.
Definition at line 1086 of file SimplifyCFG.cpp.
References llvm::MutableArrayRef< T >::begin(), llvm::countLeadingZeros(), llvm::MutableArrayRef< T >::end(), and I.
Referenced by performBranchToCommonDestFolding(), and SimplifyCondBranchToCondBranch().
|
static |
Definition at line 3131 of file SimplifyCFG.cpp.
References DL, FoldCondBranchOnValueKnownInPredecessorImpl(), and llvm::None.
|
static |
If we have a conditional branch on something for which we know the constant value in predecessors (e.g.
a phi node in the current block), thread edges from the predecessor to their ultimate destination.
Definition at line 2991 of file SimplifyCFG.cpp.
References AddPredecessorToBlock(), llvm::any_of(), llvm::DomTreeUpdater::applyUpdates(), BB, BlockIsSimpleEnoughToThreadThrough(), Cond, llvm::dbgs(), DL, llvm::MapVector< KeyT, ValueT, SmallDenseMap< KeyT, unsigned, N >, SmallVector< std::pair< KeyT, ValueT >, N > >::empty(), 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::getIncomingValueForBlock(), getKnownValueOnEdge(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), llvm::ConstantInt::getZExtValue(), llvm::PHINode::incoming_values(), Insert, llvm::MapVector< KeyT, ValueT, SmallDenseMap< KeyT, unsigned, N >, SmallVector< std::pair< KeyT, ValueT >, N > >::insert(), LLVM_DEBUG, llvm::MergeBlockIntoPredecessor(), N, llvm::None, llvm::predecessors(), llvm::AssumptionCache::registerAssumption(), llvm::Instruction::setDebugLoc(), llvm::BranchInst::setSuccessor(), llvm::simplifyInstruction(), and llvm::SplitBlockPredecessors().
Referenced by FoldCondBranchOnValueKnownInPredecessor().
|
static |
Definition at line 5653 of file SimplifyCFG.cpp.
References llvm::And, Builder, llvm::APInt::countPopulation(), llvm::ConstantInt::getBitWidth(), llvm::ConstantInt::getValue(), llvm::Constant::isNullValue(), llvm::isPowerOf2_32(), llvm::Log2_32(), and llvm::ArrayRef< T >::size().
Referenced by trySwitchToSelect().
|
static |
Given a BB that starts with the specified two-entry PHI node, see if we can eliminate it.
Definition at line 3147 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(), DL, dominatesMergePoint(), llvm::Instruction::eraseFromParent(), llvm::Instruction::extractProfMetadata(), llvm::tgtok::FalseVal, 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, Insert, llvm::Type::isIntegerTy(), LLVM_DEBUG, llvm::PatternMatch::m_AnyIntegralConstant(), llvm::MIPatternMatch::m_BinOp(), llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_ImmConstant(), llvm::MIPatternMatch::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::tgtok::TrueVal, and TwoEntryPHINodeFoldingThreshold.
|
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 5381 of file SimplifyCFG.cpp.
References llvm::count(), FindPHIForConditionForwarding(), llvm::BasicBlock::phis(), llvm::PHINode::setIncomingValue(), and SI.
|
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 1065 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().
|
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 5507 of file SimplifyCFG.cpp.
References ConstantFold(), ConstantPool, DL, llvm::Use::getUser(), I, llvm::BasicBlock::instructionsWithoutDebug(), LookupConstant(), SI, and ValidLookupTableConstant().
Referenced by initializeUniqueCases(), and SwitchToLookupTable().
|
static |
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
Return NULL if value is not a constant int.
Definition at line 472 of file SimplifyCFG.cpp.
References DL, llvm::ConstantInt::get(), llvm::ConstantExpr::getIntegerCast(), llvm::ConstantInt::getType(), llvm::Value::getType(), and llvm::Type::isPointerTy().
|
static |
Definition at line 2969 of file SimplifyCFG.cpp.
References From, llvm::BranchInst::getCondition(), llvm::Value::getContext(), getFalse(), llvm::BranchInst::getSuccessor(), getTrue(), I, and llvm::BranchInst::isConditional().
Referenced by FoldCondBranchOnValueKnownInPredecessorImpl().
|
inlinestatic |
Definition at line 1053 of file SimplifyCFG.cpp.
References llvm::MDNode::getOperand(), and I.
|
static |
Return true if all the PHI nodes in the basic block BB
receive compatible (identical) incoming values when coming from all of the predecessor blocks that are specified in IncomingBlocks
.
Note that if the values aren't exactly identical, but EquivalenceSet
is provided, and both of the values are present in the set, then they are considered equal.
Definition at line 308 of file SimplifyCFG.cpp.
References llvm::all_of(), assert(), BB, and llvm::ArrayRef< T >::size().
Referenced by SafeToMergeTerminators().
|
static |
Definition at line 5596 of file SimplifyCFG.cpp.
References llvm::Function::begin(), DL, getCaseResults(), llvm::BasicBlock::getFirstNonPHIOrDbg(), I, mapCaseToResult(), MaxSwitchCasesPerResult, Results, SI, and llvm::Function::size().
Referenced by trySwitchToSelect().
|
static |
Definition at line 4663 of file SimplifyCFG.cpp.
References llvm::CallBase::getIntrinsicID(), I, and llvm::RISCVFenceField::R.
Referenced by removeEmptyCleanup().
|
static |
|
static |
Definition at line 1419 of file SimplifyCFG.cpp.
References I1, llvm::BasicBlock::phis(), and llvm::successors().
|
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 ...
Definition at line 2584 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.
|
static |
Definition at line 6071 of file SimplifyCFG.cpp.
References llvm::ArrayRef< T >::back(), llvm::ArrayRef< T >::front(), isSwitchDense(), and llvm::ArrayRef< T >::size().
Definition at line 6059 of file SimplifyCFG.cpp.
References UINT64_MAX.
Referenced by isSwitchDense(), ReduceSwitchRange(), and ShouldBuildLookupTable().
|
static |
Definition at line 6038 of file SimplifyCFG.cpp.
References llvm::BitWidth, DL, llvm::isPowerOf2_32(), llvm::TargetTransformInfo::isTypeLegal(), and IT.
Referenced by ShouldBuildLookupTable().
|
static |
Return if an instruction's type or any of its operands' types are a vector type.
Definition at line 3541 of file SimplifyCFG.cpp.
References llvm::any_of(), and I.
Referenced by llvm::FoldBranchToCommonDest().
|
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 5466 of file SimplifyCFG.cpp.
Referenced by ConstantFold(), and getCaseResults().
|
static |
Definition at line 5578 of file SimplifyCFG.cpp.
References I.
Referenced by initializeUniqueCases().
|
static |
Definition at line 4894 of file SimplifyCFG.cpp.
References llvm::Instruction::eraseFromParent(), llvm::BasicBlock::front(), llvm::CleanupReturnInst::getCleanupPad(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::CleanupReturnInst::getUnwindDest(), and llvm::Value::replaceAllUsesWith().
|
static |
If this block is a landingpad
exception handling block, categorize all the predecessor invoke
s into sets, with all invoke
s in each set being "mergeable" together, and then merge invokes in each set together.
This is a weird mix of hoisting and sinking. Visually, it goes from: [...] [...] | | [invoke0] [invoke1] / \ / \ [cont0] [landingpad] [cont1] to: [...] [...] \ / [invoke] / \ [cont] [landingpad]
But of course we can only do that if the invokes share the landingpad
, edges invoke0->cont0 and invoke1->cont1 are "compatible", and the invoked functions are "compatible".
Definition at line 2529 of file SimplifyCFG.cpp.
References BB, EnableMergeCompatibleInvokes, MergeCompatibleInvokesImpl(), llvm::predecessors(), and llvm::ArrayRef< T >::size().
|
static |
Definition at line 2384 of file SimplifyCFG.cpp.
References assert(), llvm::Instruction::clone(), llvm::BasicBlock::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::ArrayRef< T >::front(), llvm::Value::getContext(), llvm::BasicBlock::getInstList(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallVectorImpl< T >::reserve(), llvm::InvokeInst::setNormalDest(), llvm::ArrayRef< T >::size(), and llvm::successors().
Referenced by MergeCompatibleInvokes().
|
static |
Definition at line 3885 of file SimplifyCFG.cpp.
References BB, DL, llvm::Instruction::getParent(), llvm::BasicBlock::getSingleSuccessor(), llvm::BranchInst::getSuccessor(), llvm::Value::hasNUses(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), mergeConditionalStoreToAddress(), P, S, llvm::set_intersect(), SI, and std::swap().
Referenced by SimplifyCondBranchToCondBranch().
|
static |
Definition at line 3742 of file SimplifyCFG.cpp.
References assert(), BB, llvm::IRBuilderBase::CreateNot(), llvm::IRBuilderBase::CreateOr(), llvm::IRBuilderBase::CreateStore(), E, llvm::BasicBlock::end(), ensureValueAvailableInSuccessor(), llvm::Instruction::eraseFromParent(), llvm::find(), findUniqueStoreInBlocks(), llvm::Instruction::getAAMetadata(), llvm::StoreInst::getAlign(), llvm::BasicBlock::getFirstInsertionPt(), llvm::IRBuilderBase::GetInsertPoint(), llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::TargetTransformInfo::getUserCost(), llvm::StoreInst::getValueOperand(), I, llvm::StoreInst::isUnordered(), llvm::AAMDNodes::merge(), MergeCondStoresAggressively, llvm::min(), PHINodeFoldingThreshold, llvm::pred_begin(), llvm::pred_end(), S, llvm::IRBuilderBase::SetInsertPoint(), SI, llvm::SplitBlockAndInsertIfThen(), and llvm::SplitBlockPredecessors().
Referenced by mergeConditionalStores().
|
static |
Check if passing a value to an instruction will cause undefined behavior.
Definition at line 6907 of file SimplifyCFG.cpp.
References llvm::any_of(), Arg, GEP, I, llvm::isGuaranteedToTransferExecutionToSuccessor(), llvm::make_range(), llvm::NullPointerIsDefined(), and SI.
Referenced by removeUndefIntroducingPredecessor(), and validateAndCostRequiredSelects().
|
static |
Definition at line 3419 of file SimplifyCFG.cpp.
References AddPredecessorToBlock(), llvm::DomTreeUpdater::applyUpdates(), BB, Builder, CloneInstructionsIntoPredecessorBlockAndUpdateSSAUses(), createLogicalOp(), llvm::dbgs(), extractPredSuccWeights(), FitWeights(), llvm::BranchInst::getCondition(), llvm::CmpInst::getInversePredicate(), llvm::Instruction::getMetadata(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BranchInst::getSuccessor(), llvm::Value::hasOneUse(), I, Insert, llvm::Instruction::insertBefore(), LLVM_DEBUG, llvm::RemapInstruction(), llvm::RF_IgnoreMissingLocals, llvm::RF_NoModuleLevelChanges, setBranchWeights(), llvm::BranchInst::setCondition(), llvm::Instruction::setMetadata(), llvm::CmpInst::setPredicate(), llvm::BranchInst::setSuccessor(), shouldFoldCondBranchesToCommonDestination(), and llvm::BranchInst::swapSuccessors().
Referenced by llvm::FoldBranchToCommonDest().
|
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 6464 of file SimplifyCFG.cpp.
References assert(), llvm::sampleprof::Base, Builder, llvm::countTrailingZeros(), DL, get, isSwitchDense(), llvm::min(), Shift, SI, and llvm::sort().
|
static |
Definition at line 4776 of file SimplifyCFG.cpp.
References llvm::PHINode::addIncoming(), llvm::DomTreeUpdater::applyUpdates(), assert(), BB, llvm::DeleteDeadBlock(), get, llvm::CleanupReturnInst::getCleanupPad(), llvm::BasicBlock::getFirstNonPHI(), llvm::PHINode::getIncomingValueForBlock(), llvm::ilist_node_with_parent< NodeTy, ParentTy, Options >::getNextNode(), llvm::Instruction::getParent(), llvm::Value::getType(), llvm::CleanupReturnInst::getUnwindDest(), llvm::Value::hasOneUse(), Insert, isCleanupBlockEmpty(), llvm::Instruction::isUsedOutsideOfBlock(), llvm::make_early_inc_range(), llvm::Instruction::moveBefore(), llvm::BasicBlock::phis(), pred, llvm::predecessors(), llvm::removeUnwindEdge(), llvm::User::replaceUsesOfWith(), and llvm::Value::use_empty().
|
static |
Definition at line 5729 of file SimplifyCFG.cpp.
References llvm::PHINode::addIncoming(), llvm::DomTreeUpdater::applyUpdates(), Builder, llvm::numbers::e, llvm::PHINode::getBasicBlockIndex(), llvm::Instruction::getParent(), i, Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::is_contained(), llvm::predecessors(), llvm::PHINode::removeIncomingValue(), llvm::BasicBlock::removePredecessor(), and SI.
Referenced by trySwitchToSelect().
|
static |
If BB has an incoming value that will always trigger undefined behavior (eg.
null pointer dereference), remove the branch leading here.
Definition at line 6993 of file SimplifyCFG.cpp.
References llvm::DomTreeUpdater::applyUpdates(), BB, Builder, Cond, llvm::numbers::e, llvm::Instruction::eraseFromParent(), llvm::BranchInst::getCondition(), llvm::BasicBlock::getContext(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), i, Insert, llvm::BranchInst::isUnconditional(), passingValueIsAlwaysUndefined(), and SI.
|
static |
|
static |
Try to reuse the switch table index compare.
Following pattern:
Is optimized to:
Jump threading will then eliminate the second if(cond).
Definition at line 6143 of file SimplifyCFG.cpp.
References get, llvm::BranchInst::getCondition(), getFalse(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::CmpInst::getPredicate(), getTrue(), llvm::Value::getType(), llvm::BasicBlock::getUniquePredecessor(), llvm::predecessors(), and llvm::Value::replaceAllUsesWith().
Referenced by SwitchToLookupTable().
|
static |
Return true if it is safe to merge these two terminator instructions together.
Definition at line 332 of file SimplifyCFG.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count(), Fail, llvm::Instruction::getParent(), IncomingValuesAreCompatible(), llvm::succ_begin(), llvm::succ_end(), and llvm::successors().
Referenced by llvm::FoldBranchToCommonDest().
|
static |
Definition at line 865 of file SimplifyCFG.cpp.
References assert(), llvm::MDBuilder::createBranchWeights(), I, and N.
|
static |
Definition at line 854 of file SimplifyCFG.cpp.
References llvm::any_of(), llvm::MDBuilder::createBranchWeights(), N, SI, and llvm::RISCVFenceField::W.
Referenced by performBranchToCommonDestFolding(), and SimplifyCondBranchToCondBranch().
|
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 6086 of file SimplifyCFG.cpp.
References DL, I, isSwitchDense(), isTypeLegalForLookupTable(), and SI.
Referenced by SwitchToLookupTable().
|
static |
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.
Definition at line 3380 of file SimplifyCFG.cpp.
References assert(), llvm::Instruction::extractProfMetadata(), llvm::BranchProbability::getCompl(), llvm::Instruction::getMetadata(), llvm::Instruction::getParent(), llvm::TargetTransformInfo::getPredictableBranchThreshold(), llvm::BranchInst::getSuccessor(), llvm::is_contained(), llvm::BranchInst::isConditional(), llvm::BranchProbability::isUnknown(), llvm::None, and llvm::predecessors().
Referenced by llvm::FoldBranchToCommonDest(), and performBranchToCommonDestFolding().
|
static |
If we have a conditional branch as a predecessor of another block, this function tries to simplify it.
We know that PBI and BI are both conditional branches, and BI is in one of the successor blocks of PBI - PBI branches to BI.
Definition at line 4049 of file SimplifyCFG.cpp.
References AddPredecessorToBlock(), llvm::DomTreeUpdater::applyUpdates(), assert(), BB, llvm::BasicBlock::begin(), Builder, Cond, createLogicalOp(), llvm::dbgs(), DL, extractPredSuccWeights(), FitWeights(), get, llvm::PHINode::getBasicBlockIndex(), llvm::BranchInst::getCondition(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BranchInst::getSuccessor(), Insert, llvm::BranchInst::isConditional(), LLVM_DEBUG, mergeConditionalStores(), MergeCondStores, llvm::BasicBlock::phis(), setBranchWeights(), llvm::BranchInst::setCondition(), llvm::PHINode::setIncomingValue(), llvm::BranchInst::setSuccessor(), and tryWidenCondBranchToCondBranch().
|
static |
Check whether BB's predecessors end with unconditional branches.
If it is true, sink any common code from the predecessors to BB.
Definition at line 2006 of file SimplifyCFG.cpp.
References assert(), BB, canSinkInstructions(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::dbgs(), llvm::SmallPtrSetImpl< PtrType >::erase(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::IsBlockFollowedByDeoptOrUnreachable(), llvm::isSafeToSpeculativelyExecute(), LLVM_DEBUG, llvm::predecessors(), sinkLastInstruction(), and llvm::SplitBlockPredecessors().
|
static |
Definition at line 1834 of file SimplifyCFG.cpp.
References llvm::all_of(), llvm::Instruction::andIRFlags(), llvm::any_of(), llvm::Instruction::applyMergedLocation(), assert(), BB, llvm::combineMetadataForCSE(), llvm::PHINode::Create(), E, llvm::Instruction::getDebugLoc(), llvm::User::getNumOperands(), llvm::User::getOperand(), llvm::User::getOperandUse(), I, llvm::Instruction::moveBefore(), llvm::RISCVFenceField::O, llvm::Use::set(), llvm::Value::user_begin(), and llvm::Value::user_empty().
Referenced by SinkCommonCodeFromPredecessors().
STATISTIC | ( | NumBitMaps | , |
"Number of switch instructions turned into bitmaps" | |||
) |
STATISTIC | ( | NumFoldValueComparisonIntoPredecessors | , |
"Number of value comparisons folded into predecessor basic blocks" | |||
) |
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 | ( | 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 | ( | 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" | |||
) |
|
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 6207 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(), DL, llvm::numbers::e, E, get, getCaseResults(), llvm::Module::getContext(), llvm::Function::getFnAttribute(), 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, 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().
|
static |
If a switch is only used to initialize one or more phi nodes in a common successor block with only two different constant values, try to replace the switch with a select.
Returns true if the fold was made.
Definition at line 5766 of file SimplifyCFG.cpp.
References assert(), Builder, Cond, DL, foldSwitchToSelect(), initializeUniqueCases(), removeSwitchAfterSelectFold(), and SI.
|
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 6670 of file SimplifyCFG.cpp.
References llvm::DomTreeUpdater::applyUpdates(), assert(), BB, llvm::BasicBlock::begin(), Builder, llvm::Instruction::eraseFromParent(), llvm::InvokeInst::getNormalDest(), llvm::BasicBlock::getTerminator(), llvm::InvokeInst::getUnwindDest(), I, 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().
|
static |
If the previous block ended with a widenable branch, determine if reusing the target block is profitable and legal.
This will have the effect of "widening" PBI, but doesn't require us to reason about hosting safety.
Definition at line 3997 of file SimplifyCFG.cpp.
References llvm::DomTreeUpdater::applyUpdates(), BB, llvm::Instruction::getParent(), llvm::BasicBlock::getSinglePredecessor(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminatingDeoptimizeCall(), I, Insert, llvm::none_of(), llvm::parseWidenableBranch(), llvm::BasicBlock::phis(), llvm::BasicBlock::removePredecessor(), and llvm::BranchInst::setSuccessor().
Referenced by SimplifyCondBranchToCondBranch().
|
static |
Estimate the cost of the insertion(s) and check that the PHI nodes can be converted to selects.
Definition at line 2644 of file SimplifyCFG.cpp.
References BB, computeSpeculationCost(), CostKind, llvm::TargetTransformInfo::getCmpSelInstrCost(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getType(), passingValueIsAlwaysUndefined(), PHINodeFoldingThreshold, llvm::BasicBlock::phis(), and llvm::MCID::Select.
|
static |
Return true if the backend will be able to handle initializing an array of constants like C.
Definition at line 5438 of file SimplifyCFG.cpp.
References llvm::TargetTransformInfo::shouldBuildLookupTablesForConstant().
Referenced by getCaseResults().
|
static |
Return true if there are any keys in C1 that exist in C2 as well.
Definition at line 819 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().
|
static |
Referenced by llvm::FoldBranchToCommonDest().
|
static |
Referenced by llvm::FoldBranchToCommonDest().
|
static |
Referenced by MergeCompatibleInvokes().
|
static |
|
static |
|
static |
Referenced by BlockIsSimpleEnoughToThreadThrough().
|
static |
Referenced by dominatesMergePoint().
|
static |
Referenced by initializeUniqueCases().
|
static |
Referenced by SimplifyCondBranchToCondBranch().
|
static |
Referenced by mergeConditionalStoreToAddress().
|
static |
Referenced by mergeConditionalStoreToAddress(), and validateAndCostRequiredSelects().
|
static |
|
static |
Referenced by dominatesMergePoint().
|
static |
Referenced by FoldTwoEntryPHINode().