diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
--- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
+++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
@@ -265,7 +265,7 @@
 /// to an entirely separate nest.
 static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
                                  DominatorTree &DT, LoopInfo &LI,
-                                 MemorySSAUpdater *MSSAU) {
+                                 MemorySSAUpdater *MSSAU, ScalarEvolution *SE) {
   // If the loop is already at the top level, we can't hoist it anywhere.
   Loop *OldParentL = L.getParentLoop();
   if (!OldParentL)
@@ -319,7 +319,7 @@
     // Because we just hoisted a loop out of this one, we have essentially
     // created new exit paths from it. That means we need to form LCSSA PHI
     // nodes for values used in the no-longer-nested loop.
-    formLCSSA(*OldContainingL, DT, &LI, nullptr);
+    formLCSSA(*OldContainingL, DT, &LI, SE);
 
     // We shouldn't need to form dedicated exits because the exit introduced
     // here is the (just split by unswitching) preheader. However, after trivial
@@ -549,7 +549,7 @@
   // If this was full unswitching, we may have changed the nesting relationship
   // for this loop so hoist it to its correct parent if needed.
   if (FullUnswitch)
-    hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+    hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE);
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
@@ -842,7 +842,7 @@
 
   // We may have changed the nesting relationship for this loop so hoist it to
   // its correct parent if needed.
-  hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+  hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE);
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
@@ -2277,7 +2277,7 @@
     // First build LCSSA for this loop so that we can preserve it when
     // forming dedicated exits. We don't want to perturb some other loop's
     // LCSSA while doing that CFG edit.
-    formLCSSA(UpdateL, DT, &LI, nullptr);
+    formLCSSA(UpdateL, DT, &LI, SE);
 
     // For loops reached by this loop's original exit blocks we may
     // introduced new, non-dedicated exits. At least try to re-form dedicated
diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp
--- a/llvm/lib/Transforms/Utils/LCSSA.cpp
+++ b/llvm/lib/Transforms/Utils/LCSSA.cpp
@@ -200,9 +200,6 @@
         UserBB = PN->getIncomingBlock(*UseToRewrite);
 
       if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
-        // Tell the VHs that the uses changed. This updates SCEV's caches.
-        if (UseToRewrite->get()->hasValueHandle())
-          ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front());
         UseToRewrite->set(&UserBB->front());
         continue;
       }
@@ -210,10 +207,6 @@
       // If we added a single PHI, it must dominate all uses and we can directly
       // rename it.
       if (AddedPHIs.size() == 1) {
-        // Tell the VHs that the uses changed. This updates SCEV's caches.
-        // We might call ValueIsRAUWd multiple times for the same value.
-        if (UseToRewrite->get()->hasValueHandle())
-          ValueHandleBase::ValueIsRAUWd(*UseToRewrite, AddedPHIs[0]);
         UseToRewrite->set(AddedPHIs[0]);
         continue;
       }
diff --git a/llvm/test/Transforms/LCSSA/pr44058.ll b/llvm/test/Transforms/LCSSA/pr44058.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/LCSSA/pr44058.ll
@@ -0,0 +1,37 @@
+; RUN: opt -passes="verify<scalar-evolution>,lcssa,verify<scalar-evolution>" -verify-scev-strict -S %s
+
+; The first SCEV verification is required because it queries SCEV and populates
+; SCEV caches. Second SCEV verification checks if the caches are in valid state.
+
+; Check that the second SCEV verification doesn't fail.
+define void @foo(i32* %arg, i32* %arg1, i1 %arg2) {
+bb:
+  br label %bb3
+
+bb3:                                              ; preds = %bb13, %bb
+  %tmp = load i32, i32* %arg
+  %tmp4 = load i32, i32* %arg1
+  %tmp5 = add i32 %tmp4, %tmp
+  %tmp6 = icmp sgt i32 %tmp5, %tmp
+  br i1 %tmp6, label %bb7, label %bb11
+
+bb7:                                              ; preds = %bb3
+  br i1 %arg2, label %bb10, label %bb8
+
+bb8:                                              ; preds = %bb7
+  %tmp9 = add nsw i32 %tmp, 1
+  ret void
+
+bb10:                                             ; preds = %bb7
+  br label %bb11
+
+bb11:                                             ; preds = %bb10, %bb3
+  %tmp12 = phi i32 [ 0, %bb3 ], [ %tmp4, %bb10 ]
+  br label %bb13
+
+bb13:                                             ; preds = %bb13, %bb11
+  %tmp14 = phi i32 [ %tmp15, %bb13 ], [ 0, %bb11 ]
+  %tmp15 = add nuw nsw i32 %tmp14, 1
+  %tmp16 = icmp slt i32 %tmp15, %tmp12
+  br i1 %tmp16, label %bb13, label %bb3
+}