From: Tobias Nipkow <nipkow@in.tum.de>

A data flow analysis algorithm for computing dominators

Nan Jiang

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.

https://www.isa-afp.org/entries/Dominance_CHK.html

Enjoy!

smime.p7s

Last updated: Dec 05 2021 at 22:18 UTC