xref: /llvm-project/llvm/lib/Analysis/AliasSetTracker.cpp (revision 825c74c241504c261b9f7fc87fbb0cf777b7e2fc)
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/Analysis/MemoryLocation.h"
17 #include "llvm/Config/llvm-config.h"
18 #include "llvm/IR/CallSite.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/IR/PatternMatch.h"
28 #include "llvm/IR/Value.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/AtomicOrdering.h"
31 #include "llvm/Support/Casting.h"
32 #include "llvm/Support/CommandLine.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/ErrorHandling.h"
36 #include "llvm/Support/raw_ostream.h"
37 #include <cassert>
38 #include <cstdint>
39 #include <vector>
40 
41 using namespace llvm;
42 
43 static cl::opt<unsigned>
44     SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
45                         cl::init(250),
46                         cl::desc("The maximum number of pointers may-alias "
47                                  "sets may contain before degradation"));
48 
49 /// mergeSetIn - Merge the specified alias set into this alias set.
50 ///
51 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
52   assert(!AS.Forward && "Alias set is already forwarding!");
53   assert(!Forward && "This set is a forwarding set!!");
54 
55   bool WasMustAlias = (Alias == SetMustAlias);
56   // Update the alias and access types of this set...
57   Access |= AS.Access;
58   Alias  |= AS.Alias;
59 
60   if (Alias == SetMustAlias) {
61     // Check that these two merged sets really are must aliases.  Since both
62     // used to be must-alias sets, we can just check any pointer from each set
63     // for aliasing.
64     AliasAnalysis &AA = AST.getAliasAnalysis();
65     PointerRec *L = getSomePointer();
66     PointerRec *R = AS.getSomePointer();
67 
68     // If the pointers are not a must-alias pair, this set becomes a may alias.
69     if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
70                  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
71         MustAlias)
72       Alias = SetMayAlias;
73   }
74 
75   if (Alias == SetMayAlias) {
76     if (WasMustAlias)
77       AST.TotalMayAliasSetSize += size();
78     if (AS.Alias == SetMustAlias)
79       AST.TotalMayAliasSetSize += AS.size();
80   }
81 
82   bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
83   if (UnknownInsts.empty()) {            // Merge call sites...
84     if (ASHadUnknownInsts) {
85       std::swap(UnknownInsts, AS.UnknownInsts);
86       addRef();
87     }
88   } else if (ASHadUnknownInsts) {
89     UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
90     AS.UnknownInsts.clear();
91   }
92 
93   AS.Forward = this; // Forward across AS now...
94   addRef();          // AS is now pointing to us...
95 
96   // Merge the list of constituent pointers...
97   if (AS.PtrList) {
98     SetSize += AS.size();
99     AS.SetSize = 0;
100     *PtrListEnd = AS.PtrList;
101     AS.PtrList->setPrevInList(PtrListEnd);
102     PtrListEnd = AS.PtrListEnd;
103 
104     AS.PtrList = nullptr;
105     AS.PtrListEnd = &AS.PtrList;
106     assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
107   }
108   if (ASHadUnknownInsts)
109     AS.dropRef(AST);
110 }
111 
112 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
113   if (AliasSet *Fwd = AS->Forward) {
114     Fwd->dropRef(*this);
115     AS->Forward = nullptr;
116   }
117 
118   if (AS->Alias == AliasSet::SetMayAlias)
119     TotalMayAliasSetSize -= AS->size();
120 
121   AliasSets.erase(AS);
122 }
123 
124 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
125   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
126   AST.removeAliasSet(this);
127 }
128 
129 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
130                           LocationSize Size, const AAMDNodes &AAInfo,
131                           bool KnownMustAlias) {
132   assert(!Entry.hasAliasSet() && "Entry already in set!");
133 
134   // Check to see if we have to downgrade to _may_ alias.
135   if (isMustAlias() && !KnownMustAlias)
136     if (PointerRec *P = getSomePointer()) {
137       AliasAnalysis &AA = AST.getAliasAnalysis();
138       AliasResult Result =
139           AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
140                    MemoryLocation(Entry.getValue(), Size, AAInfo));
141       if (Result != MustAlias) {
142         Alias = SetMayAlias;
143         AST.TotalMayAliasSetSize += size();
144       } else {
145         // First entry of must alias must have maximum size!
146         P->updateSizeAndAAInfo(Size, AAInfo);
147       }
148       assert(Result != NoAlias && "Cannot be part of must set!");
149     }
150 
151   Entry.setAliasSet(this);
152   Entry.updateSizeAndAAInfo(Size, AAInfo);
153 
154   // Add it to the end of the list...
155   ++SetSize;
156   assert(*PtrListEnd == nullptr && "End of list is not null?");
157   *PtrListEnd = &Entry;
158   PtrListEnd = Entry.setPrevInList(PtrListEnd);
159   assert(*PtrListEnd == nullptr && "End of list is not null?");
160   // Entry points to alias set.
161   addRef();
162 
163   if (Alias == SetMayAlias)
164     AST.TotalMayAliasSetSize++;
165 }
166 
167 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
168   if (UnknownInsts.empty())
169     addRef();
170   UnknownInsts.emplace_back(I);
171 
172   // Guards are marked as modifying memory for control flow modelling purposes,
173   // but don't actually modify any specific memory location.
174   using namespace PatternMatch;
175   bool MayWriteMemory = I->mayWriteToMemory() &&
176     !match(I, m_Intrinsic<Intrinsic::experimental_guard>()) &&
177     !(I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()));
178   if (!MayWriteMemory) {
179     Alias = SetMayAlias;
180     Access |= RefAccess;
181     return;
182   }
183 
184   // FIXME: This should use mod/ref information to make this not suck so bad
185   Alias = SetMayAlias;
186   Access = ModRefAccess;
187 }
188 
189 /// aliasesPointer - Return true if the specified pointer "may" (or must)
190 /// alias one of the members in the set.
191 ///
192 bool AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
193                               const AAMDNodes &AAInfo,
194                               AliasAnalysis &AA) const {
195   if (AliasAny)
196     return true;
197 
198   if (Alias == SetMustAlias) {
199     assert(UnknownInsts.empty() && "Illegal must alias set!");
200 
201     // If this is a set of MustAliases, only check to see if the pointer aliases
202     // SOME value in the set.
203     PointerRec *SomePtr = getSomePointer();
204     assert(SomePtr && "Empty must-alias set??");
205     return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
206                                    SomePtr->getAAInfo()),
207                     MemoryLocation(Ptr, Size, AAInfo));
208   }
209 
210   // If this is a may-alias set, we have to check all of the pointers in the set
211   // to be sure it doesn't alias the set...
212   for (iterator I = begin(), E = end(); I != E; ++I)
213     if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
214                  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
215       return true;
216 
217   // Check the unknown instructions...
218   if (!UnknownInsts.empty()) {
219     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
220       if (auto *Inst = getUnknownInst(i))
221         if (isModOrRefSet(
222                 AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
223           return true;
224   }
225 
226   return false;
227 }
228 
229 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
230                                   AliasAnalysis &AA) const {
231 
232   if (AliasAny)
233     return true;
234 
235   if (!Inst->mayReadOrWriteMemory())
236     return false;
237 
238   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
239     if (auto *UnknownInst = getUnknownInst(i)) {
240       ImmutableCallSite C1(UnknownInst), C2(Inst);
241       if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||
242           isModOrRefSet(AA.getModRefInfo(C2, C1)))
243         return true;
244     }
245   }
246 
247   for (iterator I = begin(), E = end(); I != E; ++I)
248     if (isModOrRefSet(AA.getModRefInfo(
249             Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
250       return true;
251 
252   return false;
253 }
254 
255 Instruction* AliasSet::getUniqueInstruction() {
256   if (size() != 0)
257     // Can't track source of pointer, might be many instruction
258     return nullptr;
259   if (AliasAny)
260     // May have collapses alias set
261     return nullptr;
262  if (1 != UnknownInsts.size())
263     return nullptr;
264   return cast<Instruction>(UnknownInsts[0]);
265 }
266 
267 void AliasSetTracker::clear() {
268   // Delete all the PointerRec entries.
269   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
270        I != E; ++I)
271     I->second->eraseFromList();
272 
273   PointerMap.clear();
274 
275   // The alias sets should all be clear now.
276   AliasSets.clear();
277 }
278 
279 
280 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
281 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
282 /// the pointer was found.
283 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
284                                                     LocationSize Size,
285                                                     const AAMDNodes &AAInfo) {
286   AliasSet *FoundSet = nullptr;
287   for (iterator I = begin(), E = end(); I != E;) {
288     iterator Cur = I++;
289     if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
290 
291     if (!FoundSet) {      // If this is the first alias set ptr can go into.
292       FoundSet = &*Cur;   // Remember it.
293     } else {              // Otherwise, we must merge the sets.
294       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
295     }
296   }
297 
298   return FoundSet;
299 }
300 
301 bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
302   for (const AliasSet &AS : *this)
303     if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
304       return true;
305   return false;
306 }
307 
308 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
309   AliasSet *FoundSet = nullptr;
310   for (iterator I = begin(), E = end(); I != E;) {
311     iterator Cur = I++;
312     if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
313       continue;
314     if (!FoundSet)            // If this is the first alias set ptr can go into.
315       FoundSet = &*Cur;       // Remember it.
316     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
317       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
318   }
319   return FoundSet;
320 }
321 
322 AliasSet &AliasSetTracker::getAliasSetFor(const MemoryLocation &MemLoc) {
323 
324   Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
325   const LocationSize Size = MemLoc.Size;
326   const AAMDNodes &AAInfo = MemLoc.AATags;
327 
328   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
329 
330   if (AliasAnyAS) {
331     // At this point, the AST is saturated, so we only have one active alias
332     // set. That means we already know which alias set we want to return, and
333     // just need to add the pointer to that set to keep the data structure
334     // consistent.
335     // This, of course, means that we will never need a merge here.
336     if (Entry.hasAliasSet()) {
337       Entry.updateSizeAndAAInfo(Size, AAInfo);
338       assert(Entry.getAliasSet(*this) == AliasAnyAS &&
339              "Entry in saturated AST must belong to only alias set");
340     } else {
341       AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
342     }
343     return *AliasAnyAS;
344   }
345 
346   // Check to see if the pointer is already known.
347   if (Entry.hasAliasSet()) {
348     // If the size changed, we may need to merge several alias sets.
349     // Note that we can *not* return the result of mergeAliasSetsForPointer
350     // due to a quirk of alias analysis behavior. Since alias(undef, undef)
351     // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
352     // the right set for undef, even if it exists.
353     if (Entry.updateSizeAndAAInfo(Size, AAInfo))
354       mergeAliasSetsForPointer(Pointer, Size, AAInfo);
355     // Return the set!
356     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
357   }
358 
359   if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
360     // Add it to the alias set it aliases.
361     AS->addPointer(*this, Entry, Size, AAInfo);
362     return *AS;
363   }
364 
365   // Otherwise create a new alias set to hold the loaded pointer.
366   AliasSets.push_back(new AliasSet());
367   AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
368   return AliasSets.back();
369 }
370 
371 void AliasSetTracker::add(Value *Ptr, LocationSize Size,
372                           const AAMDNodes &AAInfo) {
373   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
374 }
375 
376 void AliasSetTracker::add(LoadInst *LI) {
377   if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
378 
379   addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
380 }
381 
382 void AliasSetTracker::add(StoreInst *SI) {
383   if (isStrongerThanMonotonic(SI->getOrdering())) return addUnknown(SI);
384 
385   addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
386 }
387 
388 void AliasSetTracker::add(VAArgInst *VAAI) {
389   addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
390 }
391 
392 void AliasSetTracker::add(AnyMemSetInst *MSI) {
393   auto MemLoc = MemoryLocation::getForDest(MSI);
394   addPointer(MemLoc, AliasSet::ModAccess);
395 }
396 
397 void AliasSetTracker::add(AnyMemTransferInst *MTI) {
398   auto SrcLoc = MemoryLocation::getForSource(MTI);
399   addPointer(SrcLoc, AliasSet::RefAccess);
400 
401   auto DestLoc = MemoryLocation::getForDest(MTI);
402   addPointer(DestLoc, AliasSet::ModAccess);
403 }
404 
405 void AliasSetTracker::addUnknown(Instruction *Inst) {
406   if (isa<DbgInfoIntrinsic>(Inst))
407     return; // Ignore DbgInfo Intrinsics.
408 
409   if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
410     // These intrinsics will show up as affecting memory, but they are just
411     // markers.
412     switch (II->getIntrinsicID()) {
413     default:
414       break;
415       // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
416     case Intrinsic::assume:
417     case Intrinsic::sideeffect:
418       return;
419     }
420   }
421   if (!Inst->mayReadOrWriteMemory())
422     return; // doesn't alias anything
423 
424   AliasSet *AS = findAliasSetForUnknownInst(Inst);
425   if (AS) {
426     AS->addUnknownInst(Inst, AA);
427     return;
428   }
429   AliasSets.push_back(new AliasSet());
430   AS = &AliasSets.back();
431   AS->addUnknownInst(Inst, AA);
432 }
433 
434 void AliasSetTracker::add(Instruction *I) {
435   // Dispatch to one of the other add methods.
436   if (LoadInst *LI = dyn_cast<LoadInst>(I))
437     return add(LI);
438   if (StoreInst *SI = dyn_cast<StoreInst>(I))
439     return add(SI);
440   if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
441     return add(VAAI);
442   if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
443     return add(MSI);
444   if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
445     return add(MTI);
446   return addUnknown(I);
447 }
448 
449 void AliasSetTracker::add(BasicBlock &BB) {
450   for (auto &I : BB)
451     add(&I);
452 }
453 
454 void AliasSetTracker::add(const AliasSetTracker &AST) {
455   assert(&AA == &AST.AA &&
456          "Merging AliasSetTracker objects with different Alias Analyses!");
457 
458   // Loop over all of the alias sets in AST, adding the pointers contained
459   // therein into the current alias sets.  This can cause alias sets to be
460   // merged together in the current AST.
461   for (const AliasSet &AS : AST) {
462     if (AS.Forward)
463       continue; // Ignore forwarding alias sets
464 
465     // If there are any call sites in the alias set, add them to this AST.
466     for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
467       if (auto *Inst = AS.getUnknownInst(i))
468         add(Inst);
469 
470     // Loop over all of the pointers in this alias set.
471     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
472       addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
473                  (AliasSet::AccessLattice)AS.Access);
474   }
475 }
476 
477 // deleteValue method - This method is used to remove a pointer value from the
478 // AliasSetTracker entirely.  It should be used when an instruction is deleted
479 // from the program to update the AST.  If you don't use this, you would have
480 // dangling pointers to deleted instructions.
481 //
482 void AliasSetTracker::deleteValue(Value *PtrVal) {
483   // First, look up the PointerRec for this pointer.
484   PointerMapType::iterator I = PointerMap.find_as(PtrVal);
485   if (I == PointerMap.end()) return;  // Noop
486 
487   // If we found one, remove the pointer from the alias set it is in.
488   AliasSet::PointerRec *PtrValEnt = I->second;
489   AliasSet *AS = PtrValEnt->getAliasSet(*this);
490 
491   // Unlink and delete from the list of values.
492   PtrValEnt->eraseFromList();
493 
494   if (AS->Alias == AliasSet::SetMayAlias) {
495     AS->SetSize--;
496     TotalMayAliasSetSize--;
497   }
498 
499   // Stop using the alias set.
500   AS->dropRef(*this);
501 
502   PointerMap.erase(I);
503 }
504 
505 // copyValue - This method should be used whenever a preexisting value in the
506 // program is copied or cloned, introducing a new value.  Note that it is ok for
507 // clients that use this method to introduce the same value multiple times: if
508 // the tracker already knows about a value, it will ignore the request.
509 //
510 void AliasSetTracker::copyValue(Value *From, Value *To) {
511   // First, look up the PointerRec for this pointer.
512   PointerMapType::iterator I = PointerMap.find_as(From);
513   if (I == PointerMap.end())
514     return;  // Noop
515   assert(I->second->hasAliasSet() && "Dead entry?");
516 
517   AliasSet::PointerRec &Entry = getEntryFor(To);
518   if (Entry.hasAliasSet()) return;    // Already in the tracker!
519 
520   // getEntryFor above may invalidate iterator \c I, so reinitialize it.
521   I = PointerMap.find_as(From);
522   // Add it to the alias set it aliases...
523   AliasSet *AS = I->second->getAliasSet(*this);
524   AS->addPointer(*this, Entry, I->second->getSize(),
525                  I->second->getAAInfo(),
526                  true);
527 }
528 
529 AliasSet &AliasSetTracker::mergeAllAliasSets() {
530   assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
531          "Full merge should happen once, when the saturation threshold is "
532          "reached");
533 
534   // Collect all alias sets, so that we can drop references with impunity
535   // without worrying about iterator invalidation.
536   std::vector<AliasSet *> ASVector;
537   ASVector.reserve(SaturationThreshold);
538   for (iterator I = begin(), E = end(); I != E; I++)
539     ASVector.push_back(&*I);
540 
541   // Copy all instructions and pointers into a new set, and forward all other
542   // sets to it.
543   AliasSets.push_back(new AliasSet());
544   AliasAnyAS = &AliasSets.back();
545   AliasAnyAS->Alias = AliasSet::SetMayAlias;
546   AliasAnyAS->Access = AliasSet::ModRefAccess;
547   AliasAnyAS->AliasAny = true;
548 
549   for (auto Cur : ASVector) {
550     // If Cur was already forwarding, just forward to the new AS instead.
551     AliasSet *FwdTo = Cur->Forward;
552     if (FwdTo) {
553       Cur->Forward = AliasAnyAS;
554       AliasAnyAS->addRef();
555       FwdTo->dropRef(*this);
556       continue;
557     }
558 
559     // Otherwise, perform the actual merge.
560     AliasAnyAS->mergeSetIn(*Cur, *this);
561   }
562 
563   return *AliasAnyAS;
564 }
565 
566 AliasSet &AliasSetTracker::addPointer(Value *P, LocationSize Size,
567                                       const AAMDNodes &AAInfo,
568                                       AliasSet::AccessLattice E) {
569   AliasSet &AS = getAliasSetFor(MemoryLocation(P, Size, AAInfo));
570   AS.Access |= E;
571 
572   if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
573     // The AST is now saturated. From here on, we conservatively consider all
574     // pointers to alias each-other.
575     return mergeAllAliasSets();
576   }
577 
578   return AS;
579 }
580 
581 //===----------------------------------------------------------------------===//
582 //               AliasSet/AliasSetTracker Printing Support
583 //===----------------------------------------------------------------------===//
584 
585 void AliasSet::print(raw_ostream &OS) const {
586   OS << "  AliasSet[" << (const void*)this << ", " << RefCount << "] ";
587   OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
588   switch (Access) {
589   case NoAccess:     OS << "No access "; break;
590   case RefAccess:    OS << "Ref       "; break;
591   case ModAccess:    OS << "Mod       "; break;
592   case ModRefAccess: OS << "Mod/Ref   "; break;
593   default: llvm_unreachable("Bad value for Access!");
594   }
595   if (Forward)
596     OS << " forwarding to " << (void*)Forward;
597 
598   if (!empty()) {
599     OS << "Pointers: ";
600     for (iterator I = begin(), E = end(); I != E; ++I) {
601       if (I != begin()) OS << ", ";
602       I.getPointer()->printAsOperand(OS << "(");
603       if (I.getSize() == MemoryLocation::UnknownSize)
604         OS << ", unknown)";
605       else
606         OS << ", " << I.getSize() << ")";
607     }
608   }
609   if (!UnknownInsts.empty()) {
610     OS << "\n    " << UnknownInsts.size() << " Unknown instructions: ";
611     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
612       if (i) OS << ", ";
613       if (auto *I = getUnknownInst(i)) {
614         if (I->hasName())
615           I->printAsOperand(OS);
616         else
617           I->print(OS);
618       }
619     }
620   }
621   OS << "\n";
622 }
623 
624 void AliasSetTracker::print(raw_ostream &OS) const {
625   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
626      << PointerMap.size() << " pointer values.\n";
627   for (const AliasSet &AS : *this)
628     AS.print(OS);
629   OS << "\n";
630 }
631 
632 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
633 LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
634 LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
635 #endif
636 
637 //===----------------------------------------------------------------------===//
638 //                     ASTCallbackVH Class Implementation
639 //===----------------------------------------------------------------------===//
640 
641 void AliasSetTracker::ASTCallbackVH::deleted() {
642   assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
643   AST->deleteValue(getValPtr());
644   // this now dangles!
645 }
646 
647 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
648   AST->copyValue(getValPtr(), V);
649 }
650 
651 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
652   : CallbackVH(V), AST(ast) {}
653 
654 AliasSetTracker::ASTCallbackVH &
655 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
656   return *this = ASTCallbackVH(V, AST);
657 }
658 
659 //===----------------------------------------------------------------------===//
660 //                            AliasSetPrinter Pass
661 //===----------------------------------------------------------------------===//
662 
663 namespace {
664 
665   class AliasSetPrinter : public FunctionPass {
666     AliasSetTracker *Tracker;
667 
668   public:
669     static char ID; // Pass identification, replacement for typeid
670 
671     AliasSetPrinter() : FunctionPass(ID) {
672       initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
673     }
674 
675     void getAnalysisUsage(AnalysisUsage &AU) const override {
676       AU.setPreservesAll();
677       AU.addRequired<AAResultsWrapperPass>();
678     }
679 
680     bool runOnFunction(Function &F) override {
681       auto &AAWP = getAnalysis<AAResultsWrapperPass>();
682       Tracker = new AliasSetTracker(AAWP.getAAResults());
683       errs() << "Alias sets for function '" << F.getName() << "':\n";
684       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
685         Tracker->add(&*I);
686       Tracker->print(errs());
687       delete Tracker;
688       return false;
689     }
690   };
691 
692 } // end anonymous namespace
693 
694 char AliasSetPrinter::ID = 0;
695 
696 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
697                 "Alias Set Printer", false, true)
698 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
699 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
700                 "Alias Set Printer", false, true)
701