Find a way to stack allocate closures

[yorickpeterse]

Description

In #783 we're introducing the ability to define stack allocated types capable of storing both heap and stack allocated types. We should find a way to extend such functionality to also work for closures.

Stack allocating closures poses a few challenges:

• fn types are currently assumed to be pointers, not stack allocated data
• stack allocated closures don't have a uniform layout, as their size is dictated by the variables they capture
• closures may assign captured variables new values, which won't work reliably if we copy the stack data similar to inline types

For closures to be stack allocated, we most likely need to treat them similarly as generic type arguments and generate specialized versions. This however is likely to require extensive changes to how we specialize types and methods, so I'm not sure about this yet.

Related issues

• Introduce support for user-defined, stack allocated value types #750
• Make enums and tuples stack allocated types #780
• Implement some form of escape analysis to allocate values on the stack #776

Related work

• https://mjtsai.com/blog/2019/01/17/stack-allocation-for-non-escaping-swift-closures/
• [SR-7286] non-escaping closures aren't stack allocated swiftlang/swift#49834

[yorickpeterse]

For closures it might make more sense to keep their memory layout the same, but use escape analysis to allocate them on the stack. Most closures aren't likely to outlive the method they're defined in, so this might be good enough. This also removes the need for complex specialization changes.

[yorickpeterse]

As part of #776 I have the foundations in place for stack allocating closures. The current issue is that when a method defines an argument of type fn ..., the size of that type isn't known and thus can't be allocated on the stack. For this to work, we need to specialize over closures as mentioned in this issue's description (which I forgot about when working on the escape analysis issue).

[yorickpeterse]

Not only do we need to specialize closures similar to generics, but we also need to make sure that capture information is propagated across inferred types and type signatures. Consider this example:

let a = 10
let b = fn { a }
let c: fn -> Int = b

For b we know what variables are captured. However, for c the type is set to a new closure type for which we don't have this information. This is fine at the moment because closures have a uniform representation on the stack (= a pointer). To solve that, when comparing closure A against closure B (A -> B), B must inherit the capture information of A.

Another challenge is that if we infer a whole bunch of types according to a closure, they should all be specialized to the same closure type. In the above example that means b and c should be the same single specialized type, instead of two different types that happen to share the same layout.

We also can't generate type parameters and then turn closures into some sort of special trait requirement, as this wouldn't work for return types. Consider this:

fn example -> fn (Int) -> Int { ... }

If we use generated parameters, we'd turn that into something like this:

fn example[R: fn (Int) -> Int] -> R { ... }

The problem here is that we never end up assigning R upon a call to example, because whatever is assigned to it depends on the body of example and not the call to it. In theory we could just assign it to whatever is returned by default such that it's always the same, but that in turn might not work if the closure captures any arguments and those argument types differ.

I'm not sure yet how to approach these challenges, so I'll postpone this until 0.19.0 as I suspect it will take some time to figure all this out. We can however use the foundations provided by #798 to implement the type uni proposal from #776 (comment).