Strengthening invariants for efficient computation

This paper presents program analyses and transformations for strengthening invariants for the purpose of efficient computation. Finding the stronger i nvariants corresponds to discovering a general class of auxiliary informati on for any incremental computation problem. Combining the techniques with p revious techniques for caching intermediate results, we obtain a systematic approach that transforms non-incremental programs into efficient increment al programs that use and maintain useful auxiliary information as well as u seful intermediate results. The use of auxiliary information allows us to a chieve a greater degree of incrementality than otherwise possible. Applicat ions of the approach include strength reduction in optimizing compilers and finite differencing in transformational programming. (C) 2001 Elsevier Sci ence B.V. All rights reserved.