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,72 @@
+; 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.
+
+@0 = internal global i32 0, align 4
+@z = external global i32, align 4
+
+declare void @foo(i32*)
+
+; Function Attrs: norecurse
+define void @test1(i32* %arg) #0 {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[I12:%.*]] = load i32, i32* [[ARG:%.*]], align 4
+; CHECK-NEXT:    [[I14:%.*]] = load i32, i32* @z, align 4
+; CHECK-NEXT:    switch i32 [[I14]], label [[BB15:%.*]] [
+; CHECK-NEXT:    i32 0, label [[BB16:%.*]]
+; CHECK-NEXT:    i32 2, label [[BB20:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       bb15:
+; CHECK-NEXT:    ret void
+; CHECK:       bb16:
+; CHECK-NEXT:    [[I18:%.*]] = shl i32 [[I12]], 2
+; CHECK-NEXT:    [[I19:%.*]] = getelementptr inbounds i32, i32* null, i32 [[I18]]
+; CHECK-NEXT:    tail call void @foo(i32* [[I19]])
+; CHECK-NEXT:    br label [[BB24:%.*]]
+; CHECK:       bb20:
+; CHECK-NEXT:    [[I22:%.*]] = shl i32 [[I12]], 2
+; CHECK-NEXT:    [[I23:%.*]] = getelementptr inbounds i32, i32* null, i32 [[I22]]
+; CHECK-NEXT:    tail call void @foo(i32* [[I23]])
+; CHECK-NEXT:    br label [[BB24]]
+; CHECK:       bb24:
+; CHECK-NEXT:    [[I27_PRE_PHI:%.*]] = phi i32 [ [[I22]], [[BB20]] ], [ [[I18]], [[BB16]] ]
+; CHECK-NEXT:    [[I28:%.*]] = getelementptr inbounds i32, i32* null, i32 [[I27_PRE_PHI]]
+; CHECK-NEXT:    [[I29:%.*]] = load i32, i32* [[I28]], align 4
+; CHECK-NEXT:    store i32 [[I29]], i32* @z, align 4
+; CHECK-NEXT:    br label [[BB20]]
+;
+bb:
+  %i12 = load i32, i32* %arg, align 4
+  %i14 = load i32, i32* @z, align 4
+  switch i32 %i14, label %bb15 [
+  i32 0, label %bb16
+  i32 2, label %bb20
+  ]
+
+bb15:                                             ; preds = %bb
+  ret void
+
+bb16:                                             ; preds = %bb
+  %i18 = shl i32 %i12, 2
+  %i19 = getelementptr inbounds i32, i32* null, i32 %i18
+  tail call void @foo(i32* %i19)
+  br label %bb24
+
+bb20:                                             ; preds = %bb24, %bb
+  %i22 = shl i32 %i12, 2
+  %i23 = getelementptr inbounds i32, i32* null, i32 %i22
+  tail call void @foo(i32* %i23)
+  br label %bb24
+
+bb24:                                             ; preds = %bb20, %bb16
+  %i27 = shl i32 %i12, 2
+  %i28 = getelementptr inbounds i32, i32* null , i32 %i27
+  %i29 = load i32, i32* %i28, align 4
+  store i32 %i29, i32* @z, align 4
+  br label %bb20
+}
+
+attributes #0 = { norecurse }