LLVM API Documentation

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