Proposed: C# compiler could use flow analysis to track types in variables permitting the use of a constrained instruction on virtual calls.

[benaadams]

Boxing for isinst aside https://github.com/dotnet/coreclr/issues/12877 it would be nice if Pattern Matching issued a constrained instruction prior to callvirt where a generic type was matched to an interface

Version Used:

Microsoft Visual Studio Enterprise 2017
Version 15.3.4
VisualStudio.15.Release/15.3.4+26730.15
C#7

Steps to Reproduce:

int key0, key1;
PatternMatchEquality<int>.Equals(key0, key1)

Where

public class PatternMatchEquality<TKey>
{
    private static readonly EqualityComparer<TKey> _defaultComparer = EqualityComparer<TKey>.Default;

    public static bool Equals(TKey key0, TKey key1)
    {
        switch (key0)
        {
            case IEquatable<TKey> key:
                return key.Equals(key1);
            default:
                //return _defaultComparer.Equals(key0, key1);
                throw new Exception();
        }
    }
}

Expected Behavior:

il output

ldarg.1      // key1
constrained. !0/*TKey*/ <--------
callvirt     instance bool class [System.Runtime]System.IEquatable`1<!0/*TKey*/>::Equals(!0/*TKey*/)
ret        

Actual Behavior:

il output

  .method public hidebysig static bool 
    Equals(
      !0/*TKey*/ key0, 
      !0/*TKey*/ key1
    ) cil managed 
  {
    .maxstack 2
    .locals init (
      [0] !0/*TKey*/ V_0,
      [1] class [System.Runtime]System.IEquatable`1<!0/*TKey*/> V_1
    )

    // [185 13 - 185 26]
    IL_0000: ldarg.0      // key0
    IL_0001: stloc.0      // V_0
    IL_0002: ldloc.0      // V_0
    IL_0003: box          !0/*TKey*/
    IL_0008: brfalse.s    IL_0021
    IL_000a: ldloc.0      // V_0
    IL_000b: box          !0/*TKey*/
    IL_0010: isinst       class [System.Runtime]System.IEquatable`1<!0/*TKey*/>
    IL_0015: dup          
    IL_0016: stloc.1      // V_1
    IL_0017: brfalse.s    IL_0021

    IL_0019: ldloc.1      // V_1

    // [188 21 - 188 45]
    IL_001a: ldarg.1      // key1
    // <------- No constrained. !0
    IL_001b: callvirt     instance bool class [System.Runtime]System.IEquatable`1<!0/*TKey*/>::Equals(!0/*TKey*/)
    IL_0020: ret          

    // [190 22 - 190 44]
    IL_0021: newobj       instance void [System.Runtime]System.Exception::.ctor()
    IL_0026: throw        

  } // end of method PatternMatchEquality`1::Equals

/cc @gafter @AlekseyTs @agocke

[gafter]

This has nothing to do with pattern-matching. It produces the same instructions for key.Equals(key1) no matter where key is declared. e.g. it produces the same code for this

    public static bool Equals(IEquatable<TKey> key, TKey key1)
    {
        return key.Equals(key1);
    }

[gafter]

I see, though, why you suggest the constraint (since the receiver is "known" to be a TKey). However, the variable key is mutable, which means it is not constrained by the C# compiler to only contain a variable of type TKey. The C# compiler does not use any kind of flow-analysis to determine the concrete types of objects in variables for the purpose of issuing constrained calls when the type is known.

[benaadams]

