Deferred Data-Flow Analysis

Loss of precision due to the conservative nature of compile-time dataflowanalysis is a general problem and impacts a wide variety of optimizations. Wepropose a limited form of runtime dataflow analysis, called deferred dataflowanalysis (DDFA), which attempts to improve precision by performing most of theanalysis at compile-time and using additional information at runtime tostitch together information collected at compile-time. Wepresent an interprocedural DDFA framework that is applicable for arbitrarycontrol structures including multi-way forks, recursion, separately compiledfunctions and higher-order functions. We present algorithms for constructionof region summary functions and for composition and application of thesefunctions. Dividing the analysis in this manner raises two concerns: (1) isit possible to generate correct and compact summary functions for regions? (2)is it possible to correctly and efficiently compose and apply these functionsat run-time? To address these concerns, we show that DDFA terminates, is safeand provides good results.