Index: llvm/lib/Analysis/ValueTracking.cpp =================================================================== --- llvm/lib/Analysis/ValueTracking.cpp +++ llvm/lib/Analysis/ValueTracking.cpp @@ -536,7 +536,29 @@ // feeding the assume is trivially true, thus causing the removal of // the assume). - if (Inv->getParent() == CxtI->getParent()) { + auto GuaranteedToExecuteInvFrom = [&](BasicBlock::const_iterator I) { + // We limit the scan distance between the context instruction and the assume + // to avoid a compile-time explosion. This limit is chosen arbitrarily, so + // it can be adjusted if needed (could be turned into a cl::opt). + unsigned ScanLimit = 15; + for (BasicBlock::const_iterator IE(Inv); I != IE; ++I) + if (!isGuaranteedToTransferExecutionToSuccessor(&*I) || --ScanLimit == 0) + return false; + return true; + }; + + const BasicBlock *InvBB = Inv->getParent(); + if (!CxtI) { + // If there is no context instruction, assume the start of the entry block + // as context, and see whether the assume is guaranteed reachable from + // there. + if (InvBB != &InvBB->getParent()->getEntryBlock()) + return false; + + return GuaranteedToExecuteInvFrom(InvBB->begin()); + } + + if (InvBB == CxtI->getParent()) { // If Inv and CtxI are in the same block, check if the assume (Inv) is first // in the BB. if (Inv->comesBefore(CxtI)) @@ -551,22 +573,15 @@ // The context comes first, but they're both in the same block. // Make sure there is nothing in between that might interrupt // the control flow, not even CxtI itself. - // We limit the scan distance between the assume and its context instruction - // to avoid a compile-time explosion. This limit is chosen arbitrarily, so - // it can be adjusted if needed (could be turned into a cl::opt). - unsigned ScanLimit = 15; - for (BasicBlock::const_iterator I(CxtI), IE(Inv); I != IE; ++I) - if (!isGuaranteedToTransferExecutionToSuccessor(&*I) || --ScanLimit == 0) - return false; - - return !isEphemeralValueOf(Inv, CxtI); + return GuaranteedToExecuteInvFrom(CxtI->getIterator()) && + !isEphemeralValueOf(Inv, CxtI); } // Inv and CxtI are in different blocks. if (DT) { if (DT->dominates(Inv, CxtI)) return true; - } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) { + } else if (InvBB == CxtI->getParent()->getSinglePredecessor()) { // We don't have a DT, but this trivially dominates. return true; } @@ -639,9 +654,7 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, unsigned Depth, const Query &Q) { - // Use of assumptions is context-sensitive. If we don't have a context, we - // cannot use them! - if (!Q.AC || !Q.CxtI) + if (!Q.AC) return; unsigned BitWidth = Known.getBitWidth(); @@ -661,8 +674,6 @@ if (!AssumeVH) continue; CallInst *I = cast(AssumeVH); - assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() && - "Got assumption for the wrong function!"); if (Q.isExcluded(I)) continue; Index: llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll +++ llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll @@ -454,15 +454,15 @@ ; CHECK-LABEL: 'test_guard_and_assume' ; CHECK-NEXT: Classifying expressions for: @test_guard_and_assume ; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ 0, %entry ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,4) S: [0,4) Exits: (-1 + %count) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,4) S: [0,4) Exits: (-1 + %count) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %idx = getelementptr inbounds i32, i32* %data, i64 %iv -; CHECK-NEXT: --> {%data,+,4}<%loop> U: full-set S: full-set Exits: (-4 + (4 * %count) + %data) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {%data,+,4}<%loop> U: full-set S: full-set Exits: (-4 + (4 * %count) + %data) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %iv.next = add nuw i64 %iv, 1 ; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,5) S: [1,5) Exits: %count LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test_guard_and_assume -; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %count) +; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %count) ; CHECK-NEXT: Loop %loop: max backedge-taken count is 3 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-1 + %count) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (-1 + %count) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; Index: llvm/test/Analysis/ScalarEvolution/ranges.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/ranges.ll +++ llvm/test/Analysis/ScalarEvolution/ranges.ll @@ -43,7 +43,7 @@ ; CHECK-LABEL: 'shl' ; CHECK-NEXT: Classifying expressions for: @shl ; CHECK-NEXT: %res = shl i32 %a, 2 -; CHECK-NEXT: --> (4 * %a) U: [0,-3) S: [-2147483648,2147483645) +; CHECK-NEXT: --> (4 * %a) U: [0,4093) S: [0,4093) ; CHECK-NEXT: Determining loop execution counts for: @shl ; %res = shl i32 %a, 2 @@ -56,7 +56,7 @@ ; CHECK-LABEL: 'lshr' ; CHECK-NEXT: Classifying expressions for: @lshr ; CHECK-NEXT: %res = lshr i32 %a, 31 -; CHECK-NEXT: --> (%a /u -2147483648) U: [0,2) S: [0,2) +; CHECK-NEXT: --> (%a /u -2147483648) U: [0,1) S: [0,1) ; CHECK-NEXT: Determining loop execution counts for: @lshr ; %res = lshr i32 %a, 31 @@ -70,7 +70,7 @@ ; CHECK-LABEL: 'udiv' ; CHECK-NEXT: Classifying expressions for: @udiv ; CHECK-NEXT: %res = udiv i32 %a, -2147483648 -; CHECK-NEXT: --> (%a /u -2147483648) U: [0,2) S: [0,2) +; CHECK-NEXT: --> (%a /u -2147483648) U: [0,1) S: [0,1) ; CHECK-NEXT: Determining loop execution counts for: @udiv ; %res = udiv i32 %a, 2147483648 @@ -83,7 +83,7 @@ ; CHECK-LABEL: 'sext' ; CHECK-NEXT: Classifying expressions for: @sext ; CHECK-NEXT: %res = sext i8 %a to i64 -; CHECK-NEXT: --> (sext i8 %a to i64) U: [-128,128) S: [-128,128) +; CHECK-NEXT: --> (zext i8 %a to i64) U: [0,128) S: [0,128) ; CHECK-NEXT: Determining loop execution counts for: @sext ; %res = sext i8 %a to i64 @@ -96,7 +96,7 @@ ; CHECK-LABEL: 'zext' ; CHECK-NEXT: Classifying expressions for: @zext ; CHECK-NEXT: %res = zext i8 %a to i64 -; CHECK-NEXT: --> (zext i8 %a to i64) U: [0,256) S: [0,256) +; CHECK-NEXT: --> (zext i8 %a to i64) U: [0,128) S: [0,128) ; CHECK-NEXT: Determining loop execution counts for: @zext ; %res = zext i8 %a to i64 Index: llvm/test/Transforms/SimplifyCFG/pr46638.ll =================================================================== --- llvm/test/Transforms/SimplifyCFG/pr46638.ll +++ llvm/test/Transforms/SimplifyCFG/pr46638.ll @@ -13,9 +13,7 @@ ; CHECK-NEXT: call void @dummy(i32 [[EXT]]) ; CHECK-NEXT: ret void ; CHECK: true2.critedge: -; CHECK-NEXT: [[CMP2_C:%.*]] = icmp sgt i32 [[X]], 0 -; CHECK-NEXT: [[EXT_C:%.*]] = zext i1 [[CMP2_C]] to i32 -; CHECK-NEXT: call void @dummy(i32 [[EXT_C]]) +; CHECK-NEXT: call void @dummy(i32 0) ; CHECK-NEXT: call void @dummy(i32 2) ; CHECK-NEXT: ret void ; Index: llvm/unittests/Analysis/ValueTrackingTest.cpp =================================================================== --- llvm/unittests/Analysis/ValueTrackingTest.cpp +++ llvm/unittests/Analysis/ValueTrackingTest.cpp @@ -1568,6 +1568,65 @@ EXPECT_EQ(Known.getMaxValue(), 575); } +TEST_F(ValueTrackingTest, ComputeKnownBitsArgNoCxtI) { + // Take advantage of assumptions on arguments w/o a context. + parseAssembly( + "define void @test(i32 %x) {\n" + " %A = and i32 %x, 31\n" + " %c = icmp eq i32 %A, 0\n" + " call void @llvm.assume(i1 %c)\n" + " ret void\n" + "}\n" + "declare void @llvm.assume(i1)\n"); + AssumptionCache AC(*F); + KnownBits Known = computeKnownBits(F->getArg(0), M->getDataLayout(), + /* Depth */ 0, &AC, nullptr); + EXPECT_EQ(Known.Zero.getZExtValue(), 31u); + EXPECT_EQ(Known.One.getZExtValue(), 0u); +} + +TEST_F(ValueTrackingTest, ComputeKnownBitsArgNoCxtIFront) { + // Take advantage of assumptions on arguments w/o a context. + parseAssembly( + "define void @test(i32 %x) {\n" + " %e = mul i32 %x, 7" + " %A = and i32 %x, 31\n" + " %c = icmp eq i32 %A, 0\n" + " call void @llvm.assume(i1 %c)\n" + " call void @may.not.transfer.execution.to.successor()\n" + " ret void\n" + "}\n" + "declare void @llvm.assume(i1)\n" + "declare void @may.not.transfer.execution.to.successor()\n"); + AssumptionCache AC(*F); + KnownBits Known = computeKnownBits(F->getArg(0), M->getDataLayout(), + /* Depth */ 0, &AC, nullptr); + EXPECT_EQ(Known.Zero.getZExtValue(), 31u); + EXPECT_EQ(Known.One.getZExtValue(), 0u); +} + +TEST_F(ValueTrackingTest, ComputeKnownBitsArgNoCxtIInvalid) { + // Do not take advantage of assumptions on arguments w/o a context if control + // is not guaranteed to reach them. + parseAssembly( + "define void @test(i32 %x) {\n" + " %e = mul i32 %x, 7" + " %A = and i32 %x, 31\n" + " %c = icmp eq i32 %A, 0\n" + " call void @may.not.transfer.execution.to.successor()\n" + " call void @llvm.assume(i1 %c)\n" + " call void @may.not.transfer.execution.to.successor()\n" + " ret void\n" + "}\n" + "declare void @llvm.assume(i1)\n" + "declare void @may.not.transfer.execution.to.successor()\n"); + AssumptionCache AC(*F); + KnownBits Known = computeKnownBits(F->getArg(0), M->getDataLayout(), + /* Depth */ 0, &AC, nullptr); + EXPECT_EQ(Known.Zero.getZExtValue(), 0u); + EXPECT_EQ(Known.One.getZExtValue(), 0u); +} + class IsBytewiseValueTest : public ValueTrackingTest, public ::testing::WithParamInterface< std::pair> {