Index: llvm/include/llvm/Analysis/AliasSetTracker.h
===================================================================
--- llvm/include/llvm/Analysis/AliasSetTracker.h
+++ llvm/include/llvm/Analysis/AliasSetTracker.h
@@ -333,6 +333,7 @@
 
     void deleted() override;
     void allUsesReplacedWith(Value *) override;
+    void oneUseReplacedWith(Use &U, Value *New) override;
 
   public:
     ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
Index: llvm/include/llvm/IR/ValueHandle.h
===================================================================
--- llvm/include/llvm/IR/ValueHandle.h
+++ llvm/include/llvm/IR/ValueHandle.h
@@ -114,6 +114,14 @@
   static void ValueIsDeleted(Value *V);
   static void ValueIsRAUWd(Value *Old, Value *New);
 
+  /// This callback is used for only one very specific purpose: to keep
+  /// AliasSetTrackers that are cached by LICM up to date when SSAUpdater
+  /// modifies IR. Thus it is called only explicitly by the transformation and
+  /// never from Value methods, unlike regular callbacks (ValueIsDeleted,
+  /// ValueIsRAUWd). It should be removed once LICM stops keeping ASTs across
+  /// invocations.
+  static void ValueUseIsReplaced(Use &U, Value *New);
+
 private:
   // Internal implementation details.
   ValueHandleBase **getPrevPtr() const { return PrevPair.getPointer(); }
@@ -436,6 +444,12 @@
   /// implemented as a CallbackVH, it would use this method to call
   /// setValPtr(new_value).  AssertingVH would do nothing in this method.
   virtual void allUsesReplacedWith(Value *) {}
+
+  /// This callback is used for only one very specific purpose: to keep
+  /// AliasSetTrackers that are cached by LICM up to date when SSAUpdater
+  /// modifies IR. It should be removed once LICM stops keeping ASTs across
+  /// invocations.
+  virtual void oneUseReplacedWith(Use &U, Value *New) {}
 };
 
 /// Value handle that poisons itself if the Value is deleted.
Index: llvm/lib/Analysis/AliasSetTracker.cpp
===================================================================
--- llvm/lib/Analysis/AliasSetTracker.cpp
+++ llvm/lib/Analysis/AliasSetTracker.cpp
@@ -725,6 +725,10 @@
   AST->copyValue(getValPtr(), V);
 }
 
+void AliasSetTracker::ASTCallbackVH::oneUseReplacedWith(Use &, Value *New) {
+  AST->copyValue(getValPtr(), New);
+}
+
 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
   : CallbackVH(V), AST(ast) {}
 
Index: llvm/lib/IR/Value.cpp
===================================================================
--- llvm/lib/IR/Value.cpp
+++ llvm/lib/IR/Value.cpp
@@ -977,5 +977,33 @@
 #endif
 }
 
+void ValueHandleBase::ValueUseIsReplaced(Use &U, Value *New) {
+  Value *Old = U.get();
+  assert(Old->HasValueHandle &&
+         "Should only be called if ValueHandles present");
+  assert(Old != New && "Changing value into itself!");
+  assert(Old->getType() == New->getType() &&
+         "Can't replace use of value with new value of different type!");
+
+  // Get the linked list base, which is guaranteed to exist since the
+  // HasValueHandle flag is set.
+  LLVMContextImpl *pImpl = Old->getContext().pImpl;
+  ValueHandleBase *Entry = pImpl->ValueHandles[Old];
+
+  assert(Entry && "Value bit set but no entries exist");
+
+  // We use a local ValueHandleBase as an iterator so that ValueHandles can add
+  // and remove themselves from the list without breaking our iteration. This is
+  // not really an AssertingVH; we just have to give ValueHandleBase some kind.
+  for (ValueHandleBase Iterator(Assert, *Entry); Entry; Entry = Iterator.Next) {
+    Iterator.RemoveFromUseList();
+    Iterator.AddToExistingUseListAfter(Entry);
+    assert(Entry->Next == &Iterator && "Loop invariant broken.");
+
+    if (Entry->getKind() == Callback)
+      static_cast<CallbackVH *>(Entry)->oneUseReplacedWith(U, New);
+  }
+}
+
 // Pin the vtable to this file.
 void CallbackVH::anchor() {}
Index: llvm/lib/Transforms/Utils/SSAUpdater.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SSAUpdater.cpp
+++ llvm/lib/Transforms/Utils/SSAUpdater.cpp
@@ -195,10 +195,16 @@
   else
     V = GetValueInMiddleOfBlock(User->getParent());
 
-  // Notify that users of the existing value that it is being replaced.
   Value *OldVal = U.get();
-  if (OldVal != V && OldVal->hasValueHandle())
-    ValueHandleBase::ValueIsRAUWd(OldVal, V);
+  if (OldVal != V && OldVal->hasValueHandle()) {
+    // This is the only use of ValueUseIsReplaced callback and it is used here
+    // for only one very specific purpose: to keep AliasSetTrackers that are
+    // cached by LICM up to date when SSAUpdater modifies IR. It should be
+    // removed once LICM stops keeping ASTs across invocations (and some other
+    // means of keeping ASTs up to date within single invocation of LICM are
+    // implemented).
+    ValueHandleBase::ValueUseIsReplaced(U, V);
+  }
 
   U.set(V);
 }
Index: llvm/test/Transforms/LCSSA/pr44320.ll
===================================================================
--- llvm/test/Transforms/LCSSA/pr44320.ll
+++ llvm/test/Transforms/LCSSA/pr44320.ll
@@ -1,4 +1,3 @@
-; XFAIL: *
 ; RUN: opt -passes="verify<scalar-evolution>,lcssa,verify<scalar-evolution>" -verify-scev-strict -S -disable-output %s
 
 ; The first SCEV verification is required because it queries SCEV and populates