How could I get alias set information from data_reference_p

How could I get alias set information from data_reference_p

[Li Feng]

Hi,

I'm now working on Graphite branch and need to know
the alias set information for each data_reference_p, which
would be an integer (or alias_set_type) stands for which
alias set it is in.

I tried to get the alias set information with get_alias_set (tree)
(I've no idea how this function works, just a experimental
trying), for my testcase, it returns 2 for all the
data_reference_p->ref, which I think is unreasonable.
So I think I may go wrong somewhere.

The question will be: how could I get it's relevant
alias set information from data_reference_p?

p.s. :
In Graphite, the data reference was built for each
gimple stmt with:
get_references_in_stmt (stmt, &references);
then for each ref in references, data reference is created with:
dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);

Thanks,
Li

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

On Tue, Jul 14, 2009 at 8:01 AM, Li Feng<nemokingdom@gmail.com> wrote:
> Hi,
>
> I'm now working on Graphite branch and need to know
> the alias set information for each data_reference_p, which
> would be an integer (or alias_set_type) stands for which
> alias set it is in.
>
> I tried to get the alias set information with get_alias_set (tree)
> (I've no idea how this function works, just a experimental
> trying), for my testcase, it returns 2 for all the
> data_reference_p->ref, which I think is unreasonable.
> So I think I may go wrong somewhere.
>
> The question will be: how could I get it's relevant
> alias set information from data_reference_p?
>
> p.s. :
> In Graphite, the data reference was built for each
> gimple stmt with:
> get_references_in_stmt (stmt, &references);
> then for each ref in references, data reference is created with:
> dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);

get_alias_set (dr->ref) is the correct thing.  Why do you think it
is unreasonable to return 2 for all of them?  Why do you need
alias-set information anyway?

Thanks,
Richard.

> Thanks,
> Li
>

Re: How could I get alias set information from data_reference_p

[Li Feng]

Hi Richard,
On Tue, Jul 14, 2009 at 4:54 PM, Richard
Guenther<richard.guenther@gmail.com> wrote:
> On Tue, Jul 14, 2009 at 8:01 AM, Li Feng<nemokingdom@gmail.com> wrote:
>> Hi,
>>
>> I'm now working on Graphite branch and need to know
>> the alias set information for each data_reference_p, which
>> would be an integer (or alias_set_type) stands for which
>> alias set it is in.
>>
>> I tried to get the alias set information with get_alias_set (tree)
>> (I've no idea how this function works, just a experimental
>> trying), for my testcase, it returns 2 for all the
>> data_reference_p->ref, which I think is unreasonable.
>> So I think I may go wrong somewhere.
>>
>> The question will be: how could I get it's relevant
>> alias set information from data_reference_p?
>>
>> p.s. :
>> In Graphite, the data reference was built for each
>> gimple stmt with:
>> get_references_in_stmt (stmt, &references);
>> then for each ref in references, data reference is created with:
>> dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
>
> get_alias_set (dr->ref) is the correct thing.  Why do you think it
> is unreasonable to return 2 for all of them?  Why do you need
> alias-set information anyway?

The testcase looks like this, where I assume that
p and a in the same alias set, while q and Q in another, and so on.
But between them, the alias set number  should be different, otherwise
maybe I misunderstood somewhere about the alias set.

int Q[10];

int foo()
{
  int i;
  int a[10], b[20];
  int *p = a;
  int *q = Q;

  for (i = 0; i < 10; i++)
    {
      p[i] = i;
      a[i]= i - 5;
      b[i] = i*i;
      q[i] = 5;
    }

  return Q[3]*a[2]*b[10];
}

For you question,
We are using this information before dependency checking under
polyhedron, if 2 data references get different dimensions and they
are not in the same alias set, we could conclude that they
takes no dependency.

Li

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

On Tue, Jul 14, 2009 at 11:12 AM, Li Feng<nemokingdom@gmail.com> wrote:
> Hi Richard,
> On Tue, Jul 14, 2009 at 4:54 PM, Richard
> Guenther<richard.guenther@gmail.com> wrote:
>> On Tue, Jul 14, 2009 at 8:01 AM, Li Feng<nemokingdom@gmail.com> wrote:
>>> Hi,
>>>
>>> I'm now working on Graphite branch and need to know
>>> the alias set information for each data_reference_p, which
>>> would be an integer (or alias_set_type) stands for which
>>> alias set it is in.
>>>
>>> I tried to get the alias set information with get_alias_set (tree)
>>> (I've no idea how this function works, just a experimental
>>> trying), for my testcase, it returns 2 for all the
>>> data_reference_p->ref, which I think is unreasonable.
>>> So I think I may go wrong somewhere.
>>>
>>> The question will be: how could I get it's relevant
>>> alias set information from data_reference_p?
>>>
>>> p.s. :
>>> In Graphite, the data reference was built for each
>>> gimple stmt with:
>>> get_references_in_stmt (stmt, &references);
>>> then for each ref in references, data reference is created with:
>>> dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
>>
>> get_alias_set (dr->ref) is the correct thing.  Why do you think it
>> is unreasonable to return 2 for all of them?  Why do you need
>> alias-set information anyway?
>
> The testcase looks like this, where I assume that
> p and a in the same alias set, while q and Q in another, and so on.
> But between them, the alias set number  should be different, otherwise
> maybe I misunderstood somewhere about the alias set.
>
> int Q[10];
>
> int foo()
> {
>  int i;
>  int a[10], b[20];
>  int *p = a;
>  int *q = Q;
>
>  for (i = 0; i < 10; i++)
>    {
>      p[i] = i;
>      a[i]= i - 5;
>      b[i] = i*i;
>      q[i] = 5;
>    }
>
>  return Q[3]*a[2]*b[10];
> }

You misunderstood what alias-set numbers represent.  Alias-set
numbers encode type-based alias information only - which in
your case cannot disambiguate a or Q.

> For you question,
> We are using this information before dependency checking under
> polyhedron, if 2 data references get different dimensions and they
> are not in the same alias set, we could conclude that they
> takes no dependency.

For dependency checking you should use the dependence
checking routines or query the alias-oracle.

Richard.

> Li
>

Re: How could I get alias set information from data_reference_p

[Sebastian Pop]

Hi Richi,

On Tue, Jul 14, 2009 at 04:40, Richard
Guenther<richard.guenther@gmail.com> wrote:
> You misunderstood what alias-set numbers represent.  Alias-set
> numbers encode type-based alias information only - which in
> your case cannot disambiguate a or Q.
>

I also have misunderstood this.

> For dependency checking you should use the dependence
> checking routines or query the alias-oracle.

How could we use the alias-oracle to output a different number for
each alias set?  Could you provide some directions to implement such a
function?

Thanks,
Sebastian

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

On Tue, Jul 14, 2009 at 5:14 PM, Sebastian Pop<sebpop@gmail.com> wrote:
> Hi Richi,
>
> On Tue, Jul 14, 2009 at 04:40, Richard
> Guenther<richard.guenther@gmail.com> wrote:
>> You misunderstood what alias-set numbers represent.  Alias-set
>> numbers encode type-based alias information only - which in
>> your case cannot disambiguate a or Q.
>>
>
> I also have misunderstood this.
>
>> For dependency checking you should use the dependence
>> checking routines or query the alias-oracle.
>
> How could we use the alias-oracle to output a different number for
> each alias set?  Could you provide some directions to implement such a
> function?

What do you mean by 'different number for each alias set'?  If you
want to have a number that is the same for all conflicting memory
references then you have to build the full conflict map and partition it.

Likely not what you want?  Why do you need alias-set numbers?

Thanks,
Richard.

> Thanks,
> Sebastian
>

Re: How could I get alias set information from data_reference_p

[Sebastian Pop]

On Tue, Jul 14, 2009 at 10:26, Richard
Guenther<richard.guenther@gmail.com> wrote:
> What do you mean by 'different number for each alias set'?

An alias set numbering maps alias sets to integer numbers,
and that map is one-to-one.

>  If you want to have a number that is the same for all conflicting
> memory references then you have to build the full conflict map and
> partition it.

> Likely not what you want?

maybe

> Why do you need alias-set numbers?

We want to represent the alias set information as an extra subscript
on memory accesses: for example,

if we have A[10] and supposing that A is in alias set 6, this would be
represented as "memory_access[6][10]".

For B[3][4] with base array B in alias set 7 and 8, we would represent
this as "memory_access[7][3][4] or memory_access[8][3][4]".

The data dependence test that we currently have in the graphite branch
would work with alias sets represented by an extra dimension to the
array dimensions.

Sebastian

Re: How could I get alias set information from data_reference_p

[Sebastian Pop]

On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote:
>> Why do you need alias-set numbers?
>
> We want to represent the alias set information as an extra subscript
> on memory accesses: for example,
>
> if we have A[10] and supposing that A is in alias set 6, this would be
> represented as "memory_access[6][10]".
>
> For B[3][4] with base array B in alias set 7 and 8, we would represent
> this as "memory_access[7][3][4] or memory_access[8][3][4]".
>
> The data dependence test that we currently have in the graphite branch
> would work with alias sets represented by an extra dimension to the
> array dimensions.

And by the way, right now we consider that all the data refs alias each
other, that means that we set the alias dimension of the memory
accesses to 1 for every data reference.  This makes the test very
conservative: in the example above, with the current implementation,
we would have:

A: memory_access[1][10]
B: memory_access[1][3][4]

Sebastian

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote:
> On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote:
>>> Why do you need alias-set numbers?
>>
>> We want to represent the alias set information as an extra subscript
>> on memory accesses: for example,
>>
>> if we have A[10] and supposing that A is in alias set 6, this would be
>> represented as "memory_access[6][10]".
>>
>> For B[3][4] with base array B in alias set 7 and 8, we would represent
>> this as "memory_access[7][3][4] or memory_access[8][3][4]".
>>
>> The data dependence test that we currently have in the graphite branch
>> would work with alias sets represented by an extra dimension to the
>> array dimensions.
>
> And by the way, right now we consider that all the data refs alias each
> other, that means that we set the alias dimension of the memory
> accesses to 1 for every data reference.  This makes the test very
> conservative: in the example above, with the current implementation,
> we would have:
>
> A: memory_access[1][10]
> B: memory_access[1][3][4]

Well, so you really want to have sort-of the base objects partitioned
into must(!)-conflict sets?  Thus,

  (*p)[1][2]
  (*q)[1][3]

is only correct if the resulting accesses may not alias?  (that is,
p == q?)

No, we don't have such information readily available.  You have
to compute it.  Likely by building a complete conflict map of
the bases of all memory references and partitioning it.

Which doesn't sound like a great idea - it's quadratic.  Thus, can't
you represent this in a more sparse way?

Richard.

> Sebastian
>

Re: How could I get alias set information from data_reference_p

[Li Feng]

Hi Richard,

Maybe you could look into this thread and give us
some suggestion/confirmation.
Now we plan to use dr_may_alias_p (DR1, DR2) to partition
the alias set.
http://groups.google.de/group/gcc-graphite/browse_thread/thread/7bffbe9037b5adf4?hl=en

Thanks,
Li

On Wed, Jul 15, 2009 at 5:34 AM, Richard
Guenther<richard.guenther@gmail.com> wrote:
> On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote:
>> On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote:
>>>> Why do you need alias-set numbers?
>>>
>>> We want to represent the alias set information as an extra subscript
>>> on memory accesses: for example,
>>>
>>> if we have A[10] and supposing that A is in alias set 6, this would be
>>> represented as "memory_access[6][10]".
>>>
>>> For B[3][4] with base array B in alias set 7 and 8, we would represent
>>> this as "memory_access[7][3][4] or memory_access[8][3][4]".
>>>
>>> The data dependence test that we currently have in the graphite branch
>>> would work with alias sets represented by an extra dimension to the
>>> array dimensions.
>>
>> And by the way, right now we consider that all the data refs alias each
>> other, that means that we set the alias dimension of the memory
>> accesses to 1 for every data reference.  This makes the test very
>> conservative: in the example above, with the current implementation,
>> we would have:
>>
>> A: memory_access[1][10]
>> B: memory_access[1][3][4]
>
> Well, so you really want to have sort-of the base objects partitioned
> into must(!)-conflict sets?  Thus,
>
>  (*p)[1][2]
>  (*q)[1][3]
>
> is only correct if the resulting accesses may not alias?  (that is,
> p == q?)
>
> No, we don't have such information readily available.  You have
> to compute it.  Likely by building a complete conflict map of
> the bases of all memory references and partitioning it.
>
> Which doesn't sound like a great idea - it's quadratic.  Thus, can't
> you represent this in a more sparse way?
>
> Richard.
>
>> Sebastian
>>
>

Re: How could I get alias set information from data_reference_p

[Tobias Grosser]

