LLVM  14.0.0git
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"
18 #include "llvm/Config/llvm-config.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/InstIterator.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/PassManager.h"
27 #include "llvm/IR/PatternMatch.h"
28 #include "llvm/IR/Value.h"
29 #include "llvm/InitializePasses.h"
30 #include "llvm/Pass.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
37 
38 using namespace llvm;
39 
40 static cl::opt<unsigned>
41  SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
42  cl::init(250),
43  cl::desc("The maximum number of pointers may-alias "
44  "sets may contain before degradation"));
45 
46 /// mergeSetIn - Merge the specified alias set into this alias set.
47 ///
49  assert(!AS.Forward && "Alias set is already forwarding!");
50  assert(!Forward && "This set is a forwarding set!!");
51 
52  bool WasMustAlias = (Alias == SetMustAlias);
53  // Update the alias and access types of this set...
54  Access |= AS.Access;
55  Alias |= AS.Alias;
56 
57  if (Alias == SetMustAlias) {
58  // Check that these two merged sets really are must aliases. Since both
59  // used to be must-alias sets, we can just check any pointer from each set
60  // for aliasing.
61  AliasAnalysis &AA = AST.getAliasAnalysis();
62  PointerRec *L = getSomePointer();
63  PointerRec *R = AS.getSomePointer();
64 
65  // If the pointers are not a must-alias pair, this set becomes a may alias.
66  if (!AA.isMustAlias(
67  MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
68  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())))
69  Alias = SetMayAlias;
70  }
71 
72  if (Alias == SetMayAlias) {
73  if (WasMustAlias)
74  AST.TotalMayAliasSetSize += size();
75  if (AS.Alias == SetMustAlias)
76  AST.TotalMayAliasSetSize += AS.size();
77  }
78 
79  bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
80  if (UnknownInsts.empty()) { // Merge call sites...
81  if (ASHadUnknownInsts) {
82  std::swap(UnknownInsts, AS.UnknownInsts);
83  addRef();
84  }
85  } else if (ASHadUnknownInsts) {
86  llvm::append_range(UnknownInsts, AS.UnknownInsts);
87  AS.UnknownInsts.clear();
88  }
89 
90  AS.Forward = this; // Forward across AS now...
91  addRef(); // AS is now pointing to us...
92 
93  // Merge the list of constituent pointers...
94  if (AS.PtrList) {
95  SetSize += AS.size();
96  AS.SetSize = 0;
97  *PtrListEnd = AS.PtrList;
98  AS.PtrList->setPrevInList(PtrListEnd);
99  PtrListEnd = AS.PtrListEnd;
100 
101  AS.PtrList = nullptr;
102  AS.PtrListEnd = &AS.PtrList;
103  assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
104  }
105  if (ASHadUnknownInsts)
106  AS.dropRef(AST);
107 }
108 
109 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
110  if (AliasSet *Fwd = AS->Forward) {
111  Fwd->dropRef(*this);
112  AS->Forward = nullptr;
113  } else // Update TotalMayAliasSetSize only if not forwarding.
114  if (AS->Alias == AliasSet::SetMayAlias)
115  TotalMayAliasSetSize -= AS->size();
116 
117  AliasSets.erase(AS);
118  // If we've removed the saturated alias set, set saturated marker back to
119  // nullptr and ensure this tracker is empty.
120  if (AS == AliasAnyAS) {
121  AliasAnyAS = nullptr;
122  assert(AliasSets.empty() && "Tracker not empty");
123  }
124 }
125 
126 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
127  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
128  AST.removeAliasSet(this);
129 }
130 
131 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
132  LocationSize Size, const AAMDNodes &AAInfo,
133  bool KnownMustAlias, bool SkipSizeUpdate) {
134  assert(!Entry.hasAliasSet() && "Entry already in set!");
135 
136  // Check to see if we have to downgrade to _may_ alias.
137  if (isMustAlias())
138  if (PointerRec *P = getSomePointer()) {
139  if (!KnownMustAlias) {
140  AliasAnalysis &AA = AST.getAliasAnalysis();
141  AliasResult Result = AA.alias(
142  MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
143  MemoryLocation(Entry.getValue(), Size, AAInfo));
144  if (Result != AliasResult::MustAlias) {
145  Alias = SetMayAlias;
146  AST.TotalMayAliasSetSize += size();
147  }
148  assert(Result != AliasResult::NoAlias && "Cannot be part of must set!");
149  } else if (!SkipSizeUpdate)
150  P->updateSizeAndAAInfo(Size, AAInfo);
151  }
152 
153  Entry.setAliasSet(this);
154  Entry.updateSizeAndAAInfo(Size, AAInfo);
155 
156  // Add it to the end of the list...
157  ++SetSize;
158  assert(*PtrListEnd == nullptr && "End of list is not null?");
159  *PtrListEnd = &Entry;
160  PtrListEnd = Entry.setPrevInList(PtrListEnd);
161  assert(*PtrListEnd == nullptr && "End of list is not null?");
162  // Entry points to alias set.
163  addRef();
164 
165  if (Alias == SetMayAlias)
166  AST.TotalMayAliasSetSize++;
167 }
168 
169 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
170  if (UnknownInsts.empty())
171  addRef();
172  UnknownInsts.emplace_back(I);
173 
174  // Guards are marked as modifying memory for control flow modelling purposes,
175  // but don't actually modify any specific memory location.
176  using namespace PatternMatch;
177  bool MayWriteMemory = I->mayWriteToMemory() && !isGuard(I) &&
178  !(I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()));
179  if (!MayWriteMemory) {
180  Alias = SetMayAlias;
181  Access |= RefAccess;
182  return;
183  }
184 
185  // FIXME: This should use mod/ref information to make this not suck so bad
186  Alias = SetMayAlias;
187  Access = ModRefAccess;
188 }
189 
190 /// aliasesPointer - If the specified pointer "may" (or must) alias one of the
191 /// members in the set return the appropriate AliasResult. Otherwise return
192 /// NoAlias.
193 ///
195  const AAMDNodes &AAInfo,
196  AliasAnalysis &AA) const {
197  if (AliasAny)
198  return AliasResult::MayAlias;
199 
200  if (Alias == SetMustAlias) {
201  assert(UnknownInsts.empty() && "Illegal must alias set!");
202 
203  // If this is a set of MustAliases, only check to see if the pointer aliases
204  // SOME value in the set.
205  PointerRec *SomePtr = getSomePointer();
206  assert(SomePtr && "Empty must-alias set??");
207  return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
208  SomePtr->getAAInfo()),
209  MemoryLocation(Ptr, Size, AAInfo));
210  }
211 
212  // If this is a may-alias set, we have to check all of the pointers in the set
213  // to be sure it doesn't alias the set...
214  for (iterator I = begin(), E = end(); I != E; ++I) {
215  AliasResult AR =
216  AA.alias(MemoryLocation(Ptr, Size, AAInfo),
217  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()));
218  if (AR != AliasResult::NoAlias)
219  return AR;
220  }
221 
222  // Check the unknown instructions...
223  if (!UnknownInsts.empty()) {
224  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
225  if (auto *Inst = getUnknownInst(i))
226  if (isModOrRefSet(
227  AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
228  return AliasResult::MayAlias;
229  }
230 
231  return AliasResult::NoAlias;
232 }
233 
235  AliasAnalysis &AA) const {
236 
237  if (AliasAny)
238  return true;
239 
240  assert(Inst->mayReadOrWriteMemory() &&
241  "Instruction must either read or write memory.");
242 
243  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
244  if (auto *UnknownInst = getUnknownInst(i)) {
245  const auto *C1 = dyn_cast<CallBase>(UnknownInst);
246  const auto *C2 = dyn_cast<CallBase>(Inst);
247  if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||
248  isModOrRefSet(AA.getModRefInfo(C2, C1)))
249  return true;
250  }
251  }
252 
253  for (iterator I = begin(), E = end(); I != E; ++I)
255  Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
256  return true;
257 
258  return false;
259 }
260 
262  if (AliasAny)
263  // May have collapses alias set
264  return nullptr;
265  if (begin() != end()) {
266  if (!UnknownInsts.empty())
267  // Another instruction found
268  return nullptr;
269  if (std::next(begin()) != end())
270  // Another instruction found
271  return nullptr;
272  Value *Addr = begin()->getValue();
273  assert(!Addr->user_empty() &&
274  "where's the instruction which added this pointer?");
275  if (std::next(Addr->user_begin()) != Addr->user_end())
276  // Another instruction found -- this is really restrictive
277  // TODO: generalize!
278  return nullptr;
279  return cast<Instruction>(*(Addr->user_begin()));
280  }
281  if (1 != UnknownInsts.size())
282  return nullptr;
283  return cast<Instruction>(UnknownInsts[0]);
284 }
285 
287  // Delete all the PointerRec entries.
288  for (auto &I : PointerMap)
289  I.second->eraseFromList();
290 
291  PointerMap.clear();
292 
293  // The alias sets should all be clear now.
294  AliasSets.clear();
295 }
296 
297 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
298 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
299 /// the pointer was found. MustAliasAll is updated to true/false if the pointer
300 /// is found to MustAlias all the sets it merged.
301 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
303  const AAMDNodes &AAInfo,
304  bool &MustAliasAll) {
305  AliasSet *FoundSet = nullptr;
306  MustAliasAll = true;
307  for (AliasSet &AS : llvm::make_early_inc_range(*this)) {
308  if (AS.Forward)
309  continue;
310 
311  AliasResult AR = AS.aliasesPointer(Ptr, Size, AAInfo, AA);
312  if (AR == AliasResult::NoAlias)
313  continue;
314 
315  if (AR != AliasResult::MustAlias)
316  MustAliasAll = false;
317 
318  if (!FoundSet) {
319  // If this is the first alias set ptr can go into, remember it.
320  FoundSet = &AS;
321  } else {
322  // Otherwise, we must merge the sets.
323  FoundSet->mergeSetIn(AS, *this);
324  }
325  }
326 
327  return FoundSet;
328 }
329 
330 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
331  AliasSet *FoundSet = nullptr;
332  for (AliasSet &AS : llvm::make_early_inc_range(*this)) {
333  if (AS.Forward || !AS.aliasesUnknownInst(Inst, AA))
334  continue;
335  if (!FoundSet) {
336  // If this is the first alias set ptr can go into, remember it.
337  FoundSet = &AS;
338  } else {
339  // Otherwise, we must merge the sets.
340  FoundSet->mergeSetIn(AS, *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 
409  if (isStrongerThanMonotonic(SI->getOrdering()))
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::experimental_noalias_scope_decl:
440  case Intrinsic::sideeffect:
441  case Intrinsic::pseudoprobe:
442  return;
443  }
444  }
445  if (!Inst->mayReadOrWriteMemory())
446  return; // doesn't alias anything
447 
448  if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
449  AS->addUnknownInst(Inst, AA);
450  return;
451  }
452  AliasSets.push_back(new AliasSet());
453  AliasSets.back().addUnknownInst(Inst, AA);
454 }
455 
457  // Dispatch to one of the other add methods.
458  if (LoadInst *LI = dyn_cast<LoadInst>(I))
459  return add(LI);
460  if (StoreInst *SI = dyn_cast<StoreInst>(I))
461  return add(SI);
462  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
463  return add(VAAI);
464  if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
465  return add(MSI);
466  if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
467  return add(MTI);
468 
469  // Handle all calls with known mod/ref sets genericall
470  if (auto *Call = dyn_cast<CallBase>(I))
471  if (Call->onlyAccessesArgMemory()) {
472  auto getAccessFromModRef = [](ModRefInfo MRI) {
473  if (isRefSet(MRI) && isModSet(MRI))
474  return AliasSet::ModRefAccess;
475  else if (isModSet(MRI))
476  return AliasSet::ModAccess;
477  else if (isRefSet(MRI))
478  return AliasSet::RefAccess;
479  else
480  return AliasSet::NoAccess;
481  };
482 
483  ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(Call));
484 
485  // Some intrinsics are marked as modifying memory for control flow
486  // modelling purposes, but don't actually modify any specific memory
487  // location.
488  using namespace PatternMatch;
489  if (Call->use_empty() &&
490  match(Call, m_Intrinsic<Intrinsic::invariant_start>()))
491  CallMask = clearMod(CallMask);
492 
493  for (auto IdxArgPair : enumerate(Call->args())) {
494  int ArgIdx = IdxArgPair.index();
495  const Value *Arg = IdxArgPair.value();
496  if (!Arg->getType()->isPointerTy())
497  continue;
498  MemoryLocation ArgLoc =
499  MemoryLocation::getForArgument(Call, ArgIdx, nullptr);
500  ModRefInfo ArgMask = AA.getArgModRefInfo(Call, ArgIdx);
501  ArgMask = intersectModRef(CallMask, ArgMask);
502  if (!isNoModRef(ArgMask))
503  addPointer(ArgLoc, getAccessFromModRef(ArgMask));
504  }
505  return;
506  }
507 
508  return addUnknown(I);
509 }
510 
512  for (auto &I : BB)
513  add(&I);
514 }
515 
517  assert(&AA == &AST.AA &&
518  "Merging AliasSetTracker objects with different Alias Analyses!");
519 
520  // Loop over all of the alias sets in AST, adding the pointers contained
521  // therein into the current alias sets. This can cause alias sets to be
522  // merged together in the current AST.
523  for (const AliasSet &AS : AST) {
524  if (AS.Forward)
525  continue; // Ignore forwarding alias sets
526 
527  // If there are any call sites in the alias set, add them to this AST.
528  for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
529  if (auto *Inst = AS.getUnknownInst(i))
530  add(Inst);
531 
532  // Loop over all of the pointers in this alias set.
533  for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
534  addPointer(
535  MemoryLocation(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo()),
536  (AliasSet::AccessLattice)AS.Access);
537  }
538 }
539 
540 // deleteValue method - This method is used to remove a pointer value from the
541 // AliasSetTracker entirely. It should be used when an instruction is deleted
542 // from the program to update the AST. If you don't use this, you would have
543 // dangling pointers to deleted instructions.
544 //
546  // First, look up the PointerRec for this pointer.
547  PointerMapType::iterator I = PointerMap.find_as(PtrVal);
548  if (I == PointerMap.end()) return; // Noop
549 
550  // If we found one, remove the pointer from the alias set it is in.
551  AliasSet::PointerRec *PtrValEnt = I->second;
552  AliasSet *AS = PtrValEnt->getAliasSet(*this);
553 
554  // Unlink and delete from the list of values.
555  PtrValEnt->eraseFromList();
556 
557  if (AS->Alias == AliasSet::SetMayAlias) {
558  AS->SetSize--;
559  TotalMayAliasSetSize--;
560  }
561 
562  // Stop using the alias set.
563  AS->dropRef(*this);
564 
565  PointerMap.erase(I);
566 }
567 
568 // copyValue - This method should be used whenever a preexisting value in the
569 // program is copied or cloned, introducing a new value. Note that it is ok for
570 // clients that use this method to introduce the same value multiple times: if
571 // the tracker already knows about a value, it will ignore the request.
572 //
574  // First, look up the PointerRec for this pointer.
575  PointerMapType::iterator I = PointerMap.find_as(From);
576  if (I == PointerMap.end())
577  return; // Noop
578  assert(I->second->hasAliasSet() && "Dead entry?");
579 
580  AliasSet::PointerRec &Entry = getEntryFor(To);
581  if (Entry.hasAliasSet()) return; // Already in the tracker!
582 
583  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
584  I = PointerMap.find_as(From);
585  // Add it to the alias set it aliases...
586  AliasSet *AS = I->second->getAliasSet(*this);
587  AS->addPointer(*this, Entry, I->second->getSize(), I->second->getAAInfo(),
588  true, true);
589 }
590 
591 AliasSet &AliasSetTracker::mergeAllAliasSets() {
592  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
593  "Full merge should happen once, when the saturation threshold is "
594  "reached");
595 
596  // Collect all alias sets, so that we can drop references with impunity
597  // without worrying about iterator invalidation.
598  std::vector<AliasSet *> ASVector;
599  ASVector.reserve(SaturationThreshold);
600  for (AliasSet &AS : *this)
601  ASVector.push_back(&AS);
602 
603  // Copy all instructions and pointers into a new set, and forward all other
604  // sets to it.
605  AliasSets.push_back(new AliasSet());
606  AliasAnyAS = &AliasSets.back();
607  AliasAnyAS->Alias = AliasSet::SetMayAlias;
608  AliasAnyAS->Access = AliasSet::ModRefAccess;
609  AliasAnyAS->AliasAny = true;
610 
611  for (auto Cur : ASVector) {
612  // If Cur was already forwarding, just forward to the new AS instead.
613  AliasSet *FwdTo = Cur->Forward;
614  if (FwdTo) {
615  Cur->Forward = AliasAnyAS;
616  AliasAnyAS->addRef();
617  FwdTo->dropRef(*this);
618  continue;
619  }
620 
621  // Otherwise, perform the actual merge.
622  AliasAnyAS->mergeSetIn(*Cur, *this);
623  }
624 
625  return *AliasAnyAS;
626 }
627 
628 AliasSet &AliasSetTracker::addPointer(MemoryLocation Loc,
629  AliasSet::AccessLattice E) {
630  AliasSet &AS = getAliasSetFor(Loc);
631  AS.Access |= E;
632 
633  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
634  // The AST is now saturated. From here on, we conservatively consider all
635  // pointers to alias each-other.
636  return mergeAllAliasSets();
637  }
638 
639  return AS;
640 }
641 
642 //===----------------------------------------------------------------------===//
643 // AliasSet/AliasSetTracker Printing Support
644 //===----------------------------------------------------------------------===//
645 
646 void AliasSet::print(raw_ostream &OS) const {
647  OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
648  OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
649  switch (Access) {
650  case NoAccess: OS << "No access "; break;
651  case RefAccess: OS << "Ref "; break;
652  case ModAccess: OS << "Mod "; break;
653  case ModRefAccess: OS << "Mod/Ref "; break;
654  default: llvm_unreachable("Bad value for Access!");
655  }
656  if (Forward)
657  OS << " forwarding to " << (void*)Forward;
658 
659  if (!empty()) {
660  OS << "Pointers: ";
661  for (iterator I = begin(), E = end(); I != E; ++I) {
662  if (I != begin()) OS << ", ";
663  I.getPointer()->printAsOperand(OS << "(");
664  if (I.getSize() == LocationSize::afterPointer())
665  OS << ", unknown after)";
666  else if (I.getSize() == LocationSize::beforeOrAfterPointer())
667  OS << ", unknown before-or-after)";
668  else
669  OS << ", " << I.getSize() << ")";
670  }
671  }
672  if (!UnknownInsts.empty()) {
673  OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
674  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
675  if (i) OS << ", ";
676  if (auto *I = getUnknownInst(i)) {
677  if (I->hasName())
678  I->printAsOperand(OS);
679  else
680  I->print(OS);
681  }
682  }
683  }
684  OS << "\n";
685 }
686 
688  OS << "Alias Set Tracker: " << AliasSets.size();
689  if (AliasAnyAS)
690  OS << " (Saturated)";
691  OS << " alias sets for " << PointerMap.size() << " pointer values.\n";
692  for (const AliasSet &AS : *this)
693  AS.print(OS);
694  OS << "\n";
695 }
696 
697 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
700 #endif
701 
702 //===----------------------------------------------------------------------===//
703 // ASTCallbackVH Class Implementation
704 //===----------------------------------------------------------------------===//
705 
706 void AliasSetTracker::ASTCallbackVH::deleted() {
707  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
708  AST->deleteValue(getValPtr());
709  // this now dangles!
710 }
711 
712 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
713  AST->copyValue(getValPtr(), V);
714 }
715 
716 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
717  : CallbackVH(V), AST(ast) {}
718 
719 AliasSetTracker::ASTCallbackVH &
720 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
721  return *this = ASTCallbackVH(V, AST);
722 }
723 
724 //===----------------------------------------------------------------------===//
725 // AliasSetPrinter Pass
726 //===----------------------------------------------------------------------===//
727 
728 namespace {
729 
730  class AliasSetPrinter : public FunctionPass {
731  public:
732  static char ID; // Pass identification, replacement for typeid
733 
734  AliasSetPrinter() : FunctionPass(ID) {
736  }
737 
738  void getAnalysisUsage(AnalysisUsage &AU) const override {
739  AU.setPreservesAll();
741  }
742 
743  bool runOnFunction(Function &F) override {
744  auto &AAWP = getAnalysis<AAResultsWrapperPass>();
745  AliasSetTracker Tracker(AAWP.getAAResults());
746  errs() << "Alias sets for function '" << F.getName() << "':\n";
747  for (Instruction &I : instructions(F))
748  Tracker.add(&I);
749  Tracker.print(errs());
750  return false;
751  }
752  };
753 
754 } // end anonymous namespace
755 
756 char AliasSetPrinter::ID = 0;
757 
758 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
759  "Alias Set Printer", false, true)
761 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
762  "Alias Set Printer", false, true)
763 
765 
768  auto &AA = AM.getResult<AAManager>(F);
769  AliasSetTracker Tracker(AA);
770  OS << "Alias sets for function '" << F.getName() << "':\n";
771  for (Instruction &I : instructions(F))
772  Tracker.add(&I);
773  Tracker.print(OS);
774  return PreservedAnalyses::all();
775 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::AliasSetTracker::addUnknown
void addUnknown(Instruction *I)
Definition: AliasSetTracker.cpp:427
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1288
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:103
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:506
llvm::MemoryLocation::get
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
Definition: MemoryLocation.cpp:37
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1833
llvm::LocationSize::afterPointer
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:123
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::isModOrRefSet
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:190
IntrinsicInst.h
AtomicOrdering.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:783
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:217
InstIterator.h
llvm::Function
Definition: Function.h:62
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Pass.h
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::enumerate
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:1981
ErrorHandling.h
llvm::createModRefInfo
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
Definition: AliasAnalysis.h:378
llvm::AliasSetTracker::print
void print(raw_ostream &OS) const
Definition: AliasSetTracker.cpp:687
llvm::AliasSetTracker
Definition: AliasSetTracker.h:329
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
llvm::DenseMapIterator
Definition: DenseMap.h:56
llvm::MemoryLocation::Size
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
Definition: MemoryLocation.h:226
Module.h
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:82
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::AliasSet::print
void print(raw_ostream &OS) const
Definition: AliasSetTracker.cpp:646
sets
print alias sets
Definition: AliasSetTracker.cpp:761
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
AliasAnalysis.h
llvm::isGuard
bool isGuard(const User *U)
Returns true iff U has semantics of a guard expressed in a form of call of llvm.experimental....
Definition: GuardUtils.cpp:18
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::AliasSetTracker::clear
void clear()
Definition: AliasSetTracker.cpp:286
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:206
CommandLine.h
llvm::MemoryLocation::AATags
AAMDNodes AATags
The metadata nodes which describes the aliasing of the location (each member is null if that kind of ...
Definition: MemoryLocation.h:230
llvm::AliasSet::end
iterator end() const
Definition: AliasSetTracker.h:220
Printer
print alias Alias Set Printer
Definition: AliasSetTracker.cpp:762
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::Instruction::mayReadOrWriteMemory
bool mayReadOrWriteMemory() const
Return true if this instruction may read or write memory.
Definition: Instruction.h:598
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::AAResults
Definition: AliasAnalysis.h:508
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LocationSize
Definition: MemoryLocation.h:65
llvm::AliasSetTracker::dump
void dump() const
Definition: AliasSetTracker.cpp:699
llvm::AliasSetsPrinterPass
Definition: AliasSetTracker.h:461
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MemoryLocation::getForSource
static MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
Definition: MemoryLocation.cpp:95
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::AliasSet
Definition: AliasSetTracker.h:49
false
Definition: StackSlotColoring.cpp:142
llvm::AliasSetsPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AliasSetTracker.cpp:766
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::AliasSet::empty
bool empty() const
Definition: AliasSetTracker.h:221
PatternMatch.h
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:197
llvm::AliasSet::mergeSetIn
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST)
Merge the specified alias set into this alias set.
Definition: AliasSetTracker.cpp:48
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1029
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::clearMod
LLVM_NODISCARD ModRefInfo clearMod(const ModRefInfo MRI)
Definition: AliasAnalysis.h:223
llvm::cl::opt
Definition: CommandLine.h:1432
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::isNoModRef
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
Definition: AliasAnalysis.h:186
llvm::AliasSetTracker::add
void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo)
These methods are used to add different types of instructions to the alias sets.
Definition: AliasSetTracker.cpp:397
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
MemoryLocation.h
llvm::AliasSet::size
unsigned size()
Definition: AliasSetTracker.h:225
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:441
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
llvm::AliasSet::dump
void dump() const
Definition: AliasSetTracker.cpp:698
llvm::AliasSetTracker::getAliasAnalysis
AAResults & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
Definition: AliasSetTracker.h:397
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:149
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MemoryLocation::getForArgument
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
Definition: MemoryLocation.cpp:131
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::AliasSetTracker::getAliasSetFor
AliasSet & getAliasSetFor(const MemoryLocation &MemLoc)
Return the alias set which contains the specified memory location.
Definition: AliasSetTracker.cpp:346
llvm::AliasSet::iterator
Define an iterator for alias sets... this is just a forward iterator.
Definition: AliasSetTracker.h:235
llvm::AliasSet::aliasesPointer
AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo, AAResults &AA) const
If the specified pointer "may" (or must) alias one of the members in the set return the appropriate A...
Definition: AliasSetTracker.cpp:194
DataLayout.h
llvm::AliasSetTracker::copyValue
void copyValue(Value *From, Value *To)
This method should be used whenever a preexisting value in the program is copied or cloned,...
Definition: AliasSetTracker.cpp:573
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:100
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1748
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:107
SaturationThreshold
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"))
llvm::LoadInst::getOrdering
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:232
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::AAResults::getModRefBehavior
FunctionModRefBehavior getModRefBehavior(const CallBase *Call)
Return the behavior of the given call site.
Definition: AliasAnalysis.cpp:423
llvm::AliasSetTracker::deleteValue
void deleteValue(Value *PtrVal)
This method is used to remove a pointer value from the AliasSetTracker entirely.
Definition: AliasSetTracker.cpp:545
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::initializeAliasSetPrinterPass
void initializeAliasSetPrinterPass(PassRegistry &)
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::AnyMemSetInst
This class represents any memset intrinsic.
Definition: IntrinsicInst.h:1010
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:129
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Function.h
PassManager.h
llvm::AAResults::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
Definition: AliasAnalysis.cpp:120
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
GuardUtils.h
llvm::AliasSet::begin
iterator begin() const
Definition: AliasSetTracker.h:219
llvm::AAResults::getArgModRefInfo
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
Definition: AliasAnalysis.cpp:178
Instructions.h
llvm::isRefSet
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:200
llvm::AliasSet::isMustAlias
bool isMustAlias() const
Definition: AliasSetTracker.h:206
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1336
llvm::isStrongerThanMonotonic
bool isStrongerThanMonotonic(AtomicOrdering AO)
Definition: AtomicOrdering.h:124
llvm::AAResults::isMustAlias
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
A trivial helper function to check to see if the specified pointers are must-alias.
Definition: AliasAnalysis.h:580
llvm::AliasSet::getUniqueInstruction
Instruction * getUniqueInstruction()
If this alias set is known to contain a single instruction and only a single unique instruction,...
Definition: AliasSetTracker.cpp:261
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
AliasSetTracker.h
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::MemoryLocation::getForDest
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
Definition: MemoryLocation.cpp:113
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::cl::desc
Definition: CommandLine.h:412
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets", "Alias Set Printer", false, true) INITIALIZE_PASS_END(AliasSetPrinter
raw_ostream.h
llvm::intersectModRef
LLVM_NODISCARD ModRefInfo intersectModRef(const ModRefInfo MRI1, const ModRefInfo MRI2)
Definition: AliasAnalysis.h:237
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1927
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::AAResults::getModRefInfo
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc)
getModRefInfo (for call sites) - Return information about whether a particular call site modifies or ...
Definition: AliasAnalysis.cpp:218
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::AliasSet::aliasesUnknownInst
bool aliasesUnknownInst(const Instruction *Inst, AAResults &AA) const
Definition: AliasSetTracker.cpp:234
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37