Dominators.H File Reference

Dominator and post-dominator tree computation via the Lengauer-Tarjan algorithm. More...

#include <utility>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>
#include <tpl_array.H>
#include <htlist.H>
#include <tpl_dynListStack.H>
#include <ah-errors.H>
#include <tpl_dynSetTree.H>

Include dependency graph for Dominators.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Lengauer_Tarjan_Dominators< GT, SA >
	Computes dominator tree and dominance frontiers of a digraph using the Lengauer-Tarjan algorithm. More...
class	Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >
	Computes post-dominator tree and post-dominance frontiers of a digraph using the Lengauer-Tarjan algorithm on the reversed graph. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< std::pair< typename GT::Node *, typename GT::Node * > >	Aleph::compute_dominators (GT &g, typename GT::Node *root, SA sa=SA())
	Compute immediate dominators of a digraph from a root node.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::build_dominator_tree (GT &g, typename GT::Node *root, GT &tree, SA sa=SA())
	Build the dominator tree of a digraph.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynMapTree< typename GT::Node *, DynSetTree< typename GT::Node * > >	Aleph::compute_dominance_frontiers (GT &g, typename GT::Node *root, SA sa=SA())
	Compute dominance frontiers of a digraph.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< std::pair< typename GT::Node *, typename GT::Node * > >	Aleph::compute_post_dominators (const GT &g, typename GT::Node *exit_node, SA sa=SA())
	Compute immediate post-dominators of a digraph from an exit node.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::build_post_dominator_tree (const GT &g, typename GT::Node *exit_node, GT &tree, SA sa=SA())
	Build the post-dominator tree of a digraph.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynMapTree< typename GT::Node *, DynSetTree< typename GT::Node * > >	Aleph::compute_post_dominance_frontiers (const GT &g, typename GT::Node *exit_node, SA sa=SA())
	Compute post-dominance frontiers of a digraph.

Detailed Description

Dominator and post-dominator tree computation via the Lengauer-Tarjan algorithm.

This file implements the Lengauer-Tarjan algorithm for computing immediate dominators and the dominator tree of a directed graph from a given root node, in O(E * alpha(V)) time. It also provides post-dominator computation by running the same algorithm on the reversed graph from a designated exit node.

Definitions

• A node d dominates v if every path from the root to v passes through d.
• The immediate dominator (idom) of v is the closest strict dominator of v.
• The dominator tree has an edge from idom(v) to v for each non-root reachable node.
• The dominance frontier DF(x) is the set of nodes y such that x dominates a predecessor of y but does not strictly dominate y. Dominance frontiers are essential for SSA construction in compilers.

Algorithm Overview

The Lengauer-Tarjan algorithm uses a single DFS traversal followed by semi-dominator computation with a Union-Find structure with path compression:

1. DFS: Number nodes in DFS order, record DFS tree parent.
2. Semi-dominators: Process nodes in reverse DFS order. For each node, examine predecessors via incoming arcs and compute the semi-dominator using EVAL/LINK on the Union-Find forest.
3. Immediate dominators: Forward pass resolving deferred idom values.

Complexity

Operation	Time	Space
Dominator tree	O(E * alpha(V))	O(V)

| Dominance frontiers | O(V + E) additional | O(V + |DF|) |

Applications

• SSA form construction in optimizing compilers
• Control-flow analysis and optimization
• Program dependence graph construction
• Loop detection and nesting analysis

Usage Example

List_Digraph<Graph_Node<std::string>, Graph_Arc<int>> cfg;
// ... build control-flow graph ...
auto root = cfg.get_first_node();
 
// Get immediate dominators as (node, idom) pairs
auto idoms = compute_dominators(cfg, root);
 
// Build dominator tree as a separate graph
decltype(cfg) dom_tree;
build_dominator_tree(cfg, root, dom_tree);
 
// Compute dominance frontiers for SSA construction
auto df = compute_dominance_frontiers(cfg, root);

See also

Tarjan.H Strongly connected components (same DFS-based family)

topological_sort.H Topological ordering for DAGs

Author

Leandro Rabindranath León

Definition in file Dominators.H.