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.
Referenced by determine_dominators_for_sons().
| 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:
