Re: Rewrite of PROPOSAL 001213.1 re default location

[DAVID WEATHERFORD <david dot weatherford at sun dot com>]

OK, I'm totally confused.  Maybe I'm misrembering the discussion
from 7 (!) years ago, but I don't recall ever talking about
split, overlapping lifetimes.  I thought overlapping loclists
were to handle the simple migration to/from registers that I
described in my previous mail.

In any case, the loclist mechanism is certainly not able to
describe all the possible situations that arise in highly
optimised code.  We know that we don't have a good story
concerning optimization, even in draft 5.  That will have
to wait for some future revision.

Since Jeff Nelson thinks that the "exists simultaneously"
verbiage was describing such esoterica, I'll concede that
I am mistaken and move on.

Section 2.5.4 needs some explanatory comments, in any event.

Dave W.


Ron 603-884-2088 wrote:
> 
> >Sorry, Ron, I still don't get it.  The current definition of location
> >lists covers exactly this case by allowing overlapping ranges.  For
> >your example, the entries should be
> >
> >     1       (<beginning of module>, <end of module>+1)
> >                                        static address &x
> >
> >     2       (<first assignment>,  <second assignment>)
> >                                        register Ri
> >
> >     3       (<second assignment>, <routine exit>)
> >                                        register Rj
> >
> >On the phone you objected to this interpretation of the current
> >spec.  What exactly do you think the above means, then?
> 
> I decided that it might be better to address this comment separately
> rather than make the rewrite longer than it already was, because I believe
> it is a misunderstanding of DWARF itself. Unfortunately I got interrupted
> by my day job (:-) and did not get to it as quickly as I had hoped. In any
> case...
> 
> Consider this example:
> 
> foo () {
> 
>     int x;
> 
>     x = ...some expression #1...
> 
>     ...some expression #2 that uses the value of x...
> 
>     x = ...some expression #3...
> 
>     ...some expression #4 that uses the value of x...
> 
> }
> 
> Assuming that these are the only assignments and uses of x, an optimizing
> compiler might note that the value of x assigned in the first line can
> never flow into a use of the value of x that might have been assigned in
> the second line. As such, the variable x can be "split" into two independent
> child variables, let me call them x1 and x2, but bear in mind that these
> are really pseudo-names for different lifetimes of the same variable x.
> This results resulting in the following equivalent program:
> 
> foo () {
> 
>     int x;
> 
>     x1 = ...some expression #1...
> 
>     ...some expression #2 that uses the value of x1...
> 
>     x2 = ...some expression #3...
> 
>     ...some expression #4 that uses the value of x2...
> 
> }
> 
> Since x1 and x2 are independent, they can be independently allocated.
> Moreover, it is now quite valid for the program to be rewritten (say as
> a result of some form of scheduling) by interchanging the order of the
> second and third statement, yielding
> 
> foo () {
> 
>     int x;
> 
>     x1 = ...some expression #1...
> 
>     x2 = ...some expression #3...
> 
> /*break*/
> 
>     ...some expression #2 that uses the value of x1...
> 
>     ...some expression #4 that uses the value of x2...
> 
> }
> 
> Now suppose that execution is stopped at the point in the code corresponding
> to /*break*/ and the user issues a command to the debugger to display the
> value of x.
> 
> At this point x has two values, corresponding to the two assignments.
> Both are valid and correct, and neither should be considered to hide or
> take priority over the other.
> 
>     [Which is not to say that many debuggers are capable of handling this
>     situation correctly....]
> 
> Many more complicated optimizations can create this same sort situation
> in which there is more than one value associated with a single variable:
> loop unrolling, inlining, code scheduling and the like can all contribute.
> What has long fascinated me is the multiple active values can arise even
> for simple straightline code.
> 
> Now, consider what DWARF says (Section 2.4.6 in V2, 2.5.4 in V2.1
> [identical text])
> 
>     Address ranges may overlap. When they do, they describe a situation
>     in which an object exists simultaneously in more than one place.
> 
> In the example above, the two address ranges for variable x (corresponding
> to x1 and x2) do overlap. The object x does exist simultaneously in
> more than one place. Neither place is more correct than the other.
> 
>     If you think that x1 ought to be more correct because it got computed
>     first, then suppose that the optimizer had gone further and scheduled
>     the assignment to x2 before the assignment to x1. The optimizer has
>     not made a mistake, the semantics of the program are still correct,
>     and the situation for the debugger (and user) is unchanged by
>     interchanging the order of assignment to x1 and x2.
> 
> Now suppose that I replace the declaration of x in the above example with an
> external declaration of x. The sequence of transformations performed by
> the optimizer is still valid. In particular:
> 
>    - When stopped at /*break*/ in this second variant, there are two, NOT
>      THREE, values of x simultaneously active.
> 
>    - The static storage allocated for x is still sitting there, of course;
>      but the bits contained there have nothing to do with the value x.
>      In effect, the "x object" has moved and no longer resides in static
>      storage.
> 
>         Indeed, a perverse optimizer could even go further and reuse the
>         static storage associated with x for some other purpose during
>         the time that x "lives" in one (or more) register locations.
> 
> Hopefully this makes it clear why I believe the location list suggested
> above is not a semantically correct representation of the actual program
> state. It implies there are three simultaneous instances of x when there
> are really only two.
> 
> Moreover, I hope it makes clear why I believe the DWARF text is absolutely
> correct as it stands; it means exactly what it says. Indeed, it has to mean
> that otherwise the location list structure is not capable of representing
> accurately either variant of my example. Any notion of "nesting" or
> "ordering" or "priority" among the several entries of a location list
> runs counter to an object that "exists simultaneously in more than one
> place".
> 
> Historical Note
> 
> I have a further reason for believing this is the correct and proper
> interpretation of the DWARF text. I remember having a discussion with
> Jeff Nelson, who many moons ago was DEC's representative to the PLSIG
> DWARF committee. Jeff approached me on this very point and I coached
> him carefully and urged him make sure that the committee got this point
> right. He told me later they had and when I saw the resulting text
> I was satisfied that he was right.
> 
> As it happens, that was before Jeff and I came up with the idea of
> a default location to save space; otherwise the default location concept
> might have made it way into DWARF many years ago...

-- 
Dave Weatherford                Forte Tools
David.Weatherford@Sun.COM       Sun Microsystems, Inc.