Don't Store Memory-Spilled Values on Stack & Steady State Memory Spilling

[Sword-Smith]

We can only access values on the stack if they are confined to the top 16 words. That is how we determine if a value should be spilled to memory or not. But once it's spilled to memory it no longer needs to live on the stack and can thus give room to other values that might become accessible after a value above has been spilled. We currently leave the memory-spilled value on the stack which is sub-optimal.

To find the minimal set of values that need to be spilled to memory, we should complete the following tasks:

• [ ] Write more tests covering corner-cases of variable spilling to gain confidence we don't mess anything up
• [ ] Add a benchmark for a program that benefits from this optimized spill-handling
• [ ] Remove the value that is copied to memory ("spilled") from the stack
• [ ] Run the compiler until the FunctionState field spill_required no longer changes (is in a steady state).

[Sword-Smith]

Changes required:

1. Code generator ast::Stmt::Return should only generate pop instructions for variables that are not spilled.

2. Return type of tasm_code_generator -> VStack -> find_stack_value

This function should return the tuple Either<StackPosition, MemoryPosition>, ast::DataType and not a triplet as it does now. And spilled values may not increase the position value.

find_tuple_element should return the same type as find_stack_value.

3. get_stack_height should not accumulate the height of spilled values.

4. In tasm_code_generator -> compile_expr

   let spill_code = spill
       .map(|x| copy_top_stack_value_to_memory(x, result_type.size_of()))
       .unwrap_or_default();

5. In tasm_code_generator ->VStack-> get_code_to_spill_to_memory

   let mut spill_code =
               copy_value_to_memory(memory_spill_address, data_type.size_of(), top_of_value);

The two last expressions need to be changed to code that moves the top stack value to memory instead of copying it as we do now.

Places where memory spilling is already handled this way (included for better overview of codebase, code doesn't need to change here):

• overwrite_value
• replace_tuple_element
• restore_stack_code Vstack should be restored here, but values spilled inside a block do not need to be cleaned from memory, as kmalloc ensures that these values are not reused.
• Code generation of ast::Stmt::Let as compile_expr places the evaluated expression either in memory or on top of the stack.

[Sword-Smith]

To be honest, I'm not a 100 % sure this change is worth the complexity, at least not without considering a change to the FunctionState data structure. Maybe the VStack value is not appropriate to handle both spilled and non-spilled values? Not sure yet, how to proceed here. Will have to think about it.

[Sword-Smith]

Let's start with seeing if we can move spilled values to memory instead of copying them. The only complication here is how to handle function arguments that must be spilled. The caller must copy the correct values to memory and not push them to stack. How does the called know which arguments to store to memory? The caller would have to compile the function first, then read out which function arguments that should be passed via memory. I see two difficulties with this approach:

1. Where should the knowledge about which arguments to spill be stored?
2. How should recursive function calls be made? Here, we will not know which arguments to spill before compilation is complete.