[DAGCombiner] Make DAGCombiner smarter about overflow

[deadalnix]

Summary

Leverage it to transform addc into add.

[RKSimon]

include/llvm/CodeGen/SelectionDAG.h

1283 ↗

(On Diff #87056)

Please document both the enum and the method.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1836 ↗

(On Diff #87056)

SDLoc DL(N);

[deadalnix]

Add documentation and style change.

[RKSimon]

include/llvm/CodeGen/SelectionDAG.h

1287 ↗

(On Diff #87140)

result of

1290 ↗

(On Diff #87140)

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

1283 ↗

(On Diff #87056)

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

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2780 ↗

(On Diff #87140)

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

2782 ↗

(On Diff #87140)

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 ↗

(On Diff #87140)

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 ↗

(On Diff #87140)

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 ↗

(On Diff #87140)

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.

llvm/trunk/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,

llvm/trunk/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);

llvm/trunk/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();
 

llvm/trunk/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