LLVM 22.0.0git
Classes | Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | List of all members
llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT > Struct Template Reference

#include "llvm/Support/GenericDomTreeConstruction.h"

Classes

struct  BatchUpdateInfo
struct  BlockNamePrinter
struct  InfoRec
struct  InsertionInfo

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<typename DescendCondition>
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)

Public Attributes

SmallVector< NodePtr, 64 > NumToNode = {nullptr}
std::conditional_t< GraphHasNodeNumbers< NodePtr >, SmallVector< InfoRec, 64 >, DenseMap< NodePtr, InfoRec > > NodeInfos
BatchUpdateInfo * BatchUpdates

Static Public Attributes

static constexpr bool IsPostDom = DomTreeT::IsPostDominator

Detailed Description

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

Definition at line 55 of file GenericDomTreeConstruction.h.

Member Typedef Documentation

◆ BatchUpdatePtr

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdatePtr = BatchUpdateInfo *

Definition at line 99 of file GenericDomTreeConstruction.h.

◆ GraphDiffT

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::GraphDiffT = GraphDiff<NodePtr, IsPostDom>

Definition at line 61 of file GenericDomTreeConstruction.h.

◆ NodeOrderMap

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NodeOrderMap = DenseMap<NodePtr, unsigned>

Definition at line 182 of file GenericDomTreeConstruction.h.

◆ NodePtr

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NodePtr = typename DomTreeT::NodePtr

Definition at line 56 of file GenericDomTreeConstruction.h.

◆ NodeT

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NodeT = typename DomTreeT::NodeType

Definition at line 57 of file GenericDomTreeConstruction.h.

◆ RootsT

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::RootsT = decltype(DomTreeT::Roots)

Definition at line 59 of file GenericDomTreeConstruction.h.

◆ TreeNodePtr

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::TreeNodePtr = DomTreeNodeBase<NodeT> *

Definition at line 58 of file GenericDomTreeConstruction.h.

◆ UpdateKind

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateKind = typename DomTreeT::UpdateKind

Definition at line 83 of file GenericDomTreeConstruction.h.

◆ UpdateT

template<typename DomTreeT>
using llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateT = typename DomTreeT::UpdateType

Definition at line 82 of file GenericDomTreeConstruction.h.

Constructor & Destructor Documentation

◆ SemiNCAInfo()

template<typename DomTreeT>
llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::SemiNCAInfo ( BatchUpdatePtr BUI)
inline

Definition at line 102 of file GenericDomTreeConstruction.h.

References BatchUpdates.

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

Member Function Documentation

◆ addVirtualRoot()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::addVirtualRoot ( )
inline

Definition at line 326 of file GenericDomTreeConstruction.h.

References assert(), getNodeInfo(), IsPostDom, and NumToNode.

Referenced by doFullDFSWalk(), and FindRoots().

◆ AlwaysDescend()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::AlwaysDescend ( NodePtr ,
NodePtr  )
inlinestatic

Definition at line 164 of file GenericDomTreeConstruction.h.

Referenced by CalculateFromScratch(), FindRoots(), RemoveRedundantRoots(), and verifyReachability().

◆ ApplyNextUpdate()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::ApplyNextUpdate ( DomTreeT & DT,
BatchUpdateInfo & BUI )
inlinestatic

Definition at line 1180 of file GenericDomTreeConstruction.h.

References llvm::dbgs(), DeleteEdge(), InsertEdge(), LLVM_DEBUG, llvm::GraphDiff< NodePtr, InverseGraph >::popUpdateForIncrementalUpdates(), and llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::PreViewCFG.

Referenced by ApplyUpdates().

◆ ApplyUpdates()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::ApplyUpdates ( DomTreeT & DT,
GraphDiffT & PreViewCFG,
GraphDiffT * PostViewCFG )
inlinestatic

Definition at line 1131 of file GenericDomTreeConstruction.h.

References ApplyNextUpdate(), CalculateFromScratch(), DeleteEdge(), llvm::GraphDiff< NodePtr, InverseGraph >::getNumLegalizedUpdates(), InsertEdge(), llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::IsRecalculated, llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::NumLegalized, and llvm::GraphDiff< NodePtr, InverseGraph >::popUpdateForIncrementalUpdates().

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

◆ attachNewSubtree()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::attachNewSubtree ( DomTreeT & DT,
const TreeNodePtr AttachTo )
inline

Definition at line 599 of file GenericDomTreeConstruction.h.

References llvm::drop_begin(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getIDom(), getNodeForBlock(), getNodeInfo(), llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::IDom, and NumToNode.

Referenced by CalculateFromScratch(), and ComputeUnreachableDominators().

◆ CalculateFromScratch()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::CalculateFromScratch ( DomTreeT & DT,
BatchUpdatePtr BUI )
inlinestatic

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<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::clear ( )
inline

Definition at line 104 of file GenericDomTreeConstruction.h.

References NodeInfos, and NumToNode.

Referenced by DeleteUnreachable(), RemoveRedundantRoots(), verifyParentProperty(), verifyReachability(), and verifySiblingProperty().

◆ ComputeUnreachableDominators()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::ComputeUnreachableDominators ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const NodePtr Root,
const TreeNodePtr Incoming,
SmallVectorImpl< std::pair< NodePtr, TreeNodePtr > > & DiscoveredConnectingEdges )
inlinestatic

Definition at line 887 of file GenericDomTreeConstruction.h.

References assert(), attachNewSubtree(), llvm::dbgs(), LLVM_DEBUG, runDFS(), runSemiNCA(), and SemiNCAInfo().

Referenced by InsertUnreachable().

◆ DeleteEdge()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::DeleteEdge ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const NodePtr From,
const NodePtr To )
inlinestatic

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<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::DeleteReachable ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr FromTN,
const TreeNodePtr ToTN )
inlinestatic

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<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::DeleteUnreachable ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr ToTN )
inlinestatic

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<typename DomTreeT>
template<typename DescendCondition>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::doFullDFSWalk ( const DomTreeT & DT,
DescendCondition DC )
inline

Definition at line 548 of file GenericDomTreeConstruction.h.

References addVirtualRoot(), assert(), IsPostDom, and runDFS().

Referenced by CalculateFromScratch(), verifyParentProperty(), verifyReachability(), and verifySiblingProperty().

◆ eval()

template<typename DomTreeT>
unsigned llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::eval ( unsigned V,
unsigned LastLinked,
SmallVectorImpl< InfoRec * > & Stack,
ArrayRef< InfoRec * > NumToInfo )
inline

Definition at line 244 of file GenericDomTreeConstruction.h.

References assert(), llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::Label, llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::Parent, and llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::Semi.

Referenced by runSemiNCA().

◆ FindRoots()

template<typename DomTreeT>
RootsT llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::FindRoots ( const DomTreeT & DT,
BatchUpdatePtr BUI )
inlinestatic

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<typename DomTreeT>
template<bool Inversed>
SmallVector< NodePtr, 8 > llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::getChildren ( NodePtr N)
inlinestatic

Definition at line 119 of file GenericDomTreeConstruction.h.

References llvm::children(), llvm::erase(), N, and llvm::detail::reverse_if().

◆ getChildren() [2/2]

template<typename DomTreeT>
template<bool Inversed>
SmallVector< NodePtr, 8 > llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::getChildren ( NodePtr N,
BatchUpdatePtr BUI )
inlinestatic

Definition at line 112 of file GenericDomTreeConstruction.h.

References getChildren(), N, and llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo::PreViewCFG.

Referenced by DeleteEdge(), FindRoots(), getChildren(), HasForwardSuccessors(), HasProperSupport(), InsertReachable(), and runDFS().

◆ GetEntryNode()

template<typename DomTreeT>
NodePtr llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::GetEntryNode ( const DomTreeT & DT)
inlinestatic

Definition at line 344 of file GenericDomTreeConstruction.h.

References assert().

Referenced by FindRoots(), and verifyRoots().

◆ getIDom()

