LLVM  6.0.0svn
Classes | Namespaces | Typedefs | Enumerations | Functions
GenericDomTree.h File Reference

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

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>
#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/raw_ostream.h"
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...
 
struct  llvm::DomTreeBuilder::Update< NodePtr >
 
class  llvm::DominatorTreeBase< NodeT, IsPostDom >
 Core dominator tree base class. More...
 

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 
 llvm::DomTreeBuilder
 

Typedefs

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

Enumerations

enum  llvm::DomTreeBuilder::UpdateKind : unsigned char { llvm::DomTreeBuilder::UpdateKind::Insert, llvm::DomTreeBuilder::UpdateKind::Delete }
 

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::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)
 

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.