Implement function inlining optimization in SSA

No source files, entry points, or existing tests are named. Start by locating the SSA optimizer, call-graph handling, and optimization pass ordering, then review how SSA values and multiple returns are represented. Done means conservative inlining handles the listed cases, updates related compiler state, and has tests for each required behavior.

Description

Function inlining eliminates call overhead by replacing function calls with the function body. This optimization is especially valuable for small, frequently-called functions and enables further optimizations.

Current Behavior

int add(int a, int b) { return a + b; }
int compute() {
    return add(3, 4);  // Function call overhead
}

Expected Behavior

After inlining:

int compute() {
    return 3 + 4;  // Direct computation, enables constant folding
}

Implementation Requirements

1. Inlining Analysis

• Calculate function size (instruction count)
• Estimate call frequency
• Cost-benefit analysis
• Detect recursive calls

2. SSA Transformation

• Clone function body in SSA form
• Replace parameters with arguments
• Rename SSA variables to avoid conflicts
• Handle return values

3. Integration Points

• Inline before other optimizations
• Update call graph
• Preserve debug information
• Handle multiple return points

4. Heuristics

bool should_inline(func_t *func, call_site_t *site) {
    if (func->insn_count > 30) return false;  // Too large
    if (func->is_recursive) return false;      // Recursive
    if (site->in_loop) return true;            // Hot path
    if (func->call_count == 1) return true;    // Called once
    return func->insn_count < 10;              // Small enough
}

Test Cases

// Simple inlining
static int square(int x) { return x * x; }
int test1() {
    return square(5);  // Should inline to: return 5 * 5;
}

// Multiple returns
int abs(int x) {
    if (x < 0) return -x;
    return x;
}
int test2(int y) {
    return abs(y) + 1;  // Should inline with phi node
}

// Loop context (high value)
int sum(int *arr, int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += get_value(arr, i);  // Should inline if small
    }
    return total;
}

// Don't inline large functions
int complex_function(int x) {
    // 100+ instructions
}

// Don't inline recursive
int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n-1);  // Don't inline
}

Performance Impact

• 5-15% improvement for call-heavy code
• Enables constant folding and dead code elimination
• Reduces function call overhead
• Improves instruction cache locality

Implementation Strategy

1. Add function size calculation
2. Implement basic inlining for leaf functions
3. Handle multiple returns with phi nodes
4. Add heuristics for call sites
5. Integrate with existing optimizations

Benefits

• Eliminates function call overhead
• Enables cross-function optimizations
• Improves constant propagation
• Better register allocation

Interaction with Other Optimizations

• Run before: Constant propagation, DCE, LICM
• Enables: Constant folding, better CSE
• Consider: Code size vs speed tradeoff

Notes

• Start with static functions
• Be conservative with size limits
• Profile-guided inlining in future