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