Re: [tcb] Improve SSA-CCP to work with aliased stores, structuresand arrays

[Daniel Berlin <dberlin at dberlin dot org>]

On Fri, 15 Oct 2004, Diego Novillo wrote:

> Given
>
> ----------------------------------------------------------------------
> struct A a;
> const int B = 42;
>
> void foo (int i)
> {
>  if (i > 10)
>    a.a = 42;
>  else
>    {
>      a.b = 21;
>      a.a = a.b + 21;
>    }
>
>  if (a.a != B)
>    link_error ();
> }
> ----------------------------------------------------------------------
>
> GCC will not fold 'a.a != B' into '0'.
>
> While CCP has all the logic to propagate the constants in this case, it
> is missing the ability to associate constants with stores and loads
> (i.e., pointer dereferences, structures and global/aliased variables).
> We don't keep loads and stores in SSA, but we do build a factored
> use-def web for them (in the virtual operands).
>
> Essentially, the patch extends Brian Booth's work to propagate constants
> in global variables.  It associates constant values with the SSA names
> in the V_MAY_DEF/V_MUST_DEF operands.  However, this is not enough,
> because we glob partial loads/stores with the base symbol:
>
> 	# a_5 = V_MAY_DEF <a_4>
> 	a.a = 2;
>
> 	# VUSE <a_5>
> 	x_3 = a.b;
>
> In the example above, CCP will associate value '2' with 'a_5', but it
> would be wrong to replace the load from 'a.b' with '2', because '2' had
> been stored into a.a.  So, we also keep track of the memory reference
> expression where the store was done.  This may not be necessary when we
> start representing partial loads and stores (Dan?).

It won't be necessary.
Where we don't know, you'll see VUSE<a_5, 0, -1> (IE it's somewhere int he 
object) and where we do know, you'll see VUSE <a_5, 2, 4> or whatever.

Also, the immediate uses of <a_5, 2, 4> will be linked up with the right 
uses, and vice versa.
The only thing you'll have to watch out for is the "don't know" 
definitions of variables, which you can't propagate from (since we don't 
know if it really wrote that part), and don't know 
uses of variablse, which you can't propagate to.

You can think of V_MAY_DEF <a_5, 2, 4> as V_MUST_DEF <a_5, 2, 4>. We 
*know* it defined bytes 2-6 of a_5.

--Dan

Attachment: 20041014-store-ccp.diff.gz
Description: GNU Zip compressed data