Index: llvm/include/llvm/Analysis/ScalarEvolution.h
===================================================================
--- llvm/include/llvm/Analysis/ScalarEvolution.h
+++ llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -2053,6 +2053,12 @@
   std::tuple<SCEV *, FoldingSetNodeID, void *>
   findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
 
+  /// Push PHI nodes in the header of the given loop onto the given Worklist
+  /// if they have a cached SCEV expression. If no expression is cached, then
+  /// there also aren't any dependent expressions to invalidate.
+  void pushCachedLoopPHIs(const Loop *L,
+                          SmallVectorImpl<Instruction *> &Worklist);
+
   FoldingSet<SCEV> UniqueSCEVs;
   FoldingSet<SCEVPredicate> UniquePreds;
   BumpPtrAllocator SCEVAllocator;
Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -7020,13 +7020,17 @@
 }
 
 /// Push PHI nodes in the header of the given loop onto the given Worklist.
-static void
-PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
+/// Only push PHIs for which a SCEV expression has been cached, otherwise there
+/// cannot be any dependent expressions to invalidate.
+void ScalarEvolution::pushCachedLoopPHIs(
+    const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
   BasicBlock *Header = L->getHeader();
-
-  // Push all Loop-header PHIs onto the Worklist stack.
-  for (PHINode &PN : Header->phis())
-    Worklist.push_back(&PN);
+  for (PHINode &PN : Header->phis()) {
+    ValueExprMapType::iterator It =
+        ValueExprMap.find_as(static_cast<Value *>(&PN));
+    if (It != ValueExprMap.end())
+      Worklist.push_back(&PN);
+  }
 }
 
 const ScalarEvolution::BackedgeTakenInfo &
@@ -7087,7 +7091,7 @@
   // it handles SCEVUnknown PHI nodes specially.
   if (Result.hasAnyInfo()) {
     SmallVector<Instruction *, 16> Worklist;
-    PushLoopPHIs(L, Worklist);
+    pushCachedLoopPHIs(L, Worklist);
 
     SmallPtrSet<Instruction *, 8> Discovered;
     while (!Worklist.empty()) {
@@ -7210,7 +7214,7 @@
     }
 
     // Drop information about expressions based on loop-header PHIs.
-    PushLoopPHIs(CurrL, Worklist);
+    pushCachedLoopPHIs(CurrL, Worklist);
 
     while (!Worklist.empty()) {
       Instruction *I = Worklist.pop_back_val();