Optimization: Use LLVM registers for stack-top values

[navicore]

Summary

Keep the top N stack values in LLVM virtual registers instead of always storing to memory, allowing LLVM to optimize register allocation and reduce memory operations.

Current Behavior

All stack operations go through memory:

; Push 5
store i64 0, ptr %stack          ; store discriminant
store i64 5, ptr %stack+8        ; store value

; Add
%a = load i64, ptr %stack-32+8   ; load first operand
%b = load i64, ptr %stack+8      ; load second operand
%sum = add i64 %a, %b
store i64 %sum, ptr %stack-32+8  ; store result

Even though LLVM can optimize some of this, the explicit memory operations limit optimization potential.

Proposed Optimization

Track the top N values (e.g., top 2-4) as LLVM SSA values:

; Current stack state: [... | %top1 | %top0]
; Push 5
%new_top0 = i64 5
; Now: [... | %top0 | %new_top0]

; Add (assuming both are integers)
%sum = add i64 %top0, %new_top0
; Now: [... | %sum]

Benefits

• Values stay in CPU registers
• No memory loads/stores for common operations
• Enables more LLVM optimizations (constant propagation, dead code elimination)
• Spill to memory only when needed (deep stack access, function calls)

Implementation Approach

1. Track virtual stack: Maintain a list of SSA values representing stack top
2. Spill on overflow: When virtual stack exceeds N, spill oldest to memory
3. Reload on underflow: When accessing beyond virtual stack, load from memory
4. Sync at control flow: Ensure consistent state at branches and function calls

Example Transformation

: example ( Int -- Int )
  dup 2 i.* swap 1 i.+ i.+ ;

Current: Multiple memory operations
Optimized:

%doubled = mul i64 %input, 2
%inc = add i64 %input, 1
%result = add i64 %doubled, %inc

Complexity

Medium-high:

• Requires tracking stack state during codegen
• Need to handle control flow merging (phi nodes)
• Function calls require spilling all virtual values
• Interactions with closures and quotations need care

Related

• Optimization: Specialize codegen for integer-only operations #186 (integer specialization) - complementary optimization
• Optimization: Inline small word definitions at call sites #187 (word inlining) - enables more register optimization across words

Part of performance optimization effort. See benchmarks in benchmarks/compute/.

[navicore]

#203