Parallelizing Top-Down Interprocedural Analyses

Modularity is a central theme in any scalable program analysis. The core idea in a modular analysis is to build summaries at proce-dure boundaries, and use the summary of a procedure to analyze the effect of calling it at its calling context. There are two ways to perform a modular program analysis: (1) top-down and (2) bottom-up. A bottom-up analysis proceeds upwards from the leaves of the call graph, and analyzes each procedure in the most general calling context and builds its summary. In contrast, a top-down analysis starts from the root of the call graph, and proceeds downward, an-alyzing each procedure in its calling context. Top-down analyses have several applications in verification and software model check-ing. However, traditionally, bottom-up analyses have been easier to scale and parallelize than top-down analyses. In this paper, we propose a generic framework, BOLT, whic