#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/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 | 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 bool | remomveUndefDbgAssignsFromEntryBlock (BasicBlock *BB) |
| Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan. More... | |
| static BasicBlock * | SplitBlockImpl (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 BasicBlock * | SplitBlockPredecessorsImpl (BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DomTreeUpdater *DTU, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA) |
| static Instruction * | SplitBlockAndInsertIfThenImpl (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 | 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. More... | |
| 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. More... | |
| static void | convertToGuardPredicates (SmallVectorImpl< BasicBlock * > &GuardBlocks, SmallVectorImpl< WeakVH > &DeletionCandidates, const BBSetVector &Incoming, const BBSetVector &Outgoing, const StringRef Prefix, Optional< unsigned > MaxControlFlowBooleans) |
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.
Typedef Documentation
◆ BBPredicates
| using BBPredicates = DenseMap<BasicBlock *, Instruction *> |
Definition at line 1695 of file BasicBlockUtils.cpp.
◆ BBSetVector
| using BBSetVector = SetVector<BasicBlock *> |
Definition at line 1696 of file BasicBlockUtils.cpp.
Function Documentation
◆ calcPredicateUsingBooleans()
|
static |
We record the predicate of each outgoing block using a phi of boolean.
Definition at line 1813 of file BasicBlockUtils.cpp.
References llvm::PHINode::addIncoming(), assert(), Context, llvm::PHINode::Create(), llvm::dbgs(), llvm::numbers::e, llvm::SetVector< T, Vector, Set >::front(), llvm::ConstantInt::getFalse(), llvm::Type::getInt1Ty(), llvm::ConstantInt::getTrue(), i, llvm::tgtok::In, llvm::invertCondition(), LLVM_DEBUG, redirectToHub(), and llvm::SetVector< T, Vector, Set >::size().
Referenced by convertToGuardPredicates().
◆ calcPredicateUsingInteger()
|
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 1768 of file BasicBlockUtils.cpp.
References llvm::SetVector< T, Vector, Set >::begin(), Context, llvm::CmpInst::Create(), llvm::SelectInst::Create(), llvm::PHINode::Create(), llvm::numbers::e, llvm::find(), llvm::SetVector< T, Vector, Set >::front(), llvm::ConstantInt::get(), llvm::Type::getInt32Ty(), llvm::Value::getName(), i, llvm::CmpInst::ICMP_EQ, llvm::tgtok::In, redirectToHub(), and llvm::SetVector< T, Vector, Set >::size().
Referenced by convertToGuardPredicates().
◆ convertToGuardPredicates()
|
static |
Definition at line 1883 of file BasicBlockUtils.cpp.
References calcPredicateUsingBooleans(), calcPredicateUsingInteger(), llvm::BasicBlock::Create(), llvm::numbers::e, F, llvm::SetVector< T, Vector, Set >::front(), i, llvm::cl::Prefix, setupBranchForGuard(), and llvm::SetVector< T, Vector, Set >::size().
◆ reconnectPhis()
|
static |
Definition at line 1666 of file BasicBlockUtils.cpp.
References assert(), llvm::BasicBlock::begin(), llvm::PHINode::Create(), llvm::BasicBlock::end(), llvm::BasicBlock::front(), llvm::UndefValue::get(), I, llvm::tgtok::In, and llvm::SetVector< T, Vector, Set >::size().
◆ redirectToHub()
|
static |
Definition at line 1709 of file BasicBlockUtils.cpp.
References assert(), BB, llvm::MCID::Branch, llvm::SetVector< T, Vector, Set >::count(), and llvm::BranchInst::Create().
Referenced by calcPredicateUsingBooleans(), and calcPredicateUsingInteger().
◆ remomveUndefDbgAssignsFromEntryBlock()
|
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 485 of file BasicBlockUtils.cpp.
References assert(), BB, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), llvm::iterator_range< IteratorT >::empty(), llvm::at::getAssignmentInsts(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), and llvm::DbgVariableIntrinsic::isUndef().
Referenced by llvm::RemoveRedundantDbgInstrs().
◆ removeRedundantDbgInstrsUsingBackwardScan()
|
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 366 of file BasicBlockUtils.cpp.
References BB, llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear(), llvm::at::getAssignmentInsts(), 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 |
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 424 of file BasicBlockUtils.cpp.
References BB, llvm::iterator_range< IteratorT >::empty(), 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(), llvm::at::getAssignmentInsts(), and I.
Referenced by llvm::RemoveRedundantDbgInstrs().
◆ setupBranchForGuard()
|
static |
Definition at line 1748 of file BasicBlockUtils.cpp.
References assert(), llvm::SetVector< T, Vector, Set >::back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::BranchInst::Create(), llvm::numbers::e, and i.
Referenced by convertToGuardPredicates().
◆ SplitBlockAndInsertIfThenImpl()
|
static |
Definition at line 1456 of file BasicBlockUtils.cpp.
References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::DomTreeUpdater::applyUpdates(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), Cond, llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::ReplaceInstWithInst(), llvm::SmallVectorImpl< T >::reserve(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), llvm::BasicBlock::splitBasicBlock(), llvm::succ_size(), llvm::successors(), and llvm::CallingConv::Tail.
Referenced by llvm::SplitBlockAndInsertIfThen().
◆ SplitBlockImpl()
|
static |
Definition at line 861 of file BasicBlockUtils.cpp.
References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::DomTreeUpdater::applyUpdates(), assert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::BasicBlock::end(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), I, llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::DomTreeUpdater::Lazy, llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), llvm::SmallVectorImpl< T >::reserve(), llvm::BasicBlock::splitBasicBlock(), llvm::splitBlockBefore(), llvm::Twine::str(), llvm::succ_size(), and llvm::successors().
Referenced by llvm::SplitBlock().
◆ SplitBlockPredecessorsImpl()
|
static |
Definition at line 1165 of file BasicBlockUtils.cpp.
References assert(), BB, llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::PoisonValue::get(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getMetadata(), llvm::Loop::getStartLoc(), llvm::BasicBlock::getTerminator(), I, llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), SplitLandingPadPredecessorsImpl(), UpdateAnalysisInformation(), and UpdatePHINodes().
Referenced by llvm::SplitBlockPredecessors().
◆ SplitLandingPadPredecessorsImpl()
|
static |
Definition at line 1272 of file BasicBlockUtils.cpp.
References llvm::PHINode::addIncoming(), assert(), llvm::Instruction::clone(), llvm::BasicBlock::Create(), llvm::PHINode::Create(), llvm::BranchInst::Create(), llvm::numbers::e, llvm::Instruction::eraseFromParent(), llvm::BasicBlock::getContext(), llvm::Instruction::getDebugLoc(), llvm::BasicBlock::getFirstInsertionPt(), llvm::BasicBlock::getFirstNonPHI(), llvm::BasicBlock::getInstList(), llvm::BasicBlock::getLandingPadInst(), llvm::Value::getName(), llvm::BasicBlock::getParent(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), i, llvm::BasicBlock::isLandingPad(), llvm::Type::isTokenTy(), llvm::pred_begin(), llvm::pred_end(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::Value::setName(), UpdateAnalysisInformation(), UpdatePHINodes(), and llvm::Value::use_empty().
Referenced by SplitBlockPredecessorsImpl(), and llvm::SplitLandingPadPredecessors().
◆ UpdateAnalysisInformation()
|
static |
Update DominatorTree, LoopInfo, and LCCSA analysis information.
Definition at line 978 of file BasicBlockUtils.cpp.
References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::DomTreeUpdater::applyUpdates(), assert(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeUpdater::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::DomTreeUpdater::hasDomTree(), llvm::DominatorTreeBase< BasicBlock, false >::Insert, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BasicBlock::isEntryBlock(), llvm::DominatorTree::isReachableFromEntry(), llvm::LoopBase< BlockT, LoopT >::moveToHeader(), llvm::AArch64CC::PL, llvm::DomTreeUpdater::recalculate(), llvm::SmallVectorImpl< T >::reserve(), llvm::DominatorTreeBase< NodeT, IsPostDom >::setNewRoot(), llvm::ArrayRef< T >::size(), llvm::DominatorTreeBase< NodeT, IsPostDom >::splitBlock(), and llvm::MemorySSAUpdater::wireOldPredecessorsToNewImmediatePredecessor().
Referenced by SplitBlockPredecessorsImpl(), and SplitLandingPadPredecessorsImpl().
◆ UpdatePHINodes()
|
static |
Update the PHI nodes in OrigBB to include the values coming from NewBB.
This also updates AliasAnalysis, if available.
Definition at line 1092 of file BasicBlockUtils.cpp.
References llvm::PHINode::addIncoming(), llvm::ArrayRef< T >::begin(), llvm::BasicBlock::begin(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::PHINode::Create(), llvm::numbers::e, llvm::ArrayRef< T >::end(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::PHINode::getIncomingValueForBlock(), llvm::Value::getName(), llvm::PHINode::getNumIncomingValues(), llvm::Value::getType(), i, I, llvm::PHINode::removeIncomingValue(), and llvm::ArrayRef< T >::size().
Referenced by HandleInlinedEHPad(), SplitBlockPredecessorsImpl(), and SplitLandingPadPredecessorsImpl().
Variable Documentation
◆ MaxDeoptOrUnreachableSuccessorCheckDepth
|
static |
Referenced by llvm::IsBlockFollowedByDeoptOrUnreachable().
