A data flow analysis algorithm for computing dominators (Q7361913)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Dominance_CHK
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A data flow analysis algorithm for computing dominators |
AFP entry Dominance_CHK |
Statements
5 September 2021
0 references
Nan Jiang
0 references
A data flow analysis algorithm for computing dominators (English)
0 references
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.
0 references
