next up previous contents
Next: Register Coalescing Pass Up: Optimization passes Previous: Loop Optimizer   Contents

Subsections

ET-Trees

We used ET-trees for maintaining dominance information in loop optimizer. ET-tree is a data structure for representing trees. It offers logarithmic time for standard tree operations (insert, remove, link, cut) and poly-logarithmic time for finding common ancestor of two nodes.

The tree is represented by a sequence of symbols obtained by calling algorithm [*] on root node.


\begin{algorithm} % latex2html id marker 1404\caption{dfs (node)}\begin{algori... ...$c$), $node$)} \ENDFOR \STATE{{\bf return} $s$} \end{algorithmic}\end{algorithm}

Such sequences are called Eulerian Tours, hence the name of the structure. For example, for tree on figure [*], the corresponding ET-sequence is 1,2,1,3,4,5,4,6,4,3,1.

Figure: A tree with ET-sequence 1,2,1,3,4,5,4,6,4,3,1
\scalebox{1.0}{ \includegraphics{et-tree1.ps}}

Because it's inefficient to maintain these sequences as strings, slightly different approach is used -- the sequence itself is represented by a binary tree, where the represented sequence is obtained by reading the values of the nodes from left to right.

For example, two possible encodings of the above sequence are shown in figure [*].

Figure: Two possible encodings of the above sequence.
\scalebox{0.9}{ \includegraphics{et-tree2.ps}}

In our implementation, we have chosen splay-trees as the sequence representation, with some modifications:

  1. All occurrences of the same node are linked from left to right, this allows faster implementation of remove.
  2. Because node values can be of any type, a hashtable is used to convert node values to appropriate internal representation.

There are two data types for representing nodes -- et_forest_occurrence and et_forest_node. et_forest_occurrence represents the occurrences of the nodes in tree (therefore, these nodes form the splay-tree). It contains informations for the splay-tree (parent node, left son, right son), pointer to the next occurrence of the same node, and number of nodes in left and right subtree (this is used for comparison whether an occurrence is before another one, or not). et_forest_node represents each node. It contains pointers to the first and last occurrences of the node and the node value. The et_forest_t is then simply a hashtable converting node value to appropriate et_forest_node.

Implementation of of tree operations

  1. Insertion of new node is trivial -- we simply create a node with one occurrence.
  2. Insertion of an edge -- we splay first occurrences of both nodes, create new occurrence of parent node and link them together as shown in figure [*].

    Figure: Insertion of edge (p,c).
    \scalebox{1.0}{ \includegraphics{et-tree3.ps}}

  3. Removal of a node -- We simply remove edges to child nodes and possibly the edge to parent node and then dispose the node with single occurrence.
  4. Removal of an edge -- Because we know that the occurrences before the first occurrence of child node and after the last occurrence of child node belongs to parent node, we cut the sequence using two splays and one join, removing one occurrence of parent node, as shown in figure [*].

    Figure: Deletion of edge (p,c).
    \scalebox{1.0}{ \includegraphics{et-tree4.ps}}

  5. Nearest common ancestor of two nodes is calculated by algorithm [*].
    \begin{algorithm} % latex2html id marker 1455\caption{nearest common ancestor ... ...e)$} \ENDWHILE \STATE{{\bf return} $candidate$} \end{algorithmic}\end{algorithm}
  6. Splay trees are well known and therefore not covered here.
next up previous contents
Next: Register Coalescing Pass Up: Optimization passes Previous: Loop Optimizer   Contents
Jan Hubicka 2003-05-04