1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the AliasSetTracker and AliasSet classes.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/AliasSetTracker.h"
15 #include "llvm/Analysis/AliasAnalysis.h"
16 #include "llvm/Instructions.h"
17 #include "llvm/IntrinsicInst.h"
18 #include "llvm/Pass.h"
19 #include "llvm/Type.h"
20 #include "llvm/Target/TargetData.h"
21 #include "llvm/Assembly/Writer.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/InstIterator.h"
24 #include "llvm/Support/Format.h"
25 #include "llvm/Support/raw_ostream.h"
28 /// mergeSetIn - Merge the specified alias set into this alias set.
30 void AliasSet::mergeSetIn(AliasSet
&AS
, AliasSetTracker
&AST
) {
31 assert(!AS
.Forward
&& "Alias set is already forwarding!");
32 assert(!Forward
&& "This set is a forwarding set!!");
34 // Update the alias and access types of this set...
35 AccessTy
|= AS
.AccessTy
;
36 AliasTy
|= AS
.AliasTy
;
38 if (AliasTy
== MustAlias
) {
39 // Check that these two merged sets really are must aliases. Since both
40 // used to be must-alias sets, we can just check any pointer from each set
42 AliasAnalysis
&AA
= AST
.getAliasAnalysis();
43 PointerRec
*L
= getSomePointer();
44 PointerRec
*R
= AS
.getSomePointer();
46 // If the pointers are not a must-alias pair, this set becomes a may alias.
47 if (AA
.alias(L
->getValue(), L
->getSize(), R
->getValue(), R
->getSize())
48 != AliasAnalysis::MustAlias
)
52 if (CallSites
.empty()) { // Merge call sites...
53 if (!AS
.CallSites
.empty())
54 std::swap(CallSites
, AS
.CallSites
);
55 } else if (!AS
.CallSites
.empty()) {
56 CallSites
.insert(CallSites
.end(), AS
.CallSites
.begin(), AS
.CallSites
.end());
60 AS
.Forward
= this; // Forward across AS now...
61 addRef(); // AS is now pointing to us...
63 // Merge the list of constituent pointers...
65 *PtrListEnd
= AS
.PtrList
;
66 AS
.PtrList
->setPrevInList(PtrListEnd
);
67 PtrListEnd
= AS
.PtrListEnd
;
70 AS
.PtrListEnd
= &AS
.PtrList
;
71 assert(*AS
.PtrListEnd
== 0 && "End of list is not null?");
75 void AliasSetTracker::removeAliasSet(AliasSet
*AS
) {
76 if (AliasSet
*Fwd
= AS
->Forward
) {
83 void AliasSet::removeFromTracker(AliasSetTracker
&AST
) {
84 assert(RefCount
== 0 && "Cannot remove non-dead alias set from tracker!");
85 AST
.removeAliasSet(this);
88 void AliasSet::addPointer(AliasSetTracker
&AST
, PointerRec
&Entry
,
89 unsigned Size
, bool KnownMustAlias
) {
90 assert(!Entry
.hasAliasSet() && "Entry already in set!");
92 // Check to see if we have to downgrade to _may_ alias.
93 if (isMustAlias() && !KnownMustAlias
)
94 if (PointerRec
*P
= getSomePointer()) {
95 AliasAnalysis
&AA
= AST
.getAliasAnalysis();
96 AliasAnalysis::AliasResult Result
=
97 AA
.alias(P
->getValue(), P
->getSize(), Entry
.getValue(), Size
);
98 if (Result
== AliasAnalysis::MayAlias
)
100 else // First entry of must alias must have maximum size!
102 assert(Result
!= AliasAnalysis::NoAlias
&& "Cannot be part of must set!");
105 Entry
.setAliasSet(this);
106 Entry
.updateSize(Size
);
108 // Add it to the end of the list...
109 assert(*PtrListEnd
== 0 && "End of list is not null?");
110 *PtrListEnd
= &Entry
;
111 PtrListEnd
= Entry
.setPrevInList(PtrListEnd
);
112 assert(*PtrListEnd
== 0 && "End of list is not null?");
113 addRef(); // Entry points to alias set...
116 void AliasSet::addCallSite(CallSite CS
, AliasAnalysis
&AA
) {
117 CallSites
.push_back(CS
);
119 AliasAnalysis::ModRefBehavior Behavior
= AA
.getModRefBehavior(CS
);
120 if (Behavior
== AliasAnalysis::DoesNotAccessMemory
)
122 else if (Behavior
== AliasAnalysis::OnlyReadsMemory
) {
128 // FIXME: This should use mod/ref information to make this not suck so bad
133 /// aliasesPointer - Return true if the specified pointer "may" (or must)
134 /// alias one of the members in the set.
136 bool AliasSet::aliasesPointer(const Value
*Ptr
, unsigned Size
,
137 AliasAnalysis
&AA
) const {
138 if (AliasTy
== MustAlias
) {
139 assert(CallSites
.empty() && "Illegal must alias set!");
141 // If this is a set of MustAliases, only check to see if the pointer aliases
142 // SOME value in the set...
143 PointerRec
*SomePtr
= getSomePointer();
144 assert(SomePtr
&& "Empty must-alias set??");
145 return AA
.alias(SomePtr
->getValue(), SomePtr
->getSize(), Ptr
, Size
);
148 // If this is a may-alias set, we have to check all of the pointers in the set
149 // to be sure it doesn't alias the set...
150 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
151 if (AA
.alias(Ptr
, Size
, I
.getPointer(), I
.getSize()))
154 // Check the call sites list and invoke list...
155 if (!CallSites
.empty()) {
156 if (AA
.hasNoModRefInfoForCalls())
159 for (unsigned i
= 0, e
= CallSites
.size(); i
!= e
; ++i
)
160 if (AA
.getModRefInfo(CallSites
[i
], const_cast<Value
*>(Ptr
), Size
)
161 != AliasAnalysis::NoModRef
)
168 bool AliasSet::aliasesCallSite(CallSite CS
, AliasAnalysis
&AA
) const {
169 if (AA
.doesNotAccessMemory(CS
))
172 if (AA
.hasNoModRefInfoForCalls())
175 for (unsigned i
= 0, e
= CallSites
.size(); i
!= e
; ++i
)
176 if (AA
.getModRefInfo(CallSites
[i
], CS
) != AliasAnalysis::NoModRef
||
177 AA
.getModRefInfo(CS
, CallSites
[i
]) != AliasAnalysis::NoModRef
)
180 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
181 if (AA
.getModRefInfo(CS
, I
.getPointer(), I
.getSize()) !=
182 AliasAnalysis::NoModRef
)
188 void AliasSetTracker::clear() {
189 // Delete all the PointerRec entries.
190 for (PointerMapType::iterator I
= PointerMap
.begin(), E
= PointerMap
.end();
192 I
->second
->eraseFromList();
196 // The alias sets should all be clear now.
201 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
202 /// instruction referring to the pointer into. If there are multiple alias sets
203 /// that may alias the pointer, merge them together and return the unified set.
205 AliasSet
*AliasSetTracker::findAliasSetForPointer(const Value
*Ptr
,
207 AliasSet
*FoundSet
= 0;
208 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
209 if (!I
->Forward
&& I
->aliasesPointer(Ptr
, Size
, AA
)) {
210 if (FoundSet
== 0) { // If this is the first alias set ptr can go into.
211 FoundSet
= I
; // Remember it.
212 } else { // Otherwise, we must merge the sets.
213 FoundSet
->mergeSetIn(*I
, *this); // Merge in contents.
220 /// containsPointer - Return true if the specified location is represented by
221 /// this alias set, false otherwise. This does not modify the AST object or
223 bool AliasSetTracker::containsPointer(Value
*Ptr
, unsigned Size
) const {
224 for (const_iterator I
= begin(), E
= end(); I
!= E
; ++I
)
225 if (!I
->Forward
&& I
->aliasesPointer(Ptr
, Size
, AA
))
232 AliasSet
*AliasSetTracker::findAliasSetForCallSite(CallSite CS
) {
233 AliasSet
*FoundSet
= 0;
234 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
)
235 if (!I
->Forward
&& I
->aliasesCallSite(CS
, AA
)) {
236 if (FoundSet
== 0) { // If this is the first alias set ptr can go into.
237 FoundSet
= I
; // Remember it.
238 } else if (!I
->Forward
) { // Otherwise, we must merge the sets.
239 FoundSet
->mergeSetIn(*I
, *this); // Merge in contents.
249 /// getAliasSetForPointer - Return the alias set that the specified pointer
251 AliasSet
&AliasSetTracker::getAliasSetForPointer(Value
*Pointer
, unsigned Size
,
253 AliasSet::PointerRec
&Entry
= getEntryFor(Pointer
);
255 // Check to see if the pointer is already known...
256 if (Entry
.hasAliasSet()) {
257 Entry
.updateSize(Size
);
259 return *Entry
.getAliasSet(*this)->getForwardedTarget(*this);
260 } else if (AliasSet
*AS
= findAliasSetForPointer(Pointer
, Size
)) {
261 // Add it to the alias set it aliases...
262 AS
->addPointer(*this, Entry
, Size
);
265 if (New
) *New
= true;
266 // Otherwise create a new alias set to hold the loaded pointer...
267 AliasSets
.push_back(new AliasSet());
268 AliasSets
.back().addPointer(*this, Entry
, Size
);
269 return AliasSets
.back();
273 bool AliasSetTracker::add(Value
*Ptr
, unsigned Size
) {
275 addPointer(Ptr
, Size
, AliasSet::NoModRef
, NewPtr
);
280 bool AliasSetTracker::add(LoadInst
*LI
) {
282 AliasSet
&AS
= addPointer(LI
->getOperand(0),
283 AA
.getTypeStoreSize(LI
->getType()),
284 AliasSet::Refs
, NewPtr
);
285 if (LI
->isVolatile()) AS
.setVolatile();
289 bool AliasSetTracker::add(StoreInst
*SI
) {
291 Value
*Val
= SI
->getOperand(0);
292 AliasSet
&AS
= addPointer(SI
->getOperand(1),
293 AA
.getTypeStoreSize(Val
->getType()),
294 AliasSet::Mods
, NewPtr
);
295 if (SI
->isVolatile()) AS
.setVolatile();
299 bool AliasSetTracker::add(FreeInst
*FI
) {
301 addPointer(FI
->getOperand(0), ~0, AliasSet::Mods
, NewPtr
);
305 bool AliasSetTracker::add(VAArgInst
*VAAI
) {
307 addPointer(VAAI
->getOperand(0), ~0, AliasSet::ModRef
, NewPtr
);
312 bool AliasSetTracker::add(CallSite CS
) {
313 if (isa
<DbgInfoIntrinsic
>(CS
.getInstruction()))
314 return true; // Ignore DbgInfo Intrinsics.
315 if (AA
.doesNotAccessMemory(CS
))
316 return true; // doesn't alias anything
318 AliasSet
*AS
= findAliasSetForCallSite(CS
);
320 AliasSets
.push_back(new AliasSet());
321 AS
= &AliasSets
.back();
322 AS
->addCallSite(CS
, AA
);
325 AS
->addCallSite(CS
, AA
);
330 bool AliasSetTracker::add(Instruction
*I
) {
331 // Dispatch to one of the other add methods...
332 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
))
334 else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
))
336 else if (CallInst
*CI
= dyn_cast
<CallInst
>(I
))
338 else if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(I
))
340 else if (FreeInst
*FI
= dyn_cast
<FreeInst
>(I
))
342 else if (VAArgInst
*VAAI
= dyn_cast
<VAArgInst
>(I
))
347 void AliasSetTracker::add(BasicBlock
&BB
) {
348 for (BasicBlock::iterator I
= BB
.begin(), E
= BB
.end(); I
!= E
; ++I
)
352 void AliasSetTracker::add(const AliasSetTracker
&AST
) {
353 assert(&AA
== &AST
.AA
&&
354 "Merging AliasSetTracker objects with different Alias Analyses!");
356 // Loop over all of the alias sets in AST, adding the pointers contained
357 // therein into the current alias sets. This can cause alias sets to be
358 // merged together in the current AST.
359 for (const_iterator I
= AST
.begin(), E
= AST
.end(); I
!= E
; ++I
)
360 if (!I
->Forward
) { // Ignore forwarding alias sets
361 AliasSet
&AS
= const_cast<AliasSet
&>(*I
);
363 // If there are any call sites in the alias set, add them to this AST.
364 for (unsigned i
= 0, e
= AS
.CallSites
.size(); i
!= e
; ++i
)
365 add(AS
.CallSites
[i
]);
367 // Loop over all of the pointers in this alias set...
368 AliasSet::iterator I
= AS
.begin(), E
= AS
.end();
370 for (; I
!= E
; ++I
) {
371 AliasSet
&NewAS
= addPointer(I
.getPointer(), I
.getSize(),
372 (AliasSet::AccessType
)AS
.AccessTy
, X
);
373 if (AS
.isVolatile()) NewAS
.setVolatile();
378 /// remove - Remove the specified (potentially non-empty) alias set from the
380 void AliasSetTracker::remove(AliasSet
&AS
) {
381 // Drop all call sites.
382 AS
.CallSites
.clear();
384 // Clear the alias set.
385 unsigned NumRefs
= 0;
386 while (!AS
.empty()) {
387 AliasSet::PointerRec
*P
= AS
.PtrList
;
389 Value
*ValToRemove
= P
->getValue();
391 // Unlink and delete entry from the list of values.
394 // Remember how many references need to be dropped.
397 // Finally, remove the entry.
398 PointerMap
.erase(ValToRemove
);
401 // Stop using the alias set, removing it.
402 AS
.RefCount
-= NumRefs
;
403 if (AS
.RefCount
== 0)
404 AS
.removeFromTracker(*this);
407 bool AliasSetTracker::remove(Value
*Ptr
, unsigned Size
) {
408 AliasSet
*AS
= findAliasSetForPointer(Ptr
, Size
);
409 if (!AS
) return false;
414 bool AliasSetTracker::remove(LoadInst
*LI
) {
415 unsigned Size
= AA
.getTypeStoreSize(LI
->getType());
416 AliasSet
*AS
= findAliasSetForPointer(LI
->getOperand(0), Size
);
417 if (!AS
) return false;
422 bool AliasSetTracker::remove(StoreInst
*SI
) {
423 unsigned Size
= AA
.getTypeStoreSize(SI
->getOperand(0)->getType());
424 AliasSet
*AS
= findAliasSetForPointer(SI
->getOperand(1), Size
);
425 if (!AS
) return false;
430 bool AliasSetTracker::remove(FreeInst
*FI
) {
431 AliasSet
*AS
= findAliasSetForPointer(FI
->getOperand(0), ~0);
432 if (!AS
) return false;
437 bool AliasSetTracker::remove(VAArgInst
*VAAI
) {
438 AliasSet
*AS
= findAliasSetForPointer(VAAI
->getOperand(0), ~0);
439 if (!AS
) return false;
444 bool AliasSetTracker::remove(CallSite CS
) {
445 if (AA
.doesNotAccessMemory(CS
))
446 return false; // doesn't alias anything
448 AliasSet
*AS
= findAliasSetForCallSite(CS
);
449 if (!AS
) return false;
454 bool AliasSetTracker::remove(Instruction
*I
) {
455 // Dispatch to one of the other remove methods...
456 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
))
458 else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
))
460 else if (CallInst
*CI
= dyn_cast
<CallInst
>(I
))
462 else if (FreeInst
*FI
= dyn_cast
<FreeInst
>(I
))
464 else if (VAArgInst
*VAAI
= dyn_cast
<VAArgInst
>(I
))
470 // deleteValue method - This method is used to remove a pointer value from the
471 // AliasSetTracker entirely. It should be used when an instruction is deleted
472 // from the program to update the AST. If you don't use this, you would have
473 // dangling pointers to deleted instructions.
475 void AliasSetTracker::deleteValue(Value
*PtrVal
) {
476 // Notify the alias analysis implementation that this value is gone.
477 AA
.deleteValue(PtrVal
);
479 // If this is a call instruction, remove the callsite from the appropriate
481 CallSite CS
= CallSite::get(PtrVal
);
482 if (CS
.getInstruction())
483 if (!AA
.doesNotAccessMemory(CS
))
484 if (AliasSet
*AS
= findAliasSetForCallSite(CS
))
485 AS
->removeCallSite(CS
);
487 // First, look up the PointerRec for this pointer.
488 PointerMapType::iterator I
= PointerMap
.find(PtrVal
);
489 if (I
== PointerMap
.end()) return; // Noop
491 // If we found one, remove the pointer from the alias set it is in.
492 AliasSet::PointerRec
*PtrValEnt
= I
->second
;
493 AliasSet
*AS
= PtrValEnt
->getAliasSet(*this);
495 // Unlink and delete from the list of values.
496 PtrValEnt
->eraseFromList();
498 // Stop using the alias set.
504 // copyValue - This method should be used whenever a preexisting value in the
505 // program is copied or cloned, introducing a new value. Note that it is ok for
506 // clients that use this method to introduce the same value multiple times: if
507 // the tracker already knows about a value, it will ignore the request.
509 void AliasSetTracker::copyValue(Value
*From
, Value
*To
) {
510 // Notify the alias analysis implementation that this value is copied.
511 AA
.copyValue(From
, To
);
513 // First, look up the PointerRec for this pointer.
514 PointerMapType::iterator I
= PointerMap
.find(From
);
515 if (I
== PointerMap
.end())
517 assert(I
->second
->hasAliasSet() && "Dead entry?");
519 AliasSet::PointerRec
&Entry
= getEntryFor(To
);
520 if (Entry
.hasAliasSet()) return; // Already in the tracker!
522 // Add it to the alias set it aliases...
523 I
= PointerMap
.find(From
);
524 AliasSet
*AS
= I
->second
->getAliasSet(*this);
525 AS
->addPointer(*this, Entry
, I
->second
->getSize(), true);
530 //===----------------------------------------------------------------------===//
531 // AliasSet/AliasSetTracker Printing Support
532 //===----------------------------------------------------------------------===//
534 void AliasSet::print(raw_ostream
&OS
) const {
535 OS
<< " AliasSet[" << format("0x%p", (void*)this) << "," << RefCount
<< "] ";
536 OS
<< (AliasTy
== MustAlias
? "must" : "may") << " alias, ";
538 case NoModRef
: OS
<< "No access "; break;
539 case Refs
: OS
<< "Ref "; break;
540 case Mods
: OS
<< "Mod "; break;
541 case ModRef
: OS
<< "Mod/Ref "; break;
542 default: llvm_unreachable("Bad value for AccessTy!");
544 if (isVolatile()) OS
<< "[volatile] ";
546 OS
<< " forwarding to " << (void*)Forward
;
551 for (iterator I
= begin(), E
= end(); I
!= E
; ++I
) {
552 if (I
!= begin()) OS
<< ", ";
553 WriteAsOperand(OS
<< "(", I
.getPointer());
554 OS
<< ", " << I
.getSize() << ")";
557 if (!CallSites
.empty()) {
558 OS
<< "\n " << CallSites
.size() << " Call Sites: ";
559 for (unsigned i
= 0, e
= CallSites
.size(); i
!= e
; ++i
) {
561 WriteAsOperand(OS
, CallSites
[i
].getCalledValue());
567 void AliasSetTracker::print(raw_ostream
&OS
) const {
568 OS
<< "Alias Set Tracker: " << AliasSets
.size() << " alias sets for "
569 << PointerMap
.size() << " pointer values.\n";
570 for (const_iterator I
= begin(), E
= end(); I
!= E
; ++I
)
575 void AliasSet::dump() const { print(errs()); }
576 void AliasSetTracker::dump() const { print(errs()); }
578 //===----------------------------------------------------------------------===//
579 // ASTCallbackVH Class Implementation
580 //===----------------------------------------------------------------------===//
582 void AliasSetTracker::ASTCallbackVH::deleted() {
583 assert(AST
&& "ASTCallbackVH called with a null AliasSetTracker!");
584 AST
->deleteValue(getValPtr());
588 AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value
*V
, AliasSetTracker
*ast
)
589 : CallbackVH(V
), AST(ast
) {}
591 AliasSetTracker::ASTCallbackVH
&
592 AliasSetTracker::ASTCallbackVH::operator=(Value
*V
) {
593 return *this = ASTCallbackVH(V
, AST
);
596 //===----------------------------------------------------------------------===//
597 // AliasSetPrinter Pass
598 //===----------------------------------------------------------------------===//
601 class AliasSetPrinter
: public FunctionPass
{
602 AliasSetTracker
*Tracker
;
604 static char ID
; // Pass identification, replacement for typeid
605 AliasSetPrinter() : FunctionPass(&ID
) {}
607 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
608 AU
.setPreservesAll();
609 AU
.addRequired
<AliasAnalysis
>();
612 virtual bool runOnFunction(Function
&F
) {
613 Tracker
= new AliasSetTracker(getAnalysis
<AliasAnalysis
>());
615 for (inst_iterator I
= inst_begin(F
), E
= inst_end(F
); I
!= E
; ++I
)
617 Tracker
->print(errs());
624 char AliasSetPrinter::ID
= 0;
625 static RegisterPass
<AliasSetPrinter
>
626 X("print-alias-sets", "Alias Set Printer", false, true);