Fix lexico negative data dep distances

[Sebastian Pop]

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