[ARM]: Add optimized NEON uint64x2_t multiply routine.

[easyaspi314]

Summary

Patch to fix bug 39967

There are a few further optimizations that can be made, but this is many times better than scalarizing.

These take up to 11 cycles, however, the smallest possible case is 7 with two pre-interleaved values, or 4 if we are using a single vmull.

This automatically tries to select the proper routine.

twomul is used for multiplies that could not be simplified. It takes 7 instructions and 11 cycles. It looks like so:

vmovn.i64 topLo, top
vmovn.i64 botLo, bot
vrev64.32 bot, bot

vmul.i32 bot, bot, top
vpaddl.i32 bot, bot
vshl.i64 top, bot, #32
vmlal.u32 top, botLo, topLo

ssemul is simpler, clearer, and more modular. It has the same timing as twomul, but it has one more instruction.

However, if something is simplified, such as preinterleaving a load/constant or removing multiplies on bits that are known to be zero, ssemul ends up being faster and shorter.

vmovn.i64 topLo, top
vshrn.i64 topHi, top, #32
vmovn.i64 botHi, bot
vshrn.i64 botLo, bot, #32 

vmull.u32 ret, topLo, botHi
vmlal.u32 ret, topHi, botLo
vshl.i64  ret, ret, #32 
vmlal.u32 ret, topLo, botLo

Some missing optimizations:

1. Masking a uint64x2_t/v2i64 by 0xFFFFFFFF shouldn't actually generate a vand, it should remove one multiply and one vshrn.
2. Constant interleaving is put into two vldr instructions. This might not be the most efficient, as I want a vld1.64 I don't know how adr comes into play, but I think it could be run in parallel with shifting on the other multiple.
3. Load interleaving should be implemented. If a multiple is used only once and it is loaded from a pointer, by replacing vld1.64 with vld2.32 and using the two uint32x2_t/v2i32 values generated, we can also avoid vshrn/vmovn.
4. Cost model is pretty weird with v2i64 in NEON. We should probably fix the "add 4 to the cost" hack, as NEON v2i64 vectors are not as expensive as they are made out to be with that huge penalty.

[easyaspi314]

lib/Target/ARM/ARMISelLowering.cpp

7485 ↗

