Implement register coalescing to eliminate unnecessary moves

[jserv]

Description

Register coalescing is an optimization that eliminates move instructions by assigning the source and destination of a move to the same register. This reduces instruction count and improves performance by eliminating redundant data movement.

Current Problem

// Current code generation creates many moves
int x = a + b;  // t1 = a + b; x = t1 (MOVE)
int y = x;      // y = x (MOVE)
int z = y * 2;  // t2 = y * 2; z = t2 (MOVE)
return z;       // return z (MOVE to return register)

// After coalescing: eliminate 3-4 moves

Coalescing Algorithm

1. Move Instruction Analysis

typedef struct {
    insn_t *insn;
    var_t *src;
    var_t *dst;
    bool can_coalesce;
    int benefit;  // Estimated benefit of coalescing
} move_info_t;

typedef struct {
    move_info_t **moves;
    int count;
    ig_graph_t *interference_graph;
} coalesce_context_t;

void collect_moves(func_t *func, coalesce_context_t *ctx) {
    for (bb in func->bbs) {
        for (insn in bb->insns) {
            if (is_move(insn)) {
                move_info_t *info = analyze_move(insn);
                add_move(ctx, info);
            }
        }
    }
}

bool is_move(insn_t *insn) {
    return insn->op == OP_MOV || 
           (insn->op == OP_ASSIGN && insn->rs2 == NULL);
}

2. Interference Check

bool can_coalesce_safely(var_t *src, var_t *dst, ig_graph_t *graph) {
    // Cannot coalesce if they interfere
    if (interferes(graph, src, dst)) {
        return false;
    }
    
    // Check George's criterion: conservative coalescing
    // For each neighbor of src, it must either:
    // - Already interfere with dst, or
    // - Have low degree (< K colors)
    for (neighbor in get_neighbors(graph, src)) {
        if (!interferes(graph, neighbor, dst)) {
            if (degree(graph, neighbor) >= NUM_REGISTERS) {
                return false;  // Would create high-degree node
            }
        }
    }
    
    return true;
}

bool interferes(ig_graph_t *graph, var_t *v1, var_t *v2) {
    // Check if live ranges overlap
    if (v1->live_end < v2->live_start || 
        v2->live_end < v1->live_start) {
        return false;  // Disjoint ranges
    }
    
    // Check interference graph
    return has_edge(graph, v1, v2);
}

3. Coalescing Strategy

typedef enum {
    COALESCE_AGGRESSIVE,  // Try all possible coalescing
    COALESCE_CONSERVATIVE, // Only guaranteed safe
    COALESCE_OPTIMISTIC   // Aggressive with backoff
} coalesce_strategy_t;

void coalesce_moves(coalesce_context_t *ctx, coalesce_strategy_t strategy) {
    // Sort moves by benefit
    sort_moves_by_benefit(ctx->moves);
    
    bool changed = true;
    while (changed) {
        changed = false;
        
        for (move in ctx->moves) {
            if (move->can_coalesce) {
                bool should_coalesce = false;
                
                switch (strategy) {
                case COALESCE_CONSERVATIVE:
                    should_coalesce = can_coalesce_safely(
                        move->src, move->dst, ctx->interference_graph);
                    break;
                    
                case COALESCE_AGGRESSIVE:
                    should_coalesce = !interferes(
                        ctx->interference_graph, move->src, move->dst);
                    break;
                    
                case COALESCE_OPTIMISTIC:
                    should_coalesce = evaluate_coalesce_benefit(move) > 0;
                    break;
                }
                
                if (should_coalesce) {
                    perform_coalescing(move, ctx);
                    changed = true;
                }
            }
        }
    }
}

4. Performing Coalescing

void perform_coalescing(move_info_t *move, coalesce_context_t *ctx) {
    var_t *src = move->src;
    var_t *dst = move->dst;
    
    // Merge variables
    var_t *merged = merge_variables(src, dst);
    
    // Update interference graph
    merge_nodes(ctx->interference_graph, src, dst, merged);
    
    // Update all uses and defs
    replace_all_occurrences(src, merged);
    replace_all_occurrences(dst, merged);
    
    // Remove move instruction
    remove_instruction(move->insn);
    
    // Update live ranges
    merged->live_start = min(src->live_start, dst->live_start);
    merged->live_end = max(src->live_end, dst->live_end);
}

