Putting pointer analysis to work

ABSTRACT

This paper addresses the problem of how to apply pointer analysis to a wide variety of compiler applications. We are not presenting a new pointer analysis. Rather, we focus on putting two existing pointer analyses, points-to analysis and connection analysis, to work.We demonstrate that the fundamental problem is that one must be able to compare the memory locations read/written via pointer indirections, at different program points, and one must also be able to summarize the effect of pointer references over regions in the program. It is straightforward to compute read/write sets for indirections involving stack-directed pointers using points-to information. However, for heap-directed pointers we show that one needs to introduce the notion of anchor handles into the connection analysis and then express read/write sets to the heap with respect to these anchor handles.Based on the read/write sets we show how to extend traditional analyses like common subexpression elimination, loop-invariant removal and location-invariant removal to include pointer references. We also demonstrate the use of our information on more advanced techniques such as array dependence testing and program understanding. We have implemented our techniques in our McCAT C compiler, and we demonstrate examples of applying our methods on a set of pointer-intensive C benchmarks, as well as present concrete empirical data on the improvements achieved.

References

1. 1.A. V. Aho, R. Sethi, and J. D. Ullman. Compilcra -- Principles, Techniques, and Tools. Addison-Wesley Pub. Co., Reading, Mass., corrected edition, 1988.
2. 2.J. Auslander, M. Philipose, C. Chambers, S. J. Eggers, and B. N. Bershad. Fast, effective dynamic compilation. In Proc. of the A GM SIGPLAN '96 Go,}. on Programming Lang.uage Desi.~n and lmpl~m~ntntlon, pages 149-159, Philadelphia, Fenn., May 1996.
3. 3.T. M. Austin, S. E. Breach, and G. S. Sold. Efliclen~ detection of allpointer and array access errors. In Proc. of the A CM SIGPLAN "9~ Conf. on Proyrammin9 Long,age Design and Implementation, pages 290-301, Orlando, Flor., June 1994.
4. 4.D. Callahma, S. Cart, and K. Kennedy. Improving feaster alloca~iort for subscripted variables. In Proc. bf the SIGPLAN '90 Gonfl on Programminq Lan. guage Design and Implementation, pages 53-65, White Plains, N. Y., June 1990.
5. 5.D. R. Chase, M. Wegman, mad F. K. Zadeck. Analysis of pointers and structures. In Proe. o} the SIGPLAN '90 Gonf. on Programming Language Desiqn and Implementaa'tion, pages 296-310, White Plains, N. Y., June 1990.
6. 6.J.-D. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interprocedural computation of pointerinduced aliases and side effects. {n Conf_; Rec. of the ".l~entieSh Ann. ACM SIGPLAN-SIGACT Syrup. on Principles of Programming Languages, pages 232-245, Charleston, South Carolina, Jan. 1993.
7. 7.K.D. Cooper and J. Lu. Register promotion in C pro- ~rogmS. In Proc. of the A CM SIGPLAN '97 Conf. on ramming Language Design and Implementation, pages 308-319, Las Vegas, Nee., Jtm. 1997.
8. 8.A. Deutsch. A stordess model of aliasing and its abstractions using finite representations of right-rea-~lar equivalence relations. In Proc. of the 1992 Intl. Conf. on Computer Languages, pages 2-13, Oakland, Calif., Apr. 1992.
9. 9.A. Deutsch. Interprocedural may-alias analysis for ~v~inters: Beyond k-limiting. In Proc. Of the A CM SIG- AN '9g Uonf. on Programming Language Design and lmple'mentation, pages 230-241, Orlando, Flor., June 1994.
10. 10.M. Emami, R. Ghiya, and L. J. Hendren. Contextsensitive interprocedural points-to analysis in the presence of function pointers. In Proc. of the A GM SIC- PLAN '9J Conf-. on Programming Language Design and Imple'mentation, pages 242-256, Orlando, Flor., June 1994.
11. 11.R. Ghiya. Putting Pointer Analysis to Work. Phi) thesis, School of Computer Science, McGill University, November 1997. In Preparation.
12. 12.R. Ghiya and L. J. Hendren. Connection analysis: A practical interprocedural heap analysis for C. Intl. J. of Parallel Programming, 24(6), pages 547-578, 1996.
13. 13.R. Ghiya and L. J. Hendren. Is it a tree, a DAG, or a cyclic graph? a shape analysis for he_ap-~rec_ted_po'mt: ers in -{2. In Conf. Ree. of the 23rd A CM ~IGPI,AN- SIGA CT ,.qymp. on Principles of Programming Languages, pages 1-15, St. Petersburg, Flor., Jan. 1996.
14. 14.V. A. Guarna, Jr. A technique for analyzing pointer and structure references in parallel restructmJng compilers. In Proc. of the 1988 Intl. Conf. on Parallel Processing, volume II, pages 212-220, St. Charles, Ill., Aug. 1988.
15. 15.L. Hendren, C. Donawa, M. Emami, G. Gao, Justiani, and B. Sridharan. Designing the McCAT compiler based on a family of structured intermediate representations. In Proe. of the 5th lntl. Work. on Languages and Compilers for Parallel Computing, number 757 in Lec. Notes in Comp. Sci., pages 406-420, New Haven, Conn., Aug. 1992. Springer-Verlag. Publ. in 1993.
16. 16.L. J. Hendren and A. Nicolau. Parallelizing programs with recursive data structures. IEEE Trans. on Parallel and Distrib. Systems, 1(1):35-47, Jan. 1990.
17. 17.S. Horwitz, P. Pfeiffer, and T. Reps. Dependence grisly, sis for pointer variables. In Proe. of the SIGPLAN 89 Conf. on Programming Language Design and Implementation, pages 28-40, Portland, Ore., Jun. 1989.
18. 18.J. Hummd, L. J. Hendren, and A. Nicolau. A general data dependence test for dynamic, pointer-based data structures. In Proceedings of the A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 218-229, Odando, Flor., June 1994.
19. 19.W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proe. of the A CM SIGPLAN '92 Conf. on Programming Language Design and Implementation, pages 235-248, San Francisco, Calif., Jun. 1992.
20. 20.W. Landi, B. G. Ryder, and S. Zhang. Interprocedural modification side effect analysis with pointer aliasing. In Proe. of the A CM SIGPLAN "93 Conf. on Programming Language Design and Implementation, pages 56-- 67, Albuquerque, hi. Mex., Jun. 1993.
21. 21.C. Lapkowski and L. J. ttendren. Extended SSA numbering: Introducing SSAproperties to !a.~_g?aages with multi=level pointem, In Proceedings of CASCON'96, "lbronto, Ontario, Nov. 1996.
22. 22.J. R. Lan~ and P. N. Hilfinger. Detecting conflicts between structure accesses. In Proe. of the SIGPLAN "88 Conf. on Programming Language Design and Implementation, pages 21-34, Atlanta, Georgia, Jun. 1988.
23. 23.J. It. Larns and E. Schnarr. EEL: Machine~ independent executable editing. In Proc. of the A GM SIGPLAN "95 Conf. on Programming Language Design and Implementation, pages 291--300, La Jolla, Calif., Jun. 1995.
24. 24.C.-K. Luk and T. C. Mowry. Compiler-based prefetching for recursive data structures. In Proe. of_ the Seventh Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, pages 222- 233, Cambridge, Mass., Oct. 1996.
25. 25.A. Rogers, M. C. Carlisle, J. H. Reppy, and L. J. Hendren. Supporting dynamic data structures on distributed-memory mac/~es. A CM Trans. on Programming Languages and Systems, 17(2):233-263, Mar. 1995.
26. 26.E. Ruf. Context-insensitive alias analysis reconsidered. In Proc. of the A CM 3IGPLAN '95 Conf. on Programming Language Design and Implementation, pages 13- 22, La JolIa, Calif., Jun. 1995.
27. 27.M. Sagiv, T. Reps, and It. Wilhelm. Solving shapeanalysis problems in languages with destructive up dating. In Conf. Ree. of the 23rd A CM SIGPLAN- SIGtfCT Syrup. on Principles of Programming Languages, pages 16-31, St. Petersburg, Flor., Jan. 1996.
28. 28.M. Shapiro and S. Horwitz. The effects of the precision of pointer analysis. In Proceedings of the 1997 Static Analysis Symposium, Paris, France, Sep. 1997.
29. 29.M. Shapiro and S. Horwitz. Fast and accurate flowinsensitive points-to analysis. In Con}. Rec. of the ~jlth A CM SIGPLAN-SIGA CT Syrup. on Principles of Programming Languages, pages 1-14, Paris, France, Jan. 1997.
30. 30.R. M. Stallrnan. Using and Porting GNU CG. Cambridge, Mass., Jun. 1992. Available via anonymous ftp from prop. ai.r, it. edu.
31. 31.B. Steensgaard. Points-to analysis in almost linear time. In Conf. Rec. of the 23rd A CM SIGPLAN- SIGACT Syrup. on Principles of Programming Languages, pages 32-41, St. Petersburg, F}or., Jan. 1996.
32. 32.X. Tang, R. Ghiya, L. J. Hendren, and G. R. Gao. Heap analysis and optimizations for threaded programs. In Proe. of the 1997 Conf. on Parallel Architectures and Compilation Techniques (PA CT'97), San Francisco, Calif., Nov. 1997.
33. 33.R.P. WiLson and M. S. Lain. Efficient context-sensitive pointer analysis for C programs. In Proc. of the A CM SIGPLAN "95 Conf. on Programming Language Design and Implementation, pages 1-12, La Jolla, Calif., Jun. 1995.
34. 34.S. C. Woo, M. Ohara, E. Torrie, J. P. Shingh, and A. Gupta. The SPLAStt-2 programs: Characterization and methodological considerations. In Proc. of the ~2nd Ann. Intl. Syrup. on Computer Architecture, pages 24-36, Santa Margherita Ligure, Italy, Jtm. 1995.
35. 35.S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer aliasing: A step towards practical analyses. In Proceedings of the $th Symposium on the Foundations of Software Engineering, October 1996.

Index Terms

• Information systems

  • Information storage systems

    • Record storage systems

      • Record storage alternatives

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language features

• Theory of computation

  • Semantics and reasoning

    • Program constructs