#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/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/InstructionSimplify.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/DebugInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/EHPersonalities.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/IntrinsicsWebAssembly.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/MemoryModelRelaxationAnnotations.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/ProfDataUtils.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/CommandLine.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 <cstdint>
#include <iterator>
#include <map>
#include <optional>
#include <utility>

Macros
#define	DEBUG_TYPE "local"

Typedefs
using	PredBlockVector = SmallVector< BasicBlock *, 16 >

using	IncomingValueMap = SmallDenseMap< BasicBlock , Value , 16 >

using	DbgValReplacement = std::optional< DIExpression * >
	A replacement for a dbg.value expression.

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.

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.

static bool	CanPropagatePredecessorsForPHIs (BasicBlock BB, BasicBlock Succ, const SmallPtrSetImpl< BasicBlock * > &BBPreds)
	Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ, into Succ.

static Value *	selectIncomingValueForBlock (Value OldVal, BasicBlock BB, IncomingValueMap &IncomingValues)
	Determines the value to use as the phi node input for a block.

static void	gatherIncomingValuesToPhi (PHINode *PN, IncomingValueMap &IncomingValues)
	Create a map from block to value for the operands of a given phi.

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.

static bool	CanRedirectPredsOfEmptyBBToSucc (BasicBlock BB, BasicBlock Succ, const SmallPtrSetImpl< BasicBlock * > &BBPreds, BasicBlock *&CommonPred)

static bool	introduceTooManyPhiEntries (BasicBlock BB, BasicBlock Succ)
	Check whether removing `BB` will make the phis in its `Succ` have too many incoming entries.

static void	redirectValuesFromPredecessorsToPhi (BasicBlock BB, const PredBlockVector &BBPreds, PHINode PN, BasicBlock *CommonPred)
	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.

static bool	EliminateDuplicatePHINodesNaiveImpl (BasicBlock BB, SmallPtrSetImpl< PHINode > &ToRemove)

static bool	EliminateDuplicatePHINodesSetBasedImpl (BasicBlock BB, SmallPtrSetImpl< PHINode > &ToRemove)

static bool	PhiHasDebugValue (DILocalVariable DIVar, DIExpression DIExpr, PHINode *APN)
	===------------------------------------------------------------------—===// Dbg Intrinsic utilities

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

static bool	valueCoversEntireFragment (Type ValTy, DbgVariableRecord DVR)

static void	insertDbgValueOrDbgVariableRecord (DIBuilder &Builder, Value DV, DILocalVariable DIVar, DIExpression *DIExpr, const DebugLoc &NewLoc, BasicBlock::iterator Instr)

static void	insertDbgValueOrDbgVariableRecordAfter (DIBuilder &Builder, Value DV, DILocalVariable DIVar, DIExpression *DIExpr, const DebugLoc &NewLoc, BasicBlock::iterator Instr)

static DIExpression *	dropInitialDeref (const DIExpression *DIExpr)

static bool	isArray (AllocaInst *AI)
	Determine whether this alloca is either a VLA or an array.

static bool	isStructure (AllocaInst *AI)
	Determine whether this alloca is a structure.

static void	insertDbgVariableRecordsForPHIs (BasicBlock BB, SmallVectorImpl< PHINode > &InsertedPHIs)

static void	updateOneDbgValueForAlloca (const DebugLoc &Loc, DILocalVariable DIVar, DIExpression DIExpr, Value NewAddress, DbgValueInst DVI, DbgVariableRecord *DVR, DIBuilder &Builder, int Offset)

template<typename T >
static void	salvageDbgAssignAddress (T *Assign)

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

uint64_t	getDwarfOpForBinOp (Instruction::BinaryOps Opcode)

static void	handleSSAValueOperands (uint64_t CurrentLocOps, SmallVectorImpl< uint64_t > &Opcodes, SmallVectorImpl< Value * > &AdditionalValues, Instruction *I)

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

uint64_t	getDwarfOpForIcmpPred (CmpInst::Predicate Pred)

Value *	getSalvageOpsForIcmpOp (ICmpInst Icmp, 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, function_ref< DbgValReplacement(DbgVariableRecord &DVR)> RewriteDVRExpr)
	Point debug users of `From` to `To` using exprs given by `RewriteExpr`, possibly moving/undefing users to prevent use-before-def.

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.

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

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

static const std::optional< BitPart > &	collectBitParts (Value V, bool MatchBSwaps, bool MatchBitReversals, std::map< Value , std::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.

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

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

Variables
cl::opt< bool >	UseNewDbgInfoFormat

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 cl::opt< unsigned >	MaxPhiEntriesIncreaseAfterRemovingEmptyBlock ("max-phi-entries-increase-after-removing-empty-block", cl::init(1000), cl::Hidden, cl::desc("Stop removing an empty block if removing it will introduce more " "than this number of phi entries in its successor"))

static const unsigned	BitPartRecursionMaxDepth = 48

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "local"

Definition at line 93 of file Local.cpp.

Typedef Documentation

◆ DbgValReplacement

using DbgValReplacement = std::optional<DIExpression *>

A replacement for a dbg.value expression.

Definition at line 2663 of file Local.cpp.

◆ IncomingValueMap

using IncomingValueMap = SmallDenseMap<BasicBlock *, Value *, 16>

Definition at line 928 of file Local.cpp.

◆ PredBlockVector

using PredBlockVector = SmallVector<BasicBlock *, 16>

Definition at line 927 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 638 of file Local.cpp.

References I.

Referenced by llvm::RecursivelyDeleteDeadPHINode().

◆ bitTransformIsCorrectForBitReverse()

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

static

Definition at line 4089 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 4078 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 862 of file Local.cpp.

References llvm::First.

Referenced by CanPropagatePredecessorsForPHIs().

◆ CanPropagatePredecessorsForPHIs()

static bool CanPropagatePredecessorsForPHIs	(	BasicBlock *	BB,
		BasicBlock *	Succ,
		const SmallPtrSetImpl< BasicBlock * > &	BBPreds
	)

static

Return true if we can fold BB, an almost-empty BB ending in an unconditional branch to Succ, into Succ.

Assumption: Succ is the single successor for BB.

Definition at line 871 of file Local.cpp.

References assert(), llvm::BasicBlock::begin(), CanMergeValues(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::BasicBlock::getSinglePredecessor(), I, LLVM_DEBUG, and llvm::succ_begin().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ CanRedirectPredsOfEmptyBBToSucc()

static bool CanRedirectPredsOfEmptyBBToSucc	(	BasicBlock *	BB,
		BasicBlock *	Succ,
		const SmallPtrSetImpl< BasicBlock * > &	BBPreds,
		BasicBlock *&	CommonPred
	)

static

Definition at line 1024 of file Local.cpp.

References llvm::any_of(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::BasicBlock::getTerminator(), llvm::BasicBlock::hasNPredecessorsOrMore(), llvm::BasicBlock::phis(), and llvm::predecessors().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ collectBitParts()

static const std::optional< BitPart > & collectBitParts	(	Value *	V,
		bool	MatchBSwaps,
		bool	MatchBitReversals,
		std::map< Value *, std::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 3858 of file Local.cpp.

Referenced by collectBitParts(), and llvm::recognizeBSwapOrBitReverseIdiom().

◆ dropInitialDeref()

static DIExpression * dropInitialDeref ( const DIExpression * DIExpr )

static

Definition at line 1771 of file Local.cpp.

References llvm::ArrayRef< T >::drop_front(), llvm::dwarf::DW_OP_LLVM_arg, llvm::MDNode::getContext(), and llvm::DIExpression::getElements().

Referenced by llvm::InsertDebugValueAtStoreLoc().

◆ EliminateDuplicatePHINodesNaiveImpl()

static bool EliminateDuplicatePHINodesNaiveImpl	(	BasicBlock *	BB,
		SmallPtrSetImpl< PHINode * > &	ToRemove
	)

static

Definition at line 1389 of file Local.cpp.

References llvm::BasicBlock::begin(), I, llvm::Instruction::isIdenticalToWhenDefined(), llvm::Value::replaceAllUsesWith(), and ToRemove.

Referenced by llvm::EliminateDuplicatePHINodes().

◆ EliminateDuplicatePHINodesSetBasedImpl()

static bool EliminateDuplicatePHINodesSetBasedImpl	(	BasicBlock *	BB,
		SmallPtrSetImpl< PHINode * > &	ToRemove
	)

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

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

Definition at line 967 of file Local.cpp.

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

Referenced by redirectValuesFromPredecessorsToPhi().

◆ getDwarfOpForBinOp()

uint64_t getDwarfOpForBinOp ( Instruction::BinaryOps Opcode )

Definition at line 2484 of file Local.cpp.

Referenced by getSalvageOpsForBinOp().

◆ getDwarfOpForIcmpPred()

uint64_t getDwarfOpForIcmpPred ( CmpInst::Predicate Pred )

Definition at line 2560 of file Local.cpp.

References llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLE, llvm::CmpInst::ICMP_SLT, llvm::CmpInst::ICMP_UGE, llvm::CmpInst::ICMP_UGT, llvm::CmpInst::ICMP_ULE, and llvm::CmpInst::ICMP_ULT.

Referenced by getSalvageOpsForIcmpOp().

◆ getSalvageOpsForBinOp()

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

Definition at line 2526 of file Local.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::DIExpression::appendOffset(), getDwarfOpForBinOp(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), handleSSAValueOperands(), llvm::Offset, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::salvageDebugInfoImpl().

◆ getSalvageOpsForGEP()

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

Definition at line 2458 of file Local.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::DIExpression::appendOffset(), assert(), llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::BitWidth, DL, llvm::dwarf::DW_OP_LLVM_arg, llvm::MapVector< KeyT, ValueT, MapType, VectorType >::empty(), GEP, llvm::APInt::getSExtValue(), llvm::SmallVectorImpl< T >::insert(), llvm::Offset, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::salvageDebugInfoImpl().

◆ getSalvageOpsForIcmpOp()

Value * getSalvageOpsForIcmpOp	(	ICmpInst *	Icmp,
		uint64_t	CurrentLocOps,
		SmallVectorImpl< uint64_t > &	Opcodes,
		SmallVectorImpl< Value * > &	AdditionalValues
	)

Definition at line 2585 of file Local.cpp.

References getDwarfOpForIcmpPred(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), handleSSAValueOperands(), llvm::CmpInst::isSigned(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::salvageDebugInfoImpl().

◆ handleSSAValueOperands()

static void handleSSAValueOperands	(	uint64_t	CurrentLocOps,
		SmallVectorImpl< uint64_t > &	Opcodes,
		SmallVectorImpl< Value * > &	AdditionalValues,
		Instruction *	I
	)

static

Definition at line 2514 of file Local.cpp.

References llvm::SmallVectorImpl< T >::append(), llvm::dwarf::DW_OP_LLVM_arg, I, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by getSalvageOpsForBinOp(), and getSalvageOpsForIcmpOp().

◆ insertDbgValueOrDbgVariableRecord()

static void insertDbgValueOrDbgVariableRecord	(	DIBuilder &	Builder,
		Value *	DV,
		DILocalVariable *	DIVar,
		DIExpression *	DIExpr,
		const DebugLoc &	NewLoc,
		BasicBlock::iterator	Instr
	)

static

Definition at line 1690 of file Local.cpp.

References llvm::DebugLoc::get(), llvm::ValueAsMetadata::get(), and UseNewDbgInfoFormat.

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

◆ insertDbgValueOrDbgVariableRecordAfter()

static void insertDbgValueOrDbgVariableRecordAfter	(	DIBuilder &	Builder,
		Value *	DV,
		DILocalVariable *	DIVar,
		DIExpression *	DIExpr,
		const DebugLoc &	NewLoc,
		BasicBlock::iterator	Instr
	)

static

Definition at line 1709 of file Local.cpp.

References llvm::DebugLoc::get(), llvm::ValueAsMetadata::get(), and UseNewDbgInfoFormat.

Referenced by llvm::ConvertDebugDeclareToDebugValue().

◆ insertDbgVariableRecordsForPHIs()

static void insertDbgVariableRecordsForPHIs	(	BasicBlock *	BB,
		SmallVectorImpl< PHINode * > &	InsertedPHIs
	)

static

Definition at line 2075 of file Local.cpp.

References assert(), llvm::DbgVariableRecord::clone(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::end(), llvm::BasicBlock::end(), llvm::filterDbgVars(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::find(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BasicBlock::getFirstNonPHI(), I, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::MapVector< KeyT, ValueT, MapType, VectorType >::insert(), llvm::BasicBlock::insertDbgRecordBefore(), llvm::is_contained(), llvm::Instruction::isEHPad(), llvm::DbgVariableRecord::location_ops(), PHI, llvm::DbgVariableRecord::replaceVariableLocationOp(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size(), and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::insertDebugValuesForPHIs().

◆ introduceTooManyPhiEntries()

static bool introduceTooManyPhiEntries	(	BasicBlock *	BB,
		BasicBlock *	Succ
	)

static

Check whether removing BB will make the phis in its Succ have too many incoming entries.

This function does not check whether BB is foldable or not.

Definition at line 1057 of file Local.cpp.

References llvm::BasicBlock::hasNPredecessors(), MaxPhiEntriesIncreaseAfterRemovingEmptyBlock, llvm::BasicBlock::phis(), and llvm::pred_size().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ isArray()

static bool isArray ( AllocaInst * AI )

static

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

Definition at line 1944 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 2766 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 1950 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

Definition at line 3035 of file Local.cpp.

References llvm::canSimplifyInvokeNoUnwind(), llvm::changeToCall(), llvm::changeToUnreachable(), llvm::ConstantFoldTerminator(), llvm::BranchInst::Create(), llvm::BasicBlock::Create(), llvm::SmallVectorBase< Size_T >::empty(), F, llvm::BasicBlock::getFirstNonPHI(), llvm::Value::getName(), llvm::hash_combine_range(), I, II, llvm::SmallPtrSetImpl< PtrType >::insert(), isEqual(), LHS, llvm::PatternMatch::m_CombineOr(), llvm::PatternMatch::m_Undef(), llvm::PatternMatch::m_Zero(), llvm::PatternMatch::match(), llvm::NullPointerIsDefined(), llvm::SmallVectorImpl< T >::pop_back_val(), Ptr, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BasicBlock::removePredecessor(), RHS, llvm::Successor, llvm::successors(), llvm::User::value_op_begin(), and llvm::User::value_op_end().

Referenced by llvm::removeUnreachableBlocks().

◆ 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 1608 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,
		BasicBlock *	CommonPred
	)

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

BB	The block with the value flowing into the phi.
BBPreds	The predecessors of BB.
PN	The phi that we are updating.
CommonPred	The common predecessor of BB and PN's BasicBlock

Definition at line 1089 of file Local.cpp.

References llvm::PHINode::addIncoming(), assert(), gatherIncomingValuesToPhi(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::PHINode::getNumIncomingValues(), getParent(), llvm::PHINode::removeIncomingValue(), replaceUndefValuesInPhi(), and selectIncomingValueForBlock().

Referenced by llvm::TryToSimplifyUncondBranchFromEmptyBlock().

◆ replaceDominatedUsesWith()

template<typename RootType , typename ShouldReplaceFn >

static unsigned replaceDominatedUsesWith	(	Value *	From,
		Value *	To,
		const RootType &	Root,
		const ShouldReplaceFn &	ShouldReplace
	)

static

Definition at line 3542 of file Local.cpp.

References assert(), llvm::dbgs(), From, llvm::Value::getType(), II, LLVM_DEBUG, and llvm::make_early_inc_range().

◆ replaceUndefValuesInPhi()

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

static

Replace the incoming undef values to a phi with the values from a block-to-value map.

Parameters

PN	The phi we are replacing the undefs in.
IncomingValues	A map from block to value.

Definition at line 983 of file Local.cpp.

References llvm::count_if(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::UndefValue::get(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getNumIncomingValues(), llvm::Value::getType(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::PHINode::setIncomingValue(), and llvm::SmallVectorBase< Size_T >::size().

Referenced by redirectValuesFromPredecessorsToPhi().

◆ rewriteDebugUsers()

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

static

Point debug users of From to To using exprs given by RewriteExpr, possibly moving/undefing users to prevent use-before-def.

Returns true if changes are made.

Definition at line 2668 of file Local.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::DominatorTree::dominates(), llvm::SmallPtrSetImplBase::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::findDbgUsers(), From, llvm::DbgRecord::getMarker(), llvm::Instruction::getNextNonDebugInstruction(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::SmallPtrSetImpl< PtrType >::insert(), LLVM_DEBUG, llvm::DbgMarker::MarkedInstr, llvm::Instruction::moveAfter(), llvm::DbgRecord::removeFromParent(), llvm::DbgVariableRecord::replaceVariableLocationOp(), llvm::DbgVariableIntrinsic::replaceVariableLocationOp(), llvm::salvageDebugInfo(), llvm::DbgVariableRecord::setExpression(), llvm::DbgVariableIntrinsic::setExpression(), and Users.

Referenced by llvm::replaceAllDbgUsesWith().

◆ salvageDbgAssignAddress()

template<typename T >

static void salvageDbgAssignAddress ( T * Assign )

static

Definition at line 2278 of file Local.cpp.

References llvm::DIExpression::appendOpsToArg(), assert(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DIExpression::foldConstantMath(), llvm::DIExpression::getFragmentInfo(), I, and llvm::salvageDebugInfoImpl().

Referenced by llvm::salvageDebugInfoForDbgValues().

◆ 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

OldVal	The value we are considering selecting.
BB	The block that the value flows in from.
IncomingValues	A map from block-to-value for other phi inputs that we have examined.

Returns: the selected value.

Definition at line 942 of file Local.cpp.

References assert(), 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

Definition at line 679 of file Local.cpp.

References DL, I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::isInstructionTriviallyDead(), llvm::salvageDebugInfo(), llvm::simplifyInstruction(), and llvm::Value::use_empty().

Referenced by llvm::SimplifyInstructionsInBlock().

◆ STATISTIC() [1/2]

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

◆ STATISTIC() [2/2]

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

◆ updateOneDbgValueForAlloca()

static void updateOneDbgValueForAlloca	(	const DebugLoc &	Loc,
		DILocalVariable *	DIVar,
		DIExpression *	DIExpr,
		Value *	NewAddress,
		DbgValueInst *	DVI,
		DbgVariableRecord *	DVR,
		DIBuilder &	Builder,
		int	Offset
	)

static

Definition at line 2221 of file Local.cpp.

References assert(), llvm::DIExpression::getElement(), llvm::DIExpression::getNumElements(), llvm::Offset, llvm::DIExpression::prepend(), llvm::DbgVariableRecord::replaceVariableLocationOp(), llvm::DbgVariableIntrinsic::replaceVariableLocationOp(), llvm::DbgVariableRecord::setExpression(), and llvm::DbgVariableIntrinsic::setExpression().

Referenced by llvm::replaceDbgValueForAlloca().

◆ valueCoversEntireFragment() [1/2]

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 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 1638 of file Local.cpp.

References assert(), DL, llvm::DIExpression::getActiveBits(), llvm::Instruction::getDataLayout(), llvm::DbgVariableIntrinsic::getExpression(), llvm::TypeSize::getFixed(), llvm::DbgVariableIntrinsic::getNumVariableLocationOps(), llvm::DbgVariableIntrinsic::getVariable(), llvm::DbgVariableIntrinsic::getVariableLocationOp(), and llvm::DbgVariableIntrinsic::isAddressOfVariable().

Referenced by llvm::ConvertDebugDeclareToDebugValue().

◆ valueCoversEntireFragment() [2/2]

static bool valueCoversEntireFragment	(	Type *	ValTy,
		DbgVariableRecord *	DVR
	)

static

Definition at line 1665 of file Local.cpp.

References assert(), DL, llvm::DIExpression::getActiveBits(), llvm::Module::getDataLayout(), llvm::DbgVariableRecord::getExpression(), llvm::TypeSize::getFixed(), llvm::DbgRecord::getModule(), llvm::DbgVariableRecord::getNumVariableLocationOps(), llvm::DbgVariableRecord::getVariable(), llvm::DbgVariableRecord::getVariableLocationOp(), and llvm::DbgVariableRecord::isAddressOfVariable().

Variable Documentation

◆ BitPartRecursionMaxDepth

const unsigned BitPartRecursionMaxDepth = 48

static

Definition at line 123 of file Local.cpp.

Referenced by collectBitParts().

◆ MaxPhiEntriesIncreaseAfterRemovingEmptyBlock

cl::opt< unsigned > MaxPhiEntriesIncreaseAfterRemovingEmptyBlock("max-phi-entries-increase-after-removing-empty-block", cl::init(1000), cl::Hidden, cl::desc("Stop removing an empty block if removing it will introduce more " "than this number of phi entries in its successor"))	(	"max-phi-entries-increase-after-removing-empty-block"	,
		cl::init(1000)	,
		cl::Hidden	,
		cl::desc("Stop removing an empty block if removing it will introduce more " "than this number of phi entries in its successor")
	)

static

Referenced by introduceTooManyPhiEntries().

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

Referenced by llvm::EliminateDuplicatePHINodes(), and EliminateDuplicatePHINodesSetBasedImpl().

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

Referenced by llvm::EliminateDuplicatePHINodes(), and EliminateDuplicatePHINodesSetBasedImpl().

◆ UseNewDbgInfoFormat

cl::opt<bool> UseNewDbgInfoFormat

extern

Referenced by llvm::ConvertDebugDeclareToDebugValue(), insertDbgValueOrDbgVariableRecord(), and insertDbgValueOrDbgVariableRecordAfter().

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ DbgValReplacement

◆ IncomingValueMap

◆ PredBlockVector

Function Documentation

◆ areAllUsesEqual()

◆ bitTransformIsCorrectForBitReverse()

◆ bitTransformIsCorrectForBSwap()

◆ CanMergeValues()

◆ CanPropagatePredecessorsForPHIs()

◆ CanRedirectPredsOfEmptyBBToSucc()

◆ collectBitParts()

◆ dropInitialDeref()

◆ EliminateDuplicatePHINodesNaiveImpl()

◆ EliminateDuplicatePHINodesSetBasedImpl()

◆ gatherIncomingValuesToPhi()

◆ getDwarfOpForBinOp()

◆ getDwarfOpForIcmpPred()

◆ getSalvageOpsForBinOp()

◆ getSalvageOpsForGEP()

◆ getSalvageOpsForIcmpOp()

◆ handleSSAValueOperands()

◆ insertDbgValueOrDbgVariableRecord()

◆ insertDbgValueOrDbgVariableRecordAfter()

◆ insertDbgVariableRecordsForPHIs()

◆ introduceTooManyPhiEntries()

◆ isArray()

◆ isBitCastSemanticsPreserving()

◆ isStructure()

◆ markAliveBlocks()

◆ PhiHasDebugValue()

◆ redirectValuesFromPredecessorsToPhi()

◆ replaceDominatedUsesWith()

◆ replaceUndefValuesInPhi()

◆ rewriteDebugUsers()

◆ salvageDbgAssignAddress()

◆ selectIncomingValueForBlock()

◆ simplifyAndDCEInstruction()

◆ STATISTIC() [1/2]

◆ STATISTIC() [2/2]

◆ updateOneDbgValueForAlloca()

◆ valueCoversEntireFragment() [1/2]

◆ valueCoversEntireFragment() [2/2]

Variable Documentation

◆ BitPartRecursionMaxDepth

◆ MaxPhiEntriesIncreaseAfterRemovingEmptyBlock

◆ PHICSEDebugHash

◆ PHICSENumPHISmallSize

◆ UseNewDbgInfoFormat