LLVM  16.0.0git
Classes | Namespaces | Macros | Functions
GenericDomTreeConstruction.h File Reference
#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 <optional>
#include <queue>
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.


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


 This is an optimization pass for GlobalISel generic memory operations.


#define DEBUG_TYPE   "dom-tree-builder"


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


#define DEBUG_TYPE   "dom-tree-builder"

Definition at line 50 of file GenericDomTreeConstruction.h.