LLVM: llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT > Struct Template Reference (original) (raw)

#include "[llvm/Support/GenericDomTreeConstruction.h](GenericDomTreeConstruction%5F8h%5Fsource.html)"

Public Types
using NodePtr = typename DomTreeT::NodePtr
using NodeT = typename DomTreeT::NodeType
using TreeNodePtr = DomTreeNodeBase<NodeT> *
using RootsT = decltype(DomTreeT::Roots)
using GraphDiffT = GraphDiff<NodePtr, IsPostDom>
using UpdateT = typename DomTreeT::UpdateType
using UpdateKind = typename DomTreeT::UpdateKind
using BatchUpdatePtr = BatchUpdateInfo *
using NodeOrderMap = DenseMap<NodePtr, unsigned>
Public Member Functions
SemiNCAInfo (BatchUpdatePtr BUI)
void clear ()
InfoRec & getNodeInfo (NodePtr BB)
NodePtr getIDom (NodePtr BB)
TreeNodePtr getNodeForBlock (NodePtr BB, DomTreeT &DT)
template<bool IsReverse = false, typename DescendCondition>
unsigned runDFS (NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum, const NodeOrderMap *SuccOrder=nullptr)
unsigned eval (unsigned V, unsigned LastLinked, SmallVectorImpl< InfoRec * > &Stack, ArrayRef< InfoRec * > NumToInfo)
void runSemiNCA ()
void addVirtualRoot ()
template
void doFullDFSWalk (const DomTreeT &DT, DescendCondition DC)
void attachNewSubtree (DomTreeT &DT, const TreeNodePtr AttachTo)
void reattachExistingSubtree (DomTreeT &DT, const TreeNodePtr AttachTo)
bool verifyRoots (const DomTreeT &DT)
bool verifyReachability (const DomTreeT &DT)
bool verifyParentProperty (const DomTreeT &DT)
bool verifySiblingProperty (const DomTreeT &DT)
Static Public Member Functions
template<bool Inversed>
static SmallVector< NodePtr, 8 > getChildren (NodePtr N, BatchUpdatePtr BUI)
template<bool Inversed>
static SmallVector< NodePtr, 8 > getChildren (NodePtr N)
static bool AlwaysDescend (NodePtr, NodePtr)
static bool HasForwardSuccessors (const NodePtr N, BatchUpdatePtr BUI)
static NodePtr GetEntryNode (const DomTreeT &DT)
static RootsT FindRoots (const DomTreeT &DT, BatchUpdatePtr BUI)
static void RemoveRedundantRoots (const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)
static void CalculateFromScratch (DomTreeT &DT, BatchUpdatePtr BUI)
static void InsertEdge (DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
static bool UpdateRootsBeforeInsertion (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
static bool isPermutation (const SmallVectorImpl< NodePtr > &A, const SmallVectorImpl< NodePtr > &B)
static void UpdateRootsAfterUpdate (DomTreeT &DT, const BatchUpdatePtr BUI)
static void InsertReachable (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
static void UpdateInsertion (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)
static void InsertUnreachable (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const NodePtr To)
static void ComputeUnreachableDominators (DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl< std::pair< NodePtr, TreeNodePtr > > &DiscoveredConnectingEdges)
static void DeleteEdge (DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
static void DeleteReachable (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr FromTN, const TreeNodePtr ToTN)
static bool HasProperSupport (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN)
static void DeleteUnreachable (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN)
static void ApplyUpdates (DomTreeT &DT, GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG)
static void ApplyNextUpdate (DomTreeT &DT, BatchUpdateInfo &BUI)
static bool VerifyLevels (const DomTreeT &DT)
static bool VerifyDFSNumbers (const DomTreeT &DT)
static bool IsSameAsFreshTree (const DomTreeT &DT)
Static Public Attributes
static constexpr bool IsPostDom = DomTreeT::IsPostDominator

template
struct llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >

Definition at line 55 of file GenericDomTreeConstruction.h.

◆ BatchUpdatePtr

template

◆ GraphDiffT

template

◆ NodeOrderMap

template

◆ NodePtr

template

◆ NodeT

template

◆ RootsT

template

◆ TreeNodePtr

template

◆ UpdateKind

template

◆ UpdateT

template

template

◆ addVirtualRoot()

template

◆ AlwaysDescend()

template

◆ ApplyNextUpdate()

template

◆ ApplyUpdates()

template

◆ attachNewSubtree()

template

◆ CalculateFromScratch()

template

Definition at line 560 of file GenericDomTreeConstruction.h.

References AlwaysDescend(), attachNewSubtree(), llvm::dbgs(), doFullDFSWalk(), FindRoots(), IsPostDom, llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::IsRecalculated, LLVM_DEBUG, llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::PostViewCFG, llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::PreViewCFG, runSemiNCA(), and SemiNCAInfo().

Referenced by ApplyUpdates(), llvm::DomTreeBuilder::Calculate(), llvm::DomTreeBuilder::CalculateWithUpdates(), DeleteReachable(), DeleteUnreachable(), UpdateRootsAfterUpdate(), and UpdateRootsBeforeInsertion().

◆ clear()

template

◆ ComputeUnreachableDominators()

template

◆ DeleteEdge()

template

Definition at line 912 of file GenericDomTreeConstruction.h.

References assert(), llvm::dbgs(), DeleteReachable(), DeleteUnreachable(), getChildren(), llvm::DomTreeNodeBase< NodeT >::getIDom(), HasProperSupport(), llvm::is_contained(), IsPostDom, LLVM_DEBUG, and UpdateRootsAfterUpdate().

Referenced by ApplyNextUpdate(), ApplyUpdates(), and llvm::DomTreeBuilder::DeleteEdge().

◆ DeleteReachable()

template

Definition at line 965 of file GenericDomTreeConstruction.h.

References assert(), CalculateFromScratch(), llvm::dbgs(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::DomTreeNodeBase< NodeT >::getLevel(), LLVM_DEBUG, reattachExistingSubtree(), runDFS(), runSemiNCA(), and SemiNCAInfo().

Referenced by DeleteEdge().

◆ DeleteUnreachable()

template

Definition at line 1030 of file GenericDomTreeConstruction.h.

References assert(), CalculateFromScratch(), clear(), llvm::dbgs(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::DomTreeNodeBase< NodeT >::getLevel(), InsertReachable(), llvm::is_contained(), IsPostDom, LLVM_DEBUG, N, NumToNode, llvm::SmallVectorTemplateBase< T, bool >::push_back(), reattachExistingSubtree(), runDFS(), runSemiNCA(), and SemiNCAInfo().

Referenced by DeleteEdge().

◆ doFullDFSWalk()

template

template

◆ eval()

template

◆ FindRoots()

template

Definition at line 352 of file GenericDomTreeConstruction.h.

References addVirtualRoot(), AlwaysDescend(), assert(), BatchUpdates, llvm::dbgs(), llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::DFSNum, getChildren(), GetEntryNode(), getNodeInfo(), HasForwardSuccessors(), I, IsPostDom, LLVM_DEBUG, N, nodes, NumToNode, llvm::SmallVectorTemplateBase< T, bool >::pop_back(), RemoveRedundantRoots(), runDFS(), SemiNCAInfo(), and llvm::Total.

Referenced by CalculateFromScratch(), UpdateRootsAfterUpdate(), and verifyRoots().

◆ getChildren() [1/2]

template

template<bool Inversed>

◆ getChildren() [2/2]

template

template<bool Inversed>

◆ GetEntryNode()

template

◆ getIDom()

template

◆ getNodeForBlock()

template

◆ getNodeInfo()

template

Definition at line 130 of file GenericDomTreeConstruction.h.

References llvm::GraphHasNodeNumbers, and NodeInfos.

Referenced by addVirtualRoot(), attachNewSubtree(), FindRoots(), getIDom(), reattachExistingSubtree(), runDFS(), runSemiNCA(), verifyParentProperty(), verifyReachability(), and verifySiblingProperty().

◆ HasForwardSuccessors()

template

◆ HasProperSupport()

template

◆ InsertEdge()

template

◆ InsertReachable()

template

Definition at line 736 of file GenericDomTreeConstruction.h.

References assert(), llvm::dbgs(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getChildren(), llvm::DomTreeNodeBase< NodeT >::getLevel(), II, IsPostDom, LLVM_DEBUG, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), UpdateInsertion(), and UpdateRootsBeforeInsertion().

Referenced by DeleteUnreachable(), InsertEdge(), and InsertUnreachable().

◆ InsertUnreachable()

template

◆ isPermutation()

template

◆ IsSameAsFreshTree()

template

◆ reattachExistingSubtree()

template

◆ RemoveRedundantRoots()

template

Definition at line 508 of file GenericDomTreeConstruction.h.

References AlwaysDescend(), assert(), clear(), llvm::dbgs(), HasForwardSuccessors(), llvm::is_contained(), IsPostDom, LLVM_DEBUG, N, NumToNode, runDFS(), SemiNCAInfo(), and std::swap().

Referenced by FindRoots().

◆ runDFS()

template

template<bool IsReverse = false, typename DescendCondition>

Definition at line 195 of file GenericDomTreeConstruction.h.

References A(), assert(), B(), BatchUpdates, llvm::SmallVectorTemplateCommon< T, typename >::empty(), getChildren(), getNodeInfo(), IsPostDom, NumToNode, llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::Parent, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::sort().

Referenced by ComputeUnreachableDominators(), DeleteReachable(), DeleteUnreachable(), doFullDFSWalk(), FindRoots(), and RemoveRedundantRoots().

◆ runSemiNCA()

template

Definition at line 276 of file GenericDomTreeConstruction.h.

References assert(), eval(), getNodeInfo(), N, NumToNode, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::SmallVectorImpl< T >::reserve().

Referenced by CalculateFromScratch(), ComputeUnreachableDominators(), DeleteReachable(), and DeleteUnreachable().

◆ UpdateInsertion()

template

◆ UpdateRootsAfterUpdate()

template

◆ UpdateRootsBeforeInsertion()

template

◆ VerifyDFSNumbers()

template

◆ VerifyLevels()

template

◆ verifyParentProperty()

template

Definition at line 1455 of file GenericDomTreeConstruction.h.

References llvm::DomTreeNodeBase< NodeT >::children(), clear(), llvm::dbgs(), llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::DFSNum, doFullDFSWalk(), llvm::errs(), llvm::raw_ostream::flush(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getNodeInfo(), llvm::DomTreeNodeBase< NodeT >::isLeaf(), and LLVM_DEBUG.

Referenced by llvm::DomTreeBuilder::Verify().

◆ verifyReachability()

template

◆ verifyRoots()

template

◆ verifySiblingProperty()

template

◆ BatchUpdates

template

◆ IsPostDom

template

Definition at line 60 of file GenericDomTreeConstruction.h.

Referenced by addVirtualRoot(), CalculateFromScratch(), DeleteEdge(), DeleteUnreachable(), doFullDFSWalk(), FindRoots(), InsertEdge(), InsertReachable(), RemoveRedundantRoots(), runDFS(), UpdateInsertion(), UpdateRootsAfterUpdate(), UpdateRootsBeforeInsertion(), VerifyDFSNumbers(), and verifyRoots().

◆ NodeInfos

template

◆ NumToNode

template

The documentation for this struct was generated from the following files: