Darren C. Atkinson
William G. Griswold
ABSTRACT
Understanding large software systems is difficult. Traditionally, automated tools are used to assist program understanding. However, the representations constructed by these tools often require prohibitive time and space. Demand-driven techniques can be used to reduce these requirements. However, the use of pointers in modern languages introduces additional problems that do not integrate well with these techniques. We present new techniques for effectively coping with pointers in large software systems written in the C programming language and use our techniques to implement a program slicing tool.First, we use a fast, flow-insensitive, points-to analysis before traditional data-flow analysis. Second, we allow the user to parameterize the points-to analysis so that the resulting program slices more closely match the actual program behavior. Such information cannot easily be obtained by the tool or might otherwise be deemed unsafe. Finally, we present data-flow equations for dealing with pointers to local variables in recursive programs. These equations allow the user to select an arbitrary amount of calling context in order to better trade performance for precision.To validate our techniques, we present empirical results using our program slicer on large programs. The results indicate that cost-effective analysis of large programs with pointers is feasible using our techniques.
- 1.A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA, 1986. Google Scholar
Digital Library
- 2.D. C. Atkinson and W. G. Griswold. The design of wholeprogram analysis tools. In Proceedings of the 18th International Conference on So&are Engineering, pages 16-27, Berlin, Germany, March 1996. Google ScholarDigital Library
- 3.E. Duesterwald and M. L. Soffa. Demand-driven computation of inter-procedural data flow. In Proceedings of the 22nd ACM Symposium on Principles of Programming Languages, pages 37-48, San Francisco, CA, January 1995. Google ScholarDigital Library
- 4.M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the ACM ' 94 SIGPLAN Conference on Programming Language Design and Implementation, pages 20-24, Orlando, FL, June 1994. Google ScholarDigital Library
- 5.J. I. Gobat and D. C. Atkinson. The FElt system: User's guide and reference manual. Computer Science Technical Report CS94-376, University of California, San Diego, Department of Computer Science 8s Engineering, 1994.Google Scholar
- 6.W. G. Griswold and D. C. Atkinson. Managing the design trade-offs for a program understanding and transformation tool. Journal of Systems and Sofnyare, 30(1-2):99-l 16, July- August 1995. Google ScholarDigital Library
- 7.S. Horwitz, T. Reps, and M. Sagiv. Demand interproceduml dataflow analysis. In Proceedings of the 3rd ACM Symposium on Four&ions of Software Engineering, pages 104- 115, Washington, DC, October 1995. Google ScholarDigital Library
- 8.B. W. Kemighan and D. M. Ritchie. The C Programming Language. Prentice Hall, Englewood Cliffs, NJ, 2nd edition, 1988. Google ScholarDigital Library
- 9.J. Knoop and B. Steffen. The interprocedural coincidence theorem. In Proceedings of the 4th Intemational Conference on Compiler Construction, pages 125-140, Paderbom, Germany, October 1992. Google ScholarDigital Library
- 10.W. A. Landi, B. G. Ryder, and S. Zhang. Interprocedural modification side effect analysis with pointer aliasing. In Proceedings of the ACM SIGPLAN ' 93 Conference on Programming Lunguage Design and Implementation, pages 56-67, Albuquerque, NM, June 1993. Google ScholarDigital Library
- 11.M. M. Lehman and L. A. Belady, editors. Program Evolution: Processes of Sofrware Change. Academic Press, Orlando, FL, 1985. Google ScholarDigital Library
- 12.G. N. Naumovich, L. A. Clarke, and L. J. Osterweil. Verification of communication protocols using data flow analysis. In Proceedings of the 4th ACM Symposium on Four&ions of Softwure Engineering, pages 93-105, San Francisco, CA, November 1996. Google ScholarDigital Library
- 13.D. L. Parnas. On the criteria to be used in decomposing systems into modules. Communications of the ACM, X(12):1053-1058, December 1972. Google ScholarDigital Library
- 14.E. Ruf. Context-insensitive alias analysis reconsidered. In Proceedings of the ACM SIGPLAN ' 95 Conference on Programming Lunguage Design and Implementation, pages 13- 22, La Jolla, CA, June 1995. Google ScholarDigital Library
- 15.M. Shapiro and S. Horwitz. The effects of the precision of pointer analysis. In Proceedings of the 4th International Symposium on Static Analysis, pages 16-34, Paris, France, January 1997. Google ScholarDigital Library
- 16.M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In Proceedings of the 24th ACM Symposium on Principles of Programming Languages, pages l-14, Paris, France, January 1997. Google ScholarDigital Library
- 17.B. Steensgaard. Points-to analysis by type inference of programs with structures and unions. In Proceedings of the 6th Intemational Conference on Compiler Construction, pages 136-150, Linkoping, Sweden, April 1996. Google ScholarDigital Library
- 18.B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM Symposium on Principles of Programming Languages, pages 32-41, St. Petersburg Beach, FL, January 1996. Google ScholarDigital Library
- 19.B. Stroustrup. The C++ Programming Language. Addison- Wesley, Reading, MA, 2nd edition, 1991. Google ScholarDigital Library
- 20.M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.Google ScholarDigital Library
Index Terms
- Effective whole-program analysis in the presence of pointers
Recommendations
Effective whole-program analysis in the presence of pointers
Understanding large software systems is difficult. Traditionally, automated tools are used to assist program understanding. However, the representations constructed by these tools often require prohibitive time and space. Demand-driven techniques can be ...
Efficient points-to analysis for whole-program analysis
To function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large ...
Efficient points-to analysis for whole-program analysis
ESEC/FSE-7: Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineeringTo function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large ...
Comments