Line data Source code
1 : //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the AliasSetTracker and AliasSet classes.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "llvm/Analysis/AliasSetTracker.h"
15 : #include "llvm/Analysis/AliasAnalysis.h"
16 : #include "llvm/Analysis/GuardUtils.h"
17 : #include "llvm/Analysis/MemoryLocation.h"
18 : #include "llvm/Config/llvm-config.h"
19 : #include "llvm/IR/CallSite.h"
20 : #include "llvm/IR/Constants.h"
21 : #include "llvm/IR/DataLayout.h"
22 : #include "llvm/IR/Function.h"
23 : #include "llvm/IR/InstIterator.h"
24 : #include "llvm/IR/Instruction.h"
25 : #include "llvm/IR/Instructions.h"
26 : #include "llvm/IR/IntrinsicInst.h"
27 : #include "llvm/IR/Module.h"
28 : #include "llvm/IR/PatternMatch.h"
29 : #include "llvm/IR/Value.h"
30 : #include "llvm/Pass.h"
31 : #include "llvm/Support/AtomicOrdering.h"
32 : #include "llvm/Support/Casting.h"
33 : #include "llvm/Support/CommandLine.h"
34 : #include "llvm/Support/Compiler.h"
35 : #include "llvm/Support/Debug.h"
36 : #include "llvm/Support/ErrorHandling.h"
37 : #include "llvm/Support/raw_ostream.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 : ///
52 23820 : void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
53 : assert(!AS.Forward && "Alias set is already forwarding!");
54 : assert(!Forward && "This set is a forwarding set!!");
55 :
56 23820 : bool WasMustAlias = (Alias == SetMustAlias);
57 : // Update the alias and access types of this set...
58 23820 : Access |= AS.Access;
59 23820 : Alias |= AS.Alias;
60 :
61 23820 : 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 4289 : AliasAnalysis &AA = AST.getAliasAnalysis();
66 4289 : PointerRec *L = getSomePointer();
67 4289 : PointerRec *R = AS.getSomePointer();
68 :
69 : // If the pointers are not a must-alias pair, this set becomes a may alias.
70 8578 : if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
71 8578 : MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
72 : MustAlias)
73 4289 : Alias = SetMayAlias;
74 : }
75 :
76 23820 : if (Alias == SetMayAlias) {
77 23820 : if (WasMustAlias)
78 4477 : AST.TotalMayAliasSetSize += size();
79 23820 : if (AS.Alias == SetMustAlias)
80 23124 : AST.TotalMayAliasSetSize += AS.size();
81 : }
82 :
83 : bool ASHadUnknownInsts = !AS.UnknownInsts.empty();
84 23820 : if (UnknownInsts.empty()) { // Merge call sites...
85 23703 : if (ASHadUnknownInsts) {
86 : std::swap(UnknownInsts, AS.UnknownInsts);
87 : addRef();
88 : }
89 117 : } else if (ASHadUnknownInsts) {
90 0 : UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end());
91 : AS.UnknownInsts.clear();
92 : }
93 :
94 23820 : AS.Forward = this; // Forward across AS now...
95 : addRef(); // AS is now pointing to us...
96 :
97 : // Merge the list of constituent pointers...
98 23820 : if (AS.PtrList) {
99 23820 : SetSize += AS.size();
100 23820 : AS.SetSize = 0;
101 23820 : *PtrListEnd = AS.PtrList;
102 23820 : AS.PtrList->setPrevInList(PtrListEnd);
103 23820 : PtrListEnd = AS.PtrListEnd;
104 :
105 23820 : AS.PtrList = nullptr;
106 23820 : AS.PtrListEnd = &AS.PtrList;
107 : assert(*AS.PtrListEnd == nullptr && "End of list is not null?");
108 : }
109 23820 : if (ASHadUnknownInsts)
110 : AS.dropRef(AST);
111 23820 : }
112 :
113 21213 : void AliasSetTracker::removeAliasSet(AliasSet *AS) {
114 21213 : if (AliasSet *Fwd = AS->Forward) {
115 21204 : Fwd->dropRef(*this);
116 21204 : AS->Forward = nullptr;
117 : }
118 :
119 21213 : if (AS->Alias == AliasSet::SetMayAlias)
120 396 : TotalMayAliasSetSize -= AS->size();
121 :
122 : AliasSets.erase(AS);
123 21213 : }
124 :
125 21213 : void AliasSet::removeFromTracker(AliasSetTracker &AST) {
126 : assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
127 21213 : AST.removeAliasSet(this);
128 21213 : }
129 :
130 236245 : void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
131 : LocationSize Size, const AAMDNodes &AAInfo,
132 : bool KnownMustAlias) {
133 : assert(!Entry.hasAliasSet() && "Entry already in set!");
134 :
135 : // Check to see if we have to downgrade to _may_ alias.
136 236245 : if (isMustAlias() && !KnownMustAlias)
137 62020 : if (PointerRec *P = getSomePointer()) {
138 8098 : AliasAnalysis &AA = AST.getAliasAnalysis();
139 : AliasResult Result =
140 16196 : AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
141 8098 : MemoryLocation(Entry.getValue(), Size, AAInfo));
142 8098 : if (Result != MustAlias) {
143 7103 : Alias = SetMayAlias;
144 7103 : AST.TotalMayAliasSetSize += size();
145 : } else {
146 : // First entry of must alias must have maximum size!
147 995 : P->updateSizeAndAAInfo(Size, AAInfo);
148 : }
149 : assert(Result != NoAlias && "Cannot be part of must set!");
150 : }
151 :
152 : Entry.setAliasSet(this);
153 236245 : Entry.updateSizeAndAAInfo(Size, AAInfo);
154 :
155 : // Add it to the end of the list...
156 236245 : ++SetSize;
157 : assert(*PtrListEnd == nullptr && "End of list is not null?");
158 236245 : *PtrListEnd = &Entry;
159 236245 : PtrListEnd = Entry.setPrevInList(PtrListEnd);
160 : assert(*PtrListEnd == nullptr && "End of list is not null?");
161 : // Entry points to alias set.
162 : addRef();
163 :
164 236245 : if (Alias == SetMayAlias)
165 181312 : AST.TotalMayAliasSetSize++;
166 236245 : }
167 :
168 37724 : void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
169 37724 : if (UnknownInsts.empty())
170 : addRef();
171 37724 : UnknownInsts.emplace_back(I);
172 :
173 : // Guards are marked as modifying memory for control flow modelling purposes,
174 : // but don't actually modify any specific memory location.
175 : using namespace PatternMatch;
176 37724 : bool MayWriteMemory = I->mayWriteToMemory() && !isGuard(I) &&
177 44434 : !(I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()));
178 : if (!MayWriteMemory) {
179 978 : Alias = SetMayAlias;
180 978 : Access |= RefAccess;
181 978 : return;
182 : }
183 :
184 : // FIXME: This should use mod/ref information to make this not suck so bad
185 36746 : Alias = SetMayAlias;
186 36746 : Access = ModRefAccess;
187 : }
188 :
189 : /// aliasesPointer - Return true if the specified pointer "may" (or must)
190 : /// alias one of the members in the set.
191 : ///
192 363092 : bool AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
193 : const AAMDNodes &AAInfo,
194 : AliasAnalysis &AA) const {
195 363092 : if (AliasAny)
196 : return true;
197 :
198 363092 : if (Alias == SetMustAlias) {
199 : assert(UnknownInsts.empty() && "Illegal must alias set!");
200 :
201 : // If this is a set of MustAliases, only check to see if the pointer aliases
202 : // SOME value in the set.
203 185892 : PointerRec *SomePtr = getSomePointer();
204 : assert(SomePtr && "Empty must-alias set??");
205 371784 : return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
206 : SomePtr->getAAInfo()),
207 185892 : MemoryLocation(Ptr, Size, AAInfo));
208 : }
209 :
210 : // If this is a may-alias set, we have to check all of the pointers in the set
211 : // to be sure it doesn't alias the set...
212 3605222 : for (iterator I = begin(), E = end(); I != E; ++I)
213 3561649 : if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
214 3561649 : MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
215 : return true;
216 :
217 : // Check the unknown instructions...
218 43573 : if (!UnknownInsts.empty()) {
219 40017 : for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
220 : if (auto *Inst = getUnknownInst(i))
221 38684 : if (isModOrRefSet(
222 : AA.getModRefInfo(Inst, MemoryLocation(Ptr, Size, AAInfo))))
223 : return true;
224 : }
225 :
226 : return false;
227 : }
228 :
229 52813 : bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
230 : AliasAnalysis &AA) const {
231 :
232 52813 : if (AliasAny)
233 : return true;
234 :
235 51096 : if (!Inst->mayReadOrWriteMemory())
236 : return false;
237 :
238 102759 : for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
239 : if (auto *UnknownInst = getUnknownInst(i)) {
240 : ImmutableCallSite C1(UnknownInst), C2(Inst);
241 30068 : if (!C1 || !C2 || isModOrRefSet(AA.getModRefInfo(C1, C2)) ||
242 571 : isModOrRefSet(AA.getModRefInfo(C2, C1)))
243 : return true;
244 : }
245 : }
246 :
247 24520 : for (iterator I = begin(), E = end(); I != E; ++I)
248 22419 : if (isModOrRefSet(AA.getModRefInfo(
249 : Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()))))
250 : return true;
251 :
252 : return false;
253 : }
254 :
255 2407 : Instruction* AliasSet::getUniqueInstruction() {
256 2407 : if (AliasAny)
257 : // May have collapses alias set
258 : return nullptr;
259 2407 : if (begin() != end()) {
260 2383 : if (!UnknownInsts.empty())
261 : // Another instruction found
262 : return nullptr;
263 2311 : if (std::next(begin()) != end())
264 : // Another instruction found
265 : return nullptr;
266 2267 : Value *Addr = begin()->getValue();
267 : assert(!Addr->user_empty() &&
268 : "where's the instruction which added this pointer?");
269 2267 : if (std::next(Addr->user_begin()) != Addr->user_end())
270 : // Another instruction found -- this is really restrictive
271 : // TODO: generalize!
272 : return nullptr;
273 : return cast<Instruction>(*(Addr->user_begin()));
274 : }
275 48 : if (1 != UnknownInsts.size())
276 : return nullptr;
277 16 : return cast<Instruction>(UnknownInsts[0]);
278 : }
279 :
280 47596 : void AliasSetTracker::clear() {
281 : // Delete all the PointerRec entries.
282 47596 : for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
283 283689 : I != E; ++I)
284 236093 : I->second->eraseFromList();
285 :
286 47596 : PointerMap.clear();
287 :
288 : // The alias sets should all be clear now.
289 : AliasSets.clear();
290 47596 : }
291 :
292 :
293 : /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
294 : /// alias the pointer. Return the unified set, or nullptr if no set that aliases
295 : /// the pointer was found.
296 233890 : AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
297 : LocationSize Size,
298 : const AAMDNodes &AAInfo) {
299 : AliasSet *FoundSet = nullptr;
300 1114773 : for (iterator I = begin(), E = end(); I != E;) {
301 : iterator Cur = I++;
302 880883 : if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
303 :
304 189828 : if (!FoundSet) { // If this is the first alias set ptr can go into.
305 : FoundSet = &*Cur; // Remember it.
306 : } else { // Otherwise, we must merge the sets.
307 9860 : FoundSet->mergeSetIn(*Cur, *this); // Merge in contents.
308 : }
309 : }
310 :
311 233890 : return FoundSet;
312 : }
313 :
314 0 : bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
315 0 : for (const AliasSet &AS : *this)
316 0 : if (!AS.Forward && AS.aliasesUnknownInst(Inst, AA))
317 : return true;
318 : return false;
319 : }
320 :
321 37724 : AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
322 : AliasSet *FoundSet = nullptr;
323 192573 : for (iterator I = begin(), E = end(); I != E;) {
324 : iterator Cur = I++;
325 154849 : if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
326 : continue;
327 50707 : if (!FoundSet) // If this is the first alias set ptr can go into.
328 : FoundSet = &*Cur; // Remember it.
329 13885 : else if (!Cur->Forward) // Otherwise, we must merge the sets.
330 13885 : FoundSet->mergeSetIn(*Cur, *this); // Merge in contents.
331 : }
332 37724 : return FoundSet;
333 : }
334 :
335 906071 : AliasSet &AliasSetTracker::getAliasSetFor(const MemoryLocation &MemLoc) {
336 :
337 906071 : Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
338 906071 : const LocationSize Size = MemLoc.Size;
339 906071 : const AAMDNodes &AAInfo = MemLoc.AATags;
340 :
341 906071 : AliasSet::PointerRec &Entry = getEntryFor(Pointer);
342 :
343 906071 : if (AliasAnyAS) {
344 : // At this point, the AST is saturated, so we only have one active alias
345 : // set. That means we already know which alias set we want to return, and
346 : // just need to add the pointer to that set to keep the data structure
347 : // consistent.
348 : // This, of course, means that we will never need a merge here.
349 71145 : if (Entry.hasAliasSet()) {
350 66710 : Entry.updateSizeAndAAInfo(Size, AAInfo);
351 : assert(Entry.getAliasSet(*this) == AliasAnyAS &&
352 : "Entry in saturated AST must belong to only alias set");
353 : } else {
354 4435 : AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
355 : }
356 71145 : return *AliasAnyAS;
357 : }
358 :
359 : // Check to see if the pointer is already known.
360 834926 : if (Entry.hasAliasSet()) {
361 : // If the size changed, we may need to merge several alias sets.
362 : // Note that we can *not* return the result of mergeAliasSetsForPointer
363 : // due to a quirk of alias analysis behavior. Since alias(undef, undef)
364 : // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
365 : // the right set for undef, even if it exists.
366 603140 : if (Entry.updateSizeAndAAInfo(Size, AAInfo))
367 2104 : mergeAliasSetsForPointer(Pointer, Size, AAInfo);
368 : // Return the set!
369 603140 : return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
370 : }
371 :
372 231786 : if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
373 : // Add it to the alias set it aliases.
374 177864 : AS->addPointer(*this, Entry, Size, AAInfo);
375 177864 : return *AS;
376 : }
377 :
378 : // Otherwise create a new alias set to hold the loaded pointer.
379 53922 : AliasSets.push_back(new AliasSet());
380 53922 : AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
381 53922 : return AliasSets.back();
382 : }
383 :
384 7579 : void AliasSetTracker::add(Value *Ptr, LocationSize Size,
385 : const AAMDNodes &AAInfo) {
386 7579 : addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
387 7579 : }
388 :
389 231537 : void AliasSetTracker::add(LoadInst *LI) {
390 231537 : if (isStrongerThanMonotonic(LI->getOrdering()))
391 37 : return addUnknown(LI);
392 463000 : addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
393 : }
394 :
395 208808 : void AliasSetTracker::add(StoreInst *SI) {
396 208808 : if (isStrongerThanMonotonic(SI->getOrdering()))
397 9 : return addUnknown(SI);
398 417598 : addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
399 : }
400 :
401 1 : void AliasSetTracker::add(VAArgInst *VAAI) {
402 1 : addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
403 1 : }
404 :
405 292 : void AliasSetTracker::add(AnyMemSetInst *MSI) {
406 292 : addPointer(MemoryLocation::getForDest(MSI), AliasSet::ModAccess);
407 292 : }
408 :
409 619 : void AliasSetTracker::add(AnyMemTransferInst *MTI) {
410 619 : addPointer(MemoryLocation::getForDest(MTI), AliasSet::ModAccess);
411 619 : addPointer(MemoryLocation::getForSource(MTI), AliasSet::RefAccess);
412 619 : }
413 :
414 626698 : void AliasSetTracker::addUnknown(Instruction *Inst) {
415 : if (isa<DbgInfoIntrinsic>(Inst))
416 : return; // Ignore DbgInfo Intrinsics.
417 :
418 : if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
419 : // These intrinsics will show up as affecting memory, but they are just
420 : // markers.
421 824 : switch (II->getIntrinsicID()) {
422 : default:
423 : break;
424 : // FIXME: Add lifetime/invariant intrinsics (See: PR30807).
425 : case Intrinsic::assume:
426 : case Intrinsic::sideeffect:
427 : return;
428 : }
429 : }
430 511129 : if (!Inst->mayReadOrWriteMemory())
431 : return; // doesn't alias anything
432 :
433 37724 : AliasSet *AS = findAliasSetForUnknownInst(Inst);
434 37724 : if (AS) {
435 36822 : AS->addUnknownInst(Inst, AA);
436 36822 : return;
437 : }
438 902 : AliasSets.push_back(new AliasSet());
439 : AS = &AliasSets.back();
440 902 : AS->addUnknownInst(Inst, AA);
441 : }
442 :
443 1092087 : void AliasSetTracker::add(Instruction *I) {
444 : // Dispatch to one of the other add methods.
445 : if (LoadInst *LI = dyn_cast<LoadInst>(I))
446 231537 : return add(LI);
447 : if (StoreInst *SI = dyn_cast<StoreInst>(I))
448 208808 : return add(SI);
449 : if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
450 1 : return add(VAAI);
451 : if (AnyMemSetInst *MSI = dyn_cast<AnyMemSetInst>(I))
452 292 : return add(MSI);
453 : if (AnyMemTransferInst *MTI = dyn_cast<AnyMemTransferInst>(I))
454 619 : return add(MTI);
455 :
456 : // Handle all calls with known mod/ref sets genericall
457 : CallSite CS(I);
458 650830 : if (CS && CS.onlyAccessesArgMemory()) {
459 : auto getAccessFromModRef = [](ModRefInfo MRI) {
460 24258 : if (isRefSet(MRI) && isModSet(MRI))
461 : return AliasSet::ModRefAccess;
462 335 : else if (isModSet(MRI))
463 : return AliasSet::ModAccess;
464 300 : else if (isRefSet(MRI))
465 : return AliasSet::RefAccess;
466 : else
467 : return AliasSet::NoAccess;
468 :
469 : };
470 :
471 48512 : ModRefInfo CallMask = createModRefInfo(AA.getModRefBehavior(CS));
472 :
473 : // Some intrinsics are marked as modifying memory for control flow
474 : // modelling purposes, but don't actually modify any specific memory
475 : // location.
476 : using namespace PatternMatch;
477 48231 : if (I->use_empty() && match(I, m_Intrinsic<Intrinsic::invariant_start>()))
478 : CallMask = clearMod(CallMask);
479 :
480 73031 : for (auto AI = CS.arg_begin(), AE = CS.arg_end(); AI != AE; ++AI) {
481 48775 : const Value *Arg = *AI;
482 97550 : if (!Arg->getType()->isPointerTy())
483 24516 : continue;
484 24259 : unsigned ArgIdx = std::distance(CS.arg_begin(), AI);
485 : MemoryLocation ArgLoc = MemoryLocation::getForArgument(CS, ArgIdx,
486 24259 : nullptr);
487 48518 : ModRefInfo ArgMask = AA.getArgModRefInfo(CS, ArgIdx);
488 : ArgMask = intersectModRef(CallMask, ArgMask);
489 24259 : if (!isNoModRef(ArgMask))
490 24258 : addPointer(ArgLoc, getAccessFromModRef(ArgMask));
491 : }
492 : return;
493 : }
494 :
495 626574 : return addUnknown(I);
496 : }
497 :
498 97094 : void AliasSetTracker::add(BasicBlock &BB) {
499 1180200 : for (auto &I : BB)
500 1083106 : add(&I);
501 97094 : }
502 :
503 21680 : void AliasSetTracker::add(const AliasSetTracker &AST) {
504 : assert(&AA == &AST.AA &&
505 : "Merging AliasSetTracker objects with different Alias Analyses!");
506 :
507 : // Loop over all of the alias sets in AST, adding the pointers contained
508 : // therein into the current alias sets. This can cause alias sets to be
509 : // merged together in the current AST.
510 23203 : for (const AliasSet &AS : AST) {
511 1523 : if (AS.Forward)
512 : continue; // Ignore forwarding alias sets
513 :
514 : // If there are any call sites in the alias set, add them to this AST.
515 4499 : for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
516 : if (auto *Inst = AS.getUnknownInst(i))
517 1673 : add(Inst);
518 :
519 : // Loop over all of the pointers in this alias set.
520 15539 : for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI)
521 14126 : addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
522 28252 : (AliasSet::AccessLattice)AS.Access);
523 : }
524 21680 : }
525 :
526 : // deleteValue method - This method is used to remove a pointer value from the
527 : // AliasSetTracker entirely. It should be used when an instruction is deleted
528 : // from the program to update the AST. If you don't use this, you would have
529 : // dangling pointers to deleted instructions.
530 : //
531 1393 : void AliasSetTracker::deleteValue(Value *PtrVal) {
532 : // First, look up the PointerRec for this pointer.
533 1393 : PointerMapType::iterator I = PointerMap.find_as(PtrVal);
534 1393 : if (I == PointerMap.end()) return; // Noop
535 :
536 : // If we found one, remove the pointer from the alias set it is in.
537 34 : AliasSet::PointerRec *PtrValEnt = I->second;
538 34 : AliasSet *AS = PtrValEnt->getAliasSet(*this);
539 :
540 : // Unlink and delete from the list of values.
541 34 : PtrValEnt->eraseFromList();
542 :
543 34 : if (AS->Alias == AliasSet::SetMayAlias) {
544 6 : AS->SetSize--;
545 6 : TotalMayAliasSetSize--;
546 : }
547 :
548 : // Stop using the alias set.
549 : AS->dropRef(*this);
550 :
551 34 : PointerMap.erase(I);
552 : }
553 :
554 : // copyValue - This method should be used whenever a preexisting value in the
555 : // program is copied or cloned, introducing a new value. Note that it is ok for
556 : // clients that use this method to introduce the same value multiple times: if
557 : // the tracker already knows about a value, it will ignore the request.
558 : //
559 477 : void AliasSetTracker::copyValue(Value *From, Value *To) {
560 : // First, look up the PointerRec for this pointer.
561 477 : PointerMapType::iterator I = PointerMap.find_as(From);
562 477 : if (I == PointerMap.end())
563 453 : return; // Noop
564 : assert(I->second->hasAliasSet() && "Dead entry?");
565 :
566 48 : AliasSet::PointerRec &Entry = getEntryFor(To);
567 48 : if (Entry.hasAliasSet()) return; // Already in the tracker!
568 :
569 : // getEntryFor above may invalidate iterator \c I, so reinitialize it.
570 24 : I = PointerMap.find_as(From);
571 : // Add it to the alias set it aliases...
572 24 : AliasSet *AS = I->second->getAliasSet(*this);
573 24 : AS->addPointer(*this, Entry, I->second->getSize(),
574 48 : I->second->getAAInfo(),
575 : true);
576 : }
577 :
578 62 : AliasSet &AliasSetTracker::mergeAllAliasSets() {
579 : assert(!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold) &&
580 : "Full merge should happen once, when the saturation threshold is "
581 : "reached");
582 :
583 : // Collect all alias sets, so that we can drop references with impunity
584 : // without worrying about iterator invalidation.
585 : std::vector<AliasSet *> ASVector;
586 62 : ASVector.reserve(SaturationThreshold);
587 168 : for (iterator I = begin(), E = end(); I != E; I++)
588 106 : ASVector.push_back(&*I);
589 :
590 : // Copy all instructions and pointers into a new set, and forward all other
591 : // sets to it.
592 62 : AliasSets.push_back(new AliasSet());
593 62 : AliasAnyAS = &AliasSets.back();
594 62 : AliasAnyAS->Alias = AliasSet::SetMayAlias;
595 62 : AliasAnyAS->Access = AliasSet::ModRefAccess;
596 62 : AliasAnyAS->AliasAny = true;
597 :
598 168 : for (auto Cur : ASVector) {
599 : // If Cur was already forwarding, just forward to the new AS instead.
600 106 : AliasSet *FwdTo = Cur->Forward;
601 106 : if (FwdTo) {
602 31 : Cur->Forward = AliasAnyAS;
603 : AliasAnyAS->addRef();
604 : FwdTo->dropRef(*this);
605 31 : continue;
606 : }
607 :
608 : // Otherwise, perform the actual merge.
609 75 : AliasAnyAS->mergeSetIn(*Cur, *this);
610 : }
611 :
612 62 : return *AliasAnyAS;
613 : }
614 :
615 487793 : AliasSet &AliasSetTracker::addPointer(Value *P, LocationSize Size,
616 : const AAMDNodes &AAInfo,
617 : AliasSet::AccessLattice E) {
618 487793 : AliasSet &AS = getAliasSetFor(MemoryLocation(P, Size, AAInfo));
619 487793 : AS.Access |= E;
620 :
621 487793 : if (!AliasAnyAS && (TotalMayAliasSetSize > SaturationThreshold)) {
622 : // The AST is now saturated. From here on, we conservatively consider all
623 : // pointers to alias each-other.
624 62 : return mergeAllAliasSets();
625 : }
626 :
627 : return AS;
628 : }
629 :
630 : //===----------------------------------------------------------------------===//
631 : // AliasSet/AliasSetTracker Printing Support
632 : //===----------------------------------------------------------------------===//
633 :
634 270 : void AliasSet::print(raw_ostream &OS) const {
635 270 : OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] ";
636 397 : OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
637 270 : switch (Access) {
638 0 : case NoAccess: OS << "No access "; break;
639 94 : case RefAccess: OS << "Ref "; break;
640 91 : case ModAccess: OS << "Mod "; break;
641 85 : case ModRefAccess: OS << "Mod/Ref "; break;
642 0 : default: llvm_unreachable("Bad value for Access!");
643 : }
644 270 : if (Forward)
645 5 : OS << " forwarding to " << (void*)Forward;
646 :
647 270 : if (!empty()) {
648 252 : OS << "Pointers: ";
649 642 : for (iterator I = begin(), E = end(); I != E; ++I) {
650 390 : if (I != begin()) OS << ", ";
651 390 : I.getPointer()->printAsOperand(OS << "(");
652 390 : if (I.getSize() == LocationSize::unknown())
653 22 : OS << ", unknown)";
654 : else
655 736 : OS << ", " << I.getSize() << ")";
656 : }
657 : }
658 270 : if (!UnknownInsts.empty()) {
659 111 : OS << "\n " << UnknownInsts.size() << " Unknown instructions: ";
660 369 : for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
661 147 : if (i) OS << ", ";
662 : if (auto *I = getUnknownInst(i)) {
663 147 : if (I->hasName())
664 0 : I->printAsOperand(OS);
665 : else
666 147 : I->print(OS);
667 : }
668 : }
669 : }
670 270 : OS << "\n";
671 270 : }
672 :
673 148 : void AliasSetTracker::print(raw_ostream &OS) const {
674 296 : OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
675 148 : << PointerMap.size() << " pointer values.\n";
676 418 : for (const AliasSet &AS : *this)
677 270 : AS.print(OS);
678 148 : OS << "\n";
679 148 : }
680 :
681 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
682 : LLVM_DUMP_METHOD void AliasSet::dump() const { print(dbgs()); }
683 : LLVM_DUMP_METHOD void AliasSetTracker::dump() const { print(dbgs()); }
684 : #endif
685 :
686 : //===----------------------------------------------------------------------===//
687 : // ASTCallbackVH Class Implementation
688 : //===----------------------------------------------------------------------===//
689 :
690 2 : void AliasSetTracker::ASTCallbackVH::deleted() {
691 : assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
692 2 : AST->deleteValue(getValPtr());
693 : // this now dangles!
694 2 : }
695 :
696 28 : void AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) {
697 28 : AST->copyValue(getValPtr(), V);
698 28 : }
699 :
700 3846034 : AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
701 3846034 : : CallbackVH(V), AST(ast) {}
702 :
703 : AliasSetTracker::ASTCallbackVH &
704 0 : AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
705 0 : return *this = ASTCallbackVH(V, AST);
706 : }
707 :
708 : //===----------------------------------------------------------------------===//
709 : // AliasSetPrinter Pass
710 : //===----------------------------------------------------------------------===//
711 :
712 : namespace {
713 :
714 : class AliasSetPrinter : public FunctionPass {
715 : AliasSetTracker *Tracker;
716 :
717 : public:
718 : static char ID; // Pass identification, replacement for typeid
719 :
720 8 : AliasSetPrinter() : FunctionPass(ID) {
721 8 : initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry());
722 : }
723 :
724 8 : void getAnalysisUsage(AnalysisUsage &AU) const override {
725 : AU.setPreservesAll();
726 : AU.addRequired<AAResultsWrapperPass>();
727 8 : }
728 :
729 148 : bool runOnFunction(Function &F) override {
730 148 : auto &AAWP = getAnalysis<AAResultsWrapperPass>();
731 148 : Tracker = new AliasSetTracker(AAWP.getAAResults());
732 148 : errs() << "Alias sets for function '" << F.getName() << "':\n";
733 837 : for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
734 1674 : Tracker->add(&*I);
735 148 : Tracker->print(errs());
736 148 : delete Tracker;
737 148 : return false;
738 : }
739 : };
740 :
741 : } // end anonymous namespace
742 :
743 : char AliasSetPrinter::ID = 0;
744 :
745 10756 : INITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets",
746 : "Alias Set Printer", false, true)
747 10756 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
748 21520 : INITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets",
749 : "Alias Set Printer", false, true)
|
