This is a substantial rewrite of the AliasSetTracker class which now uses

a union-find based algorithm, is significantly faster, and is more general.
It will also scale to handle call instructions correctly, which is a nice
added bonus.

This includes a new pass -print-alias-sets which can be used to show how
alias sets are formed for a particular analysis.


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

1 files changed, 218 insertions, 111 deletions

diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp
index 1413660d92..db704b654a 100644
--- a/lib/Analysis/AliasSetTracker.cpp
+++ b/lib/Analysis/AliasSetTracker.cpp
@@ -9,70 +9,107 @@
 #include "llvm/iMemory.h"
 #include "llvm/iOther.h"
 #include "llvm/iTerminators.h"
+#include "llvm/Pass.h"
+#include "llvm/Assembly/Writer.h"
+#include "llvm/Support/InstIterator.h"
 
-/// updateAccessTypes - Depending on what type of accesses are in this set,
-/// decide whether the set contains just references, just modifications, or a
-/// mix.
+/// mergeSetIn - Merge the specified alias set into this alias set...
 ///
-void AliasSet::updateAccessType() {
-  if (!Calls.empty() || !Invokes.empty()) {
-    AccessTy = ModRef;
-  } else if (!Loads.empty()) {
-    if (Stores.empty())
-      AccessTy = Refs;
-    else
-      AccessTy = ModRef;
-  } else {
-    AccessTy = Mods;
+void AliasSet::mergeSetIn(AliasSet &AS) {
+  assert(!AS.Forward && "Alias set is already forwarding!");
+  assert(!Forward && "This set is a forwarding set!!");
+
+  // Update the alias and access types of this set...
+  AccessTy |= AS.AccessTy;
+  AliasTy  |= AS.AliasTy;
+
+  if (CallSites.empty()) {            // Merge call sites...
+    if (!AS.CallSites.empty())
+      std::swap(CallSites, AS.CallSites);
+  } else if (!AS.CallSites.empty()) {
+    CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end());
+    AS.CallSites.clear();
   }
+  
+  // FIXME: If AS's refcount is zero, nuke it now...
+  assert(RefCount != 0);
+
+  AS.Forward = this;  // Forward across AS now...
+  RefCount++;         // AS is now pointing to us...
+
+  // Merge the list of constituent pointers...
+  PtrListTail->second.setTail(AS.PtrListHead);
+  PtrListTail = AS.PtrListTail;
+  AS.PtrListHead = AS.PtrListTail = 0;
 }
 
-/// mergeSetIn - Merge the specified alias set into this alias set...
-///
-void AliasSet::mergeSetIn(const AliasSet &AS) {
-  // Merge instruction sets...
-    Loads.insert(  Loads.end(), AS.Loads.begin()  , AS.Loads.end());
-   Stores.insert( Stores.end(), AS.Stores.begin() , AS.Stores.end());
-    Calls.insert(  Calls.end(), AS.Calls.begin()  , AS.Calls.end());
-  Invokes.insert(Invokes.end(), AS.Invokes.begin(), AS.Invokes.end());
+void AliasSetTracker::removeAliasSet(AliasSet *AS) {
+  AliasSets.erase(AS);
+}
 
-  // Update the alias and access types of this set...
-  if (AS.getAliasType() == MayAlias)
-    AliasTy = MayAlias;
-  updateAccessType();
+void AliasSet::removeFromTracker(AliasSetTracker &AST) {
+  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
+  AST.removeAliasSet(this);
+}
+
+void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry){
+  assert(!Entry.second.hasAliasSet() && "Entry already in set!");
+
+  AliasAnalysis &AA = AST.getAliasAnalysis();
+
+  if (isMustAlias())    // Check to see if we have to downgrade to _may_ alias
+    if (Value *V = getSomePointer())
+      if (AA.alias(V, Entry.first) == AliasAnalysis::MayAlias)
+        AliasTy = MayAlias;
+
+  Entry.second.setAliasSet(this);
+
+  // Add it to the end of the list...
+  if (PtrListTail)
+    PtrListTail->second.setTail(&Entry);
+  else
+    PtrListHead = &Entry;
+  PtrListTail = &Entry;
+  RefCount++;               // Entry points to alias set...
 }
 
-/// pointerAliasesSet - Return true if the specified pointer "may" (or must)
+void AliasSet::addCallSite(CallSite CS) {
+  CallSites.push_back(CS);
+  AliasTy = MayAlias;         // FIXME: Too conservative
+}
+
+/// aliasesPointer - Return true if the specified pointer "may" (or must)
 /// alias one of the members in the set.
 ///
-bool AliasSet::pointerAliasesSet(const Value *Ptr, AliasAnalysis &AA) const {
-  if (!Calls.empty() || !Invokes.empty())
-    return true;
-  for (unsigned i = 0, e = Loads.size(); i != e; ++i)
-    if (AA.alias(Ptr, Loads[i]->getOperand(0)))
-      return true;
-  for (unsigned i = 0, e = Stores.size(); i != e; ++i)
-    if (AA.alias(Ptr, Stores[i]->getOperand(1)))
+bool AliasSet::aliasesPointer(const Value *Ptr, AliasAnalysis &AA) const {
+  if (AliasTy == MustAlias) {
+    assert(CallSites.empty() && "Illegal must alias set!");
+
+    // If this is a set of MustAliases, only check to see if the pointer aliases
+    // SOME value in the set...
+    Value *SomePtr = getSomePointer();
+    assert(SomePtr && "Empty must-alias set??");
+    return AA.alias(SomePtr, Ptr);
+  }
+
+  // If this is a may-alias set, we have to check all of the pointers in the set
+  // to be sure it doesn't alias the set...
+  for (iterator I = begin(), E = end(); I != E; ++I)
+    if (AA.alias(Ptr, *I))
       return true;
-  return false;
-}
 
-/// getSomePointer - This method may only be called when the AliasType of the
-/// set is MustAlias.  This is used to return any old pointer (which must alias
-/// all other pointers in the set) so that the caller can decide whether to turn
-/// this set into a may alias set or not.
-///
-Value *AliasSet::getSomePointer() const {
-  assert(getAliasType() == MustAlias &&
-         "Cannot call getSomePointer on a 'MayAlias' set!");
-  assert(Calls.empty() && Invokes.empty() && "Call/invokes mean may alias!");
+  // Check the call sites list and invoke list...
+  if (!CallSites.empty())
+    // FIXME: this is pessimistic!
+    return true;
 
-  if (!Loads.empty())
-    return Loads[0]->getOperand(0);
-  assert(!Stores.empty() && "There are no instructions in this set!");
-  return Stores[0]->getOperand(1);
+  return false;
 }
 
+bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const {
+  // FIXME: Too conservative!
+  return true;
+}
 
 
 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
@@ -81,92 +118,162 @@ Value *AliasSet::getSomePointer() const {
 ///
 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr) {
   AliasSet *FoundSet = 0;
-  for (unsigned i = 0; i != AliasSets.size(); ++i) {
-    if (AliasSets[i].pointerAliasesSet(Ptr, AA)) {
+  for (iterator I = begin(), E = end(); I != E; ++I)
+    if (I->aliasesPointer(Ptr, AA)) {
       if (FoundSet == 0) {  // If this is the first alias set ptr can go into...
-        FoundSet = &AliasSets[i];   // Remember it.
+        FoundSet = I;       // Remember it.
       } else {              // Otherwise, we must merge the sets...
-        FoundSet->mergeSetIn(AliasSets[i]);     // Merge in contents...
-        AliasSets.erase(AliasSets.begin()+i);   // Remove the set...
-        --i;                                    // Don't skip the next set
+        FoundSet->mergeSetIn(*I);     // Merge in contents...
       }
     }
-  }
 
   return FoundSet;
 }
 
+AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
+  AliasSet *FoundSet = 0;
+  for (iterator I = begin(), E = end(); I != E; ++I)
+    if (I->aliasesCallSite(CS, AA)) {
+      if (FoundSet == 0) {  // If this is the first alias set ptr can go into...
+        FoundSet = I;       // Remember it.
+      } else {              // Otherwise, we must merge the sets...
+        FoundSet->mergeSetIn(*I);     // Merge in contents...
+      }
+    }
 
-void AliasSetTracker::add(LoadInst *LI) {
-  Value *Pointer = LI->getOperand(0);
-
-  // Check to see if the loaded pointer aliases any sets...
-  AliasSet *AS = findAliasSetForPointer(Pointer);
-  if (AS) {
-    AS->Loads.push_back(LI);
-    // Check to see if we need to change this into a MayAlias set now...
-    if (AS->getAliasType() == AliasSet::MustAlias)
-      if (AA.alias(AS->getSomePointer(), Pointer) != AliasAnalysis::MustAlias)
-        AS->AliasTy = AliasSet::MayAlias;
-    AS->updateAccessType();
+  return FoundSet;
+}
+
+
+
+
+/// getAliasSetForPointer - Return the alias set that the specified pointer
+/// lives in...
+AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer) {
+  AliasSet::HashNodePair &Entry = getEntryFor(Pointer);
+
+  // Check to see if the pointer is already known...
+  if (Entry.second.hasAliasSet()) {
+    // Return the set!
+    return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this);
+  } else if (AliasSet *AS = findAliasSetForPointer(Pointer)) {
+    // Add it to the alias set it aliases...
+    AS->addPointer(*this, Entry);
+    return *AS;
   } else {
-    // Otherwise create a new alias set to hold the load...
+    // Otherwise create a new alias set to hold the loaded pointer...
     AliasSets.push_back(AliasSet());
-    AliasSets.back().Loads.push_back(LI);
-    AliasSets.back().AccessTy = AliasSet::Refs;
+    AliasSets.back().addPointer(*this, Entry);
+    return AliasSets.back();
   }
 }
 
+void AliasSetTracker::add(LoadInst *LI) {
+  addPointer(LI->getOperand(0), AliasSet::Refs);
+}
+
 void AliasSetTracker::add(StoreInst *SI) {
-  Value *Pointer = SI->getOperand(1);
-
-  // Check to see if the loaded pointer aliases any sets...
-  AliasSet *AS = findAliasSetForPointer(Pointer);
-  if (AS) {
-    AS->Stores.push_back(SI);
-    // Check to see if we need to change this into a MayAlias set now...
-    if (AS->getAliasType() == AliasSet::MustAlias)
-      if (AA.alias(AS->getSomePointer(), Pointer) != AliasAnalysis::MustAlias)
-        AS->AliasTy = AliasSet::MayAlias;
-    AS->updateAccessType();
-  } else {
-    // Otherwise create a new alias set to hold the load...
+  addPointer(SI->getOperand(1), AliasSet::Mods);
+}
+
+void AliasSetTracker::add(CallSite CS) {
+  AliasSet *AS = findAliasSetForCallSite(CS);
+  if (!AS) {
     AliasSets.push_back(AliasSet());
-    AliasSets.back().Stores.push_back(SI);
-    AliasSets.back().AccessTy = AliasSet::Mods;
+    AS = &AliasSets.back();
   }
+  AS->addCallSite(CS); 
 }
 
+void AliasSetTracker::add(Instruction *I) {
+  // Dispatch to one of the other add methods...
+  if (LoadInst *LI = dyn_cast<LoadInst>(I))
+    add(LI);
+  else if (StoreInst *SI = dyn_cast<StoreInst>(I))
+    add(SI);
+  else if (CallInst *CI = dyn_cast<CallInst>(I))
+    add(CI);
+  else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
+    add(II);
+}
 
-void AliasSetTracker::mergeAllSets() {
-  if (AliasSets.size() < 2) return;  // Noop
+//===----------------------------------------------------------------------===//
+//               AliasSet/AliasSetTracker Printing Support
+//===----------------------------------------------------------------------===//
 
-  // Merge all of the sets into set #0
-  for (unsigned i = 1, e = AliasSets.size(); i != e; ++i)
-    AliasSets[0].mergeSetIn(AliasSets[i]);
+void AliasSet::print(std::ostream &OS) const {
+  OS << "  AliasSet[" << (void*)this << "," << RefCount << "] ";
+  OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, ";
+  switch (AccessTy) {
+  case NoModRef: OS << "No access "; break;
+  case Refs    : OS << "Ref       "; break;
+  case Mods    : OS << "Mod       "; break;
+  case ModRef  : OS << "Mod/Ref   "; break;
+  default: assert(0 && "Bad value for AccessTy!");
+  }
+  if (Forward)
+    OS << " forwarding to " << (void*)Forward;
 
-  // Delete extraneous sets...
-  AliasSets.erase(AliasSets.begin()+1, AliasSets.end());
-}
 
-void AliasSetTracker::add(CallInst *CI) {
-  if (!AliasSets.empty()) {
-    mergeAllSets();
-  } else {
-    AliasSets.push_back(AliasSet());
+  if (begin() != end()) {
+    OS << "Pointers: ";
+    for (iterator I = begin(), E = end(); I != E; ++I) {
+      if (I != begin()) OS << ", ";
+      WriteAsOperand(OS, *I);
+    }
   }
-  AliasSets[0].AccessTy = AliasSet::ModRef;
-  AliasSets[0].AliasTy = AliasSet::MayAlias;
-  AliasSets[0].Calls.push_back(CI);
+  if (!CallSites.empty()) {
+    OS << "\n    " << CallSites.size() << " Call Sites: ";
+    for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
+      if (i) OS << ", ";
+      WriteAsOperand(OS, CallSites[i].getCalledValue());
+    }      
+  }
+  OS << "\n";
 }
 
-void AliasSetTracker::add(InvokeInst *II) {
-  if (!AliasSets.empty()) {
-    mergeAllSets();
-  } else {
-    AliasSets.push_back(AliasSet());
-  }
-  AliasSets[0].AccessTy = AliasSet::ModRef;
-  AliasSets[0].AliasTy = AliasSet::MayAlias;
-  AliasSets[0].Invokes.push_back(II);
+void AliasSetTracker::print(std::ostream &OS) const {
+  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
+     << PointerMap.size() << " pointer values.\n";
+  for (const_iterator I = begin(), E = end(); I != E; ++I)
+    I->print(OS);
+  OS << "\n";
+}
+
+void AliasSet::dump() const { print (std::cerr); }
+void AliasSetTracker::dump() const { print(std::cerr); }
+
+
+//===----------------------------------------------------------------------===//
+//                            AliasSetPrinter Pass
+//===----------------------------------------------------------------------===//
+
+namespace {
+  class AliasSetPrinter : public FunctionPass {
+    AliasSetTracker *Tracker;
+  public:
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.setPreservesAll();
+      AU.addRequired<AliasAnalysis>();
+    }
+
+    virtual bool runOnFunction(Function &F) {
+      Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
+
+      for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
+        Tracker->add(*I);
+      return false;
+    }
+
+    /// print - Convert to human readable form
+    virtual void print(std::ostream &OS) const {
+      Tracker->print(OS);
+    }
+
+    virtual void releaseMemory() {
+      delete Tracker;
+    }
+  };
+  RegisterPass<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer",
+                                  PassInfo::Analysis | PassInfo::Optimization);
 }