第181集：强度削弱

核心知识点讲解

什么是强度削弱？

强度削弱（Strength Reduction）是一种循环优化技术，它将循环中的昂贵操作替换为更便宜的操作，从而减少循环的执行时间。

这里的"强度"指的是操作的计算成本，强度削弱就是将高强度（计算成本高）的操作替换为低强度（计算成本低）的操作。

常见的强度削弱替换

归纳变量

强度削弱通常与归纳变量密切相关。归纳变量是其值在每次循环迭代中按照固定规则变化的变量。

归纳变量的类型

1. 基本归纳变量：直接由循环控制变量定义的变量，如 i 在 for (i = 0; i < n; i++) 中
2. 派生归纳变量：其值由基本归纳变量通过线性函数计算得到的变量，如 j = i * 2 中的 j

归纳变量的性质

• 线性关系：派生归纳变量与基本归纳变量之间存在线性关系，如 j = a * i + b
• 固定步长：每次循环迭代中，归纳变量的变化量是固定的
• 可预测性：归纳变量的值在编译时可以部分预测

强度削弱的工作原理

强度削弱的基本思想是：

1. 识别归纳变量：找到循环中的归纳变量，特别是派生归纳变量
2. 分析计算模式：分析归纳变量的计算模式，寻找可以替换的高强度操作
3. 替换操作：将高强度操作替换为低强度操作
4. 维护不变式：确保替换后的代码语义与原代码相同

强度削弱的实现步骤

1. 循环识别：识别程序中的循环结构
2. 归纳变量检测：检测循环中的基本归纳变量和派生归纳变量
3. 强度分析：分析派生归纳变量计算中的高强度操作
4. 替换操作：将高强度操作替换为低强度操作
5. 代码生成：生成优化后的代码

强度削弱的好处

1. 提高执行速度：低强度操作执行更快
2. 减少能耗：低强度操作消耗更少的CPU资源
3. 简化代码：替换后的代码通常更简单
4. 为其他优化创造机会：如归纳变量消除、循环展开等

实用案例分析

基本强度削弱示例

原始代码

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

优化分析

1. 识别归纳变量：
   • 基本归纳变量：i
   • 派生归纳变量：i * 4
2. 分析计算模式：i * 4 是一个乘法操作，每次迭代 i 增加 1，所以 i * 4 每次增加 4
3. 替换操作：将乘法替换为加法

优化后代码

for (int i = 0, j = 0; i < n; i++, j += 4) {
    a[i] = j;
}

复杂强度削弱示例

原始代码

for (int i = 0; i < n; i++) {
    a[i] = i * 2 + 5;
    b[i] = i * 2 + 10;
}

优化分析

1. 识别归纳变量：
   • 基本归纳变量：i
   • 派生归纳变量：i * 2 + 5 和 i * 2 + 10
2. 分析计算模式：两个派生归纳变量都基于 i * 2，可以共享这个计算
3. 替换操作：将乘法替换为加法，并共享计算结果

优化后代码

for (int i = 0, j = 0; i < n; i++, j += 2) {
    a[i] = j + 5;
    b[i] = j + 10;
}

数组访问的强度削弱

原始代码

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

优化分析

1. 识别归纳变量：
   • 基本归纳变量：i
   • 派生归纳变量：i * 2 和 i * 2 + 1
2. 分析计算模式：两个派生归纳变量都用于数组索引
3. 替换操作：将乘法替换为加法

优化后代码

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

嵌套循环的强度削弱

原始代码

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        a[i][j] = i * m + j;
    }
}

优化分析

1. 识别归纳变量：
   • 外层循环基本归纳变量：i
   • 内层循环基本归纳变量：j
   • 派生归纳变量：i * m + j
2. 分析计算模式：i * m 在每次外层循环迭代中是不变的，j 在每次内层循环迭代中增加 1
3. 替换操作：将乘法替换为加法，并将 i * m 外提到内层循环外

优化后代码

for (int i = 0; i < n; i++) {
    int base = i * m;
    for (int j = 0; j < m; j++) {
        a[i][j] = base + j;
    }
}

进一步优化（将 i * m 也进行强度削弱）：

int base = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        a[i][j] = base + j;
    }
    base += m;
}

代码实现

归纳变量检测

class InductionVariableDetector:
    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_basic_induction_variable(self, var, loop):
        """检查变量是否是基本归纳变量"""
        # 简化实现：检查变量是否在循环中以固定步长递增
        # 实际实现需要更复杂的分析
        for block in loop:
            for instr in self.cfg.get(block, []):
                if f"{var} = {var} +" in instr or f"{var} +=" in instr:
                    return True
        return False
    
    def _is_derived_induction_variable(self, var, loop, basic_ivs):
        """检查变量是否是派生归纳变量"""
        for block in loop:
            for instr in self.cfg.get(block, []):
                if f"{var} =" in instr:
                    # 检查是否是基本归纳变量的线性函数
                    _, right = instr.split('=', 1)
                    right = right.strip()
                    
                    # 检查是否包含基本归纳变量
                    uses = self._get_uses(instr)
                    for iv in basic_ivs:
                        if iv in uses:
                            # 检查是否是线性表达式
                            if '*' in right or '+' in right:
                                return True
        return False
    
    def detect_induction_variables(self, loop):
        """检测循环中的归纳变量"""
        # 收集循环中所有定义的变量
        all_defs = set()
        for block in loop:
            all_defs.update(self._get_defs(block))
        
        # 检测基本归纳变量
        basic_ivs = []
        for var in all_defs:
            if self._is_basic_induction_variable(var, loop):
                basic_ivs.append(var)
        
        # 检测派生归纳变量
        derived_ivs = []
        for var in all_defs:
            if var not in basic_ivs and self._is_derived_induction_variable(var, loop, basic_ivs):
                derived_ivs.append(var)
        
        return basic_ivs, derived_ivs

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

loop = {"B2", "B3"}

iv_detector = InductionVariableDetector(cfg)
basic_ivs, derived_ivs = iv_detector.detect_induction_variables(loop)

print("基本归纳变量:", basic_ivs)
print("派生归纳变量:", derived_ivs)

强度削弱实现

class StrengthReducer:
    def __init__(self, cfg):
        self.cfg = cfg
        self.iv_detector = InductionVariableDetector(cfg)
    
    def _find_strength_opportunities(self, loop, basic_ivs, derived_ivs):
        """寻找强度削弱的机会"""
        opportunities = []
        
        for block in loop:
            for instr in self.cfg.get(block, []):
                if '=' in instr:
                    left, right = instr.split('=', 1)
                    left = left.strip()
                    right = right.strip()
                    
                    # 检查是否是乘法操作
                    if '*' in right:
                        # 检查是否是归纳变量的乘法
                        uses = self.iv_detector._get_uses(instr)
                        for iv in basic_ivs:
                            if iv in uses:
                                # 提取乘法因子
                                factors = right.split('*')
                                for factor in factors:
                                    factor = factor.strip()
                                    if factor.isdigit():
                                        opportunities.append((block, instr, left, iv, int(factor)))
        
        return opportunities
    
    def reduce_strength(self, loop):
        """执行强度削弱"""
        # 检测归纳变量
        basic_ivs, derived_ivs = self.iv_detector.detect_induction_variables(loop)
        
        if not basic_ivs:
            return self.cfg
        
        # 寻找强度削弱机会
        opportunities = self._find_strength_opportunities(loop, basic_ivs, derived_ivs)
        
        if not opportunities:
            return self.cfg
        
        # 执行强度削弱
        optimized_cfg = self.cfg.copy()
        
        for block, instr, var, iv, factor in opportunities:
            # 创建新的变量来存储计算结果
            new_var = f"{var}_reduced"
            
            # 在循环入口处初始化新变量
            # 简化实现：假设B1是循环前的块
            if "B1" in optimized_cfg:
                # 查找iv的初始化值
                iv_init = None
                for init_instr in optimized_cfg["B1"]:
                    if f"{iv} =" in init_instr:
                        _, init_val = init_instr.split('=', 1)
                        iv_init = init_val.strip()
                        break
                
                if iv_init is not None:
                    # 添加新变量的初始化
                    optimized_cfg["B1"].append(f"{new_var} = {iv_init} * {factor}")
            
            # 替换原指令
            original_instrs = optimized_cfg.get(block, [])
            new_instrs = []
            
            for i in original_instrs:
                if i == instr:
                    # 替换为使用新变量
                    new_instrs.append(f"{var} = {new_var}")
                elif f"{iv} = {iv} +" in i or f"{iv} +=" in i:
                    # 在更新归纳变量的同时更新新变量
                    new_instrs.append(i)
                    new_instrs.append(f"{new_var} = {new_var} + {factor}")
                else:
                    new_instrs.append(i)
            
            optimized_cfg[block] = new_instrs
        
        return optimized_cfg

# 测试示例
reducer = StrengthReducer(cfg)
optimized_cfg = reducer.reduce_strength(loop)

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

高级强度削弱实现

class AdvancedStrengthReducer:
    def __init__(self, cfg):
        self.cfg = cfg
        self.iv_detector = InductionVariableDetector(cfg)
    
    def _analyze_linear_relation(self, var, loop, basic_ivs):
        """分析派生归纳变量与基本归纳变量之间的线性关系"""
        for block in loop:
            for instr in self.cfg.get(block, []):
                if f"{var} =" in instr:
                    _, right = instr.split('=', 1)
                    right = right.strip()
                    
                    # 分析线性关系：var = a * iv + b
                    a = 1
                    b = 0
                    iv = None
                    
                    # 简化实现：只处理简单的线性表达式
                    if '+' in right:
                        terms = right.split('+')
                        for term in terms:
                            term = term.strip()
                            if '*' in term:
                                # 处理乘法项
                                factors = term.split('*')
                                for factor in factors:
                                    factor = factor.strip()
                                    if factor.isdigit():
                                        a = int(factor)
                                    elif factor in basic_ivs:
                                        iv = factor
                            elif term.isdigit():
                                # 处理常数项
                                b = int(term)
                            elif term in basic_ivs:
                                # 处理基本归纳变量项
                                iv = term
                    elif '*' in right:
                        # 处理只有乘法的情况
                        factors = right.split('*')
                        for factor in factors:
                            factor = factor.strip()
                            if factor.isdigit():
                                a = int(factor)
                            elif factor in basic_ivs:
                                iv = factor
                    
                    if iv is not None:
                        return iv, a, b
        
        return None, 1, 0
    
    def reduce_strength(self, loop):
        """执行高级强度削弱"""
        # 检测归纳变量
        basic_ivs, derived_ivs = self.iv_detector.detect_induction_variables(loop)
        
        if not basic_ivs or not derived_ivs:
            return self.cfg
        
        # 分析每个派生归纳变量的线性关系
        optimized_cfg = self.cfg.copy()
        
        for var in derived_ivs:
            iv, a, b = self._analyze_linear_relation(var, loop, basic_ivs)
            
            if iv is not None:
                # 创建新的变量来存储计算结果
                new_var = f"{var}_reduced"
                
                # 在循环入口处初始化新变量
                if "B1" in optimized_cfg:
                    # 查找iv的初始化值
                    iv_init = 0
                    for init_instr in optimized_cfg["B1"]:
                        if f"{iv} =" in init_instr:
                            _, init_val = init_instr.split('=', 1)
                            iv_init = int(init_val.strip())
                            break
                    
                    # 添加新变量的初始化
                    initial_value = a * iv_init + b
                    optimized_cfg["B1"].append(f"{new_var} = {initial_value}")
                
                # 替换原指令并更新新变量
                for block in loop:
                    original_instrs = optimized_cfg.get(block, [])
                    new_instrs = []
                    
                    for i in original_instrs:
                        if f"{var} =" in i:
                            # 替换为使用新变量
                            new_instrs.append(f"{var} = {new_var}")
                        elif f"{iv} = {iv} +" in i or f"{iv} +=" in i:
                            # 在更新基本归纳变量的同时更新新变量
                            new_instrs.append(i)
                            # 提取步长
                            if "+=" in i:
                                _, step = i.split('+=', 1)
                                step = int(step.strip())
                            else:
                                step = 1
                            # 更新新变量
                            new_instrs.append(f"{new_var} = {new_var} + {a * step}")
                        else:
                            new_instrs.append(i)
                    
                    optimized_cfg[block] = new_instrs
        
        return optimized_cfg

# 测试示例
advanced_reducer = AdvancedStrengthReducer(cfg)
optimized_cfg = advanced_reducer.reduce_strength(loop)

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

技术要点总结

1. 强度削弱的核心：将循环中的高强度操作替换为低强度操作，减少计算成本

2. 常见的强度削弱替换：

   • 乘法 → 加法
   • 除法 → 右移（当除数是2的幂时）
   • 取模 → 位与（当模数是2的幂时）
   • 幂运算 → 乘法链

3. 归纳变量的重要性：

   • 基本归纳变量：直接由循环控制变量定义
   • 派生归纳变量：由基本归纳变量通过线性函数计算得到
   • 强度削弱主要针对派生归纳变量

4. 强度削弱的实现步骤：

   • 循环识别
   • 归纳变量检测
   • 强度分析
   • 操作替换
   • 代码生成

5. 强度削弱的应用场景：

   • 数组索引计算
   • 偏移量计算
   • 线性函数计算
   • 循环中的重复计算

6. 强度削弱与其他优化的结合：

   • 归纳变量消除：在强度削弱后，可以进一步消除冗余的归纳变量
   • 循环展开：强度削弱后的代码更适合循环展开
   • 代码外提：强度削弱可以与代码外提结合使用

7. 强度削弱的局限性：

   • 只能应用于具有固定模式的计算
   • 对于复杂的非线性计算效果有限
   • 可能会增加代码大小

8. 实际应用中的挑战：

   • 准确识别归纳变量
   • 分析复杂的计算模式
   • 处理嵌套循环
   • 确保优化的正确性

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