Range check elimination for multi-dimensional array

[kunalspathak]

For Jagged array, it is not possible to hoist the column length check out of the loop, however it should be possible for 2D array or if we are doing loop cloning we should be able to generate a faster version of loop that doesn't have these checks.

static int Calculate(int[,] b, int col)
{
    int  result = 0;
    for (int i = 1; i < 10; i++)
    {
        result = result + b[i,col];
    }
    return result;
}

G_M3911_IG01:
       4883EC28             sub      rsp, 40
                                                ;; bbWeight=1    PerfScore 0.25
G_M3911_IG02:
       33C0                 xor      eax, eax
       41B801000000         mov      r8d, 1
                                                ;; bbWeight=1    PerfScore 0.50
G_M3911_IG03:
       458BC8               mov      r9d, r8d
       442B4918             sub      r9d, dword ptr [rcx+24]
       443B4910             cmp      r9d, dword ptr [rcx+16]
       732E                 jae      SHORT G_M3911_IG05            # <-- can be outside the loop
       448BD2               mov      r10d, edx
       442B511C             sub      r10d, dword ptr [rcx+28]
       443B5114             cmp      r10d, dword ptr [rcx+20]
       7321                 jae      SHORT G_M3911_IG05           # <-- can be outside the loop
       448B5914             mov      r11d, dword ptr [rcx+20]
       4D0FAFD9             imul     r11, r9
       4D8BCA               mov      r9, r10
       4D03CB               add      r9, r11
       4203448920           add      eax, dword ptr [rcx+4*r9+32]
       41FFC0               inc      r8d
       4183F80A             cmp      r8d, 10
       7CCA                 jl       SHORT G_M3911_IG03
                                                ;; bbWeight=4    PerfScore 74.00
G_M3911_IG04:
       4883C428             add      rsp, 40
       C3                   ret
                                                ;; bbWeight=1    PerfScore 1.25
G_M3911_IG05:
       E8445D4A5F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3

category:cq
theme:range-check
skill-level:expert
cost:large

[kunalspathak]

Example of simple case where array/index are not part of argument.

static int InnerProduct()
{
    int[,] b = new int[,] { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } };
    int  result = 0;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            result = result + b[i,j];
        }
    }
    return result;
}

Generates

G_M64019_IG03:
        52800003          mov     w3, #0
                                                ;; bbWeight=4    PerfScore 2.00
G_M64019_IG04:
        B9401804          ldr     w4, [x0,#24]
        4B040045          sub     w5, w2, w4
        B9401004          ldr     w4, [x0,#16]
        6B0400BF          cmp     w5, w4
        540002A2          bhs     G_M64019_IG08
        2A0503E4          mov     w4, w5
        B9401C05          ldr     w5, [x0,#28]
        4B050066          sub     w6, w3, w5
        B9401405          ldr     w5, [x0,#20]
        6B0500DF          cmp     w6, w5
        540001E2          bhs     G_M64019_IG08
        B9401405          ldr     w5, [x0,#20]
        9B0418A4          madd    x4, x5, x4, x6
        8B040805          add     x5, x0, x4, LSL #2
        B94020A4          ldr     w4, [x5,#32]
        0B010081          add     w1, w4, w1
        11000463          add     w3, w3, #1
        7100087F          cmp     w3, #2
        54FFFDCB          blt     G_M64019_IG04
                                                ;; bbWeight=16    PerfScore 496.00
G_M64019_IG05:
        11000442          add     w2, w2, #1
        7100085F          cmp     w2, #2
        54FFFD4B          blt     G_M64019_IG03
                                                ;; bbWeight=4    PerfScore 8.00
...
                                                ;; bbWeight=1    PerfScore 2.00
G_M64019_IG08:
        97FF6496          bl      CORINFO_HELP_RNGCHKFAIL
        D43E0000          bkpt

[kunalspathak]

This need to happen in .NET 6.0

[kunalspathak]

I don't think we will have bandwidth to do this in .NET 6.0. Marking this for future.