Re: Array bounds checking

>moss@cs.umass.edu (Eliot Moss) writes:
>>[Opt. techniques can eliminate most array bounds checks.]


larus@primost.cs.wisc.edu (James Larus) writes:
>[See Rajiv Gupta's SIGPLAN PLDI paper titled ``A Fresh Look at
> Optimizing Array Bounds Checking''. After all optimizations were
> applied, programs with bounds checks ran 0-46% slower than without.
> That's down from 78-325% slower.]


John Levine (moderator) writes:
>[How does this compare with IBM's results? The papers I've seen on PL.8
>suggest that they didn't think bounds checking was very expensive. -John]


As soon as I saw the paper title in the proceedings, I was interested.
I looked explicitly in the referenced papers list and didn't see
anything that looked like a reference to the IBM PL.8 stuff. I might
have missed it. Frankly, I didn't understand Rajiv's paper in enough
detail and I was [[excuse]] so I didn't go back and re-read it (yet).




>From ``An Overview of the PL.8 Compiler'', Marc Auslander & Martin
Hopkins (IBM T. J. Watson, Yorktown Heights 10598), from ?? (c) 1982
ACM 0-89791-074-5/82/006/0022


The 801 instruction `TGTI' (trap greater than immediate) is used for
range checking. It is inserted whenever a subscripted reference is
made. Because traps are modeled as result-producing instreuctions,
they can be moved and eliminated in the same way as other computations.
``The use of the trap "results" as operands of storage reference
operations expresses exactly the right dependence.'' The trap must be
evaluated before the storage reference. If several are required, they
are joined with a LIST pseudo-instruction. Global optimization
handles TRAP and LIST operations. They also discuss how to map TGTI on
to machines (68000 and IBM 370) wihtout such a trap instruction.


``The result of this effort is that checked code from the PL.8 compiler
is normally 5 to 10 percent slower than unchecked code. This cost
allows the use of checked code in production as well as during testing.
Because almost all the work of making checking code efficient comes
from applying the same processes which operate on useful computation,
confidence in the correctness of checking code is high.''


;-D oN ( Library liberty ) Pardo
--
pardo@cs.washington.edu
        {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
--

Return to the comp.compilers page.
Search the comp.compilers archives again.