Optimizing array bound checks using flow analysis

作者: Rajiv Gupta

DOI: 10.1145/176454.176507

关键词:

摘要: Bound checks are introduced in programs for the run-time detection of array bound violations. Compile-time optimizations employed to reduce execution-time overhead due checks. The program execution time through elimination and propagation out loops. An optimized terminates with an violation if only same outcome would have resulted during containing all However, point at which occurs may not be same. Experimental results indicate that number performed a is greatly reduced using these techniques.

参考文章(11)
Ravi Sethi, Jeffrey D. Ullman, Alfred V. Aho, Compilers: Principles, Techniques, and Tools ,(1986)
Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements Stanford University. ,(1984)
Utpal K. Banerjee, Dependence analysis for supercomputing ,(1988)
W.H. Harrison, Compiler Analysis of the Value Ranges for Variables IEEE Transactions on Software Engineering. ,vol. SE-3, pp. 243- 250 ,(1977) , 10.1109/TSE.1977.231133
Norihisa Suzuki, Kiyoshi Ishihata, Implementation of an array bound checker Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '77. pp. 132- 143 ,(1977) , 10.1145/512950.512963
Mark N. Wegman, Frank Kenneth Zadeck, Constant propagation with conditional branches symposium on principles of programming languages. pp. 291- 299 ,(1985) , 10.1145/318593.318659
Rajiv Gupta, Madalene Spezialetti, Loop monotonic computations: an approach for the efficient run-time detection of races Proceedings of the symposium on Testing, analysis, and verification. pp. 98- 111 ,(1991) , 10.1145/120807.120816
Mark N. Wegman, F. Kenneth Zadeck, Constant propagation with conditional branches ACM Transactions on Programming Languages and Systems. ,vol. 13, pp. 181- 210 ,(1991) , 10.1145/103135.103136
David Callahan, Keith D. Cooper, Ken Kennedy, Linda Torczon, Interprocedural constant propagation ACM SIGPLAN Notices. ,vol. 39, pp. 155- 166 ,(2004) , 10.1145/989393.989412
Rajiv Gupta, A fresh look at optimizing array bound checking programming language design and implementation. ,vol. 25, pp. 272- 282 ,(1990) , 10.1145/93542.93581