C backend without heap allocations

[AltGr]

trafficstars

The current C backend being prototyped follows the functional spirit from the lambda-calculus it stems from: functions work with return values, and for that proceed with allocations and return pointers. Mixing this with unboxed structures was really tedious, so at the moment all structures, fields, etc. are similarly heap-allocated pointers (with our very dumb, but lightning fast allocator).

Mainly for interoperability, at some point we would like to have a more idiomatic C backend. (It should also be much faster, but I expect the first one to be already so fast it won't really matter anyway). This issue is to gather ideas and plans for this new backend, which I expect will be much easier to write by transitioning the code from the allocating C backend than from scratch.

1. Make structures, enums, arrays, etc. flat instead of embedding pointers. Monomorphisation should make that possible, but of course it'll need to include generating specific code for traversals (arrays with variable-length elements, vs. all arrays containing only pointers which have a know memory size in the current backend)

2. Use return-pointers for functions returns (so that they don't have to allocate).

   mystruct* foo(const myenum* x) { ... }
   

   becomes

   void foo(mystruct* return_pointer, const myenym* x) { ... }
   

3. Replace heap allocations with stack allocations. It becomes the responsibility of the caller to allocate, which can be done since the callee return type is always fully known. We want reference-passing, so keep using only pointers, but allocate them on the stack as follows:

   {
     mystruct foo_return[1];
     foo(foo_return, x);
   }
   

   assuming this function needs to return a sub-structure or element of foo_return, we'll have to do a copy.