Optimizing array bound checks using flow analysis

ABSTRACT

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

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 3: David Callahan , Keith D. Cooper , Ken Kennedy , Linda Torczon, Interprocedural constant propagation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.152-161, June 25-27, 1986, Palo Alto, California, United States
• 4: Frederick Chi-Tak Chow, A portable machine-independent global optimizer--design and measurements, 1984
• 5: Rajiv Gupta, A fresh look at optimizing array bound checking, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.272-282, June 1990, White Plains, New York, United States
• 6: 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, p.98-111, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120816]
• 7: HARRISON, W. 1977. Compiler analysis of the value ranges for variables. IEEE Trans. Softw. Eng. 3, 3 (May), 243-250.
• 8: Victoria Markstein , John Cocke , Peter Markstein, Optimization of range checking, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.114-119, June 23-25, 1982, Boston, Massachusetts, United States
• 9: Norihisa Suzuki , Kiyoshi Ishihata, Implementation of an array bound checker, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.132-143, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512963]
• 10: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Languages, Reliability

Keywords:
available checks, check hoisting, dataflow analysis, very busy checks