Reuse analysis attempts to discover those instances of array accesses
that refer to the same cache line. There are three kinds of reuse:
temporal, spatial and group. In the above example, we say that the
reference `A[i][j]` has *spatial reuse* within the innermost
loop since the same cache line is used by two consecutive iterations in
the innermost loop. The reference `B[j][0]` has *temporal
reuse* in the outer loop since iterations of the outer loop refer to
the same locations. Lastly, we say that different accesses `B[j][0]` and `B[j+1][0]` have *group reuse* because many of
the instances of the former refer to locations accessed by the latter.

Trying to determine accurately all the iterations that use the same
data is too expensive. We can succinctly capture our intuitive
characterization that reuse is carried by a specific loop with the
following mathematical formulation. We represent an -dimensional
loop nest as a polytope in an -dimensional iteration space, with
the outermost loop represented by the first dimension in the space.
We represent the shape of the set of iterations that use the same data
by a *reuse vector space*[29].

For example, the access of `b[j][0]` in our example is represented as
`B(``)`, so reuse
occurs between iterations
and whenever
That is, temporal reuse occurs whenever the difference between the
two iterations lies in the nullspace of
, that is,
. We refer to this vector space as the
temporal reuse vector space. This mathematical approach succinctly
captures the intuitive concept that the direction of reuse of `B[j][0]` lies along the outer loop. This approach can handle more
complicated access patterns such as `C[i+j]` by representing their
reuse vector space as .

Similar analysis can be used to find spatial reuse. For reuse among
different array references, Gannon *et al*. observe that data reuse is
exploitable only if the references are *uniformly generated*; that
is, references whose array index expressions differ in at most the
constant term[11]. For example, references `B[j][0]` and `B[j+1][0]` are uniformly generated; references `C[i]` and `C[j]` are not. Pairs of uniformly generated references
can be analyzed in a similar fashion[29]. For our
example in Figure 2(a), our algorithm will determine that `A[i][j]` has spatial reuse on the inner loop, and both `B[j][0]`
and `B[j+1][0]` share group reuse and also have temporal reuse on
the outer loop.