#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Type.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/raw_ostream.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <cstdint>
#include <string>
#include <utility>
#include <vector>

Macros
#define	DEBUG_TYPE "basicblock-utils"

Functions
static bool	DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan (BasicBlock *BB)
	Remove redundant instructions within sequences of consecutive dbg.value instructions.

static bool	removeRedundantDbgInstrsUsingBackwardScan (BasicBlock *BB)

static bool	DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan (BasicBlock *BB)
	Remove redundant dbg.value instructions using a forward scan.

static bool	DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock (BasicBlock *BB)

static bool	removeRedundantDbgInstrsUsingForwardScan (BasicBlock *BB)

static bool	removeUndefDbgAssignsFromEntryBlock (BasicBlock *BB)
	Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.

static BasicBlock *	SplitBlockImpl (BasicBlock Old, BasicBlock::iterator SplitPt, DomTreeUpdater DTU, DominatorTree DT, LoopInfo LI, MemorySSAUpdater *MSSAU, const Twine &BBName, bool Before)

static void	UpdateAnalysisInformation (BasicBlock OldBB, BasicBlock NewBB, ArrayRef< BasicBlock * > Preds, DomTreeUpdater DTU, DominatorTree DT, LoopInfo LI, MemorySSAUpdater MSSAU, bool PreserveLCSSA, bool &HasLoopExit)
	Update DominatorTree, LoopInfo, and LCCSA analysis information.

static void	UpdatePHINodes (BasicBlock OrigBB, BasicBlock NewBB, ArrayRef< BasicBlock * > Preds, BranchInst *BI, bool HasLoopExit)
	Update the PHI nodes in OrigBB to include the values coming from NewBB.

static void	SplitLandingPadPredecessorsImpl (BasicBlock OrigBB, ArrayRef< BasicBlock > Preds, const char Suffix1, const char Suffix2, SmallVectorImpl< BasicBlock * > &NewBBs, DomTreeUpdater DTU, DominatorTree DT, LoopInfo LI, MemorySSAUpdater MSSAU, bool PreserveLCSSA)

static BasicBlock *	SplitBlockPredecessorsImpl (BasicBlock BB, ArrayRef< BasicBlock > Preds, const char Suffix, DomTreeUpdater DTU, DominatorTree DT, LoopInfo LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)

Variables
static cl::opt< unsigned >	MaxDeoptOrUnreachableSuccessorCheckDepth ("max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable"))

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "basicblock-utils"

Definition at line 54 of file BasicBlockUtils.cpp.

Function Documentation

◆ DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan()

static bool DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan ( BasicBlock * BB )

static

Remove redundant instructions within sequences of consecutive dbg.value instructions.

This is done using a backward scan to keep the last dbg.value describing a specific variable/fragment.

BackwardScan strategy:

Given a sequence of consecutive DbgValueInst like this

dbg.value ..., "x", FragmentX1 (*) dbg.value ..., "y", FragmentY1 dbg.value ..., "x", FragmentX2 dbg.value ..., "x", FragmentX1 (**)

then the instruction marked with (*) can be removed (it is guaranteed to be obsoleted by the instruction marked with (**) as the latter instruction is describing the same variable using the same fragment info).

Possible improvements:

Check fully overlapping fragments and not only identical fragments.
Support dbg.declare. dbg.label, and possibly other meta instructions being part of the sequence of consecutive instructions.

