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