LLVM 19.0.0git
Macros | Typedefs | Functions | Variables
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/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>

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "basicblock-utils"
 

Typedefs

using BBPredicates = DenseMap< BasicBlock *, Instruction * >
 
using BBSetVector = SetVector< BasicBlock * >
 

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 BasicBlockSplitBlockImpl (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 BasicBlockSplitBlockPredecessorsImpl (BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
 
static void reconnectPhis (BasicBlock *Out, BasicBlock *GuardBlock, const SetVector< BasicBlock * > &Incoming, BasicBlock *FirstGuardBlock)
 
static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub (BasicBlock *BB, BasicBlock *FirstGuardBlock, const BBSetVector &Outgoing)
 
static void setupBranchForGuard (SmallVectorImpl< BasicBlock * > &GuardBlocks, const BBSetVector &Outgoing, BBPredicates &GuardPredicates)
 
static void calcPredicateUsingInteger (const BBSetVector &Incoming, const BBSetVector &Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates)
 We are using one integer to represent the block we are branching to.
 
static void calcPredicateUsingBooleans (const BBSetVector &Incoming, const BBSetVector &Outgoing, SmallVectorImpl< BasicBlock * > &GuardBlocks, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates)
 We record the predicate of each outgoing block using a phi of boolean.
 
static void convertToGuardPredicates (SmallVectorImpl< BasicBlock * > &GuardBlocks, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing, const StringRef Prefix, std::optional< unsigned > MaxControlFlowBooleans)
 

Variables

static cl::opt< unsignedMaxDeoptOrUnreachableSuccessorCheckDepth ("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.

Typedef Documentation

◆ BBPredicates

Definition at line 1931 of file BasicBlockUtils.cpp.

◆ BBSetVector

Definition at line 1932 of file BasicBlockUtils.cpp.

Function Documentation

◆ calcPredicateUsingBooleans()

static void calcPredicateUsingBooleans ( const BBSetVector Incoming,
const BBSetVector Outgoing,
SmallVectorImpl< BasicBlock * > &  GuardBlocks,
BBPredicates GuardPredicates,
SmallVectorImpl< WeakVH > &  DeletionCandidates 
)
static

◆ calcPredicateUsingInteger()

static void calcPredicateUsingInteger ( const BBSetVector Incoming,
const BBSetVector Outgoing,
SmallVectorImpl< BasicBlock * > &  GuardBlocks,
BBPredicates GuardPredicates 
)
static

We are using one integer to represent the block we are branching to.

Then at each guard block, the predicate was calcuated using a simple icmp eq.

Definition at line 2004 of file BasicBlockUtils.cpp.

References llvm::SetVector< T, Vector, Set, N >::begin(), Context, llvm::PHINode::Create(), llvm::SelectInst::Create(), llvm::find(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::Type::getInt32Ty(), redirectToHub(), and llvm::SetVector< T, Vector, Set, N >::size().

Referenced by convertToGuardPredicates().

◆ convertToGuardPredicates()

static void convertToGuardPredicates ( SmallVectorImpl< BasicBlock * > &  GuardBlocks,
SmallVectorImpl< WeakVH > &  DeletionCandidates,
const BBSetVector Incoming,
const BBSetVector Outgoing,
const StringRef  Prefix,
std::optional< unsigned MaxControlFlowBooleans 
)
static

◆ 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 504 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

◆ reconnectPhis()

static void reconnectPhis ( BasicBlock Out,
BasicBlock GuardBlock,
const SetVector< BasicBlock * > &  Incoming,
BasicBlock FirstGuardBlock 
)
static

◆ redirectToHub()

static std::tuple< Value *, BasicBlock *, BasicBlock * > redirectToHub ( BasicBlock BB,
BasicBlock FirstGuardBlock,
const BBSetVector Outgoing 
)
static

◆ removeRedundantDbgInstrsUsingBackwardScan()

static bool removeRedundantDbgInstrsUsingBackwardScan ( BasicBlock BB)
static

◆ removeRedundantDbgInstrsUsingForwardScan()

static bool removeRedundantDbgInstrsUsingForwardScan ( BasicBlock BB)
static

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

◆ setupBranchForGuard()

static void setupBranchForGuard ( SmallVectorImpl< BasicBlock * > &  GuardBlocks,
const BBSetVector Outgoing,
BBPredicates GuardPredicates 
)
static

◆ 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

◆ 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

◆ UpdateAnalysisInformation()

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

◆ UpdatePHINodes()

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

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