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 (auto *Inst = getUnknownInst(i))
 203         if (AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo)) !=
 204             MRI_NoModRef)
 205           return true;
 206   }
 207
 208   return false;
 209 }
 210
 211 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
 212                                   AliasAnalysis &AA) const {
 213
 214   if (AliasAny)
 215     return true;
 216
 217   if (!Inst->mayReadOrWriteMemory())
 218     return false;
 219
 220   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
 221     if (auto *Inst = getUnknownInst(i)) {
 222       ImmutableCallSite C1(Inst), C2(Inst);
 223       if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
 224           AA.getModRefInfo(C2, C1) != MRI_NoModRef)
 225         return true;
 226     }
 227   }
 228
 229   for (iterator I = begin(), E = end(); I != E; ++I)
 230     if (AA.getModRefInfo(Inst, MemoryLocation(I.getPointer(), I.getSize(),
 231                                               I.getAAInfo())) != MRI_NoModRef)
 232       return true;
 233
 234   return false;
 235 }
 236
 237 void AliasSetTracker::clear() {
 238   // Delete all the PointerRec entries.
 239   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
 240        I != E; ++I)
 241     I->second->eraseFromList();
 242
 243   PointerMap.clear();
 244
 245   // The alias sets should all be clear now.
 246   AliasSets.clear();
 247 }
 248
 249
 250 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
 251 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
 252 /// the pointer was found.
 253 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
 254                                                     uint64_t Size,
 255                                                     const AAMDNodes &AAInfo) {
 256   AliasSet *FoundSet = nullptr;
 257   for (iterator I = begin(), E = end(); I != E;) {
 258     iterator Cur = I++;
 259     if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
 260
 261     if (!FoundSet) {      // If this is the first alias set ptr can go into.
 262       FoundSet = &*Cur;   // Remember it.
 263     } else {              // Otherwise, we must merge the sets.
 264       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
 265     }
 266   }
 267
 268   return FoundSet;
 269 }
 270
 271 bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
 272   for (const AliasSet &AS : *this)
 273     if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
 274       return true;
 275   return false;
 276 }
 277
 278 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
 279   AliasSet *FoundSet = nullptr;
 280   for (iterator I = begin(), E = end(); I != E;) {
 281     iterator Cur = I++;
 282     if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
 283       continue;
 284     if (!FoundSet)            // If this is the first alias set ptr can go into.
 285       FoundSet = &*Cur;       // Remember it.
 286     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
 287       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
 288   }
 289   return FoundSet;
 290 }
 291
 292 /// getAliasSetForPointer - Return the alias set that the specified pointer
 293 /// lives in.
 294 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
 295                                                  const AAMDNodes &AAInfo) {
 296   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
 297
 298   if (AliasAnyAS) {
 299     // At this point, the AST is saturated, so we only have one active alias
 300     // set. That means we already know which alias set we want to return, and
 301     // just need to add the pointer to that set to keep the data structure
 302     // consistent.
 303     // This, of course, means that we will never need a merge here.
 304     if (Entry.hasAliasSet()) {
 305       Entry.updateSizeAndAAInfo(Size, AAInfo);
 306       assert(Entry.getAliasSet(*this) == AliasAnyAS &&
 307              "Entry in saturated AST must belong to only alias set");
 308     } else {
 309       AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
 310     }
 311     return *AliasAnyAS;
 312   }
 313
 314   // Check to see if the pointer is already known.
 315   if (Entry.hasAliasSet()) {
 316     // If the size changed, we may need to merge several alias sets.
 317     // Note that we can *not* return the result of mergeAliasSetsForPointer
 318     // due to a quirk of alias analysis behavior. Since alias(undef, undef)
 319     // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
 320     // the right set for undef, even if it exists.
 321     if (Entry.updateSizeAndAAInfo(Size, AAInfo))
 322       mergeAliasSetsForPointer(Pointer, Size, AAInfo);
 323     // Return the set!
 324     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
 325   }
 326
 327   if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
 328     // Add it to the alias set it aliases.
 329     AS->addPointer(*this, Entry, Size, AAInfo);
 330     return *AS;
 331   }
 332
 333   // Otherwise create a new alias set to hold the loaded pointer.
 334   AliasSets.push_back(new AliasSet());
 335   AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
 336   return AliasSets.back();
 337 }
 338
 339 void AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
 340   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
 341 }
 342
 343 void AliasSetTracker::add(LoadInst *LI) {
 344   if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
 345
 346   AAMDNodes AAInfo;
 347   LI->getAAMetadata(AAInfo);
 348
 349   AliasSet::AccessLattice Access = AliasSet::RefAccess;
 350   const DataLayout &DL = LI->getModule()->getDataLayout();
 351   AliasSet &AS = addPointer(LI->getOperand(0),
 352                             DL.getTypeStoreSize(LI->getType()), AAInfo, Access);
 353   if (LI->isVolatile()) AS.setVolatile();
 354 }
 355
 356 void AliasSetTracker::add(StoreInst *SI) {
 357   if (isStrongerThanMonotonic(SI->getOrdering())) return addUnknown(SI);
 358
 359   AAMDNodes AAInfo;
 360   SI->getAAMetadata(AAInfo);
 361
 362   AliasSet::AccessLattice Access = AliasSet::ModAccess;
 363   const DataLayout &DL = SI->getModule()->getDataLayout();
 364   Value *Val = SI->getOperand(0);
 365   AliasSet &AS = addPointer(
 366       SI->getOperand(1), DL.getTypeStoreSize(Val->getType()), AAInfo, Access);
 367   if (SI->isVolatile()) AS.setVolatile();
 368 }
 369
 370 void AliasSetTracker::add(VAArgInst *VAAI) {
 371   AAMDNodes AAInfo;
 372   VAAI->getAAMetadata(AAInfo);
 373
 374   addPointer(VAAI->getOperand(0), MemoryLocation::UnknownSize, AAInfo,
 375              AliasSet::ModRefAccess);
 376 }
 377
 378 void AliasSetTracker::add(MemSetInst *MSI) {
 379   AAMDNodes AAInfo;
 380   MSI->getAAMetadata(AAInfo);
 381
 382   uint64_t Len;
 383
 384   if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
 385     Len = C->getZExtValue();
 386   else
 387     Len = MemoryLocation::UnknownSize;
 388
 389   AliasSet &AS =
 390       addPointer(MSI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
 391   if (MSI->isVolatile())
 392     AS.setVolatile();
 393 }
 394
 395 void AliasSetTracker::add(MemTransferInst *MTI) {
 396   AAMDNodes AAInfo;
 397   MTI->getAAMetadata(AAInfo);
 398
 399   uint64_t Len;
 400   if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
 401     Len = C->getZExtValue();
 402   else
 403     Len = MemoryLocation::UnknownSize;
 404
 405   AliasSet &ASSrc =
 406       addPointer(MTI->getRawSource(), Len, AAInfo, AliasSet::RefAccess);
 407   if (MTI->isVolatile())
 408     ASSrc.setVolatile();
 409
 410   AliasSet &ASDst =
 411       addPointer(MTI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
 412   if (MTI->isVolatile())
 413     ASDst.setVolatile();
 414 }
 415
 416 void AliasSetTracker::addUnknown(Instruction *Inst) {
 417   if (isa<DbgInfoIntrinsic>(Inst))
 418     return; // Ignore DbgInfo Intrinsics.
 419
 420   if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
 421     // These intrinsics will show up as affecting memory, but they are just
 422     // markers.
 423     switch (II->getIntrinsicID()) {
 424     default:
 425       break;
 426       // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
 427     case Intrinsic::assume:
 428       return;
 429     }
 430   }
 431   if (!Inst->mayReadOrWriteMemory())
 432     return; // doesn't alias anything
 433
 434   AliasSet *AS = findAliasSetForUnknownInst(Inst);
 435   if (AS) {
 436     AS->addUnknownInst(Inst, AA);
 437     return;
 438   }
 439   AliasSets.push_back(new AliasSet());
 440   AS = &AliasSets.back();
 441   AS->addUnknownInst(Inst, AA);
 442 }
 443
 444 void AliasSetTracker::add(Instruction *I) {
 445   // Dispatch to one of the other add methods.
 446   if (LoadInst *LI = dyn_cast<LoadInst>(I))
 447     return add(LI);
 448   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 449     return add(SI);
 450   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
 451     return add(VAAI);
 452   if (MemSetInst *MSI = dyn_cast<MemSetInst>(I))
 453     return add(MSI);
 454   if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(I))
 455     return add(MTI);
 456   return addUnknown(I);
 457 }
 458
 459 void AliasSetTracker::add(BasicBlock &BB) {
 460   for (auto &I : BB)
 461     add(&I);
 462 }
 463
 464 void AliasSetTracker::add(const AliasSetTracker &AST) {
 465   assert(&AA == &AST.AA &&
 466          "Merging AliasSetTracker objects with different Alias Analyses!");
 467
 468   // Loop over all of the alias sets in AST, adding the pointers contained
 469   // therein into the current alias sets.  This can cause alias sets to be
 470   // merged together in the current AST.
 471   for (const AliasSet &AS : AST) {
 472     if (AS.Forward)
 473       continue; // Ignore forwarding alias sets
 474
 475     // If there are any call sites in the alias set, add them to this AST.
 476     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
 477       if (auto *Inst = AS.getUnknownInst(i))
 478         add(Inst);
 479
 480     // Loop over all of the pointers in this alias set.
 481     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
 482       AliasSet &NewAS =
 483           addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
 484                      (AliasSet::AccessLattice)AS.Access);
 485       if (AS.isVolatile()) NewAS.setVolatile();
 486     }
 487   }
 488 }
 489
 490 // deleteValue method - This method is used to remove a pointer value from the
 491 // AliasSetTracker entirely.  It should be used when an instruction is deleted
 492 // from the program to update the AST.  If you don't use this, you would have
 493 // dangling pointers to deleted instructions.
 494 //
 495 void AliasSetTracker::deleteValue(Value *PtrVal) {
 496   // First, look up the PointerRec for this pointer.
 497   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
 498   if (I == PointerMap.end()) return;  // Noop
 499
 500   // If we found one, remove the pointer from the alias set it is in.
 501   AliasSet::PointerRec *PtrValEnt = I->second;
 502   AliasSet *AS = PtrValEnt->getAliasSet(*this);
 503
 504   // Unlink and delete from the list of values.
 505   PtrValEnt->eraseFromList();
 506
 507   if (AS->Alias == AliasSet::SetMayAlias) {
 508     AS->SetSize--;
 509     TotalMayAliasSetSize--;
 510   }
 511
 512   // Stop using the alias set.
 513   AS->dropRef(*this);
 514
 515   PointerMap.erase(I);
 516 }
 517
 518 // copyValue - This method should be used whenever a preexisting value in the
 519 // program is copied or cloned, introducing a new value.  Note that it is ok for
 520 // clients that use this method to introduce the same value multiple times: if
 521 // the tracker already knows about a value, it will ignore the request.
 522 //
 523 void AliasSetTracker::copyValue(Value *From, Value *To) {
 524   // First, look up the PointerRec for this pointer.
 525   PointerMapType::iterator I = PointerMap.find_as(From);
 526   if (I == PointerMap.end())
 527     return;  // Noop
 528   assert(I->second->hasAliasSet() && "Dead entry?");
 529
 530   AliasSet::PointerRec &Entry = getEntryFor(To);
 531   if (Entry.hasAliasSet()) return;    // Already in the tracker!
 532
 533   // getEntryFor above may invalidate iterator \c I, so reinitialize it.
 534   I = PointerMap.find_as(From);
 535   // Add it to the alias set it aliases...
 536   AliasSet *AS = I->second->getAliasSet(*this);
 537   AS->addPointer(*this, Entry, I->second->getSize(),
 538                  I->second->getAAInfo(),
 539                  true);
 540 }
 541
 542 AliasSet &AliasSetTracker::mergeAllAliasSets() {
 543   assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
 544          "Full merge should happen once, when the saturation threshold is "
 545          "reached");
 546
 547   // Collect all alias sets, so that we can drop references with impunity
 548   // without worrying about iterator invalidation.
 549   std::vector<AliasSet *> ASVector;
 550   ASVector.reserve(SaturationThreshold);
 551   for (iterator I = begin(), E = end(); I != E; I++)
 552     ASVector.push_back(&*I);
 553
 554   // Copy all instructions and pointers into a new set, and forward all other
 555   // sets to it.
 556   AliasSets.push_back(new AliasSet());
 557   AliasAnyAS = &AliasSets.back();
 558   AliasAnyAS->Alias = AliasSet::SetMayAlias;
 559   AliasAnyAS->Access = AliasSet::ModRefAccess;
 560   AliasAnyAS->AliasAny = true;
 561
 562   for (auto Cur : ASVector) {
 563
 564     // If Cur was already forwarding, just forward to the new AS instead.
 565     AliasSet *FwdTo = Cur->Forward;
 566     if (FwdTo) {
 567       Cur->Forward = AliasAnyAS;
 568       AliasAnyAS->addRef();
 569       FwdTo->dropRef(*this);
 570       continue;
 571     }
 572
 573     // Otherwise, perform the actual merge.
 574     AliasAnyAS->mergeSetIn(*Cur, *this);
 575   }
 576
 577   return *AliasAnyAS;
 578 }
 579
 580 AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size,
 581                                       const AAMDNodes &AAInfo,
 582                                       AliasSet::AccessLattice E) {
 583
 584   AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo);
 585   AS.Access |= E;
 586
 587   if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
 588     // The AST is now saturated. From here on, we conservatively consider all
 589     // pointers to alias each-other.
 590     return mergeAllAliasSets();
 591   }
 592
 593   return AS;
 594 }
 595
 596 //===----------------------------------------------------------------------===//
 597 //               AliasSet/AliasSetTracker Printing Support
 598 //===----------------------------------------------------------------------===//
 599
 600 void AliasSet::print(raw_ostream &OS) const {
 601   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
 602   OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
 603   switch (Access) {
 604   case NoAccess:     OS << "No access "; break;
 605   case RefAccess:    OS << "Ref       "; break;
 606   case ModAccess:    OS << "Mod       "; break;
 607   case ModRefAccess: OS << "Mod/Ref   "; break;
 608   default: llvm_unreachable("Bad value for Access!");
 609   }
 610   if (isVolatile()) OS << "[volatile] ";
 611   if (Forward)
 612     OS << " forwarding to " << (void*)Forward;
 613
 614
 615   if (!empty()) {
 616     OS << "Pointers: ";
 617     for (iterator I = begin(), E = end(); I != E; ++I) {
 618       if (I != begin()) OS << ", ";
 619       I.getPointer()->printAsOperand(OS << "(");
 620       OS << ", " << I.getSize() << ")";
 621     }
 622   }
 623   if (!UnknownInsts.empty()) {
 624     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
 625     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
 626       if (i) OS << ", ";
 627       if (auto *I = getUnknownInst(i))
 628         I->printAsOperand(OS);
 629     }
 630   }
 631   OS << "\n";
 632 }
 633
 634 void AliasSetTracker::print(raw_ostream &OS) const {
 635   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
 636      << PointerMap.size() << " pointer values.\n";
 637   for (const AliasSet &AS : *this)
 638     AS.print(OS);
 639   OS << "\n";
 640 }
 641
 642 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 643 LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
 644 LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
 645 #endif
 646
 647 //===----------------------------------------------------------------------===//
 648 //                     ASTCallbackVH Class Implementation
 649 //===----------------------------------------------------------------------===//
 650
 651 void AliasSetTracker::ASTCallbackVH::deleted() {
 652   assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
 653   AST->deleteValue(getValPtr());
 654   // this now dangles!
 655 }
 656
 657 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
 658   AST->copyValue(getValPtr(), V);
 659 }
 660
 661 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
 662   : CallbackVH(V), AST(ast) {}
 663
 664 AliasSetTracker::ASTCallbackVH &
 665 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
 666   return *this = ASTCallbackVH(V, AST);
 667 }
 668
 669 //===----------------------------------------------------------------------===//
 670 //                            AliasSetPrinter Pass
 671 //===----------------------------------------------------------------------===//
 672
 673 namespace {
 674   class AliasSetPrinter : public FunctionPass {
 675     AliasSetTracker *Tracker;
 676   public:
 677     static char ID; // Pass identification, replacement for typeid
 678     AliasSetPrinter() : FunctionPass(ID) {
 679       initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
 680     }
 681
 682     void getAnalysisUsage(AnalysisUsage &AU) const override {
 683       AU.setPreservesAll();
 684       AU.addRequired<AAResultsWrapperPass>();
 685     }
 686
 687     bool runOnFunction(Function &F) override {
 688       auto &AAWP = getAnalysis<AAResultsWrapperPass>();
 689       Tracker = new AliasSetTracker(AAWP.getAAResults());
 690       errs() << "Alias sets for function '" << F.getName() << "':\n";
 691       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
 692         Tracker->add(&*I);
 693       Tracker->print(errs());
 694       delete Tracker;
 695       return false;
 696     }
 697   };
 698 }
 699
 700 char AliasSetPrinter::ID = 0;
 701 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
 702                 "Alias Set Printer", false, true)
 703 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 704 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
 705                 "Alias Set Printer", false, true)