Re: How could I get alias set information from data_reference_p

[Daniel Berlin <dberlin@dberlin.org>]

On Thu, Jul 16, 2009 at 5:00 AM, Li Feng<nemokingdom@gmail.com> wrote:
> Hi Richard,
> On 7/16/09, Richard Guenther <richard.guenther@gmail.com> wrote:
>> On Thu, Jul 16, 2009 at 1:15 AM, Tobias
>> Grosser<grosser@fim.uni-passau.de> wrote:
>>> On Wed, 2009-07-15 at 22:48 +0200, Richard Guenther wrote:
>>>> On Wed, Jul 15, 2009 at 10:46 PM, Richard
>>>> Guenther<richard.guenther@gmail.com> wrote:
>>>> > On Wed, Jul 15, 2009 at 9:15 PM, Tobias
>>>> > Grosser<grosser@fim.uni-passau.de> wrote:
>>>> >>> A note on Lis final graph algorithm.  I don't understand why you
>>>> >>> want
>>>> >>> to allow data-references to be part of multiple alias-sets?  (Of
>>>> >>> course
>>>> >>> I don't know how you are going to use the alias-sets ...)
>>>> >>
>>>> >> Just to pass more information to Graphite. The easiest example might
>>>> >> be
>>>> >> something like
>>>> >>
>>>> >> A -- B -- C
>>>> >>
>>>> >> if we have
>>>> >>
>>>> >> AS1 = {A,B}
>>>> >> AS2 = {B,C}
>>>> >>
>>>> >> we know that A and C do not alias and therefore do not have any
>>>> >
>>>> > No, from the above you _don't_ know that.  How would you arrive
>>>> > at that conclusion?
>>>>
>>>> What I want to say is that, if  A -- B -- C is supposed to be the alias
>>>> graph
>>>> resulting from querying the alias oracle for the pairs (A, B), (A, C),
>>>> (B, C)
>>>> then this is a result that will never occur.  Because if (A, B) is true
>>>> and (B, C) is true then (A, C) will be true as well.
>>>
>>> What for example for this case:
>>>
>>> void foo (*b) {
>>>  int *a
>>>  int *c
>>>
>>>  if (bar())
>>>        a = b;
>>>  else
>>>        c = b;
>>> }
>>>
>>> I thought this may give us the example above, but it seems I am wrong.
>>> If the alias oracle is transitive that would simplify the algorithm a
>>> lot. Can we rely on the transitivity?
>>
>> Actually I was too fast (or rather it was too late), an example with
>> A -- B -- C would be
>>
>> int a, c;
>> void foo(int *p)
>>
>> with B == (*p).  B may alias a and c but a may not alias c.
>>
>> So, back to my first question then, which is still valid.
>>
>> Just to pass more information to Graphite. The easiest example might be
>> something like
>>
>> A -- B -- C
>>
>> if we have
>>
>> AS1 = {A,B}
>> AS2 = {B,C}
>>
>> we know that A and C do not alias and therefore do not have any
>> dependencies.
>>
>> How do you derive at 'A and C do not alias' from looking at
>> the alias set numbers for AS1 and AS2.  How do you still
>> figure out that B aliases A and C just from looking at
>> the alias set numbers?  Or rather, what single alias set number
>> does B get?
> AS1 = {A,B}
> AS2 = {B,C}
>
> B is not neccessary to have only a single alias set number,
> for this situation, B will have alias number both 1 and 2 (it
> is in both alias set),
> A will be with alias number 1 and
> C will be with alias number 2.
> So A and C got different alias set number, we could conclude
> that they are not alias.
> While for A and B or B and C, as B got alias number both 1 and 2,
> so they may alias.

So if i understand you right, it seems all you've done is inverted the
existing alias/points-to sets.
IE instead of saying A has B, C, D in it's alias set, you are saying B
is in the alias set of A, C is in the alias set of A, D is in the
alias set of A.

Effectively,

A -> {B, C, D}
B -> {C, D, E}
becomes
B -> A
C -> A, B
D -> A ,B
E -> B

Then you are assigning numbers to the sets that appear on the RHS.
You still end up with bitmaps, and you still have to intersect them
(or describe containment some other way and do containment queries).

For a large program, this mapping is actually massive and quite
expensive to compute (In points-to, normally you use location
equivalence and BDD's to compress the sets. I never got around to
finishing location equivalence inside GCC, though it is in the LLVM
implementation i did if you want to look).

--Dan