Architecture: Pluggable Allocation System with Interprocedural Liveness Analysis

[CTalkobt]

Overview

This issue proposes a comprehensive refactoring of memory/resource allocation in the compiler to use a plugin architecture combined with interprocedural liveness analysis. This will make allocation strategies more testable, debuggable, and easier to extend.

Current State

Memory allocation is currently scattered across multiple subsystems:

• Frame allocation (VRegAllocator.cpp) - stack variables
• Static allocation - global variables (implicit, no central strategy)
• Zero-page allocation (implicit in code generation)
• Register allocation - CPU registers (implicit in M65Emitter)

Problems with current approach:

1. Hard to debug: No unified view of allocation decisions
2. Hard to test: Each allocator is tightly coupled to its consumer
3. Hard to optimize: Static allocation can't reuse slots across functions due to lack of liveness info
4. Hard to extend: Adding new allocation strategies requires surgery in multiple files

Proposed Solution

Phase 1: Pluggable Allocator Interface

Create a common allocator interface and registry system:

// include/Allocator.hpp

struct AllocationRequest {
    std::string name;
    uint32_t size;
    uint8_t alignment;
    std::string scope;  // "local", "global", "zp_temp", etc.
    int priority;
};

struct AllocationRecord {
    std::string name;
    uint32_t offset;
    uint32_t size;
    uint8_t alignment;
    std::string scope;
    std::string reason;  // Why this allocation was chosen
};

class Allocator {
public:
    virtual ~Allocator() = default;
    
    virtual uint32_t allocate(const AllocationRequest& req, std::string& errorMsg) = 0;
    virtual bool deallocate(uint32_t offset, uint32_t size) { return false; }
    virtual void reset() = 0;
    
    virtual uint32_t getCurrentOffset() const = 0;
    virtual uint32_t getTotalCapacity() const = 0;
    
    virtual std::vector<AllocationRecord> getRecords() const = 0;
    virtual void dump(std::ostream& os, bool verbose = false) const = 0;
    virtual std::string getName() const = 0;
};

class AllocationRegistry {
private:
    std::map<std::string, std::unique_ptr<Allocator>> allocators_;
    
public:
    void registerAllocator(std::unique_ptr<Allocator> alloc);
    Allocator* get(const std::string& name);
    void dumpAll(std::ostream& os, bool verbose = false) const;
};

Files to create:

• include/Allocator.hpp - Interface and registry
• src/main/AllocationRegistry.cpp - Registry implementation

Existing code to refactor:

• Convert VRegAllocator.cpp → FrameAllocator.cpp (implement Allocator interface)
• Convert ZP allocation → ZeroPageAllocator.cpp (implement Allocator interface)
• Create StaticAllocator.cpp for global variable allocation

Phase 2: Interprocedural Liveness Analysis

Add call-flow graph and liveness analysis to enable better allocation decisions:

// include/CallFlowGraph.hpp

struct LivenessInterval {
    std::string startingFunc;
    uint32_t startOffset;
    std::vector<std::string> callChain;
    uint32_t endOffset;
    std::string endingFunc;
    std::vector<CodePoint> callPointsWithin;
};

struct VariableLifetime {
    std::string name;
    std::string type;
    std::vector<LivenessInterval> intervals;  // Can be disjoint
    std::set<std::string> mayAlias;
    bool isVolatile;
    bool isAcrossCallBoundary;
};

class CallFlowGraph {
public:
    virtual std::vector<VariableLifetime> getLiveVariables(const std::string& func) const = 0;
    virtual bool mayShareMemory(const VariableLifetime& v1, const VariableLifetime& v2) const = 0;
    virtual bool canSafelyShareSlot(
        const std::string& var1Func, uint32_t var1End,
        const std::string& var2Func, uint32_t var2Start) const = 0;
};

Files to create:

• include/CallFlowGraph.hpp - Call-flow interface
• include/ExecutionOrderAnalyzer.hpp - Execution order tracking
• src/main/LivenessAnalyzer.cpp - Liveness analysis implementation

Phase 3: Enhanced Static Allocator

Implement a smart static allocator that uses liveness analysis for slot reuse:

class StaticAllocator : public Allocator {
    // Can reuse slots when:
    // 1. Variables don't overlap in execution order
    // 2. No aliasing issues across function boundaries
    // 3. Call-flow guarantees safe reuse
};

Benefits:

• Reduces binary size by reusing static slots
• Works correctly with call graphs
• Tracks why each decision was made

Files to create/modify:

• src/main/StaticAllocator.cpp - Smart allocation with liveness
• src/main/O45Linker.cpp - Integrate allocation records for debugging

Phase 4: Debugging & Introspection

Enhanced debug output showing allocation decisions:

=== Frame Allocator ===
Current offset: 0x16 / 0x100
Allocations:
  x: offset=0x0 size=2 (declaration order, no alignment padding)
  y: offset=0x2 size=2
  z: offset=0x4 size=2

=== Static Allocator ===
Slot 0: 0x4000-0x4007 (8 bytes)
  Current: file_handle [process() 0x0150-0x0160]
  Reuse: temp_buf [cleanup() 0x0140-0x0145]
    Reason: file_handle ends before cleanup() is called
            Execution order guaranteed safe
  Status: Can reuse after process() → cleanup()

Implementation:

• Add --allocation-dump compiler flag
• Add --allocation-verbose for detailed analysis
• Integration with existing -P<Name> optimization controls

Benefits

1. Debuggability: Centralized view of all allocation decisions
2. Testability: Each allocator can be tested independently
3. Extensibility: Easy to add new allocation strategies (register colors, cache-aware, etc.)
4. Optimization: Static allocator can reuse slots with proper liveness info
5. Correctness: Liveness analysis catches edge cases in call-flow
6. Observability: Records explain why each allocation was made

Estimated Effort

Phase	Tasks	Effort	Priority
1	Interface design, FrameAllocator, ZPAllocator	2-3 days	High
2	CallFlowGraph, LivenessAnalyzer, ExecutionOrder	4-5 days	High
3	StaticAllocator with reuse logic	3-4 days	Medium
4	Debug output, flags, visualization	2-3 days	Medium

Total: 11-15 days (~2-3 weeks)

Implementation Plan

Step 1: Create allocator infrastructure

• Define Allocator interface (include/Allocator.hpp)
• Implement AllocationRegistry
• Unit tests for interface

Step 2: Port existing allocators

• Convert VRegAllocator → FrameAllocator
• Extract ZPAllocator from code generation
• Update CodeGenerator to use registry
• Verify no regressions (all tests pass)

Step 3: Call-flow graph

• Design CallFlowGraph and VariableLifetime structures
• Implement LivenessAnalyzer for IR
• Add execution order computation
• Unit tests for liveness analysis

Step 4: Smart static allocator

• Implement StaticAllocator with slot reuse
• Integrate with LivenessAnalyzer
• Test on real programs (test_short, test_long, etc.)
• Measure binary size impact

Step 5: Debugging features

• Add allocation dump functionality
• Integrate with compiler flags (-Pallocation-verbose)
• Add allocation record output to .s45 assembly
• Update documentation

Testing Strategy

1. Unit tests: Each allocator independently (test with mock CallFlowGraph)
2. Integration tests: CodeGenerator with full registry
3. Regression tests: Existing test suite (make test)
4. Size/performance tests: Measure binary size improvement with smart static allocator
5. Correctness tests: Liveness analysis on programs with complex call-flow

Related Issues

• Frame Offset Bug Fix (already completed): Fixed declaration-order allocation
• Linker Segment Attributes (already completed): Improved code layout
• Static Variable Optimization: Future work for reducing binary size

Open Questions

1. Recursive functions: How to handle variable lifetimes in recursive calls?

   • Proposal: Mark as "always live" to be conservative

2. Indirect calls: How to handle function pointers / callbacks?

   • Proposal: Use may-alias analysis, assume worst case

3. Thread safety: Should allocators be thread-safe?

   • Proposal: Not needed for compile-time allocators, but design for future

4. Plugin registry order: Should allocators be tried in a specific order?

   • Proposal: Yes - frame first (safest), then static (with liveness), then ZP (smallest)

Related Code

• VRegAllocator: src/main/VRegAllocator.cpp
• CodeGenerator: src/main/CodeGenerator.cpp
• O45Linker: src/main/O45Linker.cpp
• IRCodeGen: src/main/IRCodeGen.cpp

---

Note: This architecture was designed during investigation of allocation bugs (frame offset ordering, linker segment handling, tail deduplication) and emerged as a pattern for making similar future bugs easier to track and prevent.