blob: e74543bb508aafca3d8168cf02c08e12db699f92 [file] [log] [blame]
Chris Lattner009cc3d2002-09-26 21:49:07 +00001//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
Misha Brukman2b37d7c2005-04-21 21:13:18 +00002//
John Criswellb576c942003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukman2b37d7c2005-04-21 21:13:18 +00007//
John Criswellb576c942003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner009cc3d2002-09-26 21:49:07 +00009//
10// This file implements the AliasSetTracker and AliasSet classes.
Misha Brukman2b37d7c2005-04-21 21:13:18 +000011//
Chris Lattner009cc3d2002-09-26 21:49:07 +000012//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/AliasSetTracker.h"
15#include "llvm/Analysis/AliasAnalysis.h"
Misha Brukman47b14a42004-07-29 17:30:56 +000016#include "llvm/Instructions.h"
Zhou Sheng7e4286e2009-03-03 06:02:04 +000017#include "llvm/IntrinsicInst.h"
Chris Lattner9971ac42003-02-24 20:37:56 +000018#include "llvm/Pass.h"
Chris Lattner5b3a4552005-03-17 15:38:16 +000019#include "llvm/Type.h"
Chris Lattner31a9d182003-02-26 22:11:00 +000020#include "llvm/Target/TargetData.h"
Chris Lattner9971ac42003-02-24 20:37:56 +000021#include "llvm/Assembly/Writer.h"
David Greene43c48ac2009-12-23 19:27:59 +000022#include "llvm/Support/Debug.h"
Torok Edwinc25e7582009-07-11 20:10:48 +000023#include "llvm/Support/ErrorHandling.h"
Chris Lattner9971ac42003-02-24 20:37:56 +000024#include "llvm/Support/InstIterator.h"
Chris Lattner791102f2009-08-23 05:17:37 +000025#include "llvm/Support/raw_ostream.h"
Chris Lattnere2609242003-12-14 04:52:11 +000026using namespace llvm;
Brian Gaeked0fde302003-11-11 22:41:34 +000027
Chris Lattnercc8d5242004-11-27 18:37:42 +000028/// mergeSetIn - Merge the specified alias set into this alias set.
Chris Lattner009cc3d2002-09-26 21:49:07 +000029///
Chris Lattnercc8d5242004-11-27 18:37:42 +000030void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
Chris Lattner9971ac42003-02-24 20:37:56 +000031 assert(!AS.Forward && "Alias set is already forwarding!");
32 assert(!Forward && "This set is a forwarding set!!");
Chris Lattner009cc3d2002-09-26 21:49:07 +000033
34 // Update the alias and access types of this set...
Chris Lattner9971ac42003-02-24 20:37:56 +000035 AccessTy |= AS.AccessTy;
36 AliasTy |= AS.AliasTy;
Chris Lattnerfedac7d2010-08-29 04:14:47 +000037 Volatile |= AS.Volatile;
Chris Lattner9971ac42003-02-24 20:37:56 +000038
Chris Lattnercc8d5242004-11-27 18:37:42 +000039 if (AliasTy == MustAlias) {
40 // Check that these two merged sets really are must aliases. Since both
41 // used to be must-alias sets, we can just check any pointer from each set
42 // for aliasing.
43 AliasAnalysis &AA = AST.getAliasAnalysis();
Chris Lattnerd7168dd2009-03-09 05:11:09 +000044 PointerRec *L = getSomePointer();
45 PointerRec *R = AS.getSomePointer();
Chris Lattnercc8d5242004-11-27 18:37:42 +000046
47 // If the pointers are not a must-alias pair, this set becomes a may alias.
Chris Lattnerd7168dd2009-03-09 05:11:09 +000048 if (AA.alias(L->getValue(), L->getSize(), R->getValue(), R->getSize())
Chris Lattnercc8d5242004-11-27 18:37:42 +000049 != AliasAnalysis::MustAlias)
50 AliasTy = MayAlias;
51 }
52
Chris Lattner9971ac42003-02-24 20:37:56 +000053 if (CallSites.empty()) { // Merge call sites...
54 if (!AS.CallSites.empty())
55 std::swap(CallSites, AS.CallSites);
56 } else if (!AS.CallSites.empty()) {
57 CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end());
58 AS.CallSites.clear();
59 }
Misha Brukman2b37d7c2005-04-21 21:13:18 +000060
Chris Lattner9971ac42003-02-24 20:37:56 +000061 AS.Forward = this; // Forward across AS now...
Chris Lattnerb8a31ac2004-07-22 07:58:18 +000062 addRef(); // AS is now pointing to us...
Chris Lattner9971ac42003-02-24 20:37:56 +000063
64 // Merge the list of constituent pointers...
Chris Lattner2cffeec2003-12-18 08:11:56 +000065 if (AS.PtrList) {
66 *PtrListEnd = AS.PtrList;
Chris Lattnerd7168dd2009-03-09 05:11:09 +000067 AS.PtrList->setPrevInList(PtrListEnd);
Chris Lattner2cffeec2003-12-18 08:11:56 +000068 PtrListEnd = AS.PtrListEnd;
69
70 AS.PtrList = 0;
71 AS.PtrListEnd = &AS.PtrList;
Chris Lattner3080b602004-09-15 16:59:47 +000072 assert(*AS.PtrListEnd == 0 && "End of list is not null?");
Chris Lattner2cffeec2003-12-18 08:11:56 +000073 }
Chris Lattner009cc3d2002-09-26 21:49:07 +000074}
75
Chris Lattner9971ac42003-02-24 20:37:56 +000076void AliasSetTracker::removeAliasSet(AliasSet *AS) {
Chris Lattnerb8a31ac2004-07-22 07:58:18 +000077 if (AliasSet *Fwd = AS->Forward) {
78 Fwd->dropRef(*this);
79 AS->Forward = 0;
80 }
Chris Lattner9971ac42003-02-24 20:37:56 +000081 AliasSets.erase(AS);
82}
83
84void AliasSet::removeFromTracker(AliasSetTracker &AST) {
85 assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
86 AST.removeAliasSet(this);
87}
88
Chris Lattnerd7168dd2009-03-09 05:11:09 +000089void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
Chris Lattnerb66e6482004-09-14 19:15:32 +000090 unsigned Size, bool KnownMustAlias) {
Chris Lattnerd7168dd2009-03-09 05:11:09 +000091 assert(!Entry.hasAliasSet() && "Entry already in set!");
Chris Lattner9971ac42003-02-24 20:37:56 +000092
Chris Lattnerb66e6482004-09-14 19:15:32 +000093 // Check to see if we have to downgrade to _may_ alias.
94 if (isMustAlias() && !KnownMustAlias)
Chris Lattnerd7168dd2009-03-09 05:11:09 +000095 if (PointerRec *P = getSomePointer()) {
Chris Lattner3080b602004-09-15 16:59:47 +000096 AliasAnalysis &AA = AST.getAliasAnalysis();
Chris Lattner31a9d182003-02-26 22:11:00 +000097 AliasAnalysis::AliasResult Result =
Chris Lattnerd7168dd2009-03-09 05:11:09 +000098 AA.alias(P->getValue(), P->getSize(), Entry.getValue(), Size);
Chris Lattner31a9d182003-02-26 22:11:00 +000099 if (Result == AliasAnalysis::MayAlias)
Chris Lattner9971ac42003-02-24 20:37:56 +0000100 AliasTy = MayAlias;
Chris Lattner31a9d182003-02-26 22:11:00 +0000101 else // First entry of must alias must have maximum size!
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000102 P->updateSize(Size);
Chris Lattner31a9d182003-02-26 22:11:00 +0000103 assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!");
104 }
Chris Lattner9971ac42003-02-24 20:37:56 +0000105
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000106 Entry.setAliasSet(this);
107 Entry.updateSize(Size);
Chris Lattner9971ac42003-02-24 20:37:56 +0000108
109 // Add it to the end of the list...
Chris Lattner2cffeec2003-12-18 08:11:56 +0000110 assert(*PtrListEnd == 0 && "End of list is not null?");
111 *PtrListEnd = &Entry;
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000112 PtrListEnd = Entry.setPrevInList(PtrListEnd);
Chris Lattner3080b602004-09-15 16:59:47 +0000113 assert(*PtrListEnd == 0 && "End of list is not null?");
Chris Lattner9476d742010-08-29 04:13:43 +0000114 addRef(); // Entry points to alias set.
Chris Lattner9971ac42003-02-24 20:37:56 +0000115}
116
Chris Lattner5b5f7c12004-03-15 04:08:36 +0000117void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) {
Chris Lattnercb7f6532010-08-29 18:42:23 +0000118 CallSites.push_back(CS.getInstruction());
Chris Lattner5b5f7c12004-03-15 04:08:36 +0000119
Duncan Sandsdff67102007-12-01 07:51:45 +0000120 AliasAnalysis::ModRefBehavior Behavior = AA.getModRefBehavior(CS);
121 if (Behavior == AliasAnalysis::DoesNotAccessMemory)
122 return;
123 else if (Behavior == AliasAnalysis::OnlyReadsMemory) {
124 AliasTy = MayAlias;
125 AccessTy |= Refs;
126 return;
Chris Lattner5b5f7c12004-03-15 04:08:36 +0000127 }
128
129 // FIXME: This should use mod/ref information to make this not suck so bad
130 AliasTy = MayAlias;
Chris Lattner577385e2003-05-03 03:42:08 +0000131 AccessTy = ModRef;
Chris Lattner9971ac42003-02-24 20:37:56 +0000132}
133
134/// aliasesPointer - Return true if the specified pointer "may" (or must)
Chris Lattner009cc3d2002-09-26 21:49:07 +0000135/// alias one of the members in the set.
136///
Chris Lattner31a9d182003-02-26 22:11:00 +0000137bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size,
138 AliasAnalysis &AA) const {
Chris Lattner9971ac42003-02-24 20:37:56 +0000139 if (AliasTy == MustAlias) {
Chris Lattnerfcead4f2004-03-15 06:28:07 +0000140 assert(CallSites.empty() && "Illegal must alias set!");
141
Chris Lattner9971ac42003-02-24 20:37:56 +0000142 // If this is a set of MustAliases, only check to see if the pointer aliases
Chris Lattner9476d742010-08-29 04:13:43 +0000143 // SOME value in the set.
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000144 PointerRec *SomePtr = getSomePointer();
Chris Lattner9971ac42003-02-24 20:37:56 +0000145 assert(SomePtr && "Empty must-alias set??");
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000146 return AA.alias(SomePtr->getValue(), SomePtr->getSize(), Ptr, Size);
Chris Lattner9971ac42003-02-24 20:37:56 +0000147 }
148
149 // If this is a may-alias set, we have to check all of the pointers in the set
150 // to be sure it doesn't alias the set...
151 for (iterator I = begin(), E = end(); I != E; ++I)
Chris Lattnerb8a31ac2004-07-22 07:58:18 +0000152 if (AA.alias(Ptr, Size, I.getPointer(), I.getSize()))
Chris Lattner9971ac42003-02-24 20:37:56 +0000153 return true;
154
155 // Check the call sites list and invoke list...
Chris Lattnerefe30ef2004-07-27 02:20:26 +0000156 if (!CallSites.empty()) {
Chris Lattnerefe30ef2004-07-27 02:20:26 +0000157 for (unsigned i = 0, e = CallSites.size(); i != e; ++i)
Chris Lattner6e1f5102010-08-29 04:06:55 +0000158 if (AA.getModRefInfo(CallSites[i], Ptr, Size) != AliasAnalysis::NoModRef)
Chris Lattnerefe30ef2004-07-27 02:20:26 +0000159 return true;
160 }
Chris Lattner9971ac42003-02-24 20:37:56 +0000161
Chris Lattner009cc3d2002-09-26 21:49:07 +0000162 return false;
163}
164
Chris Lattner9971ac42003-02-24 20:37:56 +0000165bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const {
Duncan Sandsdff67102007-12-01 07:51:45 +0000166 if (AA.doesNotAccessMemory(CS))
167 return false;
Chris Lattner5b5f7c12004-03-15 04:08:36 +0000168
Chris Lattnercb7f6532010-08-29 18:42:23 +0000169 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
170 if (AA.getModRefInfo(getCallSite(i), CS) != AliasAnalysis::NoModRef ||
171 AA.getModRefInfo(CS, getCallSite(i)) != AliasAnalysis::NoModRef)
Chris Lattnerefe30ef2004-07-27 02:20:26 +0000172 return true;
Chris Lattnercb7f6532010-08-29 18:42:23 +0000173 }
Chris Lattnerefe30ef2004-07-27 02:20:26 +0000174
175 for (iterator I = begin(), E = end(); I != E; ++I)
176 if (AA.getModRefInfo(CS, I.getPointer(), I.getSize()) !=
177 AliasAnalysis::NoModRef)
178 return true;
179
180 return false;
Chris Lattner009cc3d2002-09-26 21:49:07 +0000181}
182
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000183void AliasSetTracker::clear() {
184 // Delete all the PointerRec entries.
Dan Gohmanb5b56ba2009-07-30 20:21:41 +0000185 for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
186 I != E; ++I)
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000187 I->second->eraseFromList();
188
189 PointerMap.clear();
190
191 // The alias sets should all be clear now.
192 AliasSets.clear();
193}
194
Chris Lattner009cc3d2002-09-26 21:49:07 +0000195
Chris Lattner009cc3d2002-09-26 21:49:07 +0000196/// findAliasSetForPointer - Given a pointer, find the one alias set to put the
197/// instruction referring to the pointer into. If there are multiple alias sets
198/// that may alias the pointer, merge them together and return the unified set.
199///
Chris Lattner31a9d182003-02-26 22:11:00 +0000200AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
201 unsigned Size) {
Chris Lattner009cc3d2002-09-26 21:49:07 +0000202 AliasSet *FoundSet = 0;
Chris Lattner6e1f5102010-08-29 04:06:55 +0000203 for (iterator I = begin(), E = end(); I != E; ++I) {
204 if (I->Forward || !I->aliasesPointer(Ptr, Size, AA)) continue;
205
206 if (FoundSet == 0) { // If this is the first alias set ptr can go into.
207 FoundSet = I; // Remember it.
208 } else { // Otherwise, we must merge the sets.
209 FoundSet->mergeSetIn(*I, *this); // Merge in contents.
Chris Lattner009cc3d2002-09-26 21:49:07 +0000210 }
Chris Lattner6e1f5102010-08-29 04:06:55 +0000211 }
Chris Lattner9971ac42003-02-24 20:37:56 +0000212
213 return FoundSet;
214}
215
Chris Lattner07bfa522004-11-26 21:36:25 +0000216/// containsPointer - Return true if the specified location is represented by
217/// this alias set, false otherwise. This does not modify the AST object or
218/// alias sets.
219bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const {
220 for (const_iterator I = begin(), E = end(); I != E; ++I)
221 if (!I->Forward && I->aliasesPointer(Ptr, Size, AA))
222 return true;
223 return false;
224}
225
226
227
Chris Lattner9971ac42003-02-24 20:37:56 +0000228AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
229 AliasSet *FoundSet = 0;
Chris Lattner6e1f5102010-08-29 04:06:55 +0000230 for (iterator I = begin(), E = end(); I != E; ++I) {
231 if (I->Forward || !I->aliasesCallSite(CS, AA))
232 continue;
233
Chris Lattnercb7f6532010-08-29 18:42:23 +0000234 if (FoundSet == 0) // If this is the first alias set ptr can go into.
235 FoundSet = I; // Remember it.
236 else if (!I->Forward) // Otherwise, we must merge the sets.
Chris Lattner6e1f5102010-08-29 04:06:55 +0000237 FoundSet->mergeSetIn(*I, *this); // Merge in contents.
Chris Lattner6e1f5102010-08-29 04:06:55 +0000238 }
Chris Lattner009cc3d2002-09-26 21:49:07 +0000239 return FoundSet;
240}
241
242
Chris Lattner009cc3d2002-09-26 21:49:07 +0000243
Chris Lattner9971ac42003-02-24 20:37:56 +0000244
245/// getAliasSetForPointer - Return the alias set that the specified pointer
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000246/// lives in.
Chris Lattner12c11552004-07-21 05:18:04 +0000247AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size,
248 bool *New) {
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000249 AliasSet::PointerRec &Entry = getEntryFor(Pointer);
Chris Lattner9971ac42003-02-24 20:37:56 +0000250
Chris Lattner9476d742010-08-29 04:13:43 +0000251 // Check to see if the pointer is already known.
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000252 if (Entry.hasAliasSet()) {
253 Entry.updateSize(Size);
Chris Lattner9971ac42003-02-24 20:37:56 +0000254 // Return the set!
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000255 return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
Chris Lattner6e1f5102010-08-29 04:06:55 +0000256 }
257
258 if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) {
Chris Lattner9476d742010-08-29 04:13:43 +0000259 // Add it to the alias set it aliases.
Chris Lattner31a9d182003-02-26 22:11:00 +0000260 AS->addPointer(*this, Entry, Size);
Chris Lattner9971ac42003-02-24 20:37:56 +0000261 return *AS;
Chris Lattner009cc3d2002-09-26 21:49:07 +0000262 }
Chris Lattner6e1f5102010-08-29 04:06:55 +0000263
264 if (New) *New = true;
Chris Lattner9476d742010-08-29 04:13:43 +0000265 // Otherwise create a new alias set to hold the loaded pointer.
Chris Lattner6e1f5102010-08-29 04:06:55 +0000266 AliasSets.push_back(new AliasSet());
267 AliasSets.back().addPointer(*this, Entry, Size);
268 return AliasSets.back();
Chris Lattner009cc3d2002-09-26 21:49:07 +0000269}
270
Chris Lattner61d46272004-07-26 05:50:23 +0000271bool AliasSetTracker::add(Value *Ptr, unsigned Size) {
272 bool NewPtr;
273 addPointer(Ptr, Size, AliasSet::NoModRef, NewPtr);
274 return NewPtr;
275}
276
277
Chris Lattner12c11552004-07-21 05:18:04 +0000278bool AliasSetTracker::add(LoadInst *LI) {
279 bool NewPtr;
280 AliasSet &AS = addPointer(LI->getOperand(0),
Dan Gohmanfc2a3ed2009-07-25 00:48:42 +0000281 AA.getTypeStoreSize(LI->getType()),
Chris Lattner12c11552004-07-21 05:18:04 +0000282 AliasSet::Refs, NewPtr);
Chris Lattnere2609242003-12-14 04:52:11 +0000283 if (LI->isVolatile()) AS.setVolatile();
Chris Lattner12c11552004-07-21 05:18:04 +0000284 return NewPtr;
Chris Lattner9971ac42003-02-24 20:37:56 +0000285}
286
Chris Lattner12c11552004-07-21 05:18:04 +0000287bool AliasSetTracker::add(StoreInst *SI) {
288 bool NewPtr;
289 Value *Val = SI->getOperand(0);
290 AliasSet &AS = addPointer(SI->getOperand(1),
Dan Gohmanfc2a3ed2009-07-25 00:48:42 +0000291 AA.getTypeStoreSize(Val->getType()),
Chris Lattner12c11552004-07-21 05:18:04 +0000292 AliasSet::Mods, NewPtr);
Chris Lattnere2609242003-12-14 04:52:11 +0000293 if (SI->isVolatile()) AS.setVolatile();
Chris Lattner12c11552004-07-21 05:18:04 +0000294 return NewPtr;
Chris Lattner009cc3d2002-09-26 21:49:07 +0000295}
296
Dan Gohman235fc572008-04-14 18:34:50 +0000297bool AliasSetTracker::add(VAArgInst *VAAI) {
298 bool NewPtr;
Chris Lattner05a24e52008-05-22 03:23:06 +0000299 addPointer(VAAI->getOperand(0), ~0, AliasSet::ModRef, NewPtr);
Dan Gohman235fc572008-04-14 18:34:50 +0000300 return NewPtr;
301}
302
Chris Lattnere2609242003-12-14 04:52:11 +0000303
Chris Lattner12c11552004-07-21 05:18:04 +0000304bool AliasSetTracker::add(CallSite CS) {
Zhou Sheng7e4286e2009-03-03 06:02:04 +0000305 if (isa<DbgInfoIntrinsic>(CS.getInstruction()))
306 return true; // Ignore DbgInfo Intrinsics.
Duncan Sandsdff67102007-12-01 07:51:45 +0000307 if (AA.doesNotAccessMemory(CS))
308 return true; // doesn't alias anything
Chris Lattnerfcead4f2004-03-15 06:28:07 +0000309
Chris Lattner9971ac42003-02-24 20:37:56 +0000310 AliasSet *AS = findAliasSetForCallSite(CS);
Chris Lattner6e1f5102010-08-29 04:06:55 +0000311 if (AS) {
Chris Lattner12c11552004-07-21 05:18:04 +0000312 AS->addCallSite(CS, AA);
313 return false;
Chris Lattner9971ac42003-02-24 20:37:56 +0000314 }
Chris Lattner6e1f5102010-08-29 04:06:55 +0000315 AliasSets.push_back(new AliasSet());
316 AS = &AliasSets.back();
317 AS->addCallSite(CS, AA);
318 return true;
Chris Lattner009cc3d2002-09-26 21:49:07 +0000319}
320
Chris Lattner12c11552004-07-21 05:18:04 +0000321bool AliasSetTracker::add(Instruction *I) {
Chris Lattner6e1f5102010-08-29 04:06:55 +0000322 // Dispatch to one of the other add methods.
Chris Lattner9971ac42003-02-24 20:37:56 +0000323 if (LoadInst *LI = dyn_cast<LoadInst>(I))
Chris Lattner12c11552004-07-21 05:18:04 +0000324 return add(LI);
Chris Lattner6e1f5102010-08-29 04:06:55 +0000325 if (StoreInst *SI = dyn_cast<StoreInst>(I))
Chris Lattner12c11552004-07-21 05:18:04 +0000326 return add(SI);
Chris Lattner6e1f5102010-08-29 04:06:55 +0000327 if (CallInst *CI = dyn_cast<CallInst>(I))
Chris Lattner12c11552004-07-21 05:18:04 +0000328 return add(CI);
Chris Lattner6e1f5102010-08-29 04:06:55 +0000329 if (InvokeInst *II = dyn_cast<InvokeInst>(I))
Chris Lattner12c11552004-07-21 05:18:04 +0000330 return add(II);
Chris Lattner6e1f5102010-08-29 04:06:55 +0000331 if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
Dan Gohman235fc572008-04-14 18:34:50 +0000332 return add(VAAI);
Chris Lattner12c11552004-07-21 05:18:04 +0000333 return true;
Chris Lattner009cc3d2002-09-26 21:49:07 +0000334}
335
Chris Lattner319d05b2003-03-03 23:28:05 +0000336void AliasSetTracker::add(BasicBlock &BB) {
337 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
338 add(I);
339}
340
341void AliasSetTracker::add(const AliasSetTracker &AST) {
342 assert(&AA == &AST.AA &&
343 "Merging AliasSetTracker objects with different Alias Analyses!");
344
345 // Loop over all of the alias sets in AST, adding the pointers contained
346 // therein into the current alias sets. This can cause alias sets to be
347 // merged together in the current AST.
Chris Lattner6e1f5102010-08-29 04:06:55 +0000348 for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) {
349 if (I->Forward) continue; // Ignore forwarding alias sets
350
351 AliasSet &AS = const_cast<AliasSet&>(*I);
Chris Lattner319d05b2003-03-03 23:28:05 +0000352
Chris Lattner6e1f5102010-08-29 04:06:55 +0000353 // If there are any call sites in the alias set, add them to this AST.
354 for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i)
355 add(AS.CallSites[i]);
Chris Lattner319d05b2003-03-03 23:28:05 +0000356
Chris Lattner6e1f5102010-08-29 04:06:55 +0000357 // Loop over all of the pointers in this alias set.
358 bool X;
359 for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
360 AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(),
361 (AliasSet::AccessType)AS.AccessTy, X);
362 if (AS.isVolatile()) NewAS.setVolatile();
Chris Lattner319d05b2003-03-03 23:28:05 +0000363 }
Chris Lattner6e1f5102010-08-29 04:06:55 +0000364 }
Chris Lattner319d05b2003-03-03 23:28:05 +0000365}
366
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000367/// remove - Remove the specified (potentially non-empty) alias set from the
368/// tracker.
369void AliasSetTracker::remove(AliasSet &AS) {
Chris Lattnerf2998572006-06-27 23:48:59 +0000370 // Drop all call sites.
371 AS.CallSites.clear();
372
373 // Clear the alias set.
374 unsigned NumRefs = 0;
375 while (!AS.empty()) {
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000376 AliasSet::PointerRec *P = AS.PtrList;
377
378 Value *ValToRemove = P->getValue();
Chris Lattnerf2998572006-06-27 23:48:59 +0000379
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000380 // Unlink and delete entry from the list of values.
381 P->eraseFromList();
Chris Lattnerf2998572006-06-27 23:48:59 +0000382
383 // Remember how many references need to be dropped.
384 ++NumRefs;
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000385
Chris Lattnerf2998572006-06-27 23:48:59 +0000386 // Finally, remove the entry.
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000387 PointerMap.erase(ValToRemove);
Chris Lattnerf2998572006-06-27 23:48:59 +0000388 }
389
390 // Stop using the alias set, removing it.
Chris Lattner356d8c22006-06-27 23:56:13 +0000391 AS.RefCount -= NumRefs;
392 if (AS.RefCount == 0)
393 AS.removeFromTracker(*this);
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000394}
395
Chris Lattner61d46272004-07-26 05:50:23 +0000396bool AliasSetTracker::remove(Value *Ptr, unsigned Size) {
397 AliasSet *AS = findAliasSetForPointer(Ptr, Size);
398 if (!AS) return false;
399 remove(*AS);
400 return true;
401}
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000402
403bool AliasSetTracker::remove(LoadInst *LI) {
Dan Gohmanfc2a3ed2009-07-25 00:48:42 +0000404 unsigned Size = AA.getTypeStoreSize(LI->getType());
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000405 AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size);
406 if (!AS) return false;
407 remove(*AS);
408 return true;
409}
410
411bool AliasSetTracker::remove(StoreInst *SI) {
Dan Gohmanfc2a3ed2009-07-25 00:48:42 +0000412 unsigned Size = AA.getTypeStoreSize(SI->getOperand(0)->getType());
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000413 AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size);
414 if (!AS) return false;
415 remove(*AS);
416 return true;
417}
418
Dan Gohman235fc572008-04-14 18:34:50 +0000419bool AliasSetTracker::remove(VAArgInst *VAAI) {
420 AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), ~0);
421 if (!AS) return false;
422 remove(*AS);
423 return true;
424}
425
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000426bool AliasSetTracker::remove(CallSite CS) {
Duncan Sandsdff67102007-12-01 07:51:45 +0000427 if (AA.doesNotAccessMemory(CS))
428 return false; // doesn't alias anything
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000429
430 AliasSet *AS = findAliasSetForCallSite(CS);
431 if (!AS) return false;
432 remove(*AS);
433 return true;
434}
435
436bool AliasSetTracker::remove(Instruction *I) {
437 // Dispatch to one of the other remove methods...
438 if (LoadInst *LI = dyn_cast<LoadInst>(I))
439 return remove(LI);
Chris Lattner9476d742010-08-29 04:13:43 +0000440 if (StoreInst *SI = dyn_cast<StoreInst>(I))
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000441 return remove(SI);
Chris Lattner9476d742010-08-29 04:13:43 +0000442 if (CallInst *CI = dyn_cast<CallInst>(I))
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000443 return remove(CI);
Chris Lattner9476d742010-08-29 04:13:43 +0000444 if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I))
Dan Gohman235fc572008-04-14 18:34:50 +0000445 return remove(VAAI);
Chris Lattner6d4b0d72004-07-21 07:04:26 +0000446 return true;
447}
448
Chris Lattner2cffeec2003-12-18 08:11:56 +0000449
Chris Lattnerc43e0ae2004-05-23 21:10:58 +0000450// deleteValue method - This method is used to remove a pointer value from the
Chris Lattner2cffeec2003-12-18 08:11:56 +0000451// AliasSetTracker entirely. It should be used when an instruction is deleted
452// from the program to update the AST. If you don't use this, you would have
453// dangling pointers to deleted instructions.
454//
Chris Lattnerc43e0ae2004-05-23 21:10:58 +0000455void AliasSetTracker::deleteValue(Value *PtrVal) {
Chris Lattnerb66e6482004-09-14 19:15:32 +0000456 // Notify the alias analysis implementation that this value is gone.
457 AA.deleteValue(PtrVal);
458
Chris Lattner959e3212006-06-26 19:20:48 +0000459 // If this is a call instruction, remove the callsite from the appropriate
Chris Lattnercb7f6532010-08-29 18:42:23 +0000460 // AliasSet (if present).
461 if (CallSite CS = PtrVal) {
462 if (!AA.doesNotAccessMemory(CS)) {
463 // Scan all the alias sets to see if this call site is contained.
464 for (iterator I = begin(), E = end(); I != E; ++I) {
465 if (I->Forward) continue;
466
467 I->removeCallSite(CS);
468 }
469 }
470 }
Chris Lattner959e3212006-06-26 19:20:48 +0000471
Chris Lattnerb66e6482004-09-14 19:15:32 +0000472 // First, look up the PointerRec for this pointer.
Dan Gohmanb5b56ba2009-07-30 20:21:41 +0000473 PointerMapType::iterator I = PointerMap.find(PtrVal);
Chris Lattner2cffeec2003-12-18 08:11:56 +0000474 if (I == PointerMap.end()) return; // Noop
475
476 // If we found one, remove the pointer from the alias set it is in.
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000477 AliasSet::PointerRec *PtrValEnt = I->second;
478 AliasSet *AS = PtrValEnt->getAliasSet(*this);
Chris Lattner2cffeec2003-12-18 08:11:56 +0000479
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000480 // Unlink and delete from the list of values.
481 PtrValEnt->eraseFromList();
482
483 // Stop using the alias set.
Chris Lattnerb8a31ac2004-07-22 07:58:18 +0000484 AS->dropRef(*this);
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000485
Chris Lattner2cffeec2003-12-18 08:11:56 +0000486 PointerMap.erase(I);
487}
488
Chris Lattnerb66e6482004-09-14 19:15:32 +0000489// 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//
494void 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.
Dan Gohmanb5b56ba2009-07-30 20:21:41 +0000499 PointerMapType::iterator I = PointerMap.find(From);
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000500 if (I == PointerMap.end())
Chris Lattnerb66e6482004-09-14 19:15:32 +0000501 return; // Noop
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000502 assert(I->second->hasAliasSet() && "Dead entry?");
Chris Lattnerb66e6482004-09-14 19:15:32 +0000503
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000504 AliasSet::PointerRec &Entry = getEntryFor(To);
505 if (Entry.hasAliasSet()) return; // Already in the tracker!
Chris Lattnerb66e6482004-09-14 19:15:32 +0000506
507 // Add it to the alias set it aliases...
Devang Patel6d9a2df2009-03-30 18:34:47 +0000508 I = PointerMap.find(From);
Chris Lattnerd7168dd2009-03-09 05:11:09 +0000509 AliasSet *AS = I->second->getAliasSet(*this);
510 AS->addPointer(*this, Entry, I->second->getSize(), true);
Chris Lattnerb66e6482004-09-14 19:15:32 +0000511}
512
513
Chris Lattner2cffeec2003-12-18 08:11:56 +0000514
Chris Lattner9971ac42003-02-24 20:37:56 +0000515//===----------------------------------------------------------------------===//
516// AliasSet/AliasSetTracker Printing Support
517//===----------------------------------------------------------------------===//
518
Chris Lattner791102f2009-08-23 05:17:37 +0000519void AliasSet::print(raw_ostream &OS) const {
Benjamin Kramer03392742010-08-30 14:46:53 +0000520 OS << " AliasSet[" << (void*)this << ", " << RefCount << "] ";
Dan Gohman92c7b652008-04-21 19:48:48 +0000521 OS << (AliasTy == MustAlias ? "must" : "may") << " alias, ";
Chris Lattner9971ac42003-02-24 20:37:56 +0000522 switch (AccessTy) {
523 case NoModRef: OS << "No access "; break;
524 case Refs : OS << "Ref "; break;
525 case Mods : OS << "Mod "; break;
526 case ModRef : OS << "Mod/Ref "; break;
Torok Edwinc23197a2009-07-14 16:55:14 +0000527 default: llvm_unreachable("Bad value for AccessTy!");
Chris Lattner009cc3d2002-09-26 21:49:07 +0000528 }
Chris Lattnere2609242003-12-14 04:52:11 +0000529 if (isVolatile()) OS << "[volatile] ";
Chris Lattner9971ac42003-02-24 20:37:56 +0000530 if (Forward)
531 OS << " forwarding to " << (void*)Forward;
532
533
Dan Gohmancb406c22007-10-03 19:26:29 +0000534 if (!empty()) {
Chris Lattner9971ac42003-02-24 20:37:56 +0000535 OS << "Pointers: ";
536 for (iterator I = begin(), E = end(); I != E; ++I) {
537 if (I != begin()) OS << ", ";
Chris Lattnerb8a31ac2004-07-22 07:58:18 +0000538 WriteAsOperand(OS << "(", I.getPointer());
539 OS << ", " << I.getSize() << ")";
Chris Lattner9971ac42003-02-24 20:37:56 +0000540 }
541 }
542 if (!CallSites.empty()) {
543 OS << "\n " << CallSites.size() << " Call Sites: ";
544 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
545 if (i) OS << ", ";
Chris Lattnercb7f6532010-08-29 18:42:23 +0000546 WriteAsOperand(OS, CallSites[i]);
Misha Brukman2b37d7c2005-04-21 21:13:18 +0000547 }
Chris Lattner9971ac42003-02-24 20:37:56 +0000548 }
549 OS << "\n";
550}
551
Chris Lattner791102f2009-08-23 05:17:37 +0000552void AliasSetTracker::print(raw_ostream &OS) const {
Chris Lattner9971ac42003-02-24 20:37:56 +0000553 OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
554 << PointerMap.size() << " pointer values.\n";
555 for (const_iterator I = begin(), E = end(); I != E; ++I)
556 I->print(OS);
557 OS << "\n";
558}
559
David Greene43c48ac2009-12-23 19:27:59 +0000560void AliasSet::dump() const { print(dbgs()); }
561void AliasSetTracker::dump() const { print(dbgs()); }
Chris Lattner9971ac42003-02-24 20:37:56 +0000562
Chris Lattner9971ac42003-02-24 20:37:56 +0000563//===----------------------------------------------------------------------===//
Dan Gohmanb5b56ba2009-07-30 20:21:41 +0000564// ASTCallbackVH Class Implementation
565//===----------------------------------------------------------------------===//
566
567void AliasSetTracker::ASTCallbackVH::deleted() {
568 assert(AST && "ASTCallbackVH called with a null AliasSetTracker!");
569 AST->deleteValue(getValPtr());
570 // this now dangles!
571}
572
573AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast)
Dan Gohmana818c302009-07-31 18:21:48 +0000574 : CallbackVH(V), AST(ast) {}
575
576AliasSetTracker::ASTCallbackVH &
577AliasSetTracker::ASTCallbackVH::operator=(Value *V) {
578 return *this = ASTCallbackVH(V, AST);
579}
Dan Gohmanb5b56ba2009-07-30 20:21:41 +0000580
581//===----------------------------------------------------------------------===//
Chris Lattner9971ac42003-02-24 20:37:56 +0000582// AliasSetPrinter Pass
583//===----------------------------------------------------------------------===//
584
585namespace {
Nick Lewycky6726b6d2009-10-25 06:33:48 +0000586 class AliasSetPrinter : public FunctionPass {
Chris Lattner9971ac42003-02-24 20:37:56 +0000587 AliasSetTracker *Tracker;
588 public:
Nick Lewyckyecd94c82007-05-06 13:37:16 +0000589 static char ID; // Pass identification, replacement for typeid
Owen Anderson90c579d2010-08-06 18:33:48 +0000590 AliasSetPrinter() : FunctionPass(ID) {}
Devang Patel794fd752007-05-01 21:15:47 +0000591
Chris Lattner9971ac42003-02-24 20:37:56 +0000592 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
593 AU.setPreservesAll();
594 AU.addRequired<AliasAnalysis>();
595 }
596
597 virtual bool runOnFunction(Function &F) {
598 Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
599
600 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
Chris Lattner6ffe5512004-04-27 15:13:33 +0000601 Tracker->add(&*I);
David Greene4850a892009-12-23 22:49:57 +0000602 Tracker->print(errs());
Chris Lattner4983cf72006-01-03 06:05:22 +0000603 delete Tracker;
Chris Lattner9971ac42003-02-24 20:37:56 +0000604 return false;
605 }
Chris Lattner9971ac42003-02-24 20:37:56 +0000606 };
Chris Lattner009cc3d2002-09-26 21:49:07 +0000607}
Dan Gohman844731a2008-05-13 00:00:25 +0000608
609char AliasSetPrinter::ID = 0;
Owen Andersond13db2c2010-07-21 22:09:45 +0000610INITIALIZE_PASS(AliasSetPrinter, "print-alias-sets",
611 "Alias Set Printer", false, true);