LLVM 19.0.0git
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 "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.