diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp
--- a/llvm/lib/Transforms/Scalar/NewGVN.cpp
+++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp
@@ -2758,6 +2758,14 @@
         dbgs()
         << "Not creating real PHI of ops because it simplified to existing "
            "value or constant\n");
+    // We have leaders for all operands, but do not create a real PHI node with
+    // those leaders as operands, so the link between the operands and the
+    // PHI-of-ops is not materialized in the IR. If any of those leaders
+    // changes, the PHI-of-op may change also, so we need to add the operands as
+    // additional users.
+    for (auto &O : PHIOps)
+      addAdditionalUsers(O.first, I);
+
     return E;
   }
   auto *ValuePHI = RealToTemp.lookup(I);
diff --git a/llvm/test/Transforms/NewGVN/phi-of-ops-simplified-to-existing-value-then-changes-again.ll b/llvm/test/Transforms/NewGVN/phi-of-ops-simplified-to-existing-value-then-changes-again.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/phi-of-ops-simplified-to-existing-value-then-changes-again.ll
@@ -0,0 +1,239 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn -S %s | FileCheck %s
+
+; Test cases where initially a PHI-of-ops can be simplified to an existing
+; value, but later we need to revisit the decision because the leader of
+; one of the operands used for the simplification changed.
+
+declare void @use(i1)
+
+define void @pr36501(i1 %c) {
+; CHECK-LABEL: @pr36501(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[PHI_1:%.*]] = phi i32 [ -2022207984, [[BB:%.*]] ], [ 0, [[BB7:%.*]] ]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB3:%.*]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[PHI_2:%.*]] = phi i32 [ -1, [[BB2]] ], [ [[PHI_1]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[PHI_2]], 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB7]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br label [[BB7]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ [[TMP5]], [[BB3]] ], [ true, [[BB6]] ]
+; CHECK-NEXT:    [[PHI_3:%.*]] = phi i32 [ [[PHI_2]], [[BB3]] ], [ 0, [[BB6]] ]
+; CHECK-NEXT:    call void @use(i1 [[PHIOFOPS]])
+; CHECK-NEXT:    br label [[BB1]]
+;
+bb:
+  br label %bb1
+
+bb1:
+  %phi.1 = phi i32 [ -2022207984, %bb ], [ 0, %bb7 ]
+  br i1 %c, label %bb3, label %bb2
+
+bb2:
+  br label %bb3
+
+bb3:
+  %phi.2 = phi i32 [ -1, %bb2 ], [ %phi.1, %bb1 ]
+  %tmp5 = icmp eq i32 %phi.2, 0
+  br i1 %tmp5, label %bb6, label %bb7
+
+bb6:
+  br label %bb7
+
+bb7:                                              ; preds = %bb6, %bb3
+  %phi.3 = phi i32 [ %phi.2, %bb3 ], [ 0, %bb6 ]
+  %tmp9 = icmp eq i32 %phi.3, 0
+  call void @use(i1 %tmp9)
+  br label %bb1
+}
+
+define void @pr42422(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @pr42422(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ [[TMP23:%.*]], [[BB22:%.*]] ], [ 0, [[BB1]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp sle i32 [[TMP]], 1
+; CHECK-NEXT:    br i1 [[TMP3]], label [[BB4:%.*]], label [[BB24:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB5:%.*]], label [[BB6:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB19:%.*]]
+; CHECK:       bb6:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB7:%.*]], label [[BB8:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB16:%.*]]
+; CHECK:       bb8:
+; CHECK-NEXT:    [[TMP9:%.*]] = phi i64 [ [[TMP12:%.*]], [[BB11:%.*]] ], [ 0, [[BB6]] ]
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp sle i64 [[TMP9]], 1
+; CHECK-NEXT:    br i1 [[TMP10]], label [[BB11]], label [[BB13:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12]] = add nsw i64 [[TMP9]], 1
+; CHECK-NEXT:    br label [[BB8]]
+; CHECK:       bb13:
+; CHECK-NEXT:    br i1 true, label [[BB14:%.*]], label [[BB15:%.*]]
+; CHECK:       bb14:
+; CHECK-NEXT:    br label [[BB16]]
+; CHECK:       bb15:
+; CHECK-NEXT:    store i8 undef, i8* null, align 1
+; CHECK-NEXT:    br label [[BB16]]
+; CHECK:       bb16:
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i32 [ undef, [[BB15]] ], [ 1, [[BB14]] ], [ 9, [[BB7]] ]
+; CHECK-NEXT:    switch i32 [[TMP17]], label [[BB19]] [
+; CHECK-NEXT:    i32 0, label [[BB6]]
+; CHECK-NEXT:    i32 9, label [[BB18:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i32 [ 0, [[BB18]] ], [ [[TMP17]], [[BB16]] ], [ 1, [[BB5]] ]
+; CHECK-NEXT:    [[TMP21:%.*]] = icmp eq i32 [[TMP20]], 0
+; CHECK-NEXT:    br i1 [[TMP21]], label [[BB22]], label [[BB25:%.*]]
+; CHECK:       bb22:
+; CHECK-NEXT:    [[TMP23]] = add nsw i32 [[TMP]], 1
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb24:
+; CHECK-NEXT:    br label [[BB25]]
+; CHECK:       bb25:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[BB24]] ], [ [[TMP21]], [[BB19]] ]
+; CHECK-NEXT:    [[TMP26:%.*]] = phi i32 [ [[TMP20]], [[BB19]] ], [ 0, [[BB24]] ]
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB1]], label [[BB28:%.*]]
+; CHECK:       bb28:
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb25, %bb
+  br label %bb2
+
+bb2:                                              ; preds = %bb22, %bb1
+  %tmp = phi i32 [ %tmp23, %bb22 ], [ 0, %bb1 ]
+  %tmp3 = icmp sle i32 %tmp, 1
+  br i1 %tmp3, label %bb4, label %bb24
+
+bb4:                                              ; preds = %bb2
+  br i1 %c.1, label %bb5, label %bb6
+
+bb5:                                              ; preds = %bb4
+  br label %bb19
+
+bb6:                                              ; preds = %bb16, %bb4
+  br i1 %c.2, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb6
+  br label %bb16
+
+bb8:                                              ; preds = %bb11, %bb6
+  %tmp9 = phi i64 [ %tmp12, %bb11 ], [ 0, %bb6 ]
+  %tmp10 = icmp sle i64 %tmp9, 1
+  br i1 %tmp10, label %bb11, label %bb13
+
+bb11:                                             ; preds = %bb8
+  %tmp12 = add nsw i64 %tmp9, 1
+  br label %bb8
+
+bb13:                                             ; preds = %bb8
+  br i1 true, label %bb14, label %bb15
+
+bb14:                                             ; preds = %bb13
+  br label %bb16
+
+bb15:                                             ; preds = %bb13
+  br label %bb16
+
+bb16:                                             ; preds = %bb15, %bb14, %bb7
+  %tmp17 = phi i32 [ undef, %bb15 ], [ 1, %bb14 ], [ 9, %bb7 ]
+  switch i32 %tmp17, label %bb19 [
+  i32 0, label %bb6
+  i32 9, label %bb18
+  ]
+
+bb18:                                             ; preds = %bb16
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb16, %bb5
+  %tmp20 = phi i32 [ 0, %bb18 ], [ %tmp17, %bb16 ], [ 1, %bb5 ]
+  %tmp21 = icmp eq i32 %tmp20, 0
+  br i1 %tmp21, label %bb22, label %bb25
+
+bb22:                                             ; preds = %bb19
+  %tmp23 = add nsw i32 %tmp, 1
+  br label %bb2
+
+bb24:                                             ; preds = %bb2
+  br label %bb25
+
+bb25:                                             ; preds = %bb24, %bb19
+  %tmp26 = phi i32 [ %tmp20, %bb19 ], [ 0, %bb24 ]
+  %tmp27 = icmp eq i32 %tmp26, 0
+  br i1 %tmp27, label %bb1, label %bb28
+
+bb28:                                             ; preds = %bb25
+  ret void
+}
+
+define void @PR42557(i32 %tmp6, i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @PR42557(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[TMP6:%.*]], [[BB1]] ]
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB2:%.*]], label [[BB1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB16:%.*]], label [[BB11:%.*]]
+; CHECK:       bb16:
+; CHECK-NEXT:    [[TMP17:%.*]] = add i32 [[TMP]], 1
+; CHECK-NEXT:    br label [[BB11]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i32 [ [[TMP17]], [[BB16]] ], [ 0, [[BB2]] ]
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0
+; CHECK-NEXT:    call void @use(i1 [[TMP13]])
+; CHECK-NEXT:    [[TMP15:%.*]] = icmp ne i32 [[TMP]], 0
+; CHECK-NEXT:    br i1 [[TMP15]], label [[BB18:%.*]], label [[BB19:%.*]]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ [[TMP13]], [[BB11]] ], [ false, [[BB18]] ]
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i32 [ [[TMP12]], [[BB11]] ], [ 1, [[BB18]] ]
+; CHECK-NEXT:    call void @use(i1 [[PHIOFOPS]])
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp = phi i32 [ 0, %bb ], [ %tmp6, %bb1 ]
+  br i1 %c.1, label %bb2, label %bb1
+
+bb2:                                              ; preds = %bb1
+  br i1 %c.2, label %bb16, label %bb11
+
+bb16:                                             ; preds = %bb2
+  %tmp17 = add i32 %tmp, 1
+  br label %bb11
+
+bb11:                                             ; preds = %bb16, %bb2
+  %tmp12 = phi i32 [ %tmp17, %bb16 ], [ 0, %bb2 ]
+  %tmp13 = icmp eq i32 %tmp12, 0
+  call void @use(i1 %tmp13)
+  %tmp15 = icmp ne i32 %tmp, 0
+  br i1 %tmp15, label %bb18, label %bb19
+
+bb18:                                             ; preds = %bb11
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb11
+  %tmp20 = phi i32 [ %tmp12, %bb11 ], [ 1, %bb18 ]
+  %tmp21 = icmp eq i32 %tmp20, 0
+  call void @use(i1 %tmp21)
+  ret void
+}
diff --git a/llvm/test/Transforms/NewGVN/pr36501-changed-after-3.ll b/llvm/test/Transforms/NewGVN/pr36501-changed-after-3.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/pr36501-changed-after-3.ll
@@ -0,0 +1,172 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s -newgvn | FileCheck %s
+
+; Test for PR36501.
+
+define void @func_1() local_unnamed_addr #0 {
+; CHECK-LABEL: @func_1(
+; CHECK-NEXT:    br label [[TMP1:%.*]]
+; CHECK:       1:
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ -2022207984, [[TMP0:%.*]] ], [ 0, [[DOTLOOPEXIT_8:%.*]] ]
+; CHECK-NEXT:    br i1 undef, label [[TMP3:%.*]], label [[TMP2:%.*]]
+; CHECK:       2:
+; CHECK-NEXT:    br label [[TMP3]]
+; CHECK:       3:
+; CHECK-NEXT:    [[DOT1:%.*]] = phi i32 [ -1, [[TMP2]] ], [ [[DOT0]], [[TMP1]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[DOT1]], 0
+; CHECK-NEXT:    br i1 [[TMP4]], label [[DOTPREHEADER:%.*]], label [[DOTLOOPEXIT:%.*]]
+; CHECK:       .preheader:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH:%.*]], label [[DOTLOOPEXIT]]
+; CHECK:       .lr.ph:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH]], label [[DOTLOOPEXIT]]
+; CHECK:       .loopexit:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ [[TMP4]], [[TMP3]] ], [ true, [[DOTPREHEADER]] ], [ true, [[DOTLR_PH]] ]
+; CHECK-NEXT:    [[DOT4:%.*]] = phi i32 [ [[DOT1]], [[TMP3]] ], [ 0, [[DOTPREHEADER]] ], [ 0, [[DOTLR_PH]] ]
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[DOTPREHEADER_1:%.*]], label [[DOTLOOPEXIT_1:%.*]]
+; CHECK:       .preheader.1:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_1:%.*]], label [[DOTLOOPEXIT_1]]
+; CHECK:       .lr.ph.1:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_1]], label [[DOTLOOPEXIT_1]]
+; CHECK:       .loopexit.1:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_2:%.*]], label [[DOTLOOPEXIT_2:%.*]]
+; CHECK:       .preheader.2:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_2:%.*]], label [[DOTLOOPEXIT_2]]
+; CHECK:       .lr.ph.2:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_2]], label [[DOTLOOPEXIT_2]]
+; CHECK:       .loopexit.2:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_3:%.*]], label [[DOTLOOPEXIT_3:%.*]]
+; CHECK:       .preheader.3:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_3:%.*]], label [[DOTLOOPEXIT_3]]
+; CHECK:       .lr.ph.3:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_3]], label [[DOTLOOPEXIT_3]]
+; CHECK:       .loopexit.3:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_4:%.*]], label [[DOTLOOPEXIT_4:%.*]]
+; CHECK:       .preheader.4:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_4:%.*]], label [[DOTLOOPEXIT_4]]
+; CHECK:       .lr.ph.4:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_4]], label [[DOTLOOPEXIT_4]]
+; CHECK:       .loopexit.4:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_5:%.*]], label [[DOTLOOPEXIT_5:%.*]]
+; CHECK:       .preheader.5:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_5:%.*]], label [[DOTLOOPEXIT_5]]
+; CHECK:       .lr.ph.5:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_5]], label [[DOTLOOPEXIT_5]]
+; CHECK:       .loopexit.5:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_6:%.*]], label [[DOTLOOPEXIT_6:%.*]]
+; CHECK:       .preheader.6:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_6:%.*]], label [[DOTLOOPEXIT_6]]
+; CHECK:       .lr.ph.6:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_6]], label [[DOTLOOPEXIT_6]]
+; CHECK:       .loopexit.6:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_7:%.*]], label [[DOTLOOPEXIT_7:%.*]]
+; CHECK:       .preheader.7:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_7:%.*]], label [[DOTLOOPEXIT_7]]
+; CHECK:       .lr.ph.7:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_7]], label [[DOTLOOPEXIT_7]]
+; CHECK:       .loopexit.7:
+; CHECK-NEXT:    br i1 undef, label [[DOTPREHEADER_8:%.*]], label [[DOTLOOPEXIT_8]]
+; CHECK:       .preheader.8:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_8:%.*]], label [[DOTLOOPEXIT_8]]
+; CHECK:       .lr.ph.8:
+; CHECK-NEXT:    br i1 undef, label [[DOTLR_PH_8]], label [[DOTLOOPEXIT_8]]
+; CHECK:       .loopexit.8:
+; CHECK-NEXT:    br label [[TMP1]]
+;
+  br label %1
+
+1:                                                ; preds = %.loopexit.8, %0
+  %.0 = phi i32 [ -2022207984, %0 ], [ 0, %.loopexit.8 ]
+  %2 = icmp eq i16 undef, 0
+  br i1 %2, label %4, label %3
+
+3:                                                ; preds = %1
+  br label %4
+
+4:                                                ; preds = %3, %1
+  %.1 = phi i32 [ -1, %3 ], [ %.0, %1 ]
+  %5 = icmp eq i32 %.1, 0
+  br i1 %5, label %.preheader, label %.loopexit
+
+.preheader:                                       ; preds = %4
+  br i1 undef, label %.lr.ph, label %.loopexit
+
+.lr.ph:                                           ; preds = %.lr.ph, %.preheader
+  br i1 undef, label %.lr.ph, label %.loopexit
+
+.loopexit:                                        ; preds = %.lr.ph, %.preheader, %4
+  %.4 = phi i32 [ %.1, %4 ], [ 0, %.preheader ], [ 0, %.lr.ph ]
+  %6 = icmp eq i32 %.4, 0
+  br i1 %6, label %.preheader.1, label %.loopexit.1
+
+.preheader.1:                                     ; preds = %.loopexit
+  br i1 undef, label %.lr.ph.1, label %.loopexit.1
+
+.lr.ph.1:                                         ; preds = %.lr.ph.1, %.preheader.1
+  br i1 undef, label %.lr.ph.1, label %.loopexit.1
+
+.loopexit.1:                                      ; preds = %.lr.ph.1, %.preheader.1, %.loopexit
+  br i1 undef, label %.preheader.2, label %.loopexit.2
+
+.preheader.2:                                     ; preds = %.loopexit.1
+  br i1 undef, label %.lr.ph.2, label %.loopexit.2
+
+.lr.ph.2:                                         ; preds = %.lr.ph.2, %.preheader.2
+  br i1 undef, label %.lr.ph.2, label %.loopexit.2
+
+.loopexit.2:                                      ; preds = %.lr.ph.2, %.preheader.2, %.loopexit.1
+  br i1 undef, label %.preheader.3, label %.loopexit.3
+
+.preheader.3:                                     ; preds = %.loopexit.2
+  br i1 undef, label %.lr.ph.3, label %.loopexit.3
+
+.lr.ph.3:                                         ; preds = %.lr.ph.3, %.preheader.3
+  br i1 undef, label %.lr.ph.3, label %.loopexit.3
+
+.loopexit.3:                                      ; preds = %.lr.ph.3, %.preheader.3, %.loopexit.2
+  br i1 undef, label %.preheader.4, label %.loopexit.4
+
+.preheader.4:                                     ; preds = %.loopexit.3
+  br i1 undef, label %.lr.ph.4, label %.loopexit.4
+
+.lr.ph.4:                                         ; preds = %.lr.ph.4, %.preheader.4
+  br i1 undef, label %.lr.ph.4, label %.loopexit.4
+
+.loopexit.4:                                      ; preds = %.lr.ph.4, %.preheader.4, %.loopexit.3
+  br i1 undef, label %.preheader.5, label %.loopexit.5
+
+.preheader.5:                                     ; preds = %.loopexit.4
+  br i1 undef, label %.lr.ph.5, label %.loopexit.5
+
+.lr.ph.5:                                         ; preds = %.lr.ph.5, %.preheader.5
+  br i1 undef, label %.lr.ph.5, label %.loopexit.5
+
+.loopexit.5:                                      ; preds = %.lr.ph.5, %.preheader.5, %.loopexit.4
+  br i1 undef, label %.preheader.6, label %.loopexit.6
+
+.preheader.6:                                     ; preds = %.loopexit.5
+  br i1 undef, label %.lr.ph.6, label %.loopexit.6
+
+.lr.ph.6:                                         ; preds = %.lr.ph.6, %.preheader.6
+  br i1 undef, label %.lr.ph.6, label %.loopexit.6
+
+.loopexit.6:                                      ; preds = %.lr.ph.6, %.preheader.6, %.loopexit.5
+  br i1 undef, label %.preheader.7, label %.loopexit.7
+
+.preheader.7:                                     ; preds = %.loopexit.6
+  br i1 undef, label %.lr.ph.7, label %.loopexit.7
+
+.lr.ph.7:                                         ; preds = %.lr.ph.7, %.preheader.7
+  br i1 undef, label %.lr.ph.7, label %.loopexit.7
+
+.loopexit.7:                                      ; preds = %.lr.ph.7, %.preheader.7, %.loopexit.6
+  br i1 undef, label %.preheader.8, label %.loopexit.8
+
+.preheader.8:                                     ; preds = %.loopexit.7
+  br i1 undef, label %.lr.ph.8, label %.loopexit.8
+
+.lr.ph.8:                                         ; preds = %.lr.ph.8, %.preheader.8
+  br i1 undef, label %.lr.ph.8, label %.loopexit.8
+
+.loopexit.8:                                      ; preds = %.lr.ph.8, %.preheader.8, %.loopexit.7
+  br label %1
+}
diff --git a/llvm/test/Transforms/NewGVN/pr42422-changed-after-2.ll b/llvm/test/Transforms/NewGVN/pr42422-changed-after-2.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/pr42422-changed-after-2.ll
@@ -0,0 +1,143 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -newgvn < %s | FileCheck %s
+
+; Test for PR42422.
+
+define void @d() {
+; CHECK-LABEL: @d(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br label [[FOR_COND1:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[INC18:%.*]], [[FOR_INC17:%.*]] ], [ 0, [[FOR_COND]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[TMP0]], 1
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END19:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br i1 undef, label [[FOR_BODY3:%.*]], label [[FOR_BODY_FOR_COND4_CRIT_EDGE:%.*]]
+; CHECK:       for.body.for.cond4_crit_edge:
+; CHECK-NEXT:    br label [[FOR_COND4:%.*]]
+; CHECK:       for.body3:
+; CHECK-NEXT:    br label [[CLEANUP14:%.*]]
+; CHECK:       for.cond4:
+; CHECK-NEXT:    br i1 undef, label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[CLEANUP:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br label [[FOR_COND6:%.*]]
+; CHECK:       for.cond6:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i64 [ [[INC:%.*]], [[FOR_INC:%.*]] ], [ 0, [[IF_END]] ]
+; CHECK-NEXT:    [[CMP7:%.*]] = icmp sle i64 [[TMP1]], 1
+; CHECK-NEXT:    br i1 [[CMP7]], label [[FOR_INC]], label [[FOR_END9:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i64 [[TMP1]], 1
+; CHECK-NEXT:    br label [[FOR_COND6]]
+; CHECK:       for.end9:
+; CHECK-NEXT:    br i1 true, label [[IF_THEN11:%.*]], label [[IF_END12:%.*]]
+; CHECK:       if.then11:
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       if.end12:
+; CHECK-NEXT:    store i8 undef, i8* null
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[CLEANUP_DEST:%.*]] = phi i32 [ undef, [[IF_END12]] ], [ 1, [[IF_THEN11]] ], [ 9, [[IF_THEN]] ]
+; CHECK-NEXT:    switch i32 [[CLEANUP_DEST]], label [[CLEANUP14]] [
+; CHECK-NEXT:    i32 0, label [[FOR_COND4]]
+; CHECK-NEXT:    i32 9, label [[FOR_END13:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       for.end13:
+; CHECK-NEXT:    br label [[CLEANUP14]]
+; CHECK:       cleanup14:
+; CHECK-NEXT:    [[CLEANUP_DEST15:%.*]] = phi i32 [ 0, [[FOR_END13]] ], [ [[CLEANUP_DEST]], [[CLEANUP]] ], [ 1, [[FOR_BODY3]] ]
+; CHECK-NEXT:    [[COND1:%.*]] = icmp eq i32 [[CLEANUP_DEST15]], 0
+; CHECK-NEXT:    br i1 [[COND1]], label [[FOR_INC17]], label [[CLEANUP20:%.*]]
+; CHECK:       for.inc17:
+; CHECK-NEXT:    [[INC18]] = add nsw i32 [[TMP0]], 1
+; CHECK-NEXT:    br label [[FOR_COND1]]
+; CHECK:       for.end19:
+; CHECK-NEXT:    br label [[CLEANUP20]]
+; CHECK:       cleanup20:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ true, [[FOR_END19]] ], [ [[COND1]], [[CLEANUP14]] ]
+; CHECK-NEXT:    [[CLEANUP_DEST21:%.*]] = phi i32 [ [[CLEANUP_DEST15]], [[CLEANUP14]] ], [ 0, [[FOR_END19]] ]
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[FOR_COND]], label [[CLEANUP23:%.*]]
+; CHECK:       cleanup23:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %cleanup20, %entry
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.inc17, %for.cond
+  %0 = phi i32 [ %inc18, %for.inc17 ], [ 0, %for.cond ]
+  %cmp = icmp sle i32 %0, 1
+  br i1 %cmp, label %for.body, label %for.end19
+
+for.body:                                         ; preds = %for.cond1
+  %tobool = icmp ne i32 undef, 0
+  br i1 %tobool, label %for.body3, label %for.body.for.cond4_crit_edge
+
+for.body.for.cond4_crit_edge:                     ; preds = %for.body
+  br label %for.cond4
+
+for.body3:                                        ; preds = %for.body
+  br label %cleanup14
+
+for.cond4:                                        ; preds = %cleanup, %for.body.for.cond4_crit_edge
+  br i1 undef, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.cond4
+  br label %cleanup
+
+if.end:                                           ; preds = %for.cond4
+  br label %for.cond6
+
+for.cond6:                                        ; preds = %for.inc, %if.end
+  %1 = phi i64 [ %inc, %for.inc ], [ 0, %if.end ]
+  %cmp7 = icmp sle i64 %1, 1
+  br i1 %cmp7, label %for.inc, label %for.end9
+
+for.inc:                                          ; preds = %for.cond6
+  %inc = add nsw i64 %1, 1
+  br label %for.cond6
+
+for.end9:                                         ; preds = %for.cond6
+  br i1 true, label %if.then11, label %if.end12
+
+if.then11:                                        ; preds = %for.end9
+  br label %cleanup
+
+if.end12:                                         ; preds = %for.end9
+  br label %cleanup
+
+cleanup:                                          ; preds = %if.end12, %if.then11, %if.then
+  %cleanup.dest = phi i32 [ undef, %if.end12 ], [ 1, %if.then11 ], [ 9, %if.then ]
+  switch i32 %cleanup.dest, label %cleanup14 [
+  i32 0, label %for.cond4
+  i32 9, label %for.end13
+  ]
+
+for.end13:                                        ; preds = %cleanup
+  br label %cleanup14
+
+cleanup14:                                        ; preds = %for.end13, %cleanup, %for.body3
+  %cleanup.dest15 = phi i32 [ 0, %for.end13 ], [ %cleanup.dest, %cleanup ], [ 1, %for.body3 ]
+  %cond1 = icmp eq i32 %cleanup.dest15, 0
+  br i1 %cond1, label %for.inc17, label %cleanup20
+
+for.inc17:                                        ; preds = %cleanup14
+  %inc18 = add nsw i32 %0, 1
+  br label %for.cond1
+
+for.end19:                                        ; preds = %for.cond1
+  br label %cleanup20
+
+cleanup20:                                        ; preds = %for.end19, %cleanup14
+  %cleanup.dest21 = phi i32 [ %cleanup.dest15, %cleanup14 ], [ 0, %for.end19 ]
+  %cond = icmp eq i32 %cleanup.dest21, 0
+  br i1 %cond, label %for.cond, label %cleanup23
+
+cleanup23:                                        ; preds = %cleanup20
+  ret void
+}
diff --git a/llvm/test/Transforms/NewGVN/pr42557-changed-after-1.ll b/llvm/test/Transforms/NewGVN/pr42557-changed-after-1.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/NewGVN/pr42557-changed-after-1.ll
@@ -0,0 +1,68 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -newgvn < %s | FileCheck %s
+
+; Test for PR42557.
+
+declare void @use1(i1)
+declare i1 @get1()
+
+define void @hoge(i32 %tmp6) {
+; CHECK-LABEL: @hoge(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[A:%.*]] = call i1 @get1()
+; CHECK-NEXT:    [[B:%.*]] = call i1 @get1()
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ [[TMP6:%.*]], [[BB1]] ]
+; CHECK-NEXT:    br i1 [[A]], label [[BB2:%.*]], label [[BB1]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[B]], label [[BB16:%.*]], label [[BB11:%.*]]
+; CHECK:       bb16:
+; CHECK-NEXT:    [[TMP17:%.*]] = add i32 [[TMP]], 1
+; CHECK-NEXT:    br label [[BB11]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i32 [ [[TMP17]], [[BB16]] ], [ 0, [[BB2]] ]
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i32 [[TMP12]], 0
+; CHECK-NEXT:    call void @use1(i1 [[TMP13]])
+; CHECK-NEXT:    [[TMP15:%.*]] = icmp ne i32 [[TMP]], 0
+; CHECK-NEXT:    br i1 [[TMP15]], label [[BB18:%.*]], label [[BB19:%.*]]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB19]]
+; CHECK:       bb19:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ [[TMP13]], [[BB11]] ], [ false, [[BB18]] ]
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i32 [ [[TMP12]], [[BB11]] ], [ 1, [[BB18]] ]
+; CHECK-NEXT:    call void @use1(i1 [[PHIOFOPS]])
+; CHECK-NEXT:    ret void
+;
+bb:
+  %A = call i1 @get1()
+  %B = call i1 @get1()
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp = phi i32 [ 0, %bb ], [ %tmp6, %bb1 ]
+  br i1 %A, label %bb2, label %bb1
+
+bb2:                                              ; preds = %bb1
+  br i1 %B, label %bb16, label %bb11
+
+bb16:                                             ; preds = %bb2
+  %tmp17 = add i32 %tmp, 1
+  br label %bb11
+
+bb11:                                             ; preds = %bb16, %bb2
+  %tmp12 = phi i32 [ %tmp17, %bb16 ], [ 0, %bb2 ]
+  %tmp13 = icmp eq i32 %tmp12, 0
+  call void @use1(i1 %tmp13)
+  %tmp15 = icmp ne i32 %tmp, 0
+  br i1 %tmp15, label %bb18, label %bb19
+
+bb18:                                             ; preds = %bb11
+  br label %bb19
+
+bb19:                                             ; preds = %bb18, %bb11
+  %tmp20 = phi i32 [ %tmp12, %bb11 ], [ 1, %bb18 ]
+  %tmp21 = icmp eq i32 %tmp20, 0
+  call void @use1(i1 %tmp21)
+  ret void
+}