doc/ego/cf/cf3

   1 .NH 2
   2 Immediate dominators
   3 .PP
   4 A basic block B dominates a block C if every path
   5 in the control flow graph from the procedure entry block
   6 to C goes through B.
   7 The immediate dominator of C is the closest dominator
   8 of C on any path from the entry block.
   9 See also
  10 .[~[
  11 aho compiler design
  12 .], section 13.1.]
  13 .PP
  14 There are a number of algorithms to compute
  15 the immediate dominator relation.
  16 .IP 1.
  17 Purdom and Moore give an algorithm that is
  18 easy to program and easy to describe (although the
  19 description they give is unreadable;
  20 it is given in a very messy Algol60 program full of gotos).
  21 .[
  22 predominators
  23 .]
  24 .IP 2.
  25 Aho and Ullman present a bitvector algorithm, which is also
  26 easy to program and to understand.
  27 (See
  28 .[~[
  29 aho compiler design
  30 .], section 13.1.]).
  31 .IP 3
  32 Lengauer and Tarjan introduce a fast algorithm that is
  33 hard to understand, yet remarkably easy to implement.
  34 .[
  35 lengauer dominators
  36 .]
  37 .LP
  38 The Purdom-Moore algorithm is very slow if the
  39 number of basic blocks in the flow graph is large.
  40 The Aho-Ullman algorithm in fact computes the
  41 dominator relation,
  42 from which the immediate dominator relation can be computed
  43 in time quadratic to the number of basic blocks, worst case.
  44 The storage requirement is also quadratic to the number
  45 of blocks.
  46 The running time of the third algorithm is proportional
  47 to:
  48 .DS
  49 (number of edges in the graph) * log(number of blocks).
  50 .DE
  51 We have chosen this algorithm because it is fast
  52 (as shown by experiments done by Lengauer and Tarjan),
  53 it is easy to program and requires little data space.