Add ADDC to SelectionDAG::computeKnownBits and ComputeNumSignBits.

[deadalnix]

Summary

As per title.

[RKSimon]

Tests?

[deadalnix]

I asked myself the same question. Not sure how I'd test this.

[davide]

In D29521#667167, @deadalnix wrote:

I asked myself the same question. Not sure how I'd test this.

Probably you can mimic the tests for add (if any?)

[deadalnix]

In D29521#667258, @davide wrote:

Probably you can mimic the tests for add (if any?)

I'm not aware of any, however, surely, there is some test somewhere that depends on it. I'll try removing the add case and see what breaks.

[RKSimon]

In D29521#667282, @deadalnix wrote:

In D29521#667258, @davide wrote:

Probably you can mimic the tests for add (if any?)

I'm not aware of any, however, surely, there is some test somewhere that depends on it. I'll try removing the add case and see what breaks.

There are very few scalar tests - llvm\test\CodeGen\X86\known-bits.ll is almost empty. The llvm\test\CodeGen\X86\known-bits-vector.ll has more examples - scalarizing one of those should be trivial.

[deadalnix]

Add test case for add and adc.

The test case for adc is a bit complex, but it was necessary to put the adc in a context where its surrounding cannot be optimized away. That means computing a result using the carry, and returning it somehow, while making sure the result of the adc itself can be optimized away.

[RKSimon]

Please can you rebase? I've added the current known-bits.ll test codegen (rL294184) so you can show the delta.

[deadalnix]

rebase

[RKSimon]

LGTM

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (ConstantSDNode *CLHS = isConstOrConstSplat(Op.getOperand(0))) {
           // Top bits known zero.
           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2);
         }
       }
     }
     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) {
+    if (Opcode == ISD::ADD || Opcode == ISD::ADDC) {
       KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroLow);
       if (KnownZeroHigh > 1)
         KnownZero |= APInt::getHighBitsSet(BitWidth, KnownZeroHigh - 1);
       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
if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 
       // If we aren't rotating out all of the known-in sign bits, return the
       // number that are left.  This handles rotl(sext(x), 1) for example.
       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
       if (Tmp > RotAmt+1) return Tmp-RotAmt;
     }
     break;
   case ISD::ADD:
+  case ISD::ADDC:
     // Add can have at most one carry bit.  Thus we know that the output
     // is, at worst, one more bit than the inputs.
     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
     if (Tmp == 1) return 1;  // Early out.
 
     // Special case decrementing a value (ADD X, -1):
     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
       if (CRHS->isAllOnesValue()) {

test/CodeGen/X86/known-bits.ll

 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; X32-NEXT:    andl %esi, %edi
 ; X32-NEXT:    andl {{[0-9]+}}(%esp), %esi
 ; X32-NEXT:    addl %edi, %esi
 ; X32-NEXT:    adcl {{[0-9]+}}(%esp), %edx
 ; X32-NEXT:    adcl $0, %ecx
 ; X32-NEXT:    shldl $22, %edx, %ecx
 ; X32-NEXT:    shldl $22, %esi, %edx
-; X32-NEXT:    shll $22, %esi
-; X32-NEXT:    movl %esi, 4(%eax)
 ; X32-NEXT:    movl %edx, 8(%eax)
 ; X32-NEXT:    movl %ecx, 12(%eax)
+; X32-NEXT:    movl $0, 4(%eax)
 ; X32-NEXT:    movl $0, (%eax)
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    popl %edi
 ; X32-NEXT:    retl $4
 ;
 ; X64-LABEL: knownbits_mask_addc_shl:
 ; X64:       # BB#0:
 ; X64-NEXT:    andq $-1024, %rdi # imm = 0xFC00
 ; X64-NEXT:    andq $-1024, %rsi # imm = 0xFC00
 ; X64-NEXT:    addq %rdi, %rsi
 ; X64-NEXT:    sbbq %rax, %rax
 ; X64-NEXT:    subl %eax, %edx
 ; X64-NEXT:    shldq $54, %rsi, %rdx
-; X64-NEXT:    shlq $54, %rsi
-; X64-NEXT:    movq %rsi, %rax
+; X64-NEXT:    xorl %eax, %eax
 ; X64-NEXT:    retq
   %1 = and i64 %a0, -1024
   %2 = zext i64 %1 to i128
   %3 = and i64 %a1, -1024
   %4 = zext i64 %3 to i128
   %5 = add i128 %2, %4
   %6 = zext i64 %a2 to i128
   %7 = shl i128 %6, 64
   %8 = add i128 %5, %7
   %9 = shl i128 %8, 54
   ret i128 %9
 }