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 #define DEBUG_TYPE "cbudatastructure" 00017 #include "llvm/Analysis/DataStructure/DataStructure.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/Analysis/DataStructure/DSGraph.h" 00020 #include "llvm/Support/Debug.h" 00021 #include "llvm/ADT/SCCIterator.h" 00022 #include "llvm/ADT/Statistic.h" 00023 #include "llvm/ADT/STLExtras.h" 00024 #include <iostream> 00025 using namespace llvm; 00026 00027 namespace { 00028 RegisterAnalysis<CompleteBUDataStructures> 00029 X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis"); 00030 Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined"); 00031 } 00032 00033 00034 // run - Calculate the bottom up data structure graphs for each function in the 00035 // program. 00036 // 00037 bool CompleteBUDataStructures::runOnModule(Module &M) { 00038 BUDataStructures &BU = getAnalysis<BUDataStructures>(); 00039 GlobalECs = BU.getGlobalECs(); 00040 GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs); 00041 GlobalsGraph->setPrintAuxCalls(); 00042 00043 // Our call graph is the same as the BU data structures call graph 00044 ActualCallees = BU.getActualCallees(); 00045 00046 std::vector<DSGraph*> Stack; 00047 hash_map<DSGraph*, unsigned> ValMap; 00048 unsigned NextID = 1; 00049 00050 Function *MainFunc = M.getMainFunction(); 00051 if (MainFunc) { 00052 if (!MainFunc->isExternal()) 00053 calculateSCCGraphs(getOrCreateGraph(*MainFunc), Stack, NextID, ValMap); 00054 } else { 00055 std::cerr << "CBU-DSA: No 'main' function found!\n"; 00056 } 00057 00058 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 00059 if (!I->isExternal() && !DSInfo.count(I)) { 00060 #ifndef NDEBUG 00061 if (MainFunc) 00062 std::cerr << "*** CBU: Function unreachable from main: " 00063 << I->getName() << "\n"; 00064 #endif 00065 calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap); 00066 } 00067 00068 GlobalsGraph->removeTriviallyDeadNodes(); 00069 00070 00071 // Merge the globals variables (not the calls) from the globals graph back 00072 // into the main function's graph so that the main function contains all of 00073 // the information about global pools and GV usage in the program. 00074 if (MainFunc && !MainFunc->isExternal()) { 00075 DSGraph &MainGraph = getOrCreateGraph(*MainFunc); 00076 const DSGraph &GG = *MainGraph.getGlobalsGraph(); 00077 ReachabilityCloner RC(MainGraph, GG, 00078 DSGraph::DontCloneCallNodes | 00079 DSGraph::DontCloneAuxCallNodes); 00080 00081 // Clone the global nodes into this graph. 00082 for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(), 00083 E = GG.getScalarMap().global_end(); I != E; ++I) 00084 if (isa<GlobalVariable>(*I)) 00085 RC.getClonedNH(GG.getNodeForValue(*I)); 00086 00087 MainGraph.maskIncompleteMarkers(); 00088 MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs | 00089 DSGraph::IgnoreGlobals); 00090 } 00091 00092 return false; 00093 } 00094 00095 DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) { 00096 // Has the graph already been created? 00097 DSGraph *&Graph = DSInfo[&F]; 00098 if (Graph) return *Graph; 00099 00100 // Copy the BU graph... 00101 Graph = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs); 00102 Graph->setGlobalsGraph(GlobalsGraph); 00103 Graph->setPrintAuxCalls(); 00104 00105 // Make sure to update the DSInfo map for all of the functions currently in 00106 // this graph! 00107 for (DSGraph::retnodes_iterator I = Graph->retnodes_begin(); 00108 I != Graph->retnodes_end(); ++I) 00109 DSInfo[I->first] = Graph; 00110 00111 return *Graph; 00112 } 00113 00114 00115 00116 unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG, 00117 std::vector<DSGraph*> &Stack, 00118 unsigned &NextID, 00119 hash_map<DSGraph*, unsigned> &ValMap) { 00120 assert(!ValMap.count(&FG) && "Shouldn't revisit functions!"); 00121 unsigned Min = NextID++, MyID = Min; 00122 ValMap[&FG] = Min; 00123 Stack.push_back(&FG); 00124 00125 // The edges out of the current node are the call site targets... 00126 for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end(); 00127 CI != CE; ++CI) { 00128 Instruction *Call = CI->getCallSite().getInstruction(); 00129 00130 // Loop over all of the actually called functions... 00131 callee_iterator I = callee_begin(Call), E = callee_end(Call); 00132 for (; I != E && I->first == Call; ++I) { 00133 assert(I->first == Call && "Bad callee construction!"); 00134 if (!I->second->isExternal()) { 00135 DSGraph &Callee = getOrCreateGraph(*I->second); 00136 unsigned M; 00137 // Have we visited the destination function yet? 00138 hash_map<DSGraph*, unsigned>::iterator It = ValMap.find(&Callee); 00139 if (It == ValMap.end()) // No, visit it now. 00140 M = calculateSCCGraphs(Callee, Stack, NextID, ValMap); 00141 else // Yes, get it's number. 00142 M = It->second; 00143 if (M < Min) Min = M; 00144 } 00145 } 00146 } 00147 00148 assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!"); 00149 if (Min != MyID) 00150 return Min; // This is part of a larger SCC! 00151 00152 // If this is a new SCC, process it now. 00153 bool IsMultiNodeSCC = false; 00154 while (Stack.back() != &FG) { 00155 DSGraph *NG = Stack.back(); 00156 ValMap[NG] = ~0U; 00157 00158 FG.cloneInto(*NG); 00159 00160 // Update the DSInfo map and delete the old graph... 00161 for (DSGraph::retnodes_iterator I = NG->retnodes_begin(); 00162 I != NG->retnodes_end(); ++I) 00163 DSInfo[I->first] = &FG; 00164 00165 // Remove NG from the ValMap since the pointer may get recycled. 00166 ValMap.erase(NG); 00167 delete NG; 00168 00169 Stack.pop_back(); 00170 IsMultiNodeSCC = true; 00171 } 00172 00173 // Clean up the graph before we start inlining a bunch again... 00174 if (IsMultiNodeSCC) 00175 FG.removeTriviallyDeadNodes(); 00176 00177 Stack.pop_back(); 00178 processGraph(FG); 00179 ValMap[&FG] = ~0U; 00180 return MyID; 00181 } 00182 00183 00184 /// processGraph - Process the BU graphs for the program in bottom-up order on 00185 /// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs. 00186 void CompleteBUDataStructures::processGraph(DSGraph &G) { 00187 hash_set<Instruction*> calls; 00188 00189 // The edges out of the current node are the call site targets... 00190 unsigned i = 0; 00191 for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE; 00192 ++CI, ++i) { 00193 const DSCallSite &CS = *CI; 00194 Instruction *TheCall = CS.getCallSite().getInstruction(); 00195 00196 assert(calls.insert(TheCall).second && 00197 "Call instruction occurs multiple times in graph??"); 00198 00199 // Fast path for noop calls. Note that we don't care about merging globals 00200 // in the callee with nodes in the caller here. 00201 if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0) 00202 continue; 00203 00204 // Loop over all of the potentially called functions... 00205 // Inline direct calls as well as indirect calls because the direct 00206 // callee may have indirect callees and so may have changed. 00207 // 00208 callee_iterator I = callee_begin(TheCall),E = callee_end(TheCall); 00209 unsigned TNum = 0, Num = 0; 00210 DEBUG(Num = std::distance(I, E)); 00211 for (; I != E; ++I, ++TNum) { 00212 assert(I->first == TheCall && "Bad callee construction!"); 00213 Function *CalleeFunc = I->second; 00214 if (!CalleeFunc->isExternal()) { 00215 // Merge the callee's graph into this graph. This works for normal 00216 // calls or for self recursion within an SCC. 00217 DSGraph &GI = getOrCreateGraph(*CalleeFunc); 00218 ++NumCBUInlines; 00219 G.mergeInGraph(CS, *CalleeFunc, GI, 00220 DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes | 00221 DSGraph::DontCloneAuxCallNodes); 00222 DEBUG(std::cerr << " Inlining graph [" << i << "/" 00223 << G.getFunctionCalls().size()-1 00224 << ":" << TNum << "/" << Num-1 << "] for " 00225 << CalleeFunc->getName() << "[" 00226 << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size() 00227 << "] into '" /*<< G.getFunctionNames()*/ << "' [" 00228 << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() 00229 << "]\n"); 00230 } 00231 } 00232 } 00233 00234 // Recompute the Incomplete markers 00235 G.maskIncompleteMarkers(); 00236 G.markIncompleteNodes(DSGraph::MarkFormalArgs); 00237 00238 // Delete dead nodes. Treat globals that are unreachable but that can 00239 // reach live nodes as live. 00240 G.removeDeadNodes(DSGraph::KeepUnreachableGlobals); 00241 }