JIT: avoid store covariance check for ref-type ldelem from same array

[AndyAyersMS]

The jit optimizes stelem.ref to avoid the store covariance check when the value being stored is from the same array (at least for obvious cases like a[i] = a[j]) or the value being stored is null.

But it doesn't do the same for stelem with a ref type. Looks like it easily could.

category:cq
theme:optimization
skill-level:expert
cost:small

[AndyAyersMS]

Also note that in the typical array element "swap" idiom the jit only optimizes one of the store checks, eg

object temp = a[i];
a[i] = a[j];        // store check optimized by jit to simple write barrier
a[j] = temp;        // store check not optimized

[ViktorHofer]

I found that great blog from Dave Detlefs about the state of bounds check elimination in the CLR from 2009: https://blogs.msdn.microsoft.com/clrcodegeneration/2009/08/13/array-bounds-check-elimination-in-the-clr/.

If someone could give it a read, what has changed sine then? Which of the examples are now optimized by default by the JIT?

[mattwarren]

If someone could give it a read, what has changed sine then? Which of the examples are now optimized by default by the JIT?

I'm pretty sure that @mikedn has been looking at 'bounds check elimination' recently

[mikedn]

@ViktorHofer Bounds check elimination and covariance check elimination are different. The only thing they have in common is that for element stores you get a helper call that does both a bound check and a variance check (in cases that require it). Maybe a separate issue should be opened for this.

[ViktorHofer]

My bad, wrong issue. I wanted to post this in the Array.Reverse thread where it came up. Sorry!

[AndyAyersMS]

Have a prototype CovariantStore that uses SSA/VN to spot the element swap idiom. Currently shoehorned into assertion prop. Fires on following the various swap helpers in corelib, and (not shown) in maybe 20 odd methods in broader Fx.

System.Type:GetEnumData(byref,byref):this (x4)
System.Reflection.Emit.ILGenerator:SortExceptions(ref)
System.Globalization.CultureData:nativeEnumTimeFormats(ref,int,bool):ref
System.Collections.Generic.ArraySortHelper`1[__Canon]:SwapIfGreater(ref,ref,int,int)
System.Collections.Generic.ArraySortHelper`1[__Canon]:Swap(ref,int,int)
System.Collections.Generic.ArraySortHelper`1[__Canon]:PickPivotAndPartition(ref,int,int,ref):int (x3)
System.Collections.Generic.ArraySortHelper`1[__Canon]:Heapsort(ref,int,int,ref)
System.Collections.Generic.ArraySortHelper`1[__Canon]:DownHeap(ref,int,int,int,ref)
System.Collections.Generic.ArraySortHelper`1[__Canon]:InsertionSort(ref,int,int,ref)
System.Collections.Generic.GenericArraySortHelper`1[__Canon]:SwapIfGreaterWithItems(ref,int,int)
System.Collections.Generic.GenericArraySortHelper`1[__Canon]:Swap(ref,int,int)
System.Collections.Generic.GenericArraySortHelper`1[__Canon]:PickPivotAndPartition(ref,int,int):int (x3)
System.Collections.Generic.GenericArraySortHelper`1[__Canon]:Heapsort(ref,int,int)
System.Collections.Generic.GenericArraySortHelper`1[__Canon]:DownHeap(ref,int,int,int)
System.Collections.Generic.GenericArraySortHelper`1[__Canon]:InsertionSort(ref,int,int)
System.Collections.Generic.ArraySortHelper`2[__Canon,__Canon]:SwapIfGreaterWithItems(ref,ref,ref,int,int) (x2)
System.Collections.Generic.ArraySortHelper`2[__Canon,__Canon]:Swap(ref,ref,int,int) (x2)
System.Collections.Generic.ArraySortHelper`2[__Canon,__Canon]:PickPivotAndPartition(ref,ref,int,int,ref):int (x2)
System.Collections.Generic.ArraySortHelper`2[__Canon,__Canon]:Heapsort(ref,ref,int,int,ref) (x2)
System.Collections.Generic.ArraySortHelper`2[__Canon,__Canon]:DownHeap(ref,ref,int,int,int,ref) (x2)
System.Collections.Generic.ArraySortHelper`2[__Canon,__Canon]:InsertionSort(ref,ref,int,int,ref) (x2)
System.Collections.Generic.GenericArraySortHelper`2[__Canon,__Canon]:SwapIfGreaterWithItems(ref,ref,int,int) (x2)
System.Collections.Generic.GenericArraySortHelper`2[__Canon,__Canon]:Swap(ref,ref,int,int) (x2)
System.Collections.Generic.GenericArraySortHelper`2[__Canon,__Canon]:PickPivotAndPartition(ref,ref,int,int):int (x2)
System.Collections.Generic.GenericArraySortHelper`2[__Canon,__Canon]:Heapsort(ref,ref,int,int) (x2)
System.Collections.Generic.GenericArraySortHelper`2[__Canon,__Canon]:DownHeap(ref,ref,int,int,int) (x2)
System.Collections.Generic.GenericArraySortHelper`2[__Canon,__Canon]:InsertionSort(ref,ref,int,int) (x2)

