8 代码优化

约 5630 个字 83 行代码 预计阅读时间 20 分钟

1 流图

用于描述程序控制流程的工具

1.1 基本块 Basic Block

流图的基本单位

「基本块」是满足下列条件的 最大连续 三地址指令序列：

• 控制流只能从基本块的 第一个指令 进入该块 => 不存在跳转到基本块 中间/末尾 的指令
• 控制流在 离开 基本块前不会 跳转/停机 => 直至该块的最后一条指令

---

基本块划分算法

• 输入：三地址指令序列
• 输出：与输入序列对应的基本块列表（每条指令属于且仅属于一个基本块）

• 算法

  1. 确定指令序列中的「首指令 Leaders」，即基本块的第一条指令

     • 指令序列中的 首条三地址指令 是一个 Leader
     • 所有的 条件/无条件 跳转指令 的 目标指令 是一个 Leader
     • 紧跟 条件/无条件跳转指令 的 后一条 指令是一个 Leader（允许这条指令是跳转指令）

  2. 每个代码块对应了 From CurLeader To NextLeader（前闭后开）/ 指令序列结尾 之间的所有指令

1.2 流图 Flow Graph

啊其实就是流程图？

• 流图的节点是基本块
• 可能存在自循环边
• 当且仅当 \(C\) 的首条指令可能紧随 \(B\) 的最后一条指令执行时，存在边 \(B \rightarrow C\)
  • 此时，我们称：
    • B 是 C 的「前驱 Predecessor」
    • C 是 B 的「后继 Successor」
  • 这条边可能存在于以下两种情形
    • \(B \rightarrow C\) 的 条件/无条件 跳转语句
    • 按照原始的三地址指令序列，\(C\) 紧随 \(B\)，且 \(B\) 的结尾不存在跳转语句

2 常用代码优化方案

• 我们将代码优化分为以下几类：

  • 机器无关优化 —— 针对中间代码
  • 机器相关优化 —— 针对目标代码
  • 局部代码优化 —— 在单个基本块内进行优化
  • 全局代码优化 —— 面向多个基本块进行优化

• 常用代码优化方式包括以下几种：

  • 删除公共子表达式

    • 若表达式 X op Y 已经被计算过，且设计的变量值没有变化

      => 此次出现的 X op Y 称为「公共子表达式 Common Subexpression」

    • 这次就不用算哩 => 直接把这一行从代码里删去（使用首条表达式的结果进行改写）

    • 可能存在 局部/全局 的 公共子表达式

  • 删除无用代码

    • 「无用代码 Dead-Code」- 计算结果永远不会被调用的代码

    • 「复制传播」

      常用的公共子表达式删除算法（及其他优化算法）会引入一些形如 x = y 的赋值语句

      在执行完 x = y 后，我们应该尽可能使用 y 替换原本对于 x 的引用

      => 复制传播为删除无用代码提供了便利（复制语句本身可能冗余 -> 我们不再使用左侧的变量）

  • 常量合并 Constant Folding

    若在编译时刻推导出 一个表达式的值为常量，我们就可以用一个 const 对表达式进行替换（不用算哩）

  • 代码移动 Code Motion

    用于处理「循环不变计算 Loop-Invariant Computation」（无论循环多少次结果都不变的表达式）

    我们将这些表达式移出循环 => 在 进入代码前 就进行求值

    • 循环不变计算的相对性

      对于 多重嵌套循环，某给表达式可能对于当前循环不变，但对于更外层的循环迁移

      => 只能外移有限层

  • 强度削弱 Strengt Reduction

    我们使用较快的操作代替较慢的操作，如用 PLUS 替代 MUL

    • 循环中的强度削弱

      对于变量 \(X\) ，若存在常数 \(c\) 是的每次都是 \(X += c\) ，则称 \(X\) 为「归纳变量 Induction Variable」

      归纳变量可以通过在每次迭代中进行一次简单的 增量运算 实现

      // Init
      i = i + 1;
      t = 4 * i;
      // After
      i = i + 1;
      t = t + 4; // 加法比乘法简单
      // 同时需要在前一状态中追加 t 的初始化（本来依赖 i，现在靠自己）
      t = 4 * i; // => 只用算一次乘法
      

  • 删除归纳变量

    在循环中，若 一组归纳变量 的变化步调保持一致，可以删到只剩一个

    // Before j&t 每次变化 -1 的整数倍
    for() {
        j = j - 1;
        t1 = t1 - 4;
        i = i + 1;
        t2 = t2 + 4;        
    }
    if(j<=i) {};
    // After 删除当前状态中不使用的变量
    for() {
        t1 = t1 - 4;
        t2 = t2 + 4;
    }
    // 按比例替换后续状态中被删除的变量
    if(t1<=t2) {} // 按比例是 4*t1<=4*t2 约分一下
    

