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