Index: llvm/include/llvm/Analysis/ScalarEvolution.h
===================================================================
--- llvm/include/llvm/Analysis/ScalarEvolution.h
+++ llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1756,6 +1756,12 @@
   BackedgeTakenInfo computeBackedgeTakenCount(const Loop *L,
                                               bool AllowPredicates = false);
 
+  /// Adds the given loop in the cache of users of non-constant SCEVs
+  /// contained in backedge taken info.
+  void updateBackedgeTakenCountUsers(const Loop *L,
+                                     const BackedgeTakenInfo &BTI,
+                                     bool Predicated = false);
+
   /// Compute the number of times the backedge of the specified loop will
   /// execute if it exits via the specified block. If AllowPredicates is set,
   /// this call will try to use a minimal set of SCEV predicates in order to
Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8350,6 +8350,19 @@
       Worklist.push_back(&PN);
 }
 
+void ScalarEvolution::updateBackedgeTakenCountUsers(
+    const Loop *L, const BackedgeTakenInfo &BTI, bool Predicated) {
+  // Remember which SCEVs are used in exit limits for invalidation purposes.
+  // We only care about non-constant SCEVs here, so we can ignore
+  // ConstantMaxNotTaken and MaxBECount, which must be SCEVConstant.
+  for (const auto &ENT : BTI.ExitNotTaken) {
+    if (!isa<SCEVConstant>(ENT.ExactNotTaken))
+      BECountUsers[ENT.ExactNotTaken].insert({L, Predicated});
+    if (!isa<SCEVConstant>(ENT.SymbolicMaxNotTaken))
+      BECountUsers[ENT.SymbolicMaxNotTaken].insert({L, Predicated});
+  }
+}
+
 const ScalarEvolution::BackedgeTakenInfo &
 ScalarEvolution::getPredicatedBackedgeTakenInfo(const Loop *L) {
   auto &BTI = getBackedgeTakenInfo(L);
@@ -8364,6 +8377,8 @@
   BackedgeTakenInfo Result =
       computeBackedgeTakenCount(L, /*AllowPredicates=*/true);
 
+  // Cache the fact that this loop uses SCEVs contained in the computed result.
+  updateBackedgeTakenCountUsers(L, Result, /*Predicated=*/true);
   return PredicatedBackedgeTakenCounts.find(L)->second = std::move(Result);
 }
 
@@ -8419,12 +8434,20 @@
       ConstantEvolutionLoopExitValue.erase(&PN);
   }
 
+  // Cache the fact that this loop uses SCEVs contained in the computed result.
+  // Do this right before returning the result, because we could clear the cache
+  // in other getBackedgeTakenInfo info queries that could happen after the call
+  // to computeBackedgeTakenCount.
+  updateBackedgeTakenCountUsers(L, Result);
+
   // Re-lookup the insert position, since the call to
   // computeBackedgeTakenCount above could result in a
   // recusive call to getBackedgeTakenInfo (on a different
   // loop), which would invalidate the iterator computed
-  // earlier.
-  return BackedgeTakenCounts.find(L)->second = std::move(Result);
+  // earlier. Also the entry for the loop could be deleted during other
+  // getBackedgeTakenInfo queries that could happen in this function after
+  // the computeBackedgeTakenCount call.
+  return BackedgeTakenCounts[L] = std::move(Result);
 }
 
 void ScalarEvolution::forgetAllLoops() {
@@ -8831,17 +8854,6 @@
   // a single exit that must be taken the maximum or zero times.
   bool MaxOrZero = (MustExitMaxOrZero && ExitingBlocks.size() == 1);
 
-  // Remember which SCEVs are used in exit limits for invalidation purposes.
-  // We only care about non-constant SCEVs here, so we can ignore
-  // EL.ConstantMaxNotTaken
-  // and MaxBECount, which must be SCEVConstant.
-  for (const auto &Pair : ExitCounts) {
-    if (!isa<SCEVConstant>(Pair.second.ExactNotTaken))
-      BECountUsers[Pair.second.ExactNotTaken].insert({L, AllowPredicates});
-    if (!isa<SCEVConstant>(Pair.second.SymbolicMaxNotTaken))
-      BECountUsers[Pair.second.SymbolicMaxNotTaken].insert(
-          {L, AllowPredicates});
-  }
   return BackedgeTakenInfo(std::move(ExitCounts), CouldComputeBECount,
                            MaxBECount, MaxOrZero);
 }
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<allowspeculation>,simple-loop-unswitch<nontrivial>),loop(loop-predication)' -S < %s | FileCheck %s
 
-; REQUIRES: asserts
-; XFAIL: *
+; 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.
 
 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"
 
 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