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