Guarded devirtualization generates checks that are never true

[MichalStrehovsky]

(This is native AOT)

Compile this:

using System;
using System.Runtime.CompilerServices;

class TestDevirtualizationIntoAbstract
{
    class Something { }

    abstract class Base
    {
        [MethodImpl(MethodImplOptions.NoInlining)]
        public virtual Type GetSomething() => typeof(Something);
    }

    sealed class Derived : Base { }

    class Unrelated : Base
    {
        public override Type GetSomething() => typeof(Unrelated);
    }

    static void Main()
    {
        TestUnrelated(new Unrelated());
        Test(null);
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    static Type Test(Derived d) => d?.GetSomething();

    [MethodImpl(MethodImplOptions.NoInlining)]
    static Type TestUnrelated(Base d) => d?.GetSomething();
}

And look at the disassembly of Test (Godbolt: https://godbolt.org/z/bro8n7sd9)

TestDevirtualizationIntoAbstract:Test(TestDevirtualizationIntoAbstract+Derived):System.Type (FullOpts):
; Emitting BLENDED_CODE for generic X64 - Unix
; FullOpts code
; NativeAOT compilation
; optimized code
; rsp based frame
; partially interruptible
; Final local variable assignments
;
;  V00 arg0         [V00,T00] (  3,  2.50)     ref  ->  rdi         class-hnd single-def <TestDevirtualizationIntoAbstract+Derived>
;# V01 OutArgs      [V01    ] (  1,  1   )  struct ( 0) [rsp+0x00]  do-not-enreg[XS] addr-exposed "OutgoingArgSpace"
;* V02 tmp1         [V02    ] (  0,  0   )     ref  ->  zero-ref    "guarded devirt return temp"
;* V03 tmp2         [V03    ] (  0,  0   )     ref  ->  zero-ref    class-hnd exact "guarded devirt this exact temp" <TestDevirtualizationIntoAbstract+Unrelated>
;
; Lcl frame size = 8
G_M25112_IG01:  ;; offset=0x0000
       push     rax
                        ;; size=1 bbWeight=0.50 PerfScore 0.50
G_M25112_IG02:  ;; offset=0x0001
       lea      rax, gword ptr [(reloc 0x445110)]      ; 'ILCompiler.DependencyAnalysis.FrozenRuntimeTypeNode'
       xor      rcx, rcx
       test     rdi, rdi
       cmove    rax, rcx
                        ;; size=16 bbWeight=0.50 PerfScore 0.62
G_M25112_IG03:  ;; offset=0x0011
       add      rsp, 8
       ret      

Notice we did a "GDV" (the guard being a null check :)) to the only possible descendant of Base (that's the Unrelated class).

But we shouldn't have done this GDV. The method Test takes a Derived, not Base. So Unrelated is not in the class hierarchy. Seems like we forget the exact type information between devirt attempt and when GDV happens.

Cc @EgorBo

[dotnet-policy-service[bot]]

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

[EgorBo]

@MichalStrehovsky it looks more like an issue on NAOT side in resolveVirtualMethod call. We pass there

dvInfo.virtualMethod = "Base.GetSomething"
dvInfo.objClass = "TestDevirtualizationIntoAbstract+Derived"

but it returns no devirtualizedMethod to jit.

I am seeing in the dump

no derived method: object class cannot be referenced from R2R code due to missing tokens

which is CORINFO_DEVIRTUALIZATION_FAILED_BUBBLE_IMPL_NOT_REFERENCEABLE

[MichalStrehovsky]

resolveVirtualMethod sometimes rejects devirtualizing so that JIT doesn't generate direct calls to impossible methods. For example if a type was never allocated and we didn't scan the instance method, we don't want RyuJIT to make a direct call (or even inline) the method since we didn't look at it because it's impossible.

CORINFO_DEVIRTUALIZATION_FAILED_BUBBLE_IMPL_NOT_REFERENCEABLE is a R2R term because I didn't want to rev JitInterface just to add a new enum member for when native AOT rejects this. So in native AOT "being outside input bubble" means "outside whole program view".

[EgorBo]

resolveVirtualMethod sometimes rejects devirtualizing so that JIT doesn't generate direct calls to impossible methods. For example if a type was never allocated and we didn't scan the instance method, we don't want RyuJIT to make a direct call (or even inline) the method since we didn't look at it because it's impossible.

CORINFO_DEVIRTUALIZATION_FAILED_BUBBLE_IMPL_NOT_REFERENCEABLE is a R2R term because I didn't want to rev JitInterface just to add a new enum member for when native AOT rejects this. So in native AOT "being outside input bubble" means "outside whole program view".

I am a bit confused, so are you confirming it needs to be fixed on ILC side in this case? because JIT doesn't see any MethodDesc representing Derived.GetSomething

[EgorBo]

hm.. wait, I am totally lost, isn't codegen looking good as is?

There is no GDV check in the codegen, it's a frozen object representing typeof(Something) which Derived.GetSomething returns. Then, we have a cmov because we don't need to return that frozen object if d instance is null

var frozenTypeof = typeof(Something);
if (d == null)
    return null;
else
    return frozenTypeof;

[MichalStrehovsky]

There is no GDV check in the codegen, it's a frozen object representing typeof(Something) which Derived.GetSomething returns. Then, we have a cmov because we don't need to return that frozen object if d instance is null

Its's typeof(Unrelated). It cannot be typeof(Something) because Derived.GetSomething is NoInlining.

[EgorBo]

There is no GDV check in the codegen, it's a frozen object representing typeof(Something) which Derived.GetSomething returns. Then, we have a cmov because we don't need to return that frozen object if d instance is null

Its's typeof(Unrelated). It cannot be typeof(Something) because Derived.GetSomething is NoInlining.

I see, then it's a correctness issue here (bug)?

Looks like it's what NAOT's getExactClasses return to JIT:

We have exactly 1 classes implementing TestDevirtualizationIntoAbstract+Base:
  0) TestDevirtualizationIntoAbstract+Unrelated

so basically it says that only one class implements Base. Is it expected that Derived is removed?

[EgorBo]

Although, there is no correctness issue in this given example since the method will return null. The inlined typeof(Unrelated) is just unused.

[MichalStrehovsky]

I see, then it's a correctness issue here (bug)?

I wouldn't say correctness. The only real instance of Base that can exist in the above program is Unrelated. RyuJIT asks for descendants of Base. But we already know from the signature it's not only Base, but also Derived and Unrelated is not Derived. The problem is that RyuJIT could be asking for descendants of Derived. It looks like a possible perf optimization opportunity to me (do we always ask for the base class in GDV when we could be asking about a more restricted descendant of the base?).

[EgorBo]

The problem is that RyuJIT could be asking for descendants of Derived. It looks like a possible perf optimization opportunity to me (do we always ask for the base class in GDV when we could be asking about a more restricted descendant of the base?).

The way I see it:

1. Jit starts importing IL call instruction:

