Internal compiler error: Type error after pass 'expand allocations'

[nbos]

Compiling program

entry main [n] (xs: [n]i64) =
  tabulate n
  (\_ -> let xs = scatter (copy xs) xs xs
     let xs = xs with [0] = n
     in spread xs[0] 0 xs xs :> [n]i64)

with backend opencl results in the error

Internal compiler error.  Please report this:
  https://github.com/diku-dk/futhark/issues
Type error after pass 'expand allocations':
In function entry_main
When checking function body
In expression of statement
  {ext_mem_6737 : ({}, mem@device),
   defunc_2_map_res_6550 : ({}, [n_6369][n_6369]i64 @ ext_mem_6737 -> {base: [n_6369, n_6369]; contiguous: true; LMADs: [{offset: 0i64; strides: [n_6369, 1i64]; shape: [n_6369, n_6369]; permutation: [0, 1]; monotonicity: [Inc, Inc]}]})}
in body of last case
Type error:
Variable scatter_res_r_coalesced_6686 referenced after being consumed.

[athas]

Nasty one. This is the handling of memory expansion for irregular allocations that computes a program slice that consumes its input, just like the original program. I will have to consider whether this is even solvable without violating the asymptotics of the program. If not, then we can make memory expansion recognise the problem and fall back to a compiler limitation, but that will not make the program work. Full support for such irregular nested parallel programs will probably have to wait for #1740 to be done.

[athas]

(This program isn't actually irregular, but the compiler isn't smart enough to see it, and it would be irregular without the in-place update of xs[0].)

[athas]

You have a real talent for finding obscure bugs, but fortunately also for distilling small reproduction cases.

[nbos]

What I have is a large program in which a lot of special cases and irregularity probably crept in. Whatever behavior I am trying to achieve gets lost in the minimization. Is there, in general, a quick and easy way to check if a piece of code is regular, besides getting it to compile?

[athas]

No. In principle the types can tell you, but there is no tool that actually does so. Maybe we should write one.

[nbos]

Ok, it would be nice indeed!