diff --git a/llvm/include/llvm/Support/KnownBits.h b/llvm/include/llvm/Support/KnownBits.h --- a/llvm/include/llvm/Support/KnownBits.h +++ b/llvm/include/llvm/Support/KnownBits.h @@ -202,6 +202,11 @@ return getBitWidth() - Zero.countPopulation(); } + /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry. + static KnownBits computeForAddCarry(const KnownBits &LHS, + const KnownBits &RHS, + const KnownBits &Carry); + /// Compute known bits resulting from adding LHS and RHS. static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS); diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp @@ -2907,39 +2907,10 @@ 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(/* IsSub */ false, /* NSW */ false, + Known, Known2); break; } case ISD::UADDO: @@ -2957,34 +2928,26 @@ 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 known bits for the sum here."); + + // 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 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1); 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; - } - - Known.Zero.setLowBits(KnownZeroLow); - if (KnownZeroHigh > 1) - Known.Zero.setHighBits(KnownZeroHigh - 1); + Known = KnownBits::computeForAddCarry(Known, Known2, Carry); break; } case ISD::SREM: diff --git a/llvm/lib/Support/KnownBits.cpp b/llvm/lib/Support/KnownBits.cpp --- a/llvm/lib/Support/KnownBits.cpp +++ b/llvm/lib/Support/KnownBits.cpp @@ -15,6 +15,21 @@ using namespace llvm; +KnownBits KnownBits::computeForAddCarry(const KnownBits &LHS, + const KnownBits &RHS, + const KnownBits &Carry) { + assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit."); + + KnownBits KnownOut; + KnownOut = KnownBits::computeForAddSub(true, false, LHS, RHS); + + // Adjust for carry. + KnownBits ExtendedCarry = Carry.zextOrTrunc(LHS.getBitWidth(), true); + KnownOut = KnownBits::computeForAddSub(true, false, KnownOut, ExtendedCarry); + + return KnownOut; +} + KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS) { // Carry in a 1 for a subtract, rather than 0. diff --git a/llvm/test/CodeGen/X86/pr32282.ll b/llvm/test/CodeGen/X86/pr32282.ll --- a/llvm/test/CodeGen/X86/pr32282.ll +++ b/llvm/test/CodeGen/X86/pr32282.ll @@ -13,19 +13,18 @@ ; 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 diff --git a/llvm/test/CodeGen/X86/x32-va_start.ll b/llvm/test/CodeGen/X86/x32-va_start.ll --- a/llvm/test/CodeGen/X86/x32-va_start.ll +++ b/llvm/test/CodeGen/X86/x32-va_start.ll @@ -58,7 +58,12 @@ store i32 %3, i32* %gp_offset_p, align 16 br label %vaarg.end ; CHECK: movl {{[^,]*}}, [[ADDR:.*]] -; CHECK: addl [[COUNT]], [[ADDR]] + +; Nowadays we can do value tracking through CopyFromReg, so we know that +; [[COUNT]] is $8 here (we actually get "cmpl $40, $8" when catching [[COUNT]] +; above), and constant folding is expected in the addl and movl below. +; CHECK: addl $8, [[ADDR]] +; CHECK: movl $16, ; SSE: jmp .[[END:.*]] ; NOSSE: movl ([[ADDR]]), %eax ; NOSSE: retq diff --git a/llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp b/llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp --- a/llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp +++ b/llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp @@ -157,4 +157,47 @@ false); } +// Piggy-backing on the AArch64 tests to verify SelectionDAG::computeKnownBits. +TEST_F(AArch64SelectionDAGTest, ComputeNumSignBits_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, ComputeNumSignBits_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