SSA如何构建？

上周牛牛给大家介绍了什么SSA，这周我们来唠唠如何构建SSA。

需要处理数据流的交汇问题，以此保证数据赋值的单一性。无论是使用 block-argument 还是 phi 指令，都需要找到数据流交汇点，这才是难点。

  1、通过 Load-Store 的方式作弊

LLVM 中为了前端生成 SSA 格式的 LLVMIR，使用 store 和 load 开了一个后门，通过这两个指令设置的内存不受 ssa 格式影响，因此可以简单的将多次赋值的指令全部处理为内存，转入 LLVM-IR 以后将会有一个特殊的 pass 进行 memory 2 reg 操作，将内存操作转换为虚拟寄存器和 phi 指令的使用。这个方式其实是直接回避了数据流合并的问题，通过内存开了个口子，还是使用的重复赋值数据。但是实现及其简单。

 cmp b, c 
 pa = alloc(i32)
 jg else 
then: 
    store b, pa 
    jmp end
else:
    store c, pa 
end:
    a = load(pa)

剩下两种分析方案，不管是 cfg 还是 ast 入手去生成 ssa，其实都是期望通过对于控制流合并点和变量定义的筛选，找到数据流合并点，数据流合并点才是真正需要插入 phi 值的时候。和 LLVM 先转成用内存作弊的 IR 然后进行转换类似，很多构建方案将会创建过多的 phi 指令，然后再通过后续的优化进行精简。

   2、基于 cfg 求解支配边界构造: 算法 Cytron 1991

因为 ast 到 ssa-cfg 之间其实隔了两层，cfg 需要控制流的分析，ssa 需要数据流的分析。对于 cfg 的分析更为简单，一般会先构建 cfg，然后对 cfg 进行分析，分析的对象是 cfg 中的节点，也就是基本快。最后得到的结果也是需要在哪些基本快中插入 phi 指令。其实对 cfg 分析，还是对于控制流的分析，通过这个分析得到控制流的交汇点，如果交汇点的两个前序中定义了某个变量，则可以认为这两个前序节点中的某个变量定义不同，这个控制流的交汇点就是数据流的交汇点，可以直接插入 phi 指令。在很多算法中，可以插入过量的 phi 节点以保证 SSA 格式的正确，然后通过后续的优化进行处理去除多余的 phi。LLVM 的构建方案就是使用 Cytron 1991 算法。

论文：https://www.cs.utexas.edu/~pingali/CS380C/2010/papers/ssaCytron.pdf

3、基于 ast 构造: 论文 Braun 2013

改论文的思路仍然是评估cfg，但是认为输入是结构化语言的语法树，通过对基本块的操作和标记算法，确定闭合基本块，通过评估基本块的前驱节点判断是是否增加phi指令，通过map和规定算法通过ast可以同时生成ssa格式的ir和cfg流程图。并且对于简化phi指令生成最小ssa也有优化算法和算法验证。

论文：https://pp.info.unikarlsruhe.de/uploads/publikationen/braun13cc.pdf

  4、CFG 设计

一般的语言中端设计方案：CFG+SSA 的结构。一般的整个程序表示为一个 Module，其中包含多个 Function，每个 Function 内含多个 BaseBlocks 的列表，这些 BaseBlock 本身是图的一个个节点，内部保存自身的前序和后继节点，在示例中我们画出了这样一个图。特殊的两个 block 是 enter 和 exit 被 function 直接指向表示函数入口和出口。每个 block 内含多条 Instruction 表示指令，这些指令都是遵守 SSA 形式的。通过这样的 CFG 设计可以表达程序的控制流。

   5、Use-def 链设计

基础结构定义如下。所有的 value 是可以被使用的变量，user 表示可以使用其他值，而且 user 继承自 value，每个 user 同时作为 value 也可以被其他的 value 使用，还有 use 结构, use 存在两个指针分别指向 user 和 value，表示一个 user 正在使用一个 value。

运行时数据排布如下， 每个 value 保存 use 列表，其中表示哪些 user 使用了自己，比如 (user 1 user 2) 而 user 保留两个 use 列表

>其中一个表示自己在使用哪些 value，比如 (user 1)

>另一个表示哪些 user 在使用自己。比如 (user 3 user 4 )

参考：https://llvm.org/doxygen/classllvm_1_1User.html

  6、Sea of nodes

Sea of node 的设计主要使用在 java 和 javascript 中，主要由 cliff click 大神的两篇论文提出：

>From Quads to Graphs

>A Simple Graph-Based Intermediate Representation

其主要的想法是将能分析的数据都分析出来，通过 Region 节点表达控制流，通过指令运算节点表达数据流。一个示例如下，左图表示传统的 CFG+SSA 图的模式，右图表达对应逻辑在 sea of node 形式 IR 下的表达。Sea of node 的优势在于可以非常好的将数据流和控制流分离开，并且显示的表达这个控制流和数据流，而不是通过 CFG+userdef 两个图嵌套在一起的形式去表达。一个数据流和控制流的关系如下图所示。

yaklang 的 SSA 实现正在开发中！

主要构建算法参考论文Braun 13， cfg设计参考常规方案(非son)，ssa指令设计追求高层IR抽象化避免底层内存相关操作。

[ssa(https://github.com/yaklang/yaklang/tree/feature/ssa/common/yak/ssa)

1、YuLang

[MaxXSoft/YuLang] (https://github.com/MaxXSoft/YuLang)

一个比较完整实现的语言，前端完成了 ast 的构建，中端完成了 ssa 格式的转换以及 pass 构架和两个 pass 的编写，后端接入 LLVM 编译得到目标文件。使用 cpp 编写。

唯一的不足可能是只生成了 obj 文件，而语言标准库的 import 只显示为外部引用包，需要再手动依赖 clang 的连接器，将多个 object 和 archive 文件进行链接。

Ssa 的设计：全部变量通过 store+load 的方案进行构建。后续交给 LLVM 直接进行优化即可。

   2、LLVM

代码结构、模块化设计设计的胜利！

LLVM 创造性地设计了一套前中后分离的方案，让语言的前后端分离，同时中间层进行基于 SSA 形式的 LLVMIR 的优化使得优化方案可以尽可能地复用。

但是LLVM仍然处于操控内存等比较偏向底层的IR设计。

   3、MLIR

MLIR的设计目标是尽可能创建一套可以将多种IR互相转换的框架。

对于语言的介入，提供了一套 IR 的表示，以及对应的 api，提供了比较方便的代码生成器快速生成定义。在 MLIR 中称为 Dialect。

对于进入 IR 以后的转换，提供了类似 LLVM 的 analyzer 和 passmanage 的组合，分析 ssa 形式 cfg 的内容并进行转换。

对于接入的语言，可以在 MLIR 的层面上进行互相转换。和 LLVM 的前中后的分离不同，MLIR 希望做的是一个中间层，其他接入 MLIR 的语言都是 Dialect，这些 Dialect 是平级关系，可以互相转换。通过这样的方式可以完成 HighLevelPL -> MLIR -> LLVM的转换，这是一个从高到低的转换，但是对于 MLIR 来说这是平级的。具体来说这是通过 PASS 机制实现的。

4、DCC

一个安卓加固工具，将 dex 内的字节码转换为 c 语言的 native 层代码。转换部分使用 androguard 库完成 cfg 的构建，然后使用论文Braun 13的 SSA 构建方法建立ssa格式ir。[HowItWorks.md] (https://github.com/amimo/dcc/blob/master/HowItWorks.md)