Symbolic pointer analysis

ABSTRACT

One of the bottlenecks in the recent movement of hardware synthesis from behavioral C programs is the difficulty in reasoning about runtime pointer values at compile time. The pointer analysis problem has been investigated in the compiler community for two decades, which has yielded efficient, polynomial time algorithms for context-insensitive analysis. However, at the accuracy level for which hardware synthesis is desired, namely context and flow sensitive analysis, the time and space complexity of the best algorithms reported grow exponentially with program size. In this paper, we present our first step towards a new analysis technology which potentially leads to almost-linear time complexity and sub-linear space complexity algorithm even for the most accurate analysis. The key idea that contributes to this efficiency is to implicitly encode the pointer-to relation in the Boolean domain, thereby capturing the procedure transfer function completely, compactly and canonically. This represents a wide departure from the traditional techniques, all of which explicitly capture pointer-to relation using variations of point-to graph, which have to be re-evaluated for different calling contexts. Experiments for our first flow-insensitive algorithm on common benchmarks show promising result.

REFERENCES

• 1: 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]
• 2: O. Andersen, Program Analysis and Specialization for the C Programming Language, Ph.D. thesis, Computer Science Department, University of Copenhagen, 1994.
• 3: 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
• 4: 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
• 5: O. Coudert, C. Berthet, and J. C. Madre, "A unified framework for the formal verification of sequential circuits," in Proceedings of the International Conference on Computer-Aided Design, November 1990, pp. 126--129.
• 6: O. Coudert , J. C. Madre, The implicit set paradigm: a new approach to finite state system verification, Formal Methods in System Design, v.6 n.2, p.133-145, March 1995 [doi>10.1007/BF01383965]
• 7: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 8: 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]
• 9: Sean Zhang , Barbara G. Ryder , William Landi, Program decomposition for pointer aliasing: a step toward practical analyses, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.81-92, October 16-18, 1996, San Francisco, California, United States
• 10: Donglin Liang , Mary Jean Harrold, Efficient Computation of Parameterized Pointer Information for Interprocedural Analyses, Proceedings of the 8th International Symposium on Static Analysis, p.279-298, July 16-18, 2001
• 11: L. Semeria and G. De Micheli, "Resolution, optimization, and encoding of pointer variables for the behavioral synthesis from c," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, February 2001.
• 12: Preeti Ranjan Panda , Luc Semeria , Giovanni de Micheli, Cache-efficient memory layout of aggregate data structures, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500026]
• 13: J. Zhu, Static memory allocation by pointer analysis and coloring, Proceedings of the conference on Design, automation and test in Europe, p.785-790, March 2001, Munich, Germany
• 14: S. Horwitz , T. Reps , D. Binkley, Interprocedural slicing using dependence graphs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.35-46, June 20-24, 1988, Atlanta, Georgia, United States
• 15: Donglin Liang , Maikel Pennings , Mary Jean Harrold, Extending and evaluating flow-insenstitive and context-insensitive points-to analyses for Java, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.73-79, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379676]
• 16: F. Somenzi, "CUDD: Binary decision diagram package release," http://vlsi.Colorado.EDU/~fabio/CUDD/cuddIntro.html, 1998.
• 17: L. Hendren et al, "Mccat compiler project," http://www-acaps.cs.mcgill.ca/~benadmin/benchmarks/.
• 18: W. Landi et al, "Prolangs analysis framework," http://www.prolangs.rutgers.edu.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware; Microprocessors and microcomputers

General Terms:
Algorithms, Design, Experimentation, Theory