On Tue, 2009-07-14 at 23:34 +0200, Richard Guenther wrote:
> On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote:
> > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote:
> >>> Why do you need alias-set numbers?
> >>
> >> We want to represent the alias set information as an extra subscript
> >> on memory accesses: for example,
> >>
> >> if we have A[10] and supposing that A is in alias set 6, this would be
> >> represented as "memory_access[6][10]".
> >>
> >> For B[3][4] with base array B in alias set 7 and 8, we would represent
> >> this as "memory_access[7][3][4] or memory_access[8][3][4]".
> >>
> >> The data dependence test that we currently have in the graphite branch
> >> would work with alias sets represented by an extra dimension to the
> >> array dimensions.
> >
> > And by the way, right now we consider that all the data refs alias each
> > other, that means that we set the alias dimension of the memory
> > accesses to 1 for every data reference.  This makes the test very
> > conservative: in the example above, with the current implementation,
> > we would have:
> >
> > A: memory_access[1][10]
> > B: memory_access[1][3][4]
> 
> Well, so you really want to have sort-of the base objects partitioned
> into must(!)-conflict sets?  Thus,

Is there anything like must-conflict? I thought the alias oracle just
returns may conflict relations.
This information should be passed to graphite without loosing any
information.

>   (*p)[1][2]
>   (*q)[1][3]
> 
> is only correct if the resulting accesses may not alias?  (that is,
> p == q?)

What do you mean by is correct?

> 
> No, we don't have such information readily available.  You have
> to compute it.  Likely by building a complete conflict map of
> the bases of all memory references and partitioning it.
> 
> Which doesn't sound like a great idea - it's quadratic.  Thus, can't
> you represent this in a more sparse way?

It is quadratic in what? In the number of data references?

If the only way we can get the information if two data references may
alias is asking the oracle, I do not think there is an alternative. We
have to get at least this information. So there will be nb_of_drs^2
calls to the alias oracle. Or is there any alternative?

I think the only way to get to less complexity is to limit the
information passed to graphite. E.g. we can put everything in the same
alias set as we do now. This is very conservative but definitely faster.

I tend to take the high complexity at the moment, as I do not think we
get many SCoPs that are too big to handle and passing all the details
allows Graphite to do more optimizations. However we can switch to the
old approach if the number of data references passes a certain limit, so
gcc's speed will not suffer.

Tobi

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

On Wed, Jul 15, 2009 at 1:00 PM, Tobias
Grosser<grosser@fim.uni-passau.de> wrote:
> On Tue, 2009-07-14 at 23:34 +0200, Richard Guenther wrote:
>> On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote:
>> > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote:
>> >>> Why do you need alias-set numbers?
>> >>
>> >> We want to represent the alias set information as an extra subscript
>> >> on memory accesses: for example,
>> >>
>> >> if we have A[10] and supposing that A is in alias set 6, this would be
>> >> represented as "memory_access[6][10]".
>> >>
>> >> For B[3][4] with base array B in alias set 7 and 8, we would represent
>> >> this as "memory_access[7][3][4] or memory_access[8][3][4]".
>> >>
>> >> The data dependence test that we currently have in the graphite branch
>> >> would work with alias sets represented by an extra dimension to the
>> >> array dimensions.
>> >
>> > And by the way, right now we consider that all the data refs alias each
>> > other, that means that we set the alias dimension of the memory
>> > accesses to 1 for every data reference.  This makes the test very
>> > conservative: in the example above, with the current implementation,
>> > we would have:
>> >
>> > A: memory_access[1][10]
>> > B: memory_access[1][3][4]
>>
>> Well, so you really want to have sort-of the base objects partitioned
>> into must(!)-conflict sets?  Thus,
>
> Is there anything like must-conflict? I thought the alias oracle just
> returns may conflict relations.

True.  This is why I ask ;)

> This information should be passed to graphite without loosing any
> information.
>
>>   (*p)[1][2]
>>   (*q)[1][3]
>>
>> is only correct if the resulting accesses may not alias?  (that is,
>> p == q?)
>
> What do you mean by is correct?

I try to ask what you are going to do with the computed alias-set
numbers and what is the property required for the alias-set numbers
so that their use do not result in invalid transformations from graphite.

So, what does the 1 in (*p)[1][2] semantically mean?

>>
>> No, we don't have such information readily available.  You have
>> to compute it.  Likely by building a complete conflict map of
>> the bases of all memory references and partitioning it.
>>
>> Which doesn't sound like a great idea - it's quadratic.  Thus, can't
>> you represent this in a more sparse way?
>
> It is quadratic in what? In the number of data references?

Yes.  You need to build the full conflict map (or a conflict graph,
as Li proposes in his final algorithm).

> If the only way we can get the information if two data references may
> alias is asking the oracle, I do not think there is an alternative. We
> have to get at least this information. So there will be nb_of_drs^2
> calls to the alias oracle. Or is there any alternative?

I don't know.  It depends on how you are going to use the information.

> I think the only way to get to less complexity is to limit the
> information passed to graphite. E.g. we can put everything in the same
> alias set as we do now. This is very conservative but definitely faster.
>
> I tend to take the high complexity at the moment, as I do not think we
> get many SCoPs that are too big to handle and passing all the details
> allows Graphite to do more optimizations. However we can switch to the
> old approach if the number of data references passes a certain limit, so
> gcc's speed will not suffer.

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

IMHO what you want is to assign a different alias-set to all partitions
of the graph.  Where for two partitions P1 and P2 there is no edge
between them in the conflict graph.

That may of course be just as precise as using a single alias set.

Note that you likely want to distinguish read-read conflicts from
true or anti dependences, no?  Depending on how you are going
to use them again ...

Richard.

Re: How could I get alias set information from data_reference_p

[Tobias Grosser]

On Wed, 2009-07-15 at 13:26 +0200, Richard Guenther wrote:
> On Wed, Jul 15, 2009 at 1:00 PM, Tobias
> Grosser<grosser@fim.uni-passau.de> wrote:
> > On Tue, 2009-07-14 at 23:34 +0200, Richard Guenther wrote:
> >> On Tue, Jul 14, 2009 at 6:08 PM, Sebastian Pop<sebpop@gmail.com> wrote:
> >> > On Tue, Jul 14, 2009 at 11:03, Sebastian Pop<sebpop@gmail.com> wrote:
> >> >>> Why do you need alias-set numbers?
> >> >>
> >> >> We want to represent the alias set information as an extra subscript
> >> >> on memory accesses: for example,
> >> >>
> >> >> if we have A[10] and supposing that A is in alias set 6, this would be
> >> >> represented as "memory_access[6][10]".
> >> >>
> >> >> For B[3][4] with base array B in alias set 7 and 8, we would represent
> >> >> this as "memory_access[7][3][4] or memory_access[8][3][4]".
> >> >>
> >> >> The data dependence test that we currently have in the graphite branch
> >> >> would work with alias sets represented by an extra dimension to the
> >> >> array dimensions.
> >> >
> >> > And by the way, right now we consider that all the data refs alias each
> >> > other, that means that we set the alias dimension of the memory
> >> > accesses to 1 for every data reference.  This makes the test very
> >> > conservative: in the example above, with the current implementation,
> >> > we would have:
> >> >
> >> > A: memory_access[1][10]
> >> > B: memory_access[1][3][4]
> >>
> >> Well, so you really want to have sort-of the base objects partitioned
> >> into must(!)-conflict sets?  Thus,
> >
> > Is there anything like must-conflict? I thought the alias oracle just
> > returns may conflict relations.
> 
> True.  This is why I ask ;)
> 
> > This information should be passed to graphite without loosing any
> > information.
> >
> >>   (*p)[1][2]
> >>   (*q)[1][3]
> >>
> >> is only correct if the resulting accesses may not alias?  (that is,
> >> p == q?)
> >
> > What do you mean by is correct?
> 
> I try to ask what you are going to do with the computed alias-set
> numbers and what is the property required for the alias-set numbers
> so that their use do not result in invalid transformations from graphite.
> 
> So, what does the 1 in (*p)[1][2] semantically mean?
> 
> >>
> >> No, we don't have such information readily available.  You have
> >> to compute it.  Likely by building a complete conflict map of
> >> the bases of all memory references and partitioning it.
> >>
> >> Which doesn't sound like a great idea - it's quadratic.  Thus, can't
> >> you represent this in a more sparse way?
> >
> > It is quadratic in what? In the number of data references?
> 
> Yes.  You need to build the full conflict map (or a conflict graph,
> as Li proposes in his final algorithm).
>
> > If the only way we can get the information if two data references may
> > alias is asking the oracle, I do not think there is an alternative. We
> > have to get at least this information. So there will be nb_of_drs^2
> > calls to the alias oracle. Or is there any alternative?
> I don't know.  It depends on how you are going to use the information.

The idea is that we want to get rid of the need to call a function, to
know if two data references alias, but - as Sebastian explained - to map
them to virtual memory locations.

