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/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/CFGDiff.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>

Go to the source code of this file.

Classes
class	llvm::DomTreeNodeBase< NodeT >
	Base class for the actual dominator tree node. More...
struct	llvm::DomTreeNodeTraits< NodeT >
	Default DomTreeNode traits for NodeT. More...
class	llvm::DominatorTreeBase< NodeT, IsPostDom >
	Core dominator tree base class. More...

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.
namespace	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, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
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, either NodeRef->getParent() must return the parent node that is also a pointer or DomTreeNodeTraits needs to be specialized.

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

Definition in file GenericDomTree.h.