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  case Intrinsic::sideeffect:
440  return;
441  }
442  }
443  if (!Inst->mayReadOrWriteMemory())
444  return; // doesn't alias anything
445 
446  AliasSet *AS = findAliasSetForUnknownInst(Inst);
447  if (AS) {
448  AS->addUnknownInst(Inst, AA);
449  return;
450  }
451  AliasSets.push_back(new AliasSet());
452  AS = &AliasSets.back();
453  AS->addUnknownInst(Inst, AA);
454 }
455 
457  // Dispatch to one of the other add methods.
458  if (LoadInst *LI = dyn_cast<LoadInst>(I))
459  return add(LI);
460  if (StoreInst *SI = dyn_cast<StoreInst>(I))
461  return add(SI);
462  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
463  return add(VAAI);
464  if (MemSetInst *MSI = dyn_cast<MemSetInst>(I))
465  return add(MSI);
466  if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(I))
467  return add(MTI);
468  return addUnknown(I);
469 }
470 
472  for (auto &I : BB)
473  add(&I);
474 }
475 
477  assert(&AA == &AST.AA &&
478  "Merging AliasSetTracker objects with different Alias Analyses!");
479 
480  // Loop over all of the alias sets in AST, adding the pointers contained
481  // therein into the current alias sets. This can cause alias sets to be
482  // merged together in the current AST.
483  for (const AliasSet &AS : AST) {
484  if (AS.Forward)
485  continue; // Ignore forwarding alias sets
486 
487  // If there are any call sites in the alias set, add them to this AST.
488  for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
489  if (auto *Inst = AS.getUnknownInst(i))
490  add(Inst);
491 
492  // Loop over all of the pointers in this alias set.
493  for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
494  AliasSet &NewAS =
495  addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
496  (AliasSet::AccessLattice)AS.Access);
497  if (AS.isVolatile()) NewAS.setVolatile();
498  }
499  }
500 }
501 
502 // deleteValue method - This method is used to remove a pointer value from the
503 // AliasSetTracker entirely. It should be used when an instruction is deleted
504 // from the program to update the AST. If you don't use this, you would have
505 // dangling pointers to deleted instructions.
506 //
508  // First, look up the PointerRec for this pointer.
509  PointerMapType::iterator I = PointerMap.find_as(PtrVal);
510  if (I == PointerMap.end()) return; // Noop
511 
512  // If we found one, remove the pointer from the alias set it is in.
513  AliasSet::PointerRec *PtrValEnt = I->second;
514  AliasSet *AS = PtrValEnt->getAliasSet(*this);
515 
516  // Unlink and delete from the list of values.
517  PtrValEnt->eraseFromList();
518 
519  if (AS->Alias == AliasSet::SetMayAlias) {
520  AS->SetSize--;
521  TotalMayAliasSetSize--;
522  }
523 
524  // Stop using the alias set.
525  AS->dropRef(*this);
526 
527  PointerMap.erase(I);
528 }
529 
530 // copyValue - This method should be used whenever a preexisting value in the
531 // program is copied or cloned, introducing a new value. Note that it is ok for
532 // clients that use this method to introduce the same value multiple times: if
533 // the tracker already knows about a value, it will ignore the request.
534 //
536  // First, look up the PointerRec for this pointer.
537  PointerMapType::iterator I = PointerMap.find_as(From);
538  if (I == PointerMap.end())
539  return; // Noop
540  assert(I->second->hasAliasSet() && "Dead entry?");
541 
542  AliasSet::PointerRec &Entry = getEntryFor(To);
543  if (Entry.hasAliasSet()) return; // Already in the tracker!
544 
545  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
546  I = PointerMap.find_as(From);
547  // Add it to the alias set it aliases...
548  AliasSet *AS = I->second->getAliasSet(*this);
549  AS->addPointer(*this, Entry, I->second->getSize(),
550  I->second->getAAInfo(),
551  true);
552 }
553 
554 AliasSet &AliasSetTracker::mergeAllAliasSets() {
555  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
556  "Full merge should happen once, when the saturation threshold is "
557  "reached");
558 
559  // Collect all alias sets, so that we can drop references with impunity
560  // without worrying about iterator invalidation.
561  std::vector<AliasSet *> ASVector;
562  ASVector.reserve(SaturationThreshold);
563  for (iterator I = begin(), E = end(); I != E; I++)
564  ASVector.push_back(&*I);
565 
566  // Copy all instructions and pointers into a new set, and forward all other
567  // sets to it.
568  AliasSets.push_back(new AliasSet());
569  AliasAnyAS = &AliasSets.back();
570  AliasAnyAS->Alias = AliasSet::SetMayAlias;
571  AliasAnyAS->Access = AliasSet::ModRefAccess;
572  AliasAnyAS->AliasAny = true;
573 
574  for (auto Cur : ASVector) {
575 
576  // If Cur was already forwarding, just forward to the new AS instead.
577  AliasSet *FwdTo = Cur->Forward;
578  if (FwdTo) {
579  Cur->Forward = AliasAnyAS;
580  AliasAnyAS->addRef();
581  FwdTo->dropRef(*this);
582  continue;
583  }
584 
585  // Otherwise, perform the actual merge.
586  AliasAnyAS->mergeSetIn(*Cur, *this);
587  }
588 
589  return *AliasAnyAS;
590 }
591 
592 AliasSet &AliasSetTracker::addPointer(Value *P, uint64_t Size,
593  const AAMDNodes &AAInfo,
594  AliasSet::AccessLattice E) {
595  AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo);
596  AS.Access |= E;
597 
598  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
599  // The AST is now saturated. From here on, we conservatively consider all
600  // pointers to alias each-other.
601  return mergeAllAliasSets();
602  }
603 
604  return AS;
605 }
606 
607 //===----------------------------------------------------------------------===//
608 // AliasSet/AliasSetTracker Printing Support
609 //===----------------------------------------------------------------------===//
610 
611 void AliasSet::print(raw_ostream &OS) const {
612  OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
613  OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
614  switch (Access) {
615  case NoAccess: OS << "No access "; break;
616  case RefAccess: OS << "Ref "; break;
617  case ModAccess: OS << "Mod "; break;
618  case ModRefAccess: OS << "Mod/Ref "; break;
619  default: llvm_unreachable("Bad value for Access!");
620  }
621  if (isVolatile()) OS << "[volatile] ";
622  if (Forward)
623  OS << " forwarding to " << (void*)Forward;
624 
625  if (!empty()) {
626  OS << "Pointers: ";
627  for (iterator I = begin(), E = end(); I != E; ++I) {
628  if (I != begin()) OS << ", ";
629  I.getPointer()->printAsOperand(OS << "(");
630  OS << ", " << I.getSize() << ")";
631  }
632  }
633  if (!UnknownInsts.empty()) {
634  OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
635  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
636  if (i) OS << ", ";
637  if (auto *I = getUnknownInst(i))
638  I->printAsOperand(OS);
639  }
640  }
641  OS << "\n";
642 }
643 
645  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
646  << PointerMap.size() << " pointer values.\n";
647  for (const AliasSet &AS : *this)
648  AS.print(OS);
649  OS << "\n";
650 }
651 
652 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
655 #endif
656 
657 //===----------------------------------------------------------------------===//
658 // ASTCallbackVH Class Implementation
659 //===----------------------------------------------------------------------===//
660 
661 void AliasSetTracker::ASTCallbackVH::deleted() {
662  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
663  AST->deleteValue(getValPtr());
664  // this now dangles!
665 }
666 
667 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
668  AST->copyValue(getValPtr(), V);
669 }
670 
671 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
672  : CallbackVH(V), AST(ast) {}
673 
674 AliasSetTracker::ASTCallbackVH &
675 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
676  return *this = ASTCallbackVH(V, AST);
677 }
678 
679 //===----------------------------------------------------------------------===//
680 // AliasSetPrinter Pass
681 //===----------------------------------------------------------------------===//
682 
683 namespace {
684 
685  class AliasSetPrinter : public FunctionPass {
686  AliasSetTracker *Tracker;
687 
688  public:
689  static char ID; // Pass identification, replacement for typeid
690 
691  AliasSetPrinter() : FunctionPass(ID) {
693  }
694 
695  void getAnalysisUsage(AnalysisUsage &AU) const override {
696  AU.setPreservesAll();
698  }
699 
700  bool runOnFunction(Function &F) override {
701  auto &AAWP = getAnalysis<AAResultsWrapperPass>();
702  Tracker = new AliasSetTracker(AAWP.getAAResults());
703  errs() << "Alias sets for function '" << F.getName() << "':\n";
704  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
705  Tracker->add(&*I);
706  Tracker->print(errs());
707  delete Tracker;
708  return false;
709  }
710  };
711 
712 } // end anonymous namespace
713 
714 char AliasSetPrinter::ID = 0;
715 
716 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
717  "Alias Set Printer", false, true)
719 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
720  "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
Value * getLength() const
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
bool isStrongerThanMonotonic(AtomicOrdering ao)
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.
static bool runOnFunction(Function &F, bool PostInlining)
#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...
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:3573
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
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
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:220
Establish a view to a call site for examination.
Definition: CallSite.h:713
#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...
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:386
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
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...
Value * getRawDest() const
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:495