[SelectionDAG] Use KnownBits::computeForAddSub in SelectionDAG::computeKnownBits

[bjope]

Summary

Start using KnownBits::computeForAddSub in
SelectionDAG::computeKnownBits when doing value
tracking for addition/subtraction.

This should improve the precision of the known bits,
as we only used to make a simple estimate of known
zeroes. The KnownBits::computeForAddSub function is
also able to deduce bits that are known to be one
in the result.

[lebedev.ri]

This looks ok, but should have more tests.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2971–2974 ↗

(On Diff #194305)

When committing, this should/could be a separate change.

2986 ↗

(On Diff #194305)

This is correct, what llvm::haveNoCommonBitsSet() does.

[bjope]

Added a unittest (by using the AArch64SelectionDAGTest unittest framework).

[nikic]

We have an accurate known bits implementation for adds in KnownBits::computeForAddSub(), which should handle this and more automatically. We use it to compute add known bits in IR. Is there a reason why it's not used for SDAG known bits?

[lebedev.ri]

In D60460#1460375, @nikic wrote:

We have an accurate known bits implementation for adds in KnownBits::computeForAddSub(), which should handle this and more automatically. We use it to compute add known bits in IR. Is there a reason why it's not used for SDAG known bits?

Hmm, good point. In general because of IR Value vs DAG SDValue. But clearly that function should work here..

[bjope]

In D60460#1460387, @lebedev.ri wrote:

In D60460#1460375, @nikic wrote:

We have an accurate known bits implementation for adds in KnownBits::computeForAddSub(), which should handle this and more automatically. We use it to compute add known bits in IR. Is there a reason why it's not used for SDAG known bits?

Hmm, good point. In general because of IR Value vs DAG SDValue. But clearly that function should work here..

Ahh, great! Using KnownBits::computeForAddSub() sounds like the right thing to do. I'll give it a try!

And then I guess we should do the same for SUB. I need to figure out if the computeForAddSub cover the special cases handled by SelectionDAG for SUB. I might skip doing anything about SUB in this patch if it turns out to be non-trivial to simply replace the current logic with a call to computeForAddSub.

[bjope]

Use KnownBits::computeForAddSub instead, and do it for both ADD* and SUB* nodes.

[nikic]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2948 ↗

(On Diff #194468)

I think it would make more sense to move the computeForAddSub calculation above this branch, and then do something like this here:

// With ADDE and ADDCARRY a carry bit may be added, so we can only use
// this information if we know that the low bit is clear.
if (!lowBitSet(Known.Zero)) { // How do you write this operation with APInt?
  Known.One.clearAllBits();
  Known.Zero.clearAllBits();
  break;
}

Known.Zero.clearBit(0);

This allows us to use the full known bits result, just without the low bit, if it is possible.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2911 ↗

(On Diff #194468)

No need to construct KnownLHS here
KnownBits KnownLHS = computeKnownBits
(or we could add a Known3 to the top of the function?)

2933 ↗

(On Diff #194468)

KnownBits KnownLHS = computeKnownBits

[bjope]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2948 ↗

(On Diff #194468)

Or maybe I can use computeForAddSub a second time, simulating an add of the carry bit

// With ADDE and ADDCARRY, a carry bit may be added in.
if (Opcode == ISD::ADDE || Opcode == ISD::ADDCARRY) {
  // TODO: Can we compute known bits for the carry bit? For now we set it to
  // unknown.
  Known2.setAllZero();
  Known2.Zero.clearBit(0);
  Known = KnownBits::computeForAddSub(/* IsAdd */ true, /* NSW */ false,
                                      Known, Known2);
}

[bjope]

Simplified based on feedback.

[nikic]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2948 ↗

(On Diff #194468)

This works and is fully accurate. I think it would be slightly better to integrate the carry in the computeForAddSub() calculation, because it's cheaper than doing it twice. I've opened D60522 to support this. With this method the implementation here would reduce to:

bool CarryKnownZero = Opcode != ISD::ADDE && Opcode != ISD::ADDCARRY;
Known = KnownBits::computeForAddCarry(
    Known, Known2, CarryKnownZero, /*CarryKnownOne*/ false);

[bjope]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2929 ↗

(On Diff #194497)

Am I missing something, or isn't ADDC and ADDE producing multiple results (just like ADDCARRY etc above)?
So isn't it necessary to check if we are tracking the result of getResNo()==0 or getResNo()=1 also for ADDC and ADDE?

[bjope]

Updated to use a KnownBits::computeForAddCarry helper. I added a simple
implementation here, but the idea is to replace it by the improved version
from D60522 instead (if we land that patch before this one).

Also added a TODO for computing known bits for the carry in ADDCARRY. If we do
not think it is worth the trouble I can remove the TODO again before landing
this.
It is probably more important to add known bits tracking for the non-carry
result produced SUBCARRY (as we can rewrite ADDCARRY into SUBCARRY which at
the moment results in losing info about known bits).

[lebedev.ri]

llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp

160 ↗

(On Diff #194701)

If a diff is based on some other patch, it is best not to include that other patch into this diff (be more specific for which commits you want to generate the diff in git), but instead mark that other patch as parent.

[bjope]

llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp

160 ↗

(On Diff #194701)

Not sure if I get that. You asked for test cases, and these are the test cases I added (they would fail without the improvements in computeKnownBits for ADD and SUB).

Although, I see now that I made a typo in the test names. They should be called ComputeKnownBits_ADD and ComputeKnownBits_SUB.

However, if I rebase this upon https://reviews.llvm.org/D60522 this patch will use the helpers in KnownBits (which also includes more exhaustive unittests). So I guess these tests will become less important after that rebase.

161 ↗

(On Diff #194701)

typo: ComputeKnownBits_ADD

182 ↗

(On Diff #194701)

typo: ComputeKnownBits_SUB

[bjope]

llvm/test/CodeGen/X86/x32-va_start.ll

62 ↗

(On Diff #194701)

The patch with CopyFromReg has been reverted. So this diff will go away after rebasing to trunk.

[lebedev.ri]

(Yes, i think it is best to rebase this ontop of D60522.)

llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp

160 ↗

(On Diff #194701)

Not sure if I get that.

Oh sorry, i quickly looked over this, and though this was already based on D60522 *AND* included it's testcases here.
All good.

[lebedev.ri]

Rebase now that D60522 landed?

[bjope]

Rebased. Corrected typos in the test cases.

[nikic]

LGTM

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (Op.getResNo() == 1) {
               TargetLowering::ZeroOrOneBooleanContent &&
           BitWidth > 1)
         Known.Zero.setBitsFrom(1);
       break;
     }
     LLVM_FALLTHROUGH;
   case ISD::SUB:
   case ISD::SUBC: {
-    if (ConstantSDNode *CLHS = isConstOrConstSplat(Op.getOperand(0))) {
-      // We know that the top bits of C-X are clear if X contains less bits
-      // than C (i.e. no wrap-around can happen).  For example, 20-X is
-      // positive if we can prove that X is >= 0 and < 16.
-      if (CLHS->getAPIntValue().isNonNegative()) {
-        unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
-        // NLZ can't be BitWidth with no sign bit
-        APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
-        Known2 = computeKnownBits(Op.getOperand(1), DemandedElts,
-                         Depth + 1);
-
-        // If all of the MaskV bits are known to be zero, then we know the
-        // output top bits are zero, because we now know that the output is
-        // from [0-C].
-        if ((Known2.Zero & MaskV) == MaskV) {
-          unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
-          // Top bits known zero.
-          Known.Zero.setHighBits(NLZ2);
-        }
-      }
-    }
-
-    // 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.
-    Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
-    unsigned KnownZeroLow = Known2.countMinTrailingZeros();
-    if (KnownZeroLow == 0)
-      break;
-
+    Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
-    KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
-    Known.Zero.setLowBits(KnownZeroLow);
+    Known = KnownBits::computeForAddSub(/* Add */ false, /* NSW */ false,
+                                        Known, Known2);
     break;
   }
   case ISD::UADDO:
   case ISD::SADDO:
   case ISD::ADDCARRY:
     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)
         Known.Zero.setBitsFrom(1);
       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.
-    Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
-    unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
-    unsigned KnownZeroLow = Known2.countMinTrailingZeros();
+    assert(Op.getResNo() == 0 && "We only compute knownbits for the sum here.");
 
-    Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
-    KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
-    KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
-
-    if (Opcode == ISD::ADDE || Opcode == ISD::ADDCARRY) {
-      // With ADDE and ADDCARRY, 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)
-        Known.Zero.setBits(1, KnownZeroLow);
-      break;
-    }
+    // With ADDE and ADDCARRY, a carry bit may be added in.
+    KnownBits Carry(1);
+    if (Opcode == ISD::ADDE)
+      // Can't track carry from glue, set carry to unknown.
+      Carry.resetAll();
+    else if (Opcode == ISD::ADDCARRY)
+      // TODO: Compute known bits for the carry operand. Not sure if it is worth
+      // the trouble (how often will we find a known carry bit). And I haven't
+      // tested this very much yet, but something like this might work:
+      //   Carry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
+      //   Carry = Carry.zextOrTrunc(1, false);
+      Carry.resetAll();
+    else
+      Carry.setAllZero();
 
-    Known.Zero.setLowBits(KnownZeroLow);
-    if (KnownZeroHigh > 1)
-      Known.Zero.setHighBits(KnownZeroHigh - 1);
+    Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
+    Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
+    Known = KnownBits::computeForAddCarry(Known, Known2, Carry);
     break;
   }
   case ISD::SREM:
     if (ConstantSDNode *Rem = isConstOrConstSplat(Op.getOperand(1))) {
       const APInt &RA = Rem->getAPIntValue().abs();
       if (RA.isPowerOf2()) {
         APInt LowBits = RA - 1;
         Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);

llvm/trunk/test/CodeGen/X86/pr32282.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-unknown -mcpu=skx | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mcpu=skx | FileCheck %s --check-prefix=X64
 
 ; Check for assert in foldMaskAndShiftToScale due to out of range mask scaling.
 
 @b = common global i8 zeroinitializer, align 1
 @c = common global i8 zeroinitializer, align 1
 @d = common global i64 zeroinitializer, align 8
 @e = common global i64 zeroinitializer, align 8
 
 define void @foo(i64 %x) nounwind {
 ; X86-LABEL: foo:
 ; X86:       # %bb.0:
 ; X86-NEXT:    pushl %eax
-; X86-NEXT:    movl d, %eax
+; X86-NEXT:    movl d+4, %eax
 ; X86-NEXT:    notl %eax
-; X86-NEXT:    movl d+4, %ecx
+; X86-NEXT:    movl d, %ecx
 ; X86-NEXT:    notl %ecx
-; X86-NEXT:    andl $701685459, %ecx # imm = 0x29D2DED3
-; X86-NEXT:    andl $-564453154, %eax # imm = 0xDE5B20DE
-; X86-NEXT:    shrdl $21, %ecx, %eax
-; X86-NEXT:    shrl $21, %ecx
-; X86-NEXT:    andl $-2, %eax
-; X86-NEXT:    addl $7, %eax
-; X86-NEXT:    adcl $0, %ecx
-; X86-NEXT:    pushl %ecx
+; X86-NEXT:    andl $-566231040, %ecx # imm = 0xDE400000
+; X86-NEXT:    andl $701685459, %eax # imm = 0x29D2DED3
+; X86-NEXT:    shrdl $21, %eax, %ecx
+; X86-NEXT:    shrl $21, %eax
+; X86-NEXT:    addl $7, %ecx
+; X86-NEXT:    adcl $0, %eax
 ; X86-NEXT:    pushl %eax
+; X86-NEXT:    pushl %ecx
 ; X86-NEXT:    pushl {{[0-9]+}}(%esp)
 ; X86-NEXT:    pushl {{[0-9]+}}(%esp)
 ; X86-NEXT:    calll __divdi3
 ; X86-NEXT:    addl $16, %esp
 ; X86-NEXT:    orl %eax, %edx
 ; X86-NEXT:    setne {{[0-9]+}}(%esp)
 ; X86-NEXT:    popl %eax
 ; X86-NEXT:    retl

llvm/trunk/unittests/CodeGen/AArch64SelectionDAGTest.cpp

TEST_F(AArch64SelectionDAGTest, SimplifyDemandedVectorElts_EXTRACT_SUBVECTOR) {
   auto KnownUndef = APInt(3, 0);
   auto KnownZero = APInt(3, 0);
   TargetLowering::TargetLoweringOpt TLO(*DAG, false, false);
   EXPECT_EQ(TL.SimplifyDemandedVectorElts(Op, DemandedElts, KnownUndef,
                                           KnownZero, TLO),
             false);
 }
 
+// Piggy-backing on the AArch64 tests to verify SelectionDAG::computeKnownBits.
+TEST_F(AArch64SelectionDAGTest, ComputeKnownBits_ADD) {
+  if (!TM)
+    return;
+  SDLoc Loc;
+  auto IntVT = EVT::getIntegerVT(Context, 8);
+  auto UnknownOp = DAG->getRegister(0, IntVT);
+  auto Mask = DAG->getConstant(0x8A, Loc, IntVT);
+  auto N0 = DAG->getNode(ISD::AND, Loc, IntVT, Mask, UnknownOp);
+  auto N1 = DAG->getConstant(0x55, Loc, IntVT);
+  auto Op = DAG->getNode(ISD::ADD, Loc, IntVT, N0, N1);
+  // N0 = ?000?0?0
+  // N1 = 01010101
+  //  =>
+  // Known.One  = 01010101 (0x55)
+  // Known.Zero = 00100000 (0x20)
+  KnownBits Known = DAG->computeKnownBits(Op);
+  EXPECT_EQ(Known.Zero, APInt(8, 0x20));
+  EXPECT_EQ(Known.One, APInt(8, 0x55));
+}
+
+// Piggy-backing on the AArch64 tests to verify SelectionDAG::computeKnownBits.
+TEST_F(AArch64SelectionDAGTest, ComputeKnownBits_SUB) {
+  if (!TM)
+    return;
+  SDLoc Loc;
+  auto IntVT = EVT::getIntegerVT(Context, 8);
+  auto N0 = DAG->getConstant(0x55, Loc, IntVT);
+  auto UnknownOp = DAG->getRegister(0, IntVT);
+  auto Mask = DAG->getConstant(0x2e, Loc, IntVT);
+  auto N1 = DAG->getNode(ISD::AND, Loc, IntVT, Mask, UnknownOp);
+  auto Op = DAG->getNode(ISD::SUB, Loc, IntVT, N0, N1);
+  // N0 = 01010101
+  // N1 = 00?0???0
+  //  =>
+  // Known.One  = 00000001 (0x1)
+  // Known.Zero = 10000000 (0x80)
+  KnownBits Known = DAG->computeKnownBits(Op);
+  EXPECT_EQ(Known.Zero, APInt(8, 0x80));
+  EXPECT_EQ(Known.One, APInt(8, 0x1));
+}
+
 } // end anonymous namespace