JIT: IV widening does not kick in for simple foreach over `List<int>`

[jakobbotsch]

Example taken from #9304:

    static int SumForeach(List<int> l)
    {
        int result = 0;

        foreach (int i in l)
        {
            result += i;
        }

        return result;
    }

Codegen:

; Assembly listing for method Program:SumForeach(System.Collections.Generic.List`1[int]):int (FullOpts)
; Emitting BLENDED_CODE for X64 with AVX - Windows
; FullOpts code
; optimized code
; rsp based frame
; fully interruptible
; No PGO data
; 2 inlinees with PGO data; 4 single block inlinees; 0 inlinees without PGO data
; Final local variable assignments
;
;  V00 arg0         [V00,T07] (  3,  3   )     ref  ->  rcx         class-hnd single-def <System.Collections.Generic.List`1[int]>
;  V01 loc0         [V01,T04] (  4, 12.27)     int  ->  rax        
;* V02 loc1         [V02    ] (  0,  0   )  struct (24) zero-ref    ld-addr-op <System.Collections.Generic.List`1+Enumerator[int]>
;* V03 loc2         [V03    ] (  0,  0   )     int  ->  zero-ref   
;  V04 OutArgs      [V04    ] (  1,  1   )  struct (32) [rsp+0x00]  do-not-enreg[XS] addr-exposed "OutgoingArgSpace"
;* V05 tmp1         [V05    ] (  0,  0   )  struct (24) zero-ref    ld-addr-op "NewObj constructor temp" <System.Collections.Generic.List`1+Enumerator[int]>
;* V06 tmp2         [V06,T06] (  0,  0   )   ubyte  ->  zero-ref    "Inline return value spill temp"
;* V07 tmp3         [V07    ] (  0,  0   )     ref  ->  zero-ref    class-hnd "Inline stloc first use temp" <System.Collections.Generic.List`1[int]>
;  V08 tmp4         [V08,T03] (  3, 12.63)     ref  ->  rcx         single-def "field V02._list (fldOffset=0x0)" P-INDEP
;  V09 tmp5         [V09,T00] (  6, 23.54)     int  ->  rdx         "field V02._index (fldOffset=0x8)" P-INDEP
;* V10 tmp6         [V10,T11] (  0,  0   )     int  ->  zero-ref    single-def "field V02._version (fldOffset=0xc)" P-INDEP
;  V11 tmp7         [V11,T05] (  2,  7.27)     int  ->   r8         "field V02._current (fldOffset=0x10)" P-INDEP
;  V12 tmp8         [V12,T08] (  3,  3   )     ref  ->  rcx         single-def "field V05._list (fldOffset=0x0)" P-INDEP
;* V13 tmp9         [V13,T12] (  0,  0   )     int  ->  zero-ref    single-def "field V05._index (fldOffset=0x8)" P-INDEP
;* V14 tmp10        [V14,T09] (  0,  0   )     int  ->  zero-ref    single-def "field V05._version (fldOffset=0xc)" P-INDEP
;* V15 tmp11        [V15    ] (  0,  0   )     int  ->  zero-ref    single-def "field V05._current (fldOffset=0x10)" P-INDEP
;  V16 tmp12        [V16,T01] (  3, 21.81)     ref  ->   r8         "arr expr"
;* V17 cse0         [V17,T10] (  0,  0   )     int  ->  zero-ref    "CSE #01: aggressive"
;  V18 cse1         [V18,T02] (  2, 16   )     int  ->   r8         "CSE #02: aggressive"
;
; Lcl frame size = 40

G_M40154_IG01:  ;; offset=0x0000
       sub      rsp, 40
						;; size=4 bbWeight=1 PerfScore 0.25
G_M40154_IG02:  ;; offset=0x0004
       xor      eax, eax
       mov      edx, dword ptr [rcx+0x14]
       xor      edx, edx
       jmp      SHORT G_M40154_IG04
       align    [0 bytes for IG03]
						;; size=9 bbWeight=1 PerfScore 4.50
G_M40154_IG03:  ;; offset=0x000D
       add      eax, r8d
						;; size=3 bbWeight=3.63 PerfScore 0.91
G_M40154_IG04:  ;; offset=0x0010
       mov      r8d, dword ptr [rcx+0x10]
       cmp      edx, r8d
       jae      SHORT G_M40154_IG06
						;; size=9 bbWeight=8 PerfScore 26.00
G_M40154_IG05:  ;; offset=0x0019
       mov      r8, gword ptr [rcx+0x08]
       cmp      edx, dword ptr [r8+0x08]
       jae      SHORT G_M40154_IG07
       mov      r10d, edx
       mov      r8d, dword ptr [r8+4*r10+0x10]
       inc      edx
       jmp      SHORT G_M40154_IG03
						;; size=22 bbWeight=3.63 PerfScore 38.16
G_M40154_IG06:  ;; offset=0x002F
       add      rsp, 40
       ret      
						;; size=5 bbWeight=4 PerfScore 5.00
G_M40154_IG07:  ;; offset=0x0034
       call     CORINFO_HELP_RNGCHKFAIL
       int3     
						;; size=6 bbWeight=0 PerfScore 0.00

; Total bytes of code 58, prolog size 4, PerfScore 74.82, instruction count 21, allocated bytes for code 58 (MethodHash=ae626325) for method Program:SumForeach(System.Collections.Generic.List`1[int]):int (FullOpts)
; ============================================================

