Programmer specified pointer independence

ABSTRACT

Good alias analysis is essential in order to achieve high performance on modern processors, yet precise interprocedural analysis does not scale well. We present a source code annotation, #pragma independent, which provides precise pointer aliasing information to the compiler, and describe a tool which highlights the most important and most likely correct locations at which a programmer should insert these annotations. Using this tool we perform a limit study on the effectiveness of pointer independence in improving program performance through improved compilation.

REFERENCES

• 1: Jonathan Aldrich , Valentin Kostadinov , Craig Chambers, Alias annotations for program understanding, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 2: ANSI. Programming languages - C, 1999.
• 3: Mihai Budiu , Seth Copen Goldstein, Compiling Application-Specific Hardware, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.853-863, September 02-04, 2002
• 4: Mihai Budiu , Seth C. Goldstein, Optimizing memory accesses for spatial computation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 5: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 6: Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.57-69, June 18-21, 2000, Vancouver, British Columbia, Canada
• 7: David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 8: Jeffrey S. Foster , Tachio Terauchi , Alex Aiken, Flow-sensitive type qualifiers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 9: Rakesh Ghiya , Laurie J. Hendren, Putting pointer analysis to work, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.121-133, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268957]
• 10: Rakesh Ghiya , Daniel Lavery , David Sehr, On the importance of points-to analysis and other memory disambiguation methods for C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.47-58, June 2001, Snowbird, Utah, United States
• 11: Dan Grossman , Greg Morrisett , Trevor Jim , Michael Hicks , Yanling Wang , James Cheney, Region-based memory management in cyclone, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 12: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 13: Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999 [doi>10.1145/325478.325519]
• 14: Michael Hind , Anthony Pioli, Evaluating the effectiveness of pointer alias analyses, Science of Computer Programming, v.39 n.1, p.31-55, Jan. 2001 [doi>10.1016/S0167-6423(00)00014-9]
• 15: Joseph Hummel , Alexandru Nicolau , Laurie J. Hendren, A Language for Conveying the Aliasing Properties of Dynamic, Pointer-Based Data Structures, Proceedings of the 8th International Symposium on Parallel Processing, p.208-216, April 01, 1994
• 16: Intel Corporation. Intel Itanium 2 Processor Reference Manual, 2002.
• 17: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 18: Jin Lin , Tong Chen , Wei-Chung Hsu , Pen-Chung Yew, Speculative register promotion using Advanced Load Address Table (ALAT), Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 19: John Lu , Keith D. Cooper, Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.308-319, June 16-18, 1997, Las Vegas, Nevada, United States
• 20: Alexandru Nicolau, Run-time disambiguation: coping with statically unpredictable dependencies, IEEE Transactions on Computers, v.38 n.5, p.633-678, May 1989
• 21: Matthew Postiff , David Greene , Trevor Mudge, The store-load address table and speculative register promotion, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.235-244, December 2000, Monterey, California, United States [doi>10.1145/360128.360152]
• 22: A. V. S. Sastry , Roy D. C. Ju, A new algorithm for scalar register promotion based on SSA form, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.15-25, June 17-19, 1998, Montreal, Quebec, Canada
• 23: Standard Performance Evaluation Corp. SPEC CPU95 Benchmark Suite, 1995.
• 24: Standard Performance Evaluation Corp. SPEC CPU2000 Benchmark Suite, 2000.
• 25: Linus Torvalds. Managing kernel development. Presentation at Linux Lunacy Geek Cruise, September 2003.
• 26: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• 27: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Performance

Keywords:
alias analysis, memory performance, pointer independence