第2章
IR基础知识

目前流行的编译器通常采用三段式设计，分为前端、中端和后端，编译器的典型架构如图2-1所示。

前端 ：对程序进行解析，确保程序符合语言规定的词法、语法、语义规则。前端完成后通常将程序变换成另一种表示，这种新的表示一般更便于进行编译优化或者目标代码生成。

中端 ：目的是对程序进行优化。为了便于进行优化，通常使用IR来描述程序，不同的语言可以翻译成统一的IR，这样针对IR进行的优化可以做到语言无关。中端常见的优化有常量传播（Constant Propagation，CP）、死代码消除（Dead Code Elimination，DCE）、循环不变代码外提（Loop Invariant Code Motion，LICM）、循环展开（Loop Unrolling，LU）等。

后端 ：目的是将程序翻译成目标机器可以识别的机器码。后端的工作通常包括指令选择、指令调度、寄存器分配和机器码生成。

注意

通常我们提到的优化都是指语言无关、架构无关的编译优化，但现实中也存在一些语言相关、架构相关的优化技术，这些优化技术都是对特定问题的分析和解决，不在本书的讨论范围内。

IR是编译优化的基础，本章将主要讨论IR相关知识。

2.1 IR分类

在编译器的实现中，不同的阶段会根据不同的目的使用不同的IR表示，常见的IR分类如下。

2.1.1 树IR

最典型的树IR就是AST（Abstract Syntax Tree，抽象语法树）。AST通常在编译器前端实现中使用，主要原因是高级语言的语法通常都使用上下文无关的文法。使用AST不但可以简单、直接地表达源程序的语法，还可以使用属性文法对原程序进行翻译，以生成供中端使用的IR。例如Clang中就是使用AST对源程序进行分析，以代码清单2-1中的add源码（整型加法）为例来看看Clang生成的AST。

代码清单2-1 源码add（2-1.c）

使用Clang 进行编译，编译命令为clang -cc1 -ast-dump 2-1.c，获得的AST如图2-2所示。

在图2-2中，整个函数是一个复合节点（CompoundStmt），该节点包含了return语句的节点（ReturnStmt）。而return节点又是由一个二元操作节点构成（add是二元操作的一种类型）的，二元操作节点包含了两个表达式（都是DeclRefExpr）。AST形式是非常自然的表达形式，它可以通过文法解析得到。

2.1.2 线性IR

线性IR使用如三元组、四元组或者自定义的IR描述。

LLVM中端使用的LLVM IR是一种线性IR，编译优化都是基于LLVM IR的。使用Clang编译代码清单2-1可以获得线性IR，编译命令为clang -S -emit-llvm 2-1.c -o 2-2.ll，对应的IR如代码清单2-2所示。

代码清单2-2 代码清单2-1对应的IR（2-2.ll）

线性IR的表达能力非常完备，每一条IR语句都完成一个简单的功能，例如对上述IR功能的解析如代码清单2-3所示。

代码清单2-3 代码清单2-1对应的IR解析

2.1.3 图IR

图IR使用图表示源程序，由于通过图可以较为方便地得到程序的控制流，这将有利于编译优化过程。CFG（Control Flow Graph，控制流图）就是典型的图IR。在某些编译器中还有一些其他的图IR表示，例如JVM的C2编译器、V8的TurboFan编译器都采用sea-of-node的图IR。图2-3展示了一个while循环对应的CFG。

假设有一个示例函数factor，用于计算n的阶乘，其源码如代码清单2-4所示。

代码清单2-4 阶乘运算示例源码factor

利用Clang生成LLVM IR，然后利用opt 工具生成CFG。其对应的CFG示意图和对应的基本块（基本块将在2.2.1节介绍）如图2-4所示。

注意

LLVM项目中主要使用线性IR和图IR。LLVM的中端主要基于线性IR实现语义的表达，优化过程中很多优化会基于CFG进行。LLVM的后端使用图IR和线性IR，例如在指令选择时使用图IR，而在寄存器分配、代码生成时会将图IR变换成线性IR，相关内容将在后续章节进一步介绍。

同一类型的IR在实现时也存在不同的实现方式，例如对线性IR采用静态单赋值形式能大大简化编译器的实现。现代主流的编译器基本上都是基于CFG和静态单赋值。2.2节和2.3节将分别介绍CFG和静态单赋值的相关概念。

注意

为什么存在这么多IR？主要原因是不同IR的抽象程度不同，而且实现不同，同时IR对优化算法的实现有很大的影响。所以在实际使用中会根据不同的需求选择不同的IR。

2.2 CFG的基本块与构建

CFG使用图的方式来描述程序的执行，为了简化描述，CFG引入了基本块（Basic Block，BB）的概念。首先把代码划分成基本块，基本块作为CFG的节点，CFG中的边描述了基本块之间的执行顺序。

2.2.1 基本块

基本块是一段最长连续执行的指令序列，且满足以下条件。

1）只能从第一行指令开始执行（保证指令序列只有一个入口）。

2）除最后一条指令外，指令序列中不包含分支、跳转、终止指令（保证指令序列只有一个出口）。

基本块内的代码总是从基本块入口开始顺序执行，直到在基本块出口结束，中间不会跳到别的代码段或者从别的代码跳进来。这意味着，基本块中的第一条指令被执行后，基本块中的其余指令必然按顺序执行一次。

通常基本块会基于IR进行划分，主要原因是高级语言中一行代码包含的信息比较多，需要将高级语言转化为IR后再划分基本块。

CFG的生成包含两步：识别基本块、建立基本块之间的关联。

1）识别基本块的关键在于识别基本块的leader指令，符合以下三种情况之一的指令可以成为leader。

①指令序列的第一行是leader。

②任何条件或者非条件跳转指令的目标行指令是leader。

③任意条件或者非条件跳指令的下一行指令是leader。

2）定义基本块边界。定义基本块边界的规则如下。

①leader是基本块的一部分。

②leader到下一个leader之间的指令序列构成基本块。

基本块之间的关联非常简单，反映了基本块之间的执行顺序。当一个基本块跳转到另一个基本块时，即这两个基本块之间存在关联。

根据基本块的定义，当遇到以下指令时会产生一个 新的基本块 。

1）过程和函数入口点。

2）跳转或分支的目标指令。

3）条件分支之后的“直通”（fallthrough）指令。

4）引发异常的指令之后的指令。

5）异常处理程序的起始指令。

而一个基本块的 结束指令 可能是：

1）直接和间接的无条件和条件分支指令。

2）可能引发异常的指令。

3）返回指令（return）。

4）如果函数调用不能返回，用于抛出异常的函数或特殊调用指令，如C中的longjmp和exit。

注意

调用指令本身不是基本块的开始或者结束指令，它应该包含在基本块中。调用指令执行结束后会继续执行下一条指令，通常认为它并不改变控制流，所以认为它不是基本块的边界指令。

2.2.2 构建CFG

当确定基本块之后，再构造CFG就显得容易多了。CFG是一个有向图：它以基本块作为节点，如果一个基本块A执行完之后，可以跳转到另一个基本块B，则图中包含从A节点到B节点的有向边，CFG图描述了程序控制流的所有可能执行路径，具体的构建方法如下。

1）如果当前基本块以分支指令结尾，则在当前基本块与所跳转到的目标基本块之间加入一条有向边。

2）如果当前基本块以条件分支指令结尾，则在当前基本块以及跳转条件成立、不成立的目标基本块之间分别加入一条有向边（共两条边）。

3）如果当前基本块以返回指令结尾，则不需要加入新的边。

4）如果当前基本块不是以跳转指令结束，则在当前基本块和相邻的后继基本块之间加入一条有向边。

在所有的基本块都扫描完毕后，CFG就建立完成了。

2.3 静态单赋值

SSA（Static Single Assignment，静态单赋值）是三位研究员在1988年提出的一种IR ，它是目前编译优化中使用最广泛的技术，在LLVM代码生成中经过指令选择后的IR为SSA形式，基于SSA有不少相关的编译优化，在寄存器分配时先析构SSA再完成寄存器分配。正如SSA的名字所示，它有以下特点。

1） 静态 ：对代码进行静态分析，不需要考虑代码动态的执行情况。

2） 单赋值 ：每个变量名只被赋值一次。

2.3.1 基本概念

首先来探讨单赋值这个概念，代码清单2-5所示是一段C代码，为了描述方便，在每一条语句之前增加了编号，形如“1:”表示语句1。

代码清单2-5 单赋值示例代码

在这个代码片段中，变量x被定义/赋值两次（语句1和语句3），不符合变量单次赋值的要求。为了让代码的形式满足SSA形式，需要引入变换，对多次赋值的变量进行重命名，例如在语句3中引入一个新的变量t，后续所有使用x的语句都修改为使用变量t。在SSA的变换中，为了更形象地描述x和t之间是变量重命名的关系，通常是为变量引入版本信息（通过下标来描述版本），例如语句1和语句2中的x替换为x ₁ ，语句3和语句4中的x替换为x ₂ ，以保证语义的正确性（为什么引入版本信息，而不是使用完全无关的变量，主要是方便SSA构造，参见2.3.2节），对应的SSA形式如代码清单2-6所示。

代码清单2-6 SSA示例代码

SSA的形式看起来比较简单，但是引入了重命名的变量会带来新的问题，主要是变量汇聚问题。下面通过代码清单2-7所示的示例来介绍变量汇聚问题。

代码清单2-7 带变量汇聚的单赋值示例代码

在这个代码片段中，变量y在语句1、语句3和语句5中共被赋值3次，按照变量重命名的规则，使用3个变量y ₁ 、y ₂ 和y ₃ 对这3次赋值进行替换，可得到代码清单2-8所示的代码：

代码清单2-8 带变量汇聚的SSA示例代码

但是语句7则有新的问题，此处y的值既可能是y ₂ 也可能是y ₃ （取决于分支的执行路径），所以需要引入一个新的表达方式将y ₂ 和y ₃ 重新汇聚为一个变量——这个方式就是引入φ（Phi）函数。φ函数本质上是一个选择操作，指从不同的执行路径中选择执行结果，例如当if语句执行时φ函数的结果为y ₂ ，当else语句执行时φ函数的结果为y ₃ 。语句7的φ函数表示如代码清单2-9所示。

代码清单2-9 φ函数表示

这里定义一个新的变量y ₄ 表示φ函数的结果，那么语句7中的y则可以替换为y ₄ ，结果如代码清单2-10所示。

代码清单2-10 使用y ₄ 表示φ函数结果

实际上，汇聚信息通过CFG更容易被描述，CFG中的交叉点就是汇聚点。例如，代码清单2-10对应的CFG如图2-5所示，在图中汇聚点可引入φ函数。

下面讨论SSA中的 静态 含义，例如循环中定义的变量也只考虑一次赋值，而不考虑循环的动态执行情况。考虑一个C代码片段，如代码清单2-11所示。

代码清单2-11 静态SSA示例源码

在代码清单2-11中，变量x在语句1和语句5中一共被赋值两次，变量y在语句2和语句4中一共被赋值两次，所以需要对变量x和变量y进行重命名。但是根据该例中的循环条件，语句4和语句5在循环内部，两个语句会被执行10次，但是在SSA的表达中并不考虑循环实际执行的次数，只需要考虑程序的静态结构并确定重命名变量。因为该程序片段也存在汇聚点，所以需要插入φ函数。代码清单2-11插入φ函数后的SSA形式CFG描述示意如图2-6所示。

引入SSA形式的目的在于简化编译器的实现，每个变量名只对应一次赋值操作，在变量使用的地方要查看变量定义信息，可以直接通过IR得到。这意味着变量的Use-Def（使用-定义） 关系在IR中是显式提供的，不需要额外的IR结构来表示这一关系。这种形式使得IR结构变简单，将有利于编译器的实现。（特别是需要使用Use-Def关系的场景，将可以直接获取到这一信息。）

引入φ函数后，SSA的表达能力就完备了（可以描述所有的功能），但通常硬件并没有相应的指令描述φ函数，所以引入φ函数后还需要在编译结束阶段（通常是指令生成阶段）将φ函数消除。另外，φ函数有自己的特点，在编译优化时会引入新的问题，2.3.3节将会进一步讨论。

由此可以总结使用SSA涉及的三种处理。

1）识别多次定义的变量，将其进行重命名。

2）在汇聚点插入φ函数。

3）在指令生成阶段将φ函数消除。

前两种处理用于构造SSA，后一种处理是析构SSA，2.3.2节和2.3.3节将分别讨论相关内容。

2.3.2 SSA构造

SSA的构造涉及两步：变量重命名和插入φ函数。在代码清单2-10所示的例子中可以发现，插入φ函数后会增加新的变量定义（见图2-5，在插入φ函数后引入变量y，用于保存φ函数的结果），所以插入φ函数后需要执行变量重命名（如将y重命名为y ₄ ），因此SSA构造算法可以调整为先插入φ函数再执行变量重命名。

而插入φ函数需要找到变量的汇聚点，典型方法是通过支配边界来计算。因为支配边界指的是变量的汇聚点，所以只需要在支配边界处插入φ函数即可（具体参见第4章）。由此SSA构造算法可以分解为4步。

1）遍历程序构造CFG（参见2.2.2节）。

2）计算支配边界。

3）根据每一个基本块（记为b）的支配边界（记为DF(b)）确定φ函数的位置。DF(b)是基本块b所定义变量的汇聚点集合，对于基本块b定义的每一个变量在DF(b)中都放置着一个φ函数。注意，因为φ函数对变量进行了一次新的定义，所以在插入φ函数后可能会出现因引入了新的变量定义，而需要插入额外φ函数的情况。

4）变量重命名，并将后续使用原变量的地方修改为使用新的变量，通常可以采用栈的方式来更新后续变量的引用。

注意

在上述SSA构造算法中，为了保证放置φ函数的代价最小，需要计算支配树和支配边界，根据支配边界放置φ函数，然后对变量进行重命名（如果要避免死φ函数，需要执行活性分析或者死代码消除），因此执行成本比较高。Braun等人优化了SSA构造算法，在2013年提出了快速、高效构造SSA的算法。本质上，前面介绍的算法是沿着CFG前向进行操作的，即算法首先收集变量所有的定义，然后计算放置φ函数的位置。而Braun等提出的算法认为可以对CFG进行逆向操作，只有在使用变量时才去处理所有涉及的定义点，更多内容参考具体论文“Simple and Efficient Construction of Static Single Assignment Form” 。

2.3.3 SSA析构

SSA析构是指将SSA中的φ函数消除。从直觉上讲，SSA析构似乎比较简单，以图2-7a为例，通过赋值进行φ函数消除。

本质上，消除φ函数的思路是将φ函数上移到前驱基本块中，并直接使用赋值语句消除φ函数。该方法也称为朴素（naive）算法。例如，将图2-7a中基本块4的φ函数y ₄ =φ(y ₂ ,y ₃ )分别复制到基本块2和基本块3的最后，同时分别使用赋值语句更新y ₄ 的值：在基本块2中使用y ₂ 更新y ₄ ，在基本块3中使用y ₃ 更新y ₄ ，如图2-7b所示。然后，通过复制传播优化消除冗余赋值，可以得到图2-7c所示的结果。但是这样的消除方法在某些场景是不正确的，可能会引入Lost Copy问题和Swap问题。

1.Lost Copy问题及解决方法

接下来以代码清单2-12为例说明Lost Copy问题。

代码清单2-12 Lost Copy问题示例代码

图2-8a是针对上述代码构建的CFG图。对图2-8a进行复制传播优化，可以发现：基本块2中的t=i ₂ 是冗余指令，是可以被删除的，得到优化后的CFG如图2-8b所示。按照消除φ函数的方法，分别将i ₂ =φ(i ₁ ,i ₃ )分别复制到基本块1和基本块2的最后，同时分别使用赋值语句更新i ₂ 的值，在基本块1中使用i ₁ 更新i ₂ ，在基本块2中使用i ₃ 更新i ₂ ，此时得到的析构图如图2-8c所示。

