LLVM API Documentation
00001 //===- CompleteBottomUp.cpp - Complete Bottom-Up Data Structure Graphs ----===// 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 is the exact same as the bottom-up graphs, but we use take a completed 00011 // call graph and inline all indirect callees into their callers graphs, making 00012 // the result more useful for things like pool allocation. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/Analysis/DataStructure/DataStructure.h" 00017 #include "llvm/Module.h" 00018 #include "llvm/Analysis/DataStructure/DSGraph.h" 00019 #include "llvm/Support/Debug.h" 00020 #include "llvm/ADT/SCCIterator.h" 00021 #include "llvm/ADT/Statistic.h" 00022 #include "llvm/ADT/STLExtras.h" 00023 using namespace llvm; 00024 00025 namespace { 00026 RegisterAnalysis<CompleteBUDataStructures> 00027 X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis"); 00028 Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined"); 00029 } 00030 00031 00032 // run - Calculate the bottom up data structure graphs for each function in the 00033 // program. 00034 // 00035 bool CompleteBUDataStructures::runOnModule(Module &M) { 00036 BUDataStructures &BU = getAnalysis<BUDataStructures>(); 00037 GlobalsGraph = new DSGraph(BU.getGlobalsGraph()); 00038 GlobalsGraph->setPrintAuxCalls(); 00039 00040 #if 1 // REMOVE ME EVENTUALLY 00041 // FIXME: TEMPORARY (remove once finalization of indirect call sites in the 00042 // globals graph has been implemented in the BU pass) 00043 TDDataStructures &TD = getAnalysis<TDDataStructures>(); 00044 00045 ActualCallees.clear(); 00046 00047 // The call graph extractable from the TD pass is _much more complete_ and 00048 // trustable than that generated by the BU pass so far. Until this is fixed, 00049 // we hack it like this: 00050 for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) { 00051 if (MI->isExternal()) continue; 00052 const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls(); 00053 00054 for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) { 00055 Instruction *TheCall = CSs[CSi].getCallSite().getInstruction(); 00056 00057 if (CSs[CSi].isIndirectCall()) { // indirect call: insert all callees 00058 const std::vector<GlobalValue*> &Callees = 00059 CSs[CSi].getCalleeNode()->getGlobals(); 00060 for (unsigned i = 0, e = Callees.size(); i != e; ++i) 00061 if (Function *F = dyn_cast<Function>(Callees[i])) 00062 ActualCallees.insert(std::make_pair(TheCall, F)); 00063 } else { // direct call: insert the single callee directly 00064 ActualCallees.insert(std::make_pair(TheCall, 00065 CSs[CSi].getCalleeFunc())); 00066 } 00067 } 00068 } 00069 #else 00070 // Our call graph is the same as the BU data structures call graph 00071 ActualCallees = BU.getActualCallees(); 00072 #endif 00073 00074 std::vector<DSGraph*> Stack; 00075 hash_map<DSGraph*, unsigned> ValMap; 00076 unsigned NextID = 1; 00077 00078 if (Function *Main = M.getMainFunction()) { 00079 if (!Main->isExternal()) 00080 calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap); 00081 } else { 00082 std::cerr << "CBU-DSA: No 'main' function found!\n"; 00083 } 00084 00085 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00086 if (!I->isExternal() && !DSInfo.count(I)) 00087 calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap); 00088 00089 GlobalsGraph->removeTriviallyDeadNodes(); 00090 return false; 00091 } 00092 00093 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) { 00094 // Has the graph already been created? 00095 DSGraph *&Graph = DSInfo[&F]; 00096 if (Graph) return *Graph; 00097 00098 // Copy the BU graph... 00099 Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F)); 00100 Graph->setGlobalsGraph(GlobalsGraph); 00101 Graph->setPrintAuxCalls(); 00102 00103 // Make sure to update the DSInfo map for all of the functions currently in 00104 // this graph! 00105 for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin(); 00106 I != Graph->getReturnNodes().end(); ++I) 00107 DSInfo[I->first] = Graph; 00108 00109 return *Graph; 00110 } 00111 00112 00113 00114 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG, 00115 std::vector<DSGraph*> &Stack, 00116 unsigned &NextID, 00117 hash_map<DSGraph*, unsigned> &ValMap) { 00118 assert(!ValMap.count(&FG) && "Shouldn't revisit functions!"); 00119 unsigned Min = NextID++, MyID = Min; 00120 ValMap[&FG] = Min; 00121 Stack.push_back(&FG); 00122 00123 // The edges out of the current node are the call site targets... 00124 for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) { 00125 Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction(); 00126 00127 // Loop over all of the actually called functions... 00128 ActualCalleesTy::iterator I, E; 00129 for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I) 00130 if (!I->second->isExternal()) { 00131 DSGraph &Callee = getOrCreateGraph(*I->second); 00132 unsigned M; 00133 // Have we visited the destination function yet? 00134 hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee); 00135 if (It == ValMap.end()) // No, visit it now. 00136 M = calculateSCCGraphs(Callee, Stack, NextID, ValMap); 00137 else // Yes, get it's number. 00138 M = It->second; 00139 if (M < Min) Min = M; 00140 } 00141 } 00142 00143 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!"); 00144 if (Min != MyID) 00145 return Min; // This is part of a larger SCC! 00146 00147 // If this is a new SCC, process it now. 00148 bool IsMultiNodeSCC = false; 00149 while (Stack.back() != &FG) { 00150 DSGraph *NG = Stack.back(); 00151 ValMap[NG] = ~0U; 00152 00153 DSGraph::NodeMapTy NodeMap; 00154 FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap); 00155 00156 // Update the DSInfo map and delete the old graph... 00157 for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin(); 00158 I != NG->getReturnNodes().end(); ++I) 00159 DSInfo[I->first] = &FG; 00160 00161 // Remove NG from the ValMap since the pointer may get recycled. 00162 ValMap.erase(NG); 00163 delete NG; 00164 00165 Stack.pop_back(); 00166 IsMultiNodeSCC = true; 00167 } 00168 00169 // Clean up the graph before we start inlining a bunch again... 00170 if (IsMultiNodeSCC) 00171 FG.removeTriviallyDeadNodes(); 00172 00173 Stack.pop_back(); 00174 processGraph(FG); 00175 ValMap[&FG] = ~0U; 00176 return MyID; 00177 } 00178 00179 00180 /// processGraph - Process the BU graphs for the program in bottom-up order on 00181 /// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs. 00182 void CompleteBUDataStructures::processGraph(DSGraph &G) { 00183 hash_set<Instruction*> calls; 00184 00185 // The edges out of the current node are the call site targets... 00186 for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) { 00187 const DSCallSite &CS = G.getFunctionCalls()[i]; 00188 Instruction *TheCall = CS.getCallSite().getInstruction(); 00189 00190 assert(calls.insert(TheCall).second && 00191 "Call instruction occurs multiple times in graph??"); 00192 00193 00194 // Loop over all of the potentially called functions... 00195 // Inline direct calls as well as indirect calls because the direct 00196 // callee may have indirect callees and so may have changed. 00197 // 00198 ActualCalleesTy::iterator I, E; 00199 tie(I, E) = ActualCallees.equal_range(TheCall); 00200 unsigned TNum = 0, Num = std::distance(I, E); 00201 for (; I != E; ++I, ++TNum) { 00202 Function *CalleeFunc = I->second; 00203 if (!CalleeFunc->isExternal()) { 00204 // Merge the callee's graph into this graph. This works for normal 00205 // calls or for self recursion within an SCC. 00206 DSGraph &GI = getOrCreateGraph(*CalleeFunc); 00207 ++NumCBUInlines; 00208 G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits | 00209 DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes | 00210 DSGraph::DontCloneAuxCallNodes); 00211 DEBUG(std::cerr << " Inlining graph [" << i << "/" << e-1 00212 << ":" << TNum << "/" << Num-1 << "] for " 00213 << CalleeFunc->getName() << "[" 00214 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size() 00215 << "] into '" /*<< G.getFunctionNames()*/ << "' [" 00216 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() 00217 << "]\n"); 00218 } 00219 } 00220 } 00221 00222 // Recompute the Incomplete markers 00223 assert(G.getInlinedGlobals().empty()); 00224 G.maskIncompleteMarkers(); 00225 G.markIncompleteNodes(DSGraph::MarkFormalArgs); 00226 00227 // Delete dead nodes. Treat globals that are unreachable but that can 00228 // reach live nodes as live. 00229 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00230 }