Only have the recognition part implemented so far. Looks like it may be a bit tedious to reconstruct the fully-loaded store tree from the helper call (we'll need a bounds check, in general). And this will eventually lower to a write barrier call. So result is not much code size savings, but a cheaper call into the runtime.

[AndyAyersMS]

Revised the recognition to destructure VNs instead of parsing the IR and realized I could let morph do the heavy lifting for new IR creation, so have updated the CovariantStore prototype to something that is fully functional.

jit-diffs shows regressions, because we're now making the bounds check explicit in jitted code rather than via the covariant store check helper. But this should be a perf win.

Total bytes of diff: 228 (0.00% of base)
    diff is a regression.

Top file regressions by size (bytes):
         212 : System.Private.CoreLib.dasm (0.00% of base)
          16 : Microsoft.CodeAnalysis.dasm (0.00% of base)

2 total files with size differences (0 improved, 2 regressed), 127 unchanged.

Top method regressions by size (bytes):
          52 ( 6.07% of base) : System.Private.CoreLib.dasm - Type:GetEnumData(byref,byref):this
          32 ( 1.14% of base) : System.Private.CoreLib.dasm - ArraySortHelper`1:PickPivotAndPartition(ref,int,int,ref):int (7 methods)
          16 ( 1.20% of base) : System.Private.CoreLib.dasm - ArraySortHelper`1:InsertionSort(ref,int,int,ref) (7 methods)
          14 ( 0.39% of base) : System.Private.CoreLib.dasm - ArraySortHelper`2:DownHeap(ref,ref,int,int,int,ref) (7 methods)
          13 ( 0.50% of base) : System.Private.CoreLib.dasm - ArraySortHelper`2:InsertionSort(ref,ref,int,int,ref) (7 methods)
          12 ( 0.88% of base) : System.Private.CoreLib.dasm - ArraySortHelper`2:SwapIfGreaterWithItems(ref,ref,ref,int,int) (7 methods)
          12 ( 0.30% of base) : System.Private.CoreLib.dasm - ArraySortHelper`2:PickPivotAndPartition(ref,ref,int,int,ref):int (7 methods)
          10 ( 0.45% of base) : System.Private.CoreLib.dasm - ArraySortHelper`1:DownHeap(ref,int,int,int,ref) (7 methods)
           8 ( 1.09% of base) : Microsoft.CodeAnalysis.dasm - ImmutableArrayExtensions:DeOrder(struct):struct (7 methods)
           8 ( 1.37% of base) : Microsoft.CodeAnalysis.dasm - ArrayExtensions:ReverseContents(ref,int,int) (7 methods)
           8 ( 0.76% of base) : System.Private.CoreLib.dasm - ArraySortHelper`1:SwapIfGreater(ref,ref,int,int) (9 methods)
           8 ( 5.10% of base) : System.Private.CoreLib.dasm - ILGenerator:SortExceptions(ref)
           8 ( 1.63% of base) : System.Private.CoreLib.dasm - ArraySortHelper`1:Swap(ref,int,int) (7 methods)
           8 ( 0.61% of base) : System.Private.CoreLib.dasm - ArraySortHelper`1:Heapsort(ref,int,int,ref) (7 methods)
           8 ( 1.08% of base) : System.Private.CoreLib.dasm - ArraySortHelper`2:Swap(ref,ref,int,int) (7 methods)
           8 ( 0.45% of base) : System.Private.CoreLib.dasm - ArraySortHelper`2:Heapsort(ref,ref,int,int,ref) (7 methods)
           3 ( 0.85% of base) : System.Private.CoreLib.dasm - CultureData:nativeEnumTimeFormats(ref,int,bool):ref

17 total methods with size differences (0 improved, 17 regressed), 203689 unchanged.

[AndyAyersMS]

Not sure I entirely trust these, but here are some perf results for array sorting of a ref type:

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-8650U CPU 1.90GHz (Kaby Lake R), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.100-alpha1-015528
  [Host]     : .NET Core 5.0.0 (CoreCLR 5.0.19.52501, CoreFX 5.0.19.53102), X64 RyuJIT
  Job-WQHOZR : .NET Core 5.0.0 (CoreCLR 5.0.19.55101, CoreFX 5.0.19.52915), X64 RyuJIT
  Job-OPDYOK : .NET Core 5.0.0 (CoreCLR 5.0.19.53101, CoreFX 5.0.19.52915), X64 RyuJIT

Method	Toolchain	Size	Mean
Array	base	512	54.40 us
Array	diff	512	47.56 us
Array_ComparerClass	base	512	58.07 us
Array_ComparerClass	diff	512	52.82 us
Array_ComparerStruct	base	512	61.70 us
Array_ComparerStruct	diff	512	57.13 us
Array_Comparison	base	512	57.57 us
Array_Comparison	diff	512	55.15 us
List	base	512	50.99 us
List	diff	512	46.01 us
LinqQuery	base	512	121.74 us
LinqQuery	diff	512	94.00 us
LinqOrderByExtension	base	512	102.13 us
LinqOrderByExtension	diff	512	93.47 us

[AndyAyersMS]

Have tried generalizing this a bit to handle cases like #6416, and some others (say destination is exactly object[]). But looks like I need a more general way to undo a call post-morph.

@dotnet/jit-contrib what's the best way, post morph, to "inline" a call? Looks like we do something similar when transforming recursive tail calls...? Hoist any setup to statements, accumulate non-setup early args, then late args...?

Here I am basically inlining a call to CORINFO_HELP_ARRADDR_ST, and stripping out the covariant store check part.

[AndyAyersMS]

Spanification of the corelib sort routines (#27700) has taken care of most of these cases, as spans are not covariant.

So I currently don't see much opportunity here.