LLVM  10.0.0svn
AliasSetTracker.cpp
Go to the documentation of this file.
1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the AliasSetTracker and AliasSet classes.
10 //
11 //===----------------------------------------------------------------------===//
12 
16 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Config/llvm-config.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, bool SkipSizeUpdate) {
132  assert(!Entry.hasAliasSet() && "Entry already in set!");
133 
134  // Check to see if we have to downgrade to _may_ alias.
135  if (isMustAlias())
136  if (PointerRec *P = getSomePointer()) {
137  if (!KnownMustAlias) {
138  AliasAnalysis &AA = AST.getAliasAnalysis();
139  AliasResult Result = AA.alias(
140  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  }
146  assert(Result != NoAlias && "Cannot be part of must set!");
147  } else if (!SkipSizeUpdate)
148  P->updateSizeAndAAInfo(Size, AAInfo);
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 - If the specified pointer "may" (or must) alias one of the
189 /// members in the set return the appropriate AliasResult. Otherwise return
190 /// NoAlias.
191 ///
193  const AAMDNodes &AAInfo,
194  AliasAnalysis &AA) const {
195  if (AliasAny)
196  return MayAlias;
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 (AliasResult AR = AA.alias(
214  MemoryLocation(Ptr, Size, AAInfo),
215  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
216  return AR;
217 
218  // Check the unknown instructions...
219  if (!UnknownInsts.empty()) {
220  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
221  if (auto *Inst = getUnknownInst(i))
222  if (isModOrRefSet(
223  AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
224  return MayAlias;
225  }
226 
227  return NoAlias;
228 }
229 
231  AliasAnalysis &AA) const {
232 
233  if (AliasAny)
234  return true;
235 
236  assert(Inst->mayReadOrWriteMemory() &&
237  "Instruction must either read or write memory.");
238 
239  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
240  if (auto *UnknownInst = getUnknownInst(i)) {
241  const auto *C1 = dyn_cast<CallBase>(UnknownInst);
242  const auto *C2 = dyn_cast<CallBase>(Inst);
243  if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||
244  isModOrRefSet(AA.getModRefInfo(C2, C1)))
245  return true;
246  }
247  }
248 
249  for (iterator I = begin(), E = end(); I != E; ++I)
251  Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
252  return true;
253 
254  return false;
255 }
256 
258  if (AliasAny)
259  // May have collapses alias set
260  return nullptr;
261  if (begin() != end()) {
262  if (!UnknownInsts.empty())
263  // Another instruction found
264  return nullptr;
265  if (std::next(begin()) != end())
266  // Another instruction found
267  return nullptr;
268  Value *Addr = begin()->getValue();
269  assert(!Addr->user_empty() &&
270  "where's the instruction which added this pointer?");
271  if (std::next(Addr->user_begin()) != Addr->user_end())
272  // Another instruction found -- this is really restrictive
273  // TODO: generalize!
274  return nullptr;
275  return cast<Instruction>(*(Addr->user_begin()));
276  }
277  if (1 != UnknownInsts.size())
278  return nullptr;
279  return cast<Instruction>(UnknownInsts[0]);
280 }
281 
283  // Delete all the PointerRec entries.
284  for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
285  I != E; ++I)
286  I->second->eraseFromList();
287 
288  PointerMap.clear();
289 
290  // The alias sets should all be clear now.
291  AliasSets.clear();
292 }
293 
294 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
295 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
296 /// the pointer was found. MustAliasAll is updated to true/false if the pointer
297 /// is found to MustAlias all the sets it merged.
298 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
299  LocationSize Size,
300  const AAMDNodes &AAInfo,
301  bool &MustAliasAll) {
302  AliasSet *FoundSet = nullptr;
303  AliasResult AllAR = MustAlias;
304  for (iterator I = begin(), E = end(); I != E;) {
305  iterator Cur = I++;
306  if (Cur->Forward)
307  continue;
308 
309  AliasResult AR = Cur->aliasesPointer(Ptr, Size, AAInfo, AA);
310  if (AR == NoAlias)
311  continue;
312 
313  AllAR =
314  AliasResult(AllAR & AR); // Possible downgrade to May/Partial, even No
315 
316  if (!FoundSet) {
317  // If this is the first alias set ptr can go into, remember it.
318  FoundSet = &*Cur;
319  } else {
320  // Otherwise, we must merge the sets.
321  FoundSet->mergeSetIn(*Cur, *this);
322  }
323  }
324 
325  MustAliasAll = (AllAR == MustAlias);
326  return FoundSet;
327 }
328 
329 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
330  AliasSet *FoundSet = nullptr;
331  for (iterator I = begin(), E = end(); I != E;) {
332  iterator Cur = I++;
333  if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
334  continue;
335  if (!FoundSet) {
336  // If this is the first alias set ptr can go into, remember it.
337  FoundSet = &*Cur;
338  } else {
339  // Otherwise, we must merge the sets.
340  FoundSet->mergeSetIn(*Cur, *this);
341  }
342  }
343  return FoundSet;
344 }
345 
347 
348  Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
349  const LocationSize Size = MemLoc.Size;
350  const AAMDNodes &AAInfo = MemLoc.AATags;
351 
352  AliasSet::PointerRec &Entry = getEntryFor(Pointer);
353 
354  if (AliasAnyAS) {
355  // At this point, the AST is saturated, so we only have one active alias
356  // set. That means we already know which alias set we want to return, and
357  // just need to add the pointer to that set to keep the data structure
358  // consistent.
359  // This, of course, means that we will never need a merge here.
360  if (Entry.hasAliasSet()) {
361  Entry.updateSizeAndAAInfo(Size, AAInfo);
362  assert(Entry.getAliasSet(*this) == AliasAnyAS &&
363  "Entry in saturated AST must belong to only alias set");
364  } else {
365  AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
366  }
367  return *AliasAnyAS;
368  }
369 
370  bool MustAliasAll = false;
371  // Check to see if the pointer is already known.
372  if (Entry.hasAliasSet()) {
373  // If the size changed, we may need to merge several alias sets.
374  // Note that we can *not* return the result of mergeAliasSetsForPointer
375  // due to a quirk of alias analysis behavior. Since alias(undef, undef)
376  // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
377  // the right set for undef, even if it exists.
378  if (Entry.updateSizeAndAAInfo(Size, AAInfo))
379  mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll);
380  // Return the set!
381  return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
382  }
383 
384  if (AliasSet *AS =
385  mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll)) {
386  // Add it to the alias set it aliases.
387  AS->addPointer(*this, Entry, Size, AAInfo, MustAliasAll);
388  return *AS;
389  }
390 
391  // Otherwise create a new alias set to hold the loaded pointer.
392  AliasSets.push_back(new AliasSet());
393  AliasSets.back().addPointer(*this, Entry, Size, AAInfo, true);
394  return AliasSets.back();
395 }
396 
398  const AAMDNodes &AAInfo) {
399  addPointer(MemoryLocation(Ptr, Size, AAInfo), AliasSet::NoAccess);
400 }
401 
404  return addUnknown(LI);
405  addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
406 }
407 
410  return addUnknown(SI);
411  addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
412 }
413 
415  addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
416 }
417 
419  addPointer(MemoryLocation::getForDest(MSI), AliasSet::ModAccess);
420 }
421 
423  addPointer(MemoryLocation::getForDest(MTI), AliasSet::ModAccess);
424  addPointer(MemoryLocation::getForSource(MTI), AliasSet::RefAccess);
425 }
426 
428  if (isa<DbgInfoIntrinsic>(Inst))
429  return; // Ignore DbgInfo Intrinsics.
430 
431  if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
432  // These intrinsics will show up as affecting memory, but they are just
433  // markers.
434  switch (II->getIntrinsicID()) {
435  default:
436  break;
437  // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
438  case Intrinsic::assume:
439  case Intrinsic::sideeffect:
440  return;
441  }
442  }
443  if (!Inst->mayReadOrWriteMemory())
444  return; // doesn't alias anything
445 
446  if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
447  AS->addUnknownInst(Inst, AA);
448  return;
449  }
450  AliasSets.push_back(new AliasSet());
451  AliasSets.back().addUnknownInst(Inst, AA);
452 }
453 
455  // Dispatch to one of the other add methods.
456  if (LoadInst *LI = dyn_cast<LoadInst>(I))
457  return add(LI);
458  if (StoreInst *SI = dyn_cast<StoreInst>(I))
459  return add(SI);
460  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
461  return add(VAAI);
462  if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
463  return add(MSI);
464  if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
465  return add(MTI);
466 
467  // Handle all calls with known mod/ref sets genericall
468  if (auto *Call = dyn_cast<CallBase>(I))
469  if (Call->onlyAccessesArgMemory()) {
470  auto getAccessFromModRef = [](ModRefInfo MRI) {
471  if (isRefSet(MRI) && isModSet(MRI))
472  return AliasSet::ModRefAccess;
473  else if (isModSet(MRI))
474  return AliasSet::ModAccess;
475  else if (isRefSet(MRI))
476  return AliasSet::RefAccess;
477  else
478  return AliasSet::NoAccess;
479  };
480 
481  ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(Call));
482 
483  // Some intrinsics are marked as modifying memory for control flow
484  // modelling purposes, but don't actually modify any specific memory
485  // location.
486  using namespace PatternMatch;
487  if (Call->use_empty() &&
488  match(Call, m_Intrinsic<Intrinsic::invariant_start>()))
489  CallMask = clearMod(CallMask);
490 
491  for (auto IdxArgPair : enumerate(Call->args())) {
492  int ArgIdx = IdxArgPair.index();
493  const Value *Arg = IdxArgPair.value();
494  if (!Arg->getType()->isPointerTy())
495  continue;
496  MemoryLocation ArgLoc =
497  MemoryLocation::getForArgument(Call, ArgIdx, nullptr);
498  ModRefInfo ArgMask = AA.getArgModRefInfo(Call, ArgIdx);
499  ArgMask = intersectModRef(CallMask, ArgMask);
500  if (!isNoModRef(ArgMask))
501  addPointer(ArgLoc, getAccessFromModRef(ArgMask));
502  }
503  return;
504  }
505 
506  return addUnknown(I);
507 }
508 
510  for (auto &I : BB)
511  add(&I);
512 }
513 
515  assert(&AA == &AST.AA &&
516  "Merging AliasSetTracker objects with different Alias Analyses!");
517 
518  // Loop over all of the alias sets in AST, adding the pointers contained
519  // therein into the current alias sets. This can cause alias sets to be
520  // merged together in the current AST.
521  for (const AliasSet &AS : AST) {
522  if (AS.Forward)
523  continue; // Ignore forwarding alias sets
524 
525  // If there are any call sites in the alias set, add them to this AST.
526  for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
527  if (auto *Inst = AS.getUnknownInst(i))
528  add(Inst);
529 
530  // Loop over all of the pointers in this alias set.
531  for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
532  addPointer(
533  MemoryLocation(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo()),
534  (AliasSet::AccessLattice)AS.Access);
535  }
536 }
537 
539  assert(MSSA && L && "MSSA and L must be available");
540  for (const BasicBlock *BB : L->blocks())
541  if (auto *Accesses = MSSA->getBlockAccesses(BB))
542  for (auto &Access : *Accesses)
543  if (auto *MUD = dyn_cast<MemoryUseOrDef>(&Access))
544  add(MUD->getMemoryInst());
545 }
546 
547 // deleteValue method - This method is used to remove a pointer value from the
548 // AliasSetTracker entirely. It should be used when an instruction is deleted
549 // from the program to update the AST. If you don't use this, you would have
550 // dangling pointers to deleted instructions.
551 //
553  // First, look up the PointerRec for this pointer.
554  PointerMapType::iterator I = PointerMap.find_as(PtrVal);
555  if (I == PointerMap.end()) return; // Noop
556 
557  // If we found one, remove the pointer from the alias set it is in.
558  AliasSet::PointerRec *PtrValEnt = I->second;
559  AliasSet *AS = PtrValEnt->getAliasSet(*this);
560 
561  // Unlink and delete from the list of values.
562  PtrValEnt->eraseFromList();
563 
564  if (AS->Alias == AliasSet::SetMayAlias) {
565  AS->SetSize--;
566  TotalMayAliasSetSize--;
567  }
568 
569  // Stop using the alias set.
570  AS->dropRef(*this);
571 
572  PointerMap.erase(I);
573 }
574 
575 // copyValue - This method should be used whenever a preexisting value in the
576 // program is copied or cloned, introducing a new value. Note that it is ok for
577 // clients that use this method to introduce the same value multiple times: if
578 // the tracker already knows about a value, it will ignore the request.
579 //
581  // First, look up the PointerRec for this pointer.
582  PointerMapType::iterator I = PointerMap.find_as(From);
583  if (I == PointerMap.end())
584  return; // Noop
585  assert(I->second->hasAliasSet() && "Dead entry?");
586 
587  AliasSet::PointerRec &Entry = getEntryFor(To);
588  if (Entry.hasAliasSet()) return; // Already in the tracker!
589 
590  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
591  I = PointerMap.find_as(From);
592  // Add it to the alias set it aliases...
593  AliasSet *AS = I->second->getAliasSet(*this);
594  AS->addPointer(*this, Entry, I->second->getSize(), I->second->getAAInfo(),
595  true, true);
596 }
597 
598 AliasSet &AliasSetTracker::mergeAllAliasSets() {
599  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
600  "Full merge should happen once, when the saturation threshold is "
601  "reached");
602 
603  // Collect all alias sets, so that we can drop references with impunity
604  // without worrying about iterator invalidation.
605  std::vector<AliasSet *> ASVector;
606  ASVector.reserve(SaturationThreshold);
607  for (iterator I = begin(), E = end(); I != E; I++)
608  ASVector.push_back(&*I);
609 
610  // Copy all instructions and pointers into a new set, and forward all other
611  // sets to it.
612  AliasSets.push_back(new AliasSet());
613  AliasAnyAS = &AliasSets.back();
614  AliasAnyAS->Alias = AliasSet::SetMayAlias;
615  AliasAnyAS->Access = AliasSet::ModRefAccess;
616  AliasAnyAS->AliasAny = true;
617 
618  for (auto Cur : ASVector) {
619  // If Cur was already forwarding, just forward to the new AS instead.
620  AliasSet *FwdTo = Cur->Forward;
621  if (FwdTo) {
622  Cur->Forward = AliasAnyAS;
623  AliasAnyAS->addRef();
624  FwdTo->dropRef(*this);
625  continue;
626  }
627 
628  // Otherwise, perform the actual merge.
629  AliasAnyAS->mergeSetIn(*Cur, *this);
630  }
631 
632  return *AliasAnyAS;
633 }
634 
635 AliasSet &AliasSetTracker::addPointer(MemoryLocation Loc,
636  AliasSet::AccessLattice E) {
637  AliasSet &AS = getAliasSetFor(Loc);
638  AS.Access |= E;
639 
640  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
641  // The AST is now saturated. From here on, we conservatively consider all
642  // pointers to alias each-other.
643  return mergeAllAliasSets();
644  }
645 
646  return AS;
647 }
648 
649 //===----------------------------------------------------------------------===//
650 // AliasSet/AliasSetTracker Printing Support
651 //===----------------------------------------------------------------------===//
652 
653 void AliasSet::print(raw_ostream &OS) const {
654  OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
655  OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
656  switch (Access) {
657  case NoAccess: OS << "No access "; break;
658  case RefAccess: OS << "Ref "; break;
659  case ModAccess: OS << "Mod "; break;
660  case ModRefAccess: OS << "Mod/Ref "; break;
661  default: llvm_unreachable("Bad value for Access!");
662  }
663  if (Forward)
664  OS << " forwarding to " << (void*)Forward;
665 
666  if (!empty()) {
667  OS << "Pointers: ";
668  for (iterator I = begin(), E = end(); I != E; ++I) {
669  if (I != begin()) OS << ", ";
670  I.getPointer()->printAsOperand(OS << "(");
671  if (I.getSize() == LocationSize::unknown())
672  OS << ", unknown)";
673  else
674  OS << ", " << I.getSize() << ")";
675  }
676  }
677  if (!UnknownInsts.empty()) {
678  OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
679  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
680  if (i) OS << ", ";
681  if (auto *I = getUnknownInst(i)) {
682  if (I->hasName())
683  I->printAsOperand(OS);
684  else
685  I->print(OS);
686  }
687  }
688  }
689  OS << "\n";
690 }
691 
693  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
694  << PointerMap.size() << " pointer values.\n";
695  for (const AliasSet &AS : *this)
696  AS.print(OS);
697  OS << "\n";
698 }
699 
700 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
703 #endif
704 
705 //===----------------------------------------------------------------------===//
706 // ASTCallbackVH Class Implementation
707 //===----------------------------------------------------------------------===//
708 
709 void AliasSetTracker::ASTCallbackVH::deleted() {
710  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
711  AST->deleteValue(getValPtr());
712  // this now dangles!
713 }
714 
715 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
716  AST->copyValue(getValPtr(), V);
717 }
718 
719 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
720  : CallbackVH(V), AST(ast) {}
721 
722 AliasSetTracker::ASTCallbackVH &
723 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
724  return *this = ASTCallbackVH(V, AST);
725 }
726 
727 //===----------------------------------------------------------------------===//
728 // AliasSetPrinter Pass
729 //===----------------------------------------------------------------------===//
730 
731 namespace {
732 
733  class AliasSetPrinter : public FunctionPass {
734  AliasSetTracker *Tracker;
735 
736  public:
737  static char ID; // Pass identification, replacement for typeid
738 
739  AliasSetPrinter() : FunctionPass(ID) {
741  }
742 
743  void getAnalysisUsage(AnalysisUsage &AU) const override {
744  AU.setPreservesAll();
746  }
747 
748  bool runOnFunction(Function &F) override {
749  auto &AAWP = getAnalysis<AAResultsWrapperPass>();
750  Tracker = new AliasSetTracker(AAWP.getAAResults());
751  errs() << "Alias sets for function '" << F.getName() << "':\n";
752  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
753  Tracker->add(&*I);
754  Tracker->print(errs());
755  delete Tracker;
756  return false;
757  }
758  };
759 
760 } // end anonymous namespace
761 
762 char AliasSetPrinter::ID = 0;
763 
764 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
765  "Alias Set Printer", false, true)
767 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
768  "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:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:476
Define an iterator for alias sets... this is just a forward iterator.
bool user_empty() const
Definition: Value.h:383
void dump() const
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:84
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:247
print alias sets
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
F(f)
block Block Frequency true
An instruction for reading from memory.
Definition: Instructions.h:167
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:47
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
inst_iterator inst_begin(Function *F)
Definition: InstIterator.h:131
bool isMustAlias() const
void initializeAliasSetPrinterPass(PassRegistry &)
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
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 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:320
bool isStrongerThanMonotonic(AtomicOrdering ao)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
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:432
void print(raw_ostream &OS) const
unsigned const MachineRegisterInfo * MRI
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:223
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:4278
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
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...
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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:4355
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.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
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:90
AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo, AliasAnalysis &AA) const
If the specified pointer "may" (or must) alias one of the members in the set return the appropriate A...
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...
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:243
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:643
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental.guard intrinsic.
Definition: GuardUtils.cpp:17
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
iterator end() const
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:372
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:214
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
#define I(x, y, z)
Definition: MD5.cpp:58
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:332
uint32_t Size
Definition: Profile.cpp:46
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:395
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:45
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
bool empty() const
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
inst_iterator inst_end(Function *F)
Definition: InstIterator.h:132
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...
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
bool use_empty() const
Definition: Value.h:342
void deleteValue(Value *PtrVal)
This method is used to remove a pointer value from the AliasSetTracker entirely.
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:1500
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
user_iterator user_end()
Definition: Value.h:403
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
Definition: Instruction.h:532
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)