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