dom_info Struct Reference
Collaboration diagram for dom_info:
Data Fields | |
| TBB * | dfs_parent |
| TBB * | key |
| TBB * | path_min |
| TBB * | bucket |
| TBB * | next_bucket |
| TBB * | dom |
| TBB * | set_chain |
| unsigned int * | set_size |
| TBB * | set_child |
| TBB * | dfs_order |
| basic_block * | dfs_to_bb |
| unsigned int | dfsnum |
| unsigned int | nodes |
| bitmap | fake_exit_edge |
Detailed Description
We work in a poor-mans object oriented fashion, and carry an instance of this structure through all our 'methods'. It holds various arrays reflecting the (sub)structure of the flowgraph. Most of them are of type TBB and are also indexed by TBB.
Field Documentation
| TBB* dom_info::bucket |
bucket[x] points to the first node of the set of nodes having x as key.
| TBB* dom_info::dfs_order |
If b is the number of a basic block (BB->index), 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.
| TBB* dom_info::dfs_parent |
The parent of a node in the DFS tree.
Referenced by link_roots().
| basic_block* dom_info::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. Note, that in our structure there are
more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
is true for every basic block bb, but not the opposite.
Referenced by link_roots().
| unsigned int dom_info::dfsnum |
This is the next free DFS number when creating the DFS tree.
| TBB* dom_info::dom |
After the algorithm is done, dom[x] contains the immediate dominator
of x.
| bitmap dom_info::fake_exit_edge |
Blocks with bits set here have a fake edge to EXIT. These are used
to turn a DFS forest into a proper tree.
Referenced by init_dom_info(), and link_roots().
| TBB* dom_info::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. Such a node is also called
semidominator.
Referenced by compress().
| TBB* dom_info::next_bucket |
And next_bucket[x] points to the next node.
| unsigned int dom_info::nodes |
The number of nodes in the DFS tree (==dfsnum-1).
| TBB* dom_info::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].
Referenced by compress().
| TBB* dom_info::set_chain |
The following few fields implement the structures needed for disjoint
sets. set_chain[x] is the next node on the path from x to the representative
of the set containing x. If set_chain[x]==0 then x is a root.
Referenced by compress().
| TBB* dom_info::set_child |
set_child[x] is used for balancing the tree representing a set. It can
be understood as the next sibling of x.
Referenced by compress().
| unsigned int* dom_info::set_size |
set_size[x] is the number of elements in the set named by x.
Referenced by compress().
The documentation for this struct was generated from the following file:
