语法分析树

语法分析树是对输入程序的推导或语法分析的图表示。

相对于源程序文本，语法分析树比较大，因为它表示了完整的推导过程，树中的每个结点分别对应于推导过程中的各个语法符号。编译器必须为每个结点和边分配内存，并必须在编译期间遍历所有的边和结点。

语法分析树主要用于语法分析的讨论中和属性语法系统中，此时语法分析树是主要的IR。

抽象语法树（AST）

抽象语法树保留了语法分析树个基本结构，但剔除了其中非必要的结点（主要是忽略了非终结符的大部分结点）。表达式地优先级和语法保持原样，但无关的结点已经消失了。

a×2+a×2×b的AST：

AST是一种接近源码层次的表示。因为其与语法分析树大致对应，语法分析器可以直接建立AST。

CFG（Control flow graph，控制流图）

程序中最简单的控制流单位是一个basic block（基本程序块），即（最大长度的）无分支代码序列。基本程序块是一个操作序列，其中的各个操作总是按序全部执行，除非某个操作引发了异常。控制总是从第一个操作进入基本程序块，在完成最后一个操作后退出基本程序块。

在CFG中，每一个结点都代表一个basic block（基本快， a straight-line piece of code without any jumps or jump targets；jump targets start a block, and jumps end a block）。CFG中的有向边用于表示控制流中的跳转。在大多数的表示中，有两种特殊指向块：

• entry block，通过它控制进入流图
• exit block，经由它所有控制离开流图
  根据其构造过程，在CFG中，每一条 A→B的边拥有以下属性：

  outdegree(A) > 1 or indegree(B) > 1 (or both).

控制流图对程序中各个基本程序块之间的控制流建立了模型。一个CFG是一个有向图。每一个结点对应于一个基本程序块，每一条边对应于一个可能的控制转移。

CFG对各种可能的运行时控制流路径提供了一种图表示法。CFG不同于面向语法的IR（如AST），后者的表明了语法结构。

while循环的CFG：

if-then-else的CFG：

编译器通常把CFG和另一种IR联用。CFG表示了块之间的关系，而块内的操作则用另一种IR表示（例如表达层次上的AST、DAG或某种线性IR，这种得到的组合是一种混合IR）。

线性IR

汇编语言就是一种线性代码，其包含一个指令序列，其中的各个指令出现的按顺序执行。编译器中使用的线性IR类似于抽象机的汇编代码

使用线性形式的逻辑为：充当编译器输入的源代码是一种线性形式，而编译器输出的目标机代码也是线性的。线性IR中控制流通常模拟了目标机上控制流的实现，故线性代码通常包含条件分支和跳转。控制流将线性IR中基本程序块划分下来，块结束于分支、跳转或有标号的操作之前

1. 堆栈机代码

堆栈机代码是一种单地址代码，假设操作数存在于一个栈中。大多数操作从栈中获得操作数，并将其结果存入栈中。堆栈机代码比较紧凑，栈本身建立了一个隐式地命名空间，从而消除了IR中的许多名字。这缩减了IR形式下程序的大小，但使用栈意味着所有的结果和参数都是暂态的，除非代码将其显示地移入内存中

Java使用了字节码（这是一种紧凑的IR，在概念上类似于堆栈机代码）。这种字节码在解释器上运行，或者先转换为目标机代码后执行。

字节码：

• 为具有紧凑的形式而特地设计的IR
• 通常针对抽象堆栈机的代码
• 字节码得名于其受限的大小
• 其操作通常是一个字节或者更小
  Java 编译器并不像 C/C++ 那样直接将高级语言转换成为机器语言（直接的 CPU 指令）；它将 Java 语言转换成为 JVM 可以理解的 Java 字节码。因为 Java 字节码没有任何依赖于平台的代码，它可以在任意安装好 JVM （准确的说是 JRE）的硬件上运行，即使当 CPU 或 OS 不同时也如此。编译好的文件的大小与源码的大小几乎一样，这让通过网络来传输和运行编译的代码变得简单。

【注】 栈IR通常包含一个swap操作，该操作魂环栈顶两个元素的值

SSA（静态单赋值）

