Eliminating array bounds checks

From Spivey's Corner
Jump to: navigation, search

The Oberon compiler inserts code into every array access and every pointer dereference to check for runtime errors, like a subscript that is out of bounds or a pointer that is null. In many cases, it is possible to eliminate the checks because it is possible to determine from the program that no error can occur. For example, an array access inside a FOR loop may be safe given the bounds of the loop, and several uses of the same pointer in successive statements may be able to share one check that the pointer is non-null. Modify the Oberon compiler (or a simpler one taken from the Compilers labs) so that it represents the checks explicitly in its IR, and introduce a pass that removes unnecessary checks, so speeding up the code without compromising safety.


AT+98: A. Adl-Tabatabai et al., Fast, effective code generation in a just-in-time Java compiler, SIGPLAN Notices 33, 5 (May 1998), pp. 280–90.

Mos16: A. Mosoi, Bounds check elimination for Go, 2016. https://docs.google.com/document/d/1vdAEAjYdzjnPA9WDOQ1e4e05cYVMpqSxJYZT33Cqw2g

QHV02: F. Qian, L. Hendren and C. Verbrugge, A comprehensive approach to array bounds elimination for Java. In Compiler Construction (R. Nigel Horspool, ed.), pp. 325–41, Springer, 2002.

WWM09: T. Wüthinger, C. Wimmer and H. Mössenbock, Array bounds check elimination in the context of deoptimization, Science of Computer Programming 74, 5 (March 2009), pp. 279–95.