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: f891f,eac70c5fad02d925 X-Google-Attributes: gidf891f,public X-Google-Thread: 103376,eac70c5fad02d925 X-Google-Attributes: gid103376,public From: ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) Subject: Re: Concerning subscript bounds checks Date: 1996/06/24 Message-ID: <4ql9eq$hdt@goanna.cs.rmit.EDU.AU>#1/1 X-Deja-AN: 161797819 references: <4qdj3e$btf@goanna.cs.rmit.EDU.AU> organization: Comp Sci, RMIT, Melbourne, Australia keywords: subscripts newsgroups: comp.lang.ada,comp.lang.misc nntp-posting-user: ok Date: 1996-06-24T00:00:00+00:00 List-Id: dewar@cs.nyu.edu (Robert Dewar) writes: >Richard said >"The remaining 4 occur in this context: ... >A reasonably smart compiler should be able to tell that these four >subscripts are also safe. >" >I suspect this judgment is based on informal reasoning ("well it is pretty >obvious to me that it can be figured out"). Wrong. I worked out in some detail a straightforward method for a compiler to handle this. I chose not to write it up here because it's (a) obvious and (b) old hat. >As always compiler optimizations, >particularly range analysis are always more complicated than they appear >from simple examples. Look, I was *PRAISING* Ada, not criticising anything. I have *NO IDEA* what optimisations GNAT or any other Ada compiler does or does not do. I know for a fact that the analysis required for this particular example and for a wide range of examples like it (basically looping over a bunch of vectors and _conditionally_ routing elements from one set of vectors to another: APL Compress and Merge operations and a few other patterns I've seen in Fortran code) is straightforward to specify and would take linear time to compute (I am taking the attitude here that if a variable outlives a goto you just throw up your hands and be pessimistic). *Of course* doing such an analysis takes time. *Of course* the compiler's time spent doing that could have been spent doing other things. *Of course* the compiler writers' time spent implementing that could have been spent implementing other things. *Of course* it might be beyond any reasonable dispute in some particular case that *not* doing this optimisation might be the right choice. >P.S. GNAT has not even started to think about optimizing checks yet, >you get junk checks even in simple loops. It's something we plan >to start work on soon! The central point I was making was a very simple, very obvious, very positive one: I translated an algorithm from Fortran to Ada, and it _easily_ and _naturally_ fell out that 62 out of 66 subscripts could _obviously_ be compiled without checks using purely local information (no data flow or range analysis needed). I call that a _good_ result. (The 4 subscripts that aren't quite so obvious are executed with low frequency, and only the upper bound is not obviously safe.) -- Fifty years of programming language research, and we end up with C++ ??? Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.