3 基本块优化

许多重要的局部优化技术都需要将 基本块 转换为「无环有向图 Directed Acyclic Graph」

3.1 基本块的 DAG 表示

块内的每一条语句 \(s\) 都对应了一个内部节点 \(N\)

• 语句节点 \(N\) 的标号为语句中的 运算符
• 定值变量表 （左侧变量）与节点 \(N\) 相关联，表示 \(s\) 为基本块内 最晚 对表中该变量进行赋值的语句
• \(N\) 的 childs 为本块中 处于 \(s\) 之前 · 最后一个 对 \(s\) 中涉及的运算分量进行赋值语句所对应的节点

• 若 \(s\) 中的某个运算分量在 \(s\) 之前尚未被赋值

  => 该分量对应的子节点即为代表该分量初值的 Leaf Node

  这种节点的变量标号需要加下标 0，表示初始化

• 若新构造节点的 定值变量表 曾出现在其他节点的依赖中，则对其他节点的依赖进行删除（变量只出现一次）

  对于以下两条三地址指令：

  b = a - d;
  d = a - d;
  

  显然在构建第二条指令时，已经存在重复结构 -> 直接在 \(b\) 所在的节点附加 \(d\)

  => 这一情况也表明该代码中存在 局部公共子表达式

• 若变量的值在编译过程中可以确定，如常量赋值 x = 3，我们就需要将同时记录 定值变量名 + 确定值 \(x = 3\)

3.2 基于基本块的 DAG 删除无用代码

• 从 DAG 中删除所有 没有 附加活跃变量（在基本块外没有被使用）的 根节点，既可以删除所有对应无用代码的节点。

• 根节点 表示在 本块内 该变量不是任何人的依赖

3.3 数组元素赋值指令的表示

如何防止系统将可能被更改的数组元素 a[i] 判定为公共子表达式

• 对形如 x = a[i] 的指令，我们记运算符为 =[] ，定值变量表为 a，子节点为 a, i

• 对形如 a[j] = x 的指令，我们记运算符为 []= ，定值变量表为 空，子节点为 a, j, y

  改节点的创建将 杀死 kill 所有 · 已经存在的 · 依赖于数组a 的节点（如前面创建的 =[]）

  => 被杀死 killed 的节点不会有定值变量，不会成为公共子表达式

3.4 基本块 DAG 信息推断

• 确定哪些变量的值在 被本基本块赋值前 被引用过

  => 创建了 Leaf Node 的变量

• 哪些语句的计算结果可以在 本块以外 被引用

  => 节点的定值变量从创建到构造结束一直没变的变量

3.5 根据 DAG 重组基本块

• 对于每个具有 若干定值变量 的节点，构造一个三地址语句以计算变量的值（大家值是一样的）

  • 我们倾向于将计算结果赋给在 基本块出口处活跃 的变量（缺少 全局活跃变量信息 的话，就假设除临时变量外的 所有人 在出口处活跃）

  • 若节点具有 多个活跃变量，就必须使用 复制语句 为 每个变量 赋正确的值

    如 \(x,y,z\) 是同一节点上的多个活跃变量，首先 \(x=res\)，紧接着 \(y = x,\ z = x\)

• 对于 记录了确定值 的变量，我们直接用定值对其进行替换

• 对于 被删除 的变量，我们使用同一节点中的保留者进行替换（是公共子表达式）

4 数据流分析 Data-Flow Analysis

数据流分析将每个 程序点 与 一个 数据流值 相关联，主要应用包括：

• 到达-定值 分析 Reaching-Definition Analysis
• 活跃变量 分析 Live-Variable Analysis
• 可用表达式 分析 Available- Expression Analysis

4.1 数据流分析模式

• 语句 的数据流模式

  • IN[s] 表示 语句 s 之前的数据流值
  • OUT[s] 表示 语句 s 之后的数据流值
  • \(f_S\) 表示 语句 s 的「传递函数 Transfer Function」，具有两种风格：
    • 信息沿执行路径传播 \(OUT[s]= f_s(IN[s])\)
    • 信息沿执行路径逆向传播 \(IN[s] = f_s(OUT[s])\)

  • 基本块内相邻语句的数据流传递关系

    假设 基本块 \(B = s_1,s_2,...,s_n\)，则 \(IN[s_{i+1} = OUT[s_i], i \in [1,n-1]\)

• 基本块 的数据流模式

  • IN[B] 表示 基本块 B 之前的数据流值，\(IN[B]=IN[s_1]\)
  • OUT[B] 表示 基本块 B 之后的数据流值，\(OUT[B]=OUT[s_n]\)

  • \(f_B\) 表示 基本块B 的传递函数，在前向传递过程中：

    \(OUT[B] = OUT[s_n] = f_{sn}(IN[s_n]) = ... = f_{sn}f{s(n-1)}...f_{s1}(IN[B])\)

5 到达定值分析

• 定值 Definition

  对于变量 \(x\)，定值 可以是一个 对 \(x\) 赋值的语句

• 到达定值 Reaching Definition

  若存在一条 From 紧跟在 \(x\) 的定值 \(d\) 后的点 To 某一程序点 \(p\) 的路径，且 \(d\) 在该路径上没有被 killed，则称 定值 \(d\) 到达程序点 \(p\)

  => 在 \(p\) 出使用的 \(x\) 可能 由 \(d\) 最后赋值

  • 我们为每个控制流图添加空基本块 ENTRY & EXIT，所有离开流程图的控制流都止于 EXIT

• 到达定值分析的主要用途

  • 检测 循环不变计算
  • 常量合并
  • 判定变量在该点是否 未经定值 就被引用

• 到达定值的传递函数

  • 对于 语句 - \(f_s\) - \(s:u=v+w\)

    \(f_s(x) = gen_s \cup (x-kill_s)\)

    • \(f_s(x)\) 即为语句 s 之后所有定值语句狗生的集合
    • \(gen_s\) 由语句 s 生成的定值语句集合，此处为 \(\{s\}\)
    • \(kill_s\) 由语句 s 杀死的定值语句集合，即程序中所有其他已存在的对 \(u\) 的定值语句

  • 对于 基本块 - \(f_B\)

    \[ \begin{align} &f_B(x) = gen_B \cup (x-kill_B)\\\\ &kill_B = kill_1 \cup kill_2 \cup ... \cup kill_n\\\\ &gen_B = gen_n \cup (gen_{n-1}-kill_n) \cup ... \cup (gen_1 - kill_n - kill_{n-1} - ... - kill_2) \end{align} \]
    • \(gen_B\) 就是基本块 B 中所有最后对一个变量赋值语句的集合
    • \(kill\) 的语句对象可以跨越基本块

5.1 到达定值的数据流方程

\[ \begin{align} &OUT[ENTRY] = \phi \tag{1}\\\\ &OUT[B] = gen_B \cup (IN[B]-kill_B),\ B \neq ENTRY\tag{2}\\\\ &IN[B] = \cup_{P为B的一个前驱}\ OUT[P],\ B \neq ENTRY\tag{3} \end{align} \]

我们可以通过以下的迭代算法计算 \(IN[B],\ OUT[B]\)：

// initialization
OUT[ENTRY] = {};
for(B !== ENTRY) OUT[B] = {};

// calculation
var flag = true; // 某个 OUT 发生了变化
while(flag) {
    flag = false;
    for(B !== ENTRY) {
        IN[B] = OUT[P1] + ... OUT[Pn]; // P 为 B 的前驱
        OUT[B] = genB + (IN[B] - killB);
        if(some OUT[B] changed) flag = true;
    }
}

5.2 引用-定值链 Use-Definition Chains

• UD Links 是一个 列表， 记录到达变量每一次引用所有到达定值
• 建立 UD Links
  • 若 基本块 B 中的 变量 a 在引用前存在定值，则存储 a 的 最后一次定值
  • 若 基本块 B 中的 变量 a 在 引用前不存在定值，则保存 \(IN[B]\) 中 所有 对于 a 的定值

6 活跃变量分析

• 活跃变量

  对于变量 \(x\) 与程序点 \(p\)，若在流图中沿着 从 \(p\) 开始的某条路径会引用 变量 \(x\) 在 \(p\) 处的值，则称 变量 \(x\) 在 \(p\) 处是「活跃 live」的；否则称其在 \(p\) 出「不活跃 dead」

  => 在后面还会用到此处为变量赋的值

• 活跃变量信息的用途

  • 删除无用赋值

    => 本处赋值在本块的后续、出口后的其他块中均不被使用

  • 为基本块分配寄存器

    • 若所有寄存器都被占用，则清理存储 dead 变量的寄存器
    • 若在基本块结束时，不需要保存 dead 状态的变量

• 活跃变量的传递函数 \(f_B\)

  这是一个「逆向数据流」问题 => 考虑会不会在之后被使用 \(IN[B] = f_B(OUT[B]\))

  \(f_B(x) = use_B \cup (x-def_B)\)

  • \(x\) 在 B 出口处的 活跃变量 集合

  • \(def_B\) 在 B 中被赋值，但 定值前 在 B 中 没有被引用 的变量集合

    在 B 中首次被定义（等式左侧） => 在 入口处 一定不活跃

  • \(use_B\) 在 B 中被引用，但 引用前 在 B 中 没有被定值 的变量集合

    在 B 中没有定义却直接使用（等式右侧），一定是前面传来的 => 入口处活跃

6.1 活跃变量数据流方程

\[ \begin{align} &IN[EXIT] = \phi \\\\ &IN[B] = use_B \cup (OUT[B]-def_B),\ B \neq EXIT\\\\ &OUT[B] = \cup_{S为B的后继}\ IN[S],\ B \neq EXIT \end{align} \]

迭代算法如下：

IN[EXIT] = null;
for(B !== EXIT) IN[B] = {};

while(某个 IN 变化) {
    for(B !== EXIT) {
        OUT[B] = IN[S1] + ... + IN[Sn]; // S是B的后继
        IN[B] = useB + (OUT[B] - defB);
    }
}

6.2 定值-引用链 Definition-Use Chains

• 假设变量 \(x\) 有一的定值 \(d\)，该定值能够到达的所有引用的集合被称为 \(x\) 在 \(d\) 处的「定值-引用链 DU Chain」

• 在求解活跃变量数据流方程的 \(OUT[B]\) 时，将其表示为 从 B 的末尾能够到达的的引用集合，就可以根据这些信息计算 B 中每个变量在其定值处的 DU 链

  • 若 B 中先后存在两个对 变量\(x\) 定值的语句 \(d,d'\)，则 之间所有对 \(x\) 的引用都是 \(d\) 的 DU 链

    d: x = val1;
        ...
       ? = x + ...; => d 的 DU 链
        ...
    d': x = val2;
    

  • 若 \(d\) 为 B 中最后对 \(x\) 定值的语句，则 \(d\) 的 DU 链 = B中其后所有对 \(x\) 的引用 + \(OUT[B]\) 中所有对 \(x\) 的引用

7 可用表达式分析

• 从流图的 首节点 到某一程序点 \(p\) 的 所有路径 都对表达式 \(x \ op \ y\) 进行了计算，且最后一次计算到点 \(p\) 之间不涉及 \(x,\ y\) 的修改，则称 \(x\ op\ y\) 在 \(p\) 处「可用 available」

  => 之前的计算结果有效，不用再算一遍了

• 主要用途

  • 消除 全局 公共子表达式

  • 进行 复制传播

    对于复制语句 x=y 可以使用 \(y\) 替代 \(x\) 的条件为：

    从流图的 首节点 到达该程序点的 每条路径 都存在复制语句 x=y，且从最后一次复制到该程序点之间 没有再次 对 \(x,\ y\) 进行赋值

7.1 可用表达式的传递函数

• 若基本块 B 对依赖变量 \(x,\ y\) 重新赋值，并且没有重新计算 \(x\ op\ y\)，则称 B 杀死该表达式
• 若基本块 B 对 \(x\ op\ y\) 进行计算，且没有更改其依赖，则称 B 生成该表达式
• 传递函数 \(f_B(x) = e-gen_B \cup (x - e-kill_B)\)
  • \(e-gen_B\) 基本块 B 生成的表达式集合，计算方法如下：
    1. 初始化 \(e-gen_B = \phi\)
    2. 扫描基本块中的每个 z = x op y
       • 将 x op y 加入 \(e-gen_B\)
       • 从 \(e-gen_B\) 中删除与 z 相关的表达式
  • \(e-kill_B\) 基本块 B 杀死的表达式集合（杀死对象是所有块组成的全集），计算方法如下：
    1. 初始化 \(e-kill_B = \phi\)
    2. 扫描基本块中的每个 z = x op y
       • 从 \(e-kill_B\) 中删除与 x op y
       • 将所有与 z 相关的表达式加入 \(e-kill_B\)

7.2 可用表达式的数据流方程

\[ \begin{align} &OUT[ENTRY] = \phi\\\\ &OUT[B] = f_B(IN[B])\\\\ &f_B(x) = e\_gen_B \cup (x-e\_kill_B)\\\\ &IN[B] = \cap_{P是B的前驱}\ OUT[P] \end{align} \]

迭代算法如下：

OUT[ENTRY] = null;
// 初始化为 空集 局限性很大（交集一直为 empty）
for(B !== ENTRY) OUT[B] = U;

while(OUT changed) {
    for(B !== ENTRY) {
        IN[B] = intersection(OUT[Pi]);
        OUT[B] = eGenB + (IN[B] - eKillB);
    }
}

8 支配节点与回边

• 支配节点 Dominators

  若从流图的入口节点到某一节点 \(n\) 的 每条路径 都经过节点 \(d\)，则称 \(d dominate n\)，记为 \(d \ dom \ n\)

  • 每个节点都支配本身

  • 入口节点支配所有节点

  • 我们可以用 支配节点数 Dominator Tree 表达节点间的支配关系：每个节点支配包括自己在内的所有后代节点

• 直接支配节点 Immediate Dominator

  从入口节点到 curNode 的 所有 路径上，与其相连的最后一个支配节点

8.1 支配节点的数据流方程

• \(IN[B]\) 为基本块入口处的支配节点集合，\(OUT[B]\) 为出口处的支配节点集合

方程组如下： $$ \begin{align} &OUT[ENTRY] = {ENTRY}\\ &OUT[B] = IN[B] \cup {B},\ B \neq ENTRY\\ &IN[B] = \cap_{P是B的前驱}\ OUT[P] \end{align} $$

可以通过以下迭代算法进行求解：

OUT[ENTRY] = {ENTRY};
for(B !== ENTRY) OUT[B] = N;

while(OUT changed) {
    for(B !== ENTRY) {
        IN[B] = interception(OUT[Pi]);
        OUT[B] = IN[B] + {B};
    }
}

8.2 回边 Back Edge

用于识别自然循环

• 对于流图中的两个节点 \(d,\ n\) 满足关系 \(d \ dom \ n\)。若存在有向边 \(n \rightarrow d\)，则称为「回边 Back Edge」

8.3 自然循环 Natrual Loop

• 具有唯一的入口节点 header，支配循环中的所有节点
• 循环中至少有一条 返回 header 的路径
• 「性质」除非两个自然循环的 header 相同，否则 互斥/完全包含
  • 我们将不包含其他循环的循环称为「最内循环 Innermost Loop」
• 对于具有 相同 header 的两个循环，我们难以确定哪个是最内循环 => 直接合并

---

自然循环可以通过以下方法进行识别：

• 给定回边 \(n \rightarrow d\)，其自然循环为 \(d\) + 所有不经 \(d\) 到达 \(n\) 的节点 + \(n\) 本身（\(d\) 为循环的 header）

• 一般步骤

  1. 加入 \(n,\ d\)
  2. 加入所有直接到达 \(n\) 的节点 \(x\)
  3. 加上所有 \(x\) 的 直接前驱（是 \(n\) 就停止）
  4. 递归

• 构造某条回边所在自然循环的算法

  stack = [];
  loop = {n, d};
  stack.push(n); // 不用考虑 d 的前驱
  
  while(stack != empty) {
      m = stack.top();
      stack.pop();
      for(m 的 所有前驱) {
          if(p is NOT in loop) {
              loop += {p};
              stack.push(p);
          }
      }
  }
  

9 删除全局公共子表达式

我们可以使用 可用表达式 来判断点 \(p\) 处的表达式是否为 全局公共子表达式

我们查看以下情形：

// 部分代码
1: a = x + y;
2: b = x + y;
3: c = x + y;
// 前后继关系
a   b
 \ /
  c

=> 单独以 \(a,\ b\) 替换 \(c\) 都是不合适的 => 我们不知道具体会走哪条路径

---

下面是一个正确的替换方法 => 使用第三方 \(u\)

// code
1: u = x + y;
   a = u;
2: u = x + y;
   b = u;
3: c = u;

---

9.1 删除算法

• 输入：带有可用表达式信息的 Flow Graph
• 输出：修正后的 Flow Graph

对于语句 \(s:z=x\ op\ y\)，若 \(x\ op\ y\) 在 \(s\) 之前 可用，则执行如下步骤： 1. 从 \(s\) 开始 逆向 搜索，但不 穿过 任何计算了 \(x\ op\ y\) 的块

 => 找到 *所有 · 最近的 · 计算了* $x\ op\ y$ 的语句

1. 建立临时变量 \(u\)

2. 将所有在 Step 1 中找到的所有语句 \(w = x\ op\ y\) 使用以下语句组替代：

   u = x op y;
   w = x;
   

3. 替换 \(s\) 为 \(z=u\)

10 删除复制语句

我们查看以下例子：

           x = y        x = y+1
          /     \       /
  t1 = x*2      t2 = x*3
 支持复制传播    不支持复制传播

-> 因为不是所有的 subNode 都可以进行复制传播，\(x= y\) 不可删除

10.1 删除算法

• 输入：流图 G，DU 链，个基本块入口处的 可用复制语句 集合
• 输出：修改后的流图 G‘

对于每个复制语句 \(x=y\) ： 1. 根据 DU 链找出该定值语句所能到达的对于 \(x\) 的引用 2. 确定对于每个引用所在的 B' ，\(IN[B]\) 是否都包含了 \(x=y\)，B‘ 的该引用前没有重新对 \(x,\ y\) 进行赋值 3. 若满足 Step 2，删除原本的 \(x=y\)，对于 Step 1 中找到的引用都适用 \(y\) 进行替换

11 代码移动

11.1 检测循环不变计算

• 输入：循环 L，每个三地址指令的 UD 链

• 输出：L 的循环不变计算语句

• 将 运算分量 为 常数 / 所有定值点都在L外部 的语句标记为“不变”

• 将 先前未被标记，且 运算分量 为 常数 / 所有定值点都在L外部 / 只有一个到达定值且为L中已经标为“不变” 的语句标记为“不变”
• 循环执行 Step 2 直至不出现新的“不变”语句

11.2 代码外提

• 前置首节点 preHeader
  • 循环不变计算将被提前至原本 header 之前一个称为 preHeader 的 new Block 中
  • preHeader 的 唯一后继 为原本的 header，并且代理了原本所有从循环外进入 header 的路径（内部到达 header 的路径不变）
• 循环不变计算语句 \(s:x=y+z\) 移动条件
  • 语句所在的 Block 是 L 的 所有出口节点 的 支配节点
  • 循环中 没有其他语句 对其变量 \(x\) 进行赋值
  • 循环中 所有 对 \(x\) 的引用 仅 由 \(s\) 到达
• 算法
  1. 寻找 循环不变计算
  2. 对于 Step 1 中找到的每一条语句，检查是否符合上述条件
  3. 按照书写顺序，将所有循环不变语句移动至 preHeader（若其计算分量的定值点在循环体内，则只有可以一同外提的时候才能拎出来）

12 作用于归纳变量的强度削弱

• 对于变量 \(x\)，若存在常量 \(c\) ，是的每次 \(x\) 的操作都满足 \(x += c\)，则称 \(x\) 为归纳变量
• 若循环 L 中的变量 \(i\) 形如 \(i=i+c\)，则称 \(i\) 为 L 的 基本归纳变量

• 若 \(j=c*i+d\) 且 \(i\) 为基本归纳变量，则 \(j\) 为 属于 \(i\) 族的归纳变量

  我们认为与变量 \(j\) 关联的三元组为 \((i,c,d)\)

12.1 归纳变量检测算法

1. 扫描循环 L 的语句，找出所有的 基本归纳变量，与其关联的三元组为 \((id,1,0)\)
2. 寻找循环中 只有一次定值 的变量 \(k\)，具有形式 \(k=c'*j+d'\)，\(j\) 为 基本/非基本归纳变量
   • 基本归纳变量 => \(k \in i\)，三元组为 \((j,c',d')\)
   • 非基本归纳变量 => 假设 \(k\in i\)
     • 循环 L 中对 \(j\) 的 唯一定值 & 对 \(k\) 的唯一定值之间，没有 对 \(i\) 定值
     • 循环 L 外 没有 \(j\) 的定值可以到达 \(k\)

12.2 强度削弱算法

对于每个 基本归纳变量 \(i\)，对于族中的每个归纳变量 \(j:(i,c,d)\) ： 1. 建立临时变量 \(t\) => 具有相同三元组的族裔可以共用一个 2. 使用 \(j=t\) 替换 \(j=c*i+d\) 3. 在紧跟定值 \(i = i+n\) 处添加 \(t=t+c*n\) 4. 将 \(t:(i,c,d)\) 加入 \(i\) 族 5. 在 preHead 末尾追加 \(t=c*i,\ t = t+d\)，使得循环开始时 \(t=c*i+d = j\)

12.3 删除归纳变量

• 对于引入的 \(j=t\) ，若可以在归纳变量 \(j\) 的 所有引用点 用 \(t\) 进行替换，且 \(j\) 在 L 的出口处不活跃，则可以删除语句 \(j=t\)

12.4 删除仅用于测试的归纳变量

• 完成 强度削弱 后，部分归纳变量仅用于测试。若可以使用对其他归纳变量的测试替代，则可以删除该归纳变量。
• 对于用于测试的基本归纳变量 \(i\) ，取其某个族裔 \(j\)（让两个常数尽可能简单），使用对 \(j\) 的测试替换对 \(i\) 的测试，即 \(relop\ i \ x \ B \rightarrow relop \ j\ c*x+d\ B\)
• 对于 \(relop \ i_1\ i_2\ B\)，若能找到两族族裔 \(j_1:(i_1,c,d),\ j_2:(i_2,c,d)\)，则可以替换为 \(relop\ (j_1,\ j_2,\ B),\ c > 0\)