JIT might emit unnecessary null check when enumerating arrays of KVP

[GrabYourPitchforks]

Reported via Discord. A null check is being emitted that we'd reasonably expect to have been elided. Repro code:

    public long EnumerateKvps(KeyValuePair<string, int>[] kvps)
    {
        long result = 0;
        
        foreach (var kvp in kvps)
        {
            result += kvp.Value;
        }
        
        return result;
    }

Codegen, x64 release (per sharplab):

C.EnumerateKvps(System.Collections.Generic.KeyValuePair`2<System.String,Int32>[])
    L0000: xor eax, eax
    L0002: xor ecx, ecx
    L0004: mov r8d, [rdx+8]
    L0008: test r8d, r8d
    L000b: jle short L0030
    L000d: nop [rax]
    L0010: movsxd r9, ecx
    L0013: shl r9, 4
    L0017: lea r9, [rdx+r9+0x10]
    L001c: cmp [r9], r9d  ; <-- this null check should have been elided
    L001f: mov r9d, [r9+8]
    L0023: movsxd r9, r9d
    L0026: add rax, r9
    L0029: inc ecx
    L002b: cmp r8d, ecx
    L002e: jg short L0010
    L0030: ret

L0017 - L0023 taken as a whole are interesting. It seems like all of those lines could have been the single instruction movsxd r9, [rdx + r9 + 0x18]. But for some reason, on L001f and L0023, the two instructions are not being folded into one another.

category:cq
theme:structs
skill-level:expert
cost:medium
impact:medium

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

Issue Details

---

Reported via Discord. A null check is being emitted that we'd reasonably expect to have been elided. Repro code:

    public long EnumerateKvps(KeyValuePair<string, int>[] kvps)
    {
        long result = 0;
        
        foreach (var kvp in kvps)
        {
            result += kvp.Value;
        }
        
        return result;
    }

Codegen, x64 release (per sharplab):

C.EnumerateKvps(System.Collections.Generic.KeyValuePair`2<System.String,Int32>[])
    L0000: xor eax, eax
    L0002: xor ecx, ecx
    L0004: mov r8d, [rdx+8]
    L0008: test r8d, r8d
    L000b: jle short L0030
    L000d: nop [rax]
    L0010: movsxd r9, ecx
    L0013: shl r9, 4
    L0017: lea r9, [rdx+r9+0x10]
    L001c: cmp [r9], r9d  ; <-- this null check should have been elided
    L001f: mov r9d, [r9+8]
    L0023: movsxd r9, r9d
    L0026: add rax, r9
    L0029: inc ecx
    L002b: cmp r8d, ecx
    L002e: jg short L0010
    L0030: ret

L0017 - L0023 taken as a whole are interesting. It seems like all of those lines could have been the single instruction movsxd r9, [rdx + r9 + 0x18]. But for some reason, on L001f and L0023, the two instructions are not being folded into one another.

Author:	GrabYourPitchforks
Assignees:	-
Labels:	tenet-performance, area-CodeGen-coreclr
Milestone:	-

[EgorBo]

Minimal repro:

public struct Foo
{
    long key;
    long value;

    public long Value => value;
}

long Test(Foo[] f)
{
    Foo c = f[0];
    return c.Value;
}

First of all it looks like a missing forward sub opportunity:

[jakobbotsch]

First of all it looks like a missing forward sub opportunity:

We cannot forward sub under an ADDR node.

To me it looks like the problem is that when we copy from the array, we introduce a field-by-field copy, and the key is unused here so it is converted from an indirection to a null check. We do not manage to remove this null check even though there will be a dereference of a "related" field (the value) in the future that will do the null check.

[jakobbotsch]

We cannot forward sub under an ADDR node.

I suppose the forward sub part doesn't have anything to do with the ADDR node since LocalAddressVisitor is already replacing that entire tree with the promoted local. We do not handle the assignment until morph, and it's hard for forward sub to do much with the block assignment and field read.

[jakobbotsch]

Even in the "forward" direction we do not manage to elide the copy of the unused field:

public struct Foo
{
    public long key;
    public long value;

    public long Key => key;
    public long Value => value;
}

