第180集：代码外提

核心知识点讲解

什么是代码外提？

代码外提（Loop-Invariant Code Motion，LICM）是一种循环优化技术，它将循环内的循环不变计算移到循环体外，避免在每次循环迭代中重复计算相同的值。

循环不变计算是指在循环执行过程中，其值不会发生变化的计算。例如：

// 循环不变计算：x * 10
for (i = 0; i < n; i++) {
    y = x * 10;
    a[i] = y + i;
}

通过代码外提，可以优化为：

y = x * 10;
for (i = 0; i < n; i++) {
    a[i] = y + i;
}

代码外提的好处

1. 减少计算量：避免重复计算，减少CPU执行时间
2. 降低能耗：减少计算次数，降低处理器能耗
3. 提高缓存利用率：减少循环体大小，提高指令缓存命中率
4. 为其他优化创造机会：简化循环体，使其他优化技术更容易应用

循环不变量的识别

识别循环不变量是代码外提的关键步骤。一个表达式是循环不变的，当且仅当：

1. 所有操作数都是循环不变的：表达式中使用的所有变量在循环内都不会被修改
2. 表达式本身在循环内不会被修改：表达式的结果不会被循环内的其他操作改变

代码外提的条件

并不是所有的循环不变计算都可以外提到循环体外。代码外提需要满足以下条件：

1. 安全性条件

• 执行条件：外提后的计算必须在循环执行前执行，且执行次数与原代码相同
  • 如果循环可能不执行（如 for (i = 0; i < 0; i++)），那么外提的计算也不应该执行
• 异常安全性：外提的计算不应该引入新的异常
• 语义保持：外提后的代码语义必须与原代码相同

2. 可行性条件

• 循环不变性：计算结果在循环内不会改变
• 可达性：外提的计算在原代码中对所有循环迭代都是可达的
• 副作用：计算没有副作用，或者副作用可以安全地外提

代码外提的实现算法

代码外提的实现通常包括以下步骤：

1. 循环识别：识别程序中的循环结构
2. 不变量检测：识别循环内的循环不变计算
3. 外提条件检查：检查不变计算是否满足外提条件
4. 代码变换：将满足条件的不变计算外提到循环体外
5. 代码清理：删除循环内被外提的计算

数据流分析在代码外提中的应用

代码外提需要使用数据流分析来：

1. 到达定值分析：确定变量在循环入口处的值是否可用
2. 活跃变量分析：确定变量在循环出口处是否仍然被使用
3. 循环不变性分析：确定表达式是否是循环不变的

实用案例分析

基本代码外提示例

原始代码

for (int i = 0; i < n; i++) {
    int j = i * 2;
    a[j] = x * y + i;
    b[j] = x * y - i;
}

优化分析

1. 识别循环不变计算：x * y 在循环内不会改变
2. 检查外提条件：
   • x * y 是循环不变的
   • 循环执行前计算 x * y 是安全的
   • 计算没有副作用
3. 执行代码外提：将 x * y 计算移到循环外

优化后代码

int temp = x * y;
for (int i = 0; i < n; i++) {
    int j = i * 2;
    a[j] = temp + i;
    b[j] = temp - i;
}

复杂表达式的代码外提

原始代码

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        a[i][j] = (x + y) * (z - w) + i * j;
    }
}

优化分析

1. 识别循环不变计算：
   • 对于内层循环，(x + y) * (z - w) 和 i 都是不变的
   • 对于外层循环，(x + y) * (z - w) 是不变的
2. 执行代码外提：
   • 将 (x + y) * (z - w) 外提到外层循环
   • 将 i 相关的计算在适当位置外提

优化后代码

int temp = (x + y) * (z - w);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        a[i][j] = temp + i * j;
    }
}

带有条件判断的代码外提

原始代码

for (int i = 0; i < n; i++) {
    if (flag) {
        y = x * 10;
    } else {
        y = x * 20;
    }
    a[i] = y + i;
}

优化分析

1. 识别循环不变计算：x * 10 和 x * 20 都是循环不变的
2. 检查外提条件：
   • 虽然计算在条件分支中，但它们仍然是循环不变的
   • 可以将条件判断一起外提
3. 执行代码外提：将条件判断和不变计算外提到循环外

优化后代码

int y;
if (flag) {
    y = x * 10;
} else {
    y = x * 20;
}
for (int i = 0; i < n; i++) {
    a[i] = y + i;
}

数组访问的代码外提

原始代码

for (int i = 0; i < n; i++) {
    a[i] = b[0] + c[0];
}

优化分析

1. 识别循环不变计算：b[0] + c[0] 是循环不变的
2. 执行代码外提：将数组访问外提到循环外

优化后代码

int temp = b[0] + c[0];
for (int i = 0; i < n; i++) {
    a[i] = temp;
}

代码实现

循环不变计算检测

class LoopInvariantDetector:
    def __init__(self, cfg):
        self.cfg = cfg  # 控制流图，格式为 {block_name: [instructions]}
    
    def _get_defs(self, block):
        """获取基本块中定义的变量"""
        defs = set()
        for instr in self.cfg.get(block, []):
            if '=' in instr:
                left, _ = instr.split('=', 1)
                left = left.strip()
                defs.add(left)
        return defs
    
    def _get_uses(self, instr):
        """获取指令中使用的变量"""
        uses = set()
        if '=' in instr:
            _, right = instr.split('=', 1)
            expr = right.strip()
        else:
            expr = instr.strip()
        
        # 简单的变量提取
        for token in expr.split():
            token = token.strip('+*-/()[]{};')
            if token.isidentifier():
                uses.add(token)
        
        return uses
    
    def _is_invariant(self, instr, loop, loop_defs):
        """检查指令是否是循环不变的"""
        if '=' not in instr:
            return False
        
        left, right = instr.split('=', 1)
        left = left.strip()
        right = right.strip()
        
        # 检查左侧变量是否在循环中被定义
        if left in loop_defs:
            return False
        
        # 检查右侧使用的变量是否在循环中被定义
        uses = self._get_uses(right)
        for var in uses:
            if var in loop_defs:
                return False
        
        return True
    
    def detect_invariants(self, loop):
        """检测循环中的循环不变计算"""
        # 收集循环中所有定义的变量
        loop_defs = set()
        for block in loop:
            loop_defs.update(self._get_defs(block))
        
        # 检测循环不变计算
        invariants = []
        for block in loop:
            for instr in self.cfg.get(block, []):
                if self._is_invariant(instr, loop, loop_defs):
                    invariants.append((block, instr))
        
        return invariants

# 测试示例
cfg = {
    "B1": ["i = 0", "goto B2"],
    "B2": ["if i < n goto B3", "goto B5"],
    "B3": ["y = x * 10", "a[i] = y + i", "i = i + 1", "goto B2"],
    "B5": ["return"]
}

loop = {"B2", "B3"}

lid = LoopInvariantDetector(cfg)
invariants = lid.detect_invariants(loop)

print("检测到的循环不变计算:")
for block, instr in invariants:
    print(f"  {block}: {instr}")

代码外提实现

class LoopInvariantCodeMotion:
    def __init__(self, cfg):
        self.cfg = cfg
        self.lid = LoopInvariantDetector(cfg)
    
    def _can_move(self, instr, loop, entry_block):
        """检查指令是否可以外提"""
        # 简化实现：假设所有循环不变计算都可以外提
        # 实际实现需要考虑更多因素，如异常安全性、副作用等
        return True
    
    def _insert_before_loop(self, invariant_instrs, entry_block):
        """在循环入口前插入外提的指令"""
        # 简化实现：在循环入口块前添加一个新块
        new_block_name = f"{entry_block}_pre"
        self.cfg[new_block_name] = invariant_instrs
        return new_block_name
    
    def optimize(self, loop, entry_block):
        """执行代码外提"""
        # 1. 检测循环不变计算
        invariants = self.lid.detect_invariants(loop)
        
        if not invariants:
            print("没有可外提的循环不变计算")
            return self.cfg
        
        # 2. 收集可外提的指令
        invariant_instrs = []
        blocks_to_modify = {}
        
        for block, instr in invariants:
            if self._can_move(instr, loop, entry_block):
                invariant_instrs.append(instr)
                # 记录需要修改的块和指令
                if block not in blocks_to_modify:
                    blocks_to_modify[block] = []
                blocks_to_modify[block].append(instr)
        
        if not invariant_instrs:
            print("没有可安全外提的循环不变计算")
            return self.cfg
        
        # 3. 在循环前插入外提的指令
        pre_block = self._insert_before_loop(invariant_instrs, entry_block)
        
        # 4. 修改控制流：将前置块连接到循环入口
        # 简化实现：假设B1是前置块
        # 实际实现需要更复杂的控制流分析和修改
        
        # 5. 从循环中删除外提的指令
        for block, instrs_to_remove in blocks_to_modify.items():
            original_instrs = self.cfg.get(block, [])
            new_instrs = [instr for instr in original_instrs if instr not in instrs_to_remove]
            self.cfg[block] = new_instrs
        
        print(f"外提到循环外的指令:")
        for instr in invariant_instrs:
            print(f"  {instr}")
        
        return self.cfg

# 测试示例
licm = LoopInvariantCodeMotion(cfg)
optimized_cfg = licm.optimize(loop, "B2")

print("\n优化后的控制流图:")
for block, instrs in optimized_cfg.items():
    print(f"\n{block}:")
    for instr in instrs:
        print(f"  {instr}")

高级代码外提实现

class AdvancedLICM:
    def __init__(self, cfg):
        self.cfg = cfg
        self.lid = LoopInvariantDetector(cfg)
    
    def _find_entry_block(self, loop):
        """查找循环的入口块"""
        # 简化实现：假设循环中编号最小的块是入口块
        # 实际实现需要基于支配关系分析
        return min(loop)
    
    def _find_predecessors(self, block):
        """查找基本块的前驱"""
        predecessors = []
        for b, instrs in self.cfg.items():
            # 简化实现：检查是否有跳转到目标块的指令
            for instr in instrs:
                if f"goto {block}" in instr or f"if " in instr and f" goto {block}" in instr:
                    predecessors.append(b)
        return predecessors
    
    def _build_control_dependencies(self):
        """构建控制依赖关系"""
        # 简化实现：返回空字典
        # 实际实现需要复杂的控制依赖分析
        return {}
    
    def optimize(self, loop):
        """执行高级代码外提"""
        # 1. 查找循环入口块
        entry_block = self._find_entry_block(loop)
        
        # 2. 检测循环不变计算
        invariants = self.lid.detect_invariants(loop)
        
        if not invariants:
            return self.cfg
        
        # 3. 构建控制依赖关系
        control_deps = self._build_control_dependencies()
        
        # 4. 按依赖顺序排序不变计算
        # 简化实现：保持原顺序
        sorted_invariants = invariants
        
        # 5. 外提不变计算
        invariant_instrs = []
        blocks_to_modify = {}
        
        for block, instr in sorted_invariants:
            invariant_instrs.append(instr)
            if block not in blocks_to_modify:
                blocks_to_modify[block] = []
            blocks_to_modify[block].append(instr)
        
        # 6. 在循环前插入外提的指令
        # 简化实现：在入口块前添加指令
        if invariant_instrs:
            # 查找入口块的前驱
            predecessors = self._find_predecessors(entry_block)
            if predecessors:
                # 在第一个前驱块末尾添加外提的指令
                pred_block = predecessors[0]
                self.cfg[pred_block].extend(invariant_instrs)
            else:
                # 如果没有前驱，创建新的入口块
                new_entry = f"{entry_block}_pre"
                self.cfg[new_entry] = invariant_instrs
                # 需要更新控制流，这里简化处理
        
        # 7. 从循环中删除外提的指令
        for block, instrs_to_remove in blocks_to_modify.items():
            original_instrs = self.cfg.get(block, [])
            new_instrs = [instr for instr in original_instrs if instr not in instrs_to_remove]
            self.cfg[block] = new_instrs
        
        return self.cfg

# 测试示例
alicm = AdvancedLICM(cfg)
optimized_cfg = alicm.optimize(loop)

print("\n高级优化后的控制流图:")
for block, instrs in optimized_cfg.items():
    print(f"\n{block}:")
    for instr in instrs:
        print(f"  {instr}")

技术要点总结

1. 代码外提的核心：识别并外提循环不变计算，避免重复计算

2. 循环不变计算的识别：

   • 表达式中使用的所有变量在循环内都不会被修改
   • 表达式本身在循环内不会被修改

3. 代码外提的条件：

   • 安全性：外提不会改变程序语义
   • 可行性：外提后的计算在所有循环迭代中都执行
   • 无副作用：外提的计算没有副作用，或副作用可以安全外提

4. 代码外提的实现步骤：

   • 循环识别
   • 不变量检测
   • 外提条件检查
   • 代码变换
   • 代码清理

5. 数据流分析的应用：

   • 到达定值分析：确定变量值的可用性
   • 活跃变量分析：确定变量的使用情况
   • 循环不变性分析：确定表达式是否是循环不变的

6. 代码外提的局限性：

   • 无法外提有副作用的计算（如I/O操作）
   • 无法外提依赖于循环控制变量的计算
   • 无法外提可能抛出异常的计算（除非异常处理也能外提）

7. 代码外提的最佳实践：

   • 识别并外提复杂的循环不变计算
   • 考虑外提条件判断和整个表达式树
   • 与其他优化技术（如复写传播、死代码消除）结合使用

8. 实际应用中的挑战：

   • 准确识别循环不变计算
   • 处理复杂的控制流
   • 处理数组访问和指针操作
   • 确保外提的安全性和正确性

代码外提是一种简单但有效的循环优化技术，它可以显著提高循环密集型程序的性能。通过理解代码外提的原理和实现方法，我们可以编写更高效的代码，或者更好地理解编译器如何优化我们的代码。在实际编程中，我们也可以手动应用代码外提技术来优化关键循环，提高程序性能。