Generic virtual method devirtualization does not happen

[NinoFloris]

Consider the following benchmark example:

    public interface IFoo 
    {
        object Foo();
    }

    public interface IFooGeneric 
    {
        T FooGeneric<T>();
    }

    public sealed class Impl: IFoo, IFooGeneric
    {
        [MethodImpl(MethodImplOptions.NoInlining)]
        public object Foo() => null;

        [MethodImpl(MethodImplOptions.NoInlining)]
        public T FooGeneric<T>() => default;
    }

    public class DevirtBenchmark
    {
        const int Operations = 100000;
        static Impl ImplInstance;
        static IFoo IFooInstance;
        static IFooGeneric IFooGenericInstance;

        [GlobalSetup(Target = "ImplFooGeneric,IFooViaImpl,IFooGenericViaImpl")]
        public void SetupImpl() => ImplInstance = new Impl();

        [GlobalSetup(Target = "IFoo")]
        public void SetupIFoo() => IFooInstance = new Impl();

        [GlobalSetup(Target = "IFooGeneric")]
        public void SetupIFooGenric() => IFooGenericInstance = new Impl();

        [Benchmark(OperationsPerInvoke = Operations)]
        public void ImplFooGeneric()
        {
            for (int i = 0; i < Operations; i++)
            {
                ImplInstance.FooGeneric<object>();
            }
        }

        [Benchmark(OperationsPerInvoke = Operations)]
        public void IFoo()
        {
            for (int i = 0; i < Operations; i++)
            {
                IFooInstance.Foo();
            }
        }

        [Benchmark(OperationsPerInvoke = Operations)]
        public void IFooViaImpl()
        {
            for (int i = 0; i < Operations; i++)
            {
                ((IFoo)ImplInstance).Foo();
            }
        }

        [Benchmark(OperationsPerInvoke = Operations)]
        public void IFooGeneric()
        {
            for (int i = 0; i < Operations; i++)
            {
                IFooGenericInstance.FooGeneric<object>();
            }
        }

        [Benchmark(OperationsPerInvoke = Operations)]
        public void IFooGenericViaImpl()
        {
            for (int i = 0; i < Operations; i++)
            {
                ((IFooGeneric)ImplInstance).FooGeneric<object>();
            }
        }
    }

Results show the JIT can succesfully devirtualize IFooViaImpl by observing the concrete type before the cast. Yet it fails to do so for IFooGenericViaImpl while those - extremely slow calls - would benefit most from this working correctly.

// * Summary *

BenchmarkDotNet=v0.12.0, OS=macOS Mojave 10.14.6 (18G3020) [Darwin 18.7.0]
Intel Core i7-4980HQ CPU 2.80GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT DEBUG
  DefaultJob : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT


|             Method |     Mean |     Error |    StdDev |
|------------------- |---------:|----------:|----------:|
|     ImplFooGeneric | 1.818 ns | 0.0081 ns | 0.0072 ns |
|               IFoo | 2.360 ns | 0.0354 ns | 0.0331 ns |
|        IFooViaImpl | 1.546 ns | 0.0056 ns | 0.0052 ns |
|        IFooGeneric | 7.758 ns | 0.0605 ns | 0.0566 ns |
| IFooGenericViaImpl | 7.739 ns | 0.0242 ns | 0.0227 ns |

/cc @AndyAyersMS

EDIT: I have added a direct generic call for scale
What I also noticed is that the class itself needs to be sealed as well for IFooViaImpl to devirtualize, yet that method is already final in IL, this seems like a rather small fix.

category:cq
theme:devirtualization
skill-level:expert
cost:large

[AndyAyersMS]

Interface calls to generic methods are handled via ldvirtfn internally; I haven't looked into what would be involved in devirtualizing these. Added an entry onto my (admittedly large) todo list at #7541.

When devirtualizing interface calls we must have an exact class or a sealed class; sealing the method is not sufficient.

[NinoFloris]

Exact class would mean, new T() within view or stored in a static readonly kind of guarantee?

Rereading this refreshed my memory on class vs method sealing

Not real happy with having to drop the final method check from interface call devirt, but right now I can't tell whether a method is an explicit interface implementation or an inherited one that happens to be marked sealed (the latter is probably rare but possible), and so relying just on the final bit on the method can lead to the wrong devirtualization.

This is a shame, anything that can be done here?

[AndyAyersMS]

