An efficient static analysis algorithm to detect redundant memory operations

Abstract

As memory system performance becomes an increasingly dominant factor in overall system performance, it is important to optimize programs for memory related operations. This paper concerns static analysis to detect redundant memory operations and enable other compiler transformations to remove such redundant operations.We present an extended global value numbering algorithm to detect redundant memory operations. The key of the new algorithm is a novel SSA-based representation for memory state which allows accurate reasoning about memory state. Using this representation, the algorithm can trace values through memory operations to detect equivalence in the same way that it traces them through register-based scalar operations. Thus it discovers both redundancy involving scalar values and redundancy involving memory operations. The redundancy relation detected by the algorithm can then be used by traditional redundancy elimination transformations to remove those redundant operations.Experiments using a suite of realistic applications demonstrate the algorithm is powerful and fast. In practice, it has essentially linear time complexity.

References

1. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
2. Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables in programs. In Conference Record of ACM Symposium on Principles of Programming Languages (POPL), pages 1--11, 1988.
3. Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, University of Copenhagen, 1994.
4. Rastislav Bodik and Sadun Anik. Path-sensitive value-flow analysis. In Conference Record of ACM Symposium on Principles of Programming Languages (POPL), pages 237--251, 1998.
5. Rastislav Bodik, Rajiv Gupta, and Mary Lou Soffa. Complete removal of redundant expressions. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 1--14, 1998.
6. Rastislav Bodik, Rajiv Gupta, and Mary Lou Soffa. Load-reuse analysis: Design and evaluation. In Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation, pages 64--76, 1999.
7. Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. Value numbering. Software Practice and Experience, 27(6):701--724, June 1997.
8. Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. Value numbering. Software---Practice and Experience, 27(6):701--724, June 1997.
9. Jiazhen Cai and Robert Paige. Using multiset discrimination to solve language processing problems without hashing. Theoretical Computer Science, 145(1&2):189--228, 1995.
10. Jong-Deok Choi, Michael Burke, and Paul Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Conference Record of ACM Symposium on Principles of Programming Languages (POPL), 1993.
11. F. Chow, S. Chan, S. Liu, R. Lo, and M. Streich. Effective representation of aliases and indirect memory operations in ssa form. In Compiler Construction, pages 253--267, 1996.
12. Cliff Click and Keith D. Cooper. Combining analyses, combining optimizations. ACM Transactions on Programming Languages and Systems (TOPLAS), 17(2):181--196, March 1995.
13. John Cocke. Global common subexpression elimination. SIGPLAN Notices, 5(7):20--24, July 1970. In Proceedings of a Symposium on Compiler Construction.
14. Ron Cytron and Reid Gershbein. Efficient accomodation of may-alias information in ssa-form. In Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation, pages 36--45, 1993.
15. Manuvir Das. Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 35--46, 2000.
16. Alain Deutsch. Interprocedural May-Alias analysis for pointers: Beyond k-limiting. In Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, pages 230--241, 1994.
17. Andrei P. Ershov. On programming of arithmetic expressions. Communications of the ACM, 1(8):3--6, August 1958. The figures appear in volume 1, number 9, page 16.
18. S.P. Harbison. An architecture alternative to optimizing compilers. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 57--65, 1982.
19. John B. Kam and Jeffrey D. Ullman. Global data flow analysis and iterative algorithms. Journal of the ACM, 23(1):158--171, January 1976.
20. Jens Knoop, Oliver Rüthing, and Bernhard Steffen. Lazy code motion. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation, pages 224--234, 1992.
21. William Landi and Barbara G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation, pages 235--248, 1992.
22. Chunho Lee, Miodrag Potkonjak, and William H. Mangione-Smith. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems. In International Symposium on Microarchitecture, pages 330--335, 1997.
23. M.H. Lipasti, C.B. Wilkerson, and J.P. Shen. Value locality and load value prediction. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 138--147, 1996.
24. Raymond Lo, Fred Chow, Robert Kennedy, Shin-Ming Liu, and Pang Tu. Register promotion by sparse partial redundancy elimination of loads and stores. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 26--37, 1998.
25. John Lu and Keith Cooper. Register promotion in c programs. In Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation, pages 308--319, 1997.
26. E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Commun. ACM, 22(2):96--103, 1979.
27. G. Ramalingarn, John Field, and Frank Tip. Aggregate structure identification and its application to program analysis. In Conference Record of ACM Symposium on Principles of Programming Languages (POPL), pages 119--132, 1999.
28. Erik Ruff Context-insensitive alias analysis reconsidered. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, pages 13--22, 1995.
29. Barbara G. Ryder, William A. Landi, Philip A. Stocks, Sean Zhang, and Rita Altucher. A schema for interprocedural modification sid-effect analysis with pointer aliasing. ACM Transactions on Programming Languages and Systems (TOPLAS), 23(2), March 2001.
30. A. Sastry and Roy Ju. A new algorithm for scalar register promotion based on ssa form. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, pages 15--25, 1998.
31. Taylor Simpson. Value-Driven Redundancy Elimination. PhD thesis, Rice University, 1996.
32. Avinash Sodani and Gurinder S. Sohi. Dynamic instruction reuse. In International Symposium on Computer Architecture, pages 194--205, 1997.
33. SPEC. http://www.specbench.org/osg/cpu2000/cint2000/.
34. Bjarne Steensgaard. Points-to analysis in almost linear time. In Conference Record of ACM Symposium on Principles of Programming Languages (POPL), pages 32--41, 1996.
35. Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2):181--210, 1991.
36. Robert P. Wilson and Monica S. Lain. Efficient context-sensitive pointer analysis for c programs. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming Language Design and Implementation, pages 1--12, 1995.
37. J. Yang and R. Gupta. Load redundancy removal through instruction reuse. In International Conference on Parallel Processing, pages 61--68, 2000.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers