×

Properties of data flow frameworks: A unified model. (English) Zbl 0695.68049

A comprehensive overview of data flow frameworks and their characterizing properties is presented, to clarify property definitions and demonstrate their interrelation. Properties ensuring the existence of a solution are differentiated from those guaranteeing particular convergence behavior for specific solution procedures. Examples illustrate the orthogonality of these precision and convergence properties. In addition, several data flow problems are categorized with respect to these properties.
Reviewer: T.J.Marlowe

MSC:

68N99 Theory of software
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramsky, S., Hankin C. (eds.): Abstract interpretation of declarative languages. Chichester: Ellis Horwood 1987
[2] Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: principles, techniques, and tools. Reading, MA: Addison-Wesley 1986 · Zbl 1155.68020
[3] Allen, F.E., Cocke, J.: A program data flow analysis procedure. Commun. ACM19, 137-147 (1977) · Zbl 0317.68016 · doi:10.1145/360018.360025
[4] Allen, R., Kennedy, K.: Automatic translation of FORTRAN programs to vector form. ACM Trans. Program. Lang. Syst.9, 491-542 (1987) · Zbl 0631.68019 · doi:10.1145/29873.29875
[5] Alpern, B., Wegman, M., Zadeck, F.K.: Detecting inequality of values in programs. In: Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languates, pp. 1-11, 1988
[6] Apt, K.R.: A static analysis of CSP programs. Proceedings of 1983 Conference on Logics of Programs. (Lect. Notes Comput. Sci., vol. 164, pp. 1-17) Berlin Heidelberg New York: Springer 1983
[7] Banning, J.P.: An efficieny way to find the side effects of procedure calls and the aliases of variables. In: Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pp. 29-41, 1979
[8] Barth, J.M.: A practical interprocedural data flow analysis algorithm. Commun. ACM21, 724-737 (1978) · doi:10.1145/359588.359596
[9] Beatty, J.: Register assignment algorithm for generation of highly optimized object code. IBM J. Res. Dev.18, 20-39 (1974) · Zbl 0273.68023 · doi:10.1147/rd.181.0020
[10] Birkhoff, G.: Lattice theory. American Mathematical Society Colloquium Publications, Washington, DC, 1967 · Zbl 0153.02501
[11] Burke, M.: An interval analysis approach toward exhaustive and incremental interprocedural data flow analysis. ACM Trans. Program. Lang. Syst.12, 341-395 (1990) · doi:10.1145/78969.78963
[12] Burke, M.: Private communication (1989)
[13] Burke, M., Cytron, R.: Interprocedural dependence analysis and parallelization. In: Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pp. 162-175. SIGPLAN Notices21, No. 6 (1986)
[14] Burke, M., Ryder, B.G.: A critical analysis of incremental iterative data flow analysis algorithms. IEEE Trans. Software Eng16, 723-728 (1990) · Zbl 05114102 · doi:10.1109/32.56098
[15] Cai, J.: Fixed point computation and transformational programming. PhD thesis, Department of Computer Science, Rutgers University, 1987. Rutgers Technical Report DCS-TR-217
[16] Cai, J., Paige, R.: Program derivation by fixed point computation. Sci. Comput. Program.11, 197-261 (1989) · Zbl 0681.68020 · doi:10.1016/0167-6423(88)90033-0
[17] Callahan, D.: The program summary graph and flow sensitive interprocedural data flow analysis. In: Proceedings of the SIGPLAN ’88 Conference on Programming Language Design and Implementation, pp. 47-56, 1988
[18] Callahan, D., Cooper, K., Kennedy, K., Torczon, L.: Interprocedural constant propagation. In: Conference Record of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, pp. 152-161, 1986
[19] Callahan, D., Subhlok, J.: Static analysis of low-level synchronization. In: Conference Record of the 1988 Workshop on Parallel and Distributed Debugging, pp. 100-111, 1988
[20] Carroll, M.: Data flow update via attribute and dominator updates. PhD thesis, Department of Computer Science, Rutgers University, 1988
[21] Carroll, M., Ryder, B.: Incremental data flow update via attribute and dominator updates. In: Conference Record of the Fiftheenth Annual ACM Symposium on Principles of Programming Languages, pp. 274-284, 1988
[22] Chow, A., Rudmik, A.: The design of a data flow analyzer. In: Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pp. 106-113, 1982
[23] Cooper, K.: Analyzing aliases of reference formal parameters. In: Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, pp. 281-290, 1984
[24] Cooper, K., Kennedy, K.: Efficient computation of flow insensitive interprocedural summary information. In: Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, pp. 247-258. SIGPLAN Notices19, No. 6 (1984)
[25] Cooper, K., Kennedy, K.: Interprocedural side-effect analysis in linear time. In: Proceedings of the SIGPLAN ’88 Conference on Programming Language Design and Implementation, pp. 57-66, 1988
[26] Cooper, K., Kennedy, K.: Fast interprocedural alias analysis. In: Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, pp. 49-59, 1989
[27] Cousot, P.: Semantic foundations of program analysis. In: Program Flow Analysis: Theory and Applications, Chap. 10. Englewood Cliffs, NJ: Prentice Hall 1981
[28] Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: Conference Record of the Fourth Annual ACM Symposium on Principles of Programming Languages, pp. 238-252. SIGPLAN Notices12, No. 1 (1977)
[29] Cousot, P., Cousot, R.: Automatic synthesis of optimal invariant assertions: Mathematical foundations. In: Proceedings ACM Symposium on Artificial Intelligence and Programming Languages, pp. 1-12. SIGPLAN Notices12, No. 8 (1977) · Zbl 0586.68019
[30] Cousot, P., Cousot, R.: Systematic design of program analysis frameworks. In: Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pp. 269-282. SIGPLAN Notices14, No. 1 (1979) · Zbl 0413.06004
[31] Coutant, D.S.: Retargetable high-level alias analysis. In: Conference Record of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, pp. 110-118. SIGPLAN Notices21, No. 1 (1986)
[32] Cytron, R.: Do-across: Beyond vectorization for multiprocessors. In: Conference Record of the 1986 International Conference on Parallel Processing, pp. 836-844, 1986
[33] Cytron, R., Ferrante, J., Rosen, B., Wegman, M., Zadeck, F.K.: An efficient method of computing static single assignment form. In: Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, pp. 25-35, 1989
[34] Cytron, R., Lowry, A., Zadeck, F.K.: Code motion of control structures in high-level languages. In: Conference Record of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, pp. 70-85, 1986
[35] Dijkstra, E.W., Gasteren, A. van: A simple fixpoint argument without the restriction to continuity. Acta Inf.23, 1-8 (1986) · Zbl 0591.68007 · doi:10.1007/BF00268074
[36] Emrath, P.A., Padua, D.A.: Automatic detection of nondeterminacy in parallel programs. In: Proceedings of the ACM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging, pp. 89-99, 1988
[37] Ferrante, J., Ottenstein, K., Warren, J.: The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst.9, 319-349 (1987) · Zbl 0623.68012 · doi:10.1145/24039.24041
[38] Fong, A.C.: Generalized common subexpressions in very high level languages. In: Conference Record of the Fourth Annual ACM Symposium on Principles of Programming Languages, pp. 48-57, 1977
[39] Graham, S., Wegman, M.: A fast and usually linear algorithm for global data flow analysis. J. ACM23, 172-202 (1976) · Zbl 0326.68023 · doi:10.1145/321921.321939
[40] Harrold, M.J., Soffa, M.L.: Computation of interprocedural definition and use dependencies. In: Proceedings of the IEEE Comp. Soc. 1990 Int. Conference on Computer Languages, pp. 297-306, 1990
[41] Hecht, M.S.: Flow analysis of computer programs. Amsterdam: Elsevier North-Holland 1977 · Zbl 0381.68013
[42] Hecht, M.S., Ullman, J.D.: Analysis of a simple algorithm for global flow problems. In: Conference Record of the ACM Symposium on Principles of Programming Languages, pp. 207-217, 1973 · Zbl 0309.68036
[43] Holley, I., Rosen, B.: Qualified data flow problems. IEEE Trans. Software Eng., SE-7, 60-78 (1981) · Zbl 05341208 · doi:10.1109/TSE.1981.234509
[44] Hopcroft, J., Ullman, J.D.: Introduction to automata theory, languages, and computation. Reading, MA: Addison-Wesley 1979 · Zbl 0426.68001
[45] Horwitz, S., Demers, A., Teitelbaum, T.: An efficient general iterative algorithm for data-flow analysis. Acta Inf.24, 679-694 (1987) · Zbl 0612.68015 · doi:10.1007/BF00282621
[46] Horwitz, S., Prins, J., Reps, T.: Integrating non-interfering versions of programs. In: Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pp. 133-145, 1988
[47] Horwitz, S., Prins, J., Reps, T.: On the adequacy of program dependence graphs representing programs. In: Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pp. 146-157, 1988
[48] Horwitz, S., Pfeiffer, P., Reps, T.: Dependence analysis for pointer variables. In: Proceedings of the SIGPLAN ’89 Conference on Programming Language Design and Implementation, pp. 28-40, 1989
[49] Horwitz, S., Reps, T., Binkley, D.: Interprocedural slicing using dependence graphs. In: Proceedings of the SIGPLAN’88, Conference on Programming Language Design and Implementation, pp. 35-46, 1988
[50] Kam, J.B., Ullman, J.D.: Global data flow analysis and iterative algorithms. J. ACM23, 158-171 (1976) · Zbl 0315.68031 · doi:10.1145/321921.321938
[51] Kam, J.B., Ullman, J.D.: Monotone data flow analysis frameworks. Acta Inf.7, 305-317 (1977) · Zbl 0375.68020 · doi:10.1007/BF00290339
[52] Kennedy, K.: A survey of data flow analysis techniques. In: Program flow analysis theory and applications, Chap. 1 Englewood Cliffs, NJ: Prentice Hall 1981
[53] Kildall, G.: A unified approach to global program optimization. In: Conference Record of the ACM Symposium on Principles of Programming Languages, pp. 194-206, 1973 · Zbl 0309.68020
[54] Knuth, D.E.: An empirical study of FORTRAN programs. Software Pract. Exper.1, 105-133 (1971) · Zbl 0243.68003 · doi:10.1002/spe.4380010203
[55] Larus, J., Hilflinger, P.: Detecting conflicts in structure accesses. In: Proceedings of the SIGPLAN’88, Conference on Programming Language Design and Implementation, pp. 21-34, (1986)
[56] Lindstrom, G.: Static evaluation of functional programs. In: Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pp. 196-206. SIGPLAN Notices21, No. 7 (1986)
[57] Manna, Z., Shamir, A.: The theoretical aspects of the optimal fixedpoint. SIAM J. Comput.5, 414-426 (1976) · Zbl 0358.68017 · doi:10.1137/0205033
[58] Manna, Z., Shamir, A.: The optimal approach to recursive programs. Commun. ACM20, 824-831 (1977) · Zbl 0361.68022 · doi:10.1145/359863.359885
[59] Marlowe, T.J.: Incremental iteration and data flow analysis. PhD thesis, Department of Computer Science, Rutgers University, 1989
[60] Marlowe, T.J., Ryder, B.G.: An efficient hybrid algorithm for incremental data flow analysis. In: Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pp. 184-196, 1990 · Zbl 0695.68049
[61] McDowell, C.E.: A practical algorithm for static analysis of parallel programs. J. Parallel Distrib. Comput.22, 96-103 (1979)
[62] Morel, E. Renvoise, C.: Global optimization by suppression of redundancies. Commun. ACM22, 96-103 (1979) · Zbl 0393.68010 · doi:10.1145/359060.359069
[63] Myers, E.W.: A precise interprocedural data flow algorithm. In: Conference Record of the Eighth Annual ACM Symposium on Principles of Programming Languages, pp. 219-230, 1981
[64] Neirynck, A., Panangaden, P., Demers, A.: Computation of aliases and support sets. In: Conference Record of the Fourteenth Annual ACM Symposium on Principles of Programming Languages, pp. 274-283, 1987
[65] Ottenstein, K.J., Ottenstein, L.M.: The program dependence graph in a software development environment. In: Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pp. 177-184, 1984 · Zbl 0549.68007
[66] Padua, D., Wolfe, M.J.: Advanced compiler optimizations for supercomputers. Commun. ACM22, 1184-1201 (1986) · doi:10.1145/7902.7904
[67] Paull, M.C.: Algorithm design ? A recursion transformation framework. New York, NY: Wiley Interscience 1988
[68] Rapps S., Weyuker, E.: Selecting software test data using data flow information. IEEE Trans. Software Eng. Se-11, 367-375 (1985) · Zbl 05341617 · doi:10.1109/TSE.1985.232226
[69] Reif, J., Lewis, H.: Efficient symbolic analysis of programs. J. Comput. Syst. Sci.11, 280-313 (1986) · Zbl 0603.68012 · doi:10.1016/0022-0000(86)90031-0
[70] Reif, J., Tarjan, R.E.: Symbolic program analysis in almost-linear time. SIAM J. Comput.9, 81-93 (1981) · Zbl 0481.68025
[71] Reps, T., Teitelbaum, T., Demers, A.: Incremental context-dependent analysis for language-based editors. ACM Trans. Program. Lang. Syst.5, 449-477 (1983) · doi:10.1145/2166.357218
[72] Rosen, B.: Monoids for rapid data flow analysis. SIAM J. Comput.9, 159-196 (1980) · Zbl 0448.68007 · doi:10.1137/0209015
[73] Rosen, B.: A lubricant for data flow analysis. SIAM J. Comput.11, 493-511 (1982) · Zbl 0488.68021 · doi:10.1137/0211039
[74] Rosen, B., Wegman, M., Zadeck, F.K.: Global value numbers and redundant computations. In: Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pp. 12-27, 1988
[75] Ruggieri, C., Murtagh, T.: Lifetime analysis of dynamically allocated objects. In: Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pp. 285-293, 1988
[76] Ryder, B.G., Marlowe, T.J., Paull, M.C.: Conditions for incremental iteration: examples and counterexamples. Sci. Comput. Program.11, 1-15 (1988) · Zbl 0661.68014 · doi:10.1016/0167-6423(88)90061-5
[77] Ryder, B.G., Pande, H.: The interprocedural structure of C programs: An empirical study. Laboratory for Computer Science Research Technical Report LCSR-TR-99, Rutgers University, 1988
[78] Ryder, B.G., Paull, M.C.: Elimination algorithms for data flow analysis. ACM Comput. Surv.18, 277-316 (1986) · doi:10.1145/27632.27649
[79] Sagiv, S., Edelstein, O., Francez, N., Rodeh, M.: Resolving circularity in attribute grammars with applications to data flow analysis. In: Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, pp. 36-46, 1989
[80] Schonberg, E.: On-the-fly detection of access anomalies. In: Proceedings of the SIGPLAN ’89 Conference on Programming Language Design and Implementation, pp. 285-297, 1989
[81] Schwartz, J.T., Sharir, M.: A design for optimizations of the bitvectoring class. (Courant Comput. Sci. Rep. 17) New York, NY: New York University 1979
[82] Shapiro, R.M., Saint, H.: The representation of algorithms. Technical Report CA-7002-1432. Massachusetts Computer Associates, 1970 · Zbl 0224.68003
[83] Sharir, M., Pnueli, A.: Two approaches to interprocedural data flow analysis. In: Program Flow Analysis: Theory and Applications, Chap. 7. Englewood Cliffs, NJ: Prentice Hall 1981
[84] Shasha, D., Snir, M.: Efficient and correct execution of parallel programs that share memory. ACM Trans. Program. Lang. Syst.10, 282-312 (1988) · doi:10.1145/42190.42277
[85] Tarjan, R.E.: Testing flow graph reducibility. J. Comput. Syst. Sci.9, 355-365 (1974) · Zbl 0315.68018 · doi:10.1016/S0022-0000(74)80049-8
[86] Tarjan, R.E.: Iterative Algorithms for global Flow Analysis. In: Algorithms and Complexity-New Directions and Recent Results, pp. 71-101. New York: Academic Press 1976
[87] Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM26, 690-715 (1979) · Zbl 0413.68063 · doi:10.1145/322154.322161
[88] Tarjan, R.E.: A unified approach to path problems. J. ACM28, 576-593 (1981) · Zbl 0462.68041
[89] Tarjan, R.E.: Fast algorithms for solving path problems. J. ACM28, 594-614 (1981) · Zbl 0462.68042 · doi:10.1145/322261.322273
[90] Tenenbaum, A.: Determination of types in very high level languages. PhD thesis, Courant Institute of Mathematical Sciences, New York University, 1974. Technical Report Number CCSR #3
[91] Tenenbaum, A.: Compile time type determination in SETL. In: Proc.ACM 1974 Annual Conference, pp. 95-100, 1974
[92] Ullman, J.D., Hecht, M.S.: Flow graph reducibility. SIAM J. Comput.1, 188-202 (1972) · Zbl 0265.68031 · doi:10.1137/0201014
[93] Walz, J., Johnson, G.: Incremental evaluation for a general class of circular attribute grammars. In: Proceedings of the SIGPLAN ’88 Conference on Programming Language Design and Implementation, pp. 209-221. SIGPLAN Notices23 No. 7 (1988)
[94] Wegman, M., Zadeck, F.K.: Constant propagation with conditional branches. In: Conference Record of the Twelfth Annual ACM Symposium on Principles of Programming Languages, pp. 291-299, 1985
[95] Weihl, W.: Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables. In: Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, pp. 83-94, 1980
[96] Weiser, M.: Program slicing. IEEE Trans. Software Eng. SE-10, 352-357 (1984) · Zbl 0552.68004 · doi:10.1109/TSE.1984.5010248
[97] Zadeck, F.K.: Incremental data flow analysis in a structured program editor. PhD thesis, Rice University, 1983
[98] Zadeck, F.K.: Incremental data flow analysis in a structured program editor. In: Proceedings of the ACM SIGPLAN Symposium on Compiler Construction, pp. 132-143. SIGPLAN Notices19, No. 6 (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.