LLVM API Documentation
00001 //===- Steensgaard.cpp - Context Insensitive 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 data structure graphs to implement a simple context 00011 // insensitive alias analysis. It does this by computing the local analysis 00012 // graphs for all of the functions, then merging them together into a single big 00013 // graph without cloning. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/DataStructure/DataStructure.h" 00018 #include "llvm/Analysis/DataStructure/DSGraph.h" 00019 #include "llvm/Analysis/AliasAnalysis.h" 00020 #include "llvm/Analysis/Passes.h" 00021 #include "llvm/Module.h" 00022 #include "llvm/Support/Debug.h" 00023 #include <iostream> 00024 using namespace llvm; 00025 00026 namespace { 00027 class Steens : public ModulePass, public AliasAnalysis { 00028 DSGraph *ResultGraph; 00029 00030 EquivalenceClasses<GlobalValue*> GlobalECs; // Always empty 00031 public: 00032 Steens() : ResultGraph(0) {} 00033 ~Steens() { 00034 releaseMyMemory(); 00035 assert(ResultGraph == 0 && "releaseMemory not called?"); 00036 } 00037 00038 //------------------------------------------------ 00039 // Implement the Pass API 00040 // 00041 00042 // run - Build up the result graph, representing the pointer graph for the 00043 // program. 00044 // 00045 bool runOnModule(Module &M); 00046 00047 virtual void releaseMyMemory() { delete ResultGraph; ResultGraph = 0; } 00048 00049 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00050 AliasAnalysis::getAnalysisUsage(AU); 00051 AU.setPreservesAll(); // Does not transform code... 00052 AU.addRequired<LocalDataStructures>(); // Uses local dsgraph 00053 } 00054 00055 // print - Implement the Pass::print method... 00056 void print(std::ostream &O, const Module *M) const { 00057 assert(ResultGraph && "Result graph has not yet been computed!"); 00058 ResultGraph->writeGraphToFile(O, "steensgaards"); 00059 } 00060 00061 //------------------------------------------------ 00062 // Implement the AliasAnalysis API 00063 // 00064 00065 AliasResult alias(const Value *V1, unsigned V1Size, 00066 const Value *V2, unsigned V2Size); 00067 00068 ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size); 00069 00070 private: 00071 void ResolveFunctionCall(Function *F, const DSCallSite &Call, 00072 DSNodeHandle &RetVal); 00073 }; 00074 00075 // Register the pass... 00076 RegisterOpt<Steens> X("steens-aa", 00077 "Steensgaard's alias analysis (DSGraph based)"); 00078 00079 // Register as an implementation of AliasAnalysis 00080 RegisterAnalysisGroup<AliasAnalysis, Steens> Y; 00081 } 00082 00083 ModulePass *llvm::createSteensgaardPass() { return new Steens(); } 00084 00085 /// ResolveFunctionCall - Resolve the actual arguments of a call to function F 00086 /// with the specified call site descriptor. This function links the arguments 00087 /// and the return value for the call site context-insensitively. 00088 /// 00089 void Steens::ResolveFunctionCall(Function *F, const DSCallSite &Call, 00090 DSNodeHandle &RetVal) { 00091 assert(ResultGraph != 0 && "Result graph not allocated!"); 00092 DSGraph::ScalarMapTy &ValMap = ResultGraph->getScalarMap(); 00093 00094 // Handle the return value of the function... 00095 if (Call.getRetVal().getNode() && RetVal.getNode()) 00096 RetVal.mergeWith(Call.getRetVal()); 00097 00098 // Loop over all pointer arguments, resolving them to their provided pointers 00099 unsigned PtrArgIdx = 0; 00100 for (Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 00101 AI != AE && PtrArgIdx < Call.getNumPtrArgs(); ++AI) { 00102 DSGraph::ScalarMapTy::iterator I = ValMap.find(AI); 00103 if (I != ValMap.end()) // If its a pointer argument... 00104 I->second.mergeWith(Call.getPtrArg(PtrArgIdx++)); 00105 } 00106 } 00107 00108 00109 /// run - Build up the result graph, representing the pointer graph for the 00110 /// program. 00111 /// 00112 bool Steens::runOnModule(Module &M) { 00113 InitializeAliasAnalysis(this); 00114 assert(ResultGraph == 0 && "Result graph already allocated!"); 00115 LocalDataStructures &LDS = getAnalysis<LocalDataStructures>(); 00116 00117 // Create a new, empty, graph... 00118 ResultGraph = new DSGraph(GlobalECs, getTargetData()); 00119 ResultGraph->spliceFrom(LDS.getGlobalsGraph()); 00120 00121 // Loop over the rest of the module, merging graphs for non-external functions 00122 // into this graph. 00123 // 00124 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00125 if (!I->isExternal()) 00126 ResultGraph->spliceFrom(LDS.getDSGraph(*I)); 00127 00128 ResultGraph->removeTriviallyDeadNodes(); 00129 00130 // FIXME: Must recalculate and use the Incomplete markers!! 00131 00132 // Now that we have all of the graphs inlined, we can go about eliminating 00133 // call nodes... 00134 // 00135 std::list<DSCallSite> &Calls = ResultGraph->getAuxFunctionCalls(); 00136 assert(Calls.empty() && "Aux call list is already in use??"); 00137 00138 // Start with a copy of the original call sites. 00139 Calls = ResultGraph->getFunctionCalls(); 00140 00141 for (std::list<DSCallSite>::iterator CI = Calls.begin(), E = Calls.end(); 00142 CI != E;) { 00143 DSCallSite &CurCall = *CI++; 00144 00145 // Loop over the called functions, eliminating as many as possible... 00146 std::vector<Function*> CallTargets; 00147 if (CurCall.isDirectCall()) 00148 CallTargets.push_back(CurCall.getCalleeFunc()); 00149 else 00150 CurCall.getCalleeNode()->addFullFunctionList(CallTargets); 00151 00152 for (unsigned c = 0; c != CallTargets.size(); ) { 00153 // If we can eliminate this function call, do so! 00154 Function *F = CallTargets[c]; 00155 if (!F->isExternal()) { 00156 ResolveFunctionCall(F, CurCall, ResultGraph->getReturnNodes()[F]); 00157 CallTargets[c] = CallTargets.back(); 00158 CallTargets.pop_back(); 00159 } else 00160 ++c; // Cannot eliminate this call, skip over it... 00161 } 00162 00163 if (CallTargets.empty()) { // Eliminated all calls? 00164 std::list<DSCallSite>::iterator I = CI; 00165 Calls.erase(--I); // Remove entry 00166 } 00167 } 00168 00169 // Remove our knowledge of what the return values of the functions are, except 00170 // for functions that are externally visible from this module (e.g. main). We 00171 // keep these functions so that their arguments are marked incomplete. 00172 for (DSGraph::ReturnNodesTy::iterator I = 00173 ResultGraph->getReturnNodes().begin(), 00174 E = ResultGraph->getReturnNodes().end(); I != E; ) 00175 if (I->first->hasInternalLinkage()) 00176 ResultGraph->getReturnNodes().erase(I++); 00177 else 00178 ++I; 00179 00180 // Update the "incomplete" markers on the nodes, ignoring unknownness due to 00181 // incoming arguments... 00182 ResultGraph->maskIncompleteMarkers(); 00183 ResultGraph->markIncompleteNodes(DSGraph::IgnoreGlobals | 00184 DSGraph::MarkFormalArgs); 00185 00186 // Remove any nodes that are dead after all of the merging we have done... 00187 // FIXME: We should be able to disable the globals graph for steens! 00188 //ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00189 00190 DEBUG(print(std::cerr, &M)); 00191 return false; 00192 } 00193 00194 AliasAnalysis::AliasResult Steens::alias(const Value *V1, unsigned V1Size, 00195 const Value *V2, unsigned V2Size) { 00196 assert(ResultGraph && "Result graph has not been computed yet!"); 00197 00198 DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap(); 00199 00200 DSGraph::ScalarMapTy::iterator I = GSM.find(const_cast<Value*>(V1)); 00201 DSGraph::ScalarMapTy::iterator J = GSM.find(const_cast<Value*>(V2)); 00202 if (I != GSM.end() && !I->second.isNull() && 00203 J != GSM.end() && !J->second.isNull()) { 00204 DSNodeHandle &V1H = I->second; 00205 DSNodeHandle &V2H = J->second; 00206 00207 // If at least one of the nodes is complete, we can say something about 00208 // this. If one is complete and the other isn't, then they are obviously 00209 // different nodes. If they are both complete, we can't say anything 00210 // useful. 00211 if (I->second.getNode()->isComplete() || 00212 J->second.getNode()->isComplete()) { 00213 // If the two pointers point to different data structure graph nodes, they 00214 // cannot alias! 00215 if (V1H.getNode() != V2H.getNode()) 00216 return NoAlias; 00217 00218 // See if they point to different offsets... if so, we may be able to 00219 // determine that they do not alias... 00220 unsigned O1 = I->second.getOffset(), O2 = J->second.getOffset(); 00221 if (O1 != O2) { 00222 if (O2 < O1) { // Ensure that O1 <= O2 00223 std::swap(V1, V2); 00224 std::swap(O1, O2); 00225 std::swap(V1Size, V2Size); 00226 } 00227 00228 if (O1+V1Size <= O2) 00229 return NoAlias; 00230 } 00231 } 00232 } 00233 00234 // If we cannot determine alias properties based on our graph, fall back on 00235 // some other AA implementation. 00236 // 00237 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00238 } 00239 00240 AliasAnalysis::ModRefResult 00241 Steens::getModRefInfo(CallSite CS, Value *P, unsigned Size) { 00242 AliasAnalysis::ModRefResult Result = ModRef; 00243 00244 // Find the node in question. 00245 DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap(); 00246 DSGraph::ScalarMapTy::iterator I = GSM.find(P); 00247 00248 if (I != GSM.end() && !I->second.isNull()) { 00249 DSNode *N = I->second.getNode(); 00250 if (N->isComplete()) { 00251 // If this is a direct call to an external function, and if the pointer 00252 // points to a complete node, the external function cannot modify or read 00253 // the value (we know it's not passed out of the program!). 00254 if (Function *F = CS.getCalledFunction()) 00255 if (F->isExternal()) 00256 return NoModRef; 00257 00258 // Otherwise, if the node is complete, but it is only M or R, return this. 00259 // This can be useful for globals that should be marked const but are not. 00260 if (!N->isModified()) 00261 Result = (ModRefResult)(Result & ~Mod); 00262 if (!N->isRead()) 00263 Result = (ModRefResult)(Result & ~Ref); 00264 } 00265 } 00266 00267 return (ModRefResult)(Result & AliasAnalysis::getModRefInfo(CS, P, Size)); 00268 }