Deferred Data-flow Analysis
Shamik Sharma
Anurag Acharya
Joel Saltz
Submitted for publication.
Abstract:
Loss of precision due to the conservative nature of compile-time
dataflow analysis is a general problem and impacts a wide variety of
optimizations. We propose a limited form of runtime dataflow
analysis, called deferred dataflow analysis (DDFA), which attempts to
improve precision by performing most of the analysis at compile-time
and using additional information at runtime to {\em stitch} together
information collected at compile-time. We present an interprocedural
DDFA framework that is applicable for arbitrary control structures
including multi-way forks, recursion, separately compiled functions
and higher-order functions. We present algorithms for construction of
{\em region} summary functions and for composition and application of
these functions. Dividing the analysis in this manner raises two
concerns: (1) is it possible to generate correct and compact summary
functions for regions? (2) is it possible to correctly and
efficiently compose and apply these functions at {\em run-time}? To
address these concerns, we show that DDFA terminates, is safe and
provides good results.
Postscript
(compressed 73K). Also available as UCSB TRCS98-03.
A more detailed version is available as