[SelectionDAG] Make SelectionDAG aware of the known bits in UADDO and SADDO.

[deadalnix]

Summary

As per title. This is extracted from D29872 and I threw SADDO in.

[deadalnix]

Regenerate some tests in master to reduce noise in this diff.

[deadalnix]

Fix the ISD::SUB case, which needs to was threated as ADDE. It is probably possible to do somethign better, but it's good enough for now.

[jyknight]

The multiple fall-throughs make this confusing. Since there's now three different properties that need to be checked (ADD vs SUB, carry-result vs no carry-result, carry-in vs no carry-in), a single fallthrough chain isn't really sufficient. I'd put all of the variants for all kinds of ADD/SUB in one case section, with ifs for the parts that need to be distinguished from each-other.

Should also move USUBO and SSUBO support down with the ADD/SUB variants, and treat them appropriately.

Also, ought to fix the exact same issue that occurs in ComputeNumSignBits for these operations.

[deadalnix]

Simplify the sub logic.

[RKSimon]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2520

Add some description comments

2523

Worth doing an early out here if KnownZeroLow == 0?

2528

KnownZero.setBits(0, KnownZeroLow);

2543

KnownZero.setBits(1, BitWidth);

2575

KnownZero.setBit(1, KnownZeroLow);

[deadalnix]

• Add comment for the sub case.
• Bail out early when KnownZeroLow == 0
• Use setBits

[deadalnix]

More setBits

[RKSimon]

LGTM with a couple of minors

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2579

KnownZero.setLowBits ?

2581

KnownZero.setHighBits ?

[deadalnix]

Use setLowBits and setHighBits

[RKSimon]

LGTM - thanks.

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::SELECT_CC:
     if (!KnownOne && !KnownZero)
       break;
     computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1);
 
     // Only known if known in both the LHS and RHS.
     KnownOne &= KnownOne2;
     KnownZero &= KnownZero2;
     break;
-  case ISD::SADDO:
-  case ISD::UADDO:
   case ISD::SSUBO:
   case ISD::USUBO:
   case ISD::SMULO:
   case ISD::UMULO:
     if (Op.getResNo() != 1)
       break;
     // The boolean result conforms to getBooleanContents.
     // If we know the result of a setcc has the top bits zero, use this info.
if (ConstantSDNode *CLHS = isConstOrConstSplat(Op.getOperand(0))) {
         // from [0-C].
         if ((KnownZero2 & MaskV) == MaskV) {
           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
           // Top bits known zero.
           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
         }
       }
     }
-    LLVM_FALLTHROUGH;
+
+    // If low bits are know to be zero in both operands, then we know they are
+    // going to be 0 in the result. Both addition and complement operations
+    // preserve the low zero bits.
+    computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, DemandedElts,
+                     Depth + 1);
+    unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
+    if (KnownZeroLow == 0)
+      break;
+
+    computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, DemandedElts,
+                     Depth + 1);
+    KnownZeroLow = std::min(KnownZeroLow,
+                            KnownZero2.countTrailingOnes());
+    KnownZero.setBits(0, KnownZeroLow);
+    break;
   }
+  case ISD::UADDO:
+  case ISD::SADDO:
+    if (Op.getResNo() == 1) {
+      // If we know the result of a setcc has the top bits zero, use this info.
+      if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) ==
+              TargetLowering::ZeroOrOneBooleanContent &&
+          BitWidth > 1)
+        KnownZero.setBits(1, BitWidth);
+      break;
+    }
+    LLVM_FALLTHROUGH;
   case ISD::ADD:
   case ISD::ADDC:
   case ISD::ADDE: {
     // Output known-0 bits are known if clear or set in both the low clear bits
     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
     // low 3 bits clear.
     // Output known-0 bits are also known if the top bits of each input are
     // known to be clear. For example, if one input has the top 10 bits clear
     // and the other has the top 8 bits clear, we know the top 7 bits of the
     // output must be clear.
     computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, DemandedElts,
                      Depth + 1);
     unsigned KnownZeroHigh = KnownZero2.countLeadingOnes();
     unsigned KnownZeroLow = KnownZero2.countTrailingOnes();
 
     computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, DemandedElts,
                      Depth + 1);
     KnownZeroHigh = std::min(KnownZeroHigh,
                              KnownZero2.countLeadingOnes());
     KnownZeroLow = std::min(KnownZeroLow,
                             KnownZero2.countTrailingOnes());
 
-    if (Opcode == ISD::ADD || Opcode == ISD::ADDC) {
-      KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
-      if (KnownZeroHigh > 1)
-        KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
+    if (Opcode == ISD::ADDE) {
+      // With ADDE, a carry bit may be added in, so we can only use this
+      // information if we know (at least) that the low two bits are clear.
+      // We then return to the caller that the low bit is unknown but that
+      // other bits are known zero.
+      if (KnownZeroLow >= 2)
+        KnownZero.setBits(1, KnownZeroLow);
       break;
     }
 
-    // With ADDE, a carry bit may be added in, so we can only use this
-    // information if we know (at least) that the low two bits are clear.  We
-    // then return to the caller that the low bit is unknown but that other bits
-    // are known zero.
-    if (KnownZeroLow >= 2) // ADDE
-      KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroLow);
+    KnownZero.setBits(0, KnownZeroLow);
+    if (KnownZeroHigh > 1)
+      KnownZero.setBits(BitWidth - KnownZeroHigh + 1, BitWidth);
     break;
   }
   case ISD::SREM:
     if (ConstantSDNode *Rem = isConstOrConstSplat(Op.getOperand(1))) {
       const APInt &RA = Rem->getAPIntValue().abs();
       if (RA.isPowerOf2()) {
         APInt LowBits = RA - 1;
         computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, DemandedElts,

test/CodeGen/X86/known-bits.ll

 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: knownbits_uaddo_saddo:
 ; X64:       # BB#0:
 ; X64-NEXT:    shlq $32, %rdi
 ; X64-NEXT:    shlq $32, %rsi
 ; X64-NEXT:    addq %rdi, %rsi
-; X64-NEXT:    setb %cl
+; X64-NEXT:    setb %al
 ; X64-NEXT:    seto %dl
-; X64-NEXT:    leal (%rsi,%rsi), %eax
-; X64-NEXT:    orb %cl, %dl
+; X64-NEXT:    orb %al, %dl
+; X64-NEXT:    xorl %eax, %eax
 ; X64-NEXT:    retq
   %1 = shl i64 %a0, 32
   %2 = shl i64 %a1, 32
   %u = call {i64, i1} @llvm.uadd.with.overflow.i64(i64 %1, i64 %2)
   %uval = extractvalue {i64, i1} %u, 0
   %uovf = extractvalue {i64, i1} %u, 1
   %s = call {i64, i1} @llvm.sadd.with.overflow.i64(i64 %1, i64 %2)
   %sval = extractvalue {i64, i1} %s, 0