CSE fails for a tree of chained NEGs

[SingleAccretion]

While working on #49535, I have uncovered (via an SPMI replay) what appears to be a preexisting issue in how CSE is performed.

The following reproduction hits a noway_assert in optcse.cpp:3290:

private static int _counter = 100;

private static int Problem()
{
    var a = 21;
    _counter = 42;

    return 43 - (0 - (a - _counter));
}

The trees

*************** In optOptimizeCSEs()
Blocks/Trees at start of optOptimizeCSE phase

-----------------------------------------------------------------------------------------------------------------------------------------
BBnum BBid ref try hnd preds           weight    lp [IL range]     [jump]      [EH region]         [flags]
-----------------------------------------------------------------------------------------------------------------------------------------
BB01 [0000]  1                             1       [000..017)        (return)                     i label target
-----------------------------------------------------------------------------------------------------------------------------------------

------------ BB01 [000..017) (return), preds={} succs={}

***** BB01
STMT00001 (IL 0x003...0x005)
N003 (  5,  6) [000005] -A--G-------              *  ASG       int    $42
N001 (  3,  4) [000004] ----G--N----              +--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] $100
N002 (  1,  1) [000003] ------------              \--*  CNS_INT   int    42 $42

***** BB01
STMT00002 (IL 0x00A...0x016)
N009 ( 11, 12) [000013] ----G-------              *  RETURN    int    $141
N008 ( 10, 11) [000012] ----G-------              \--*  ADD       int    <l:$47, c:$1c1>
N006 (  8,  9) [000016] ----G-------                 +--*  NEG       int    <l:$45, c:$182>
N005 (  7,  8) [000015] ----G-------                 |  \--*  NEG       int    <l:$44, c:$181>
N004 (  6,  7) [000010] ----G-------                 |     \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5) [000014] ----G-------                 |        +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4) [000009] ----G-------                 |        |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1) [000008] ------------                 |        \--*  CNS_INT   int    21 $44
N007 (  1,  1) [000006] ------------                 \--*  CNS_INT   int    43 $46

-------------------------------------------------------------------------------------------------------------------

*************** In optOptimizeValnumCSEs()

CSE candidate #01, key=$45 in BB01, [cost= 8, size= 9]:
N006 (  8,  9) CSE #01 (use)[000016] ----G-------              *  NEG       int    <l:$45, c:$182>
N005 (  7,  8)              [000015] ----G-------              \--*  NEG       int    <l:$44, c:$181>
N004 (  6,  7) CSE #01 (use)[000010] ----G-------                 \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------                    +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------                    |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------                    \--*  CNS_INT   int    21 $44

Blocks that generate CSE def/uses
BB01 cseGen = 0000000000000003

Performing DataFlow for ValnumCSE's
StartMerge BB01
  :: cseOut    = 0000000000000007
EndMerge BB01
  :: cseIn     = 0000000000000000
  :: cseGen    = 0000000000000003
  => cseOut    = 0000000000000003
  != preMerge  = 0000000000000007, => true

After performing DataFlow for ValnumCSE's
BB01 cseIn  = 0000000000000000, cseGen = 0000000000000003, cseOut = 0000000000000003

Labeling the CSEs with Use/Def information
BB01 [000010] Def of CSE #01 [weight=1   ]
BB01 [000016] Use of CSE #01 [weight=1   ]

************ Trees at start of optValnumCSE_Heuristic()

------------ BB01 [000..017) (return), preds={} succs={}

***** BB01
STMT00001 (IL 0x003...0x005)
N003 (  5,  6)              [000005] -A--G-------              *  ASG       int    $42
N001 (  3,  4)              [000004] ----G--N----              +--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] $100
N002 (  1,  1)              [000003] ------------              \--*  CNS_INT   int    42 $42

***** BB01
STMT00002 (IL 0x00A...0x016)
N009 ( 11, 12)              [000013] ----G-------              *  RETURN    int    $141
N008 ( 10, 11)              [000012] ----G-------              \--*  ADD       int    <l:$47, c:$1c1>
N006 (  8,  9) CSE #01 (use)[000016] ----G-------                 +--*  NEG       int    <l:$45, c:$182>
N005 (  7,  8)              [000015] ----G-------                 |  \--*  NEG       int    <l:$44, c:$181>
N004 (  6,  7) CSE #01 (def)[000010] ----G-------                 |     \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------                 |        +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------                 |        |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------                 |        \--*  CNS_INT   int    21 $44
N007 (  1,  1)              [000006] ------------                 \--*  CNS_INT   int    43 $46

-------------------------------------------------------------------------------------------------------------------


Aggressive CSE Promotion cutoff is 200.000000
Moderate CSE Promotion cutoff is 100.000000
enregCount is 1
Framesize estimate is 0x0000
We have a small frame

Sorted CSE candidates:
CSE #01, {$45 , $4  } useCnt=1: [def=100.000000, use=100.000000, cost=  6      ]
        :: N004 (  6,  7) CSE #01 (def)[000010] ----G-------              *  ADD       int    <l:$45, c:$1c0>


Considering CSE #01 {$45 , $4  } [def=100.000000, use=100.000000, cost=  6      ]
CSE Expression :
N004 (  6,  7) CSE #01 (def)[000010] ----G-------              *  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------              +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------              |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------              \--*  CNS_INT   int    21 $44

