Mirsad Todorovac wrote:
On Fri, 16 Nov 2001, Frank Heckenbach wrote:
I.e., it has to resolve equations!? (If a is an array [1 .. 20] and in the loop it says `a [i * i - 3]', it should find that i is allowed to be in the range 2 .. 4 and -4 .. -2?
Horrors. If i is a subrange, the compiler can calculate (mini * mini - 3) and (maxi * maxi - 3). If these are satisfactory then it omits the range checks on the index operation.
Nice, but wrong (e.g.: i: -4 .. 4)!
IMHO such min-max analisys is feaible: for exmaple, compiler knows (or can be made that way) that by multiplying x*x you get a positive number (except for complex numbers, of course).
So, if range is -4 .. 7, x*x falls into 0 .. max(abs(x))
Yes, that's the other way (before, you'd suggested to decide at compile time which x values are valid, which means solving the (in)equation).
The other way basically amounts to interval arithmetic. This is more feasible. So if i is 2 .. 4, it could find that i * i - 3 is 1 .. 13 and omit the check. But if i is -4 .. 4 or Integer, i * i - 3 would be -3 .. 13 or -3 .. Sqr (MaxInt) - 3, resp., and it would have to do checks at runtime.
Frank