JIT: Assertion prop should generate fewer array-bound complement assertions

[JosephTremoulet]

When we find an array-bound-related JTrue, we always create assertions for both the branch-taken edge and the fall-through edge. One of those assertions indicates that an index or constant is out-of-bounds, which is at best useless (because we don't try to prove subsequent accesses are out-of-bounds or eliminate subsequent also-out-of-bounds comparisons) and at worst harmful (because of bad interaction with range merging). See #9773 (comment).
category:cq
theme:assertion-prop
skill-level:expert
cost:medium
impact:medium

[mikedn]

because we don't try to prove subsequent accesses are out-of-bounds or eliminate subsequent also-out-of-bounds comparisons

It turns out that there is a somewhat convoluted case where array bound complementary assertions have an effect:

The JIT can eliminate redundant EQ/NE comparisons:

if (x == y) {
    Console.WriteLine();
    if (x == y) { // eliminated
        Console.WriteLine();
    }
}

But what does this has to do with array bound assertions, those do not involve EQ/NE. Well, they sometimes do indirectly:

bool cond = i < a.Length;
if (cond == false) {
    Console.WriteLine();
    if (cond == false) {
        Console.WriteLine();
    }   
}

Now the 2 comparisons involve the array length and optCreateJTrueBoundsAssertion takes over and creates the assertion(s). If it stops creating complementary assertions thinking that they're only needed by range check then the nested comparison is no longer eliminated because we only have assertions for the "else" edge.

How common is this pattern? Well, I ran into this only because I accidentally jit-diffed a checked corelib and ended up with a regression. This pattern is produced by Debug.Assert calling BCLDebug.Assert and both testing the assert condition which in some cases happens to involve an array (or string) length.

This pattern appears to be very rare but then the range checks that are eliminated by removing complementary assertions aren't very common either. Perhaps we should keep these complementary assertions and instead make range check understand that <a.len, 0> is actually <0, 0>.

[JosephTremoulet]

Thanks for the analysis. Part of me thinks it's unfortunate that the jtrue bounds for unsigned array length compares have such different handling than the other jtrue bounds, and would like to make things consistent either by not worrying about missing the pattern above or by creating complementary assertions for the unsigned compare case... but we don't have OAK_THROW and so can't even represent those complementary assertions, and adding it purely in the name of consistency would be "unfortunate" as well. Maybe there's an underlying issue with the representation, and it would be better for the assertion kind to be 'relop' and then have the distinction of const-vs-local-vs-arrlen be a property of each operand of the assertion...

Perhaps we should keep these complementary assertions and instead make range check understand that <a.len, 0> is actually <0, 0>

Yes, fixing the problem by making the analysis smarter certainly sounds like a good option.

[mikedn]

Part of me thinks it's unfortunate that the jtrue bounds for unsigned array length compares have such different handling than the other jtrue bounds, and would like to make things consistent either by not worrying about missing the pattern above or by creating complementary assertions for the unsigned compare case

Maybe it is enough to cleanup the optAssertionEdge thing I added so it doesn't look like a special case added just for OAK_NO_THROW, see this commit in my fork. I was planning to include that in a PR for this issue but maybe I should send it separately.

The fact that in some cases we don't always generate complementary assertions doesn't sound that inconsistent to me, at least for a JIT compiler. In fact it already happens in a corner case - when the assertion table fills up. Because of this no code can assume that complementary assertions do exist.

Maybe there's an underlying issue with the representation, and it would be better for the assertion kind to be 'relop' and then have the distinction of const-vs-local-vs-arrlen be a property of each operand of the assertion...

I'm wondering the same thing. It would seem that both assertion prop and range check target specific optimization and as such the implementation is very special cased. Like we generate i < a.len from relops but not from array range checks. Or we optimize some very specific casts but not others (e.g. OAK_NO_THROW tells us that the index is positive and that can turn a signed cats into a slightly cheaper unsigned cast).

Yes, fixing the problem by making the analysis smarter certainly sounds like a good option.

Another option is to stop generating i >= a.len assertions but keep generating i >= a.len == true assertions. Only the later variant (despite the two variants being obviously equivalent) does impact the pattern described in my previous post.

[kunalspathak]

Removing JitUntriaged, now that it is part of #76671

[AndyAyersMS]

@EgorBo sounds similar to things you have been looking at recently