An Improved Algorithm for Redundancy Detection Using Global Value Numbering
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Global value numbering (GVN) is a method for detecting equivalent expressions in programs. Most of the GVN algorithms concentrate on detecting equalities among variables and hence, are limited in their ability to identify value-based redundancies. In this paper, we suggest improvements by which the efficient GVN algorithm by Gulwani and Necula (2007) can be made to detect expression equivalences that are required for identifying value based redundancies. The basic idea for doing so is to use an anticipability-based Join algorithm to compute more precise equivalence information at join points. We provide a proof of correctness of the improved algorithm and show that its running time is a polynomial in the number of expressions in the program.
Abstract
Global value numbering (GVN) is a method for detecting equivalent expressions in programs. Most of the GVN algorithms concentrate on detecting equalities among variables and hence, are limited in their ability to identify value-based redundancies. In this paper, we suggest improvements by which the efficient GVN algorithm by Gulwani and Necula (2007) can be made to detect expression equivalences that are required for identifying value based redundancies. The basic idea for doing so is to use an anticipability-based Join algorithm to compute more precise equivalence information at join points. We provide a proof of correctness of the improved algorithm and show that its running time is a polynomial in the number of expressions in the program.
참고문헌 (16)
- S. Gulwani, "A polynomial-time algorithm for global value numbering", Science of Computer Programming, 64(1), pp.97~114 (2007)
- B. K. Rosen, "Global value numbers and redundant computations", Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL1988), pp.12~27 (1988)
- O. Ruthing, "Static Analysis", pp.232~247 (1999), Springer
- G. A. Kildall, "A unified approach to global program optimization", Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL1973), pp.194~206 (1973)
- A. W. Appel, "Modern Compiler Implementation in Java" (2002), Cambridge University Press
- S. S. Muchnick, "Muchnick, Advanced Compiler Design Implementation" (1997), Morgan Kaufmann Publishers
- B. Alpern, "Detecting equality of variables in programs", Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL1988), pp.1~11 (1988)
- J. Knoop, "Lazy code motion", Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI1992), pp.224~234 (1992)
- E. Morel, "Global optimization by suppression of partial redundancies", Communications of the ACM, 22(2), pp.96~103 (1979)
- V. K. Paleri, "Partial redundancy elimination : a simple, pragmatic, and provably correct algorithm", Science of Computer Programming, 48(1), pp.1~20 (2003)
- P. Briggs, "Value numbering", Software-Practice and Experience, 27(6), pp.701~724 (1997)
- T. VanDrunen, "Compiler Construction", pp.167~184 (2004), Springer
- K. Gargi, "A sparse algorithm for predicated global value numbering", ACM SIGPLAN Notices, 37(5), pp.45~56 (2002)
- J. T. Nie, "Programming Languages and Systems", pp.319~334 (2007), Springer
- R. Cytron, "Efficiently computing static single assignment form and the control dependence graph", ACM Transactions on Programming Languages and Systems, 13(4), pp.451~490 (1991)
- B. Steffen, "The value flow graph: a program representation for optimal program transformations", Proceedings of the 3rd European Symposium on Programming, pp.389~405 (1990)