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

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 >::BlockNamePrinter
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertionInfo
struct	llvm::DomTreeBuilder::SemiNCAInfo< DomTreeT >::InsertionInfo::Compare

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.
namespace	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, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
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:

[1] 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 that uses SLT to perform full constructions and SemiNCA for incremental updates.

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

[2] 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 49 of file GenericDomTreeConstruction.h.