LLVM  14.0.0git
Macros | Typedefs | Functions | Variables
Local.cpp File Reference
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/EHPersonalities.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/BinaryFormat/Dwarf.h"
#include "llvm/IR/Argument.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/DIBuilder.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalObject.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/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/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "local"
 

Typedefs

using PredBlockVector = SmallVector< BasicBlock *, 16 >
 
using IncomingValueMap = DenseMap< BasicBlock *, Value * >
 
using DbgValReplacement = Optional< DIExpression * >
 A replacement for a dbg.value expression. More...
 

Functions

 STATISTIC (NumRemoved, "Number of unreachable basic blocks removed")
 
 STATISTIC (NumPHICSEs, "Number of PHI's that got CSE'd")
 
static bool areAllUsesEqual (Instruction *I)
 areAllUsesEqual - Check whether the uses of a value are all the same. More...
 
static bool simplifyAndDCEInstruction (Instruction *I, SmallSetVector< Instruction *, 16 > &WorkList, const DataLayout &DL, const TargetLibraryInfo *TLI)
 
static bool CanMergeValues (Value *First, Value *Second)
 Return true if we can choose one of these values to use in place of the other. More...
 
static bool CanPropagatePredecessorsForPHIs (BasicBlock *BB, BasicBlock *Succ)
 Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ, into Succ. More...
 
static ValueselectIncomingValueForBlock (Value *OldVal, BasicBlock *BB, IncomingValueMap &IncomingValues)
 Determines the value to use as the phi node input for a block. More...
 
static void gatherIncomingValuesToPhi (PHINode *PN, IncomingValueMap &IncomingValues)
 Create a map from block to value for the operands of a given phi. More...
 
static void replaceUndefValuesInPhi (PHINode *PN, const IncomingValueMap &IncomingValues)
 Replace the incoming undef values to a phi with the values from a block-to-value map. More...
 
static void redirectValuesFromPredecessorsToPhi (BasicBlock *BB, const PredBlockVector &BBPreds, PHINode *PN)
 Replace a value flowing from a block to a phi with potentially multiple instances of that value flowing from the block's predecessors to the phi. More...
 
static bool EliminateDuplicatePHINodesNaiveImpl (BasicBlock *BB)
 
static bool EliminateDuplicatePHINodesSetBasedImpl (BasicBlock *BB)
 
static Align tryEnforceAlignment (Value *V, Align PrefAlign, const DataLayout &DL)
 If the specified pointer points to an object that we control, try to modify the object's alignment to PrefAlign. More...
 
static bool PhiHasDebugValue (DILocalVariable *DIVar, DIExpression *DIExpr, PHINode *APN)
 ===------------------------------------------------------------------—===// Dbg Intrinsic utilities More...
 
static bool valueCoversEntireFragment (Type *ValTy, DbgVariableIntrinsic *DII)
 Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) described by DII. More...
 
static DebugLoc getDebugValueLoc (DbgVariableIntrinsic *DII, Instruction *Src)
 Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted to a dbg.value. More...
 
static bool isArray (AllocaInst *AI)
 Determine whether this alloca is either a VLA or an array. More...
 
static bool isStructure (AllocaInst *AI)
 Determine whether this alloca is a structure. More...
 
static void replaceOneDbgValueForAlloca (DbgValueInst *DVI, Value *NewAddress, DIBuilder &Builder, int Offset)
 
ValuegetSalvageOpsForGEP (GetElementPtrInst *GEP, const DataLayout &DL, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
 
uint64_t getDwarfOpForBinOp (Instruction::BinaryOps Opcode)
 
ValuegetSalvageOpsForBinOp (BinaryOperator *BI, uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues)
 
static bool rewriteDebugUsers (Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT, function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)> RewriteExpr)
 Point debug users of From to To using exprs given by RewriteExpr, possibly moving/undefing users to prevent use-before-def. More...
 
static bool isBitCastSemanticsPreserving (const DataLayout &DL, Type *FromTy, Type *ToTy)
 Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and semantics of the value. More...
 
static bool markAliveBlocks (Function &F, SmallPtrSetImpl< BasicBlock * > &Reachable, DomTreeUpdater *DTU=nullptr)
 
template<typename RootType , typename DominatesFn >
static unsigned replaceDominatedUsesWith (Value *From, Value *To, const RootType &Root, const DominatesFn &Dominates)
 
static const Optional< BitPart > & collectBitParts (Value *V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value *, Optional< BitPart >> &BPS, int Depth, bool &FoundRoot)
 Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitreverse. More...
 
static bool bitTransformIsCorrectForBSwap (unsigned From, unsigned To, unsigned BitWidth)
 
static bool bitTransformIsCorrectForBitReverse (unsigned From, unsigned To, unsigned BitWidth)
 

Variables

static cl::opt< bool > PHICSEDebugHash ("phicse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that PHINodes's hash " "function is well-behaved w.r.t. its isEqual predicate"))
 
static cl::opt< unsigned > PHICSENumPHISmallSize ("phicse-num-phi-smallsize", cl::init(32), cl::Hidden, cl::desc("When the basic block contains not more than this number of PHI nodes, " "perform a (faster!) exhaustive search instead of set-driven one."))
 
static const unsigned BitPartRecursionMaxDepth = 48
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "local"

Definition at line 91 of file Local.cpp.

Typedef Documentation

◆ DbgValReplacement

A replacement for a dbg.value expression.

Definition at line 1937 of file Local.cpp.

◆ IncomingValueMap

Definition at line 889 of file Local.cpp.

◆ PredBlockVector

Definition at line 888 of file Local.cpp.

Function Documentation

◆ areAllUsesEqual()

static bool areAllUsesEqual ( Instruction I)
static

areAllUsesEqual - Check whether the uses of a value are all the same.

This is similar to Instruction::hasOneUse() except this will also return true when there are no uses or multiple uses that all refer to the same value.

Definition at line 602 of file Local.cpp.

References I.

Referenced by llvm::RecursivelyDeleteDeadPHINode().

◆ bitTransformIsCorrectForBitReverse()

static bool bitTransformIsCorrectForBitReverse ( unsigned  From,
unsigned  To,
unsigned  BitWidth 
)
static

Definition at line 3125 of file Local.cpp.

References llvm::BitWidth, and From.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ bitTransformIsCorrectForBSwap()

static bool bitTransformIsCorrectForBSwap ( unsigned  From,
unsigned  To,
unsigned  BitWidth 
)
static

Definition at line 3114 of file Local.cpp.

References llvm::BitWidth, and From.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ CanMergeValues()

static bool CanMergeValues ( Value First,
Value Second 
)
static

Return true if we can choose one of these values to use in place of the other.

Note that we will always choose the non-undef value to keep.

Definition at line 823 of file Local.cpp.

References First.

Referenced by CanPropagatePredecessorsForPHIs().

◆ CanPropagatePredecessorsForPHIs()

static bool CanPropagatePredecessorsForPHIs ( BasicBlock BB,
BasicBlock Succ 
)
static

◆ collectBitParts()

static const Optional<BitPart>& collectBitParts ( Value V,
bool  MatchBSwaps,
bool  MatchBitReversals,
std::map< Value *, Optional< BitPart >> &  BPS,
int  Depth,
bool &  FoundRoot 
)
static

Analyze the specified subexpression and see if it is capable of providing pieces of a bswap or bitreverse.

The subexpression provides a potential piece of a bswap or bitreverse if it can be proved that each non-zero bit in the output of the expression came from a corresponding bit in some other value. This function is recursive, and the end result is a mapping of bitnumber to bitnumber. It is the caller's responsibility to validate that the bitnumber to bitnumber mapping is correct for a bswap or bitreverse.

For example, if the current subexpression if "(shl i32 %X, 24)" then we know that the expression deposits the low byte of X into the high byte of the result and that all other bits are zero. This expression is accepted and a BitPart is returned with Provider set to X and Provenance[24-31] set to [0-7].