[MethodImpl(MethodImplOptions.NoInlining)]
static long Test(Foo[] f)
{
    Foo c = f[0];
    return c.Key;
}

; Assembly listing for method Runtime_67223:Test(Runtime_67223+Foo[]):long
; Emitting BLENDED_CODE for X64 CPU with AVX - Windows
; optimized code
; rsp based frame
; partially interruptible
; No PGO data
; 0 inlinees with PGO data; 1 single block inlinees; 0 inlinees without PGO data
; Final local variable assignments
;
;  V00 arg0         [V00,T00] (  4,  4   )     ref  ->  rcx         class-hnd single-def
;* V01 loc0         [V01    ] (  0,  0   )  struct (16) zero-ref    ld-addr-op
;  V02 OutArgs      [V02    ] (  1,  1   )  lclBlk (32) [rsp+00H]   "OutgoingArgSpace"
;  V03 tmp1         [V03,T02] (  2,  2   )    long  ->  rax         single-def V01.key(offs=0x00) P-INDEP "field V01.key (fldOffset=0x0)"
;* V04 tmp2         [V04    ] (  0,  0   )    long  ->  zero-ref    single-def V01.value(offs=0x08) P-INDEP "field V01.value (fldOffset=0x8)"
;  V05 tmp3         [V05,T01] (  3,  6   )   byref  ->  rcx         single-def "BlockOp address local"
;
; Lcl frame size = 40

G_M39532_IG01:              ;; offset=0000H
       4883EC28             sub      rsp, 40
                                                ;; size=4 bbWeight=0    PerfScore 0.00
G_M39532_IG02:              ;; offset=0004H
       83790800             cmp      dword ptr [rcx+8], 0
       760F                 jbe      SHORT G_M39532_IG04
       4883C110             add      rcx, 16
       488B01               mov      rax, qword ptr [rcx]
       8B5108               mov      edx, dword ptr [rcx+8]    ; unnecessary
                                                ;; size=16 bbWeight=1    PerfScore 8.25
G_M39532_IG03:              ;; offset=0014H
       4883C428             add      rsp, 40
       C3                   ret
                                                ;; size=5 bbWeight=1    PerfScore 1.25
G_M39532_IG04:              ;; offset=0019H
       E8B201585F           call     CORINFO_HELP_RNGCHKFAIL
       CC                   int3
                                                ;; size=6 bbWeight=0    PerfScore 0.00

; Total bytes of code 31, prolog size 4, PerfScore 12.60, instruction count 10, allocated bytes for code 31 (MethodHash=f0d86593) for method Runtime_67223:Test(Runtime_67223+Foo[]):long
; ============================================================

[jakobbotsch]

Codegen diff with #81095:

@@ -8,16 +8,15 @@
 ; Final local variable assignments
 ;
 ;* V00 this         [V00    ] (  0,  0   )     ref  ->  zero-ref    this class-hnd single-def
-;  V01 arg1         [V01,T06] (  3,  3   )     ref  ->  rdx         class-hnd single-def
-;  V02 loc0         [V02,T02] (  4, 10   )    long  ->  rax        
-;  V03 loc1         [V03,T04] (  3,  6   )     ref  ->  rdx         class-hnd single-def
-;  V04 loc2         [V04,T01] (  5, 17   )     int  ->  rcx        
+;  V01 arg1         [V01,T05] (  3,  3   )     ref  ->  rdx         class-hnd single-def
+;  V02 loc0         [V02,T01] (  4, 10   )    long  ->  rax        
+;  V03 loc1         [V03,T03] (  3,  6   )     ref  ->  rdx         class-hnd single-def
+;  V04 loc2         [V04,T00] (  5, 17   )     int  ->  rcx        
 ;* V05 loc3         [V05    ] (  0,  0   )  struct (16) zero-ref    ld-addr-op
 ;# V06 OutArgs      [V06    ] (  1,  1   )  lclBlk ( 0) [rsp+00H]   "OutgoingArgSpace"
 ;* V07 tmp1         [V07    ] (  0,  0   )     ref  ->  zero-ref    V05.key(offs=0x00) P-INDEP "field V05.key (fldOffset=0x0)"
