LLVM  6.0.0svn
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/GenericDomTree.h"

Collaboration diagram for llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >:
Collaboration graph
[legend]

Classes

struct  BatchUpdateInfo
 
struct  BlockNamePrinter
 
struct  ChildrenGetter
 
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 UpdateT = typename DomTreeT::UpdateType
 
using BatchUpdatePtr = BatchUpdateInfo *
 

Public Member Functions

 SemiNCAInfo (BatchUpdatePtr BUI)
 
void clear ()
 
NodePtr getIDom (NodePtr BB) const
 
TreeNodePtr getNodeForBlock (NodePtr BB, DomTreeT &DT)
 
template<bool IsReverse = false, typename DescendCondition >
unsigned runDFS (NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum)
 
NodePtr eval (NodePtr VIn, unsigned LastLinked)
 
void runSemiNCA (DomTreeT &DT, const unsigned MinLevel=0)
 
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

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 void UpdateRootsAfterUpdate (DomTreeT &DT, const BatchUpdatePtr BUI)
 
static void InsertReachable (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
 
static void VisitInsertion (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN, const unsigned RootLevel, const TreeNodePtr NCD, InsertionInfo &II)
 
static void UpdateInsertion (DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)
 
static void UpdateLevelsAfterInsertion (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 EraseNode (DomTreeT &DT, const TreeNodePtr TN)
 
static void ApplyUpdates (DomTreeT &DT, ArrayRef< UpdateT > Updates)
 
static void LegalizeUpdates (ArrayRef< UpdateT > AllUpdates, SmallVectorImpl< UpdateT > &Result)
 
static void ApplyNextUpdate (DomTreeT &DT, BatchUpdateInfo &BUI)
 
static bool VerifyLevels (const DomTreeT &DT)
 
static bool VerifyDFSNumbers (const DomTreeT &DT)
 

Public Attributes

std::vector< NodePtrNumToNode = {nullptr}
 
DenseMap< NodePtr, InfoRecNodeToInfo
 
BatchUpdateInfoBatchUpdates
 

Static Public Attributes

static constexpr bool IsPostDom = DomTreeT::IsPostDominator
 

Detailed Description

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

Definition at line 50 of file GenericDomTree.h.

Member Typedef Documentation

◆ BatchUpdatePtr

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

Definition at line 93 of file GenericDomTreeConstruction.h.

◆ NodePtr

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

Definition at line 52 of file GenericDomTreeConstruction.h.

◆ NodeT

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

Definition at line 53 of file GenericDomTreeConstruction.h.

◆ RootsT

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

Definition at line 55 of file GenericDomTreeConstruction.h.

◆ TreeNodePtr

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

Definition at line 54 of file GenericDomTreeConstruction.h.

◆ UpdateT

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

Definition at line 73 of file GenericDomTreeConstruction.h.

Constructor & Destructor Documentation

◆ SemiNCAInfo()

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

Definition at line 96 of file GenericDomTreeConstruction.h.

Member Function Documentation

◆ addVirtualRoot()

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

◆ AlwaysDescend()

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

◆ ApplyNextUpdate()

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

◆ ApplyUpdates()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::ApplyUpdates ( DomTreeT &  DT,
ArrayRef< UpdateT Updates 
)
inlinestatic

◆ attachNewSubtree()

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

◆ CalculateFromScratch()

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

◆ clear()

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

◆ ComputeUnreachableDominators()

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

◆ DeleteEdge()

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

◆ DeleteReachable()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::DeleteReachable ( DomTreeT &  DT,
const BatchUpdatePtr  BUI,
const TreeNodePtr  FromTN,
const TreeNodePtr  ToTN 
)
inlinestatic

◆ DeleteUnreachable()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::DeleteUnreachable ( DomTreeT &  DT,
const BatchUpdatePtr  BUI,
const TreeNodePtr  ToTN 
)
inlinestatic

◆ doFullDFSWalk()

template<typename DomTreeT >
template<typename DescendCondition >
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::doFullDFSWalk ( const DomTreeT &  DT,
DescendCondition  DC 
)
inline

◆ EraseNode()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::EraseNode ( DomTreeT &  DT,
const TreeNodePtr  TN 
)
inlinestatic

◆ eval()

template<typename DomTreeT >
NodePtr llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::eval ( NodePtr  VIn,
unsigned  LastLinked 
)
inline

◆ FindRoots()

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

◆ GetEntryNode()

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

◆ getIDom()

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

◆ getNodeForBlock()

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

◆ HasForwardSuccessors()

template<typename DomTreeT >
static bool llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::HasForwardSuccessors ( const NodePtr  N,
BatchUpdatePtr  BUI 
)
inlinestatic

◆ HasProperSupport()

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

◆ InsertEdge()

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

◆ InsertReachable()

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

◆ InsertUnreachable()

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

◆ LegalizeUpdates()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::LegalizeUpdates ( ArrayRef< UpdateT AllUpdates,
SmallVectorImpl< UpdateT > &  Result 
)
inlinestatic

◆ reattachExistingSubtree()

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

◆ RemoveRedundantRoots()

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

◆ runDFS()

template<typename DomTreeT >
template<bool IsReverse = false, typename DescendCondition >
unsigned llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::runDFS ( NodePtr  V,
unsigned  LastNum,
DescendCondition  Condition,
unsigned  AttachToNum 
)
inline

◆ runSemiNCA()

template<typename DomTreeT >
void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::runSemiNCA ( DomTreeT &  DT,
const unsigned  MinLevel = 0 
)
inline

◆ UpdateInsertion()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateInsertion ( DomTreeT &  DT,
const BatchUpdatePtr  BUI,
const TreeNodePtr  NCD,
InsertionInfo II 
)
inlinestatic

◆ UpdateLevelsAfterInsertion()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::UpdateLevelsAfterInsertion ( InsertionInfo II)
inlinestatic

◆ UpdateRootsAfterUpdate()

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

◆ UpdateRootsBeforeInsertion()

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

◆ VerifyDFSNumbers()

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

◆ VerifyLevels()

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

◆ verifyParentProperty()

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

◆ verifyReachability()

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

◆ verifyRoots()

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

◆ verifySiblingProperty()

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

◆ VisitInsertion()

template<typename DomTreeT >
static void llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::VisitInsertion ( DomTreeT &  DT,
const BatchUpdatePtr  BUI,
const TreeNodePtr  TN,
const unsigned  RootLevel,
const TreeNodePtr  NCD,
InsertionInfo II 
)
inlinestatic

Member Data Documentation

◆ BatchUpdates

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

Definition at line 92 of file GenericDomTreeConstruction.h.

◆ IsPostDom

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

◆ NodeToInfo

template<typename DomTreeT >
DenseMap<NodePtr, InfoRec> llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NodeToInfo

Definition at line 71 of file GenericDomTreeConstruction.h.

◆ NumToNode

template<typename DomTreeT >
std::vector<NodePtr> llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::NumToNode = {nullptr}

Definition at line 70 of file GenericDomTreeConstruction.h.


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