The performance of the memory hierarchy, and in particular the data
cache, can significantly impact program execution speed.
Thus, instruction reordering to minimize data cache misses is an
important consideration for optimizing compilers.
In this paper, we prove that the problem of instruction reordering for
data cache miss minimization belongs to the class of NP-complete
problems. 
The framework that we develop for the proof
exposes the symbiotic relationship among the references to the cache.
This symbiosis exists because a single cache reference lengthens the
life span of its neighbors in the cache and thus provides opportunity
for additional cache hits through reference to the neighbors.
We present a greedy heuristic designed to exploit
this symbiotic relationship to improve data cache performance for
general purpose programs.
Experiments with a prototype implementation of
the heuristic show that we can improve data cache performance in
many cases.