第190集：线性扫描寄存器分配

1. 什么是线性扫描寄存器分配？

线性扫描寄存器分配（Linear Scan Register Allocation）是一种高效的寄存器分配算法，它通过线性扫描程序的指令流来分配寄存器。与基于图着色的算法相比，线性扫描算法具有更低的时间复杂度和空间复杂度，因此在编译时间受限的场景中更为常用。

线性扫描的基本思想

1. 计算活跃区间：确定每个变量从定义到最后一次使用的区间
2. 按开始点排序：将活跃区间按其开始点排序
3. 线性扫描：按顺序处理每个活跃区间，分配可用的寄存器
4. 处理溢出：当寄存器不足时，选择合适的变量溢出到内存

线性扫描的优势

• 时间复杂度低：O(n log n)，其中 n 是变量数量
• 空间复杂度低：不需要构建和存储干涉图
• 实现简单：算法逻辑清晰，易于实现
• 编译速度快：适合需要快速编译的场景

2. 活跃区间管理

2.1 活跃区间的表示

class LiveRange:
    """表示变量的活跃区间"""
    def __init__(self, var, start, end, weight=1):
        self.var = var  # 变量名
        self.start = start  # 开始位置
        self.end = end  # 结束位置
        self.weight = weight  # 权重，表示变量的重要性
        self.register = None  # 分配的寄存器
        self.spilled = False  # 是否被溢出

    def __lt__(self, other):
        """按开始位置排序"""
        return self.start < other.start

    def overlaps(self, other):
        """检查是否与另一个活跃区间重叠"""
        return not (self.end < other.start or other.end < self.start)

2.2 活跃区间的计算

def compute_live_ranges(function):
    """计算函数中变量的活跃区间"""
    live_ranges = []
    
    # 1. 计算指令顺序
    instruction_order = []
    for block in function.blocks:
        for instr in block.instructions:
            instruction_order.append(instr)
    
    # 2. 为每个变量计算活跃区间
    var_uses = {}
    var_defs = {}
    
    # 收集变量的定义和使用位置
    for i, instr in enumerate(instruction_order):
        # 处理定义
        for var in instr.defines:
            if var not in var_defs:
                var_defs[var] = i
        
        # 处理使用
        for var in instr.uses:
            if var not in var_uses:
                var_uses[var] = []
            var_uses[var].append(i)
    
    # 构建活跃区间
    for var in set(var_defs.keys()) | set(var_uses.keys()):
        start = var_defs.get(var, 0)
        end = max(var_uses.get(var, [start]))
        live_ranges.append(LiveRange(var, start, end))
    
    return live_ranges

2.3 活跃区间的优先级

变量的优先级影响寄存器分配和溢出决策：

• 使用频率：频繁使用的变量优先级更高
• 活跃区间长度：短活跃区间的变量更容易分配寄存器
• 是否在循环中：循环中的变量优先级更高
• 访问模式：连续访问的变量优先级更高

def calculate_weight(live_range, function):
    """计算活跃区间的权重"""
    # 1. 计算使用频率
    use_count = count_uses(function, live_range.var)
    
    # 2. 计算是否在循环中
    in_loop = is_in_loop(function, live_range.start, live_range.end)
    
    # 3. 计算权重
    weight = use_count
    if in_loop:
        weight *= 2  # 循环中的变量权重翻倍
    
    live_range.weight = weight
    return weight

3. 线性扫描算法的实现

3.1 基本步骤

1. 计算活跃区间：确定每个变量的活跃区间
2. 排序活跃区间：按开始点排序
3. 初始化寄存器池：准备可用的寄存器
4. 扫描并分配：线性扫描活跃区间，分配寄存器
5. 处理溢出：当寄存器不足时，选择变量溢出

3.2 核心算法

