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<class GT, class 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 728 of file Dominators.H.

Member Typedef Documentation

◆ Arc

template<class GT , class SA = Dft_Show_Arc<GT>>

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

private

Definition at line 733 of file Dominators.H.

◆ Node

template<class GT , class SA = Dft_Show_Arc<GT>>

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

private

Definition at line 732 of file Dominators.H.

Constructor & Destructor Documentation

◆ Lengauer_Tarjan_Post_Dominators() [1/3]

template<class GT , class 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 810 of file Dominators.H.

◆ Lengauer_Tarjan_Post_Dominators() [2/3]

template<class GT , class 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<class GT , class 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<class GT , class 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 868 of file Dominators.H.

References Aleph::clear_graph(), Aleph::divide_and_conquer_partition_dp(), 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<class GT , class 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 838 of file Dominators.H.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), 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<class GT , class 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 774 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<class GT , class 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 1020 of file Dominators.H.

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

◆ get_filter() [1/2]

template<class GT , class 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 1011 of file Dominators.H.

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

◆ get_filter() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

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

inlinenoexcept

Get the arc filter.

Definition at line 1008 of file Dominators.H.

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

◆ get_graph()

template<class GT , class 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 1017 of file Dominators.H.

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

◆ get_ipdom()

template<class GT , class 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 917 of file Dominators.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), 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<class GT , class 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 1014 of file Dominators.H.

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

◆ operator()()

template<class GT , class 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 999 of file Dominators.H.

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

◆ operator=() [1/2]

template<class GT , class 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<class GT , class 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<class GT , class 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