Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -1077,49 +1077,51 @@ Operator *I = dyn_cast(V); if (!I) return; + // Do not overwrite KnownZero and KnownOne computed before. + APInt KnownZero1(KnownZero), KnownOne1(KnownOne); APInt KnownZero2(KnownZero), KnownOne2(KnownOne); switch (I->getOpcode()) { default: break; case Instruction::Load: if (MDNode *MD = cast(I)->getMetadata(LLVMContext::MD_range)) - computeKnownBitsFromRangeMetadata(*MD, KnownZero); + computeKnownBitsFromRangeMetadata(*MD, KnownZero1); break; case Instruction::And: { // If either the LHS or the RHS are Zero, the result is zero. - computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q); + computeKnownBits(I->getOperand(1), KnownZero1, KnownOne1, DL, Depth + 1, Q); computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q); // Output known-1 bits are only known if set in both the LHS & RHS. - KnownOne &= KnownOne2; + KnownOne1 &= KnownOne2; // Output known-0 are known to be clear if zero in either the LHS | RHS. - KnownZero |= KnownZero2; + KnownZero1 |= KnownZero2; break; } case Instruction::Or: { - computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q); + computeKnownBits(I->getOperand(1), KnownZero1, KnownOne1, DL, Depth + 1, Q); computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q); // Output known-0 bits are only known if clear in both the LHS & RHS. - KnownZero &= KnownZero2; + KnownZero1 &= KnownZero2; // Output known-1 are known to be set if set in either the LHS | RHS. - KnownOne |= KnownOne2; + KnownOne1 |= KnownOne2; break; } case Instruction::Xor: { - computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q); + computeKnownBits(I->getOperand(1), KnownZero1, KnownOne1, DL, Depth + 1, Q); computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q); // Output known-0 bits are known if clear or set in both the LHS & RHS. - APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); + APInt KnownZeroOut = (KnownZero1 & KnownZero2) | (KnownOne1 & KnownOne2); // Output known-1 are known to be set if set in only one of the LHS, RHS. - KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); - KnownZero = KnownZeroOut; + KnownOne1 = (KnownZero1 & KnownOne2) | (KnownOne1 & KnownZero2); + KnownZero1 = KnownZeroOut; break; } case Instruction::Mul: { bool NSW = cast(I)->hasNoSignedWrap(); - computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, KnownZero, - KnownOne, KnownZero2, KnownOne2, DL, Depth, Q); + computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, KnownZero1, + KnownOne1, KnownZero2, KnownOne2, DL, Depth, Q); break; } case Instruction::UDiv: { @@ -1137,16 +1139,16 @@ LeadZ = std::min(BitWidth, LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); - KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ); + KnownZero1 = APInt::getHighBitsSet(BitWidth, LeadZ); break; } case Instruction::Select: - computeKnownBits(I->getOperand(2), KnownZero, KnownOne, DL, Depth + 1, Q); + computeKnownBits(I->getOperand(2), KnownZero1, KnownOne1, DL, Depth + 1, Q); computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q); // Only known if known in both the LHS and RHS. - KnownOne &= KnownOne2; - KnownZero &= KnownZero2; + KnownOne1 &= KnownOne2; + KnownZero1 &= KnownZero2; break; case Instruction::FPTrunc: case Instruction::FPExt: @@ -1169,14 +1171,14 @@ SrcBitWidth = DL.getTypeSizeInBits(SrcTy->getScalarType()); assert(SrcBitWidth && "SrcBitWidth can't be zero"); - KnownZero = KnownZero.zextOrTrunc(SrcBitWidth); - KnownOne = KnownOne.zextOrTrunc(SrcBitWidth); - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); - KnownZero = KnownZero.zextOrTrunc(BitWidth); - KnownOne = KnownOne.zextOrTrunc(BitWidth); + KnownZero1 = KnownZero1.zextOrTrunc(SrcBitWidth); + KnownOne1 = KnownOne1.zextOrTrunc(SrcBitWidth); + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); + KnownZero1 = KnownZero1.zextOrTrunc(BitWidth); + KnownOne1 = KnownOne1.zextOrTrunc(BitWidth); // Any top bits are known to be zero. if (BitWidth > SrcBitWidth) - KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); + KnownZero1 |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); break; } case Instruction::BitCast: { @@ -1185,7 +1187,7 @@ // TODO: For now, not handling conversions like: // (bitcast i64 %x to <2 x i32>) !I->getType()->isVectorTy()) { - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); break; } break; @@ -1194,28 +1196,28 @@ // Compute the bits in the result that are not present in the input. unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits(); - KnownZero = KnownZero.trunc(SrcBitWidth); - KnownOne = KnownOne.trunc(SrcBitWidth); - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); - KnownZero = KnownZero.zext(BitWidth); - KnownOne = KnownOne.zext(BitWidth); + KnownZero1 = KnownZero1.trunc(SrcBitWidth); + KnownOne1 = KnownOne1.trunc(SrcBitWidth); + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); + KnownZero1 = KnownZero1.zext(BitWidth); + KnownOne1 = KnownOne1.zext(BitWidth); // If the sign bit of the input is known set or clear, then we know the // top bits of the result. - if (KnownZero[SrcBitWidth-1]) // Input sign bit known zero - KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); - else if (KnownOne[SrcBitWidth-1]) // Input sign bit known set - KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); + if (KnownZero1[SrcBitWidth-1]) // Input sign bit known zero + KnownZero1 |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); + else if (KnownOne1[SrcBitWidth-1]) // Input sign bit known set + KnownOne1 |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); break; } case Instruction::Shl: // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 if (ConstantInt *SA = dyn_cast(I->getOperand(1))) { uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); - KnownZero <<= ShiftAmt; - KnownOne <<= ShiftAmt; - KnownZero |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); + KnownZero1 <<= ShiftAmt; + KnownOne1 <<= ShiftAmt; + KnownZero1 |= APInt::getLowBitsSet(BitWidth, ShiftAmt); // low bits known 0 } break; case Instruction::LShr: @@ -1225,11 +1227,11 @@ uint64_t ShiftAmt = SA->getLimitedValue(BitWidth); // Unsigned shift right. - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); - KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); - KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); + KnownZero1 = APIntOps::lshr(KnownZero1, ShiftAmt); + KnownOne1 = APIntOps::lshr(KnownOne1, ShiftAmt); // high bits known zero. - KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); + KnownZero1 |= APInt::getHighBitsSet(BitWidth, ShiftAmt); } break; case Instruction::AShr: @@ -1239,28 +1241,28 @@ uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1); // Signed shift right. - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); - KnownZero = APIntOps::lshr(KnownZero, ShiftAmt); - KnownOne = APIntOps::lshr(KnownOne, ShiftAmt); + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); + KnownZero1 = APIntOps::lshr(KnownZero1, ShiftAmt); + KnownOne1 = APIntOps::lshr(KnownOne1, ShiftAmt); APInt HighBits(APInt::getHighBitsSet(BitWidth, ShiftAmt)); - if (KnownZero[BitWidth-ShiftAmt-1]) // New bits are known zero. - KnownZero |= HighBits; - else if (KnownOne[BitWidth-ShiftAmt-1]) // New bits are known one. - KnownOne |= HighBits; + if (KnownZero1[BitWidth-ShiftAmt-1]) // New bits are known zero. + KnownZero1 |= HighBits; + else if (KnownOne1[BitWidth-ShiftAmt-1]) // New bits are known one. + KnownOne1 |= HighBits; } break; case Instruction::Sub: { bool NSW = cast(I)->hasNoSignedWrap(); computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, - KnownZero, KnownOne, KnownZero2, KnownOne2, DL, + KnownZero1, KnownOne1, KnownZero2, KnownOne2, DL, Depth, Q); break; } case Instruction::Add: { bool NSW = cast(I)->hasNoSignedWrap(); computeKnownBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, - KnownZero, KnownOne, KnownZero2, KnownOne2, DL, + KnownZero1, KnownOne1, KnownZero2, KnownOne2, DL, Depth, Q); break; } @@ -1273,32 +1275,32 @@ Q); // The low bits of the first operand are unchanged by the srem. - KnownZero = KnownZero2 & LowBits; - KnownOne = KnownOne2 & LowBits; + KnownZero1 = KnownZero2 & LowBits; + KnownOne1 = KnownOne2 & LowBits; // If the first operand is non-negative or has all low bits zero, then // the upper bits are all zero. if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) - KnownZero |= ~LowBits; + KnownZero1 |= ~LowBits; // If the first operand is negative and not all low bits are zero, then // the upper bits are all one. if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) - KnownOne |= ~LowBits; + KnownOne1 |= ~LowBits; - assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); + assert((KnownZero1 & KnownOne1) == 0 && "Bits known to be one AND zero?"); } } // The sign bit is the LHS's sign bit, except when the result of the // remainder is zero. - if (KnownZero.isNonNegative()) { + if (KnownZero1.isNonNegative()) { APInt LHSKnownZero(BitWidth, 0), LHSKnownOne(BitWidth, 0); computeKnownBits(I->getOperand(0), LHSKnownZero, LHSKnownOne, DL, Depth + 1, Q); // If it's known zero, our sign bit is also zero. if (LHSKnownZero.isNegative()) - KnownZero.setBit(BitWidth - 1); + KnownZero1.setBit(BitWidth - 1); } break; @@ -1307,23 +1309,23 @@ APInt RA = Rem->getValue(); if (RA.isPowerOf2()) { APInt LowBits = (RA - 1); - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); - KnownZero |= ~LowBits; - KnownOne &= LowBits; + KnownZero1 |= ~LowBits; + KnownOne1 &= LowBits; break; } } // Since the result is less than or equal to either operand, any leading // zero bits in either operand must also exist in the result. - computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); + computeKnownBits(I->getOperand(0), KnownZero1, KnownOne1, DL, Depth + 1, Q); computeKnownBits(I->getOperand(1), KnownZero2, KnownOne2, DL, Depth + 1, Q); - unsigned Leaders = std::max(KnownZero.countLeadingOnes(), + unsigned Leaders = std::max(KnownZero1.countLeadingOnes(), KnownZero2.countLeadingOnes()); - KnownOne.clearAllBits(); - KnownZero = APInt::getHighBitsSet(BitWidth, Leaders); + KnownOne1.clearAllBits(); + KnownZero1 = APInt::getHighBitsSet(BitWidth, Leaders); break; } @@ -1334,7 +1336,7 @@ Align = DL.getABITypeAlignment(AI->getType()->getElementType()); if (Align > 0) - KnownZero = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); + KnownZero1 = APInt::getLowBitsSet(BitWidth, countTrailingZeros(Align)); break; } case Instruction::GetElementPtr: { @@ -1382,7 +1384,7 @@ } } - KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ); + KnownZero1 = APInt::getLowBitsSet(BitWidth, TrailZ); break; } case Instruction::PHI: { @@ -1420,12 +1422,12 @@ computeKnownBits(R, KnownZero2, KnownOne2, DL, Depth + 1, Q); // We need to take the minimum number of known bits - APInt KnownZero3(KnownZero), KnownOne3(KnownOne); + APInt KnownZero3(KnownZero1), KnownOne3(KnownOne1); computeKnownBits(L, KnownZero3, KnownOne3, DL, Depth + 1, Q); - KnownZero = APInt::getLowBitsSet(BitWidth, - std::min(KnownZero2.countTrailingOnes(), - KnownZero3.countTrailingOnes())); + KnownZero1 = APInt::getLowBitsSet( + BitWidth, std::min(KnownZero2.countTrailingOnes(), + KnownZero3.countTrailingOnes())); break; } } @@ -1437,13 +1439,13 @@ // Otherwise take the unions of the known bit sets of the operands, // taking conservative care to avoid excessive recursion. - if (Depth < MaxDepth - 1 && !KnownZero && !KnownOne) { + if (Depth < MaxDepth - 1 && !KnownZero1 && !KnownOne1) { // Skip if every incoming value references to ourself. if (dyn_cast_or_null(P->hasConstantValue())) break; - KnownZero = APInt::getAllOnesValue(BitWidth); - KnownOne = APInt::getAllOnesValue(BitWidth); + KnownZero1 = APInt::getAllOnesValue(BitWidth); + KnownOne1 = APInt::getAllOnesValue(BitWidth); for (Value *IncValue : P->incoming_values()) { // Skip direct self references. if (IncValue == P) continue; @@ -1454,11 +1456,11 @@ // want to waste time spinning around in loops. computeKnownBits(IncValue, KnownZero2, KnownOne2, DL, MaxDepth - 1, Q); - KnownZero &= KnownZero2; - KnownOne &= KnownOne2; + KnownZero1 &= KnownZero2; + KnownOne1 &= KnownOne2; // If all bits have been ruled out, there's no need to check // more operands. - if (!KnownZero && !KnownOne) + if (!KnownZero1 && !KnownOne1) break; } } @@ -1467,7 +1469,7 @@ case Instruction::Call: case Instruction::Invoke: if (MDNode *MD = cast(I)->getMetadata(LLVMContext::MD_range)) - computeKnownBitsFromRangeMetadata(*MD, KnownZero); + computeKnownBitsFromRangeMetadata(*MD, KnownZero1); // If a range metadata is attached to this IntrinsicInst, intersect the // explicit range specified by the metadata and the implicit range of // the intrinsic. @@ -1480,16 +1482,16 @@ // If this call is undefined for 0, the result will be less than 2^n. if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) LowBits -= 1; - KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); + KnownZero1 |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); break; } case Intrinsic::ctpop: { unsigned LowBits = Log2_32(BitWidth)+1; - KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); + KnownZero1 |= APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); break; } case Intrinsic::x86_sse42_crc32_64_64: - KnownZero |= APInt::getHighBitsSet(64, 32); + KnownZero1 |= APInt::getHighBitsSet(64, 32); break; } } @@ -1497,26 +1499,28 @@ case Instruction::ExtractValue: if (IntrinsicInst *II = dyn_cast(I->getOperand(0))) { ExtractValueInst *EVI = cast(I); - if (EVI->getNumIndices() != 1) break; + if (EVI->getNumIndices() != 1) + break; if (EVI->getIndices()[0] == 0) { switch (II->getIntrinsicID()) { - default: break; + default: + break; case Intrinsic::uadd_with_overflow: case Intrinsic::sadd_with_overflow: - computeKnownBitsAddSub(true, II->getArgOperand(0), - II->getArgOperand(1), false, KnownZero, - KnownOne, KnownZero2, KnownOne2, DL, Depth, Q); + computeKnownBitsAddSub( + true, II->getArgOperand(0), II->getArgOperand(1), false, + KnownZero1, KnownOne1, KnownZero2, KnownOne2, DL, Depth, Q); break; case Intrinsic::usub_with_overflow: case Intrinsic::ssub_with_overflow: - computeKnownBitsAddSub(false, II->getArgOperand(0), - II->getArgOperand(1), false, KnownZero, - KnownOne, KnownZero2, KnownOne2, DL, Depth, Q); + computeKnownBitsAddSub( + false, II->getArgOperand(0), II->getArgOperand(1), false, + KnownZero1, KnownOne1, KnownZero2, KnownOne2, DL, Depth, Q); break; case Intrinsic::umul_with_overflow: case Intrinsic::smul_with_overflow: computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false, - KnownZero, KnownOne, KnownZero2, KnownOne2, DL, + KnownZero1, KnownOne1, KnownZero2, KnownOne2, DL, Depth, Q); break; } @@ -1524,6 +1528,8 @@ } } + KnownZero |= KnownZero1; + KnownOne |= KnownOne1; assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); } Index: test/Analysis/ValueTracking/assume.ll =================================================================== --- /dev/null +++ test/Analysis/ValueTracking/assume.ll @@ -0,0 +1,14 @@ +; RUN: opt < %s -instcombine -S | FileCheck %s + +define i32 @assume_add(i32 %a, i32 %b) { +; CHECK-LABEL: @assume_add( + %1 = add i32 %a, %b + %last_two_digits = and i32 %1, 3 + %2 = icmp eq i32 %last_two_digits, 0 + call void @llvm.assume(i1 %2) + %3 = add i32 %1, 3 +; CHECK: %3 = or i32 %1, 3 + ret i32 %3 +} + +declare void @llvm.assume(i1)