Improving program slicing with dynamic points-to data

ABSTRACT

Program slicing is a potentially useful analysis for aiding program understanding. However, slices of even small programs are often too large to be generally useful. Imprecise pointer analyses have been suggested as one cause of this problem. In this paper, we use dynamic points-to data, which represents optimal or optimistic pointer information, to obtain a bound on the best case slice size improvement that can be achieved with improved pointer precision. Our experiments show that slice size can be reduced significantly for programs that make frequent use of calls through function pointers because for them the dynamic pointer data results in a considerably smaller call graph, which leads to fewer data dependences. Programs without or with only few calls through function pointers, however, show only insignificant improvement. We identified Amdahl's law as the reason for this behavior: C programs appear to have a large fraction of direct data dependences so that reducing spurious dependences via pointers is only of limited benefit. Consequently, to make slicing useful in general for such programs, improvements beyond better pointer analyses will be necessary. On the other hand, since we show that collecting dynamic function pointer information can be performed with little overhead (average slowdown of 10% for our benchmarks), dynamic pointer information may be a practical approach to making slicing of programs with frequent function pointer use more successful in reality.

REFERENCES

• 1: G. M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the AFIPS 1967 Joint Computer Conference, pages 483-485, Atlantic City, NJ, Apr. 1967.
• 2: L. O. Andersen. Program Analysis and Specialization for the C Programming Language. Ph.D. dissertation, University of Copenhagen, Department of Computer Science, May 1994.
• 3: Darren Carter Atkinson , William G. Griswold, The design and implementation of practical and task-oriented whole-program analysis tools, 1999
• 4: Darren C. Atkinson , William G. Griswold, The design of whole-program analysis tools, Proceedings of the 18th international conference on Software engineering, p.16-27, March 25-29, 1996, Berlin, Germany
• 5: Darren C. Atkinson , William G. Griswold, Effective whole-program analysis in the presence of pointers, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.46-55, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 6: Implementation Techniques for Efficient Data-Flow Analysis of Large Programs, Proceedings of the IEEE International Conference on Software Maintenance (ICSM'01), p.52, November 07-09, 2001
• 7: L. Beltracchi, J. R. Lyle, and D. R. Wallace. Using a program slicing CASE tool for evaluating high integrity software systems. In Proceedings of the 1996 American Nuclear Society International Topical Meeting on Nuclear Plant Instrumentation, Control and Human-Machine Interface Technologies, pages 1033-1039, University Park, PA, May 1996.
• 8: Leeann Bent , Darren C. Atkinson , William G. Griswold, A Comparative Study of Two Whole Program Slicers for C, University of California at San Diego, La Jolla, CA, 2001
• 9: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: M. A. Francel and S. Rugaber. The value of slicing while debugging. In Proceedings of the 7th International Workshop on Program Comprehension, pages 151-169, Pittsburgh, PA, May 2001,
• 11: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912]
• 12: 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
• 13: GrammaTech, Inc. Codesurfer user guide and reference manual.
• 14: Mary Jean Harrold , Ning Ci, Reuse-driven interprocedural slicing, Proceedings of the 20th international conference on Software engineering, p.74-83, April 19-25, 1998, Kyoto, Japan
• 15: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 16: Susan Horwitz , Thomas Reps , Mooly Sagiv, Demand interprocedural dataflow analysis, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.104-115, October 12-15, 1995, Washington, D.C., United States
• 17: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 18: Donglin Liang , Mary Jean Harrold, Reuse-Driven Interprocedural Slicing in the Presence of Pointers and Recursions, Proceedings of the IEEE International Conference on Software Maintenance, p.421, August 30-September 03, 1999
• 19: Donglin Liang , Mary Jean Harrold, Light-weight context recovery for efficient and accurate program analyses, Proceedings of the 22nd international conference on Software engineering, p.366-375, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337222]
• 20: M. Mock, D. C. Atkinson, C. Chambers, and S. J. Eggers. Gathering dynamic points-data and its incorporation in a program slicing tool for C programs. School of Engineering Technical Report COEN-2002-03-16, Santa Clara University, Department of Computer Engineering, Mar. 2002.
• 21: M. Mock, M. Berryman, C. Chambers, and S. J. Eggers. Calpa: A tool for automating dynamic compilation. In Proceedings of the 2nd Workshop on Feedback-Directed Optimization, pages 100-109, Haifa, Israel, Nov. 1999.
• 22: Markus Mock , Craig Chambers , Susan J. Eggers, Calpa: a tool for automating selective dynamic compilation, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.291-302, December 2000, Monterey, California, United States [doi>10.1145/360128.360158]
• 23: Markus Mock , Manuvir Das , Craig Chambers , Susan J. Eggers, Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-72, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379671]
• 24: H. D. Pande , W. A. Landi , B. G. Ryder, Interprocedural Def-Use Associations for C Systems with Single Level Pointers, IEEE Transactions on Software Engineering, v.20 n.5, p.385-403, May 1994 [doi>10.1109/32.286418]
• 25: Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.47-56, June 18-21, 2000, Vancouver, British Columbia, Canada
• 26: Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001 [doi>10.1145/383043.381532]
• 27: Marc Shapiro, II , Susan Horwitz, The Effects of the Presision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 28: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 29: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 30: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 31: F. Tip. A survey of program slicing techniques. J. Prog. Lang., 3(3):121-189, Sept. 1995.
• 32: F. Tip , T. B. Dinesh, A slicing-based approach for locating type errors, ACM Transactions on Software Engineering and Methodology (TOSEM), v.10 n.1, p.5-55, Jan. 2001 [doi>10.1145/366378.366379]
• 33: M. Weiser. Program slicing. IEEE Trans. Softw. Eng., SE-10(4):352-357, July 1984.
• 34: 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.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Experimentation, Languages, Measurement

Keywords:
dynamic analysis, points-to analysis, program slicing