def linear_scan_register_allocation(function, num_registers):
    """线性扫描寄存器分配算法"""
    # 1. 计算活跃区间
    live_ranges = compute_live_ranges(function)
    
    # 2. 按开始点排序
    live_ranges.sort()
    
    # 3. 初始化
    active = []  # 当前活跃的区间
    free_registers = list(range(num_registers))  # 可用寄存器
    spilled = []  # 需要溢出的区间
    
    # 4. 线性扫描
    for lr in live_ranges:
        # 4.1 过期处理：释放已经结束的活跃区间
        expire_old_intervals(lr, active, free_registers)
        
        # 4.2 分配寄存器
        if free_registers:
            # 有可用寄存器，直接分配
            lr.register = free_registers.pop(0)
            active.append(lr)
            # 按结束点排序活跃区间，便于过期处理
            active.sort(key=lambda x: x.end)
        else:
            # 无可用寄存器，选择溢出
            spill_candidate = select_spill_candidate(active, lr)
            if spill_candidate.end > lr.end:
                # 溢出候选的结束点比当前区间晚，溢出它
                lr.register = spill_candidate.register
                spill_candidate.register = None
                spill_candidate.spilled = True
                spilled.append(spill_candidate)
                active.remove(spill_candidate)
                active.append(lr)
                active.sort(key=lambda x: x.end)
            else:
                # 溢出当前区间
                lr.spilled = True
                spilled.append(lr)
    
    # 5. 处理溢出
    if spilled:
        generate_spill_code(function, spilled)
    
    # 6. 构建分配映射
    allocation = {}
    for lr in live_ranges:
        if lr.register is not None:
            allocation[lr.var] = lr.register
    
    return allocation, spilled

def expire_old_intervals(current_lr, active, free_registers):
    """释放已经结束的活跃区间"""
    to_remove = []
    for lr in active:
        if lr.end < current_lr.start:
            to_remove.append(lr)
            free_registers.append(lr.register)
    
    for lr in to_remove:
        active.remove(lr)

def select_spill_candidate(active, current_lr):
    """选择溢出候选"""
    # 选择结束点最晚的活跃区间
    return max(active, key=lambda x: x.end)

3.3 溢出处理

def generate_spill_code(function, spilled_ranges):
    """为溢出的变量生成溢出代码"""
    for lr in spilled_ranges:
        var = lr.var
        # 为变量分配栈空间
        stack_offset = allocate_stack_space(function, var)
        
        # 在变量定义后插入存储指令
        insert_store_instructions(function, var, stack_offset)
        
        # 在变量使用前插入加载指令
        insert_load_instructions(function, var, stack_offset)
    
    return function

4. 线性扫描的高级技术

4.1 寄存器类支持

def linear_scan_by_register_class(function, register_classes):
    """按寄存器类进行线性扫描分配"""
    # 1. 按类型分组变量
    grouped_ranges = {}
    for reg_class, registers in register_classes.items():
        grouped_ranges[reg_class] = []
    
    # 计算所有活跃区间
    all_ranges = compute_live_ranges(function)
    
    # 分组
    for lr in all_ranges:
        var_type = get_variable_type(lr.var, function)
        # 根据变量类型选择寄存器类
        reg_class = map_type_to_register_class(var_type)
        if reg_class in grouped_ranges:
            grouped_ranges[reg_class].append(lr)
    
    # 2. 为每个寄存器类分配寄存器
    allocations = {}
    spilled = []
    
    for reg_class, ranges in grouped_ranges.items():
        if not ranges:
            continue
        
        num_registers = len(register_classes[reg_class])
        # 为当前寄存器类执行线性扫描
        class_alloc, class_spilled = linear_scan_register_allocation_for_class(
            ranges, num_registers, register_classes[reg_class]
        )
        allocations.update(class_alloc)
        spilled.extend(class_spilled)
    
    return allocations, spilled

4.2 区间分裂

区间分裂（Range Splitting）是一种优化技术，它将一个长活跃区间分裂成多个短活跃区间，从而提高寄存器分配的成功率：

def split_live_range(live_range, split_points):
    """分裂活跃区间"""
    # 按分裂点排序
    split_points = sorted(split_points)
    
    # 确保分裂点在活跃区间内
    valid_splits = [p for p in split_points if live_range.start < p < live_range.end]
    
    if not valid_splits:
        return [live_range]
    
    # 分裂区间
    new_ranges = []
    current_start = live_range.start
    
    for split in valid_splits:
        # 创建新的活跃区间
        new_range = LiveRange(
            live_range.var,
            current_start,
            split - 1,
            live_range.weight
        )
        new_ranges.append(new_range)
        current_start = split
    
    # 添加最后一个区间
    new_range = LiveRange(
        live_range.var,
        current_start,
        live_range.end,
        live_range.weight
    )
    new_ranges.append(new_range)
    
    return new_ranges

