1 files changed, 396 insertions, 68 deletions

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index 0ec0e74233b3..ae6f970eff4c 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -20,6 +20,8 @@
 #include "llvm/IntrinsicInst.h"
 #include "llvm/Function.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
@@ -117,10 +119,6 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
       Pointer = Inst->getOperand(1);
       // calls to free() erase the entire structure
       PointerSize = ~0ULL;
-    } else if (isFreeCall(Inst)) {
-      Pointer = Inst->getOperand(0);
-      // calls to free() erase the entire structure
-      PointerSize = ~0ULL;
     } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
       // Debug intrinsics don't cause dependences.
       if (isa<DbgInfoIntrinsic>(Inst)) continue;
@@ -174,7 +172,7 @@ MemDepResult MemoryDependenceAnalysis::
 getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, 
                          BasicBlock::iterator ScanIt, BasicBlock *BB) {
 
-  Value* invariantTag = 0;
+  Value *invariantTag = 0;
 
   // Walk backwards through the basic block, looking for dependencies.
   while (ScanIt != BB->begin()) {
@@ -185,12 +183,12 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad,
     if (invariantTag == Inst) {
       invariantTag = 0;
       continue;
-    } else if (IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst)) {
+    } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
       // If we pass an invariant-end marker, then we've just entered an
       // invariant region and can start ignoring dependencies.
       if (II->getIntrinsicID() == Intrinsic::invariant_end) {
         uint64_t invariantSize = ~0ULL;
-        if (ConstantInt* CI = dyn_cast<ConstantInt>(II->getOperand(2)))
+        if (ConstantInt *CI = dyn_cast<ConstantInt>(II->getOperand(2)))
           invariantSize = CI->getZExtValue();
         
         AliasAnalysis::AliasResult R =
@@ -203,9 +201,9 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad,
       // If we reach a lifetime begin or end marker, then the query ends here
       // because the value is undefined.
       } else if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
-                   II->getIntrinsicID() == Intrinsic::lifetime_end) {
+                 II->getIntrinsicID() == Intrinsic::lifetime_end) {
         uint64_t invariantSize = ~0ULL;
-        if (ConstantInt* CI = dyn_cast<ConstantInt>(II->getOperand(1)))
+        if (ConstantInt *CI = dyn_cast<ConstantInt>(II->getOperand(1)))
           invariantSize = CI->getZExtValue();
 
         AliasAnalysis::AliasResult R =
@@ -371,20 +369,41 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
     // calls to free() erase the entire structure, not just a field.
     MemSize = ~0UL;
   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
-    CallSite QueryCS = CallSite::get(QueryInst);
-    bool isReadOnly = AA->onlyReadsMemory(QueryCS);
-    LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
-                                           QueryParent);
+    int IntrinsicID = 0;  // Intrinsic IDs start at 1.
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
+      IntrinsicID = II->getIntrinsicID();
+
+    switch (IntrinsicID) {
+      case Intrinsic::lifetime_start:
+      case Intrinsic::lifetime_end:
+      case Intrinsic::invariant_start:
+        MemPtr = QueryInst->getOperand(2);
+        MemSize = cast<ConstantInt>(QueryInst->getOperand(1))->getZExtValue();
+        break;
+      case Intrinsic::invariant_end:
+        MemPtr = QueryInst->getOperand(3);
+        MemSize = cast<ConstantInt>(QueryInst->getOperand(2))->getZExtValue();
+        break;
+      default:
+        CallSite QueryCS = CallSite::get(QueryInst);
+        bool isReadOnly = AA->onlyReadsMemory(QueryCS);
+        LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
+                                               QueryParent);
+    }
   } else {
     // Non-memory instruction.
     LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
   }
   
   // If we need to do a pointer scan, make it happen.
-  if (MemPtr)
-    LocalCache = getPointerDependencyFrom(MemPtr, MemSize, 
-                                          isa<LoadInst>(QueryInst),
-                                          ScanPos, QueryParent);
+  if (MemPtr) {
+    bool isLoad = !QueryInst->mayWriteToMemory();
+    if (IntrinsicInst *II = dyn_cast<MemoryUseIntrinsic>(QueryInst)) {
+      isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end;
+    }
+    LocalCache = getPointerDependencyFrom(MemPtr, MemSize, isLoad, ScanPos,
+                                          QueryParent);
+  }
   
   // Remember the result!
   if (Instruction *I = LocalCache.getInst())