(On Diff #179602)

Can someone help me here? I can't figure this one out.

[easyaspi314]

Actually, further optimizations can be done later. At the very least, this is usable. I still left the notes for someone who wants to implement them later, but I think that at least, for now, it is far better than it was.

I don't know who I should put for a reviewer, but I think it is ready for review.

[easyaspi314]

*facepalms* Wow, I am an idiot.

Note to self: Check your PWD before running svn diff.

[efriedma]

Please upload patches with full context (see https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface).

lib/Target/ARM/ARMISelLowering.cpp

7465 ↗

(On Diff #179672)

Alternatively, we could try to handle simplifications by adding a DAGCombine for VSHRu and VMULLu nodes with constant operands, instead of trying to avoid emitting them. The end result is roughly the same (it's probably unlikely to construct a trivial VSHRu or VMULLu any other way), but it might be easier to understand. But I guess it would get tricky if we tried to emit the form using "vrev64". Probably okay as-is.

Needs more test coverage for various cases where the upper/lower half an operand is zero.

lib/Target/ARM/ARMTargetTransformInfo.cpp

528 ↗

(On Diff #179672)

Did you really mean UMULO (llvm.umul.with.overflow)? I mean, I guess it's theoretically possible to implement, but I think we'll just scalarize it at the moment.

(The cost model changes need test coverage in test/Analysis/CostModel/ARM/ .)

test/CodeGen/ARM/vmul.ll

69 ↗

(On Diff #179672)

DAGCombine should be able to catch the redundant AND... but it looks like DAGCombiner::visitTRUNCATE doesn't try to handle demanded bits for vectors. (I guess it didn't get updated when other operations got support for vector operands?)

[craig.topper]

test/CodeGen/ARM/vmul.ll

69 ↗

(On Diff #179672)

PR39689 mentions this is disabled for vectors. Maybe @RKSimon or @spatel are working on it?

[easyaspi314]

I am going to add constant interleaving, more tests, and call it done. I think that twomul and interleaved loads are much smaller and lower priority optimizations, and something I am not comfortable enough to do myself.

lib/Target/ARM/ARMISelLowering.cpp

7465 ↗

(On Diff #179672)

This is the exact same method used in X86ISelLowering.cpp/LowerMUL, except for the early return to work around missing optimizations later on.

If we use the twomul/vrev64 version, we would only use it if none of them are zero and none could be pre-interleaved. Once things get interleaved and/or we eliminate one of the multiplies, we lose the benefit.

lib/Target/ARM/ARMTargetTransformInfo.cpp

528 ↗

(On Diff #179672)

Oh yeah, I did that wrong. Should be normal multiply.

test/CodeGen/ARM/vmul.ll

69 ↗

(On Diff #179672)

That would explain why it was choking on this when X86 does not.

[easyaspi314]

Fixed cost model and added cost model tests. I also made a larger diff.

I can't figure out the constant interleaving, as I can't seem to figure out how to detect a literal vector. Everything I tried returned false. I don't want to spend too much time on it. If any of you want to finish it, go ahead. It is still better than what it was.

[easyaspi314]

I figured things out and I am on track to adding twomul and constant interleaving.

[easyaspi314]

This is what I have now. Constant swapping and twomul is now implemented, and I will update the patch once I finish the documentation and tests, as well as double-check the return values on my phone.

typedef unsigned long long v2i64 __attribute__((vector_size(16)));

v2i64 mult(v2i64 v1, v2i64 v2) {
  return v1 * v2;
}

v2i64 mult_lo(v2i64 v1, v2i64 v2) {
  return (v1 & 0xFFFFFFFF) * (v2 & 0xFFFFFFFF);
}

v2i64 mult_lo_lohi(v2i64 v1, v2i64 v2) {
  return (v1 & 0xFFFFFFFF) * v2;
}

v2i64 mult_constant(v2i64 v1) {
  return 1234567889904ULL * v1;
}

v2i64 mult_lo_constant(v2i64 v1) {
  return v1 * 1234ULL;
}

mult:
	vmov	d17, r2, r3
	mov	r12, sp
	vmov	d16, r0, r1
	vld1.64	{d18, d19}, [r12]
	vrev64.32	q10, q8
	vmovn.i64	d16, q8
	vmovn.i64	d17, q9
	vmul.i32	q10, q10, q9
	vpaddl.u32	q10, q10
	vshl.i64	q9, q10, #32
	vmlal.u32	q9, d17, d16
	vmov	r0, r1, d18
	vmov	r2, r3, d19
	bx	lr

mult_lo:
	vmov	d19, r2, r3
	vmov.i64	q8, #0xffffffff
	vmov	d18, r0, r1
	mov	r0, sp
	vand	q9, q9, q8
	vld1.64	{d20, d21}, [r0]
	vand	q8, q10, q8
	vmovn.i64	d18, q9
	vmovn.i64	d16, q8
	vmull.u32	q8, d16, d18
	vmov	r0, r1, d16
	vmov	r2, r3, d17
	bx	lr

mult_lo_lohi:
	vmov	d19, r2, r3
	vmov.i64	q8, #0xffffffff
	vmov	d18, r0, r1
	mov	r0, sp
	vld1.64	{d20, d21}, [r0]
	vand	q8, q9, q8
	vshrn.i64	d18, q10, #32
	vmovn.i64	d16, q8
	vmovn.i64	d17, q10
	vmull.u32	q9, d16, d18
	vshl.i64	q9, q9, #32
	vmlal.u32	q9, d16, d17
	vmov	r0, r1, d18
	vmov	r2, r3, d19
	bx	lr

mult_constant:
	adr	r12, .LCPI3_0
	vmov	d17, r2, r3
	vld1.64	{d18, d19}, [r12:128]
	vmov	d16, r0, r1
	vmul.i32	q9, q8, q9
	vldr	d20, .LCPI3_1
	vmovn.i64	d16, q8
	vpaddl.u32	q9, q9
	vshl.i64	q9, q9, #32
	vmlal.u32	q9, d16, d20
	vmov	r0, r1, d18
	vmov	r2, r3, d19
	bx	lr
.LCPI3_0:
	.long	1912275952
	.long	1912275952
	.long	287
	.long	287
.LCPI3_1:
	.long	1912275952
	.long	1912275952

mult_lo_constant:
        vmov    d17, r2, r3
        vldr    d18, .LCPI4_0
        vmov    d16, r0, r1
        vshrn.i64       d19, q8, #32
        vmovn.i64       d16, q8
        vmull.u32       q10, d19, d18
        vshl.i64        q10, q10, #32
        vmlal.u32       q10, d16, d18
        vmov    r0, r1, d20
        vmov    r2, r3, d21
        bx      lr
.LCPI4_0:
        .long   1234
        .long   1234

If someone can optimize that redundant load in mult_constant, I would appreciate it.

This is the code I want:

mult_constant:
	adr	r12, .LCPI3_0
	vmov	d17, r2, r3
	vld1.64	{d22, d23}, [r12:128]
	vmov	d16, r0, r1
	vmul.i32	q9, q8, q11
	vmovn.i64	d16, q8
	vpaddl.u32	q9, q9
	vshl.i64	q9, q9, #32
	vmlal.u32	q9, d16, d22
	vmov	r0, r1, d18
	vmov	r2, r3, d19
	bx	lr
.LCPI3_0:
	.long	1912275952
	.long	1912275952
	.long	287
	.long	287

[easyaspi314]

Oops, that's not right. mult_constant isn't matching.

I think I am going to fall back to ssemul for all constants like I originally planned.

[easyaspi314]

vmul.i32 Qd,Qn,Qm actually takes 4 cycles, which means twomul has the same timing as ssemul, 11 cycles.
@efriedma that explains why twomul wasn't visibly faster in my tests.

However, twomul saves an instruction, so I am keeping it.

twomul:
	vrev64.32	q10, q8        @ 1 cycle,  total 1
	vmovn.i64	d16, q8        @ 1 cycle,  total 2
	vmovn.i64	d17, q9        @ 1 cycle,  total 3
	vmul.i32	q10, q10, q9   @ 4 cycles, total 7
	vpaddl.u32	q10, q10       @ 1 cycle,  total 8
	vshl.i64	q9, q10, #32   @ 1 cycle,  total 9
	vmlal.u32	q9, d17, d16   @ 2 cycles, total 11

ssemul:
	vshrn.i64       d20, q8, #32   @ 1 cycle,  total 1
	vmovn.i64       d16, q8        @ 1 cycle,  total 2
	vmovn.i64       d21, q9        @ 1 cycle,  total 3
	vmull.u32       q11, d21, d20  @ 2 cycles, total 5
	vshrn.i64       d17, q9, #32   @ 1 cycle,  total 6
	vmlal.u32       q11, d17, d16  @ 2 cycles, total 8
	vshl.i64        q9, q11, #32   @ 1 cycle,  total 9
	vmlal.u32       q9, d21, d16   @ 2 cycles, total 11

[easyaspi314]

Ok, done. I fixed twomul and constant interleaving, and added a couple more tests.

I also lowered the cost for multiplication to be in relation to normal mul i64, which makes it so LLVM will properly autovectorize it.

[RKSimon]

test/Analysis/CostModel/ARM/mult.ll

1 ↗

(On Diff #180192)

You might find the utils\update_analyze_test_checks.py script useful to make this more maintainable - see X86\arith.ll for examples.

test/CodeGen/ARM/vmul.ll

40 ↗

(On Diff #180192)

Please add these new tests to trunk with current codegen now then rebase this patch so it shows the changes to codegen.

69 ↗

(On Diff #179672)

PR39689 mentions this is disabled for vectors. Maybe @RKSimon or @spatel are working on it?

I've been putting it off as there's a load of yak shaving to be done for it - but I will look again.

[easyaspi314]

v2i64 mul5(v2i64 val)
{
    return val * 5;
}

mul5:
    vmov    d17, r2, r3
    vmov    d16, r0, r1
    vmov.i32    d18, #0x5
    vshrn.i64   d19, q8, #32
    vmovn.i64   d16, q8
    vmull.u32   q10, d19, d18
    vshl.i64    q10, q10, #32
    vmlal.u32   q10, d16, d18
    vmov    r0, r1, d20
    vmov    r2, r3, d21
    bx  lr

Ummmmmm…that should DEFINITELY be a shift+add. That would be much cheaper.

The cost model is definitely messed up…nope, something else. I set the multiply cost to 80000, and it still chose it over shifts!

mul5:
    movdqa  xmm1, xmmword ptr [rip + LCPI0_0]
    movdqa  xmm2, xmm0
    pmuludq xmm2, xmm1
    psrlq   xmm0, 32
    pmuludq xmm0, xmm1
    psllq   xmm0, 32
    paddq   xmm0, xmm2
    ret

What?! We should be shifting + adding here too! Are we just not doing shift + adds for vectors?

What the heck?

test/Analysis/CostModel/ARM/mult.ll

1 ↗

(On Diff #180192)

Ok, will take a look at that.

test/CodeGen/ARM/vmul.ll

40 ↗

(On Diff #180192)

Okay, I will try to do that.

I just run svn update, right? I don't know why I chose SVN.

[easyaspi314]

Updated tests with the generation tools, changed multiply cost to 8.

Each time I was about to submit it I got distracted and had to update and build again. ¯\_(ツ)_/¯

[RKSimon]

@easyaspi314 What happened with this?

Target/ARM/ARMISelLowering.cpp

 
 static SDValue LowerMUL(SDValue Op, SelectionDAG &DAG) {
   // Multiplications are only custom-lowered for 128-bit vectors so that
-  // VMULL can be detected.  Otherwise v2i64 multiplications are not legal.
+  // VMULL can be detected.
   EVT VT = Op.getValueType();
   assert(VT.is128BitVector() && VT.isInteger() &&
          "unexpected type for custom-lowering ISD::MUL");

     }
 
     if (!NewOpc) {
-      if (VT == MVT::v2i64)
-        // Fall through to expand this.  It is not legal.
-        return SDValue();
-      else
+      if (VT == MVT::v2i64) {
+        // One optimal way of doing an i64x2 is the same way as for SSE:
+        //    vshrn.i64  topHi, top, #32      @ v2i32 topHi = top >> 32;
+        //    vmovn.i64  topLo, top           @ v2i32 topLo = top & 0xFFFFFFFF;
+        //    vshrn.i64  botHi, bot, #32      @ v2i32 botHi = bot >> 32;
+        //    vmovn.i64  botLo, bot           @ v2i32 botLo = bot & 0xFFFFFFFF;
+        //    vmull.u32  ret64, topHi, botLo  @ v2i64 ret64 = (v2i64)topHi * (v2i64)botLo;
+        //    vmlal.u64  ret64, topLo, botHi  @ ret64 += (v2i64)topLo * (v2i64)botHi;
+        //    vshl.i64   ret64, ret64, #32    @ ret64 <<= 32;
+        //    vmlal.u32  ret64, topLo, botLo  @ ret64 += (v2i64)topLo * (v2i64)botLo;
+        // TODO: Implement the faster but less modular way, which is this:
+        //    vmovn.i64  topLo, top           @ v2i64 topLo = top & 0xFFFFFFFF;
+        //    vmovn.i64  botLo, bot           @ v2i64 botLo = bot & 0xFFFFFFFF;
+        //                                    @ v4i32 bot32 = (v4i32)bot;
+        //    vrev64.32  botRe, bot           @ v4i32 botRe = (v4i32) {
+        //                                    @     bot32[1], bot32[0],
+        //                                    @     bot32[3], bot32[2]
+        //                                    @ };
+        //    vmul.i32   botRe, botRe, top    @ botRe *= (v4i32)top;
+        //    vpaddl.u32 botRe, botRe         @ top = (v2i64) {
+        //                                    @     (u64)botRe[0] + (u64)botRe[1],
+        //                                    @     (u64)botRe[2] + (u64)botRe[3]
+        //                                    @ }
+        //    vshl.i64   top,   botRe, #32    @ top <<= 32;
+        //    vmlal.u32  top,   topLo, botLo  @ top += (v2i64)topLo * (v2i64)botLo;
+        // Also, ideally, make it so optimizations can interleave one or more
+        // loads as a uint32x2x2_t for the first variant to avoid vshrn/vmovn
+        // like so:
+        //    vld2.32    {topLo,topHi} [topPtr]
+        //    vld2.32    {botLo,botHi} [botPtr]
+        //    vmull.u32  ret64, topHi, botLo
+        //    vmlal.u64  ret64, topLo, botHi
+        //    vshl.i64   ret64, ret64, #32
+        //    vmlal.u32  ret64, topLo, botLo
+        // This optimization only works if the pointer hasn't been loaded and is
+        // only used for the multiply, as swapping back removes the benefit.
+        // Also, (top & 0xFFFFFFFF) * (bot & 0xFFFFFFFF) should not generate a
+        // mask.
+        SDLoc DL(Op);
+        SDValue top = Op.getOperand(0);
+        SDValue bot = Op.getOperand(1);
+        KnownBits topKnown = DAG.computeKnownBits(top);
+        KnownBits botKnown = DAG.computeKnownBits(bot);
+
+        APInt LowerBitsMask = APInt::getLowBitsSet(64, 32);
+        bool topLoIsZero = LowerBitsMask.isSubsetOf(topKnown.Zero);
+        bool botLoIsZero = LowerBitsMask.isSubsetOf(botKnown.Zero);
+
+        APInt UpperBitsMask = APInt::getHighBitsSet(64, 32);
+        bool topHiIsZero = UpperBitsMask.isSubsetOf(topKnown.Zero);
+        bool botHiIsZero = UpperBitsMask.isSubsetOf(botKnown.Zero);
+        SDValue topLo = DAG.getNode(ISD::TRUNCATE, DL, MVT::v2i32, top);
+        SDValue botLo = DAG.getNode(ISD::TRUNCATE, DL, MVT::v2i32, bot);
+
+        SDValue c32 = DAG.getConstant(32, DL, MVT::i32);
+        SDValue Zero = DAG.getConstant(0, DL, VT);
+
+        SDValue topLoBotLo = Zero;
+        if (!topLoIsZero && !botLoIsZero)
+          topLoBotLo = DAG.getNode(ARMISD::VMULLu, DL, VT, topLo, botLo);
+
+        // Don't go any further if we are only multiplying low bits.
+        if (topHiIsZero && botHiIsZero)
+          return topLoBotLo;
+
+        SDValue topLoBotHi = Zero;
+        if (!topLoIsZero && !botHiIsZero) {
+          SDValue botHi =
+              DAG.getNode(ISD::TRUNCATE, DL, MVT::v2i32,
+                          DAG.getNode(ARMISD::VSHRu, DL, VT, bot, c32));
+          topLoBotHi = DAG.getNode(ARMISD::VMULLu, DL, VT, topLo, botHi);
+        }
+        SDValue topHiBotLo = Zero;
+        if (!topHiIsZero && !botLoIsZero) {
+          SDValue topHi =
+              DAG.getNode(ISD::TRUNCATE, DL, MVT::v2i32,
+                          DAG.getNode(ARMISD::VSHRu, DL, VT, top, c32));
+          topHiBotLo = DAG.getNode(ARMISD::VMULLu, DL, VT, topHi, botLo);
+        }
+
+        // (optimized to vmlal.u32)
+        SDValue Hi = DAG.getNode(ISD::ADD, DL, VT, topLoBotHi, topHiBotLo);
+        Hi = DAG.getNode(ARMISD::VSHL, DL, VT, Hi, c32);
+        // (optimized to vmlal.u32)
+        return DAG.getNode(ISD::ADD, DL, VT, topLoBotLo, Hi);
+      } else
         // Other vector multiplications are legal.
         return Op;
     }

Target/ARM/ARMTargetTransformInfo.cpp

     { ISD::SREM, MVT::v16i8, 16 * FunctionCallDivCost},
     { ISD::UREM, MVT::v16i8, 16 * FunctionCallDivCost},
     // Multiplication.
+    // TODO: Are these correct?
+    { ISD::UMULO, MVT::v2i64, 11},
+    { ISD::SMULO, MVT::v2i64, 11},
   };
 
   if (ST->hasNEON())