Fully flow and context sensitive points-to analysis in GCC 4.6.0

[Uday P. Khedker]

Richard Biener wrote, On Thursday 24 January 2013 05:28 PM:

>> In the program below, we have a global pointer p that has conditional
>> assignments before its
>> use on the RHS of a copy statement.
>> -----------------------------------------------------------------------------------------
>> #include<stdio.h>
>>
>> int **p;
>> int main()
>> {
>>      int *x,*y,a,c,*z;
>>      x = &a;
>>      z = &c;
>>      if(a)
>>          p = &x;
>>      else
>>          p = &y;
>>       int **t = p;
>>       printf("%d,%d",*z,*x);
>>    }
>> -----------------------------------------------------------------------------------------
>> The assignment t=p does not seem to load p inspite of p being a global
>> pointer. Here's
>> the relevant code fragment from test.c.017t.ssa:
>> ----------------------------------------------------------------------------------------
>> <bb 3>:
>>    p = &x;
>>    goto <bb 5>;
>>
>> <bb 4>:
>>    p = &y;
>>
>> <bb 5>:
>>    t_3 = p;
>
> here p is loaded directly into t_3, you can consider it optimized
> (copy propagated)
> from
>
>    D.1234_8 = p;
>    t_3 = D.1234_8;
>
>>    x.1_4 = x;
>>    D.2524_5 = *x.1_4;
>>    D.2525_6 = *z_1;
>> ---------------------------------------------------------------------------------------
>> Note that p is global but it has been loaded neither loaded, nor does it
>> have a PHI function.
>
> As p resides in memory it does not need a PHI - values are merged by
> storing them to memory.

Yes, but because it is in memory, should it not be loaded? I thought every memory
access is preceded by a load. At least that is how I interpreted your original statement.

>
>> There is no way we can put the pointees of p in SSA_NAME_PTR_INFO of p in a
>> flow sensitive
>> manner.
>>
>> So if a later optimization pass were to find out aliases of p or pointees of
>> p for the statement
>> t_3 = p, I don't know how will we supply the information that was discovered
>> by our analysis.
>
> Your analysis should have come across that statement
>
>    t_3 = p;
>
> and record that t_3 points to what p points to at this point of the program,
> thus compute a solution for all SSA name pointers.

Yes that is easy to do. But my concern is what if there is a pass that requires/uses pointer
information of p in the statement t_3 = p.

>
> This is what the present points-to algorithm does, and at the end it simply
> discards anything but the solutions computed for SSA name pointers
> which are stored in SSA_NAME_PTR_INFO.

Oh, does it mean that the SSA_NAME_PTR_INFO would not be present for p
but would be present only for t_3 (because p is not an SSA name and t_3 is)?

If this is true, can we assume the invariant that any pass would seek pointer
info only for SSA names and not for any non-SSA name?

If that is the case, then I think there is a simple way in which we can make the
result of our analysis available to all other passes without they having to
consult our data structure.


Uday.