LLVM API Documentation

GlobalsModRef.cpp

Go to the documentation of this file.
00001 //===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This simple pass provides alias and mod/ref information for global values
00011 // that do not have their address taken, and keeps track of whether functions
00012 // read or write memory (are "pure").  For this simple (but very common) case,
00013 // we can provide pretty accurate and useful information.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #define DEBUG_TYPE "globalsmodref-aa"
00018 #include "llvm/Analysis/Passes.h"
00019 #include "llvm/Module.h"
00020 #include "llvm/Pass.h"
00021 #include "llvm/Instructions.h"
00022 #include "llvm/Constants.h"
00023 #include "llvm/DerivedTypes.h"
00024 #include "llvm/Analysis/AliasAnalysis.h"
00025 #include "llvm/Analysis/CallGraph.h"
00026 #include "llvm/Support/Compiler.h"
00027 #include "llvm/Support/CommandLine.h"
00028 #include "llvm/Support/InstIterator.h"
00029 #include "llvm/ADT/Statistic.h"
00030 #include "llvm/ADT/SCCIterator.h"
00031 #include <set>
00032 using namespace llvm;
00033 
00034 STATISTIC(NumNonAddrTakenGlobalVars,
00035           "Number of global vars without address taken");
00036 STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
00037 STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
00038 STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
00039 STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
00040 
00041 namespace {
00042   /// FunctionRecord - One instance of this structure is stored for every
00043   /// function in the program.  Later, the entries for these functions are
00044   /// removed if the function is found to call an external function (in which
00045   /// case we know nothing about it.
00046   struct VISIBILITY_HIDDEN FunctionRecord {
00047     /// GlobalInfo - Maintain mod/ref info for all of the globals without
00048     /// addresses taken that are read or written (transitively) by this
00049     /// function.
00050     std::map<GlobalValue*, unsigned> GlobalInfo;
00051 
00052     /// MayReadAnyGlobal - May read global variables, but it is not known which.
00053     bool MayReadAnyGlobal;
00054 
00055     unsigned getInfoForGlobal(GlobalValue *GV) const {
00056       unsigned Effect = MayReadAnyGlobal ? AliasAnalysis::Ref : 0;
00057       std::map<GlobalValue*, unsigned>::const_iterator I = GlobalInfo.find(GV);
00058       if (I != GlobalInfo.end())
00059         Effect |= I->second;
00060       return Effect;
00061     }
00062 
00063     /// FunctionEffect - Capture whether or not this function reads or writes to
00064     /// ANY memory.  If not, we can do a lot of aggressive analysis on it.
00065     unsigned FunctionEffect;
00066 
00067     FunctionRecord() : MayReadAnyGlobal (false), FunctionEffect(0) {}
00068   };
00069 
00070   /// GlobalsModRef - The actual analysis pass.
00071   class VISIBILITY_HIDDEN GlobalsModRef
00072       : public ModulePass, public AliasAnalysis {
00073     /// NonAddressTakenGlobals - The globals that do not have their addresses
00074     /// taken.
00075     std::set<GlobalValue*> NonAddressTakenGlobals;
00076 
00077     /// IndirectGlobals - The memory pointed to by this global is known to be
00078     /// 'owned' by the global.
00079     std::set<GlobalValue*> IndirectGlobals;
00080 
00081     /// AllocsForIndirectGlobals - If an instruction allocates memory for an
00082     /// indirect global, this map indicates which one.
00083     std::map<Value*, GlobalValue*> AllocsForIndirectGlobals;
00084 
00085     /// FunctionInfo - For each function, keep track of what globals are
00086     /// modified or read.
00087     std::map<Function*, FunctionRecord> FunctionInfo;
00088 
00089   public:
00090     static char ID;
00091     GlobalsModRef() : ModulePass(&ID) {}
00092 
00093     bool runOnModule(Module &M) {
00094       InitializeAliasAnalysis(this);                 // set up super class
00095       AnalyzeGlobals(M);                          // find non-addr taken globals
00096       AnalyzeCallGraph(getAnalysis<CallGraph>(), M); // Propagate on CG
00097       return false;
00098     }
00099 
00100     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00101       AliasAnalysis::getAnalysisUsage(AU);
00102       AU.addRequired<CallGraph>();
00103       AU.setPreservesAll();                         // Does not transform code
00104     }
00105 
00106     //------------------------------------------------
00107     // Implement the AliasAnalysis API
00108     //
00109     AliasResult alias(const Value *V1, unsigned V1Size,
00110                       const Value *V2, unsigned V2Size);
00111     ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
00112     ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
00113       return AliasAnalysis::getModRefInfo(CS1,CS2);
00114     }
00115     bool hasNoModRefInfoForCalls() const { return false; }
00116 
00117     /// getModRefBehavior - Return the behavior of the specified function if
00118     /// called from the specified call site.  The call site may be null in which
00119     /// case the most generic behavior of this function should be returned.
00120     ModRefBehavior getModRefBehavior(Function *F,
00121                                          std::vector<PointerAccessInfo> *Info) {
00122       if (FunctionRecord *FR = getFunctionInfo(F)) {
00123         if (FR->FunctionEffect == 0)
00124           return DoesNotAccessMemory;
00125         else if ((FR->FunctionEffect & Mod) == 0)
00126           return OnlyReadsMemory;
00127       }
00128       return AliasAnalysis::getModRefBehavior(F, Info);
00129     }
00130     
00131     /// getModRefBehavior - Return the behavior of the specified function if
00132     /// called from the specified call site.  The call site may be null in which
00133     /// case the most generic behavior of this function should be returned.
00134     ModRefBehavior getModRefBehavior(CallSite CS,
00135                                          std::vector<PointerAccessInfo> *Info) {
00136       Function* F = CS.getCalledFunction();
00137       if (!F) return AliasAnalysis::getModRefBehavior(CS, Info);
00138       if (FunctionRecord *FR = getFunctionInfo(F)) {
00139         if (FR->FunctionEffect == 0)
00140           return DoesNotAccessMemory;
00141         else if ((FR->FunctionEffect & Mod) == 0)
00142           return OnlyReadsMemory;
00143       }
00144       return AliasAnalysis::getModRefBehavior(CS, Info);
00145     }
00146 
00147     virtual void deleteValue(Value *V);
00148     virtual void copyValue(Value *From, Value *To);
00149 
00150   private:
00151     /// getFunctionInfo - Return the function info for the function, or null if
00152     /// we don't have anything useful to say about it.
00153     FunctionRecord *getFunctionInfo(Function *F) {
00154       std::map<Function*, FunctionRecord>::iterator I = FunctionInfo.find(F);
00155       if (I != FunctionInfo.end())
00156         return &I->second;
00157       return 0;
00158     }
00159 
00160     void AnalyzeGlobals(Module &M);
00161     void AnalyzeCallGraph(CallGraph &CG, Module &M);
00162     bool AnalyzeUsesOfPointer(Value *V, std::vector<Function*> &Readers,
00163                               std::vector<Function*> &Writers,
00164                               GlobalValue *OkayStoreDest = 0);
00165     bool AnalyzeIndirectGlobalMemory(GlobalValue *GV);
00166   };
00167 }
00168 
00169 char GlobalsModRef::ID = 0;
00170 static RegisterPass<GlobalsModRef>
00171 X("globalsmodref-aa", "Simple mod/ref analysis for globals", false, true);
00172 static RegisterAnalysisGroup<AliasAnalysis> Y(X);
00173 
00174 Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
00175 
00176 /// AnalyzeGlobals - Scan through the users of all of the internal
00177 /// GlobalValue's in the program.  If none of them have their "address taken"
00178 /// (really, their address passed to something nontrivial), record this fact,
00179 /// and record the functions that they are used directly in.
00180 void GlobalsModRef::AnalyzeGlobals(Module &M) {
00181   std::vector<Function*> Readers, Writers;
00182   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00183     if (I->hasLocalLinkage()) {
00184       if (!AnalyzeUsesOfPointer(I, Readers, Writers)) {
00185         // Remember that we are tracking this global.
00186         NonAddressTakenGlobals.insert(I);
00187         ++NumNonAddrTakenFunctions;
00188       }
00189       Readers.clear(); Writers.clear();
00190     }
00191 
00192   for (Module::global_iterator I = M.global_begin(), E = M.global_end();
00193        I != E; ++I)
00194     if (I->hasLocalLinkage()) {
00195       if (!AnalyzeUsesOfPointer(I, Readers, Writers)) {
00196         // Remember that we are tracking this global, and the mod/ref fns
00197         NonAddressTakenGlobals.insert(I);
00198 
00199         for (unsigned i = 0, e = Readers.size(); i != e; ++i)
00200           FunctionInfo[Readers[i]].GlobalInfo[I] |= Ref;
00201 
00202         if (!I->isConstant())  // No need to keep track of writers to constants
00203           for (unsigned i = 0, e = Writers.size(); i != e; ++i)
00204             FunctionInfo[Writers[i]].GlobalInfo[I] |= Mod;
00205         ++NumNonAddrTakenGlobalVars;
00206 
00207         // If this global holds a pointer type, see if it is an indirect global.
00208         if (isa<PointerType>(I->getType()->getElementType()) &&
00209             AnalyzeIndirectGlobalMemory(I))
00210           ++NumIndirectGlobalVars;
00211       }
00212       Readers.clear(); Writers.clear();
00213     }
00214 }
00215 
00216 /// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
00217 /// If this is used by anything complex (i.e., the address escapes), return
00218 /// true.  Also, while we are at it, keep track of those functions that read and
00219 /// write to the value.
00220 ///
00221 /// If OkayStoreDest is non-null, stores into this global are allowed.
00222 bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
00223                                          std::vector<Function*> &Readers,
00224                                          std::vector<Function*> &Writers,
00225                                          GlobalValue *OkayStoreDest) {
00226   if (!isa<PointerType>(V->getType())) return true;
00227 
00228   for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI)
00229     if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
00230       Readers.push_back(LI->getParent()->getParent());
00231     } else if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
00232       if (V == SI->getOperand(1)) {
00233         Writers.push_back(SI->getParent()->getParent());
00234       } else if (SI->getOperand(1) != OkayStoreDest) {
00235         return true;  // Storing the pointer
00236       }
00237     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
00238       if (AnalyzeUsesOfPointer(GEP, Readers, Writers)) return true;
00239     } else if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
00240       // Make sure that this is just the function being called, not that it is
00241       // passing into the function.
00242       for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
00243         if (CI->getOperand(i) == V) return true;
00244     } else if (InvokeInst *II = dyn_cast<InvokeInst>(*UI)) {
00245       // Make sure that this is just the function being called, not that it is
00246       // passing into the function.
00247       for (unsigned i = 3, e = II->getNumOperands(); i != e; ++i)
00248         if (II->getOperand(i) == V) return true;
00249     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(*UI)) {
00250       if (CE->getOpcode() == Instruction::GetElementPtr ||
00251           CE->getOpcode() == Instruction::BitCast) {
00252         if (AnalyzeUsesOfPointer(CE, Readers, Writers))
00253           return true;
00254       } else {
00255         return true;
00256       }
00257     } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(*UI)) {
00258       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
00259         return true;  // Allow comparison against null.
00260     } else if (FreeInst *F = dyn_cast<FreeInst>(*UI)) {
00261       Writers.push_back(F->getParent()->getParent());
00262     } else {
00263       return true;
00264     }
00265   return false;
00266 }
00267 
00268 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
00269 /// which holds a pointer type.  See if the global always points to non-aliased
00270 /// heap memory: that is, all initializers of the globals are allocations, and
00271 /// those allocations have no use other than initialization of the global.
00272 /// Further, all loads out of GV must directly use the memory, not store the
00273 /// pointer somewhere.  If this is true, we consider the memory pointed to by
00274 /// GV to be owned by GV and can disambiguate other pointers from it.
00275 bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
00276   // Keep track of values related to the allocation of the memory, f.e. the
00277   // value produced by the malloc call and any casts.
00278   std::vector<Value*> AllocRelatedValues;
00279 
00280   // Walk the user list of the global.  If we find anything other than a direct
00281   // load or store, bail out.
00282   for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){
00283     if (LoadInst *LI = dyn_cast<LoadInst>(*I)) {
00284       // The pointer loaded from the global can only be used in simple ways:
00285       // we allow addressing of it and loading storing to it.  We do *not* allow
00286       // storing the loaded pointer somewhere else or passing to a function.
00287       std::vector<Function*> ReadersWriters;
00288       if (AnalyzeUsesOfPointer(LI, ReadersWriters, ReadersWriters))
00289         return false;  // Loaded pointer escapes.
00290       // TODO: Could try some IP mod/ref of the loaded pointer.
00291     } else if (StoreInst *SI = dyn_cast<StoreInst>(*I)) {
00292       // Storing the global itself.
00293       if (SI->getOperand(0) == GV) return false;
00294 
00295       // If storing the null pointer, ignore it.
00296       if (isa<ConstantPointerNull>(SI->getOperand(0)))
00297         continue;
00298 
00299       // Check the value being stored.
00300       Value *Ptr = SI->getOperand(0)->getUnderlyingObject();
00301 
00302       if (isa<MallocInst>(Ptr)) {
00303         // Okay, easy case.
00304       } else if (CallInst *CI = dyn_cast<CallInst>(Ptr)) {
00305         Function *F = CI->getCalledFunction();
00306         if (!F || !F->isDeclaration()) return false;     // Too hard to analyze.
00307         if (F->getName() != "calloc") return false;   // Not calloc.
00308       } else {
00309         return false;  // Too hard to analyze.
00310       }
00311 
00312       // Analyze all uses of the allocation.  If any of them are used in a
00313       // non-simple way (e.g. stored to another global) bail out.
00314       std::vector<Function*> ReadersWriters;
00315       if (AnalyzeUsesOfPointer(Ptr, ReadersWriters, ReadersWriters, GV))
00316         return false;  // Loaded pointer escapes.
00317 
00318       // Remember that this allocation is related to the indirect global.
00319       AllocRelatedValues.push_back(Ptr);
00320     } else {
00321       // Something complex, bail out.
00322       return false;
00323     }
00324   }
00325 
00326   // Okay, this is an indirect global.  Remember all of the allocations for
00327   // this global in AllocsForIndirectGlobals.
00328   while (!AllocRelatedValues.empty()) {
00329     AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
00330     AllocRelatedValues.pop_back();
00331   }
00332   IndirectGlobals.insert(GV);
00333   return true;
00334 }
00335 
00336 /// AnalyzeCallGraph - At this point, we know the functions where globals are
00337 /// immediately stored to and read from.  Propagate this information up the call
00338 /// graph to all callers and compute the mod/ref info for all memory for each
00339 /// function.
00340 void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
00341   // We do a bottom-up SCC traversal of the call graph.  In other words, we
00342   // visit all callees before callers (leaf-first).
00343   for (scc_iterator<CallGraph*> I = scc_begin(&CG), E = scc_end(&CG); I != E;
00344        ++I) {
00345     std::vector<CallGraphNode *> &SCC = *I;
00346     assert(!SCC.empty() && "SCC with no functions?");
00347 
00348     if (!SCC[0]->getFunction()) {
00349       // Calls externally - can't say anything useful.  Remove any existing
00350       // function records (may have been created when scanning globals).
00351       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00352         FunctionInfo.erase(SCC[i]->getFunction());
00353       continue;
00354     }
00355 
00356     FunctionRecord &FR = FunctionInfo[SCC[0]->getFunction()];
00357 
00358     bool KnowNothing = false;
00359     unsigned FunctionEffect = 0;
00360 
00361     // Collect the mod/ref properties due to called functions.  We only compute
00362     // one mod-ref set.
00363     for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
00364       Function *F = SCC[i]->getFunction();
00365       if (!F) {
00366         KnowNothing = true;
00367         break;
00368       }
00369 
00370       if (F->isDeclaration()) {
00371         // Try to get mod/ref behaviour from function attributes.
00372         if (F->doesNotAccessMemory()) {
00373           // Can't do better than that!
00374         } else if (F->onlyReadsMemory()) {
00375           FunctionEffect |= Ref;
00376           if (!F->isIntrinsic())
00377             // This function might call back into the module and read a global -
00378             // consider every global as possibly being read by this function.
00379             FR.MayReadAnyGlobal = true;
00380         } else {
00381           FunctionEffect |= ModRef;
00382           // Can't say anything useful unless it's an intrinsic - they don't
00383           // read or write global variables of the kind considered here.
00384           KnowNothing = !F->isIntrinsic();
00385         }
00386         continue;
00387       }
00388 
00389       for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
00390            CI != E && !KnowNothing; ++CI)
00391         if (Function *Callee = CI->second->getFunction()) {
00392           if (FunctionRecord *CalleeFR = getFunctionInfo(Callee)) {
00393             // Propagate function effect up.
00394             FunctionEffect |= CalleeFR->FunctionEffect;
00395 
00396             // Incorporate callee's effects on globals into our info.
00397             for (std::map<GlobalValue*, unsigned>::iterator GI =
00398                    CalleeFR->GlobalInfo.begin(), E = CalleeFR->GlobalInfo.end();
00399                  GI != E; ++GI)
00400               FR.GlobalInfo[GI->first] |= GI->second;
00401             FR.MayReadAnyGlobal |= CalleeFR->MayReadAnyGlobal;
00402           } else {
00403             // Can't say anything about it.  However, if it is inside our SCC,
00404             // then nothing needs to be done.
00405             CallGraphNode *CalleeNode = CG[Callee];
00406             if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end())
00407               KnowNothing = true;
00408           }
00409         } else {
00410           KnowNothing = true;
00411         }
00412     }
00413 
00414     // If we can't say anything useful about this SCC, remove all SCC functions
00415     // from the FunctionInfo map.
00416     if (KnowNothing) {
00417       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00418         FunctionInfo.erase(SCC[i]->getFunction());
00419       continue;
00420     }
00421 
00422     // Scan the function bodies for explicit loads or stores.
00423     for (unsigned i = 0, e = SCC.size(); i != e && FunctionEffect != ModRef;++i)
00424       for (inst_iterator II = inst_begin(SCC[i]->getFunction()),
00425              E = inst_end(SCC[i]->getFunction());
00426            II != E && FunctionEffect != ModRef; ++II)
00427         if (isa<LoadInst>(*II)) {
00428           FunctionEffect |= Ref;
00429           if (cast<LoadInst>(*II).isVolatile())
00430             // Volatile loads may have side-effects, so mark them as writing
00431             // memory (for example, a flag inside the processor).
00432             FunctionEffect |= Mod;
00433         } else if (isa<StoreInst>(*II)) {
00434           FunctionEffect |= Mod;
00435           if (cast<StoreInst>(*II).isVolatile())
00436             // Treat volatile stores as reading memory somewhere.
00437             FunctionEffect |= Ref;
00438         } else if (isa<MallocInst>(*II) || isa<FreeInst>(*II)) {
00439           FunctionEffect |= ModRef;
00440         }
00441 
00442     if ((FunctionEffect & Mod) == 0)
00443       ++NumReadMemFunctions;
00444     if (FunctionEffect == 0)
00445       ++NumNoMemFunctions;
00446     FR.FunctionEffect = FunctionEffect;
00447 
00448     // Finally, now that we know the full effect on this SCC, clone the
00449     // information to each function in the SCC.
00450     for (unsigned i = 1, e = SCC.size(); i != e; ++i)
00451       FunctionInfo[SCC[i]->getFunction()] = FR;
00452   }
00453 }
00454 
00455 
00456 
00457 /// alias - If one of the pointers is to a global that we are tracking, and the
00458 /// other is some random pointer, we know there cannot be an alias, because the
00459 /// address of the global isn't taken.
00460 AliasAnalysis::AliasResult
00461 GlobalsModRef::alias(const Value *V1, unsigned V1Size,
00462                      const Value *V2, unsigned V2Size) {
00463   // Get the base object these pointers point to.
00464   Value *UV1 = const_cast<Value*>(V1->getUnderlyingObject());
00465   Value *UV2 = const_cast<Value*>(V2->getUnderlyingObject());
00466 
00467   // If either of the underlying values is a global, they may be non-addr-taken
00468   // globals, which we can answer queries about.
00469   GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
00470   GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
00471   if (GV1 || GV2) {
00472     // If the global's address is taken, pretend we don't know it's a pointer to
00473     // the global.
00474     if (GV1 && !NonAddressTakenGlobals.count(GV1)) GV1 = 0;
00475     if (GV2 && !NonAddressTakenGlobals.count(GV2)) GV2 = 0;
00476 
00477     // If the the two pointers are derived from two different non-addr-taken
00478     // globals, or if one is and the other isn't, we know these can't alias.
00479     if ((GV1 || GV2) && GV1 != GV2)
00480       return NoAlias;
00481 
00482     // Otherwise if they are both derived from the same addr-taken global, we
00483     // can't know the two accesses don't overlap.
00484   }
00485 
00486   // These pointers may be based on the memory owned by an indirect global.  If
00487   // so, we may be able to handle this.  First check to see if the base pointer
00488   // is a direct load from an indirect global.
00489   GV1 = GV2 = 0;
00490   if (LoadInst *LI = dyn_cast<LoadInst>(UV1))
00491     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
00492       if (IndirectGlobals.count(GV))
00493         GV1 = GV;
00494   if (LoadInst *LI = dyn_cast<LoadInst>(UV2))
00495     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
00496       if (IndirectGlobals.count(GV))
00497         GV2 = GV;
00498 
00499   // These pointers may also be from an allocation for the indirect global.  If
00500   // so, also handle them.
00501   if (AllocsForIndirectGlobals.count(UV1))
00502     GV1 = AllocsForIndirectGlobals[UV1];
00503   if (AllocsForIndirectGlobals.count(UV2))
00504     GV2 = AllocsForIndirectGlobals[UV2];
00505 
00506   // Now that we know whether the two pointers are related to indirect globals,
00507   // use this to disambiguate the pointers.  If either pointer is based on an
00508   // indirect global and if they are not both based on the same indirect global,
00509   // they cannot alias.
00510   if ((GV1 || GV2) && GV1 != GV2)
00511     return NoAlias;
00512 
00513   return AliasAnalysis::alias(V1, V1Size, V2, V2Size);
00514 }
00515 
00516 AliasAnalysis::ModRefResult
00517 GlobalsModRef::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
00518   unsigned Known = ModRef;
00519 
00520   // If we are asking for mod/ref info of a direct call with a pointer to a
00521   // global we are tracking, return information if we have it.
00522   if (GlobalValue *GV = dyn_cast<GlobalValue>(P->getUnderlyingObject()))
00523     if (GV->hasLocalLinkage())
00524       if (Function *F = CS.getCalledFunction())
00525         if (NonAddressTakenGlobals.count(GV))
00526           if (FunctionRecord *FR = getFunctionInfo(F))
00527             Known = FR->getInfoForGlobal(GV);
00528 
00529   if (Known == NoModRef)
00530     return NoModRef; // No need to query other mod/ref analyses
00531   return ModRefResult(Known & AliasAnalysis::getModRefInfo(CS, P, Size));
00532 }
00533 
00534 
00535 //===----------------------------------------------------------------------===//
00536 // Methods to update the analysis as a result of the client transformation.
00537 //
00538 void GlobalsModRef::deleteValue(Value *V) {
00539   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00540     if (NonAddressTakenGlobals.erase(GV)) {
00541       // This global might be an indirect global.  If so, remove it and remove
00542       // any AllocRelatedValues for it.
00543       if (IndirectGlobals.erase(GV)) {
00544         // Remove any entries in AllocsForIndirectGlobals for this global.
00545         for (std::map<Value*, GlobalValue*>::iterator
00546              I = AllocsForIndirectGlobals.begin(),
00547              E = AllocsForIndirectGlobals.end(); I != E; ) {
00548           if (I->second == GV) {
00549             AllocsForIndirectGlobals.erase(I++);
00550           } else {
00551             ++I;
00552           }
00553         }
00554       }
00555     }
00556   }
00557 
00558   // Otherwise, if this is an allocation related to an indirect global, remove
00559   // it.
00560   AllocsForIndirectGlobals.erase(V);
00561 
00562   AliasAnalysis::deleteValue(V);
00563 }
00564 
00565 void GlobalsModRef::copyValue(Value *From, Value *To) {
00566   AliasAnalysis::copyValue(From, To);
00567 }