Finite differencing replaces repeated computation of an expensive function f(i) with computation of incremental changes in f(i) from its previous value.
Finite differencing has several advantages:
Components of the transformation:
Example: Optimization of subscript expressions: Consider the following program fragment with an array reference inside a loop:
var x: array[1..100] of real; for i := 1 to 100 do x[i] ...
The compiler will produce intermediate code such as the following.
i := 1 L7: if ( i <= 100 ) x[i*8 - 8] ... i := i + 1 goto L7
We will assume that the subscript expression f(i) = i*8 - 8 is an expensive expression that we would like to replace. Introduce a new variable E = i*8 - 8 and add code to update E whenever i is updated so that this relationship always holds:
i := 1 E := 0 L7: if ( i <= 100 ) x[E] ... i := i + 1 E := E + 8 goto L7If we change the test of i to a test of E, then code involving i becomes dead code that can be eliminated:
E := 0 L7: if ( E <= 792 ) x[E] ... E := E + 8 goto L7Now the code is simpler, and the expensive operation has been obtained at no runtime cost.