• 在静态单赋值形式中，名字唯一地对应到代码中特定的定义位置
• 每个名字都是通过单个操作定义的，这也是静态单赋值形式名称的来历
• 每次在操作中使用某个名字作为参数时，这个名字都编码了对应值的来源地信息
• 文本化的名字实际上指向了一个特定的定义位置
• wikipedia的解释：

  static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once, and every variable is defined before it is used. Existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, use-def chains are explicit and each contains a single element.

该代码的SSA形式包含了新的赋值（x3、x5和x6），这些使得x的各个SSA形式名与x的各处使用（在对s和z的赋值中）协调起来。这些赋值确保了沿CFG中的每条边，x的当前值都分配了唯一的名字，名字的分配与控制流沿哪条代码路径转移到该边无关。这些赋值操作的右侧都包含了一个操作—φ函数，用于合并来自不同的边（φ函数获取几个名字并将其合并，以定义一个新的名字）。

φ函数的行为取决于上下文，它选择其中一个参数的值来定义其目标SSA的名字，该参数对应于CFG中控制流进入当前的边。

在基本程序块的入口处，其所有φ函数都将在任何其他语句之前并发执行。

• 首先，它们都会读取适当参数的值
• 然后，定义其目标SSA名字
  用这种方法定义φ函数地行为允许操控SSA形式的算法在处理基本程序块的顶部时可以忽略φ函数的顺序
  【注】
• φ函数的参数为进入进本程序块的各条边相关联的值的SSA形式名。
  在控制流进入一个basic program block时，该程序块中的所有φ函数都将并行执行
• 构造SSA形式的过程会在CFG中的每个汇合点之后插入φ函数。汇合点即为CFG中多条代码路径汇合的地方。在汇合点处，不同的SSA形式名必须调和为一个名字。

在整个过程已经转换为SSA赋值形式之后，需遵守两条规则：

1. 过程中的每个定义都创建了一个唯一的名字
   每个使用处都引用了一个定义
2. 引入SSA意在代码优化。SSA中φ函数的放置包含了值的产生和使用两方面的信息。命名空间的单赋值特性，使得编译器可以规避许多与值的生命周期有关的问题。

数据流分析

数据流分析是指一组用来获取有关数据如何沿着程序的执行路径流动的相关信息的技术。【例如某一个赋值语句的结果在任何后续的执行路径中都没有被使用，则可以吧这个赋值语句当作死代码消除】

程序的执行可以看作是对程序状态的一系列转换。程序状态由程序中的所有变量的值的组成，同时包括运行时刻栈的栈顶之下的各个帧栈的相关值。一个中间代码语句的每次执行都会把一个输入状态转换成一个新的输入状态。这个新的输入状态和处于该语句之前的程序点相关联，而输出状态和该语句之后的程序点相关联。

当在分析一个程序的行为时，必须考虑程序执行时可能采取的各种通过程序的流图的程序点序列（“路径”）。然后从各个程序点上可能的程序状态中抽取出需要的信息，用以解决特定数据流分析问题。

流图会给出的可能的执行路径的信息为：

• 在一个基本快内部，一个语句之后的 数据点和它的下一个语句之前的程序点相同
• 如果有一个从基本快B1到基本快B2的边，那么B2的第一个语句之前的程序点可能紧跟在B1的最后一个语句后的程序点之后

可以把从点P1到点P2的一个执行路径（execution path，简称路径）定义为满足下列条件的点序列P1,P2,...,Pn:

• 要么Pi是紧靠在一个语句前面的点，且Pi+1是紧跟在该语句后的点
• 要么Pi是某个基本块的结尾，且Pi+1是该基本块的一个后继基本块的开头

到达定值（reaching definition）

到达定值是最常见和有用的数据流模式之一。编译器能够根据到达定值信息知道 x在点p上的值是否为常量，而如果x 在点p上被使用，则调试器可以指出x是否未经定值就被使用。

如果存在一条从紧跟在定值d后面的程序点到达某一程序点p的路径，并且在这条路径上d没有被“杀死”，就说定值d到达程序点p（如果在这条路径上有对变量x的其他定值，就说变量x的这个定值被“杀死”了）。

来自wikipedia的解释：

In compiler theory, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment.
例如：

d1 : y := 3
d2 : x := y

对于d2而言，d1是达到i定值

d1 : y := 3
d2 : y := 4
d3 : x := y

对于d3而言，d1不在是到达定值，因为d2“杀死”了它：在d1中定义的值再也无法到达d3。
变量x的一个定值是（可能）将一个值赋给x的语句。过程参数、数组访问和间接引用都可以有别名，因此指出一个语句是否向特定程序变量x赋值并不是一件容易的事。

数据流分析模式

在所有的数据流分析应用中，则会把每个程序点和一个数据流值（data-flow value）关联起来。这个值是在该点可能观察到的所有程序状态的集合的抽象表示。所有可能的数据流值的集合称为这个数据流应用的域（domain）。【例如，到达定值的数据流值的域是程序的定值集合的所有子集的集合】

把每个语句s之前和之后的数据流值分别记为IN[s]和OUT[s]。数据流问题（data-flow problem）就是要对一组约束求解（这组约束对所有的语句s限定了IN[s]和OUT[s]之间的关系）。

约束分为两种：

• 基于语句语义（传递函数）的约束
• 基于控制流的约束

传递函数

在一个语句之前和之后的数据流值受该语句的语义的约束。一个赋值语句之前和之后的数据流值的关系被称为传递函数（transfer function）。

迭代数据流分析（ITERATIVE DATA-FLOW ANALYSIS）

编译器使用数据流分析来确定进行优化的机会，并证明特定变换的安全性。即Cytron et al.’s algorithm。

传统SSA构造算法（即从线性IR到SSA的构造）的具体步骤

1. 遍历IR构造CFG
2. 计算支配边界
3. 确定φ函数（Phi函数）的位置
4. 变量重命名

1. 遍历IR构造CFG

确定基本块（basic block）的算法：
（1）查找基本块入口源代码的首行、转移代码（有条件和无条件）、转移代码的下一行
（2）基本块构造：由入口点开始，将其组织成各自的基本块。
（3）如果有语句不在任一基本块中，则称之为“死代码”，删除

当确定基本块之后，接着构造CFG

CFG构造如果在一个有序代码中，基本块B2跟在B1后，那么产生一个B1到B2的有向边
（1）有跳转点。这个点从B1的结束点跳转到B2的开始点
（2）无跳转点（有序代码中），B2跟在B1后，且B1的结束点不是无条件跳转语句

支配性（Dominance）

例如，从B0到B6的每条代码路径都包含了结点B0、B1、B5和B6。因此，Dom(B6)为{B0，B1，B5，B6}。

集合Dom(Bi)中包含了支配Bi的所有结点。

支配性：在入口结点B0的流图中，当且仅当Bi位于从B0到Bj的每条路径上时，结点Bi才支配结点Bj。

求解数据流问题的方程：

为使用上述方程，需要使用三个步骤：
（1） 构建一个CFG
（2） 收集各个程序块的初始信息
（3） 求解方程，生成各个程序块的Dom集合

考虑CFG的结点n中的一个定义。该值到达某个结点m时，如果n∈Dom(m)，则该值不需要φ函数，因为到达m的每条代码路径都必然经由n。该值无法到达m的唯一可能就是有一个同名定义的干扰，即在n和m之间的某个结点p中，出现了与该值同名的另一个定义。在这种情况下，在n中的定义无需φ函数，而p中的重新定义则需要。

结点n中的定义，仅在满足下列条件的汇合点才需要插入对应的φ函数：
（1）n支配m的一个前驱
（2）n并不严格支配m

严格支配性：当且仅当a∈Dom(b)-{b}时，a严格支配b。

【注】：DF(n)表示：在离开n的每条CFG路径上，从结点n可达但不支配的第一个结点。

此例中，B5支配B6、B7和B8，但不支配B3。在每条离开B5的路径上，B3都是B5不支配的第一个结点，因而，DF(B5)={B3}。

支配者树（dominator tree）

给出流图中的一个结点n，严格支配n的结点集是Dom(n)-{n}。该集合中与n最接近的结点称为n的直接支配结点，记为IDom(n)。流图的入口没有直接支配结点。

流图的支配者树包含流图中的每个结点。如果m为IDom(n)，那么支配者树中有一条边从m指向n。

伪代码实现：

2.计算支配边界

