John B. Kam
Abstract
Kildall has developed data propagation algorithms for code optimization in a general lattice theoretic framework. In another direction, Hecht and Ullman gave a strong upper bound on the number of iterations required for propagation algorithms when the data is represented by bit vectors and depth-first ordering of the flow graph is used. The present paper combines the ideas of these two papers by considering conditions under which the bound of Hecht and Ullman applies to the depth-first version of Kildall's general data propagation algorithm. It is shown that the following condition is necessary and sufficient: Let ƒ and g be any two functions which could be associated with blocks of a flow graph, let x be an arbitrary lattice element, and let 0 be the lattice zero. Then (*) (∀ƒ,g,x) [ƒg(0) ≥ g(0) ∧ ƒ(x) ∧ x]. Then it is shown that several of the particular instances of the techniques Kildall found useful do not meet condition (*).
- 1 AHO, A V., AND ULmSAN, J.D The Theory of Parsing, Translat,on and Compiling, Vol. II" Compding. Prentice-Hall, Englewood Cliffs, N J., 1973 Google Scholar
Digital Library
- 2 ALLEN, F.E. Program optnni~atlon. Annual Review m Automatic Programming, Vol. 5, Pergamon Press, New York, 1969, 239-307.Google Scholar
- 3 ALLEN, F.E. Control flow analysm SIGPLAN Notices 5, 7 (July 1970), 1-19. Google ScholarDigital Library
- 4 COCKE, J Global common subexpression elnnination SIGPLAN Nohces 5, 7 (July 1970), 20-24. Google ScholarDigital Library
- 5 HECHT, M.S., AN}) ULLMAN, J.D. Analysis of a simple algorithm for global flow problems. Proc. ACM Conf. on Principles of Programming Languages, Oct. 1973, pp. 207-217. Google ScholarDigital Library
- 6 HECHT, M S., AND ULLMAN, J D Characterizations of reducible flow graphs. J. ACM 21, 3 (July 1974), 367-375. Google ScholarDigital Library
- 7 HOPCROFT, J.E, AND TARJAN, R.E. Algorithm 447--Efficmnt algorithms for graph mampulation. Comm ACM 16, 6 (June 1973), 372-378. Google ScholarDigital Library
- 8 KAM, J.B., AN}) ULLMAN, J D Monotone data flow analysis frameworks TR-169, Dep. of Elec. Eng., Computer Sciences Lab., Princeton U., Princeton, N J, Jan 1975Google Scholar
- 9 KENNEDY, K A global flow analysis algorithm lnt J Computer Math. 3, 1 (Dec 1971), 5-15.Google Scholar
- 10 KILDALL, G A Global expression optimization during compilation. TR 724)6-02, Computer Scl Group, U. of Washington, Seattle, Wash , June 1972. See also Proc. ACM Conf. on Principles of Programming Languages, Oct. 1973, pp 194-206 Google ScholarDigital Library
- 11 KNUTH, D.E. An empirmal study of FORTRAN programs. Software Pratt and Exper. 1, 2 (April 1971), 105-134Google ScholarCross Ref
- 12 SCHAEFER, M. A Malhemahcal Theory of Global Flow Analysis Prentice-Hall, Englewood Chffs, N J., 1973.Google Scholar
- 13 ULLMAN, J D Fast algorithms for the elimination of commonsubexpressions Acta Informatwa Z, 3 (Dec. 1973), 191-213Google ScholarDigital Library
- 14 VYSSOTSKY, V.A. Private communication to M.S. Hecht, June 1973Google Scholar
Index Terms
- Global Data Flow Analysis and Iterative Algorithms
Recommendations
Interprocedural data flow analysis in Soot using value contexts
SOAP '13: Proceedings of the 2nd ACM SIGPLAN International Workshop on State Of the Art in Java Program analysisAn interprocedural analysis is precise if it is flow sensitive and fully context-sensitive even in the presence of recursion. Many methods of interprocedural analysis sacrifice precision for scalability while some are precise but limited to only a ...
Double iterative framework for flow-sensitive interprocedural data flow analysis
Compiler optimization, parallel processing, data flow testing, and symbolic debugging can benefit from interprocedural data flow analysis. However, the live, reaching definition, and most summary data flow problems are theoretically intractable in the ...
Describing data flow analysis techniques with Kleene algebra
Static program analysis consists of compile-time techniques for determining properties of programs without actually running them. Using Kleene algebra, we formalize four instances of a general class of static intraprocedural data flow analyses known as '...
Comments