SSA如何构建?
2023-8-11 16:34:4 Author: mp.weixin.qq.com(查看原文) 阅读量:5 收藏

上周牛牛给大家介绍了什么SSA,SSA格式到底是个啥?这周我们来唠唠如何构建SSA。

如何构建 SSA 格式的 IR

需要处理数据流的交汇问题,以此保证数据赋值的单一性。无论是使用 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 设计可以表达程序的控制流。

对于数据流的表达是通过这些 SSA 形式的 Instruction 表达的,在后文将会讲解。

   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

大的要来了!

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)

更新日志

Yakit  v1.2.3-sp4

Yaklang 1.2.4-sp1/sp2

More

YAK官方资源

YAK 语言官方教程:
https://yaklang.com/docs/intro/
Yakit 视频教程:
https://space.bilibili.com/437503777
Github下载地址:
https://github.com/yaklang/yakit
Yakit官网下载地址:
https://yaklang.com/
Yakit安装文档:
https://yaklang.com/products/download_and_install
Yakit使用文档:
https://yaklang.com/products/intro/
常见问题速查:
https://yaklang.com/products/FAQ

长按识别添加工作人员

开启Yakit进阶之旅


文章来源: https://mp.weixin.qq.com/s?__biz=Mzk0MTM4NzIxMQ==&mid=2247509107&idx=2&sn=3fc0e87263ee1dc45d465218606f1614&chksm=c2d1d8d7f5a651c1837eb1c59fac2368c65e78a9e44bf736675a219512c62b56f5abf3deefd4&scene=58&subscene=0#rd
如有侵权请联系:admin#unsafe.sh