放置φ函数的关键在于判断何处真正需要φ函数，以及哪个变量需要φ函数。

由于CFG中只有汇合点才是支配边界的成员，故首先识别出图中的所有汇合点。对于一个汇合点j，我们考察其在CFG中的每个前驱结点。

计算支配边界的算法：

3.放置φ函数（即确定φ函数的位置）

常规算法会在每个汇合点起始处，为每个变量放置一个φ函数。有了支配边界之后，编译器便可以更加准确地判断在何处可能需要φ函数。

基本思想是：基本块b中对x的定义，要求在DF(b)集合包含的每个结点起始处都放置一个对应的φ函数。因为φ函数是对x的一个新的定义，此处插入φ函数，进而可能导致额外的φ函数。

编译器可以进一步缩小插入的φ函数集合。只在单个基本块中活动的变量，绝不会出现与之相应的活动φ函数。为了实现这一规则，编译器可以计算跨多个程序块的活动变量名的集合，该集合称为全局名字（global name）。它可以对该集合中的名字插入φ函数，而忽略不在该集合中的名字。

找到全局名字集合

插入φ函数的算法：

对于每个全乎名字x，算法将WorkList初始化为Blocks(x)。对于WorkList中的每个基本块b，算法在b的支配边界中每个程序块d的起始位置插入φ函数。在向d添加对应于x的φ函数之后，算法将d添加到WorkList，以反映d中对x的新赋值操作。

φ函数插入算法中的第一步是找到全局名字集合并为每个名字计算Blocks集合。

• 图(a)中代码，全局名字集合为{a，b，c，d，i}。
• 图(d)给出了Blocks集合。

【注意】：算法为y和z创建了Blocks集合，虽然二者不属于Globals中。将Globals和Blocks集合的计算分离开来，可以避免实例化这些额外的集合，但代价是需要增加一趟对代码的处理。

4.重命名

在最终的静态单赋值形式中，每个全局名字都变为一个基本名，而对该基本名的各个定义则通过添加数字下标来区分。对于对应到源语言变量的名字，比如说x，算法使用x作为基本名。因而，重命名算法遇到对x的第一个定义将被命名为x0，第二个将被命名为x1。对于编译器产生的临时值，算法必须产生一个不同的基本名。

算法（插入φ函数之后的重命名）实现为：

for each global name i
    counter[i] ← 0
    stack[i] ← ∅
Rename(n0)


NewName(n)
    i ← counter[n]
    counter[n] ← counter[n] + 1
    push i onto stack[n]
    return "ni"

Rename(b)
    for each φ-function in b, "x ← φ(...)"
        rewrite x as NewName(x)
    for each operation "x ← y op z" in b
        rewrite y with subscript top(stack[y])
        rewrite z with subscript top(stack[z])
        rewrite x as NewName(x)
    for each successor of b in the cfg
        fill in φ-function parameters
    for each successor s of b in the dominator tree
        Rename(s)
    for each operation "x ← y op z" in b and each φ-function "x ← φ(...)"
        pop(stack[x])

该算法对过程的支配者树进行先序遍历，其中对定义和使用都进行可重命名。在每个基本块中，算法首先重命名由程序块顶部的φ函数定义的值，然后按序访问程序块中的各个操作。算法会用当前的静态单赋值形式重写各个操作数，接下来为操作的结果创建一个新的静态单赋值形式名。算法的后一步使得新名字成为当前的名字。在程序块中所有的操作都已经重写之后，算法将使用当前的静态单赋值形式名，重写程序块在CFG中各后继结点中的适当φ函数参数。最后，算法对当前程序块在支配者树中的子结点进行递归处理。当算法从这些递归调用返回时，它会将当前静态单赋值形式名的集合恢复到访问当前程序块之前的状态。

为了管理这一处理过程，算法对每个全局名字使用一个计数器和一个栈。全局名字的栈包含了该名字当前静态单赋值形式的下标。在每个定义处，算法通过将目标名字的当前计数器压栈来产生新的下标，并将计数器加1。因而，名字n栈顶的值总是n当前静态单赋值形式名的下标。作为处理程序块的最后一步，算法会将该程序块中产生的所有名字从栈中弹出，以恢复在该程序块的直接支配结点末尾处的的当前静态单赋值形式名字集合。处理当前程序块在支配者树中余下的兄弟结点，可能需要这些名字。

当算法中的控制流在支配者树中上下移动时，栈模拟了当前程序块中最新定义的生命周期。而在这一方面，计数器则是单调递增的，以确保各个连续的定义都能分配一个唯一的静态单赋值形式名

该算法初始化了栈和计数器，然后对支配者树的根结点（即CFG的入口结点）调用Rename。Rename会重写该程序块，并下降到其在支配者树的各个后继结点上递归处理。为完成对该程序块的处理，Rename会弹出处理该程序块期间压栈的任何名字，而NewName会操作计数器和栈，以按需创建新的静态单赋值形式名。

Simple and Direction SSA Constriruction Algorithm

传统的SSA构造算法（如之前的Cytron et al.’s algorithm），是直接从线性IR构造SSA。而Simple and Efficient Construction of Static Single Assignment Form这一论文则是允许从AST、Bytecode甚至源码直接构造SSA。

一.LLVM的做法

LLVM IR虽然为为SSA形式，但如果所有生成的LLVM IR都要前端自己计算好如何生成SSA形式，对于前端而言将十分棘手。故LLVM IR借助“memory不是SSA value”的特点，给用户留了一个后门：前端在生成LLVM IR时，可以选择不生成真正的SSA形式，而是把局部变量生成alloca/load/store形式：

• 用alloca来“声明”变量，得到一个指向该变量的指针；
• 用store来把值存进变量里；
• 用load来把值读出为SSA value。

此时，对局部变量的读写就变得跟普通内存的读写一样，不需要SSA形式。接着，LLVM利用mem2reg pass，识别出这种模式的alloca，并将它提升为SSA value（并消除掉store与load，改为普通的SSA层面的def-use/use-def关系，并且在合适的位置安插φ函数和变量重命名）。

Clang就是讲生成SSA形式的任务交给LLVM处理：Clang的前端只会把某些临时值生成SSA value；对于显示的局部变量，Clang前端都只是生成alloca/load/store形式的LLVM IR；交给LLVM IR之后，经过mem2reg pass，IR才真正进入了普通的SSA形式。

LLVM的mem2reg pass本质上就是识别“局部变量”的模式，并对它们构建SSA形式。

LLVM mem2reg pass的实现：

// 遍历指令序列找到 alloca
for (Instruction instr : instructions)
{
    if (isa<Alloca>(instr))
        allocas.push_back(instr);
}

// 一个一个的提升 alloca 指令
for (Alloca alloca : allocas)
{
    // 判断是否可以提升
    if (!alloca.isAllocaPromoteable())
        continue;

    // 跳过无使用者的alloca指令
    if (alloca.user_begin() == alloca.user_end())
        continue;

    // 收集alloca指令的使用，定义信息
    info.analyzeAlloca(alloca);

    // 下面的函数，对只有一次定义（即只有一条 store 指令）的 alloca 进行优化
    // 把所有的 load 指令全部用定义时保存的 value 替换
    if (info.definingBlocks.size() == 1)
        rewriteSingleStoreAlloca(alloca, info);

    // 下面的代码仅仅对只在一个基本块中使用和定义的alloca指令进行优化
    if (info.onlyUsedOneBlock)
        promoteSingleBlockAlloca(alloca, info);

    // 插入无参数的Phi函数，使用标准的基于支配边界的算法，其中使用DJ图的方式进行了优化
    determineInsertionPoint(alloca, allocaNum, info);

    // 使用 IDF 和标准 ssa 构造算法提升 alloca ，决定那些需要插入 Phi 函数
    DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
    ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
    IDF.setLiveInBlocks(LiveInBlocks);
    IDF.setDefiningBlocks(DefBlocks);
    IDF.calculate(PHIBlocks);

    // 执行 SSA 重命名算法，并插入 Phi 节点
    RenamePassWorkList.emplace_back(&F.front(), nullptr, std::move(Values));
    do {
        // RenamePass may add new worklist entries.
        RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList);
    } while (!RenamePassWorkList.empty());

    // 移除 allocas
    for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 
    {
        Instruction *A = Allocas[i];
        A->replaceAllUsesWith(UndefValue::get(A->getType()));
        A->eraseFromParent();
    }

  // 最后执行一趟消除平凡Phi函数的操作，
    while (eliminatedAPHI)
    {
        // if the phi merges one value and/or undefs, get the value
        if ((V = simplifyInstruction(phi, DT)) != null)
        {
            phi.replaceAllUsesWith(V);
            phi.eraseFromBasicBlock();
            newPhiNodes.remove(entity);
            eliminatedAPHI = true;
            continue;
        }
    }
}

