The phi translated pointer can be computed when returning a partially cached result

instead of stored.  This reduces memdep memory usage, and also eliminates a bunch of
weakvh's.  This speeds up gvn on gcc.c-torture/20001226-1.c from 23.9s to 8.45s (2.8x)
on a different machine than earlier.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@91885 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index c04631b2a1c646630cc8b91aceb68f8cbef33152..f83cc4f710e7f0befb1bd32c98c5642fe97ad110 100644 (file)
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -132,21 +132,17 @@ namespace llvm {
     }
   };
 
-  /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache, and an
-  /// entry in the results set for a non-local query.  For each BasicBlock (the
-  /// BB entry) it keeps a MemDepResult and the (potentially phi translated)
-  /// address that was live in the block.
-  class NonLocalDepEntry {
+  /// NonLocalDepResult - This is a result from a NonLocal dependence query.
+  /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the
+  /// (potentially phi translated) address that was live in the block.
+  class NonLocalDepResult {
     BasicBlock *BB;
     MemDepResult Result;
-    WeakVH Address;
+    Value *Address;
   public:
-    NonLocalDepEntry(BasicBlock *bb, MemDepResult result, Value *address)
+    NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
       : BB(bb), Result(result), Address(address) {}
-
-    // This is used for searches.
-    NonLocalDepEntry(BasicBlock *bb) : BB(bb) {}
-
+    
     // BB is the sort key, it can't be changed.
     BasicBlock *getBB() const { return BB; }
     
@@ -154,7 +150,7 @@ namespace llvm {
       Result = R;
       Address = Addr;
     }
-
+    
     const MemDepResult &getResult() const { return Result; }
     
     /// getAddress - Return the address of this pointer in this block.  This can
@@ -165,7 +161,27 @@ namespace llvm {
     ///
     /// The address is always null for a non-local 'call' dependence.
     Value *getAddress() const { return Address; }
+  };
+  
+  /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache.  For
+  /// each BasicBlock (the BB entry) it keeps a MemDepResult.
+  class NonLocalDepEntry {
+    BasicBlock *BB;
+    MemDepResult Result;
+  public:
+    NonLocalDepEntry(BasicBlock *bb, MemDepResult result)
+      : BB(bb), Result(result) {}
+
+    // This is used for searches.
+    NonLocalDepEntry(BasicBlock *bb) : BB(bb) {}
 
+    // BB is the sort key, it can't be changed.
+    BasicBlock *getBB() const { return BB; }
+    
+    void setResult(const MemDepResult &R) { Result = R; }
+
+    const MemDepResult &getResult() const { return Result; }
+    
     bool operator<(const NonLocalDepEntry &RHS) const {
       return BB < RHS.BB;
     }
@@ -283,7 +299,7 @@ namespace llvm {
     /// This method assumes the pointer has a "NonLocal" dependency within BB.
     void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
                                       BasicBlock *BB,
-                                     SmallVectorImpl<NonLocalDepEntry> &Result);
+                                    SmallVectorImpl<NonLocalDepResult> &Result);
     
     /// removeInstruction - Remove an instruction from the dependence analysis,
     /// updating the dependence of instructions that previously depended on it.
@@ -307,7 +323,7 @@ namespace llvm {
                                            BasicBlock *BB);
     bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t Size,
                                      bool isLoad, BasicBlock *BB,
-                                     SmallVectorImpl<NonLocalDepEntry> &Result,
+                                     SmallVectorImpl<NonLocalDepResult> &Result,
                                      DenseMap<BasicBlock*, Value*> &Visited,
                                      bool SkipFirstBlock = false);
     MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index d7b0b64ea979355f3fbe8180323d27b580600675..2d74709df292bf0baf7bd89bff2ad318032aaa5b 100644 (file)
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -547,9 +547,9 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
     // If we had a dirty entry for the block, update it.  Otherwise, just add
     // a new entry.
     if (ExistingResult)
-      ExistingResult->setResult(Dep, 0);
+      ExistingResult->setResult(Dep);
     else
-      Cache.push_back(NonLocalDepEntry(DirtyBB, Dep, 0));
+      Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
     
     // If the block has a dependency (i.e. it isn't completely transparent to
     // the value), remember the association!
@@ -579,7 +579,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
 ///
 void MemoryDependenceAnalysis::
 getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
-                             SmallVectorImpl<NonLocalDepEntry> &Result) {
+                             SmallVectorImpl<NonLocalDepResult> &Result) {
   assert(isa<PointerType>(Pointer->getType()) &&
          "Can't get pointer deps of a non-pointer!");
   Result.clear();
@@ -600,9 +600,9 @@ getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
                                    Result, Visited, true))
     return;
   Result.clear();
