| //===- TopDownClosure.cpp - Compute the top-down interprocedure closure ---===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the TDDataStructures class, which represents the |
| // Top-down Interprocedural closure of the data structure graph over the |
| // program. This is useful (but not strictly necessary?) for applications |
| // like pointer analysis. |
| // |
| //===----------------------------------------------------------------------===// |
| #define DEBUG_TYPE "td_dsa" |
| |
| #include "dsa/DataStructure.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/IR/DerivedTypes.h" |
| #include "dsa/DSGraph.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/FormattedStream.h" |
| #include "llvm/Support/Timer.h" |
| #include "llvm/ADT/Statistic.h" |
| using namespace llvm; |
| |
| #define TIME_REGION(VARNAME, DESC) |
| |
| namespace { |
| RegisterPass<TDDataStructures> // Register the pass |
| Y("dsa-td", "Top-down Data Structure Analysis"); |
| |
| RegisterPass<EQTDDataStructures> // Register the pass |
| Z("dsa-eqtd", "EQ Top-down Data Structure Analysis"); |
| |
| STATISTIC (NumTDInlines, "Number of graphs inlined"); |
| } |
| |
| char TDDataStructures::ID; |
| char EQTDDataStructures::ID; |
| |
| TDDataStructures::~TDDataStructures() { |
| releaseMemory(); |
| } |
| |
| EQTDDataStructures::~EQTDDataStructures() { |
| releaseMemory(); |
| } |
| |
| void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N, |
| DenseSet<DSNode*> &Visited) { |
| if (!N || Visited.count(N)) return; |
| Visited.insert(N); |
| |
| // Handle this node |
| { |
| N->addFullFunctionSet(ExternallyCallable); |
| } |
| |
| for (DSNode::edge_iterator ii = N->edge_begin(), |
| ee = N->edge_end(); ii != ee; ++ii) |
| if (!ii->second.isNull()) { |
| DSNodeHandle &NH = ii->second; |
| DSNode * NN = NH.getNode(); |
| NN->addFullFunctionSet(ExternallyCallable); |
| markReachableFunctionsExternallyAccessible(NN, Visited); |
| } |
| } |
| |
| |
| // run - Calculate the top down data structure graphs for each function in the |
| // program. |
| // |
| bool TDDataStructures::runOnModule(Module &M) { |
| |
| init(useEQBU ? &getAnalysis<EquivBUDataStructures>() |
| : &getAnalysis<BUDataStructures>(), |
| true, true, true, false); |
| // Figure out which functions must not mark their arguments complete because |
| // they are accessible outside this compilation unit. Currently, these |
| // arguments are functions which are reachable by incomplete or external |
| // nodes in the globals graph. |
| const DSScalarMap &GGSM = GlobalsGraph->getScalarMap(); |
| DenseSet<DSNode*> Visited; |
| for (DSScalarMap::global_iterator I=GGSM.global_begin(), E=GGSM.global_end(); |
| I != E; ++I) { |
| DSNode *N = GGSM.find(*I)->second.getNode(); |
| if (N->isIncompleteNode() || N->isExternalNode()) |
| markReachableFunctionsExternallyAccessible(N, Visited); |
| } |
| |
| // Loop over unresolved call nodes. Any functions passed into (but not |
| // returned!) from unresolvable call nodes may be invoked outside of the |
| // current module. |
| for (DSGraph::afc_iterator I = GlobalsGraph->afc_begin(), |
| E = GlobalsGraph->afc_end(); I != E; ++I) |
| for (unsigned arg = 0, e = I->getNumPtrArgs(); arg != e; ++arg) |
| markReachableFunctionsExternallyAccessible(I->getPtrArg(arg).getNode(), |
| Visited); |
| Visited.clear(); |
| |
| // Clear Aux of Globals Graph to be refilled in later by post-TD unresolved |
| // functions |
| GlobalsGraph->getAuxFunctionCalls().clear(); |
| |
| // Functions without internal linkage are definitely externally callable! |
| for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| if (!I->isDeclaration() && !I->hasInternalLinkage() && !I->hasPrivateLinkage()) |
| ExternallyCallable.insert(I); |
| |
| // Debug code to print the functions that are externally callable |
| #if 0 |
| for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| if (ExternallyCallable.count(I)) { |
| errs() << "ExternallyCallable: " << I->getNameStr() << "\n"; |
| } |
| #endif |
| |
| // We want to traverse the call graph in reverse post-order. To do this, we |
| // calculate a post-order traversal, then reverse it. |
| DenseSet<DSGraph*> VisitedGraph; |
| std::vector<DSGraph*> PostOrder; |
| |
| {TIME_REGION(XXX, "td:Compute postorder"); |
| |
| // Calculate top-down from main... |
| if (Function *F = M.getFunction("main")) |
| ComputePostOrder(*F, VisitedGraph, PostOrder); |
| |
| // Next calculate the graphs for each unreachable function... |
| for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| if (!I->isDeclaration()) |
| ComputePostOrder(*I, VisitedGraph, PostOrder); |
| |
| VisitedGraph.clear(); // Release memory! |
| } |
| |
| {TIME_REGION(XXX, "td:Inline stuff"); |
| |
| // Visit each of the graphs in reverse post-order now! |
| while (!PostOrder.empty()) { |
| InlineCallersIntoGraph(PostOrder.back()); |
| PostOrder.pop_back(); |
| } |
| } |
| |
| // Free the IndCallMap. |
| while (!IndCallMap.empty()) { |
| delete IndCallMap.begin()->second; |
| IndCallMap.erase(IndCallMap.begin()); |
| } |
| |
| formGlobalECs(); |
| |
| ExternallyCallable.clear(); |
| GlobalsGraph->removeTriviallyDeadNodes(); |
| GlobalsGraph->computeExternalFlags(DSGraph::DontMarkFormalsExternal); |
| GlobalsGraph->computeIntPtrFlags(); |
| |
| // Make sure each graph has updated external information about globals |
| // in the globals graph. |
| VisitedGraph.clear(); |
| for (Module::iterator F = M.begin(); F != M.end(); ++F) { |
| if (!(F->isDeclaration())){ |
| DSGraph *Graph = getOrCreateGraph(F); |
| if (!VisitedGraph.insert(Graph).second) continue; |
| |
| cloneGlobalsInto(Graph, DSGraph::DontCloneCallNodes | |
| DSGraph::DontCloneAuxCallNodes); |
| |
| Graph->computeExternalFlags(DSGraph::DontMarkFormalsExternal); |
| Graph->computeIntPtrFlags(); |
| // Clean up uninteresting nodes |
| Graph->removeDeadNodes(0); |
| |
| } |
| } |
| |
| // CBU contains the correct call graph. |
| // Restore it, so that subsequent passes and clients can get it. |
| restoreCorrectCallGraph(); |
| return false; |
| } |
| |
| |
| void TDDataStructures::ComputePostOrder(const Function &F, |
| DenseSet<DSGraph*> &Visited, |
| std::vector<DSGraph*> &PostOrder) { |
| if (F.isDeclaration()) return; |
| DSGraph* G = getOrCreateGraph(&F); |
| if (!Visited.insert(G).second) return; |
| |
| // Recursively traverse all of the callee graphs. |
| svset<const Function*> Callees; |
| |
| // Go through all of the callsites in this graph and find all callees |
| // Here we're trying to capture all possible callees so that we can ensure |
| // each function has all possible callers inlined into it. |
| for (DSGraph::fc_iterator CI = G->fc_begin(), E = G->fc_end(); |
| CI != E; ++CI) { |
| // Direct calls are easy, no reason to look at DSCallGraph |
| // or anything to do with SCC's |
| if (CI->isDirectCall()) { |
| ComputePostOrder(*CI->getCalleeFunc(), Visited, PostOrder); |
| } |
| else { |
| // Otherwise, ask the DSCallGraph for the full set of possible |
| // callees for this callsite. |
| // This includes all members of the SCC's of those callees, |
| // and well as others in F's SCC, since we must assume |
| // any indirect call might be intra-SCC. |
| callgraph.addFullFunctionSet(CI->getCallSite(), Callees); |
| } |
| } |
| |
| for (svset<const Function*>::iterator I = Callees.begin(), |
| E = Callees.end(); I != E; ++I) |
| ComputePostOrder(**I, Visited, PostOrder); |
| |
| PostOrder.push_back(G); |
| } |
| |
| /// InlineCallersIntoGraph - Inline all of the callers of the specified DS graph |
| /// into it, then recompute completeness of nodes in the resultant graph. |
| void TDDataStructures::InlineCallersIntoGraph(DSGraph* DSG) { |
| // Inline caller graphs into this graph. First step, get the list of call |
| // sites that call into this graph. |
| std::vector<CallerCallEdge> EdgesFromCaller; |
| std::map<DSGraph*, std::vector<CallerCallEdge> >::iterator |
| CEI = CallerEdges.find(DSG); |
| if (CEI != CallerEdges.end()) { |
| std::swap(CEI->second, EdgesFromCaller); |
| CallerEdges.erase(CEI); |
| } |
| |
| // Sort the caller sites to provide a by-caller-graph ordering. |
| std::sort(EdgesFromCaller.begin(), EdgesFromCaller.end()); |
| |
| |
| // Merge information from the globals graph into this graph. FIXME: This is |
| // stupid. Instead of us cloning information from the GG into this graph, |
| // then having RemoveDeadNodes clone it back, we should do all of this as a |
| // post-pass over all of the graphs. We need to take cloning out of |
| // removeDeadNodes and gut removeDeadNodes at the same time first though. :( |
| cloneGlobalsInto(DSG, DSGraph::DontCloneCallNodes | |
| DSGraph::DontCloneAuxCallNodes); |
| |
| DEBUG(errs() << "[TD] Inlining callers into '" |
| << DSG->getFunctionNames() << "'\n"); |
| |
| DSG->maskIncompleteMarkers(); |
| // Iteratively inline caller graphs into this graph. |
| while (!EdgesFromCaller.empty()) { |
| DSGraph* CallerGraph = EdgesFromCaller.back().CallerGraph; |
| |
| // Iterate through all of the call sites of this graph, cloning and merging |
| // any nodes required by the call. |
| ReachabilityCloner RC(DSG, CallerGraph, |
| DSGraph::DontCloneCallNodes | |
| DSGraph::DontCloneAuxCallNodes); |
| |
| // Inline all call sites from this caller graph. |
| do { |
| const DSCallSite &CS = *EdgesFromCaller.back().CS; |
| const Function &CF = *EdgesFromCaller.back().CalledFunction; |
| DEBUG(errs() << " [TD] Inlining graph into Fn '" |
| << CF.getName().str() << "' from "); |
| if (CallerGraph->getReturnNodes().empty()) { |
| DEBUG(errs() << "SYNTHESIZED INDIRECT GRAPH"); |
| } else { |
| DEBUG(errs() << "Fn '" << CS.getCallSite().getInstruction()-> |
| getParent()->getParent()->getName().str() << "'"); |
| } |
| DEBUG(errs() << ": " << CF.getFunctionType()->getNumParams() |
| << " args\n"); |
| |
| // Get the formal argument and return nodes for the called function and |
| // merge them with the cloned subgraph. |
| DSCallSite T1 = DSG->getCallSiteForArguments(CF); |
| RC.mergeCallSite(T1, CS); |
| ++NumTDInlines; |
| |
| EdgesFromCaller.pop_back(); |
| } while (!EdgesFromCaller.empty() && |
| EdgesFromCaller.back().CallerGraph == CallerGraph); |
| } |
| |
| |
| |
| // Next, now that this graph is finalized, we need to recompute the |
| // incompleteness markers for this graph and remove unreachable nodes. |
| |
| // If any of the functions is externally callable, treat everything in its |
| // SCC as externally callable. |
| bool isExternallyCallable = false; |
| for (DSGraph::retnodes_iterator I = DSG->retnodes_begin(), |
| E = DSG->retnodes_end(); I != E; ++I) |
| if (ExternallyCallable.count(I->first)) { |
| isExternallyCallable = true; |
| break; |
| } |
| |
| // Recompute the Incomplete markers. Depends on whether args are complete |
| unsigned IncFlags = DSGraph::IgnoreFormalArgs; |
| IncFlags |= DSGraph::IgnoreGlobals | DSGraph::MarkVAStart; |
| DSG->markIncompleteNodes(IncFlags); |
| |
| // If this graph contains functions that are externally callable, now is the time to mark |
| // their arguments and return values as external. At this point TD is inlining all caller information, |
| // and that means External callers too. |
| unsigned ExtFlags |
| = isExternallyCallable ? DSGraph::MarkFormalsExternal : DSGraph::DontMarkFormalsExternal; |
| DSG->computeExternalFlags(ExtFlags); |
| DSG->computeIntPtrFlags(); |
| |
| cloneIntoGlobals(DSG, DSGraph::DontCloneCallNodes | |
| DSGraph::DontCloneAuxCallNodes); |
| // |
| // Delete dead nodes. Treat globals that are unreachable as dead also. |
| // |
| // FIXME: |
| // Do not delete unreachable globals as the comment describes. For its |
| // alignment checks on the results of load instructions, SAFECode must be |
| // able to find the DSNode of both the result of the load as well as the |
| // pointer dereferenced by the load. If we remove unreachable globals, then |
| // if the dereferenced pointer is a global, its DSNode will not reachable |
| // from the local graph's scalar map, and chaos ensues. |
| // |
| // So, for now, just remove dead nodes but leave the globals alone. |
| // |
| DSG->removeDeadNodes(0); |
| |
| // We are done with computing the current TD Graph! Finally, before we can |
| // finish processing this function, we figure out which functions it calls and |
| // records these call graph edges, so that we have them when we process the |
| // callee graphs. |
| if (DSG->fc_begin() == DSG->fc_end()) return; |
| |
| // Loop over all the call sites and all the callees at each call site, and add |
| // edges to the CallerEdges structure for each callee. |
| for (DSGraph::fc_iterator CI = DSG->fc_begin(), E = DSG->fc_end(); |
| CI != E; ++CI) { |
| |
| // Handle direct calls efficiently. |
| if (CI->isDirectCall()) { |
| if (!CI->getCalleeFunc()->isDeclaration() && |
| !DSG->getReturnNodes().count(CI->getCalleeFunc())) |
| CallerEdges[getOrCreateGraph(CI->getCalleeFunc())] |
| .push_back(CallerCallEdge(DSG, &*CI, CI->getCalleeFunc())); |
| continue; |
| } |
| |
| svset<const Function*> AllCallees; |
| std::vector<const Function*> Callees; |
| |
| // Get the list of callees |
| callgraph.addFullFunctionSet(CI->getCallSite(), AllCallees); |
| |
| // Filter all non-declarations, and calls within this DSGraph |
| for (svset<const Function*>::iterator I = AllCallees.begin(), |
| E = AllCallees.end(); I != E; ++I) { |
| const Function *F = *I; |
| if (!F->isDeclaration() && getDSGraph(**I) != DSG) |
| Callees.push_back(F); |
| } |
| AllCallees.clear(); |
| |
| // If there is exactly one callee from this call site, remember the edge in |
| // CallerEdges. |
| if (Callees.size() == 1) { |
| const Function * Callee = Callees[0]; |
| CallerEdges[getOrCreateGraph(Callee)] |
| .push_back(CallerCallEdge(DSG, &*CI, Callee)); |
| } |
| if (Callees.size() <= 1) continue; |
| |
| // Otherwise, there are multiple callees from this call site, so it must be |
| // an indirect call. Chances are that there will be other call sites with |
| // this set of targets. If so, we don't want to do M*N inlining operations, |
| // so we build up a new, private, graph that represents the calls of all |
| // calls to this set of functions. |
| |
| std::map<std::vector<const Function*>, DSGraph*>::iterator IndCallRecI = |
| IndCallMap.lower_bound(Callees); |
| |
| // If we already have this graph, recycle it. |
| if (IndCallRecI != IndCallMap.end() && IndCallRecI->first == Callees) { |
| DEBUG(errs() << " [TD] *** Reuse of indcall graph for " << Callees.size() |
| << " callees!\n"); |
| DSGraph * IndCallGraph = IndCallRecI->second; |
| assert(IndCallGraph->getFunctionCalls().size() == 1); |
| |
| // Merge the call into the CS already in the IndCallGraph |
| ReachabilityCloner RC(IndCallGraph, DSG, 0); |
| RC.mergeCallSite(IndCallGraph->getFunctionCalls().front(), *CI); |
| } else { |
| // Otherwise, create a new DSGraph to represent this. |
| DSGraph* IndCallGraph = new DSGraph(DSG->getGlobalECs(), |
| DSG->getDataLayout(), *TypeSS); |
| |
| // Clone over the call into the new DSGraph |
| ReachabilityCloner RC(IndCallGraph, DSG, 0); |
| DSCallSite ClonedCS = RC.cloneCallSite(*CI); |
| |
| // Add the cloned CS to the graph, as if it were an original call. |
| IndCallGraph->getFunctionCalls().push_back(ClonedCS); |
| |
| // Save this graph for use later, should we need it. |
| IndCallRecI = IndCallMap.insert(IndCallRecI, |
| std::make_pair(Callees, IndCallGraph)); |
| |
| // Additionally, make sure that each of the callees inlines this graph |
| // exactly once. |
| DSCallSite *NCS = &IndCallGraph->getFunctionCalls().front(); |
| for (unsigned i = 0, e = Callees.size(); i != e; ++i) { |
| DSGraph* CalleeGraph = getDSGraph(*Callees[i]); |
| if (CalleeGraph != DSG) |
| CallerEdges[CalleeGraph].push_back(CallerCallEdge(IndCallGraph, NCS, |
| Callees[i])); |
| } |
| } |
| } |
| } |