Email Gateway (Sep 07 2021 at 19:07): Email Gateway (Sep 07 2021 at 19:07):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: Jan 04 2025 at 20:18 UTC