Redundant null checks in null-coalescing scenarios

[rameel]

JIT compiler generates redundant null checks in null-coalescing scenarios or after non-null assignment.

Example 1

public static ReadOnlySpan<char> Test1(string s)
{
    s = s ?? "";
    return s;
}

public static ReadOnlySpan<char> Test2(string s)
{
    var v = s ?? "";
    return v; // return s ?? ""
}

In Test1, the JIT does not eliminate the dead branch for the null value, even though s cannot be null after the null-coalescing operation. However, in Test2, the generated code is optimized.

Sample:Test1(System.String):System.ReadOnlySpan`1[ushort] (FullOpts):
       push     rbp
       mov      rbp, rsp
       mov      rax, 0x730E50600008      ; ''
       test     rdi, rdi
       cmove    rdi, rax
       test     rdi, rdi
       je       SHORT G_M33461_IG04
       lea      rax, bword ptr [rdi+0x0C]
       mov      edx, dword ptr [rdi+0x08]
       jmp      SHORT G_M33461_IG05
G_M33461_IG04:  ;; offset=0x0023
       xor      rax, rax
       xor      edx, edx
G_M33461_IG05:  ;; offset=0x0027
       pop      rbp
       ret      

Sample:Test2(System.String):System.ReadOnlySpan`1[ushort] (FullOpts):
       mov      rax, 0x730E50600008      ; ''
       test     rdi, rdi
       cmove    rdi, rax
       lea      rax, bword ptr [rdi+0x0C]
       mov      edx, dword ptr [rdi+0x08]
       ret      

Example 2

public static bool Test3(string s)
{
    var v = s != null ? s : "";
    return v != null;
}

public static bool Test4(string s)
{
    return (s ?? "") != null;
}

For Test3 and Test4, I expected the JIT to generate a simple return true, since the result of (s ?? "") can never be null. For example:

mov eax, 1
ret

However, the JIT generates explicit null checks instead:

Sample:Test3(System.String):ubyte (FullOpts):
       mov      rax, 0x730E50600008      ; ''
       test     rdi, rdi
       cmove    rdi, rax
       test     rdi, rdi
       setne    al
       movzx    rax, al
       ret      

Sample:Test4(System.String):ubyte (FullOpts):
       mov      rax, 0x730E50600008      ; ''
       test     rdi, rdi
       cmove    rdi, rax
       test     rdi, rdi
       setne    al
       movzx    rax, al
       ret      

Source code: godbolt

[dotnet-policy-service]

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

[EgorBo]

Looks like both of your Example 2 snippetes generate the expected codegen if you replace return <condition> with if <condition> return true/false.

This problem is expected to be fixed by #107499

[EgorBo]

Example 1 seems to be a different issue, from a quick look smells like jump-threading + phi?

public static ReadOnlySpan<char> Test1(string s)
{
    s = s ?? "";
    return s;
}

cc @AndyAyersMS

[AndyAyersMS]

Example 1 seems to be a different issue, from a quick look smells like jump-threading + phi?

Yep...We can't jump thread since the PHI def in BB03 is also used elsewhere, and we don't know how to revise those uses to be either V03.1 or V03.2

--- Trying RBO in BB03 ---
Relop [000021] BB03 value unknown, trying inference
BB03 has global phi for V03.3; no phi-based threading

------------ BB03 [0002] [00A..00D) -> BB05(0.5),BB04(0.5) (cond), preds={BB01,BB02} succs={BB04,BB05}

***** BB03 [0002]
STMT00025 ( ??? ... ??? )
N004 (  0,  0) [000118] DA---------                         *  STORE_LCL_VAR ref    V03 tmp1         d:3 $VN.Void
N003 (  0,  0) [000117] -----------                         \--*  PHI       ref    $200
N001 (  0,  0) [000120] ----------- pred BB02                  +--*  PHI_ARG   ref    V03 tmp1         u:2 $1c0
N002 (  0,  0) [000119] ----------- pred BB01                  \--*  PHI_ARG   ref    V03 tmp1         u:1 $c0

***** BB03 [0002]
STMT00007 ( INL01 @ 0x000[E-] ... ??? ) <- INLRT @ 0x00C[E-]
N004 (  5,  5) [000022] -----+-----                         *  JTRUE     void   $VN.Void
N003 (  3,  3) [000021] J----+-N---                         \--*  NE        int    $181
N001 (  1,  1) [000010] -----+-----                            +--*  LCL_VAR   ref    V03 tmp1         u:3 $200
N002 (  1,  1) [000020] -----+-----                            \--*  CNS_INT   ref    null $VN.Null

[AndyAyersMS]

Local assertion prop in morph should get this, but it fumbles. We have