-;  V08 tmp2         [V08,T03] (  2,  8   )     int  ->   r9         V05.value(offs=0x08) P-INDEP "field V05.value (fldOffset=0x8)"
-;  V09 tmp3         [V09,T00] (  3, 24   )   byref  ->   r9         "BlockOp address local"
-;  V10 cse0         [V10,T05] (  3,  6   )     int  ->   r8         "CSE - aggressive"
+;  V08 tmp2         [V08,T02] (  2,  8   )     int  ->   r9         V05.value(offs=0x08) P-INDEP "field V05.value (fldOffset=0x8)"
+;  V09 cse0         [V09,T04] (  3,  6   )     int  ->   r8         "CSE - aggressive"
 ;
 ; Lcl frame size = 0
 
@@ -34,19 +33,17 @@ G_M51593_IG02:
 G_M51593_IG03:
        mov      r9d, ecx
        shl      r9, 4
-       lea      r9, bword ptr [rdx+r9+10H]
-       cmp      dword ptr [r9], r9d
-       mov      r9d, dword ptr [r9+08H]
+       mov      r9d, dword ptr [rdx+r9+18H]
        movsxd   r9, r9d
        add      rax, r9
        inc      ecx
        cmp      r8d, ecx
        jg       SHORT G_M51593_IG03
-						;; size=32 bbWeight=4 PerfScore 35.00
+						;; size=25 bbWeight=4 PerfScore 19.00
 G_M51593_IG04:
        ret      
 						;; size=1 bbWeight=1 PerfScore 1.00
 
-; Total bytes of code 49, prolog size 0, PerfScore 44.90, instruction count 17, allocated bytes for code 49 (MethodHash=b5703676) for method Program:EnumerateKvps(System.Collections.Generic.KeyValuePair`2[System.String,int][]):long:this
+; Total bytes of code 42, prolog size 0, PerfScore 28.20, instruction count 15, allocated bytes for code 42 (MethodHash=b5703676) for method Program:EnumerateKvps(System.Collections.Generic.KeyValuePair`2[System.String,int][]):long:this
 ; ============================================================

To get the contained movsxd we would need some later forward sub pass, we currently end up with the indexing and int->long cast in two separate statements.

[jakobbotsch]

To get the contained movsxd we would need some later forward sub pass, we currently end up with the indexing and int->long cast in two separate statements.

Actually, it would maybe be possible to teach early forward sub to handle it, we do have the necessary information at that point for it:

***** BB02
STMT00004 ( 0x009[E-] ... 0x010 )
               [000020] -A-XG------                         ▌  ASG       struct (copy)
               [000019] D------N---                         ├──▌  LCL_VAR   struct<System.Collections.Generic.KeyValuePair`2, 16>(P) V05 loc3         
                                                            ├──▌    ref    V05.System.Collections.Generic.KeyValuePair`2[System.__Canon,int]:key (offs=0x00) -> V07 tmp1          (last use)
                                                            ├──▌    int    V05.System.Collections.Generic.KeyValuePair`2[System.__Canon,int]:value (offs=0x08) -> V08 tmp2         
               [000018] ---XG------                         └──▌  OBJ       struct<System.Collections.Generic.KeyValuePair`2, 16>
               [000017] ---XG------                            └──▌  INDEX_ADDR byref System.Collections.Generic.KeyValuePair`2[]
               [000015] -----------                               ├──▌  LCL_VAR   ref    V03 loc1         
               [000016] -----------                               └──▌  LCL_VAR   int    V04 loc2         

***** BB02
STMT00006 ( 0x011[E-] ... ??? )
               [000029] -AC--------                         ▌  ASG       long  
               [000028] D------N---                         ├──▌  LCL_VAR   long   V02 loc0         
               [000027] --C--------                         └──▌  ADD       long  
               [000021] -----------                            ├──▌  LCL_VAR   long   V02 loc0          (last use)
               [000026] --C--------                            └──▌  CAST      long <- int
               [000038] -----------                               └──▌  LCL_VAR   int    V08 tmp2          (last use)

It would require some of the block morphing logic as part of forward sub though, and I'm not sure how valuable it would be.