diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -1719,6 +1719,13 @@
     // LHS always has at least one use that is not dominated by Root, this will
     // never do anything if LHS has only one use.
     if (!LHS->hasOneUse()) {
+      // Cached information for anything that uses LHS will be invalid.
+      if (MD) {
+        for (auto *U : LHS->users())
+          MD->invalidateCachedPointerInfo(U);
+        MD->invalidateCachedPointerInfo(LHS);
+      }
+
       unsigned NumReplacements =
           DominatesByEdge
               ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
@@ -1726,9 +1733,6 @@
 
       Changed |= NumReplacements > 0;
       NumGVNEqProp += NumReplacements;
-      // Cached information for anything that uses LHS will be invalid.
-      if (MD)
-        MD->invalidateCachedPointerInfo(LHS);
     }
 
     // Now try to deduce additional equalities from this one. For example, if
@@ -1797,6 +1801,13 @@
       if (Num < NextNum) {
         Value *NotCmp = findLeader(Root.getEnd(), Num);
         if (NotCmp && isa<Instruction>(NotCmp)) {
+          // Cached information for anything that uses NotCmp will be invalid.
+          if (MD) {
+            for (auto *U : NotCmp->users())
+              MD->invalidateCachedPointerInfo(U);
+            MD->invalidateCachedPointerInfo(NotCmp);
+          }
+
           unsigned NumReplacements =
               DominatesByEdge
                   ? replaceDominatedUsesWith(NotCmp, NotVal, *DT, Root)
@@ -1804,9 +1815,6 @@
                                              Root.getStart());
           Changed |= NumReplacements > 0;
           NumGVNEqProp += NumReplacements;
-          // Cached information for anything that uses NotCmp will be invalid.
-          if (MD)
-            MD->invalidateCachedPointerInfo(NotCmp);
         }
       }
       // Ensure that any instruction in scope that gets the "A < B" value number
diff --git a/llvm/test/Transforms/GVN/condprop-md-invalidation2.ll b/llvm/test/Transforms/GVN/condprop-md-invalidation2.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/GVN/condprop-md-invalidation2.ll
@@ -0,0 +1,72 @@
+; RUN: opt -gvn %s -S | FileCheck %s
+
+; Test case for PR31651.
+
+target datalayout = "p:16:16"
+
+declare void @CVAL_VERIFY_FUNC(i16)
+
+declare i16 @gen()
+
+define i16 @main() #1 {
+  %ub.16 = alloca [4 x i16], align 2
+  br label %bb1
+
+bb1:                                              ; preds = %bb12, %0
+  %step1.7.0 = phi i16 [ 0, %0 ], [ %_tmp72, %bb12 ]
+  %_tmp13 = icmp eq i16 %step1.7.0, 0
+  br i1 %_tmp13, label %bb5, label %bb4
+
+bb4:                                              ; preds = %bb1
+  %_tmp18 = add i16 %step1.7.0, -1
+  %_tmp20 = getelementptr [4 x i16], [4 x i16]* %ub.16, i16 0, i16 %_tmp18
+  %_tmp21 = load i16, i16* %_tmp20, align 2
+  br label %bb5
+
+bb5:                                              ; preds = %bb1, %bb4
+  %step1.7.0.sink = phi i16 [ %step1.7.0, %bb4 ], [ 0, %bb1 ]
+  %_tmp22.sink = phi i16 [ %_tmp21, %bb4 ], [ 10, %bb1 ]
+  %_tmp26 = getelementptr [4 x i16], [4 x i16]* %ub.16, i16 0, i16 %step1.7.0.sink
+  store i16 %_tmp22.sink, i16* %_tmp26, align 2
+  %_tmp28 = icmp eq i16 %step1.7.0, 0
+  br i1 %_tmp28, label %bb7, label %bb8
+
+; CHECK-LABEL: bb7:
+; CHECK-NEXT:   %_tmp47 = getelementptr [4 x i16], [4 x i16]* %ub.16, i16 0, i16 0
+; CHECK-NEXT:   %_tmp48 = load i16, i16* %_tmp47, align 2
+bb7:                                              ; preds = %bb_usw2
+  %_tmp47 = getelementptr [4 x i16], [4 x i16]* %ub.16, i16 0, i16 %step1.7.0
+  %_tmp48 = load i16, i16* %_tmp47, align 2
+  call void @CVAL_VERIFY_FUNC(i16 %_tmp48)
+  br label %bb12
+
+bb8:                                              ; preds = %bb_usw2
+  %_tmp57 = getelementptr [4 x i16], [4 x i16]* %ub.16, i16 0, i16 %step1.7.0
+  %_tmp58 = load i16, i16* %_tmp57, align 2
+  call void @CVAL_VERIFY_FUNC(i16 %_tmp58)
+  br label %bb12
+
+bb12:                                             ; preds = %bb9, %bb11, %bb10
+  %_tmp72 = add i16 %step1.7.0, 1
+  %_tmp74 = icmp slt i16 %_tmp72, 3
+  br i1 %_tmp74, label %bb1, label %bb14
+
+
+; CHECK-LABEL: bb14:
+; CHECK-NOT:    %_tmp79 = phi
+; CHECK-NEXT:   %i.8.0 = phi i16
+; CHECK:        %_tmp79 = load i16, i16* %_tmp78, align 2
+bb14:                                             ; preds = %bb12, %bb14
+  %i.8.0 = phi i16 [ %_tmp91, %bb14 ], [ 0, %bb12 ]
+  %_tmp78 = getelementptr [4 x i16], [4 x i16]* %ub.16, i16 0, i16 %i.8.0
+  %_tmp79 = load i16, i16* %_tmp78, align 2
+  call void @CVAL_VERIFY_FUNC(i16 %_tmp79)
+  %_tmp91 = add i16 %i.8.0, 1
+  %_tmp93 = icmp slt i16 %_tmp91, 101
+  br i1 %_tmp93, label %bb14, label %bb17
+
+bb17:                                             ; preds = %bb14
+  ret i16 0
+
+  uselistorder [4 x i16]* %ub.16, { 4, 3, 2, 0, 1 }
+}