LLVM  6.0.0svn
AliasSetTracker.cpp
Go to the documentation of this file.
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 
16 #include "llvm/IR/DataLayout.h"
17 #include "llvm/IR/InstIterator.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/IR/Module.h"
22 #include "llvm/IR/Type.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/Debug.h"
27 using namespace llvm;
28 
29 static cl::opt<unsigned>
30  SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
31  cl::init(250),
32  cl::desc("The maximum number of pointers may-alias "
33  "sets may contain before degradation"));
34 
35 /// mergeSetIn - Merge the specified alias set into this alias set.
36 ///
38  assert(!AS.Forward && "Alias set is already forwarding!");
39  assert(!Forward && "This set is a forwarding set!!");
40 
41  bool WasMustAlias = (Alias == SetMustAlias);
42  // Update the alias and access types of this set...
43  Access |= AS.Access;
44  Alias |= AS.Alias;
45  Volatile |= AS.Volatile;
46 
47  if (Alias == SetMustAlias) {
48  // Check that these two merged sets really are must aliases. Since both
49  // used to be must-alias sets, we can just check any pointer from each set
50  // for aliasing.
51  AliasAnalysis &AA = AST.getAliasAnalysis();
52  PointerRec *L = getSomePointer();
53  PointerRec *R = AS.getSomePointer();
54 
55  // If the pointers are not a must-alias pair, this set becomes a may alias.
56  if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
57  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
58  MustAlias)
59  Alias = SetMayAlias;
60  }
61 
62  if (Alias == SetMayAlias) {
63  if (WasMustAlias)
64  AST.TotalMayAliasSetSize += size();
65  if (AS.Alias == SetMustAlias)
66  AST.TotalMayAliasSetSize += AS.size();
67  }
68 
69  bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
70  if (UnknownInsts.empty()) { // Merge call sites...
71  if (ASHadUnknownInsts) {
72  std::swap(UnknownInsts, AS.UnknownInsts);
73  addRef();
74  }
75  } else if (ASHadUnknownInsts) {
76  UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
77  AS.UnknownInsts.clear();
78  }
79 
80  AS.Forward = this; // Forward across AS now...
81  addRef(); // AS is now pointing to us...
82 
83  // Merge the list of constituent pointers...
84  if (AS.PtrList) {
85  SetSize += AS.size();
86  AS.SetSize = 0;
87  *PtrListEnd = AS.PtrList;
88  AS.PtrList->setPrevInList(PtrListEnd);
89  PtrListEnd = AS.PtrListEnd;
90 
91  AS.PtrList = nullptr;
92  AS.PtrListEnd = &AS.PtrList;
93  assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
94  }
95  if (ASHadUnknownInsts)
96  AS.dropRef(AST);
97 }
98 
99 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
100  if (AliasSet *Fwd = AS->Forward) {
101  Fwd->dropRef(*this);
102  AS->Forward = nullptr;
103  }
104 
105  if (AS->Alias == AliasSet::SetMayAlias)
106  TotalMayAliasSetSize -= AS->size();
107 
108  AliasSets.erase(AS);
109 
110 }
111 
112 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
113  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
114  AST.removeAliasSet(this);
115 }
116 
117 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
118  uint64_t Size, const AAMDNodes &AAInfo,
119  bool KnownMustAlias) {
120  assert(!Entry.hasAliasSet() && "Entry already in set!");
121 
122  // Check to see if we have to downgrade to _may_ alias.
123  if (isMustAlias() && !KnownMustAlias)
124  if (PointerRec *P = getSomePointer()) {
125  AliasAnalysis &AA = AST.getAliasAnalysis();
126  AliasResult Result =
127  AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
128  MemoryLocation(Entry.getValue(), Size, AAInfo));
129  if (Result != MustAlias) {
130  Alias = SetMayAlias;
131  AST.TotalMayAliasSetSize += size();
132  } else {
133  // First entry of must alias must have maximum size!
134  P->updateSizeAndAAInfo(Size, AAInfo);
135  }
136  assert(Result != NoAlias && "Cannot be part of must set!");
137  }
138 
139  Entry.setAliasSet(this);
140  Entry.updateSizeAndAAInfo(Size, AAInfo);
141 
142  // Add it to the end of the list...
143  ++SetSize;
144  assert(*PtrListEnd == nullptr && "End of list is not null?");
145  *PtrListEnd = &Entry;
146  PtrListEnd = Entry.setPrevInList(PtrListEnd);
147  assert(*PtrListEnd == nullptr && "End of list is not null?");
148  // Entry points to alias set.
149  addRef();
150 
151  if (Alias == SetMayAlias)
152  AST.TotalMayAliasSetSize++;
153 }
154 
155 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
156  if (UnknownInsts.empty())
157  addRef();
158  UnknownInsts.emplace_back(I);
159 
160  if (!I->mayWriteToMemory()) {
161  Alias = SetMayAlias;
162  Access |= RefAccess;
163  return;
164  }
165 
166  // FIXME: This should use mod/ref information to make this not suck so bad
167  Alias = SetMayAlias;
168  Access = ModRefAccess;
169 }
170 
171 /// aliasesPointer - Return true if the specified pointer "may" (or must)
172 /// alias one of the members in the set.
173 ///
174 bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
175  const AAMDNodes &AAInfo,
176  AliasAnalysis &AA) const {
177  if (AliasAny)
178  return true;
179 
180  if (Alias == SetMustAlias) {
181  assert(UnknownInsts.empty() && "Illegal must alias set!");
182 
183  // If this is a set of MustAliases, only check to see if the pointer aliases
184  // SOME value in the set.
185  PointerRec *SomePtr = getSomePointer();
186  assert(SomePtr && "Empty must-alias set??");
187  return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
188  SomePtr->getAAInfo()),
189  MemoryLocation(Ptr, Size, AAInfo));
190  }
191 
192  // If this is a may-alias set, we have to check all of the pointers in the set
193  // to be sure it doesn't alias the set...
194  for (iterator I = begin(), E = end(); I != E; ++I)
195  if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
196  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
197  return true;
198 
199  // Check the unknown instructions...
200  if (!UnknownInsts.empty()) {
201  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
202  if (auto *Inst = getUnknownInst(i))
203  if (AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo)) !=
204  MRI_NoModRef)
205  return true;
206  }
207 
208  return false;
209 }
210 
212  AliasAnalysis &AA) const {
213 
214  if (AliasAny)
215  return true;
216 
217  if (!Inst->mayReadOrWriteMemory())
218  return false;
219 
220  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
221  if (auto *UnknownInst = getUnknownInst(i)) {
222  ImmutableCallSite C1(UnknownInst), C2(Inst);
223  if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
224  AA.getModRefInfo(C2, C1) != MRI_NoModRef)
225  return true;
226  }
227  }
228 
229  for (iterator I = begin(), E = end(); I != E; ++I)
230  if (AA.getModRefInfo(Inst, MemoryLocation(I.getPointer(), I.getSize(),
231  I.getAAInfo())) != MRI_NoModRef)
232  return true;
233 
234  return false;
235 }
236 
238  // Delete all the PointerRec entries.
239  for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
240  I != E; ++I)
241  I->second->eraseFromList();
242 
243  PointerMap.clear();
244 
245  // The alias sets should all be clear now.
246  AliasSets.clear();
247 }
248 
249 
250 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
251 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
252 /// the pointer was found.
253 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
254  uint64_t Size,
255  const AAMDNodes &AAInfo) {
256  AliasSet *FoundSet = nullptr;
257  for (iterator I = begin(), E = end(); I != E;) {
258  iterator Cur = I++;
259  if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
260 
261  if (!FoundSet) { // If this is the first alias set ptr can go into.
262  FoundSet = &*Cur; // Remember it.
263  } else { // Otherwise, we must merge the sets.
264  FoundSet->mergeSetIn(*Cur, *this); // Merge in contents.
265  }
266  }
267 
268  return FoundSet;
269 }
270 
272  for (const AliasSet &AS : *this)
273  if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
274  return true;
275  return false;
276 }
277 
278 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
279  AliasSet *FoundSet = nullptr;
280  for (iterator I = begin(), E = end(); I != E;) {
281  iterator Cur = I++;
282  if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
283  continue;
284  if (!FoundSet) // If this is the first alias set ptr can go into.
285  FoundSet = &*Cur; // Remember it.
286  else if (!Cur->Forward) // Otherwise, we must merge the sets.
287  FoundSet->mergeSetIn(*Cur, *this); // Merge in contents.
288  }
289  return FoundSet;
290 }
291 
292 /// getAliasSetForPointer - Return the alias set that the specified pointer
293 /// lives in.
295  const AAMDNodes &AAInfo) {
296  AliasSet::PointerRec &Entry = getEntryFor(Pointer);
297 
298  if (AliasAnyAS) {
299  // At this point, the AST is saturated, so we only have one active alias
300  // set. That means we already know which alias set we want to return, and
301  // just need to add the pointer to that set to keep the data structure
302  // consistent.
303  // This, of course, means that we will never need a merge here.
304  if (Entry.hasAliasSet()) {
305  Entry.updateSizeAndAAInfo(Size, AAInfo);
306  assert(Entry.getAliasSet(*this) == AliasAnyAS &&
307  "Entry in saturated AST must belong to only alias set");
308  } else {
309  AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
310  }
311  return *AliasAnyAS;
312  }
313 
314  // Check to see if the pointer is already known.
315  if (Entry.hasAliasSet()) {
316  // If the size changed, we may need to merge several alias sets.
317  // Note that we can *not* return the result of mergeAliasSetsForPointer
318  // due to a quirk of alias analysis behavior. Since alias(undef, undef)
319  // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
320  // the right set for undef, even if it exists.
321  if (Entry.updateSizeAndAAInfo(Size, AAInfo))
322  mergeAliasSetsForPointer(Pointer, Size, AAInfo);
323  // Return the set!
324  return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
325  }
326 
327  if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
328  // Add it to the alias set it aliases.
329  AS->addPointer(*this, Entry, Size, AAInfo);
330  return *AS;
331  }
332 
333  // Otherwise create a new alias set to hold the loaded pointer.
334  AliasSets.push_back(new AliasSet());
335  AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
336  return AliasSets.back();
337 }
338 
339 void AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
340  addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
341 }
342 
344  if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
345 
346  AAMDNodes AAInfo;
347  LI->getAAMetadata(AAInfo);
348 
349  AliasSet::AccessLattice Access = AliasSet::RefAccess;
350  const DataLayout &DL = LI->getModule()->getDataLayout();
351  AliasSet &AS = addPointer(LI->getOperand(0),
352  DL.getTypeStoreSize(LI->getType()), AAInfo, Access);
353  if (LI->isVolatile()) AS.setVolatile();
354 }
355 
357  if (isStrongerThanMonotonic(SI->getOrdering())) return addUnknown(SI);
358 
359  AAMDNodes AAInfo;
360  SI->getAAMetadata(AAInfo);
361 
362  AliasSet::AccessLattice Access = AliasSet::ModAccess;
363  const DataLayout &DL = SI->getModule()->getDataLayout();
364  Value *Val = SI->getOperand(0);
365  AliasSet &AS = addPointer(
366  SI->getOperand(1), DL.getTypeStoreSize(Val->getType()), AAInfo, Access);
367  if (SI->isVolatile()) AS.setVolatile();
368 }
369 
371  AAMDNodes AAInfo;
372  VAAI->getAAMetadata(AAInfo);
373 
374  addPointer(VAAI->getOperand(0), MemoryLocation::UnknownSize, AAInfo,
375  AliasSet::ModRefAccess);
376 }
377 
379  AAMDNodes AAInfo;
380  MSI->getAAMetadata(AAInfo);
381 
382  uint64_t Len;
383 
384  if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
385  Len = C->getZExtValue();
386  else
388 
389  AliasSet &AS =
390  addPointer(MSI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
391  if (MSI->isVolatile())
392  AS.setVolatile();
393 }
394 
396  AAMDNodes AAInfo;
397  MTI->getAAMetadata(AAInfo);
398 
399  uint64_t Len;
400  if (ConstantInt *C = dyn_cast<ConstantInt>(MTI->getLength()))
401  Len = C->getZExtValue();
402  else
404 
405  AliasSet &ASSrc =
406  addPointer(MTI->getRawSource(), Len, AAInfo, AliasSet::RefAccess);
407  if (MTI->isVolatile())
408  ASSrc.setVolatile();
409 
410  AliasSet &ASDst =
411  addPointer(MTI->getRawDest(), Len, AAInfo, AliasSet::ModAccess);
412  if (MTI->isVolatile())
413  ASDst.setVolatile();
414 }
415 
417  if (isa<DbgInfoIntrinsic>(Inst))
418  return; // Ignore DbgInfo Intrinsics.
419 
420  if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
421  // These intrinsics will show up as affecting memory, but they are just
422  // markers.
423  switch (II->getIntrinsicID()) {
424  default:
425  break;
426  // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
427  case Intrinsic::assume:
428  return;
429  }
430  }
431  if (!Inst->mayReadOrWriteMemory())
432  return; // doesn't alias anything
433 
434  AliasSet *AS = findAliasSetForUnknownInst(Inst);
435  if (AS) {
436  AS->addUnknownInst(Inst, AA);
437  return;
438  }
439  AliasSets.push_back(new AliasSet());
440  AS = &AliasSets.back();
441  AS->addUnknownInst(Inst, AA);
442 }
443 
445  // Dispatch to one of the other add methods.
446  if (LoadInst *LI = dyn_cast<LoadInst>(I))
447  return add(LI);
448  if (StoreInst *SI = dyn_cast<StoreInst>(I))
449  return add(SI);
450  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
451  return add(VAAI);
452  if (MemSetInst *MSI = dyn_cast<MemSetInst>(I))
453  return add(MSI);
454  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(I))
455  return add(MTI);
456  return addUnknown(I);
457 }
458 
460  for (auto &I : BB)
461  add(&I);
462 }
463 
465  assert(&AA == &AST.AA &&
466  "Merging AliasSetTracker objects with different Alias Analyses!");
467 
468  // Loop over all of the alias sets in AST, adding the pointers contained
469  // therein into the current alias sets. This can cause alias sets to be
470  // merged together in the current AST.
471  for (const AliasSet &AS : AST) {
472  if (AS.Forward)
473  continue; // Ignore forwarding alias sets
474 
475  // If there are any call sites in the alias set, add them to this AST.
476  for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
477  if (auto *Inst = AS.getUnknownInst(i))
478  add(Inst);
479 
480  // Loop over all of the pointers in this alias set.
481  for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
482  AliasSet &NewAS =
483  addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
484  (AliasSet::AccessLattice)AS.Access);
485  if (AS.isVolatile()) NewAS.setVolatile();
486  }
487  }
488 }
489 
490 // deleteValue method - This method is used to remove a pointer value from the
491 // AliasSetTracker entirely. It should be used when an instruction is deleted
492 // from the program to update the AST. If you don't use this, you would have
493 // dangling pointers to deleted instructions.
494 //
496  // First, look up the PointerRec for this pointer.
497  PointerMapType::iterator I = PointerMap.find_as(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  if (AS->Alias == AliasSet::SetMayAlias) {
508  AS->SetSize--;
509  TotalMayAliasSetSize--;
510  }
511 
512  // Stop using the alias set.
513  AS->dropRef(*this);
514 
515  PointerMap.erase(I);
516 }
517 
518 // copyValue - This method should be used whenever a preexisting value in the
519 // program is copied or cloned, introducing a new value. Note that it is ok for
520 // clients that use this method to introduce the same value multiple times: if
521 // the tracker already knows about a value, it will ignore the request.
522 //
524  // First, look up the PointerRec for this pointer.
525  PointerMapType::iterator I = PointerMap.find_as(From);
526  if (I == PointerMap.end())
527  return; // Noop
528  assert(I->second->hasAliasSet() && "Dead entry?");
529 
530  AliasSet::PointerRec &Entry = getEntryFor(To);
531  if (Entry.hasAliasSet()) return; // Already in the tracker!
532 
533  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
534  I = PointerMap.find_as(From);
535  // Add it to the alias set it aliases...
536  AliasSet *AS = I->second->getAliasSet(*this);
537  AS->addPointer(*this, Entry, I->second->getSize(),
538  I->second->getAAInfo(),
539  true);
540 }
541 
542 AliasSet &AliasSetTracker::mergeAllAliasSets() {
543  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
544  "Full merge should happen once, when the saturation threshold is "
545  "reached");
546 
547  // Collect all alias sets, so that we can drop references with impunity
548  // without worrying about iterator invalidation.
549  std::vector<AliasSet *> ASVector;
550  ASVector.reserve(SaturationThreshold);
551  for (iterator I = begin(), E = end(); I != E; I++)
552  ASVector.push_back(&*I);
553 
554  // Copy all instructions and pointers into a new set, and forward all other
555  // sets to it.
556  AliasSets.push_back(new AliasSet());
557  AliasAnyAS = &AliasSets.back();
558  AliasAnyAS->Alias = AliasSet::SetMayAlias;
559  AliasAnyAS->Access = AliasSet::ModRefAccess;
560  AliasAnyAS->AliasAny = true;
561 
562  for (auto Cur : ASVector) {
563 
564  // If Cur was already forwarding, just forward to the new AS instead.
565  AliasSet *FwdTo = Cur->Forward;
566  if (FwdTo) {
567  Cur->Forward = AliasAnyAS;
568  AliasAnyAS->addRef();
569  FwdTo->dropRef(*this);
570  continue;
571  }
572 
573  // Otherwise, perform the actual merge.
574  AliasAnyAS->mergeSetIn(*Cur, *this);
575  }
576 
577  return *AliasAnyAS;
578 }
579 
580 AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size,
581  const AAMDNodes &AAInfo,
582  AliasSet::AccessLattice E) {
583 
584  AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo);
585  AS.Access |= E;
586 
587  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
588  // The AST is now saturated. From here on, we conservatively consider all
589  // pointers to alias each-other.
590  return mergeAllAliasSets();
591  }
592 
593  return AS;
594 }
595 
596 //===----------------------------------------------------------------------===//
597 // AliasSet/AliasSetTracker Printing Support
598 //===----------------------------------------------------------------------===//
599 
600 void AliasSet::print(raw_ostream &OS) const {
601  OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
602  OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
603  switch (Access) {
604  case NoAccess: OS << "No access "; break;
605  case RefAccess: OS << "Ref "; break;
606  case ModAccess: OS << "Mod "; break;
607  case ModRefAccess: OS << "Mod/Ref "; break;
608  default: llvm_unreachable("Bad value for Access!");
609  }
610  if (isVolatile()) OS << "[volatile] ";
611  if (Forward)
612  OS << " forwarding to " << (void*)Forward;
613 
614 
615  if (!empty()) {
616  OS << "Pointers: ";
617  for (iterator I = begin(), E = end(); I != E; ++I) {
618  if (I != begin()) OS << ", ";
619  I.getPointer()->printAsOperand(OS << "(");
620  OS << ", " << I.getSize() << ")";
621  }
622  }
623  if (!UnknownInsts.empty()) {
624  OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
625  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
626  if (i) OS << ", ";
627  if (auto *I = getUnknownInst(i))
628  I->printAsOperand(OS);
629  }
630  }
631  OS << "\n";
632 }
633 
635  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
636  << PointerMap.size() << " pointer values.\n";
637  for (const AliasSet &AS : *this)
638  AS.print(OS);
639  OS << "\n";
640 }
641 
642 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
645 #endif
646 
647 //===----------------------------------------------------------------------===//
648 // ASTCallbackVH Class Implementation
649 //===----------------------------------------------------------------------===//
650 
651 void AliasSetTracker::ASTCallbackVH::deleted() {
652  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
653  AST->deleteValue(getValPtr());
654  // this now dangles!
655 }
656 
657 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
658  AST->copyValue(getValPtr(), V);
659 }
660 
661 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
662  : CallbackVH(V), AST(ast) {}
663 
664 AliasSetTracker::ASTCallbackVH &
665 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
666  return *this = ASTCallbackVH(V, AST);
667 }
668 
669 //===----------------------------------------------------------------------===//
670 // AliasSetPrinter Pass
671 //===----------------------------------------------------------------------===//
672 
673 namespace {
674  class AliasSetPrinter : public FunctionPass {
675  AliasSetTracker *Tracker;
676  public:
677  static char ID; // Pass identification, replacement for typeid
678  AliasSetPrinter() : FunctionPass(ID) {
680  }
681 
682  void getAnalysisUsage(AnalysisUsage &AU) const override {
683  AU.setPreservesAll();
685  }
686 
687  bool runOnFunction(Function &F) override {
688  auto &AAWP = getAnalysis<AAResultsWrapperPass>();
689  Tracker = new AliasSetTracker(AAWP.getAAResults());
690  errs() << "Alias sets for function '" << F.getName() << "':\n";
691  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
692  Tracker->add(&*I);
693  Tracker->print(errs());
694  delete Tracker;
695  return false;
696  }
697  };
698 }
699 
700 char AliasSetPrinter::ID = 0;
701 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
702  "Alias Set Printer", false, true)
704 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
705  "Alias Set Printer", false, true)
The two locations precisely alias each other.
Definition: AliasAnalysis.h:85
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST)
Merge the specified alias set into this alias set.
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets", "Alias Set Printer", false, true) INITIALIZE_PASS_END(AliasSetPrinter
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
Define an iterator for alias sets... this is just a forward iterator.
void dump() const
static cl::opt< unsigned > SaturationThreshold("alias-set-saturation-threshold", cl::Hidden, cl::init(250), cl::desc("The maximum number of pointers may-alias " "sets may contain before degradation"))
bool containsUnknown(const Instruction *I) const
Return true if the specified instruction "may" (or must) alias one of the members in any of the sets...
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:233
print alias sets
This class wraps the llvm.memset intrinsic.
The two locations do not alias at all.
Definition: AliasAnalysis.h:79
An instruction for reading from memory.
Definition: Instructions.h:164
print alias Alias Set Printer
Value * getRawSource() const
Return the arguments to the instruction.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:217
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:132
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:361
bool isMustAlias() const
void initializeAliasSetPrinterPass(PassRegistry &)
#define F(x, y, z)
Definition: MD5.cpp:55
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
friend class AliasSetTracker
iterator begin() const
bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const
An instruction for storing to memory.
Definition: Instructions.h:306
Value * getOperand(unsigned i) const
Definition: User.h:154
The access neither references nor modifies the value stored in memory.
Definition: AliasAnalysis.h:96
void getAAMetadata(AAMDNodes &N, bool Merge=false) const
Fills the AAMDNodes structure with AA metadata from this instruction.
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:404
void print(raw_ostream &OS) const
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
AliasAnalysis & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
Value * getRawDest() const
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:73
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
const AMDGPUAS & AS
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
bool isVolatile() const
void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
Definition: AsmWriter.cpp:3538
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Representation for a specific memory location.
Iterator for intrusive lists based on ilist_node.
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
static bool isStrongerThanMonotonic(AtomicOrdering ao)
void print(raw_ostream &OS) const
void copyValue(Value *From, Value *To)
This method should be used whenever a preexisting value in the program is copied or cloned...
Module.h This file contains the declarations for the Module class.
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
void add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:57
ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
void setPreservesAll()
Set by analyses that do not transform their input at all.
iterator end() const
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
Basic Alias true
This class wraps the llvm.memcpy/memmove intrinsics.
bool isVolatile() const
Return true if this is a store to a volatile memory location.
Definition: Instructions.h:339
AliasSet & getAliasSetForPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo)
Return the alias set that the specified pointer lives in.
AtomicOrdering getOrdering() const
Returns the ordering constraint of this store instruction.
Definition: Instructions.h:358
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
Establish a view to a call site for examination.
Definition: CallSite.h:687
#define I(x, y, z)
Definition: MD5.cpp:58
bool isVolatile() const
Return true if this alias set contains volatile loads or stores.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, AliasAnalysis &AA) const
Return true if the specified pointer "may" (or must) alias one of the members in the set...
Value * getLength() const
LLVM Value Representation.
Definition: Value.h:73
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:388
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
bool empty() const
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:389
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:133
void addUnknown(Instruction *I)
int * Ptr
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
void deleteValue(Value *PtrVal)
This method is used to remove a pointer value from the AliasSetTracker entirely.
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
Definition: Instruction.h:460