2021-01-08
Removing the ReorderStatements
pass
This is a copy-pase of the commit message from 61badb32562e0e7fd64464cc0dffadcebf6cc76b.
The purpose of the ReorderStatements
pass was to improve locality of code the
futhark IR. The motivating problem was some double buffers in OptionPricing
which would only be copied to at the very end of the program. This lead to some
arrays being in-use for much longer than needed, preventing the reuse of their
memory blocks. More details here:
https://munksgaard.me/technical-diary/2020-10-07.html#orgbbfe6a7
Unfortunately, I have not seen any actual benefits from introducing this
pass. In the OptionPricing
benchmark specifically, it turned out that moving
final double-buffer copy up did not yield any additional opportunities for
memory block merging. And in fact, some benchmarks actually use more memory
after having been reordered, because of the simplistic way this pass is
implemented. As an example, consider the following code:
1: let map_res@ext_mem = ... 2: let res_mem = alloc ... 3: let res@res_mem = copy(map_res) 4: in (res_mem, res)
The ReorderStatements
algorithm would start by looking at the result of the
body, (res_mem, res)
and determine that both would need to be
computed. Because it does not know the difference between a memory block and an
array it arbitrarily decides to compute res_mem
first, resulting in the
following reordered code:
1: let res_mem = alloc ... 2: let map_res@ext_mem = ... 3: let res@res_mem = copy(map_res) 4: in (res_mem, res)
But now there's no opportunity to merge resmem with extmem, because their lifetimes overlap.
I'm afraid overcoming this problem would require a significant rewrite of
ReorderStatements
, and I'm not even sure we'd get any performance benefits out
of it.
Therefore, I'm removing the pass for now. We can always dig it up again later.