Index: llvm/lib/Transforms/Scalar/GVN.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/GVN.cpp
+++ llvm/lib/Transforms/Scalar/GVN.cpp
@@ -2031,9 +2031,12 @@
   return Changed;
 }
 
-static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
+static void patchAndReplaceAllUsesWith(DominatorTree *DT, Instruction *I, Value *Repl) {
   patchReplacementInstruction(I, Repl);
-  I->replaceAllUsesWith(Repl);
+  // Replace I with Repl everywhere it does not violate the dominator tree.
+  I->replaceUsesWithIf(Repl, [&Repl,&DT](Use &U) {
+                        return DT->dominates(Repl, U); 
+  });
 }
 
 /// Attempt to eliminate a load, first by eliminating it
@@ -2074,7 +2077,7 @@
     Value *AvailableValue = AV.MaterializeAdjustedValue(L, L, *this);
 
     // Replace the load!
-    patchAndReplaceAllUsesWith(L, AvailableValue);
+    patchAndReplaceAllUsesWith(DT, L, AvailableValue);
     markInstructionForDeletion(L);
     if (MSSAU)
       MSSAU->removeMemoryAccess(L);
@@ -2583,10 +2586,12 @@
   }
 
   // Remove it!
-  patchAndReplaceAllUsesWith(I, Repl);
-  if (MD && Repl->getType()->isPtrOrPtrVectorTy())
-    MD->invalidateCachedPointerInfo(Repl);
-  markInstructionForDeletion(I);
+  patchAndReplaceAllUsesWith(DT, I, Repl);
+  if (I->uses().empty()) {
+    if (MD && Repl->getType()->isPtrOrPtrVectorTy())
+      MD->invalidateCachedPointerInfo(Repl);
+    markInstructionForDeletion(I);
+  }
   return true;
 }
 
Index: llvm/test/Transforms/GVN/load-pre-identical-branches.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/GVN/load-pre-identical-branches.ll
@@ -0,0 +1,42 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -gvn -S < %s | FileCheck %s
+
+; Check that PRE-LOAD with two identical branches does not
+; result in invalid dominator tree.
+declare void @use(i32)
+
+define void @test1(i1 %c, i32 %arg) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[SHL1:%.*]] = shl i32 [[ARG:%.*]], 2
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[SHL2:%.*]] = shl i32 [[ARG]], 2
+; CHECK-NEXT:    call void @use(i32 [[SHL2]])
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[SHL3_PRE_PHI:%.*]] = phi i32 [ [[SHL2]], [[BB2]] ], [ [[SHL1]], [[BB1]] ]
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, ptr null, i32 [[SHL3_PRE_PHI]]
+; CHECK-NEXT:    [[V:%.*]] = load i32, ptr [[GEP]], align 4
+; CHECK-NEXT:    call void @use(i32 [[V]])
+; CHECK-NEXT:    br label [[BB2]]
+;
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  %shl1 = shl i32 %arg, 2
+  br label %bb3
+
+bb2:
+  %shl2 = shl i32 %arg, 2
+  call void @use(i32 %shl2)
+  br label %bb3
+
+bb3:
+  %shl3 = shl i32 %arg, 2
+  %gep = getelementptr i32, ptr null, i32 %shl3
+  %v = load i32, ptr %gep, align 4
+  call void @use(i32 %v)
+  br label %bb2
+}