Please do not modify this page directly. Instead, send suggestions to the author.
- A plan to fix local variable debug information in GCC
by Alexandre Oliva <aoliva@redhat.com>
- 2007-12-20 draft
Introduction
The DWARF Debugging Information Format, version 3, determines the ways a compiler can communicate the location of user variables at run time to debug information consumers such as debuggers, program analysis tools, run-time monitors, etc.
One possibility is that the location of a variable is fixed throughout the execution of a function. This is generally good enough for unoptimized programs.
However, for optimized programs, the location of a variable can vary. The variable may be live for some parts of a function, even in multiple locations simultaneously. At other parts, it may be completely unavailable, or it may still be computable even if no location actually holds its value. The encoding, in these cases, can be a location list: tuples with possibly-overlapping ranges of instructions, and location expressions that determine a location or a value for the variable.
Historically, GCC started with the simpler, fixed-location model. In fact, back then, there weren't debug information formats that could represent anything better than this.
More recently, GCC gained code to keep track of varying locations, and to emit debug information accordingly. Unfortunately, very many optimization passes discard information that would be necessary to emit correct and complete variable location lists.
Coalescing, scalarizing, substituting, propagating, and many other transformations prevent the late-running variable tracker from doing a complete or even accurate job. By the time it runs, many variables no longer show up in the retained annotations, although they're still conceptually available.
The variable tracker can't handle sharing of a location by multiple user variables, multiple active locations for the same variable, and it can't tell when a variable is overwritten, if the assignment is optimized away. This last limitations is inherent to a model based on inspecting only actual code, and trying to make inferences from that. In order to be able to represent not only what remained in the code, but also what was optimized, combined or otherwise apparently-removed, additional information needs to be kept around.
This paper describes an approach to maintain this information.
Goals
Correctness
Ensure that, for every user variable for which we emit debug information, the information is correct, i.e., if it provides locations or value expressions for a variable in a certain range of instructions, then, for all instructions in that range, the values specified in the debug information must match the value the user variable is bound to.
We say a variable is bound to a value when control flow crosses a theoretical instruction placed at the point of the program in which the user variable is, or should be have been, assigned that value. This theoretical instruction is maintained roughly in place regardless of optimizations that move, remove or otherwise optimize any code generated to implement the source-level variable modification. More details below, in the "scheduling and reordering" section.
Completeness
Try to ensure that, if the value of a variable is a known constant at a certain point in the program, this information is present in debug information.
Try to ensure that, if the value of a variable is available at any location, or computable from values available at any other locations at a certain point in the program, this information is present in debug information.
Run-time efficienty
Stop missing optimizations for the sake of preserving variable location debug information.
Compile-time efficienty
Avoid using additional memory and CPU cycles that would be needed only to generate debug information when compiling without generating debug information.
Internal Representation
For historical reasons, GCC has two completely different, even if nearly isomorphic, internal representations: trees and RTL. This decision has required a lot of code to be duplicated for low-level manipulation and simplification of each of these representations.
Since tracking variables and their values must start early to ensure correctness, and be carried throughout the complete optimization process, it might seem tempting to introduce yet another representation for debug information, decaying both isomorphic representations into a single debug information representation. The drawbacks would be additional duplication of internal representation manipulation code, and the possibility of increasing memory use out of the need for representing information in yet another format.
Another concern is that even the simplest compiler transformations may need to be reflected in debug information. This might indicate a need for modifying every point of transformation in every optimization pass so as to propagate information into the debug information representation. This is undesirable, because it would be very intrusive.
But then, keeping references to the correct values, expressions or variables, as transformations are made, is precisely what optimization passes have to do to perform their jobs correctly. Finding a way to take advantage of this is a very non-intrusive way of keeping debug information accurate. In fact, most transformations wouldn't need any changes whatsoever: uses of variables in debug information can, in most optimization passes, be handled just like any other uses.
Once this is established, a possible representation becomes almost obvious: statements (in trees) or instructions (in rtl) that assert, to the variable tracker, that a user variable or member is represented by a given expression, or that bind a user variable to a value:
# DEBUG var => expr
By var, we mean a tree expression that denotes a user variable, for now. We envision trivially extending it to support components of variables in the future.
By expr, we mean a tree or rtl expression that computes the value of the variable at the point in which the statement or instruction appears in the program, and that the variable is expected to hold until (i) execution crosses another such annotation for that variable, or (ii) the value becomes no longer computable, because all locations containing it or usable to compute it are no longer provably usable to compute it. For example, if the variable is bound to the value of a certain hardware register, and the register is subsequently modified, but the bound value is not known to be available elsewhere, then the variable is regarded as unavailable at that point.
A special value needs to be specified for each debug annotation representation that denotes an unavailable variable. Although in some cases this condition can be detected implicitly, as described above, in others we must be able to describe that, at the point of the binding, the value that should be bound to the variable is not available, for example, because it was completely optimized away and it's not even computable any more, or because the compiler has been unable to represent or to keep track of the expected value of the variable at that point.
Also, it might be useful to represent the expression as a list of expressions, to establish larger equivalence classes to begin with and to get better resistance against complete loss of values. It may also be useful distinguish lvalues from rvalues in the representation, but for now we're keeping it simpler, to see if we can make do without the additional complexity.
Generating debug information
Generating initial annotations when entering SSA is early enough in the translation that the program will still reflect very reliably the original source code. We will only emit such annotations for user variables that are GIMPLE registers, i.e., variables that present in the source code, that are not addressable and that hold scalar values. Addressable or non-scalar user variables don't have varying locations, so we don't need these annotations to generate correct debug information for them.
As optimizations transform the code, the initially-trivial mapping between such user variables and implementation locations gets more and more fuzzy. Even when the compiler retains mnemonic names that resemble user variable names for such implementation locations (GIMPLE registers, RTL pseudos, hardware registers and stack slots), it is important to keep in mind that source- and implementation concepts are in different name spaces, and that the implementation locations cannot be assumed to remain associated with the user variables they were initially named after.
The purpose of the annotations is precisely to establish a mapping from user variables to implementation concepts without preventing optimizations. The choice of focusing not so much on locations, but rather on values, is intended to minimize the impact of optimizations on the ability to represent the value a variable holds, which is what debug information consumers are most often interested in. Actual locations are a slightly secondary issue, that we expect to be able to infer from the value binding annotations, but that may require more explicit annotations, as mentioned above.
After every assignment to user variables that are GIMPLE registers, we emit a DEBUG statement that will preserve, throughout compilation, the information that, at that point, the user variable was bound to the value of that expression. So, after putting an assignment such as the following in SSA form, we emit the debug statement below right after it:
x_1 = whatever; # DEBUG x => x_1
Likewise, at control flow merge points, for each PHI node associated with a user variable we introduce in the SSA representation, we emit an annotation:
# x_4 = PHI <x_1(3), x_2(4), x_3(7)>; # DEBUG x => x_4
Then, we let tree optimizers do their jobs. Whenever they rename, renumber, coalesce, combine or otherwise optimize a variable, they will most likely automatically update debug statements that mention them as well.
In the rare cases in which the presence of such a statement might prevent an optimization, we need to adjust the optimizer code such that the optimization is not prevented. This most often amounts to skipping or otherwise ignoring debug statements. In a few rare cases, additional code might be needed specifically to adjust debug statements.
During conversion to RTL, the debug statements also decay to debug instructions, and the tree value expressions are trivially converted to RTL. Conceptually, however, it's still the same representation: a binding from user variable to expression. RTL optimizers will most often adjust debug instructions automatically.
The exceptions can be handled often at no cost: the test for whether an element of the instruction stream is an instruction or some kind of note (that never needs updating) is a range test, in its optimized form. By placing the identifier for a debug instruction at one of the limits of this range, testing for ranges that include or exclude debug instructions requires identical code, except for the constants.
Since most code that tests for INSN_P and handles instructions can and should match debug instructions as well, in order to keep them up to date, we extend INSN_P so as to match debug instructions, and modify the code in the exceptions, that need to skip debug instructions, by using an alternate test, with the same meaning as the original definition of INSN_P. These simple and non-intrusive changes are relatively common, but still, by far, the exception rather than the rule. As in tree level, there are transformations that require special handling of debug annotations, but these are even rarer.
When optimizations are completed, including register allocation and scheduling, it is time to take the data collected in debug instructions and emit debug information out of them. Conceptually, the debug instructions represent points of assignment, at which a user variable ought to evaluate to the annotated expression, maintained throughout compilation. However, when the value of a user variable is available at more than one location (think, for example, stack variable temporarily held also in a register), it is important to note it, such that, if a debugging session attempts to modify the variable, all copies are modified.
The idea is to use some mechanism to determine equivalent expressions throughout a function (say some variant of Global Value Numbering). At debug instructions, we assert that the value of the named variable is in the equivalence class the expression belongs to. As we scan basic blocks forward and find that expressions in an equivalence class are modified, we remove them from the equivalence class, and thus from the list of available locations for the variables that hold that value. When members of an equivalence class are copied, we add the copies to equivalence class. At function calls and volatile asm statements, we remove non-function-private memory slots from equivalence classes. At function calls, we also remove call-clobbered registers from all equivalence classes. When no live expression remains in the equivalence class that represents a variable, it is understood that its value is no longer available. At basic block confluences, we combine information from the end states of the incoming blocks and the block-entry debug statements that had been added after PHI nodes earlier.
When multiple variables are held in the same equivalence class, some care must be taken to determine which locations can be used as modifiable copies of a variable and which hold incidental copies. More investigation is needed to design strategies to make this partitioning, such that the end result is accurate debug information.
Also, except for transformations that require special handling to update debug annotations properly but that haven't been improved accordingly, debug information should come out as complete as possible.
Scheduling and reordering
Optimizing code involves a lot of moving code around. Basic block reordering, loop unrolling, and other forms of code duplication, movement or removal that affect placement of sequences of instructions, but not so much the instructions to be executed in a given execution path, have no effect on the debug information annotations presented in this article. When moving, duplicating or removing code along these lines, debug annotations can be regarded just like regular instructions.
Other than that, debug annotations should generally remain in place, serving as guides for what would amount to the natural execution order of the program, regardless of optimizations that reorder instructions, move instructions out of loops or conditionals.
For example, if we move to an unconditional block a computation that was only to be performed inside a conditional, the debug annotation that binds the variable to the conditionally-computed value should remain in the conditional block, unless it is completely eliminated. Likewise, if some computation is hoisted out of a loop, the debug annotation should remain in the loop, where the user expects the assignment to take place.
Moving a computation to an earlier point shouldn't require modification in subsequent debug annotations, but moving it to a later point may, especially when the move crosses the annotation. For example, if an assignment instruction, say x = y, is moved past the end of a loop, debug annotations that refer to x in their expressions probably need to have it replaced with y, such that the binding remains with the same value in spite of the assignment move.
Transformations that reorder instructions within a single block, such as instruction scheduling, don't require modification of annotations. Debug annotations should be maintained after the assignments they refer to, if the assignments are still nearby, and this is trivially accomplished through scheduling dependencies. Other than that, debug annotations should generally have high scheduling priority, such that they are kept right after the corresponding assignment, or moved early when an assignment was hoisted out of a loop. That said, reordering debug annotations may be undesirable and surprising at times. Also, care must be taken to not schedule too early bindings for values that are completely optimized away: because these have no dependencies, they might be moved too early, to the point of making the range of the previous binding an empty range.
Testability
Since debug annotations are added early, and, in most cases, maintained up-to-date by the same code that optimizers use to maintain executable code up-to-date, debug annotations are likely to remain accurate throughout compilation.
The risk of this approach is that the annotations get in the way of optimizations, thus causing executable code to vary depending on whether or not debug information is to be generated. The risk of varying code could be removed at the expense of generating and maintaining debug annotations throughout compilation and just throwing them away at the end. This is undesirable, for it would slow down compilation without debug information and waste memory while at that.
Therefore, we've built testing mechanisms into the compiler build machinery to detect cases in which the presence of debug annotations would cause code changes.
The bootstrap-debug Makefile target, by default, compiles the second bootstrap stage without debug information, and the third bootstrap stage with it, and then compares all object files after stripping them, a process that discards all debug information.
Furthermore, bootstrap4-debug, after bootstrap-debug and prepare-bootstrap4-debug-lib-g0, rebuilds all target libraries without debug information, and compares them with the stage3 target libraries, built with debug information.
At the time of this writing, both tests pass on platforms x86_64-linux-gnu and i686-linux-gnu, and ppc64-linux-gnu and ia64-linux-gnu are getting close.
Additional testing mechanisms should be built in, to exercise a wider range of internal GCC behaviors and extensions, for example, by comparing the compiler output with and without debug information while compiling all of its testsuite.
Even if testing mechanisms fail to catch an error, the generation of debug annotations is controlled by a command-line option, such that any code changes caused by it can be easily avoided, at the expense of the quality of the debug information.
Testing for accuracy and completeness of debug information can be best accomplished using a debugging environment. For example, writing programs of increasing complexity, adding functional-call or asm probe points to stabilize the internal execution state, and then examining the state of the program at these probe points in a debugger, shall let us know how accurate and how complete variable location information is.
Measuring accuracy is easy: if you ask for the value of a variable, and get a value other than the expected, there's a bug in the compiler. If you get "unavailable", this can still be regarded as accurate, for locations are always optional. However, it might be incomplete. Telling whether the variable was indeed optimized away, or whether the value is available or computable but the information is missing, is a harder problem, but it's not part of the accuracy test, but rather of the completeness test.
A completeness score for an unoptimized program might very often be unachievable for optimized programs, not because the compiler is doing a poor job at maintaining debug information, but rather because the compiler is doing a good job at optimizing it, to the point that no possibility remains of computing the value of certain variables at certain points in the program. This should be taken into account when desigining completeness tests.
Concerns
Memory consumption
Keeping more information around requires more memory; information theory tells us that there's only so much information you can fit in a bit.
In order to generate correct debug information, more information needs to be retained throughout compilation. The only way to arrange for debug information to not require any additional memory is to waste memory when not generating debug information. But this is probably undesirable, even if it would minimize the risks of debug annotations affecting optimizations and modifying the generated code.
Therefore, the better debug information we want, the more memory overhead we're going to have to tolerate.
Of course at times we can trade memory for efficiency, using more computationally expensive representations that are more compact, when we can't have both compactness and efficiency.
At other times, we may trade memory for maintainability. For example, instead of emitting annotations as soon as we enter SSA mode, we could emit them on demand, i.e., whenever we deleted, moved or significantly modified an SSA assignment for which we would have emitted a debug annotation. Additional memory would be needed to mark assignments that should have gained annotations but haven't, and care must be taken to make sure that transformations aren't made without leaving a correct (even if still implied) debug annotation in place. It is not clear that this would save significant memory, for a large fraction of relevant assignments are probably modified or moved anyway, so it might turn out to be a maintainability and performance loss for small memory gains. More investigation is required to determine whether this is indeed the case.
Worst case, a user may trade memory for debug information quality: if the memory use of this scheme turns out to be too high for some scenario, the user can disable debug information annotations through a command line option, or disable debug information altogether.
Intrusiveness
Given that nearly all compiler transformations would require reflection in debug information, any solution that doesn't take advantage of this fact is bound to require changes all over the compiler.
Perhaps not so much for Tree-SSA passes, that are relatively well-behaved and use a narrow API to make transformations, but very clearly so for RTL passes, that very often modify instructions in place, and at times even reuse locations assigned to user variables as temporaries (the same is true of tree-ssa-reassoc, FWIW).
Even when we do use the strength of optimizers to maintain debug information up to date, there are exceptions in which detailed knowledge about the transformation taking place enables us to adjust the annotations properly, if possible, or to discard location information for the variable otherwise.
It is just not possible to hope that information can be maintained accurate throughout compilation without any effort from optimizers, or even through a trivial API for a debug information generator. A number of the exceptions that require detailed knowledge about the ongoing transformation would be indistinguishable from other common transformations that would have very different effects on debug information. At this point, any expectations of lower intrusiveness by use of such an API vanish.
By letting optimizers do their jobs on debug annotations, and handling exceptions only at the few locations where they are needed, trivially in most such cases, we keep intrusiveness at a minimum.
Of course we could get even lower intrusiveness by accepting errors in debug information, or accepting to generate different code depending on debug information command-line options. But these options shouldn't be considered seriously.
Complexity
The annotations are conceptually trivial and they can be immediately handled by optimizers. It is hard to imagine a simpler design that would still enable us to get right cases such as those in the examples below.
Worrying about the representation of debug annotations as statements or instructions, rather than notes, is missing the fact that, most of the time, we do want them to be updated just like statements and instructions, rather than handled like notes, that never need updating.
Worrying about the representation of debug annotations in-line, rather than an on-the-side representation, is a valid concern, but it's addressed by the testability of the design, and the in-line representation is highly advantageous, not only for using optimizers to keep debug information accurate, but also for doing away with the need for yet another internal representation and all the efforts into maintaining it accurate.
Optimizations
Correct and more complete debugging information isn't supposed to disable optimizations. Keep in mind that enabling debug information isn't supposed to modify the executable code in any way whatsoever.
The goal is to ensure that whatever debug information the compiler generates actually matches the executable code, and that it is as complete as viable.
The goal is not to disable optimizations so as to preserve variables or code, such that they could be represented in debug information and provide for a debugging experience more like that of code that is not optimized. If debug information disables any optimization, that's a bug that needs fixing. Preventing optimizations that lower the quality of debug information is a separate feature, and one that will benefit from this work, but that won't be accomplished through this work.
It is worth mentioning that, while testing the implementation of this design, a number of opportunities for optimization that GCC missed were detected and fixed, others were merely detected sof ar, and at least one optimization shortcoming kept in place in order to get better debug information could be removed, for the new debug information infrastructure enables the optimization to be applied in its fullest extent.
Examples
It is desirable to be able to represent constants and other optimized-away values, rather than stating variables have values they can no longer have:
int
x1 (int x)
{
int i;
i = 2;
f(i);
i = x;
h();
i = 7;
g(i);
}Even if variable i is completely optimized away, a debugger can still print the correct values for i if we keep annotations such as:
(debug (var_location i (const_int 2))) (set (reg arg0) (const_int 2)) (call (mem (symbol_ref f))) (debug (var_location i unknown)) (call (mem (symbol_ref h))) (debug (var_location i (const_int 7))) (set (reg arg0) (const_int 7)) (call (mem (symbol_ref g)))
In this case, before the call to h, not only the assignment to i was dead, but also the value of the incoming argument x had already been clobbered. If i had been assigned to another constant instead, debug information could easily represent this, through an extension to DWARF version 3 that enable location lists to contain value expressions, in addition to location expressions.
Another example that covers PHI nodes and conditionals:
int
x2 (int x, int y, int z)
{
int c = z;
whatever0(c);
c = x;
whatever1();
if (some_condition)
{
whatever2();
c = y;
whatever3();
}
whatever4(c);
}With SSA infrastructure, this program can be optimized to:
int
x2 (int x, int y, int z)
{
int c;
# bb 1
whatever0(z_0(D));
whatever1();
if (some_condition)
{
# bb 2
whatever2();
whatever3();
}
# bb 3
# c_1 = PHI <x_2(D)(1), y_3(D)(2)>;
whatever4(c_1);
}Note how, without debug annotations, c is only initialized just before the call to whatever4. At all other points, the value of c would be unavailable to the debugger, possibly even wrong, if prior assignments to c had survived optimization.
If we were to annotate the SSA definitions forward-propagated into c versions as applying to c, we'd end up with all of x_2, y_3 and z_0 applied to c throughout the entire function, in the absence of additional markers.
Now, with the annotations proposed in this paper, what is initially:
int
x2 (int x, int y, int z)
{
int c;
# bb 1
c_4 = z_0(D);
# DEBUG c => c_4
whatever0(c_4);
c_5 = x_2(D);
# DEBUG c => c_5
whatever1();
if (some_condition)
{
# bb 2
whatever2();
c_6 = y_3(D);
# DEBUG c => c_6
whatever3();
}
# bb 3
# c_1 = PHI <c_5(D)(1), c_6(D)(2)>
# DEBUG c => c_1
whatever4(c_1);
}is optimized into:
int
x2 (int x, int y, int z)
{
int c;
# bb 1
# DEBUG c => z_0(D)
whatever0(z_0(D));
# DEBUG c => x_2(D)
whatever1();
if (some_condition)
{
# bb 2
whatever2();
# DEBUG c => y_3(D)
whatever3();
}
# bb 3
# c_1 = PHI <x_2(D)(1), y_3(D)(2)>;
# DEBUG c => c_1
whatever4(c_1);
}and then, at every one of the inspection points, we get the correct value for variable c.
Conclusion
This design enables a compiler to emit variable location debug information that complies with the DWARF version 3 standard, and that is likely to be as complete as theoretically possible, with an implementation that is conceptually simple, relatively easy to introduce, trivial to test and easy to maintain in the long run. Not wasting memory or CPU cycles during compilation without debug information are welcome bonuses.