Discovering Auxiliary Information for Incremental Computation
Yanhong A. Liu, Scott D. Stoller, and Tim Teitelbaum
Abstract:
This paper presents program analyses and transformations that discover
a general class of auxiliary information for any incremental
computation problem. Combining these techniques with previous
techniques for caching intermediate results, we obtain a systematic
approach that transforms non-incremental programs into efficient
incremental programs that use and maintain useful auxiliary
information as well as useful intermediate results. The use of
auxiliary information allows us to achieve a greater degree of
incrementality than otherwise possible. Applications of the approach
include strength-reduction in optimizing compilers and finite
differencing in transformational programming.
Scott Stoller's Home Page