Review the multi-op instruction usage for Arm64

[tannergooding]

After seeing the msub PR (#66621) which folds mul, sub into a single msub I went and looked in the Arm64 manual for other interesting "combined operation" instructions.

There is a set of (shifted register) instructions which can combine a shift, op (the variants ending with s also set flags):

• add, adds - Add
• sub, subs - Subtract
• cmp - Compare #84605
• cmn - Compare Negative #84667
• neg, negs - Negate #84667
• and, ands - Bitwise AND
• bic, bics - Bitwise bit clear
• eon - Bitwise exclusive OR NOT
• eor - Bitwise exclusive OR
• orr - Bitwise inclusive OR
• mvn - Bitwise NOT
• orn - Bitwise inclusive OR NOT
• tst - Test Bits
• cbz instead of cmp #0 [arm64] optimize test for bound checks against a 0 index #42514

There is a set of (extended register) instructions which can combine a zero-extend, op or sign-extend, op:

• add, adds - Add
• sub, subs - Subtract
• cmp - Compare
• cmn - Compare Negative

There is a set of (carry) instructions which can utilize the carry from a previous operation:

• adc, adcs - Add with carry
• sbc, sbcs - Subtract with carry
• ngc, ngcs - Negate with carry

There are the multiply integer instructions which can combine an op, mul:

• madd - Multiply-add
• msub - Multiply-subtract
• mneg - Multiply-negate

There are then some long multiply instructions which can return a product twice the size of the inputs (i32 * i32 = i64 or similar; effectively good for covering zero or sign extend, multiply):

• smull, umull - Multiply long
• smaddl, umaddl - Multiply-add long Optimise long multiply + add/sub/neg on arm64. #91886
• smsubl, umsubl - Multiply-subtract long Optimise long multiply + add/sub/neg on arm64. #91886
• smnegl, umnegl - Multiply-negate long Optimise long multiply + add/sub/neg on arm64. #91886

Finally there is the "multiply high" instructions which can return just the upper bits of a wide multiply:

• smulh, umulh - Multiply High

There may be other interesting instructions as well, but these are ones that may have broader usage/application and which likely be good to validate we are covering

category:implementation
theme:intrinsics

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

[ghost]

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

Issue Details

---

After seeing the msub PR (#66621) which folds mul, sub into a single msub I went and looked in the Arm64 manual for other interesting "combined operation" instructions.

There is a set of (shifted register) instructions which can combine a shift, op (the variants ending with s also set flags):

• add, adds - Add
• sub, subs - Subtract
• cmp - Compare
• cmn - Compare Negative
• neg, negs - Negate
• and, ands - Bitwise AND
• bic, bics - Bitwise bit clear
• eon - Bitwise exclusive OR NOT
• eor - Bitwise exclusive OR
• orr - Bitwise inclusive OR
• mvn - Bitwise NOT
• orn - Bitwise inclusive OR NOT
• tst - Test Bits

There is a set of (extended register) instructions which can combine a zero-extend, op or sign-extend, op:

• add, adds - Add
• sub, subs - Subtract
• cmp - Compare
• cmn - Compare Negative

There is a set of (carry) instructions which can utilize the carry from a previous operation:

• adc, adcs - Add with carry
• sbc, sbcs - Subtract with carry
• ngc, ngcs - Negate with carry

There are the multiply integer instructions which can combine an op, mul:

• madd - Multiply-add
• msub - Multiply-subtract
• mneg - Multiply-negate

There are then some long multiply instructions which can return a product twice the size of the inputs (i32 * i32 = i64 or similar):

• smull, umull - Multiply long
• smaddl, umaddl - Multiply-add long
• smsubl, umsubl - Multiply-subtract long
• smnegl, umnegl - Multiply-negate long

Finally there is the "multiply high" instructions which can return just the upper bits of a wide multiply:

• smulh, umulh - Multiply High

There may be other interesting instructions as well, but these are ones that may have broader usage/application and which likely be good to validate we are covering

Author:	tannergooding
Assignees:	-
Labels:	arch-arm64, area-CodeGen-coreclr, untriaged
Milestone:	-

[TIHan]

These look like really good optimization opportunities.

[JulieLeeMSFT]

Thanks @tannergooding for compiling all these cases. Let me put this in the future item.

[a74nh]

@tannergooding and @kunalspathak : is there anyone looking at the remaining instructions? If not, then this could be a good set of items for @SwapnilGaikwad to work through.

While doing this, it's probably worth adding some DisasmCheck tests for them too.

[kunalspathak]

@TIHan - are you planning to work on any of these?

[kunalspathak]

this could be a good set of items for @SwapnilGaikwad to work through.

Sounds good to me.

[a74nh]

MNEG support: #79550

[kunalspathak]

@a74nh - Are there more items that you or @SwapnilGaikwad will be working on?

[SwapnilGaikwad]

Hi @kunalspathak, we plan to look at the extended register instruction combinations next (add, adds, sub, subs, cmp and cmn).

[kunalspathak]

Hi @kunalspathak, we plan to look at the extended register instruction combinations next (add, adds, sub, subs, cmp and cmn).

Sounds good.

[kunalspathak]

@TIHan - Could you please update the issue description on which instructions are you planning to work on? It will help @SwapnilGaikwad to pick some other instructions to optimize.

[snickolls-arm]

We should be able to tick off ADD/ADDS/SUB/SUBS (extended register) as they were included in #76273. The JIT is generating these correctly for additions with byte and short.

Looking at the (carry) set, it's not obvious which patterns they might be useful for as it's rare to need to carry on 64-bit. They would be useful for Int128 acceleration but this may be better as it's own issue, as it's a wider scope than just the JIT.

runtime/src/libraries/System.Private.CoreLib/src/System/Int128.cs

Line 692 in 1d1bf92

public static Int128 operator +(Int128 left, Int128 right)

[a74nh]

Looking at the (carry) set, it's not obvious which patterns they might be useful for as it's rare to need to carry on 64-bit. They would be useful for Int128 acceleration but this may be better as it's own issue, as it's a wider scope than just the JIT.

Agreed. This issue was intended for general codegen opportunities from the IR. Intrinsifying Int128.cs feels like it falls outside the scope.

For this issue, if there's are no opportunities to lower general IR to the carry instructions, then we should consider those complete. (We could lower the Int128 + method to an add carry, but it'd require matching 6+ nodes, then a heavy graph rewrite, which isn't really practical)

[tannergooding]

There are several general patterns that can be applicable to generate carry/borrow instructions and while Int128 is a primary case, it also applies to cases like BigInteger or various user defined types.

One common general pattern for an add; add with carry is:

T lower = left._lower + right._lower;
T carry = (lower < left._lower) ? 1: 0;
T upper = left._upper + right._upper + carry;

and for sub; sub with borrow:

T lower = left._lower - right._lower;
T borrow = (lower > left._lower) ? 1 : 0;
T upper = left._upper - right._upper - borrow;

Noting that this assumes an unsigned comparison in computing the carry/borrow but is the correct algorithm for both signed and unsigned integers. The same general pattern can also apply to overflow checking and so would be applicable for add; jump if unsigned overflow or similar.

The pattern for detecting signed overflow for addition (rather than simply computing if a carry is needed; that is doing add; jump if signed overflow) is a bit more complex, but roughly boils down to:

T result = left + right;

if ((left._upper ^ right._upper) >= 0) // signs of inputs match
{
    if ((result._upper ^ left._upper) < 0) // signs of inputs don't match the output
    {
        // overflow!
    }
}

This can be simplified down to a single compare as: (result._upper & ~(left._upper ^ right._upper)) < 0; which works because matching signs produce 0, while mismatching signs produce 1. We negate that then bitwise and it with the result sign. This gives us "false" for anything with mismatched signs or with matching signs for the inputs and the result.

Signed overflow for subtraction is similar, but doing (leftSign != rightSign) && (leftSign != resultSign)

[a74nh]

There are several general patterns that can be applicable to generate carry/borrow instructions

Agreed with the patterns shown. However, it's still a few nodes that need matching. Do you think it's suitable to do in the lowering phase?

[tannergooding]

Starting in lowering is probably a fine approach, but we should consider whether such patterns are likely to be broken by things like morph or cse due to the shape and higher expense they appear to have by the more complex IR. It might turn out to be better to recognize and transform it earlier instead, such as to use some dedicated node to help ensure it all flows smoothly.