Store the intermediate information used to compute dominator or post dominator information. More...

#include <Dominance.hpp>

Collaboration diagram for dom_info< GraphObj >:

Public Member Functions
	dom_info (const GraphObj &_g, const Vertex &_en_block, const Vertex &_ex_block, const ParameterConstRef param)
	Constructor. More...

void	calc_dfs_tree (bool reverse)
	The main entry for calculating the DFS tree or forest. More...

void	calc_idoms (bool reverse)
	This calculates the immediate dominators (or post-dominators if REVERSE is true). More...

void	fill_dom_map (CustomUnorderedMapStable< Vertex, Vertex > &dom_map)
	fill the dominator map after its computation More...

Private Types
using	Vertex = typename boost::graph_traits< const GraphObj >::vertex_descriptor
	The algorithm uses two different indices for each Vertex: a generic index given by boost and the index in the dfs search. More...

using	in_edge_iterator = typename boost::graph_traits< const GraphObj >::in_edge_iterator
	edge_iterator definition. More...

using	out_edge_iterator = typename boost::graph_traits< const GraphObj >::out_edge_iterator
	edge_iterator definition. More...

using	edge = typename boost::graph_traits< const GraphObj >::edge_descriptor
	edge definition. More...

using	Vertex_iterator = typename boost::graph_traits< const GraphObj >::vertex_iterator
	Vertex iterator definition. More...

Private Member Functions
void	calc_dfs_tree_rec (Vertex bb)
	The recursive variant of creating a DFS tree. More...

void	compress (TBB v)
	Compress the path from V to the root of its set and update path_min at the same time. More...

TBB	eval (TBB v)
	Compress the path from V to the set root of V if needed (when the root has changed since the last call). More...

void	link_roots (TBB v, TBB w)
	This essentially merges the two sets of V and W, giving a single set with the new root V. More...

Private Attributes
std::vector< TBB >	dfs_parent
	The parent of a node in the DFS tree. More...

std::vector< TBB >	key
	For a node x key[x] is roughly the node nearest to the root from which exists a way to x only over nodes behind x. More...

std::vector< TBB >	path_min
	The value in path_min[x] is the node y on the path from x to the root of the tree x is in with the smallest key[y]. More...

std::vector< TBB >	bucket
	bucket[x] points to the first node of the set of nodes having x as key. More...

std::vector< TBB >	next_bucket
	And next_bucket[x] points to the next node. More...

std::vector< TBB >	set_chain
	set_chain[x] is the next node on the path from x to the representant of the set containing x. More...

std::vector< unsigned int >	set_size
	set_size[x] is the number of elements in the set named by x. More...

std::vector< TBB >	set_child
	set_child[x] is used for balancing the tree representing a set. More...

unsigned int	dfsnum
	This is the next free DFS number when creating the DFS tree. More...

unsigned int	nodes
	The number of nodes in the DFS tree (==dfsnum-1). More...

CustomOrderedSet< TBB >	fake_exit_edge
	Blocks with bits set here have a fake edge to EXIT. More...

const unsigned long int	last_basic_block
	index of the last basic block More...

const Vertex &	en_block
	Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward problem). More...

const Vertex &	ex_block
	Ending block. More...

const GraphObj &	g
	Flow graph reference. More...

std::vector< TBB >	dom
	After the algorithm is done, dom[x] contains the immediate dominator of x. More...

std::vector< TBB >	dfs_order
	If b is the number of a basic block (index_map[bb_Vertex]), dfs_order[b] is the number of that node in DFS order counted from 1. More...

std::vector< Vertex >	dfs_to_bb
	If x is the DFS-index of a node which corresponds with a basic block, dfs_to_bb[x] is that basic block. More...

std::map< Vertex, size_t >	index_map
	index map putting into relation vertices and arbitrary indexes. More...

int	debug_level
	debug_level More...

Detailed Description

template<typename GraphObj>
class dom_info< GraphObj >

Store the intermediate information used to compute dominator or post dominator information.