但是此时程序的 正确性 发生了变化，计算得到y的结果和原始程序不同：原来程序y的值为10，消除φ函数后y的值为11。导致这一结果的主要原因是变量的作用域发生了变化。在原始的CFG中变量i ₁ 的作用域为基本块1，变量i ₂ 的作用域为基本块2、3，在消除φ函数后i ₂ 的作用域为基本块1、2、3。

该问题称为Lost Copy问题，解决的方法有两种：一种是引入 关键边 的概念，通过对关键边的拆分来解决该问题；另一种是通过 变量冲突 解决该问题。首先来看如何通过关键边的拆分解决该问题。SSA析构Lost Copy问题的思路的示意如图2-9所示。

先来介绍关键边的概念。关键边指的是CFG中边的源节点有多个后继节点，边的目的节点有多个前驱节点。例如，图2-9a中基本块2的true边对应的源节点是基本块2。基本块2有两个后继节点：基本块2和基本块3。true边的目的节点仍然是基本块2，基本块2有两个前驱节点：基本块1和基本块2。所以true边是关键边，解决这个问题的方法是拆分关键边，即引入一个新的基本块，这样就不存在关键边，如图2-9b所示。

引入关键边后再消除φ函数，可以得到如图2-9c所示的结果，该结果是正确的。

注意

关键边的作用除了在SSA析构中使用外，在部分冗余消除中也有使用。根本原因是消除部分冗余后，也可能会扩大变量（或者表达式）的作用域，而通过关键边的拆分可以解决这一问题 。关于部分冗余消除的知识可以参考其他编译优化相关的书籍。

2.Swap问题及解决方法

除了Lost Copy问题外，SSA析构时还可能出现Swap问题。Swap问题是指，当一个基本块存在多个变量的汇聚时，需要为每个变量插入一个φ函数，从而导致存在多个φ函数位于基本块的最前面的情况。但是多个φ函数之间应该按照什么样的顺序放置和执行呢？

直观上看，多个φ函数放在同一个基本块中，会按照其放置顺序依次执行。但该如何确定φ函数的放置顺序？这涉及φ函数的一个重要特性： φ函数本身蕴含了并行性 ，即多个φ函数都应该在基本块的入口处 同时 被处理完成，因为后续的语句可能同时访问所有φ函数定义的变量。但是CPU只能顺序执行一个基本块中的多个φ函数语句，这意味着在编译时需要将并行执行的φ函数串行化，同时保证并行化的语义，否则将导致正确性出现问题。例如，当多个φ函数定义的变量有依赖时（如两个φ函数定义的变量相互引用），并行φ函数的执行结果并不依赖于φ函数定义的顺序，但串行执行时φ函数定义的顺序将影响结果，因此串行执行SSA析构时会带来正确性的问题。下面给出一个简单的示例以说明Swap问题，如代码清单2-13所示。

代码清单2-13 Swap问题示例代码

对应的CFG图和SSA形式如图2-10a和图2-10b所示。在图2-10b中可以看到有两个φ函数定义：x ₁ 和y1。

由于代码可能存在复制传播的优化 ，假设进行复制传播优化后的SSA形式如图2-10c所示，其中x ₁ 依赖于x ₀ 和y ₁ ，y ₁ 依赖于y ₀ 和x ₁ ，因此x ₁ 和y ₁ 相互依赖。

现在对图2-10c进行SSA析构。因为图2-10c中存在的关键边，在析构SSA时可以先对关键边进行拆分，然后进行析构。当然也可以不拆分关键边，但关键边拆分后示例会更加简单，所以这里进行了关键边拆分。拆分关键边后以及进行析构SSA后的图分别如图2-11a和图2-11b所示。

经过SSA析构后，程序逻辑发生了变化：图2-10a中循环是交换两个变量，但是图2-11b并不会交换变量，两个变量指向同一个值，这就是“交换问题”。该问题的处理方法是，如果φ函数有依赖，则插入临时变量。

在析构循环体中的指令时，引入临时变量可以保证正确性（x ₁ 和y ₁ 在相互赋值之前通过临时变量交换）。实际上，φ函数依赖还可以进一步分为循环依赖和非循环依赖。对这两种不同的依赖处理方法也有所不同。

