[AliasSetTracker] Degrade AliasSetTracker results when may-alias sets get too large.

[mkuper]

Summary

The cause of PR28832 is the quadratic behavior of repeated inserts into AliasSetTracker - inserting a pointer into AST is linear, since it requires walking over all "may" alias sets, and running an alias check vs. each pointer in such a set.
This patch tracks (more or less) the total number of pointers in all "may" sets, and when that number exceeds a threshold, declares the tracker "saturated" - and lumps all pointers into a single "may" set.

For the example in PR28832, without this patch, I have:

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
43.4251 ( 47.4%)   0.0440 ( 33.2%)  43.4691 ( 47.4%)  43.4471 ( 47.4%)  Loop Invariant Code Motion
19.6565 ( 21.5%)   0.0040 (  3.0%)  19.6605 ( 21.5%)  19.6512 ( 21.5%)  Loop Invariant Code Motion
17.5580 ( 19.2%)   0.0040 (  3.0%)  17.5620 ( 19.2%)  17.5534 ( 19.2%)  Loop Invariant Code Motion
 3.0498 (  3.3%)   0.0080 (  6.0%)   3.0578 (  3.3%)   3.0563 (  3.3%)  Value Propagation

And with this patch, with a threshold of 250:

---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
5.6446 ( 29.1%)   0.0160 (  5.6%)   5.6606 ( 28.8%)   5.6570 ( 28.8%)  Value Propagation
2.2423 ( 11.6%)   0.0040 (  1.4%)   2.2463 ( 11.4%)   2.2448 ( 11.4%)  Loop Invariant Code Motion
1.6510 (  8.5%)   0.0039 (  1.4%)   1.6549 (  8.4%)   1.6526 (  8.4%)  Loop Invariant Code Motion
1.5398 (  8.0%)   0.0040 (  1.4%)   1.5438 (  7.9%)   1.5429 (  7.9%)  Loop Invariant Code Motion

A threshold of 1000 produces a significant slowdown:

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
10.0644 ( 25.7%)   0.0080 (  2.4%)  10.0724 ( 25.5%)  10.0689 ( 25.5%)  Loop Invariant Code Motion
 7.5912 ( 19.4%)   0.0159 (  4.8%)   7.6071 ( 19.3%)   7.6063 ( 19.3%)  Loop Invariant Code Motion
 7.4471 ( 19.0%)   0.0120 (  3.6%)   7.4591 ( 18.9%)   7.4571 ( 18.9%)  Loop Invariant Code Motion
 5.5252 ( 14.1%)   0.0200 (  6.0%)   5.5452 ( 14.1%)   5.5454 ( 14.1%)  Value Propagation

This isn't in a committable state - it needs some cleanup, more testing, and some substantive fixes (per the TODOs).
So no point in reviewing it in detail yet, but I'd like to get a direction check.

Danny, w.r.t to our earlier discussion - I'm not a fan of the idea of having a saturated AST be unsafe to query, so this is required anyway. We can add isSaturated() checks to LICM to speed it up further, as a separate patch.

[hfinkel]

There might not be anything we can do in general that is better than this, but could we degrade to using summaries of some kind instead of N^2 queries. For example, imagine that, in the degraded mode, we represented each set using the result of GetUnderlyingObject and the merged AA metadata. Then we queried using <Ptr, Size, AAMD> vs <UO, UnknownSize, MergedAAMD>, but only once per set, not once per pointer in each set? I'm trying to think of a way to keep getting the easy cases, such as noalias function parameters, even if we degrade on the hard things.

[mkuper]

A more committable version of the patch.
(With full degradation)

[davidxl]

include/llvm/Analysis/AliasSetTracker.h

130 ↗