-  Result.push_back(NonLocalDepEntry(FromBB,
-                                    MemDepResult::getClobber(FromBB->begin()),
-                                    Pointer));
+  Result.push_back(NonLocalDepResult(FromBB,
+                                     MemDepResult::getClobber(FromBB->begin()),
+                                     Pointer));
 }
 
 /// GetNonLocalInfoForBlock - Compute the memdep value for BB with
@@ -657,9 +657,9 @@ GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
   // If we had a dirty entry for the block, update it.  Otherwise, just add
   // a new entry.
   if (ExistingResult)
-    ExistingResult->setResult(Dep, Pointer);
+    ExistingResult->setResult(Dep);
   else
-    Cache->push_back(NonLocalDepEntry(BB, Dep, Pointer));
+    Cache->push_back(NonLocalDepEntry(BB, Dep));
   
   // If the block has a dependency (i.e. it isn't completely transparent to
   // the value), remember the reverse association because we just added it
@@ -727,7 +727,7 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
 bool MemoryDependenceAnalysis::
 getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t PointeeSize,
                             bool isLoad, BasicBlock *StartBB,
-                            SmallVectorImpl<NonLocalDepEntry> &Result,
+                            SmallVectorImpl<NonLocalDepResult> &Result,
                             DenseMap<BasicBlock*, Value*> &Visited,
                             bool SkipFirstBlock) {
   
@@ -760,11 +760,12 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t PointeeSize,
       }
     }
     
+    Value *Addr = Pointer.getAddr();
     for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
          I != E; ++I) {
-      Visited.insert(std::make_pair(I->getBB(), Pointer.getAddr()));
+      Visited.insert(std::make_pair(I->getBB(), Addr));
       if (!I->getResult().isNonLocal())
-        Result.push_back(*I);
+        Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
     }
     ++NumCacheCompleteNonLocalPtr;
     return false;
@@ -808,7 +809,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t PointeeSize,
       
       // If we got a Def or Clobber, add this to the list of results.
       if (!Dep.isNonLocal()) {
-        Result.push_back(NonLocalDepEntry(BB, Dep, Pointer.getAddr()));
+        Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
         continue;
       }
     }
@@ -890,9 +891,9 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t PointeeSize,
       // a computation of the pointer in this predecessor.
       if (PredPtrVal == 0) {
         // Add the entry to the Result list.
-        NonLocalDepEntry Entry(Pred,
-                               MemDepResult::getClobber(Pred->getTerminator()),
-                               PredPtrVal);
+        NonLocalDepResult Entry(Pred,
+                                MemDepResult::getClobber(Pred->getTerminator()),
+                                PredPtrVal);
         Result.push_back(Entry);
 
         // Since we had a phi translation failure, the cache for CacheKey won't
@@ -960,9 +961,10 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t PointeeSize,
       
       assert(I->getResult().isNonLocal() &&
              "Should only be here with transparent block");
-      I->setResult(MemDepResult::getClobber(BB->begin()), Pointer.getAddr());
+      I->setResult(MemDepResult::getClobber(BB->begin()));
       ReverseNonLocalPtrDeps[BB->begin()].insert(CacheKey);
-      Result.push_back(*I);
+      Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
+                                         Pointer.getAddr()));
       break;
     }
   }
@@ -1116,7 +1118,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
         if (DI->getResult().getInst() != RemInst) continue;
         
         // Convert to a dirty entry for the subsequent instruction.
-        DI->setResult(NewDirtyVal, DI->getAddress());
+        DI->setResult(NewDirtyVal);
         
         if (Instruction *NextI = NewDirtyVal.getInst())
           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
@@ -1158,7 +1160,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
         if (DI->getResult().getInst() != RemInst) continue;
         
         // Convert to a dirty entry for the subsequent instruction.
-        DI->setResult(NewDirtyVal, DI->getAddress());
+        DI->setResult(NewDirtyVal);
         
         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index ec4d7cb579f01600903367d45d3f783d191f271a..249194d036c040ecd056969581958cd2f853500d 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1358,7 +1358,7 @@ static bool isLifetimeStart(Instruction *Inst) {
 bool GVN::processNonLocalLoad(LoadInst *LI,
                               SmallVectorImpl<Instruction*> &toErase) {
   // Find the non-local dependencies of the load.
-  SmallVector<NonLocalDepEntry, 64> Deps;
+  SmallVector<NonLocalDepResult, 64> Deps;
   MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(),
                                    Deps);
   //DEBUG(errs() << "INVESTIGATING NONLOCAL LOAD: "