As background... (from https://github.com/dotnet/coreclr/issues/12877#issuecomment-329247453)

The scenario I'm trying to cover is calling struct generics if the type implements the the interface; so in effect getting the benefit of having a generic constraint without one being present.

The example I was looking at was the default comparer on dictionary; which currently goes via hoops and inheritance to implement the constrained EqualityComparer since TKey itself is not constrained.

However while that works, it also ends up with virtual calls for Equals and GetHashCode that can't be inlined

                Method |        Mean | Scaled |  Gen 0 | Allocated |
---------------------- |------------:|-------:|-------:|----------:|
    ConstrainedGeneric |   0.7292 ns |   1.00 |      - |       0 B |
OverridableConstrained |   1.2454 ns |   1.71 |      - |       0 B |
      EqualityComparer |   1.8306 ns |   2.51 |      - |       0 B |
     IEqualityComparer |   2.7401 ns |   3.76 |      - |       0 B |*
          FuncComparer |   6.3357 ns |   8.69 |      - |       0 B | 
  PatternMatchEquality |  11.6117 ns |  15.92 | 0.0076 |      24 B |
       EqualityGeneric | 571.9018 ns | 784.25 | 0.0582 |     184 B |**

*  Dictionary     
** Uses key0.Equals(key1) no-constraint so via Object.Equals

As highlighted by ravendb in their fast-dictionary blog post; and the same thing could be achieved with the default comparer and struct keys in the regular dictionary.

Using a non-inherited Equatable as a static default and then with an override when the instance comparer is not null; gets most of the way there (second test)

internal class DictionaryEquatableComparer<T> where T : IEquatable<T>
{
    public bool Equals(T x, T y) => x.Equals(y);
    public int GetHashCode(T obj) => obj.GetHashCode();
}

public class OverridableComparer<TKey> where TKey : IEquatable<TKey>
{
    private static readonly DictionaryEquatableComparer<TKey> s_comparer = new DictionaryEquatableComparer<TKey>();
    private IEqualityComparer<TKey> _comparer;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public bool KeyEquals(TKey key0, TKey key1)
    {
        return _comparer == null ? s_comparer.Equals(key0, key1) : _comparer.Equals(key0, key1);
    }
}

However can't be used in dictionary as TKey is not constrained.

So was looking to see if pattern matching could solve it; as at Jit time everything is known about the key type (if struct; i.e. whether it implements IEquatable) so it could elide everything out in a method; rather than on an object. Essentially applying a generic constraint; and binding to the interface methods (rather than the interface) after the fact/internally.

That was the hope and motivation anyway :)

[benaadams]

However, the variable key is mutable, which means it is not constrained by the C# compiler to only contain a variable of type TKey.

It is (logically) at this point however isn't it?

case IEquatable<TKey> key:
    return key.Equals(key1); // <----

Its both TKey and IEquatable<TKey>?

[benaadams]

Specifically I'd like to do something like this for Dictionary<TKey, TValue>

private static readonly EqualityComparer<TKey> s_defaultComparer;
private readonly IEqualityComparer<TKey> _customComparer;

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool KeyEquals(TKey key0, TKey key1)
{
    bool result;
    if (_customComparer == null)
    {
        switch (key0)
        {
            case IEquatable<TKey> key:
                result = key.Equals(key1);
                break;
            default:
                result = s_defaultComparer.Equals(key0, key1);
                break;
        }
    }
    else
    {
        result = _customComparer.Equals(key0, key1);
    }

    return result;
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public int KeyHashCode(TKey key)
{
    int result;
    if (_customComparer == null)
    {
        switch (key)
        {
            case IEquatable<TKey> k:
                result = k.GetHashCode();
                break;
            default:
                result = s_defaultComparer.GetHashCode(key);
                break;
        }
    }
    else
    {
        result = _customComparer.GetHashCode(key);
    }

    return result & 0x7FFFFFFF;
}

[gafter]

The constrained call serves to avoid boxing the receiver. But in this case the receiver is already a reference type.

[gafter]

The proposed use of the constrained prefix violates the IL specification, which requires that the constraint type be the same as the receiver type. You are proposing a constraint type of TKey, but the call receiver's type is IEquatable<TKey>. Therefore the proposed code to be generated would be incorrect.

[benaadams]

Because its actually?

var key = key1 as IEquatable<TKey>

Maybe I want something more like?

switch (typeof(TKey))
{
    case IEquatable<TKey>:
        result = key0.Equals(key1); // bind to IEquatable<TKey>.Equals not Object.Equals

[gafter]

That's not correct IL either, as TKey is not constrained or otherwise a subtype of IEquatable<TKey>, which is a requirement of the callvirt instruction.

[benaadams]

Loosing the perf wins at

typeof(IEquatable<>).MakeGenericType(typeof(TKey)).IsAssignableFrom(typeof(TKey))

Will raise something over at csharplang

Thank you for looking at it