Runtime: [Jit] Loop condition doesn't elide bounds check

[benaadams]

As a condition of a while it doesn't elide the check

while ((uint)i >= (uint)entries.Length)
{    
    // not elided
    if (entries[i].hashCode == hashCode && comparer.Equals(key, entries[i].key))
    {

Changing it to an if + break does elide the check

do
{
    if ((uint)i >= (uint)entries.Length)
    {
        break;
    }

    // elided
    if (entries[i].hashCode == hashCode && comparer.Equals(key, entries[i].key))
    {

category:cq
theme:bounds-checks
skill-level:expert
cost:small

[mikedn]

I looked at this in the past. The reason why this doesn't work in the while loop is that the loop is turned into a do/while loop with the loop condition being duplicated. Something like:
```C#
for (uint i = head; i < (uint)entries.Length; i = entries[i].next)
s += entries[i].value;

```C#
if (i < (uint)entries.Length) {
    do {
        s += entries[i].value;
        i = entries[i].next;
    } while (i < (uint)entries.Length));
}

Each if creates the expected OAK_NO_THROW assertion:

N009 (  8,  8) [000073] -A-X--------              *  JTRUE     void  
In BB01 New Global ArrBnds  Assertion: (512, -1) ($200,$ffffffff) [idx: {InitVal($c1)};len: {ARR_LENGTH($100)}] in range  index=#02, mask=0000000000000002
N004 (  5,  5) [000015] ------------              *  JTRUE     void  
In BB02 New Global ArrBnds  Assertion: (523, -1) ($20b,$ffffffff) [idx: {402};len: {ARR_LENGTH($100)}] in range  index=#04, mask=0000000000000008

But then the i in entries[i] is not the i from assertions, it is PhiDef($3, $4, $202). And assertion propagation doesn't know how to propagate OAK_NO_THROW through PHIs. Maybe it should but doing that seems expensive.

It's probably RangeCheck that should pay attention to these assertions and generate the appropriate ranges. This is something I hope I'll look at in the future.

[glenn-slayden]

@mikedn wrote:
Maybe it should, but doing that seems expensive.

Could you clarify: time-expensive for JITting, or time- (and/or) space- (and/or) cache-miss (and/or) predictivity-expensive of the emitted ASM itself? <sup>[note 1]</sup>

If it's not the former, and considering the lack of elision is specifically related to loop code, wouldn't the gain (or loss, see next paragraph) in runtime performance here almost always easily swamp the one-time JIT hit, making this a higher priority fix?

But also more generally, isn't the elision--or redundant presence--at runtime, of any (public) memory fetch or store in fact a correctness bug, considering the strong concurrency guarantees of the .NET memory model? Of course I'm referring to where the checked condition depends on volatile value(s) visible elsewhere. Perhaps this issue here somehow inherently confined to checks of local variables only... which would still need to be true even now given ref-locals?

Pardon my lack of understanding on these matters.

<sub>Notes:
1. I assume you don't mean time expensive for csc.</sub>

[benaadams]

I'm referring to where the checked condition depends on volatile value(s)

Explicit volatiles or Volatile.Read+Volatile.Write are treated differently; always forcing a memory access.

[mikedn]

Could you clarify: time-expensive for JITting, or time- (and/or) space- (and/or) cache-miss (and/or) predictivity-expensive of the emitted ASM itself? [note 1]

Hmm, I don't remember the details. I think it seemed to me at the time that doing this might require multiple scans of the entire assertion table, possible leading to quadratic complexity.

The bigger problem is that the existing assertion propagation design doesn't quite scale. It does a ton of upfront work to generate these assertions but it doesn't know if they are actually needed. Worse, there's a limit to the number of assertions it tracks (for perf reasons) and generating useless assertions can mean not having room for useful ones. And on top of it, assertion propagation is already one the expensive JIT phases.

If it's not the former, and considering the lack of elision is specifically related to loop code, wouldn't the gain (or loss, see next paragraph) in runtime performance here almost always easily swamp the one-time JIT hit, making this a higher priority fix?

Could be. And that's typically true about a lot of optimizations that the JIT could do. But there are other potentially better approaches to this problem and AFAIR the perf impact of this specific range check wasn't very big. So it doesn't seem worthwhile to jump at fixing this issue using the first idea that crosses one's mind.

And as far as I'm concerned, I slowly arrived at the conclusion that it would better to put effort into improving certain other parts of the JIT (e.g. some IR design issues inherited from the legacy JIT32 that impact SSA graph traversal performance) before attempting to improve array range check elimination. That, of course, it solely my personal opinion. The JIT team may very well think otherwise.

But also more generally, isn't the elision--or redundant presence--at runtime, of any (public) memory fetch or store in fact a correctness bug, considering the strong concurrency guarantees of the .NET memory model? Of course I'm referring to where the checked condition depends on volatile value(s) visible elsewhere. Perhaps this issue here somehow inherently confined to checks of local variables only... which would still need to be true even now given ref-locals?

I'm not quite sure I understand what specific concerns you have around the memory model and range check elimination. I'll try to point out some thing that perhaps will clarify this:

• The memory model does not prevent load elimination or load reordering (with respect to other non volatile loads). So there's no problem eliminating or moving the array length load that the range check normally performs.
• Volatile loads generally block optimizations (unless there are bugs in the JIT)
• .NET arrays are fixed size, their Length can't change. The JIT assumes that. Of course, you could change the Length by using unsafe code. That would be completely bogus and the JIT doesn't care about such scenarios.
• Range check elimination requires the JIT to be able to reason about both the index and the array reference. That generally means that they must be local variables so other threads cannot change them. It is possible for other JIT optimizations (e.g. CSE) to transform class field accesses into local variable accesses by caching field values into local variables but that doesn't work very well currently.

[AndyAyersMS]

There is some data on the relative usefulness of assertions over in dotnet/coreclr#18678. Roughly speaking only about 10% of the generated assertions are used.

[glenn-slayden]

@mikedn @AndyAyersMS @benaadams Thanks for the helpful insights.