question on points-to analysis

question on points-to analysis

[Amker.Cheng]

Hi,
I am studying gcc's points-to analysis right now and encountered a question.
In paper "Off-line Variable Substitution for Scaling Points-to
Analysis", section 3.2
It says that we should not substitute a variable with other if it is
taken address.
But in GCC's implementation, it units pointer but not location
equivalent variables
in function unite_pointer_equivalences.
I am puzzled why gcc does this operation and How gcc keeps accuracy of points-to
information after doing this.

Further more, I did not found any words about this in paper
"Exploiting Pointer and Location Equivalence to Optimize Pointer
Analysis", which
according comments in gcc, is the basis of GCC's implementation.

Any tips?Thanks in advance.

-- 
Best Regards.

Re: question on points-to analysis

[Richard Guenther]

On Thu, Sep 9, 2010 at 1:19 PM, Amker.Cheng <amker.cheng@gmail.com> wrote:
> Hi,
> I am studying gcc's points-to analysis right now and encountered a question.
> In paper "Off-line Variable Substitution for Scaling Points-to
> Analysis", section 3.2
> It says that we should not substitute a variable with other if it is
> taken address.
> But in GCC's implementation, it units pointer but not location
> equivalent variables
> in function unite_pointer_equivalences.
> I am puzzled why gcc does this operation and How gcc keeps accuracy of points-to
> information after doing this.
>
> Further more, I did not found any words about this in paper
> "Exploiting Pointer and Location Equivalence to Optimize Pointer
> Analysis", which
> according comments in gcc, is the basis of GCC's implementation.
>
> Any tips?Thanks in advance.

Danny should have the answers to these questions buried deep in his
mind.

;)

Richard.

> --
> Best Regards.
>

Re: question on points-to analysis

[Daniel Berlin]

On Thu, Sep 9, 2010 at 7:24 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Thu, Sep 9, 2010 at 1:19 PM, Amker.Cheng <amker.cheng@gmail.com> wrote:
>> Hi,
>> I am studying gcc's points-to analysis right now and encountered a question.
>> In paper "Off-line Variable Substitution for Scaling Points-to
>> Analysis", section 3.2
>> It says that we should not substitute a variable with other if it is
>> taken address.
>  and How gcc keeps accuracy of points-to
>> information after doing this.
In theory, this is true, but a lot of the optimizations decrease
accuracy at a cost of making the problem solvable in a reasonable
amount of time.
By performing it after building initial points-to sets, the amount of
accuracy loss is incredibly small.
The only type of constraint that will generate inaccuracy at that
point is a complex address taken with offset one, which is pretty
rare.
On the other hand, *not* doing it will make the problem take forever to solve :)

What's better, something that gives correct but slightly conservative
answers in 10s, or something that gives correct and 1% less
conservative answers in 200s?

Re: question on points-to analysis

[Amker.Cheng]

> In theory, this is true, but a lot of the optimizations decrease
> accuracy at a cost of making the problem solvable in a reasonable
> amount of time.
> By performing it after building initial points-to sets, the amount of
> accuracy loss is incredibly small.
> The only type of constraint that will generate inaccuracy at that
> point is a complex address taken with offset one, which is pretty
> rare.
> On the other hand, *not* doing it will make the problem take forever to solve :)
>
> What's better, something that gives correct but slightly conservative
> answers in 10s, or something that gives correct and 1% less
> conservative answers in 200s?
>

Got it, Thanks for Richard's quick reply and Daniel's detailed explanation.
I need to dig deep to understand the codes.


-- 
Best Regards.