Morphing BB01
BB01 ineligible for cross-block
Assertions in: #NA
fgMorphTree BB01, STMT00001 (before)
               [000005] DA---------                         *  STORE_LCL_VAR ref    V03 tmp1         
               [000000] -----------                         \--*  LCL_VAR   ref    V01 arg0         
GenTreeNode creates assertion:
               [000005] DA---+-----                         *  STORE_LCL_VAR ref    V03 tmp1         
In BB01 New Local Copy     Assertion: V03 == V01, index = #01

fgMorphTree BB01, STMT00000 (before)
               [000004] -----------                         *  JTRUE     void  
               [000003] -----------                         \--*  NE        int   
               [000001] -----------                            +--*  LCL_VAR   ref    V01 arg0          (last use)
               [000002] -----------                            \--*  CNS_INT   ref    null
GenTreeNode creates assertion:
               [000004] -----+-----                         *  JTRUE     void  
In BB01 New Local Constant Assertion: V01 != null, index = #02
GenTreeNode creates assertion:
               [000004] -----+-----                         *  JTRUE     void  
In BB01 New Local Constant Assertion: V01 == null, index = #03
GenTreeNode creates assertion:
               [000004] -----+-----                         *  JTRUE     void  
In BB01 New Local Subrange Assertion: V01 in [0..1], index = #04

...

Morphing BB03
Using `if true` assertions from pred BB01
Assertions in: #NA
fgMorphTree BB03, STMT00002 (before)
               [000009] DA---------                         *  STORE_LCL_VAR ref    V01 arg0         
               [000008] -----------                         \--*  LCL_VAR   ref    V03 tmp1          (last use)
GenTreeNode creates assertion:
               [000009] DA---+-----                         *  STORE_LCL_VAR ref    V01 arg0         
In BB03 New Local Copy     Assertion: V01 == V03, index = #06

fgMorphTree BB03, STMT00007 (before)
               [000022] -----------                         *  JTRUE     void  
               [000021] -----------                         \--*  NE        int   
               [000010] -----------                            +--*  LCL_VAR   ref    V01 arg0         
               [000020] -----------                            \--*  CNS_INT   ref    null

GenTreeNode creates assertion:
               [000022] -----+-----                         *  JTRUE     void  
In BB03 New Local Constant Assertion: V03 != null, index = #07
GenTreeNode creates assertion:
               [000022] -----+-----                         *  JTRUE     void  
In BB03 New Local Constant Assertion: V03 == null, index = #08
GenTreeNode creates assertion:
               [000022] -----+-----                         *  JTRUE     void  
In BB03 New Local Subrange Assertion: V03 in [0..1], index = #09

fgMorphTree BB03, STMT00007 (after)
               [000022] -----+-----                         *  JTRUE     void  
               [000021] J----+-N---                         \--*  NE        int   
               [000010] -----+-----                            +--*  LCL_VAR   ref    V03 tmp1         
               [000020] -----+-----                            \--*  CNS_INT   ref    null

In BB03 the assignment kills the information about V01, even though it is equal to V03. We then copy prop V03 onto V01 and have no info about V03.

We could add assertions about V03 when we see [000004], since we know at that point V01 == V03, and then we'd get this cleaned up in global morph. And if for some reason we didn't copy prop we could preserve the assertions about V01 at [000009] since again we know at that point V01 == V03.

Also it is wrong to create subrange assertions for TYP_REF. That one is my fault.

[EgorBo]

@AndyAyersMS I've filed a PR to fix it in global assertprop #111985

It shows nice diffs and presumably can find more cases because we also rely on VN with its powerful IsKnownNonNull(vn) that may look further than local prop. However, I suspect my pr may come with terrible TP regressions, so if this can be done in local prop while maintaining diffs I guess it should be done there?

[AndyAyersMS]

Seems like we should optimize away [000009] since it is assigning a local a value it already has, that would likely also fix this and might prevent some ping-pong copy prop like we see here.

And this bit seems odd, we should have the copy and non-null assertions here...

Morphing BB03
Using `if true` assertions from pred BB01
Assertions in: #NA

[AndyAyersMS]

Ah, no, I am being a bit dumb. BB03 also has BB02 as a pred.

So the fix here is more complex. When we see V03 = cns in BB02, we should also generate V03 != null. When we generate the true condition V01 == null at the end of BB01, and we have V03 == V01, we should also generate V03 != null. Then these two will merge at BB03, and we can remove the branch.

[AndyAyersMS]

I wonder how costly this sort of assertion flooding ends up being.

The root issue is that assertion merging is dumb, it literally requires the same exact assertion (each assertion is given a unique BV bit, and we just intersect BVs). Either we have to generalize the merging logic (which seems expensive) or we manifest all the implied assertions at gen time (which also may be expensive).

VN based AP is perhaps a bit less prone to this, but not immune.

Probably worth an experiment.