Flow Graph Reducibility
Authors:
- Matthew S. HechtMHMatthew S. Hecht
- Jeffrey D. UllmanJUJeffrey D. Ullman
- 1 June 1972
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 1 (2) , 188-202
Abstract
The structure of , programs can often be described by a technique called “interval analysis” on their flow graphs. Here, we characterize the set of flow graphs that can be analyzed in this way in terms of two very simple transformations on graphs. We then give a necessary and sufficient condition for analyzability and apply it to “goto-less programs,” showing that they all meet the criterion.Keywords
This publication has 9 references indexed in Scilit:
- A global flow analysis algorithmInternational Journal of Computer Mathematics, 1972
- Linear and Context-Free Graph GrammarsJournal of the ACM, 1972
- Depth-first search and linear graph algorithms1971
- Algorithmic approximationsJournal of Computer and System Sciences, 1971
- Structure and meaning of elementary programs1971
- Control flow analysisACM SIGPLAN Notices, 1970
- Global common subexpression eliminationACM SIGPLAN Notices, 1970
- Letters to the editor: The go to statement reconsideredCommunications of the ACM, 1968
- Letters to the editor: go to statement considered harmfulCommunications of the ACM, 1968