Improve spill cost calculation with execution frequency and loop depth

[jserv]

Description

The current spill cost calculation uses simple heuristics that don't account for execution frequency or loop nesting depth. This leads to poor spilling decisions where frequently-used variables in hot loops get spilled while rarely-used variables stay in registers.

Current Problem

// Current: all variables treated equally
void bad_spill_decision() {
    int rarely_used = get_value();  // Used once
    
    for (int i = 0; i < 1000000; i++) {
        int frequently_used = i * 2;  // Used million times
        // Current allocator might spill frequently_used!
        process(frequently_used);
    }
    
    return rarely_used;  // Keep in register whole time?
}

Improved Spill Cost Model

1. Execution Frequency Analysis

typedef struct {
    int static_count;     // Number of uses/defs in code
    int dynamic_count;    // Estimated execution count
    int loop_depth;       // Nesting level (0 = not in loop)
    bool in_hot_path;     // Profile-guided info
} use_info_t;

typedef struct {
    var_t *var;
    use_info_t *uses;     // Array of use sites
    int num_uses;
    use_info_t *defs;     // Array of definition sites
    int num_defs;
    float total_cost;     // Computed spill cost
} spill_info_t;

2. Loop Depth Tracking

void compute_loop_depths(func_t *func) {
    // Find natural loops
    loop_forest_t *loops = find_natural_loops(func);
    
    // Assign depth to each basic block
    for (loop in loops) {
        for (bb in loop->blocks) {
            bb->loop_depth = loop->nesting_level;
            
            // Mark loop headers for special treatment
            if (bb == loop->header) {
                bb->is_loop_header = true;
                bb->estimated_iterations = estimate_loop_iterations(loop);
            }
        }
    }
}

int estimate_loop_iterations(loop_t *loop) {
    // Simple heuristics
    if (has_constant_bound(loop)) {
        return get_constant_bound(loop);
    } else if (is_while_loop(loop)) {
        return 10;  // Conservative estimate
    } else {
        return 100; // Default for complex loops
    }
}

3. Spill Cost Calculation

float calculate_spill_cost_advanced(spill_info_t *info) {
    float cost = 0.0;
    
    // Cost of spilling definitions (stores)
    for (int i = 0; i < info->num_defs; i++) {
        use_info_t *def = &info->defs[i];
        float def_cost = STORE_COST;
        
        // Exponential weight for loop depth
        def_cost *= pow(LOOP_WEIGHT, def->loop_depth);
        
        // Estimated dynamic count
        def_cost *= estimate_execution_count(def);
        
        cost += def_cost;
    }
    
    // Cost of spilling uses (loads)
    for (int i = 0; i < info->num_uses; i++) {
        use_info_t *use = &info->uses[i];
        float use_cost = LOAD_COST;
        
        // Loop depth weight
        use_cost *= pow(LOOP_WEIGHT, use->loop_depth);
        
        // Execution count
        use_cost *= estimate_execution_count(use);
        
        // Special cases
        if (use->in_hot_path) {
            use_cost *= HOT_PATH_WEIGHT;
        }
        
        cost += use_cost;
    }
    
    // Normalize by live range length
    int range_length = info->var->live_end - info->var->live_start;
    cost /= max(1, range_length);
    
    // Special adjustments
    if (info->var->is_constant) {
        cost *= REMATERIALIZABLE_DISCOUNT;  // Can recreate instead of load
    }
    
    if (info->var->crosses_call) {
        cost *= CALL_CROSSING_DISCOUNT;  // Likely spilled anyway
    }
    
    return cost;
}

4. Rematerialization Detection

bool is_rematerializable(var_t *var) {
    if (var->is_constant) return true;
    
    // Check if variable comes from simple computation
    insn_t *def = get_single_definition(var);
    if (!def) return false;
    
    switch (def->op) {
    case OP_LOAD_CONST:
    case OP_GET_ADDR:
        return true;
        
    case OP_ADD:
    case OP_SUB:
        // Rematerializable if operands are available
        return operands_available_at_uses(def);
        
    default:
        return false;
    }
}

float get_rematerialization_cost(var_t *var) {
    if (var->is_constant) {
        return 1.0;  // Single instruction
    }
    
    insn_t *def = get_single_definition(var);
    return count_instructions(def);
}

5. Profile-Guided Spill Costs

typedef struct {
    char *function_name;
    int bb_id;
    long execution_count;
} profile_data_t;

void apply_profile_data(func_t *func, profile_data_t *profile) {
    for (entry in profile) {
        if (strcmp(entry->function_name, func->name) == 0) {
            basic_block_t *bb = find_bb_by_id(func, entry->bb_id);
            bb->execution_count = entry->execution_count;
            bb->is_hot = entry->execution_count > HOT_THRESHOLD;
        }
    }
}

float estimate_execution_count(use_info_t *use) {
    if (use->bb->execution_count > 0) {
        // Use profile data
        return use->bb->execution_count;
    } else {
        // Use static estimate
        return pow(10, use->loop_depth) * use->bb->static_frequency;
    }
}

6. Spill Priority Queue

typedef struct {
    var_t **vars;
    float *costs;
    int count;
} spill_queue_t;

void build_spill_priority_queue(func_t *func, spill_queue_t *queue) {
    for (var in all_variables) {
        spill_info_t *info = analyze_variable(var);
        float cost = calculate_spill_cost_advanced(info);
        
        // Insert into priority queue (min-heap)
        insert_with_priority(queue, var, cost);
    }
}

var_t *select_spill_candidate(spill_queue_t *queue) {
    // Return variable with minimum spill cost
    return extract_min(queue);
}

Configuration Constants

#define LOAD_COST 3.0          // Cycles for memory load
#define STORE_COST 2.0         // Cycles for memory store
#define LOOP_WEIGHT 10.0       // Multiplier per loop level
#define HOT_PATH_WEIGHT 5.0    // Extra weight for hot paths
#define REMATERIALIZABLE_DISCOUNT 0.1  // 90% discount
#define CALL_CROSSING_DISCOUNT 0.5     // 50% discount
#define HOT_THRESHOLD 1000     // Execution count for "hot"

Test Cases

// Loop depth consideration
void test_loop_spill() {
    int outer = 0;
    for (int i = 0; i < 100; i++) {
        int inner = 0;
        for (int j = 0; j < 100; j++) {
            inner += i * j;  // Should keep inner, i, j in registers
        }
        outer += inner;
    }
    return outer;  // outer less important than loop variables
}

// Rematerialization
void test_rematerialize() {
    const int constant = 42;
    int result = 0;
    for (int i = 0; i < 1000; i++) {
        // Should rematerialize constant rather than spill
        result += constant * i;
    }
    return result;
}

// Profile-guided
void test_profile_guided(int flag) {
    int cold_var = complex_computation();
    
    if (flag) {  // Assume rarely taken
        use(cold_var);
    }
    
    // Hot loop
    for (int i = 0; i < 1000000; i++) {
        int hot_var = i * 2;
        process(hot_var);  // Keep hot_var in register
    }
}

Expected Impact

• 40-60% better spill decisions
• Significantly reduced spilling in loops
• Better performance for hot code paths
• Smaller performance degradation under register pressure

Success Metrics

• Loop variables rarely spilled
• Measurable performance improvement in loops
• Reduced total spill count
• Better correlation with profiling data