2020-Pipelining Bottom-up Data Flow Analysis

[skyleaworlder]

https://dl.acm.org/doi/10.1145/3377811.3380425

Qingkai Shi The Hong Kong University of Science and Technology Hong Kong, China qshiaa@cse.ust.hk
Charles Zhang The Hong Kong University of Science and Technology Hong Kong, China charlesz@cse.ust.hk

ICSE '20

from @Ling-WYJ

[skyleaworlder]

传统 modular analysis 是给函数做 summary，根据调用关系明确构建 summary 的顺序，进而通过排序做到并行。

本文认为为单个函数生成 summary 的过程可以拆分成多个 sub-tasks，同样可以做到并行。并以 IFDS / IDE 框架为基础，并行化生成可用于 null dereference 和 taint analysis 检查的 summary。（下图 fig 2 就是将一个 summary 的构建拆分成了 3 个阶段，结果是获得了更细粒度的流水线，最理想情况下加速 150%）

[skyleaworlder]

如果将待分析的函数称为 current function，调用 current function 的函数称为 caller，current function 调用的函数称为 callee，那么本文将创建 summary 分成了 3 个步骤：

1. caller 处创建的 data fact 传入到了 current function，（后面不知道经历了什么），反正又传回了 caller；
2. current function 中创建的 data fact，（后面不知道经历了什么），反正传回了 caller；
3. callee 中创建的 data fact 传到了 current function 中，然后又继续传到了 caller。

如果称 current function 为 $f$ ，那么上述三点又记为 $f_0$ , $f_1$ , $f_2$。就比如 fig 5 中，bar 并没有调用其他函数，所以不存在 $bar_2$，同样的，foo 函数并没有参数，即便调用也不会从 caller 中流入 data fact，所以没有 $foo_0$。

[skyleaworlder]

在 IFDS 中，summary 是将整个待分析 function 的图 “compact-化” 之后的结果 (compact representation)，也就是 “折叠” 了整个 function 对应的 graph。众所周知，IFDS 中每个调用了的 function 都有一个 entry node $e_f$ 和一个 exit node $x_f$ ，那么该函数 f 的 summary 可以表示成 $S_f = \left\{ (e_f, \textbf{a}) \to (x_f, \textbf{b}) : \textbf{a}, \textbf{b} \in D_f \right\}$。$S_f$ 是一个集合，里面存着一系列 entry node 到 exit node 连接的边。

为什么本文将 summary 划分成了上面那三个子类，(1) 首先肯定是因为在 IFDS 的 summary 表示法中，上面那三个子类加起来就是整个 summary；(2) 其次是因为这三类在该 summary 表示法中非常好做区分：

1. 首先， f 这个函数的 data fact 有 0 以及 a, b, c 之类的。$(e_f, \textbf{a})$ 表示非 0 的 data fact，也就是表示这个 data fact 是从外部传进来的。
2. 如果是 0 开始，也就意味着 “这次计算看的不是外部传入的 data fact”。从 0 开始往下看，可达节点是 current function 中新创建的 data fact。如果说其中一个 data fact 调用了某 callee，并最终流到 current function 的 exit node 上，接着传出到 caller。这正是上面提的第 2 个步骤。
3. 如果对于 callee 也从 0 开始，也就意味着 “这次计算看的不是外部传入的 data fact”，而是看的 callee 本身创建的 data fact。并且这个 data fact 要流回到 f 的 exit node 中，接着传出到 caller。这正是上面提到的第 3 个步骤。

由此可见，上述三点将 “外部传入”、“本地创建” 以及 “调用函数创建” 三种情况列举了出来，并且这三种情况在 IFDS 的 graph 上有很明显的特征（有关于 0 这个 data fact）。也正因此，三者可以并行，因为三者两两之间不存在任何依赖关系。

[skyleaworlder]

文中 3.5 提到，一般情况下 $S_g^0$ 和 $S_g^1$ 两个集合可能比 $S_g^2$ 要大得多，所以为了进一步加速，可以对这两个集合中涉及到的 data fact 再做 partition。文中提出的就是最简单的划分方式——给一个偶数，然后从 entry node 的 data fact 平均分。

但问题在于 $S_g^0$ 这么做可以，但 $S_g^1$ 都是从 0 开始流下来的。所以文中给出的解决方案就是不看 0，而是看那些 immediate predecessor 是 0 的节点。与此类似的，看 $S_g^2$ 自然是看那些 “immediate predecessor 来自 callee，并且创建了 data fact” 的。

[skyleaworlder]

这个图的 speedup 是 (Coyote 比上正常开多线程 - 1)。按道理说，如果 f0 / f1 / f2 三段时间长度相等，那图中的 speedup 应该在 2.0 以上，因为 2.0 是三段相等的最糟糕情况。但是正如文中所说的 f0 和 f1 的时间要远远长于 f2，但是在流水线里还必须先计算 f0 和 f1，这对加速比产生了不小的影响，不过文中提出 “将 f0 / f1 内部将 data fact 分组计算” 又可以显著减少 f0 / f1 的长度。再搭配上本身就存在的函数级别的并行，speedup 就来到了 3.0。

本文提出的方法和传统的 function level 的调度策略和计算方式是正交的，也就是说本文的方法可以作用在所有 function level 方法上面并再进行加速。

后文对本文提出方法进行了讨论：对于一个调用图，一般来说在叶子处，互相调用关系比较简单；而越靠近程序入口，调用关系越复杂。这体现在调用边的稠密上。

• 调用关系如果稀疏，那么传统方法和本方法差别不大，因为传统也可以解决 function level 的并行，本方法的优化点不在这里；
• 调用关系如果密集，本方法将带来显著的提升效果。