JIT: IV opts relop evaluation misses combining facts to prove relops

[jakobbotsch]

I collected some stats for #110222 to figure out where strength reduction bails out.

Those stats looks like:

NonLoopUses: 30772
CouldNotInitializeCursors: 27066
IVUseMismatch: 34895
SameStep: 1652
SameStepWidened: 951
StepNonConstant: 3

For CouldNotInitializeCursors the reason is often that we fail to compute the trip count of the loop, in which case the IV use in the loop test disqualifies the loop from strength reduction. I looked at one such case, System.Reflection.Internal.EncodingHelper:DecodeUtf8, in libraries_tests.run. There we are unable to prove that the loop bound is at least 1:

STMT00047 ( ??? ... ??? )
N004 (  0,  0) [000202] DA---------                         ▌  STORE_LCL_VAR int    V14 tmp10        d:2 $VN.Void
N003 (  0,  0) [000201] -----------                         └──▌  PHI       int    $3c1
N001 (  0,  0) [000219] ----------- pred BB10                  ├──▌  PHI_ARG   int    V14 tmp10        u:3
N002 (  0,  0) [000216] ----------- pred BB09                  └──▌  PHI_ARG   int    V14 tmp10        u:1 $40
  => <L00, 0, 1>
  L00 exits when:
  <L00, 1, 1> >= V20.1
  Does not overflow past the test
  Need to prove 1 <= V20.1: unknown

It turns out this is implied by the combination of facts from two dominating compares:

***** BB03 [0002]
STMT00001 ( 0x00D[E-] ... 0x00E )
N004 (  5,  5) [000007] -----+-----                         ▌  JTRUE     void   $VN.Void
N003 (  3,  3) [000006] J----+-N---                         └──▌  NE        int    $1c1
N001 (  1,  1) [000004] -----+-----                            ├──▌  LCL_VAR   int    V01 arg1         u:1 $c0
N002 (  1,  1) [000005] -----+-----                            └──▌  CNS_INT   int    0 $40

...

***** BB06 [0006]
STMT00016 ( INL02 @ 0x016[E-] ... ??? ) <- INL01 @ ??? <- INLRT @ 0x016[E-]
N004 (  5,  5) [000055] -----+-----                         ▌  JTRUE     void   $VN.Void
N003 (  3,  3) [000054] J----+-N---                         └──▌  GE        int    $1c4
N001 (  1,  1) [000034] -----+-----                            ├──▌  LCL_VAR   int    V01 arg1         u:1 $c0
N002 (  1,  1) [000053] -----+-----                            └──▌  CNS_INT   int    0 $40

However, RBO is not able to combine these two facts to prove the 1 <= V20.1. OTOH, range check actually eliminates bounds checks based on the combination of these two facts in this method, so we can likely use assertions or range check directly in addition to RBO to prove it.

<0, $c0 + -1> BetweenBounds <0, [000115]>
$c0 upper bound is:  {InitVal($41)}
Array size is: 1 (minimum)

[dotnet-policy-service]

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch
See info in area-owners.md if you want to be subscribed.

[jakobbotsch]

OTOH, range check actually eliminates bounds checks based on the combination of these two facts in this method, so we can likely use assertions or range check directly in addition to RBO to prove it.

Actually range check "proves" this in an unsound way, making only use of the != 0 check:

runtime/src/coreclr/jit/rangecheck.cpp

Lines 756 to 762 in 05fa881

	if ((cnstLimit == 0) && (curAssertion->assertionKind == Compiler::OAK_NOT_EQUAL) &&
	m_pCompiler->vnStore->IsVNCheckedBound(curAssertion->op1.vn))
	{
	// we have arr.Len != 0, so the length must be atleast one
	limit = Limit(Limit::keConstant, 1);
	cmpOper = GT_GE;
	}

IsVNCheckedBound is not enough on its own to imply non-negativity, so this is not sound. It happens to work because the VNs marked as checked bounds are usually non-negative values, but I do not think that's an IR invariant we want to enforce.