Computes post-dominator tree and post-dominance frontiers of a digraph using the Lengauer-Tarjan algorithm on the reversed graph. More...

#include <Dominators.H>

Collaboration diagram for Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >:

[legend]

Public Member Functions
	Lengauer_Tarjan_Post_Dominators (SA __sa=SA()) noexcept
	Construct a post-dominator computation instance.

	Lengauer_Tarjan_Post_Dominators (const Lengauer_Tarjan_Post_Dominators &)=delete
	Post-dominator instances should not be copied (they hold internal state)

Lengauer_Tarjan_Post_Dominators &	operator= (const Lengauer_Tarjan_Post_Dominators &)=delete

	Lengauer_Tarjan_Post_Dominators (Lengauer_Tarjan_Post_Dominators &&)=default
	Move is allowed.

Lengauer_Tarjan_Post_Dominators &	operator= (Lengauer_Tarjan_Post_Dominators &&)=default

DynList< std::pair< Node , Node > >	compute_ipdom (const GT &g, Node *exit_node)
	Compute immediate post-dominators.

void	build_tree (const GT &g, Node *exit_node, GT &tree)
	Build the post-dominator tree as a separate graph.

Node *	get_ipdom (const GT &g, Node exit_node, Node node)
	Get the immediate post-dominator of a specific node.

bool	post_dominates (const GT &g, Node exit_node, Node d, Node *v)
	Test whether node d post-dominates node v.

DynMapTree< Node , DynSetTree< Node > >	post_dominance_frontiers (const GT &g, Node *exit_node)
	Compute post-dominance frontiers for all reachable nodes.

void	operator() (const GT &g, Node *exit_node, GT &tree)
	Build post-dominator tree (operator() alias).

Accessors
SA &	get_filter () noexcept
	Get the arc filter.

const SA &	get_filter () const noexcept
	Get the arc filter (const).

bool	has_computation () const noexcept
	Check if a computation has been performed.

GT *	get_graph () const noexcept
	Get the graph of the last computation.

Node *	get_exit () const noexcept
	Get the exit node of the last computation.

Private Types
using	Node = typename GT::Node

using	Arc = typename GT::Arc

Private Member Functions
Node *	to_rev (Node *orig) const
	Map original node to reversed graph node.

Node *	to_orig (Node *rev_n) const
	Map reversed graph node to original node.

void	ensure_computed (const GT &g, Node *exit_node)
	Ensure computation is up to date.

Private Attributes
SA	sa

GT	rev

Lengauer_Tarjan_Dominators< GT, SA >	dom

GT *	gptr = nullptr

Node *	exit_ptr = nullptr

bool	is_computed = false

DynMapTree< Node , Node >	orig_to_rev

DynMapTree< Node , Node >	rev_to_orig

Detailed Description

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
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.

A node d post-dominates v if every path from v to a designated exit node passes through d. The post-dominator tree is the dominator tree of the reversed graph rooted at the exit node.

This class internally inverts the digraph with invert_digraph() and runs Lengauer_Tarjan_Dominators on the result. Results are transparently mapped back to the original graph nodes.

The class caches its computation: calling multiple methods with the same graph and exit node reuses the previous result without recomputing.

Template Parameters

GT	The directed graph type.
SA	Arc filter class for the internal iterator.

Complexity

Operation	Time	Space
Post-dominator tree	O(E * alpha(V))	O(V + E)

| Post-dominance frontiers | O(V + E) additional | O(V + |PDF|) |

Applications

Control dependence graph (CDG) construction
Program dependence graph (PDG) construction
Compiler optimization and code motion

Note: This class creates an internal copy of the reversed graph.

Warning: This class is NOT thread-safe.

See also: Lengauer_Tarjan_Dominators

Definition at line 730 of file Dominators.H.

Member Typedef Documentation

◆ Arc

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::Arc = typename GT::Arc

private

Definition at line 735 of file Dominators.H.

◆ Node

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

using Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::Node = typename GT::Node

private

Definition at line 734 of file Dominators.H.

Constructor & Destructor Documentation

◆ Lengauer_Tarjan_Post_Dominators() [1/3]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::Lengauer_Tarjan_Post_Dominators ( SA __sa = SA() )

inlinenoexcept

Construct a post-dominator computation instance.

Parameters

__sa	Arc filter functor. Defaults to Dft_Show_Arc<GT>.

Definition at line 812 of file Dominators.H.

◆ Lengauer_Tarjan_Post_Dominators() [2/3]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::Lengauer_Tarjan_Post_Dominators ( const Lengauer_Tarjan_Post_Dominators< GT, SA > & )

delete

Post-dominator instances should not be copied (they hold internal state)

◆ Lengauer_Tarjan_Post_Dominators() [3/3]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::Lengauer_Tarjan_Post_Dominators ( Lengauer_Tarjan_Post_Dominators< GT, SA > && )

default

Move is allowed.

Member Function Documentation

◆ build_tree()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::build_tree	(	const GT &	g,
		Node *	exit_node,
		GT &	tree
	)

