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

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

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