第196集：优化实战（二）—— 循环优化

核心知识点讲解

循环识别

循环识别是循环优化的第一步，目的是在程序中准确识别出循环结构。常见的循环识别算法包括：

  1. 基于控制流图的循环识别：

    • 寻找具有唯一入口（循环头）和返回路径的强连通分量
    • 识别循环不变量和循环变量

  2. 循环的分类：

    • do-while 循环：循环体至少执行一次
    • while 循环：可能一次也不执行
    • for 循环：具有初始化、条件和步进的循环
    • 嵌套循环：循环中包含其他循环

  3. 循环的表示：

    • 使用循环树（Loop Tree）表示嵌套关系
    • 记录循环的基本信息：循环头、循环体、循环出口等

代码外提

代码外提（Loop-Invariant Code Motion, LICM）是将循环不变的计算移到循环外部，避免重复计算。

代码外提的条件：

  1. 计算结果在循环内不发生变化
  2. 计算在每次循环迭代中都会执行
  3. 移动后不会改变程序的语义

代码外提的步骤：

  1. 识别循环不变计算
  2. 检查外提条件
  3. 将不变计算移到循环前置块
  4. 更新引用该计算的地方

强度削弱

强度削弱（Strength Reduction）是将强度较高的操作替换为强度较低的操作，例如：

  • 将乘法替换为加法
  • 将除法替换为乘法或移位
  • 将幂运算替换为乘法

强度削弱的应用场景：

  1. 归纳变量：在循环中线性变化的变量
  2. 数组索引计算：将复杂的地址计算简化
  3. 常量折叠：将运行时计算替换为编译时计算

实现

循环识别实现

def identify_loops(cfg):
    """识别控制流图中的循环"""
    loops = []
    # 1. 构建支配树
    dominators = build_dominator_tree(cfg)
    # 2. 寻找回边
    back_edges = find_back_edges(cfg, dominators)
    # 3. 构建循环
    for back_edge in back_edges:
        loop = build_loop(back_edge, cfg, dominators)
        loops.append(loop)
    return loops

def find_back_edges(cfg, dominators):
    """寻找控制流图中的回边"""
    back_edges = []
    for edge in cfg.edges:
        head, tail = edge
        if tail in dominators[head]:
            back_edges.append(edge)
    return back_edges

def build_loop(back_edge, cfg, dominators):
    """根据回边构建循环"""
    head, tail = back_edge
    loop = {'header': tail, 'body': set()}
    # 收集循环体节点
    worklist = [head]
    while worklist:
        node = worklist.pop()
        if node not in loop['body']:
            loop['body'].add(node)
            # 添加所有前驱节点
            for pred in cfg.predecessors(node):
                if pred not in loop['body']:
                    worklist.append(pred)
    return loop

代码外提实现

def loop_invariant_code_motion(loop, cfg):
    """执行循环不变代码外提"""
    invariant_stmts = []
    # 1. 识别循环不变语句
    for node in loop['body']:
        for stmt in node.stmts:
            if is_invariant(stmt, loop, cfg):
                invariant_stmts.append((node, stmt))
    # 2. 创建前置块
    preheader = create_preheader(loop, cfg)
    # 3. 移动不变语句到前置块
    for node, stmt in invariant_stmts:
        # 检查是否可以安全移动
        if can_move(stmt, loop, cfg):
            # 从原节点移除
            node.stmts.remove(stmt)
            # 添加到前置块
            preheader.stmts.append(stmt)
    return cfg

def is_invariant(stmt, loop, cfg):
    """检查语句是否是循环不变的"""
    # 检查所有操作数是否是循环不变的
    for op in get_operands(stmt):
        if is_loop_variable(op, loop, cfg):
            return False
    return True

def can_move(stmt, loop, cfg):
    """检查语句是否可以安全移动"""
    # 检查是否有副作用
    if has_side_effects(stmt):
        return False
    # 检查所有引用是否在循环内
    for ref in get_references(stmt):
        if is_defined_in_loop(ref, loop, cfg):
            return False
    return True

强度削弱实现

def strength_reduction(loop, cfg):
    """执行强度削弱优化"""
    # 1. 识别归纳变量
    induction_vars = identify_induction_variables(loop, cfg)
    # 2. 对每个归纳变量执行强度削弱
    for var in induction_vars:
        if is_linear_induction(var, loop, cfg):
            # 执行强度削弱
            reduce_strength(var, loop, cfg)
    return cfg

def identify_induction_variables(loop, cfg):
    """识别循环中的归纳变量"""
    induction_vars = []
    for node in loop['body']:
        for stmt in node.stmts:
            if is_induction_assignment(stmt, loop, cfg):
                var = get_assigned_variable(stmt)
                induction_vars.append(var)
    return induction_vars

def reduce_strength(var, loop, cfg):
    """对归纳变量执行强度削弱"""
    # 找到归纳变量的定义
    def_stmt = find_definition(var, loop, cfg)
    # 分析归纳变量的更新方式
    update = analyze_update(def_stmt)
    # 执行强度削弱
    if update['op'] == '*':
        # 将乘法替换为加法
        replace_with_addition(var, update, loop, cfg)
    elif update['op'] == '/':
        # 将除法替换为乘法或移位
        replace_with_multiplication(var, update, loop, cfg)

实用案例分析

案例：数组求和循环优化

原始代码

int sum_array(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

优化步骤

  1. 循环识别：

    • 识别出 for 循环，循环变量为 i
    • 循环条件为 i &lt; n
    • 循环步进为 i++

  2. 代码外提：

    • 识别出 n 是循环不变量
    • 数组 arr 的基地址是循环不变量

  3. 强度削弱：

    • 识别出 i 是归纳变量
    • 数组索引计算 arr[i] 可以优化

  4. 优化后代码：

int sum_array(int arr[], int n) {
    int sum = 0;
    int *p = arr; // 数组基地址外提
    int limit = n; // 循环边界外提
    for (int i = 0; i < limit; i++) {
        sum += *p++; // 强度削弱：将 arr[i] 替换为 *p++
    }
    return sum;
}

案例：矩阵乘法循环优化

原始代码

void matrix_multiply(int a[][N], int b[][N], int c[][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            c[i][j] = 0;
            for (int k = 0; k < N; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

优化步骤

  1. 循环识别：

    • 识别出三层嵌套循环
    • 外层循环变量 i，中层 j，内层 k

  2. 循环变换：

    • 交换循环顺序，提高缓存命中率

  3. 代码外提：

    • 外提不变的数组访问

  4. 强度削弱：

    • 优化数组索引计算

  5. 优化后代码：

void matrix_multiply(int a[][N], int b[][N], int c[][N]) {
    // 循环交换：i -> k -> j
    for (int i = 0; i < N; i++) {
        int *a_row = a[i]; // 外提数组行指针
        for (int k = 0; k < N; k++) {
            int a_val = a_row[k]; // 外提内层循环不变量
            for (int j = 0; j < N; j++) {
                c[i][j] += a_val * b[k][j]; // 强度削弱
            }
        }
    }
}

代码优化建议

  1. 循环识别优化：

    • 使用更精确的循环识别算法，如 Havlak 算法
    • 考虑循环的嵌套关系，优先优化内层循环
    • 识别并处理特殊循环，如计数循环、指针递增循环等

  2. 代码外提优化：

    • 结合常量传播，进一步提高外提效果
    • 考虑移动后的代码对其他优化的影响
    • 注意副作用，确保移动不会改变程序语义

  3. 强度削弱优化：

    • 针对不同的处理器架构，选择合适的强度削弱策略
    • 结合指令选择，选择最优的指令序列
    • 考虑溢出风险，确保优化后的代码正确性

  4. 循环变换优化：

    • 结合循环交换、循环分块等技术
    • 考虑数据局部性，优化缓存使用
    • 针对不同的硬件平台，选择合适的变换策略

  5. 实现建议：

    • 使用模块化设计，将循环识别、代码外提、强度削弱等功能分离
    • 实现增量优化，避免重复计算
    • 添加调试信息，便于验证优化效果

总结

本集我们深入学习了循环优化的实战技术，包括：

  1. 循环识别的方法和实现
  2. 代码外提的条件和步骤
  3. 强度削弱的应用场景和实现
  4. 实际案例：数组求和和矩阵乘法的循环优化
  5. 代码优化建议

循环优化是编译器优化中最重要的部分之一，通过合理应用循环优化技术，可以显著提高程序的执行效率。在实际应用中，需要根据具体的代码结构和硬件平台，选择合适的优化策略，以达到最佳的优化效果。

« 上一篇 优化实战（一）—— 局部优化 下一篇 » 优化实战（三）—— 寄存器分配
↑