Skip to main content
SpringerLink
Log in

Pathlistings applied to data flow analysis

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

In this paper the pathlisting mechanism is developed as a new tool useful in performing efficient data flow analysis of programs for a wide variety of problems. An algorithm using this tool for forward flow, code improvement problems is presented. It is shown that for all practical purposes this algorithm is linear in the size of the input which is, generally speaking, a reducible flow graph modeling the given program. Pathlistings generalize the nodelisting approach, introduced by Kennedy, for solving data flow problems. The efficiency of the pathlisting algorithm is due to the reuse of intermediate values and due to the fact that the cycles of a reducible flow graph can be ordered. Other advantages of the approach are also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho, A.V., Ullman, J.D.: The theory of parsing, translation and compiling, Vol. I: Parsing. Englewood Cliffs, N.J.: Prentice-Hall 1973

    Google Scholar 

  2. Aho, A.V., Ullman, J.C.: The theory of parsing translation, and compiling, Vol. II: Compiling. Englewood Cliffs, N.J.: Prentice-Hall 1973

    Google Scholar 

  3. Aho, A.V., Ullman, J.D.: Node listings for reducible flow graphs. Proceedings of Seventh Annual ACM Symposium on Theory of Computing Albuquerque, N.M., pp. 177–185, 1975

  4. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley 1974

    Google Scholar 

  5. Allen, F.E., Cocke, J.: A catalogue of optimizing transformations, design and optimization of compilers, pp. 1–30. (R. Rustin, ed.) Englewood Cliffs, N.J.: Prentice-Hall 1972

    Google Scholar 

  6. Cocke, J., Schwartz, J.T.: Programming languages and their compilers: preliminary notes. Computer Science Department, New York University, 1970

  7. Graham, S.L., Wegman, M.: A fast and usually linear algorithm for global flow analysis. J.A.C.M. 23, 172–202 (1976)

    Article  Google Scholar 

  8. Hecht, M.S., Ullman, J.D.: Flow graph reducibility. SIAM J. Comput. 1, 188–202 (1972)

    Google Scholar 

  9. Hecht, M.S., Ullman, J.D.: Characterizations of reducible flow graphs. JACM 21, 367–375 (1974)

    Article  Google Scholar 

  10. Hecht, M.S., Ullman, J.D.: A simple algorithm for global data flow analysis problems. SIAM J. Comput. 4, 519–521 (1975)

    Google Scholar 

  11. Kennedy, K.: A global flow analysis algorithm. Internat. J. Comput. Math. 3, 5–15 (1971)

    Google Scholar 

  12. Kennedy, K.: Safety of code motion. Internat. J. Comput. Math. 3, 117–130 (1972)

    Google Scholar 

  13. Kennedy, K.: Node listings applied to data flow analysis. Conference Record of the Second ACM Symposium on Principles of Programming Languages, Palo Alto, California, pp. 10–21, 1975

  14. Kennedy, K., Zucconi, L.: Applications of a graph grammar for program control flow analysis. Conf. Record of the Fourth ACM Symposium on the Principles of Programming Languages, Los Angeles, pp. 72–85 1977

  15. Killdall, G.A.: A unified approach to global program optimization. Conference Record of ACM Symposium on Principles of Programming Languages. Boston, pp. 194–206, 1973

  16. Knuth, D.E.: An empirical study of FORTRAN programs. Software practice and Experience 1, 105–134 (1971)

    Google Scholar 

  17. Kam, J.B., Ullman, J.D.: Global data flow analysis and iterative algorithms. J.A.C.M. 23, 158–171 (1976)

    Article  Google Scholar 

  18. Markowsky, G., Tarjan, R.E.: Lower bounds on the lengths of node sequences in directed graphs. IBM Research Report RC5477, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1975

    Google Scholar 

  19. Rosen, B.K.: High-level data flow analysis. Communications of the ACM. 20, 712–724 (1977)

    Article  Google Scholar 

  20. Schaefer, M.: A mathematical theory of global program optimization. Englewood Cliffs, N.J.: Prentice-Hall 1973

    Google Scholar 

  21. Tarjan, R.E.: Finding dominators in directed graphs. SIAM J. Comput. 3, 62–89 (1974)

    Google Scholar 

  22. Tarjan, R.E.: Solving path problems on directed graphs. Draft, Computer Science Department, Stanford University, Stanford, California, 1975

    Google Scholar 

  23. Tarjan, R.E.: Applications of path compression on balanced trees. STAN-CS-75-512, Computer Science Department, Stanford University, Stanford, California, 1975

    Google Scholar 

  24. Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. JACM 22, 215–225 (1975)

    Article  Google Scholar 

  25. Ullman, J.D.: Fast algorithms for the elimination of common subexpressions. Acta Informat. 2, 191–213 1973)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Science, The Ohio State University, 43210, Columbus, Ohio, USA

    Jayashree Ramanathan

  2. Department of Mathematical Sciences, Rice University, 77001, Houston, Texas, USA

    Ken Kennedy

Authors
  1. Jayashree Ramanathan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ken Kennedy
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Work supported by National Science Foundation grant DCR73-00365-AO

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ramanathan, J., Kennedy, K. Pathlistings applied to data flow analysis. Acta Informatica 16, 253–273 (1981). https://doi.org/10.1007/BF00289306

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00289306

Keywords

Search

Navigation