GenericDomTreeConstruction.h File Reference

#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/GenericDomTree.h"

Include dependency graph for GenericDomTreeConstruction.h:

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

Go to the source code of this file.

Namespaces
namespace	llvm
	List of target independent CodeGen pass IDs.
Functions
template<class GraphT >
unsigned	llvm::DFSPass (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *V, unsigned N)
template<class GraphT >
GraphT::NodeType *	llvm::Eval (DominatorTreeBase< typename GraphT::NodeType > &DT, typename GraphT::NodeType *VIn, unsigned LastLinked)
template<class FuncT , class NodeT >
void	llvm::Calculate (DominatorTreeBase< typename GraphTraits< NodeT >::NodeType > &DT, FuncT &F)

---

Detailed Description

Generic dominator tree construction - This file provides routines to construct immediate dominator information for a flow-graph based on the algorithm described in this document:

A Fast Algorithm for Finding Dominators in a Flowgraph T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141.

This implements the O(n*log(n)) versions of EVAL and LINK, because it turns out that the theoretically slower O(n*log(n)) implementation is actually faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.

Definition in file GenericDomTreeConstruction.h.