[JIT] Range check elimination

[omariom]

I don't think there is perf impact. Just an interesting case which may point to something important.

The difference is in these lines:

mov      dword ptr [rcx+rax+16], r8d
lea      rax, bword ptr [rcx+rax+16]
;vs
lea      rax, bword ptr [rcx+rax+16]
mov      dword ptr [rax], r8d

[MethodImpl(MethodImplOptions.NoInlining)]
private static void TestRangeCheckElimination(Entry[] entries, int index, int value)
{
    entries[index].hashCode = value;
    entries[index].next     = value;
    entries[index].key      = value;
    entries[index].value    = value;
}

[MethodImpl(MethodImplOptions.NoInlining)]
private static void TestRangeCheckEliminationWithRef(Entry[] entries, int index, int value)
{
    ref Entry entry = ref entries[index];

    entry.hashCode = value;
    entry.next     = value;
    entry.key      = value;
    entry.value    = value;
}

Assembly for TestRangeCheckElimination

; Assembly listing for method TestDotNetCore.Program:TestRangeCheckElimination(ref,int,int)
; Emitting BLENDED_CODE for X64 CPU with AVX
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
;  V00 arg0         [V00,T00] ( 15, 15   )     ref  ->  rcx         class-hnd
;  V01 arg1         [V01,T03] ( 12, 12   )     int  ->  rdx        
;  V02 arg2         [V02,T01] ( 14, 14   )     int  ->   r8        
;  V03 OutArgs      [V03    ] (  1,  1   )  lclBlk (32) [rsp+0x00]  
;  V04 cse0         [V04,T02] ( 14, 14   )   byref  ->  rax        
;  V05 cse1         [V05,T04] ( 10, 10   )    long  ->  rax        
;  V06 cse2         [V06,T05] (  5,  5   )     int  ->  rax        
;
; Lcl frame size = 40

G_M10648_IG01:
       4883EC28             sub      rsp, 40

G_M10648_IG02:
       8B4108               mov      eax, dword ptr [rcx+8]
       3BD0                 cmp      edx, eax
       7322                 jae      SHORT G_M10648_IG04
       4863C2               movsxd   rax, edx
       48C1E004             shl      rax, 4
       4489440110           mov      dword ptr [rcx+rax+16], r8d
       488D440110           lea      rax, bword ptr [rcx+rax+16]
       44894004             mov      dword ptr [rax+4], r8d
       44894008             mov      dword ptr [rax+8], r8d
       4489400C             mov      dword ptr [rax+12], r8d

G_M10648_IG03:
       4883C428             add      rsp, 40
       C3                   ret      

G_M10648_IG04:
       E86E50305F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3     

; Total bytes of code 51, prolog size 4 for method 

Assembly for TestRangeCheckEliminationWithRe

; Assembly listing for method TestDotNetCore.Program:TestRangeCheckEliminationWithRef(ref,int,int)
; Emitting BLENDED_CODE for X64 CPU with AVX
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
;  V00 arg0         [V00,T02] (  4,  4   )     ref  ->  rcx         class-hnd
;  V01 arg1         [V01,T03] (  4,  4   )     int  ->  rdx        
;  V02 arg2         [V02,T01] (  6,  6   )     int  ->   r8        
;  V03 tmp0         [V03,T00] (  5, 10   )   byref  ->  rax        
;  V04 OutArgs      [V04    ] (  1,  1   )  lclBlk (32) [rsp+0x00]  
;
; Lcl frame size = 40

G_M60939_IG01:
       4883EC28             sub      rsp, 40

G_M60939_IG02:
       3B5108               cmp      edx, dword ptr [rcx+8]
       7320                 jae      SHORT G_M60939_IG04
       4863C2               movsxd   rax, edx
       48C1E004             shl      rax, 4
       488D440110           lea      rax, bword ptr [rcx+rax+16]
       448900               mov      dword ptr [rax], r8d
       44894004             mov      dword ptr [rax+4], r8d
       44894008             mov      dword ptr [rax+8], r8d
       4489400C             mov      dword ptr [rax+12], r8d

G_M60939_IG03:
       4883C428             add      rsp, 40
       C3                   ret      

G_M60939_IG04:
       E82250305F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3     

