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