JIT: cycles in connection graph lead to non-minimal fix point retypings

[AndyAyersMS]

If there are cycles in the connection graph, then even when all objects are stack allocated we may end up typing references as byrefs. For example:

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

using System;
using System.Runtime.CompilerServices;
using Xunit;

public class X
{
    public X() { a = 15; b = 35; }
    public int a;
    public int b;
}

public class ConnectionCycles
{
   static bool b;

   [Fact]
   public static int Problem()
   {
       return SubProblem(false) + SubProblem(true);
   }

   [MethodImpl(MethodImplOptions.NoInlining)]
   static int SubProblem(bool b)
   {
       X x1 = new X();
       X x2 = new X();

       if (b)
       {
           x1 = x2;
       }
       else
       {
           x2 = x1;
       }

       SideEffect();

       return x1.a + x2.b;
   }


   [MethodImpl(MethodImplOptions.NoInlining)]
   static void SideEffect() { }
}

Here the x1 and x2 form a cycle, and so both end up as TYP_BYREF despite being definitely stack pointing:

; Assembly listing for method ConnectionCycles:SubProblem(ubyte):int (FullOpts)
; Emitting BLENDED_CODE for X64 with AVX - Windows
; FullOpts code
; optimized code
; rsp based frame
; partially interruptible
; No PGO data
; 0 inlinees with PGO data; 4 single block inlinees; 0 inlinees without PGO data
; Final local variable assignments
;
;  V00 arg0         [V00,T00] (  3,  3   )   ubyte  ->  rcx         single-def
;  V01 loc0         [V01,T02] (  3,  2.50)   byref  ->  rbx         class-hnd <X>
;  V02 loc1         [V02,T03] (  3,  2.50)   byref  ->  rsi         class-hnd <X>
;  V03 OutArgs      [V03    ] (  1,  1   )  struct (32) [rsp+0x00]  do-not-enreg[XS] addr-exposed "OutgoingArgSpace" <UNNAMED>
;* V04 tmp1         [V04    ] (  0,  0   )    long  ->  zero-ref    class-hnd exact "NewObj constructor temp" <X>
;* V05 tmp2         [V05    ] (  0,  0   )    long  ->  zero-ref    class-hnd exact "NewObj constructor temp" <X>
;  V06 tmp3         [V06    ] (  5,  4.50)  struct (16) [rsp+0x38]  do-not-enreg[XSF] must-init addr-exposed "stack allocated X" <X>
;  V07 tmp4         [V07    ] (  5,  4.50)  struct (16) [rsp+0x28]  do-not-enreg[XSF] must-init addr-exposed "stack allocated X" <X>
;  V08 cse0         [V08,T01] (  3,  3   )    long  ->  rax         "CSE #01: aggressive"
;
; Lcl frame size = 72

G_M33005_IG01:        ; bbWeight=1, gcrefRegs=0000 {}, byrefRegs=0000 {}, byref, nogc <-- Prolog IG
       push     rsi
       push     rbx
       sub      rsp, 72
       xor      eax, eax
       mov      qword ptr [rsp+0x28], rax
       vxorps   xmm4, xmm4, xmm4
       vmovdqa  xmmword ptr [rsp+0x30], xmm4
       mov      qword ptr [rsp+0x40], rax
                                                ;; size=28 bbWeight=1 PerfScore 6.83
G_M33005_IG02:        ; bbWeight=1, gcrefRegs=0000 {}, byrefRegs=0000 {}, byref, isz
       mov      rax, 0x7FFCD6E94688      ; X
       mov      qword ptr [rsp+0x38], rax
       mov      dword ptr [rsp+0x40], 15
       mov      dword ptr [rsp+0x44], 35
       lea      rbx, [rsp+0x38]
       mov      qword ptr [rsp+0x28], rax
       mov      dword ptr [rsp+0x30], 15
       mov      dword ptr [rsp+0x34], 35
       lea      rsi, [rsp+0x28]
       test     cl, cl
       jne      SHORT G_M33005_IG04
                                                ;; size=66 bbWeight=1 PerfScore 8.50
G_M33005_IG03:        ; bbWeight=0.50, gcrefRegs=0000 {}, byrefRegs=0008 {rbx}, byref, isz
                            ; byrRegs +[rbx]
       lea      rsi, bword ptr [rsp+0x38]
                            ; byrRegs +[rsi]
       jmp      SHORT G_M33005_IG05
                                                ;; size=7 bbWeight=0.50 PerfScore 1.25
G_M33005_IG04:        ; bbWeight=0.50, gcrefRegs=0000 {}, byrefRegs=0040 {rsi}, byref
                            ; byrRegs -[rbx]
       lea      rbx, bword ptr [rsp+0x28]
                            ; byrRegs +[rbx]
                                                ;; size=5 bbWeight=0.50 PerfScore 0.25
G_M33005_IG05:        ; bbWeight=1, gcrefRegs=0000 {}, byrefRegs=0048 {rbx rsi}, byref
       call     [ConnectionCycles:SideEffect()]
                            ; gcr arg pop 0
       mov      eax, dword ptr [rbx+0x08]
       add      eax, dword ptr [rsi+0x0C]
                                                ;; size=12 bbWeight=1 PerfScore 8.00
G_M33005_IG06:        ; bbWeight=1, epilog, nogc, extend
       add      rsp, 72
       pop      rbx
       pop      rsi
       ret
                                                ;; size=7 bbWeight=1 PerfScore 2.25

; Total bytes of code 125, prolog size 28, PerfScore 27.08, instruction count 29, allocated bytes for code 125 (MethodHash=6bfa7f12) for method ConnectionCycles:SubProblem(ubyte):int (FullOpts)

The root cause is that the retyping fixed-point computation is pessimistic, and can only mark a local as definitely stack pointing if all connected locals are definitely stack pointing. So if there is a connection graph cycle then none of the members in the cycle ever can be marked as definitely stack pointing.

An optimistic algorithm would instead assume all locals are definitely stack pointing until proven otherwise and would reach a "better" fixed point.

[dotnet-policy-service]

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