The SoA backend, the branch is here: branch is moving towards supporting a wide variety of programs.

This backend currently factors out each field of a data constructor to its own region / separate buffer. This is contrary to the original Gibbon which uses one buffer for the complete data type. The SoA transformation is necessary for complex transformations like vectorization. It may also be important to use this representation for skipping over unused fields in a traversal. Since each field is in a separate buffer, this makes it easier to skip past unused fields. See this blog post I wrote that talks about detailed experiments I did with a list-based representation.

Current Status:

The compiler works well for data types such as List and Tree where the only packed fields in the data type are self recursive fields. The other fields are scalar fields. In addition, the Gibbon compiler is only well supported for data types where the scalars are before the recursive fields. This is also true for the SoA backend since it follows the AoS backend. Hence the SoA backend can compile programs that use data types like the following currently.

data List = Cons Int List | Nil
data Tree = Node Int Tree Tree | Leaf Int
data Tree1 = Node Int Float Tree Tree | Leaf Int Float
data Tree2 = Node Float Tree Tree Tree | Node2 Int Tree Tree | Leaf Int

Near term TODO (Next 6 months)

• For tree based programs, the SoA backend seg faults with O3. There is a segmentation fault in gib_grow_region. With no optimization, the tree based programs show correct behaviour. This is likely a bug in the runtime of the old compiler and needs to be corrected. (This was not a bug in the runtime, rather a consequence of stack allocating cursor arrays in recursive functions.)

• A data type definition could contain other packed fields in the definition that are not self recursive.
  For instance, consider a data type definition of a Tree that contains a List. data Tree = Node Int List Tree Tree | Leaf Int List. There are a few problems here, firstly, List is not self recursive but it is still a packed type. Hence, there are two options for its representation, an AoS or an SoA. Since the implementation factors out all packed fields to SoA when we compile with the --SoA flag. It means that the List will also be an SoA representation. Hence we need to make sure Inferlocations and other passes can handle this correctly. We also want to have the choice to compile the List as AoS vs SoA. This also needs to be supported.

• The SoA optimization needs to be supported for the gibbon2 backend as well. This means we need support for indirection and redirection pointers that point to SoA regions.

• Performance optimization: The SoA backend for List with O3 is around 10 times slower than the AoS list. We should generate more efficient code. In particular, for the SoA backend, there is a big opportunity to do alias analysis and remove unnecessary computations. Remove dead code amongst others.
  In addition, the cursor array is currently malloced in every recursive call. This is excessive and inefficient.
  I need to add an additional temporary cursor per packed output type as a function argument to ensure that we don't waste time mallocing and making function calls.

Relatively long term TODO : (Next 1-3 years)

• Since the Gibbon compiler cannot support data types where scalar fields are after Packed fields correctly. This also follows for the SoA backend.
  Hence, a data type like data Tree = Node Tree Tree Int | Leaf Int may result in a compilation error.

• Right now, the compiler provides a compile time flag --SoA that changes all packed types to SoA layouts. This is too restrictive. We may want some datatypes as AoS vs others as SoA. To have this choice, The programmer needs to have the flexibility to choose the representation. One way is to provide an Annotation in the top level haskell code, or have it in the type definition. The latter is nicer IMO.

• There is also a tradeoff between a fully factored representation vs a mix between AoS and SoA. We should provide the flexibility to choose something in between. We could also develop a heuristic to choose the best intermediate layout.

• My Blog post showed that inplace updates can be important for more complex optimizations like vectorization and skipping over dead fields, we should add support for inplace updates.

• The current functions are not tail recursive, we should have support for tail recursive functions. I was working on a branch a long time back but this needs to be thoroughly updated.

• We also need the compiler to codegen for loops in the C code for better vectorization, however, at the moment, there is no support for enabling for loops. Tail recursion is fine for simple data types like List but not for more complex data types. This requires new L2 IR and data flow analysis. My plan is to make a new PR where I introduce a new L2 Ir construct. Maybe a "map" like function?

• Right now we generate C, but we may need a different backend for instance C++ to utilize optimizations / generate faster code.