template<typename DomTreeT>
NodePtr llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::getIDom ( NodePtr BB)
inline

Definition at line 147 of file GenericDomTreeConstruction.h.

References getNodeInfo(), and llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::IDom.

Referenced by attachNewSubtree(), and getNodeForBlock().

◆ getNodeForBlock()

template<typename DomTreeT>
TreeNodePtr llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::getNodeForBlock ( NodePtr BB,
DomTreeT & DT )
inline

Definition at line 149 of file GenericDomTreeConstruction.h.

References assert(), getIDom(), and getNodeForBlock().

Referenced by attachNewSubtree(), and getNodeForBlock().

◆ getNodeInfo()

template<typename DomTreeT>
InfoRec & llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::getNodeInfo ( NodePtr BB)
inline

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<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::HasForwardSuccessors ( const NodePtr N,
BatchUpdatePtr BUI )
inlinestatic

Definition at line 339 of file GenericDomTreeConstruction.h.

References assert(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), getChildren(), and N.

Referenced by FindRoots(), and RemoveRedundantRoots().

◆ HasProperSupport()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::HasProperSupport ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr TN )
inlinestatic

Definition at line 1006 of file GenericDomTreeConstruction.h.

References llvm::dbgs(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getChildren(), and LLVM_DEBUG.

Referenced by DeleteEdge().

◆ InsertEdge()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertEdge ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const NodePtr From,
const NodePtr To )
inlinestatic

Definition at line 648 of file GenericDomTreeConstruction.h.

References assert(), llvm::dbgs(), InsertReachable(), InsertUnreachable(), IsPostDom, and LLVM_DEBUG.

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

◆ InsertReachable()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertReachable ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr From,
const TreeNodePtr To )
inlinestatic

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<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertUnreachable ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr From,
const NodePtr To )
inlinestatic

Definition at line 862 of file GenericDomTreeConstruction.h.

References ComputeUnreachableDominators(), llvm::dbgs(), InsertReachable(), and LLVM_DEBUG.

Referenced by InsertEdge().

◆ isPermutation()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::isPermutation ( const SmallVectorImpl< NodePtr > & A,
const SmallVectorImpl< NodePtr > & B )
inlinestatic

Definition at line 696 of file GenericDomTreeConstruction.h.

References A(), B(), llvm::from_range, and N.

Referenced by UpdateRootsAfterUpdate(), and verifyRoots().

◆ IsSameAsFreshTree()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::IsSameAsFreshTree ( const DomTreeT & DT)
inlinestatic

Definition at line 1532 of file GenericDomTreeConstruction.h.

References llvm::errs(), and llvm::raw_ostream::flush().

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

◆ reattachExistingSubtree()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::reattachExistingSubtree ( DomTreeT & DT,
const TreeNodePtr AttachTo )
inline

Definition at line 618 of file GenericDomTreeConstruction.h.

References assert(), llvm::drop_begin(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getNodeInfo(), llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec::IDom, N, NumToNode, and llvm::DomTreeNodeBase< NodeT >::setIDom().

Referenced by DeleteReachable(), and DeleteUnreachable().

◆ RemoveRedundantRoots()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::RemoveRedundantRoots ( const DomTreeT & DT,
BatchUpdatePtr BUI,
RootsT & Roots )
inlinestatic

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<typename DomTreeT>
template<bool IsReverse = false, typename DescendCondition>
unsigned llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::runDFS ( NodePtr V,
unsigned LastNum,
DescendCondition Condition,
unsigned AttachToNum,
const NodeOrderMap * SuccOrder = nullptr )
inline

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<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::runSemiNCA ( )
inline

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<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateInsertion ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr NCD,
InsertionInfo & II )
inlinestatic

Definition at line 842 of file GenericDomTreeConstruction.h.