   callvirt instance class [System.Runtime]System.Type TestDevirtualizationIntoAbstract/Base::GetSomething()

   so now JIT has a CORINFO_MEHTOD_HANDLE of the base Base::GetSomething.

2. Jit realizes that the actual object's class is Derived (from the method signature, like you've pointed out).

3. Jit comes to impDevirtualizeCall where it basically wants to get an exact method handle to use. For that, it invokes resolveVirtualMethod with:

   dvInfo.virtualMethod = "Base.GetSomething"
   dvInfo.objClass      = "TestDevirtualizationIntoAbstract+Derived"

   NAOT rejects this attempt via CORINFO_DEVIRTUALIZATION_FAILED_BUBBLE_IMPL_NOT_REFERENCEABLE and returns null in dvInfo.devirtualizedMethod parameter.

4. In such cases, when JIT can't devirtualize right away, it switches to GDV/PGO routine. In GDV routine, it first tries getExactClasses API. This API returns just one item - Unrelated. It means that JIT doesn't need any GDV check and can just import it as direct call to Unrelated (for that, it calls resolveVirtualMethod again, but this time NAOT happily returns the expected Unrelated::GetSomething.

So to be fair, I don't see what JIT does wrong here. Perhaps, we need a new JIT-VM API - getExactMethod? It seems to me that resolveVirtualMethod at the 3rd step is expected to return a correct method handle here.

[MichalStrehovsky]

Would it be incorrect to call getExactClasses with Derived instead of Base?

[EgorBo]

Would it be incorrect to call getExactClasses with Derived instead of Base?

Ah, good point, let's see. Interestingly, if we do that, we'll get a bigger codegen for your Test method 🙂:

; Assembly listing for method TestDevirtualizationIntoAbstract:Test(TestDevirtualizationIntoAbstract+Derived):System.Type (FullOpts)
G_M25112_IG01:  ;; offset=0x0000
       sub      rsp, 40
G_M25112_IG02:  ;; offset=0x0004
       test     rcx, rcx
       je       SHORT G_M25112_IG05
G_M25112_IG03:  ;; offset=0x0009
       mov      rax, qword ptr [rcx]
       call     [rax+0x30]TestDevirtualizationIntoAbstract+Base:GetSomething():System.Type:this
       nop      
G_M25112_IG04:  ;; offset=0x0010
       add      rsp, 40
       ret      
G_M25112_IG05:  ;; offset=0x0015
       xor      rax, rax
G_M25112_IG06:  ;; offset=0x0017
       add      rsp, 40
       ret      
; Total bytes of code 28

[EgorBo]

Would it be incorrect to call getExactClasses with Derived instead of Base?

hm.. but if we do that, getExactClasses will bail out:

No exact classes implementing TestDevirtualizationIntoAbstract+Derived
Not guessing; no PGO and no exact classes

that's why in my ASM above ^ Base:GetSomething() is a virtual call. Is it an issue?

[MichalStrehovsky]

hm.. but if we do that, getExactClasses will bail out:

Yeah, that's the expected behavior - based on whole program view, we know this will never be anything.

I think not inlining or generating calls to an impossible method would already be an improvement. This can only be a virtual call since there's nothing concrete this could legitimately call into. We actually know there is nothing this could legitimately call into so we could even replace the call with int3 (or some kind of throw helper, in case people shoot themselves in the foot with unsafe casts).

I wonder if this tightening of the method being called could result in improvements for "actually possible" cases where we have many possible descendants of Base (so GDV would reject or generate unnecessarily many type checks), but few descendants of Derived.

[EgorBo]

Closed by https://github.com/dotnet/runtime/pull/108497