# 北大程序分析笔记（SSA和稀疏分析） **URL:** \ **Category:** 学术研究\ **Created:** [2020 年10 月 4 日 04:21 UTC](https://forum.90sec.com/t/topic/1321 "2020-10-04T04:21:35Z")\ **Posts on this page:** 6\ **Page:** 1
作者： ![anemone](https://forum.90sec.com/letter_avatar_proxy/v4/letter/a/46a35a/32.png) [@anemone](https://forum.90sec.com/u/anemone)\ 发布日期： [2020 年10 月 4 日 04:21 UTC](https://forum.90sec.com/t/topic/1321/1 "2020-10-04T04:21:35Z")
# 数据流分析的问题 先前有很多数据流分析问题都是关于变量中的值分析，例如：符号分析、常量传播、污点分析等。考虑对以下CFG做数值分析： ![image-20201002210707678](https://forum.90sec.com/uploads/default/original/2X/9/903aff21021e5c8372e202810de91643611df0d0.png) - 在空间复杂度方面，对每个节点都需要保存一份关于x, y, z的值，而一个节点通常只影响了少数变量（如节点2与y,z 无关） - 在时间复杂度方面，对当节点一更新y时，更新至于节点3有关，但是数据流必须通过2才能传到3 # 基于Def-Use的数据流分析 ## Def-Use关系 > 给定变量x，如果结点A可能改变x的值，结点B可能使用结点A改变后的x的值，则结点A和结点B存在Def-Use关系 以上面的CFG来说，节点0和节点1，节点1和节点3就存在Def-Use关系。 基于Def-Use的数据流分析首先将其转换为Def-Use边的图，再根据DefUse边做数据流分析： ![image-20201002211638949](https://forum.90sec.com/uploads/default/original/2X/e/e575d6fc884f76aef315b4fb4cc34c079218a8a1.png) 例如上图，有以下转换函数： - y\_0=f\_0() - y\_1=f\_1(y\_0\sqcap y\_1) - x\_2=f\_2(x\_2\sqcap x\_0) - z\_3=f\_3(y\_0\sqcap y\_1) 对Def-Use的数据流分析有以下好处： - 节点只需保存与自己相关的抽象值 - 图上的边大大减少，即图变为稀疏图 - 分析效率提高 ## 相关性质 - may分析，返回结果是真实结果的超集； - soundness和precision，等效于原数据流分析效果。 ## 需要解决的问题 问题1：如何构造Def-Use？ 可以用Reaching Definition分析得到，那么分析复杂度为 O(nm^2)，n为控制流图节点，m为赋值语句个数，速度不够快。 问题2：如果分支语句过多，Def-Use的边反而会增加： ![image-20201002211638949](https://forum.90sec.com/uploads/default/original/2X/e/e575d6fc884f76aef315b4fb4cc34c079218a8a1.png) # 静态单赋值和稀疏分析 ## 静态单赋值 为解决上述问题，引入静态单赋值（SSA），在SSA中，每个变量只被赋值一次，并且引入 \phi() 函数表示控制流汇聚的情况，例如如下代码（左侧）表示为静态单赋值形式（右侧）： ![image-20201003114951916](https://forum.90sec.com/uploads/default/original/2X/a/a49c40b9bace2403f11362c91e434c54d9d73d3b.png) SSA有如下几个好处： - SSA直接提供了def-use链，如下所示，等号左边变量为入度，等号右边变量为出度： ![image-20201003115232485](https://forum.90sec.com/uploads/default/original/2X/3/3fec69963550bdb4a3d551131a9918f1c0a6c9ec.png) - SSA的边不会平方增长（因为有 \phi() ）： - SSA上的流非敏感分析和流敏感分析等价（变量间赋值关系反映了数据流向） ## 稀疏分析 基于SSA的分析被称为 **稀疏分析** （sparse program analysis） # 构造SSA 首先讨论 \phi 的加入条件，对于一个代码块B，若满足一下条件，需要在B前加 \phi ： 1. 到达B的路径≥2； 2. 其中有一条路径经过了某变量i的赋值语句s； 3. 有一条路径没有经过s； 4. s和B之间没有别的代码块满足条件。 ## 支配关系 **节点A支配（dominate）节点B** ，指所有从Entry到B的路径都要经过A，如下两种情况，A都支配B： ![image-20201003162723477](https://forum.90sec.com/uploads/default/original/2X/b/b36b1b57848f8fcc5f289bb8cde2b9137e3af22d.png) **结点A严格支配（Strictly dominate）结点B** ，A支配B并且A和B不是一个结点（如上图中，只有左图A严格支配B）。 **结点A的支配边界（Dominance Frontier）中包括B** ，当且仅当： - A支配B的某一个前驱结点，即A在B的某条路径上： ![image](https://forum.90sec.com/uploads/default/original/2X/4/47874f39340de03ff5ac43c5512f034225f96c93.png) - 或者，A不严格支配B，即A==B： ![image](https://forum.90sec.com/uploads/default/original/2X/a/aea37a08267943b3f4222711e96ec3266b7c9f91.png) ``` 对于任意赋值语句`x=...`所在的节点A，在A的所有支配边界插入 $\phi$ 。 ``` 对任意变量i，令 A 为所有对 i 赋值的节点，节点 a\in A ， DF(a) 为 a 的支配边界集合， DF^+(A) 为所有需要插入 \phi(i) 的节点： - \mathrm{DF}(\mathrm{A})=\mathrm{U}\_{\{\mathrm{a} \in \mathrm{A}\}} \mathrm{DF}(\mathrm{a}) - \mathrm{DF}^{+}(\mathrm{A})=\lim \_{i \rightarrow \infty} D F^{i}(A) - DF^{1}(A)=DF(A) - DF^{i+1}(A)=D F\left(\cup\_{j \leq i} DF^{j}(A)\right) ## 计算支配边界 计算直接支配者（immediate dominator）：a严格支配b，并且不存在c，a严格支配c且c严格支配b， 则a是b的直接支配者，记为idom(b) 直接支配关系实际上是一个树，即支配树，支配树可以反映支配边界： ![image-20201003170259206](https://forum.90sec.com/uploads/default/original/2X/5/5ef0f62b0d7bd35af193951521964c1a46c5a813.png) 计算支配树的算法有两种： - Lengauer and Tarjan算法 - 复杂度为 O(E\alpha(E,N)) - E为边数，N为结点数，𝛼 为Ackerman函数的逆（Ackerman函数基本可以认为是常数） - Cooper, Harvey, Kennedy算法 - 复杂度为 O(N^2) ，实际比 Lengauer and Tarjan 快 # 静态单赋值的限制和实际做法 SSA需要每个内存位置一旦赋值，其值都不会发生改变，但是在指针操作时并不满足，例如下面C代码的指针操作： ```c a=10; i=&a; *i=20; b=a; // b=? /* to SSA */ a=10; i=&a; *i=20; b=a; // b=10 ``` 将其翻译成SSA之后，可以看到b值实际上被变量 i 影响，但是SSA没法反应这个信息，因此分析下来 b=10 ，这种情况在java也存在： ```java a.f=10; y=a; y.f=20; b=a.f; // b=? /* to SSA */ a.f=10; y=a; y.f=20; b=a.f; // b=10 ``` 因此在实际使用时，会做部分SSA，只对能转换的组做优化。 对于Java来说，栈上的变量为优化组，堆上的变量为不优化组； 对于C的情况：和top-level（从没被&取过地址的变量）为优化组，address-taken（曾经被&取过地址的变量 ）为不优化组。 # Reference - 软件分析技术，北京大学，[https://xiongyingfei.github.io/SA/2019/05\_static\_single\_assignment.pdf](https://xiongyingfei.github.io/SA/2019/05_static_single_assignment.pdf) ---
作者： ![maplgebra](https://forum.90sec.com/user_avatar/forum.90sec.com/maplgebra/32/1628_2.png) [@maplgebra](https://forum.90sec.com/u/maplgebra)\ 发布日期： [2020 年10 月 4 日 05:11 UTC](https://forum.90sec.com/t/topic/1321/2 "2020-10-04T05:11:11Z")
_dominator tree_ 是个好东西，它帮我做了很多东西，文中提到是普遍的正向支配树，还有一个 _post dominator tree_. 想要了解_dominator tree_，参考这篇文章[A Simple, Fast Dominance Algorithm](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4A8AE201BE0995509D5882032A26EA47?doi=10.1.1.14.3249&rep=rep1&type=pdf) llvm 的ir也是用的ssa，但是因为ssa的限制，llvm用了phi和alloca(居多)来解决。 ~~让我来当你的小助手吧~~ Hahahahahahahha ---
作者： ![panda](https://forum.90sec.com/user_avatar/forum.90sec.com/panda/32/4495_2.png) [@panda](https://forum.90sec.com/u/panda)\ 发布日期： [2020 年10 月 4 日 11:15 UTC](https://forum.90sec.com/t/topic/1321/3 "2020-10-04T11:15:59Z")
膜师傅啊 这玩意对于一些项目开发在算法上帮助是巨大的 过一段时间要研究相关的东东 mark 一下 ---
作者： ![dongting](https://forum.90sec.com/letter_avatar_proxy/v4/letter/d/e8c25b/32.png) [@dongting](https://forum.90sec.com/u/dongting)\ 发布日期： [2020 年10 月 4 日 14:58 UTC](https://forum.90sec.com/t/topic/1321/4 "2020-10-04T14:58:56Z")
赞啊，感觉90会有良好的学术氛围。先mark后面学习下 ---
作者： ![maplgebra](https://forum.90sec.com/user_avatar/forum.90sec.com/maplgebra/32/1628_2.png) [@maplgebra](https://forum.90sec.com/u/maplgebra)\ 发布日期： [2020 年10 月 4 日 15:03 UTC](https://forum.90sec.com/t/topic/1321/5 "2020-10-04T15:03:57Z")
欢迎， 信安不止眼前的苟且，还有未知的远方。 ---
作者： ![anemone](https://forum.90sec.com/letter_avatar_proxy/v4/letter/a/46a35a/32.png) [@anemone](https://forum.90sec.com/u/anemone)\ 发布日期： [2020 年10 月 5 日 08:50 UTC](https://forum.90sec.com/t/topic/1321/6 "2020-10-05T08:50:22Z")
太厉害了 ddw