4.3 预着色

预着色（Pre-coloring）是指将某些变量预先分配到特定的寄存器，例如：

• 函数参数：使用调用约定指定的寄存器
• 返回值：使用特定的返回值寄存器
• 特殊变量：需要使用特定寄存器的变量

def precolor_variables(function, allocations):
    """预着色变量"""
    # 1. 处理函数参数
    for i, param in enumerate(function.parameters):
        # 根据调用约定分配寄存器
        reg = get_parameter_register(i)
        if reg is not None:
            allocations[param] = reg
    
    # 2. 处理返回值
    if function.return_var:
        reg = get_return_register()
        if reg is not None:
            allocations[function.return_var] = reg
    
    # 3. 处理特殊变量
    for var in function.special_vars:
        reg = get_special_register(var)
        if reg is not None:
            allocations[var] = reg
    
    return allocations

5. 线性扫描与图着色的比较

5.1 时间复杂度

• 线性扫描：O(n log n)，其中 n 是变量数量
• 图着色：O(n²) 或更高，取决于算法实现

5.2 空间复杂度

• 线性扫描：O(n)，只需要存储活跃区间
• 图着色：O(n²)，需要存储干涉图

5.3 代码质量

• 线性扫描：代码质量通常略低于图着色，但对于大多数程序来说已经足够好
• 图着色：能够找到更优的寄存器分配方案，代码质量更高

5.4 适用场景

• 线性扫描：适合需要快速编译的场景，如 JIT 编译器
• 图着色：适合需要高质量代码的场景，如静态编译器的优化编译

6. 线性扫描的优化

6.1 寄存器分配顺序优化

def optimize_allocation_order(live_ranges):
    """优化分配顺序"""
    # 1. 按权重排序
    live_ranges.sort(key=lambda x: x.weight, reverse=True)
    
    # 2. 然后按开始点排序
    live_ranges.sort(key=lambda x: x.start)
    
    return live_ranges

6.2 溢出优化

def optimize_spilling(spilled_ranges, function):
    """优化溢出"""
    # 1. 合并相邻的溢出变量访问
    merge_adjacent_accesses(function, spilled_ranges)
    
    # 2. 延迟加载和提前存储
    optimize_load_store(function, spilled_ranges)
    
    # 3. 批量溢出
    batch_spill(function, spilled_ranges)
    
    return function

6.3 指令重排序

通过重排序指令来减少寄存器压力：

def reorder_instructions(block):
    """重排序指令以减少寄存器压力"""
    # 1. 分析指令的寄存器使用
    instr_info = []
    for instr in block.instructions:
        info = {
            'instr': instr,
            'uses': get_register_uses(instr),
            'defines': get_register_defines(instr),
            'pressure': calculate_instruction_pressure(instr)
        }
        instr_info.append(info)
    
    # 2. 重排序指令
    # 例如，先执行低寄存器压力的指令
    instr_info.sort(key=lambda x: x['pressure'])
    
    # 3. 更新块的指令
    block.instructions = [info['instr'] for info in instr_info]
    
    return block

7. 现代编译器中的应用

7.1 LLVM 中的线性扫描

LLVM 提供了线性扫描寄存器分配器作为一种快速分配选项：

• FastRegisterAllocator：基于线性扫描的快速分配器
• 适用于 -O0：在没有优化的编译模式下使用
• 编译速度快：牺牲一些代码质量以获得更快的编译速度

7.2 GCC 中的线性扫描

GCC 也实现了线性扫描寄存器分配：

• -fira-algorithm=linear：使用线性扫描算法
• 适用于大型函数：对于大型函数，线性扫描可能比图着色更快
• 可与其他优化结合：可以与其他优化技术结合使用

7.3 JIT 编译器中的应用

线性扫描在 JIT 编译器中特别有用：

• 即时编译：需要快速生成代码
• 动态代码生成：无法提前进行复杂的分析
• 内存限制：JIT 编译器通常内存受限

8. 线性扫描的性能分析

8.1 基准测试

以下是一个基准测试，比较线性扫描和图着色寄存器分配的性能：

