Investigate optimizing away Span<class> type checks

[JosephTremoulet]

The Span constructors that take arrays have checks to ensure that the dynamic type of the T[] argument is exactly T[] (as opposed to U[] for some subtype U of T), since Spans, unlike arrays, aren't covariant. We should see if there are cases where the JIT can optimize away this check (when the constructor gets inlined), such as when T is a sealed type or when we can propagate an exact type from a new T[] expression.
category:cq
theme:optimization
skill-level:expert
cost:medium

[AndyAyersMS]

We currently can't propagate exactness from newarr, so there's not much we can do here until that is addressed.

Seems like an easy enough thing to fix though, since array allocation is idiomatic.

[AndyAyersMS]

Have added type capture from newarr, at least a simple variant, where we are recognizing the helper call that creates the array. Would be nice to generalize this but we don't have ways of expressing type exactness or non-null-ness on the evaluation stack. Something to consider for the future.

Am now looking to augment the optimization done in morph on obj.GetType() == ... to try and use information from gtGetClassHandle to give a better estimate (sometimes an exact estimate) of the object's type. Here we are trusting that the importer/inliner type deductions remain valid through calls to morph, which is not guaranteed, though seems likely.

To do this optimization cleanly we also need to propagate non-nullness. This isn't something we are set up to do very well yet. The only cases we where we can propagate non-null on assignment of non-null are single-def temps, like inlinee args or some internal temps. Single-def locals may have uses before defs.

Otherwise we have to leave a residual null check.

[JosephTremoulet]

We have non-null propagation in assertion prop, should it be able to clean things up or there's a reason we need to propagate non-nullness earlier and/or that assertion prop shouldn't be able to handle the analysis needed here?

[JosephTremoulet]

Also, is it easy to get cases where the array referent type is sealed?

[AndyAyersMS]

I wasn't sure morph would nicely handle a comma injection needed for an upstream null check, but it looks like can.

Array of final-ref-type may be somewhat frequent given string[]. It is something we can look for generally (eg at the tail end of gtGetClassHandle) if we don't have an exact type. It would require a few more calls back into the VM: getClassAttribs to check for arrayness, getChildType to get the element type, and then getClassAttribs again to check for finalness of the child type. And maybe some recursion if the element type its itself array-of-ref type.

I can prototype and get some idea how often it comes up.

[AndyAyersMS]

Implemented a prototype. This allows the jit to remove the Span ctor type check for string[] even if the array constructor is not seen.

The change has 3 parts:

• obtain class handles for array contructors
• sharpen exactness for final non-variant-non-array, and array-of final non-variant-non-array
• use info in morph's type test optimization

While we find a lot more exact types with these changes I don't see any impact on codegen in the framework jit diff set. I'll look through the full test suite to see if anything pops up there outside of the span tests.

This is not to say the extra exactness is useless or a bad thing -- one could imagine doing more with exact types than we do now -- say, optimizing away array store checks. But currently we don't find much use for it outside of the one case seen in the span constructor. Devirtualization can already get most cases here because the exactness sharpening relies on final and devirt can trigger off of final already.

So will likely shelve for now pending further motivating cases. Also if we do this for real I'd like to pull the type test optimizations earlier....

[AndyAyersMS]

If user constructs a Span<T> with T a ref type in a loop we might not be able to optimize away the covariant type check in many cases, even with the above. This check is quite costly. We might be able to hoist it or express it more compactly/cheaply via some helper or intrinsic (like we do for the similar array store check).

ReadOnlySpan<T> is immune from this as no type test is required, and Span<T> for value types short-circuits the type test and so is also immune.

Note if caller is shared we can't even inline, see #7580, and in such cases a cheaper check is appealing, if viable.

Example below from @ahsonkhan. Note some trickery may be needed to get past CS0165 (this error seems not to fire if you build against ref assemblies, thanks perhaps to dotnet/roslyn#1722) -- if you fix it (as I did initially) by initializing the span local you are likely introducing a dominating check that will allow the jit to optimize away the in-loop checks.

[MethodImpl(MethodImplOptions.NoInlining)]
public static Span<string> ConstructSpanString(string[] array, bool output = true)
{
    Stopwatch sw = new Stopwatch();
    Span<string> span;

    sw.Restart();
    for (int j = 0; j < 100000; j++)
    {
        span = new Span<string>(array);
    }
    sw.Stop();

    if (output) Console.WriteLine("Span - length: " + span.Length + " : " + typeof(string) + " : " + sw.ElapsedTicks);
    return span;
}

[EgorBo]

@AndyAyersMS @JosephTremoulet isn't it fixed in #32790 ?

[AndyAyersMS]

Yes. Thanks again for the fix!