LLVM  6.0.0svn
Classes | Namespaces | Macros | Functions
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
 Compute iterated dominance frontiers using a linear time algorithm.
 
 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::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

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.