@@ -688,6 +707,274 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
   }
 }
 
+/// isPHITranslatable - Return true if the specified computation is derived from
+/// a PHI node in the current block and if it is simple enough for us to handle.
+static bool isPHITranslatable(Instruction *Inst) {
+  if (isa<PHINode>(Inst))
+    return true;
+  
+  // We can handle bitcast of a PHI, but the PHI needs to be in the same block
+  // as the bitcast.
+  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
+    Instruction *OpI = dyn_cast<Instruction>(BC->getOperand(0));
+    if (OpI == 0 || OpI->getParent() != Inst->getParent())
+      return true;
+    return isPHITranslatable(OpI);
+  }
+  
+  // We can translate a GEP if all of its operands defined in this block are phi
+  // translatable. 
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
+    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
+      Instruction *OpI = dyn_cast<Instruction>(GEP->getOperand(i));
+      if (OpI == 0 || OpI->getParent() != Inst->getParent())
+        continue;
+      
+      if (!isPHITranslatable(OpI))
+        return false;
+    }
+    return true;
+  }
+  
+  if (Inst->getOpcode() == Instruction::Add &&
+      isa<ConstantInt>(Inst->getOperand(1))) {
+    Instruction *OpI = dyn_cast<Instruction>(Inst->getOperand(0));
+    if (OpI == 0 || OpI->getParent() != Inst->getParent())
+      return true;
+    return isPHITranslatable(OpI);
+  }
+
+  //   cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
+  //   if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
+  //     cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
+  
+  return false;
+}
+
+/// GetPHITranslatedValue - Given a computation that satisfied the
+/// isPHITranslatable predicate, see if we can translate the computation into
+/// the specified predecessor block.  If so, return that value.
+Value *MemoryDependenceAnalysis::
+GetPHITranslatedValue(Value *InVal, BasicBlock *CurBB, BasicBlock *Pred,
+                      const TargetData *TD) const {  
+  // If the input value is not an instruction, or if it is not defined in CurBB,
+  // then we don't need to phi translate it.
+  Instruction *Inst = dyn_cast<Instruction>(InVal);
+  if (Inst == 0 || Inst->getParent() != CurBB)
+    return InVal;
+  
+  if (PHINode *PN = dyn_cast<PHINode>(Inst))
+    return PN->getIncomingValueForBlock(Pred);
+  
+  // Handle bitcast of PHI.
+  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
+    // PHI translate the input operand.
+    Value *PHIIn = GetPHITranslatedValue(BC->getOperand(0), CurBB, Pred, TD);
+    if (PHIIn == 0) return 0;
+    
+    // Constants are trivial to phi translate.
+    if (Constant *C = dyn_cast<Constant>(PHIIn))
+      return ConstantExpr::getBitCast(C, BC->getType());
+    
+    // Otherwise we have to see if a bitcasted version of the incoming pointer
+    // is available.  If so, we can use it, otherwise we have to fail.
+    for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end();
+         UI != E; ++UI) {
+      if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI))
+        if (BCI->getType() == BC->getType())
+          return BCI;
+    }
+    return 0;
+  }
+
+  // Handle getelementptr with at least one PHI translatable operand.
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
+    SmallVector<Value*, 8> GEPOps;
+    BasicBlock *CurBB = GEP->getParent();
+    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
+      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.
+      Value *InOp = GetPHITranslatedValue(GEPOp, CurBB, Pred, TD);
+      if (InOp == 0) return 0;
+      
+      GEPOps.push_back(InOp);
+    }
+    
+    // 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))
+        if (GEPI->getType() == GEP->getType() &&
+            GEPI->getNumOperands() == GEPOps.size() &&
+            GEPI->getParent()->getParent() == CurBB->getParent()) {
+          bool Mismatch = false;
+          for (unsigned i = 0, e = GEPOps.size(); i != e; ++i)
+            if (GEPI->getOperand(i) != GEPOps[i]) {
+              Mismatch = true;
+              break;
+            }
+          if (!Mismatch)
+            return GEPI;
+        }
+    }
+    return 0;
+  }
+  
+  // Handle add with a constant RHS.
+  if (Inst->getOpcode() == Instruction::Add &&
+      isa<ConstantInt>(Inst->getOperand(1))) {
+    // PHI translate the LHS.
+    Value *LHS;
+    Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
+    Instruction *OpI = dyn_cast<Instruction>(Inst->getOperand(0));
+    bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
+    bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
+    
+    if (OpI == 0 || OpI->getParent() != Inst->getParent())
+      LHS = Inst->getOperand(0);
+    else {
+      LHS = GetPHITranslatedValue(Inst->getOperand(0), CurBB, Pred, TD);
+      if (LHS == 0)
+        return 0;
+    }
+    
+    // If the PHI translated LHS is an add of a constant, fold the immediates.
+    if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
+      if (BOp->getOpcode() == Instruction::Add)
+        if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
+          LHS = BOp->getOperand(0);
+          RHS = ConstantExpr::getAdd(RHS, CI);
+          isNSW = isNUW = false;
+        }
+    
+    // See if the add simplifies away.
+    if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD))
+      return Res;
+    
+    // Otherwise, see if we have this add available somewhere.
+    for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end();
+         UI != E; ++UI) {
+      if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*UI))
+        if (BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
+            BO->getParent()->getParent() == CurBB->getParent())
+          return BO;
+    }
+    
+    return 0;
+  }
+  
+  return 0;
+}
+
+/// GetAvailablePHITranslatePointer - Return the value computed by
+/// PHITranslatePointer if it dominates PredBB, otherwise return null.
+Value *MemoryDependenceAnalysis::
+GetAvailablePHITranslatedValue(Value *V,
+                               BasicBlock *CurBB, BasicBlock *PredBB,
+                               const TargetData *TD,
+                               const DominatorTree &DT) const {
+  // See if PHI translation succeeds.
+  V = GetPHITranslatedValue(V, CurBB, PredBB, TD);
+  if (V == 0) return 0;
+  
+  // Make sure the value is live in the predecessor.
+  if (Instruction *Inst = dyn_cast_or_null<Instruction>(V))
+    if (!DT.dominates(Inst->getParent(), PredBB))
+      return 0;
+  return V;
+}
+
+
+/// InsertPHITranslatedPointer - Insert a computation of the PHI translated
+/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
+/// block.  All newly created instructions are added to the NewInsts list.
+///
+Value *MemoryDependenceAnalysis::
+InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB,
+                           BasicBlock *PredBB, const TargetData *TD,
+                           const DominatorTree &DT,
+                           SmallVectorImpl<Instruction*> &NewInsts) const {
+  // See if we have a version of this value already available and dominating
+  // PredBB.  If so, there is no need to insert a new copy.
+  if (Value *Res = GetAvailablePHITranslatedValue(InVal, CurBB, PredBB, TD, DT))
+    return Res;
+  
+  // If we don't have an available version of this value, it must be an
+  // instruction.
+  Instruction *Inst = cast<Instruction>(InVal);
+  
+  // Handle bitcast of PHI translatable value.
+  if (BitCastInst *BC = dyn_cast<BitCastInst>(Inst)) {
+    Value *OpVal = InsertPHITranslatedPointer(BC->getOperand(0),
+                                              CurBB, PredBB, TD, DT, NewInsts);
+    if (OpVal == 0) return 0;
+      
+    // Otherwise insert a bitcast at the end of PredBB.
+    BitCastInst *New = new BitCastInst(OpVal, InVal->getType(),
+                                       InVal->getName()+".phi.trans.insert",
+                                       PredBB->getTerminator());
+    NewInsts.push_back(New);
+    return New;
+  }
+  
+  // Handle getelementptr with at least one PHI operand.
+  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
+    SmallVector<Value*, 8> GEPOps;
+    BasicBlock *CurBB = GEP->getParent();
+    for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) {
+      Value *OpVal = InsertPHITranslatedPointer(GEP->getOperand(i),
+                                                CurBB, PredBB, TD, DT, NewInsts);
+      if (OpVal == 0) return 0;
+      GEPOps.push_back(OpVal);
+    }
+    
+    GetElementPtrInst *Result = 
+      GetElementPtrInst::Create(GEPOps[0], GEPOps.begin()+1, GEPOps.end(),
+                                InVal->getName()+".phi.trans.insert",
+                                PredBB->getTerminator());
+    Result->setIsInBounds(GEP->isInBounds());
+    NewInsts.push_back(Result);
+    return Result;
+  }
+  
+#if 0
+  // FIXME: This code works, but it is unclear that we actually want to insert
+  // a big chain of computation in order to make a value available in a block.
+  // This needs to be evaluated carefully to consider its cost trade offs.
+  
+  // Handle add with a constant RHS.
+  if (Inst->getOpcode() == Instruction::Add &&
+      isa<ConstantInt>(Inst->getOperand(1))) {
+    // PHI translate the LHS.
+    Value *OpVal = InsertPHITranslatedPointer(Inst->getOperand(0),
+                                              CurBB, PredBB, TD, DT, NewInsts);
+    if (OpVal == 0) return 0;
+    
+    BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1),
+                                           InVal->getName()+".phi.trans.insert",
+                                                    PredBB->getTerminator());
+    Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
+    Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
+    NewInsts.push_back(Res);
+    return Res;
+  }
+#endif
+  
+  return 0;
+}
 
 /// getNonLocalPointerDepFromBB - Perform a dependency query based on
 /// pointer/pointeesize starting at the end of StartBB.  Add any clobber/def
@@ -831,66 +1118,107 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize,
       NumSortedEntries = Cache->size();
     }
     
-    // If this is directly a PHI node, just use the incoming values for each
-    // pred as the phi translated version.
-    if (PHINode *PtrPHI = dyn_cast<PHINode>(PtrInst)) {
-      Cache = 0;
-      
-      for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
-        BasicBlock *Pred = *PI;
-        Value *PredPtr = PtrPHI->getIncomingValueForBlock(Pred);
-        
-        // Check to see if we have already visited this pred block with another
-        // pointer.  If so, we can't do this lookup.  This failure can occur
-        // with PHI translation when a critical edge exists and the PHI node in
-        // the successor translates to a pointer value different than the
-        // pointer the block was first analyzed with.
-        std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
-          InsertRes = Visited.insert(std::make_pair(Pred, PredPtr));
+    // If this is a computation derived from a PHI node, use the suitably
+    // translated incoming values for each pred as the phi translated version.
+    if (!isPHITranslatable(PtrInst))
+      goto PredTranslationFailure;
 
-        if (!InsertRes.second) {
-          // If the predecessor was visited with PredPtr, then we already did
-          // the analysis and can ignore it.
-          if (InsertRes.first->second == PredPtr)
-            continue;
-          
-          // Otherwise, the block was previously analyzed with a different
-          // pointer.  We can't represent the result of this case, so we just
-          // treat this as a phi translation failure.
-          goto PredTranslationFailure;
-        }
+    Cache = 0;
+      
+    for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
+      BasicBlock *Pred = *PI;
+      // Get the PHI translated pointer in this predecessor.  This can fail and
+      // return null if not translatable.
+      Value *PredPtr = GetPHITranslatedValue(PtrInst, BB, Pred, TD);
+      
+      // Check to see if we have already visited this pred block with another
+      // pointer.  If so, we can't do this lookup.  This failure can occur
+      // with PHI translation when a critical edge exists and the PHI node in
+      // the successor translates to a pointer value different than the
+      // pointer the block was first analyzed with.
+      std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
+        InsertRes = Visited.insert(std::make_pair(Pred, PredPtr));
 
-        // FIXME: it is entirely possible that PHI translating will end up with
-        // the same value.  Consider PHI translating something like:
-        // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
-        // to recurse here, pedantically speaking.
+      if (!InsertRes.second) {
+        // If the predecessor was visited with PredPtr, then we already did
+        // the analysis and can ignore it.
+        if (InsertRes.first->second == PredPtr)
+          continue;
         
-        // If we have a problem phi translating, fall through to the code below
-        // to handle the failure condition.
-        if (getNonLocalPointerDepFromBB(PredPtr, PointeeSize, isLoad, Pred,
-                                        Result, Visited))
-          goto PredTranslationFailure;
+        // Otherwise, the block was previously analyzed with a different
+        // pointer.  We can't represent the result of this case, so we just
+        // treat this as a phi translation failure.
+        goto PredTranslationFailure;
       }
       
-      // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
-      CacheInfo = &NonLocalPointerDeps[CacheKey];
-      Cache = &CacheInfo->second;
-      NumSortedEntries = Cache->size();
+      // If PHI translation was unable to find an available pointer in this
+      // predecessor, then we have to assume that the pointer is clobbered in
+      // that predecessor.  We can still do PRE of the load, which would insert
+      // a computation of the pointer in this predecessor.
+      if (PredPtr == 0) {
+        // Add the entry to the Result list.
+        NonLocalDepEntry Entry(Pred,
+                               MemDepResult::getClobber(Pred->getTerminator()));
+        Result.push_back(Entry);
+
+        // Add it to the cache for this CacheKey so that subsequent queries get
+        // this result.
+        Cache = &NonLocalPointerDeps[CacheKey].second;
+        MemoryDependenceAnalysis::NonLocalDepInfo::iterator It =
+          std::upper_bound(Cache->begin(), Cache->end(), Entry);
+        
+        if (It != Cache->begin() && prior(It)->first == Pred)
+          --It;
+
+        if (It == Cache->end() || It->first != Pred) {
+          Cache->insert(It, Entry);
+          // Add it to the reverse map.
+          ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey);
+        } else if (!It->second.isDirty()) {
+          // noop
+        } else if (It->second.getInst() == Pred->getTerminator()) {
+          // Same instruction, clear the dirty marker.
+          It->second = Entry.second;
+        } else if (It->second.getInst() == 0) {
+          // Dirty, with no instruction, just add this.
+          It->second = Entry.second;
+          ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey);
+        } else {
+          // Otherwise, dirty with a different instruction.
+          RemoveFromReverseMap(ReverseNonLocalPtrDeps, It->second.getInst(),
+                               CacheKey);
+          It->second = Entry.second;
+          ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey);
+        }
+        Cache = 0;
+        continue;
+      }
+
+      // FIXME: it is entirely possible that PHI translating will end up with
+      // the same value.  Consider PHI translating something like:
+      // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
+      // to recurse here, pedantically speaking.
       
-      // Since we did phi translation, the "Cache" set won't contain all of the
-      // results for the query.  This is ok (we can still use it to accelerate
-      // specific block queries) but we can't do the fastpath "return all
-      // results from the set"  Clear out the indicator for this.
-      CacheInfo->first = BBSkipFirstBlockPair();
-      SkipFirstBlock = false;
-      continue;
+      // If we have a problem phi translating, fall through to the code below
+      // to handle the failure condition.
+      if (getNonLocalPointerDepFromBB(PredPtr, PointeeSize, isLoad, Pred,
+                                      Result, Visited))
+        goto PredTranslationFailure;
     }
     
-    // TODO: BITCAST, GEP.
+    // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
+    CacheInfo = &NonLocalPointerDeps[CacheKey];
+    Cache = &CacheInfo->second;
+    NumSortedEntries = Cache->size();
     
-    //   cerr << "MEMDEP: Could not PHI translate: " << *Pointer;
-    //   if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst))
-    //     cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0);
+    // Since we did phi translation, the "Cache" set won't contain all of the
+    // results for the query.  This is ok (we can still use it to accelerate
+    // specific block queries) but we can't do the fastpath "return all
+    // results from the set"  Clear out the indicator for this.
+    CacheInfo->first = BBSkipFirstBlockPair();
+    SkipFirstBlock = false;
+    continue;
+
   PredTranslationFailure:
     
     if (Cache == 0) {