This pass transforms parallelism expressed with arbitrarily nested SOACs to instead be expressed with limited-nesting SegOps. This is the so-called "flattening transformation" (sometimes called "vectorization", although we do not use that term much in the Futhark compiler).

This is a sophisticated pass that does various clever things:

• Detects uniform nesting and flattens it more efficiently than the nonuniform case.
• DPH-style vectorization avoidance.
• Incremental flattening (Futhark.Pass.Flatten.Incremental).
• Intrablock flattening (Futhark.Pass.Flatten.Intrablock).

The goal is that *any* Futhark program must be compilable parallel GPU code, although in some cases the resulting code is not particularly efficient.

The idea is to perform distribution on one level at a time, and produce "irregular maps" that can accept and produce irregular arrays. These irregular maps will then be transformed into flat parallelism based on their contents. If irregular maps contain only a single Stm, then it is fairly straightforward, as we simply implement flattening rules for every single kind of expression. Of course that is also somewhat inefficient, so we want to support multiple Stms for things like scalar code.

Nomenclature:

A map-nest is the collection of parallel operations enclosing some code. For simplicity, we say "map-nest" even when the top level parallel operation is actually a redomap or other screma.

An irregular array is a multidimensional array like '[[1,2],[3]]', where rows have different shapes. These are not directly supported in Futhark or in the Futhark IR, but are encoded in various ways.

We say that an operation or type in a map-nest is uniform when its size (including internal sizes and sizes of inputs) and control flow is invariant to the map-nest. Converse, it is nonuniform when it is variant. When we distribute a uniform statement, the intermediate results are regular, and otherwise irregular. A statement that uses an irregular array is necessarily nonuniform.

Take care not to confuse the terms "regular" and "uniform" - we say "regular" only about arrays! Uniform is the general concept.

Uniform nested parallelism is nested parallelism whose size is uniform to the enclosing map nest, and which uses only variables whose types are uniform, and which is enclosed in uniform control flow. /Nonuniform nested parallelism/ is the converse. Many of the optimisations here are about detecting the uniform case. We previously often used the terms "regular nested parallelism" and "irregular nested parallelism", but this is now discouraged, as explained above.