One way to define the behavior of a program is via a set of input/output pairs: the program transforms a given input into its corresponding output. This definition is adequate for a program's user, who wishes only to see the program's result. However, a view of the computation's internal state is essential for a program's implementor or maintainer, who must locate the problem when the program fails to produce the desired result. On the other hand, this model is not intended to capture the particulars of a machine-level view of a program's computational behavior. A machine-level model would include many details about an individual implementation, such as the machine's instruction set, that do not appear in and are not specified by a high-level language.

The purpose of the model is to define the view of execution that should be presented to a user by a source-level debugger. The debugger typically constructs its source-level view of a computation from a lower-level representation that is hidden from the programmer. The model developed in this section will be used in Chapter 3 to determine what the debugger's response to a given command should be at a given point in a computation.

This model was produced by combining Horning and Randell's view of sequential processes [Horning73] and the standard semantics of Algol-like languages. Although the resulting model is neither as general nor as precise as Horning and Randell's, it is well-suited for describing the expected behavior of a source-level debugger. A more formal treatment of much of the material in this section, though with a somewhat different emphasis, appears in Chapters 3 and 4 of Satterthwaite's dissertation [Satterthwaite75].

Programmers often envision a program's execution behavior in terms of a processor interpreting the source statements of the program. This processor has a set of state variables, which hold values of user-defined variables and auxiliary variables (used by the processor to execute the program). The program's execution can be described in terms of a sequence of values of these state variables. This sequence is called a computation.

An action specifies the transition from one state to the next: it assigns new values to some state variables; the remaining state variables keep their old values. The final state of a finite computation is a state for which no action is defined. A computation's action sequence is the sequence of actions performed to generate the computation. In general, a given action sequence does not completely specify a computation, because it could be applied to several initial states.

A program is a compact description of these state transitions and their sequencing. A program is executed by a processor. The state variables of a processor include:

In an Algol-like language, the transition from one state to the next involves changes to only the variables and the auxiliaries; the statements are constant over the program's execution. That is, the program cannot create new statements and execute them. (This is not true of LISP, for example.)

The most important auxiliary variable is the program counter, which identifies a program "portion" that is about to be executed. In general, the granularity, or level of detail, at which a program's execution can be viewed is dependent on the language definition. For a language that specifies the execution order within a statement, or for an expression language (such as Bliss [Wulf+71]), it might be an expression. For a language that does not specify the execution order of expressions within a statement, the granularity must be statement level or higher; in the typical language a statement is a reasonable program "portion". (Most Algol-like languages define "statement" recursively. Therefore the execution of a composite statement, such as a loop, generally implies the execution of several nested statements. A more complete computational model for Algol-like languages could also mark the end of execution of each composite statement.) The remainder of the discussion assumes statement granularity unless otherwise noted.

With the exception of dynamically-allocated variables (which can be handled by a simple extension), a user-defined variable can be thought of as having a conceptual lifetime that extends over the entire computation. Each variable has a type, which specifies the range of values it can assume. However, a single variable identifier can refer to different variables at different points in a computation. An environment is a mapping from identifiers to a subset of the variables. If a given environment associates a previously-used identifier with a new variable, the old variable is inaccessible in that environment. Algol-like languages are statically scoped, meaning that the environment is a function of a point in the program text (i.e., the program counter). In contrast, most dialects of LISP are dynamically scoped, meaning that the environment is a function of the point in the computation.

Variable binding is a related concept for the handling of dynamically-allocated variables. Algol-like languages permit recursion, implying that multiple instances of a particular variable can exist at the same time. For a given identifier, the correct instance of its variable (i.e., the binding of the identifier) is a function of the history of the currently active procedure calls, that is, the order of their occurrence and their data. At a given point in a computation, statements in an Algol-like language cannot refer to a different instance of a variable than that specified by the binding rule. To implement the binding of non-local variables, the processor keeps a history of the currently active procedure calls, called the procedure call chain, as part of the auxiliaries. At procedure entry and exit, the processor manipulates these auxiliaries to maintain the proper binding.

