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

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

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

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

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.

I made a quick fix and checking diffs now

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.

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).

@jakobbotsch

The most obvious example is VN,

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

Navigation Menu

Repository navigation

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

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

EgorBo commented on Oct 4, 2021

gfoidl commented on Oct 4, 2021

SingleAccretion commented on Oct 4, 2021

EgorBo commented on Oct 4, 2021

stephentoub commented on Oct 4, 2021

SingleAccretion commented on Oct 4, 2021

JulieLeeMSFT commented on Oct 4, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions