LLVM  14.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/Analysis/PostDominators.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.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/LLVMContext.h"
#include "llvm/IR/PseudoProbe.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>
Include dependency graph for BasicBlockUtils.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "basicblock-utils"
 

Typedefs

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

Functions

static bool removeRedundantDbgInstrsUsingBackwardScan (BasicBlock *BB)
 Remove redundant instructions within sequences of consecutive dbg.value instructions. More...
 
static bool removeRedundantDbgInstrsUsingForwardScan (BasicBlock *BB)
 Remove redundant dbg.value instructions using a forward scan. More...
 
static BasicBlockSplitBlockImpl (BasicBlock *Old, Instruction *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. More...
 
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. More...
 
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 InstructionSplitBlockAndInsertIfThenImpl (Value *Cond, Instruction *SplitBefore, bool Unreachable, MDNode *BranchWeights, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, BasicBlock *ThenBlock)
 
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 convertToGuardPredicates (BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing)
 
static void createGuardBlocks (SmallVectorImpl< BasicBlock * > &GuardBlocks, Function *F, const BBSetVector &Outgoing, BBPredicates &GuardPredicates, StringRef Prefix)
 

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.

Typedef Documentation

◆ BBPredicates

Definition at line 1615 of file BasicBlockUtils.cpp.

◆ BBSetVector

Definition at line 1616 of file BasicBlockUtils.cpp.

Function Documentation

◆ convertToGuardPredicates()

static void convertToGuardPredicates ( BasicBlock FirstGuardBlock,
BBPredicates GuardPredicates,
SmallVectorImpl< WeakVH > &  DeletionCandidates,
const BBSetVector Incoming,
const BBSetVector Outgoing 
)
static

◆ createGuardBlocks()

static void createGuardBlocks ( SmallVectorImpl< BasicBlock * > &  GuardBlocks,
Function F,
const BBSetVector Outgoing,
BBPredicates GuardPredicates,
StringRef  Prefix 
)
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

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.addr, dbg.declare. dbg.label, and possibly other meta instructions being part of the sequence of consecutive instructions.

Definition at line 367 of file BasicBlockUtils.cpp.

References BB, llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear(), I, llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert(), and llvm::reverse().

Referenced by llvm::RemoveRedundantDbgInstrs().

◆ removeRedundantDbgInstrsUsingForwardScan()

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

References BB, llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find(), and I.

Referenced by llvm::RemoveRedundantDbgInstrs().

◆ SplitBlockAndInsertIfThenImpl()

static Instruction* SplitBlockAndInsertIfThenImpl ( Value Cond,
Instruction SplitBefore,
bool  Unreachable,
MDNode BranchWeights,
DomTreeUpdater DTU,
DominatorTree DT,
LoopInfo LI,
BasicBlock ThenBlock 
)
static

◆ SplitBlockImpl()

static BasicBlock* SplitBlockImpl ( BasicBlock Old,
Instruction 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"))
static