Therefore, the source-level view of a computation in an Algol-like language can be completely described by the constant program text (T) together with the sequence of values of the user-defined variables (V), the program counter (PC), and the procedure call chain (C). These are the items that the user will want to observe via the debugger to monitor the program's behavior. The first line of the following figure shows a fully-specified finite computation. The second line shows that the transformation from state si to its successor si+1 is caused by the execution of the piece of program text at PCi.

Note that the location of the statement that is about to be executed (i.e., the program counter) is an explicit element of the computational state. Therefore, a computation that executes the same actions on the same data, but that uses different copies of those actions (i.e., actions at some other location in the program text), is a different computation.

For ease of later reference, we informally partition the model into three parts: locations, data, and history. The location elements of a computation are the program counter and the action about to be executed at some state in the computation. The data elements of a computation are the variables and their values at some state in the computation. The history elements of a computation refer to the sequencing of code or data elements, such as the procedure call chain or the number of times that a given action was executed.

This source-level model is easily extended to handle multiple processes. Each process creates a separate computation, with its own program counter and procedure call chain. Variables and program text can be shared among more than one process. [We are not interested in methods for interprocess communication here.]

This source-level computational model is an abstraction; an executing program demonstrates observable behavior that is outside the model. Furthermore, the actual sequence of steps required to execute a program on a computer is much more detailed than this model suggests. To present a source-level view of a computation, a debugger must map these details into a correct source view and it must hide the parts of the implementation that are extraneous to the source view.

A program's computational behavior does not include any encoding of program or output timing, data or program storage particulars that the user might be able to deduce from the program's physical behavior, or audible cues from specific hardware (such as disks). These and other similar items are not directly specified by the high-level specification of the program; rather they are implied by the low-level implementation of the programming language, the operating system, the hardware, and so on. The definition of computational behavior constructed here expressly avoids defining all such behavior so as to avoid constraining the low-level implementation.

A computer could directly execute a program written in an Algol-like language, either by interpreting it or by having an instruction set that implemented the language. For efficiency and flexibility, a high-level program is usually translated into a lower-level representation that is more suited to the particular machine, frequently the native instruction set of the machine. This translation is performed by a compiler. Of course, a program's execution on an actual computer can be viewed at many different levels: the sequence of program statements, the sequence of machine instructions, the sequence of steps to perform each machine instruction (often in the form of microcode), the physical behavior of the circuits in the machine, etc. The source-level view is thus only one of several possibilities; it has the advantage of being the view formulated by the programmer.

A compiler translates each source statement into a sequence of lower-level instructions that carry out the actions specified by the statement. There are usually many distinct ways to accomplish these same actions; which one the compiler chooses does not affect the definition of program behavior we have already constructed. The compiler frequently uses temporary storage to hold intermediate results; where and how many of these temporaries exist is immaterial to the user. The compiler also selects particular arrangements of storage to hold values of user-defined variables. For example, most users are not concerned with whether array elements are stored by row or by column.

A single source program represents a possibly infinite number of computations, corresponding to different initial states (i.e., different inputs). If the program text contains no branches or procedure calls, then it specifies exactly one action sequence, which contains the same number of actions in precisely the same order as the program. But even a single action sequence can represent multiple computations for different input. If the program text contains conditional branches, the program specifies many different action sequences, depending on the program's input. If the program contains loops or procedure calls, the sequence of actions executed for a given input can be longer than the total number of actions in the program. When a program fails to specify a termination condition, the resulting computations are infinitely long. Analytically determining the sequence of actions and states that arise from a given input is at best tedious (for simple programs) and at worst virtually impossible (for complex ones). In fact, the major use of a debugger is to help programmers monitor program behavior, to pinpoint where in a computation a program begins to stray from its intended behavior.

A debugger that can monitor a computation can help a user with debugging, testing, and performance analysis activities. The important features for debugging are the following basic operations: reporting the current execution point, displaying the values of variables, setting and fielding breakpoints, and displaying the procedure call chain. For testing, a debugger can collect information for statement execution counts or data use counts, to ensure that all control paths and data configurations have been tested. Execution summaries can also isolate program areas that might profit from tuning.

