LLVM API Documentation
00001 //===- DataStructureAA.cpp - Data Structure Based Alias Analysis ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass uses the top-down data structure graphs to implement a simple 00011 // context sensitive alias analysis. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Constants.h" 00016 #include "llvm/DerivedTypes.h" 00017 #include "llvm/Module.h" 00018 #include "llvm/Analysis/AliasAnalysis.h" 00019 #include "llvm/Analysis/Passes.h" 00020 #include "llvm/Analysis/DataStructure/DataStructure.h" 00021 #include "llvm/Analysis/DataStructure/DSGraph.h" 00022 using namespace llvm; 00023 00024 namespace { 00025 class DSAA : public ModulePass, public AliasAnalysis { 00026 TDDataStructures *TD; 00027 BUDataStructures *BU; 00028 00029 // These members are used to cache mod/ref information to make us return 00030 // results faster, particularly for aa-eval. On the first request of 00031 // mod/ref information for a particular call site, we compute and store the 00032 // calculated nodemap for the call site. Any time DSA info is updated we 00033 // free this information, and when we move onto a new call site, this 00034 // information is also freed. 00035 CallSite MapCS; 00036 std::multimap<DSNode*, const DSNode*> CallerCalleeMap; 00037 public: 00038 DSAA() : TD(0) {} 00039 ~DSAA() { 00040 InvalidateCache(); 00041 } 00042 00043 void InvalidateCache() { 00044 MapCS = CallSite(); 00045 CallerCalleeMap.clear(); 00046 } 00047 00048 //------------------------------------------------ 00049 // Implement the Pass API 00050 // 00051 00052 // run - Build up the result graph, representing the pointer graph for the 00053 // program. 00054 // 00055 bool runOnModule(Module &M) { 00056 InitializeAliasAnalysis(this); 00057 TD = &getAnalysis<TDDataStructures>(); 00058 BU = &getAnalysis<BUDataStructures>(); 00059 return false; 00060 } 00061 00062 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00063 AliasAnalysis::getAnalysisUsage(AU); 00064 AU.setPreservesAll(); // Does not transform code 00065 AU.addRequiredTransitive<TDDataStructures>(); // Uses TD Datastructures 00066 AU.addRequiredTransitive<BUDataStructures>(); // Uses BU Datastructures 00067 } 00068 00069 //------------------------------------------------ 00070 // Implement the AliasAnalysis API 00071 // 00072 00073 AliasResult alias(const Value *V1, unsigned V1Size, 00074 const Value *V2, unsigned V2Size); 00075 00076 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 00077 ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) { 00078 return AliasAnalysis::getModRefInfo(CS1,CS2); 00079 } 00080 00081 virtual void deleteValue(Value *V) { 00082 InvalidateCache(); 00083 BU->deleteValue(V); 00084 TD->deleteValue(V); 00085 } 00086 00087 virtual void copyValue(Value *From, Value *To) { 00088 if (From == To) return; 00089 InvalidateCache(); 00090 BU->copyValue(From, To); 00091 TD->copyValue(From, To); 00092 } 00093 00094 private: 00095 DSGraph *getGraphForValue(const Value *V); 00096 }; 00097 00098 // Register the pass... 00099 RegisterOpt<DSAA> X("ds-aa", "Data Structure Graph Based Alias Analysis"); 00100 00101 // Register as an implementation of AliasAnalysis 00102 RegisterAnalysisGroup<AliasAnalysis, DSAA> Y; 00103 } 00104 00105 ModulePass *llvm::createDSAAPass() { return new DSAA(); } 00106 00107 // getGraphForValue - Return the DSGraph to use for queries about the specified 00108 // value... 00109 // 00110 DSGraph *DSAA::getGraphForValue(const Value *V) { 00111 if (const Instruction *I = dyn_cast<Instruction>(V)) 00112 return &TD->getDSGraph(*I->getParent()->getParent()); 00113 else if (const Argument *A = dyn_cast<Argument>(V)) 00114 return &TD->getDSGraph(*A->getParent()); 00115 else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V)) 00116 return &TD->getDSGraph(*BB->getParent()); 00117 return 0; 00118 } 00119 00120 AliasAnalysis::AliasResult DSAA::alias(const Value *V1, unsigned V1Size, 00121 const Value *V2, unsigned V2Size) { 00122 if (V1 == V2) return MustAlias; 00123 00124 DSGraph *G1 = getGraphForValue(V1); 00125 DSGraph *G2 = getGraphForValue(V2); 00126 assert((!G1 || !G2 || G1 == G2) && "Alias query for 2 different functions?"); 00127 00128 // Get the graph to use... 00129 DSGraph &G = *(G1 ? G1 : (G2 ? G2 : &TD->getGlobalsGraph())); 00130 00131 const DSGraph::ScalarMapTy &GSM = G.getScalarMap(); 00132 DSGraph::ScalarMapTy::const_iterator I = GSM.find((Value*)V1); 00133 if (I == GSM.end()) return NoAlias; 00134 00135 DSGraph::ScalarMapTy::const_iterator J = GSM.find((Value*)V2); 00136 if (J == GSM.end()) return NoAlias; 00137 00138 DSNode *N1 = I->second.getNode(), *N2 = J->second.getNode(); 00139 unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset(); 00140 if (N1 == 0 || N2 == 0) 00141 // Can't tell whether anything aliases null. 00142 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00143 00144 // We can only make a judgment if one of the nodes is complete. 00145 if (N1->isComplete() || N2->isComplete()) { 00146 if (N1 != N2) 00147 return NoAlias; // Completely different nodes. 00148 00149 // See if they point to different offsets... if so, we may be able to 00150 // determine that they do not alias... 00151 if (O1 != O2) { 00152 if (O2 < O1) { // Ensure that O1 <= O2 00153 std::swap(V1, V2); 00154 std::swap(O1, O2); 00155 std::swap(V1Size, V2Size); 00156 } 00157 00158 if (O1+V1Size <= O2) 00159 return NoAlias; 00160 } 00161 } 00162 00163 // FIXME: we could improve on this by checking the globals graph for aliased 00164 // global queries... 00165 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00166 } 00167 00168 /// getModRefInfo - does a callsite modify or reference a value? 00169 /// 00170 AliasAnalysis::ModRefResult 00171 DSAA::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00172 DSNode *N = 0; 00173 // First step, check our cache. 00174 if (CS.getInstruction() == MapCS.getInstruction()) { 00175 { 00176 const Function *Caller = CS.getInstruction()->getParent()->getParent(); 00177 DSGraph &CallerTDGraph = TD->getDSGraph(*Caller); 00178 00179 // Figure out which node in the TD graph this pointer corresponds to. 00180 DSScalarMap &CallerSM = CallerTDGraph.getScalarMap(); 00181 DSScalarMap::iterator NI = CallerSM.find(P); 00182 if (NI == CallerSM.end()) { 00183 InvalidateCache(); 00184 return DSAA::getModRefInfo(CS, P, Size); 00185 } 00186 N = NI->second.getNode(); 00187 } 00188 00189 HaveMappingInfo: 00190 assert(N && "Null pointer in scalar map??"); 00191 00192 typedef std::multimap<DSNode*, const DSNode*>::iterator NodeMapIt; 00193 std::pair<NodeMapIt, NodeMapIt> Range = CallerCalleeMap.equal_range(N); 00194 00195 // Loop over all of the nodes in the callee that correspond to "N", keeping 00196 // track of aggregate mod/ref info. 00197 bool NeverReads = true, NeverWrites = true; 00198 for (; Range.first != Range.second; ++Range.first) { 00199 if (Range.first->second->isModified()) 00200 NeverWrites = false; 00201 if (Range.first->second->isRead()) 00202 NeverReads = false; 00203 if (NeverReads == false && NeverWrites == false) 00204 return AliasAnalysis::getModRefInfo(CS, P, Size); 00205 } 00206 00207 ModRefResult Result = ModRef; 00208 if (NeverWrites) // We proved it was not modified. 00209 Result = ModRefResult(Result & ~Mod); 00210 if (NeverReads) // We proved it was not read. 00211 Result = ModRefResult(Result & ~Ref); 00212 00213 return ModRefResult(Result & AliasAnalysis::getModRefInfo(CS, P, Size)); 00214 } 00215 00216 // Any cached info we have is for the wrong function. 00217 InvalidateCache(); 00218 00219 Function *F = CS.getCalledFunction(); 00220 00221 if (!F) return AliasAnalysis::getModRefInfo(CS, P, Size); 00222 00223 if (F->isExternal()) { 00224 // If we are calling an external function, and if this global doesn't escape 00225 // the portion of the program we have analyzed, we can draw conclusions 00226 // based on whether the global escapes the program. 00227 Function *Caller = CS.getInstruction()->getParent()->getParent(); 00228 DSGraph *G = &TD->getDSGraph(*Caller); 00229 DSScalarMap::iterator NI = G->getScalarMap().find(P); 00230 if (NI == G->getScalarMap().end()) { 00231 // If it wasn't in the local function graph, check the global graph. This 00232 // can occur for globals who are locally reference but hoisted out to the 00233 // globals graph despite that. 00234 G = G->getGlobalsGraph(); 00235 NI = G->getScalarMap().find(P); 00236 if (NI == G->getScalarMap().end()) 00237 return AliasAnalysis::getModRefInfo(CS, P, Size); 00238 } 00239 00240 // If we found a node and it's complete, it cannot be passed out to the 00241 // called function. 00242 if (NI->second.getNode()->isComplete()) 00243 return NoModRef; 00244 return AliasAnalysis::getModRefInfo(CS, P, Size); 00245 } 00246 00247 // Get the graphs for the callee and caller. Note that we want the BU graph 00248 // for the callee because we don't want all caller's effects incorporated! 00249 const Function *Caller = CS.getInstruction()->getParent()->getParent(); 00250 DSGraph &CallerTDGraph = TD->getDSGraph(*Caller); 00251 DSGraph &CalleeBUGraph = BU->getDSGraph(*F); 00252 00253 // Figure out which node in the TD graph this pointer corresponds to. 00254 DSScalarMap &CallerSM = CallerTDGraph.getScalarMap(); 00255 DSScalarMap::iterator NI = CallerSM.find(P); 00256 if (NI == CallerSM.end()) { 00257 ModRefResult Result = ModRef; 00258 if (isa<ConstantPointerNull>(P) || isa<UndefValue>(P)) 00259 return NoModRef; // null is never modified :) 00260 else { 00261 assert(isa<GlobalVariable>(P) && 00262 cast<GlobalVariable>(P)->getType()->getElementType()->isFirstClassType() && 00263 "This isn't a global that DSA inconsiderately dropped " 00264 "from the graph?"); 00265 00266 DSGraph &GG = *CallerTDGraph.getGlobalsGraph(); 00267 DSScalarMap::iterator NI = GG.getScalarMap().find(P); 00268 if (NI != GG.getScalarMap().end() && !NI->second.isNull()) { 00269 // Otherwise, if the node is only M or R, return this. This can be 00270 // useful for globals that should be marked const but are not. 00271 DSNode *N = NI->second.getNode(); 00272 if (!N->isModified()) 00273 Result = (ModRefResult)(Result & ~Mod); 00274 if (!N->isRead()) 00275 Result = (ModRefResult)(Result & ~Ref); 00276 } 00277 } 00278 00279 if (Result == NoModRef) return Result; 00280 return ModRefResult(Result & AliasAnalysis::getModRefInfo(CS, P, Size)); 00281 } 00282 00283 // Compute the mapping from nodes in the callee graph to the nodes in the 00284 // caller graph for this call site. 00285 DSGraph::NodeMapTy CalleeCallerMap; 00286 DSCallSite DSCS = CallerTDGraph.getDSCallSiteForCallSite(CS); 00287 CallerTDGraph.computeCalleeCallerMapping(DSCS, *F, CalleeBUGraph, 00288 CalleeCallerMap); 00289 00290 // Remember the mapping and the call site for future queries. 00291 MapCS = CS; 00292 00293 // Invert the mapping into CalleeCallerInvMap. 00294 for (DSGraph::NodeMapTy::iterator I = CalleeCallerMap.begin(), 00295 E = CalleeCallerMap.end(); I != E; ++I) 00296 CallerCalleeMap.insert(std::make_pair(I->second.getNode(), I->first)); 00297 00298 N = NI->second.getNode(); 00299 goto HaveMappingInfo; 00300 }