// benchmark.c
int main() {
    int a[1000], b[1000], c[1000];
    
    // 初始化数组
    for (int i = 0; i < 1000; i++) {
        a[i] = i;
        b[i] = i * 2;
    }
    
    // 计算 c[i] = a[i] * b[i] + a[i] + b[i]
    for (int i = 0; i < 1000; i++) {
        c[i] = a[i] * b[i] + a[i] + b[i];
    }
    
    // 验证结果
    int sum = 0;
    for (int i = 0; i < 1000; i++) {
        sum += c[i];
    }
    
    printf("Sum: %d\n", sum);
    return 0;
}

8.2 编译时间比较

# 使用线性扫描
clang -O2 -mllvm -regalloc=fast benchmark.c -o linear_scan

# 使用图着色
clang -O2 -mllvm -regalloc=greedy benchmark.c -o graph_coloring

# 比较编译时间
time clang -O2 -mllvm -regalloc=fast benchmark.c -o linear_scan
time clang -O2 -mllvm -regalloc=greedy benchmark.c -o graph_coloring

8.3 执行性能比较

# 运行时间比较
time ./linear_scan
time ./graph_coloring

# 代码大小比较
ls -l linear_scan graph_coloring

9. 线性扫描的局限性

9.1 代码质量

线性扫描算法的代码质量通常略低于图着色算法，主要原因：

• 局部决策：线性扫描是一种贪心算法，基于局部信息做决策
• 缺乏全局视角：无法全局优化寄存器分配
• 溢出策略简单：溢出决策基于简单的启发式规则

9.2 寄存器约束

线性扫描在处理复杂的寄存器约束时可能遇到困难：

• 特殊寄存器要求：某些指令可能需要特定的寄存器
• 寄存器配对：某些指令需要配对使用寄存器
• 调用约定：需要遵守特定的寄存器使用约定

9.3 优化机会

线性扫描可能错过一些优化机会：

• 寄存器复用：可能无法最优地复用寄存器
• 溢出优化：溢出代码可能不够优化
• 与其他优化的集成：与其他优化技术的集成可能不够紧密

10. 未来发展方向

10.1 混合分配策略

结合线性扫描和图着色的优点：

• 快速路径：使用线性扫描处理简单情况
• 精确路径：使用图着色处理复杂情况
• 自适应选择：根据函数特征自动选择最佳策略

10.2 机器学习辅助

使用机器学习技术改进线性扫描：

• 预测溢出成本：预测哪些变量溢出的成本最低
• 优化分配顺序：学习最优的分配顺序
• 调整启发式参数：根据程序特征调整算法参数

10.3 硬件感知分配

考虑硬件特性的寄存器分配：

• 寄存器访问延迟：不同寄存器可能有不同的访问延迟
• 功耗考虑：某些寄存器使用可能更节能
• SIMD 寄存器：优化 SIMD 寄存器的使用

11. 总结

线性扫描寄存器分配是一种高效的寄存器分配算法，它通过线性扫描程序的指令流来分配寄存器。与基于图着色的算法相比，线性扫描算法具有更低的时间复杂度和空间复杂度，因此在编译时间受限的场景中更为常用。

线性扫描的核心优势在于：

• 编译速度快：时间复杂度低，适合快速编译
• 实现简单：算法逻辑清晰，易于实现和维护
• 内存效率高：不需要构建和存储干涉图
• 适用于 JIT：特别适合即时编译和动态代码生成

尽管线性扫描的代码质量通常略低于图着色算法，但对于大多数程序来说已经足够好。在编译时间和代码质量之间，线性扫描提供了一种很好的平衡。

随着编译器技术的发展，线性扫描算法也在不断演进，通过结合其他优化技术和机器学习方法，进一步提高其性能和代码质量。

12. 练习

1. 手动计算活跃区间：为以下代码片段计算每个变量的活跃区间

   int a = 1;
   int b = 2;
   int c = a + b;
   a = 5;
   int d = a * c;

2. 手动执行线性扫描：假设只有2个寄存器，手动执行线性扫描算法分配寄存器

3. 实现简化的线性扫描算法：实现一个简化版的线性扫描寄存器分配算法

4. 溢出分析：分析当寄存器不足时，线性扫描算法如何选择溢出的变量

5. 性能比较实验：使用不同的寄存器分配算法编译同一个程序，比较编译时间和执行性能

6. 区间分裂优化：实现区间分裂技术，提高寄存器分配的成功率

7. 寄存器约束处理：修改线性扫描算法，处理简单的寄存器约束