It holds various arrays reflecting the (sub)structure of the flowgraph. Most of them are of type TBB and are also indexed by TBB.

Definition at line 91 of file Dominance.hpp.

Member Typedef Documentation

◆ edge

template<typename GraphObj>

using dom_info< GraphObj >::edge = typename boost::graph_traits<const GraphObj>::edge_descriptor

private

edge definition.

Definition at line 103 of file Dominance.hpp.

◆ in_edge_iterator

template<typename GraphObj>

using dom_info< GraphObj >::in_edge_iterator = typename boost::graph_traits<const GraphObj>::in_edge_iterator

private

edge_iterator definition.

Definition at line 99 of file Dominance.hpp.

◆ out_edge_iterator

template<typename GraphObj>

using dom_info< GraphObj >::out_edge_iterator = typename boost::graph_traits<const GraphObj>::out_edge_iterator

private

edge_iterator definition.

Definition at line 101 of file Dominance.hpp.

◆ Vertex

template<typename GraphObj>

using dom_info< GraphObj >::Vertex = typename boost::graph_traits<const GraphObj>::vertex_descriptor

private

The algorithm uses two different indices for each Vertex: a generic index given by boost and the index in the dfs search.

Definition of Vertex

Definition at line 97 of file Dominance.hpp.

◆ Vertex_iterator

template<typename GraphObj>

using dom_info< GraphObj >::Vertex_iterator = typename boost::graph_traits<const GraphObj>::vertex_iterator

private

Vertex iterator definition.

Definition at line 105 of file Dominance.hpp.

Constructor & Destructor Documentation

◆ dom_info()

template<typename GraphObj>

dom_info< GraphObj >::dom_info	(	const GraphObj &	_g,
		const Vertex &	_en_block,
		const Vertex &	_ex_block,
		const ParameterConstRef	param
	)

inline

Constructor.

Parameters

g	is the starting graph
en_block	is the entry block
ex_block	is the exit_block,
param	is the set of input parameters

Definition at line 340 of file Dominance.hpp.

Member Function Documentation

◆ calc_dfs_tree()

template<typename GraphObj>

void dom_info< GraphObj >::calc_dfs_tree ( bool reverse )

inline

The main entry for calculating the DFS tree or forest.

Parameters

reverse	is true, if we are interested in the reverse flow graph. In that case the result is not necessarily a tree but a forest, because there may be nodes from which the EXIT_BLOCK is unreachable.
source	is the ENTRY_BLOCK when reverse is false while it is the EXIT_BLOCK if reverse is true

Definition at line 381 of file Dominance.hpp.

References dom_info< GraphObj >::calc_dfs_tree_rec(), counter, DEBUG_LEVEL_VERY_PEDANTIC, dom_info< GraphObj >::dfsnum, dom_info< GraphObj >::en_block, INDENT_DBG_MEX, index, dom_info< GraphObj >::last_basic_block, and THROW_ASSERT.

Referenced by dominance< BBGraph >::calculate_dominance_info().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calc_dfs_tree_rec()

template<typename GraphObj>

void dom_info< GraphObj >::calc_dfs_tree_rec ( Vertex bb )

inlineprivate

The recursive variant of creating a DFS tree.

After this is done all nodes reachable from BB were visited, have assigned their dfs number and are linked together to form a tree.

Parameters

bb	is the basic block Vertex BB.

Definition at line 195 of file Dominance.hpp.

References DEBUG_LEVEL_VERY_PEDANTIC, INDENT_DBG_MEX, dom_info< GraphObj >::last_basic_block, and lenet_tvm::target.

Referenced by dom_info< GraphObj >::calc_dfs_tree().

Here is the caller graph for this function:

◆ calc_idoms()

template<typename GraphObj>

void dom_info< GraphObj >::calc_idoms ( bool reverse )

inline

This calculates the immediate dominators (or post-dominators if REVERSE is true).

On return the immediate dominator to node V is in dom[V].

Definition at line 482 of file Dominance.hpp.