(On Diff #67933)

Singifies --> Signifies

132–133 ↗

(On Diff #67933)

How about it be called 'AliasAny' ?

418 ↗

(On Diff #67933)

nit: AliasAnyAS may sound better

436 ↗

(On Diff #67933)

Add brief documentation.

lib/Analysis/AliasSetTracker.cpp

29 ↗

(On Diff #67933)

add option description.

82 ↗

(On Diff #67933)

AS.SetSize --> AS.size() to be consistent

294 ↗

(On Diff #67933)

can this logic of checking SaturatedAS be folded into 'mergeAliasSetsForPointer such that there is no need to make any change in this method.

554 ↗

(On Diff #67933)

Use SaturatedAS->MergeSetIn(Cur ...) ?

590 ↗

(On Diff #67933)

The AST is now ..

[mkuper]

Thanks, David!

include/llvm/Analysis/AliasSetTracker.h

132–133 ↗

(On Diff #67933)

Sounds good.

418 ↗

(On Diff #67933)

Sure, wasn't happy with the "saturated" name to begin with.
Do you have any name suggestions for the option, too? (after this change, that's the only place "saturation" will appear in, which may be a bit confusing).

lib/Analysis/AliasSetTracker.cpp

29 ↗

(On Diff #67933)

Ugh, right, thanks!

294 ↗

(On Diff #67933)

It can, but since this is a major behavior difference between a saturated and a non-saturated AST, I think it would be clearer to leave it here.

mergeAliasSetsForPointer used to be called findAliasSetsForPointer. I changed the name in r266381 - the idea was to more clearly separate between the "merging" behavior, and the "get/find the right set" behavior. See discussion in https://reviews.llvm.org/D18939?id=53163#inline-159392

Do you see a specific reason for this to live in merge()?

554 ↗

(On Diff #67933)

Right, was going to change this between the two versions, and it slipped my mind. I think I can't use MergeSetIn() as is, but I can factor out the common logic.

[mkuper]

Updated per David's comments, except for the getAliasSetForPointer() change.

(Re mergeAllAliasSets - I was wrong, it can use mergeSetIn() as is, it does the right thing.)

[davidxl]

lib/Analysis/AliasSetTracker.cpp

297 ↗

(On Diff #68066)

Ok. Please add a little more comments here: something like 'AST is saturated at this point, .."

301 ↗

(On Diff #68066)

Add assert that aliasSet of Entry is indeed AliasAnyAS.

532 ↗

(On Diff #68066)

assert AliasAnyAS is null and may alias set size has reached threshold.

[mkuper]

lib/Analysis/AliasSetTracker.cpp

297 ↗

(On Diff #68066)

Sure.

301 ↗

(On Diff #68066)

Good idea, thanks!

532 ↗

(On Diff #68066)

We're already checking the exact same pre-condition before the call (line 570), but I don't mind an assert.

[davidxl]

lgtm.

Please also check with Danny and Hal.

[reames]

I am not actively objecting to this patch, but I really don't like the overall direction here. Having a threshold where our ability to optimize falls off a cliff just seems really undesirable. As Hal pointed out, there are likely options for summarizing alias sets to allow quicker AA queries. How much have we explored that design space?

[hfinkel]

In D23432#521624, @reames wrote:

I am not actively objecting to this patch, but I really don't like the overall direction here. Having a threshold where our ability to optimize falls off a cliff just seems really undesirable. As Hal pointed out, there are likely options for summarizing alias sets to allow quicker AA queries. How much have we explored that design space?

My understanding from the discussion is that all uses of the ASTracker are going to be replaced with MemorySSA-based algorithms; that is why I was okay with this (for now). If we still need an AST concept, then we'll want to do something more sophisticated.

llvm/trunk/include/llvm/Analysis/AliasSetTracker.h

void eraseFromList() {
       if (AS->PtrListEnd == &NextInList) {
         AS->PtrListEnd = PrevInList;
         assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
       }
       delete this;
     }
   };
 
-  PointerRec *PtrList, **PtrListEnd;  // Doubly linked list of nodes.
-  AliasSet *Forward;             // Forwarding pointer.
+  // Doubly linked list of nodes.
+  PointerRec *PtrList, **PtrListEnd;
+  // Forwarding pointer.
+  AliasSet *Forward;
 
   /// All instructions without a specific address in this alias set.
   std::vector<AssertingVH<Instruction> > UnknownInsts;
 
   /// Number of nodes pointing to this AliasSet plus the number of AliasSets
   /// forwarding to it.
-  unsigned RefCount : 28;
+  unsigned RefCount : 27;
+
+  // Signifies that this set should be considered to alias any pointer.
+  // Use when the tracker holding this set is saturated.
+  unsigned AliasAny : 1;
 
   /// The kinds of access this alias set models.
   ///
   /// We keep track of whether this alias set merely refers to the locations of
   /// memory (and not any particular access), whether it modifies or references
   /// the memory, or whether it does both. The lattice goes from "NoAccess" to
   /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
   enum AccessLattice {
class AliasSet : public ilist_node<AliasSet> {
   enum AliasLattice {
     SetMustAlias = 0, SetMayAlias = 1
   };
   unsigned Alias : 1;
 
   /// True if this alias set contains volatile loads or stores.
   unsigned Volatile : 1;
 
+  unsigned SetSize;
+
   void addRef() { ++RefCount; }
+
   void dropRef(AliasSetTracker &AST) {
     assert(RefCount >= 1 && "Invalid reference count detected!");
     if (--RefCount == 0)
       removeFromTracker(AST);
   }
 
   Instruction *getUnknownInst(unsigned i) const {
     assert(i < UnknownInsts.size());
public:
 
   // Alias Set iteration - Allow access to all of the pointers which are part of
   // this alias set.
   class iterator;
   iterator begin() const { return iterator(PtrList); }
   iterator end()   const { return iterator(); }
   bool empty() const { return PtrList == nullptr; }
 
+  // Unfortunately, ilist::size() is linear, so we have to add code to keep
+  // track of the list's exact size.
+  unsigned size() { return SetSize; }
+
   void print(raw_ostream &OS) const;
   void dump() const;
 
   /// Define an iterator for alias sets... this is just a forward iterator.
   class iterator : public std::iterator<std::forward_iterator_tag,
                                         PointerRec, ptrdiff_t> {
     PointerRec *CurNode;
 
public:
     }
   };
 
 private:
   // Can only be created by AliasSetTracker. Also, ilist creates one
   // to serve as a sentinel.
   friend struct ilist_sentinel_traits<AliasSet>;
   AliasSet()
       : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0),
-      Access(NoAccess), Alias(SetMustAlias), Volatile(false) {
-  }
+        AliasAny(false), Access(NoAccess), Alias(SetMustAlias),
+        Volatile(false), SetSize(0) {}
 
   AliasSet(const AliasSet &AS) = delete;
   void operator=(const AliasSet &AS) = delete;
 
   PointerRec *getSomePointer() const {
     return PtrList;
   }
 
typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*,
     PointerMapType;
 
   // Map from pointers to their node
   PointerMapType PointerMap;
 
 public:
   /// Create an empty collection of AliasSets, and use the specified alias
   /// analysis object to disambiguate load and store addresses.
-  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
+  explicit AliasSetTracker(AliasAnalysis &aa)
+      : AA(aa), TotalMayAliasSetSize(0), AliasAnyAS(nullptr) {}
   ~AliasSetTracker() { clear(); }
 
   /// These methods are used to add different types of instructions to the alias
   /// sets. Adding a new instruction can result in one of three actions
   /// happening:
   ///
   ///   1. If the instruction doesn't alias any other sets, create a new set.
   ///   2. If the instruction aliases exactly one set, add it to the set
public:
   iterator begin() { return AliasSets.begin(); }
   iterator end()   { return AliasSets.end(); }
 
   void print(raw_ostream &OS) const;
   void dump() const;
 
 private:
   friend class AliasSet;
+
+  // The total number of pointers contained in all "may" alias sets.
+  unsigned TotalMayAliasSetSize;
+
+  // A non-null value signifies this AST is saturated. A saturated AST lumps
+  // all pointers into a single "May" set.
+  AliasSet *AliasAnyAS;
+
   void removeAliasSet(AliasSet *AS);
 
   /// 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[ASTCallbackVH(V, this)];
     if (!Entry)
       Entry = new AliasSet::PointerRec(V);
     return *Entry;
   }
 
   AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo,
-                       AliasSet::AccessLattice E,
-                       bool &NewSet) {
-    NewSet = false;
-    AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet);
-    AS.Access |= E;
-    return AS;
-  }
+                       AliasSet::AccessLattice E, bool &NewSet);
   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size,
                                      const AAMDNodes &AAInfo);
 
+  /// Merge all alias sets into a single set that is considered to alias any
+  /// pointer.
+  AliasSet &mergeAllAliasSets();
+
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
   AST.print(OS);
   return OS;
 }
 
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/Analysis/AliasSetTracker.cpp

 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
+static cl::opt<unsigned>
+    SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
+                        cl::init(250),
+                        cl::desc("The maximum number of pointers may-alias "
+                                 "sets may contain before degradation"));
+
 /// mergeSetIn - Merge the specified alias set into this alias set.
 ///
 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
   assert(!AS.Forward && "Alias set is already forwarding!");
   assert(!Forward && "This set is a forwarding set!!");
 
+  bool WasMustAlias = (Alias == SetMustAlias);
   // Update the alias and access types of this set...
   Access |= AS.Access;
   Alias  |= AS.Alias;
   Volatile |= AS.Volatile;
 
   if (Alias == SetMustAlias) {
     // Check that these two merged sets really are must aliases.  Since both
     // used to be must-alias sets, we can just check any pointer from each set
     // for aliasing.
     AliasAnalysis &AA = AST.getAliasAnalysis();
     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(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
                  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
         MustAlias)
       Alias = SetMayAlias;
   }
 
+  if (Alias == SetMayAlias) {
+    if (WasMustAlias)
+      AST.TotalMayAliasSetSize += size();
+    if (AS.Alias == SetMustAlias)
+      AST.TotalMayAliasSetSize += AS.size();
+  }
+
   bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
   if (UnknownInsts.empty()) {            // Merge call sites...
     if (ASHadUnknownInsts) {
       std::swap(UnknownInsts, AS.UnknownInsts);
       addRef();
     }
   } else if (ASHadUnknownInsts) {
     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
     AS.UnknownInsts.clear();
   }
 
-  AS.Forward = this;  // Forward across AS now...
-  addRef();           // AS is now pointing to us...
+  AS.Forward = this; // Forward across AS now...
+  addRef();          // AS is now pointing to us...
 
   // Merge the list of constituent pointers...
   if (AS.PtrList) {
+    SetSize += AS.size();
+    AS.SetSize = 0;
     *PtrListEnd = AS.PtrList;
     AS.PtrList->setPrevInList(PtrListEnd);
     PtrListEnd = AS.PtrListEnd;
 
     AS.PtrList = nullptr;
     AS.PtrListEnd = &AS.PtrList;
     assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
   }
   if (ASHadUnknownInsts)
     AS.dropRef(AST);
 }
 
 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
   if (AliasSet *Fwd = AS->Forward) {
     Fwd->dropRef(*this);
     AS->Forward = nullptr;
   }
+
+  if (AS->Alias == AliasSet::SetMayAlias)
+    TotalMayAliasSetSize -= AS->size();
+
   AliasSets.erase(AS);
+
 }
 
 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
   AST.removeAliasSet(this);
 }
 
 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
                           uint64_t Size, const AAMDNodes &AAInfo,
                           bool KnownMustAlias) {
   assert(!Entry.hasAliasSet() && "Entry already in set!");
 
   // Check to see if we have to downgrade to _may_ alias.
   if (isMustAlias() && !KnownMustAlias)
     if (PointerRec *P = getSomePointer()) {
       AliasAnalysis &AA = AST.getAliasAnalysis();
       AliasResult Result =
           AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
                    MemoryLocation(Entry.getValue(), Size, AAInfo));
-      if (Result != MustAlias)
+      if (Result != MustAlias) {
         Alias = SetMayAlias;
-      else                  // First entry of must alias must have maximum size!
+        AST.TotalMayAliasSetSize += size();
+      } else {
+        // First entry of must alias must have maximum size!        
         P->updateSizeAndAAInfo(Size, AAInfo);
+      }
       assert(Result != NoAlias && "Cannot be part of must set!");
     }
 
   Entry.setAliasSet(this);
   Entry.updateSizeAndAAInfo(Size, AAInfo);
 
   // Add it to the end of the list...
+  ++SetSize;
   assert(*PtrListEnd == nullptr && "End of list is not null?");
   *PtrListEnd = &Entry;
   PtrListEnd = Entry.setPrevInList(PtrListEnd);
   assert(*PtrListEnd == nullptr && "End of list is not null?");
-  addRef();               // Entry points to alias set.
+  // Entry points to alias set.
+  addRef();
+
+  if (Alias == SetMayAlias)
+    AST.TotalMayAliasSetSize++;
 }
 
 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
   if (UnknownInsts.empty())
     addRef();
   UnknownInsts.emplace_back(I);
 
   if (!I->mayWriteToMemory()) {
     Alias = SetMayAlias;
     Access |= RefAccess;
     return;
   }
 
   // FIXME: This should use mod/ref information to make this not suck so bad
   Alias = SetMayAlias;
   Access = ModRefAccess;
 }
 
 /// aliasesPointer - Return true if the specified pointer "may" (or must)
 /// alias one of the members in the set.
 ///
 bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
                               const AAMDNodes &AAInfo,
                               AliasAnalysis &AA) const {
+  if (AliasAny)
+    return true;
+
   if (Alias == SetMustAlias) {
     assert(UnknownInsts.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.
     PointerRec *SomePtr = getSomePointer();
     assert(SomePtr && "Empty must-alias set??");
     return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
         return true;
   }
 
   return false;
 }
 
 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
                                   AliasAnalysis &AA) const {
+
+  if (AliasAny)
+    return true;
+
   if (!Inst->mayReadOrWriteMemory())
     return false;
 
   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
     ImmutableCallSite C1(getUnknownInst(i)), C2(Inst);
     if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
         AA.getModRefInfo(C2, C1) != MRI_NoModRef)
       return true;
for (iterator I = begin(), E = end(); I != E;) {
     if (!FoundSet)            // If this is the first alias set ptr can go into.
       FoundSet = &*Cur;       // Remember it.
     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
   }
   return FoundSet;
 }
 
-
-
-
 /// getAliasSetForPointer - Return the alias set that the specified pointer
 /// lives in.
 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
                                                  const AAMDNodes &AAInfo,
                                                  bool *New) {
   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
 
+  if (AliasAnyAS) {
+    // At this point, the AST is saturated, so we only have one active alias
+    // set. That means we already know which alias set we want to return, and
+    // just need to add the pointer to that set to keep the data structure
+    // consistent.
+    // This, of course, means that we will never need a merge here.
+    if (Entry.hasAliasSet()) {
+      Entry.updateSizeAndAAInfo(Size, AAInfo);
+      assert(Entry.getAliasSet(*this) == AliasAnyAS &&
+             "Entry in saturated AST must belong to only alias set");
+    } else {
+      AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
+    }
+    return *AliasAnyAS;
+  }
+
   // Check to see if the pointer is already known.
   if (Entry.hasAliasSet()) {
     // If the size changed, we may need to merge several alias sets.
     // Note that we can *not* return the result of mergeAliasSetsForPointer
     // due to a quirk of alias analysis behavior. Since alias(undef, undef)
     // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
     // the right set for undef, even if it exists.
     if (Entry.updateSizeAndAAInfo(Size, AAInfo))
void AliasSetTracker::deleteValue(Value *PtrVal) {
   if (I == PointerMap.end()) return;  // Noop
 
   // If we found one, remove the pointer from the alias set it is in.
   AliasSet::PointerRec *PtrValEnt = I->second;
   AliasSet *AS = PtrValEnt->getAliasSet(*this);
 
   // Unlink and delete from the list of values.
   PtrValEnt->eraseFromList();
-  
+  if (AS->Alias == AliasSet::SetMayAlias) {
+    AS->SetSize--;
+    TotalMayAliasSetSize--;
+  }
+  
   // Stop using the alias set.
   AS->dropRef(*this);
   
   PointerMap.erase(I);
 }
 
 // copyValue - This method should be used whenever a preexisting value in the
 // program is copied or cloned, introducing a new value.  Note that it is ok for
void AliasSetTracker::copyValue(Value *From, Value *To) {
   I = PointerMap.find_as(From);
   // Add it to the alias set it aliases...
   AliasSet *AS = I->second->getAliasSet(*this);
   AS->addPointer(*this, Entry, I->second->getSize(),
                  I->second->getAAInfo(),
                  true);
 }
 
+AliasSet &AliasSetTracker::mergeAllAliasSets() {
+  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
+         "Full merge should happen once, when the saturation threshold is "
+         "reached");
+
+  // Collect all alias sets, so that we can drop references with impunity
+  // without worrying about iterator invalidation.
+  std::vector<AliasSet *> ASVector;
+  ASVector.reserve(SaturationThreshold);
+  for (iterator I = begin(), E = end(); I != E; I++)
+    ASVector.push_back(&*I);
+
+  // Copy all instructions and pointers into a new set, and forward all other
+  // sets to it.
+  AliasSets.push_back(new AliasSet());
+  AliasAnyAS = &AliasSets.back();
+  AliasAnyAS->Alias = AliasSet::SetMayAlias;
+  AliasAnyAS->Access = AliasSet::ModRefAccess;
+  AliasAnyAS->AliasAny = true;
+
+  for (auto Cur : ASVector) {
+    
+    // If Cur was already forwarding, just forward to the new AS instead.
+    AliasSet *FwdTo = Cur->Forward;
+    if (FwdTo) {
+      Cur->Forward = AliasAnyAS;
+      AliasAnyAS->addRef();      
+      FwdTo->dropRef(*this);
+      continue;
+    }
 
+    // Otherwise, perform the actual merge.
+    AliasAnyAS->mergeSetIn(*Cur, *this);
+  }
+
+  return *AliasAnyAS;
+}
+
+AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size,
+                                      const AAMDNodes &AAInfo,
+                                      AliasSet::AccessLattice E, bool &NewSet) {
+
+  NewSet = false;
+  AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet);
+  AS.Access |= E;
+
+  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
+    // The AST is now saturated. From here on, we conservatively consider all
+    // pointers to alias each-other.
+    return mergeAllAliasSets();
+  }
+
+  return AS;
+}
 
 //===----------------------------------------------------------------------===//
 //               AliasSet/AliasSetTracker Printing Support
 //===----------------------------------------------------------------------===//
 
 void AliasSet::print(raw_ostream &OS) const {
   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
   OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
public:
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesAll();
       AU.addRequired<AAResultsWrapperPass>();
     }
 
     bool runOnFunction(Function &F) override {
       auto &AAWP = getAnalysis<AAResultsWrapperPass>();
       Tracker = new AliasSetTracker(AAWP.getAAResults());
-
+      errs() << "Alias sets for function '" << F.getName() << "':\n";
       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
         Tracker->add(&*I);
       Tracker->print(errs());
       delete Tracker;
       return false;
     }
   };
 }
 
 char AliasSetPrinter::ID = 0;
 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
                 "Alias Set Printer", false, true)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
                 "Alias Set Printer", false, true)

