[JIT] Elide bounds check for reverse iteration over arrays and spans

[GrabYourPitchforks]

Currently the JITter is smart enough to elide bounds checks when forward-iterating over arrays or spans, as in the below sample.

byte[] array;
for (int i = 0; i < array.Length; i++) {
  // consume array[i]
}

It would help certain tight loops if the JITter could also recognize the reverse-iteration pattern and elide the bounds checks in that scenario as well.

byte[] array;
for (int i = array.Length - 1; i >= 0 /* or any non-negative const */; i--) {
  // consume array[i]
}

This optimization would save a cmp and jae instruction in these tight loops, and in certain cases it would also allow omitting the stack frame setup that normally accompanies methods that might throw exceptions.

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

[Therzok]

for (int i = array.Length - 1; i >= 0 /* or any non-negative const */; i++) {

That should be i--.

[GrabYourPitchforks]

@Therzok Serves me right for writing the code in notepad. :) I've fixed the sample.

[GrabYourPitchforks]

It turns out the JIT can correctly elide checks in one particular variant of this access pattern.

int i = arr.Length;
while ((uint)(--i) < (uint)arr.Length) {
  // accesses to arr[i] won't incur additional checks here
}

I've been using this in some of my code, but it's somewhat unnatural. It also doesn't support terminating the loop at an arbitrary non-negative const; it always iterates all the way to the very first element.

[benaadams]

There are some weirder patterns: https://github.com/dotnet/coreclr/issues/15476

[mikedn]

This and 15476 are sort of related, if they're implemented that will probably happen in the RangeCheck phase. I'm looking into this but it's probably going to take a while, the rangecheck phase is a bit of a mess and it is difficult and risky to extend it to handle new patterns.

[ViktorHofer]

This pattern and others are described in https://blogs.msdn.microsoft.com/clrcodegeneration/2009/08/13/array-bounds-check-elimination-in-the-clr/.

@mikedn maybe we could compare what has change since then? In nearly all examples (excluding the static variable access as it seems trickier) the author provided possible optimizations.

[mikedn]

To an extent the simplest and shortest answer is that not a lot has changed. Here are the cases where something did change:

static int[] Test_ArrayCopy1(int n) {
    int[] ia = new int[n];
    for (int i = 0; i < n; i++)
        ia[i] = i;  // Bound check eliminated via loop cloning, far from ideal, should be fixable
    return ia;
}

static int[] v;
static void Test_ArrayInGlobal() {
    for (int i = 0; i < v.Length; i++)
        // This might have worked until recently when a bug fix made this case more conservative
        v[i] = i;
}

static int Test_TwoArrays(int[] ia1, int[] ia2) {
    // The programmer knows a precondition: ia1.Length == ia2.Length
    int sum = 0;
    for (int i = 0; i < ia1.Length; i++)
        // This one works via loop cloning. There's not much else the JIT can do here
        // because the precondition is not known to the JIT.
        sum += (ia1[i] + ia2[i]);
    return sum;
}

static int[] Test_ArrayCopy2(int[] ia1) {
    // An array copy loop operation.
    int[] res = new int[ia1.Length];
    for (int i = 0; i < res.Length; i++)
        res[i] = ia1[i]; // Loop cloning again, meh. This one should be 
    return res;
}

[jakobbotsch]

We handle this with loop cloning today (after #67930), so we get the following codegen:

; Assembly listing for method MustHaveValueBenchmark.C:Foo(int[])
; Emitting BLENDED_CODE for X64 CPU with AVX - Windows
; optimized code
; rsp based frame
; partially interruptible
; No PGO data
; Final local variable assignments
;
;  V00 arg0         [V00,T01] (  5,  7   )     ref  ->  rsi         class-hnd single-def
;  V01 loc0         [V01,T00] ( 12, 19.04)     int  ->  rbx        
;  V02 OutArgs      [V02    ] (  1,  1   )  lclBlk (32) [rsp+00H]   "OutgoingArgSpace"
;  V03 cse0         [V03,T02] (  4,  3.04)     int  ->  rdi         "CSE - aggressive"
;
; Lcl frame size = 32

G_M21382_IG01:
       push     rdi
       push     rsi
       push     rbx
       sub      rsp, 32
       mov      rsi, rcx
						;; size=10 bbWeight=1    PerfScore 3.50
G_M21382_IG02:
       mov      edi, dword ptr [rsi+08H]
       lea      ebx, [rdi-01H]
       test     ebx, ebx
       jl       SHORT G_M21382_IG06
       cmp      edi, ebx
       jle      SHORT G_M21382_IG05
						;; size=14 bbWeight=1    PerfScore 5.00
G_M21382_IG03:
       mov      ecx, ebx
       mov      ecx, dword ptr [rsi+4*rcx+10H]
       call     [MustHaveValueBenchmark.C:Consume(int)]
       dec      ebx
       jns      SHORT G_M21382_IG03
						;; size=16 bbWeight=3.96 PerfScore 25.74
G_M21382_IG04:
       jmp      SHORT G_M21382_IG06
						;; size=2 bbWeight=1    PerfScore 2.00
G_M21382_IG05:
       cmp      ebx, edi
       jae      SHORT G_M21382_IG07
       mov      ecx, ebx
       mov      ecx, dword ptr [rsi+4*rcx+10H]
       call     [MustHaveValueBenchmark.C:Consume(int)]
       dec      ebx
       jns      SHORT G_M21382_IG05
						;; size=20 bbWeight=0.04 PerfScore 0.31
G_M21382_IG06:
       add      rsp, 32
       pop      rbx
       pop      rsi
       pop      rdi
       ret      
						;; size=8 bbWeight=1    PerfScore 2.75
G_M21382_IG07:
       call     CORINFO_HELP_RNGCHKFAIL
       int3     
						;; size=6 bbWeight=0    PerfScore 0.00

; Total bytes of code 76, prolog size 7, PerfScore 46.90, instruction count 31, allocated bytes for code 76 (MethodHash=453dac79) for method MustHaveValueBenchmark.C:Foo(int[])
; ============================================================

Of course it would be better if we could just prove it to be safe and avoid this code duplication.