Frank Heckenbach wrote:
Mirsad Todorovac wrote:
... snip ...
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):
1. compiler checks the minimum bounds for arrays inside loopI.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. But this is much later in the development, the first thing is to implement the range checks. This is simply pushing the calculated index, a min and a max from the array declaration, and calling chk. So the pseudo (stack) code looks something like:
LDA array (load address) LD i DUP MUL LDC 3 SUB * LDC min * LDC max * CALL chk LDC min SUB (convert to zero based index, if min non-zero) IXA n (n is size of an array element) LDI (load indirect, access array[ix])
and the range checking decision mechanism decides whether to omit the operations marked with an '*'. Executing them harms nothing but running time.
2. compiler asserts two versions of loop: one with range-checking, onw without 3. at run-time check finds the maximum bounds for loop variable; - if it's safe for minimum bounds found in 1, loop without bound-checking is called (fast) - if it's determined algorythmic that range-error will occur inevitably in the loop, runtime exception is raisedNot 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)
You can't precheck loop variables without ridiculous analysis. Except for a for index, they can all be altered arbitrarily, and the for limitations may or may not be enforced. The safe time to check is at usage.
What if the loop calls any routine which might (directly or indirectly) call Halt conditionally?
So what? A halt is a halt is a halt.
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.
For many years I have made a practice of declaring a precise index type for each and every array. Obviously conformant arrays are slightly different. But the mechanism I suggested still works, it just has to get the min/max values from the parameters.
My pseudo code probably looks nothing like yours, I am not familiar with GCCs intermediate forms, which I believe are designed for optimization analysis. So I am limiting myself to prodding, having been there in the past.