BasicBlockUtils.cpp File Reference

#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/IRBuilder.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.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>

Go to the source code of this file.

Macros
#define	DEBUG_TYPE   "basicblock-utils"

Functions
static void	emptyAndDetachBlock (BasicBlock *BB, SmallVectorImpl< DominatorTree::UpdateType > *Updates, bool KeepOneInputPHIs)
	Zap all the instructions in the block and replace them with an unreachable instruction and notify the basic block's successors that one of their predecessors is going away.
static bool	removeRedundantDbgInstrsUsingBackwardScan (BasicBlock *BB)
	Remove redundant instructions within sequences of consecutive dbg.value instructions.
static bool	removeRedundantDbgInstrsUsingForwardScan (BasicBlock *BB)
	Remove redundant dbg.value instructions using a forward scan.
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 53 of file BasicBlockUtils.cpp.

Function Documentation

emptyAndDetachBlock()

void emptyAndDetachBlock ( BasicBlock * BB, SmallVectorImpl< DominatorTree::UpdateType > * Updates, bool KeepOneInputPHIs )

static

Zap all the instructions in the block and replace them with an unreachable instruction and notify the basic block's successors that one of their predecessors is going away.

Definition at line 65 of file BasicBlockUtils.cpp.

References assert(), llvm::BasicBlock::back(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::BasicBlock::empty(), llvm::Instruction::eraseFromParent(), llvm::PoisonValue::get(), llvm::BasicBlock::getContext(), llvm::BasicBlock::getTerminator(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::BasicBlock::size(), and llvm::successors().

Referenced by llvm::detachDeadBlocks().

removeRedundantDbgInstrsUsingBackwardScan()

bool removeRedundantDbgInstrsUsingBackwardScan ( 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.

Definition at line 421 of file BasicBlockUtils.cpp.

References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::filterDbgVars(), llvm::at::getAssignmentInsts(), I, llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().

Referenced by llvm::RemoveRedundantDbgInstrs().

removeRedundantDbgInstrsUsingForwardScan()

bool removeRedundantDbgInstrsUsingForwardScan ( 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 476 of file BasicBlockUtils.cpp.

References llvm::DbgVariableRecord::Declare, llvm::filterDbgVars(), llvm::at::getAssignmentInsts(), I, llvm::InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key, llvm::make_early_inc_range(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

Referenced by llvm::RemoveRedundantDbgInstrs().

removeUndefDbgAssignsFromEntryBlock()

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 536 of file BasicBlockUtils.cpp.

References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::filterDbgVars(), llvm::at::getAssignmentInsts(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::BasicBlock::isEntryBlock(), and llvm::make_early_inc_range().

Referenced by llvm::RemoveRedundantDbgInstrs().

SplitBlockImpl()

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

static

Definition at line 905 of file BasicBlockUtils.cpp.

References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdates(), assert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::SmallVectorTemplateCommon< T, typename >::size(), llvm::BasicBlock::splitBasicBlock(), llvm::splitBlockBefore(), llvm::Twine::str(), llvm::succ_size(), and llvm::successors().

Referenced by llvm::SplitBlock(), and llvm::SplitBlock().

SplitBlockPredecessorsImpl()

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

static

Definition at line 1207 of file BasicBlockUtils.cpp.

References assert(), llvm::BasicBlock::begin(), llvm::BasicBlock::canSplitPredecessors(), llvm::cast(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::ArrayRef< T >::empty(), llvm::PoisonValue::get(), llvm::BasicBlock::getContext(), 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::isa(), llvm::BasicBlock::isLandingPad(), llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), SplitLandingPadPredecessorsImpl(), UpdateAnalysisInformation(), and UpdatePHINodes().

Referenced by llvm::SplitBlockPredecessors(), and llvm::SplitBlockPredecessors().

SplitLandingPadPredecessorsImpl()

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 1314 of file BasicBlockUtils.cpp.

References llvm::PHINode::addIncoming(), assert(), llvm::Instruction::clone(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::PHINode::Create(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::Instruction::eraseFromParent(), llvm::BasicBlock::getContext(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BasicBlock::getFirstNonPHIIt(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getLandingPadInst(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::Value::getType(), llvm::Instruction::insertInto(), llvm::isa(), 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()

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 1023 of file BasicBlockUtils.cpp.

References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdates(), assert(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::getDomTree(), llvm::LoopBase< BlockT, LoopT >::getLoopDepth(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::BasicBlock::getParent(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getRootNode(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::hasDomTree(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, 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::SmallVectorTemplateCommon< T, typename >::size(), llvm::DominatorTreeBase< NodeT, IsPostDom >::splitBlock(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().

Referenced by SplitBlockPredecessorsImpl(), and SplitLandingPadPredecessorsImpl().

UpdatePHINodes()

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 1137 of file BasicBlockUtils.cpp.

References llvm::PHINode::addIncoming(), llvm::BasicBlock::begin(), llvm::cast(), llvm::SmallPtrSetImpl< PtrType >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::PHINode::Create(), llvm::from_range, 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, llvm::isa(), 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().