futhark-0.9.1: An optimising compiler for a functional, array-oriented language.

Safe HaskellNone
LanguageHaskell2010

Futhark.Optimise.InPlaceLowering

Description

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.

Synopsis

Documentation

inPlaceLowering :: Pass Kernels Kernels Source #

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