OSR + dynamic PGO not optimizing interface dispatch as expected

[stephentoub]

Consider this code:

class Program
{
    static void Main()
    {
        IPrinter printer = new Printer();
        for (int i = 0; ; i++)
        {
            DoWork(printer, i);
        }
    }

    static void DoWork(IPrinter printer, int i)
    {
        printer.PrintIfTrue(i == int.MaxValue);
    }

    interface IPrinter
    {
        void PrintIfTrue(bool condition);
    }

    class Printer : IPrinter
    {
        public void PrintIfTrue(bool condition)
        {
            if (condition) Console.WriteLine("Print!");
        }
    }
}

When I run that, the OSR variant of Main includes the properly devirtualized and inlined invocation of Printer.PrintIfTrue:

; Assembly listing for method Program:Main()
; Emitting BLENDED_CODE for X64 CPU with AVX - Windows
; Tier-1 compilation
; OSR variant for entry point 0x8
; optimized code
; instrumented for collecting profile data
; rsp based frame
; fully interruptible
; with Dynamic PGO: edge weights are invalid, and fgCalledCount is 9999
; 2 inlinees with PGO data; 0 single block inlinees; 0 inlinees without PGO data

G_M000_IG01:                ;; offset=0000H
       4883EC38             sub      rsp, 56
       4889BC24B8000000     mov      qword ptr [rsp+B8H], rdi
       4889B424B0000000     mov      qword ptr [rsp+B0H], rsi
       488BBC2480000000     mov      rdi, gword ptr [rsp+80H]
       8B74247C             mov      esi, dword ptr [rsp+7CH]

G_M000_IG02:                ;; offset=0020H
       48B9982D1F3FFC7F0000 mov      rcx, 0x7FFC3F1F2D98
       48390F               cmp      qword ptr [rdi], rcx
       7521                 jne      SHORT G_M000_IG05
       81FEFFFFFF7F         cmp      esi, 0x7FFFFFFF
       7404                 je       SHORT G_M000_IG04

G_M000_IG03:                ;; offset=0037H
       FFC6                 inc      esi
       EBE5                 jmp      SHORT G_M000_IG02

G_M000_IG04:                ;; offset=003BH
       48B9D820C02F5A020000 mov      rcx, 0x25A2FC020D8
       488B09               mov      rcx, gword ptr [rcx]
       FF1572CD0D00         call     [Console:WriteLine(String)]
       EBE7                 jmp      SHORT G_M000_IG03

G_M000_IG05:                ;; offset=0050H
       33D2                 xor      edx, edx
       81FEFFFFFF7F         cmp      esi, 0x7FFFFFFF
       0F94C2               sete     dl
       488BCF               mov      rcx, rdi
       49BB1000F53EFC7F0000 mov      r11, 0x7FFC3EF50010
       41FF13               call     [r11]IPrinter:PrintIfTrue(bool):this
       EBCA                 jmp      SHORT G_M000_IG03

However, if change the code to manually inline DoWork:

class Program
{
    static void Main()
    {
        IPrinter printer = new Printer();
        for (int i = 0; ; i++)
        {
            printer.PrintIfTrue(i == int.MaxValue);
        }
    }

    interface IPrinter
    {
        void PrintIfTrue(bool condition);
    }

    class Printer : IPrinter
    {
        public void PrintIfTrue(bool condition)
        {
            if (condition) Console.WriteLine("Print!");
        }
    }
}

then the PrintIfTrue method is not devirtualized/inlined:

; Assembly listing for method Program:Main()
; Emitting BLENDED_CODE for X64 CPU with AVX - Windows
; Tier-1 compilation
; OSR variant for entry point 0x8
; optimized code
; instrumented for collecting profile data
; rsp based frame
; partially interruptible
; with Dynamic PGO: edge weights are invalid, and fgCalledCount is 9999

G_M000_IG01:                ;; offset=0000H
       4883EC38             sub      rsp, 56
       4889BC24C8000000     mov      qword ptr [rsp+C8H], rdi
       4889B424C0000000     mov      qword ptr [rsp+C0H], rsi
       488BBC2490000000     mov      rdi, gword ptr [rsp+90H]
       8BB4248C000000       mov      esi, dword ptr [rsp+8CH]

G_M000_IG02:                ;; offset=0023H
       FF05AB210F00         inc      dword ptr [(reloc 0x7ffc3c5f2e54)]
       488BCF               mov      rcx, rdi
       48BA582E5F3CFC7F0000 mov      rdx, 0x7FFC3C5F2E58
       E8157EC25F           call     CORINFO_HELP_CLASSPROFILE32
       488BCF               mov      rcx, rdi
       33D2                 xor      edx, edx
       81FEFFFFFF7F         cmp      esi, 0x7FFFFFFF
       0F94C2               sete     dl
       49BB1000353CFC7F0000 mov      r11, 0x7FFC3C350010
       41FF13               call     [r11]IPrinter:PrintIfTrue(bool):this
       FFC6                 inc      esi
       EBC9                 jmp      SHORT G_M000_IG02

cc: @EgorBo, @AndyAyersMS

category:cq
theme:osr

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

Issue Details

---

Consider this code:

class Program
{
    static void Main()
    {
        IPrinter printer = new Printer();
        for (int i = 0; ; i++)
        {
            DoWork(printer, i);
        }
    }

    static void DoWork(IPrinter printer, int i)
    {
        printer.PrintIfTrue(i == int.MaxValue);
    }

    interface IPrinter
    {
        void PrintIfTrue(bool condition);
    }

    class Printer : IPrinter
    {
        public void PrintIfTrue(bool condition)
        {
            if (condition) Console.WriteLine("Print!");
        }
    }
}

When I run that, the OSR variant of Main includes the properly devirtualized and inlined invocation of Printer.PrintIfTrue:

; Assembly listing for method Program:Main()
; Emitting BLENDED_CODE for X64 CPU with AVX - Windows
; Tier-1 compilation
; OSR variant for entry point 0x8
; optimized code
; instrumented for collecting profile data
; rsp based frame
; fully interruptible
; with Dynamic PGO: edge weights are invalid, and fgCalledCount is 9999
; 2 inlinees with PGO data; 0 single block inlinees; 0 inlinees without PGO data

G_M000_IG01:                ;; offset=0000H
       4883EC38             sub      rsp, 56
       4889BC24B8000000     mov      qword ptr [rsp+B8H], rdi
       4889B424B0000000     mov      qword ptr [rsp+B0H], rsi
       488BBC2480000000     mov      rdi, gword ptr [rsp+80H]
       8B74247C             mov      esi, dword ptr [rsp+7CH]

G_M000_IG02:                ;; offset=0020H
       48B9982D1F3FFC7F0000 mov      rcx, 0x7FFC3F1F2D98
       48390F               cmp      qword ptr [rdi], rcx
       7521                 jne      SHORT G_M000_IG05
       81FEFFFFFF7F         cmp      esi, 0x7FFFFFFF
       7404                 je       SHORT G_M000_IG04

G_M000_IG03:                ;; offset=0037H
       FFC6                 inc      esi
       EBE5                 jmp      SHORT G_M000_IG02

G_M000_IG04:                ;; offset=003BH
       48B9D820C02F5A020000 mov      rcx, 0x25A2FC020D8
       488B09               mov      rcx, gword ptr [rcx]
       FF1572CD0D00         call     [Console:WriteLine(String)]
       EBE7                 jmp      SHORT G_M000_IG03

G_M000_IG05:                ;; offset=0050H
       33D2                 xor      edx, edx
       81FEFFFFFF7F         cmp      esi, 0x7FFFFFFF
       0F94C2               sete     dl
       488BCF               mov      rcx, rdi
       49BB1000F53EFC7F0000 mov      r11, 0x7FFC3EF50010
       41FF13               call     [r11]IPrinter:PrintIfTrue(bool):this
       EBCA                 jmp      SHORT G_M000_IG03

However, if change the code to manually inline DoWork:

class Program
{
    static void Main()
    {
        IPrinter printer = new Printer();
        for (int i = 0; ; i++)
        {
            printer.PrintIfTrue(i == int.MaxValue);
        }
    }

    interface IPrinter
    {
        void PrintIfTrue(bool condition);
    }

    class Printer : IPrinter
    {
        public void PrintIfTrue(bool condition)
        {
            if (condition) Console.WriteLine("Print!");
        }
    }
}

then the PrintIfTrue method is not devirtualized/inlined:

; Assembly listing for method Program:Main()
; Emitting BLENDED_CODE for X64 CPU with AVX - Windows
; Tier-1 compilation
; OSR variant for entry point 0x8
; optimized code
; instrumented for collecting profile data
; rsp based frame
; partially interruptible
; with Dynamic PGO: edge weights are invalid, and fgCalledCount is 9999

G_M000_IG01:                ;; offset=0000H
       4883EC38             sub      rsp, 56
       4889BC24C8000000     mov      qword ptr [rsp+C8H], rdi
       4889B424C0000000     mov      qword ptr [rsp+C0H], rsi
       488BBC2490000000     mov      rdi, gword ptr [rsp+90H]
       8BB4248C000000       mov      esi, dword ptr [rsp+8CH]

G_M000_IG02:                ;; offset=0023H
       FF05AB210F00         inc      dword ptr [(reloc 0x7ffc3c5f2e54)]
       488BCF               mov      rcx, rdi
       48BA582E5F3CFC7F0000 mov      rdx, 0x7FFC3C5F2E58
       E8157EC25F           call     CORINFO_HELP_CLASSPROFILE32
       488BCF               mov      rcx, rdi
       33D2                 xor      edx, edx
       81FEFFFFFF7F         cmp      esi, 0x7FFFFFFF
       0F94C2               sete     dl
       49BB1000353CFC7F0000 mov      r11, 0x7FFC3C350010
       41FF13               call     [r11]IPrinter:PrintIfTrue(bool):this
       FFC6                 inc      esi
       EBC9                 jmp      SHORT G_M000_IG02

cc: @EgorBo, @AndyAyersMS

Author:	stephentoub
Assignees:	-
Labels:	area-CodeGen-coreclr
Milestone:	-

[EgorBo]

The issue is fixed with this patch: EgorBo@0769601

@AndyAyersMS does it look good? I assume prior moving to OSR version we already collected PGO we needed

[jakobbotsch]

I think it is intentional that we profile OSR methods: #61453.
I don't think we currently can support both probing and devirtualizing the same call (the first problem is that gtGuardedDevirtualizationCandidateInfo and gtHandleHistogramProfileCandidateInfo share the same union). However, it is possible my recent changes have changed how we prioritize probing vs devirtualization here...

[jakobbotsch]

No, I think this was never enabled given this comment:

runtime/src/coreclr/jit/importer.cpp

Lines 22212 to 22215 in f35b4b3

	// Possibly instrument. Note for OSR+PGO we will instrument when
	// optimizing and (currently) won't devirtualize. We may want
	// to revisit -- if we can devirtualize we should be able to
	// suppress the probe.

[AndyAyersMS]

It's odd in the first listing that there are no block probes and that we didn't clone the loop to hoist out the invariant type test.

So, I think we need to look deeper at what's going on in both cases.

@AndyAyersMS does it look good? I assume prior moving to OSR version we already collected PGO we needed

That's not the current design. OSR+PGO needs to emit some probes since it's possible the Tier0 version never executes parts of the method, and we want Tier1 to see the full picture.

But we could perhaps be clever about omitting some probes in the parts of the method where OSR and Tier0 overlap. Also, if we knew somehow the method was never going to be called again then we could omit probes all together as we'll never make it to Tier1. But I don't think we can ever know this.

Another way to handle all this is for the OSR method to switch back to Tier0 at the end of the loop. I didn't do this because it seemed more complicated. This would allow us to keep all the probing in Tier0 code.

[EgorBo]

But we could perhaps be clever about omitting some probes in the parts of the method where OSR and Tier0 overlap.

can we just use the fact that we have class probes for given IL offset already?

Also, if we knew somehow the method was never going to be called again then we could omit probes all together as we'll never make it to Tier1. But I don't think we can ever know this.

unless caller's name is Main() 😄 (and it doesn't have loops)

[AndyAyersMS]

But we could perhaps be clever about omitting some probes in the parts of the method where OSR and Tier0 overlap.

can we just use the fact that we have class probes for given IL offset already?

Perhaps -- you could say if we have probes and data then maybe we could omit the class probe.

[AndyAyersMS]

Answering my own questions:

It's odd in the first listing that there are no block probes

We don't add counters to the first version of Main because we think there's no point -- the OSR method has only one basic block (note the return in Main is unreachable).

We don't add a class probe for the interface call site because it's in an inlinee.

In the second version we have more complex control flow in Main and a top-level interface call site. So we add counters and a class probe to the OSR method. Because we never make it out of OSR this version is incredibly slow.

... and that we didn't clone the loop to hoist out the invariant type test.

We're not able to recognize the loop as a clonable loop because there is no plausible header block. That is, we expect to see a block outside the loop that enters the loop, and here BB01 is in the loop.

*************** In optFindLoops()
*************** In optMarkLoopHeads()
1 loop heads marked
*************** In optFindNaturalLoops()
FindLoop: checking head:BB01 top:BB02 bottom:BB01
    BB01->BB02 is not a backedge
FindLoop: checking head:BB04 top:BB05 bottom:BB02
    BB02->BB05 is not a backedge
FindLoop: checking head:BB04 top:BB05 bottom:BB03
    BB03->BB05 is not a backedge
