Evicted variables and the interaction of global register allocation and symbolic debugging

ABSTRACT

A symbolic debugger allows a user to display the values of program variables at a breakpoint. However, problems arise if the program is translated by an optimizing compiler. This paper addresses the effects of global register allocation and assignment: a register assigned to a variable V may not be holding V's value at a breakpoint since the register can also be assigned to other variables. We define the problem of determining whether a variable is in its assigned register as the residence problem. Prior work on debugging of optimized code has focused on the currency problem; detecting whether a variable's run-time value is the expected value. Determining residence is a more serious problem than currency detection. We present a data flow algorithm that accurately computes a variable's residency, by determining when a variable becomes evicted from its register. We measure the effectiveness of different approaches to determine variable residence for three C programs from the SPEC suite.

REFERENCES

• 1: A. Adl-Tabatabai. Symbolic debugging of optimized C code. Unpublished draft from School of Computer Science, Carnegie Mellon University, 1992.
• 2: A. V. Aho, R. Sethi, and Unman J. D. Compilers. Addison-Wesley, 1986.
• 3: T. Bemmerl and R. Wismueller. Quellcode debugging yon global optimierten programmen. Presented at 1992 Dagstuhl Seminar, Feb. 1992. (in German).
• 4: Gary Brooks , Gilbert J. Hansen , Steve Simmons, A new approach to debugging optimized code, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.1-11, June 15-19, 1992, San Francisco, California, United States
• 5: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 6: Fred C. Chow , John L. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.501-536, Oct. 1990 [doi>10.1145/88616.88621]
• 7: M. Copperman. Debugging optimized code: Currentness determination with data flow. In Proc. Supercomputer Debugging Workshop '92, Dallas, October 1992. Los Alamos National Laboratory.
• 8: Max Copperman, DEBUGGING OPTIMIZED CODE WITHOUT BEING MISLED, University of California at Santa Cruz, Santa Cruz, CA, 1993
• 9: Max Copperman , Charles E. McDowell, DETECTING UNEXPECTED DATA VALUES IN OPTIMIZED CODE, University of California at Santa Cruz, Santa Cruz, CA, 1990
• 10: Max Copperman , Charles E. McDowell, A FURTHER NOTE ON HENNESSY''S ``SYMBOLIC DEBUGGING OF OPTIMIZED CODE'''', University of California at Santa Cruz, Santa Cruz, CA, 1992
• 11: D. S. Coutant , S. Meloy , M. Ruscetta, DOC: a practical approach to source-level debugging of globally optimized code, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.125-134, June 20-24, 1988, Atlanta, Georgia, United States
• 12: John Hennessy, Symbolic Debugging of Optimized Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.323-344, July 1982 [doi>10.1145/357172.357173]
• 13: S. Simmons. Personal communication. 1992.
• 14: David Wall , Amitabh Srivastava , Fred Templin, A note on Hennessy's “symbolic debugging of optimized code”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.176-181, Jan. 1985 [doi>10.1145/2363.215005]
• 15: Polle T. Zellweger, An interactive high-level debugger for control-flow optimized programs (Summary), Proceedings of the ACM SIGSOFT/SIGPLAN software engineering symposium on High-level debugging, p.159-171, January 1983 [doi>10.1145/800007.808029]
• 16: Polle Trescott Zellweger, Interactive source-level debugging for optimized programs (compilation, high-level), 1984

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures
      D.3.4 Processors
          Subjects: Optimization; Compilers

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Languages, Performance