A data flow analysis algorithm for computing dominators

 

Title: A data flow analysis algorithm for computing dominators
Author: Nan Jiang
Submission date: 2021-09-05
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.
BibTeX:
@article{Dominance_CHK-AFP,
  author  = {Nan Jiang},
  title   = {A data flow analysis algorithm for computing dominators},
  journal = {Archive of Formal Proofs},
  month   = sep,
  year    = 2021,
  note    = {\url{https://isa-afp.org/entries/Dominance_CHK.html},
            Formal proof development},
  ISSN    = {2150-914x},
}
License: BSD License
Status: [ok] This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.