GenericDomTreeConstruction.h File Reference

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

#include <queue>
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Debug.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.

Classes
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InfoRec
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BatchUpdateInfo
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::ChildrenGetter< Inverse >
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::BlockNamePrinter
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertionInfo
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertionInfo::DecreasingLevel

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

Macros
#define	DEBUG_TYPE   "dom-tree-builder"

Functions
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

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

Linear-Time Algorithms for Dominators and Related Problems Loukas Georgiadis, Princeton University, November 2005, pp. 21-23: ftp://ftp.cs.princeton.edu/reports/2005/737.pdf

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.

The file uses the Depth Based Search algorithm to perform incremental updates (insertion and deletions). The implemented algorithm is based on this publication:

An Experimental Study of Dynamic Dominators Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10: https://arxiv.org/pdf/1604.02711.pdf

Definition in file GenericDomTreeConstruction.h.

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "dom-tree-builder"

Definition at line 45 of file GenericDomTreeConstruction.h.