References DEBUG_LEVEL_VERY_PEDANTIC, dom_info< GraphObj >::eval(), INDENT_DBG_MEX, k, dom_info< GraphObj >::last_basic_block, dom_info< GraphObj >::link_roots(), and dom_info< GraphObj >::nodes.

Referenced by dominance< BBGraph >::calculate_dominance_info().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compress()

template<typename GraphObj>

void dom_info< GraphObj >::compress ( TBB v )

inlineprivate

Compress the path from V to the root of its set and update path_min at the same time.

After compress(V) set_chain[V] is the root of the set V is in and path_min[V] is the node with the smallest key[] value on the path from V to that root.

Parameters

v	is the basic block ID of V.

Definition at line 242 of file Dominance.hpp.

Referenced by dom_info< GraphObj >::eval().

Here is the caller graph for this function:

◆ eval()

template<typename GraphObj>

TBB dom_info< GraphObj >::eval ( TBB v )

inlineprivate

Compress the path from V to the set root of V if needed (when the root has changed since the last call).

Returns the node with the smallest key[] value on the path from V to the root.

Parameters

v	is the basic block ID of V.

Definition at line 265 of file Dominance.hpp.

References dom_info< GraphObj >::compress().

Referenced by dom_info< GraphObj >::calc_idoms().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ fill_dom_map()

template<typename GraphObj>

void dom_info< GraphObj >::fill_dom_map ( CustomUnorderedMapStable< Vertex, Vertex > & dom_map )

inline

fill the dominator map after its computation

Parameters

dom_map is the dominator map.

Definition at line 606 of file Dominance.hpp.

References DEBUG_LEVEL_VERY_PEDANTIC, dom_info< GraphObj >::en_block, and INDENT_DBG_MEX.

Referenced by dominance< BBGraph >::calculate_dominance_info().

Here is the caller graph for this function:

◆ link_roots()

template<typename GraphObj>

void dom_info< GraphObj >::link_roots	(	TBB	v,
		TBB	w
	)

inlineprivate

This essentially merges the two sets of V and W, giving a single set with the new root V.

The internal representation of these disjoint sets is a balanced tree. Currently link(V,W) is only used with V being the parent of W.

Definition at line 299 of file Dominance.hpp.

Referenced by dom_info< GraphObj >::calc_idoms().

Here is the caller graph for this function:

Field Documentation

◆ bucket

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::bucket

private

bucket[x] points to the first node of the set of nodes having x as key.

Definition at line 122 of file Dominance.hpp.

◆ debug_level

template<typename GraphObj>

int dom_info< GraphObj >::debug_level

private

debug_level

Definition at line 187 of file Dominance.hpp.

◆ dfs_order

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::dfs_order

private

If b is the number of a basic block (index_map[bb_Vertex]), dfs_order[b] is the number of that node in DFS order counted from 1.

This is an index into most of the other arrays in this structure.

Definition at line 174 of file Dominance.hpp.

◆ dfs_parent

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::dfs_parent

private

The parent of a node in the DFS tree.

Definition at line 108 of file Dominance.hpp.

◆ dfs_to_bb

template<typename GraphObj>

std::vector<Vertex> dom_info< GraphObj >::dfs_to_bb

private

If x is the DFS-index of a node which corresponds with a basic block, dfs_to_bb[x] is that basic block.

Note, that in our structure there are more nodes that basic blocks, so only dfs_to_bb[dfs_order[index_map[bb]]]==bb is true for every basic block bb, but not the opposite.

Definition at line 181 of file Dominance.hpp.

◆ dfsnum

template<typename GraphObj>

unsigned int dom_info< GraphObj >::dfsnum

private

This is the next free DFS number when creating the DFS tree.

Definition at line 143 of file Dominance.hpp.

Referenced by dom_info< GraphObj >::calc_dfs_tree().

◆ dom

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::dom

private

After the algorithm is done, dom[x] contains the immediate dominator of x.

Definition at line 167 of file Dominance.hpp.

Referenced by dominance< BBGraph >::get_dominator_map().

◆ en_block

template<typename GraphObj>

const Vertex& dom_info< GraphObj >::en_block

