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

[Richard Biener]

On Thu, Jan 24, 2013 at 9:02 AM, Uday P. Khedker <uday@cse.iitb.ac.in> wrote:
>
>
> Richard Biener wrote, On Thursday 24 January 2013 01:57 AM:
>
>> On Wed, Jan 23, 2013 at 8:12 PM, Uday Khedker <uday@cse.iitb.ac.in> wrote:
>>>
>>> Hi Richard,
>>>
>>> I am trying to understand the full implications of your statement:
>>>
>>>
>>>>> Yes, that's what I say.  Any pointer that is dereferenced is first
>>>>> copied to
>>>>> an SSA name.  Basically everything residing in memory first has to be
>>>>> loaded to an SSA name before it can be dereferenced.  That load is
>>>>> explicit
>>>>> in the IL
>>>
>>>
>>> There are many parts and let me take one by one:
>>>
>>> - You talk about dereference. So a statement p=q would not mean loading
>>>    q into memory. Had q been a global scalar variable, it would have been
>>>    loaded into an SSA name. Then why is it not loaded when it is global
>>>    pointer. Why a load only for p=*q and not for p=q?
>>
>>
>> If q is a global pointer it is of course also first loaded into an SSA
>> name.
>>
>>> - When we have p=*q, agreed that we are loading a value from memory but
>>>    then it is *q that is being loaded. Why should an SSA name be created
>>>    for q even when q is a local pointer?
>>
>>
>> If q is a local pointer that does not have its address taken then it will
>> be
>> in SSA form.  If it is not in SSA form then q is first loaded into an SSA
>> name
>> before it can be dereferenced.
>>
>>>
>>> What am I missing?
>>
>>
>> If I remember the discussion correctly it was about where to put
>> points-to results.
>
>
> Yes that is the context and we are trying to devise a way of implementing
> your suggestion.
>
> My student Pritam has come up with an example that seems to differ from your
> explanation (and
> we don't know how to proceed).
>
> 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.

> 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.

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.  What the present points-to
fails to do is to properly handle changes of 'p' in a flow-sensitive manner
if you'd consider another store to p like

   p = &z;

after

  t_3 = p;

then if no other transform would have optimized this in some way then
it would compute that t_3 also may point to &z (then it of course also
does not handle killing defs of memory).

Hope this helps,
Richard.

> Uday.