1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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/iMemory.h"
17 #include "llvm/iOther.h"
18 #include "llvm/iTerminators.h"
19 #include "llvm/Pass.h"
20 #include "llvm/Target/TargetData.h"
21 #include "llvm/Assembly/Writer.h"
22 #include "llvm/Support/InstIterator.h"
25 /// mergeSetIn - Merge the specified alias set into this alias set...
27 void AliasSet::mergeSetIn(AliasSet &AS) {
28 assert(!AS.Forward && "Alias set is already forwarding!");
29 assert(!Forward && "This set is a forwarding set!!");
31 // Update the alias and access types of this set...
32 AccessTy |= AS.AccessTy;
33 AliasTy |= AS.AliasTy;
35 if (CallSites.empty()) { // Merge call sites...
36 if (!AS.CallSites.empty())
37 std::swap(CallSites, AS.CallSites);
38 } else if (!AS.CallSites.empty()) {
39 CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end());
43 // FIXME: If AS's refcount is zero, nuke it now...
44 assert(RefCount != 0);
46 AS.Forward = this; // Forward across AS now...
47 RefCount++; // AS is now pointing to us...
49 // Merge the list of constituent pointers...
51 *PtrListEnd = AS.PtrList;
52 AS.PtrList->second.setPrevInList(PtrListEnd);
53 PtrListEnd = AS.PtrListEnd;
56 AS.PtrListEnd = &AS.PtrList;
60 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
64 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
65 assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
66 AST.removeAliasSet(this);
69 void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry,
71 assert(!Entry.second.hasAliasSet() && "Entry already in set!");
73 AliasAnalysis &AA = AST.getAliasAnalysis();
75 if (isMustAlias()) // Check to see if we have to downgrade to _may_ alias
76 if (HashNodePair *P = getSomePointer()) {
77 AliasAnalysis::AliasResult Result =
78 AA.alias(P->first, P->second.getSize(), Entry.first, Size);
79 if (Result == AliasAnalysis::MayAlias)
81 else // First entry of must alias must have maximum size!
82 P->second.updateSize(Size);
83 assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!");
86 Entry.second.setAliasSet(this);
87 Entry.second.updateSize(Size);
89 // Add it to the end of the list...
90 assert(*PtrListEnd == 0 && "End of list is not null?");
92 PtrListEnd = Entry.second.setPrevInList(PtrListEnd);
93 RefCount++; // Entry points to alias set...
96 void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) {
97 CallSites.push_back(CS);
99 if (Function *F = CS.getCalledFunction()) {
100 if (AA.doesNotAccessMemory(F))
102 else if (AA.onlyReadsMemory(F)) {
109 // FIXME: This should use mod/ref information to make this not suck so bad
114 /// aliasesPointer - Return true if the specified pointer "may" (or must)
115 /// alias one of the members in the set.
117 bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size,
118 AliasAnalysis &AA) const {
119 if (AliasTy == MustAlias) {
120 // If this is a set of MustAliases, only check to see if the pointer aliases
121 // SOME value in the set...
122 HashNodePair *SomePtr = getSomePointer();
123 assert(SomePtr && "Empty must-alias set??");
124 return AA.alias(SomePtr->first, SomePtr->second.getSize(), Ptr, Size);
127 // If this is a may-alias set, we have to check all of the pointers in the set
128 // to be sure it doesn't alias the set...
129 for (iterator I = begin(), E = end(); I != E; ++I)
130 if (AA.alias(Ptr, Size, I->first, I->second.getSize()))
133 // Check the call sites list and invoke list...
134 if (!CallSites.empty())
135 // FIXME: this is pessimistic!
141 bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const {
142 // FIXME: Use mod/ref information to prune this better!
143 if (Function *F = CS.getCalledFunction())
144 if (AA.doesNotAccessMemory(F))
151 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
152 /// instruction referring to the pointer into. If there are multiple alias sets
153 /// that may alias the pointer, merge them together and return the unified set.
155 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
157 AliasSet *FoundSet = 0;
158 for (iterator I = begin(), E = end(); I != E; ++I)
159 if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) {
160 if (FoundSet == 0) { // If this is the first alias set ptr can go into...
161 FoundSet = I; // Remember it.
162 } else { // Otherwise, we must merge the sets...
163 FoundSet->mergeSetIn(*I); // Merge in contents...
170 AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
171 AliasSet *FoundSet = 0;
172 for (iterator I = begin(), E = end(); I != E; ++I)
173 if (!I->Forward && I->aliasesCallSite(CS, AA)) {
174 if (FoundSet == 0) { // If this is the first alias set ptr can go into...
175 FoundSet = I; // Remember it.
176 } else if (!I->Forward) { // Otherwise, we must merge the sets...
177 FoundSet->mergeSetIn(*I); // Merge in contents...
187 /// getAliasSetForPointer - Return the alias set that the specified pointer
189 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size){
190 AliasSet::HashNodePair &Entry = getEntryFor(Pointer);
192 // Check to see if the pointer is already known...
193 if (Entry.second.hasAliasSet() && Size <= Entry.second.getSize()) {
195 return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this);
196 } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) {
197 // Add it to the alias set it aliases...
198 AS->addPointer(*this, Entry, Size);
201 // Otherwise create a new alias set to hold the loaded pointer...
202 AliasSets.push_back(AliasSet());
203 AliasSets.back().addPointer(*this, Entry, Size);
204 return AliasSets.back();
208 void AliasSetTracker::add(LoadInst *LI) {
210 addPointer(LI->getOperand(0),
211 AA.getTargetData().getTypeSize(LI->getType()), AliasSet::Refs);
212 if (LI->isVolatile()) AS.setVolatile();
215 void AliasSetTracker::add(StoreInst *SI) {
217 addPointer(SI->getOperand(1),
218 AA.getTargetData().getTypeSize(SI->getOperand(0)->getType()),
220 if (SI->isVolatile()) AS.setVolatile();
224 void AliasSetTracker::add(CallSite CS) {
225 AliasSet *AS = findAliasSetForCallSite(CS);
227 AliasSets.push_back(AliasSet());
228 AS = &AliasSets.back();
230 AS->addCallSite(CS, AA);
233 void AliasSetTracker::add(Instruction *I) {
234 // Dispatch to one of the other add methods...
235 if (LoadInst *LI = dyn_cast<LoadInst>(I))
237 else if (StoreInst *SI = dyn_cast<StoreInst>(I))
239 else if (CallInst *CI = dyn_cast<CallInst>(I))
241 else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
245 void AliasSetTracker::add(BasicBlock &BB) {
246 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
250 void AliasSetTracker::add(const AliasSetTracker &AST) {
251 assert(&AA == &AST.AA &&
252 "Merging AliasSetTracker objects with different Alias Analyses!");
254 // Loop over all of the alias sets in AST, adding the pointers contained
255 // therein into the current alias sets. This can cause alias sets to be
256 // merged together in the current AST.
257 for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I)
258 if (!I->Forward) { // Ignore forwarding alias sets
259 AliasSet &AS = const_cast<AliasSet&>(*I);
261 // If there are any call sites in the alias set, add them to this AST.
262 for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i)
263 add(AS.CallSites[i]);
265 // Loop over all of the pointers in this alias set...
266 AliasSet::iterator I = AS.begin(), E = AS.end();
268 addPointer(I->first, I->second.getSize(),
269 (AliasSet::AccessType)AS.AccessTy);
274 // remove method - This method is used to remove a pointer value from the
275 // AliasSetTracker entirely. It should be used when an instruction is deleted
276 // from the program to update the AST. If you don't use this, you would have
277 // dangling pointers to deleted instructions.
279 void AliasSetTracker::remove(Value *PtrVal) {
280 // First, look up the PointerRec for this pointer...
281 hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal);
282 if (I == PointerMap.end()) return; // Noop
284 // If we found one, remove the pointer from the alias set it is in.
285 AliasSet::HashNodePair &PtrValEnt = *I;
286 AliasSet *AS = PtrValEnt.second.getAliasSet(*this);
288 // Unlink from the list of values...
289 PtrValEnt.second.removeFromList();
290 // Stop using the alias set
291 if (--AS->RefCount == 0)
292 AS->removeFromTracker(*this);
298 //===----------------------------------------------------------------------===//
299 // AliasSet/AliasSetTracker Printing Support
300 //===----------------------------------------------------------------------===//
302 void AliasSet::print(std::ostream &OS) const {
303 OS << " AliasSet[" << (void*)this << "," << RefCount << "] ";
304 OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, ";
306 case NoModRef: OS << "No access "; break;
307 case Refs : OS << "Ref "; break;
308 case Mods : OS << "Mod "; break;
309 case ModRef : OS << "Mod/Ref "; break;
310 default: assert(0 && "Bad value for AccessTy!");
312 if (isVolatile()) OS << "[volatile] ";
314 OS << " forwarding to " << (void*)Forward;
317 if (begin() != end()) {
319 for (iterator I = begin(), E = end(); I != E; ++I) {
320 if (I != begin()) OS << ", ";
321 WriteAsOperand(OS << "(", I->first);
322 OS << ", " << I->second.getSize() << ")";
325 if (!CallSites.empty()) {
326 OS << "\n " << CallSites.size() << " Call Sites: ";
327 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
329 WriteAsOperand(OS, CallSites[i].getCalledValue());
335 void AliasSetTracker::print(std::ostream &OS) const {
336 OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
337 << PointerMap.size() << " pointer values.\n";
338 for (const_iterator I = begin(), E = end(); I != E; ++I)
343 void AliasSet::dump() const { print (std::cerr); }
344 void AliasSetTracker::dump() const { print(std::cerr); }
346 //===----------------------------------------------------------------------===//
347 // AliasSetPrinter Pass
348 //===----------------------------------------------------------------------===//
351 class AliasSetPrinter : public FunctionPass {
352 AliasSetTracker *Tracker;
354 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
355 AU.setPreservesAll();
356 AU.addRequired<AliasAnalysis>();
359 virtual bool runOnFunction(Function &F) {
360 Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
362 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
367 /// print - Convert to human readable form
368 virtual void print(std::ostream &OS) const {
372 virtual void releaseMemory() {
376 RegisterPass<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer",
377 PassInfo::Analysis | PassInfo::Optimization);