contrib/llvm/lib/Analysis/AliasSetTracker.cpp

   1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the AliasSetTracker and AliasSet classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/AliasSetTracker.h"
  15 #include "llvm/Analysis/AliasAnalysis.h"
  16 #include "llvm/IR/DataLayout.h"
  17 #include "llvm/IR/InstIterator.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/IR/IntrinsicInst.h"
  20 #include "llvm/IR/Module.h"
  21 #include "llvm/IR/LLVMContext.h"
  22 #include "llvm/IR/Type.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 using namespace llvm;
  28
  29 static cl::opt<unsigned>
  30     SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
  31                         cl::init(250),
  32                         cl::desc("The maximum number of pointers may-alias "
  33                                  "sets may contain before degradation"));
  34
  35 /// mergeSetIn - Merge the specified alias set into this alias set.
  36 ///
  37 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
  38   assert(!AS.Forward && "Alias set is already forwarding!");
  39   assert(!Forward && "This set is a forwarding set!!");
  40
  41   bool WasMustAlias = (Alias == SetMustAlias);
  42   // Update the alias and access types of this set...
  43   Access |= AS.Access;
  44   Alias  |= AS.Alias;
  45   Volatile |= AS.Volatile;
  46
  47   if (Alias == SetMustAlias) {
  48     // Check that these two merged sets really are must aliases.  Since both
  49     // used to be must-alias sets, we can just check any pointer from each set
  50     // for aliasing.
  51     AliasAnalysis &AA = AST.getAliasAnalysis();
  52     PointerRec *L = getSomePointer();
  53     PointerRec *R = AS.getSomePointer();
  54
  55     // If the pointers are not a must-alias pair, this set becomes a may alias.
  56     if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
  57                  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
  58         MustAlias)
  59       Alias = SetMayAlias;
  60   }
  61
  62   if (Alias == SetMayAlias) {
  63     if (WasMustAlias)
  64       AST.TotalMayAliasSetSize += size();
  65     if (AS.Alias == SetMustAlias)
  66       AST.TotalMayAliasSetSize += AS.size();
  67   }
  68
  69   bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
  70   if (UnknownInsts.empty()) {            // Merge call sites...
  71     if (ASHadUnknownInsts) {
  72       std::swap(UnknownInsts, AS.UnknownInsts);
  73       addRef();
  74     }
  75   } else if (ASHadUnknownInsts) {
  76     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
  77     AS.UnknownInsts.clear();
  78   }
  79
  80   AS.Forward = this; // Forward across AS now...
  81   addRef();          // AS is now pointing to us...
  82
  83   // Merge the list of constituent pointers...
  84   if (AS.PtrList) {
  85     SetSize += AS.size();
  86     AS.SetSize = 0;
  87     *PtrListEnd = AS.PtrList;
  88     AS.PtrList->setPrevInList(PtrListEnd);
  89     PtrListEnd = AS.PtrListEnd;
  90
  91     AS.PtrList = nullptr;
  92     AS.PtrListEnd = &AS.PtrList;
  93     assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
  94   }
  95   if (ASHadUnknownInsts)
  96     AS.dropRef(AST);
  97 }
  98
  99 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
 100   if (AliasSet *Fwd = AS->Forward) {
 101     Fwd->dropRef(*this);
 102     AS->Forward = nullptr;
 103   }
 104
 105   if (AS->Alias == AliasSet::SetMayAlias)
 106     TotalMayAliasSetSize -= AS->size();
 107
 108   AliasSets.erase(AS);
 109
 110 }
 111
 112 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
 113   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
 114   AST.removeAliasSet(this);
 115 }
 116
 117 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
 118                           uint64_t Size, const AAMDNodes &AAInfo,
 119                           bool KnownMustAlias) {
 120   assert(!Entry.hasAliasSet() && "Entry already in set!");
 121
 122   // Check to see if we have to downgrade to _may_ alias.
 123   if (isMustAlias() && !KnownMustAlias)
 124     if (PointerRec *P = getSomePointer()) {
 125       AliasAnalysis &AA = AST.getAliasAnalysis();
 126       AliasResult Result =
 127           AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
 128                    MemoryLocation(Entry.getValue(), Size, AAInfo));
 129       if (Result != MustAlias) {
 130         Alias = SetMayAlias;
 131         AST.TotalMayAliasSetSize += size();
 132       } else {
 133         // First entry of must alias must have maximum size!
 134         P->updateSizeAndAAInfo(Size, AAInfo);
 135       }
 136       assert(Result != NoAlias && "Cannot be part of must set!");
 137     }
 138
 139   Entry.setAliasSet(this);
 140   Entry.updateSizeAndAAInfo(Size, AAInfo);
 141
 142   // Add it to the end of the list...
 143   ++SetSize;
 144   assert(*PtrListEnd == nullptr && "End of list is not null?");
 145   *PtrListEnd = &Entry;
 146   PtrListEnd = Entry.setPrevInList(PtrListEnd);
 147   assert(*PtrListEnd == nullptr && "End of list is not null?");
 148   // Entry points to alias set.
 149   addRef();
 150
 151   if (Alias == SetMayAlias)
 152     AST.TotalMayAliasSetSize++;
 153 }
 154
 155 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
 156   if (UnknownInsts.empty())
 157     addRef();
 158   UnknownInsts.emplace_back(I);
 159
 160   if (!I->mayWriteToMemory()) {
 161     Alias = SetMayAlias;
 162     Access |= RefAccess;
 163     return;
 164   }
 165
 166   // FIXME: This should use mod/ref information to make this not suck so bad
 167   Alias = SetMayAlias;
 168   Access = ModRefAccess;
 169 }
 170
 171 /// aliasesPointer - Return true if the specified pointer "may" (or must)
 172 /// alias one of the members in the set.
 173 ///
 174 bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
 175                               const AAMDNodes &AAInfo,
 176                               AliasAnalysis &AA) const {
 177   if (AliasAny)
 178     return true;
 179
 180   if (Alias == SetMustAlias) {
 181     assert(UnknownInsts.empty() && "Illegal must alias set!");
 182
 183     // If this is a set of MustAliases, only check to see if the pointer aliases
 184     // SOME value in the set.
 185     PointerRec *SomePtr = getSomePointer();
 186     assert(SomePtr && "Empty must-alias set??");
 187     return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
 188                                    SomePtr->getAAInfo()),
 189                     MemoryLocation(Ptr, Size, AAInfo));
 190   }
 191
 192   // If this is a may-alias set, we have to check all of the pointers in the set
 193   // to be sure it doesn't alias the set...
 194   for (iterator I = begin(), E = end(); I != E; ++I)
 195     if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
 196                  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
 197       return true;
 198
 199   // Check the unknown instructions...
 200   if (!UnknownInsts.empty()) {
 201     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
 202       if (AA.getModRefInfo(UnknownInsts[i],
 203                            MemoryLocation(Ptr, Size, AAInfo)) != MRI_NoModRef)
 204         return true;
 205   }
 206
 207   return false;
 208 }
 209
 210 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
 211                                   AliasAnalysis &AA) const {
 212
 213   if (AliasAny)
 214     return true;
 215
 216   if (!Inst->mayReadOrWriteMemory())
 217     return false;
 218
 219   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
 220     ImmutableCallSite C1(getUnknownInst(i)), C2(Inst);
 221     if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
 222         AA.getModRefInfo(C2, C1) != MRI_NoModRef)
 223       return true;
 224   }
 225
 226   for (iterator I = begin(), E = end(); I != E; ++I)
 227     if (AA.getModRefInfo(Inst, MemoryLocation(I.getPointer(), I.getSize(),
 228                                               I.getAAInfo())) != MRI_NoModRef)
 229       return true;
 230
 231   return false;
 232 }
 233
 234 void AliasSetTracker::clear() {
 235   // Delete all the PointerRec entries.
 236   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
 237        I != E; ++I)
 238     I->second->eraseFromList();
 239
 240   PointerMap.clear();
 241
 242   // The alias sets should all be clear now.
 243   AliasSets.clear();
 244 }
 245
 246
 247 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
 248 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
 249 /// the pointer was found.
 250 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
 251                                                     uint64_t Size,
 252                                                     const AAMDNodes &AAInfo) {
 253   AliasSet *FoundSet = nullptr;
 254   for (iterator I = begin(), E = end(); I != E;) {
 255     iterator Cur = I++;
 256     if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
 257
 258     if (!FoundSet) {      // If this is the first alias set ptr can go into.
 259       FoundSet = &*Cur;   // Remember it.
 260     } else {              // Otherwise, we must merge the sets.
 261       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
 262     }
 263   }
 264
 265   return FoundSet;
 266 }
 267
 268 bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
 269   for (const AliasSet &AS : *this)
 270     if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
 271       return true;
 272   return false;
 273 }
 274
 275 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
 276   AliasSet *FoundSet = nullptr;
 277   for (iterator I = begin(), E = end(); I != E;) {
 278     iterator Cur = I++;
 279     if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
 280       continue;
 281     if (!FoundSet)            // If this is the first alias set ptr can go into.
 282       FoundSet = &*Cur;       // Remember it.
 283     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
 284       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
 285   }
 286   return FoundSet;
 287 }
 288
 289 /// getAliasSetForPointer - Return the alias set that the specified pointer
 290 /// lives in.
 291 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
 292                                                  const AAMDNodes &AAInfo) {
 293   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
 294
 295   if (AliasAnyAS) {
 296     // At this point, the AST is saturated, so we only have one active alias
 297     // set. That means we already know which alias set we want to return, and
 298     // just need to add the pointer to that set to keep the data structure
 299     // consistent.
 300     // This, of course, means that we will never need a merge here.
 301     if (Entry.hasAliasSet()) {
 302       Entry.updateSizeAndAAInfo(Size, AAInfo);
 303       assert(Entry.getAliasSet(*this) == AliasAnyAS &&
 304              "Entry in saturated AST must belong to only alias set");
 305     } else {
 306       AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
 307     }
 308     return *AliasAnyAS;
 309   }
 310
 311   // Check to see if the pointer is already known.
 312   if (Entry.hasAliasSet()) {
 313     // If the size changed, we may need to merge several alias sets.
 314     // Note that we can *not* return the result of mergeAliasSetsForPointer
 315     // due to a quirk of alias analysis behavior. Since alias(undef, undef)
 316     // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
 317     // the right set for undef, even if it exists.
 318     if (Entry.updateSizeAndAAInfo(Size, AAInfo))
 319       mergeAliasSetsForPointer(Pointer, Size, AAInfo);
 320     // Return the set!
 321     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
 322   }
 323
 324   if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
 325     // Add it to the alias set it aliases.
 326     AS->addPointer(*this, Entry, Size, AAInfo);
 327     return *AS;
 328   }
 329
 330   // Otherwise create a new alias set to hold the loaded pointer.
 331   AliasSets.push_back(new AliasSet());
 332   AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
 333   return AliasSets.back();
 334 }
 335
 336 void AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
 337   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
 338 }
 339
 340 void AliasSetTracker::add(LoadInst *LI) {
 341   if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
 342
 343   AAMDNodes AAInfo;
 344   LI->getAAMetadata(AAInfo);
 345
 346   AliasSet::AccessLattice Access = AliasSet::RefAccess;
 347   const DataLayout &DL = LI->getModule()->getDataLayout();
 348   AliasSet &AS = addPointer(LI->getOperand(0),
 349                             DL.getTypeStoreSize(LI->getType()), AAInfo, Access);
 350   if (LI->isVolatile()) AS.setVolatile();
 351 }
 352
 353 void AliasSetTracker::add(StoreInst *SI) {
 354   if (isStrongerThanMonotonic(SI->getOrdering())) return addUnknown(SI);
 355
 356   AAMDNodes AAInfo;
 357   SI->getAAMetadata(AAInfo);
 358
 359   AliasSet::AccessLattice Access = AliasSet::ModAccess;
 360   const DataLayout &DL = SI->getModule()->getDataLayout();
 361   Value *Val = SI->getOperand(0);
 362   AliasSet &AS = addPointer(
 363       SI->getOperand(1), DL.getTypeStoreSize(Val->getType()), AAInfo, Access);
 364   if (SI->isVolatile()) AS.setVolatile();
 365 }
 366
 367 void AliasSetTracker::add(VAArgInst *VAAI) {
 368   AAMDNodes AAInfo;
 369   VAAI->getAAMetadata(AAInfo);
 370
 371   addPointer(VAAI->getOperand(0), MemoryLocation::UnknownSize, AAInfo,
 372              AliasSet::ModRefAccess);
 373 }
 374
 375 void AliasSetTracker::add(MemSetInst *MSI) {
 376   AAMDNodes AAInfo;
 377   MSI->getAAMetadata(AAInfo);
 378
 379   uint64_t Len;
 380
 381   if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
 382     Len = C->getZExtValue();
 383   else
 384     Len = MemoryLocation::UnknownSize;
 385
 386   AliasSet &AS =
 387       addPointer(MSI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
 388   if (MSI->isVolatile())
 389     AS.setVolatile();
 390 }
 391
 392 void AliasSetTracker::add(MemTransferInst *MTI) {
 393   AAMDNodes AAInfo;
 394   MTI->getAAMetadata(AAInfo);
 395
 396   uint64_t Len;
 397   if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
 398     Len = C->getZExtValue();
 399   else
 400     Len = MemoryLocation::UnknownSize;
 401
 402   AliasSet &ASSrc =
 403       addPointer(MTI->getRawSource(), Len, AAInfo, AliasSet::RefAccess);
 404   if (MTI->isVolatile())
 405     ASSrc.setVolatile();
 406
 407   AliasSet &ASDst =
 408       addPointer(MTI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
 409   if (MTI->isVolatile())
 410     ASDst.setVolatile();
 411 }
 412
 413 void AliasSetTracker::addUnknown(Instruction *Inst) {
 414   if (isa<DbgInfoIntrinsic>(Inst))
 415     return; // Ignore DbgInfo Intrinsics.
 416
 417   if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
 418     // These intrinsics will show up as affecting memory, but they are just
 419     // markers.
 420     switch (II->getIntrinsicID()) {
 421     default:
 422       break;
 423       // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
 424     case Intrinsic::assume:
 425       return;
 426     }
 427   }
 428   if (!Inst->mayReadOrWriteMemory())
 429     return; // doesn't alias anything
 430
 431   AliasSet *AS = findAliasSetForUnknownInst(Inst);
 432   if (AS) {
 433     AS->addUnknownInst(Inst, AA);
 434     return;
 435   }
 436   AliasSets.push_back(new AliasSet());
 437   AS = &AliasSets.back();
 438   AS->addUnknownInst(Inst, AA);
 439 }
 440
 441 void AliasSetTracker::add(Instruction *I) {
 442   // Dispatch to one of the other add methods.
 443   if (LoadInst *LI = dyn_cast<LoadInst>(I))
 444     return add(LI);
 445   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 446     return add(SI);
 447   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
 448     return add(VAAI);
 449   if (MemSetInst *MSI = dyn_cast<MemSetInst>(I))
 450     return add(MSI);
 451   if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(I))
 452     return add(MTI);
 453   return addUnknown(I);
 454 }
 455
 456 void AliasSetTracker::add(BasicBlock &BB) {
 457   for (auto &I : BB)
 458     add(&I);
 459 }
 460
 461 void AliasSetTracker::add(const AliasSetTracker &AST) {
 462   assert(&AA == &AST.AA &&
 463          "Merging AliasSetTracker objects with different Alias Analyses!");
 464
 465   // Loop over all of the alias sets in AST, adding the pointers contained
 466   // therein into the current alias sets.  This can cause alias sets to be
 467   // merged together in the current AST.
 468   for (const AliasSet &AS : AST) {
 469     if (AS.Forward)
 470       continue; // Ignore forwarding alias sets
 471
 472     // If there are any call sites in the alias set, add them to this AST.
 473     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
 474       add(AS.UnknownInsts[i]);
 475
 476     // Loop over all of the pointers in this alias set.
 477     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
 478       AliasSet &NewAS =
 479           addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
 480                      (AliasSet::AccessLattice)AS.Access);
 481       if (AS.isVolatile()) NewAS.setVolatile();
 482     }
 483   }
 484 }
 485
 486 // deleteValue method - This method is used to remove a pointer value from the
 487 // AliasSetTracker entirely.  It should be used when an instruction is deleted
 488 // from the program to update the AST.  If you don't use this, you would have
 489 // dangling pointers to deleted instructions.
 490 //
 491 void AliasSetTracker::deleteValue(Value *PtrVal) {
 492   // If this is a call instruction, remove the callsite from the appropriate
 493   // AliasSet (if present).
 494   if (Instruction *Inst = dyn_cast<Instruction>(PtrVal)) {
 495     if (Inst->mayReadOrWriteMemory()) {
 496       // Scan all the alias sets to see if this call site is contained.
 497       for (iterator I = begin(), E = end(); I != E;) {
 498         iterator Cur = I++;
 499         if (!Cur->Forward)
 500           Cur->removeUnknownInst(*this, Inst);
 501       }
 502     }
 503   }
 504
 505   // First, look up the PointerRec for this pointer.
 506   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
 507   if (I == PointerMap.end()) return;  // Noop
 508
 509   // If we found one, remove the pointer from the alias set it is in.
 510   AliasSet::PointerRec *PtrValEnt = I->second;
 511   AliasSet *AS = PtrValEnt->getAliasSet(*this);
 512
 513   // Unlink and delete from the list of values.
 514   PtrValEnt->eraseFromList();
 515
 516   if (AS->Alias == AliasSet::SetMayAlias) {
 517     AS->SetSize--;
 518     TotalMayAliasSetSize--;
 519   }
 520
 521   // Stop using the alias set.
 522   AS->dropRef(*this);
 523
 524   PointerMap.erase(I);
 525 }
 526
 527 // copyValue - This method should be used whenever a preexisting value in the
 528 // program is copied or cloned, introducing a new value.  Note that it is ok for
 529 // clients that use this method to introduce the same value multiple times: if
 530 // the tracker already knows about a value, it will ignore the request.
 531 //
 532 void AliasSetTracker::copyValue(Value *From, Value *To) {
 533   // First, look up the PointerRec for this pointer.
 534   PointerMapType::iterator I = PointerMap.find_as(From);
 535   if (I == PointerMap.end())
 536     return;  // Noop
 537   assert(I->second->hasAliasSet() && "Dead entry?");
 538
 539   AliasSet::PointerRec &Entry = getEntryFor(To);
 540   if (Entry.hasAliasSet()) return;    // Already in the tracker!
 541
 542   // getEntryFor above may invalidate iterator \c I, so reinitialize it.
 543   I = PointerMap.find_as(From);
 544   // Add it to the alias set it aliases...
 545   AliasSet *AS = I->second->getAliasSet(*this);
 546   AS->addPointer(*this, Entry, I->second->getSize(),
 547                  I->second->getAAInfo(),
 548                  true);
 549 }
 550
 551 AliasSet &AliasSetTracker::mergeAllAliasSets() {
 552   assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
 553          "Full merge should happen once, when the saturation threshold is "
 554          "reached");
 555
 556   // Collect all alias sets, so that we can drop references with impunity
 557   // without worrying about iterator invalidation.
 558   std::vector<AliasSet *> ASVector;
 559   ASVector.reserve(SaturationThreshold);
 560   for (iterator I = begin(), E = end(); I != E; I++)
 561     ASVector.push_back(&*I);
 562
 563   // Copy all instructions and pointers into a new set, and forward all other
 564   // sets to it.
 565   AliasSets.push_back(new AliasSet());
 566   AliasAnyAS = &AliasSets.back();
 567   AliasAnyAS->Alias = AliasSet::SetMayAlias;
 568   AliasAnyAS->Access = AliasSet::ModRefAccess;
 569   AliasAnyAS->AliasAny = true;
 570
 571   for (auto Cur : ASVector) {
 572
 573     // If Cur was already forwarding, just forward to the new AS instead.
 574     AliasSet *FwdTo = Cur->Forward;
 575     if (FwdTo) {
 576       Cur->Forward = AliasAnyAS;
 577       AliasAnyAS->addRef();
 578       FwdTo->dropRef(*this);
 579       continue;
 580     }
 581
 582     // Otherwise, perform the actual merge.
 583     AliasAnyAS->mergeSetIn(*Cur, *this);
 584   }
 585
 586   return *AliasAnyAS;
 587 }
 588
 589 AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size,
 590                                       const AAMDNodes &AAInfo,
 591                                       AliasSet::AccessLattice E) {
 592
 593   AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo);
 594   AS.Access |= E;
 595
 596   if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
 597     // The AST is now saturated. From here on, we conservatively consider all
 598     // pointers to alias each-other.
 599     return mergeAllAliasSets();
 600   }
 601
 602   return AS;
 603 }
 604
 605 //===----------------------------------------------------------------------===//
 606 //               AliasSet/AliasSetTracker Printing Support
 607 //===----------------------------------------------------------------------===//
 608
 609 void AliasSet::print(raw_ostream &OS) const {
 610   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
 611   OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
 612   switch (Access) {
 613   case NoAccess:     OS << "No access "; break;
 614   case RefAccess:    OS << "Ref       "; break;
 615   case ModAccess:    OS << "Mod       "; break;
 616   case ModRefAccess: OS << "Mod/Ref   "; break;
 617   default: llvm_unreachable("Bad value for Access!");
 618   }
 619   if (isVolatile()) OS << "[volatile] ";
 620   if (Forward)
 621     OS << " forwarding to " << (void*)Forward;
 622
 623
 624   if (!empty()) {
 625     OS << "Pointers: ";
 626     for (iterator I = begin(), E = end(); I != E; ++I) {
 627       if (I != begin()) OS << ", ";
 628       I.getPointer()->printAsOperand(OS << "(");
 629       OS << ", " << I.getSize() << ")";
 630     }
 631   }
 632   if (!UnknownInsts.empty()) {
 633     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
 634     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
 635       if (i) OS << ", ";
 636       UnknownInsts[i]->printAsOperand(OS);
 637     }
 638   }
 639   OS << "\n";
 640 }
 641
 642 void AliasSetTracker::print(raw_ostream &OS) const {
 643   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
 644      << PointerMap.size() << " pointer values.\n";
 645   for (const AliasSet &AS : *this)
 646     AS.print(OS);
 647   OS << "\n";
 648 }
 649
 650 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 651 LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
 652 LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
 653 #endif
 654
 655 //===----------------------------------------------------------------------===//
 656 //                     ASTCallbackVH Class Implementation
 657 //===----------------------------------------------------------------------===//
 658
 659 void AliasSetTracker::ASTCallbackVH::deleted() {
 660   assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
 661   AST->deleteValue(getValPtr());
 662   // this now dangles!
 663 }
 664
 665 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
 666   AST->copyValue(getValPtr(), V);
 667 }
 668
 669 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
 670   : CallbackVH(V), AST(ast) {}
 671
 672 AliasSetTracker::ASTCallbackVH &
 673 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
 674   return *this = ASTCallbackVH(V, AST);
 675 }
 676
 677 //===----------------------------------------------------------------------===//
 678 //                            AliasSetPrinter Pass
 679 //===----------------------------------------------------------------------===//
 680
 681 namespace {
 682   class AliasSetPrinter : public FunctionPass {
 683     AliasSetTracker *Tracker;
 684   public:
 685     static char ID; // Pass identification, replacement for typeid
 686     AliasSetPrinter() : FunctionPass(ID) {
 687       initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
 688     }
 689
 690     void getAnalysisUsage(AnalysisUsage &AU) const override {
 691       AU.setPreservesAll();
 692       AU.addRequired<AAResultsWrapperPass>();
 693     }
 694
 695     bool runOnFunction(Function &F) override {
 696       auto &AAWP = getAnalysis<AAResultsWrapperPass>();
 697       Tracker = new AliasSetTracker(AAWP.getAAResults());
 698       errs() << "Alias sets for function '" << F.getName() << "':\n";
 699       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
 700         Tracker->add(&*I);
 701       Tracker->print(errs());
 702       delete Tracker;
 703       return false;
 704     }
 705   };
 706 }
 707
 708 char AliasSetPrinter::ID = 0;
 709 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
 710                 "Alias Set Printer", false, true)
 711 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 712 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
 713                 "Alias Set Printer", false, true)