[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

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

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

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

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

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

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

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

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.

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;
 }
 
 static SDValue LowerXOR(SDValue Op, SelectionDAG &DAG) {
   SDValue Sel = Op.getOperand(0);
   SDValue Other = Op.getOperand(1);
+  SDLoc dl(Sel);
 
+  ConstantSDNode *COp1 = dyn_cast<ConstantSDNode>(Other);
+  unsigned Opc = Sel.getOpcode();
+  // If the operand is an overflow checking operation, invert the condition
+  // code and kill the xor(op, 1).
+  if (Sel.getResNo() == 1 &&
+      (Opc == ISD::SADDO || Opc == ISD::UADDO || Opc == ISD::SSUBO ||
+       Opc == ISD::USUBO || Opc == ISD::SMULO || Opc == ISD::UMULO) &&
+      COp1 && COp1->getZExtValue() == 1) {
+    // 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);
 

test/CodeGen/AArch64/arm64-xaluo.ll

 
 overflow:
   ret i1 false
 
 continue:
   ret i1 true
 }
 
+; Check cc optimization of not(overflow)
+
+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 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 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 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 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 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 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 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 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 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 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 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
+}
+
 declare {i32, i1} @llvm.sadd.with.overflow.i32(i32, i32) nounwind readnone
 declare {i64, i1} @llvm.sadd.with.overflow.i64(i64, i64) nounwind readnone
 declare {i32, i1} @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone
 declare {i64, i1} @llvm.uadd.with.overflow.i64(i64, i64) nounwind readnone
 declare {i32, i1} @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone
 declare {i64, i1} @llvm.ssub.with.overflow.i64(i64, i64) nounwind readnone
 declare {i32, i1} @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone
 declare {i64, i1} @llvm.usub.with.overflow.i64(i64, i64) nounwind readnone
 declare {i32, i1} @llvm.smul.with.overflow.i32(i32, i32) nounwind readnone
 declare {i64, i1} @llvm.smul.with.overflow.i64(i64, i64) nounwind readnone
 declare {i32, i1} @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone
 declare {i64, i1} @llvm.umul.with.overflow.i64(i64, i64) nounwind readnone