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