Index: lib/Analysis/InstructionSimplify.cpp =================================================================== --- lib/Analysis/InstructionSimplify.cpp +++ lib/Analysis/InstructionSimplify.cpp @@ -4027,6 +4027,17 @@ break; } + // In general, it is possible for computeKnownBits to determine all bits in a + // value even when the operands are not all constants. + if (!Result && I->getType()->isIntegerTy()) { + unsigned BitWidth = I->getType()->getScalarSizeInBits(); + APInt KnownZero(BitWidth, 0); + APInt KnownOne(BitWidth, 0); + computeKnownBits(I, KnownZero, KnownOne, DL, /*Depth*/0, AC, I, DT); + if ((KnownZero | KnownOne).isAllOnesValue()) + Result = ConstantInt::get(I->getContext(), KnownOne); + } + /// If called on unreachable code, the above logic may report that the /// instruction simplified to itself. Make life easier for users by /// detecting that case here, returning a safe value instead. Index: lib/Analysis/ValueTracking.cpp =================================================================== --- lib/Analysis/ValueTracking.cpp +++ lib/Analysis/ValueTracking.cpp @@ -382,6 +382,12 @@ SmallPtrSet Visited; SmallPtrSet EphValues; + // The instruction defining an assumption's condition itself is always + // considered ephemeral to that assumption (even if it has other + // non-ephemeral users). See r246696's test case for an example. + if (std::find(I->op_begin(), I->op_end(), E) != I->op_end()) + return true; + while (!WorkSet.empty()) { const Value *V = WorkSet.pop_back_val(); if (!Visited.insert(V).second) @@ -949,6 +955,56 @@ } } +template +static void computeKnownBitsFromShiftOperator(Operator *I, + APInt &KnownZero, APInt &KnownOne, + APInt &KnownZero2, APInt &KnownOne2, + const DataLayout &DL, unsigned Depth, const Query &Q, + KZFunctor KZF, KOFunctor KOF) { + unsigned BitWidth = KnownZero.getBitWidth(); + + if (ConstantInt *SA = dyn_cast(I->getOperand(1))) { + unsigned ShiftAmt = SA->getLimitedValue(BitWidth-1); + + computeKnownBits(I->getOperand(0), KnownZero, KnownOne, DL, Depth + 1, Q); + KnownZero = KZF(KnownZero, ShiftAmt); + KnownOne = KOF(KnownOne, ShiftAmt); + return; + } + + computeKnownBits(I->getOperand(1), KnownZero, KnownOne, DL, Depth + 1, Q); + + uint64_t ShiftAmtKZ = KnownZero.getLimitedValue(); + uint64_t ShiftAmtKO = KnownOne.getLimitedValue(); + KnownZero.clearAllBits(), KnownOne.clearAllBits(); + + // Early exit if we can't constrain any well-defined shift amount. + if (!(ShiftAmtKZ & (BitWidth-1)) && !(ShiftAmtKO & (BitWidth-1))) + return; + + computeKnownBits(I->getOperand(0), KnownZero2, KnownOne2, DL, Depth + 1, Q); + + bool FirstAllowed = true; + for (unsigned ShiftAmt = 0; ShiftAmt < BitWidth; ++ShiftAmt) { + // Combine the shifted known input bits only for those shift amounts + // compatible with its known constraints. + if ((ShiftAmt & ~ShiftAmtKZ) != ShiftAmt) + continue; + if ((ShiftAmt | ShiftAmtKO) != ShiftAmt) + continue; + + if (FirstAllowed) { + KnownZero = KZF(KnownZero2, ShiftAmt); + KnownOne = KOF(KnownOne2, ShiftAmt); + FirstAllowed = false; + continue; + } + + KnownZero &= KZF(KnownZero2, ShiftAmt); + KnownOne &= KOF(KnownOne2, ShiftAmt); + } +} + static void computeKnownBitsFromOperator(Operator *I, APInt &KnownZero, APInt &KnownOne, const DataLayout &DL, unsigned Depth, const Query &Q) { @@ -1085,48 +1141,60 @@ KnownOne |= APInt::getHighBitsSet(BitWidth, BitWidth - SrcBitWidth); break; } - case Instruction::Shl: + 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 - } + auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) { + return (KnownZero << ShiftAmt) | + APInt::getLowBitsSet(BitWidth, ShiftAmt); // Low bits known 0. + }; + + auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) { + return KnownOne << ShiftAmt; + }; + + computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, + KnownZero2, KnownOne2, DL, Depth, Q, + KZF, KOF); break; - case Instruction::LShr: + } + case Instruction::LShr: { // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 - if (ConstantInt *SA = dyn_cast(I->getOperand(1))) { - // Compute the new bits that are at the top now. - 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); - // high bits known zero. - KnownZero |= APInt::getHighBitsSet(BitWidth, ShiftAmt); - } + auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) { + return APIntOps::lshr(KnownZero, ShiftAmt) | + // High bits known zero. + APInt::getHighBitsSet(BitWidth, ShiftAmt); + }; + + auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) { + return APIntOps::lshr(KnownOne, ShiftAmt); + }; + + computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, + KnownZero2, KnownOne2, DL, Depth, Q, + KZF, KOF); break; - case Instruction::AShr: + } + case Instruction::AShr: { // (ashr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 - if (ConstantInt *SA = dyn_cast(I->getOperand(1))) { - // Compute the new bits that are at the top now. - 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); - - 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; - } + auto KZF = [BitWidth](const APInt &KnownZero, unsigned ShiftAmt) { + APInt KZ = APIntOps::lshr(KnownZero, ShiftAmt); + if (KZ[BitWidth-ShiftAmt-1]) // New bits are known zero. + KZ |= APInt::getHighBitsSet(BitWidth, ShiftAmt); + return KZ; + }; + + auto KOF = [BitWidth](const APInt &KnownOne, unsigned ShiftAmt) { + APInt KO = APIntOps::lshr(KnownOne, ShiftAmt); + if (KO[BitWidth-ShiftAmt-1]) // // New bits are known one. + KO |= APInt::getHighBitsSet(BitWidth, ShiftAmt); + return KO; + }; + + computeKnownBitsFromShiftOperator(I, KnownZero, KnownOne, + KnownZero2, KnownOne2, DL, Depth, Q, + KZF, KOF); break; + } case Instruction::Sub: { bool NSW = cast(I)->hasNoSignedWrap(); computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, Index: lib/Transforms/InstCombine/InstructionCombining.cpp =================================================================== --- lib/Transforms/InstCombine/InstructionCombining.cpp +++ lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2725,6 +2725,27 @@ } } + // In general, it is possible for computeKnownBits to determine all bits in a + // value even when the operands are not all constants. + if (!I->use_empty() && I->getType()->isIntegerTy()) { + unsigned BitWidth = I->getType()->getScalarSizeInBits(); + APInt KnownZero(BitWidth, 0); + APInt KnownOne(BitWidth, 0); + computeKnownBits(I, KnownZero, KnownOne, /*Depth*/0, I); + if ((KnownZero | KnownOne).isAllOnesValue()) { + Constant *C = ConstantInt::get(I->getContext(), KnownOne); + DEBUG(dbgs() << "IC: ConstFold (all bits known) to: " << *C << + " from: " << *I << '\n'); + + // Add operands to the worklist. + ReplaceInstUsesWith(*I, C); + ++NumConstProp; + EraseInstFromFunction(*I); + MadeIRChange = true; + continue; + } + } + // See if we can trivially sink this instruction to a successor basic block. if (I->hasOneUse()) { BasicBlock *BB = I->getParent(); Index: test/Transforms/InstCombine/all-bits-shift.ll =================================================================== --- /dev/null +++ test/Transforms/InstCombine/all-bits-shift.ll @@ -0,0 +1,46 @@ +; RUN: opt -S -instcombine < %s | FileCheck %s +; RUN: opt -S -instsimplify < %s | FileCheck %s +target datalayout = "E-m:e-i64:64-n32:64" +target triple = "powerpc64-unknown-linux-gnu" + +@d = global i32 15, align 4 +@b = global i32* @d, align 8 +@a = common global i32 0, align 4 + +; Function Attrs: nounwind +define signext i32 @main() #1 { +entry: + %0 = load i32*, i32** @b, align 8 + %1 = load i32, i32* @a, align 4 + %lnot = icmp eq i32 %1, 0 + %lnot.ext = zext i1 %lnot to i32 + %shr.i = lshr i32 2072, %lnot.ext + %call.lobit = lshr i32 %shr.i, 7 + %2 = and i32 %call.lobit, 1 + %3 = load i32, i32* %0, align 4 + %or = or i32 %2, %3 + store i32 %or, i32* %0, align 4 + %4 = load i32, i32* @a, align 4 + %lnot.1 = icmp eq i32 %4, 0 + %lnot.ext.1 = zext i1 %lnot.1 to i32 + %shr.i.1 = lshr i32 2072, %lnot.ext.1 + %call.lobit.1 = lshr i32 %shr.i.1, 7 + %5 = and i32 %call.lobit.1, 1 + %or.1 = or i32 %5, %or + store i32 %or.1, i32* %0, align 4 + ret i32 %or.1 + +; Check that both InstCombine and InstSimplify can use computeKnownBits to +; realize that: +; ((2072 >> (L == 0)) >> 7) & 1 +; is always zero. + +; CHECK-LABEL: @main +; CHECK: %[[V1:[0-9]+]] = load i32*, i32** @b, align 8 +; CHECK: %[[V2:[0-9]+]] = load i32, i32* %[[V1]], align 4 +; CHECK: ret i32 %[[V2]] +} + +attributes #0 = { nounwind readnone } +attributes #1 = { nounwind } + Index: test/Transforms/InstCombine/div.ll =================================================================== --- test/Transforms/InstCombine/div.ll +++ test/Transforms/InstCombine/div.ll @@ -270,9 +270,7 @@ %div = udiv <2 x i32> %shr, ret <2 x i32> %div ; CHECK-LABEL: @test31( -; CHECK-NEXT: %[[shr:.*]] = lshr <2 x i32> %x, -; CHECK-NEXT: udiv <2 x i32> %[[shr]], -; CHECK-NEXT: ret <2 x i32> +; CHECK-NEXT: ret <2 x i32> zeroinitializer } define i32 @test32(i32 %a, i32 %b) { Index: test/Transforms/InstCombine/load-combine-metadata.ll =================================================================== --- test/Transforms/InstCombine/load-combine-metadata.ll +++ test/Transforms/InstCombine/load-combine-metadata.ll @@ -17,9 +17,9 @@ ret void } -; CHECK: ![[RANGE]] = !{i32 0, i32 1, i32 8, i32 9} -!0 = !{ i32 0, i32 1 } -!1 = !{ i32 8, i32 9 } +; CHECK: ![[RANGE]] = !{i32 0, i32 5, i32 7, i32 9} +!0 = !{ i32 0, i32 5 } +!1 = !{ i32 7, i32 9 } !2 = !{!2} !3 = !{!3, !2} !4 = !{!4, !2}