Excessive/strange null reference checks after method inlining

[voinokin]

Consider the following repro example (this is actually from the live system, just narrowed down significantly):

        interface ISortKeyOps<TComparableKeyPart>
        {
            TComparableKeyPart EmptyComparableKeyPart { get; }
            byte GetComparableKeyPartsLCPInfo(TComparableKeyPart left, ref TComparableKeyPart right);
        }

        struct SortKeyOps_UInt64 : ISortKeyOps<ulong>
        {
            public ulong EmptyComparableKeyPart { get { return 0; } }

            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            public byte GetComparableKeyPartsLCPInfo(ulong left, ref ulong right) => 0x42;
        }

        struct SortKeysClassifier<TKeyOps, TComparableKeyPart>
            where TKeyOps : ISortKeyOps<TComparableKeyPart>
            where TComparableKeyPart : struct
        {
            TKeyOps KeyOps;
            ulong CurrentKeyPartOfst;
            TComparableKeyPart[] SplittersTree;

            public SortKeysClassifier(TKeyOps keyOps)
            {
                KeyOps = keyOps;
                CurrentKeyPartOfst = 5;
                SplittersTree = new TComparableKeyPart[0];
            }

            unsafe public byte Build()
            {
                var emptyKey = KeyOps.EmptyComparableKeyPart;
                return KeyOps.GetComparableKeyPartsLCPInfo(KeyOps.EmptyComparableKeyPart, ref emptyKey);
            }
        }

        unsafe static void Main(string[] args)
        {
            var keyOps = new SortKeyOps_UInt64();
            var c = new SortKeysClassifier<SortKeyOps_UInt64, ulong>(keyOps);
            var v = c.Build();
            Console.WriteLine(v);
        }

When the nested code within method Build() is inlined with .NET Core 2.1 (preview/RC/RTM) JIT, the following machine code is observed:

--- ...\Program2.cs ---
                var emptyKey = KeyOps.EmptyComparableKeyPart;
000007FE69DF1850  cmp         dword ptr [rcx],ecx  
                return KeyOps.GetComparableKeyPartsLCPInfo(KeyOps.EmptyComparableKeyPart, ref emptyKey);
000007FE69DF1852  cmp         dword ptr [rcx],ecx  
000007FE69DF1854  cmp         dword ptr [rcx],ecx  
000007FE69DF1856  mov         eax,42h  
000007FE69DF185B  ret  
--- No source file -------------------------------------------------------------

Although the code works (disregarding penalty for unneeded operations), there are certain unclarities about this:

1. It is unclear why checking for null reference more than once (if at all) if this stored in ECX never changes. To add to this - I've seen up to 8-10 such null reference checks stacked when complex expression is involved in full production code.
2. [The strangest one] ALL null checks disappear, if I remove field SplittersTree and all references to it from structure.

category:cq
theme:value-numbering
skill-level:expert
cost:medium

[RussKeldorph]

@dotnet/jit-contrib

[ArtBlnd]

Can I see IR dumps before inlining? with SplitterTree.

[voinokin]

I don't have tools ready yet to get IR. Please feel free to use the source code for repro if you're going to poach with this issue before I'll be able to provide IR (1 week maybe).

[AndyAyersMS]

I looked into this. One null check is possibly needed to preserve exception semantics, but 3 consecutive does seem unnecessary.

The culprit is here:
https://github.com/dotnet/coreclr/blob/bcabe118b783feb489c791e340f1c3ea792acde2/src/jit/assertionprop.cpp#L969-L972
I don't understand the need for the second half of the test here, as just above this we've explicitly narrowed things to TYP_REF and TYP_BYREF. We are trying to walk back from a byref to a plain gc ref, but if we end up on a byref's value number, it seems perfectly fine to assert that it is non null.

@briansull does this make sense? If so I'll put up a PR.