To construct a program that embodies some function, the programmer constructs a series of steps that are intended to transform the input into the output, little by little. In the popular top-down programming methodology, the programmer decomposes the desired function into a series of large steps, then decomposes each of these steps into a series of smaller steps, and so on, until each step is a legal statement in the chosen programming language. As a result, the programmer is familiar with the program's steps and its data structures as they appear in the program text. It is a debugger's responsibility to communicate with the programmer in precisely these terms. For example, the programmer frequently associates assertions with specific program sections, such as "the value of y is non-negative here", or "the value of x is monotonically increasing in successive iterations of this loop". These assertions may be explicitly stated in the program (as special assertion statements [Sites72] or simply as tests that print a warning message) or they may be implicit, appearing only in comments or in the programmer's mind. A debugger must report the current execution location and the values of variables correctly to help the programmer verify implicit assertions of this kind during the program checkout process.

A programmer formulates questions about the computational behavior of a program and then translates the questions into the available debugging commands. The following examples show specific questions that a programmer might want answered, as opposed to general questions (such as, "Why does the value of x differ from the value that I expected at this program point?"). A sophisticated debugger might be able to answer these general questions directly.

Many debuggers permit the user to modify as well as monitor a computation. This section briefly describes the range of modification functions and their uses. These functions are discussed in less detail than the monitoring functions because they are somewhat less important, both for debugging and for this dissertation. Although Chapters 3 and 4 consider the effects of optimization on some modification functions, the implementation portion of this dissertation concentrates on the basic monitoring functions.

A debugger that can modify a computation can help a user with debugging, development, and testing activities. The ability to assign a value to a program variable or return to a point in the procedure call chain with a return value can accelerate debugging, allowing a programmer to get a program's execution back to its intended state so that further programming errors can be discovered during the rest of that computation. A debugger can be used for interactive program development if it allows a user to assign values to variables, call procedures, or create new variables, statements, or procedures whenever the execution of the program is suspended. A debugger that allows procedure calls and the assignment of values to variables aids the program testing process by allowing easy checkout of individual program components.

The basic modification commands are:

The basic debugging operations are to set a (location) breakpoint, to determine the current execution point, to display the value of a variable, and to display the procedure traceback.

To set a breakpoint, the debugger uses the mapping from source statements to object code locations to determine the object location corresponding to a given source statement. It places a breakpoint there (i.e., it ensures that the program execution will stop there so that the debugger and possibly the user can gain control of the computation). It also records the existence of the breakpoint at the source statement in an internal database, so that the user can list or remove the breakpoint later.

To determine the current execution point, the debugger uses the mapping from object code locations to source statements, applying it to the current program counter. This mapping usually has multiple levels, such as a mapping from absolute object locations to module names, a mapping from module-relative object locations to procedure names, and a mapping from procedure-relative object locations to source statements. [Note: these levels correspond roughly to loading, linking, and compiling, respectively.] The debugger can then report the source statement, procedure name, and module name to the user. Some debuggers use this function to field a breakpoint: the debugger determines the current execution point and searches its breakpoint database to see whether the user has requested a breakpoint at that source statement. Because unplanned debugger activity may occur at an object code location representing the middle of the execution of some program portion, the debugger may need to record more information to permit mapping object locations to source statements than it needs to permit mapping in the opposite direction.

To display the value of a variable, the debugger must know what source statement defines the variable environment to be used. By default, the debugger sets the environment from the current program counter, determining the current execution point as described above. Given a source statement, the debugger uses the mapping from identifiers to user-defined variables to get the type information for the variable and find its storage location. For a non-local variable, this operation involves accessing the procedure call chain in exactly the same way that a compiled variable reference might. The debugger then prints the contents of the storage location formatted according to the type.

To display the procedure traceback, the debugger accesses the current procedure call chain, which typically records object code return addresses. For each object code location in this chain, the debugger reports the corresponding source information, as described in the paragraph on determining the current execution point. The debugger can also report the values of local variables or parameters by using the source information to determine the correct environment.

The compiler is responsible for constructing mappings that allow a debugger to communicate with the programmer about a computation in source language terms. These mappings include information about the user-defined variables, the procedure history, and program locations. Some of this information is needed whether or not a debugger is present. The compiler needs the variable information to generate code correctly; most language support systems do not need this information during execution. The language support system needs the procedure call history information during execution to manage the program's control flow and to bind variables properly. Use of this information is compiled into the program's object code. Location information is needed by the debugger only.

