1 //===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===// 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 simple pass provides alias and mod/ref information for global values 11 // that do not have their address taken, and keeps track of whether functions 12 // read or write memory (are "pure"). For this simple (but very common) case, 13 // we can provide pretty accurate and useful information. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #define DEBUG_TYPE "globalsmodref-aa" 18 #include "llvm/Analysis/Passes.h" 19 #include "llvm/Module.h" 20 #include "llvm/Pass.h" 21 #include "llvm/Instructions.h" 22 #include "llvm/Constants.h" 23 #include "llvm/DerivedTypes.h" 24 #include "llvm/IntrinsicInst.h" 25 #include "llvm/Analysis/AliasAnalysis.h" 26 #include "llvm/Analysis/CallGraph.h" 27 #include "llvm/Analysis/MemoryBuiltins.h" 28 #include "llvm/Analysis/ValueTracking.h" 29 #include "llvm/Support/CommandLine.h" 30 #include "llvm/Support/InstIterator.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/ADT/SCCIterator.h" 33 #include <set> 34 using namespace llvm; 35 36 STATISTIC(NumNonAddrTakenGlobalVars, 37 "Number of global vars without address taken"); 38 STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken"); 39 STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory"); 40 STATISTIC(NumReadMemFunctions, "Number of functions that only read memory"); 41 STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects"); 42 43 namespace { 44 /// FunctionRecord - One instance of this structure is stored for every 45 /// function in the program. Later, the entries for these functions are 46 /// removed if the function is found to call an external function (in which 47 /// case we know nothing about it. 48 struct FunctionRecord { 49 /// GlobalInfo - Maintain mod/ref info for all of the globals without 50 /// addresses taken that are read or written (transitively) by this 51 /// function. 52 std::map<const GlobalValue*, unsigned> GlobalInfo; 53 54 /// MayReadAnyGlobal - May read global variables, but it is not known which. 55 bool MayReadAnyGlobal; 56 57 unsigned getInfoForGlobal(const GlobalValue *GV) const { 58 unsigned Effect = MayReadAnyGlobal ? AliasAnalysis::Ref : 0; 59 std::map<const GlobalValue*, unsigned>::const_iterator I = 60 GlobalInfo.find(GV); 61 if (I != GlobalInfo.end()) 62 Effect |= I->second; 63 return Effect; 64 } 65 66 /// FunctionEffect - Capture whether or not this function reads or writes to 67 /// ANY memory. If not, we can do a lot of aggressive analysis on it. 68 unsigned FunctionEffect; 69 70 FunctionRecord() : MayReadAnyGlobal (false), FunctionEffect(0) {} 71 }; 72 73 /// GlobalsModRef - The actual analysis pass. 74 class GlobalsModRef : public ModulePass, public AliasAnalysis { 75 /// NonAddressTakenGlobals - The globals that do not have their addresses 76 /// taken. 77 std::set<const GlobalValue*> NonAddressTakenGlobals; 78 79 /// IndirectGlobals - The memory pointed to by this global is known to be 80 /// 'owned' by the global. 81 std::set<const GlobalValue*> IndirectGlobals; 82 83 /// AllocsForIndirectGlobals - If an instruction allocates memory for an 84 /// indirect global, this map indicates which one. 85 std::map<const Value*, const GlobalValue*> AllocsForIndirectGlobals; 86 87 /// FunctionInfo - For each function, keep track of what globals are 88 /// modified or read. 89 std::map<const Function*, FunctionRecord> FunctionInfo; 90 91 public: 92 static char ID; 93 GlobalsModRef() : ModulePass(ID) { 94 initializeGlobalsModRefPass(*PassRegistry::getPassRegistry()); 95 } 96 97 bool runOnModule(Module &M) { 98 InitializeAliasAnalysis(this); // set up super class 99 AnalyzeGlobals(M); // find non-addr taken globals 100 AnalyzeCallGraph(getAnalysis<CallGraph>(), M); // Propagate on CG 101 return false; 102 } 103 104 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 105 AliasAnalysis::getAnalysisUsage(AU); 106 AU.addRequired<CallGraph>(); 107 AU.setPreservesAll(); // Does not transform code 108 } 109 110 //------------------------------------------------ 111 // Implement the AliasAnalysis API 112 // 113 AliasResult alias(const Location &LocA, const Location &LocB); 114 ModRefResult getModRefInfo(ImmutableCallSite CS, 115 const Location &Loc); 116 ModRefResult getModRefInfo(ImmutableCallSite CS1, 117 ImmutableCallSite CS2) { 118 return AliasAnalysis::getModRefInfo(CS1, CS2); 119 } 120 121 /// getModRefBehavior - Return the behavior of the specified function if 122 /// called from the specified call site. The call site may be null in which 123 /// case the most generic behavior of this function should be returned. 124 ModRefBehavior getModRefBehavior(const Function *F) { 125 ModRefBehavior Min = UnknownModRefBehavior; 126 127 if (FunctionRecord *FR = getFunctionInfo(F)) { 128 if (FR->FunctionEffect == 0) 129 Min = DoesNotAccessMemory; 130 else if ((FR->FunctionEffect & Mod) == 0) 131 Min = OnlyReadsMemory; 132 } 133 134 return ModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min); 135 } 136 137 /// getModRefBehavior - Return the behavior of the specified function if 138 /// called from the specified call site. The call site may be null in which 139 /// case the most generic behavior of this function should be returned. 140 ModRefBehavior getModRefBehavior(ImmutableCallSite CS) { 141 ModRefBehavior Min = UnknownModRefBehavior; 142 143 if (const Function* F = CS.getCalledFunction()) 144 if (FunctionRecord *FR = getFunctionInfo(F)) { 145 if (FR->FunctionEffect == 0) 146 Min = DoesNotAccessMemory; 147 else if ((FR->FunctionEffect & Mod) == 0) 148 Min = OnlyReadsMemory; 149 } 150 151 return ModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min); 152 } 153 154 virtual void deleteValue(Value *V); 155 virtual void copyValue(Value *From, Value *To); 156 virtual void addEscapingUse(Use &U); 157 158 /// getAdjustedAnalysisPointer - This method is used when a pass implements 159 /// an analysis interface through multiple inheritance. If needed, it 160 /// should override this to adjust the this pointer as needed for the 161 /// specified pass info. 162 virtual void *getAdjustedAnalysisPointer(AnalysisID PI) { 163 if (PI == &AliasAnalysis::ID) 164 return (AliasAnalysis*)this; 165 return this; 166 } 167 168 private: 169 /// getFunctionInfo - Return the function info for the function, or null if 170 /// we don't have anything useful to say about it. 171 FunctionRecord *getFunctionInfo(const Function *F) { 172 std::map<const Function*, FunctionRecord>::iterator I = 173 FunctionInfo.find(F); 174 if (I != FunctionInfo.end()) 175 return &I->second; 176 return 0; 177 } 178 179 void AnalyzeGlobals(Module &M); 180 void AnalyzeCallGraph(CallGraph &CG, Module &M); 181 bool AnalyzeUsesOfPointer(Value *V, std::vector<Function*> &Readers, 182 std::vector<Function*> &Writers, 183 GlobalValue *OkayStoreDest = 0); 184 bool AnalyzeIndirectGlobalMemory(GlobalValue *GV); 185 }; 186 } 187 188 char GlobalsModRef::ID = 0; 189 INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, 190 "globalsmodref-aa", "Simple mod/ref analysis for globals", 191 false, true, false) 192 INITIALIZE_AG_DEPENDENCY(CallGraph) 193 INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, 194 "globalsmodref-aa", "Simple mod/ref analysis for globals", 195 false, true, false) 196 197 Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); } 198 199 /// AnalyzeGlobals - Scan through the users of all of the internal 200 /// GlobalValue's in the program. If none of them have their "address taken" 201 /// (really, their address passed to something nontrivial), record this fact, 202 /// and record the functions that they are used directly in. 203 void GlobalsModRef::AnalyzeGlobals(Module &M) { 204 std::vector<Function*> Readers, Writers; 205 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 206 if (I->hasLocalLinkage()) { 207 if (!AnalyzeUsesOfPointer(I, Readers, Writers)) { 208 // Remember that we are tracking this global. 209 NonAddressTakenGlobals.insert(I); 210 ++NumNonAddrTakenFunctions; 211 } 212 Readers.clear(); Writers.clear(); 213 } 214 215 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 216 I != E; ++I) 217 if (I->hasLocalLinkage()) { 218 if (!AnalyzeUsesOfPointer(I, Readers, Writers)) { 219 // Remember that we are tracking this global, and the mod/ref fns 220 NonAddressTakenGlobals.insert(I); 221 222 for (unsigned i = 0, e = Readers.size(); i != e; ++i) 223 FunctionInfo[Readers[i]].GlobalInfo[I] |= Ref; 224 225 if (!I->isConstant()) // No need to keep track of writers to constants 226 for (unsigned i = 0, e = Writers.size(); i != e; ++i) 227 FunctionInfo[Writers[i]].GlobalInfo[I] |= Mod; 228 ++NumNonAddrTakenGlobalVars; 229 230 // If this global holds a pointer type, see if it is an indirect global. 231 if (I->getType()->getElementType()->isPointerTy() && 232 AnalyzeIndirectGlobalMemory(I)) 233 ++NumIndirectGlobalVars; 234 } 235 Readers.clear(); Writers.clear(); 236 } 237 } 238 239 /// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer. 240 /// If this is used by anything complex (i.e., the address escapes), return 241 /// true. Also, while we are at it, keep track of those functions that read and 242 /// write to the value. 243 /// 244 /// If OkayStoreDest is non-null, stores into this global are allowed. 245 bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V, 246 std::vector<Function*> &Readers, 247 std::vector<Function*> &Writers, 248 GlobalValue *OkayStoreDest) { 249 if (!V->getType()->isPointerTy()) return true; 250 251 for (Value::use_iterator UI = V->use_begin(), E=V->use_end(); UI != E; ++UI) { 252 User *U = *UI; 253 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 254 Readers.push_back(LI->getParent()->getParent()); 255 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 256 if (V == SI->getOperand(1)) { 257 Writers.push_back(SI->getParent()->getParent()); 258 } else if (SI->getOperand(1) != OkayStoreDest) { 259 return true; // Storing the pointer 260 } 261 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) { 262 if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true; 263 } else if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 264 if (AnalyzeUsesOfPointer(BCI, Readers, Writers, OkayStoreDest)) 265 return true; 266 } else if (isFreeCall(U)) { 267 Writers.push_back(cast<Instruction>(U)->getParent()->getParent()); 268 } else if (CallInst *CI = dyn_cast<CallInst>(U)) { 269 // Make sure that this is just the function being called, not that it is 270 // passing into the function. 271 for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) 272 if (CI->getArgOperand(i) == V) return true; 273 } else if (InvokeInst *II = dyn_cast<InvokeInst>(U)) { 274 // Make sure that this is just the function being called, not that it is 275 // passing into the function. 276 for (unsigned i = 0, e = II->getNumArgOperands(); i != e; ++i) 277 if (II->getArgOperand(i) == V) return true; 278 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { 279 if (CE->getOpcode() == Instruction::GetElementPtr || 280 CE->getOpcode() == Instruction::BitCast) { 281 if (AnalyzeUsesOfPointer(CE, Readers, Writers)) 282 return true; 283 } else { 284 return true; 285 } 286 } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(U)) { 287 if (!isa<ConstantPointerNull>(ICI->getOperand(1))) 288 return true; // Allow comparison against null. 289 } else { 290 return true; 291 } 292 } 293 294 return false; 295 } 296 297 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable 298 /// which holds a pointer type. See if the global always points to non-aliased 299 /// heap memory: that is, all initializers of the globals are allocations, and 300 /// those allocations have no use other than initialization of the global. 301 /// Further, all loads out of GV must directly use the memory, not store the 302 /// pointer somewhere. If this is true, we consider the memory pointed to by 303 /// GV to be owned by GV and can disambiguate other pointers from it. 304 bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) { 305 // Keep track of values related to the allocation of the memory, f.e. the 306 // value produced by the malloc call and any casts. 307 std::vector<Value*> AllocRelatedValues; 308 309 // Walk the user list of the global. If we find anything other than a direct 310 // load or store, bail out. 311 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){ 312 User *U = *I; 313 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 314 // The pointer loaded from the global can only be used in simple ways: 315 // we allow addressing of it and loading storing to it. We do *not* allow 316 // storing the loaded pointer somewhere else or passing to a function. 317 std::vector<Function*> ReadersWriters; 318 if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters)) 319 return false; // Loaded pointer escapes. 320 // TODO: Could try some IP mod/ref of the loaded pointer. 321 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 322 // Storing the global itself. 323 if (SI->getOperand(0) == GV) return false; 324 325 // If storing the null pointer, ignore it. 326 if (isa<ConstantPointerNull>(SI->getOperand(0))) 327 continue; 328 329 // Check the value being stored. 330 Value *Ptr = GetUnderlyingObject(SI->getOperand(0)); 331 332 if (isMalloc(Ptr)) { 333 // Okay, easy case. 334 } else if (CallInst *CI = dyn_cast<CallInst>(Ptr)) { 335 Function *F = CI->getCalledFunction(); 336 if (!F || !F->isDeclaration()) return false; // Too hard to analyze. 337 if (F->getName() != "calloc") return false; // Not calloc. 338 } else { 339 return false; // Too hard to analyze. 340 } 341 342 // Analyze all uses of the allocation. If any of them are used in a 343 // non-simple way (e.g. stored to another global) bail out. 344 std::vector<Function*> ReadersWriters; 345 if (AnalyzeUsesOfPointer(Ptr, ReadersWriters, ReadersWriters, GV)) 346 return false; // Loaded pointer escapes. 347 348 // Remember that this allocation is related to the indirect global. 349 AllocRelatedValues.push_back(Ptr); 350 } else { 351 // Something complex, bail out. 352 return false; 353 } 354 } 355 356 // Okay, this is an indirect global. Remember all of the allocations for 357 // this global in AllocsForIndirectGlobals. 358 while (!AllocRelatedValues.empty()) { 359 AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV; 360 AllocRelatedValues.pop_back(); 361 } 362 IndirectGlobals.insert(GV); 363 return true; 364 } 365 366 /// AnalyzeCallGraph - At this point, we know the functions where globals are 367 /// immediately stored to and read from. Propagate this information up the call 368 /// graph to all callers and compute the mod/ref info for all memory for each 369 /// function. 370 void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) { 371 // We do a bottom-up SCC traversal of the call graph. In other words, we 372 // visit all callees before callers (leaf-first). 373 for (scc_iterator<CallGraph*> I = scc_begin(&CG), E = scc_end(&CG); I != E; 374 ++I) { 375 std::vector<CallGraphNode *> &SCC = *I; 376 assert(!SCC.empty() && "SCC with no functions?"); 377 378 if (!SCC[0]->getFunction()) { 379 // Calls externally - can't say anything useful. Remove any existing 380 // function records (may have been created when scanning globals). 381 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 382 FunctionInfo.erase(SCC[i]->getFunction()); 383 continue; 384 } 385 386 FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()]; 387 388 bool KnowNothing = false; 389 unsigned FunctionEffect = 0; 390 391 // Collect the mod/ref properties due to called functions. We only compute 392 // one mod-ref set. 393 for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) { 394 Function *F = SCC[i]->getFunction(); 395 if (!F) { 396 KnowNothing = true; 397 break; 398 } 399 400 if (F->isDeclaration()) { 401 // Try to get mod/ref behaviour from function attributes. 402 if (F->doesNotAccessMemory()) { 403 // Can't do better than that! 404 } else if (F->onlyReadsMemory()) { 405 FunctionEffect |= Ref; 406 if (!F->isIntrinsic()) 407 // This function might call back into the module and read a global - 408 // consider every global as possibly being read by this function. 409 FR.MayReadAnyGlobal = true; 410 } else { 411 FunctionEffect |= ModRef; 412 // Can't say anything useful unless it's an intrinsic - they don't 413 // read or write global variables of the kind considered here. 414 KnowNothing = !F->isIntrinsic(); 415 } 416 continue; 417 } 418 419 for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end(); 420 CI != E && !KnowNothing; ++CI) 421 if (Function *Callee = CI->second->getFunction()) { 422 if (FunctionRecord *CalleeFR = getFunctionInfo(Callee)) { 423 // Propagate function effect up. 424 FunctionEffect |= CalleeFR->FunctionEffect; 425 426 // Incorporate callee's effects on globals into our info. 427 for (std::map<const GlobalValue*, unsigned>::iterator GI = 428 CalleeFR->GlobalInfo.begin(), E = CalleeFR->GlobalInfo.end(); 429 GI != E; ++GI) 430 FR.GlobalInfo[GI->first] |= GI->second; 431 FR.MayReadAnyGlobal |= CalleeFR->MayReadAnyGlobal; 432 } else { 433 // Can't say anything about it. However, if it is inside our SCC, 434 // then nothing needs to be done. 435 CallGraphNode *CalleeNode = CG[Callee]; 436 if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()) 437 KnowNothing = true; 438 } 439 } else { 440 KnowNothing = true; 441 } 442 } 443 444 // If we can't say anything useful about this SCC, remove all SCC functions 445 // from the FunctionInfo map. 446 if (KnowNothing) { 447 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 448 FunctionInfo.erase(SCC[i]->getFunction()); 449 continue; 450 } 451 452 // Scan the function bodies for explicit loads or stores. 453 for (unsigned i = 0, e = SCC.size(); i != e && FunctionEffect != ModRef;++i) 454 for (inst_iterator II = inst_begin(SCC[i]->getFunction()), 455 E = inst_end(SCC[i]->getFunction()); 456 II != E && FunctionEffect != ModRef; ++II) 457 if (isa<LoadInst>(*II)) { 458 FunctionEffect |= Ref; 459 if (cast<LoadInst>(*II).isVolatile()) 460 // Volatile loads may have side-effects, so mark them as writing 461 // memory (for example, a flag inside the processor). 462 FunctionEffect |= Mod; 463 } else if (isa<StoreInst>(*II)) { 464 FunctionEffect |= Mod; 465 if (cast<StoreInst>(*II).isVolatile()) 466 // Treat volatile stores as reading memory somewhere. 467 FunctionEffect |= Ref; 468 } else if (isMalloc(&cast<Instruction>(*II)) || 469 isFreeCall(&cast<Instruction>(*II))) { 470 FunctionEffect |= ModRef; 471 } else if (IntrinsicInst *Intrinsic = dyn_cast<IntrinsicInst>(&*II)) { 472 // The callgraph doesn't include intrinsic calls. 473 Function *Callee = Intrinsic->getCalledFunction(); 474 ModRefBehavior Behaviour = AliasAnalysis::getModRefBehavior(Callee); 475 FunctionEffect |= (Behaviour & ModRef); 476 } 477 478 if ((FunctionEffect & Mod) == 0) 479 ++NumReadMemFunctions; 480 if (FunctionEffect == 0) 481 ++NumNoMemFunctions; 482 FR.FunctionEffect = FunctionEffect; 483 484 // Finally, now that we know the full effect on this SCC, clone the 485 // information to each function in the SCC. 486 for (unsigned i = 1, e = SCC.size(); i != e; ++i) 487 FunctionInfo[SCC[i]->getFunction()] = FR; 488 } 489 } 490 491 492 493 /// alias - If one of the pointers is to a global that we are tracking, and the 494 /// other is some random pointer, we know there cannot be an alias, because the 495 /// address of the global isn't taken. 496 AliasAnalysis::AliasResult 497 GlobalsModRef::alias(const Location &LocA, 498 const Location &LocB) { 499 // Get the base object these pointers point to. 500 const Value *UV1 = GetUnderlyingObject(LocA.Ptr); 501 const Value *UV2 = GetUnderlyingObject(LocB.Ptr); 502 503 // If either of the underlying values is a global, they may be non-addr-taken 504 // globals, which we can answer queries about. 505 const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1); 506 const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2); 507 if (GV1 || GV2) { 508 // If the global's address is taken, pretend we don't know it's a pointer to 509 // the global. 510 if (GV1 && !NonAddressTakenGlobals.count(GV1)) GV1 = 0; 511 if (GV2 && !NonAddressTakenGlobals.count(GV2)) GV2 = 0; 512 513 // If the two pointers are derived from two different non-addr-taken 514 // globals, or if one is and the other isn't, we know these can't alias. 515 if ((GV1 || GV2) && GV1 != GV2) 516 return NoAlias; 517 518 // Otherwise if they are both derived from the same addr-taken global, we 519 // can't know the two accesses don't overlap. 520 } 521 522 // These pointers may be based on the memory owned by an indirect global. If 523 // so, we may be able to handle this. First check to see if the base pointer 524 // is a direct load from an indirect global. 525 GV1 = GV2 = 0; 526 if (const LoadInst *LI = dyn_cast<LoadInst>(UV1)) 527 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0))) 528 if (IndirectGlobals.count(GV)) 529 GV1 = GV; 530 if (const LoadInst *LI = dyn_cast<LoadInst>(UV2)) 531 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0))) 532 if (IndirectGlobals.count(GV)) 533 GV2 = GV; 534 535 // These pointers may also be from an allocation for the indirect global. If 536 // so, also handle them. 537 if (AllocsForIndirectGlobals.count(UV1)) 538 GV1 = AllocsForIndirectGlobals[UV1]; 539 if (AllocsForIndirectGlobals.count(UV2)) 540 GV2 = AllocsForIndirectGlobals[UV2]; 541 542 // Now that we know whether the two pointers are related to indirect globals, 543 // use this to disambiguate the pointers. If either pointer is based on an 544 // indirect global and if they are not both based on the same indirect global, 545 // they cannot alias. 546 if ((GV1 || GV2) && GV1 != GV2) 547 return NoAlias; 548 549 return AliasAnalysis::alias(LocA, LocB); 550 } 551 552 AliasAnalysis::ModRefResult 553 GlobalsModRef::getModRefInfo(ImmutableCallSite CS, 554 const Location &Loc) { 555 unsigned Known = ModRef; 556 557 // If we are asking for mod/ref info of a direct call with a pointer to a 558 // global we are tracking, return information if we have it. 559 if (const GlobalValue *GV = 560 dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr))) 561 if (GV->hasLocalLinkage()) 562 if (const Function *F = CS.getCalledFunction()) 563 if (NonAddressTakenGlobals.count(GV)) 564 if (const FunctionRecord *FR = getFunctionInfo(F)) 565 Known = FR->getInfoForGlobal(GV); 566 567 if (Known == NoModRef) 568 return NoModRef; // No need to query other mod/ref analyses 569 return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, Loc)); 570 } 571 572 573 //===----------------------------------------------------------------------===// 574 // Methods to update the analysis as a result of the client transformation. 575 // 576 void GlobalsModRef::deleteValue(Value *V) { 577 if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { 578 if (NonAddressTakenGlobals.erase(GV)) { 579 // This global might be an indirect global. If so, remove it and remove 580 // any AllocRelatedValues for it. 581 if (IndirectGlobals.erase(GV)) { 582 // Remove any entries in AllocsForIndirectGlobals for this global. 583 for (std::map<const Value*, const GlobalValue*>::iterator 584 I = AllocsForIndirectGlobals.begin(), 585 E = AllocsForIndirectGlobals.end(); I != E; ) { 586 if (I->second == GV) { 587 AllocsForIndirectGlobals.erase(I++); 588 } else { 589 ++I; 590 } 591 } 592 } 593 } 594 } 595 596 // Otherwise, if this is an allocation related to an indirect global, remove 597 // it. 598 AllocsForIndirectGlobals.erase(V); 599 600 AliasAnalysis::deleteValue(V); 601 } 602 603 void GlobalsModRef::copyValue(Value *From, Value *To) { 604 AliasAnalysis::copyValue(From, To); 605 } 606 607 void GlobalsModRef::addEscapingUse(Use &U) { 608 // For the purposes of this analysis, it is conservatively correct to treat 609 // a newly escaping value equivalently to a deleted one. We could perhaps 610 // be more precise by processing the new use and attempting to update our 611 // saved analysis results to accommodate it. 612 deleteValue(U); 613 614 AliasAnalysis::addEscapingUse(U); 615 } 616