[AArch64] Improve codegen for inverted overflow checking intrinsics

[aemerson]

Summary

[AArch64] Improve codegen for inverted overflow checking intrinsics.

E.g. if we have a (xor(overflow-bit), 1) where overflow-bit comes from an intrinsic like llvm.sadd.with.overflow then we can kill the xor and use the inverted condition code for the CSEL.

rdar://28495949

[aemerson]

Ping.

[kristof.beyls]

lib/Target/AArch64/AArch64ISelLowering.cpp

1980–2012 ↗

(On Diff #116289)

Hi Amara,

I'm only vaguely familiar with this area of the code base.
My understanding is that you're aiming to have one more pattern apply involving an xor node.
I think it'd be nice to write out the pattern in a comment just like is available for the pattern matched in the existing code in LowerXOR.

Apart from that, with my unfamiliarity of this code base, I wonder why this pattern matching optimization is done during lowering.
Are there good reasons this optimization isn't done elsewhere, e.g. described by a tablegen pattern or during DAGCombine (e.g. in performXorCombine in this same source file)?
Apologies if the answer is blatantly obvious to people more experienced in this area.

Thanks,

Kristof

[javed.absar]

lib/Target/AArch64/AArch64ISelLowering.cpp

1987 ↗

(On Diff #116289)

Perhaps the COp1 test should be first test for efficiency e.g.

if (ConstantSDNode *OtherIsConst = dyn_cast<ConstantSDNode>(Other) ) {

if (....) {
  ...
}

}

COp1 => OtherIsConst

[aemerson]

lib/Target/AArch64/AArch64ISelLowering.cpp

1980–2012 ↗

(On Diff #116289)

Thanks for taking a look. This is part of lowering because I want to re-use the code for detecting the overflow arithmetic nodes in getAArch64XALUOOp(). That helper function is used to recognize the patterns in a few other places like LowerBR_CC and LowerSelect for example. If we leave this combine until later we can't re-use that as the pattern is destroyed.

I'll improve the comment to better explain the transformation.

1987 ↗

(On Diff #116289)

I'd prefer not to have nested if statements as that makes the rest of the block cramped. I have noticed however that isOneConstant() can be used instead, I'll use that and move it earlier in the condition.

[kristof.beyls]

lib/Target/AArch64/AArch64ISelLowering.cpp

1980–2012 ↗

(On Diff #116289)

Thanks Amara, that makes sense to me.
Now that I've looked at getAArch64XALUOOp() and where it's used, I couldn't help but notice that almost everywhere it's used, the same boiler-plate kind-of code is present around it:

if (Sel.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(LHS->getValueType(0)))
      return SDValue();
...
    AArch64CC::CondCode OFCC;
    SDValue Value, Overflow;
    std::tie(Value, Overflow) = getAArch64XALUOOp(OFCC, CCVal.getValue(0), DAG);
    SDValue CCVal = DAG.getConstant(OFCC, DL, MVT::i32);
...
  return DAG.getNode(AArch64ISD::CSEL, DL, Op.getValueType(), TVal, FVal,
                   CCVal, Overflow);
}

Couldn't that code be factored out somehow instead of having it copy pasted a few times?
I think that could improve the readability of the code and result in the advantages that the DRY-principle brings.

[aemerson]

lib/Target/AArch64/AArch64ISelLowering.cpp

1980–2012 ↗

(On Diff #116289)

Yeah, I think this is a borderline case. There's not a way I can see that can factor things out in a nice way due to the differences in the initial if-condition as well as how the AArch64 CC is mutated in two of the cases (while maintaining readability). I can split out the Opc checks though as they're the same in all cases?

[kristof.beyls]

lib/Target/AArch64/AArch64ISelLowering.cpp

1980–2012 ↗

(On Diff #116289)

Right.
I hope factoring out something like

bool matchesLegalSuAddSubMulWithOverflow(SDValue Op, SelectionDAG &DAG)
{
  unsigned Opc = Op.getOpcode();
  if (Op.getResNo() == 1 &&
      (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
       Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO))
    if (DAG.getTargetLoweringInfo().isTypeLegal(Op->getValueType(0)))
    return true;
  return false;
}

and using that would already reduce the copy paste a lot; and the actual logic of the code might become a bit more simple and obvious?
But it's debatable, so I'll leave the decision on whether to factor this out or not up to you.

[aemerson]

Rebased and updated diff to use a helper function for the overflow op result checks. I didn't put the type legal check into the helper because it's used to do an early exit rather than to continue onto the rest of the lower method.

[kristof.beyls]

Thanks Amara, LGTM modulo one tiny nitpick which you should feel free to disagree with.

test/CodeGen/AArch64/arm64-xaluo.ll

659–670 ↗

(On Diff #117994)

Just one more tiny remark: I think it might be slightly easier to maintain this test file if the tests you added here we be each next to the "positive" test you copy pasted it from higher up in this file. E.g. moving saddo.not.i32 come right after saddo.select.i32.

llvm/trunk/lib/Target/AArch64/AArch64ISelLowering.cpp

 }
 
 SDValue AArch64TargetLowering::LowerF128Call(SDValue Op, SelectionDAG &DAG,
                                              RTLIB::Libcall Call) const {
   SmallVector<SDValue, 2> Ops(Op->op_begin(), Op->op_end());
   return makeLibCall(DAG, Call, MVT::f128, Ops, false, SDLoc(Op)).first;
 }
 
+// Returns true if the given Op is the overflow flag result of an overflow
+// intrinsic operation.
+static bool isOverflowIntrOpRes(SDValue Op) {
+  unsigned Opc = Op.getOpcode();
+  return (Op.getResNo() == 1 &&
+          (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
+           Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO));
+}
+
 static SDValue LowerXOR(SDValue Op, SelectionDAG &DAG) {
   SDValue Sel = Op.getOperand(0);
   SDValue Other = Op.getOperand(1);
+  SDLoc dl(Sel);
 
+  // If the operand is an overflow checking operation, invert the condition
+  // code and kill the Not operation. I.e., transform:
+  // (xor (overflow_op_bool, 1))
+  //   -->
+  // (csel 1, 0, invert(cc), overflow_op_bool)
+  // ... which later gets transformed to just a cset instruction with an
+  // inverted condition code, rather than a cset + eor sequence.
+  if (isOneConstant(Other) && isOverflowIntrOpRes(Sel)) {
+    // Only lower legal XALUO ops.
+    if (!DAG.getTargetLoweringInfo().isTypeLegal(Sel->getValueType(0)))
+      return SDValue();
+
+    SDValue TVal = DAG.getConstant(1, dl, MVT::i32);
+    SDValue FVal = DAG.getConstant(0, dl, MVT::i32);
+    AArch64CC::CondCode CC;
+    SDValue Value, Overflow;
+    std::tie(Value, Overflow) = getAArch64XALUOOp(CC, Sel.getValue(0), DAG);
+    SDValue CCVal = DAG.getConstant(getInvertedCondCode(CC), dl, MVT::i32);
+    return DAG.getNode(AArch64ISD::CSEL, dl, Op.getValueType(), TVal, FVal,
+                       CCVal, Overflow);
+  }
   // If neither operand is a SELECT_CC, give up.
   if (Sel.getOpcode() != ISD::SELECT_CC)
     std::swap(Sel, Other);
   if (Sel.getOpcode() != ISD::SELECT_CC)
     return Op;
 
   // The folding we want to perform is:
   // (xor x, (select_cc a, b, cc, 0, -1) )
   //   -->
   // (csel x, (xor x, -1), cc ...)
   //
   // The latter will get matched to a CSINV instruction.
 
   ISD::CondCode CC = cast<CondCodeSDNode>(Sel.getOperand(4))->get();
   SDValue LHS = Sel.getOperand(0);
   SDValue RHS = Sel.getOperand(1);
   SDValue TVal = Sel.getOperand(2);
   SDValue FVal = Sel.getOperand(3);
-  SDLoc dl(Sel);
 
   // FIXME: This could be generalized to non-integer comparisons.
   if (LHS.getValueType() != MVT::i32 && LHS.getValueType() != MVT::i64)
     return Op;
 
   ConstantSDNode *CFVal = dyn_cast<ConstantSDNode>(FVal);
   ConstantSDNode *CTVal = dyn_cast<ConstantSDNode>(TVal);
 
if (LHS.getValueType() == MVT::f128) {
     if (!RHS.getNode()) {
       RHS = DAG.getConstant(0, dl, LHS.getValueType());
       CC = ISD::SETNE;
     }
   }
 
   // Optimize {s|u}{add|sub|mul}.with.overflow feeding into a branch
   // instruction.
-  unsigned Opc = LHS.getOpcode();
-  if (LHS.getResNo() == 1 && isOneConstant(RHS) &&
-      (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
-       Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO)) {
+  if (isOverflowIntrOpRes(LHS) && isOneConstant(RHS)) {
     assert((CC == ISD::SETEQ || CC == ISD::SETNE) &&
            "Unexpected condition code.");
     // Only lower legal XALUO ops.
     if (!DAG.getTargetLoweringInfo().isTypeLegal(LHS->getValueType(0)))
       return SDValue();
 
     // The actual operation with overflow check.
     AArch64CC::CondCode OFCC;

 
 SDValue AArch64TargetLowering::LowerSELECT(SDValue Op,
                                            SelectionDAG &DAG) const {
   SDValue CCVal = Op->getOperand(0);
   SDValue TVal = Op->getOperand(1);
   SDValue FVal = Op->getOperand(2);
   SDLoc DL(Op);
 
-  unsigned Opc = CCVal.getOpcode();
   // Optimize {s|u}{add|sub|mul}.with.overflow feeding into a select
   // instruction.
-  if (CCVal.getResNo() == 1 &&
-      (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
-       Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO)) {
+  if (isOverflowIntrOpRes(CCVal)) {
     // Only lower legal XALUO ops.
     if (!DAG.getTargetLoweringInfo().isTypeLegal(CCVal->getValueType(0)))
       return SDValue();
 
     AArch64CC::CondCode OFCC;
     SDValue Value, Overflow;
     std::tie(Value, Overflow) = getAArch64XALUOOp(OFCC, CCVal.getValue(0), DAG);
     SDValue CCVal = DAG.getConstant(OFCC, DL, MVT::i32);

llvm/trunk/test/CodeGen/AArch64/arm64-xaluo.ll

 ; CHECK:        cmn w0, w1
 ; CHECK-NEXT:   csel w0, w0, w1, vs
   %t = call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
+define i1 @saddo.not.i32(i32 %v1, i32 %v2) {
+entry:
+; CHECK-LABEL:  saddo.not.i32
+; CHECK:        cmn w0, w1
+; CHECK-NEXT:   cset w0, vc
+  %t = call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %v1, i32 %v2)
+  %obit = extractvalue {i32, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i64 @saddo.select.i64(i64 %v1, i64 %v2) {
 entry:
 ; CHECK-LABEL:  saddo.select.i64
 ; CHECK:        cmn x0, x1
 ; CHECK-NEXT:   csel x0, x0, x1, vs
   %t = call {i64, i1} @llvm.sadd.with.overflow.i64(i64 %v1, i64 %v2)
   %obit = extractvalue {i64, i1} %t, 1
   %ret = select i1 %obit, i64 %v1, i64 %v2
   ret i64 %ret
 }
 
+define i1 @saddo.not.i64(i64 %v1, i64 %v2) {
+entry:
+; CHECK-LABEL:  saddo.not.i64
+; CHECK:        cmn x0, x1
+; CHECK-NEXT:   cset w0, vc
+  %t = call {i64, i1} @llvm.sadd.with.overflow.i64(i64 %v1, i64 %v2)
+  %obit = extractvalue {i64, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i32 @uaddo.select.i32(i32 %v1, i32 %v2) {
 entry:
 ; CHECK-LABEL:  uaddo.select.i32
 ; CHECK:        cmn w0, w1
 ; CHECK-NEXT:   csel w0, w0, w1, hs
   %t = call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
+define i1 @uaddo.not.i32(i32 %v1, i32 %v2) {
+entry:
+; CHECK-LABEL:  uaddo.not.i32
+; CHECK:        cmn w0, w1
+; CHECK-NEXT:   cset w0, lo
+  %t = call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %v1, i32 %v2)
+  %obit = extractvalue {i32, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i64 @uaddo.select.i64(i64 %v1, i64 %v2) {
 entry:
 ; CHECK-LABEL:  uaddo.select.i64
 ; CHECK:        cmn x0, x1
 ; CHECK-NEXT:   csel x0, x0, x1, hs
   %t = call {i64, i1} @llvm.uadd.with.overflow.i64(i64 %v1, i64 %v2)
   %obit = extractvalue {i64, i1} %t, 1
   %ret = select i1 %obit, i64 %v1, i64 %v2
   ret i64 %ret
 }
 
+define i1 @uaddo.not.i64(i64 %v1, i64 %v2) {
+entry:
+; CHECK-LABEL:  uaddo.not.i64
+; CHECK:        cmn x0, x1
+; CHECK-NEXT:   cset w0, lo
+  %t = call {i64, i1} @llvm.uadd.with.overflow.i64(i64 %v1, i64 %v2)
+  %obit = extractvalue {i64, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i32 @ssubo.select.i32(i32 %v1, i32 %v2) {
 entry:
 ; CHECK-LABEL:  ssubo.select.i32
 ; CHECK:        cmp w0, w1
 ; CHECK-NEXT:   csel w0, w0, w1, vs
   %t = call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
+define i1 @ssubo.not.i32(i32 %v1, i32 %v2) {
+entry:
+; CHECK-LABEL:  ssubo.not.i32
+; CHECK:        cmp w0, w1
+; CHECK-NEXT:   cset w0, vc
+  %t = call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %v1, i32 %v2)
+  %obit = extractvalue {i32, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i64 @ssubo.select.i64(i64 %v1, i64 %v2) {
 entry:
 ; CHECK-LABEL:  ssubo.select.i64
 ; CHECK:        cmp x0, x1
 ; CHECK-NEXT:   csel x0, x0, x1, vs
   %t = call {i64, i1} @llvm.ssub.with.overflow.i64(i64 %v1, i64 %v2)
   %obit = extractvalue {i64, i1} %t, 1
   %ret = select i1 %obit, i64 %v1, i64 %v2
   ret i64 %ret
 }
 
+define i1 @ssub.not.i64(i64 %v1, i64 %v2) {
+entry:
+; CHECK-LABEL:  ssub.not.i64
+; CHECK:        cmp x0, x1
+; CHECK-NEXT:   cset w0, vc
+  %t = call {i64, i1} @llvm.ssub.with.overflow.i64(i64 %v1, i64 %v2)
+  %obit = extractvalue {i64, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i32 @usubo.select.i32(i32 %v1, i32 %v2) {
 entry:
 ; CHECK-LABEL:  usubo.select.i32
 ; CHECK:        cmp w0, w1
 ; CHECK-NEXT:   csel w0, w0, w1, lo
   %t = call {i32, i1} @llvm.usub.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
+define i1 @usubo.not.i32(i32 %v1, i32 %v2) {
+entry:
+; CHECK-LABEL:  usubo.not.i32
+; CHECK:        cmp w0, w1
+; CHECK-NEXT:   cset w0, hs
+  %t = call {i32, i1} @llvm.usub.with.overflow.i32(i32 %v1, i32 %v2)
+  %obit = extractvalue {i32, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i64 @usubo.select.i64(i64 %v1, i64 %v2) {
 entry:
 ; CHECK-LABEL:  usubo.select.i64
 ; CHECK:        cmp x0, x1
 ; CHECK-NEXT:   csel x0, x0, x1, lo
   %t = call {i64, i1} @llvm.usub.with.overflow.i64(i64 %v1, i64 %v2)
   %obit = extractvalue {i64, i1} %t, 1
   %ret = select i1 %obit, i64 %v1, i64 %v2
   ret i64 %ret
 }
 
+define i1 @usubo.not.i64(i64 %v1, i64 %v2) {
+entry:
+; CHECK-LABEL:  usubo.not.i64
+; CHECK:        cmp x0, x1
+; CHECK-NEXT:   cset w0, hs
+  %t = call {i64, i1} @llvm.usub.with.overflow.i64(i64 %v1, i64 %v2)
+  %obit = extractvalue {i64, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i32 @smulo.select.i32(i32 %v1, i32 %v2) {
 entry:
 ; CHECK-LABEL:  smulo.select.i32
 ; CHECK:        smull   x[[MREG:[0-9]+]], w0, w1
 ; CHECK-NEXT:   lsr     x[[SREG:[0-9]+]], x[[MREG]], #32
 ; CHECK-NEXT:   cmp     w[[SREG]], w[[MREG]], asr #31
 ; CHECK-NEXT:   csel    w0, w0, w1, ne
   %t = call {i32, i1} @llvm.smul.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
+define i1 @smulo.not.i32(i32 %v1, i32 %v2) {
+entry:
+; CHECK-LABEL:  smulo.not.i32
+; CHECK:        smull   x[[MREG:[0-9]+]], w0, w1
+; CHECK-NEXT:   lsr     x[[SREG:[0-9]+]], x[[MREG]], #32
+; CHECK-NEXT:   cmp     w[[SREG]], w[[MREG]], asr #31
+; CHECK-NEXT:   cset    w0, eq
+  %t = call {i32, i1} @llvm.smul.with.overflow.i32(i32 %v1, i32 %v2)
+  %obit = extractvalue {i32, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i64 @smulo.select.i64(i64 %v1, i64 %v2) {
 entry:
 ; CHECK-LABEL:  smulo.select.i64
 ; CHECK:        mul     [[MREG:x[0-9]+]], x0, x1
 ; CHECK-NEXT:   smulh   [[HREG:x[0-9]+]], x0, x1
 ; CHECK-NEXT:   cmp     [[HREG]], [[MREG]], asr #63
 ; CHECK-NEXT:   csel    x0, x0, x1, ne
   %t = call {i64, i1} @llvm.smul.with.overflow.i64(i64 %v1, i64 %v2)
   %obit = extractvalue {i64, i1} %t, 1
   %ret = select i1 %obit, i64 %v1, i64 %v2
   ret i64 %ret
 }
 
+define i1 @smulo.not.i64(i64 %v1, i64 %v2) {
+entry:
+; CHECK-LABEL:  smulo.not.i64
+; CHECK:        mul     [[MREG:x[0-9]+]], x0, x1
+; CHECK-NEXT:   smulh   [[HREG:x[0-9]+]], x0, x1
+; CHECK-NEXT:   cmp     [[HREG]], [[MREG]], asr #63
+; CHECK-NEXT:   cset    w0, eq
+  %t = call {i64, i1} @llvm.smul.with.overflow.i64(i64 %v1, i64 %v2)
+  %obit = extractvalue {i64, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i32 @umulo.select.i32(i32 %v1, i32 %v2) {
 entry:
 ; CHECK-LABEL:  umulo.select.i32
 ; CHECK:        umull   [[MREG:x[0-9]+]], w0, w1
 ; CHECK-NEXT:   cmp     xzr, [[MREG]], lsr #32
 ; CHECK-NEXT:   csel    w0, w0, w1, ne
   %t = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %v1, i32 %v2)
   %obit = extractvalue {i32, i1} %t, 1
   %ret = select i1 %obit, i32 %v1, i32 %v2
   ret i32 %ret
 }
 
+define i1 @umulo.not.i32(i32 %v1, i32 %v2) {
+entry:
+; CHECK-LABEL:  umulo.not.i32
+; CHECK:        umull   [[MREG:x[0-9]+]], w0, w1
+; CHECK-NEXT:   cmp     xzr, [[MREG]], lsr #32
+; CHECK-NEXT:   cset    w0, eq
+  %t = call {i32, i1} @llvm.umul.with.overflow.i32(i32 %v1, i32 %v2)
+  %obit = extractvalue {i32, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 define i64 @umulo.select.i64(i64 %v1, i64 %v2) {
 entry:
 ; CHECK-LABEL:  umulo.select.i64
 ; CHECK:        umulh   [[MREG:x[0-9]+]], x0, x1
 ; CHECK-NEXT:   cmp     xzr, [[MREG]]
 ; CHECK-NEXT:   csel    x0, x0, x1, ne
   %t = call {i64, i1} @llvm.umul.with.overflow.i64(i64 %v1, i64 %v2)
   %obit = extractvalue {i64, i1} %t, 1
   %ret = select i1 %obit, i64 %v1, i64 %v2
   ret i64 %ret
 }
 
+define i1 @umulo.not.i64(i64 %v1, i64 %v2) {
+entry:
+; CHECK-LABEL:  umulo.not.i64
+; CHECK:        umulh   [[MREG:x[0-9]+]], x0, x1
+; CHECK-NEXT:   cmp     xzr, [[MREG]]
+; CHECK-NEXT:   cset    w0, eq
+  %t = call {i64, i1} @llvm.umul.with.overflow.i64(i64 %v1, i64 %v2)
+  %obit = extractvalue {i64, i1} %t, 1
+  %ret = xor i1 %obit, true
+  ret i1 %ret
+}
+
 
 ;
 ; Check the use of the overflow bit in combination with a branch instruction.
 ;
 define zeroext i1 @saddo.br.i32(i32 %v1, i32 %v2) {
 entry:
 ; CHECK-LABEL:  saddo.br.i32
 ; CHECK:        cmn w0, w1