reimplement AliasSetTracker in terms of DenseMap instead of hash_map,

hopefully no functionality change.


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

3 files changed, 93 insertions, 75 deletions

diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
index 2dcc2be..786c1d1 100644
--- a/include/llvm/Analysis/AliasSetTracker.h
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -19,10 +19,11 @@
 
 #include "llvm/Support/CallSite.h"
 #include "llvm/Support/Streams.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/iterator.h"
-#include "llvm/ADT/hash_map.h"
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
+#include <vector>
 
 namespace llvm {
 
@@ -37,20 +38,21 @@ class AliasSet;
 class AliasSet : public ilist_node<AliasSet> {
   friend class AliasSetTracker;
 
-  class PointerRec;
-  typedef std::pair<Value* const, PointerRec> HashNodePair;
-
   class PointerRec {
-    HashNodePair **PrevInList, *NextInList;
+    Value *Val;  // The pointer this record corresponds to.
+    PointerRec **PrevInList, *NextInList;
     AliasSet *AS;
     unsigned Size;
   public:
-    PointerRec() : PrevInList(0), NextInList(0), AS(0), Size(0) {}
+    PointerRec(Value *V)
+      : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {}
 
-    HashNodePair *getNext() const { return NextInList; }
+    Value *getValue() const { return Val; }
+    
+    PointerRec *getNext() const { return NextInList; }
     bool hasAliasSet() const { return AS != 0; }
 
-    HashNodePair** setPrevInList(HashNodePair **PIL) {
+    PointerRec** setPrevInList(PointerRec **PIL) {
       PrevInList = PIL;
       return &NextInList;
     }
@@ -77,21 +79,22 @@ class AliasSet : public ilist_node<AliasSet> {
       AS = as;
     }
 
-    void removeFromList() {
-      if (NextInList) NextInList->second.PrevInList = PrevInList;
+    void eraseFromList() {
+      if (NextInList) NextInList->PrevInList = PrevInList;
       *PrevInList = NextInList;
       if (AS->PtrListEnd == &NextInList) {
         AS->PtrListEnd = PrevInList;
         assert(*AS->PtrListEnd == 0 && "List not terminated right!");
       }
+      delete this;
     }
   };
 
-  HashNodePair *PtrList, **PtrListEnd;  // Doubly linked list of nodes
-  AliasSet *Forward;             // Forwarding pointer
-  AliasSet *Next, *Prev;         // Doubly linked list of AliasSets
+  PointerRec *PtrList, **PtrListEnd;  // Doubly linked list of nodes.
+  AliasSet *Forward;             // Forwarding pointer.
+  AliasSet *Next, *Prev;         // Doubly linked list of AliasSets.
 
-  std::vector<CallSite> CallSites; // All calls & invokes in this node
+  std::vector<CallSite> CallSites; // All calls & invokes in this alias set.
 
   // RefCount - Number of nodes pointing to this AliasSet plus the number of
   // AliasSets forwarding to it.
@@ -157,10 +160,10 @@ public:
   void dump() const;
 
   /// Define an iterator for alias sets... this is just a forward iterator.
-  class iterator : public forward_iterator<HashNodePair, ptrdiff_t> {
-    HashNodePair *CurNode;
+  class iterator : public forward_iterator<PointerRec, ptrdiff_t> {
+    PointerRec *CurNode;
   public:
-    explicit iterator(HashNodePair *CN = 0) : CurNode(CN) {}
+    explicit iterator(PointerRec *CN = 0) : CurNode(CN) {}
 
     bool operator==(const iterator& x) const {
       return CurNode == x.CurNode;
@@ -178,12 +181,12 @@ public:
     }
     value_type *operator->() const { return &operator*(); }
 
-    Value *getPointer() const { return CurNode->first; }
-    unsigned getSize() const { return CurNode->second.getSize(); }
+    Value *getPointer() const { return CurNode->getValue(); }
+    unsigned getSize() const { return CurNode->getSize(); }
 
     iterator& operator++() {                // Preincrement
       assert(CurNode && "Advancing past AliasSet.end()!");
-      CurNode = CurNode->second.getNext();
+      CurNode = CurNode->getNext();
       return *this;
     }
     iterator operator++(int) { // Postincrement
@@ -202,7 +205,7 @@ private:
   AliasSet(const AliasSet &AS);        // do not implement
   void operator=(const AliasSet &AS);  // do not implement
 
-  HashNodePair *getSomePointer() const {
+  PointerRec *getSomePointer() const {
     return PtrList;
   }
 
@@ -223,7 +226,7 @@ private:
 
   void removeFromTracker(AliasSetTracker &AST);
 
-  void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size,
+  void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size,
                   bool KnownMustAlias = false);
   void addCallSite(CallSite CS, AliasAnalysis &AA);
   void removeCallSite(CallSite CS) {
@@ -253,7 +256,7 @@ class AliasSetTracker {
   ilist<AliasSet> AliasSets;
 
   // Map from pointers to their node
-  hash_map<Value*, AliasSet::PointerRec> PointerMap;
+  DenseMap<Value*, AliasSet::PointerRec*> PointerMap;
 public:
   /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
   /// the specified alias analysis object to disambiguate load and store
@@ -299,10 +302,7 @@ public:
   bool remove(Instruction *I);
   void remove(AliasSet &AS);
   
-  void clear() {
-    PointerMap.clear();
-    AliasSets.clear();
-  }
+  void clear();
 
   /// getAliasSets - Return the alias sets that are active.
   ///
@@ -362,11 +362,13 @@ private:
   friend class AliasSet;
   void removeAliasSet(AliasSet *AS);
 
-  AliasSet::HashNodePair &getEntryFor(Value *V) {
-    // Standard operator[], except that it returns the whole pair, not just
-    // ->second.
-    return *PointerMap.insert(AliasSet::HashNodePair(V,
-                                            AliasSet::PointerRec())).first;
+  // getEntryFor - Just like operator[] on the map, except that it creates an
+  // entry for the pointer if it doesn't already exist.
+  AliasSet::PointerRec &getEntryFor(Value *V) {
+    AliasSet::PointerRec *&Entry = PointerMap[V];
+    if (Entry == 0)
+      Entry = new AliasSet::PointerRec(V);
+    return *Entry;
   }
 
   AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E,
diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp
index 8eeb7f6..a386a49 100644
--- a/lib/Analysis/AliasSetTracker.cpp
+++ b/lib/Analysis/AliasSetTracker.cpp
@@ -39,11 +39,11 @@ void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
     // used to be must-alias sets, we can just check any pointer from each set
     // for aliasing.
     AliasAnalysis &AA = AST.getAliasAnalysis();
-    HashNodePair *L = getSomePointer();
-    HashNodePair *R = AS.getSomePointer();
+    PointerRec *L = getSomePointer();
+    PointerRec *R = AS.getSomePointer();
 
     // If the pointers are not a must-alias pair, this set becomes a may alias.
-    if (AA.alias(L->first, L->second.getSize(), R->first, R->second.getSize())
+    if (AA.alias(L->getValue(), L->getSize(), R->getValue(), R->getSize())
         != AliasAnalysis::MustAlias)
       AliasTy = MayAlias;
   }
@@ -62,7 +62,7 @@ void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
   // Merge the list of constituent pointers...
   if (AS.PtrList) {
     *PtrListEnd = AS.PtrList;
-    AS.PtrList->second.setPrevInList(PtrListEnd);
+    AS.PtrList->setPrevInList(PtrListEnd);
     PtrListEnd = AS.PtrListEnd;
 
     AS.PtrList = 0;
@@ -84,30 +84,30 @@ void AliasSet::removeFromTracker(AliasSetTracker &AST) {
   AST.removeAliasSet(this);
 }
 
-void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry,
+void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
                           unsigned Size, bool KnownMustAlias) {
-  assert(!Entry.second.hasAliasSet() && "Entry already in set!");
+  assert(!Entry.hasAliasSet() && "Entry already in set!");
 
   // Check to see if we have to downgrade to _may_ alias.
   if (isMustAlias() && !KnownMustAlias)
-    if (HashNodePair *P = getSomePointer()) {
+    if (PointerRec *P = getSomePointer()) {
       AliasAnalysis &AA = AST.getAliasAnalysis();
       AliasAnalysis::AliasResult Result =
-        AA.alias(P->first, P->second.getSize(), Entry.first, Size);
+        AA.alias(P->getValue(), P->getSize(), Entry.getValue(), Size);
       if (Result == AliasAnalysis::MayAlias)
         AliasTy = MayAlias;
       else                  // First entry of must alias must have maximum size!
-        P->second.updateSize(Size);
+        P->updateSize(Size);
       assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!");
     }
 
-  Entry.second.setAliasSet(this);
-  Entry.second.updateSize(Size);
+  Entry.setAliasSet(this);
+  Entry.updateSize(Size);
 
   // Add it to the end of the list...
   assert(*PtrListEnd == 0 && "End of list is not null?");
   *PtrListEnd = &Entry;
-  PtrListEnd = Entry.second.setPrevInList(PtrListEnd);
+  PtrListEnd = Entry.setPrevInList(PtrListEnd);
   assert(*PtrListEnd == 0 && "End of list is not null?");
   addRef();               // Entry points to alias set...
 }
@@ -139,9 +139,9 @@ bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size,
 
     // If this is a set of MustAliases, only check to see if the pointer aliases
     // SOME value in the set...
-    HashNodePair *SomePtr = getSomePointer();
+    PointerRec *SomePtr = getSomePointer();
     assert(SomePtr && "Empty must-alias set??");
-    return AA.alias(SomePtr->first, SomePtr->second.getSize(), Ptr, Size);
+    return AA.alias(SomePtr->getValue(), SomePtr->getSize(), Ptr, Size);
   }
 
   // If this is a may-alias set, we have to check all of the pointers in the set
@@ -184,6 +184,18 @@ bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const {
   return false;
 }
 
+void AliasSetTracker::clear() {
+  // Delete all the PointerRec entries.
+  for (DenseMap<Value*, AliasSet::PointerRec*>::iterator I = PointerMap.begin(),
+       E = PointerMap.end(); I != E; ++I)
+    I->second->eraseFromList();
+  
+  PointerMap.clear();
+  
+  // The alias sets should all be clear now.
+  AliasSets.clear();
+}
+
 
 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
 /// instruction referring to the pointer into.  If there are multiple alias sets
@@ -234,16 +246,16 @@ AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
 
 
 /// getAliasSetForPointer - Return the alias set that the specified pointer
-/// lives in...
+/// lives in.
 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size,
                                                  bool *New) {
-  AliasSet::HashNodePair &Entry = getEntryFor(Pointer);
+  AliasSet::PointerRec &Entry = getEntryFor(Pointer);
 
   // Check to see if the pointer is already known...
-  if (Entry.second.hasAliasSet()) {
-    Entry.second.updateSize(Size);
+  if (Entry.hasAliasSet()) {
+    Entry.updateSize(Size);
     // Return the set!
-    return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this);
+    return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
   } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) {
     // Add it to the alias set it aliases...
     AS->addPointer(*this, Entry, Size);
@@ -371,17 +383,18 @@ void AliasSetTracker::remove(AliasSet &AS) {
   // Clear the alias set.
   unsigned NumRefs = 0;
   while (!AS.empty()) {
-    AliasSet::HashNodePair *P = AS.PtrList;
+    AliasSet::PointerRec *P = AS.PtrList;
+
+    Value *ValToRemove = P->getValue();
     
-    // Unlink from the list of values.
-    P->second.removeFromList();
+    // Unlink and delete entry from the list of values.
+    P->eraseFromList();
     
     // Remember how many references need to be dropped.
     ++NumRefs;
 
     // Finally, remove the entry.
-    Value *Remove = P->first;   // Take a copy because it is invalid to pass
-    PointerMap.erase(Remove);   // a reference to the data being erased.
+    PointerMap.erase(ValToRemove);
   }
   
   // Stop using the alias set, removing it.
@@ -472,17 +485,19 @@ void AliasSetTracker::deleteValue(Value *PtrVal) {
         AS->removeCallSite(CS);
 
   // First, look up the PointerRec for this pointer.
-  hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal);
+  DenseMap<Value*, AliasSet::PointerRec*>::iterator I = PointerMap.find(PtrVal);
   if (I == PointerMap.end()) return;  // Noop
 
   // If we found one, remove the pointer from the alias set it is in.
-  AliasSet::HashNodePair &PtrValEnt = *I;
-  AliasSet *AS = PtrValEnt.second.getAliasSet(*this);
+  AliasSet::PointerRec *PtrValEnt = I->second;
+  AliasSet *AS = PtrValEnt->getAliasSet(*this);
 
-  // Unlink from the list of values...
-  PtrValEnt.second.removeFromList();
-  // Stop using the alias set
+  // Unlink and delete from the list of values.
+  PtrValEnt->eraseFromList();
+  
+  // Stop using the alias set.
   AS->dropRef(*this);
+  
   PointerMap.erase(I);
 }
 
@@ -496,16 +511,17 @@ void AliasSetTracker::copyValue(Value *From, Value *To) {
   AA.copyValue(From, To);
 
   // First, look up the PointerRec for this pointer.
-  hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(From);
-  if (I == PointerMap.end() || !I->second.hasAliasSet())
+  DenseMap<Value*, AliasSet::PointerRec*>::iterator I = PointerMap.find(From);
+  if (I == PointerMap.end())
     return;  // Noop
+  assert(I->second->hasAliasSet() && "Dead entry?");
 
-  AliasSet::HashNodePair &Entry = getEntryFor(To);
-  if (Entry.second.hasAliasSet()) return;    // Already in the tracker!
+  AliasSet::PointerRec &Entry = getEntryFor(To);
+  if (Entry.hasAliasSet()) return;    // Already in the tracker!
 
   // Add it to the alias set it aliases...
-  AliasSet *AS = I->second.getAliasSet(*this);
-  AS->addPointer(*this, Entry, I->second.getSize(), true);
+  AliasSet *AS = I->second->getAliasSet(*this);
+  AS->addPointer(*this, Entry, I->second->getSize(), true);
 }
 
 
diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index b2c895f..1021469 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -62,9 +62,9 @@ static cl::opt<bool>
 DisablePromotion("disable-licm-promotion", cl::Hidden,
                  cl::desc("Disable memory promotion in LICM pass"));
 
-// This feature is currently disabled by default because CodeGen is not yet capable
-// of rematerializing these constants in PIC mode, so it can lead to degraded
-// performance. Compile test/CodeGen/X86/remat-constant.ll with
+// This feature is currently disabled by default because CodeGen is not yet
+// capable of rematerializing these constants in PIC mode, so it can lead to
+// degraded performance. Compile test/CodeGen/X86/remat-constant.ll with
 // -relocation-model=pic to see an example of this.
 static cl::opt<bool>
 EnableLICMConstantMotion("enable-licm-constant-variables", cl::Hidden,
@@ -793,12 +793,12 @@ void LICM::FindPromotableValuesInLoop(
     // set, if the pointer is loop invariant, and if we are not eliminating any
     // volatile loads or stores.
     if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
-        AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->first))
+        AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
       continue;
     
     assert(!AS.empty() &&
            "Must alias set should have at least one pointer element in it!");
-    Value *V = AS.begin()->first;
+    Value *V = AS.begin()->getValue();
 
     // Check that all of the pointers in the alias set have the same type.  We
     // cannot (yet) promote a memory location that is loaded and stored in
@@ -806,7 +806,7 @@ void LICM::FindPromotableValuesInLoop(
     {
       bool PointerOk = true;
       for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I)
-        if (V->getType() != I->first->getType()) {
+        if (V->getType() != I->getValue()->getType()) {
           PointerOk = false;
           break;
         }
@@ -859,7 +859,7 @@ void LICM::FindPromotableValuesInLoop(
     CurAST->copyValue(V, AI);
 
     for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I)
-      ValueToAllocaMap.insert(std::make_pair(I->first, AI));
+      ValueToAllocaMap.insert(std::make_pair(I->getValue(), AI));
 
     DOUT << "LICM: Promoting value: " << *V << "\n";
   }