Index: lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- lib/Transforms/Scalar/NewGVN.cpp
+++ lib/Transforms/Scalar/NewGVN.cpp
@@ -1777,10 +1777,15 @@
       if (PI == LastPredInfo)
         continue;
       LastPredInfo = PI;
-
-      // TODO: Along the false edge, we may know more things too, like icmp of
+      // In phi of ops cases, we may have predicate info that we are evaluating
+      // in a different context.
+      if (!DT->dominates(PBranch->To, getBlockForValue(I)))
+        continue;
+      // TODO: Along the false edge, we may know more things too, like
+      // icmp of
       // same operands is false.
-      // TODO: We only handle actual comparison conditions below, not and/or.
+      // TODO: We only handle actual comparison conditions below, not
+      // and/or.
       auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
       if (!BranchCond)
         continue;
@@ -2528,11 +2533,13 @@
         // and make sure anything that tries to add it's DFS number is
         // redirected to the instruction we are making a phi of ops
         // for.
+        TempToBlock.insert({ValueOp, PredBB});
         InstrDFS.insert({ValueOp, IDFSNum});
         const Expression *E = performSymbolicEvaluation(ValueOp, Visited);
         InstrDFS.erase(ValueOp);
         AllTempInstructions.erase(ValueOp);
         ValueOp->deleteValue();
+        TempToBlock.erase(ValueOp);
         if (MemAccess)
           TempToMemory.erase(ValueOp);
         if (!E)
Index: test/Transforms/NewGVN/pr34135.ll
===================================================================
--- /dev/null
+++ test/Transforms/NewGVN/pr34135.ll
@@ -0,0 +1,44 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -newgvn -enable-phi-of-ops=true -S | FileCheck %s
+;; Make sure we don't incorrectly use predicateinfo to simplify phi of ops cases
+source_filename = "pr34135.ll"
+
+define void @snork(i32 %arg) {
+; CHECK-LABEL: @snork(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = sext i32 [[ARG:%.*]] to i64
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ 0, [[BB:%.*]] ], [ [[TMP3:%.*]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP3]] = add i64 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i64 [[TMP3]], [[TMP]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[BB1]], label [[BB7:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp sgt i64 [[TMP]], 1
+; CHECK-NEXT:    br i1 [[TMP6]], label [[BB7]], label [[BB9:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    unreachable
+;
+bb:
+  %tmp = sext i32 %arg to i64
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp2 = phi i64 [ 0, %bb ], [ %tmp3, %bb1 ]
+  %tmp3 = add i64 %tmp2, 1
+  %tmp4 = icmp slt i64 %tmp3, %tmp
+  br i1 %tmp4, label %bb1, label %bb7
+
+bb5:                                              ; preds = %bb7
+  %tmp6 = icmp sgt i64 %tmp8, 1
+  br i1 %tmp6, label %bb7, label %bb9
+
+bb7:                                              ; preds = %bb5, %bb1
+  %tmp8 = phi i64 [ undef, %bb5 ], [ %tmp, %bb1 ]
+  br label %bb5
+
+bb9:                                              ; preds = %bb5
+  unreachable
+}