#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/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 *, 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 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 | 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) |
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 *, PHINode *> |
Definition at line 1589 of file BasicBlockUtils.cpp.
◆ BBSetVector
| using BBSetVector = SetVector<BasicBlock *> |
Definition at line 1590 of file BasicBlockUtils.cpp.
Function Documentation
◆ convertToGuardPredicates()
|
static |
Definition at line 1644 of file BasicBlockUtils.cpp.
References 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().
◆ createGuardBlocks()
|
static |
Definition at line 1714 of file BasicBlockUtils.cpp.
References assert(), llvm::SetVector< T, Vector, Set >::back(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::numbers::e, F, i, llvm::cl::Prefix, llvm::SetVector< T, Vector, Set >::size(), and llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::size().
◆ reconnectPhis()
|
static |
Definition at line 1560 of file BasicBlockUtils.cpp.
References assert(), llvm::BasicBlock::back(), llvm::BasicBlock::begin(), llvm::PHINode::Create(), llvm::BasicBlock::end(), llvm::UndefValue::get(), I, llvm::tgtok::In, and llvm::SetVector< T, Vector, Set >::size().
◆ redirectToHub()
|
static |
Definition at line 1603 of file BasicBlockUtils.cpp.
References assert(), BB, llvm::MCID::Branch, llvm::SetVector< T, Vector, Set >::count(), and llvm::BranchInst::Create().
Referenced by convertToGuardPredicates().
◆ 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 356 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 |
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 403 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 |
Definition at line 1350 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::ReplaceInstWithInst(), llvm::SmallVectorImpl< T >::reserve(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), llvm::SmallPtrSetImplBase::size(), llvm::BasicBlock::splitBasicBlock(), llvm::succ_begin(), llvm::succ_end(), and llvm::CallingConv::Tail.
Referenced by llvm::SplitBlockAndInsertIfThen().
◆ SplitBlockImpl()
|
static |
Definition at line 758 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::DomTreeUpdater::Lazy, llvm::MemorySSAUpdater::moveAllAfterSpliceBlocks(), llvm::SmallVectorImpl< T >::reserve(), llvm::SmallPtrSetImplBase::size(), llvm::BasicBlock::splitBasicBlock(), llvm::splitBlockBefore(), llvm::Twine::str(), llvm::succ_begin(), and llvm::succ_end().
Referenced by llvm::SplitBlock().
◆ SplitBlockPredecessorsImpl()
|
static |
Definition at line 1061 of file BasicBlockUtils.cpp.
References assert(), BB, llvm::BasicBlock::Create(), llvm::BranchInst::Create(), llvm::numbers::e, llvm::ArrayRef< T >::empty(), llvm::UndefValue::get(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::LoopBase< BlockT, LoopT >::getLoopLatch(), llvm::Instruction::getMetadata(), llvm::Loop::getStartLoc(), llvm::BasicBlock::getTerminator(), i, I, llvm::LoopInfoBase< BlockT, LoopT >::isLoopHeader(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setMetadata(), llvm::ArrayRef< T >::size(), SplitLandingPadPredecessorsImpl(), UpdateAnalysisInformation(), and UpdatePHINodes().
Referenced by llvm::SplitBlockPredecessors().
◆ SplitLandingPadPredecessorsImpl()
|
static |
Definition at line 1166 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(), llvm::ArrayRef< T >::size(), 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 875 of file BasicBlockUtils.cpp.
References llvm::LoopBase< BlockT, LoopT >::addBasicBlockToLoop(), llvm::DomTreeUpdater::applyUpdates(), assert(), llvm::ArrayRef< T >::begin(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DominatorTreeBase< BasicBlock, false >::Delete, llvm::ArrayRef< T >::end(), 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::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::SmallPtrSetImplBase::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 988 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().