inline

Build the post-dominator tree as a separate graph.

Creates a new directed graph tree where each node that can reach the exit in the original graph is represented, and arcs go from ipdom to child. Nodes are mapped via NODE_COOKIE between the original graph and the tree.

Parameters

	g	The directed graph.
	exit_node	Exit node.
[out]	tree	Output post-dominator tree (cleared first).

Exceptions

std::domain_error If exit_node is null.

Definition at line 870 of file Dominators.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::clear_graph(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::dom, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::ensure_computed(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), GraphCommon< GT, Node, Arc >::map_nodes(), NODE_COOKIE, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::rev, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::to_orig(), and Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::to_rev().

◆ compute_ipdom()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

DynList< std::pair< Node , Node > > Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::compute_ipdom	(	const GT &	g,
		Node *	exit_node
	)

inline

Compute immediate post-dominators.

Returns a list of (node, ipdom) pairs for every node that can reach the exit node. The exit node's ipdom is nullptr.

Parameters

g	The directed graph.
exit_node	Exit node for post-dominator computation.

Returns: List of (node, immediate_post_dominator) pairs.

Exceptions

std::domain_error If exit_node is null.

Definition at line 840 of file Dominators.H.

References Aleph::DynList< T >::append(), Aleph::blossom_maximum_cardinality_matching(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::dom, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::ensure_computed(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::rev, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::to_orig(), and Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::to_rev().

Referenced by main().

◆ ensure_computed()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::ensure_computed	(	const GT &	g,
		Node *	exit_node
	)

inlineprivate

Ensure computation is up to date.

Inverts the graph and runs dominator computation on the reversed graph from the exit node.

Note: invert_digraph creates a new graph with fresh Arc objects. If the arc filter SA depends on the identity (address) of the original arcs, it will fail or filter incorrectly on the reversed graph. Stateless filters (like Dft_Show_Arc) or those depending only on Node identities are safe.

Parameters

g	The directed graph.
exit_node	Exit node (must not be null).

Definition at line 776 of file Dominators.H.

Referenced by Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::build_tree(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::compute_ipdom(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::get_ipdom(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::post_dominance_frontiers(), and Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::post_dominates().

◆ get_exit()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Node * Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::get_exit ( ) const

inlinenoexcept

Get the exit node of the last computation.

Definition at line 1022 of file Dominators.H.

References Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::exit_ptr.

◆ get_filter() [1/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

const SA & Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::get_filter ( ) const

inlinenoexcept

Get the arc filter (const).

Definition at line 1013 of file Dominators.H.

References Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::sa.

◆ get_filter() [2/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

SA & Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::get_filter ( )

inlinenoexcept

Get the arc filter.

Definition at line 1010 of file Dominators.H.

References Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::sa.

◆ get_graph()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

GT * Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::get_graph ( ) const

inlinenoexcept

Get the graph of the last computation.

Definition at line 1019 of file Dominators.H.

References Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::gptr.

◆ get_ipdom()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Node * Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::get_ipdom	(	const GT &	g,
		Node *	exit_node,
		Node *	node
	)

inline

Get the immediate post-dominator of a specific node.

Parameters

g	The directed graph.
exit_node	Exit node.
node	The node whose ipdom is queried.

Returns: Pointer to the immediate post-dominator, or nullptr if node is the exit or cannot reach the exit.

Exceptions

std::domain_error If exit_node or node is null.

Definition at line 919 of file Dominators.H.

References ah_domain_error_if, Aleph::blossom_maximum_cardinality_matching(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::dom, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::ensure_computed(), Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::rev, Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::to_orig(), and Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::to_rev().

◆ has_computation()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::has_computation ( ) const

inlinenoexcept

Check if a computation has been performed.

Definition at line 1016 of file Dominators.H.

References Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::is_computed.

◆ operator()()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

void Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::operator()	(	const GT &	g,
		Node *	exit_node,
		GT &	tree
	)

inline

Build post-dominator tree (operator() alias).

Parameters

	g	The directed graph.
	exit_node	Exit node.
[out]	tree	Output post-dominator tree.

Definition at line 1001 of file Dominators.H.

References Aleph::blossom_maximum_cardinality_matching(), and build_tree().

◆ operator=() [1/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Lengauer_Tarjan_Post_Dominators & Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::operator= ( const Lengauer_Tarjan_Post_Dominators< GT, SA > & )

delete

◆ operator=() [2/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Lengauer_Tarjan_Post_Dominators & Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::operator= ( Lengauer_Tarjan_Post_Dominators< GT, SA > && )

default

◆ post_dominance_frontiers()

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

DynMapTree< Node , DynSetTree< Node > > Aleph::Lengauer_Tarjan_Post_Dominators< GT, SA >::post_dominance_frontiers	(	const GT &	g,
		Node *	exit_node
	)

inline

Compute post-dominance frontiers for all reachable nodes.

The post-dominance frontier PDF(x) of a node x is the set of nodes y where x post-dominates a successor of y but does not strictly post-dominate y. This is the key data structure for constructing the control dependence graph (CDG).

Parameters