lib/Analysis/AliasSetTracker.cpp

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