循环依赖 可以引入临时变量解决， 非循环依赖 可以通过变量排序解决。假设有两个 非循环 依赖φ函数，如代码清单2-14所示。

代码清单2-14 非循环依赖φ函数代码示例

可以看到y2依赖x2，但是x2并不依赖y2，所以在进行SSA析构时，只要保证x2在y2之前执行，就能保证结果正确。

综合这两种依赖来看，在进行SSA析构时，如果一个基本块有多个φ函数，首先需要判断φ函数的依赖关系，再根据依赖关系分别进行处理：

1）如果存在循环依赖，则引入临时变量。

2）如果是非循环依赖，则对φ函数进行排序，保证被依赖者先于依赖者进行析构。

3）如果不存在依赖，则进行复制析构（这种复制析构也称为朴素析构）。

在一些编译器或者虚拟机的实现中就是采用上述解决方案（例如JVM的C1编译器）来解决Lost Copy和Swap问题的。

3.SSA形式变换

除了上述的解决方案，还有一种通过变换SSA形式来解决Lost Copy和Swap问题的方法，该方法涉及C-SSA（Conventional SSA，常规SSA）、T-SSA（Transformed SSA，变换SSA）、变量活跃区间、变量冲突等概念，下面先简单介绍一下相关概念。

变量活跃区间是指变量在一个区间内活跃，当变量不在区间中时，则认为变量是死亡的。变量活跃区间示例如代码清单2-15所示。

代码清单2-15 变量活跃区间示例

假设变量a在语句2以后不再被使用，变量b在语句2以后还会被使用，现在分析变量a的活跃区间。直观上看，变量a在语句1处被定义，在语句2处被使用，可以认为变量a在区间[1，2]活跃（区间包含语句1和语句2）；而变量b在语句2处被定义，它的活跃区间是[2,...]。再对变量a和变量b进一步分析可以发现：虽然变量a和变量b都在语句2处活跃，但活跃区间有所不同。变量a在语句2中最后一次被使用，即这里是其活跃区间的终点；而变量b在语句2中是第一次使用，这里是其活跃区间的起点，故而实际上变量a和变量b的活跃区间并不重叠（即可以把变量a、b分配到同一个寄存器中）。所以对变量活跃区间进一步优化，可以将变量a的活跃区间变成[1,2)，而变量b的活跃区间变为[2,...)。变量冲突指的是变量的活跃区间重叠，如果变量之间的活跃区间不重叠，则说明变量不冲突。

C-SSA 和 T-SSA 可以简单地认为是对SSA的分类，它们是析构算法中非常重要的概念，其中C-SSA指的是可以通过朴素算法直接析构的SSA形式，而T-SSA不能直接采用朴素算法进行φ函数的析构，故而只要将T-SSA转换成C-SSA，则所有SSA都可以通过朴素算法进行析构。那么C-SSA和T-SSA的根本区别是什么？下面通过一个例子来直观地认识这些区别，如图2-12所示。

在图2-12中，T-SSA和C-SSA相比，由于优化（如复制传播）的缘故而将冗余代码删除。在分支中y ₀ =y ₁ ，将y ₀ 传播到φ函数中，φ函数变成y ₃ =φ(y ₁ ,y ₂ )，经过编译优化后的SSA在满足一些特性后就被称为T-SSA。在C-SSA中，φ函数中引用的变量的活跃区间不冲突；而在T-SSA中，φ函数引用的变量活跃区间发生了冲突。例如在图2-12c中，y ₁ 和y ₂ 在基本块2存在活跃区间冲突；在图2-12b中，y ₁ 和y ₂ 在基本块2并不存在活跃区间冲突。所以，SSA消除算法的核心就是将T-SSA变换为C-SSA，通过变换解决T-SSA中φ函数引用参数的变量冲突问题。

注意

这里提到变量的活跃区间冲突并不准确，更为准确的说法是web（网）的冲突。

在寄存器分配中有一个web，一些寄存器分配算法的粒度是web，而不是变量。web是Def-Use（简写为du）链中每一个Def或者Use的最大并集，即如果du链能关联Use或者Def，则Use和Def都在du链中，web的具体计算方法如下。

1）计算每个变量的du链。

