Region array SSA

ABSTRACT

Static Single Assignment (SSA) has become the intermediate program representation of choice in most modern compilers because it enables efficient data flow analysis of scalars and thus leads to better scalar optimizations. Unfortunately not much progress has been achieved in applying the same techniques to array data flow analysis, a very important and potentially powerful technology. In this paper we propose to improve the applicability of previous efforts in array SSA through the use of a symbolic memory access descriptor that can aggregate the accesses to the elements of an array over large, interprocedural program contexts. We then show the power of our new representation by using it to implement a basic data flow algorithm, reaching definitions. Finally we apply this analysis to array constant propagation and array privatization and show performance improvement (speedups) for benchmark codes.

REFERENCES

• 1: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 2: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 3: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• 4: D. Callahan , K. Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Proceedings of the 1st International Conference on Supercomputing, p.138-171, March 1988, Athens, Greece
• 5: Lori Carter , Beth Simon , Brad Calder , Larry Carter , Jeanne Ferrante, Predicated Static Single Assignment, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.245, October 12-16, 1999
• 6: Dhruva R. Chakrabarti , Prithviraj Banerjee, Static Single Assignment Form for Message-Passing Programs, International Journal of Parallel Programming, v.29 n.2, p.139-184, April 2001 [doi>10.1023/A:1007633018973]
• 7: Jean-Francois Collard, Array SSA for Explicitly Parallel Programs, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.383-390, August 31-September 03, 1999
• 8: Jean-François Collard , Denis Barthou , Paul Feautrier, Fuzzy array dataflow analysis, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.92-101, July 19-21, 1995, Santa Barbara, California, United States
• 9: Béatrice Creusillet , François Irigoin, Exact versus Approximate Array Region Analyses, Proceedings of the 9th International Workshop on Languages and Compilers for Parallel Computing, p.86-100, August 08-10, 1996
• 10: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 11: P. Feautrier. Dataflow analysis of array and scalar references. Int. J. of Parallel Programming, 20(1):23--54, 1991.
• 12: T. Gross , P. Steenkiste, Structured dataflow analysis for arrays and its use in an optimizing complier, Software—Practice & Experience, v.20 n.2, p.133-155, February 1990 [doi>10.1002/spe.4380200203]
• 13: Junjie Gu , Zhiyuan Li , Gyungho Lee, Symbolic array dataflow analysis for array privatization and program parallelization, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224318]
• 14: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
• 15: Mary H. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Detecting coarse-grain parallelism using an interprocedural parallelizing compiler, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.49-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224337]
• 16: Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268956]
• 17: Vadim Maslov, Lazy array data-flow dependence analysis, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-325, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177911]
• 18: Dror E. Maydan , Saman P. Amarasinghe , Monica S. Lam, Array-data flow analysis and its use in array privatization, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.2-15, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158515]
• 19: Sungdo Moon , Mary W. Hall , Brian R. Murphy, Predicated array data-flow analysis for run-time parallelization, Proceedings of the 12th international conference on Supercomputing, p.204-211, July 1998, Melbourne, Australia [doi>10.1145/277830.277874]
• 20: Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002 [doi>10.1145/509705.509708]
• 21: William Pugh , David Wonnacott, An Exact Method for Analysis of Value-based Array Data Dependences, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.546-566, August 12-14, 1993
• 22: William Pugh , David Wonnacott, Nonlinear array dependence analysis, University of Maryland at College Park, College Park, MD, 1994
• 23: Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, International Journal of Parallel Programming, v.31 n.4, p.251-283, August 2003 [doi>10.1023/A:1024597010150]
• 24: Vivek Sarkar , Kathleen Knobe, Enabling Sparse Constant Propagation of Array Elements via Array SSA Form, Proceedings of the 5th International Symposium on Static Analysis, p.33-56, September 14-16, 1998
• 25: N. Schwartz. Sparse constant propagation via memory classification analysis. TR1999-782, Dept. of Computer Science, Courant Institute, NYU, March, 1999.
• 26: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
• 27: Peng Tu , David Padua, Gated SSA-based demand-driven symbolic analysis for parallelizing compilers, Proceedings of the 9th international conference on Supercomputing, p.414-423, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224648]
• 28: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 29: Peter Vanbroekhoven , Gerda Janssens , Maurice Bruynooghe , Henk Corporaal , Francky Catthoor, Advanced copy propagation for arrays, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 30: David Wonnacott, Extending Scalar Optimizations for Arrays, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.97-111, August 10-12, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Performance

Keywords:
array SSA, constant propagation, parallelization