void merge_nodes(ig_graph_t *graph, var_t *src, var_t *dst, var_t *merged) {
    // Union of neighbors
    for (neighbor in get_neighbors(graph, src)) {
        add_edge(graph, merged, neighbor);
    }
    for (neighbor in get_neighbors(graph, dst)) {
        add_edge(graph, merged, neighbor);
    }
    
    // Remove old nodes
    remove_node(graph, src);
    remove_node(graph, dst);
    
    // Add merged node
    add_node(graph, merged);
}

5. Benefit Analysis

int calculate_coalesce_benefit(move_info_t *move) {
    int benefit = 1;  // Base benefit of eliminating move
    
    // Higher benefit for moves in loops
    benefit *= pow(10, move->insn->loop_depth);
    
    // Higher benefit for frequently executed moves
    if (move->insn->bb->execution_count > 0) {
        benefit *= log(move->insn->bb->execution_count);
    }
    
    // Consider register pressure
    if (move->insn->bb->register_pressure > HIGH_PRESSURE_THRESHOLD) {
        benefit *= 2;  // More valuable when pressure is high
    }
    
    // Penalty for increasing interference
    int new_edges = count_new_interference_edges(move);
    benefit -= new_edges * INTERFERENCE_PENALTY;
    
    return benefit;
}

6. Special Cases

// Phi-node coalescing
void coalesce_phi_nodes(func_t *func) {
    for (bb in func->bbs) {
        for (phi in bb->phi_nodes) {
            // Try to assign phi result same register as operands
            for (operand in phi->operands) {
                if (can_coalesce_safely(phi->result, operand)) {
                    perform_coalescing(phi->result, operand);
                    break;
                }
            }
        }
    }
}

// Copy propagation integration
void coalesce_with_copy_propagation(func_t *func) {
    // First do copy propagation to expose more moves
    run_copy_propagation(func);
    
    // Then coalesce remaining moves
    coalesce_context_t ctx = build_context(func);
    coalesce_moves(&ctx, COALESCE_CONSERVATIVE);
}

// Two-address instruction handling (x86-style)
void handle_two_address_instructions(insn_t *insn) {
    // For instructions like: dst = dst op src
    // Try to coalesce dst with its previous value
    if (is_two_address(insn) && insn->rd == insn->rs1) {
        // Already coalesced
        return;
    }
    
    // Insert move and try to coalesce
    insert_move(insn->rd, insn->rs1);
    mark_for_coalescing(insn->rd, insn->rs1);
}

Test Cases

// Simple move chain
int test_move_chain() {
    int a = 5;
    int b = a;  // Should coalesce b with a
    int c = b;  // Should coalesce c with b/a
    return c;   // All use same register
}

// Loop with moves
int test_loop_moves(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int temp = i;      // Should coalesce
        int doubled = temp * 2;
        sum += doubled;
    }
    return sum;
}

// Phi coalescing
int test_phi_coalesce(int x, int y) {
    int result;
    if (x > y) {
        result = x;  // Phi operand 1
    } else {
        result = y;  // Phi operand 2
    }
    return result;   // Phi result - try to coalesce
}

// Cannot coalesce (interference)
int test_no_coalesce() {
    int a = 5;
    int b = 10;
    int c = a;   // Cannot coalesce c with a
    a = 20;      // a still live, interferes with c
    return a + c;
}

Integration with Register Allocator

void integrated_register_allocation(func_t *func) {
    // Phase 1: Build initial interference graph
    ig_graph_t *graph = build_interference_graph(func);
    
    // Phase 2: Coalesce moves
    coalesce_context_t ctx = {
        .interference_graph = graph,
        .moves = collect_moves(func)
    };
    coalesce_moves(&ctx, COALESCE_CONSERVATIVE);
    
    // Phase 3: Color the graph
    color_graph(graph);
    
    // Phase 4: Assign registers
    assign_registers(func, graph);
}

Expected Benefits

• 10-30% reduction in move instructions
• Better register utilization
• Improved performance (fewer instructions)
• Reduced code size

Success Metrics

• Move instruction count reduction
• No increase in spill code
• Correct program semantics preserved
• Performance improvement on benchmarks