2）du链中有公共Def或者Use，说明不同的du链有相交的部分，求并集，则构成了web。

此处引入φ-web（指φ函数中右侧使用的变量构成的web），如果φ函数中的φ-web之间有冲突，则其SSA就是T-SSA，需要将其变换为C-SSA。实现这一转换有两种典型的算法，分别是Briggs算法和Sreedhar算法，其算法思想如下。

1） Briggs算法 ：在φ函数中插入一条额外的COPY指令后再删除φ函数。首先在φ函数的前驱节点中直接插入COPY指令，然后在φ函数定义的变量位置引入一个新的变量并插入一条COPY指令（而不直接重用原来φ函数定义的变量），通过引入新的变量解决变量活跃区间冲突。当然在插入变量时需要考虑顺序。

2） Sreedhar算法 ：完全不同于Briggs算法，Sreedhar算法先考察φ函数中使用的变量是否存在冲突：如果变量之间存在冲突，则引入新的变量，并使用COPY指令缩短变量的活跃区间；如果变量之间不存在冲突，则直接使用φ函数定义的变量替换φ函数使用的变量，最后删除φ函数。

其中Briggs算法非常简单（和朴素算法类似，区别在于引入了额外的变量用于缩短变量的活跃区间），但该算法最大的问题是插入过多的COPY指令，当然后续可以通过寄存器合并，以减少COPY指令。 但研究证明， 该算法析构SSA后仍有不少冗余的COPY指令。Sreedhar算法稍微复杂 ，此处不展开介绍。下面通过例子来比较一下Briggs算法和Sreedhar算法，原始SSA的代码优化示意图如图2-13a所示。

按照Briggs算法对图2-13a中的φ函数进行析构。因为φ函数定义的变量为y ₁ ，所以在基本块1中引入y ₁ =y ₀ 的COPY指令，在基本块2中引入一个新的临时变量temp，同时引入类似temp=y ₁ 的COPY指令，之后在基本块2的尾部引入类似y ₁ =y ₂ 的COPY指令，这样就完成了SSA析构，得到如图2-13b所示的结果。由于SSA析构引入了大量的COPY指令（共计3条COPY指令），可以执行寄存器合并的操作，得到如图2-13c所示的结果。

根据Sreedhar算法对图2-13a中的φ函数进行析构。首先计算变量的冲突情况，如图2-14a所示，可以看到：基本块2中y ₁ 和y ₂ 冲突（如图中蓝色框所示），所以在基本块2中直接引入新的变量y ₁ '，并将语句变成y ₁ '=φ(y ₀ ,y ₂ )和y ₁ =y ₁ '，如图2-14b所示。在图2-14b基本块1中变量没有冲突，所以可以直接用y替换y ₀ ，此时就可以删除基本块2中的φ函数。得到析构结果如图2-14c所示。