For vector types, all analysis is performed at the per-element level. No cross-element analysis is supported (shuffle/insertion/reduction), and all constant masks must be splatted across all elements.

To avoid revisiting values, the BitPart results are memoized into the provided map. To avoid unnecessary copying of BitParts, BitParts are constructed in-place in the BPS map. Because of this BPS needs to store BitParts objects, not pointers. As we need the concept of a nullptr BitParts (Value has been analyzed and the analysis failed), we an Optional type instead to provide the same functionality.

Because we pass around references into BPS, we must use a container that does not invalidate internal references (std::map instead of DenseMap).

Definition at line 2894 of file Local.cpp.

References B, BitPartRecursionMaxDepth, llvm::BitWidth, llvm::APInt::countPopulation(), llvm::dbgs(), llvm::Depth, for, getIntrinsicID(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), llvm::APInt::getZExtValue(), I, LLVM_DEBUG, llvm::PatternMatch::m_And(), llvm::PatternMatch::m_APInt(), llvm::PatternMatch::m_BitReverse(), llvm::PatternMatch::m_BSwap(), llvm::PatternMatch::m_FShl(), llvm::PatternMatch::m_FShr(), llvm::PatternMatch::m_LogicalShift(), llvm::PatternMatch::m_Or(), llvm::PatternMatch::m_Trunc(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::m_ZExt(), llvm::PatternMatch::match(), llvm::None, P, llvm::APInt::uge(), X, and Y.

Referenced by llvm::recognizeBSwapOrBitReverseIdiom().

◆ EliminateDuplicatePHINodesNaiveImpl()

static bool EliminateDuplicatePHINodesNaiveImpl ( BasicBlock BB)
static

◆ EliminateDuplicatePHINodesSetBasedImpl()

static bool EliminateDuplicatePHINodesSetBasedImpl ( BasicBlock BB)
static

◆ gatherIncomingValuesToPhi()

static void gatherIncomingValuesToPhi ( PHINode PN,
IncomingValueMap IncomingValues 
)
static

Create a map from block to value for the operands of a given phi.

Create a map from block to value for each non-undef value flowing into PN.

Parameters
PNThe phi we are collecting the map for.
IncomingValues[out] The map from block to value for this phi.

Definition at line 928 of file Local.cpp.

References BB, llvm::numbers::e, llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), i, and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

Referenced by redirectValuesFromPredecessorsToPhi().

◆ getDebugValueLoc()

static DebugLoc getDebugValueLoc ( DbgVariableIntrinsic DII,
Instruction Src 
)
static

Produce a DebugLoc to use for each dbg.declare/inst pair that are promoted to a dbg.value.

Because no machine insts can come from debug intrinsics, only the scope and inlinedAt is significant. Zero line numbers are used in case this DebugLoc leaks into any adjacent instructions.

Definition at line 1430 of file Local.cpp.

References llvm::MDNode::get(), llvm::Value::getContext(), llvm::Instruction::getDebugLoc(), llvm::DebugLoc::getInlinedAt(), and llvm::DebugLoc::getScope().

Referenced by llvm::ConvertDebugDeclareToDebugValue(), and llvm::LowerDbgDeclare().

◆ getDwarfOpForBinOp()

uint64_t getDwarfOpForBinOp ( Instruction::BinaryOps  Opcode)

Definition at line 1828 of file Local.cpp.

References llvm::MCID::Add.

Referenced by getSalvageOpsForBinOp().

◆ getSalvageOpsForBinOp()

Value* getSalvageOpsForBinOp ( BinaryOperator BI,
uint64_t  CurrentLocOps,
SmallVectorImpl< uint64_t > &  Opcodes,
SmallVectorImpl< Value * > &  AdditionalValues 
)

◆ getSalvageOpsForGEP()