FindLoop: checking head:BB04 top:BB05 bottom:BB04
    BB04->BB05 is not a backedge
*************** In optFindAndScaleGeneralLoopBlocks()

Marking a loop from BB01 to BB05
    BB01(wt=100); unchanged: has profile weight
    BB02(wt=100); unchanged: has profile weight
    BB03(wt=0); unchanged: has profile weight
    BB04(wt=0); unchanged: has profile weight
    BB05(wt=100); unchanged: has profile weight
Found a total of 1 general loops.

*************** Finishing PHASE Find loops
Trees after Find loops

-----------------------------------------------------------------------------------------------------------------------------------------
BBnum BBid ref try hnd preds           weight    IBC  lp [IL range]     [jump]      [EH region]         [flags]
-----------------------------------------------------------------------------------------------------------------------------------------
BB01 [0001]  2       BB05                  1    9999    [008..015)-> BB04 ( cond )                     i Loop bwd bwd-target bwd-src IBC  osr-entry
BB02 [0005]  1       BB01                  1    9999    [008..009)-> BB05 ( cond )                     i nullcheck bwd IBC 
BB03 [0009]  1       BB02                  0       0    [008..009)-> BB05 (always)                     i rare hascall gcsafe bwd IBC 
BB04 [0006]  1       BB01                  0       0    [008..009)                                     i internal rare hascall gcsafe bwd IBC 
BB05 [0004]  3       BB02,BB03,BB04        1    9999    [008..009)-> BB01 (always)                     i internal bwd IBC 
-----------------------------------------------------------------------------------------------------------------------------------------

[AndyAyersMS]

We have changed our approach for OSR+PGO and this case is now handled properly. Would be nice to hoist that null check out of the loop but the call is devirtualized and inlined. Also the string literal is now accessed directly.

; Assembly listing for method Program:Main()
; Emitting BLENDED_CODE for X64 with AVX - Windows
; Tier-1 compilation
; OSR variant for entry point 0x8
; optimized code
; rsp based frame
; fully interruptible
; PGO data available, profile data was all zero
; 0 inlinees with PGO data; 2 single block inlinees; 1 inlinees without PGO data
; Final local variable assignments
;
;  V00 loc0         [V00,T01] (  1,  8   )     ref  ->  rdi         class-hnd exact
;  V01 loc1         [V01,T00] (  3, 24   )     int  ->  rsi        
;  V02 OutArgs      [V02    ] (  1,  1   )  struct (32) [rsp+00H]   do-not-enreg[XS] addr-exposed "OutgoingArgSpace"
;* V03 tmp1         [V03    ] (  0,  0   )     ref  ->  zero-ref    class-hnd exact "NewObj constructor temp"
;* V04 tmp2         [V04    ] (  0,  0   )    bool  ->  zero-ref    "Inlining Arg"
;
; Lcl frame size = 40

G_M27646_IG01:  ;; offset=0000H
       sub      rsp, 56
       mov      qword ptr [rsp+C8H], rdi
       mov      qword ptr [rsp+C0H], rsi
       mov      rdi, gword ptr [rsp+90H]
       mov      esi, dword ptr [rsp+8CH]
						;; size=35 bbWeight=8 PerfScore 50.00
G_M27646_IG02:  ;; offset=0023H
       cmp      byte  ptr [rdi], dil
       cmp      esi, 0x7FFFFFFF
       jne      SHORT G_M27646_IG04
						;; size=11 bbWeight=8 PerfScore 34.00
G_M27646_IG03:  ;; offset=002EH
       mov      rcx, 0x2D680309810      ; 'Print!'

       call     [System.Console:WriteLine(System.String)]
						;; size=16 bbWeight=4 PerfScore 13.00
G_M27646_IG04:  ;; offset=003EH
       inc      esi
       jmp      SHORT G_M27646_IG02
						;; size=4 bbWeight=8 PerfScore 18.00

; Total bytes of code 66, prolog size 35, PerfScore 121.60, instruction count 12, allocated bytes for code 66 (MethodHash=cb019401) for method Program:Main()

There is still a loophole for methods that loop enough to trigger OSR before they ever return, but eventually exit the loop and do interesting things afterwards. Because we only instrument the Tier0 version and that version always hops over to OSR, we never re-enter the Tier0 version, so we don't hit those later probes. Such methods will not see the full benefit of PGO.

One possible fix is to have the OSR method rejoin the Tier0 method once it exits the loop, but I'd need to see evidence that this pattern is common before doing the (perhaps considerable) work to support something like that.

I am going to close this. Feel free to re-open if you think we're being too hasty here.