Type check in shared generic doesn't eliminate casts to/from confirmed exact type

[benaadams]

From #49608 (review)

A type check e.g. if (typeof(T) == typeof(string)) in a shared generic doesn't eliminate casts to and from a confirmed exact type

using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

public class HashSet<T>
{
    private IEqualityComparer<T>? _comparer;

    public HashSet(IEqualityComparer<T>? comparer)
    {
        if (comparer is not null && comparer != EqualityComparer<T>.Default) 
        {
            _comparer = comparer;
        }

        if (typeof(T) == typeof(string))
        {
            // Double casts to concrete and back to generic not eliminated

            _comparer = (IEqualityComparer<T>?)
                NonRandomizedStringEqualityComparer.GetStringComparer(
                    (IEqualityComparer<string>?)_comparer);
        }
    }
}

public static class NonRandomizedStringEqualityComparer
{
    [MethodImpl(MethodImplOptions.NoInlining)]
    public static IEqualityComparer<string>? GetStringComparer(IEqualityComparer<string>? comparer)
    {
        return comparer;
    }
}

Data

Ideally the non Unsafe version:

if (typeof(T) == typeof(string))
{
    _comparer = (IEqualityComparer<T>?)NonRandomizedStringEqualityComparer
        .GetStringComparer((IEqualityComparer<string>?)_comparer);
}

Would produce the same asm as the Unsafe version:

if (typeof(T) == typeof(string))
{
    _comparer = Unsafe.As<IEqualityComparer<T>?>(
        NonRandomizedStringEqualityComparer.GetStringComparer(
            Unsafe.As<IEqualityComparer<string>?>(_comparer)));
}

However the regular casting includes a double cast even though its passed the typeof(TKey) == typeof(string) guard which implies the casts will always succeed.

G_M17833_IG07:
       mov      rcx, qword ptr [rsi]
       call     [CORINFO_HELP_READYTORUN_GENERIC_HANDLE]
       cmp      rax, qword ptr [(reloc)]
       jne      SHORT G_M17833_IG09
						;; bbWeight=1    PerfScore 8.00
G_M17833_IG08:
-      mov      rcx, qword ptr [rsi]
-      call     [CORINFO_HELP_READYTORUN_GENERIC_HANDLE]
-      mov      rdi, rax
       mov      rcx, gword ptr [rsi+24]
