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/Module.h" 00021 #include "llvm/Support/Debug.h" 00022 using namespace llvm; 00023 00024 namespace { 00025 class Steens : public ModulePass, public AliasAnalysis { 00026 DSGraph *ResultGraph; 00027 DSGraph *GlobalsGraph; // FIXME: Eliminate globals graph stuff from DNE 00028 public: 00029 Steens() : ResultGraph(0), GlobalsGraph(0) {} 00030 ~Steens() { 00031 releaseMyMemory(); 00032 assert(ResultGraph == 0 && "releaseMemory not called?"); 00033 } 00034 00035 //------------------------------------------------ 00036 // Implement the Pass API 00037 // 00038 00039 // run - Build up the result graph, representing the pointer graph for the 00040 // program. 00041 // 00042 bool runOnModule(Module &M); 00043 00044 virtual void releaseMyMemory() { delete ResultGraph; ResultGraph = 0; } 00045 00046 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00047 AliasAnalysis::getAnalysisUsage(AU); 00048 AU.setPreservesAll(); // Does not transform code... 00049 AU.addRequired<LocalDataStructures>(); // Uses local dsgraph 00050 } 00051 00052 // print - Implement the Pass::print method... 00053 void print(std::ostream &O, const Module *M) const { 00054 assert(ResultGraph && "Result graph has not yet been computed!"); 00055 ResultGraph->writeGraphToFile(O, "steensgaards"); 00056 } 00057 00058 //------------------------------------------------ 00059 // Implement the AliasAnalysis API 00060 // 00061 00062 // alias - This is the only method here that does anything interesting... 00063 AliasResult alias(const Value *V1, unsigned V1Size, 00064 const Value *V2, unsigned V2Size); 00065 00066 private: 00067 void ResolveFunctionCall(Function *F, const DSCallSite &Call, 00068 DSNodeHandle &RetVal); 00069 }; 00070 00071 // Register the pass... 00072 RegisterOpt<Steens> X("steens-aa", 00073 "Steensgaard's alias analysis (DSGraph based)"); 00074 00075 // Register as an implementation of AliasAnalysis 00076 RegisterAnalysisGroup<AliasAnalysis, Steens> Y; 00077 } 00078 00079 /// ResolveFunctionCall - Resolve the actual arguments of a call to function F 00080 /// with the specified call site descriptor. This function links the arguments 00081 /// and the return value for the call site context-insensitively. 00082 /// 00083 void Steens::ResolveFunctionCall(Function *F, const DSCallSite &Call, 00084 DSNodeHandle &RetVal) { 00085 assert(ResultGraph != 0 && "Result graph not allocated!"); 00086 DSGraph::ScalarMapTy &ValMap = ResultGraph->getScalarMap(); 00087 00088 // Handle the return value of the function... 00089 if (Call.getRetVal().getNode() && RetVal.getNode()) 00090 RetVal.mergeWith(Call.getRetVal()); 00091 00092 // Loop over all pointer arguments, resolving them to their provided pointers 00093 unsigned PtrArgIdx = 0; 00094 for (Function::aiterator AI = F->abegin(), AE = F->aend(); 00095 AI != AE && PtrArgIdx < Call.getNumPtrArgs(); ++AI) { 00096 DSGraph::ScalarMapTy::iterator I = ValMap.find(AI); 00097 if (I != ValMap.end()) // If its a pointer argument... 00098 I->second.mergeWith(Call.getPtrArg(PtrArgIdx++)); 00099 } 00100 } 00101 00102 00103 /// run - Build up the result graph, representing the pointer graph for the 00104 /// program. 00105 /// 00106 bool Steens::runOnModule(Module &M) { 00107 InitializeAliasAnalysis(this); 00108 assert(ResultGraph == 0 && "Result graph already allocated!"); 00109 LocalDataStructures &LDS = getAnalysis<LocalDataStructures>(); 00110 00111 // Create a new, empty, graph... 00112 ResultGraph = new DSGraph(getTargetData()); 00113 GlobalsGraph = new DSGraph(getTargetData()); 00114 ResultGraph->setGlobalsGraph(GlobalsGraph); 00115 ResultGraph->setPrintAuxCalls(); 00116 00117 // RetValMap - Keep track of the return values for all functions that return 00118 // valid pointers. 00119 // 00120 DSGraph::ReturnNodesTy RetValMap; 00121 00122 // Loop over the rest of the module, merging graphs for non-external functions 00123 // into this graph. 00124 // 00125 unsigned Count = 0; 00126 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00127 if (!I->isExternal()) { 00128 DSGraph::ScalarMapTy ValMap; 00129 { // Scope to free NodeMap memory ASAP 00130 DSGraph::NodeMapTy NodeMap; 00131 const DSGraph &FDSG = LDS.getDSGraph(*I); 00132 ResultGraph->cloneInto(FDSG, ValMap, RetValMap, NodeMap, 00133 DSGraph::UpdateInlinedGlobals); 00134 } 00135 00136 // Incorporate the inlined Function's ScalarMap into the global 00137 // ScalarMap... 00138 DSGraph::ScalarMapTy &GVM = ResultGraph->getScalarMap(); 00139 for (DSGraph::ScalarMapTy::iterator I = ValMap.begin(), 00140 E = ValMap.end(); I != E; ++I) 00141 GVM[I->first].mergeWith(I->second); 00142 00143 if ((++Count & 1) == 0) // Prune nodes out every other time... 00144 ResultGraph->removeTriviallyDeadNodes(); 00145 } 00146 00147 // FIXME: Must recalculate and use the Incomplete markers!! 00148 00149 // Now that we have all of the graphs inlined, we can go about eliminating 00150 // call nodes... 00151 // 00152 std::vector<DSCallSite> &Calls = 00153 ResultGraph->getAuxFunctionCalls(); 00154 assert(Calls.empty() && "Aux call list is already in use??"); 00155 00156 // Start with a copy of the original call sites... 00157 Calls = ResultGraph->getFunctionCalls(); 00158 00159 for (unsigned i = 0; i != Calls.size(); ) { 00160 DSCallSite &CurCall = Calls[i]; 00161 00162 // Loop over the called functions, eliminating as many as possible... 00163 std::vector<GlobalValue*> CallTargets; 00164 if (CurCall.isDirectCall()) 00165 CallTargets.push_back(CurCall.getCalleeFunc()); 00166 else 00167 CallTargets = CurCall.getCalleeNode()->getGlobals(); 00168 00169 for (unsigned c = 0; c != CallTargets.size(); ) { 00170 // If we can eliminate this function call, do so! 00171 bool Eliminated = false; 00172 if (Function *F = dyn_cast<Function>(CallTargets[c])) 00173 if (!F->isExternal()) { 00174 ResolveFunctionCall(F, CurCall, RetValMap[F]); 00175 Eliminated = true; 00176 } 00177 if (Eliminated) { 00178 CallTargets[c] = CallTargets.back(); 00179 CallTargets.pop_back(); 00180 } else 00181 ++c; // Cannot eliminate this call, skip over it... 00182 } 00183 00184 if (CallTargets.empty()) { // Eliminated all calls? 00185 CurCall = Calls.back(); // Remove entry 00186 Calls.pop_back(); 00187 } else 00188 ++i; // Skip this call site... 00189 } 00190 00191 RetValMap.clear(); 00192 00193 // Update the "incomplete" markers on the nodes, ignoring unknownness due to 00194 // incoming arguments... 00195 ResultGraph->maskIncompleteMarkers(); 00196 ResultGraph->markIncompleteNodes(DSGraph::IgnoreFormalArgs); 00197 00198 // Remove any nodes that are dead after all of the merging we have done... 00199 // FIXME: We should be able to disable the globals graph for steens! 00200 ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00201 00202 DEBUG(print(std::cerr, &M)); 00203 return false; 00204 } 00205 00206 // alias - This is the only method here that does anything interesting... 00207 AliasAnalysis::AliasResult Steens::alias(const Value *V1, unsigned V1Size, 00208 const Value *V2, unsigned V2Size) { 00209 // FIXME: HANDLE Size argument! 00210 assert(ResultGraph && "Result graph has not been computed yet!"); 00211 00212 DSGraph::ScalarMapTy &GSM = ResultGraph->getScalarMap(); 00213 00214 DSGraph::ScalarMapTy::iterator I = GSM.find(const_cast<Value*>(V1)); 00215 if (I != GSM.end() && I->second.getNode()) { 00216 DSNodeHandle &V1H = I->second; 00217 DSGraph::ScalarMapTy::iterator J=GSM.find(const_cast<Value*>(V2)); 00218 if (J != GSM.end() && J->second.getNode()) { 00219 DSNodeHandle &V2H = J->second; 00220 // If the two pointers point to different data structure graph nodes, they 00221 // cannot alias! 00222 if (V1H.getNode() != V2H.getNode()) // FIXME: Handle incompleteness! 00223 return NoAlias; 00224 00225 // FIXME: If the two pointers point to the same node, and the offsets are 00226 // different, and the LinkIndex vector doesn't alias the section, then the 00227 // two pointers do not alias. We need access size information for the two 00228 // accesses though! 00229 // 00230 } 00231 } 00232 00233 // If we cannot determine alias properties based on our graph, fall back on 00234 // some other AA implementation. 00235 // 00236 return AliasAnalysis::alias(V1, V1Size, V2, V2Size); 00237 }