Re: How could I get alias set information from data_reference_p

[Tobias Grosser <grosser@fim.uni-passau.de>]

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