X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoadValueNumbering.cpp;h=f1ade951f34b79e5f9e93dd276a340ef9a12a357;hb=742f9b66822cb03af0cf7b94436e9d0288565591;hp=b33eb4a7f7b5b3aad8538865e7efc93d9bce1b01;hpb=ee379a16ee0c2045122c76ca6c80b794b42c75fd;p=oota-llvm.git

diff --git a/lib/Analysis/LoadValueNumbering.cpp b/lib/Analysis/LoadValueNumbering.cpp
index b33eb4a7f7b..f1ade951f34 100644
--- a/lib/Analysis/LoadValueNumbering.cpp
+++ b/lib/Analysis/LoadValueNumbering.cpp
@@ -1,10 +1,10 @@
 //===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===//
-// 
+//
 //                     The LLVM Compiler Infrastructure
 //
 // This file was developed by the LLVM research group and is distributed under
 // the University of Illinois Open Source License. See LICENSE.TXT for details.
-// 
+//
 //===----------------------------------------------------------------------===//
 //
 // This file implements a value numbering pass that value numbers load and call
@@ -31,6 +31,7 @@
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Support/CFG.h"
+#include "llvm/Support/Compiler.h"
 #include "llvm/Target/TargetData.h"
 #include <set>
 #include <algorithm>
@@ -38,17 +39,19 @@ using namespace llvm;
 
 namespace {
   // FIXME: This should not be a FunctionPass.
-  struct LoadVN : public FunctionPass, public ValueNumbering {
-    
+  struct VISIBILITY_HIDDEN LoadVN : public FunctionPass, public ValueNumbering {
+    static char ID; // Class identification, replacement for typeinfo
+    LoadVN() : FunctionPass((intptr_t)&ID) {}
+
     /// Pass Implementation stuff.  This doesn't do any analysis.
     ///
     bool runOnFunction(Function &) { return false; }
-    
+
     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
     /// and Alias Analysis.
     ///
     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-    
+
     /// getEqualNumberNodes - Return nodes with the same value number as the
     /// specified Value.  This fills in the argument vector with any equal
     /// values.
@@ -63,7 +66,7 @@ namespace {
     virtual void deleteValue(Value *V) {
       getAnalysis<AliasAnalysis>().deleteValue(V);
     }
-    
+
     /// copyValue - This method should be used whenever a preexisting value in
     /// the program is copied or cloned, introducing a new value.  Note that
     /// analysis implementations should tolerate clients that use this method to
@@ -80,11 +83,12 @@ namespace {
                                  std::vector<Value*> &RetVals) const;
   };
 
+  char LoadVN::ID = 0;
   // Register this pass...
-  RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
+  RegisterPass<LoadVN> X("load-vn", "Load Value Numbering");
 
   // Declare that we implement the ValueNumbering interface
-  RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
+  RegisterAnalysisGroup<ValueNumbering> Y(X);
 }
 
 FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
@@ -95,10 +99,10 @@ FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
 ///
 void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<AliasAnalysis>();
+  AU.addRequiredTransitive<AliasAnalysis>();
   AU.addRequired<ValueNumbering>();
-  AU.addRequired<DominatorSet>();
-  AU.addRequired<TargetData>();
+  AU.addRequiredTransitive<DominatorTree>();
+  AU.addRequiredTransitive<TargetData>();
 }
 
 static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
@@ -109,7 +113,7 @@ static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
   // stop searching, returning success.
   if (CurBlock == Dom || !Visited.insert(CurBlock).second)
     return true;
-  
+
   // Check whether this block is known transparent or not.
   std::map<BasicBlock*, bool>::iterator TBI =
     TransparentBlocks.lower_bound(CurBlock);
@@ -125,7 +129,7 @@ static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
   } else if (!TBI->second)
     // This block is known non-transparent, so that path can't be either.
     return false;
-  
+
   // The current block is known to be transparent.  The entire path is
   // transparent if all of the predecessors paths to the parent is also
   // transparent to the memory location.
@@ -180,7 +184,7 @@ void LoadVN::getCallEqualNumberNodes(CallInst *CI,
         if (AllOperandsEqual)
           IdenticalCalls.push_back(C);
       }
-  
+
   if (IdenticalCalls.empty()) return;
 
   // Eliminate duplicates, which could occur if we chose a value that is passed