; Total bytes of code 47, prolog size 4 for method

cc @mikedn

category:cq
theme:basic-cq
skill-level:expert
cost:medium

[RussKeldorph]

@dotnet/jit-contrib

[mikedn]

I don't thinks there is perf impact. Just an interesting case which may point to something important. The difference is in this lines:

Hard to say if that particular difference has any perf impact. But that difference is not the real problem, the real problem is that lea is not eliminated. The code should look like this:

shl      rax, 4
mov      dword ptr [rcx+rax+16], r8d
mov      dword ptr [rcx+rax+20], r8d
mov      dword ptr [rcx+rax+24], r8d
mov      dword ptr [rcx+rax+28], r8d

This kind of LEA costs 3 cycles and in this context it doesn't save anything in terms of code size. Unfortunately getting the JIT to generate the proper code here isn't trivial.

[CarolEidt]

This kind of LEA costs 3 cycles and in this context it doesn't save anything in terms of code size. Unfortunately getting the JIT to generate the proper code here isn't trivial.

Yes, there are several issues here:

• Generally the JIT favors small code over faster code (at least, that's the historical bias)
• The code to handle addressing mode is complex, and spread out in several places.
• Finally, there's the fundamental phase-ordering problem of when the JIT should manifest the addressing modes. I have always been of the opinion that we should addressing modes early, and only for those addressing modes that are actually supported. Then the optimizing phases would at least have a chance of being able to reason about them.
  • That's the intent of the GTF_ADDRMODE_NO_CSE flag, but it isn't really accurate.

[mikedn]

The code generated by VC++ for the equivalent C++ code is funny:

template<typename T>
struct Array {
    void *vtbl;
    unsigned size;
    unsigned pad;
    T entries[0];
};
struct Entry {
    int a, b, c, d;
};
void Test(Array<Entry> *a, int x, int v) {
    Entry& e = a->entries[x];
    e.a = v;
    e.b = v;
    e.c = v;
    e.d = v;
}

48 63 C2             movsxd      rax,edx  
48 FF C0             inc         rax  
48 C1 E0 04          shl         rax,4  
48 03 C1             add         rax,rcx  
44 89 00             mov         dword ptr [rax],r8d  
44 89 40 04          mov         dword ptr [rax+4],r8d  
44 89 40 08          mov         dword ptr [rax+8],r8d  
44 89 40 0C          mov         dword ptr [rax+0Ch],r8d  
C3                   ret  

I would guess that it has a similar problem - some early phase does some expression optimizations and a later phase builds address modes. Though it's still strange that they can't at least push the add into the address mode operands.

[Suchiman]

Clang does it better on O1, and then seems to vectorize the code on O3

[benaadams]

For ref

Clang O1

  movsxd rax, esi
  shl rax, 4
  mov dword ptr [rdi + rax + 16], edx
  mov dword ptr [rdi + rax + 20], edx
  mov dword ptr [rdi + rax + 24], edx
  mov dword ptr [rdi + rax + 28], edx

Clang O3

  movsxd rax, esi
  shl rax, 4
  movd xmm0, edx
  pshufd xmm0, xmm0, 0                                            # xmm0 = xmm0[0,0,0,0]
  movdqu xmmword ptr [rdi + rax + 16], xmm0

[mikedn]

Yep, saw that. And for completeness GCC generates:

    movsx   rsi, esi
    sal     rsi, 4
    add     rdi, rsi
    mov     DWORD PTR [rdi+16], edx
    mov     DWORD PTR [rdi+20], edx
    mov     DWORD PTR [rdi+24], edx
    mov     DWORD PTR [rdi+28], edx

Different compiler, different codegen. The GCC/VC++ versions, wile apparently worse than Clang, may have an advantage in more complex code, they minimize register use because after add only one register is live instead of 2.

[omariom]

Interesting.
So CSE doesn't (always) work for CPUs?

[mikedn]

Well, it works but one needs to be careful not to overdo it. Or to undo it in case things turn out worse (e.g. https://en.wikipedia.org/wiki/Rematerialization).

And overdoing it can be particularly problematic in this JIT because its expression optimization facilities work only on a given expression tree at a time. CSE basically splits a tree into multiple trees by introducing temporary variables. This may block further transforms (such address mode building).