1 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// 2 // 3 // This file implements the AliasSetTracker and AliasSet classes. 4 // 5 //===----------------------------------------------------------------------===// 6 7 #include "llvm/Analysis/AliasSetTracker.h" 8 #include "llvm/Analysis/AliasAnalysis.h" 9 #include "llvm/iMemory.h" 10 #include "llvm/iOther.h" 11 #include "llvm/iTerminators.h" 12 #include "llvm/Pass.h" 13 #include "llvm/Assembly/Writer.h" 14 #include "llvm/Support/InstIterator.h" 15 16 /// mergeSetIn - Merge the specified alias set into this alias set... 17 /// 18 void AliasSet::mergeSetIn(AliasSet &AS) { 19 assert(!AS.Forward && "Alias set is already forwarding!"); 20 assert(!Forward && "This set is a forwarding set!!"); 21 22 // Update the alias and access types of this set... 23 AccessTy |= AS.AccessTy; 24 AliasTy |= AS.AliasTy; 25 26 if (CallSites.empty()) { // Merge call sites... 27 if (!AS.CallSites.empty()) 28 std::swap(CallSites, AS.CallSites); 29 } else if (!AS.CallSites.empty()) { 30 CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end()); 31 AS.CallSites.clear(); 32 } 33 34 // FIXME: If AS's refcount is zero, nuke it now... 35 assert(RefCount != 0); 36 37 AS.Forward = this; // Forward across AS now... 38 RefCount++; // AS is now pointing to us... 39 40 // Merge the list of constituent pointers... 41 PtrListTail->second.setTail(AS.PtrListHead); 42 PtrListTail = AS.PtrListTail; 43 AS.PtrListHead = AS.PtrListTail = 0; 44 } 45 46 void AliasSetTracker::removeAliasSet(AliasSet *AS) { 47 AliasSets.erase(AS); 48 } 49 50 void AliasSet::removeFromTracker(AliasSetTracker &AST) { 51 assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!"); 52 AST.removeAliasSet(this); 53 } 54 55 void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry){ 56 assert(!Entry.second.hasAliasSet() && "Entry already in set!"); 57 58 AliasAnalysis &AA = AST.getAliasAnalysis(); 59 60 if (isMustAlias()) // Check to see if we have to downgrade to _may_ alias 61 if (Value *V = getSomePointer()) 62 if (AA.alias(V, Entry.first) == AliasAnalysis::MayAlias) 63 AliasTy = MayAlias; 64 65 Entry.second.setAliasSet(this); 66 67 // Add it to the end of the list... 68 if (PtrListTail) 69 PtrListTail->second.setTail(&Entry); 70 else 71 PtrListHead = &Entry; 72 PtrListTail = &Entry; 73 RefCount++; // Entry points to alias set... 74 } 75 76 void AliasSet::addCallSite(CallSite CS) { 77 CallSites.push_back(CS); 78 AliasTy = MayAlias; // FIXME: Too conservative 79 } 80 81 /// aliasesPointer - Return true if the specified pointer "may" (or must) 82 /// alias one of the members in the set. 83 /// 84 bool AliasSet::aliasesPointer(const Value *Ptr, AliasAnalysis &AA) const { 85 if (AliasTy == MustAlias) { 86 assert(CallSites.empty() && "Illegal must alias set!"); 87 88 // If this is a set of MustAliases, only check to see if the pointer aliases 89 // SOME value in the set... 90 Value *SomePtr = getSomePointer(); 91 assert(SomePtr && "Empty must-alias set??"); 92 return AA.alias(SomePtr, Ptr); 93 } 94 95 // If this is a may-alias set, we have to check all of the pointers in the set 96 // to be sure it doesn't alias the set... 97 for (iterator I = begin(), E = end(); I != E; ++I) 98 if (AA.alias(Ptr, *I)) 99 return true; 100 101 // Check the call sites list and invoke list... 102 if (!CallSites.empty()) 103 // FIXME: this is pessimistic! 104 return true; 105 106 return false; 107 } 108 109 bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const { 110 // FIXME: Too conservative! 111 return true; 112 } 113 114 115 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the 116 /// instruction referring to the pointer into. If there are multiple alias sets 117 /// that may alias the pointer, merge them together and return the unified set. 118 /// 119 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr) { 120 AliasSet *FoundSet = 0; 121 for (iterator I = begin(), E = end(); I != E; ++I) 122 if (I->aliasesPointer(Ptr, AA)) { 123 if (FoundSet == 0) { // If this is the first alias set ptr can go into... 124 FoundSet = I; // Remember it. 125 } else { // Otherwise, we must merge the sets... 126 FoundSet->mergeSetIn(*I); // Merge in contents... 127 } 128 } 129 130 return FoundSet; 131 } 132 133 AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) { 134 AliasSet *FoundSet = 0; 135 for (iterator I = begin(), E = end(); I != E; ++I) 136 if (I->aliasesCallSite(CS, AA)) { 137 if (FoundSet == 0) { // If this is the first alias set ptr can go into... 138 FoundSet = I; // Remember it. 139 } else { // Otherwise, we must merge the sets... 140 FoundSet->mergeSetIn(*I); // Merge in contents... 141 } 142 } 143 144 return FoundSet; 145 } 146 147 148 149 150 /// getAliasSetForPointer - Return the alias set that the specified pointer 151 /// lives in... 152 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer) { 153 AliasSet::HashNodePair &Entry = getEntryFor(Pointer); 154 155 // Check to see if the pointer is already known... 156 if (Entry.second.hasAliasSet()) { 157 // Return the set! 158 return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this); 159 } else if (AliasSet *AS = findAliasSetForPointer(Pointer)) { 160 // Add it to the alias set it aliases... 161 AS->addPointer(*this, Entry); 162 return *AS; 163 } else { 164 // Otherwise create a new alias set to hold the loaded pointer... 165 AliasSets.push_back(AliasSet()); 166 AliasSets.back().addPointer(*this, Entry); 167 return AliasSets.back(); 168 } 169 } 170 171 void AliasSetTracker::add(LoadInst *LI) { 172 addPointer(LI->getOperand(0), AliasSet::Refs); 173 } 174 175 void AliasSetTracker::add(StoreInst *SI) { 176 addPointer(SI->getOperand(1), AliasSet::Mods); 177 } 178 179 void AliasSetTracker::add(CallSite CS) { 180 AliasSet *AS = findAliasSetForCallSite(CS); 181 if (!AS) { 182 AliasSets.push_back(AliasSet()); 183 AS = &AliasSets.back(); 184 } 185 AS->addCallSite(CS); 186 } 187 188 void AliasSetTracker::add(Instruction *I) { 189 // Dispatch to one of the other add methods... 190 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 191 add(LI); 192 else if (StoreInst *SI = dyn_cast<StoreInst>(I)) 193 add(SI); 194 else if (CallInst *CI = dyn_cast<CallInst>(I)) 195 add(CI); 196 else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 197 add(II); 198 } 199 200 //===----------------------------------------------------------------------===// 201 // AliasSet/AliasSetTracker Printing Support 202 //===----------------------------------------------------------------------===// 203 204 void AliasSet::print(std::ostream &OS) const { 205 OS << " AliasSet[" << (void*)this << "," << RefCount << "] "; 206 OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, "; 207 switch (AccessTy) { 208 case NoModRef: OS << "No access "; break; 209 case Refs : OS << "Ref "; break; 210 case Mods : OS << "Mod "; break; 211 case ModRef : OS << "Mod/Ref "; break; 212 default: assert(0 && "Bad value for AccessTy!"); 213 } 214 if (Forward) 215 OS << " forwarding to " << (void*)Forward; 216 217 218 if (begin() != end()) { 219 OS << "Pointers: "; 220 for (iterator I = begin(), E = end(); I != E; ++I) { 221 if (I != begin()) OS << ", "; 222 WriteAsOperand(OS, *I); 223 } 224 } 225 if (!CallSites.empty()) { 226 OS << "\n " << CallSites.size() << " Call Sites: "; 227 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { 228 if (i) OS << ", "; 229 WriteAsOperand(OS, CallSites[i].getCalledValue()); 230 } 231 } 232 OS << "\n"; 233 } 234 235 void AliasSetTracker::print(std::ostream &OS) const { 236 OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for " 237 << PointerMap.size() << " pointer values.\n"; 238 for (const_iterator I = begin(), E = end(); I != E; ++I) 239 I->print(OS); 240 OS << "\n"; 241 } 242 243 void AliasSet::dump() const { print (std::cerr); } 244 void AliasSetTracker::dump() const { print(std::cerr); } 245 246 247 //===----------------------------------------------------------------------===// 248 // AliasSetPrinter Pass 249 //===----------------------------------------------------------------------===// 250 251 namespace { 252 class AliasSetPrinter : public FunctionPass { 253 AliasSetTracker *Tracker; 254 public: 255 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 256 AU.setPreservesAll(); 257 AU.addRequired<AliasAnalysis>(); 258 } 259 260 virtual bool runOnFunction(Function &F) { 261 Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>()); 262 263 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 264 Tracker->add(*I); 265 return false; 266 } 267 268 /// print - Convert to human readable form 269 virtual void print(std::ostream &OS) const { 270 Tracker->print(OS); 271 } 272 273 virtual void releaseMemory() { 274 delete Tracker; 275 } 276 }; 277 RegisterPass<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer", 278 PassInfo::Analysis | PassInfo::Optimization); 279 } 280