This section discusses ways in which values of variables might be reported incorrectly when a conventional debugger is applied to an optimized program. Hennessy has considered this problem in some detail [Hennessy79].

Suppose that a debugger does not report the value predicted by the execution model for variable x at some arrival at program location p. From the system's point of view, the incorrect report can have several underlying causes:

From the user's point of view, the incorrect report can manifest itself in two different ways:

The preceding examples were carefully constructed to require only a straightforward mapping between source text and object code. This section describes difficulties with the program location: displaying the current location, displaying the current procedure traceback, setting the variable context, and setting and fielding breakpoints.

Recall that the debugger uses the mapping from program statements to object code locations to set breakpoints. It uses the mapping from object code locations to program statements to field breakpoints and display the current execution location. Obviously, if either of these mappings do not correctly reflect the correspondence between the source text and the object code, there will be problems with the associated debugger functions.

How should these mappings be defined? A conventional nonoptimizing compiler generates separate object code for each statement, in the order that the program statements appear in the source text. In this case, the beginning (or end) of the object code for a source statement is unique, and each object code instruction is part of the code for exactly one executable program statement. Some pieces of source text, such as ENDs or comments, may not generate any object code. For other pieces of source text, there may be several possible interpretations of what the corresponding object code is. For example, if a breakpoint is requested on a FOR statement, the breakpoint could refer to the initial entry to the statement or to the entry to each iteration. Similarly, if execution is interrupted inside loop control code at the end of a FOR loop, the source location could be reported as inside the last statement in the loop, as inside the ENDLOOP, or as inside the FOR loop header. Nevertheless, for a given language or debugger, once an interpretation for these cases is defined, the mapping between source text and object code is straightforward.

Optimization can complicate these mappings in several ways. First, an optimizing compiler may not emit any object code for an executable statement. Second, optimizations may preserve the order of execution of instructions that are meaningful to the programmer, while creating correspondences between the source text and the object code that are no longer monotonic. Finally, optimizations may rearrange the order of execution of programmer-specified instructions, causing several additional problems. These complications will be discussed in order of their complexity.

The preceding sections have shown the problems that optimizations cause for displaying values of variables and displaying current execution locations. The history element of a computation reflects sequences of variable values and/or execution locations, so naturally it will be affected as well. However, optimizations can change the history component of a computation without changing the other components.

For example, the effects of altering the order of evaluation of expressions can be visible even in a debugger with statement granularity. Suppose that register scheduling has interchanged two function calls inside a source statement so that fewer registers will be needed to perform the computation, as shown below. If the user traces the computation at medium or fine granularity, the execution ordering of the optimized program will be different than the user might expect. Similar changes would be seen if the user requests two breakpoints: one inside F and another inside G.

Many languages refuse to specify the order of evaluation of expressions so that the optimizer can perform such rearrangement freely. Nevertheless, similar problems with breakpoint or trace ordering arise if any expression containing a function call is moved, either to an earlier or later program point. For instance, if a common subexpression contains a call to the function H, hoisting its evaluation could cause breakpoints inside H to occur before other breakpoints. When such a common subexpression is stored to a compiler temporary, only these history aspects of the computation are affected. In contrast, hoisting an entire assignment statement causes incorrect variable values [as discussed in Section 3.2.1].

Additional complications arise if the debugger allows the values of variables to be modified. Recall that a roll-back variable is one whose assignment has been performed early, and a roll-forward variable is one whose assignment has been delayed. If a value is assigned to a roll-back variable from the debugger, then the variable will fail to take on the new value at the appropriate spot. If a value is assigned to a roll-forward variable from the debugger, the value will later be overwritten with the delayed store. In induction variable elimination, using the debugger to assign a value to the original induction variable will have no effect on the derived induction variable. In common subexpression elimination and hoisted stores, assigning to a component of the expression from the debugger will not affect the computed result (because it has already been performed). Similarly, using the debugger to assign a value to a component of an expression whose computation is delayed will cause a different value to be computed. Using the debugger to assign a value to a variable whose current value is in a register (or other faster memory) will have no effect. Using the debugger to assign a value to a variable that has participated in storage overlaying can have very strange results: the desired variable's value is not altered, and some other variable's value is changed. If the variable being assigned from the debugger had a constant value in that area of the original source, its value may have been propagated to other statements via constant propagation. Assigning a value to it from the debugger will have no effect; this situation is a special case of roll-back variables, in which the assignment is performed at compile time. If any of these values is later used to affect control-flow, even odder results may be seen.

These situations can be even worse if the programmer computes the new value to be assigned from the debugger by constructing expressions that use variables whose values are incorrect.

