Fix and enable copy propagation optimization

[jserv]

Description

Copy propagation is a fundamental optimization that replaces uses of a copied variable with the original source. While shecc has infrastructure for this optimization, it's currently disabled due to register allocator crashes when encountering NULL operands after dead code elimination.

Current Situation

// Code pattern
int x = 5;
int y = x;  // Copy
int z = y;  // Another copy
return z;   // Could return x directly

// Current: 4 instructions
// Optimized: 1 instruction (return 5)

Root Problem

The optimization pipeline ordering causes issues:

1. Copy propagation removes instructions
2. Dead code elimination removes unused instructions
3. Register allocator dereferences NULL operands without checking
4. Crash: Segmentation fault in register allocation

Solution Approaches

Option 1: Fix Register Allocator (Recommended)

// Add NULL checks in register allocator
void process_operand(insn_t *insn) {
    if (insn->rs1 && insn->rs1->var_name) {  // Add NULL check
        // Process operand
    }
}

Option 2: Preserve Instruction Structure

// Mark instructions as dead instead of removing
insn->is_dead = true;  // Don't set operands to NULL

Option 3: Reorder Pipeline

// Run register allocation before aggressive optimizations
// May miss optimization opportunities

Implementation Requirements

1. Debug Current Crash

• Add assertions to identify NULL dereference location
• Trace through optimization pipeline
• Document exact failure point

2. Fix Register Allocator

• Add defensive NULL checks
• Handle dead instructions gracefully
• Preserve correctness

3. Re-enable Copy Propagation

• Uncomment disabled code
• Add test cases
• Verify no regressions

4. Extend Optimization

• Handle chains of copies
• Propagate through phi nodes
• Consider memory operations

Test Cases

// Simple copy chain
int test1() {
    int a = 42;
    int b = a;
    int c = b;
    return c;  // Should optimize to: return 42;
}

// Copy with arithmetic
int test2(int x) {
    int y = x;
    int z = y + 1;
    return z;  // Should optimize to: return x + 1;
}

// Conditional copies
int test3(int cond, int x) {
    int y;
    if (cond) {
        y = x;
    } else {
        y = x;  // Both paths copy same value
    }
    return y;  // Should optimize to: return x;
}

// Don't propagate across modifications
int test4() {
    int x = 5;
    int y = x;
    x = 10;  // x modified
    return y;  // Must return 5, not x
}

Expected Performance Impact

• 5-15% fewer instructions in copy-heavy code
• Better register allocation
• Enables further constant folding
• Reduced memory traffic

Benefits

• Reduces redundant instructions
• Improves register usage
• Enables chain optimizations
• Standard SSA optimization

Debugging Strategy

// Add debug output
#ifdef DEBUG_COPY_PROP
    printf("Copy propagation: %s -> %s\n", 
           insn->rd->var_name, insn->rs1->var_name);
#endif

// Add assertions
assert(insn->rs1 != NULL && "Operand should not be NULL");

Notes

• High-value fix since code exists
• Should maintain bootstrap capability
• Consider interaction with CSE
• Document safety requirements