Repository navigation
Loop cloning can't eliminate bounds check when assigning to multi-dim jagged array #54074
Description
The core of the src\tests\JIT\Performance\CodeQuality\Benchstones\BenchI\Array2\Array2.cs benchmark is this loop:
for (; loop != 0; loop--) {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
d[i][j][k] = s[i][j][k];
}
}
}
}
Some observations:
- The inner three loops are all loop invariant w.r.t. the outer loop. Can't we just eliminate the outer loop?
- The outer loop is not cloned because it is not in the canonical form accepted by loop cloning -- "for (var=init; var < limit; var++". The
iandjloops are cloned. The innerkloop is not cloned. Why? - Without cloning, there are 5 bounds checks in the inner loop; 1 bounds check get hoisted. With cloning, there are 2 bounds checks in the inner loop; the rest become cloned loop pre-conditions.
- If the inner two loops are also cloned, can we eliminate all the bounds checks?
- The 1st and 2nd cloned loops appear to have duplicate cloning conditions (i.e., it appears they check the same array bounds multiple times
- In the non-cloned case, why can't we hoist more checks?
category:cq
theme:loop-opt
skill-level:expert
cost:medium
impact:medium
Activity
BruceForstall commentedon Jun 15, 2021
The inner
kloop is not cloned due to a heuristic to avoid creating too many "checking" blocks inCompiler::optComputeDerefConditions.After bumping that heuristic to allow the inner loop to be cloned, we still don't remove one of the bounds checks.
BruceForstall commentedon Jun 16, 2021
Why we can't eliminate the final bounds check in the inner loop: when the importer imports the
d[i][j][k] = s[i][j][k]line, it needs to preserve proper exception ordering. That means doing thed[i][j]array bounds check first, thens[i][j][k], then finally thed[i][j][k]bounds check before the assign. To do this, it introduces a temp to stored[i][j], and reuses that temp at the assign. This temp is marked both "Strict ordering of exceptions for Array store" and a "single def temp". When loop cloning goes to reconstruct the array index expressions, it sees the temp, which doesn't appear to be loop-invariant, because it is assigned in the loop. Also, its assignment is in another tree. Thus, loop cloning won't touch the "store" array bounds check, even though it really could be added to the cloning condition if we were somehow smarter, such as knowing it were single-def, and finding that def, looking for the array index pattern there.BruceForstall commentedon Jul 17, 2021
All the issues have been investigated. While more improvements could be implemented, there are none planned, so I'm closing this.
BruceForstall commentedon Oct 7, 2021
The issue with an extra bounds check for nested array access that loop cloning can't get rid of should be investigated. It happens also in other test cases with multi-dimensional (jagged) arrays and nested loops over the array indices.
[-]Loop cloning issues with Array2 benchmark[/-][+]Loop cloning can't eliminate bounds check when assigning to multi-dim jagged array[/+]