Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -6597,11 +6597,38 @@ const Instruction * ScalarEvolution::getDefiningScopeBound(ArrayRef Ops) { + // Do a bounded search of the def relation of the requested SCEVs. + SmallSet Visited; + SmallVector Worklist; + auto pushOp = [&](const SCEV *S) { + if (!Visited.insert(S).second) + return; + // Threshold of 20 here is arbitrary. + if (Visited.size() > 30) + return; + Worklist.push_back(S); + }; + + for (auto *S : Ops) + pushOp(S); + const Instruction *Bound = &*F.getEntryBlock().begin(); - for (auto *S : Ops) { - auto *DefI = getDefiningScopeBound(S); - if (DT.dominates(Bound, DefI)) - Bound = DefI; + while (!Worklist.empty()) { + auto *S = Worklist.pop_back_val(); + if (isa(S) || isa(S) || isa(S)) { + auto *DefI = getDefiningScopeBound(S); + if (DT.dominates(Bound, DefI)) + Bound = DefI; + } if (auto *S2 = dyn_cast(S)) + for (auto *Op : S2->operands()) + pushOp(Op); + else if (auto *S2 = dyn_cast(S)) + for (auto *Op : S2->operands()) + pushOp(Op); + else if (auto *S2 = dyn_cast(S)) + for (auto *Op : S2->operands()) + pushOp(Op); + } return Bound; } @@ -6668,9 +6695,7 @@ SCEVOps.push_back(getSCEV(Op)); } auto *DefI = getDefiningScopeBound(SCEVOps); - if (isGuaranteedToTransferExecutionTo(DefI, I)) - return true; - return false; + return isGuaranteedToTransferExecutionTo(DefI, I); } bool ScalarEvolution::isAddRecNeverPoison(const Instruction *I, const Loop *L) { Index: llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll +++ llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll @@ -1672,102 +1672,99 @@ @gD = external global i32 -define noundef i32 @add-recurse() { -; CHECK-LABEL: 'add-recurse' -; CHECK-NEXT: Classifying expressions for: @add-recurse +define noundef i64 @add-zext-recurse() { +; CHECK-LABEL: 'add-zext-recurse' +; CHECK-NEXT: Classifying expressions for: @add-zext-recurse ; CHECK-NEXT: %a = load i32, i32* @gA, align 4 ; CHECK-NEXT: --> %a U: full-set S: full-set -; CHECK-NEXT: %b = load i32, i32* @gB, align 4 -; CHECK-NEXT: --> %b U: full-set S: full-set -; CHECK-NEXT: %c = load i32, i32* @gC, align 4 -; CHECK-NEXT: --> %c U: full-set S: full-set -; CHECK-NEXT: %d = load i32, i32* @gD, align 4 -; CHECK-NEXT: --> %d U: full-set S: full-set -; CHECK-NEXT: %x = add i32 %a, %b -; CHECK-NEXT: --> (%a + %b) U: full-set S: full-set -; CHECK-NEXT: %y = add i32 %c, %d -; CHECK-NEXT: --> (%c + %d) U: full-set S: full-set -; CHECK-NEXT: %res = add nuw i32 %x, %y -; CHECK-NEXT: --> (%a + %b + %c + %d) U: full-set S: full-set -; CHECK-NEXT: Determining loop execution counts for: @add-recurse +; CHECK-NEXT: %x = zext i32 %a to i64 +; CHECK-NEXT: --> (zext i32 %a to i64) U: [0,4294967296) S: [0,4294967296) +; CHECK-NEXT: %res = add nuw i64 %x, 1 +; CHECK-NEXT: --> (1 + (zext i32 %a to i64)) U: [1,4294967297) S: [1,4294967297) +; CHECK-NEXT: Determining loop execution counts for: @add-zext-recurse ; call void @foo() %a = load i32, i32* @gA - %b = load i32, i32* @gB - %c = load i32, i32* @gC - %d = load i32, i32* @gD + %x = zext i32 %a to i64 + %res = add nuw i64 %x, 1 + ret i64 %res +} - %x = add i32 %a, %b - %y = add i32 %c, %d - %res = add nuw i32 %x, %y - ret i32 %res +define noundef i64 @add-sext-recurse() { +; CHECK-LABEL: 'add-sext-recurse' +; CHECK-NEXT: Classifying expressions for: @add-sext-recurse +; CHECK-NEXT: %a = load i32, i32* @gA, align 4 +; CHECK-NEXT: --> %a U: full-set S: full-set +; CHECK-NEXT: %x = sext i32 %a to i64 +; CHECK-NEXT: --> (sext i32 %a to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648) +; CHECK-NEXT: %res = add nuw i64 %x, 1 +; CHECK-NEXT: --> (1 + (sext i32 %a to i64)) U: [1,0) S: [-2147483647,2147483649) +; CHECK-NEXT: Determining loop execution counts for: @add-sext-recurse +; + call void @foo() + %a = load i32, i32* @gA + %x = sext i32 %a to i64 + %res = add nuw i64 %x, 1 + ret i64 %res } -define noundef i32 @sub-recurse() { -; CHECK-LABEL: 'sub-recurse' -; CHECK-NEXT: Classifying expressions for: @sub-recurse +define noundef i16 @add-trunc-recurse() { +; CHECK-LABEL: 'add-trunc-recurse' +; CHECK-NEXT: Classifying expressions for: @add-trunc-recurse ; CHECK-NEXT: %a = load i32, i32* @gA, align 4 ; CHECK-NEXT: --> %a U: full-set S: full-set -; CHECK-NEXT: %b = load i32, i32* @gB, align 4 -; CHECK-NEXT: --> %b U: full-set S: full-set -; CHECK-NEXT: %c = load i32, i32* @gC, align 4 -; CHECK-NEXT: --> %c U: full-set S: full-set -; CHECK-NEXT: %d = load i32, i32* @gD, align 4 -; CHECK-NEXT: --> %d U: full-set S: full-set -; CHECK-NEXT: %x = sub nuw i32 %a, %b -; CHECK-NEXT: --> ((-1 * %b) + %a) U: full-set S: full-set -; CHECK-NEXT: %y = sub nuw i32 %c, %d -; CHECK-NEXT: --> ((-1 * %d) + %c) U: full-set S: full-set -; CHECK-NEXT: %res = sub nuw i32 %x, %y -; CHECK-NEXT: --> ((-1 * %b) + (-1 * %c) + %a + %d) U: full-set S: full-set -; CHECK-NEXT: Determining loop execution counts for: @sub-recurse +; CHECK-NEXT: %x = trunc i32 %a to i16 +; CHECK-NEXT: --> (trunc i32 %a to i16) U: full-set S: full-set +; CHECK-NEXT: %res = add nuw i16 %x, 1 +; CHECK-NEXT: --> (1 + (trunc i32 %a to i16)) U: [1,0) S: [1,0) +; CHECK-NEXT: Determining loop execution counts for: @add-trunc-recurse ; call void @foo() %a = load i32, i32* @gA - %b = load i32, i32* @gB - %c = load i32, i32* @gC - %d = load i32, i32* @gD + %x = trunc i32 %a to i16 + %res = add nuw i16 %x, 1 + ret i16 %res +} - %x = sub nuw i32 %a, %b - %y = sub nuw i32 %c, %d - %res = sub nuw i32 %x, %y +define noundef i32 @add-udiv-recurse() { +; CHECK-LABEL: 'add-udiv-recurse' +; CHECK-NEXT: Classifying expressions for: @add-udiv-recurse +; CHECK-NEXT: %a = load i32, i32* @gA, align 4 +; CHECK-NEXT: --> %a U: full-set S: full-set +; CHECK-NEXT: %x = udiv i32 %a, 3 +; CHECK-NEXT: --> (%a /u 3) U: [0,1431655766) S: [0,1431655766) +; CHECK-NEXT: %res = add nuw i32 %x, 1 +; CHECK-NEXT: --> (1 + (%a /u 3)) U: [1,1431655767) S: [1,1431655767) +; CHECK-NEXT: Determining loop execution counts for: @add-udiv-recurse +; + call void @foo() + %a = load i32, i32* @gA + %x = udiv i32 %a, 3 + %res = add nuw i32 %x, 1 ret i32 %res } -define noundef i32 @mul-recurse() { -; CHECK-LABEL: 'mul-recurse' -; CHECK-NEXT: Classifying expressions for: @mul-recurse +define noundef i32 @add-mul-recurse() { +; CHECK-LABEL: 'add-mul-recurse' +; CHECK-NEXT: Classifying expressions for: @add-mul-recurse ; CHECK-NEXT: %a = load i32, i32* @gA, align 4 ; CHECK-NEXT: --> %a U: full-set S: full-set -; CHECK-NEXT: %b = load i32, i32* @gB, align 4 -; CHECK-NEXT: --> %b U: full-set S: full-set -; CHECK-NEXT: %c = load i32, i32* @gC, align 4 -; CHECK-NEXT: --> %c U: full-set S: full-set -; CHECK-NEXT: %d = load i32, i32* @gD, align 4 -; CHECK-NEXT: --> %d U: full-set S: full-set -; CHECK-NEXT: %x = mul nuw i32 %a, %b -; CHECK-NEXT: --> (%a * %b) U: full-set S: full-set -; CHECK-NEXT: %y = mul nuw i32 %c, %d -; CHECK-NEXT: --> (%c * %d) U: full-set S: full-set -; CHECK-NEXT: %res = mul nuw i32 %x, %y -; CHECK-NEXT: --> (%a * %b * %c * %d) U: full-set S: full-set -; CHECK-NEXT: Determining loop execution counts for: @mul-recurse +; CHECK-NEXT: %x = mul i32 %a, 3 +; CHECK-NEXT: --> (3 * %a) U: full-set S: full-set +; CHECK-NEXT: %res = add nuw i32 %x, 1 +; CHECK-NEXT: --> (1 + (3 * %a)) U: [1,0) S: [1,0) +; CHECK-NEXT: Determining loop execution counts for: @add-mul-recurse ; call void @foo() %a = load i32, i32* @gA - %b = load i32, i32* @gB - %c = load i32, i32* @gC - %d = load i32, i32* @gD - - %x = mul nuw i32 %a, %b - %y = mul nuw i32 %c, %d - %res = mul nuw i32 %x, %y + %x = mul i32 %a, 3 + %res = add nuw i32 %x, 1 ret i32 %res } -define noundef i32 @udiv-recurse() { -; CHECK-LABEL: 'udiv-recurse' -; CHECK-NEXT: Classifying expressions for: @udiv-recurse +define noundef i32 @add-recurse-inline() { +; CHECK-LABEL: 'add-recurse-inline' +; CHECK-NEXT: Classifying expressions for: @add-recurse-inline ; CHECK-NEXT: %a = load i32, i32* @gA, align 4 ; CHECK-NEXT: --> %a U: full-set S: full-set ; CHECK-NEXT: %b = load i32, i32* @gB, align 4 @@ -1776,13 +1773,13 @@ ; CHECK-NEXT: --> %c U: full-set S: full-set ; CHECK-NEXT: %d = load i32, i32* @gD, align 4 ; CHECK-NEXT: --> %d U: full-set S: full-set -; CHECK-NEXT: %x = add i32 %a, %b -; CHECK-NEXT: --> (%a + %b) U: full-set S: full-set -; CHECK-NEXT: %y = add i32 %c, %d -; CHECK-NEXT: --> (%c + %d) U: full-set S: full-set -; CHECK-NEXT: %res = udiv exact i32 %x, %y -; CHECK-NEXT: --> ((%a + %b) /u (%c + %d)) U: full-set S: full-set -; CHECK-NEXT: Determining loop execution counts for: @udiv-recurse +; CHECK-NEXT: %x = add nuw i32 %a, %b +; CHECK-NEXT: --> (%a + %b) U: full-set S: full-set +; CHECK-NEXT: %y = add nuw i32 %c, %d +; CHECK-NEXT: --> (%c + %d) U: full-set S: full-set +; CHECK-NEXT: %res = add nuw i32 %x, %y +; CHECK-NEXT: --> (%a + %b + %c + %d) U: full-set S: full-set +; CHECK-NEXT: Determining loop execution counts for: @add-recurse-inline ; call void @foo() %a = load i32, i32* @gA @@ -1790,8 +1787,9 @@ %c = load i32, i32* @gC %d = load i32, i32* @gD - %x = add i32 %a, %b - %y = add i32 %c, %d - %res = udiv exact i32 %x, %y + %x = add nuw i32 %a, %b + %y = add nuw i32 %c, %d + %res = add nuw i32 %x, %y ret i32 %res } +