From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,8a4455177648cb9e X-Google-Attributes: gid103376,public From: Lieven Marchand Subject: Re: Idea: Array Boundary Checks on Write Access Only Date: 1998/06/18 Message-ID: <6me766$l4t$1@xenon.inbe.net>#1/1 X-Deja-AN: 364244335 References: <35851B64.5BF271C4@cl.cam.ac.uk> <6m8v02$r2l$1@xenon.inbe.net> <3588D738.4BB32E5A@cl.cam.ac.uk> Organization: Only under extreme pressure! Newsgroups: comp.lang.ada Date: 1998-06-18T00:00:00+00:00 List-Id: Markus Kuhn writes: > Lieven Marchand wrote: > > About the only commonly used case that most compilers don't handle is > > where you put in the check yourself. > > It would be really neat if Ada compilers would keep track not only of > the declared range of a subtype, but also of the effectively possible > range of Integer variables inside a certain program fragment as part > of the flow analysis. > > For instance in code such as > > if J > 0 then > -- compiler notes that here J : range 1 .. J'Last > if I > J then > -- compiler notes that here I : range 1 .. I'Last > > then the compiler should know that inside the second "if" I > 0 always > holds. This need not be a full blown automatic proof system, just some > logic that understands simple inequalities and monotonic expressions > and that keeps track of the effective maximum and minimum value > of integer variables and supresses most checks accordingly. > Actually, most algorithms for this kind of thing would do that. Check out "Elimination of Redundant Array Subscript Range Checks" from P. Kolte and M. Wolfe for a nice introduction to this stuff. It's available on the web from cse.ogi.edu but I haven't got the URL handy. They cite the Alsys and Karlsruhe Ada compiler as previous work. In their examples (with Fortran) they eliminate typically 98% of the checks that a naive implementation inserts but I have the feeling this would be too optimistical in general. Earlier work by Gupta using a slightly different approach gives elimination percentages from 52 to 100 with typical values around 80-90. One of the problems in doing this with Ada is that the language spec describes the exact behaviour for errors like this. You have to raise the correct exception after having done all the previous effects. This restricts the freedom of the compiler to rearrange checks. In languages with similar semantics for arrays like Modula-3 the only behaviour prescribed is that it is a checked runtime error with leaves the implementation with much more freedom. One way to solve this is to do the rearrangements with the minimal checks to determine a bounds violation and on detection switch to a slower version of the routine that has the correct error behaviour but this would introduce a lot of code bloat. -- Lieven Marchand ------------------------------------------------------------------------------ Few people have a talent for constructive laziness. -- Lazarus Long