LLVM  mainline
AliasSetTracker.cpp
Go to the documentation of this file.
00001 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the AliasSetTracker and AliasSet classes.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/Analysis/AliasSetTracker.h"
00015 #include "llvm/Analysis/AliasAnalysis.h"
00016 #include "llvm/IR/DataLayout.h"
00017 #include "llvm/IR/InstIterator.h"
00018 #include "llvm/IR/Instructions.h"
00019 #include "llvm/IR/IntrinsicInst.h"
00020 #include "llvm/IR/LLVMContext.h"
00021 #include "llvm/IR/Type.h"
00022 #include "llvm/Pass.h"
00023 #include "llvm/Support/Debug.h"
00024 #include "llvm/Support/ErrorHandling.h"
00025 #include "llvm/Support/raw_ostream.h"
00026 using namespace llvm;
00027 
00028 /// mergeSetIn - Merge the specified alias set into this alias set.
00029 ///
00030 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
00031   assert(!AS.Forward && "Alias set is already forwarding!");
00032   assert(!Forward && "This set is a forwarding set!!");
00033 
00034   // Update the alias and access types of this set...
00035   AccessTy |= AS.AccessTy;
00036   AliasTy  |= AS.AliasTy;
00037   Volatile |= AS.Volatile;
00038 
00039   if (AliasTy == MustAlias) {
00040     // Check that these two merged sets really are must aliases.  Since both
00041     // used to be must-alias sets, we can just check any pointer from each set
00042     // for aliasing.
00043     AliasAnalysis &AA = AST.getAliasAnalysis();
00044     PointerRec *L = getSomePointer();
00045     PointerRec *R = AS.getSomePointer();
00046 
00047     // If the pointers are not a must-alias pair, this set becomes a may alias.
00048     if (AA.alias(AliasAnalysis::Location(L->getValue(),
00049                                          L->getSize(),
00050                                          L->getAAInfo()),
00051                  AliasAnalysis::Location(R->getValue(),
00052                                          R->getSize(),
00053                                          R->getAAInfo()))
00054         != AliasAnalysis::MustAlias)
00055       AliasTy = MayAlias;
00056   }
00057 
00058   bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
00059   if (UnknownInsts.empty()) {            // Merge call sites...
00060     if (ASHadUnknownInsts) {
00061       std::swap(UnknownInsts, AS.UnknownInsts);
00062       addRef();
00063     }
00064   } else if (ASHadUnknownInsts) {
00065     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
00066     AS.UnknownInsts.clear();
00067   }
00068 
00069   AS.Forward = this;  // Forward across AS now...
00070   addRef();           // AS is now pointing to us...
00071 
00072   // Merge the list of constituent pointers...
00073   if (AS.PtrList) {
00074     *PtrListEnd = AS.PtrList;
00075     AS.PtrList->setPrevInList(PtrListEnd);
00076     PtrListEnd = AS.PtrListEnd;
00077 
00078     AS.PtrList = nullptr;
00079     AS.PtrListEnd = &AS.PtrList;
00080     assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
00081   }
00082   if (ASHadUnknownInsts)
00083     AS.dropRef(AST);
00084 }
00085 
00086 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
00087   if (AliasSet *Fwd = AS->Forward) {
00088     Fwd->dropRef(*this);
00089     AS->Forward = nullptr;
00090   }
00091   AliasSets.erase(AS);
00092 }
00093 
00094 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
00095   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
00096   AST.removeAliasSet(this);
00097 }
00098 
00099 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
00100                           uint64_t Size, const AAMDNodes &AAInfo,
00101                           bool KnownMustAlias) {
00102   assert(!Entry.hasAliasSet() && "Entry already in set!");
00103 
00104   // Check to see if we have to downgrade to _may_ alias.
00105   if (isMustAlias() && !KnownMustAlias)
00106     if (PointerRec *P = getSomePointer()) {
00107       AliasAnalysis &AA = AST.getAliasAnalysis();
00108       AliasAnalysis::AliasResult Result =
00109         AA.alias(AliasAnalysis::Location(P->getValue(), P->getSize(),
00110                                          P->getAAInfo()),
00111                  AliasAnalysis::Location(Entry.getValue(), Size, AAInfo));
00112       if (Result != AliasAnalysis::MustAlias)
00113         AliasTy = MayAlias;
00114       else                  // First entry of must alias must have maximum size!
00115         P->updateSizeAndAAInfo(Size, AAInfo);
00116       assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!");
00117     }
00118 
00119   Entry.setAliasSet(this);
00120   Entry.updateSizeAndAAInfo(Size, AAInfo);
00121 
00122   // Add it to the end of the list...
00123   assert(*PtrListEnd == nullptr && "End of list is not null?");
00124   *PtrListEnd = &Entry;
00125   PtrListEnd = Entry.setPrevInList(PtrListEnd);
00126   assert(*PtrListEnd == nullptr && "End of list is not null?");
00127   addRef();               // Entry points to alias set.
00128 }
00129 
00130 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
00131   if (UnknownInsts.empty())
00132     addRef();
00133   UnknownInsts.push_back(I);
00134 
00135   if (!I->mayWriteToMemory()) {
00136     AliasTy = MayAlias;
00137     AccessTy |= Refs;
00138     return;
00139   }
00140 
00141   // FIXME: This should use mod/ref information to make this not suck so bad
00142   AliasTy = MayAlias;
00143   AccessTy = ModRef;
00144 }
00145 
00146 /// aliasesPointer - Return true if the specified pointer "may" (or must)
00147 /// alias one of the members in the set.
00148 ///
00149 bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
00150                               const AAMDNodes &AAInfo,
00151                               AliasAnalysis &AA) const {
00152   if (AliasTy == MustAlias) {
00153     assert(UnknownInsts.empty() && "Illegal must alias set!");
00154 
00155     // If this is a set of MustAliases, only check to see if the pointer aliases
00156     // SOME value in the set.
00157     PointerRec *SomePtr = getSomePointer();
00158     assert(SomePtr && "Empty must-alias set??");
00159     return AA.alias(AliasAnalysis::Location(SomePtr->getValue(),
00160                                             SomePtr->getSize(),
00161                                             SomePtr->getAAInfo()),
00162                     AliasAnalysis::Location(Ptr, Size, AAInfo));
00163   }
00164 
00165   // If this is a may-alias set, we have to check all of the pointers in the set
00166   // to be sure it doesn't alias the set...
00167   for (iterator I = begin(), E = end(); I != E; ++I)
00168     if (AA.alias(AliasAnalysis::Location(Ptr, Size, AAInfo),
00169                  AliasAnalysis::Location(I.getPointer(), I.getSize(),
00170                                          I.getAAInfo())))
00171       return true;
00172 
00173   // Check the unknown instructions...
00174   if (!UnknownInsts.empty()) {
00175     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
00176       if (AA.getModRefInfo(UnknownInsts[i],
00177                            AliasAnalysis::Location(Ptr, Size, AAInfo)) !=
00178             AliasAnalysis::NoModRef)
00179         return true;
00180   }
00181 
00182   return false;
00183 }
00184 
00185 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
00186                                   AliasAnalysis &AA) const {
00187   if (!Inst->mayReadOrWriteMemory())
00188     return false;
00189 
00190   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
00191     ImmutableCallSite C1(getUnknownInst(i)), C2(Inst);
00192     if (!C1 || !C2 ||
00193         AA.getModRefInfo(C1, C2) != AliasAnalysis::NoModRef ||
00194         AA.getModRefInfo(C2, C1) != AliasAnalysis::NoModRef)
00195       return true;
00196   }
00197 
00198   for (iterator I = begin(), E = end(); I != E; ++I)
00199     if (AA.getModRefInfo(Inst, AliasAnalysis::Location(I.getPointer(),
00200                                                        I.getSize(),
00201                                                        I.getAAInfo())) !=
00202            AliasAnalysis::NoModRef)
00203       return true;
00204 
00205   return false;
00206 }
00207 
00208 void AliasSetTracker::clear() {
00209   // Delete all the PointerRec entries.
00210   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
00211        I != E; ++I)
00212     I->second->eraseFromList();
00213   
00214   PointerMap.clear();
00215   
00216   // The alias sets should all be clear now.
00217   AliasSets.clear();
00218 }
00219 
00220 
00221 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
00222 /// instruction referring to the pointer into.  If there are multiple alias sets
00223 /// that may alias the pointer, merge them together and return the unified set.
00224 ///
00225 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
00226                                                   uint64_t Size,
00227                                                   const AAMDNodes &AAInfo) {
00228   AliasSet *FoundSet = nullptr;
00229   for (iterator I = begin(), E = end(); I != E;) {
00230     iterator Cur = I++;
00231     if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
00232     
00233     if (!FoundSet) {      // If this is the first alias set ptr can go into.
00234       FoundSet = Cur;     // Remember it.
00235     } else {              // Otherwise, we must merge the sets.
00236       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
00237     }
00238   }
00239 
00240   return FoundSet;
00241 }
00242 
00243 /// containsPointer - Return true if the specified location is represented by
00244 /// this alias set, false otherwise.  This does not modify the AST object or
00245 /// alias sets.
00246 bool AliasSetTracker::containsPointer(const Value *Ptr, uint64_t Size,
00247                                       const AAMDNodes &AAInfo) const {
00248   for (const_iterator I = begin(), E = end(); I != E; ++I)
00249     if (!I->Forward && I->aliasesPointer(Ptr, Size, AAInfo, AA))
00250       return true;
00251   return false;
00252 }
00253 
00254 bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
00255   for (const_iterator I = begin(), E = end(); I != E; ++I)
00256     if (!I->Forward && I->aliasesUnknownInst(Inst, AA))
00257       return true;
00258   return false;
00259 }
00260 
00261 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
00262   AliasSet *FoundSet = nullptr;
00263   for (iterator I = begin(), E = end(); I != E;) {
00264     iterator Cur = I++;
00265     if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
00266       continue;
00267     if (!FoundSet)            // If this is the first alias set ptr can go into.
00268       FoundSet = Cur;         // Remember it.
00269     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
00270       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
00271   }
00272   return FoundSet;
00273 }
00274 
00275 
00276 
00277 
00278 /// getAliasSetForPointer - Return the alias set that the specified pointer
00279 /// lives in.
00280 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
00281                                                  const AAMDNodes &AAInfo,
00282                                                  bool *New) {
00283   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
00284 
00285   // Check to see if the pointer is already known.
00286   if (Entry.hasAliasSet()) {
00287     Entry.updateSizeAndAAInfo(Size, AAInfo);
00288     // Return the set!
00289     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
00290   }
00291   
00292   if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo)) {
00293     // Add it to the alias set it aliases.
00294     AS->addPointer(*this, Entry, Size, AAInfo);
00295     return *AS;
00296   }
00297   
00298   if (New) *New = true;
00299   // Otherwise create a new alias set to hold the loaded pointer.
00300   AliasSets.push_back(new AliasSet());
00301   AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
00302   return AliasSets.back();
00303 }
00304 
00305 bool AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
00306   bool NewPtr;
00307   addPointer(Ptr, Size, AAInfo, AliasSet::NoModRef, NewPtr);
00308   return NewPtr;
00309 }
00310 
00311 
00312 bool AliasSetTracker::add(LoadInst *LI) {
00313   if (LI->getOrdering() > Monotonic) return addUnknown(LI);
00314 
00315   AAMDNodes AAInfo;
00316   LI->getAAMetadata(AAInfo);
00317 
00318   AliasSet::AccessType ATy = AliasSet::Refs;
00319   bool NewPtr;
00320   AliasSet &AS = addPointer(LI->getOperand(0),
00321                             AA.getTypeStoreSize(LI->getType()),
00322                             AAInfo, ATy, NewPtr);
00323   if (LI->isVolatile()) AS.setVolatile();
00324   return NewPtr;
00325 }
00326 
00327 bool AliasSetTracker::add(StoreInst *SI) {
00328   if (SI->getOrdering() > Monotonic) return addUnknown(SI);
00329 
00330   AAMDNodes AAInfo;
00331   SI->getAAMetadata(AAInfo);
00332 
00333   AliasSet::AccessType ATy = AliasSet::Mods;
00334   bool NewPtr;
00335   Value *Val = SI->getOperand(0);
00336   AliasSet &AS = addPointer(SI->getOperand(1),
00337                             AA.getTypeStoreSize(Val->getType()),
00338                             AAInfo, ATy, NewPtr);
00339   if (SI->isVolatile()) AS.setVolatile();
00340   return NewPtr;
00341 }
00342 
00343 bool AliasSetTracker::add(VAArgInst *VAAI) {
00344   AAMDNodes AAInfo;
00345   VAAI->getAAMetadata(AAInfo);
00346 
00347   bool NewPtr;
00348   addPointer(VAAI->getOperand(0), AliasAnalysis::UnknownSize, 
00349              AAInfo, AliasSet::ModRef, NewPtr);
00350   return NewPtr;
00351 }
00352 
00353 
00354 bool AliasSetTracker::addUnknown(Instruction *Inst) {
00355   if (isa<DbgInfoIntrinsic>(Inst)) 
00356     return true; // Ignore DbgInfo Intrinsics.
00357   if (!Inst->mayReadOrWriteMemory())
00358     return true; // doesn't alias anything
00359 
00360   AliasSet *AS = findAliasSetForUnknownInst(Inst);
00361   if (AS) {
00362     AS->addUnknownInst(Inst, AA);
00363     return false;
00364   }
00365   AliasSets.push_back(new AliasSet());
00366   AS = &AliasSets.back();
00367   AS->addUnknownInst(Inst, AA);
00368   return true;
00369 }
00370 
00371 bool AliasSetTracker::add(Instruction *I) {
00372   // Dispatch to one of the other add methods.
00373   if (LoadInst *LI = dyn_cast<LoadInst>(I))
00374     return add(LI);
00375   if (StoreInst *SI = dyn_cast<StoreInst>(I))
00376     return add(SI);
00377   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
00378     return add(VAAI);
00379   return addUnknown(I);
00380 }
00381 
00382 void AliasSetTracker::add(BasicBlock &BB) {
00383   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
00384     add(I);
00385 }
00386 
00387 void AliasSetTracker::add(const AliasSetTracker &AST) {
00388   assert(&AA == &AST.AA &&
00389          "Merging AliasSetTracker objects with different Alias Analyses!");
00390 
00391   // Loop over all of the alias sets in AST, adding the pointers contained
00392   // therein into the current alias sets.  This can cause alias sets to be
00393   // merged together in the current AST.
00394   for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) {
00395     if (I->Forward) continue;   // Ignore forwarding alias sets
00396     
00397     AliasSet &AS = const_cast<AliasSet&>(*I);
00398 
00399     // If there are any call sites in the alias set, add them to this AST.
00400     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
00401       add(AS.UnknownInsts[i]);
00402 
00403     // Loop over all of the pointers in this alias set.
00404     bool X;
00405     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
00406       AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(),
00407                                    ASI.getAAInfo(),
00408                                    (AliasSet::AccessType)AS.AccessTy, X);
00409       if (AS.isVolatile()) NewAS.setVolatile();
00410     }
00411   }
00412 }
00413 
00414 /// remove - Remove the specified (potentially non-empty) alias set from the
00415 /// tracker.
00416 void AliasSetTracker::remove(AliasSet &AS) {
00417   // Drop all call sites.
00418   if (!AS.UnknownInsts.empty())
00419     AS.dropRef(*this);
00420   AS.UnknownInsts.clear();
00421   
00422   // Clear the alias set.
00423   unsigned NumRefs = 0;
00424   while (!AS.empty()) {
00425     AliasSet::PointerRec *P = AS.PtrList;
00426 
00427     Value *ValToRemove = P->getValue();
00428     
00429     // Unlink and delete entry from the list of values.
00430     P->eraseFromList();
00431     
00432     // Remember how many references need to be dropped.
00433     ++NumRefs;
00434 
00435     // Finally, remove the entry.
00436     PointerMap.erase(ValToRemove);
00437   }
00438   
00439   // Stop using the alias set, removing it.
00440   AS.RefCount -= NumRefs;
00441   if (AS.RefCount == 0)
00442     AS.removeFromTracker(*this);
00443 }
00444 
00445 bool
00446 AliasSetTracker::remove(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
00447   AliasSet *AS = findAliasSetForPointer(Ptr, Size, AAInfo);
00448   if (!AS) return false;
00449   remove(*AS);
00450   return true;
00451 }
00452 
00453 bool AliasSetTracker::remove(LoadInst *LI) {
00454   uint64_t Size = AA.getTypeStoreSize(LI->getType());
00455 
00456   AAMDNodes AAInfo;
00457   LI->getAAMetadata(AAInfo);
00458 
00459   AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size, AAInfo);
00460   if (!AS) return false;
00461   remove(*AS);
00462   return true;
00463 }
00464 
00465 bool AliasSetTracker::remove(StoreInst *SI) {
00466   uint64_t Size = AA.getTypeStoreSize(SI->getOperand(0)->getType());
00467 
00468   AAMDNodes AAInfo;
00469   SI->getAAMetadata(AAInfo);
00470 
00471   AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size, AAInfo);
00472   if (!AS) return false;
00473   remove(*AS);
00474   return true;
00475 }
00476 
00477 bool AliasSetTracker::remove(VAArgInst *VAAI) {
00478   AAMDNodes AAInfo;
00479   VAAI->getAAMetadata(AAInfo);
00480 
00481   AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0),
00482                                         AliasAnalysis::UnknownSize, AAInfo);
00483   if (!AS) return false;
00484   remove(*AS);
00485   return true;
00486 }
00487 
00488 bool AliasSetTracker::removeUnknown(Instruction *I) {
00489   if (!I->mayReadOrWriteMemory())
00490     return false; // doesn't alias anything
00491 
00492   AliasSet *AS = findAliasSetForUnknownInst(I);
00493   if (!AS) return false;
00494   remove(*AS);
00495   return true;
00496 }
00497 
00498 bool AliasSetTracker::remove(Instruction *I) {
00499   // Dispatch to one of the other remove methods...
00500   if (LoadInst *LI = dyn_cast<LoadInst>(I))
00501     return remove(LI);
00502   if (StoreInst *SI = dyn_cast<StoreInst>(I))
00503     return remove(SI);
00504   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
00505     return remove(VAAI);
00506   return removeUnknown(I);
00507 }
00508 
00509 
00510 // deleteValue method - This method is used to remove a pointer value from the
00511 // AliasSetTracker entirely.  It should be used when an instruction is deleted
00512 // from the program to update the AST.  If you don't use this, you would have
00513 // dangling pointers to deleted instructions.
00514 //
00515 void AliasSetTracker::deleteValue(Value *PtrVal) {
00516   // Notify the alias analysis implementation that this value is gone.
00517   AA.deleteValue(PtrVal);
00518 
00519   // If this is a call instruction, remove the callsite from the appropriate
00520   // AliasSet (if present).
00521   if (Instruction *Inst = dyn_cast<Instruction>(PtrVal)) {
00522     if (Inst->mayReadOrWriteMemory()) {
00523       // Scan all the alias sets to see if this call site is contained.
00524       for (iterator I = begin(), E = end(); I != E;) {
00525         iterator Cur = I++;
00526         if (!Cur->Forward)
00527           Cur->removeUnknownInst(*this, Inst);
00528       }
00529     }
00530   }
00531 
00532   // First, look up the PointerRec for this pointer.
00533   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
00534   if (I == PointerMap.end()) return;  // Noop
00535 
00536   // If we found one, remove the pointer from the alias set it is in.
00537   AliasSet::PointerRec *PtrValEnt = I->second;
00538   AliasSet *AS = PtrValEnt->getAliasSet(*this);
00539 
00540   // Unlink and delete from the list of values.
00541   PtrValEnt->eraseFromList();
00542   
00543   // Stop using the alias set.
00544   AS->dropRef(*this);
00545   
00546   PointerMap.erase(I);
00547 }
00548 
00549 // copyValue - This method should be used whenever a preexisting value in the
00550 // program is copied or cloned, introducing a new value.  Note that it is ok for
00551 // clients that use this method to introduce the same value multiple times: if
00552 // the tracker already knows about a value, it will ignore the request.
00553 //
00554 void AliasSetTracker::copyValue(Value *From, Value *To) {
00555   // Notify the alias analysis implementation that this value is copied.
00556   AA.copyValue(From, To);
00557 
00558   // First, look up the PointerRec for this pointer.
00559   PointerMapType::iterator I = PointerMap.find_as(From);
00560   if (I == PointerMap.end())
00561     return;  // Noop
00562   assert(I->second->hasAliasSet() && "Dead entry?");
00563 
00564   AliasSet::PointerRec &Entry = getEntryFor(To);
00565   if (Entry.hasAliasSet()) return;    // Already in the tracker!
00566 
00567   // Add it to the alias set it aliases...
00568   I = PointerMap.find_as(From);
00569   AliasSet *AS = I->second->getAliasSet(*this);
00570   AS->addPointer(*this, Entry, I->second->getSize(),
00571                  I->second->getAAInfo(),
00572                  true);
00573 }
00574 
00575 
00576 
00577 //===----------------------------------------------------------------------===//
00578 //               AliasSet/AliasSetTracker Printing Support
00579 //===----------------------------------------------------------------------===//
00580 
00581 void AliasSet::print(raw_ostream &OS) const {
00582   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
00583   OS << (AliasTy == MustAlias ? "must" : "may") << " alias, ";
00584   switch (AccessTy) {
00585   case NoModRef: OS << "No access "; break;
00586   case Refs    : OS << "Ref       "; break;
00587   case Mods    : OS << "Mod       "; break;
00588   case ModRef  : OS << "Mod/Ref   "; break;
00589   default: llvm_unreachable("Bad value for AccessTy!");
00590   }
00591   if (isVolatile()) OS << "[volatile] ";
00592   if (Forward)
00593     OS << " forwarding to " << (void*)Forward;
00594 
00595 
00596   if (!empty()) {
00597     OS << "Pointers: ";
00598     for (iterator I = begin(), E = end(); I != E; ++I) {
00599       if (I != begin()) OS << ", ";
00600       I.getPointer()->printAsOperand(OS << "(");
00601       OS << ", " << I.getSize() << ")";
00602     }
00603   }
00604   if (!UnknownInsts.empty()) {
00605     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
00606     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
00607       if (i) OS << ", ";
00608       UnknownInsts[i]->printAsOperand(OS);
00609     }
00610   }
00611   OS << "\n";
00612 }
00613 
00614 void AliasSetTracker::print(raw_ostream &OS) const {
00615   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
00616      << PointerMap.size() << " pointer values.\n";
00617   for (const_iterator I = begin(), E = end(); I != E; ++I)
00618     I->print(OS);
00619   OS << "\n";
00620 }
00621 
00622 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00623 void AliasSet::dump() const { print(dbgs()); }
00624 void AliasSetTracker::dump() const { print(dbgs()); }
00625 #endif
00626 
00627 //===----------------------------------------------------------------------===//
00628 //                     ASTCallbackVH Class Implementation
00629 //===----------------------------------------------------------------------===//
00630 
00631 void AliasSetTracker::ASTCallbackVH::deleted() {
00632   assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
00633   AST->deleteValue(getValPtr());
00634   // this now dangles!
00635 }
00636 
00637 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
00638   AST->copyValue(getValPtr(), V);
00639 }
00640 
00641 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
00642   : CallbackVH(V), AST(ast) {}
00643 
00644 AliasSetTracker::ASTCallbackVH &
00645 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
00646   return *this = ASTCallbackVH(V, AST);
00647 }
00648 
00649 //===----------------------------------------------------------------------===//
00650 //                            AliasSetPrinter Pass
00651 //===----------------------------------------------------------------------===//
00652 
00653 namespace {
00654   class AliasSetPrinter : public FunctionPass {
00655     AliasSetTracker *Tracker;
00656   public:
00657     static char ID; // Pass identification, replacement for typeid
00658     AliasSetPrinter() : FunctionPass(ID) {
00659       initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
00660     }
00661 
00662     void getAnalysisUsage(AnalysisUsage &AU) const override {
00663       AU.setPreservesAll();
00664       AU.addRequired<AliasAnalysis>();
00665     }
00666 
00667     bool runOnFunction(Function &F) override {
00668       Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
00669 
00670       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
00671         Tracker->add(&*I);
00672       Tracker->print(errs());
00673       delete Tracker;
00674       return false;
00675     }
00676   };
00677 }
00678 
00679 char AliasSetPrinter::ID = 0;
00680 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
00681                 "Alias Set Printer", false, true)
00682 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00683 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
00684                 "Alias Set Printer", false, true)