[tree-ssa]: Implementing unimodular and non-singular loop transforms

[Daniel Berlin <dberlin at dberlin dot org>]

In order to implement various non-singular (If i use something like 
LAMBDA, http://iss.cs.cornell.edu/l.htm) and unimodular loop transforms 
(both classes are memory hierarchy optimizations), i am going to need 
do to matrix math.

This means one of two things:

1. Including some C based loop transformation package in gcc.
2. Including some C baesd matrix math package in gcc, and rewriting the 
lambda algorithms.

I'd of course, rather do #1, out of laziness.  In particular, the 
LAMBDA loop toolkit is easy to use and non-IR specific.  It will let 
you do any linear one-to-one loop transformation (skewing, interchange, 
unimodular, or any combination thereof, etc), and all you have to do is 
be able to generate code from the answer it gives you (which isn't that 
hard at all).
It's roughly 15 files and ~5000 lines of code.  It was build to be 
integrated into compilers.

Intel uses the LAMBDA loop toolkit (IE the actual toolkit) in its 
compilers.
HP rewrote it (IE uses the algorithms, AFAIK) in their  compilers.

I have no idea about licensing ATM (it says nothing anywhere), but i 
can contact Wei Li, who wrote it, and in fact, is a U of R CS alumni, 
just like me, and see whats up.

We could also rewrite lambda #2 since its only 5000 lines of code.
Probably take a few months.  Most of the code is code to deal with 
matrices, vectors, and lattices, not the code to deal with the loop 
nests and whatnot.

Any other people who know of any other free enough loop transformation 
kits or usable matrix math libraries, that are integratable into gcc, 
then let us discuss them.
I can rewrite the lambda algorithms to use them most likely, unless 
they have really horrible interfaces.

Ideas, thoughts?

--Dan