Optimizations performed at link-time or directly applied to final program executables have received increased attention in recent years. We discuss the discovery and elimination of redundant memory operations in the context of a link-time optimizer, an optimization that we call memory redundancy elimination (MRE). Previous research showed that existing MRE techniques are mainly based on path-insensitive information, which causes many MRE opportunities to be lost. We present a new technique for eliminating redundant loads in a path-sensitive fashion, by using a novel alias analysis algorithm that is able to expose path-sensitive memory redundancies. We also extend our previous work by removing both redundant and dead stores. Our experiments show that around 75% of load and 10% of store references in a program can be considered redundant, because they are accessing memory locations that have been referenced less than 256 memory instructions away. By combining our previous optimizations for eliminating load redundancies with the new techniques developed, we show that around 18% of the loads and 8% of the stores can be detected and eliminated, which translates into a 10% reduction in execution time.

Abstract Optimizations performed at link time or directly applied to final program executables have received increased attention in recent years. This paper discusses the discovery and elimination of redundant load operations in the context of a link‐time optimizer, an optimization that we callLoad Redundancy Elimination (LRE). Our experiments show that between 50% and 75% of a program's memory references can be considered redundant because they are accessing memory locations that have been referenced less than 200–400 instructions away. We then present three profile‐based LRE algorithms targeted at optimizing away these redundancies. Our results show that between 5% and 30% of the redundancy detected can indeed be eliminated, which translates into program speedups of around 8%. We also test our algorithm assuming different cache latencies, and show that, if latencies continue to grow, the load redundancy elimination will become more important. Copyright © 2003 John Wiley & Sons, Ltd.