Debugger implementations can be categorized by the amount of extra object code they require specifically for debugging support, in addition to the object code needed to compute the statements specified in the source program. Invasive debugger implementations include explicit calls to the debugger in the object code generated for the program. Semi-invasive debuggers require extra object code, but do not explicitly call the debugger. As a result, for invasive and semi-invasive debugger implementations, the user must specify a desire to debug a program before compiling it. To support a non-invasive debugger, a compiler places all debugging information in auxiliary tables, keeping the object code as small and as fast as when not debugging. The auxiliary tables can be kept in secondary storage until a debugging request is issued. A compiler supporting a non-invasive debugger can make the generation of the auxiliary debugging tables optional, thereby decreasing compilation size and speed when no debugging is desired, or it can create them during every compilation. If the compiler always generates the auxiliary tables, no special compilation directives are needed to allow later debugging activity.

This dissertation emphasizes non-invasive debuggers because they are more in keeping with the philosophy of optimization: the extra object code generated for invasive debuggers can consume a significant amount of execution time and space, even when no specific debugging requests (such as a breakpoint request) are active. Although advanced debugging capabilities, such as single-stepping, data breakpoints, or assertion-driven breakpoints, are easier to implement with invasive debuggers, they can also be implemented with non-invasive debuggers.

The primary objective of this research is to provide effective debugging tools for optimized programs. An essential property of any effective debugging tool is that it must be intelligible to a relatively naive user. A tool that can only be understood by compiler and optimizer experts is not sufficient.

A user will find it easiest to debug an optimized program if the debugger always responds exactly as it would for an unoptimized version of the same program. I call this property expected behavior for a given optimization. A debugger with expected behavior must present a restructured view of the actual state of the optimized program—a view that conforms to the source-level computational model. It hides the changes caused by the optimizations from the user, much as a source-level debugger hides the details of a lower-level implementation of an executing program. A less desirable but still acceptable alternative is to provide truthful behavior for an optimization. This means that the debugger avoids misleading the user: either it displays (in source program terms) how optimizations have changed the program portion under consideration, or it admits that it cannot give a correct response. Thus a debugger with truthful behavior acknowledges that optimizations have altered the program and its computational behavior. The user must participate in the restructuring of the program state. A debugger that has neither expected nor truthful behavior is likely to give incorrect and/or confusing responses to queries about an optimized program.

An example will help to characterize the distinction between expected and truthful behavior. Figure 2-2 is a repetition of Figure 1-1, in which the code motion optimization moves the assignment x←1 at statement 18 outside the loop, thereby reducing the program's execution time. The dead store elimination optimization then removes the unnecessary assignment x←0 at statement 15. As noted in Chapter 1, if the optimized program is stopped at statement 17 on the first time through the loop, a conventional debugger would report that the value of x is 1. According to the unoptimized program, x's value at that point would be 0. Therefore, a debugger with expected behavior for code motion would report that x's value is 0, even though x's storage location contains 1. Note that at subsequent arrivals at statement 17, the value of x is the same in the optimized and unoptimized program versions. To achieve expected behavior, the debugger must realize that the value of x is incorrect with respect to the source program on the first time through the loop; it must also be able to discover what the value of x should be. Truthful behavior is not as well-defined as expected behavior. Its primary goal is a negative one: to avoid hindering the user by reporting source-level information that may not be true; it can achieve this goal in a wide variety of ways, ranging from the extremely taciturn to the extremely voluble. In order of increasing informativeness, some examples of truthful responses are:

An argument stressing the importance of expected behavior, although in a setting of optimizations at the machine architecture level rather than at the program transformation level, appears in Johnson's paper on architectural requirements for source-level debugging [Johnson82b]:

A practical implementation of a system for providing expected debugging of optimized programs must have two additional properties. First, an optimized program that is capable of being debugged should not be larger or slower than an unoptimized version of the same program (although larger but faster might be tolerable on a large machine, and slower but smaller might be tolerable on a small machine). Ideally, adding debugging capabilities for optimized programs should not cost any extra execution time or space unless the debugger is actively responding to a user request. Second, the modified compiler and debugger should still be reasonably efficient in their use of time and space.

