Home | History | Annotate | Download | only in Analysis
      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/Assembly/Writer.h"
     17 #include "llvm/IR/DataLayout.h"
     18 #include "llvm/IR/Instructions.h"
     19 #include "llvm/IR/IntrinsicInst.h"
     20 #include "llvm/IR/LLVMContext.h"
     21 #include "llvm/IR/Type.h"
     22 #include "llvm/Pass.h"
     23 #include "llvm/Support/Debug.h"
     24 #include "llvm/Support/ErrorHandling.h"
     25 #include "llvm/Support/InstIterator.h"
     26 #include "llvm/Support/raw_ostream.h"
     27 using namespace llvm;
     28 
     29 /// mergeSetIn - Merge the specified alias set into this alias set.
     30 ///
     31 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
     32   assert(!AS.Forward && "Alias set is already forwarding!");
     33   assert(!Forward && "This set is a forwarding set!!");
     34 
     35   // Update the alias and access types of this set...
     36   AccessTy |= AS.AccessTy;
     37   AliasTy  |= AS.AliasTy;
     38   Volatile |= AS.Volatile;
     39 
     40   if (AliasTy == MustAlias) {
     41     // Check that these two merged sets really are must aliases.  Since both
     42     // used to be must-alias sets, we can just check any pointer from each set
     43     // for aliasing.
     44     AliasAnalysis &AA = AST.getAliasAnalysis();
     45     PointerRec *L = getSomePointer();
     46     PointerRec *R = AS.getSomePointer();
     47 
     48     // If the pointers are not a must-alias pair, this set becomes a may alias.
     49     if (AA.alias(AliasAnalysis::Location(L->getValue(),
     50                                          L->getSize(),
     51                                          L->getTBAAInfo()),
     52                  AliasAnalysis::Location(R->getValue(),
     53                                          R->getSize(),
     54                                          R->getTBAAInfo()))
     55         != AliasAnalysis::MustAlias)
     56       AliasTy = MayAlias;
     57   }
     58 
     59   if (UnknownInsts.empty()) {            // Merge call sites...
     60     if (!AS.UnknownInsts.empty())
     61       std::swap(UnknownInsts, AS.UnknownInsts);
     62   } else if (!AS.UnknownInsts.empty()) {
     63     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
     64     AS.UnknownInsts.clear();
     65   }
     66 
     67   AS.Forward = this;  // Forward across AS now...
     68   addRef();           // AS is now pointing to us...
     69 
     70   // Merge the list of constituent pointers...
     71   if (AS.PtrList) {
     72     *PtrListEnd = AS.PtrList;
     73     AS.PtrList->setPrevInList(PtrListEnd);
     74     PtrListEnd = AS.PtrListEnd;
     75 
     76     AS.PtrList = 0;
     77     AS.PtrListEnd = &AS.PtrList;
     78     assert(*AS.PtrListEnd == 0 && "End of list is not null?");
     79   }
     80 }
     81 
     82 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
     83   if (AliasSet *Fwd = AS->Forward) {
     84     Fwd->dropRef(*this);
     85     AS->Forward = 0;
     86   }
     87   AliasSets.erase(AS);
     88 }
     89 
     90 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
     91   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
     92   AST.removeAliasSet(this);
     93 }
     94 
     95 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
     96                           uint64_t Size, const MDNode *TBAAInfo,
     97                           bool KnownMustAlias) {
     98   assert(!Entry.hasAliasSet() && "Entry already in set!");
     99 
    100   // Check to see if we have to downgrade to _may_ alias.
    101   if (isMustAlias() && !KnownMustAlias)
    102     if (PointerRec *P = getSomePointer()) {
    103       AliasAnalysis &AA = AST.getAliasAnalysis();
    104       AliasAnalysis::AliasResult Result =
    105         AA.alias(AliasAnalysis::Location(P->getValue(), P->getSize(),
    106                                          P->getTBAAInfo()),
    107                  AliasAnalysis::Location(Entry.getValue(), Size, TBAAInfo));
    108       if (Result != AliasAnalysis::MustAlias)
    109         AliasTy = MayAlias;
    110       else                  // First entry of must alias must have maximum size!
    111         P->updateSizeAndTBAAInfo(Size, TBAAInfo);
    112       assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!");
    113     }
    114 
    115   Entry.setAliasSet(this);
    116   Entry.updateSizeAndTBAAInfo(Size, TBAAInfo);
    117 
    118   // Add it to the end of the list...
    119   assert(*PtrListEnd == 0 && "End of list is not null?");
    120   *PtrListEnd = &Entry;
    121   PtrListEnd = Entry.setPrevInList(PtrListEnd);
    122   assert(*PtrListEnd == 0 && "End of list is not null?");
    123   addRef();               // Entry points to alias set.
    124 }
    125 
    126 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
    127   UnknownInsts.push_back(I);
    128 
    129   if (!I->mayWriteToMemory()) {
    130     AliasTy = MayAlias;
    131     AccessTy |= Refs;
    132     return;
    133   }
    134 
    135   // FIXME: This should use mod/ref information to make this not suck so bad
    136   AliasTy = MayAlias;
    137   AccessTy = ModRef;
    138 }
    139 
    140 /// aliasesPointer - Return true if the specified pointer "may" (or must)
    141 /// alias one of the members in the set.
    142 ///
    143 bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
    144                               const MDNode *TBAAInfo,
    145                               AliasAnalysis &AA) const {
    146   if (AliasTy == MustAlias) {
    147     assert(UnknownInsts.empty() && "Illegal must alias set!");
    148 
    149     // If this is a set of MustAliases, only check to see if the pointer aliases
    150     // SOME value in the set.
    151     PointerRec *SomePtr = getSomePointer();
    152     assert(SomePtr && "Empty must-alias set??");
    153     return AA.alias(AliasAnalysis::Location(SomePtr->getValue(),
    154                                             SomePtr->getSize(),
    155                                             SomePtr->getTBAAInfo()),
    156                     AliasAnalysis::Location(Ptr, Size, TBAAInfo));
    157   }
    158 
    159   // If this is a may-alias set, we have to check all of the pointers in the set
    160   // to be sure it doesn't alias the set...
    161   for (iterator I = begin(), E = end(); I != E; ++I)
    162     if (AA.alias(AliasAnalysis::Location(Ptr, Size, TBAAInfo),
    163                  AliasAnalysis::Location(I.getPointer(), I.getSize(),
    164                                          I.getTBAAInfo())))
    165       return true;
    166 
    167   // Check the unknown instructions...
    168   if (!UnknownInsts.empty()) {
    169     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
    170       if (AA.getModRefInfo(UnknownInsts[i],
    171                            AliasAnalysis::Location(Ptr, Size, TBAAInfo)) !=
    172             AliasAnalysis::NoModRef)
    173         return true;
    174   }
    175 
    176   return false;
    177 }
    178 
    179 bool AliasSet::aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const {
    180   if (!Inst->mayReadOrWriteMemory())
    181     return false;
    182 
    183   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
    184     CallSite C1 = getUnknownInst(i), C2 = Inst;
    185     if (!C1 || !C2 ||
    186         AA.getModRefInfo(C1, C2) != AliasAnalysis::NoModRef ||
    187         AA.getModRefInfo(C2, C1) != AliasAnalysis::NoModRef)
    188       return true;
    189   }
    190 
    191   for (iterator I = begin(), E = end(); I != E; ++I)
    192     if (AA.getModRefInfo(Inst, AliasAnalysis::Location(I.getPointer(),
    193                                                        I.getSize(),
    194                                                        I.getTBAAInfo())) !=
    195            AliasAnalysis::NoModRef)
    196       return true;
    197 
    198   return false;
    199 }
    200 
    201 void AliasSetTracker::clear() {
    202   // Delete all the PointerRec entries.
    203   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
    204        I != E; ++I)
    205     I->second->eraseFromList();
    206 
    207   PointerMap.clear();
    208 
    209   // The alias sets should all be clear now.
    210   AliasSets.clear();
    211 }
    212 
    213 
    214 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
    215 /// instruction referring to the pointer into.  If there are multiple alias sets
    216 /// that may alias the pointer, merge them together and return the unified set.
    217 ///
    218 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
    219                                                   uint64_t Size,
    220                                                   const MDNode *TBAAInfo) {
    221   AliasSet *FoundSet = 0;
    222   for (iterator I = begin(), E = end(); I != E; ++I) {
    223     if (I->Forward || !I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) continue;
    224 
    225     if (FoundSet == 0) {  // If this is the first alias set ptr can go into.
    226       FoundSet = I;       // Remember it.
    227     } else {              // Otherwise, we must merge the sets.
    228       FoundSet->mergeSetIn(*I, *this);     // Merge in contents.
    229     }
    230   }
    231 
    232   return FoundSet;
    233 }
    234 
    235 /// containsPointer - Return true if the specified location is represented by
    236 /// this alias set, false otherwise.  This does not modify the AST object or
    237 /// alias sets.
    238 bool AliasSetTracker::containsPointer(Value *Ptr, uint64_t Size,
    239                                       const MDNode *TBAAInfo) const {
    240   for (const_iterator I = begin(), E = end(); I != E; ++I)
    241     if (!I->Forward && I->aliasesPointer(Ptr, Size, TBAAInfo, AA))
    242       return true;
    243   return false;
    244 }
    245 
    246 
    247 
    248 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
    249   AliasSet *FoundSet = 0;
    250   for (iterator I = begin(), E = end(); I != E; ++I) {
    251     if (I->Forward || !I->aliasesUnknownInst(Inst, AA))
    252       continue;
    253 
    254     if (FoundSet == 0)        // If this is the first alias set ptr can go into.
    255       FoundSet = I;           // Remember it.
    256     else if (!I->Forward)     // Otherwise, we must merge the sets.
    257       FoundSet->mergeSetIn(*I, *this);     // Merge in contents.
    258   }
    259   return FoundSet;
    260 }
    261 
    262 
    263 
    264 
    265 /// getAliasSetForPointer - Return the alias set that the specified pointer
    266 /// lives in.
    267 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
    268                                                  const MDNode *TBAAInfo,
    269                                                  bool *New) {
    270   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
    271 
    272   // Check to see if the pointer is already known.
    273   if (Entry.hasAliasSet()) {
    274     Entry.updateSizeAndTBAAInfo(Size, TBAAInfo);
    275     // Return the set!
    276     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
    277   }
    278 
    279   if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, TBAAInfo)) {
    280     // Add it to the alias set it aliases.
    281     AS->addPointer(*this, Entry, Size, TBAAInfo);
    282     return *AS;
    283   }
    284 
    285   if (New) *New = true;
    286   // Otherwise create a new alias set to hold the loaded pointer.
    287   AliasSets.push_back(new AliasSet());
    288   AliasSets.back().addPointer(*this, Entry, Size, TBAAInfo);
    289   return AliasSets.back();
    290 }
    291 
    292 bool AliasSetTracker::add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) {
    293   bool NewPtr;
    294   addPointer(Ptr, Size, TBAAInfo, AliasSet::NoModRef, NewPtr);
    295   return NewPtr;
    296 }
    297 
    298 
    299 bool AliasSetTracker::add(LoadInst *LI) {
    300   if (LI->getOrdering() > Monotonic) return addUnknown(LI);
    301   AliasSet::AccessType ATy = AliasSet::Refs;
    302   if (!LI->isUnordered()) ATy = AliasSet::ModRef;
    303   bool NewPtr;
    304   AliasSet &AS = addPointer(LI->getOperand(0),
    305                             AA.getTypeStoreSize(LI->getType()),
    306                             LI->getMetadata(LLVMContext::MD_tbaa),
    307                             ATy, NewPtr);
    308   if (LI->isVolatile()) AS.setVolatile();
    309   return NewPtr;
    310 }
    311 
    312 bool AliasSetTracker::add(StoreInst *SI) {
    313   if (SI->getOrdering() > Monotonic) return addUnknown(SI);
    314   AliasSet::AccessType ATy = AliasSet::Mods;
    315   if (!SI->isUnordered()) ATy = AliasSet::ModRef;
    316   bool NewPtr;
    317   Value *Val = SI->getOperand(0);
    318   AliasSet &AS = addPointer(SI->getOperand(1),
    319                             AA.getTypeStoreSize(Val->getType()),
    320                             SI->getMetadata(LLVMContext::MD_tbaa),
    321                             ATy, NewPtr);
    322   if (SI->isVolatile()) AS.setVolatile();
    323   return NewPtr;
    324 }
    325 
    326 bool AliasSetTracker::add(VAArgInst *VAAI) {
    327   bool NewPtr;
    328   addPointer(VAAI->getOperand(0), AliasAnalysis::UnknownSize,
    329              VAAI->getMetadata(LLVMContext::MD_tbaa),
    330              AliasSet::ModRef, NewPtr);
    331   return NewPtr;
    332 }
    333 
    334 
    335 bool AliasSetTracker::addUnknown(Instruction *Inst) {
    336   if (isa<DbgInfoIntrinsic>(Inst))
    337     return true; // Ignore DbgInfo Intrinsics.
    338   if (!Inst->mayReadOrWriteMemory())
    339     return true; // doesn't alias anything
    340 
    341   AliasSet *AS = findAliasSetForUnknownInst(Inst);
    342   if (AS) {
    343     AS->addUnknownInst(Inst, AA);
    344     return false;
    345   }
    346   AliasSets.push_back(new AliasSet());
    347   AS = &AliasSets.back();
    348   AS->addUnknownInst(Inst, AA);
    349   return true;
    350 }
    351 
    352 bool AliasSetTracker::add(Instruction *I) {
    353   // Dispatch to one of the other add methods.
    354   if (LoadInst *LI = dyn_cast<LoadInst>(I))
    355     return add(LI);
    356   if (StoreInst *SI = dyn_cast<StoreInst>(I))
    357     return add(SI);
    358   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
    359     return add(VAAI);
    360   return addUnknown(I);
    361 }
    362 
    363 void AliasSetTracker::add(BasicBlock &BB) {
    364   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
    365     add(I);
    366 }
    367 
    368 void AliasSetTracker::add(const AliasSetTracker &AST) {
    369   assert(&AA == &AST.AA &&
    370          "Merging AliasSetTracker objects with different Alias Analyses!");
    371 
    372   // Loop over all of the alias sets in AST, adding the pointers contained
    373   // therein into the current alias sets.  This can cause alias sets to be
    374   // merged together in the current AST.
    375   for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) {
    376     if (I->Forward) continue;   // Ignore forwarding alias sets
    377 
    378     AliasSet &AS = const_cast<AliasSet&>(*I);
    379 
    380     // If there are any call sites in the alias set, add them to this AST.
    381     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
    382       add(AS.UnknownInsts[i]);
    383 
    384     // Loop over all of the pointers in this alias set.
    385     bool X;
    386     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
    387       AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(),
    388                                    ASI.getTBAAInfo(),
    389                                    (AliasSet::AccessType)AS.AccessTy, X);
    390       if (AS.isVolatile()) NewAS.setVolatile();
    391     }
    392   }
    393 }
    394 
    395 /// remove - Remove the specified (potentially non-empty) alias set from the
    396 /// tracker.
    397 void AliasSetTracker::remove(AliasSet &AS) {
    398   // Drop all call sites.
    399   AS.UnknownInsts.clear();
    400 
    401   // Clear the alias set.
    402   unsigned NumRefs = 0;
    403   while (!AS.empty()) {
    404     AliasSet::PointerRec *P = AS.PtrList;
    405 
    406     Value *ValToRemove = P->getValue();
    407 
    408     // Unlink and delete entry from the list of values.
    409     P->eraseFromList();
    410 
    411     // Remember how many references need to be dropped.
    412     ++NumRefs;
    413 
    414     // Finally, remove the entry.
    415     PointerMap.erase(ValToRemove);
    416   }
    417 
    418   // Stop using the alias set, removing it.
    419   AS.RefCount -= NumRefs;
    420   if (AS.RefCount == 0)
    421     AS.removeFromTracker(*this);
    422 }
    423 
    424 bool
    425 AliasSetTracker::remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) {
    426   AliasSet *AS = findAliasSetForPointer(Ptr, Size, TBAAInfo);
    427   if (!AS) return false;
    428   remove(*AS);
    429   return true;
    430 }
    431 
    432 bool AliasSetTracker::remove(LoadInst *LI) {
    433   uint64_t Size = AA.getTypeStoreSize(LI->getType());
    434   const MDNode *TBAAInfo = LI->getMetadata(LLVMContext::MD_tbaa);
    435   AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size, TBAAInfo);
    436   if (!AS) return false;
    437   remove(*AS);
    438   return true;
    439 }
    440 
    441 bool AliasSetTracker::remove(StoreInst *SI) {
    442   uint64_t Size = AA.getTypeStoreSize(SI->getOperand(0)->getType());
    443   const MDNode *TBAAInfo = SI->getMetadata(LLVMContext::MD_tbaa);
    444   AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size, TBAAInfo);
    445   if (!AS) return false;
    446   remove(*AS);
    447   return true;
    448 }
    449 
    450 bool AliasSetTracker::remove(VAArgInst *VAAI) {
    451   AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0),
    452                                         AliasAnalysis::UnknownSize,
    453                                         VAAI->getMetadata(LLVMContext::MD_tbaa));
    454   if (!AS) return false;
    455   remove(*AS);
    456   return true;
    457 }
    458 
    459 bool AliasSetTracker::removeUnknown(Instruction *I) {
    460   if (!I->mayReadOrWriteMemory())
    461     return false; // doesn't alias anything
    462 
    463   AliasSet *AS = findAliasSetForUnknownInst(I);
    464   if (!AS) return false;
    465   remove(*AS);
    466   return true;
    467 }
    468 
    469 bool AliasSetTracker::remove(Instruction *I) {
    470   // Dispatch to one of the other remove methods...
    471   if (LoadInst *LI = dyn_cast<LoadInst>(I))
    472     return remove(LI);
    473   if (StoreInst *SI = dyn_cast<StoreInst>(I))
    474     return remove(SI);
    475   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
    476     return remove(VAAI);
    477   return removeUnknown(I);
    478 }
    479 
    480 
    481 // deleteValue method - This method is used to remove a pointer value from the
    482 // AliasSetTracker entirely.  It should be used when an instruction is deleted
    483 // from the program to update the AST.  If you don't use this, you would have
    484 // dangling pointers to deleted instructions.
    485 //
    486 void AliasSetTracker::deleteValue(Value *PtrVal) {
    487   // Notify the alias analysis implementation that this value is gone.
    488   AA.deleteValue(PtrVal);
    489 
    490   // If this is a call instruction, remove the callsite from the appropriate
    491   // AliasSet (if present).
    492   if (Instruction *Inst = dyn_cast<Instruction>(PtrVal)) {
    493     if (Inst->mayReadOrWriteMemory()) {
    494       // Scan all the alias sets to see if this call site is contained.
    495       for (iterator I = begin(), E = end(); I != E; ++I) {
    496         if (I->Forward) continue;
    497 
    498         I->removeUnknownInst(Inst);
    499       }
    500     }
    501   }
    502 
    503   // First, look up the PointerRec for this pointer.
    504   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
    505   if (I == PointerMap.end()) return;  // Noop
    506 
    507   // If we found one, remove the pointer from the alias set it is in.
    508   AliasSet::PointerRec *PtrValEnt = I->second;
    509   AliasSet *AS = PtrValEnt->getAliasSet(*this);
    510 
    511   // Unlink and delete from the list of values.
    512   PtrValEnt->eraseFromList();
    513 
    514   // Stop using the alias set.
    515   AS->dropRef(*this);
    516 
    517   PointerMap.erase(I);
    518 }
    519 
    520 // copyValue - This method should be used whenever a preexisting value in the
    521 // program is copied or cloned, introducing a new value.  Note that it is ok for
    522 // clients that use this method to introduce the same value multiple times: if
    523 // the tracker already knows about a value, it will ignore the request.
    524 //
    525 void AliasSetTracker::copyValue(Value *From, Value *To) {
    526   // Notify the alias analysis implementation that this value is copied.
    527   AA.copyValue(From, To);
    528 
    529   // First, look up the PointerRec for this pointer.
    530   PointerMapType::iterator I = PointerMap.find_as(From);
    531   if (I == PointerMap.end())
    532     return;  // Noop
    533   assert(I->second->hasAliasSet() && "Dead entry?");
    534 
    535   AliasSet::PointerRec &Entry = getEntryFor(To);
    536   if (Entry.hasAliasSet()) return;    // Already in the tracker!
    537 
    538   // Add it to the alias set it aliases...
    539   I = PointerMap.find_as(From);
    540   AliasSet *AS = I->second->getAliasSet(*this);
    541   AS->addPointer(*this, Entry, I->second->getSize(),
    542                  I->second->getTBAAInfo(),
    543                  true);
    544 }
    545 
    546 
    547 
    548 //===----------------------------------------------------------------------===//
    549 //               AliasSet/AliasSetTracker Printing Support
    550 //===----------------------------------------------------------------------===//
    551 
    552 void AliasSet::print(raw_ostream &OS) const {
    553   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
    554   OS << (AliasTy == MustAlias ? "must" : "may") << " alias, ";
    555   switch (AccessTy) {
    556   case NoModRef: OS << "No access "; break;
    557   case Refs    : OS << "Ref       "; break;
    558   case Mods    : OS << "Mod       "; break;
    559   case ModRef  : OS << "Mod/Ref   "; break;
    560   default: llvm_unreachable("Bad value for AccessTy!");
    561   }
    562   if (isVolatile()) OS << "[volatile] ";
    563   if (Forward)
    564     OS << " forwarding to " << (void*)Forward;
    565 
    566 
    567   if (!empty()) {
    568     OS << "Pointers: ";
    569     for (iterator I = begin(), E = end(); I != E; ++I) {
    570       if (I != begin()) OS << ", ";
    571       WriteAsOperand(OS << "(", I.getPointer());
    572       OS << ", " << I.getSize() << ")";
    573     }
    574   }
    575   if (!UnknownInsts.empty()) {
    576     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
    577     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
    578       if (i) OS << ", ";
    579       WriteAsOperand(OS, UnknownInsts[i]);
    580     }
    581   }
    582   OS << "\n";
    583 }
    584 
    585 void AliasSetTracker::print(raw_ostream &OS) const {
    586   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
    587      << PointerMap.size() << " pointer values.\n";
    588   for (const_iterator I = begin(), E = end(); I != E; ++I)
    589     I->print(OS);
    590   OS << "\n";
    591 }
    592 
    593 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    594 void AliasSet::dump() const { print(dbgs()); }
    595 void AliasSetTracker::dump() const { print(dbgs()); }
    596 #endif
    597 
    598 //===----------------------------------------------------------------------===//
    599 //                     ASTCallbackVH Class Implementation
    600 //===----------------------------------------------------------------------===//
    601 
    602 void AliasSetTracker::ASTCallbackVH::deleted() {
    603   assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
    604   AST->deleteValue(getValPtr());
    605   // this now dangles!
    606 }
    607 
    608 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
    609   AST->copyValue(getValPtr(), V);
    610 }
    611 
    612 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
    613   : CallbackVH(V), AST(ast) {}
    614 
    615 AliasSetTracker::ASTCallbackVH &
    616 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
    617   return *this = ASTCallbackVH(V, AST);
    618 }
    619 
    620 //===----------------------------------------------------------------------===//
    621 //                            AliasSetPrinter Pass
    622 //===----------------------------------------------------------------------===//
    623 
    624 namespace {
    625   class AliasSetPrinter : public FunctionPass {
    626     AliasSetTracker *Tracker;
    627   public:
    628     static char ID; // Pass identification, replacement for typeid
    629     AliasSetPrinter() : FunctionPass(ID) {
    630       initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
    631     }
    632 
    633     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
    634       AU.setPreservesAll();
    635       AU.addRequired<AliasAnalysis>();
    636     }
    637 
    638     virtual bool runOnFunction(Function &F) {
    639       Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
    640 
    641       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
    642         Tracker->add(&*I);
    643       Tracker->print(errs());
    644       delete Tracker;
    645       return false;
    646     }
    647   };
    648 }
    649 
    650 char AliasSetPrinter::ID = 0;
    651 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
    652                 "Alias Set Printer", false, true)
    653 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
    654 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
    655                 "Alias Set Printer", false, true)
    656