Mirsad Todorovac wrote:
On Thu, 15 Nov 2001, CBFalconer wrote:
Expanding, all that is required is a single routine (or in line instruction sequence) as long as chars and booleans are represented by integers, which is called or emitted just before assignment or indexing. The value to be checked is already on the stack, and it would look like:
push min push max call chkinline definitelly:
cmp min branch_less :range_error cmp max branch_greater :range_errorBut when it has to be emited after every add or subtract operation, it can produce significant overhead even if it's only 4 instructions.
You can go even further and reduce this to:
ld r0, x ld r1, y add r1, r0 jump_on_overflow :range_error(of course, instructions do not match an actual assembler).
I don't understand the latter example, but in general, assembler level suggestions are not really needed, anyway. The back-end (code generation and optimizer) is working well, I might remind you all. We only have to use it. E.g., it's possible to do a check like the first one with only one comparison and branch, and the back-end knows how to do it (this is on a generic CPUs; some CPUs might have even better mechanisms).
It's therefore better to describe what should be done on a higher level, e.g. by equivalent Pascal (or C) code. Of course, in the range checking case, that's quite clear (it's either `(x >= Min) and (x <= Max)' or just one of the comparisons, if the other bound is safe).
There are many good points there. But with range checking there is many room for optimization. For example, in some FOR loops compiler could determine the possible range of a variable.
For expensive loops that don't have constant upper and lower band but variable, this could be done (at the beginning of the expensive loop):
- compiler checks the minimum bounds for arrays inside loop
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?
- compiler asserts two versions of loop: one with range-checking, onw without
- at run-time check finds the maximum bounds for loop variable;
bound-checking is called (fast)
- if it's safe for minimum bounds found in 1, loop without
occur inevitably in the loop, runtime exception is raised
- if it's determined algorythmic that range-error will
Not necessarily correct (side-effects might occur before the range error happens).
- if neither is true, (for example, there is an conditional exit from the loop) the version of the loop compiled with range checking is performed (slow)
What if the loop calls any routine which might (directly or indirectly) call Halt conditionally?
But this may be too much for the compiler to decide,
I think so. If the programmer really cares for speed, he should help the compiler, e.g., as Chuck said, by declaring variables of correct type. If the programmer knows that it makes only sense for the counter to be between 1 and 10, he should just declare it as 1 .. 10 so (some or all) checks in the loop can be avoided, while at the beginning of the loop there will be checks (if necessary) that the loop bounds are both between 1 and 10.
Frank