Re: How could I get alias set information from data_reference_p

[Li Feng <nemokingdom@gmail.com>]

Hi Daniel,
On Thu, Jul 16, 2009 at 11:45 PM, Daniel Berlin<dberlin@dberlin.org> wrote:
> 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
>
I'm not sure about your meaning by B,C,D in A's alias set.
If that means BandCandD may alias to A, but without saying
B,C,D will alias to each other or not, then I think we may
misunderstand somewhere.

If I understand you correctly, in your example, you mean that
B,C,D is connected(may alias) to A, and C,D,E  is connected
to B. And no other relation ship between these A,B...E.
If this is true, then I think there will be 4 alias set. (We could
consider this problem as finding all the maximum cliques in an
undirected graph.)
alias set 1{A,B,C}
alias set 2{B,E}
alias set 3{B,D}
alias set 4{A,D}

So in our definition:
some data reference will be said in one alias set if they
may alias each other.
e.g.
If we have the following alias set
{A,B,C}
Then we should get A alias B, B alias C and C alias A.

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

Bitmap is not necessary, in Graphite, we would like to pass these
alias information through access polyhedron, which will need this alias set
number.
So in Graphite, a poly_dr(polyhedron representation with data reference)
will hold this access polyhedron( a polyhedron which will hold access function
inforamtion and alias information), where
we could got the information we need when we would like
to check dependency between 2 poly_drs.
> 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).
>

I can't quite understand this paragraph(especially the reason that
the mapping is expensive), can you explain with more detailed
information.

Thanks for your comment,
Li