Next: Incorporating Feedback into
Up: Achieving Larger Gains
Previous: Achieving Larger Gains
The analysis techniques presented so far have relied strictly upon static information that is available during compilation. This static
analysis could be further improved in the following ways. First, the basic
concept of locality analysis, i.e. 
can be
generalized to handle other types of reference patterns, such as scalars,
pointers, lists, etc. For example, two pointer dereferences would have
intrinsic data reuse if the compiler can determine that they point to the
same address. The localized execution space for a given reference would be
the set of paths in the control-flow graph that can lead to that reference
without accessing enough data to flush the cache. If a given reference
reuses data from an earlier reference, and that earlier reference falls
within the localized execution space of the given reference, then there is
data locality. Second, the analysis could be performed on a global
level rather than a loop-nest level. The largest gains from improving
static analysis are likely to come from prefetching large recursive data
structures, such as the trees and linked lists we saw in BARNES and PTHOR
in Section 
, and from performing interprocedural
analysis, which was important for WATER (as also described in
Section ). However, analyzing recursive data
structures may be quite difficult since it usually requires pointer
analysis, which is a difficult problem for the compiler in
general [51][37].
Rather than relying strictly upon static information, another possibility
is to make use of dynamic information. Dynamic information could be
used either at compile-time, through the use of feedback information, or at
run-time, by generating adaptive code. We will discuss both possibilities
in this subsection.