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 Cheetah, 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 without any additional synchronization, 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 in C/C++ programs.
We evaluate Cheetah on a series of standard benchmark programs and open-source projects, which demonstrates significant speedup over a conventional parallel design.
Fri 10 Jul Times are displayed in time zone: (UTC) Coordinated Universal Time change
|08:05 - 08:17|
|08:17 - 08:29|
|08:29 - 08:37|
|08:37 - 08:45|
Roman HaasCQSE GmbH, Rainer NiedermayrCQSE GmbH, Tobias RoehmCQSE GmbH, Sven ApelSaarland UniversityPre-print
|08:45 - 08:53|
|08:53 - 09:01|