SIAM Journal on Computing · 1972 · 172 citations · 6 references
ComputingComputer ScienceAlgorithmsFormal MethodsSoftware EngineeringControl-flow AnalysisData-flow AnalysisDirected Acyclic GraphsGraph AlgorithmsStatic AnalysisControl Flow GraphsInterval AnalysisStatic Control-flow AnalysisTransformations
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.
6
Frances Allen · ACM SIGPLAN Notices · 1970 · 720 citations
Global common subexpression elimination
John Cocke · ACM SIGPLAN Notices · 1970 · 210 citations
Linear and Context-Free Graph Grammars
T. Pavlidis · Journal of the ACM · 1972 · 116 citations · Full text
Language Studies, Electrical Engineering, Computational Linguistics +5