Futhark.Optimise.InPlaceLowering

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:

1. r must not be consumed after the original in-place update.
2. k and y must be available at the beginning of the loop.
3. x must be visible whenever r is visible. (This means that both x and r must be bound in the same BodyT.)
4. If x is consumed at a point after the loop, r must not be used after that point.
5. The size of r is invariant inside the loop.
6. The value r must come from something that we can actually optimise (e.g. not a function parameter).
7. 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.

Documentation

inPlaceLowering :: Pass Kernels Kernels

Apply the in-place lowering optimisation to the given program.