This blocks a non-null assertion from propagating that would eliminate the other two checks:

 ; Assembly listing for method SortKeysClassifier`2[SortKeyOps_UInt64,UInt64][SortKeyOps_UInt64,System.UInt64]:Build():ubyte:this
 ; Emitting BLENDED_CODE for X64 CPU with AVX
 ; optimized code
 ; rsp based frame
 ; partially interruptible
 ; Final local variable assignments
 ;
-;  V00 this         [V00,T00] (  5,  5   )   byref  ->  rcx         this
+;  V00 this         [V00,T00] (  4,  4   )   byref  ->  rcx         this
 ;* V01 loc0         [V01    ] (  0,  0   )    long  ->  zero-ref    ld-addr-op
 ;# V02 OutArgs      [V02    ] (  1,  1   )  lclBlk ( 0) [rsp+0x00]
 ;* V03 tmp1         [V03    ] (  0,  0   )   byref  ->  zero-ref
 G_M2022_IG01:

 G_M2022_IG02:
-       3909                 cmp      dword ptr [rcx], ecx
-       3909                 cmp      dword ptr [rcx], ecx
        3909                 cmp      dword ptr [rcx], ecx
        B842000000           mov      eax, 66

 G_M2022_IG03:
        C3                   ret

-; Total bytes of code 12, prolog size 0 for method SortKeysClassifier`2[SortKeyOps_UInt64,UInt64][SortKeyOps_UInt64,System.UInt64]:Build():ubyte:this
+; Total bytes of code 8, prolog size 0 for method SortKeysClassifier`2[SortKeyOps_UInt64,UInt64][SortKeyOps_UInt64,System.UInt64]:Build():ubyte:this

[AndyAyersMS]

Allowing this assertion to propagate generally does good things (especially in a bunch of async-inspired MoveNext methods), but causes a few sizeable regressions. Haven't root-caused the regressions just yet, but suspect maybe the new assertions are causing other useful assertions to get dropped.

@briansull do we have data anywhere on how many assertions get dropped because of size limits? If not maybe I'll start a side project to find out. Might be a good excuse to build up those general purpose metrics we have been thinking about....

[voinokin]

Not sure whether this is related or not
Here's another example where null reference checks are not uniform:

[StructLayout(LayoutKind.Sequential, Size = 16)]
struct PermuteDataRecord<TComparableKeyPart>
    where TComparableKeyPart : unmanaged
{
    public uint Ofst;
    public uint Length;
    public TComparableKeyPart CachedKeyPart;
}

[StructLayout(LayoutKind.Sequential)]
unsafe struct PermuteBuffer<TComparableKeyPart>
    where TComparableKeyPart : unmanaged
{
    PermuteDataRecord<TComparableKeyPart>[] Records;
    GCHandle Pinner;

    public PermuteBuffer(PermuteDataRecord<TComparableKeyPart>[] records)
    {
        Records = records;
        Pinner = GCHandle.Alloc(Records, GCHandleType.Pinned);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public ref PermuteDataRecord<TComparableKeyPart> GetIndexer() => ref Records[0];

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public ref TComparableKeyPart GetCachedKeyPartRef(ref PermuteDataRecord<TComparableKeyPart> indexer) => ref indexer.CachedKeyPart;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public TComparableKeyPart* GetCachedKeyPartPtrDirect(ref PermuteDataRecord<TComparableKeyPart> indexer)
    {
        return (TComparableKeyPart*)Unsafe.AsPointer(ref indexer.CachedKeyPart);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public TComparableKeyPart* GetCachedKeyPartPtrUnsafe(ref PermuteDataRecord<TComparableKeyPart> indexer)
    {
        return (TComparableKeyPart*)Unsafe.AsPointer(ref Unsafe.Add(ref Unsafe.As<PermuteDataRecord<TComparableKeyPart>, byte>(ref indexer), sizeof(ulong)));
    }
}

static void Main(string[] args)
{
    PermuteBuffer<ulong> inst = new PermuteBuffer<ulong>(TestRecords);

    int ofst = 3;
    ref var indexer = ref Unsafe.Add(ref inst.GetIndexer(), ofst);

    ref ulong rKeyPartDirect = ref indexer.CachedKeyPart;
    ref ulong rKeyPartThruRefNormal = ref inst.GetCachedKeyPartRef(ref indexer);
    ref ulong rKeyPartThruRefThruPtrDirect = ref *inst.GetCachedKeyPartPtrDirect(ref indexer);
    ref ulong rKeyPartThruRefThruPtrUnsafe = ref *inst.GetCachedKeyPartPtrUnsafe(ref indexer);

    ulong keyPartDirect = rKeyPartDirect;
    ulong keyPartThruRefNormal = rKeyPartThruRefNormal;
    ulong keyPartThruRefThruPtrDirect = rKeyPartThruRefThruPtrDirect;
    ulong keyPartThruRefThruPtrUnsafe = rKeyPartThruRefThruPtrUnsafe;

    Console.WriteLine(
        "{0}: {1} {2} {3} {4}",
        indexer,
        keyPartDirect, keyPartThruRefNormal, keyPartThruRefThruPtrDirect, keyPartThruRefThruPtrUnsafe);
}

static PermuteDataRecord<ulong>[] TestRecords = new PermuteDataRecord<ulong>[5]
{
    new PermuteDataRecord<ulong> { CachedKeyPart = 0 },
    new PermuteDataRecord<ulong> { CachedKeyPart = 1 },
    new PermuteDataRecord<ulong> { CachedKeyPart = 2 },
    new PermuteDataRecord<ulong> { CachedKeyPart = 3 },
    new PermuteDataRecord<ulong> { CachedKeyPart = 4 },
};

000007FE6D3E17FF  lea         rcx,[rsi+10h]  <== get to first array element
000007FE6D3E1803  lea         rsi,[rcx+30h]  <== offset +3 elements

• ulong keyPartDirect = rKeyPartDirect; - check present

000007FE6D3E1807  cmp         dword ptr [rsi],esi  
000007FE6D3E1809  lea         rcx,[rsi+8]  

• ulong keyPartThruRefNormal = rKeyPartThruRefNormal; - check present

000007FE6D3E180D  cmp         dword ptr [rsi],esi  
000007FE6D3E180F  lea         rdx,[rsi+8]  

-ulong keyPartThruRefThruPtrDirect = rKeyPartThruRefThruPtrDirect; - check present

000007FE6D3E1813  cmp         dword ptr [rsi],esi  
000007FE6D3E1815  lea         rax,[rsi+8]  

-ulong keyPartThruRefThruPtrUnsafe = rKeyPartThruRefThruPtrUnsafe; - check ABSENT

000007FE6D3E1819  lea         r8,[rsi+8]  

(Then get all the values)

000007FE6D3E181D  mov         rdi,qword ptr [rcx]  
000007FE6D3E1820  mov         rbx,qword ptr [rdx]  
000007FE6D3E1823  mov         rbp,qword ptr [rax]  
000007FE6D3E1826  mov         r14,qword ptr [r8] 

[mikedn]

Might be a good excuse to build up those general purpose metrics we have been thinking about....

@AndyAyersMS Give me a couple of days (next weekend?), I'm trying to sketch something.

[briansull]

It is a fairly common occurance to run out of new assertions when compiling very large methods.

[briansull]

        //
        // We only perform null-checks on GC refs
        // so only make non-null assertions about GC refs
        //

The comment above is probably why we don't make the assertion when the type is a Byref
At one time we wanted to make a null Byref an impossibility, but it was eventually allowed.

Are we now performing null checks on byrefs generally?

[AndyAyersMS]

Did some crude stats gathering and we don't lose assertions all that often. Using PMI over FX:

Table Size	Num Methods	Avg Assertion Count	Methods with Dropped Assertions
64	159493	4.55	222
128	1801	42.3	28
256	237	81.2	4

The current size determination is keyed off of compILCodeSize and so doesn't take inlining into account.

We can probably estimate the likely number of assertions fairly cheaply, eg basic block count is fairly well correlated (R ~0.6) and blocks * 2.5 is a pretty good model for the 99.5 quantile of assertion counts.

[briansull]

We also must keep the BigOffset check, because the null check is a deref of the base pointer without the offset added.

if (fgIsBigOffset(offset) || (vnStore->TypeOfVN(vn) != TYP_REF))

[AndyAyersMS]

We are generating null checks in this case....

fgMorphTree BB01, stmt 1 (before)
               [000035] ------------              /--*  NOP       void  
               [000036] ---XG-------              *  COMMA     void  
               [000003] ---XG-------              \--*  ADDR      byref 
               [000002] ---XG-------                 \--*  FIELD     struct KeyOps
               [000001] ------------                    \--*  LCL_VAR   byref  V00 this         
Before explicit null check morphing:
               [000002] ---XG--N----              *  FIELD     struct KeyOps
               [000001] ------------              \--*  LCL_VAR   byref  V00 this         
After adding explicit null check:
               [000002] *--XG--N----              *  IND       struct
               [000053] ------------              |     /--*  CNS_INT   long   16 field offset Fseq[KeyOps]
               [000054] ------------              |  /--*  ADD       byref 
               [000052] ------------              |  |  \--*  LCL_VAR   byref  V00 this         
               [000055] ---X--------              \--*  COMMA     byref 
               [000051] ---X---N----                 \--*  NULLCHECK byte  
               [000050] ------------                    \--*  LCL_VAR   byref  V00 this         

fgMorphTree BB01, stmt 1 (after)
               [000035] -----+------              /--*  NOP       void  
               [000036] ---XG+------              *  COMMA     void  
               [000051] ---X-+-N----              \--*  NULLCHECK byte  
               [000050] -----+------                 \--*  LCL_VAR   byref  V00 this         

Maybe as a result of dotnet/coreclr#16492 -- perhaps this is kicking in even when we're jitting?

[briansull]

From your data we are currently dropping some assertsions in 1.6% of the medium and large methods.

[briansull]

Could we perhaps just add an explicit null check once for any TYP_BYREF arguments on their first use?

[AndyAyersMS]

I'm not sure we can always know when there is a suitable first use.

Notes for dotnet/coreclr#16492 show diffs but that was with crossgen and some diffs were expected (given the amount of R2R we have). I should go back and revisit that change with PMI diffs.

At any rate it seems like we should condition the new case introduced in dotnet/coreclr#16492 by also checking that we are actually prejitting. When jitting there is no mystery whether zero field offsets will remain zero.