Improving instruction cache behavior by reducing cache pollution

Compiler techniques for improving instruction cache performance are described. Through repositioning of the code in the main memory, leaving memory locations unused, code duplication, and code propagation, the effectiveness of the cache can be improved due to reduced cache pollution and fewer cache misses. Results of experiments indicate that significant reduction in bus traffic results from the use of these techniques. Since memory bandwidth is a critical resource in shared memory multiprocessors, such systems can benefit from the techniques described. The notion of control dependence is used to decide when instructions belonging to different basic blocks can be allowed to share the same cache line without increasing cache pollution