Recurrences for representing the results of induction variables (scalar evolution)

A recurrence involves a <InitialValue, Operation, Step>. Consider the following program:

int A[..];
for (i = 0; i < n; i++) { //L
  p = &A[i];
  *p = ...;
}

Here, the variable p can be represented through a recurrence as {&A, +, 4}<L>.

Another example:

char A[100][200];
for (i = 1 to 100) // L0
  for (j = 1 to 200) //L1
     p = &A[i][j];
     *p = ...

Here, the variable p can be represented through a recurrence as {{&A, +, 200}<L0>, +, 1}<L1>. The initial value of the recurrence corresponding to L1 (inner loop) is given by a recurrence corresponding to L0 (outer loop).

Another example:

for (i = 0; i < n; i++) {
  j = i*i;
}

In this example, i can be represented by {0,+,1}<L>, and j can be represented by {0,+,{1,+,2}<L>}<L>. Notice that L appears twice for a quadratic relation, such that j=0+\sum_i{1+2*i}. This can be extended to an arbitrary polynomial.

This can be further generalized to other operators, e.g., multiplication.

Why would we want to represent variables as recurrences?

Because they provide a high-level structure composed of small computations as a function of the iteration count of a loop hierarchy. It does not loose information; in fact it recovers information, and it can always be converted back to its unstructured form (e.g., polynomial).
Equally importantly, they provide a canonical representation for a scalar variable that is seen to be evolving as the loop iterations execute. A canonical representation facilitates efficient comparisons, analyses, and transformations.

What is the algorithm to convert a quadratic or a polynomial to its recurrence? While a precise algorithm is out of scope for this discussion, such decomposition of a polynomial expression into linear expressions is based on well-known algebraic identities.

Loop trip count

If the loop exit condition is i<n and the transfer function of a loop body indicates that i is a basic induction variable, s.t., m1(i) = m0(i) + c, then the loop trip count can be identified as (n > i) ? floor((n - i0)/c) : 0, where i0 is m0(i) [the mapping for i at loop entry before the first iteration. Notice that the loop exit condition itself is based on the summary transfer function of the loop body (it may be the result of the composition of multiple individual instructions).