private

Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward problem).

Definition at line 158 of file Dominance.hpp.

Referenced by dom_info< GraphObj >::calc_dfs_tree(), and dom_info< GraphObj >::fill_dom_map().

◆ ex_block

template<typename GraphObj>

const Vertex& dom_info< GraphObj >::ex_block

private

Ending block.

Definition at line 161 of file Dominance.hpp.

◆ fake_exit_edge

template<typename GraphObj>

CustomOrderedSet<TBB> dom_info< GraphObj >::fake_exit_edge

private

Blocks with bits set here have a fake edge to EXIT.

These are used to turn a DFS forest into a proper tree.

Definition at line 152 of file Dominance.hpp.

◆ g

template<typename GraphObj>

const GraphObj& dom_info< GraphObj >::g

private

Flow graph reference.

Definition at line 164 of file Dominance.hpp.

◆ index_map

template<typename GraphObj>

std::map<Vertex, size_t> dom_info< GraphObj >::index_map

private

index map putting into relation vertices and arbitrary indexes.

Definition at line 184 of file Dominance.hpp.

◆ key

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::key

private

For a node x key[x] is roughly the node nearest to the root from which exists a way to x only over nodes behind x.

Such a node is also called semidominator.

Definition at line 115 of file Dominance.hpp.

◆ last_basic_block

template<typename GraphObj>

const unsigned long int dom_info< GraphObj >::last_basic_block

private

index of the last basic block

Definition at line 155 of file Dominance.hpp.

Referenced by dom_info< GraphObj >::calc_dfs_tree(), dom_info< GraphObj >::calc_dfs_tree_rec(), and dom_info< GraphObj >::calc_idoms().

◆ next_bucket

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::next_bucket

private

And next_bucket[x] points to the next node.

Definition at line 125 of file Dominance.hpp.

◆ nodes

template<typename GraphObj>

unsigned int dom_info< GraphObj >::nodes

private

The number of nodes in the DFS tree (==dfsnum-1).

Definition at line 146 of file Dominance.hpp.

Referenced by dom_info< GraphObj >::calc_idoms().

◆ path_min

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::path_min

private

The value in path_min[x] is the node y on the path from x to the root of the tree x is in with the smallest key[y].

Definition at line 119 of file Dominance.hpp.

◆ set_chain

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::set_chain

private

set_chain[x] is the next node on the path from x to the representant of the set containing x.

If set_chain[x]==0 then x is a root. It's similar to a reversed link list

Definition at line 132 of file Dominance.hpp.

◆ set_child

template<typename GraphObj>

std::vector<TBB> dom_info< GraphObj >::set_child

private

set_child[x] is used for balancing the tree representing a set.

It can be understood as the next sibling of x.

Definition at line 140 of file Dominance.hpp.

◆ set_size

template<typename GraphObj>

std::vector<unsigned int> dom_info< GraphObj >::set_size

private

set_size[x] is the number of elements in the set named by x.

Definition at line 135 of file Dominance.hpp.

The documentation for this class was generated from the following file:

/workspace/src/algorithms/dominance/Dominance.hpp

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename GraphObj> class dom_info< GraphObj >

Member Typedef Documentation

◆ edge

◆ in_edge_iterator

◆ out_edge_iterator

◆ Vertex

◆ Vertex_iterator

Constructor & Destructor Documentation

◆ dom_info()

Member Function Documentation

◆ calc_dfs_tree()

◆ calc_dfs_tree_rec()

◆ calc_idoms()

◆ compress()

◆ eval()

◆ fill_dom_map()

◆ link_roots()

Field Documentation

◆ bucket

◆ debug_level

◆ dfs_order

◆ dfs_parent

◆ dfs_to_bb

◆ dfsnum

◆ dom

◆ en_block

◆ ex_block

◆ fake_exit_edge

◆ g

◆ index_map

◆ key

◆ last_basic_block

◆ next_bucket

◆ nodes

◆ path_min

◆ set_chain

◆ set_child

◆ set_size

template<typename GraphObj>
class dom_info< GraphObj >