Deferred Data-Flow Analysis

Loss of precision due to the conservative nature of compile-time dataflowanalysis impacts a wide variety of optimizations. In this paper, we propose ageneral framework which combines compile-time analysis with limited runtimeanalysis to improve the precision of dataflow information atperformance-critical points in the program. This technique, which we refer toas deferred dataflow analysis (DDFA), performs most of the analysis atcompile-time but defers the final stages of the analysis till runtime whenadditional information is available.We present algorithms for construction of region summary functions and forcomposition and application of these functions. Dividing the analysis in thismanner raises two concerns: (1) is it possible to generate correct and compactsummary functions for regions? (2) is it possible to correctly and efficientlycompose and apply these functions at run-time? To address these concerns, weshow that DDFA terminates, is safe and that its results are at least as good asa compile-time meets-over-all-paths solution. To address concerns regardingthe size of the data-structures used to communicate information from thecompiler to the runtime system, we present space requirements of DDFA in thecontext of three different backward data-flow analyses. To address concernsregarding the runtime overhead of DDFA and to demonstrate the ability of DDFAto optimize heavy-weight operations, we present results from the application ofDDFA for two of these analyses.