GenericDomTree.h File Reference

This file defines a set of templates that efficiently compute a dominator tree over a generic graph. More...

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/CFGUpdate.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>

Include dependency graph for GenericDomTree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	llvm::DominatorTreeBase< NodeT, IsPostDom >
	Core dominator tree base class. More...
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >
class	llvm::DomTreeNodeBase< NodeT >
	Base class for the actual dominator tree node. More...
class	llvm::DominatorTreeBase< NodeT, IsPostDom >
	Core dominator tree base class. More...

Namespaces
	llvm
	This class represents lattice values for constants.
	llvm::DomTreeBuilder

Typedefs
template<typename T >
using	llvm::DomTreeBase = DominatorTreeBase< T, false >
template<typename T >
using	llvm::PostDomTreeBase = DominatorTreeBase< T, true >

Functions
template<class NodeT >
raw_ostream &	llvm::operator<< (raw_ostream &O, const DomTreeNodeBase< NodeT > *Node)
template<class NodeT >
void	llvm::PrintDomTree (const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)
template<typename DomTreeT >
void	llvm::DomTreeBuilder::Calculate (DomTreeT &DT)
template<typename DomTreeT >
void	llvm::DomTreeBuilder::CalculateWithUpdates (DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
template<typename DomTreeT >
void	llvm::DomTreeBuilder::InsertEdge (DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
template<typename DomTreeT >
void	llvm::DomTreeBuilder::DeleteEdge (DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
template<typename DomTreeT >
void	llvm::DomTreeBuilder::ApplyUpdates (DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
template<typename DomTreeT >
bool	llvm::DomTreeBuilder::Verify (const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)

Detailed Description

This file defines a set of templates that efficiently compute a dominator tree over a generic graph.

This is used typically in LLVM for fast dominance queries on the CFG, but is fully generic w.r.t. the underlying graph types.

Unlike ADT/* graph algorithms, generic dominator tree has more requirements on the graph's NodeRef. The NodeRef should be a pointer and, NodeRef->getParent() must return the parent node that is also a pointer.

FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.

Definition in file GenericDomTree.h.