Exact class would mean, new T() within view or stored in a static readonly kind of guarantee?

Yes.

This is a shame, anything that can be done here?

Aside from sealing classes, you mean? This behavior of interfaces is deeply ingrained in the spec.

Down the road, we may start to make speculative bets during codegen -- either guarded or unguarded -- and then have appropriate recovery mechanisms kick in when the bets are wrong. So if at jit time a method has no possible overriders, we could speculatively devirtualize.

[NinoFloris]

Aside from sealing classes, you mean?

Yes as sealed classes aren't the default many opportunities are missed.
Speculative devirt is great for jitted workloads but not so much for AOT.

Is this the type confusion w.r.t. sealed methods and explicit implementations you were talking about? Or isn't it expressible in C#?

public interface IFoo 
{
   void M();   
}

public class A 
{
    public virtual void M() { }
}
public class B : A {
    public sealed override void M() { }
}
public class C : B, IFoo
{
    void IFoo.M() { }
}

I've been trying to parse some of your comments like the one shared earlier but also

Disallow interface devirt if the method is final but the class is not
exact or final, since derived classes can still override final methods
when implementing interfaces.

And I guess I just can't see what the minimal repro of this is.

[AndyAyersMS]

Yes, that's the minimal repro; I had this wrong originally and fixed it in dotnet/coreclr#10371, which introduced this similar test case:

runtime/src/coreclr/tests/src/JIT/opt/Devirtualization/generic.cs

Lines 46 to 55 in fff8f5a

	class E : D
	{
	public sealed override int G() { return 17; }
	}
	// K overrides E.G for interface purposes, even though it is sealed
	class K : E, Ix
	{
	int Ix.G() { return 19; }
	}

Even with AOT we can guardedly speculate; C++ compilers do this all the time.

[NinoFloris]

Even with AOT we can guardedly speculate; C++ compilers do this all the time.

That must work out less well if you don't also do PGO, agreed that technically there's no limitation, it just requires more work to pay off for AOT.

Yes, that's the minimal repro;

Neat, looking at both examples in IL I do see quite a few ways to discern whether this (sealed + overriding G) is the case.

Some of the discriminators as I see them:

• Explicit interface methods are private on the class, this should give a huge hint while trying to devirtualize an interface call, which should always be a public method unless it's explicit.
• The override happens on the interface method, not the class as visible by .override method instance int32 Ix::G()

Using one, or a combination of these, should allow relaxing the requirements to devirtualize.
Is it a matter of this information not being available to the JIT?

I wouldn't mind trying my hand at this if you think it's possible.

[AndyAyersMS]

I do not think it is possible in general. Say the "best type" we have at jit time is a non-final, inexact E. Even if the type system knows of all of E's derived types and none of those derived types override the method for this virtual or interface slot, we still can't devirtualize; some future type loading event might introduce a derived class that could override.

The only way to future proof this is to either know E's type exactly or to know that there will never be an as of yet unknown class that will derive from E.

For virtual calls, the override patterns are more constrained, and final methods are usually sufficient (but even this has its subtleties, see #10809).

[NinoFloris]

Right! Now I'm on the same page, I got tripped up by virtual methods AND explicit instantations but what easily seems indistinguishable - by design - is interface reimplementation.

interface Ix
{
    int F();
}

public class A : Ix
{
    int Ix.F() => 1;
}

public class B: A, Ix
{
    int Ix.F() => 2;
}

Overrides on the same method yet A was already final, writing new B() into a variable typed A, and calling F() returns 2. The implications of devirtualizing to A are obvious.

I was blissfully unaware that interfaces were this deeply virtual, but then again I often use interfaces more like constraints than actual types. Viewing them as types I can understand why having them be virtual this way makes a bit more sense.

Thinking deeply about this in the context of #10809 after learning some of the subtleties of newslot; final is per slot, each explicit implementation introduces a new slot, yet because slot selection is indirect through IVMap (as opposed to direct for virtual members) - in other words based on the runtime type - you cannot rely on the slot being the same for all instances assignable to A which means final is irrelevant. And as such devirtualization is only possible if you know no new slots can be introduced in the hierarchy of A, seal those types ;)

Thank you for indulging me!

[jakobbotsch]

We now have guarded devirtualization that bridges this gap, so I am going to close this issue. Feel free to reopen if you think there are more opportunities or that I missed something.