Optimization of array subscript range checks

ABSTRACT

Compile-time elimination of subscript range checks is performed by some optimizing compilers to reduce the overhead associated with manipulating array data structures. Elimination and propagation, the two methods of subscript range check optimization, are less effective for eliminating global redundancies especially in while-loop structures with nonconstant loop guards. This paper describes a subscript range check optimization procedure that can eliminate more range checks than current methods. Two transformations called inner-loop guard elimination and conservative expression substitution are introduced to enhance propagation of range checks in nested while-loops and to define a partial order on related range checks. Global elimination is improved by considering range checks performed before control reaches a statement and after control leaves a statement. A unique feature of this method is the simplification of the available range-check analysis system for global elimination.

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: 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
• 3: HARRISON, W. Compiler analysis of the value ranges for variables. IEEE Trans. Softw. Eng. SE-3, 3(May 1977), 243-250.
• 4: 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
• 5: 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]
• 6: WELSH, J. Economic range checks in Pascal. Softw. Pract. Exper. 8 (1978), 85-97.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Performance

Keywords:
conservative expression substitution, loop guard elimination, range check optimization