Futhark.Optimise.Sink

Sinking is conceptually the opposite of hoisting. The idea is to take code that looks like this:

x = xs[i]
y = ys[i]
if x != 0 then {
  y
} else {
  0
}

and turn it into

x = xs[i]
if x != 0 then {
  y = ys[i]
  y
} else {
  0
}

The idea is to delay loads from memory until (if) they are actually needed. Code patterns like the above is particularly common in code that makes use of pattern matching on sum types.

We are currently quite conservative about when we do this. In particular, if any consumption is going on in a body, we don't do anything. This is far too conservative. Also, we are careful never to duplicate work.

This pass redundantly computes free-variable information a lot. If you ever see this pass as being a compilation speed bottleneck, start by caching that a bit.

This pass is defined on the Kernels representation. This is not because we do anything kernel-specific here, but simply because more explicit indexing is going on after SOACs are gone.

Documentation

sinkKernels :: Pass Kernels Kernels

Sinking in GPU kernels.

sinkMC :: Pass MC MC

Sinking for multicore.