LLVM  15.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 
17 #include "llvm/Config/llvm-config.h"
18 #include "llvm/IR/Function.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/IR/PatternMatch.h"
24 #include "llvm/IR/Value.h"
25 #include "llvm/InitializePasses.h"
26 #include "llvm/Pass.h"
29 #include "llvm/Support/Compiler.h"
30 #include "llvm/Support/Debug.h"
33 
34 using namespace llvm;
35 
36 static cl::opt<unsigned>
37  SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
38  cl::init(250),
39  cl::desc("The maximum number of pointers may-alias "
40  "sets may contain before degradation"));
41 
42 /// mergeSetIn - Merge the specified alias set into this alias set.
43 ///
45  assert(!AS.Forward && "Alias set is already forwarding!");
46  assert(!Forward && "This set is a forwarding set!!");
47 
48  bool WasMustAlias = (Alias == SetMustAlias);
49  // Update the alias and access types of this set...
50  Access |= AS.Access;
51  Alias |= AS.Alias;
52 
53  if (Alias == SetMustAlias) {
54  // Check that these two merged sets really are must aliases. Since both
55  // used to be must-alias sets, we can just check any pointer from each set
56  // for aliasing.
58  PointerRec *L = getSomePointer();
59  PointerRec *R = AS.getSomePointer();
60 
61  // If the pointers are not a must-alias pair, this set becomes a may alias.
62  if (!AA.isMustAlias(
63  MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
64  MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())))
65  Alias = SetMayAlias;
66  }
67 
68  if (Alias == SetMayAlias) {
69  if (WasMustAlias)
70  AST.TotalMayAliasSetSize += size();
71  if (AS.Alias == SetMustAlias)
72  AST.TotalMayAliasSetSize += AS.size();
73  }
74 
75  bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
76  if (UnknownInsts.empty()) { // Merge call sites...
77  if (ASHadUnknownInsts) {
78  std::swap(UnknownInsts, AS.UnknownInsts);
79  addRef();
80  }
81  } else if (ASHadUnknownInsts) {
82  llvm::append_range(UnknownInsts, AS.UnknownInsts);
83  AS.UnknownInsts.clear();
84  }
85 
86  AS.Forward = this; // Forward across AS now...
87  addRef(); // AS is now pointing to us...
88 
89  // Merge the list of constituent pointers...
90  if (AS.PtrList) {
91  SetSize += AS.size();
92  AS.SetSize = 0;
93  *PtrListEnd = AS.PtrList;
94  AS.PtrList->setPrevInList(PtrListEnd);
95  PtrListEnd = AS.PtrListEnd;
96 
97  AS.PtrList = nullptr;
98  AS.PtrListEnd = &AS.PtrList;
99  assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
100  }
101  if (ASHadUnknownInsts)
102  AS.dropRef(AST);
103 }
104 
105 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
106  if (AliasSet *Fwd = AS->Forward) {
107  Fwd->dropRef(*this);
108  AS->Forward = nullptr;
109  } else // Update TotalMayAliasSetSize only if not forwarding.
110  if (AS->Alias == AliasSet::SetMayAlias)
111  TotalMayAliasSetSize -= AS->size();
112 
113  AliasSets.erase(AS);
114  // If we've removed the saturated alias set, set saturated marker back to
115  // nullptr and ensure this tracker is empty.
116  if (AS == AliasAnyAS) {
117  AliasAnyAS = nullptr;
118  assert(AliasSets.empty() && "Tracker not empty");
119  }
120 }
121 
122 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
123  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
124  AST.removeAliasSet(this);
125 }
126 
127 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
128  LocationSize Size, const AAMDNodes &AAInfo,
129  bool KnownMustAlias, bool SkipSizeUpdate) {
130  assert(!Entry.hasAliasSet() && "Entry already in set!");
131 
132  // Check to see if we have to downgrade to _may_ alias.
133  if (isMustAlias())
134  if (PointerRec *P = getSomePointer()) {
135  if (!KnownMustAlias) {
137  AliasResult Result = AA.alias(
138  MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
139  MemoryLocation(Entry.getValue(), Size, AAInfo));
140  if (Result != AliasResult::MustAlias) {
141  Alias = SetMayAlias;
142  AST.TotalMayAliasSetSize += size();
143  }
144  assert(Result != AliasResult::NoAlias && "Cannot be part of must set!");
145  } else if (!SkipSizeUpdate)
146  P->updateSizeAndAAInfo(Size, AAInfo);
147  }
148 
149  Entry.setAliasSet(this);
150  Entry.updateSizeAndAAInfo(Size, AAInfo);
151 
152  // Add it to the end of the list...
153  ++SetSize;
154  assert(*PtrListEnd == nullptr && "End of list is not null?");
155  *PtrListEnd = &Entry;
156  PtrListEnd = Entry.setPrevInList(PtrListEnd);
157  assert(*PtrListEnd == nullptr && "End of list is not null?");
158  // Entry points to alias set.
159  addRef();
160 
161  if (Alias == SetMayAlias)
162  AST.TotalMayAliasSetSize++;
163 }
164 
165 void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
166  if (UnknownInsts.empty())
167  addRef();
168  UnknownInsts.emplace_back(I);
169 
170  // Guards are marked as modifying memory for control flow modelling purposes,
171  // but don't actually modify any specific memory location.
172  using namespace PatternMatch;
173  bool MayWriteMemory = I->mayWriteToMemory() && !isGuard(I) &&
174  !(I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()));
175  if (!MayWriteMemory) {
176  Alias = SetMayAlias;
177  Access |= RefAccess;
178  return;
179  }
180 
181  // FIXME: This should use mod/ref information to make this not suck so bad
182  Alias = SetMayAlias;
183  Access = ModRefAccess;
184 }
185 
186 /// aliasesPointer - If the specified pointer "may" (or must) alias one of the
187 /// members in the set return the appropriate AliasResult. Otherwise return
188 /// NoAlias.
189 ///
191  const AAMDNodes &AAInfo,
192  AliasAnalysis &AA) const {
193  if (AliasAny)
194  return AliasResult::MayAlias;
195 
196  if (Alias == SetMustAlias) {
197  assert(UnknownInsts.empty() && "Illegal must alias set!");
198 
199  // If this is a set of MustAliases, only check to see if the pointer aliases
200  // SOME value in the set.
201  PointerRec *SomePtr = getSomePointer();
202  assert(SomePtr && "Empty must-alias set??");
203  return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
204  SomePtr->getAAInfo()),
205  MemoryLocation(Ptr, Size, AAInfo));
206  }
207 
208  // If this is a may-alias set, we have to check all of the pointers in the set
209  // to be sure it doesn't alias the set...
210  for (iterator I = begin(), E = end(); I != E; ++I) {
211  AliasResult AR =
212  AA.alias(MemoryLocation(Ptr, Size, AAInfo),
213  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()));
214  if (AR != AliasResult::NoAlias)
215  return AR;
216  }
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 AliasResult::MayAlias;
225  }
226 
227  return AliasResult::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)
250  if (isModOrRefSet(AA.getModRefInfo(
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 (auto &I : PointerMap)
285  I.second->eraseFromList();
286 
287  PointerMap.clear();
288 
289  // The alias sets should all be clear now.
290  AliasSets.clear();
291 }
292 
293 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
294 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
295 /// the pointer was found. MustAliasAll is updated to true/false if the pointer
296 /// is found to MustAlias all the sets it merged.
297 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
298  LocationSize Size,
299  const AAMDNodes &AAInfo,
300  bool &MustAliasAll) {
301  AliasSet *FoundSet = nullptr;
302  MustAliasAll = true;
303  for (AliasSet &AS : llvm::make_early_inc_range(*this)) {
304  if (AS.Forward)
305  continue;
306 
307  AliasResult AR = AS.aliasesPointer(Ptr, Size, AAInfo, AA);
308  if (AR == AliasResult::NoAlias)
309  continue;
310 
311  if (AR != AliasResult::MustAlias)
312  MustAliasAll = false;
313 
314  if (!FoundSet) {
315  // If this is the first alias set ptr can go into, remember it.
316  FoundSet = &AS;
317  } else {
318  // Otherwise, we must merge the sets.
319  FoundSet->mergeSetIn(AS, *this);
320  }
321  }
322 
323  return FoundSet;
324 }
325 
326 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
327  AliasSet *FoundSet = nullptr;
328  for (AliasSet &AS : llvm::make_early_inc_range(*this)) {
329  if (AS.Forward || !AS.aliasesUnknownInst(Inst, AA))
330  continue;
331  if (!FoundSet) {
332  // If this is the first alias set ptr can go into, remember it.
333  FoundSet = &AS;
334  } else {
335  // Otherwise, we must merge the sets.
336  FoundSet->mergeSetIn(AS, *this);
337  }
338  }
339  return FoundSet;
340 }
341 
343 
344  Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
345  const LocationSize Size = MemLoc.Size;
346  const AAMDNodes &AAInfo = MemLoc.AATags;
347 
348  AliasSet::PointerRec &Entry = getEntryFor(Pointer);
349 
350  if (AliasAnyAS) {
351  // At this point, the AST is saturated, so we only have one active alias
352  // set. That means we already know which alias set we want to return, and
353  // just need to add the pointer to that set to keep the data structure
354  // consistent.
355  // This, of course, means that we will never need a merge here.
356  if (Entry.hasAliasSet()) {
357  Entry.updateSizeAndAAInfo(Size, AAInfo);
358  assert(Entry.getAliasSet(*this) == AliasAnyAS &&
359  "Entry in saturated AST must belong to only alias set");
360  } else {
361  AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
362  }
363  return *AliasAnyAS;
364  }
365 
366  bool MustAliasAll = false;
367  // Check to see if the pointer is already known.
368  if (Entry.hasAliasSet()) {
369  // If the size changed, we may need to merge several alias sets.
370  // Note that we can *not* return the result of mergeAliasSetsForPointer
371  // due to a quirk of alias analysis behavior. Since alias(undef, undef)
372  // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
373  // the right set for undef, even if it exists.
374  if (Entry.updateSizeAndAAInfo(Size, AAInfo))
375  mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll);
376  // Return the set!
377  return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
378  }
379 
380  if (AliasSet *AS =
381  mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll)) {
382  // Add it to the alias set it aliases.
383  AS->addPointer(*this, Entry, Size, AAInfo, MustAliasAll);
384  return *AS;
385  }
386 
387  // Otherwise create a new alias set to hold the loaded pointer.
388  AliasSets.push_back(new AliasSet());
389  AliasSets.back().addPointer(*this, Entry, Size, AAInfo, true);
390  return AliasSets.back();
391 }
392 
394  const AAMDNodes &AAInfo) {
395  addPointer(MemoryLocation(Ptr, Size, AAInfo), AliasSet::NoAccess);
396 }
397 
400  return addUnknown(LI);
401  addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
402 }
403 
405  if (isStrongerThanMonotonic(SI->getOrdering()))
406  return addUnknown(SI);
407  addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
408 }
409 
411  addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
412 }
413 
415  addPointer(MemoryLocation::getForDest(MSI), AliasSet::ModAccess);
416 }
417 
419  addPointer(MemoryLocation::getForDest(MTI), AliasSet::ModAccess);
420  addPointer(MemoryLocation::getForSource(MTI), AliasSet::RefAccess);
421 }
422 
424  if (isa<DbgInfoIntrinsic>(Inst))
425  return; // Ignore DbgInfo Intrinsics.
426 
427  if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
428  // These intrinsics will show up as affecting memory, but they are just
429  // markers.
430  switch (II->getIntrinsicID()) {
431  default:
432  break;
433  // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
434  case Intrinsic::assume:
435  case Intrinsic::experimental_noalias_scope_decl:
436  case Intrinsic::sideeffect:
437  case Intrinsic::pseudoprobe:
438  return;
439  }
440  }
441  if (!Inst->mayReadOrWriteMemory())
442  return; // doesn't alias anything
443 
444  if (AliasSet *AS = findAliasSetForUnknownInst(Inst)) {
445  AS->addUnknownInst(Inst, AA);
446  return;
447  }
448  AliasSets.push_back(new AliasSet());
449  AliasSets.back().addUnknownInst(Inst, AA);
450 }
451 
453  // Dispatch to one of the other add methods.
454  if (LoadInst *LI = dyn_cast<LoadInst>(I))
455  return add(LI);
456  if (StoreInst *SI = dyn_cast<StoreInst>(I))
457  return add(SI);
458  if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
459  return add(VAAI);
460  if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
461  return add(MSI);
462  if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
463  return add(MTI);
464 
465  // Handle all calls with known mod/ref sets genericall
466  if (auto *Call = dyn_cast<CallBase>(I))
467  if (Call->onlyAccessesArgMemory()) {
468  auto getAccessFromModRef = [](ModRefInfo MRI) {
469  if (isRefSet(MRI) && isModSet(MRI))
470  return AliasSet::ModRefAccess;
471  else if (isModSet(MRI))
472  return AliasSet::ModAccess;
473  else if (isRefSet(MRI))
474  return AliasSet::RefAccess;
475  else
476  return AliasSet::NoAccess;
477  };
478 
479  ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(Call));
480 
481  // Some intrinsics are marked as modifying memory for control flow
482  // modelling purposes, but don't actually modify any specific memory
483  // location.
484  using namespace PatternMatch;
485  if (Call->use_empty() &&
486  match(Call, m_Intrinsic<Intrinsic::invariant_start>()))
487  CallMask = clearMod(CallMask);
488 
489  for (auto IdxArgPair : enumerate(Call->args())) {
490  int ArgIdx = IdxArgPair.index();
491  const Value *Arg = IdxArgPair.value();
492  if (!Arg->getType()->isPointerTy())
493  continue;
494  MemoryLocation ArgLoc =
495  MemoryLocation::getForArgument(Call, ArgIdx, nullptr);
496  ModRefInfo ArgMask = AA.getArgModRefInfo(Call, ArgIdx);
497  ArgMask = intersectModRef(CallMask, ArgMask);
498  if (!isNoModRef(ArgMask))
499  addPointer(ArgLoc, getAccessFromModRef(ArgMask));
500  }
501  return;
502  }
503 
504  return addUnknown(I);
505 }
506 
508  for (auto &I : BB)
509  add(&I);
510 }
511 
513  assert(&AA == &AST.AA &&
514  "Merging AliasSetTracker objects with different Alias Analyses!");
515 
516  // Loop over all of the alias sets in AST, adding the pointers contained
517  // therein into the current alias sets. This can cause alias sets to be
518  // merged together in the current AST.
519  for (const AliasSet &AS : AST) {
520  if (AS.Forward)
521  continue; // Ignore forwarding alias sets
522 
523  // If there are any call sites in the alias set, add them to this AST.
524  for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
525  if (auto *Inst = AS.getUnknownInst(i))
526  add(Inst);
527 
528  // Loop over all of the pointers in this alias set.
529  for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
530  addPointer(
531  MemoryLocation(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo()),
532  (AliasSet::AccessLattice)AS.Access);
533  }
534 }
535 
536 // deleteValue method - This method is used to remove a pointer value from the
537 // AliasSetTracker entirely. It should be used when an instruction is deleted
538 // from the program to update the AST. If you don't use this, you would have
539 // dangling pointers to deleted instructions.
540 //
542  // First, look up the PointerRec for this pointer.
543  PointerMapType::iterator I = PointerMap.find_as(PtrVal);
544  if (I == PointerMap.end()) return; // Noop
545 
546  // If we found one, remove the pointer from the alias set it is in.
547  AliasSet::PointerRec *PtrValEnt = I->second;
548  AliasSet *AS = PtrValEnt->getAliasSet(*this);
549 
550  // Unlink and delete from the list of values.
551  PtrValEnt->eraseFromList();
552 
553  if (AS->Alias == AliasSet::SetMayAlias) {
554  AS->SetSize--;
555  TotalMayAliasSetSize--;
556  }
557 
558  // Stop using the alias set.
559  AS->dropRef(*this);
560 
561  PointerMap.erase(I);
562 }
563 
564 // copyValue - This method should be used whenever a preexisting value in the
565 // program is copied or cloned, introducing a new value. Note that it is ok for
566 // clients that use this method to introduce the same value multiple times: if
567 // the tracker already knows about a value, it will ignore the request.
568 //
570  // First, look up the PointerRec for this pointer.
571  PointerMapType::iterator I = PointerMap.find_as(From);
572  if (I == PointerMap.end())
573  return; // Noop
574  assert(I->second->hasAliasSet() && "Dead entry?");
575 
576  AliasSet::PointerRec &Entry = getEntryFor(To);
577  if (Entry.hasAliasSet()) return; // Already in the tracker!
578 
579  // getEntryFor above may invalidate iterator \c I, so reinitialize it.
580  I = PointerMap.find_as(From);
581  // Add it to the alias set it aliases...
582  AliasSet *AS = I->second->getAliasSet(*this);
583  AS->addPointer(*this, Entry, I->second->getSize(), I->second->getAAInfo(),
584  true, true);
585 }
586 
587 AliasSet &AliasSetTracker::mergeAllAliasSets() {
588  assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
589  "Full merge should happen once, when the saturation threshold is "
590  "reached");
591 
592  // Collect all alias sets, so that we can drop references with impunity
593  // without worrying about iterator invalidation.
594  std::vector<AliasSet *> ASVector;
595  ASVector.reserve(SaturationThreshold);
596  for (AliasSet &AS : *this)
597  ASVector.push_back(&AS);
598 
599  // Copy all instructions and pointers into a new set, and forward all other
600  // sets to it.
601  AliasSets.push_back(new AliasSet());
602  AliasAnyAS = &AliasSets.back();
603  AliasAnyAS->Alias = AliasSet::SetMayAlias;
604  AliasAnyAS->Access = AliasSet::ModRefAccess;
605  AliasAnyAS->AliasAny = true;
606 
607  for (auto Cur : ASVector) {
608  // If Cur was already forwarding, just forward to the new AS instead.
609  AliasSet *FwdTo = Cur->Forward;
610  if (FwdTo) {
611  Cur->Forward = AliasAnyAS;
612  AliasAnyAS->addRef();
613  FwdTo->dropRef(*this);
614  continue;
615  }
616 
617  // Otherwise, perform the actual merge.
618  AliasAnyAS->mergeSetIn(*Cur, *this);
619  }
620 
621  return *AliasAnyAS;
622 }
623 
624 AliasSet &AliasSetTracker::addPointer(MemoryLocation Loc,
625  AliasSet::AccessLattice E) {
626  AliasSet &AS = getAliasSetFor(Loc);
627  AS.Access |= E;
628 
629  if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
630  // The AST is now saturated. From here on, we conservatively consider all
631  // pointers to alias each-other.
632  return mergeAllAliasSets();
633  }
634 
635  return AS;
636 }
637 
638 //===----------------------------------------------------------------------===//
639 // AliasSet/AliasSetTracker Printing Support
640 //===----------------------------------------------------------------------===//
641 
642 void AliasSet::print(raw_ostream &OS) const {
643  OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
644  OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
645  switch (Access) {
646  case NoAccess: OS << "No access "; break;
647  case RefAccess: OS << "Ref "; break;
648  case ModAccess: OS << "Mod "; break;
649  case ModRefAccess: OS << "Mod/Ref "; break;
650  default: llvm_unreachable("Bad value for Access!");
651  }
652  if (Forward)
653  OS << " forwarding to " << (void*)Forward;
654 
655  if (!empty()) {
656  OS << "Pointers: ";
657  for (iterator I = begin(), E = end(); I != E; ++I) {
658  if (I != begin()) OS << ", ";
659  I.getPointer()->printAsOperand(OS << "(");
660  if (I.getSize() == LocationSize::afterPointer())
661  OS << ", unknown after)";
662  else if (I.getSize() == LocationSize::beforeOrAfterPointer())
663  OS << ", unknown before-or-after)";
664  else
665  OS << ", " << I.getSize() << ")";
666  }
667  }
668  if (!UnknownInsts.empty()) {
669  OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
670  for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
671  if (i) OS << ", ";
672  if (auto *I = getUnknownInst(i)) {
673  if (I->hasName())
674  I->printAsOperand(OS);
675  else
676  I->print(OS);
677  }
678  }
679  }
680  OS << "\n";
681 }
682 
684  OS << "Alias Set Tracker: " << AliasSets.size();
685  if (AliasAnyAS)
686  OS << " (Saturated)";
687  OS << " alias sets for " << PointerMap.size() << " pointer values.\n";
688  for (const AliasSet &AS : *this)
689  AS.print(OS);
690  OS << "\n";
691 }
692 
693 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
696 #endif
697 
698 //===----------------------------------------------------------------------===//
699 // ASTCallbackVH Class Implementation
700 //===----------------------------------------------------------------------===//
701 
702 void AliasSetTracker::ASTCallbackVH::deleted() {
703  assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
704  AST->deleteValue(getValPtr());
705  // this now dangles!
706 }
707 
708 void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
709  AST->copyValue(getValPtr(), V);
710 }
711 
712 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
713  : CallbackVH(V), AST(ast) {}
714 
715 AliasSetTracker::ASTCallbackVH &
716 AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
717  return *this = ASTCallbackVH(V, AST);
718 }
719 
720 //===----------------------------------------------------------------------===//
721 // AliasSetPrinter Pass
722 //===----------------------------------------------------------------------===//
723 
724 namespace {
725 
726  class AliasSetPrinter : public FunctionPass {
727  public:
728  static char ID; // Pass identification, replacement for typeid
729 
730  AliasSetPrinter() : FunctionPass(ID) {
732  }
733 
734  void getAnalysisUsage(AnalysisUsage &AU) const override {
735  AU.setPreservesAll();
737  }
738 
739  bool runOnFunction(Function &F) override {
740  auto &AAWP = getAnalysis<AAResultsWrapperPass>();
741  AliasSetTracker Tracker(AAWP.getAAResults());
742  errs() << "Alias sets for function '" << F.getName() << "':\n";
743  for (Instruction &I : instructions(F))
744  Tracker.add(&I);
745  Tracker.print(errs());
746  return false;
747  }
748  };
749 
750 } // end anonymous namespace
751 
752 char AliasSetPrinter::ID = 0;
753 
754 INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
755  "Alias Set Printer", false, true)
757 INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
758  "Alias Set Printer", false, true)
759 
761 
764  auto &AA = AM.getResult<AAManager>(F);
765  AliasSetTracker Tracker(AA);
766  OS << "Alias sets for function '" << F.getName() << "':\n";
767  for (Instruction &I : instructions(F))
768  Tracker.add(&I);
769  Tracker.print(OS);
770  return PreservedAnalyses::all();
771 }
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:152
llvm::AliasSetTracker::addUnknown
void addUnknown(Instruction *I)
Definition: AliasSetTracker.cpp:423
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1299
llvm::AliasResult::MayAlias
@ MayAlias
The two locations may or may not alias.
Definition: AliasAnalysis.h:102
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:494
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:35
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::VAArgInst
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
Definition: Instructions.h:1832
llvm::LocationSize::afterPointer
constexpr static LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:124
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::isModOrRefSet
LLVM_NODISCARD bool isModOrRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:189
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:780
llvm::MemoryLocation::Ptr
const Value * Ptr
The address of the start of the location.
Definition: MemoryLocation.h:218
InstIterator.h
llvm::Function
Definition: Function.h:60
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:2047
ErrorHandling.h
llvm::createModRefInfo
LLVM_NODISCARD ModRefInfo createModRefInfo(const FunctionModRefBehavior FMRB)
Definition: AliasAnalysis.h:377
llvm::AliasSetTracker::print
void print(raw_ostream &OS) const
Definition: AliasSetTracker.cpp:683
llvm::AliasSetTracker
Definition: AliasSetTracker.h:326
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:652
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1909
llvm::DenseMapIterator
Definition: DenseMap.h:57
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:227
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
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:642
sets
print alias sets
Definition: AliasSetTracker.cpp:757
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:282
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:186
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:231
llvm::AliasSet::end
iterator end() const
Definition: AliasSetTracker.h:217
Printer
print alias Alias Set Printer
Definition: AliasSetTracker.cpp:758
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:599
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::AAResults
Definition: AliasAnalysis.h:511
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::LocationSize
Definition: MemoryLocation.h:66
llvm::AliasSetTracker::dump
void dump() const
Definition: AliasSetTracker.cpp:695
llvm::AliasSetsPrinterPass
Definition: AliasSetTracker.h:458
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:93
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::AliasSet
Definition: AliasSetTracker.h:46
false
Definition: StackSlotColoring.cpp:141
llvm::AliasSetsPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AliasSetTracker.cpp:762
llvm::Instruction
Definition: Instruction.h:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::AliasSet::empty
bool empty() const
Definition: AliasSetTracker.h:218
PatternMatch.h
llvm::isModSet
LLVM_NODISCARD bool isModSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:196
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::AliasSet::mergeSetIn
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST)
Merge the specified alias set into this alias set.
Definition: AliasSetTracker.cpp:44
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1117
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::clearMod
LLVM_NODISCARD ModRefInfo clearMod(const ModRefInfo MRI)
Definition: AliasAnalysis.h:222
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:305
llvm::isNoModRef
LLVM_NODISCARD bool isNoModRef(const ModRefInfo MRI)
Definition: AliasAnalysis.h:185
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:393
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:78
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:222
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
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:608
llvm::AliasSet::dump
void dump() const
Definition: AliasSetTracker.cpp:694
llvm::AliasSetTracker::getAliasAnalysis
AAResults & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
Definition: AliasSetTracker.h:394
llvm::ModRefInfo
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
Definition: AliasAnalysis.h:148
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:158
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
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:342
llvm::AliasSet::iterator
Define an iterator for alias sets... this is just a forward iterator.
Definition: AliasSetTracker.h:232
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:190
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:569
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1813
llvm::AliasResult::MustAlias
@ MustAlias
The two locations precisely alias each other.
Definition: AliasAnalysis.h:106
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:233
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:176
llvm::AliasSetTracker::deleteValue
void deleteValue(Value *PtrVal)
This method is used to remove a pointer value from the AliasSetTracker entirely.
Definition: AliasSetTracker.cpp:541
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:1098
llvm::LocationSize::beforeOrAfterPointer
constexpr static LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
Definition: MemoryLocation.h:130
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Function.h
PassManager.h
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
GuardUtils.h
AA
llvm::AliasSet::begin
iterator begin() const
Definition: AliasSetTracker.h:216
Instructions.h
llvm::isRefSet
LLVM_NODISCARD bool isRefSet(const ModRefInfo MRI)
Definition: AliasAnalysis.h:199
llvm::AliasSet::isMustAlias
bool isMustAlias() const
Definition: AliasSetTracker.h:203
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1347
llvm::isStrongerThanMonotonic
bool isStrongerThanMonotonic(AtomicOrdering AO)
Definition: AtomicOrdering.h:124
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:257
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:106
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::cl::desc
Definition: CommandLine.h:405
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:236
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:210
llvm::AliasSet::aliasesUnknownInst
bool aliasesUnknownInst(const Instruction *Inst, AAResults &AA) const
Definition: AliasSetTracker.cpp:230
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37