To be able to exploit the context of a program exception, as discussed in Chapter 1, the debugger must be available at any time during any execution of a program. Therefore, if a program exception is signalled, or if the user simply decides to monitor the progress of the computation, the debugger can display information about any piece of the executing program. This philosophy is particularly important in an experimental programming environment (such as the Cedar programming environment at Xerox PARC), in which a user typically calls upon several packages developed by other programmers. Such packages fail frequently enough to warrant instant availability of the debugger to explore the program state, but infrequently enough that implementors would not enable expensive prearranged debugging features. Using the debugger to monitor a program's use of such a package can also be a valuable tool for learning about the package.

The primary concern of this research is the achievement of certain levels of debugger functionality in an optimized setting. Several features of the debugging environment are relatively unimportant to this work; they may affect the implementation of a debugger for optimized programs, but they do not affect the basic concepts discussed here:

Programmers have long realized the benefits of debugging a program interactively using the language in which it was written. However, partially because of excessive optimism about error rates, debuggers have tended to trail behind advances in other parts of programming environments.

Interactive source-level debuggers for machine languages. The first programmers debugged their programs at the console of the computer. They watched console lights for a binary representation of the current program counter and register contents, and they set console switches to examine memory locations or to alter register or memory contents. They could start, stop, or single-step the machine directly.

Non-interactive low-level debuggers for assembly languages. After a time, programmers were banned from the machine room. By this time, programs were commonly written in an assembly language. If a program halted with an error, the programmer was given an octal dump of registers and memory to pore over in solitude. (In fact, this debugging method has survived until today on some machines, even for debugging high-level languages like Fortran or C [Thompson+75].)

Interactive source-level debuggers for assembly languages. With the advent of time-sharing machines, users could again debug their programs (written in assembly language) interactively. Two important debugging features were introduced with the FLIT debugger at MIT in 1959: the user-controlled breakpoint, and symbolic variable and procedure names [Evans+66]. Contents of registers and memory could be printed in a variety of formats: instruction format, characters, and octal and decimal numeric representations; after selecting the proper format, the programmer could examine program instructions or data in the same form as they appeared in the source program. Users could also modify values of variables and patch the program. To maintain the correspondence between the source and object versions of the program, advanced debuggers of this time copied patches created during the debugging process into the source representation of the program [Lampson65].

