[PowerPC] calculate sadd/ssub overflow by sign bits

[tingwang]

Summary

This patch propose to calculate overflow by using sign bits.

Take signed-add as example: (LHS + RHS = Result), the original approach compare Result with LHS (this compare could involve multiple bits of information), and RHS with 0.
@llvm.sadd.with.overflow.i64 generates following instructions on P9:

ld 3, 0(3)
ld 4, 0(4)
add 6, 3, 4
rldicl 8, 3, 1, 63
rldicl 4, 4, 1, 63
sradi 7, 6, 63
subc    3, 6, 3
std 6, 0(5)
adde 3, 8, 7
xori 3, 3, 1
xor 3, 4, 3
blr

Alternative approach proposed here only use sign bits from LHS, RHS, and Result to decide overflow condition.

ld 3, 0(3)
ld 4, 0(4)
add 6, 3, 4
xor 4, 4, 6
xor 3, 3, 6
std 6, 0(5)
and 3, 3, 4
rldicl 3, 3, 1, 63
blr

llvm/include/llvm/CodeGen/TargetLowering.h

public:
 
   /// Return true if it is valid to merge the TargetMMOFlags in two SDNodes.
   virtual bool
   areTwoSDNodeTargetMMOFlagsMergeable(const MemSDNode &NodeX,
                                       const MemSDNode &NodeY) const {
     return true;
   }
 
+  /// Return true if it is more efficient to deduce add/sub overflow by sign
+  /// bits.
+  virtual bool useSignBitsToDeduceOverflow(EVT VT) const { return false; }
+
   /// Use bitwise logic to make pairs of compares more efficient. For example:
   /// and (seteq A, B), (seteq C, D) --> seteq (or (xor A, B), (xor C, D)), 0
   /// This should be true when it takes more than one instruction to lower
   /// setcc (cmp+set on x86 scalar), when bitwise ops are faster than logic on
   /// condition bits (crand on PowerPC), and/or when reducing cmp+br is a win.
   virtual bool convertSetCCLogicToBitwiseLogic(EVT VT) const {
     return false;
   }

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (isOperationLegal(OpcSat, LHS.getValueType())) {
     SDValue Sat = DAG.getNode(OpcSat, dl, LHS.getValueType(), LHS, RHS);
     SDValue SetCC = DAG.getSetCC(dl, OType, Result, Sat, ISD::SETNE);
     Overflow = DAG.getBoolExtOrTrunc(SetCC, dl, ResultType, ResultType);
     return;
   }
 
   SDValue Zero = DAG.getConstant(0, dl, LHS.getValueType());
 
+  if (useSignBitsToDeduceOverflow(LHS.getValueType())) {
+    SDValue COND1, COND2;
+    if (IsAdd) {
+      // For an addition, there can be overflow iff result sign is different
+      // from both operands.
+      COND1 = DAG.getNode(ISD::XOR, dl, LHS.getValueType(), LHS, Result);
+      COND2 = DAG.getNode(ISD::XOR, dl, LHS.getValueType(), RHS, Result);
+    } else {
+      // For a subtraction, there can be overflow iff operands have different
+      // sign, and result sign is different from left operand sign.
+      COND1 = DAG.getNode(ISD::XOR, dl, LHS.getValueType(), LHS, RHS);
+      COND2 = DAG.getNode(ISD::XOR, dl, LHS.getValueType(), Result, LHS);
+    }
+    SDValue FirstBitOverflow =
+        DAG.getNode(ISD::AND, dl, LHS.getValueType(), COND1, COND2);
+    Overflow = DAG.getBoolExtOrTrunc(
+        DAG.getSetCC(dl, OType, FirstBitOverflow, Zero, ISD::SETLT), dl,
+        ResultType, ResultType);
+    return;
+  }
+
   // For an addition, the result should be less than one of the operands (LHS)
   // if and only if the other operand (RHS) is negative, otherwise there will
   // be overflow.
   // For a subtraction, the result should be less than one of the operands
   // (LHS) if and only if the other operand (RHS) is (non-zero) positive,
   // otherwise there will be overflow.
   SDValue ResultLowerThanLHS = DAG.getSetCC(dl, OType, Result, LHS, ISD::SETLT);
   SDValue ConditionRHS =

llvm/lib/Target/PowerPC/PPCISelLowering.h

