Composing Dataflow Analyses and Transformations
The
29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
(POPL 2002),
Portland, Oregon, January 16-18, 2002.
Sorin Lerner,
David Grove and
Craig Chambers
Dataflow analyses can have mutually beneficial interactions.
Previous efforts to exploit these interactions have either (1)
iteratively performed each individual analysis until no further
improvements are discovered or (2) developed ``super-analyses'' that
manually combine conceptually separate analyses. We have devised a new
approach that allows analyses to be defined independently while still
enabling them to be combined automatically and profitably. Our
approach avoids the loss of precision associated with iterating
individual analyses and the implementation difficulties of manually
writing a super-analysis. The key to our approach is a novel method of
implicit communication between the individual components of a super-analysis
based on graph transformations. In this paper, we precisely define our
approach; we demonstrate that it is sound and it terminates; finally
we give experimental results showing that in practice (1) our
framework produces results at least as precise as iterating the
individual analyses while compiling at least 5 times faster, and (2)
our framework achieves the same precision as a manually written
super-analysis while incurring a compile-time overhead of less than
20%.
To get the paper, click
here.
Cecil/Vortex
Project