@@ -197,22 +201,22 @@ void LoadVN::getCallEqualNumberNodes(CallInst *CI,
   // ANY memory.
   //
   if (MRB == AliasAnalysis::OnlyReadsMemory) {
-    DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
+    DominatorTree &DT = getAnalysis<DominatorTree>();
     BasicBlock *CIBB = CI->getParent();
     for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
       CallInst *C = IdenticalCalls[i];
       bool CantEqual = false;
 
-      if (DomSetInfo.dominates(CIBB, C->getParent())) {
+      if (DT.dominates(CIBB, C->getParent())) {
         // FIXME: we currently only handle the case where both calls are in the
         // same basic block.
         if (CIBB != C->getParent()) {
           CantEqual = true;
         } else {
           Instruction *First = CI, *Second = C;
-          if (!DomSetInfo.dominates(CI, C))
+          if (!DT.dominates(CI, C))
             std::swap(First, Second);
-          
+
           // Scan the instructions between the calls, checking for stores or
           // calls to dangerous functions.
           BasicBlock::iterator I = First;
@@ -235,7 +239,7 @@ void LoadVN::getCallEqualNumberNodes(CallInst *CI,
           }
         }
 
-      } else if (DomSetInfo.dominates(C->getParent(), CIBB)) {
+      } else if (DT.dominates(C->getParent(), CIBB)) {
         // FIXME: We could implement this, but we don't for now.
         CantEqual = true;
       } else {
@@ -283,7 +287,7 @@ void LoadVN::getEqualNumberNodes(Value *V,
   LoadInst *LI = cast<LoadInst>(V);
   if (LI->isVolatile())
     return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
-  
+
   Value *LoadPtr = LI->getOperand(0);
   BasicBlock *LoadBB = LI->getParent();
   Function *F = LoadBB->getParent();
@@ -316,7 +320,7 @@ void LoadVN::getEqualNumberNodes(Value *V,
       if (LI->getOperand(0) == LoadPtr && !LI->isVolatile())
         RetVals.push_back(I);
     }
-    
+
     if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
       // If the invalidating instruction is a store, and its in our candidate
       // set, then we can do store-load forwarding: the load has the same value
@@ -335,15 +339,18 @@ void LoadVN::getEqualNumberNodes(Value *V,
   // we see any candidate loads, then we know they have the same value # as LI.
   //
   bool LoadInvalidatedInBBAfter = false;
-  for (BasicBlock::iterator I = LI->getNext(); I != LoadBB->end(); ++I) {
-    // If this instruction is a load, then this instruction returns the same
-    // value as LI.
-    if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
-      RetVals.push_back(I);
+  {
+    BasicBlock::iterator I = LI;
+    for (++I; I != LoadBB->end(); ++I) {
+      // If this instruction is a load, then this instruction returns the same
+      // value as LI.
+      if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
+        RetVals.push_back(I);
 
-    if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
-      LoadInvalidatedInBBAfter = true;
-      break;
+      if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
+        LoadInvalidatedInBBAfter = true;
+        break;
+      }
     }
   }
 
@@ -351,32 +358,29 @@ void LoadVN::getEqualNumberNodes(Value *V,
   // no need to do any global analysis at all.
   if (LoadInvalidatedInBBBefore && LoadInvalidatedInBBAfter)
     return;
-  
-  // Now that we know the set of equivalent source pointers for the load
-  // instruction, look to see if there are any load or store candidates that are
-  // identical.
+
+  // Now that we know the value is not neccesarily killed on entry or exit to
+  // the BB, find out how many load and store instructions (to this location)
+  // live in each BB in the function.
   //
-  std::map<BasicBlock*, std::vector<LoadInst*> >  CandidateLoads;
-  std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
-    
+  std::map<BasicBlock*, unsigned>  CandidateLoads;
+  std::set<BasicBlock*> CandidateStores;
+
   for (Value::use_iterator UI = LoadPtr->use_begin(), UE = LoadPtr->use_end();
        UI != UE; ++UI)
     if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
       if (Cand->getParent()->getParent() == F &&   // In the same function?
           // Not in LI's block?
           Cand->getParent() != LoadBB && !Cand->isVolatile())
-        CandidateLoads[Cand->getParent()].push_back(Cand);     // Got one...
+        ++CandidateLoads[Cand->getParent()];       // Got one.
     } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
       if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
-          Cand->getParent() != LoadBB &&
           Cand->getOperand(1) == LoadPtr) // It's a store THROUGH the ptr.
-        CandidateStores[Cand->getParent()].push_back(Cand);
+        CandidateStores.insert(Cand->getParent());
     }
-  
-  // Get dominators.
-  DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
 
-  std::set<Instruction*> Instrs;
+  // Get dominators.
+  DominatorTree &DT = getAnalysis<DominatorTree>();
 
   // TransparentBlocks - For each basic block the load/store is alive across,
   // figure out if the pointer is invalidated or not.  If it is invalidated, the
@@ -388,19 +392,19 @@ void LoadVN::getEqualNumberNodes(Value *V,
   // is live across the CFG from the source to destination blocks, and if the
   // value is not invalidated in either the source or destination blocks, add it
   // to the equivalence sets.
-  for (std::map<BasicBlock*, std::vector<LoadInst*> >::iterator
+  for (std::map<BasicBlock*, unsigned>::iterator
          I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
     bool CantEqual = false;
 
     // Right now we only can handle cases where one load dominates the other.
     // FIXME: generalize this!
     BasicBlock *BB1 = I->first, *BB2 = LoadBB;
-    if (DomSetInfo.dominates(BB1, BB2)) {
+    if (DT.dominates(BB1, BB2)) {
       // The other load dominates LI.  If the loaded value is killed entering
       // the LoadBB block, we know the load is not live.
       if (LoadInvalidatedInBBBefore)
         CantEqual = true;
-    } else if (DomSetInfo.dominates(BB2, BB1)) {
+    } else if (DT.dominates(BB2, BB1)) {
       std::swap(BB1, BB2);          // Canonicalize
       // LI dominates the other load.  If the loaded value is killed exiting
       // the LoadBB block, we know the load is not live.
@@ -430,18 +434,19 @@ void LoadVN::getEqualNumberNodes(Value *V,
     // For any loads that are not invalidated, add them to the equivalence
     // set!
     if (!CantEqual) {
-      Instrs.insert(I->second.begin(), I->second.end());
+      unsigned NumLoads = I->second;
       if (BB1 == LoadBB) {
         // If LI dominates the block in question, check to see if any of the
         // loads in this block are invalidated before they are reached.
         for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) {
-          if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
-            // The load is in the set!
-            RetVals.push_back(BBI);
-            Instrs.erase(BBI);
-            if (Instrs.empty()) break;
+          if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
+            if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) {
+              // The load is in the set!
+              RetVals.push_back(BBI);
+              if (--NumLoads == 0) break;  // Found last load to check.
+            }
           } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
-                             & AliasAnalysis::Mod) {
+                                & AliasAnalysis::Mod) {
             // If there is a modifying instruction, nothing below it will value
             // # the same.
             break;
@@ -453,11 +458,12 @@ void LoadVN::getEqualNumberNodes(Value *V,
         BasicBlock::iterator BBI = I->first->end();
         while (1) {
           --BBI;
-          if (isa<LoadInst>(BBI) && Instrs.count(BBI)) {
-            // The load is in the set!
-            RetVals.push_back(BBI);
-            Instrs.erase(BBI);
-            if (Instrs.empty()) break;
+          if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
+            if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) {
+              // The load is the same as this load!
+              RetVals.push_back(BBI);
+              if (--NumLoads == 0) break;  // Found all of the laods.
+            }
           } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize)
                              & AliasAnalysis::Mod) {
             // If there is a modifying instruction, nothing above it will value
@@ -466,8 +472,6 @@ void LoadVN::getEqualNumberNodes(Value *V,
           }
         }
       }
-
-      Instrs.clear();
     }
   }
 
@@ -477,16 +481,21 @@ void LoadVN::getEqualNumberNodes(Value *V,
   if (LoadInvalidatedInBBBefore)
     return;
 
-  for (std::map<BasicBlock*, std::vector<StoreInst*> >::iterator
-         I = CandidateStores.begin(), E = CandidateStores.end(); I != E; ++I)
-    if (DomSetInfo.dominates(I->first, LoadBB)) {
+  // Stores in the load-bb are handled above.
+  CandidateStores.erase(LoadBB);
+
+  for (std::set<BasicBlock*>::iterator I = CandidateStores.begin(),
+         E = CandidateStores.end(); I != E; ++I)
+    if (DT.dominates(*I, LoadBB)) {
+      BasicBlock *StoreBB = *I;
+
       // Check to see if the path from the store to the load is transparent
       // w.r.t. the memory location.
       bool CantEqual = false;
       std::set<BasicBlock*> Visited;
       for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
            PI != E; ++PI)
-        if (!isPathTransparentTo(*PI, I->first, LoadPtr, LoadSize, AA,
+        if (!isPathTransparentTo(*PI, StoreBB, LoadPtr, LoadSize, AA,
                                  Visited, TransparentBlocks)) {
           // None of these stores can VN the same.
           CantEqual = true;
@@ -499,9 +508,9 @@ void LoadVN::getEqualNumberNodes(Value *V,
         // of the load block to the load itself.  Now we just scan the store
         // block.
 
-        BasicBlock::iterator BBI = I->first->end();
+        BasicBlock::iterator BBI = StoreBB->end();
         while (1) {
-          assert(BBI != I->first->begin() &&
+          assert(BBI != StoreBB->begin() &&
                  "There is a store in this block of the pointer, but the store"
                  " doesn't mod the address being stored to??  Must be a bug in"
                  " the alias analysis implementation!");
@@ -510,8 +519,7 @@ void LoadVN::getEqualNumberNodes(Value *V,
             // If the invalidating instruction is one of the candidates,
             // then it provides the value the load loads.
             if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
-              if (std::find(I->second.begin(), I->second.end(), SI) !=
-                  I->second.end())
+              if (SI->getOperand(1) == LoadPtr)
                 RetVals.push_back(SI->getOperand(0));
             break;
           }