diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index cbb27a5..042c7fc 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -250,6 +250,13 @@
     Value *PHITranslatePointer(Value *V,
                                BasicBlock *CurBB, BasicBlock *PredBB,
                                const TargetData *TD) const;
+
+    /// InsertPHITranslatedPointer - Insert a computation of the PHI translated
+    /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
+    /// block.
+    Value *InsertPHITranslatedPointer(Value *V,
+                                      BasicBlock *CurBB, BasicBlock *PredBB,
+                                      const TargetData *TD) const;
     
     /// removeInstruction - Remove an instruction from the dependence analysis,
     /// updating the dependence of instructions that previously depended on it.
diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index bb5b76c..95e9437 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -752,19 +752,35 @@
   // Handle getelementptr with at least one PHI operand.
   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
     SmallVector<Value*, 8> GEPOps;
-    Value *APHIOp = 0;
     BasicBlock *CurBB = GEP->getParent();
     for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
-      GEPOps.push_back(GEP->getOperand(i)->DoPHITranslation(CurBB, Pred));
-      if (!isa<Constant>(GEPOps.back()))
-        APHIOp = GEPOps.back();
+      Value *GEPOp = GEP->getOperand(i);
+      // No PHI translation is needed of operands whose values are live in to
+      // the predecessor block.
+      if (!isa<Instruction>(GEPOp) ||
+          cast<Instruction>(GEPOp)->getParent() != CurBB) {
+        GEPOps.push_back(GEPOp);
+        continue;
+      }
+      
+      // If the operand is a phi node, do phi translation.
+      if (PHINode *PN = dyn_cast<PHINode>(GEPOp)) {
+        GEPOps.push_back(PN->getIncomingValueForBlock(Pred));
+        continue;
+      }
+      
+      // Otherwise, we can't PHI translate this random value defined in this
+      // block.
+      return 0;
     }
     
     // Simplify the GEP to handle 'gep x, 0' -> x etc.
     if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD))
       return V;
-    
+
+
     // Scan to see if we have this GEP available.
+    Value *APHIOp = GEPOps[0];
     for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end();
          UI != E; ++UI) {
       if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
@@ -787,6 +803,52 @@
   return 0;
 }
 
+/// InsertPHITranslatedPointer - Insert a computation of the PHI translated
+/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
+/// block.
+///
+/// This is only called when PHITranslatePointer returns a value that doesn't
+/// dominate the block, so we don't need to handle the trivial cases here.
+Value *MemoryDependenceAnalysis::
+InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB,
+                           BasicBlock *PredBB, const TargetData *TD) const {
+  // If the input value isn't an instruction in CurBB, it doesn't need phi
+  // translation.
+  Instruction *Inst = cast<Instruction>(InVal);
+  assert(Inst->getParent() == CurBB && "Doesn't need phi trans");
+
+  // Handle bitcast of PHI.
+  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
+    PHINode *BCPN = cast<PHINode>(BC->getOperand(0));
+    Value *PHIIn = BCPN->getIncomingValueForBlock(PredBB);
+    
+    // Otherwise insert a bitcast at the end of PredBB.
+    return new BitCastInst(PHIIn, InVal->getType(),
+                           InVal->getName()+".phi.trans.insert",
+                           PredBB->getTerminator());
+  }
+  
+  // Handle getelementptr with at least one PHI operand.
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
+    SmallVector<Value*, 8> GEPOps;
+    Value *APHIOp = 0;
+    BasicBlock *CurBB = GEP->getParent();
+    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
+      GEPOps.push_back(GEP->getOperand(i)->DoPHITranslation(CurBB, PredBB));
+      if (!isa<Constant>(GEPOps.back()))
+        APHIOp = GEPOps.back();
+    }
+    
+    GetElementPtrInst *Result = 
+      GetElementPtrInst::Create(GEPOps[0], GEPOps.begin()+1, GEPOps.end(),
+                                InVal->getName()+".phi.trans.insert",
+                                PredBB->getTerminator());
+    Result->setIsInBounds(GEP->isInBounds());
+    return Result;
+  }
+  
+  return 0;
+}
 
 /// getNonLocalPointerDepFromBB - Perform a dependency query based on
 /// pointer/pointeesize starting at the end of StartBB.  Add any clobber/def
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index e878050..72eb900 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1425,32 +1425,40 @@
   assert(UnavailablePred != 0 &&
          "Fully available value should be eliminated above!");
 
-  // If the loaded pointer is PHI node defined in this block, do PHI translation
-  // to get its value in the predecessor.
-  Value *LoadPtr = MD->PHITranslatePointer(LI->getOperand(0),
-                                           LoadBB, UnavailablePred, TD);
-  if (LoadPtr == 0) {
-    DEBUG(errs() << "COULDN'T PRE LOAD BECAUSE PTR CAN'T BE PHI TRANSLATED: "
-          << *LI->getOperand(0) << '\n' << *LI << "\n");
-    return false;
-  }
-
-  // Make sure the value is live in the predecessor.  If it was defined by a
-  // non-PHI instruction in this block, we don't know how to recompute it above.
-  if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr))
-    if (!DT->dominates(LPInst->getParent(), UnavailablePred)) {
-      DEBUG(errs() << "COULDN'T PRE LOAD BECAUSE PTR DOES NOT DOMINATE PRED: "
-                   << *LPInst << '\n' << *LI << "\n");
-      return false;
-    }
-
   // We don't currently handle critical edges :(
   if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) {
     DEBUG(errs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
                  << UnavailablePred->getName() << "': " << *LI << '\n');
     return false;
   }
+  
+  // If the loaded pointer is PHI node defined in this block, do PHI translation
+  // to get its value in the predecessor.
+  Value *LoadPtr = MD->PHITranslatePointer(LI->getOperand(0),
+                                           LoadBB, UnavailablePred, TD);
+  // Make sure the value is live in the predecessor.  MemDep found a computation
+  // of LPInst with the right value, but that does not dominate UnavailablePred,
+  // then we can't use it.
+  if (Instruction *LPInst = dyn_cast_or_null<Instruction>(LoadPtr))
+    if (!DT->dominates(LPInst->getParent(), UnavailablePred))
+      LoadPtr = 0;
 
+  // If we don't have a computation of this phi translated value, try to insert
+  // one.
+  if (LoadPtr == 0) {
+    LoadPtr = MD->InsertPHITranslatedPointer(LI->getOperand(0),
+                                             LoadBB, UnavailablePred, TD);
+    if (LoadPtr == 0) {
+      DEBUG(errs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
+                   << *LI->getOperand(0) << "\n");
+      return false;
+    }
+    
+    // FIXME: This inserts a computation, but we don't tell scalar GVN
+    // optimization stuff about it.  How do we do this?
+    DEBUG(errs() << "INSERTED PHI TRANSLATED VALUE: " << *LoadPtr << "\n");
+  }
+  
   // Make sure it is valid to move this load here.  We have to watch out for:
   //  @1 = getelementptr (i8* p, ...
   //  test p and branch if == 0
diff --git a/test/Transforms/GVN/pre-load.ll b/test/Transforms/GVN/pre-load.ll
index 637a6d2..3cb6713 100644
--- a/test/Transforms/GVN/pre-load.ll
+++ b/test/Transforms/GVN/pre-load.ll
@@ -22,6 +22,7 @@
 ; CHECK-NEXT: ret i32
 }
 
+; This is a simple phi translation case.
 define i32 @test2(i32* %p, i32* %q, i1 %C) {
 ; CHECK: @test2
 block1:
@@ -46,6 +47,7 @@
 ; CHECK: ret i32
 }
 
+; This is a PRE case that requires phi translation through a GEP.
 define i32 @test3(i32* %p, i32* %q, i32** %Hack, i1 %C) {
 ; CHECK: @test3
 block1:
@@ -73,3 +75,35 @@
 ; CHECK-NOT: load
 ; CHECK: ret i32
 }
+
+;; Here the loaded address is available, but the computation is in 'block3'
+;; which does not dominate 'block2'.
+define i32 @test4(i32* %p, i32* %q, i32** %Hack, i1 %C) {
+; CHECK: @test4
+block1:
+	br i1 %C, label %block2, label %block3
+
+block2:
+ br label %block4
+; CHECK: block2:
+; CHECK:   load i32*
+; CHECK:   br label %block4
+
+block3:
+  %B = getelementptr i32* %q, i32 1
+  store i32* %B, i32** %Hack
+
+  %A = getelementptr i32* %p, i32 1
+  store i32 0, i32* %A
+  br label %block4
+
+block4:
+  %P2 = phi i32* [%p, %block3], [%q, %block2]
+  %P3 = getelementptr i32* %P2, i32 1
+  %PRE = load i32* %P3
+  ret i32 %PRE
+; CHECK: block4:
+; CHECK-NEXT: phi i32 [
+; CHECK-NOT: load
+; CHECK: ret i32
+}