Discovering Auxiliary Information for Incremental Computation
Yanhong A. Liu, Scott D. Stoller, and Tim Teitelbaum


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