Non-interactive source-level or interactive low-level debugging for high-level languages. With the development of high-level languages, there were more alternatives. The easiest method was to insert statements to print values of variables or indications of control flow. This method required no knowledge of debugger commands (indeed, it works even when there is no debugger), but was not interactive. Another non-interactive method was exemplified by the Algol W debugger. When a runtime error was encountered, this debugger showed the program statement in which the error occurred and provided a symbolic memory dump: variables were identified by name and their values were formatted according to their declared types. The Algol W debugger also allowed contextual tracing of source statement executions, an idea based on proof by induction [Satterthwaite75]. [Note: Satterthwaite's dissertation is well worth reading. It gives an extraordinarily careful explanation of his implementation and its theoretical and historical underpinnings.] Users who insisted on interactive debugging capabilities were forced to use a machine-language debugger. These adventurous users had to understand compilation techniques to locate statement boundaries or to access array elements or fields within records.

Interactive source-level debuggers for high-level languages. As high-level languages matured, interactive source-level debuggers for high-level languages became available. By suppressing extraneous details and by interpreting low-level information from the high-level viewpoint, these debuggers translated the useful techniques that were available in earlier assembly language debuggers into high-level language terms. These techniques include breakpoints, displays of variable values, single-stepping, and traces. There are now many examples of interactive source-level debuggers for high-level languages, such as BAIL (a debugger for the SAIL language) [Reiser75], and pdx (a debugger for Pascal) [Linton81].

Much of debugging research over the past fifteen years has addressed the following fundamental debugging problem: an error may be detected much later in the program's execution than the time at which the program began to diverge from its intended behavior. This research centered on providing sophisticated monitoring capabilities and reverse execution.

Several systems were based on the idea of collecting a total history of a single computation; in such a system, the debugger is a post-processor that manipulates the completed "history tape". These systems freed users from examining a computation closely just in case an error might occur. However, this approach does have drawbacks: a post-processing debugger is necessarily read-only; it cannot modify a computation.

Balzer's EXDAMS system worked by modifying source programs to collect history information [Balzer69]. Executing the program created a history tape, which recorded statement executions and changes to variable values (similar to our computational model). The debugger answered user queries by examining the completed history tape. Because it dealt only with the history tape, the EXDAMS debugger was language-independent and extendable. The history tape could be played backward and forward at will. As a result, the debugger could perform complex analyses that were impossible for a conventional debugger, such as performing flowback analysis to determine what statement gave a variable its value. It could also present the succession of values of a given variable.

Pattis proposed a more ambitious history-based system [Pattis81]. It included a time-oriented langauge for constructing complex queries about a completed computation, such as: "Is ClearLine ever called twice in a row without an intervening call to FillLine?" It also proposed an efficient way to gather and manage the large amounts of history data, including background processing during user interactions and lazy evaluation.

The HELPER system could list the last several (50) assignment statements executed [Kulsrud69]. The AIDS system allowed retreating some number of instructions in a computation; a common use of this system was to specify that whenever the program terminated abnormally, the debugger should retreat and then trace forward to the error point [Grishman70].

Zelkowitz extended these ideas, providing a non-interactive system for reversible execution in Cornell's PL/C environment [Zelkowitz71]. The system stored the last 200 source-level steps of the computation to allow for reverse execution. The programming language was extended to include a RETRACE statement, which could reverse the program's execution 1) to a specified label, 2) for a certain number of steps, or 3) until some condition held. The RETRACE statement also specified a new statement to execute at that point; the statement could try to get the computation back on track or it could enable tracing or other debugging actions. The computation would then continue

Davis implemented a knowledge-based debugger for the PLATO system at the University of Illinois [Davis75]. Targeted at introductory computer science students, the system executed programs interpretively. When a program exception was encountered, the system used reversible execution and a database of common programming misconceptions to diagnose the source of the error and suggest a correction. Flowback analysis was a major part of this system also.

Several researchers built systems to display the values of variables graphically. Earlier display-based systems, such as the RAID system at Stanford [Petit75], had been able to monitor the values of a set of variables continuously without changing their locations on the display screen. Yarwood's non-interactive system drew pictures of arrays as sequences of values in a box. Variables used as array indices were shown as flags marking their current position in the array [Yarwood77]. The Incense system, implemented by Myers at Xerox PARC [Myers80], could display complex structures built up of records with embedded pointers. The user could also program Incense to display the values of certain variable types analogically, such as by a pie chart or bar chart. For instance, a variable of type Time could be displayed as the face of a clock.

Other recent debugging research has attempted to provide debugging capabilities in new environments, such as programming environments for robot arms and multiprocessor environments. These projects have generally focused upon providing the conventional debugging capabilities.

Mitchell L. Model addressed the problem of providing interactive source-level debugging for sophisticated artificial intelligence languages [Model79]. As an example of the kind of new problems these languages raise, displaying the changing locus of control is difficult for such languages because control is de-centralized. The problem faced by Model is quite similar to the one addressed in this dissertation: how to present a high-level view of a program's execution that is not a simple mapping from its actual implementation. The first half of his dissertation, in which he strongly motivates the need for an expected high-level view, is both interesting and enjoyable to read.

Goldman implemented a debugging environment for programming robot arms [Goldman82]. It included special-purpose data displays, such as a graphical presentation of the forces experienced by a given joint during a motion.

Researchers have recently begun to tackle the problems involved in debugging multiple processes and distributed systems, such as nondeterministic choices (that depend upon interprocess communication) and the inability to discover the relative execution order of statements in separate processors [Baiardi+83, Bates+83, Smith83]. Several proposed solutions involve recording interprocess events.

Another area of recent research involves unified program development environments that have no separable "debugger" [Archer81, Feiler82]. Instead, debugging commands are added to the source language. These environments typically support incremental program construction with the ability to modify a program and resume its execution.

A few researchers have considered the problem of debugging optimized programs. Their work is surveyed in Section 3.4.