Definition at line 386 of file BasicBlockUtils.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::SmallVectorBase< Size_T >::empty(), llvm::at::getAssignmentInsts(), llvm::DbgRecord::getDebugLoc(), llvm::DbgVariableRecord::getExpression(), llvm::DbgVariableRecord::getType(), llvm::DbgVariableRecord::getVariable(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::DbgVariableRecord::isDbgAssign(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by removeRedundantDbgInstrsUsingBackwardScan().

◆ DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan()

static bool DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan ( BasicBlock * BB )

static

Remove redundant dbg.value instructions using a forward scan.

This can remove a dbg.value instruction that is redundant due to indicating that a variable has the same value as already being indicated by an earlier dbg.value.

ForwardScan strategy:

Given two identical dbg.value instructions, separated by a block of instructions that isn't describing the same variable, like this

dbg.value X1, "x", FragmentX1 (**) <block of instructions, none being "dbg.value ..., "x", ..."> dbg.value X1, "x", FragmentX1 (*)

then the instruction marked with (*) can be removed. Variable "x" is already described as being mapped to the SSA value X1.

Possible improvements:

Keep track of non-overlapping fragments.

Definition at line 503 of file BasicBlockUtils.cpp.

References llvm::iterator_range< IteratorT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::filterDbgVars(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::at::getAssignmentInsts(), I, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by removeRedundantDbgInstrsUsingForwardScan().

◆ DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock()

static bool DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock ( BasicBlock * BB )

static

Definition at line 546 of file BasicBlockUtils.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::iterator_range< IteratorT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::filterDbgVars(), llvm::at::getAssignmentInsts(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::BasicBlock::isEntryBlock(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by removeUndefDbgAssignsFromEntryBlock().

◆ removeRedundantDbgInstrsUsingBackwardScan()

static bool removeRedundantDbgInstrsUsingBackwardScan ( BasicBlock * BB )

static

Definition at line 441 of file BasicBlockUtils.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan(), llvm::SmallVectorBase< Size_T >::empty(), llvm::at::getAssignmentInsts(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::BasicBlock::IsNewDbgInfoFormat, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by llvm::RemoveRedundantDbgInstrs().

◆ removeRedundantDbgInstrsUsingForwardScan()

static bool removeRedundantDbgInstrsUsingForwardScan ( BasicBlock * BB )

static

Definition at line 582 of file BasicBlockUtils.cpp.

References DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan(), llvm::iterator_range< IteratorT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::at::getAssignmentInsts(), I, llvm::BasicBlock::IsNewDbgInfoFormat, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::RemoveRedundantDbgInstrs().

◆ removeUndefDbgAssignsFromEntryBlock()

static bool removeUndefDbgAssignsFromEntryBlock ( BasicBlock * BB )

static

Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.

Strategy:

Scanning forward, delete dbg.assign intrinsics iff they are undef, not linked to an intrinsic, and don't share an aggregate variable with a debug intrinsic that didn't meet the criteria. In other words, undef dbg.assigns that come before non-undef debug intrinsics for the variable are deleted. Given:

dbg.assign undef, "x", FragmentX1 (*) <block of instructions, none being "dbg.value ..., "x", ..."> dbg.value V, "x", FragmentX2 <block of instructions, none being "dbg.value ..., "x", ..."> dbg.assign undef, "x", FragmentX1

then (only) the instruction marked with (*) can be removed. Possible improvements:

Keep track of non-overlapping fragments.

Definition at line 647 of file BasicBlockUtils.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock(), llvm::iterator_range< IteratorT >::empty(), llvm::SmallVectorBase< Size_T >::empty(), llvm::at::getAssignmentInsts(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::BasicBlock::isEntryBlock(), llvm::DbgVariableIntrinsic::isKillLocation(), llvm::BasicBlock::IsNewDbgInfoFormat, and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by llvm::RemoveRedundantDbgInstrs().

◆ SplitBlockImpl()

static BasicBlock * SplitBlockImpl	(	BasicBlock *	Old,
		BasicBlock::iterator	SplitPt,
		DomTreeUpdater *	DTU,
		DominatorTree *	DT,
		LoopInfo *	LI,
		MemorySSAUpdater *	MSSAU,
		const Twine &	BBName,
		bool	Before
	)

static

◆ SplitBlockPredecessorsImpl()

static BasicBlock * SplitBlockPredecessorsImpl	(	BasicBlock *	BB,
		ArrayRef< BasicBlock * >	Preds,
		const char *	Suffix,
		DomTreeUpdater *	DTU,
		DominatorTree *	DT,
		LoopInfo *	LI,
		MemorySSAUpdater *	MSSAU,
		bool	PreserveLCSSA
	)

static

Definition at line 1330 of file BasicBlockUtils.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::BasicBlock::canSplitPredecessors(), llvm::BranchInst::Create(), llvm::BasicBlock::Create(), llvm::ArrayRef< T >::empty(), llvm::PoisonValue::get(), llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getMetadata(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), I, llvm::BasicBlock::isLandingPad(), llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), SplitLandingPadPredecessorsImpl(), UpdateAnalysisInformation(), and UpdatePHINodes().

Referenced by llvm::SplitBlockPredecessors().

◆ SplitLandingPadPredecessorsImpl()

static void SplitLandingPadPredecessorsImpl	(	BasicBlock *	OrigBB,
		ArrayRef< BasicBlock * >	Preds,
		const char *	Suffix1,
		const char *	Suffix2,
		SmallVectorImpl< BasicBlock * > &	NewBBs,
		DomTreeUpdater *	DTU,
		DominatorTree *	DT,
		LoopInfo *	LI,
		MemorySSAUpdater *	MSSAU,
		bool	PreserveLCSSA
	)

static

Definition at line 1437 of file BasicBlockUtils.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::Instruction::clone(), llvm::BranchInst::Create(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::SmallVectorBase< Size_T >::empty(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BasicBlock::getFirstNonPHI(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getLandingPadInst(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), llvm::Instruction::insertInto(), llvm::BasicBlock::isLandingPad(), llvm::Type::isTokenTy(), llvm::pred_begin(), llvm::pred_end(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::Value::setName(), UpdateAnalysisInformation(), UpdatePHINodes(), and llvm::Value::use_empty().

Referenced by SplitBlockPredecessorsImpl(), and llvm::SplitLandingPadPredecessors().

◆ UpdateAnalysisInformation()

static void UpdateAnalysisInformation	(	BasicBlock *	OldBB,
		BasicBlock *	NewBB,
		ArrayRef< BasicBlock * >	Preds,
		DomTreeUpdater *	DTU,
		DominatorTree *	DT,
		LoopInfo *	LI,
		MemorySSAUpdater *	MSSAU,
		bool	PreserveLCSSA,
		bool &	HasLoopExit
	)

static

Update DominatorTree, LoopInfo, and LCCSA analysis information.

Invalidates DFS Numbering when DTU or DT is provided.

Definition at line 1146 of file BasicBlockUtils.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdates(), assert(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::getDomTree(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getParent(), llvm::LoopBase< BlockT, LoopT >::getParentLoop(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::hasDomTree(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BasicBlock::isEntryBlock(), llvm::DominatorTree::isReachableFromEntry(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::recalculate(), llvm::SmallVectorImpl< T >::reserve(), llvm::DominatorTreeBase< NodeT, IsPostDom >::setNewRoot(), llvm::ArrayRef< T >::size(), llvm::SmallVectorBase< Size_T >::size(), llvm::DominatorTreeBase< NodeT, IsPostDom >::splitBlock(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().

Referenced by SplitBlockPredecessorsImpl(), and SplitLandingPadPredecessorsImpl().

◆ UpdatePHINodes()

static void UpdatePHINodes	(	BasicBlock *	OrigBB,
		BasicBlock *	NewBB,
		ArrayRef< BasicBlock * >	Preds,
		BranchInst *	BI,
		bool	HasLoopExit
	)

static

Update the PHI nodes in OrigBB to include the values coming from NewBB.

This also updates AliasAnalysis, if available.

Definition at line 1260 of file BasicBlockUtils.cpp.

References llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), llvm::ArrayRef< T >::begin(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::PHINode::Create(), llvm::ArrayRef< T >::end(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Value::getType(), I, Idx, llvm::PHINode::removeIncomingValue(), llvm::PHINode::removeIncomingValueIf(), and llvm::ArrayRef< T >::size().

Referenced by HandleInlinedEHPad(), SplitBlockPredecessorsImpl(), and SplitLandingPadPredecessorsImpl().

Variable Documentation

◆ MaxDeoptOrUnreachableSuccessorCheckDepth

cl::opt< unsigned > MaxDeoptOrUnreachableSuccessorCheckDepth("max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden, cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable"))	(	"max-deopt-or-unreachable-succ-check-depth"	,
		cl::init(8)	,
		cl::Hidden	,
		cl::desc("Set the maximum path length when checking whether a basic block " "is followed by a block that either has a terminating " "deoptimizing call or is terminated with an unreachable")
	)

static

Referenced by llvm::IsBlockFollowedByDeoptOrUnreachable().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ DbgVariableRecordsRemoveRedundantDbgInstrsUsingBackwardScan()

BackwardScan strategy:

◆ DbgVariableRecordsRemoveRedundantDbgInstrsUsingForwardScan()

ForwardScan strategy:

◆ DbgVariableRecordsRemoveUndefDbgAssignsFromEntryBlock()

◆ removeRedundantDbgInstrsUsingBackwardScan()

◆ removeRedundantDbgInstrsUsingForwardScan()

◆ removeUndefDbgAssignsFromEntryBlock()

Strategy:

◆ SplitBlockImpl()

◆ SplitBlockPredecessorsImpl()

◆ SplitLandingPadPredecessorsImpl()

◆ UpdateAnalysisInformation()

◆ UpdatePHINodes()

Variable Documentation

◆ MaxDeoptOrUnreachableSuccessorCheckDepth