一句话：提出 Coyote 框架，通过将函数分析划分为可流水线化子任务，在调用依赖下实现自底向上数据流分析的并行加速。
自底向上程序分析天然易于并行，因为无调用关系的函数可独立分析。但调用依赖严重限制函数级并行：被调函数的分析摘要必须先完成。作者观察到调用依赖在许多情况下可以放松，提出 Coyote 框架，将每个函数的分析任务精心划分为多个子任务，以生成可流水线化的函数摘要；这些子任务即使存在调用依赖也可流水线并行执行。该思想在 IFDS/IDE 框架下形式化，并实现为 C/C++ 空指针解引用与污点检查。在标准基准和开源系统上评估，相比常规并行设计取得显著加速。
Bottom-up program analysis has been traditionally easy to parallelize because functions without caller-callee relations can be analyzed independently. However, such function-level parallelism is significantly limited by the calling dependence - functions with caller-callee relations have to be analyzed sequentially because the analysis of a function depends on the analysis results, a.k.a., function summaries, of its callees. We observe that the calling dependence can be relaxed in many cases and, as a result, the parallelism can be improved. In this paper, we present Coyote, a framework of bottom-up data flow analysis, in which the analysis task of each function is elaborately partitioned into multiple sub-tasks to generate pipelineable function summaries. These sub-tasks are pipelined and run in parallel, even though the calling dependence exists. We formalize our idea under the IFDS/IDE framework and have implemented an application to checking null-dereference bugs and taint issues in C/C++ programs. We evaluate Coyote on a series of standard benchmark programs and open-source software systems, which demonstrates significant speedup over a conventional parallel design.
DOI 原文 ·
@inproceedings{paperbot5638,
title = {Pipelining bottom-up data flow analysis},
author = {Qingkai Shi and Charles Zhang},
booktitle = {ICSE},
year = {2020},
doi = {10.1145/3377811.3380425}
}