AndyAyersMS
commented
1 year ago Running with DOTNET_JitCloneLoops=0 to simplify things a little.
The problem goes away if optJumpThreadPhi is disabled.
The problem goes away if CSE is diabled.
The actual bug is caused by this CSE:
Considering CSE #02 {$212, $28a} [def=52.182163, use=52.182163, cost= 6, call]
CSE Expression :
N006 ( 6, 6) CSE #02 (def)[000024] ---XG------ * ADD int <l:$215, c:$214>
N004 ( 4, 4) CSE #01 (def)[000092] ---XG------ +--* IND int <l:$210, c:$211>
N003 ( 2, 2) [000133] -------N--- | \--* ADD byref <l:$3c1, c:$3c2>
N001 ( 1, 1) [000020] ----------- | +--* LCL_VAR ref V02 loc1 u:3 <l:$287, c:$103>
N002 ( 1, 1) [000132] ----------- | \--* CNS_INT long 16 Fseq[_size] $382
N005 ( 1, 1) [000023] ----------- \--* CNS_INT int -2 $cc
Moderate CSE Promotion (CSE is live across a call) (156.546490 >= 100.000000)
cseRefCnt=156.546490, aggressiveRefCnt=200.000000, moderateRefCnt=100.000000
defCnt=52.182163, useCnt=52.182163, cost=6, size=6, LiveAcrossCall
def_cost=2, use_cost=1, extra_no_cost=10, extra_yes_cost=100
CSE cost savings check (323.092979 >= 256.546490) passes
Promoting CSE:
lvaGrabTemp returning 10 (V10 rat0) (a long lifetime temp) called for CSE - moderate.
CSE #02 is single-def, so associated CSE temp V10 will be in SSA
New refCnts for V10: refCnt = 2, refCntWtd = 1.04
New refCnts for V10: refCnt = 3, refCntWtd = 1.57
CSE #02 def at [000024] replaced in BB03 with def of V10
optValnumCSE morphed tree:
N010 ( 13, 11) [000025] DA-XG------ * STORE_LCL_VAR int V04 loc3 d:2 <l:$28d, c:$28c>
N009 ( 13, 11) [000227] -A-XG------ \--* COMMA int <l:$215, c:$214>
N007 ( 10, 9) CSE #02 (def)[000225] DA-XG------ +--* STORE_LCL_VAR int V10 cse0 d:1 $VN.Void
N006 ( 6, 6) [000024] ---XG------ | \--* ADD int <l:$215, c:$214>
N004 ( 4, 4) CSE #01 (def)[000092] ---XG------ | +--* IND int <l:$210, c:$211>
N003 ( 2, 2) [000133] -------N--- | | \--* ADD byref <l:$3c1, c:$3c2>
N001 ( 1, 1) [000020] ----------- | | +--* LCL_VAR ref V02 loc1 u:3 <l:$287, c:$103>
N002 ( 1, 1) [000132] ----------- | | \--* CNS_INT long 16 Fseq[_size] $382
N005 ( 1, 1) [000023] ----------- | \--* CNS_INT int -2 $cc
N008 ( 3, 2) [000226] ----------- \--* LCL_VAR int V10 cse0 u:1 <l:$215, c:$214>
Working on the replacement of the CSE #02 use at [000054] in BB11
Unmark CSE use #01 at [000116]: 1 -> 0
optValnumCSE morphed tree:
N002 ( 3, 3) [000055] DA--G------ * STORE_LCL_VAR int V05 loc4 d:4 <l:$28d, c:$28c>
N001 ( 3, 2) [000228] ----------- \--* LCL_VAR int V10 cse0 u:1 <l:$212, c:$213>The value of V02._size can change between the fetch in BB03 and the one in BB11, via this call
***** BB07
STMT00012 ( 0x033[E-] ... 0x03D )
N003 ( 16, 9) [000043] --CXG------ * CALL void Program:DoWork(System.Collections.Generic.List`1[NamedSet],int) $VN.Void
N001 ( 1, 1) [000041] ----------- arg0 in rcx +--* LCL_VAR ref V02 loc1 u:3 <l:$287, c:$103>
N002 ( 1, 1) [000042] ----------- arg1 in rdx \--* LCL_VAR int V04 loc3 u:3 $247CSE availability propagates from BB03 through BB07 and BB10 to BB11.
If RBO's optJumpThreadPhi is disabled, then, BB10 has an additional pred BB09 where the CSE is not available.
CSE then treats the instance in BB11 as a def instead of a use, and so no CSE happens.
CSE is matching liberal VNs here. So looking at VN:
BB03
N001 [000020] LCL_VAR V02 loc1 u:3 => <l:$287 {$404[$340]}, c:$103 {MemOpaque:L00}>
N002 [000132] CNS_INT 16 Fseq[_size] => $382 {LngCns: 16}
N003 [000133] ADD => <l:$3c1 {ADD($287, $382)}, c:$3c2 {ADD($103, $382)}>
VNForHandle(_size) is $44, fieldType is int, size = 4
VNForMapSelect($307, $44):mem returns $406 {$307[$44]}
VNForMapSelect($406, $287):int returns $20f {$406[$287]}
N004 [000092] IND => <l:$210 {norm=$20f {$406[$287]}, exc=$28a {NullPtrExc($287)}}, c:$211 {norm=$146 {MemOpaque:L01}, exc=$28b {NullPtrExc($103)}}>
N005 [000023] CNS_INT -2 => $cc {IntCns -2}
N006 [000024] ADD => <l:$215 {norm=$212 {ADD($cc, $20f)}, exc=$28a {NullPtrExc($287)}}, c:$214 {norm=$213 {ADD($cc, $146)}, exc=$28b {NullPtrExc($103)}}>
BB11
N001 [000050] LCL_VAR V02 loc1 u:3 => <l:$287 {$404[$340]}, c:$103 {MemOpaque:L00}>
N002 [000161] CNS_INT 16 Fseq[_size] => $382 {LngCns: 16}
N003 [000162] ADD => <l:$3c1 {ADD($287, $382)}, c:$3c2 {ADD($103, $382)}>
VNForHandle(_size) is $44, fieldType is int, size = 4
VNForMapSelect($307, $44):mem returns $406 {$307[$44]}
VNForMapSelect($406, $287):int returns $20f {$406[$287]}
N004 [000116] IND => <l:$210 {norm=$20f {$406[$287]}, exc=$28a {NullPtrExc($287)}}, c:$218 {norm=$147 {MemOpaque:L00}, exc=$28b {NullPtrExc($103)}}>
N005 [000053] CNS_INT -2 => $cc {IntCns -2}
N006 [000054] ADD => <l:$215 {norm=$212 {ADD($cc, $20f)}, exc=$28a {NullPtrExc($287)}}, c:$21a {norm=$219 {ADD($cc, $147)}, exc=$28b {NullPtrExc($103)}}>We see the same field _size fetched from the heap off of the same base $287.
As noted, the path from BB03 to BB11 includes call that takes V02 as an arg.
***** BB07, STMT00012(before)
N003 ( 16, 9) [000043] --CXG------ * CALL void Program:DoWork(System.Collections.Generic.List`1[NamedSet],int)
N001 ( 1, 1) [000041] ----------- arg0 in rcx +--* LCL_VAR ref V02 loc1 u:3
N002 ( 1, 1) [000042] ----------- arg1 in rdx \--* LCL_VAR int V04 loc3 u:3
N001 [000041] LCL_VAR V02 loc1 u:3 => <l:$287 {$404[$340]}, c:$103 {MemOpaque:L00}>
N002 [000042] LCL_VAR V04 loc3 u:3 => $247 {PhiDef($4, $3, $209)}
fgCurMemoryVN[GcHeap] assigned for CALL at [000043] to VN: $1c8.
N003 [000043] CALL => $VN.VoidWhich should trash any indirs in the GC heap based off of V02. It introduces a new memory VN.
But this memory VN merges back into the memory PHI in BB10 creating memory VN $307 which is used in the CSEs above. BB10 is pred to both BB03 and BB11. So per VN, they seem to be reading from the same memory.
Building phi application: $cb = SSA# 9.
Building phi application: $c6 = SSA# 6.
Building phi application: $305 = phi($c6, $cb).
Building phi application: $c5 = SSA# 5.
Building phi application: $306 = phi($c5, $305).
The SSA definition for GcHeap (#6) at start of BB10 is $307 {PhiMemoryDef($43, $306)}There is a loop here from BB03->BB10, with entry at BB09. But inside there we see an unrecognized loop that excludes BB09?
=======================
So, options?
- The bug is in RBO. We should not jump thread through a block with a memory PHI.
- Inhibiting RBO this way "fixes" the bug but feels hacky. Seems like a similar case could be found that does not require RBO. But I do not know this for sure.
- The bug is in CSE. CSE should kill availability of
CSE #02along the path from BB03 to BB11.- Note CSE never kills availability explicitly today, and it's not obvious how it could/should. Many different tree shapes can have the same VN. Consider a case where we assign a constant to a ref class field and then propagate that constant to unescaped byrefs. Subsequent loads of the field or byref should be CSEs, but only some of these will get killed by heap havoc. Seems like we would have to track availability per tree instead of per VN? Perhaps more simply we can just kill the whole CSE if any of its constituent trees is killed?
- The bug is in VN. We should not assign the same VN to the trees in BB03 and BB11.
- One invariant we should hold dear is that if two trees have the same VN they represent the same value at runtime. RBO for example relies on two predicate trees with the same VN to evaluate the same way. But consider that hoisting already has to do additional tests for "memory dependent" VNs to establish loop invariance, so even just a single tree may not produce the same value from one loop iteration to the next. The solution there was to separately track the implicit memory dependence of the VN and show that the same memory is available before the loop as within. But in this case the same memory is avaiable for both BB03 and BB11 indirs. So perhaps the invariant that holds here is more subtle?
- The only "variable" in the VNs here is the VN for memory, and VN gives all memory SSA defs the same VN, leading to.....
- The bug is in SSA. We should not have the same SSA def for memory in BB03 and BB11; if they differed, we would not have the same VN and so not try and CSE.
- There are no memory stores in BB10, BB03 or BB11, so no obvious way to figure out where or why to introduce this new def. So this also feels somewhat artificial/hacky.
- The bug is LOOPs, caused by the un-recognized loop headed by BB10
- In particular we have a "middle exit" loop where the side effect that causes trouble happens between the loop exit and loop header. Maybe for such loops we need to induce a new SSA def when we leave the loop, to represent potential ambiguity into which iteration might represent various bits of memory?
One question I've been asking myself here without any clear insight is why this issue is specific to VNs involving memory. Could we have the same situation with just a simple local that's conditionally defined? If so, it seems like for sure we would have hit this case already.
Also not clear how narrow/fragile the repro is; Egor suggests it is very sensitive to this code shape. Perhaps some experimentation will suggest which of the elements above is necessary?
EgorBo
SingleAccretion
The following program throws
ArgumentOutOfRangeExceptionin Release and finishes normally in Debug:https://gist.github.com/EgorBo/bdd1c3c2c65a80681e96f840df40cd2a
cc @AndyAyersMS @dotnet/jit-contrib