Type-based alias analysis

ABSTRACT

This paper evaluates three alias analyses based on programming language types. The first analysis uses type compatibility to determine aliases. The second extends the first by using additional high-level information such as field names. The third extends the second with a flow-insensitive analysis. Although other researchers suggests using types to disambiguate memory references, none evaluates its effectiveness. We perform both static and dynamic evaluations of type-based alias analyses for Modula-3, a statically-typed type-safe language. The static analysis reveals that type compatibility alone yields a very imprecise alias analysis, but the other two analyses significantly improve alias precision. We use redundant load elimination (RLE) to demonstrate the effectiveness of the three alias algorithms in terms of the opportunities for optimization, the impact on simulated execution times, and to compute an upper bound on what a perfect alias analysis would yield. We show modest dynamic improvements for (RLE), and more surprisingly, that on average our alias analysis is within 2.5% of a perfect alias analysis with respect to RLE on 8 Modula-3 programs. These results illustrate that to explore thoroughly the effectiveness of alias analyses, researchers need static, dynamic, and upper-bound analysis. In addition, we show that for type-safe languages like Modula-3 and Java, a fast and simple alias analysis may be sufficient for many applications.

References

1. 1.Alfred V. Aho, Ravi Sethi, and Jeffrey D. UUman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
2. 2.John Banning. An efficient way to find side effects of procedure calls and aliases of variables. In Conference Record of the Sixth Annual A CM SIGA CT/SIGPLAN Symposium on Principles of Programming Languages, pages 29-41, San Antonio, Texas, January 1979.
3. 3.Rodney M. Bates. K-trees. Personal communication, November 1994.
4. 4.Michael Burke, Paul R. Carini, Jong-Deok Choi, and Michael Hind. Efficient flow-insensitive alias analysis in the presence of pointers. Technical Report 19546, film T.J. Watson Research Center, Yorktown Heights, NY, September 1994.
5. 5.Brad Calder, Dirk Grunwald, and Joel Emer. A system level perspective on branch architecture performance. In 28th International Symposium on Microarchitecture, pages 199-206, November 1995.
6. 6.David R. Chase, Mark Wegman, and F. Kenneth Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 296-310, 1990.
7. 7.Jong-Deok Choi, Michael Burke, and Paul Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of the Twentieth Annual A CM SIGA CT/SIGPLAN Symposium on Principles of Programming Languages, pages 232-245, Charleston, SC, January 1993.
8. 8.Keith Cooper and John Lu. Register promotion in c programs. In Proceedings of the A CM SIGPLAN '97 Conference on Programming Language Design and Implementation, Las Vegas, Nevada, June 1997.
9. 9.Keith D. Cooper and Ken Kennedy. Fast interprocedural alias analysis. In Conference Record of the Sixteenth Annual ACM SIGACT/SIGPZAN Symposium on Principles of Programming Languages, pages 49-59, 1989.
10. 10.Jeffery Dean, Greg DeFouw, David Grove, Vassily Litvinov, and Craig Chambers. Vortex: An optimizing compiler for object-oriented languages. In Proceedings of the A CM SIGPLAN '96 Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 83-100, San Jose, CA, October 1996.
11. 11.Saumya Debray, Robert Muth, and Matthew Weippert. Alias analysis of executable code. In Conference Record of the Twentyfifih Annual A CM SIGPLAN/SIGA CT Symposium on Principles of Programming Languages, 1998.
12. 12.Digital Equipment Corporation. DEC3000 300/400/500/600/800 Models: System Programmer's Manual, 1 edition, September 1993. First Printing.
13. 13.Amer Diwan. Understanding and improving the performance of modern programming languages. PhD thesis, University of Massachusetts, Amherst, MA 01003, October 1996.
14. 14.Amer Diwan, Eliot Moss, and Kathryn S. McKinley. Simple and effective analysis of statically typed object-oriented programs. In Proceedings of the ACM SIGPLAN '96 Conference on Object-Oriented Programming Systems, Languages, and Applications, San Jose, CA, October 1996.
15. 15.Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interprocedural Points-to analysis in the presence of function pointers. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 242-256, June 1994.
16. 16.Mary F. Fernandez. Simple and effective link-time optimization of Module-3 programs. In Proceedings of Conference on Programming Language Design and Implementation, pages 103-115, La Jolla, CA, June 1995. SIGPLAN, ACM Press.
17. 17.Rakesh Ghiya and Laurie J. Hendren. Putting pointer analysis to work. In Conference Record of the Twentyfifth Annual A CM SIGPLAN/SIGA CT Symposium on Principles of Programming Languages, 1998.
18. 18.John Hennessy and David Patterson. Computer Architecture A Quantitative Approach. Morgan-Kaufmann, 1995.
19. 19.Joseph Hummel, Laurie J. Hendren, and Alexandm Nicolau. A general data dependence test for dynamic, pointer-based data structures. In Proceedings of the A CM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 218-229, 1994.
20. 20.William Landi and Barbara O. Ryder. Pointer-induced aliasing: a problem classification. In Conference Record of the Eighteenth Annual A CM SIGA CT/SIGPI. AN Symposium on Principles of Programming Languages, pages 93-103, Orlando, FL, January 1991.
21. 21.William Landi and Barbara O. Ryder. Interprocedural side effect analysis with pointer aliasing. In Proceedings of the A CM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 235-248, San Francisco, CA, June 1992.
22. 22.James R. Larus and Paul N. Hilfinger. Detecting conflicts between structure accesses. In Proceedings of the A CM SIGPLAN '88 Conference on Programming Language Design and implementation, pages 21-34, Atlanta, OA, June 1988.
23. 23.Barbara Liskov and John Outtag. Abstraction and Specification in Program Development. MIT Press, 1986.
24. 24.Farshad Nayeri, Benjamin Hurwitz, and Frank Manola. Generalizing dispatching in a distributed object system. In Proceedings of European Conference on Object-Oriented Programming, pages 450-473, Bologna, Italy, July 1994.
25. 25.Oreg Nelson, editor. Systems Programming with Modula-3. Prentice Hall, New Jersey, 1991.
26. 26.Martin C. Rinard and Pedro C. Diniz. Commutativity analysis: A new analysis framework for parallelizing compilers. In Proceedings of the A CM SiGPLAN '96 Conference on Programming Language Design and Implementation, Philadelphia, PA, June 1996.
27. 27.Eric Ruf. Context-insensitive alias analysis reconsidered. In Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 13-22, La Jolla, CA, June 1995.
28. 28.Erik Ruf. Partitioning dataflow analyses using types. In pop197, Pads, France, January 1997.
29. 29.Marc Shapiro and Susan Horwitz. The effects of the precision of pointer analysis. In Pascal Van Hentenryck, editor, Lecture Notes in Computer Science, 1302, pages 16-34. Springer-Verlag, 1997. Proceedings from the 4th International Static Analysis Symposium.
30. 30.Marc Shapiro and Susan Horwitz. Fast and accurate flow-insensitive points-to analysis. In Conference Record of the Twentyf ourth Annual A CM SIGPLAN/SlGA CT Symposium on Principles of Programming Languages, Paris, France, January 1997.
31. 31.Amitabh Srivastava and Alan Eustace. ATOM: A system for building customizexl program analysis tools. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 196-205, Orlando, FL, June 1994. Association of Computing Machinery.
32. 32.Bjarne Steensgaard. Points-to analysis in almost linear time. In Conference Record of the Twentythird Annual A CM SIGPLAN/SIGA CT Symposium on Principles of Programming Languages, pages 32-41. Association of Computing Machinery, January 1996.
33. 33.Sun Microsystems Computer Corporation. The Java language specification, 1.0 beta edition, October 1995.
34. 34.David W. Wall. Limits of instruction-level parallelism. In Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 176-189, Santa Clara, California, 1991.
35. 35.William E. Weihl. interprocedural data flow analysis in the presence of pointers, procedure variables and label variables. In Conference Record of the Seventh Annual ACM SIGA ET/SIGPIAN Symposium on Principles of Programming Languages, pages 83-94, Las Vegas, Nevada, January 1980.
36. 36.Robert P. Wilson and Monica S. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of the A CM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 1-12, La Jolla, CA, June 1995. Association of Computing Machinery.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

• Theory of computation

  • Semantics and reasoning

    • Program constructs

      • Type structures