Sun Sep 20 16:18:43 CEST 2009

Loop TX

In order to get a better idea of loop transformations, it might be
interesting to look at the ``algebra of loop transformations''.  I'd
be surprised if this doesn't exist in such an abstract form.

- interchange (transpose)
- splitting/peeling (boundary conditions or segments)
- fusion/fission
- unrolling
- invariant motion (move independent statments outside loop)
- reversal
- tiling/blocking
- skewing
- vectorization
- software pipelining
- unswitching (moving conditionals out)
- inversion (while -> do/while)

Apprently there is an abstraction called the ``Unimodular
Transformation Framework'' which deals with representing these
oparations as matrices.  Muchnick 20.4.2.

From this it seems reasonable to limit the possible loops in a
language (combinators) to get a better-behaved algebra of loop

[1] http://en.wikipedia.org/wiki/Loop_optimization