Lets say we have some data references A, B, C, D, E, F, G that alias
like this:

A -- B    F -- G
|  / |
| /  |
C -- D -- E   

What I would like is to create groups of the data references that may
touch the same memory location. So every pair of data references that
may alias has to share at least one alias set.

The easiest solution is to put all of them in one big set. This is
always correct, but very conservative.

AS1 = {A,B,C,D,E,F,G}

The next step would be to make groups of all connected components of the
graph.

AS1 = {A,B,C,D,E}
AS2 = {F,G}

The most exact solution I can think of is to take all maximal complete
sub graphs. This means all sub graphs where there is between every two
elements E1, E2 an edge.

AS1 = {A,B,C}
AS2 = {B,C,D}
AS3 = {D,E}
AS4 = {F,G}

So a statement

D[i][4j-5] = B [2j];

has these effects:

may-write [2] [i] [4j-5]
may-write [3] [i] [4j-5]
read [1] [2j]
read [2] [2j]

Another statement might be

... = E[5i][5i+j]

read [3] [5i] [5i+j]

The information is used in our data dependency checks to check and
calculate which dependencies exist.

There we have conflict equalities for every subscript. Lets look at the
possible conflict in between the write to D and the read of E.

It has to fulfill these conditions for some iterations (i,j) and (i',j')

(s0 == 2 == 3 == s0' and
s1 == i == 5i' == s1' and
s2 == 4j-5 == 5i'+j' == s2')

or 

(s0 == 3 == 3 == s0' and
s1 == i == 5i' == s1' and
s2 == 4j-5 == 5i'+j' == s2')

The first set is impossible as they are part of different alias sets and
therefor s0 != s0', however the second one might be possible e.g. for
j = 2, i = 0, i' = 0, j' = 3

The exact solution can be calculated by our linear programming solver
taking into concern even more restrictions.


> > I think the only way to get to less complexity is to limit the
> > information passed to graphite. E.g. we can put everything in the same
> > alias set as we do now. This is very conservative but definitely faster.
> >
> > I tend to take the high complexity at the moment, as I do not think we
> > get many SCoPs that are too big to handle and passing all the details
> > allows Graphite to do more optimizations. However we can switch to the
> > old approach if the number of data references passes a certain limit, so
> > gcc's speed will not suffer.
> 
> 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
dependencies. If we put A,B,C in one big set we can not say this.


> IMHO what you want is to assign a different alias-set to all partitions
> of the graph.  Where for two partitions P1 and P2 there is no edge
> between them in the conflict graph.
> 
> That may of course be just as precise as using a single alias set.
> 
> Note that you likely want to distinguish read-read conflicts from
> true or anti dependences, no?  Depending on how you are going
> to use them again ...

Sure. Actually we even want to be able to distinguish between read,
write and may-write accesses.

At the moment we do not take advantage of the difference in between
write and may-write, but as soon as we do this there might show up more
interesting problems, as it is preferable to be sure a write happened as
it removes a lot of dependencies.

Tobi

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

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?

> dependencies. If we put A,B,C in one big set we can not say this.

But that is what would be correct. (?)

Richard.

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

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.

Richard.

>> dependencies. If we put A,B,C in one big set we can not say this.
>
> But that is what would be correct. (?)
>
> Richard.
>

Re: How could I get alias set information from data_reference_p

[Tobias Grosser]

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?

Tobi

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

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?

Richard.

> Tobi
>
>
>
>

Re: How could I get alias set information from data_reference_p

[Li Feng]

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.

Li

Re: How could I get alias set information from data_reference_p

[Richard Guenther]

On Thu, Jul 16, 2009 at 11: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.

I see.  That would work.

Richard.

> Li
>

Re: How could I get alias set information from data_reference_p

[Daniel Berlin]

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

Re: How could I get alias set information from data_reference_p

[Sebastian Pop]

On Thu, Jul 16, 2009 at 10:45, Daniel Berlin<dberlin@dberlin.org> wrote:
> 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
>

Yes, this is correct.

> Then you are assigning numbers to the sets that appear on the RHS.

Correct.

> 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 the case of Graphite, the queries are limited to the data
references within a SCoP.  Usually a SCoP does not necessarily contain
huge amount of data references.  In the future, we may also set
restrictions on the number of data references that we allow in a SCoP.

Sebastian

Re: How could I get alias set information from data_reference_p

[Li Feng]

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