ARM64: Optimize a % b operation

[kunalspathak]

Optimize a % b operation for ARM64 for following scenarios:

a is unsigned int, b is power of 2.

static uint PerformMod_1(uint i) {
       return i % 8;
}

Today we generate something like this:

        53037C01          lsr     w1, w0, #3
        531D7021          lsl     w1, w1, #3
        4B010000          sub     w0, w0, w1

We can generate:

   and     w2, w1, 3

a is signed int, b is power of 2.

static int PerformMod_2(int i) {
    return i % 16;
}

Today we generate:

G_M58511_IG02:
        131F7C01          asr     w1, w0, #31
        12000C21          and     w1, w1, #15
        0B000021          add     w1, w1, w0
        13047C21          asr     w1, w1, #4
        531C6C21          lsl     w1, w1, #4
        4B010000          sub     w0, w0, w1

We can generate:

        negs   x1, x0
        and    x0, x0, #(n - 1)
        and    x1, x1, #(n - 1)
        csneg  x0, x0, x1, mi

a is an int, b is a variable.

static uint PerformMod_3(int i, int j) {
    return i % j;
}

Today we generate:

        1AC10802          sdiv    w2, w0, w1  # or udiv if a is unsigned
        1B017C41          mul     w1, w2, w1
        4B010000          sub     w0, w0, w1

We can generate using msub:

        sdiv    w3, w2, w1
        msub    w3, w3, w1, w2

Reference: https://godbolt.org/z/yxH8jZ
Reference: https://patchwork.kernel.org/patch/11126001/

category:cq
theme:optimization
skill-level:intermediate
cost:medium

[Dotnet-GitSync-Bot]

I couldn't figure out the best area label to add to this issue. Please help me learn by adding exactly one area label.

[kunalspathak]

@BruceForstall

[EgorBo]

Jit currently always gives up on % on Arm and always converts it to a - (a / b) * b in the morph phase, thus existing %(GT_MOD, GT_UMOD) optimizations in both morph and lowering don't work for it (happen later).

[kunalspathak]

Yes, I have already spoke to @sandreenko about it and reverted some of the changes he did in dotnet/coreclr#18206. With that it handles the 1st case (where a is unsigned and b is power of 2). I need to handle other 2 cases yet.

[kunalspathak]

Definitely, this will not happen in .NET 6.0.

[kunalspathak]

@TIHan - for this issue, you can start with checking what it will take to combine mul/sub into msub. Related #64591

[tannergooding]

Just noting that unlike #64591, this one is over integer types and should be safe. I'm not aware of any cases (off the top of my head) where the output could differ for a * b + c when only handling integers.

Its certainly possible, however, that there is some edge case I'm not remembering or with certain variants of the instruction (there are variants that multiply, widen or narrow, and then add/subtract for example and these may have some edge case behavior depending on how they are used and other surrounding optimizations).

[EgorBo]

We already fold a * b + c into madd on arm.

[TIHan]

Closing as we have finished the optimizations listed here.

[JulieLeeMSFT]

#68885