[DAGCombiner] Make DAGCombiner smarter about overflow

[deadalnix]

Summary

Leverage it to transform addc into add.

[RKSimon]

include/llvm/CodeGen/SelectionDAG.h

1283

Please document both the enum and the method.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1850

SDLoc DL(N);

[deadalnix]

Add documentation and style change.

[RKSimon]

include/llvm/CodeGen/SelectionDAG.h

1283

http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

Style guide says enums should ave a prefix: OFK_Never, OFK_Sometimes, OFK_Always

1287

result of

1290

You can probably drop this part of the description now that OverflowKind is documented

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2780

Does the test cases cover both of these patterns? Its not clear if it does.

2782

Are you intending to add OverflowKind::Always cases soon? If not you should possibly drop it from the enum and just put in a TODO.

[deadalnix]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2780

I need some more improvement in the handling of adde/addc ( D29443 ) to expose the second one. then it kicks in in muladd in test/CodeGen/X86/adde-carry.ll

2782

Yes I want to add some there to transform adde(X, C, Carry) => addc(X, C+1) when the carry is always there.

[deadalnix]

Address comments.

[RKSimon]

One last comment.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2780

In which case please can you drop this case until you can test for it? You can include it in another patch for review and commit it separately if you wish.

[deadalnix]

Remove case that isn't testable at this time.

[deadalnix]

Crap I landed that one instead of D29521 . @RKSimon do you think it's good ? If not I'll revert.

[RKSimon]

In D29524#667709, @deadalnix wrote:

Crap I landed that one instead of D29521 . @RKSimon do you think it's good ? If not I'll revert.

No you're ok - post LGTM.

include/llvm/CodeGen/SelectionDAG.h

public:
   /// them in the KnownZero/KnownOne bitsets. The DemandedElts argument allows
   /// us to only collect the known bits that are shared by the requested vector
   /// elements.
   /// Targets can implement the computeKnownBitsForTargetNode method in the
   /// TargetLowering class to allow target nodes to be understood.
   void computeKnownBits(SDValue Op, APInt &KnownZero, APInt &KnownOne,
                         const APInt &DemandedElts, unsigned Depth = 0) const;
 
+  /// Used to represent the possible overflow behavior of an operation.
+  /// Never: the operation cannot overflow.
+  /// Always: the operation will always overflow.
+  /// Sometime: the operation may or may not overflow.
+  enum OverflowKind {
+    OFK_Never,
+    OFK_Sometime,
+    OFK_Always,
+  };
+
+  /// Determine if the result of the addition of 2 node can overflow.
+  OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
+
   /// Test if the given value is known to have exactly one bit set. This differs
   /// from computeKnownBits in that it doesn't necessarily determine which bit
   /// is set.
   bool isKnownToBeAPowerOfTwo(SDValue Val) const;
 
   /// Return the number of times the sign bit of the register is replicated into
   /// the other bits. We know that at least 1 bit is always equal to the sign
   /// bit (itself), but other cases can give us information. For example,
   /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADDLike(SDValue N0, SDValue N1, SDNode *LocReference) {
 
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDC(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
+  SDLoc DL(N);
 
   // If the flag result is dead, turn this into an ADD.
   if (!N->hasAnyUseOfValue(1))
-    return CombineTo(N, DAG.getNode(ISD::ADD, SDLoc(N), VT, N0, N1),
-                     DAG.getNode(ISD::CARRY_FALSE,
-                                 SDLoc(N), MVT::Glue));
+    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
+                     DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
 
   // canonicalize constant to RHS.
   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
   if (N0C && !N1C)
-    return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N1, N0);
+    return DAG.getNode(ISD::ADDC, DL, N->getVTList(), N1, N0);
 
   // fold (addc x, 0) -> x + no carry out
   if (isNullConstant(N1))
     return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE,
-                                        SDLoc(N), MVT::Glue));
+                                        DL, MVT::Glue));
 
-  // fold (addc a, b) -> (or a, b), CARRY_FALSE iff a and b share no bits.
-  APInt LHSZero, LHSOne;
-  APInt RHSZero, RHSOne;
-  DAG.computeKnownBits(N0, LHSZero, LHSOne);
-
-  if (LHSZero.getBoolValue()) {
-    DAG.computeKnownBits(N1, RHSZero, RHSOne);
-
-    // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
-    // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
-    if ((RHSZero & ~LHSZero) == ~LHSZero || (LHSZero & ~RHSZero) == ~RHSZero)
-      return CombineTo(N, DAG.getNode(ISD::OR, SDLoc(N), VT, N0, N1),
-                       DAG.getNode(ISD::CARRY_FALSE,
-                                   SDLoc(N), MVT::Glue));
-  }
+  // If it cannot overflow, transform into an add.
+  if (DAG.computeOverflowKind(N0, N1) == SelectionDAG::OFK_Never)
+    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
+                     DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
 
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDE(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue CarryIn = N->getOperand(2);

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::INTRINSIC_VOID:
     // Allow the target to implement this method for its nodes.
     TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth);
     break;
   }
 
   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
 }
 
+SelectionDAG::OverflowKind SelectionDAG::computeOverflowKind(SDValue N0,
+                                                             SDValue N1) const {
+  // X + 0 never overflow
+  if (isNullConstant(N1))
+    return OFK_Never;
+
+  APInt N1Zero, N1One;
+  computeKnownBits(N1, N1Zero, N1One);
+  if (N1Zero.getBoolValue()) {
+    APInt N0Zero, N0One;
+    computeKnownBits(N0, N0Zero, N0One);
+
+    bool overflow;
+    (~N0Zero).uadd_ov(~N1Zero, overflow);
+    if (!overflow)
+      return OFK_Never;
+  }
+
+  return OFK_Sometime;
+}
+
 bool SelectionDAG::isKnownToBeAPowerOfTwo(SDValue Val) const {
   EVT OpVT = Val.getValueType();
   unsigned BitWidth = OpVT.getScalarSizeInBits();
 
   // Is the constant a known power of 2?
   if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(Val))
     return Const->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2();
 
   // A left-shift of a constant one will have exactly one bit set because
   // shifting the bit off the end is undefined.
   if (Val.getOpcode() == ISD::SHL) {

test/CodeGen/X86/divrem8_ext.ll

 ; X32-LABEL: pr25754:
 ; X32:       # BB#0:
 ; X32-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    # kill: %EAX<def> %EAX<kill> %AX<def>
 ; X32-NEXT:    divb {{[0-9]+}}(%esp)
 ; X32-NEXT:    movzbl %ah, %ecx # NOREX
 ; X32-NEXT:    movzbl %al, %eax
 ; X32-NEXT:    addl %ecx, %eax
-; X32-NEXT:    sbbl %edx, %edx
-; X32-NEXT:    andl $1, %edx
+; X32-NEXT:    xorl %edx, %edx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: pr25754:
 ; X64:       # BB#0:
 ; X64-NEXT:    movzbl %dil, %eax
 ; X64-NEXT:    # kill: %EAX<def> %EAX<kill> %AX<def>
 ; X64-NEXT:    divb %sil
 ; X64-NEXT:    movzbl %ah, %ecx # NOREX