|
LLVM 18.0.0git
|
#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 | 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 | remomveUndefDbgAssignsFromEntryBlock (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) |
| 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< 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")) |
| #define DEBUG_TYPE "basicblock-utils" |
Definition at line 54 of file BasicBlockUtils.cpp.
| using BBPredicates = DenseMap<BasicBlock *, Instruction *> |
Definition at line 1797 of file BasicBlockUtils.cpp.
| using BBSetVector = SetVector<BasicBlock *> |
Definition at line 1798 of file BasicBlockUtils.cpp.
|
static |
We record the predicate of each outgoing block using a phi of boolean.
Definition at line 1915 of file BasicBlockUtils.cpp.
References assert(), Context, llvm::PHINode::Create(), llvm::dbgs(), llvm::SmallVectorTemplateCommon< T, typename >::front(), llvm::SetVector< T, Vector, Set, N >::front(), llvm::ConstantInt::getFalse(), llvm::Type::getInt1Ty(), llvm::ConstantInt::getTrue(), llvm::invertCondition(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T, bool >::push_back(), redirectToHub(), and llvm::SetVector< T, Vector, Set, N >::size().
Referenced by convertToGuardPredicates().
|
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 1870 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::SetVector< T, Vector, Set, N >::front(), llvm::ConstantInt::get(), llvm::Type::getInt32Ty(), llvm::Value::getName(), redirectToHub(), and llvm::SetVector< T, Vector, Set, N >::size().
Referenced by convertToGuardPredicates().
|
static |
Definition at line 1985 of file BasicBlockUtils.cpp.
References calcPredicateUsingBooleans(), calcPredicateUsingInteger(), llvm::BasicBlock::Create(), F, llvm::SetVector< T, Vector, Set, N >::front(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), setupBranchForGuard(), and llvm::SetVector< T, Vector, Set, N >::size().
|
static |
Definition at line 1768 of file BasicBlockUtils.cpp.
References assert(), llvm::BasicBlock::begin(), llvm::PHINode::Create(), llvm::BasicBlock::end(), llvm::BasicBlock::front(), llvm::UndefValue::get(), I, and llvm::SetVector< T, Vector, Set, N >::size().
|
static |
Definition at line 1811 of file BasicBlockUtils.cpp.
References assert(), llvm::SetVector< T, Vector, Set, N >::count(), llvm::BranchInst::Create(), and llvm::BasicBlock::getTerminator().
Referenced by calcPredicateUsingBooleans(), and calcPredicateUsingInteger().
|
static |
Remove redundant undef dbg.assign intrinsic from an entry block using a forward scan.
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:
Definition at line 504 of file BasicBlockUtils.cpp.
References assert(), llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::contains(), 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(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by llvm::RemoveRedundantDbgInstrs().
|
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.
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:
Definition at line 385 of file BasicBlockUtils.cpp.
References llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::clear(), llvm::SmallVectorBase< Size_T >::empty(), llvm::at::getAssignmentInsts(), I, llvm::detail::DenseSetImpl< ValueT, MapTy, ValueInfoT >::insert(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::reverse().
Referenced by llvm::RemoveRedundantDbgInstrs().
|
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.
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:
Definition at line 443 of file BasicBlockUtils.cpp.
References 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, and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by llvm::RemoveRedundantDbgInstrs().
|
static |
Definition at line 1850 of file BasicBlockUtils.cpp.
References assert(), llvm::SetVector< T, Vector, Set, N >::back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::BranchInst::Create(), llvm::SmallVectorTemplateBase< T, bool >::pop_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorBase< Size_T >::size().
Referenced by convertToGuardPredicates().
|
static |
Definition at line 882 of file BasicBlockUtils.cpp.
References llvm::DominatorTreeBase< NodeT, IsPostDom >::addNewBlock(), llvm::DomTreeUpdater::applyUpdates(), assert(), llvm::DominatorTreeBase< NodeT, IsPostDom >::changeImmediateDominator(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::Value::getName(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), Name, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::SmallVectorImpl< T >::reserve(), llvm::SmallVectorBase< Size_T >::size(), llvm::BasicBlock::splitBasicBlock(), llvm::splitBlockBefore(), llvm::Twine::str(), llvm::succ_size(), and llvm::successors().
Referenced by llvm::SplitBlock().
|
static |
Definition at line 1183 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().
|
static |
Definition at line 1290 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::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().
|
static |
Update DominatorTree, LoopInfo, and LCCSA analysis information.
Definition at line 999 of file BasicBlockUtils.cpp.
References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::DomTreeUpdater::applyUpdates(), assert(), 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::SmallPtrSetImpl< PtrType >::insert(), llvm::BasicBlock::isEntryBlock(), llvm::DominatorTree::isReachableFromEntry(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::DomTreeUpdater::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().
|
static |
Update the PHI nodes in OrigBB to include the values coming from NewBB.
This also updates AliasAnalysis, if available.
Definition at line 1113 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::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().
|
static |
Referenced by llvm::IsBlockFollowedByDeoptOrUnreachable().
1.9.6