The SUIF compiler performs interprocedural constant propagation to
statically determine as many loop bounds as possible. The loop bounds are
often needed to determine the volume of data accessed by each loop, which
in turn is used to decide whether a loop is within the localized
iteration space (see the algorithm in Figure 
).
When the loop bounds remain unknown, the compiler may be faced with
deciding whether an unknown volume of data fits within the cache. To
resolve such cases, our algorithm uses one of two policies: either (i)
unknown loop counts are assumed small, and hence the data would tend to fit
in the cache; or (ii) unknown loop counts are assumed large, and therefore
the data would tend not to fit. For our experiments in the previous
section, we consistently used the former policy of assuming unknown loop
counts to be small, which tends to overestimate what remains in the cache.
We now compare this with the latter policy of assuming unknown loop counts
to be large.
When the compiler assumes unknown iteration counts to be large rather than
small, it produces identical code for 11 of the 13 benchmarks-the two
benchmarks that change are OCEAN and MG. For OCEAN, the difference in
performance is negligible. However, MG performs 4%worse with the
large-loop policy, as shown in Figure (a). In this
case, the benefit of the extra prefetches is more than offset by increased
instruction overhead. Although assuming small loop counts happens to be
better in this case, the opposite could easily be true in programs where
unknown iteration counts are actually large. One solution may be to resolve
loop counts through profiling feedback or to generate adaptive code, as we
will discuss later in Section . However, the
more interesting result of this experiment is how rarely loop bound
uncertainty affects performance. We observe that while nearly half the
benchmarks contain loops with unknown bounds, in most cases this has no
impact on locality, due to the patterns of data reuse within those loops.
