Interprocedural array region analyses | SpringerLink
Skip to main content

Interprocedural array region analyses

  • Conference paper
  • First Online:
Languages and Compilers for Parallel Computing (LCPC 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1033))

Abstract

Many program optimizations require exact knowledge of the sets of array elements that are referenced in or that flow between statements or procedures. Some examples are array privatization, generation of communications in distributed memory machines, or compile-time optimization of cache behavior in hierarchical memory machines.

Exact array region analysis is introduced in this article. These regions exactly represent the effects of statements and procedures upon array variables. To represent the flow of these data, we also introduce two new types of array region analyses: IN and OUT regions.

The intraprocedural propagation is presented, as well as a general linear framework for interprocedural analyses, that handles array reshapes.

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

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. American National Standard Programming Language FORTRAN ANSI X3.9-1978, ISO 1539-1980, 1983.

    Google Scholar 

  2. Corinne Ancourt and François Irigoin. Scanning polyhedra with DO loops. In Symposium on Principles and Practice of Parallel Programming, April 1991.

    Google Scholar 

  3. Béatrice Apvrille-Creusillet. Régions exactes et privatisation de tableaux (exact array region analysis and array privatization). Master's thesis, Université Paris VI, France, September 1994. Available via http://www.cri.ensmp.fr/∼creusil.

    Google Scholar 

  4. M. Berry et al. The PERFECT Club benchmarks: Effective performance evaluation of supercomputers. Technical Report CSRD-827, CSRD, University of Illinois, May 1989.

    Google Scholar 

  5. Michael Burke and Ron Cytron. Interprocedural dependence analysis and parallelization. ACM SIGPLAN Notices, 21(7):162–175, July 1986.

    Article  Google Scholar 

  6. D. Callahan and K. Kennedy. Analysis of interprocedural side effects in a parallel programming environment. Journal of Parallel and Distributed Computing, 5:517–550, 1988.

    Article  Google Scholar 

  7. Fabien Coelho. Compilation of I/O communications for HPF. In Frontiers'95, February 1995. Available via http://www.cri.ensmp.fr/∼coelho.

    Google Scholar 

  8. Jean-François Collard. Automatic parallelization of while-loops using speculative execution. International Journal of Parallel Programming, 23(2):191–219, 1995.

    Google Scholar 

  9. Paul Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23–53, September 1991.

    Google Scholar 

  10. Mary Hall, Brian Murphy, Saman Amarasinghe, Shih-Wei Liao, and Monica Lam. Overview of an interprocedural automatic parallelization system. In Fifth International Workshop on Compilers for Parallel Computers, pages 570–579, June 1995.

    Google Scholar 

  11. François Irigoin. Interprocedural analyses for programming environments. In Workshop on Environments and Tools for Parallel Scientific Computing, September 1992.

    Google Scholar 

  12. François Irigoin, Pierre Jouvelot, and Rémi Triolet. Semantical interprocedural parallelization: An overview of the PIPS project. In International Conference on Supercomputing, June 1991.

    Google Scholar 

  13. Chung-Chi Jim Li, Elliot M. Stewart, and W. Kent Fuchs. Compiler-assisted full checkpointing. Software: Practice and Experience, 24(10):871–886, October 1994.

    Google Scholar 

  14. Vadim Maslov. Lazy array data-flow analysis. In Symposium on Principles of Programming Language, pages 311–325, January 1994.

    Google Scholar 

  15. Vadim Maslov and William Pugh. Simplifying polynomial constraints over integers to make dependence analysis more precise. Technical Report CS-TR-3109.1, University of Maryland, College Park, February 1994.

    Google Scholar 

  16. William Pugh. A practical algorithm for exact array dependence analysis. Communications of the ACM, 35(8):102–114, August 1992.

    Article  Google Scholar 

  17. William Pugh and David Wonnacott. Eliminating false data dependences using the omega test. In International Conference on Programming Language Design and Implementation, pages 140–151, June 1992.

    Google Scholar 

  18. Rémi Triolet. Interprocedural analysis for program restructuring with Parafrase. Technical report 538, CSRD, University of Illinois, December 1985.

    Google Scholar 

  19. Rémi Triolet, Paul Feautrier, and François Irigoin. Direct parallelization of call statements. In Symposium on Compiler Construction, 1986.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Chua-Huang Huang Ponnuswamy Sadayappan Utpal Banerjee David Gelernter Alex Nicolau David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Creusillet, B., Irigoin, F. (1996). Interprocedural array region analyses. In: Huang, CH., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1995. Lecture Notes in Computer Science, vol 1033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014191

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60765-6

  • Online ISBN: 978-3-540-49446-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics