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  }
118 
119  if (AS->Alias == AliasSet::SetMayAlias)
120  TotalMayAliasSetSize -= AS->size();
121 
122  AliasSets.erase(AS);
123 }
124 
125 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
126  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
127  AST.removeAliasSet(this);
128 }
129 
130 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
131  LocationSize Size, const AAMDNodes &AAInfo,
132  bool KnownMustAlias) {
133  assert(!Entry.hasAliasSet() && "Entry already in set!");
134 
135  // Check to see if we have to downgrade to _may_ alias.
136  if (isMustAlias() && !KnownMustAlias)
137  if (PointerRec *P = getSomePointer()) {
138  AliasAnalysis &AA = AST.getAliasAnalysis();
140  AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
141  MemoryLocation(Entry.getValue(), Size, AAInfo));
142  if (Result != MustAlias) {
143  Alias = SetMayAlias;
144  AST.TotalMayAliasSetSize += size();
145  } else {
146  // First entry of must alias must have maximum size!
147  P->updateSizeAndAAInfo(Size, AAInfo);
148  }
149  assert(Result != NoAlias && "Cannot be part of must set!");
150  }
151 
152  Entry.setAliasSet(this);
153  Entry.updateSizeAndAAInfo(Size, AAInfo);
154 
155  // Add it to the end of the list...
156  ++SetSize;
157  assert(*PtrListEnd == nullptr && "End of list is not null?");
158  *PtrListEnd = &Entry;
159  PtrListEnd = Entry.setPrevInList(PtrListEnd);
160  assert(*PtrListEnd == nullptr && "End of list is not null?");
161  // Entry points to alias set.
162  addRef();
163 
164  if (Alias == SetMayAlias)
165  AST.TotalMayAliasSetSize++;
166 }
167 
168 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
169  if (UnknownInsts.empty())
170  addRef();
171  UnknownInsts.emplace_back(I);
172 
173  // Guards are marked as modifying memory for control flow modelling purposes,
174  // but don't actually modify any specific memory location.
175  using namespace PatternMatch;
176  bool MayWriteMemory = I->mayWriteToMemory() && !isGuard(I) &&
177  !(I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()));
178  if (!MayWriteMemory) {
179  Alias = SetMayAlias;
180  Access |= RefAccess;
181  return;
182  }
183 
184  // FIXME: This should use mod/ref information to make this not suck so bad
185  Alias = SetMayAlias;
186  Access = ModRefAccess;
187 }
188 
189 /// aliasesPointer - Return true if the specified pointer "may" (or must)
190 /// alias one of the members in the set.
191 ///
193  const AAMDNodes &AAInfo,
194  AliasAnalysis &AA) const {
195  if (AliasAny)
196  return true;
197 
198  if (Alias == SetMustAlias) {
199  assert(UnknownInsts.empty() && "Illegal must alias set!");
200 
201  // If this is a set of MustAliases, only check to see if the pointer aliases
202  // SOME value in the set.
203  PointerRec *SomePtr = getSomePointer();
204  assert(SomePtr && "Empty must-alias set??");
205  return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
206  SomePtr->getAAInfo()),
207  MemoryLocation(Ptr, Size, AAInfo));
208  }
209 
210  // If this is a may-alias set, we have to check all of the pointers in the set
211  // to be sure it doesn't alias the set...
212  for (iterator I = begin(), E = end(); I != E; ++I)
213  if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
214  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
215  return true;
216 
217  // Check the unknown instructions...
218  if (!UnknownInsts.empty()) {
219  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
220  if (auto *Inst = getUnknownInst(i))
221  if (isModOrRefSet(
222  AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
223  return true;
224  }
225 
226  return false;
227 }
228 
230  AliasAnalysis &AA) const {
231 
232  if (AliasAny)
233  return true;
234 
235  if (!Inst->mayReadOrWriteMemory())
236  return false;
237 
238  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
239  if (auto *UnknownInst = getUnknownInst(i)) {
240  ImmutableCallSite C1(UnknownInst), C2(Inst);
241  if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||
242  isModOrRefSet(AA.getModRefInfo(C2, C1)))
243  return true;
244  }
245  }
246 
247  for (iterator I = begin(), E = end(); I != E; ++I)
249  Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
250  return true;
251 
252  return false;
253 }
254 
256  if (AliasAny)
257  // May have collapses alias set
258  return nullptr;
259  if (begin() != end()) {
260  if (!UnknownInsts.empty())
261  // Another instruction found
262  return nullptr;
263  if (std::next(begin()) != end())
264  // Another instruction found
265  return nullptr;
266  Value *Addr = begin()->getValue();
267  assert(!Addr->user_empty() &&
268  "where's the instruction which added this pointer?");
269  if (std::next(Addr->user_begin()) != Addr->user_end())
270  // Another instruction found -- this is really restrictive
271  // TODO: generalize!
272  return nullptr;
273  return cast<Instruction>(*(Addr->user_begin()));
274  }
275  if (1 != UnknownInsts.size())
276  return nullptr;
277  return cast<Instruction>(UnknownInsts[0]);
278 }
279 
281  // Delete all the PointerRec entries.
282  for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
283  I != E; ++I)
284  I->second->eraseFromList();
285 
286  PointerMap.clear();
287 
288  // The alias sets should all be clear now.
289  AliasSets.clear();
290 }
291 
292 
293 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
294 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
295 /// the pointer was found.
296 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
297  LocationSize Size,
298  const AAMDNodes &AAInfo) {
299  AliasSet *FoundSet = nullptr;
300  for (iterator I = begin(), E = end(); I != E;) {
301  iterator Cur = I++;
302  if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
303 
304  if (!FoundSet) { // If this is the first alias set ptr can go into.
305  FoundSet = &*Cur; // Remember it.
306  } else { // Otherwise, we must merge the sets.
307  FoundSet->mergeSetIn(*Cur, *this); // Merge in contents.
308  }
309  }
310 
311  return FoundSet;
312 }
313 
315  for (const AliasSet &AS : *this)
316  if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
317  return true;
318  return false;
319 }
320 
321 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
322  AliasSet *FoundSet = nullptr;
323  for (iterator I = begin(), E = end(); I != E;) {
324  iterator Cur = I++;
325  if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
326  continue;
327  if (!FoundSet) // If this is the first alias set ptr can go into.
328  FoundSet = &*Cur; // Remember it.
329  else if (!Cur->Forward) // Otherwise, we must merge the sets.
330  FoundSet->mergeSetIn(*Cur, *this); // Merge in contents.
331  }
332  return FoundSet;
333 }
334 
336 
337  Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
338  const LocationSize Size = MemLoc.Size;
339  const AAMDNodes &AAInfo = MemLoc.AATags;
340 
341  AliasSet::PointerRec &Entry = getEntryFor(Pointer);
342 
343  if (AliasAnyAS) {
344  // At this point, the AST is saturated, so we only have one active alias
345  // set. That means we already know which alias set we want to return, and
346  // just need to add the pointer to that set to keep the data structure
347  // consistent.
348  // This, of course, means that we will never need a merge here.
349  if (Entry.hasAliasSet()) {
350  Entry.updateSizeAndAAInfo(Size, AAInfo);
351  assert(Entry.getAliasSet(*this) == AliasAnyAS &&
352  "Entry in saturated AST must belong to only alias set");
353  } else {
354  AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
355  }
356  return *AliasAnyAS;
357  }
358 
359  // Check to see if the pointer is already known.
360  if (Entry.hasAliasSet()) {
361  // If the size changed, we may need to merge several alias sets.
362  // Note that we can *not* return the result of mergeAliasSetsForPointer
363  // due to a quirk of alias analysis behavior. Since alias(undef, undef)
364  // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
365  // the right set for undef, even if it exists.
366  if (Entry.updateSizeAndAAInfo(Size, AAInfo))
367  mergeAliasSetsForPointer(Pointer, Size, AAInfo);
368  // Return the set!
369  return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
370  }
371 
372  if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
373  // Add it to the alias set it aliases.
374  AS->addPointer(*this, Entry, Size, AAInfo);
375  return *AS;
376  }
377 
378  // Otherwise create a new alias set to hold the loaded pointer.
379  AliasSets.push_back(new AliasSet());
380  AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
381  return AliasSets.back();
382 }
383 
385  const AAMDNodes &AAInfo) {
386  addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
387 }
388 
391  return addUnknown(LI);
392  addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
393 }
394 
397  return addUnknown(SI);
398  addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
399 }
400 
402  addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
403 }
404 
406  addPointer(MemoryLocation::getForDest(MSI), AliasSet::ModAccess);
407 }
408 
410  addPointer(MemoryLocation::getForDest(MTI), AliasSet::ModAccess);
411  addPointer(MemoryLocation::getForSource(MTI), AliasSet::RefAccess);
412 }
413 
415  if (isa<DbgInfoIntrinsic>(Inst))
416  return; // Ignore DbgInfo Intrinsics.
417 
418  if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
419  // These intrinsics will show up as affecting memory, but they are just
420  // markers.
421  switch (II->getIntrinsicID()) {
422  default:
423  break;
424  // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
425  case Intrinsic::assume:
426  case Intrinsic::sideeffect:
427  return;
428  }
429  }
430  if (!Inst->mayReadOrWriteMemory())
431  return; // doesn't alias anything
432 
433  AliasSet *AS = findAliasSetForUnknownInst(Inst);
434  if (AS) {
435  AS->addUnknownInst(Inst, AA);
436  return;
437  }
438  AliasSets.push_back(new AliasSet());
439  AS = &AliasSets.back();
440  AS->addUnknownInst(Inst, AA);
441 }
442 
444  // Dispatch to one of the other add methods.
445  if (LoadInst *LI = dyn_cast<LoadInst>(I))
446  return add(LI);
447  if (StoreInst *SI = dyn_cast<StoreInst>(I))
448  return add(SI);
449  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
450  return add(VAAI);
451  if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
452  return add(MSI);
453  if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
454  return add(MTI);
455 
456  // Handle all calls with known mod/ref sets genericall
457  CallSite CS(I);
458  if (CS && CS.onlyAccessesArgMemory()) {
459  auto getAccessFromModRef = [](ModRefInfo MRI) {
460  if (isRefSet(MRI) && isModSet(MRI))
461  return AliasSet::ModRefAccess;
462  else if (isModSet(MRI))
463  return AliasSet::ModAccess;
464  else if (isRefSet(MRI))
465  return AliasSet::RefAccess;
466  else
467  return AliasSet::NoAccess;
468 
469  };
470 
471  ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(CS));
472 
473  // Some intrinsics are marked as modifying memory for control flow
474  // modelling purposes, but don't actually modify any specific memory
475  // location.
476  using namespace PatternMatch;
477  if (I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()))
478  CallMask = clearMod(CallMask);
479 
480  for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
481  const Value *Arg = *AI;
482  if (!Arg->getType()->isPointerTy())
483  continue;
484  unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
486  nullptr);
487  ModRefInfo ArgMask = AA.getArgModRefInfo(CS, ArgIdx);
488  ArgMask = intersectModRef(CallMask, ArgMask);
489  if (!isNoModRef(ArgMask))
490  addPointer(ArgLoc, getAccessFromModRef(ArgMask));
491  }
492  return;
493  }
494 
495  return addUnknown(I);
496 }
497 
499  for (auto &I : BB)
500  add(&I);
501 }
502 
504  assert(&AA == &AST.AA &&
505  "Merging AliasSetTracker objects with different Alias Analyses!");
506 
507  // Loop over all of the alias sets in AST, adding the pointers contained
508  // therein into the current alias sets. This can cause alias sets to be
509  // merged together in the current AST.
510  for (const AliasSet &AS : AST) {
511  if (AS.Forward)
512  continue; // Ignore forwarding alias sets
513 
514  // If there are any call sites in the alias set, add them to this AST.
515  for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
516  if (auto *Inst = AS.getUnknownInst(i))
517  add(Inst);
518 
519  // Loop over all of the pointers in this alias set.
520  for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
521  addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
522  (AliasSet::AccessLattice)AS.Access);
523  }
524 }
525 
526 // deleteValue method - This method is used to remove a pointer value from the
527 // AliasSetTracker entirely. It should be used when an instruction is deleted
528 // from the program to update the AST. If you don't use this, you would have
529 // dangling pointers to deleted instructions.
530 //
532  // First, look up the PointerRec for this pointer.
533  PointerMapType::iterator I = PointerMap.find_as(PtrVal);
534  if (I == PointerMap.end()) return; // Noop
535 
536  // If we found one, remove the pointer from the alias set it is in.
537  AliasSet::PointerRec *PtrValEnt = I->second;
538  AliasSet *AS = PtrValEnt->getAliasSet(*this);
539 
540  // Unlink and delete from the list of values.
541  PtrValEnt->eraseFromList();
542 
543  if (AS->Alias == AliasSet::SetMayAlias) {
544  AS->SetSize--;
545  TotalMayAliasSetSize--;
546  }
547 
548  // Stop using the alias set.
549  AS->dropRef(*this);
550 
551  PointerMap.erase(I);
552 }
553 
554 // copyValue - This method should be used whenever a preexisting value in the
555 // program is copied or cloned, introducing a new value. Note that it is ok for
556 // clients that use this method to introduce the same value multiple times: if
557 // the tracker already knows about a value, it will ignore the request.
558 //
560  // First, look up the PointerRec for this pointer.
561  PointerMapType::iterator I = PointerMap.find_as(From);
562  if (I == PointerMap.end())
563  return; // Noop
564  assert(I->second->hasAliasSet() && "Dead entry?");
565 
566  AliasSet::PointerRec &Entry = getEntryFor(To);
567  if (Entry.hasAliasSet()) return; // Already in the tracker!
568 
569  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
570  I = PointerMap.find_as(From);
571  // Add it to the alias set it aliases...
572  AliasSet *AS = I->second->getAliasSet(*this);
573  AS->addPointer(*this, Entry, I->second->getSize(),
574  I->second->getAAInfo(),
575  true);
576 }
577 
578 AliasSet &AliasSetTracker::mergeAllAliasSets() {
579  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
580  "Full merge should happen once, when the saturation threshold is "
581  "reached");
582 
583  // Collect all alias sets, so that we can drop references with impunity
584  // without worrying about iterator invalidation.
585  std::vector<AliasSet *> ASVector;
586  ASVector.reserve(SaturationThreshold);
587  for (iterator I = begin(), E = end(); I != E; I++)
588  ASVector.push_back(&*I);
589 
590  // Copy all instructions and pointers into a new set, and forward all other
591  // sets to it.
592  AliasSets.push_back(new AliasSet());
593  AliasAnyAS = &AliasSets.back();
594  AliasAnyAS->Alias = AliasSet::SetMayAlias;
595  AliasAnyAS->Access = AliasSet::ModRefAccess;
596  AliasAnyAS->AliasAny = true;
597 
598  for (auto Cur : ASVector) {
599  // If Cur was already forwarding, just forward to the new AS instead.
600  AliasSet *FwdTo = Cur->Forward;
601  if (FwdTo) {
602  Cur->Forward = AliasAnyAS;
603  AliasAnyAS->addRef();
604  FwdTo->dropRef(*this);
605  continue;
606  }
607 
608  // Otherwise, perform the actual merge.
609  AliasAnyAS->mergeSetIn(*Cur, *this);
610  }
611 
612  return *AliasAnyAS;
613 }
614 
615 AliasSet &AliasSetTracker::addPointer(Value *P, LocationSize Size,
616  const AAMDNodes &AAInfo,
617  AliasSet::AccessLattice E) {
618  AliasSet &AS = getAliasSetFor(MemoryLocation(P, Size, AAInfo));
619  AS.Access |= E;
620 
621  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
622  // The AST is now saturated. From here on, we conservatively consider all
623  // pointers to alias each-other.
624  return mergeAllAliasSets();
625  }
626 
627  return AS;
628 }
629 
630 //===----------------------------------------------------------------------===//
631 // AliasSet/AliasSetTracker Printing Support
632 //===----------------------------------------------------------------------===//
633 
634 void AliasSet::print(raw_ostream &OS) const {
635  OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
636  OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
637  switch (Access) {
638  case NoAccess: OS << "No access "; break;
639  case RefAccess: OS << "Ref "; break;
640  case ModAccess: OS << "Mod "; break;
641  case ModRefAccess: OS << "Mod/Ref "; break;
642  default: llvm_unreachable("Bad value for Access!");
643  }
644  if (Forward)
645  OS << " forwarding to " << (void*)Forward;
646 
647  if (!empty()) {
648  OS << "Pointers: ";
649  for (iterator I = begin(), E = end(); I != E; ++I) {
650  if (I != begin()) OS << ", ";
651  I.getPointer()->printAsOperand(OS << "(");
652  if (I.getSize() == LocationSize::unknown())
653  OS << ", unknown)";
654  else
655  OS << ", " << I.getSize() << ")";
656  }
657  }
658  if (!UnknownInsts.empty()) {
659  OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
660  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
661  if (i) OS << ", ";
662  if (auto *I = getUnknownInst(i)) {
663  if (I->hasName())
664  I->printAsOperand(OS);
665  else
666  I->print(OS);
667  }
668  }
669  }
670  OS << "\n";
671 }
672 
674  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
675  << PointerMap.size() << " pointer values.\n";
676  for (const AliasSet &AS : *this)
677  AS.print(OS);
678  OS << "\n";
679 }
680 
681 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
684 #endif
685 
686 //===----------------------------------------------------------------------===//
687 // ASTCallbackVH Class Implementation
688 //===----------------------------------------------------------------------===//
689 
690 void AliasSetTracker::ASTCallbackVH::deleted() {
691  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
692  AST->deleteValue(getValPtr());
693  // this now dangles!
694 }
695 
696 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
697  AST->copyValue(getValPtr(), V);
698 }
699 
700 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
701  : CallbackVH(V), AST(ast) {}
702 
703 AliasSetTracker::ASTCallbackVH &
704 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
705  return *this = ASTCallbackVH(V, AST);
706 }
707 
708 //===----------------------------------------------------------------------===//
709 // AliasSetPrinter Pass
710 //===----------------------------------------------------------------------===//
711 
712 namespace {
713 
714  class AliasSetPrinter : public FunctionPass {
715  AliasSetTracker *Tracker;
716 
717  public:
718  static char ID; // Pass identification, replacement for typeid
719 
720  AliasSetPrinter() : FunctionPass(ID) {
722  }
723 
724  void getAnalysisUsage(AnalysisUsage &AU) const override {
725  AU.setPreservesAll();
727  }
728 
729  bool runOnFunction(Function &F) override {
730  auto &AAWP = getAnalysis<AAResultsWrapperPass>();
731  Tracker = new AliasSetTracker(AAWP.getAAResults());
732  errs() << "Alias sets for function '" << F.getName() << "':\n";
733  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
734  Tracker->add(&*I);
735  Tracker->print(errs());
736  delete Tracker;
737  return false;
738  }
739  };
740 
741 } // end anonymous namespace
742 
743 char AliasSetPrinter::ID = 0;
744 
745 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
746  "Alias Set Printer", false, true)
748 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
749  "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.
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.
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 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
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:410
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:4120
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:4197
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:224
Establish a view to a call site for examination.
Definition: CallSite.h:714
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:518
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)