12.83 util.dominator - Calculate dominator tree

Module: util.dominator ¶

Dominator tree is an auxiliary structure for control flow graphs. It is frequently used in the flow analysis of compilers, but also useful for handling general directed graphs.

Function: calculate-dominators start upstreams downstreams node-comparator ¶

{util.dominator} The four arguments represent a directed, possibly cyclic, graph. Here, we use Node to denote an abstract type of a node of the graph. It can be anything—the algorithm is oblivious on the actual type of nodes.

start :: Node

The start node, or the enter node, of the graph.

upstreams :: Node -> (Node …)

A procedure that takes a node, and returns its upstream (immediate ancestor) nodes.

downstreams :: Node -> (Node …)

A procedure that takes a node, and returns its downstream (immediate descendant) nodes.

node-comparator

A comparator that is used to determine if two nodes are equal to each other. It doesn’t need to have comparison procedure (we don’t need to see which is smaller than the other), but it has to have hash function, for we use hashtables internally. (See Basic comparators, for the details of comparators.)

The procedure returns a list of (node1 node2), where node2 is the immediate dominator of node1.

If there are node in the given graph that are unreachable from start, such nodes are ignored and not included in the result.

(A bit of explanation: Suppose you want to go to node X from start. There may be multiple routes, but if you have to pass node Y no matter which route you take, then Y is a dominator of X. There may be many dominators of X. Among them, there’s always one dominator such that all other X’s dominators are also its dominators—in other words, the closest dominator of X—which is called the immediate dominator of X.)

Let’s see an example. You have this directed graph:

          A (start)
          |
          v
          B <-------+
          |         |
    ------+-----    |
    |          |    |
    v          v    |
    C -------> D ---+
    |          |
    v          v
    E <------- F

Let’s represent the graph by a list of (x y z ...) where x can directly go to either y z ....

(define *graph* '((A B)
                  (B C D)
                  (C D E)
                  (D F B)
                  (F E)))

Then you can calculate the immediate dominator of each node as follows:

(calculate-dominators 'A
  (^n (filter-map (^g (and (memq n (cdr g)) (car g))) *graph*))
  (^n (assoc-ref *graph* n '()))
  eq-comparator)
  ⇒ ((E B) (F D) (D B) (C B) (B A))

That is, E’s immediate dominator is B, F’s is D, and so on.

The result itself can be viewed as a tree. It is called a dominator tree.

              F
              |
              v
        E     D     C
        |     |     |
        |     v     |
        +---> B <---+
              |
              v
              A