public:
     }
 
     bool hasAndNotCompare(SDValue) const override {
       return true;
     }
 
     bool preferIncOfAddToSubOfNot(EVT VT) const override;
 
+    bool useSignBitsToDeduceOverflow(EVT VT) const override {
+      return VT.isScalarInteger();
+    }
+
     bool convertSetCCLogicToBitwiseLogic(EVT VT) const override {
       return VT.isScalarInteger();
     }
 
     SDValue getNegatedExpression(SDValue Op, SelectionDAG &DAG, bool LegalOps,
                                  bool OptForSize, NegatibleCost &Cost,
                                  unsigned Depth = 0) const override;
 

llvm/test/CodeGen/PowerPC/saddo-ssubo.ll

entry:
   %overflow = extractvalue { i16, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_saddo_i32(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: test_saddo_i32:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    add 5, 3, 4
-; CHECK-NEXT:    cmpwi 1, 4, 0
-; CHECK-NEXT:    cmpw 5, 3
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    creqv 20, 4, 0
-; CHECK-NEXT:    isel 3, 0, 3, 20
+; CHECK-NEXT:    xor 4, 4, 5
+; CHECK-NEXT:    xor 3, 3, 5
+; CHECK-NEXT:    and 3, 3, 4
+; CHECK-NEXT:    srwi 3, 3, 31
 ; CHECK-NEXT:    blr
 entry:
   %res = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %a, i32 %b) nounwind
   %overflow = extractvalue { i32, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_saddo_i64(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: test_saddo_i64:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    add 5, 3, 4
-; CHECK-NEXT:    cmpdi 1, 4, 0
-; CHECK-NEXT:    cmpd 5, 3
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    creqv 20, 4, 0
-; CHECK-NEXT:    isel 3, 0, 3, 20
+; CHECK-NEXT:    xor 4, 4, 5
+; CHECK-NEXT:    xor 3, 3, 5
+; CHECK-NEXT:    and 3, 3, 4
+; CHECK-NEXT:    rldicl 3, 3, 1, 63
 ; CHECK-NEXT:    blr
 entry:
   %res = call { i64, i1 } @llvm.sadd.with.overflow.i64(i64 %a, i64 %b) nounwind
   %overflow = extractvalue { i64, i1 } %res, 1
   ret i1 %overflow
 }
 
 define <4 x i1> @test_saddo_v4i32(<4 x i32> %a, <4 x i32> %b) nounwind {
entry:
   %overflow = extractvalue { i16, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_ssubo_i32(i32 %a, i32 %b) nounwind {
 ; CHECK-LABEL: test_ssubo_i32:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    sub 5, 3, 4
-; CHECK-NEXT:    cmpwi 1, 4, 0
-; CHECK-NEXT:    cmpw 5, 3
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    creqv 20, 5, 0
-; CHECK-NEXT:    isel 3, 0, 3, 20
+; CHECK-NEXT:    xor 4, 3, 4
+; CHECK-NEXT:    xor 3, 5, 3
+; CHECK-NEXT:    and 3, 4, 3
+; CHECK-NEXT:    srwi 3, 3, 31
 ; CHECK-NEXT:    blr
 entry:
   %res = call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 %b) nounwind
   %overflow = extractvalue { i32, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_ssubo_i64(i64 %a, i64 %b) nounwind {
 ; CHECK-LABEL: test_ssubo_i64:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    sub 5, 3, 4
-; CHECK-NEXT:    cmpdi 1, 4, 0
-; CHECK-NEXT:    cmpd 5, 3
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    creqv 20, 5, 0
-; CHECK-NEXT:    isel 3, 0, 3, 20
+; CHECK-NEXT:    xor 4, 3, 4
+; CHECK-NEXT:    xor 3, 5, 3
+; CHECK-NEXT:    and 3, 4, 3
+; CHECK-NEXT:    rldicl 3, 3, 1, 63
 ; CHECK-NEXT:    blr
 entry:
   %res = call { i64, i1 } @llvm.ssub.with.overflow.i64(i64 %a, i64 %b) nounwind
   %overflow = extractvalue { i64, i1 } %res, 1
   ret i1 %overflow
 }
 
 define <4 x i1> @test_ssubo_v4i32(<4 x i32> %a, <4 x i32> %b) nounwind {