Fix lexico negative data dep distances
Sebastian Pop
sebastian.pop@cri.ensmp.fr
Mon Aug 29 11:19:00 GMT 2005
Daniel Berlin wrote:
> On Tue, 2005-08-23 at 10:35 +0200, Sebastian Pop wrote:
> > Hi,
> >
> > Data dependence distances should never be lexicographically negative.
>
> Why?
By definition distance vectors are lexicographically positive: in
Allen & Kenedy "Advanced Compilation for High Performance Computing"
Definition 2.11. Statement S2 has a loop-carried dependence on
statement S1 if and only if S1 references location M on iteration i,
S2 references M on iteration j and d(i,j) > 0 (that is, D(i,j)
contains a "<" as leftmost non "=" component).
> I must have missed something.
> Lexico negative seems perfectly legal to me.
Why you don't want to have negative distance vectors?
Take for example the legality of linear loop matrix transform: this
transform is legal if <any distance vector> \times <transform matrix>
is lexicographically positive. If you have a negative distance vector
V, you will allow a matrix M that transforms V into a positive
distance vector, but this changes the meaning of the program: instead
of having an anti-dependence (write after read), after transform
you'll have a true dependence (read after write).
This is just a convention (or a definition) that you have to follow if
you want to play the same game as the others ;-)
seb
More information about the Gcc-patches
mailing list