[Jit] Redundant comparisons are not eliminated

[benaadams]

The following code

if (byteValue.Length >= (2 * sizeof(ulong) + sizeof(ushort)))
{
    if (BinaryPrimitives.ReadUInt64LittleEndian(byteValue) == keepChars)
    {

Generates a double comparison once against size 18; and a second against size 8 (which is already guaranteed by the size 18 check)

G_M33915_IG30:
       cmp      r10d, 18
       jl       G_M33915_IG36
       cmp      r10d, 8
       jl       G_M33915_IG59

Method is ParseConnection in this gist https://gist.github.com/benaadams/2ac588cc3dd65088db2bb51f9e4a89e1

Seen in dotnet/aspnetcore#21004

category:cq
theme:assertion-prop
skill-level:intermediate
cost:medium
impact:small

[BruceForstall]

@AndyAyersMS

[AndyAyersMS]

optAssertionPropGlobal_RelOp only looks for exactly matching assertions; it could broaden its horizon to consider any assertion involving the variable part of the comparison.

Specifically, if optGlobalAssertionIsEqualOrNotEqualZero would return assertions where op1.vn matches and not worry if op2.vn matches we could let the caller do further screening to see if any of those assertions is relevant.

We might need to generalize the interaction of the above two methods as there could be many partially matching assertions and we might want to look at them all.

Probably worth some prospecting to see what potential impact this has.

[benaadams]

If you are going there... Jit doesn't seem to pick up where the condition is reversed e.g. > vs <= or < vs >= whether that's ja vs jbe or jl vs jge

This is problematic as Roslyn seems to like reversing the conditionals so it can be hard to get the correct incantation to get them to match and eliminate one.

[AndyAyersMS]

We should be doing some amount of expression canoncalization to reduce diversity in the jit IR. At the very least, moving the variable part of compares to the LHS so we always see x OP k where x is some jit local, OP some relational operator, and k some constant.

The handwavy proposal above would have us examine all the available assertions that involve x. Given x op k and N assertions of the form:

x op0 k0   is true
x op1 k1   is false
x op2 k2   is true
... 

we'd have to check if we could determine the result of x op k.

For single-variable sets of integer relations this comes down to interval math. Range prop does something similar already but it is too narrowly focused on loops and bounds checks.

[benaadams]

Related this

offset++;
if ((uint)offset > (uint)value.Length)
{
    // Consumed enitre string, move to next
    break;
}

value = value.Slice(offset);

generates

G_M33915_IG28:
       inc      r8d
       cmp      r8d, edx
       ja       G_M33915_IG55
       cmp      r8d, edx
       ja       G_M33915_IG60

[AndyAyersMS]

We do not support general relational assertions x OP y -- this may seem like a small distinction since we support x OP k but allowing more general forms here greatly increases complexity.

That being said, for exact redundancies like this, we might be able to do some custom processing by just looking at the predecessor block: if it branches on exactly the same condition as the current block (say the compares have the same value number) then we can optimize. Also probably worth prospecting.

[AndyAyersMS]

@benaadams do you have a more complete example for that "related" fragment?

[benaadams]

do you have a more complete example for that "related" fragment?

ParseConnection in https://gist.github.com/benaadams/02b56912b6174911f81ac1f5152fc593

G_M42236_IG28:
       inc      r8d
       cmp      r8d, edx
       ja       G_M42236_IG55
       cmp      r8d, edx
       ja       G_M42236_IG60

[benaadams]

Fixed by #43811

[AndyAyersMS]

Exactly redundant comparisons are fixed, but not implicated comparisons (as in the first example). So perhaps we should keep this one open?

It should not be that hard to break down the dominating compare VNs to see if they are testing something similar, eg x > 8 dominated by x > 18 as in the above. Maybe I should do a quick prototype to see how often we see a dominating test and dominated test checking the same SSA var.

[BruceForstall]

@AndyAyersMS Given that you suggested you might investigate, I'll mark this as 6.0 for now.

[AndyAyersMS]

Here's a bit of the screening code in action, on the parse connection example:

*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB13 dom BB12
 {NE($256, $52)}
 {EQ($256, $42)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB22 dom BB19
 {LT($267, $4a)}
 {GE($267, $40)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB23 dom BB22
 {LT($267, $5b)}
 {LT($267, $4a)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB23 dom BB19
 {LT($267, $5b)}
 {GE($267, $40)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB25 dom BB23
 {LT_UN($267, $5b)}
 {LT($267, $5b)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB25 dom BB22
 {LT_UN($267, $5b)}
 {LT($267, $4a)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB25 dom BB19
 {LT_UN($267, $5b)}
 {GE($267, $40)}
*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB28 dom BB26
 {LT($276, $5b)}
 {GE($276, $40)}

(looking for relop VNs with the same LHS vn, and either constant RHS vns or the same RHS vn).

All this tells us is that the same VN is tested against some other constant or the same value higher up in the dominator tree. To be able to optimize we have to show (a) that there's a unique path from dominating test to dominated test, and that (b) the reaching dominating test outcome determines the dominated test outcome.

There are about 7200 of these cases noted when crossgenning SPC.

So it looks promising, but be aware many of these won't pan out, eg

***** BB12
STMT00024 (IL 0x08C...0x090)
N004 (  5,  5) [000094] ------------              *  JTRUE     void  
N003 (  3,  3) [000093] J------N----              \--*  EQ        int    <l:$25b, c:$25a>
N001 (  1,  1) [000091] ------------                 +--*  LCL_VAR   int    V17 loc16        u:6 <l:$257, c:$256>
N002 (  1,  1) [000092] ------------                 \--*  CNS_INT   int    32 $42

------------ BB13 [092..098) -> BB15 (cond), preds={BB12} succs={BB14,BB15}

***** BB13
STMT00026 (IL 0x092...0x096)
N004 (  5,  5) [000103] ------------              *  JTRUE     void  
N003 (  3,  3) [000102] N------N-U--              \--*  NE        int    <l:$25d, c:$25c>
N001 (  1,  1) [000100] ------------                 +--*  LCL_VAR   int    V17 loc16        u:6 <l:$257, c:$256>
N002 (  1,  1) [000101] ------------                 \--*  CNS_INT   int    44 $52

We reach BB13 if V17 is not 32; that won't help us figure out if V17 NE 44.

The case you noted above is

*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB23 dom BB22
 {LT($267, $5b)}
 {LT($267, $4a)}

***** BB22
STMT00076 (IL   ???...  ???)
N004 (  5,  5) [000321] ------------              *  JTRUE     void  
N003 (  3,  3) [000320] J------N----              \--*  LT        int    $26c
N001 (  1,  1) [000700] ------------                 +--*  LCL_VAR   int    V139 tmp119      u:2 $267
N002 (  1,  1) [000319] ------------                 \--*  CNS_INT   int    18 $4a

------------ BB23 [0E6..0F7) -> BB140 (cond), preds={BB22} succs={BB24,BB140}
 . . .
***** BB23
STMT00165 (IL 0x0E6...  ???)
N004 (  5,  5) [000730] ------------              *  JTRUE     void  
N003 (  3,  3) [000729] J------N----              \--*  LT        int    $270
N001 (  1,  1) [000755] ------------                 +--*  LCL_VAR   int    V139 tmp119      u:2 $267
N002 (  1,  1) [000727] ------------                 \--*  CNS_INT   int    8 $5b

and here knowing that V119 is not less than 18 implies V119 must not be less than 8, so that second test is redundant.

To implement the optimization there's a fair bit of logical calculus to handle all the possible relops one might see in both positions, especially if we want to handle the unsigned variants; likely GT_GT, GT_GE, GT_LT, GT_LE, GT_EQ, GT_NE, GT_UN_GT, GT_UN_GE, GT_UN_LT, GT_UN_LE -- so say 10 possibilities for each?

Also we'd want to do two checks each time: given a dominating compare D (say known to be true) and a dominated compare T, does D imply T or does D imply !T? Note the outcomes are either

 D implies T
 D implies !T
 D doesn't imply anything about T

I don't know how to ballpark how many compares may end up being redundant without actually implementing all this. For the logic (and restricting to integral types) I'd be tempted to strongly normalize everything (say express all cases in terms of GT_LE) and then use some tricks from integer linear programming to try and show there can or cannot be a solution.

But in the short run we can perhaps only look for cases with the exact same relop, and see where that gets us.

Note there's an even higher dominating compare in the case above

*** Interesting case in HttpParser:ParseConnection(System.String[]):int: tree BB23 dom BB19
 {LT($267, $5b)}
 {GE($267, $40)}

and it's possible to generalize the logic to consider the combination of all the known-value dominating predicates.

[AndyAyersMS]

I started in on a more general version of this (prototype: MoreRedundantBranches) but the combinatorics still look ugly. One thing this doesn't handle yet is that VNs don't obey the "constants on the right" rule.

[AndyAyersMS]

At one point I started working on the more general version, see #46257 (comment)

[AndyAyersMS]

RBO gets the first case now:

--- Trying RBO in BB125 ---
Relop [001524] BB125 value unknown, trying inference

Dominator BB124 of BB125 has same VN operands but different relop
N003 (  3,  3) [001515] J---G--N---                         *  LT        int    $229
N001 (  1,  1) [001516] -----------                         +--*  LCL_VAR   int    V34 tmp25        u:3 $225
N002 (  1,  1) [001517] -----------                         \--*  CNS_INT   int    18 $e6
 Redundant compare; current relop:
N003 (  3,  3) [001524] J---G--N---                         *  LT        int    $22d
N001 (  1,  1) [001525] -----------                         +--*  LCL_VAR   int    V34 tmp25        u:3 $225
N002 (  1,  1) [001526] -----------                         \--*  CNS_INT   int    8 $d3
False successor BB125 of BB124 reaches, relop [001524] must be false

likely thanks to #95234 (dump message is a bit misleading, the VN operands are not the same here...).