Ignore the debug info intrinsics when adding instructions into alias sets.
[oota-llvm.git] / lib / Analysis / AliasSetTracker.cpp
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/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/Compiler.h"
23 #include "llvm/Support/InstIterator.h"
24 #include "llvm/Support/Streams.h"
25 using namespace llvm;
26
27 /// mergeSetIn - Merge the specified alias set into this alias set.
28 ///
29 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
30   assert(!AS.Forward && "Alias set is already forwarding!");
31   assert(!Forward && "This set is a forwarding set!!");
32
33   // Update the alias and access types of this set...
34   AccessTy |= AS.AccessTy;
35   AliasTy  |= AS.AliasTy;
36
37   if (AliasTy == MustAlias) {
38     // Check that these two merged sets really are must aliases.  Since both
39     // used to be must-alias sets, we can just check any pointer from each set
40     // for aliasing.
41     AliasAnalysis &AA = AST.getAliasAnalysis();
42     HashNodePair *L = getSomePointer();
43     HashNodePair *R = AS.getSomePointer();
44
45     // If the pointers are not a must-alias pair, this set becomes a may alias.
46     if (AA.alias(L->first, L->second.getSize(), R->first, R->second.getSize())
47         != AliasAnalysis::MustAlias)
48       AliasTy = MayAlias;
49   }
50
51   if (CallSites.empty()) {            // Merge call sites...
52     if (!AS.CallSites.empty())
53       std::swap(CallSites, AS.CallSites);
54   } else if (!AS.CallSites.empty()) {
55     CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end());
56     AS.CallSites.clear();
57   }
58
59   AS.Forward = this;  // Forward across AS now...
60   addRef();           // AS is now pointing to us...
61
62   // Merge the list of constituent pointers...
63   if (AS.PtrList) {
64     *PtrListEnd = AS.PtrList;
65     AS.PtrList->second.setPrevInList(PtrListEnd);
66     PtrListEnd = AS.PtrListEnd;
67
68     AS.PtrList = 0;
69     AS.PtrListEnd = &AS.PtrList;
70     assert(*AS.PtrListEnd == 0 && "End of list is not null?");
71   }
72 }
73
74 void AliasSetTracker::removeAliasSet(AliasSet *AS) {
75   if (AliasSet *Fwd = AS->Forward) {
76     Fwd->dropRef(*this);
77     AS->Forward = 0;
78   }
79   AliasSets.erase(AS);
80 }
81
82 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
83   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
84   AST.removeAliasSet(this);
85 }
86
87 void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry,
88                           unsigned Size, bool KnownMustAlias) {
89   assert(!Entry.second.hasAliasSet() && "Entry already in set!");
90
91   // Check to see if we have to downgrade to _may_ alias.
92   if (isMustAlias() && !KnownMustAlias)
93     if (HashNodePair *P = getSomePointer()) {
94       AliasAnalysis &AA = AST.getAliasAnalysis();
95       AliasAnalysis::AliasResult Result =
96         AA.alias(P->first, P->second.getSize(), Entry.first, Size);
97       if (Result == AliasAnalysis::MayAlias)
98         AliasTy = MayAlias;
99       else                  // First entry of must alias must have maximum size!
100         P->second.updateSize(Size);
101       assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!");
102     }
103
104   Entry.second.setAliasSet(this);
105   Entry.second.updateSize(Size);
106
107   // Add it to the end of the list...
108   assert(*PtrListEnd == 0 && "End of list is not null?");
109   *PtrListEnd = &Entry;
110   PtrListEnd = Entry.second.setPrevInList(PtrListEnd);
111   assert(*PtrListEnd == 0 && "End of list is not null?");
112   addRef();               // Entry points to alias set...
113 }
114
115 void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) {
116   CallSites.push_back(CS);
117
118   AliasAnalysis::ModRefBehavior Behavior = AA.getModRefBehavior(CS);
119   if (Behavior == AliasAnalysis::DoesNotAccessMemory)
120     return;
121   else if (Behavior == AliasAnalysis::OnlyReadsMemory) {
122     AliasTy = MayAlias;
123     AccessTy |= Refs;
124     return;
125   }
126
127   // FIXME: This should use mod/ref information to make this not suck so bad
128   AliasTy = MayAlias;
129   AccessTy = ModRef;
130 }
131
132 /// aliasesPointer - Return true if the specified pointer "may" (or must)
133 /// alias one of the members in the set.
134 ///
135 bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size,
136                               AliasAnalysis &AA) const {
137   if (AliasTy == MustAlias) {
138     assert(CallSites.empty() && "Illegal must alias set!");
139
140     // If this is a set of MustAliases, only check to see if the pointer aliases
141     // SOME value in the set...
142     HashNodePair *SomePtr = getSomePointer();
143     assert(SomePtr && "Empty must-alias set??");
144     return AA.alias(SomePtr->first, SomePtr->second.getSize(), Ptr, Size);
145   }
146
147   // If this is a may-alias set, we have to check all of the pointers in the set
148   // to be sure it doesn't alias the set...
149   for (iterator I = begin(), E = end(); I != E; ++I)
150     if (AA.alias(Ptr, Size, I.getPointer(), I.getSize()))
151       return true;
152
153   // Check the call sites list and invoke list...
154   if (!CallSites.empty()) {
155     if (AA.hasNoModRefInfoForCalls())
156       return true;
157
158     for (unsigned i = 0, e = CallSites.size(); i != e; ++i)
159       if (AA.getModRefInfo(CallSites[i], const_cast<Value*>(Ptr), Size)
160                    != AliasAnalysis::NoModRef)
161         return true;
162   }
163
164   return false;
165 }
166
167 bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const {
168   if (AA.doesNotAccessMemory(CS))
169     return false;
170
171   if (AA.hasNoModRefInfoForCalls())
172     return true;
173
174   for (unsigned i = 0, e = CallSites.size(); i != e; ++i)
175     if (AA.getModRefInfo(CallSites[i], CS) != AliasAnalysis::NoModRef ||
176         AA.getModRefInfo(CS, CallSites[i]) != AliasAnalysis::NoModRef)
177       return true;
178
179   for (iterator I = begin(), E = end(); I != E; ++I)
180     if (AA.getModRefInfo(CS, I.getPointer(), I.getSize()) !=
181            AliasAnalysis::NoModRef)
182       return true;
183
184   return false;
185 }
186
187
188 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the
189 /// instruction referring to the pointer into.  If there are multiple alias sets
190 /// that may alias the pointer, merge them together and return the unified set.
191 ///
192 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
193                                                   unsigned Size) {
194   AliasSet *FoundSet = 0;
195   for (iterator I = begin(), E = end(); I != E; ++I)
196     if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) {
197       if (FoundSet == 0) {  // If this is the first alias set ptr can go into.
198         FoundSet = I;       // Remember it.
199       } else {              // Otherwise, we must merge the sets.
200         FoundSet->mergeSetIn(*I, *this);     // Merge in contents.
201       }
202     }
203
204   return FoundSet;
205 }
206
207 /// containsPointer - Return true if the specified location is represented by
208 /// this alias set, false otherwise.  This does not modify the AST object or
209 /// alias sets.
210 bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const {
211   for (const_iterator I = begin(), E = end(); I != E; ++I)
212     if (!I->Forward && I->aliasesPointer(Ptr, Size, AA))
213       return true;
214   return false;
215 }
216
217
218
219 AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
220   AliasSet *FoundSet = 0;
221   for (iterator I = begin(), E = end(); I != E; ++I)
222     if (!I->Forward && I->aliasesCallSite(CS, AA)) {
223       if (FoundSet == 0) {  // If this is the first alias set ptr can go into.
224         FoundSet = I;       // Remember it.
225       } else if (!I->Forward) {     // Otherwise, we must merge the sets.
226         FoundSet->mergeSetIn(*I, *this);     // Merge in contents.
227       }
228     }
229
230   return FoundSet;
231 }
232
233
234
235
236 /// getAliasSetForPointer - Return the alias set that the specified pointer
237 /// lives in...
238 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size,
239                                                  bool *New) {
240   AliasSet::HashNodePair &Entry = getEntryFor(Pointer);
241
242   // Check to see if the pointer is already known...
243   if (Entry.second.hasAliasSet()) {
244     Entry.second.updateSize(Size);
245     // Return the set!
246     return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this);
247   } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) {
248     // Add it to the alias set it aliases...
249     AS->addPointer(*this, Entry, Size);
250     return *AS;
251   } else {
252     if (New) *New = true;
253     // Otherwise create a new alias set to hold the loaded pointer...
254     AliasSets.push_back(new AliasSet());
255     AliasSets.back().addPointer(*this, Entry, Size);
256     return AliasSets.back();
257   }
258 }
259
260 bool AliasSetTracker::add(Value *Ptr, unsigned Size) {
261   bool NewPtr;
262   addPointer(Ptr, Size, AliasSet::NoModRef, NewPtr);
263   return NewPtr;
264 }
265
266
267 bool AliasSetTracker::add(LoadInst *LI) {
268   bool NewPtr;
269   AliasSet &AS = addPointer(LI->getOperand(0),
270                             AA.getTargetData().getTypeStoreSize(LI->getType()),
271                             AliasSet::Refs, NewPtr);
272   if (LI->isVolatile()) AS.setVolatile();
273   return NewPtr;
274 }
275
276 bool AliasSetTracker::add(StoreInst *SI) {
277   bool NewPtr;
278   Value *Val = SI->getOperand(0);
279   AliasSet &AS = addPointer(SI->getOperand(1),
280                             AA.getTargetData().getTypeStoreSize(Val->getType()),
281                             AliasSet::Mods, NewPtr);
282   if (SI->isVolatile()) AS.setVolatile();
283   return NewPtr;
284 }
285
286 bool AliasSetTracker::add(FreeInst *FI) {
287   bool NewPtr;
288   addPointer(FI->getOperand(0), ~0, AliasSet::Mods, NewPtr);
289   return NewPtr;
290 }
291
292 bool AliasSetTracker::add(VAArgInst *VAAI) {
293   bool NewPtr;
294   addPointer(VAAI->getOperand(0), ~0, AliasSet::ModRef, NewPtr);
295   return NewPtr;
296 }
297
298
299 bool AliasSetTracker::add(CallSite CS) {
300   if (isa<DbgInfoIntrinsic>(CS.getInstruction())) 
301     return true; // Ignore DbgInfo Intrinsics.
302   if (AA.doesNotAccessMemory(CS))
303     return true; // doesn't alias anything
304
305   AliasSet *AS = findAliasSetForCallSite(CS);
306   if (!AS) {
307     AliasSets.push_back(new AliasSet());
308     AS = &AliasSets.back();
309     AS->addCallSite(CS, AA);
310     return true;
311   } else {
312     AS->addCallSite(CS, AA);
313     return false;
314   }
315 }
316
317 bool AliasSetTracker::add(Instruction *I) {
318   // Dispatch to one of the other add methods...
319   if (LoadInst *LI = dyn_cast<LoadInst>(I))
320     return add(LI);
321   else if (StoreInst *SI = dyn_cast<StoreInst>(I))
322     return add(SI);
323   else if (CallInst *CI = dyn_cast<CallInst>(I))
324     return add(CI);
325   else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
326     return add(II);
327   else if (FreeInst *FI = dyn_cast<FreeInst>(I))
328     return add(FI);
329   else if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
330     return add(VAAI);
331   return true;
332 }
333
334 void AliasSetTracker::add(BasicBlock &BB) {
335   for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
336     add(I);
337 }
338
339 void AliasSetTracker::add(const AliasSetTracker &AST) {
340   assert(&AA == &AST.AA &&
341          "Merging AliasSetTracker objects with different Alias Analyses!");
342
343   // Loop over all of the alias sets in AST, adding the pointers contained
344   // therein into the current alias sets.  This can cause alias sets to be
345   // merged together in the current AST.
346   for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I)
347     if (!I->Forward) {   // Ignore forwarding alias sets
348       AliasSet &AS = const_cast<AliasSet&>(*I);
349
350       // If there are any call sites in the alias set, add them to this AST.
351       for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i)
352         add(AS.CallSites[i]);
353
354       // Loop over all of the pointers in this alias set...
355       AliasSet::iterator I = AS.begin(), E = AS.end();
356       bool X;
357       for (; I != E; ++I) {
358         AliasSet &NewAS = addPointer(I.getPointer(), I.getSize(),
359                                      (AliasSet::AccessType)AS.AccessTy, X);
360         if (AS.isVolatile()) NewAS.setVolatile();
361       }
362     }
363 }
364
365 /// remove - Remove the specified (potentially non-empty) alias set from the
366 /// tracker.
367 void AliasSetTracker::remove(AliasSet &AS) {
368   // Drop all call sites.
369   AS.CallSites.clear();
370   
371   // Clear the alias set.
372   unsigned NumRefs = 0;
373   while (!AS.empty()) {
374     AliasSet::HashNodePair *P = AS.PtrList;
375     
376     // Unlink from the list of values.
377     P->second.removeFromList();
378     
379     // Remember how many references need to be dropped.
380     ++NumRefs;
381
382     // Finally, remove the entry.
383     Value *Remove = P->first;   // Take a copy because it is invalid to pass
384     PointerMap.erase(Remove);   // a reference to the data being erased.
385   }
386   
387   // Stop using the alias set, removing it.
388   AS.RefCount -= NumRefs;
389   if (AS.RefCount == 0)
390     AS.removeFromTracker(*this);
391 }
392
393 bool AliasSetTracker::remove(Value *Ptr, unsigned Size) {
394   AliasSet *AS = findAliasSetForPointer(Ptr, Size);
395   if (!AS) return false;
396   remove(*AS);
397   return true;
398 }
399
400 bool AliasSetTracker::remove(LoadInst *LI) {
401   unsigned Size = AA.getTargetData().getTypeStoreSize(LI->getType());
402   AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size);
403   if (!AS) return false;
404   remove(*AS);
405   return true;
406 }
407
408 bool AliasSetTracker::remove(StoreInst *SI) {
409   unsigned Size =
410     AA.getTargetData().getTypeStoreSize(SI->getOperand(0)->getType());
411   AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size);
412   if (!AS) return false;
413   remove(*AS);
414   return true;
415 }
416
417 bool AliasSetTracker::remove(FreeInst *FI) {
418   AliasSet *AS = findAliasSetForPointer(FI->getOperand(0), ~0);
419   if (!AS) return false;
420   remove(*AS);
421   return true;
422 }
423
424 bool AliasSetTracker::remove(VAArgInst *VAAI) {
425   AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), ~0);
426   if (!AS) return false;
427   remove(*AS);
428   return true;
429 }
430
431 bool AliasSetTracker::remove(CallSite CS) {
432   if (AA.doesNotAccessMemory(CS))
433     return false; // doesn't alias anything
434
435   AliasSet *AS = findAliasSetForCallSite(CS);
436   if (!AS) return false;
437   remove(*AS);
438   return true;
439 }
440
441 bool AliasSetTracker::remove(Instruction *I) {
442   // Dispatch to one of the other remove methods...
443   if (LoadInst *LI = dyn_cast<LoadInst>(I))
444     return remove(LI);
445   else if (StoreInst *SI = dyn_cast<StoreInst>(I))
446     return remove(SI);
447   else if (CallInst *CI = dyn_cast<CallInst>(I))
448     return remove(CI);
449   else if (FreeInst *FI = dyn_cast<FreeInst>(I))
450     return remove(FI);
451   else if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
452     return remove(VAAI);
453   return true;
454 }
455
456
457 // deleteValue method - This method is used to remove a pointer value from the
458 // AliasSetTracker entirely.  It should be used when an instruction is deleted
459 // from the program to update the AST.  If you don't use this, you would have
460 // dangling pointers to deleted instructions.
461 //
462 void AliasSetTracker::deleteValue(Value *PtrVal) {
463   // Notify the alias analysis implementation that this value is gone.
464   AA.deleteValue(PtrVal);
465
466   // If this is a call instruction, remove the callsite from the appropriate
467   // AliasSet.
468   CallSite CS = CallSite::get(PtrVal);
469   if (CS.getInstruction())
470     if (!AA.doesNotAccessMemory(CS))
471       if (AliasSet *AS = findAliasSetForCallSite(CS))
472         AS->removeCallSite(CS);
473
474   // First, look up the PointerRec for this pointer.
475   hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal);
476   if (I == PointerMap.end()) return;  // Noop
477
478   // If we found one, remove the pointer from the alias set it is in.
479   AliasSet::HashNodePair &PtrValEnt = *I;
480   AliasSet *AS = PtrValEnt.second.getAliasSet(*this);
481
482   // Unlink from the list of values...
483   PtrValEnt.second.removeFromList();
484   // Stop using the alias set
485   AS->dropRef(*this);
486   PointerMap.erase(I);
487 }
488
489 // copyValue - This method should be used whenever a preexisting value in the
490 // program is copied or cloned, introducing a new value.  Note that it is ok for
491 // clients that use this method to introduce the same value multiple times: if
492 // the tracker already knows about a value, it will ignore the request.
493 //
494 void AliasSetTracker::copyValue(Value *From, Value *To) {
495   // Notify the alias analysis implementation that this value is copied.
496   AA.copyValue(From, To);
497
498   // First, look up the PointerRec for this pointer.
499   hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(From);
500   if (I == PointerMap.end() || !I->second.hasAliasSet())
501     return;  // Noop
502
503   AliasSet::HashNodePair &Entry = getEntryFor(To);
504   if (Entry.second.hasAliasSet()) return;    // Already in the tracker!
505
506   // Add it to the alias set it aliases...
507   AliasSet *AS = I->second.getAliasSet(*this);
508   AS->addPointer(*this, Entry, I->second.getSize(), true);
509 }
510
511
512
513 //===----------------------------------------------------------------------===//
514 //               AliasSet/AliasSetTracker Printing Support
515 //===----------------------------------------------------------------------===//
516
517 void AliasSet::print(std::ostream &OS) const {
518   OS << "  AliasSet[" << (void*)this << "," << RefCount << "] ";
519   OS << (AliasTy == MustAlias ? "must" : "may") << " alias, ";
520   switch (AccessTy) {
521   case NoModRef: OS << "No access "; break;
522   case Refs    : OS << "Ref       "; break;
523   case Mods    : OS << "Mod       "; break;
524   case ModRef  : OS << "Mod/Ref   "; break;
525   default: assert(0 && "Bad value for AccessTy!");
526   }
527   if (isVolatile()) OS << "[volatile] ";
528   if (Forward)
529     OS << " forwarding to " << (void*)Forward;
530
531
532   if (!empty()) {
533     OS << "Pointers: ";
534     for (iterator I = begin(), E = end(); I != E; ++I) {
535       if (I != begin()) OS << ", ";
536       WriteAsOperand(OS << "(", I.getPointer());
537       OS << ", " << I.getSize() << ")";
538     }
539   }
540   if (!CallSites.empty()) {
541     OS << "\n    " << CallSites.size() << " Call Sites: ";
542     for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
543       if (i) OS << ", ";
544       WriteAsOperand(OS, CallSites[i].getCalledValue());
545     }
546   }
547   OS << "\n";
548 }
549
550 void AliasSetTracker::print(std::ostream &OS) const {
551   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
552      << PointerMap.size() << " pointer values.\n";
553   for (const_iterator I = begin(), E = end(); I != E; ++I)
554     I->print(OS);
555   OS << "\n";
556 }
557
558 void AliasSet::dump() const { print (cerr); }
559 void AliasSetTracker::dump() const { print(cerr); }
560
561 //===----------------------------------------------------------------------===//
562 //                            AliasSetPrinter Pass
563 //===----------------------------------------------------------------------===//
564
565 namespace {
566   class VISIBILITY_HIDDEN AliasSetPrinter : public FunctionPass {
567     AliasSetTracker *Tracker;
568   public:
569     static char ID; // Pass identification, replacement for typeid
570     AliasSetPrinter() : FunctionPass(&ID) {}
571
572     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
573       AU.setPreservesAll();
574       AU.addRequired<AliasAnalysis>();
575     }
576
577     virtual bool runOnFunction(Function &F) {
578       Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
579
580       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
581         Tracker->add(&*I);
582       Tracker->print(cerr);
583       delete Tracker;
584       return false;
585     }
586   };
587 }
588
589 char AliasSetPrinter::ID = 0;
590 static RegisterPass<AliasSetPrinter>
591 X("print-alias-sets", "Alias Set Printer", false, true);