Next: Incorporating Feedback into Up: Achieving Larger Gains Previous: Achieving Larger Gains

Improving Analysis

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.

Sat Jun 25 15:13:04 PDT 1994