LLVM  9.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::Compare
 

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

Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly faster than Simple Lengauer-Tarjan in practice.

O(n^2) worst cases happen when the computation of nearest common ancestors requires O(n) average time, which is very unlikely in real world. If this ever turns out to be an issue, consider implementing a hybrid algorithm.

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 47 of file GenericDomTreeConstruction.h.