Re: How could I get alias set information from data_reference_p

[Richard Guenther <richard dot guenther at gmail dot com>]

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.