Skip to content

Changes

Summary

  1. Fix versioning test against final index value for BNDCHK (commit: 2c2cc01) (details)
Commit 2c2cc01114db6a91990298f583417d7bb3eaca0a by Devin Papineau
Fix versioning test against final index value for BNDCHK

Previously this versioning test would do either a strict or non-strict
comparison depending on a few factors:
- isLoopDrivingInductionVariable,
- isIndexChildMultiplied, and
- the opcode of _loopTestTree (without consulting reverseBranch).

To deal with all of this variation there were multiple ad hoc
adjustments of +1 or -1 at different points in the determination of
maxValue (which is really supposed to be the last value).

This state of affairs led to bugs, notably when using a non-strict loop
test together with an index expression that contains a multiplication,
but also in other scenarios that I have not precisely characterized.

Now this versioning test is always (ifiucmpge maxValue arrayLength) for
increasing index expressions and (ificmplt maxValue 0) for decreasing
ones, with no regard to isLoopDrivingInductionVariable, etc., and the
corresponding ad hoc adjustments are eliminated from maxValue. Rather
than always take the ceiling and try to compensate for non-strict loop
tests after the fact, we now use the floor in the case of non-strict
loop tests and (ceiling - 1) otherwise, as described in the comment in
the extremum versioning path in buildConditionalTree(). (Note though
that instead of subtracting 1 before multiplying by incrJNode, this
change subtracts additiveConstantInStore afterward, which has the same
effect.)

Additionally, if the index expression was based on a derived IV and
involved a substitution via isDependentOnInductionVariable(), then this
versioning test would load the temporary that's defined within the loop
instead of the initial value of the IV. The temp might be uninitialized,
resulting in a versioning test that can non-deterministically pass even
if the bound check should fail. It's not much better either if the temp
happens to be initialized, since its value won't have come from the
definition within the loop and is most likely entirely unrelated to the
initial value of the IV. This commit changes the versioning test to load
the derived IV instead of the temporary.

Finally, it was also possible for a later versioning test to load an
uninitialized temporary when trying to rule out overflow in a
multiplication that appears in the index expression. To prevent this,
versioning is now disallowed if it would be necessary to substitute
beneath a multiplication.

With these changes the versioning test is still not precise, which I
believe is due to a failure to account properly for different possible
orderings of operations in the loop and possibly also to account for the
difference between the initial value of a derived IV and the value of a
temp based on it in the first iteration (e.g. tmp=iv+1).

However, it appears to be conservative. I have checked a large number of
generated test cases with different combinations of features:
- Do-while loops vs while loops (reverseBranch)
- Strict vs. non-strict loop conditions
- Increasing primary IV (with <, <= comparisons) vs. decreasing (>, >=)
- Accessing every element vs. every other element
- Getting every other element by stepping by 2 vs. multiplying by 2
- Even vs. odd array length (when accessing every other element)
- Accessing even vs. odd indices (when accessing every other element)
- Accessing elements in increasing vs. decreasing order of index
- Indexing based on primary vs. derived IV
- Stepping the primary IV by -3, -1, +1, or +3 (if using a derived IV)
- Adding an offset in the index expression vs. not adding one
- Adding an offset before multiplying vs. afterward (if multiplying)
- Using a temp (isDependentOnInductionVariable()) vs. no temp
- Setting the temp to the IV or to the index (if using a temp)
- Different initial values for the IV(s), as consistent with the above
- Every usable permutation of the statements in the loop body

In every case I had a script determine the widest loop bound that avoids
failing a bound check. I ran each test case three times:
- once with the precise bounds, which should not fail a bound check;
- once with the initial value modified to cause a bound check to fail on
  the first iteration; and
- once with the loop bound modified to do an extra iteration at the end
  and fail a bound check in the last iteration.

With this commit, all such test executions behaved as expected. In some
cases the bound check was not versioned or execution went unnecessarily
to the cold loop, but in those cases one of the following always held
before this commit:
- we already did the same thing, or
- the test passed all bound checks when it should have failed one, or
- there was a load of an uninitialized variable in the versioning test.

Most loops in real programs compute the index based on the primary IV,
which appears directly in the index expression, i.e. array[...i...]. For
these loops as they occur in the test cases described above, the only
effect of this change is to correctly run bound checks when one should
fail and to sometimes avoid going unnecessarily to the cold loop.
(commit: 2c2cc01)
The file was modified compiler/optimizer/LoopVersioner.cpp (diff)