在Sreedhar算法中，对基本块2的目的变量进行了重写，即引入替换y ₁ 的新目的变量y ₁ '，并且增加语句y ₁ =y ₁ '。在实现时也可以对源变量进行重写，例如对y ₂ 进行重写，此时y ₁ =φ(y ₀ ,y ₂ ')，并且插入新的COPY指令y ₂ '=y2。

从图2-13中可以看到，Briggs和Sreedhar算法得到的结果一致。但研究证明，对复杂的代码来说，使用Briggs算法产生的COPY指令明显比Sreedhar算法更多。来看另一个例子，原始SSA如图2-15所示。

为了分析寄存器合并的可能性，同时分析变量的活跃区间，使用Briggs算法对图2-15所示的代码进行SSA析构，结果如图2-16所示。

在图2-16中可以看到，y ₁ 、y ₂ 、temp活跃区间冲突，因此不能合并。

采用Sreedhar算法对图2-15所示的代码进行SSA析构，同时分析变量的活跃区间，结果如图2-17所示。

从图2-17中可以看出，y ₂ 和temp的活跃区间不重叠，所以可以合并。由此可以看出，Sreedhar算法效果会更好（还可以通过复制传播进一步优化，上述例子并没有体现复制传播优化的结果）。

2.3.4 SSA分类

根据变量的活跃情况不同，SSA常见的分类有最小SSA、剪枝SSA、严格SSA，其定义如下。

1） 最小SSA （minimal SSA）：它的特点是，在同一原始变量的两个不同定义的路径汇合处插入一个φ函数，这样得到的SSA就是拥有最少φ函数数量的SSA形式。这里的最小不包含一些优化（比如消除死代码中可消除的φ函数）后的结果。

2） 剪枝SSA （pruned SSA）：指的是如果变量在基本块的入口处不是活跃（live）的，就不必插入φ函数。通常有两种方法：第一种方法是在插入φ函数的时候进行活跃变量分析，只对活跃变量插入φ函数；第二种剪枝方法是在最小SSA上进行死代码消除，删掉多余的φ函数。需要注意的是，获得剪枝SSA的成本比较高，所以可以采用一些折中的方法，例如插入φ函数前先去掉仅位于同一个基本块的变量，这样既减少了变量个数也减少了计算活跃变量集的开销。

3） 严格SSA （strictly SSA）：如果一个SSA中，每个Use被其Define支配（如果从程序入口到一个节点A的所有路径都先经过节点B，则称A被B支配，具体参见第4章），那么该SSA称为严格SSA 。

不同分类的SSA在后续的优化中处理会略有不同。2.3.2节通过支配边界计算得到插入φ函数的位置，从而构造出来的SSA，所有φ函数都是必需的，故该SSA就是最小SSA。

注意

在一些编译优化过程中，由于程序的变换会导致代码不再符合SSA形式，因此要使用SSA的特性，就必须重新构造或者重命名变量，以保持SSA形式。

2.3.5 基本块参数和Phi节点

在构造SSA形式时，目前业界主要在汇聚点使用φ函数表示来自不同路径的同一个变量。最近几年，学者在一些编译器（例如MLIR、Swift等）中使用基本块参数（basic block argument）替代φ函数，主要是因为φ函数使用比较困难，主要表现如下。

1）φ函数必须位于基本块的头部。

2）本质上φ函数是并行执行的，所以在析构时要防止产生Swap问题。

3）如果基本块前驱基本块过多，会插入很多φ函数，而在插入φ函数时并无顺序要求，但在编译优化中需要将这些φ函数顺序化处理（还要保证并行化语义），较为耗时。

基本块参数和φ函数本质上并无差别，只是在表现形式上略有不同。仍然以代码清单2-11为例，对应的基本块参数表示如代码清单2-16所示。

代码清单2-16 代码清单2-11对应的基本块参数表示

基本块loop有两个参数x2和y2，用于接收基本块entry和loop在进入loop时的变量。相比φ函数，基本块参数只是将φ函数变成基本块的参数，所以两者本质上并无太大差别。但是基本块参数能够克服φ函数在使用中的问题，对算法实现更为友好。当然使用基本块参数也需要处理一些特殊情况，例如同一条指令多次使用同一个基本块，示例如代码清单2-17所示。

代码清单2-17 同一条指令多次使用同一个基本块的示例

同一条分支指令的不同目的基本块都指向了同一个基本块。例如，entry中有两个分支：block(v3)和block(v4)，两个分支需要同时进入一个基本块block，并分别将变量v3和v4传递给目的基本块block，作为入参v20，此时需要对这样的形式进行处理，否则可能会导致逻辑错误（CFG发生了变化）。当然也可以要求前端不生成这样的IR形式，或者可以对这样的IR进行变换，可通过添加一个新的基本块来解决这一问题。

2.4 本章小结

本章主要介绍IR基础知识，涵盖IR的分类、控制流和基本块、SSA相关知识（含义、构造、析构）。因为LLVM代码生成以及使用的IR主要是SSA形式，并且指令选择后的IR也是SSA形式，所以编译器基于SSA会进行一系列编译优化，在寄存器分配时是先析构SSA再完成寄存器分配，所以本章详细讨论了SSA。最后，本章还简单讨论了不同形式的SSA的实现思路，即φ函数和基本块参数。 CfsPQIcj2BurMnjs4ZlsB2MJcUwdehnTYSf/BS2TQVrWG58sNJPBdr7ZyJXBVEuq