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:

  let r =
    loop (r1 = r0) = for i < n do
      let a = r1[i]
      let r1[i] = a * i
      in r1
  ...
  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]
    let x[k,i] = a * i
    in x
  let r = x[k] 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 Body.)
4. If x is consumed at a point after the loop, r must not be used after that point.
5. The size of r1 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.
8. The result of the loop may not alias the merge parameter r1.

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

Documentation

inPlaceLoweringKernels :: Pass Kernels Kernels

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

inPlaceLoweringSeq :: Pass Seq Seq

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

inPlaceLoweringMC :: Pass MC MC

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