[ARM] Optimize {s|u}mul.with.overflow.

[jgalenson]

Summary

This extends my previous patches to also optimize overflow-checked multiplies during SelectionDAG.

[rogfer01]

lib/Target/ARM/ARMISelLowering.cpp

3955

What about

// We generate a SMUL_LOHI and then check if all the bits of the high word
// are the same as the sign bit of the low word.

4479

I think this comment should be updated after this change.

4527

I think this comment should be updated after this change.

test/CodeGen/ARM/su-addsub-overflow.ll

80

Looks like we are overloading a bit the name of this test file. Perhaps add a new testfile su-mul-overflow.ll instead?

[jgalenson]

lib/Target/ARM/ARMISelLowering.cpp

3955

That's definitely better. Thanks!

4479

Good catch!

test/CodeGen/ARM/su-addsub-overflow.ll

80

Good point. I think I prefer having them all in the same file since they're testing the same sort of things, so I'll rename the file. But I can certainly split it if you think that's best.

[jgalenson]

Update comments and rename test file.

[rogfer01]

LGTM. Please wait a couple of days before submitting just in case @efriedma has further comments.

[alexcrichton]

FWIW https://bugs.llvm.org/show_bug.cgi?id=37382 was bisected back to this revision which has shown up when we upgraded LLVM in the Rust project

[rogfer01]

