Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1536,6 +1536,11 @@ const SCEV *getExact(const Loop *L, ScalarEvolution *SE, SmallVector *Predicates = nullptr) const; + /// Returns whether the exact backedge-taken count of the loop can be + /// computed by call to getExact. If this returns true, then getExact is + /// guaranteed to not return a SCEVCouldNotCompute. + bool canComputeExact(const Loop *L, ScalarEvolution *SE) const; + /// Return the number of times this loop exit may fall through to the back /// edge, or SCEVCouldNotCompute. The loop is guaranteed not to exit via /// this block before this number of iterations, but may exit via another Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -8297,17 +8297,16 @@ (void)NumTripCountsComputed; (void)NumTripCountsNotComputed; #if LLVM_ENABLE_STATS || !defined(NDEBUG) - const SCEV *BEExact = Result.getExact(L, this); - if (BEExact != getCouldNotCompute()) { - assert(isLoopInvariant(BEExact, L) && - isLoopInvariant(Result.getConstantMax(this), L) && - "Computed backedge-taken count isn't loop invariant for loop!"); + // Note that calling getExact here may cause a recursive call to + // getBackedgeTakenInfo which would result in + // 1. different queries made to SCEV in debug and product builds, + // 2. broken caches because the recursive call may erase memoized results + // (which is done later in this function). + if (Result.canComputeExact(L, this)) ++NumTripCountsComputed; - } else if (Result.getConstantMax(this) == getCouldNotCompute() && - isa(L->getHeader()->begin())) { + else if (Result.getConstantMax(this) == getCouldNotCompute()) // Only count loops that have phi nodes as not being computable. ++NumTripCountsNotComputed; - } #endif // LLVM_ENABLE_STATS || !defined(NDEBUG) // Now that we know more about the trip count for this loop, forget any @@ -8489,14 +8488,10 @@ const SCEV * ScalarEvolution::BackedgeTakenInfo::getExact(const Loop *L, ScalarEvolution *SE, SmallVector *Preds) const { - // If any exits were not computable, the loop is not computable. - if (!isComplete() || ExitNotTaken.empty()) + if (!canComputeExact(L, SE)) return SE->getCouldNotCompute(); - const BasicBlock *Latch = L->getLoopLatch(); - // All exiting blocks we have collected must dominate the only backedge. - if (!Latch) - return SE->getCouldNotCompute(); + auto *Latch = L->getLoopLatch(); // All exiting blocks we have gathered dominate loop's latch, so exact trip // count is simply a minimum out of all these calculated exit counts. @@ -8524,6 +8519,16 @@ return SE->getUMinFromMismatchedTypes(Ops, /* Sequential */ true); } +/// Returns whether the exact backedge-taken count of the loop can be +/// computed by call to getExact. If this returns true, then getExact is +/// guaranteed to not return a SCEVCouldNotCompute. +bool ScalarEvolution::BackedgeTakenInfo::canComputeExact( + const Loop *L, ScalarEvolution *SE) const { + // If any exits were not computable, the loop is not computable. + // Also all exiting blocks we have collected must dominate the only backedge. + return isComplete() && !ExitNotTaken.empty() && L->getLoopLatch(); +} + /// Get the exact not taken count for this loop exit. const SCEV * ScalarEvolution::BackedgeTakenInfo::getExact(const BasicBlock *ExitingBlock, Index: llvm/test/Analysis/ScalarEvolution/pr62380.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/pr62380.ll +++ llvm/test/Analysis/ScalarEvolution/pr62380.ll @@ -1,12 +1,54 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2 ; RUN: opt -passes='loop(loop-deletion),loop-mssa(loop-predication,licm,simple-loop-unswitch),loop(loop-predication)' -S < %s | FileCheck %s -; REQUIRES: asserts -; XFAIL: * - target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2" target triple = "x86_64-unknown-linux-gnu" +; Check that we don't crash during ScalarEvolution::getBackedgeInfo query with an +; assertion of dereferencing an end iterator of BackedgeTakenCounts map. +; See https://github.com/llvm/llvm-project/issues/62380 for details. + define void @test(i32 %arg) { +; CHECK-LABEL: define void @test +; CHECK-SAME: (i32 [[ARG:%.*]]) { +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB1:%.*]] +; CHECK: bb1: +; CHECK-NEXT: br label [[BB2:%.*]] +; CHECK: bb2: +; CHECK-NEXT: br i1 false, label [[BB3_PREHEADER:%.*]], label [[BB1]] +; CHECK: bb3.preheader: +; CHECK-NEXT: [[LOAD_LE:%.*]] = load i32, ptr null, align 4 +; CHECK-NEXT: br label [[BB3:%.*]] +; CHECK: bb3.loopexit: +; CHECK-NEXT: br label [[BB3]] +; CHECK: bb3: +; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ [[ADD:%.*]], [[BB3_LOOPEXIT:%.*]] ], [ 0, [[BB3_PREHEADER]] ] +; CHECK-NEXT: [[ADD]] = add i32 [[PHI]], 1 +; CHECK-NEXT: [[ICMP:%.*]] = icmp ult i32 [[PHI]], [[LOAD_LE]] +; CHECK-NEXT: br i1 [[ICMP]], label [[BB5:%.*]], label [[BB4:%.*]] +; CHECK: bb4: +; CHECK-NEXT: ret void +; CHECK: bb5: +; CHECK-NEXT: [[CALL:%.*]] = call i1 @llvm.experimental.widenable.condition() +; CHECK-NEXT: br i1 [[CALL]], label [[BB9_PREHEADER:%.*]], label [[BB14:%.*]] +; CHECK: bb9.preheader: +; CHECK-NEXT: br label [[BB9:%.*]] +; CHECK: bb6: +; CHECK-NEXT: [[ADD7:%.*]] = add i32 [[PHI10:%.*]], 1 +; CHECK-NEXT: [[ICMP8:%.*]] = icmp ugt i32 [[PHI10]], 1 +; CHECK-NEXT: br i1 [[ICMP8]], label [[BB3_LOOPEXIT]], label [[BB9]] +; CHECK: bb9: +; CHECK-NEXT: [[PHI10]] = phi i32 [ [[ADD7]], [[BB6:%.*]] ], [ [[PHI]], [[BB9_PREHEADER]] ] +; CHECK-NEXT: [[ICMP11:%.*]] = icmp ult i32 [[PHI10]], [[ARG]] +; CHECK-NEXT: [[CALL12:%.*]] = call i1 @llvm.experimental.widenable.condition() +; CHECK-NEXT: [[AND:%.*]] = and i1 [[ICMP11]], true +; CHECK-NEXT: br i1 [[AND]], label [[BB6]], label [[BB13:%.*]] +; CHECK: bb13: +; CHECK-NEXT: ret void +; CHECK: bb14: +; CHECK-NEXT: ret void +; bb: br label %bb1