-      call     [CORINFO_HELP_READYTORUN_CHKCAST]
-      mov      rcx, rax
       call     [NonRandomizedStringEqualityComparer:GetStringComparer(IEqualityComparer`1):IEqualityComparer`1]
-      mov      rdx, rax
-      mov      rcx, rdi
-      call     [CORINFO_HELP_CHKCASTANY]
       lea      rcx, bword ptr [rsi+24]
       mov      rdx, rax
       call     [CORINFO_HELP_ASSIGN_REF]
-					;; bbWeight=0.50 PerfScore 10.38
+					;; bbWeight=0.50 PerfScore 4.38
G_M17833_IG09:
       nop      
						;; bbWeight=1    PerfScore 0.25

category:cq
theme:generics
skill-level:expert
cost:medium
impact:small

[AndyAyersMS]

Hmm, let me investigate.

[AndyAyersMS]

Assertion prop would be the place to catch this (the importer can't handle a conditional fact today, and is unlikely to be able to do so anytime soon).

And assertion prop doesn't' recognize this form of the class test:

N008 ( 23, 17) [000020] --CXG-------              *  JTRUE     void  
N007 ( 21, 15) [000017] J-CXG--N----              \--*  NE        int    $103
N004 ( 17,  8) [000008] --CXG-------                 +--*  CALL help r2r_ind long   HELPER.CORINFO_HELP_READYTORUN_GENERIC_HANDLE $203
N003 (  3,  2) [000007] #--X-------- arg0 in rcx     |  \--*  IND       long   $182
N002 (  1,  1) [000006] !-----------                 |     \--*  LCL_VAR   ref    V00 this         u:1 $80
N006 (  3,  6) [000013] #-----------                 \--*  IND       long   $188
N005 (  1,  4) [000012] H-----------                    \--*  CNS_INT(h) long   0xd1ffab1e class $1c4

The way AP is structured it is a bit hard to see what things it can handle, as it annoyingly splits out the "recognition" part from the "assertion gen" part. So it can recognize something and then end up not creating an assertion.

But in this case there's no recognition. This should happen in optAssertionGenJtrue. Currently the only form of "inline" type check this understands is when we have a GT_IND(GT_LCL_VAR) on one side. We'd need to generalize this to the case where we have to invoke a helper to figure out the object's type.

Once we have recognition we'd then need to generalize optCreateAssertion to re-recognize this case and generate a suitable subtype assertion.

[AndyAyersMS]

Above tree is for prejit -- when jitting we see the results of an inline expanded runtime lookup (and in this case, with an embedded CSE def):

N014 ( 18, 23) [000021] -A-X--------              *  JTRUE     void  
N013 ( 16, 21) [000020] JA-X---N----              \--*  NE        int    <l:$107, c:$106>
N011 ( 13, 10) [000012] nA-X--------                 +--*  IND       long   <l:$1c6, c:$1c5>
N010 ( 10,  8) [000161] -A-X--------                 |  \--*  COMMA     long   $14b
N008 (  9,  7) [000159] -A-X----R---                 |     +--*  ASG       long   $VN.Void
N007 (  1,  1) [000158] D------N----                 |     |  +--*  LCL_VAR   long   V10 cse2          $14b
N006 (  9,  7) [000011] #--X--------                 |     |  \--*  IND       long   $14b
N005 (  6,  5) [000010] #--X--------                 |     |     \--*  IND       long   $14a
N004 (  4,  3) [000009] ---X---N----                 |     |        \--*  ADD       long   $1c4
N002 (  3,  2) [000007] #--X--------                 |     |           +--*  IND       long   $142
N001 (  1,  1) [000006] !-----------                 |     |           |  \--*  LCL_VAR   ref    V00 this         u:1 $80
N003 (  1,  1) [000008] ------------                 |     |           \--*  CNS_INT   long   48 $c1
N009 (  1,  1) [000160] ------------                 |     \--*  LCL_VAR   long   V10 cse2          $14b
N012 (  2, 10) [000016] H-----------                 \--*  CNS_INT(h) long   0xd1ffab1e class $243

We would want to recognize the [000012] subtree as fetching the type of V00 this.

[AndyAyersMS]

Jitted case might be an example where we consider keeping / generalizing the "high level" wrapper IR around longer, so we can recognize what that big subtree means without having to explicitly pattern match it.

That is, early on in the jit we produce:

               [000021] ---X--------              *  JTRUE     void  
               [000020] ---X--------              \--*  NE        int   
               [000013] ---X--------                 +--*  RUNTIMELOOKUP long   0xd1ffab1e class
               [000012] n--X--------                 |  \--*  IND       long  
               [000011] #--X--------                 |     \--*  IND       long  
               [000010] #--X--------                 |        \--*  IND       long  
               [000009] ---X--------                 |           \--*  ADD       long  
               [000007] #--X--------                 |              +--*  IND       long  
               [000006] !-----------                 |              |  \--*  LCL_VAR   ref    V00 this         
               [000008] ------------                 |              \--*  CNS_INT   long   48
               [000016] H-----------                 \--*  CNS_INT(h) long   0xd1ffab1e class

which gives the gist of the idea. If we literally kept the above we'd still need to dig to find which local was being tested and deduce what was being looked up, but we'd at least know the diffing would pay off.

We might want something that describes the semantics more directly, but likely that means extra operands or operand like things... eg be able to view the operation both logically and in terms of the exact sequence of ops needed to carry it out.

But it's also possible this extra IR creates confusion.

[AndyAyersMS]

Going to try and do a quick assessment of how often we might see this.

[AndyAyersMS]

The jit lookup/compare pattern above isn't super common, maybe 80 hits across SPMI (out of ~750K methods, though some are crossgen so would not match)>

We would want to recognize the [000012] subtree as fetching the type of V00 this.

The above is incorrect.

What [000012] does is fetch the type of T from the dictionary, which is rooted by this. And the problem the jit faces is that knowing the type of T (or more precisely, knowing some dictionary slot must have a specific type in it at some point in the code) does not help the jit reason about what things it might find in other dictionary slots at that same point in the code. The jit has no way to know how the slot values are related.

So we either need to reason about this more abstractly, working back via tokens or sigs or something that describe these relationships, or else pass the buck over to the runtime an ask, "if we know dictionary slot X has value Y, what do we know about dictionary slot Z?"

This would help eliminate he first cast, where currently the jit says:

Considering optimization of castclass from 
00007FFD9731BA88 (System.Collections.Generic.IEqualityComparer`1[__Canon]) 
  to 
00007FFD9731BB58 (System.Collections.Generic.IEqualityComparer`1[[System.String, ...]])
  result of cast unknown, must generate runtime test

The jit should possibly be able to optimize away the second (outer) cast today even without knowing how the type are related:

Considering optimization of castclass from 
00007FFD9731BB58 (System.Collections.Generic.IEqualityComparer`1[[System.String, ...]]) 
   to 
00007FFD9731BA88 (System.Collections.Generic.IEqualityComparer`1[__Canon])

Seems like there is a missing case in CEEInfo::compareTypesForCast where we have an unshared from type and a shared to type, that we currently don't try to handle....

[benaadams]

In this example where we settled ended up with a single cast from IEqualityComparer<string>? to IEqualityComparer<TKey>? on the return; passing the TKey version as object since all the tests are ReferenceEquals

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs

Lines 65 to 72 in c569bc1

	if (typeof(TKey) == typeof(string))
	{
	IEqualityComparer<string>? stringComparer = NonRandomizedStringEqualityComparer.GetStringComparer(_comparer);
	if (stringComparer is not null)
	{
	_comparer = (IEqualityComparer<TKey>?)stringComparer;
	}
	}

[AndyAyersMS]

In this specific case the jit-time evaluation of the second cast is foiled by the contravariance of IEqualityComparer<T>.

So the jit can't remove that cast without knowing what __Canon really stands for, which brings us back to the dictionary problem mentioned above.

[AndyAyersMS]

Going to mark this as future.