Index: lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- lib/Transforms/Scalar/NewGVN.cpp
+++ lib/Transforms/Scalar/NewGVN.cpp
@@ -2808,6 +2808,12 @@
     }
     auto *ValuePHI = RealToTemp.lookup(I);
     bool NewPHI = false;
+    // We cannot re-use an existing ValuePHI, if the number of operands
+    // does not match.
+    if(ValuePHI && ValuePHI->getNumOperands() != OpPHI->getNumOperands()) {
+      removePhiOfOps(I, ValuePHI);
+      ValuePHI = nullptr;
+    }
     if (!ValuePHI) {
       ValuePHI =
           PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
Index: test/Transforms/NewGVN/phi-of-ops-move-block.ll
===================================================================
--- test/Transforms/NewGVN/phi-of-ops-move-block.ll
+++ test/Transforms/NewGVN/phi-of-ops-move-block.ll
@@ -54,3 +54,54 @@
 end:
   ret void
 }
+
+; In this test case a temporary PhiOfOps node gets moved to BB with more
+; predecessors, so a new one needs to be created.
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i32 [ 0, [[TMP0:%.*]] ], [ [[ADD:%.*]], [[CRITEDGE:%.*]] ]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[STOREMERGE]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[LR_PH:%.*]], label [[CRITEDGE]]
+; CHECK:       lr.ph:
+; CHECK-NEXT:    br i1 undef, label [[SPLIT1:%.*]], label [[SPLIT2:%.*]]
+; CHECK:       split1:
+; CHECK-NEXT:    br label [[CRITEDGE]]
+; CHECK:       split2:
+; CHECK-NEXT:    br label [[CRITEDGE]]
+; CHECK:       critedge:
+; CHECK-NEXT:    [[PHIOFOPS1:%.*]] = phi i1 [ false, [[BB1]] ], [ true, [[SPLIT2]] ], [ true, [[SPLIT1]] ]
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ undef, [[BB1]] ], [ undef, [[SPLIT2]] ], [ undef, [[SPLIT1]] ]
+; CHECK-NEXT:    [[LCSSA:%.*]] = phi i32 [ 0, [[BB1]] ], [ -1, [[SPLIT1]] ], [ -1, [[SPLIT2]] ]
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[STOREMERGE]], -1
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], label [[BB1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+  br label %bb1
+
+bb1:                                      ; preds = %critedge, %0
+  %storemerge = phi i32 [ 0, %0 ], [ %add, %critedge ]
+  %cmp1 = icmp eq i32 %storemerge, 0
+  br i1 %cmp1, label %lr.ph, label %critedge
+
+lr.ph:                                           ; preds = %bb1
+  br i1 undef, label %split1, label %split2
+
+split1:                                     ; preds = %lr.ph
+  br label %critedge
+
+split2:                                     ; preds = %lr.ph
+  br label %critedge
+
+critedge:                                        ; preds = %split1, %split2, %bb1
+  %lcssa = phi i32 [ 0, %bb1 ], [ -1, %split1 ], [ -1, %split2 ]
+  %cmp2 = icmp ne i32 %lcssa, 0
+  %brmerge = or i1 %cmp1, %cmp2
+  %add = add nsw i32 %storemerge, -1
+  br i1 %brmerge, label %bb1, label %exit
+
+exit:                                      ; preds = %critedge
+  ret void
+}