二.Simple SSA Construction

来自论文

Simple and Efficient Construction of Static Single Assignment Form
Matthias Braun1, Sebastian Buchwald1, Sebastian Hack2, Roland Leißa2, Christoph Mallon2, and Andreas Zwinkau1

Cytron et al.’s algorithm的缺点：

• 其输入程序必须表示为CFG的非SSA形式
• 为保证放置φ函数的代价最小，此算法依赖以下几点：
  • 为了计算φ函数的放置位置，需要计算支配树和迭代支配边界
  • 为避免死亡φ函数，需要执行活性分析或者死代码消除

（1）Local Value Numbering

在translate源程序的时候，需要注意：一组statements的IR通常会出现在一个basic block中。因此，此方法按照程序的执行顺序（execution order）处理所有表达式，并且在每个基本块中的变量和其当前的定义表达式（ defining expression）之间建立映射。当遇到对变量赋值情况，需要将赋值号右侧的IR作为当前变量的定义。当一个变量被访问时，就寻找其当前定义（current definition，通过algo 1实现），这一过程就称为local value numbering。当一个basic block完成了local value numbering，就称这个基本块为filled。只有当一个basic block完成了local value numbering，才能够继续添加后继基本块（这一性质在处理incomplete CFG时会用到）。

Algorithm 1: Implementation of local value numbering

writeVariable(variable, block, value):
    currentDef[variable][block] ← value
readVariable(variable, block):
    if currentDef[variable] contains block:
        # local value numbering
        return currentDef[variable][block]
    # global value numbering
    return readVariableRecursive(variable, block)

【注意】:
如果在对一个基本块进行赋值之前，对其进行访问则会出现问题。例如上例中的变量d与之对应的值v？，d的定义不能从CFG的root到当前basic block的路径上查找到。此外，程序中的多个定义也许会reach到相同的use。

（2）Global Value Numbering

如果当前块没有变量的定义，便递归地在其前驱（predecessors）基本块中查找定义。

**递归查找算法为：

• 如果基本块只有一个前驱，就只在其前驱中递归地查询定义
• 否则，从其所有predecessors中collect它的definitions，并构造一个φ函数，将φ函数加入其所有前驱中定义中，并将该φ函数作为该basic block中variable的当前定义。**

在前驱中查找的方式可能导致循环查找（recursive look-ups），比如在循环中进行查找（Due to loops in the program, those might lead to endless recursion）。为了避免程序出现死循环，在查找前先创建一个没有operands的φ函数，并将其记录为basic block中变量的当前定义。然后，我们确定φ函数的operands。如果递归查找arrive back到该基本块，则此φ函数将提供一个定义，并且递归将结束。

为了更轻易的展示global value numbering，值vi的index按照算法在插入它们的顺序进行assigning。我们假设在读取x之前已经构造好了loop，也就是说，已经通过local value numbering将v0和v1作为为x的definition，而利用loop之后的statement来查找x。由于在loop之后的block中没有x的定义，因此执行递归查找。 该block只有一个predecessor，所以在这里不需要φ函数。 这个predecessor只是一个loop header，它也没有x的定义，但有两个predecessors。因此，我们放置一个没有任何操作的（operandless） φ函数v2。 它的第一个operand是流入loop的值v0，第二个operand需要进一步递归。φ函数v3被创建并从其direct predecessors处获得其operands。 此外，之前放置的v2终止了递归。

Algorithm 2: Implementation of global value numbering

readVariableRecursive(variable, block): 
    if block not in sealedBlocks: 
        # Incomplete CFG 
        val ← new Phi(block) 
        incompletePhis[block][variable] ← val
    else if |block.preds| = 1:
        # Optimize the common case of one predecessor: No phi needed 
        val ← readVariable(variable, block.preds[0])
    else : 
        # Break potential cycles with operandless phi 
        val ← new Phi(block) 
        writeVariable(variable, block, val) 
        val ← addPhiOperands(variable, val) 
    writeVariable(variable, block, val) 
    return val

