JIT should optimize {array | span}.Length division by constant that is power of 2

[gfoidl]

E.g.

Span<byte> span = ...
nint n = span.Length / 8;    // or any constant that is a power of two

produces integer division by consant
(Also tested with .NET 6 RC 1, and didn't find an issue or PR that addressed this.)

JIT should be able to recnogize that .Length isn't negative, so produce code that is equivalent to

nint n = (nint)(uint)span.Length / 8;

which produces (on x86)

shr rax, 3

This pattern is quite common, so it's tedious and a bit unreadable to have the "cast-hacks".

category:cq
theme:expression-opts
skill-level:intermediate
cost:small
impact:small

[dotnet-issue-labeler]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[EgorBo]

heh, I did for arrays (GT_ARRLEN) #32368 🙂

[gfoidl]

Perfect 👍🏻, so the step to enable this for Span too isn't that big (hopefully).

[SingleAccretion]

It was somewhat trivial for arrays, it is not so trivial for spans, unfortunately, the reason being that most often the span's length is just a GT_LCL_VAR. Perhaps we can mark a local produced for the length specially when promoting the span.

[ghost]

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

Issue Details

---

E.g.

Span<byte> span = ...
nint n = span.Length / 8;    // or any constant that is a power of two

produces integer division by consant
(Also tested with .NET 6 RC 1, and didn't find an issue or PR that addressed this.)

JIT should be able to recnogize that .Length isn't negative, so produce code that is equivalent to

nint n = (nint)(uint)span.Length / 8;

which produces (on x86)

shr rax, 3

This pattern is quite common, so it's tedious and a bit unreadable to have the "cast-hacks".

Author:	gfoidl
Assignees:	-
Labels:	area-CodeGen-coreclr, untriaged
Milestone:	-

[EgorBo]

I made a quick fix and checking diffs now

[stephentoub]

How many other optimizations are there that currently apply only to arrays but could also be relevant to spans? It'd be great to drive that list to zero and then ensure no additional ones creep in. More and more code is being converted from arrays to spans, and we want to avoid unnecessary regressions.

[SingleAccretion]

There are certainly some optimizations that do not benefit spans equally.

The most obvious example is VN, which can "see" through assignments to array elements (because there is intrinsic understanding of array indexing similar to that of fields built into the compiler):

private static int RedundantBranchSpan(Span<int> a)
{
    a[1] = 0;

    if (a[1] is 0)
    {
        return 1;
    }

    a[2] = 1;

    if (a[1] is 0) // The compiler will not see this branch as redundant, there was a write to memory.
    {
        return 1;
    }

    return 2;
}

private static int RedundantBranchArray(int[] a)
{
    a[1] = 0;

    if (a[1] is 0)
    {
        return 1;
    }

    a[2] = 1;

    if (a[1] is 0) // The compiler will see this branch as redundant since it knows a[1] and a[2] don't interfere
    {
        return 1;
    }

    return 2;
}

// VNs are also used for CSE purposes, so redundant loads may not be optimized as well.
private static int SpanDoubleLoad(Span<int> a)
{
    int sum = 0;

    sum += a[1];

    a[2] = 1;

    sum += a[1]; // This will be a load
    
    return sum;
}

private static int ArrayDoubleLoad(int[] a)
{
    int sum = 0;

    sum += a[1];

    a[2] = 1;

    sum += a[1]; // a[1] will be CSEed and used from a register
    
    return sum;
}

It is hard for me to say which other optimizations are affected (and how), and how impactful the above is in real-world code, or how hard would the fix be (I suspect though that it will not be so trivial, because the existing mechanism already has some unsightly maintainability problems).

[JulieLeeMSFT]

The most obvious example is VN,

cc @jakobbotsch for VN on span.
cc @dotnet/jit-contrib