[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

Singifies --> Signifies

132–133

How about it be called 'AliasAny' ?

413

nit: AliasAnyAS may sound better

433

Add brief documentation.

lib/Analysis/AliasSetTracker.cpp

29

add option description.

82

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

288

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

596

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

632

The AST is now ..

[mkuper]

Thanks, David!

include/llvm/Analysis/AliasSetTracker.h

132–133

Sounds good.

413

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

Ugh, right, thanks!

288

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()?

596

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

288

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

292

Add assert that aliasSet of Entry is indeed AliasAnyAS.

521

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

[mkuper]

lib/Analysis/AliasSetTracker.cpp

288

Sure.

292

Good idea, thanks!

521

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.

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;
 
   /// 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 {
     NoAccess = 0,
     RefAccess = 1,
     ModAccess = 2,
     ModRefAccess = RefAccess | ModAccess
   };
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; }
 
+  // TODO: This should not be RefCount - RefCount is an upper bound on the
+  // size, not the actual size, since it includes other references,
+  // like forwarding sets. Unfortunately, ilist::size() is linear, so we'd have
+  // to add code to keep track of the exact size.
+  unsigned size() { return RefCount; }
+
   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;
 
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), Saturated(false) {}
   ~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;
+
+  // An upper bound for the total number of pointers contained in all
+  // "may" alias sets.
+  // TODO: Make this precise, see AliasSet::size() for details.
+  unsigned TotalMayAliasSetSize;
+
+  // Signifies this AST is saturated. A saturated AST lumps all pointers into
+  // a single "May" set.
+  bool Saturated;
+
   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);
 
+  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

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> SaturationBound("alias-set-saturation-size",
+                                         cl::Hidden, cl::init(250));
+
 /// 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...
 
   // Merge the list of constituent pointers...
   if (AS.PtrList) {
     *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;
   }
   AliasSets.erase(AS);
+
+  if (AS->Alias == AliasSet::SetMayAlias)
+    TotalMayAliasSetSize -= AS->size();
 }
 
 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...
   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.
+
+  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 {
+  // TODO: If the AST is saturated, the answer for the special set should be
+  // yes.
+
   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 {
+
+  // TODO: If the AST is saturated, the answer for the special set should be
+  // yes.
+
   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 (Saturated) {
+    // Update the data structure, for the sake of consistency.
+    // Note that we will never need a merge here, since there's only one
+    // active alias set.
+    if (Entry.hasAliasSet())
+      Entry.updateSizeAndAAInfo(Size, AAInfo);
+    else
+      AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
+    return AliasSets.back();
+  }
+
   // 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)
+    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) {
   // Add it to the alias set it aliases...
   I = PointerMap.find_as(From);
   AliasSet *AS = I->second->getAliasSet(*this);
   AS->addPointer(*this, Entry, I->second->getSize(),
                  I->second->getAAInfo(),
                  true);
 }
 
+AliasSet &AliasSetTracker::mergeAllAliasSets() {
+  Saturated = true;
 
+  // Collect all alias sets, so that we can drop references with impunity
+  // without worrying about iterator invalidation.
+  std::vector<AliasSet *> ASVector;
+  ASVector.reserve(SaturationBound);
+  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());
+  AliasSet &DummyAS = AliasSets.back();
+  DummyAS.Alias = AliasSet::SetMayAlias;
+  DummyAS.Access = AliasSet::ModRefAccess;
+
+  for (auto Cur : ASVector) {
+    // Redirect the existing set here.
+    AliasSet *FwdTo = Cur->Forward;
+    Cur->Forward = &DummyAS;
+    DummyAS.addRef();
+
+    // If Cur was already forwarding, that is enough.
+    if (FwdTo) {
+      FwdTo->dropRef(*this);
+      continue;
+    }
+
+    // Otherwise, we need to do the actual work of copying.
+    if (!Cur->UnknownInsts.empty()) {
+      if (DummyAS.UnknownInsts.empty())
+        DummyAS.addRef();
+      DummyAS.UnknownInsts.insert(DummyAS.UnknownInsts.end(),
+                                  Cur->UnknownInsts.begin(),
+                                  Cur->UnknownInsts.end());
+      Cur->UnknownInsts.clear();
+      Cur->dropRef(*this);
+    }
+
+    // Merge the list pointers...
+    if (Cur->PtrList) {
+      *DummyAS.PtrListEnd = Cur->PtrList;
+      Cur->PtrList->setPrevInList(DummyAS.PtrListEnd);
+      DummyAS.PtrListEnd = Cur->PtrListEnd;
+
+      Cur->PtrList = nullptr;
+      Cur->PtrListEnd = &Cur->PtrList;
+    }
+  }
+
+  return AliasSets.back();
+}
+
+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 (!Saturated && (TotalMayAliasSetSize > SaturationBound)) {
+    // The AS 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, ";
   switch (Access) {
   case NoAccess:     OS << "No access "; break;
   case RefAccess:    OS << "Ref       "; break;
   case ModAccess:    OS << "Mod       "; break;
   case ModRefAccess: OS << "Mod/Ref   "; break;
   default: llvm_unreachable("Bad value for Access!");
   }
   if (isVolatile()) OS << "[volatile] ";
   if (Forward)
     OS << " forwarding to " << (void*)Forward;

 
 void AliasSetTracker::print(raw_ostream &OS) const {
   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
      << PointerMap.size() << " pointer values.\n";
   for (const AliasSet &AS : *this)
     AS.print(OS);
   OS << "\n";
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
 LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
 #endif
 
 //===----------------------------------------------------------------------===//
 //                     ASTCallbackVH Class Implementation
 //===----------------------------------------------------------------------===//

test/Analysis/AliasSet/saturation.ll

+; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-size=2 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=NOSAT
+; RUN: opt -basicaa -print-alias-sets -alias-set-saturation-size=1 -S -o - < %s 2>&1 | FileCheck %s --check-prefix=SAT
+
+; 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 @foo(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
+}