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

[Richard Biener]

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.
I said that fully flow-sensitive points-to info can be attached to SSA
name definitions
via SSA_NAME_PTR_INFO (as it is done now) and that this is the only place where
we are looking at this information via the alias oracle.  Because all
indirect memory references - which
are those with a non-trivial points-to set - happen through an SSA name pointer.

The existing points-to solver of course keeps points-to sets for more
things internally
to be able to precisely deal with (sub-)memory objects.  Internally it
does so in a
flow-insensitive way.  At the end of the solving process all is
translated to points-to
solutions for the existing SSA name pointers in the program.

Maybe that clarifies my answer - if not, can you re-phrase your question again?

Thanks,
Richard.

> Uday.
>
> On Friday 12 October 2012 03:25 PM, Uday P. Khedker wrote:
>>
>> Excellent! Thanks.
>>
>> Uday.
>>
>> Richard Biener wrote, On Friday 12 October 2012 03:20 PM:
>>>
>>> On Fri, Oct 12, 2012 at 11:46 AM, Uday P. Khedker
>>> <uday@cse.iitb.ac.in> wrote:
>>>>
>>>>
>>>>
>>>> Richard Biener wrote, On Friday 12 October 2012 02:51 PM:
>>>>
>>>>>
>>>>> we _always_ see
>>>>>
>>>>>     ssa_name_1 = a;
>>>>>     use (ssa_name_1);
>>>>>
>>>>> so you have a place to associate your flow-sensitive and
>>>>> context-sensitive
>>>>> points-to-info with (the SSA name).  My point is that for _using_ the
>>>>> points-to info flow-sensitivity provided by SSA form is enough.  For
>>>>> computing
>>>>> it you of course need to flow-sensitively process assignments to 'a'.
>>>>
>>>>
>>>>
>>>> This is VERY interesting! I had not thought about the difference between
>>>> computing
>>>> and using values. Now that you point it out, I think all we need to
>>>> do is to
>>>> map
>>>> flow-sensitively computed values to ssa names.
>>>>
>>>> What about variables that do not have ssa names? Or are you saying
>>>> that all
>>>> such
>>>> variables would be copied into an artificial variables that have ssa
>>>> names?
>>>> I seem
>>>> to observe this in the dumps but I don't know if it holds in general.
>>>
>>>
>>> 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 so you should already compute points-to sets for the SSA name
>>> destination of the load.
>>>
>>> Richard.
>>>
>>>
>>>> Uday.