Aggressive CSE Promotion (300.000000 >= 200.000000)
cseRefCnt=300.000000, aggressiveRefCnt=200.000000, moderateRefCnt=100.000000
defCnt=100.000000, useCnt=100.000000, cost=6, size=7
def_cost=1, use_cost=1, extra_no_cost=12, extra_yes_cost=0
CSE cost savings check (612.000000 >= 200.000000) passes

Promoting CSE:

lvaGrabTemp returning 2 (V02 rat0) (a long lifetime temp) called for CSE - aggressive.
CSE #01 is single-def, so associated CSE temp V02 will be in SSA
New refCnts for V02: refCnt =  2, refCntWtd = 2
New refCnts for V02: refCnt =  3, refCntWtd = 3

CSE #01 def at [000010] replaced in BB01 with def of V02
optValnumCSE morphed tree:
N011 ( 10, 11)              [000013] -A--G-------              *  RETURN    int    $141
N010 (  9, 10)              [000012] -A--G-------              \--*  ADD       int    <l:$47, c:$1c1>
N008 (  7,  8)              [000020] -A--G-------                 +--*  COMMA     int    <l:$45, c:$1c0>
N006 (  6,  7)              [000018] -A--G---R---                 |  +--*  ASG       int    $VN.Void
N005 (  1,  1)              [000017] D------N----                 |  |  +--*  LCL_VAR   int    V02 cse0         d:1 <l:$45, c:$1c0>
N004 (  6,  7)              [000010] ----G-------                 |  |  \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------                 |  |     +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------                 |  |     |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------                 |  |     \--*  CNS_INT   int    21 $44
N007 (  1,  1)              [000019] ------------                 |  \--*  LCL_VAR   int    V02 cse0         u:1 <l:$45, c:$1c0>
N009 (  1,  1)              [000006] ------------                 \--*  CNS_INT   int    43 $46


Working on the replacement of the CSE #01 use at [000016] in BB01

This CSE use has side effects and/or nested CSE defs. The sideEffectList:
N006 (  6,  7)              [000018] -A--G---R---              *  ASG       int    $VN.Void
N005 (  1,  1)              [000017] D------N----              +--*  LCL_VAR   int    V02 cse0         d:1 <l:$45, c:$1c0>
N004 (  6,  7)              [000010] ----G-------              \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------                 +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------                 |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------                 \--*  CNS_INT   int    21 $44


gtFindLink failed: stm=STMT00002, exp=[000016]
stm =STMT00002 (IL 0x00A...0x016)
N011 ( 10, 11)              [000013] -A--G-------              *  RETURN    int    $141
N010 (  9, 10)              [000012] -A--G-------              \--*  ADD       int    <l:$47, c:$1c1>
N008 (  7,  8)              [000020] -A--G-------                 +--*  COMMA     int    <l:$45, c:$1c0>
N006 (  6,  7)              [000018] -A--G---R---                 |  +--*  ASG       int    $VN.Void
N005 (  1,  1)              [000017] D------N----                 |  |  +--*  LCL_VAR   int    V02 cse0         d:1 <l:$45, c:$1c0>
N004 (  6,  7)              [000010] ----G-------                 |  |  \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------                 |  |     +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------                 |  |     |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------                 |  |     \--*  CNS_INT   int    21 $44
N007 (  1,  1)              [000019] ------------                 |  \--*  LCL_VAR   int    V02 cse0         u:1 <l:$45, c:$1c0>
N009 (  1,  1)              [000006] ------------                 \--*  CNS_INT   int    43 $46

exp =N006 (  8,  9)              [000016] -A--G-------              *  NEG       int    <l:$45, c:$182>
N005 (  7,  8)              [000015] -A--G-------              \--*  NEG       int    <l:$44, c:$181>
N008 (  7,  8)              [000020] -A--G-------                 \--*  COMMA     int    <l:$45, c:$1c0>
N006 (  6,  7)              [000018] -A--G---R---                    +--*  ASG       int    $VN.Void
N005 (  1,  1)              [000017] D------N----                    |  +--*  LCL_VAR   int    V02 cse0         d:1 <l:$45, c:$1c0>
N004 (  6,  7)              [000010] ----G-------                    |  \--*  ADD       int    <l:$45, c:$1c0>
N002 (  4,  5)              [000014] ----G-------                    |     +--*  NEG       int    <l:$43, c:$180>
N001 (  3,  4)              [000009] ----G-------                    |     |  \--*  CLS_VAR   int    Hnd=0xbfd83170 Fseq[_counter] <l:$42, c:$140>
N003 (  1,  1)              [000008] ------------                    |     \--*  CNS_INT   int    21 $44
N007 (  1,  1)              [000019] ------------                    \--*  LCL_VAR   int    V02 cse0         u:1 <l:$45, c:$1c0>


Assert failure(PID 6956 [0x00001b2c], Thread: 19572 [0x4c74]): Assertion failed 'link' in 'RyuJitReproduction.Program:Problem():int' during 'Optimize Valnum CSEs' (IL size 23)

    File: C:\Users\Accretion\source\dotnet\runtime\src\coreclr\jit\optcse.cpp Line: 3290
    Image: C:\Users\Accretion\source\dotnet\runtime\artifacts\bin\coreclr\Windows.x64.Checked\CoreRun.exe

Looking into it, I think the root cause is that morph doesn't account for possible CSEs when folding NET(NEG). Will submit a fix for this shortly. One more special case for CSE in morph, but what can one do.

A bit of a separate question is should we even try do CSE on such trees...