This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Designs for better debug info in GCC
On Dec 20, 2007, Alexandre Oliva <aoliva@redhat.com> wrote:
> I'm addressing this in a bit more detail in a revised version of the
> spec, that I intend to publish in the GCC wiki RSN.
http://gcc.gnu.org/wiki/Var_Tracking_Assignments
Here's a diff between the version I posted a couple of days ago and
the one before I started adjusting formatting for better rendering in
the wiki.
Index: debug-var-loc.txt
===================================================================
RCS file: /home/aoliva/.cvs/txt/free-software/gcc/debug-var-loc.txt,v
retrieving revision 1.2
retrieving revision 1.4
diff -u -p -d -u -p -r1.2 -r1.4
--- debug-var-loc.txt 18 Dec 2007 08:03:42 -0000 1.2
+++ debug-var-loc.txt 20 Dec 2007 07:32:56 -0000 1.4
@@ -34,54 +34,66 @@ optimization passes discard information
emit correct and complete variable location lists.
Coalescing, scalarizing, substituting, propagating, and many other
-transformations prevent the late-running variable tracker from doing
-an accurate job. By the time it runs, many variables no longer show
-up in the retained annotations, although they're still conceptually
-available.
+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 tell when a user variable overlaps with
-another, and it can't tell when a variable is overwritten, if the
-assignment is optimized away. These limitations are inherent to a
-model based on inspecting 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.
+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
-* Ensure that, for every user variable for which we emit debug
-information, the information is correct, i.e., if it says the value of
-a variable at a certain instruction is at certain locations, or is a
-known constant, then the variable must not be at any other location at
-that point, and the locations or values must match reasonable
-expectations based on source code inspection.
+=== Correctness
-* Defining "reasonable expectations" is tricky, for code reordering
-typical of optimization can make room for numerous surprises. I don't
-have a precise definition for this yet, but very clearly to me saying
-that a variable holds a value that it couldn't possibly hold (e.g.,
-because it is only assigned that value in a code path that is
-knowingly not taken) is a very clear indication that something is
-amiss. The general guiding rule is, if we aren't sure the information
-is correct (or we're sure it isn't), we shouldn't pretend that it is.
+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.
-* Try to ensure that, if the value of a variable is a known constant
+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.
-* Try to ensure that, if the value of a variable is available or
-computable at any location at a certain point in the program, this
-information is present in debug information.
-* Stop missing optimizations for the sake of preserving debug
-information.
+=== Run-time efficienty
-* Avoid using additional memory and CPU cycles that would be needed
-only for debug information when compiling without generating debug
-information
+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
@@ -118,9 +130,9 @@ most optimization passes, be handled jus
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:
+by a given expression, or that bind a user variable to a value:
- # DEBUG var expr
+ # 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
@@ -128,103 +140,204 @@ 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. A special value needs to be specified for
-each representation that denotes a location or value that cannot be
-determined or represented in debug information, for example, the
-location of a variable that was completely optimized away. It might
-be useful to represent the expression as a list of expressions, and to
-distinguish lvalues from rvalues, but for now let's keep this simple.
+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. Annotations are only generated for user
-variables that are GIMPLE registers, i.e., variables that represent
-scalar values and that never have their address taken. Other kinds of
-variables don't have varying locations, so we don't need to worry
-about them.
+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.
-After every assignment to such a variable, we emit a DEBUG statement
-that will preserve, throughout compilation, the information that, at
-that point, the assigned variable was represented by that expression.
-So, after turning an assignment such as the following into SSA form,
-we emit the debug statement below right after it:
+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
+ # DEBUG x => x_1
-Likewise, at control flow merge points, for each PHI node we introduce
-in the SSA representation, we emit an annotation:
+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
+ # 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 automatically update debug statements that mention them as well.
+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 very rare
-cases, special code might be needed to adjust debug statements
-manually.
+skipping or otherwise ignoring debug statements. In a few rare cases,
+additional code might be needed specifically to adjust debug
+statements.
-After transformation to RTL, the representation needs translation, but
-conceptually it's still the same: a mapping from variable to
-expression. Again, optimizers will most often adjust debug
-instructions automatically.
+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 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
+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 both ranges requires identical code,
-except for the constants.
+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 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.
+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 pick up the 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 variable is live at more
-than one location, it is important to note it, such that, if a
-debugging session attempts to modify the variable, all copies are
-modified.
+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 represented by the expression. As we scan
+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 variable. When such
-expressions are further copied, we add them to equivalence classes.
-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
-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
-debug statements added as a side effect of PHI nodes.
+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.
-The end result is accurate debug information. Also, except for
-transformations that require special handling to update debug
-annotations properly, debug information should come out as complete as
+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,
@@ -240,9 +353,9 @@ maintaining debug annotations throughout
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 to detect
-cases in which the presence of debug annotations would cause code
-changes.
+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
@@ -285,11 +398,13 @@ or whether the value is available or com
missing, is a harder problem, but it's not part of the accuracy test,
but rather of the completeness test.
-The completeness score for an unoptimized program might very often be
+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 it is
-no longer possible to determine the value of the inspected variable.
+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
@@ -303,14 +418,16 @@ 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
-undesirable.
+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.
+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
@@ -319,29 +436,31 @@ modified an SSA assignment for which we
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 debug statement in place. It is not clear that this would
-save significant memory, for a large fraction of relevant assignments
-are modified or moved anyway, so it might very well be a
-maintainability loss and a performance penalty for no measurable
-memory gains.
+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, we may trade memory for debug information quality: if
-memory use of this scheme is too high for some scenario, one can
-disable debug information annotations through a command line option,
-or disable debug information altogether.
+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 place.
+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.
+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
@@ -378,7 +497,8 @@ 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.
+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
@@ -400,19 +520,21 @@ generates actually matches the executabl
complete as viable.
The goal is not to disable optimizations so as to preserve variables
-or code, such that it can be represented in debug information and
+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.
+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.
-Now, while testing this design, a number of opportunities for
-optimization that GCC missed were detected and fixed, others were
-merely detected, 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.
+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
@@ -449,7 +571,9 @@ print the correct values for i if we kee
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.
+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:
@@ -491,7 +615,8 @@ x2 (int x, int y, int z)
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.
+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
@@ -506,23 +631,23 @@ x2 (int x, int y, int z)
int c;
# bb 1
c_4 = z_0(D);
- # DEBUG c c_4
+ # DEBUG c => c_4
whatever0(c_4);
c_5 = x_2(D);
- # DEBUG c c_5
+ # DEBUG c => c_5
whatever1();
if (some_condition)
{
# bb 2
whatever2();
c_6 = y_3(D);
- # DEBUG c c_6
+ # DEBUG c => c_6
whatever3();
}
# bb 3
# c_1 = PHI <c_5(D)(1), c_6(D)(2)>
- # DEBUG c c_1
+ # DEBUG c => c_1
whatever4(c_1);
}
@@ -533,20 +658,20 @@ x2 (int x, int y, int z)
{
int c;
# bb 1
- # DEBUG c z_0(D)
+ # DEBUG c => z_0(D)
whatever0(z_0(D));
- # DEBUG c x_2(D)
+ # DEBUG c => x_2(D)
whatever1();
if (some_condition)
{
# bb 2
whatever2();
- # DEBUG y_3(D)
+ # DEBUG c => y_3(D)
whatever3();
}
# bb 3
# c_1 = PHI <x_2(D)(1), y_3(D)(2)>;
- # DEBUG c c_1
+ # DEBUG c => c_1
whatever4(c_1);
}
--
Alexandre Oliva http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member http://www.fsfla.org/
Red Hat Compiler Engineer aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist oliva@{lsd.ic.unicamp.br, gnu.org}