AliasSetTracker.cpp revision 6ffe551f657c948d6a473a198ecbd1188bf9ce45 
1//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
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.
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/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"
23using namespace llvm;
24
25/// mergeSetIn - Merge the specified alias set into this alias set...
26///
27void AliasSet::mergeSetIn(AliasSet &AS) {
28  assert(!AS.Forward && "Alias set is already forwarding!");
29  assert(!Forward && "This set is a forwarding set!!");
30
31  // Update the alias and access types of this set...
32  AccessTy |= AS.AccessTy;
33  AliasTy  |= AS.AliasTy;
34
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());
40    AS.CallSites.clear();
41  }
42
43  // FIXME: If AS's refcount is zero, nuke it now...
44  assert(RefCount != 0);
45
46  AS.Forward = this;  // Forward across AS now...
47  RefCount++;         // AS is now pointing to us...
48
49  // Merge the list of constituent pointers...
50  if (AS.PtrList) {
51    *PtrListEnd = AS.PtrList;
52    AS.PtrList->second.setPrevInList(PtrListEnd);
53    PtrListEnd = AS.PtrListEnd;
54
55    AS.PtrList = 0;
56    AS.PtrListEnd = &AS.PtrList;
57  }
58}
59
60void AliasSetTracker::removeAliasSet(AliasSet *AS) {
61  AliasSets.erase(AS);
62}
63
64void AliasSet::removeFromTracker(AliasSetTracker &AST) {
65  assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
66  AST.removeAliasSet(this);
67}
68
69void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry,
70                          unsigned Size) {
71  assert(!Entry.second.hasAliasSet() && "Entry already in set!");
72
73  AliasAnalysis &AA = AST.getAliasAnalysis();
74
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)
80        AliasTy = 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!");
84    }
85
86  Entry.second.setAliasSet(this);
87  Entry.second.updateSize(Size);
88
89  // Add it to the end of the list...
90  assert(*PtrListEnd == 0 && "End of list is not null?");
91  *PtrListEnd = &Entry;
92  PtrListEnd = Entry.second.setPrevInList(PtrListEnd);
93  RefCount++;               // Entry points to alias set...
94}
95
96void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) {
97  CallSites.push_back(CS);
98
99  if (Function *F = CS.getCalledFunction()) {
100    if (AA.doesNotAccessMemory(F))
101      return;
102    else if (AA.onlyReadsMemory(F)) {
103      AliasTy = MayAlias;
104      AccessTy |= Refs;
105      return;
106    }
107  }
108
109  // FIXME: This should use mod/ref information to make this not suck so bad
110  AliasTy = MayAlias;
111  AccessTy = ModRef;
112}
113
114/// aliasesPointer - Return true if the specified pointer "may" (or must)
115/// alias one of the members in the set.
116///
117bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size,
118                              AliasAnalysis &AA) const {
119  if (AliasTy == MustAlias) {
120    assert(CallSites.empty() && "Illegal must alias set!");
121
122    // If this is a set of MustAliases, only check to see if the pointer aliases
123    // SOME value in the set...
124    HashNodePair *SomePtr = getSomePointer();
125    assert(SomePtr && "Empty must-alias set??");
126    return AA.alias(SomePtr->first, SomePtr->second.getSize(), Ptr, Size);
127  }
128
129  // If this is a may-alias set, we have to check all of the pointers in the set
130  // to be sure it doesn't alias the set...
131  for (iterator I = begin(), E = end(); I != E; ++I)
132    if (AA.alias(Ptr, Size, I->first, I->second.getSize()))
133      return true;
134
135  // Check the call sites list and invoke list...
136  if (!CallSites.empty())
137    // FIXME: this is pessimistic!
138    return true;
139
140  return false;
141}
142
143bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const {
144  // FIXME: Use mod/ref information to prune this better!
145  if (Function *F = CS.getCalledFunction())
146    if (AA.doesNotAccessMemory(F))
147      return false;
148
149  return true;
150}
151
152
153/// findAliasSetForPointer - Given a pointer, find the one alias set to put the
154/// instruction referring to the pointer into.  If there are multiple alias sets
155/// that may alias the pointer, merge them together and return the unified set.
156///
157AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
158                                                  unsigned Size) {
159  AliasSet *FoundSet = 0;
160  for (iterator I = begin(), E = end(); I != E; ++I)
161    if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) {
162      if (FoundSet == 0) {  // If this is the first alias set ptr can go into...
163        FoundSet = I;       // Remember it.
164      } else {              // Otherwise, we must merge the sets...
165        FoundSet->mergeSetIn(*I);     // Merge in contents...
166      }
167    }
168
169  return FoundSet;
170}
171
172AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
173  AliasSet *FoundSet = 0;
174  for (iterator I = begin(), E = end(); I != E; ++I)
175    if (!I->Forward && I->aliasesCallSite(CS, AA)) {
176      if (FoundSet == 0) {  // If this is the first alias set ptr can go into...
177        FoundSet = I;       // Remember it.
178      } else if (!I->Forward) {     // Otherwise, we must merge the sets...
179        FoundSet->mergeSetIn(*I);     // Merge in contents...
180      }
181    }
182
183  return FoundSet;
184}
185
186
187
188
189/// getAliasSetForPointer - Return the alias set that the specified pointer
190/// lives in...
191AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size){
192  AliasSet::HashNodePair &Entry = getEntryFor(Pointer);
193
194  // Check to see if the pointer is already known...
195  if (Entry.second.hasAliasSet() && Size <= Entry.second.getSize()) {
196    // Return the set!
197    return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this);
198  } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) {
199    // Add it to the alias set it aliases...
200    AS->addPointer(*this, Entry, Size);
201    return *AS;
202  } else {
203    // Otherwise create a new alias set to hold the loaded pointer...
204    AliasSets.push_back(AliasSet());
205    AliasSets.back().addPointer(*this, Entry, Size);
206    return AliasSets.back();
207  }
208}
209
210void AliasSetTracker::add(LoadInst *LI) {
211  AliasSet &AS =
212    addPointer(LI->getOperand(0),
213               AA.getTargetData().getTypeSize(LI->getType()), AliasSet::Refs);
214  if (LI->isVolatile()) AS.setVolatile();
215}
216
217void AliasSetTracker::add(StoreInst *SI) {
218  AliasSet &AS =
219    addPointer(SI->getOperand(1),
220               AA.getTargetData().getTypeSize(SI->getOperand(0)->getType()),
221               AliasSet::Mods);
222  if (SI->isVolatile()) AS.setVolatile();
223}
224
225
226void AliasSetTracker::add(CallSite CS) {
227  if (Function *F = CS.getCalledFunction())
228    if (AA.doesNotAccessMemory(F))
229      return;
230
231  AliasSet *AS = findAliasSetForCallSite(CS);
232  if (!AS) {
233    AliasSets.push_back(AliasSet());
234    AS = &AliasSets.back();
235  }
236  AS->addCallSite(CS, AA);
237}
238
239void AliasSetTracker::add(Instruction *I) {
240  // Dispatch to one of the other add methods...
241  if (LoadInst *LI = dyn_cast<LoadInst>(I))
242    add(LI);
243  else if (StoreInst *SI = dyn_cast<StoreInst>(I))
244    add(SI);
245  else if (CallInst *CI = dyn_cast<CallInst>(I))
246    add(CI);
247  else if (InvokeInst *II = dyn_cast<InvokeInst>(I))
248    add(II);
249}
250
251void AliasSetTracker::add(BasicBlock &BB) {
252  for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
253    add(I);
254}
255
256void AliasSetTracker::add(const AliasSetTracker &AST) {
257  assert(&AA == &AST.AA &&
258         "Merging AliasSetTracker objects with different Alias Analyses!");
259
260  // Loop over all of the alias sets in AST, adding the pointers contained
261  // therein into the current alias sets.  This can cause alias sets to be
262  // merged together in the current AST.
263  for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I)
264    if (!I->Forward) {   // Ignore forwarding alias sets
265      AliasSet &AS = const_cast<AliasSet&>(*I);
266
267      // If there are any call sites in the alias set, add them to this AST.
268      for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i)
269        add(AS.CallSites[i]);
270
271      // Loop over all of the pointers in this alias set...
272      AliasSet::iterator I = AS.begin(), E = AS.end();
273      for (; I != E; ++I)
274        addPointer(I->first, I->second.getSize(),
275                   (AliasSet::AccessType)AS.AccessTy);
276    }
277}
278
279
280// remove method - This method is used to remove a pointer value from the
281// AliasSetTracker entirely.  It should be used when an instruction is deleted
282// from the program to update the AST.  If you don't use this, you would have
283// dangling pointers to deleted instructions.
284//
285void AliasSetTracker::remove(Value *PtrVal) {
286  // First, look up the PointerRec for this pointer...
287  hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal);
288  if (I == PointerMap.end()) return;  // Noop
289
290  // If we found one, remove the pointer from the alias set it is in.
291  AliasSet::HashNodePair &PtrValEnt = *I;
292  AliasSet *AS = PtrValEnt.second.getAliasSet(*this);
293
294  // Unlink from the list of values...
295  PtrValEnt.second.removeFromList();
296  // Stop using the alias set
297  if (--AS->RefCount == 0)
298    AS->removeFromTracker(*this);
299
300  PointerMap.erase(I);
301}
302
303
304//===----------------------------------------------------------------------===//
305//               AliasSet/AliasSetTracker Printing Support
306//===----------------------------------------------------------------------===//
307
308void AliasSet::print(std::ostream &OS) const {
309  OS << "  AliasSet[" << (void*)this << "," << RefCount << "] ";
310  OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, ";
311  switch (AccessTy) {
312  case NoModRef: OS << "No access "; break;
313  case Refs    : OS << "Ref       "; break;
314  case Mods    : OS << "Mod       "; break;
315  case ModRef  : OS << "Mod/Ref   "; break;
316  default: assert(0 && "Bad value for AccessTy!");
317  }
318  if (isVolatile()) OS << "[volatile] ";
319  if (Forward)
320    OS << " forwarding to " << (void*)Forward;
321
322
323  if (begin() != end()) {
324    OS << "Pointers: ";
325    for (iterator I = begin(), E = end(); I != E; ++I) {
326      if (I != begin()) OS << ", ";
327      WriteAsOperand(OS << "(", I->first);
328      OS << ", " << I->second.getSize() << ")";
329    }
330  }
331  if (!CallSites.empty()) {
332    OS << "\n    " << CallSites.size() << " Call Sites: ";
333    for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
334      if (i) OS << ", ";
335      WriteAsOperand(OS, CallSites[i].getCalledValue());
336    }
337  }
338  OS << "\n";
339}
340
341void AliasSetTracker::print(std::ostream &OS) const {
342  OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
343     << PointerMap.size() << " pointer values.\n";
344  for (const_iterator I = begin(), E = end(); I != E; ++I)
345    I->print(OS);
346  OS << "\n";
347}
348
349void AliasSet::dump() const { print (std::cerr); }
350void AliasSetTracker::dump() const { print(std::cerr); }
351
352//===----------------------------------------------------------------------===//
353//                            AliasSetPrinter Pass
354//===----------------------------------------------------------------------===//
355
356namespace {
357  class AliasSetPrinter : public FunctionPass {
358    AliasSetTracker *Tracker;
359  public:
360    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
361      AU.setPreservesAll();
362      AU.addRequired<AliasAnalysis>();
363    }
364
365    virtual bool runOnFunction(Function &F) {
366      Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
367
368      for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
369        Tracker->add(&*I);
370      return false;
371    }
372
373    /// print - Convert to human readable form
374    virtual void print(std::ostream &OS) const {
375      Tracker->print(OS);
376    }
377
378    virtual void releaseMemory() {
379      delete Tracker;
380    }
381  };
382  RegisterPass<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer",
383                                  PassInfo::Analysis | PassInfo::Optimization);
384}
385