References assert(), llvm::dbgs(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::DomTreeNodeBase< NodeT >::getLevel(), II, IsPostDom, LLVM_DEBUG, llvm::DomTreeNodeBase< NodeT >::setIDom(), and UpdateRootsAfterUpdate().

Referenced by InsertReachable().

◆ UpdateRootsAfterUpdate()

template<typename DomTreeT>
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateRootsAfterUpdate ( DomTreeT & DT,
const BatchUpdatePtr BUI )
inlinestatic

Definition at line 710 of file GenericDomTreeConstruction.h.

References assert(), CalculateFromScratch(), llvm::dbgs(), FindRoots(), isPermutation(), IsPostDom, LLVM_DEBUG, N, and llvm::none_of().

Referenced by DeleteEdge(), and UpdateInsertion().

◆ UpdateRootsBeforeInsertion()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateRootsBeforeInsertion ( DomTreeT & DT,
const BatchUpdatePtr BUI,
const TreeNodePtr From,
const TreeNodePtr To )
inlinestatic

Definition at line 678 of file GenericDomTreeConstruction.h.

References assert(), CalculateFromScratch(), llvm::dbgs(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getIDom(), llvm::is_contained(), IsPostDom, and LLVM_DEBUG.

Referenced by InsertReachable().

◆ VerifyDFSNumbers()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::VerifyDFSNumbers ( const DomTreeT & DT)
inlinestatic

Definition at line 1317 of file GenericDomTreeConstruction.h.

References assert(), llvm::errs(), llvm::raw_ostream::flush(), llvm::DomTreeNodeBase< NodeT >::getDFSNumIn(), IsPostDom, and llvm::sort().

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

◆ VerifyLevels()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::VerifyLevels ( const DomTreeT & DT)
inlinestatic

Definition at line 1283 of file GenericDomTreeConstruction.h.

References llvm::errs(), llvm::raw_ostream::flush(), llvm::DomTreeNodeBase< NodeT >::getBlock(), llvm::DomTreeNodeBase< NodeT >::getIDom(), and llvm::DomTreeNodeBase< NodeT >::getLevel().

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

◆ verifyParentProperty()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::verifyParentProperty ( const DomTreeT & DT)
inline

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<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::verifyReachability ( const DomTreeT & DT)
inline

Definition at line 1245 of file GenericDomTreeConstruction.h.

References AlwaysDescend(), clear(), doFullDFSWalk(), llvm::errs(), llvm::raw_ostream::flush(), llvm::DomTreeNodeBase< NodeT >::getBlock(), getNodeInfo(), N, and NumToNode.

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

◆ verifyRoots()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::verifyRoots ( const DomTreeT & DT)
inline

Definition at line 1206 of file GenericDomTreeConstruction.h.

References llvm::errs(), FindRoots(), llvm::raw_ostream::flush(), GetEntryNode(), isPermutation(), IsPostDom, and N.

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

◆ verifySiblingProperty()

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::verifySiblingProperty ( const DomTreeT & DT)
inline

Definition at line 1491 of file GenericDomTreeConstruction.h.

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

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

Member Data Documentation

◆ BatchUpdates

template<typename DomTreeT>
BatchUpdateInfo* llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdates

Definition at line 98 of file GenericDomTreeConstruction.h.

Referenced by FindRoots(), runDFS(), and SemiNCAInfo().

◆ IsPostDom

template<typename DomTreeT>
bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::IsPostDom = DomTreeT::IsPostDominator
staticconstexpr

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<typename DomTreeT>
std::conditional_t<GraphHasNodeNumbers<NodePtr>, SmallVector<InfoRec, 64>, DenseMap<NodePtr, InfoRec> > llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NodeInfos

Definition at line 80 of file GenericDomTreeConstruction.h.

Referenced by clear(), and getNodeInfo().

◆ NumToNode

template<typename DomTreeT>
SmallVector<NodePtr, 64> llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NumToNode = {nullptr}

Definition at line 75 of file GenericDomTreeConstruction.h.

Referenced by addVirtualRoot(), attachNewSubtree(), clear(), DeleteUnreachable(), FindRoots(), reattachExistingSubtree(), RemoveRedundantRoots(), runDFS(), runSemiNCA(), and verifyReachability().

The documentation for this struct was generated from the following files:
Generated on for LLVM by doxygen 1.14.0