addPhiOperands(variable, phi): 
    # Determine operands from predecessors 
    for pred in phi.block.preds: 
        phi.appendOperand(readVariable(variable, pred)) 
    return tryRemoveTrivialPhi(phi)

这种递归查找方法可能会导致冗余的φ函数，称之为trivial。如果一个φ函数references itself and one other value v any number of times，则称此φ函数为trivial φ函数。比如有 a.1 = φ(a.1, a.0)。这个 φ 函数完全可以被另一个定义给替换。还有一种特殊的情况，φ函数仅仅引用了自身，这种情况仅仅发生在不可达或者开始基本块，这时用一个 Undef 值（未定义值）代替。

【注意】:
如果一个trivial φ 函数被替换，这可能导致引用了此φ函数的值也变为trivial φ 函数，所以需要递归地进行替换操作。

Algorithm 3: Detect and recursively remove a trivial φ function

tryRemoveTrivialPhi(phi): 
    same ← None for op in phi.operands: 
        if op = same || op = phi: 
            # Unique value or self−reference
            continue 
        if same = None: 
            # The phi merges at least two values: not trivial 
            return phi 
        same ← op
        if same = None: 
            # The phi is unreachable or in the start block
            same ← new Undef() 

        # Remember all users except the phi itself
        users ← phi.users.remove(phi) 
        # Reroute all uses of phi to same and remove phi
        phi .replaceBy(same)

        # Try to recursively remove all phi users, 
        # which might have become trivial 
        for use in users: 
            if use is a Phi: 
                tryRemoveTrivialPhi(use) 
        return same

3.Handling Incomplete CFGs

如果再也没有predes被加入到当前basic block时，就称此basic block 为sealed。只要filled blocks还有successors，则其predecessors一定会被filled。注意，一个sealed block不一定会被filled。一个filled block包含其自身所有的instructions，并且可以为其successors提供变量定义（variable definitions）。 相反，一个sealed block可以从其predecessors中查找变量定义，因为其所有predecessors都是已知的。

即，如果一个基本块不会再加入任何前驱结点，那么就可以称为sealed基本块。因为只有filled基本块拥有后继，所以前驱基本块必须是filled。

Algorithm 4: Handling incomplete CFGs

sealBlock(block):
    for variable in incompletePhis[block]:
        addPhiOperands(variable, incompletePhis[block][variable])
    sealedBlocks.add(block)

seal操作会对该基本块的所有incompletePhis进行处理，完成处理后将该基本块加入sealed集合。

如何在一个unsealed block中处理变量（该变量没有当前定义）的查找问题呢？ 在这种情况下，我们将一个operandless的φ函数放入block中，并将其记录为proxy definition（参见algo 2中的第一种情况）。 此外，我们为每个block维护一组proxies：incomplete_phis。 当block随后成为sealed时，我们将operands添加到这些φ函数中（参见algo 4）。 此外，当φ函数is complete时，无论它是为trivial，我们都需要进行check。

在IR构造期间，sealing a block是一种explicit action。我们通过下图所示的while循环来说明如何incorporate此步骤。 首先，我们构造一个while header block，并以while entry block为起始，添加一条control flow edge（控制流边）。 由于随后需要添加一个body exit的jump，所以还不能seal while header。 接下来，我们创建body entry和while exit blocks，并且以while header起始，分别为这两个blocks添加conditional control flow（条件控制流）。由于再也没有predecessors会被添加到body entry block中，所以此时便可以seal它。 由于循环体中的break instructions（中断指令），while exit block可能会get further predecessors。 现在开始fill循环体。 这可能会包括更多的inner
control structures（内部控制结构），如下图（b）所示的if statement。最后，它们会converge（聚集）在body exit block处。 此时形成body的所有blocks都将被seal。 现在我们将edge添加回while header，并seal while header，至此循环完成。 在最后一步中，我们seal the while exit，然后在while循环后继续使用source statement进行IR的construction。

【注】：图中，附属在basic block旁边的数字代表了sealing（上面的数字）和filling（下面的数字）的顺序。