Strengthening Invariants for Efficient Computation
Yanhong A. Liu, Scott D. Stoller, and Tim Teitelbaum
This paper presents program analyses and transformations for
strengthening invariants for the purpose of efficient computation.
Finding the stronger invariants corresponds to discovering a general
class of auxiliary information for any incremental computation problem.
Combining the 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.
BiBTeX
gzip'd
PostScript
PostScript
Scott Stoller's Home Page