A similar problem is created when the value of a variable that remains constant throughout the program causes different code to be generated. Suppose that a variable has a constant value at compile-time, implying a particular control-flow. Then code to perform tests may be skipped over, or worse, deleted. The worst case occurs when a debugging variable is set to false in the beginning of a program and is used throughout the program to control debugging output. An optimizing compiler would typically remove all of the statements that produce debugging output as unreachable code; therefore, using the debugger to set the debugging variable to true cannot have the desired effect. Special debugging routines for printing or checking the integrity of data structures may also be removed by this transformation, and will hence not be available from the debugger. The compounded effects of constant propagation or other assumptions can also trigger different instruction selection during code generation or peephole optimization. If a variable's value is known to be 1, then an increment instruction may be used. Obviously the real problem here is that the variable's value was frozen at compile-time. Similarly, if a variable's value is known at compile-time to fit in one byte, then the compiler will allocate storage and generate instructions accordingly, with disastrous results if a value set from the debugger exceeds the one-byte size limit.

This brings up the subject of runtime checking. Checks may be moved outside of loops or removed altogether based on the structure of the written program. Altering the values of variables from the debugger may well invalidate those assumptions, and the protection of the checks may be subverted. It is difficult (perhaps even impossible) to detect these second-order effects.

This section considers the effects of optimization on several more complicated debugger capabilities: single-stepping, data breakpoints, and assertion-driven breakpoints. It also considers the use of a debugger as a performance monitoring tool.

The Firmware Development System (FDS) was an experimental programming environment for microprocessors developed at IBM Yorktown [Warren+78]. Microprograms were written in a version of PL/I tailored for systems programming, compiled by a cross-compiler on a larger computer, and downloaded onto the microprocessor. Optimizations were considered essential for the microprocessor environment. Since programming errors were acknowledged as inevitable, some provision for debugging optimized programs had to be made. The FDS system was intended to furnish two modes of compiler/debugger operation. In "full optimization" mode, the proposed debugger would have tersely explained the ways in which optimizations had affected the program. Even for sophisticated users, this mode would have fallen short of providing truthful behavior. In "no source change" mode, optimizations could involve only compiler-introduced temporaries, or could occur only within a statement. In this mode, the FDS debugger could almost provide expected behavior. Complete recompilation and re-execution would have been required to switch from one mode to the other.

The FDS system intended to implement a wide range of optimizations, from global optimizations to register allocation to object code optimizations, as well as a complete set of debugging capabilities, including breakpoints, displaying and modifying values of variables, and single-stepping. Its foremost goal was to help experienced programmers construct correct optimized programs for a microprocessor; it had no underlying philosophy or rules of debugging, such as providing expected or truthful behavior. Its primary approach to debugging optimized programs was to add static information: In "full optimization" mode, the optimizer would collect a variety of pre-computed tables during its optimization phases, such as an augmented storage map containing lists of storage locations for each variable at each source statement. In "no source change" mode, the optimizer would not collect special information.

The FDS debugger planned to provide expected behavior only in its references to variables at breakpoints: using the augmented storage map, the debugger would have automatically translated a reference to a variable into an access of its current storage location(s). For other user interactions, the debugger would have provided only semi-truthful behavior. The debugger used only a syntactic statement mapping, so that execution would appear to progress in the expected way through the source program rather than jumping about randomly [see Section 3.2.2.3]. To handle code-reordering optimizations, the compiler would have recorded the movement of variable assignments and uses (by number only) that could affect or be affected by the values of variables at a given source statement. When the user asked to display or modify the value of an affected variable, the debugger would have listed all relevant assignments and uses that the optimizer had inserted or deleted. This technique was a step in the right direction, but it was hampered by the debugger's sole use of the syntactic statement mapping, as well as some skimpiness and inefficiency in its pre-computed tables. No attempt was made to reconstruct variable values. Furthermore, the FDS system made no provision for describing the state of a computation that was suspended between statement boundaries (for example, due to a program exception), either in statement mapping or in variable storage mapping. Optimizations that create one-to-many and/or many-to-one correspondences from source statements to object code locations, such as inline procedure expansion and cross-jumping, would not have been handled well either.

Unfortunately, the FDS debugger project lasted only long enough to produce a design document, so no information is available regarding its performance or its effectiveness [Warren82].

Hennessy considered a more restricted problem: providing the most critical debugging features (displaying variable values, setting breakpoints, and reporting error locations) in the presence of some selected local and global optimizations [Hennessy79]. The local optimizations include common subexpression elimination, redundant store elimination, and code reordering. The global optimizations include code motion, induction variable elimination, and dead store elimination. These optimizations are sufficient to cause large differences in code ordering between the source text and the optimized object code. Because of the more complex problems associated with modifying the values of variables from the debugger, Hennessy disallowed that feature.

Rather than pre-computing a variety of tables that might be useful at runtime, as the FDS system did, Hennessy assumed that the compiler would record the augmented global flowgraph used during the optimization process and the debugger would process the flowgraph as needed. Each node of the augmented flowgraph was a directed acyclic graph, representing one basic block of both the unoptimized and the optimized programs. Hennessy developed algorithms for processing the flowgraph at runtime that can usually detect when a variable's value is incorrect in terms of the source program. Furthermore, his algorithms can sometimes correct such values to display the expected value. He did not directly address the problem of finding the correct storage location for a variable's current value.

In contrast to the FDS system, Hennessy used only a semantic statement mapping. As a result, the user could set a breakpoint to view the old value of a variable before an assignment without any concern about the effects of optimizations. Also, when reporting the location of a synchronous program exception, the semantic mapping indicates the statement responsible for the exception. However, the use of the semantic mapping restricted breakpoint placement for some common subexpression evaluations: when the start of multiple source statements corresponded to the same object code, a breakpoint was permitted only on the lexically first such statement.

Hennessy's algorithms were implemented and tested on a small group of programs to demonstrate their correctness and feasibility, but they have not yet been incorporated into any program development system.

In an unpublished manuscript, Teeple and Anderson briefly discussed an even more restricted problem: how to set breakpoints in the presence of the cross-jumping optimization [Teeple+80]. As described in Section 3.2.2.2, this optimization merges identical tails of joining code paths, thereby causing one object code instruction to correspond to multiple source statements. At a breakpoint in the common code, the debugger needs help to determine which source statement is executing. Teeple and Anderson sketched an algorithm to identify "disambiguator points" for one of the two paths to each merged region during the application of cross-jumping. They also noted flowgraph conditions under which no disambiguator points exist. Finally, they suggested a way that the debugger could use the disambiguator points at runtime to determine which statement is really executing. Their scheme was based upon tracing and breakpoints that are invisible to the user. If there were no disambiguator points, the debugger would reply with a list of the possibilities. This work provided the initial idea for the way that Navigator handles cross-jumping, which is explained in the second part of this dissertation. Since their technique was never fully designed or implemented [Teeple81], its description is incomplete. Among other things, they did not realize that merging less than an entire statement still requires path determination, and they did not discover that repeated cross-jumping can cause nested determiners.

As in the FDS system described earlier, Feiler also suggested that debugging for optimized programs should be provided by using multiple levels of optimization [Feiler82]. For each procedure or module, the user would select one of four optimization levels. The more optimized a region of the program, the less debugging support it would receive. While the FDS environment is reasonably conventional, Feiler's environment, called LOIPE, has some novel features: it adds debug statements to the source language and is based entirely upon incremental compilation. The debugger has no special access to the compiled object code.

LOIPE is an interactive programming environment for incremental program construction based on compilation. It provides a uniform view of all system actions through a syntax-directed editor—the user never sees the traditional edit-compile-execute-debug cycle. The user makes a debugging request by editing a debug statement, such as BREAK or TRACE, into the source program. In response, the system automatically recompiles and relinks that portion of the program and then resumes program execution. Similarly, the user can modify the executing program to insert new declarations or arbitrary program statements. The modified program can be resumed from the point of suspension as long as no active procedure has been changed in a semantically-inconsistent way. When this fails, the procedure call chain can sometimes be unwound to the earliest call of a modified procedure. Otherwise, the program must be restarted from the beginning. Note that the ability to resume execution after inserting a debug statement and recompiling the enclosing procedure is central to this debugging approach. The system does not permit user interrupts.

Procedures compiled without optimization would have full debugging support for program modification and resumption, as described above. Program execution can always be resumed after debug statements are added or removed.

In contrast, an optimized procedure would receive restricted debugging support. No attempt would be made to use information collected by the optimizer to hide the effects of the optimizations or to present alternatives. Nevertheless, Feiler claims that the debugger would provide a limited form of truthful behavior: it would only report variable values and current execution locations that can be shown consistently. [He does not describe how the debugger would determine which items fall into this class.] For example, only variables whose current values are not in registers can be displayed, and the current execution point might not be reported uniquely. The system would not support execution traces of optimized procedures. Furthermore, if the programmer makes any modification to an active optimized procedure (including adding or removing debug statements), that procedure would be recompiled without optimizations, and the procedure call chain would be unwound to allow resumption from the calling statement.

Two intermediate optimization levels would mitigate the adverse effects on debugging facilities. At "full debugging" level, the optimizer would not allow any optimization to cross any procedure call or debug statement. At "complete display" level, the optimizer would not cache data values in registers across procedure calls or debug statements. As a result, values of variables could be displayed for all active procedures at a breakpoint. However, this level does not address the issue of incorrect values resulting from computation-reordering optimizations.

All of this discussion represents design work; the prototype implementation of LOIPE did not include specific support for debugging optimized programs.