Thanks @alexcrichton . I cannot login to bugzilla yet (I'd reply there instead, hope I can soon). Looks like {S,U}MUL_LOHI are expanded in Thumb1 so a stop-gap approach could be not implementing this optimisation in that subtarget.

[jgalenson]

Sorry for the trouble. I see it's been fixed now.

[alexcrichton]

Oh no worries at all, thanks!

lib/Target/ARM/ARMISelLowering.cpp

case ISD::SSUBO:
     Value = DAG.getNode(ISD::SUB, dl, Op.getValueType(), LHS, RHS);
     OverflowCmp = DAG.getNode(ARMISD::CMP, dl, MVT::Glue, LHS, RHS);
     break;
   case ISD::USUBO:
     ARMcc = DAG.getConstant(ARMCC::HS, dl, MVT::i32);
     Value = DAG.getNode(ISD::SUB, dl, Op.getValueType(), LHS, RHS);
     OverflowCmp = DAG.getNode(ARMISD::CMP, dl, MVT::Glue, LHS, RHS);
     break;
+  case ISD::UMULO:
+    // We generate a UMUL_LOHI and then check if the high word is 0.
+    ARMcc = DAG.getConstant(ARMCC::EQ, dl, MVT::i32);
+    Value = DAG.getNode(ISD::UMUL_LOHI, dl,
+                        DAG.getVTList(Op.getValueType(), Op.getValueType()),
+                        LHS, RHS);
+    OverflowCmp = DAG.getNode(ARMISD::CMP, dl, MVT::Glue, Value.getValue(1),
+                              DAG.getConstant(0, dl, MVT::i32));
+    Value = Value.getValue(0); // We only want the low 32 bits for the result.
+    break;
+  case ISD::SMULO:
+    // We generate a SMUL_LOHI and then check if the high word is 0 or
+    // 0xffffffff.
+    ARMcc = DAG.getConstant(ARMCC::EQ, dl, MVT::i32);
+    Value = DAG.getNode(ISD::SMUL_LOHI, dl,
+                        DAG.getVTList(Op.getValueType(), Op.getValueType()),
+                        LHS, RHS);
+    OverflowCmp = DAG.getNode(ARMISD::CMP, dl, MVT::Glue, Value.getValue(1),
+                              DAG.getNode(ISD::SRA, dl, Op.getValueType(),
+                                          Value.getValue(0),
+                                          DAG.getConstant(31, dl, MVT::i32)));
+    Value = Value.getValue(0); // We only want the low 32 bits for the result.
+    break;
   } // switch (...)
 
   return std::make_pair(Value, OverflowCmp);
 }
 
 SDValue
 ARMTargetLowering::LowerXALUO(SDValue Op, SelectionDAG &DAG) const {
   // Let legalize expand this if it isn't a legal type yet.

 }
 
 SDValue ARMTargetLowering::LowerBRCOND(SDValue Op, SelectionDAG &DAG) const {
   SDValue Chain = Op.getOperand(0);
   SDValue Cond = Op.getOperand(1);
   SDValue Dest = Op.getOperand(2);
   SDLoc dl(Op);
 
   // Optimize {s|u}{add|sub}.with.overflow feeding into a branch instruction.
   unsigned Opc = Cond.getOpcode();
-  if (Cond.getResNo() == 1 && (Opc == ISD::SADDO || Opc == ISD::UADDO ||
-                               Opc == ISD::SSUBO || Opc == ISD::USUBO)) {
+  if (Cond.getResNo() == 1 &&
+      (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
+       Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO)) {
     // Only lower legal XALUO ops.
     if (!DAG.getTargetLoweringInfo().isTypeLegal(Cond->getValueType(0)))
       return SDValue();
 
     // The actual operation with overflow check.
     SDValue Value, OverflowCmp;
     SDValue ARMcc;
     std::tie(Value, OverflowCmp) = getARMXALUOOp(Cond, DAG, ARMcc);
if (Subtarget->isFPOnlySP() && LHS.getValueType() == MVT::f64) {
     // If softenSetCCOperands only returned one value, we should compare it to
     // zero.
     if (!RHS.getNode()) {
       RHS = DAG.getConstant(0, dl, LHS.getValueType());
       CC = ISD::SETNE;
     }
   }
 
   // Optimize {s|u}{add|sub}.with.overflow feeding into a branch instruction.
   unsigned Opc = LHS.getOpcode();
   if (LHS.getResNo() == 1 && (isOneConstant(RHS) || isNullConstant(RHS)) &&
       (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
-       Opc == ISD::USUBO) && (CC == ISD::SETEQ || CC == ISD::SETNE)) {
+       Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO) &&
+      (CC == ISD::SETEQ || CC == ISD::SETNE)) {
     // Only lower legal XALUO ops.
     if (!DAG.getTargetLoweringInfo().isTypeLegal(LHS->getValueType(0)))
       return SDValue();
 
     // The actual operation with overflow check.
     SDValue Value, OverflowCmp;
     SDValue ARMcc;
     std::tie(Value, OverflowCmp) = getARMXALUOOp(LHS.getValue(0), DAG, ARMcc);

test/CodeGen/ARM/su-addsub-overflow.ll

trap:
   unreachable
 
 cont:
   %2 = extractvalue { i32, i1 } %0, 0
   ret i32 %2
 
 }
 
+define i32 @smul(i32 %a, i32 %b) local_unnamed_addr #0 {
+; CHECK-LABEL: smul:
+; CHECK: smull r0, r[[RHI:[0-9]+]], {{r[0-9]+}}, {{r[0-9]+}}
+; CHECK-NEXT: cmp r[[RHI]], r0, asr #31
+; CHECK-NEXT: moveq pc, lr
+entry:
+  %0 = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %a, i32 %b)
+  %1 = extractvalue { i32, i1 } %0, 1
+  br i1 %1, label %trap, label %cont
+
+trap:
+  tail call void @llvm.trap() #2
+  unreachable
+
+cont:
+  %2 = extractvalue { i32, i1 } %0, 0
+  ret i32 %2
+}
+
+define i32 @umul(i32 %a, i32 %b) local_unnamed_addr #0 {
+; CHECK-LABEL: umul:
+; CHECK: umull r0, r[[RHI:[0-9]+]], {{r[0-9]+}}, {{r[0-9]+}}
+; CHECK-NEXT: cmp r[[RHI]], #0
+; CHECK-NEXT: moveq pc, lr
+entry:
+  %0 = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %a, i32 %b)
+  %1 = extractvalue { i32, i1 } %0, 1
+  br i1 %1, label %trap, label %cont
+
+trap:
+  tail call void @llvm.trap() #2
+  unreachable
+
+cont:
+  %2 = extractvalue { i32, i1 } %0, 0
+  ret i32 %2
+}
+
 define void @sum(i32* %a, i32* %b, i32 %n) local_unnamed_addr #0 {
 ; CHECK-LABEL: sum:
 ; CHECK:    ldr [[R0:r[0-9]+]],
 ; CHECK-NEXT:    ldr [[R1:r[0-9]+|lr]],
 ; CHECK-NEXT:    adds [[R2:r[0-9]+]], [[R1]], [[R0]]
 ; CHECK-NEXT:    strvc [[R2]],
 ; CHECK-NEXT:    addsvc
 ; CHECK-NEXT:    bvs

 
 declare void @external_fn(...) local_unnamed_addr #0
 
 declare void @llvm.trap() #2
 declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) #1
+declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32) #1