Value* getSalvageOpsForGEP ( GetElementPtrInst GEP,
const DataLayout DL,
uint64_t  CurrentLocOps,
SmallVectorImpl< uint64_t > &  Opcodes,
SmallVectorImpl< Value * > &  AdditionalValues 
)

◆ isArray()

static bool isArray ( AllocaInst AI)
static

Determine whether this alloca is either a VLA or an array.

Definition at line 1528 of file Local.cpp.

References llvm::AllocaInst::getAllocatedType(), llvm::AllocaInst::isArrayAllocation(), and llvm::Type::isArrayTy().

Referenced by llvm::LowerDbgDeclare().

◆ isBitCastSemanticsPreserving()

static bool isBitCastSemanticsPreserving ( const DataLayout DL,
Type FromTy,
Type ToTy 
)
static

Check if a bitcast between a value of type FromTy to type ToTy would losslessly preserve the bits and semantics of the value.

This predicate is symmetric, i.e swapping FromTy and ToTy should give the same result.

Note that Type::canLosslesslyBitCastTo is not suitable here because it allows semantically unequivalent bitcasts, such as <2 x i64> -> <4 x i32>, and also does not allow lossless pointer <-> integer conversions.

Definition at line 2004 of file Local.cpp.

References DL, and llvm::Type::isIntOrPtrTy().

Referenced by llvm::replaceAllDbgUsesWith().

◆ isStructure()

static bool isStructure ( AllocaInst AI)
static

Determine whether this alloca is a structure.

Definition at line 1534 of file Local.cpp.

References llvm::AllocaInst::getAllocatedType(), and llvm::Type::isStructTy().

Referenced by llvm::LowerDbgDeclare().

◆ markAliveBlocks()

static bool markAliveBlocks ( Function F,
SmallPtrSetImpl< BasicBlock * > &  Reachable,
DomTreeUpdater DTU = nullptr 
)
static

◆ PhiHasDebugValue()

static bool PhiHasDebugValue ( DILocalVariable DIVar,
DIExpression DIExpr,
PHINode APN 
)
static

===------------------------------------------------------------------—===// Dbg Intrinsic utilities

See if there is a dbg.value intrinsic for DIVar for the PHI node.

Definition at line 1373 of file Local.cpp.

References assert(), llvm::findDbgValues(), and llvm::is_contained().

Referenced by llvm::ConvertDebugDeclareToDebugValue().

◆ redirectValuesFromPredecessorsToPhi()

static void redirectValuesFromPredecessorsToPhi ( BasicBlock BB,
const PredBlockVector BBPreds,
PHINode PN 
)
static

Replace a value flowing from a block to a phi with potentially multiple instances of that value flowing from the block's predecessors to the phi.

Parameters
BBThe block with the value flowing into the phi.
BBPredsThe predecessors of BB.
PNThe phi that we are updating.

Definition at line 988 of file Local.cpp.

References llvm::PHINode::addIncoming(), assert(), BB, llvm::numbers::e, gatherIncomingValuesToPhi(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), getParent(), i, llvm::PHINode::removeIncomingValue(), replaceUndefValuesInPhi(), and selectIncomingValueForBlock().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ replaceDominatedUsesWith()

template<typename RootType , typename DominatesFn >
static unsigned replaceDominatedUsesWith ( Value From,
Value To,
const RootType &  Root,
const DominatesFn &  Dominates 
)
static

◆ replaceOneDbgValueForAlloca()

static void replaceOneDbgValueForAlloca ( DbgValueInst DVI,
Value NewAddress,
DIBuilder Builder,
int  Offset 
)
static

◆ replaceUndefValuesInPhi()

static void replaceUndefValuesInPhi ( PHINode PN,
const IncomingValueMap IncomingValues 
)
static

◆ rewriteDebugUsers()

static bool rewriteDebugUsers ( Instruction From,
Value To,
Instruction DomPoint,
DominatorTree DT,
function_ref< DbgValReplacement(DbgVariableIntrinsic &DII)>  RewriteExpr 
)
static

◆ selectIncomingValueForBlock()

static Value* selectIncomingValueForBlock ( Value OldVal,
BasicBlock BB,
IncomingValueMap IncomingValues 
)
static

Determines the value to use as the phi node input for a block.

Select between OldVal any value that we know flows from BB to a particular phi on the basis of which one (if either) is not undef. Update IncomingValues based on the selected value.

Parameters
OldValThe value we are considering selecting.
BBThe block that the value flows in from.
IncomingValuesA map from block-to-value for other phi inputs that we have examined.
Returns
the selected value.

Definition at line 903 of file Local.cpp.

References assert(), BB, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert().

Referenced by redirectValuesFromPredecessorsToPhi().

◆ simplifyAndDCEInstruction()

static bool simplifyAndDCEInstruction ( Instruction I,
SmallSetVector< Instruction *, 16 > &  WorkList,
const DataLayout DL,
const TargetLibraryInfo TLI 
)
static

◆ STATISTIC() [1/2]

STATISTIC ( NumPHICSEs  ,
"Number of PHI's that got CSE'd  
)

◆ STATISTIC() [2/2]

STATISTIC ( NumRemoved  ,
"Number of unreachable basic blocks removed  
)

◆ tryEnforceAlignment()

static Align tryEnforceAlignment ( Value V,
Align  PrefAlign,
const DataLayout DL 
)
static

If the specified pointer points to an object that we control, try to modify the object's alignment to PrefAlign.

Returns a minimum known alignment of the value after the operation, which may be lower than PrefAlign.

Increating value alignment isn't often possible though. If alignment is important, a more reliable approach is to simply align all global variables and allocation instructions to their preferred alignment from the beginning.

Definition at line 1301 of file Local.cpp.

References Align, DL, and llvm::Value::stripPointerCasts().

Referenced by llvm::getOrEnforceKnownAlignment().

◆ valueCoversEntireFragment()

static bool valueCoversEntireFragment ( Type ValTy,
DbgVariableIntrinsic DII 
)
static

Check if the alloc size of ValTy is large enough to cover the variable (or fragment of the variable) described by DII.

This is primarily intended as a helper for the different ConvertDebugDeclareToDebugValue functions. The dbg.declare/dbg.addr that is converted describes an alloca'd variable, so we need to use the alloc size of the value when doing the comparison. E.g. an i1 value will be identified as covering an n-bit fragment, if the store size of i1 is at least n bits.

Definition at line 1398 of file Local.cpp.

References assert(), DL, llvm::Module::getDataLayout(), llvm::TypeSize::getFixedSize(), llvm::DbgVariableIntrinsic::getFragmentSizeInBits(), llvm::Instruction::getModule(), llvm::DbgVariableIntrinsic::getNumVariableLocationOps(), llvm::DbgVariableIntrinsic::getVariableLocationOp(), llvm::DbgVariableIntrinsic::isAddressOfVariable(), llvm::LinearPolySize< TypeSize >::isKnownGE(), and llvm::LinearPolySize< LeafTy >::isScalable().

Referenced by llvm::ConvertDebugDeclareToDebugValue().

Variable Documentation

◆ BitPartRecursionMaxDepth

const unsigned BitPartRecursionMaxDepth = 48
static

Definition at line 115 of file Local.cpp.

Referenced by collectBitParts().

◆ PHICSEDebugHash

cl::opt<bool> PHICSEDebugHash("phicse-debug-hash", cl::init(false), cl::Hidden, cl::desc("Perform extra assertion checking to verify that PHINodes's hash " "function is well-behaved w.r.t. its isEqual predicate"))
static

◆ PHICSENumPHISmallSize

cl::opt<unsigned> PHICSENumPHISmallSize("phicse-num-phi-smallsize", cl::init(32), cl::Hidden, cl::desc( "When the basic block contains not more than this number of PHI nodes, " "perform a (faster!) exhaustive search instead of set-driven one."))
static