This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: "Uday P. Khedker" <uday at cse dot iitb dot ac dot in>
- Cc: gcc at gcc dot gnu dot org, Pritam Gharat <pritamg at cse dot iitb dot ac dot in>
- Date: Thu, 24 Jan 2013 12:58:54 +0100
- Subject: Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
- References: <5075B6B9.4080309@cse.iitb.ac.in> <CAGWvny=T-Hqb1_txpCMo5gVKSsYd3y9y2xOwDMuQ6PjfqmFScA@mail.gmail.com> <5076375A.30302@cse.iitb.ac.in> <CAFiYyc1gtxcFP0XKGP1arNUN2dA=f+Tn5h_AKq6asXihXGqNDg@mail.gmail.com> <5076EB85.5070501@cse.iitb.ac.in> <CAD_=9DQXOfw8a1Z9vAX+FJcLtbu_5LLgafFeK5-ue9gLzqj+_w@mail.gmail.com> <50779F81.5020700@cse.iitb.ac.in> <CA+=Sn1kcBM48UKep6pmjYQFno9fxHagRVWaoCB-DucT=XjPk6A@mail.gmail.com> <5077AD8F.8050105@cse.iitb.ac.in> <CAFiYyc2n_VutJTLZmk2-q=k4+FE9Tnd9KDv4DH+x+26OBO_AgA@mail.gmail.com> <5077E6DD.4000703@cse.iitb.ac.in> <CAFiYyc2gUX57-otpNE89YV=YJQOfwW340HHSYB+0BiFLDB_Jew@mail.gmail.com> <5077E929.60700@cse.iitb.ac.in> <5100360B.2070307@cse.iitb.ac.in> <CAFiYyc2jUZCw+7-9rQ82k5S0S17MudgNXnngPExVXbRY8wQQ4Q@mail.gmail.com> <5100EA99.5090306@cse.iitb.ac.in>
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.