Abstract
This entry formalises the fast iterative algorithm for computing dominators
due to Cooper, Harvey and Kennedy. It gives a specification of computing
dominators on a control
flow graph where each node refers to its reverse post order number. A
semilattice of reversed-ordered list which represents dominators is
built and a Kildall-style algorithm on the semilattice is defined for
computing dominators. Finally the soundness and completeness of the
algorithm are proved w.r.t. the specification.
BSD License