Re: PR 23551: why should we coalesce inlined variables?

[Michael Matz <matz at suse dot de>]

Hi,

On Mon, 9 Jul 2007, Alexandre Oliva wrote:

> >> Yeah, that's just after turning it into SSA.  How about after 
> >> optimization?  Why wouldn't we coalesce foo_2 with bar_1 and 
> >> propagate bar_2 and foo_3 into the uses (assume they're just 
> >> assignments to other variables).
> 
> > If they are just assignments then both SSA names hold the same values 
> > (i.e. are backed by the same user variables), so there's no 
> > distinction between them in debug info.
> 
> No, that's not true.

I should have added "from the point of that assignment on".

> 0:/* foo = */ foo_1 = <initial value>;
> 1:/* bar = */ bar_1 = <expr>;
> 2:...
> 3:/* foo = bar_1; */
> 4:/* bar = bar_1 + 1; */
> 5:/* foo = bar_1 - 1; */
> 6: use (bar_1 + 1);
>    use (bar_1 - 1);

You somehow keep forgetting SSA form.  Every assignment to foo will get 
it's own SSA name, hence by attaching the user-var associations with SSA 
names you will know exactly over which range a value is backed by a user 
variable.

For reference your example in SSA form would be:

0: foo_1 = <initial value>
1: bar_1 = <expr>
2: ...
3: foo_2 = bar_1
4: bar_2 = bar_1 + 1
5: foo_3 = bar_1 - 1
6: use (bar_2)
   use (foo_3)

Associations for SSA names to user variables (assuming 'foo' and 'bar' are 
not compiler introduced temps):

foo_1 => {foo}
bar_1 => {bar}
foo_2 => {bar,foo}
bar_2 => {bar+1}  (here it's associated with a complex expression, not 
                   with a user variable, that can be handleded in 
                   different ways, depending on if you want to have it 
                   associated with the "current" value of a variable)
foo_3 => {bar-1,foo}

Now, to get at the correct debug info you need to traverse this mapping 
backwards.  Basically, if you want to have the locations where a variable
sits, you look at every SSA name associated with a variable and try to 
find a covering of all instructions of the function.  There are 
usually multiple possible mappings, at which point you can make the debug 
info a bit better or worse, depending on some heuristics.

For instance for 'bar' we know that it sits in bar_1 and bar_2, it makes 
most sense to use the most current value at each point, hence 'bar' can be 
found in bar_1 from it's definition until the start of live of bar_2, when 
it changes place to that SSA name, i.e. we will get this mapping:

range value
1..5  bar_1
5...  bar_2

which I think is exactly what you wanted.  (side remark: note that bar_1 
and bar_2 will not be coalesced in this example (because the use of bar_1 
in 5: after the definition of bar_2 prevents that)).

> Correct debug info for bar:
> 
> range value
> 1..5  bar_1
> 5...  bar_1 + 1
> 
> Correct debug info for foo:

Okay, let's look for where the values of user variable 'foo' could be 
found.  First try: in foo_1, foo_2 and foo_3.  Assuming that you do 
not coalesce bar_1 and foo_2, that will be all that's required, and will 
lead to this table:

range value
0..2  foo_1
3..4  foo_2
5...  foo_3

If you do coalesce bar_1 and foo_2 (let's say you coalesce foo_2 into 
bar_1, so that you're left with only bar_1) the picture doesn't really 
change, only that in insns 3 and 4 the value for 'foo' will be found in 
bar_1, which indeed must exist also after insn 4, as we need it's value in 
insn 5.  So again, perfectly feasible to find places for variables values.

It is only important that the out-of-ssa pass correctly merges the 
associations with user variables (and does the right thing if it needs to 
generate temporary variables to implement the copies), and that a later 
pass (var-tracking) makes sensible use of that information to build the 
debug information.

> range value
> 0..4  foo_1
> 4..6  bar_1
> 6...  bar_1 - 1
> 
> Your suggested debug info for foo:
> 
> range value
> 0..2  foo_1
> 2..6  bar_1
> 6...  bar_1 - 1
> 
> See the s/4/2/ ?  That would be a bug.
> 
> > Of course you have to make sure, that if you do such propagation
> > that you merge the lists of associated variables for the involved
> > SSA names.
> 
> This is not enough.  The ranges matter.

An SSA name _is_ a range for exactly the value that it holds initially.  
It doesn't change under your back without also changing the SSA version 
number.  Conceptually it lives until the end of the function, but you 
usually find the value of a variable in the currently active SSA name for 
that variable, which limits the ranges over the instructions to exactly 
those places where also the user variable was defined to different values.


Ciao,
Michael.