The zero extension in

       mov      r10d, edx
       mov      r8d, dword ptr [r8+4*r10+0x10]

is not expected.

[dotnet-policy-service]

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

[jakobbotsch]

The problem is that List<T>.Enumerator.MoveNext() has two separate definitions of the IV _index:

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Lines 1206 to 1229 in 3e569f5

	public bool MoveNext()
	{
	List<T> localList = _list;
	if (_version == localList._version && ((uint)_index < (uint)localList._size))
	{
	_current = localList._items[_index];
	_index++;
	return true;
	}
	return MoveNextRare();
	}
	private bool MoveNextRare()
	{
	if (_version != _list._version)
	{
	ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
	}
	_index = _list._size + 1;
	_current = default;
	return false;
	}

RBO manages to get rid of the MoveNextRare call, but by that point it's too late since the SSA we've built already refers to both defs. That makes scalar evolution analysis unable to reason that List<T>.Enumerator._index is a normal add recurrence induction variable, and we only do IV widening when we can prove that.

With DOTNET_JitOptRepeat we do manage to analyze it in the second iteration after rebuilding SSA.

MoveNextRare() returns false always, so it might be possible to use this fact to optimize flow before we get to SSA such that the loop header does not have that definition as a PHI input at all. Indeed fgOptimizeUncondBranchToSimpleCond actually manages to do this jump threading required before we make it to SSA:
Before:

***** BB06 [0014]
STMT00024 ( INL04 @ 0x048[E-] ... ??? ) <- INLRT @ 0x017[E-]
               [000102] DA---+-----                         ▌  STORE_LCL_VAR int    V06 tmp2         
               [000101] -----+-----                         └──▌  CNS_INT   int    1

...

***** BB09 [0019]
STMT00020 ( INL04 @ 0x04A[E-] ... ??? ) <- INLRT @ 0x017[E-]
               [000071] DA---+-----                         ▌  STORE_LCL_VAR int    V06 tmp2         
               [000171] -----+-----                         └──▌  CNS_INT   int    0

------------ BB10 [0016] [017..020) -> BB03(0.5),BB11(0.5) (cond), preds={BB06,BB09} succs={BB11,BB03}

***** BB10 [0016]
STMT00004 ( 0x017[E-] ... ??? )
               [000012] -----+-----                         ▌  JTRUE     void  
               [000011] J----+-N---                         └──▌  NE        int   
               [000103] -----+-----                            ├──▌  LCL_VAR   ubyte  V06 tmp2         
               [000010] -----+-----                            └──▌  CNS_INT   int    0

after:

fgOptimizeUncondBranchToSimpleCond(from BB06 to cond BB10), modified BB06
   expecting opts to key off V06 in BB06
Considering uncond to cond BB09 -> BB10

....

***** BB06 [0014]
STMT00024 ( INL04 @ 0x048[E-] ... ??? ) <- INLRT @ 0x017[E-]
               [000102] DA---+-----                         ▌  STORE_LCL_VAR int    V06 tmp2         
               [000101] -----+-----                         └──▌  CNS_INT   int    1

***** BB06 [0014]
STMT00030 ( ??? ... ??? )
               [000190] -----------                         ▌  JTRUE     void  
               [000191] J------N---                         └──▌  NE        int   
               [000192] -----------                            ├──▌  LCL_VAR   ubyte  V06 tmp2         
               [000193] -----------                            └──▌  CNS_INT   int    0

...
***** BB09 [0019]
STMT00020 ( INL04 @ 0x04A[E-] ... ??? ) <- INLRT @ 0x017[E-]
               [000071] DA---+-----                         ▌  STORE_LCL_VAR int    V06 tmp2         
               [000171] -----+-----                         └──▌  CNS_INT   int    0

***** BB09 [0019]
STMT00004 ( 0x017[E-] ... ??? )
               [000012] -----+-----                         ▌  JTRUE     void  
               [000011] J----+-N---                         └──▌  NE        int   
               [000103] -----+-----                            ├──▌  LCL_VAR   ubyte  V06 tmp2         
               [000010] -----+-----                            └──▌  CNS_INT   int    0

but we don't manage to fold the flow until RBO.

@AndyAyersMS I wonder if it would be possible to run this jump threading before morph so that morph can take care of simplifying the flow before building SSA.

I suppose another possibility would be to try to teach IV ops to ignore SSA defs from unreachable blocks.

[jakobbotsch]

@AndyAyersMS I wonder if it would be possible to run this jump threading before morph so that morph can take care of simplifying the flow before building SSA.

This is as simple as passing doTailDup = true in the first fgUpdateFlowGraphPhase call, but it's not sufficient because there is a dead store in BB09 as well that inhibits the jump threading from kicking in. So we also have to reorder flow graph opts with early liveness to see that dead store eliminated. Of course reordering these may also impact the precision of liveness. I'm playing around with it locally.

[jakobbotsch]

The above works for this case but has a lot of churn overall, so I'm not sure how feasible it is.

[AndyAyersMS]

I can't quite follow in the above what happens with current code vs various experiments.

As you've noted, fgOptimizeUncondBranchToSimpleCond is a simplistic variant of jump threading but it defers all the optimization until later. Because it is simplistic it will often duplicate code for no benefit. If we enable it early, I would have expected morph to be able to do the folding. We could try and build a better heuristic perhaps, or only enable it early and not again later?

I also had plans for teaching jump threading about certain ignorable side effects but haven't worked on that for a while.

[jakobbotsch]

The above is all on current code, no experiments. I was just showing that fgOptimizeUncondBranchToSimpleCond actually does the jump threading we would like to see before SSA is built, but since it runs after morph we don't end up "exposing" this optimization to SSA.
Moving it before morph did allow morph to optimize things, but has a lot of churn: https://gist.github.com/jakobbotsch/24cbd9bfc1de4674d2da3cc9f9fe6de3
Improvements in many real world collections, but I also see lots of regressions (e.g. it often seems to break unrolling of loops ranging over vectors). So seems like a lot of work would be required to sort this out.

Perhaps I can try running a version that only does the tail duplication without any other flow graph changes before morph.

[AndyAyersMS]

Yeah, that might help -- also perhaps avoid trying to optimize blocks with backedges in or out, if we happen to have a DFS handy.

[jakobbotsch]

Another way to fix this would be to move the scalar evolution analysis to happen as part of VN. Then we could make use of the sparse conditional propagation that VN does now to realize during the analysis that one of the PHI predecessors is unreachable, making the IV a proper add recurrence.

Edit: Although perhaps it is not strong enough to realize that this particular predecessor is unreachable because of the loop structure...