Safe Haskell | None |
---|---|

Language | Haskell2010 |

This module implements an optimisation that moves in-place updates into/before loops where possible, with the end goal of minimising memory copies. As an example, consider this program:

loop (r = r0) = for i < n do let a = r[i] in let r[i] = a * i in r in ... let x = y with [k] <- r in ...

We want to turn this into the following:

let x0 = y with [k] <- r0 loop (x = x0) = for i < n do let a = a[k,i] in let x[k,i] = a * i in x in let r = x[y] in ...

The intent is that we are also going to optimise the new data
movement (in the `x0`

-binding), possibly by changing how `r0`

is
defined. For the above transformation to be valid, a number of
conditions must be fulfilled:

`r`

must not be consumed after the original in-place update.`k`

and`y`

must be available at the beginning of the loop.`x`

must be visible whenever`r`

is visible. (This means that both`x`

and`r`

must be bound in the same`BodyT`

.)- If
`x`

is consumed at a point after the loop,`r`

must not be used after that point. - The size of
`r`

is invariant inside the loop. - The value
`r`

must come from something that we can actually optimise (e.g. not a function parameter). `y`

(or its aliases) may not be used inside the body of the loop.

FIXME: the implementation is not finished yet. Specifically, the above conditions are not really checked.