Index: lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- lib/Transforms/Scalar/NewGVN.cpp
+++ lib/Transforms/Scalar/NewGVN.cpp
@@ -2686,6 +2686,11 @@
   auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);
   if (!FoundVal) {
     ExpressionToPhiOfOps[E].insert(OrigInst);
+    // Also force re-evaluation if any of the expressions operands change,
+    // as that could lead to a different result for the symbolic evaluation.
+    if (auto *BE = dyn_cast<BasicExpression>(E))
+      for (auto &Op : BE->operands())
+        ExpressionToPhiOfOps[createVariableOrConstant(Op)].insert(OrigInst);
     DEBUG(dbgs() << "Cannot find phi of ops operand for " << *TransInst
                  << " in block " << getBlockName(PredBB) << "\n");
     return nullptr;
Index: test/Transforms/NewGVN/pr35074-phi-of-ops-expr-operand-change-cases-change.ll
===================================================================
--- /dev/null
+++ test/Transforms/NewGVN/pr35074-phi-of-ops-expr-operand-change-cases-change.ll
@@ -0,0 +1,40 @@
+; RUN: opt < %s -newgvn -S | FileCheck %s
+
+; CHECK-LABEL: WhileBody:
+; br i1 false, label %BoundsCheckFail275, label %BoundsCheckOk276
+; CHECK-LABEL: WhileEnd:
+
+define void @sort(i64 %.16) {
+Entry:
+  %0 = extractvalue { i64, i1 } undef, 0
+  %1 = lshr i64 %0, 2
+  br i1 undef, label %DivZeroFail2.i, label %WhileBody.lr.ph
+
+DivZeroFail2.i:                                   ; preds = %Entry
+  unreachable
+
+WhileBody.lr.ph:                                  ; preds = %Entry
+  %2 = udiv i64 %.16, %1
+  br label %WhileBody
+
+WhileBody:                                        ; preds = %BoundsCheckOk276, %WhileBody.lr.ph
+  %iterator = phi i64 [ 0, %WhileBody.lr.ph ], [ %6, %BoundsCheckOk276 ]
+  %3 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %iterator, i64 %2)
+  %4 = extractvalue { i64, i1 } %3, 0
+  %5 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %4, i64 1)
+  %6 = extractvalue { i64, i1 } %5, 0
+  %7 = icmp ugt i64 %iterator, %.16
+  br i1 %7, label %BoundsCheckFail275, label %BoundsCheckOk276
+
+WhileEnd:                                         ; preds = %BoundsCheckOk276
+  ret void
+
+BoundsCheckFail275:                               ; preds = %WhileBody
+  unreachable
+
+BoundsCheckOk276:                                 ; preds = %WhileBody
+  %8 = icmp ult i64 %6, %.16
+  br i1 %8, label %WhileBody, label %WhileEnd
+}
+
+declare { i64, i1 } @llvm.uadd.with.overflow.i64(i64, i64)