llvm/trunk/test/Analysis/AliasSet/saturation.ll

+; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-threshold=2 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=NOSAT
+; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-threshold=1 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=SAT
+
+; CHECK-LABEL: 'allmust'
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, 4)
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4)
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %c, 4)
+; CHECK: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %d, 4)
+define void @allmust() {
+  %a = alloca i32
+  %b = alloca i32
+  %c = alloca i32
+  %d = alloca i32
+  store i32 1, i32* %a
+  store i32 2, i32* %b
+  store i32 3, i32* %c
+  store i32 4, i32* %d
+  ret void
+}
+
+; CHECK-LABEL :'mergemay'
+; NOSAT: AliasSet[{{.*}}, 2] may alias, Mod Pointers: (i32* %a, 4), (i32* %a1, 4)
+; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4)
+; SAT: AliasSet[{{.*}}, 2] may alias, Mod forwarding to 0x[[FWD:[0-9a-f]*]]
+; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD]]
+; SAT: AliasSet[0x[[FWD]], 2] may alias, Mod/Ref Pointers: (i32* %a, 4), (i32* %a1, 4), (i32* %b, 4)
+define void @mergemay(i32 %k) {
+  %a = alloca i32
+  %b = alloca i32
+  store i32 1, i32* %a
+  store i32 2, i32* %b
+  %a1 = getelementptr i32, i32 *%a, i32 %k
+  store i32 2, i32* %a1  
+  ret void
+}
+
+; CHECK-LABEL: 'mergemust'
+; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %a, 4)
+; NOSAT: AliasSet[{{.*}}, 1] must alias, Mod Pointers: (i32* %b, 4)
+; NOSAT: AliasSet[{{.*}}, 2] may alias,  Mod Pointers: (i32* %c, 4), (i32* %d, 4)
+; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD:[0-9a-f]*]]
+; SAT: AliasSet[{{.*}}, 1] must alias, Mod forwarding to 0x[[FWD]]
+; SAT: AliasSet[{{.*}}, 2] may alias,  Mod forwarding to 0x[[FWD]]
+; SAT: AliasSet[0x[[FWD]], 3] may alias, Mod/Ref Pointers: (i32* %a, 4), (i32* %b, 4), (i32* %c, 4), (i32* %d, 4)
+define void @mergemust(i32* %c, i32* %d) {
+  %a = alloca i32
+  %b = alloca i32
+  store i32 1, i32* %a
+  store i32 2, i32* %b
+  store i32 3, i32* %c
+  store i32 4, i32* %d
+  ret void
+}