diff options
Diffstat (limited to 'lib/Analysis/DataStructure/TopDownClosure.cpp')
| -rw-r--r-- | lib/Analysis/DataStructure/TopDownClosure.cpp | 470 |
1 files changed, 470 insertions, 0 deletions
diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp new file mode 100644 index 0000000000..c1a6cb85ef --- /dev/null +++ b/lib/Analysis/DataStructure/TopDownClosure.cpp @@ -0,0 +1,470 @@ +//===- 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. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/DataStructure/DataStructure.h" +#include "llvm/Module.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Analysis/DataStructure/DSGraph.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Timer.h" +#include "llvm/ADT/Statistic.h" +using namespace llvm; + +#if 0 +#define TIME_REGION(VARNAME, DESC) \ + NamedRegionTimer VARNAME(DESC) +#else +#define TIME_REGION(VARNAME, DESC) +#endif + +namespace { + RegisterAnalysis<TDDataStructures> // Register the pass + Y("tddatastructure", "Top-down Data Structure Analysis"); + + Statistic<> NumTDInlines("tddatastructures", "Number of graphs inlined"); +} + +void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N, + hash_set<DSNode*> &Visited) { + if (!N || Visited.count(N)) return; + Visited.insert(N); + + for (unsigned i = 0, e = N->getNumLinks(); i != e; ++i) { + DSNodeHandle &NH = N->getLink(i*N->getPointerSize()); + if (DSNode *NN = NH.getNode()) { + std::vector<Function*> Functions; + NN->addFullFunctionList(Functions); + ArgsRemainIncomplete.insert(Functions.begin(), Functions.end()); + markReachableFunctionsExternallyAccessible(NN, Visited); + } + } +} + + +// run - Calculate the top down data structure graphs for each function in the +// program. +// +bool TDDataStructures::runOnModule(Module &M) { + BUInfo = &getAnalysis<BUDataStructures>(); + GlobalECs = BUInfo->getGlobalECs(); + GlobalsGraph = new DSGraph(BUInfo->getGlobalsGraph(), GlobalECs); + GlobalsGraph->setPrintAuxCalls(); + + // 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 global variables in the + // globals graph. + const DSScalarMap &GGSM = GlobalsGraph->getScalarMap(); + hash_set<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->isIncomplete()) + 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(); + + // Functions without internal linkage also have unknown incoming arguments! + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + if (!I->isExternal() && !I->hasInternalLinkage()) + ArgsRemainIncomplete.insert(I); + + // We want to traverse the call graph in reverse post-order. To do this, we + // calculate a post-order traversal, then reverse it. + hash_set<DSGraph*> VisitedGraph; + std::vector<DSGraph*> PostOrder; + +#if 0 +{TIME_REGION(XXX, "td:Copy graphs"); + + // Visit each of the graphs in reverse post-order now! + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + if (!I->isExternal()) + getOrCreateDSGraph(*I); + return false; +} +#endif + + +{TIME_REGION(XXX, "td:Compute postorder"); + + // Calculate top-down from main... + if (Function *F = M.getMainFunction()) + ComputePostOrder(*F, VisitedGraph, PostOrder); + + // Next calculate the graphs for each unreachable function... + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) + 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()); + } + + + ArgsRemainIncomplete.clear(); + GlobalsGraph->removeTriviallyDeadNodes(); + + return false; +} + + +DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) { + DSGraph *&G = DSInfo[&F]; + if (G == 0) { // Not created yet? Clone BU graph... + G = new DSGraph(getAnalysis<BUDataStructures>().getDSGraph(F), GlobalECs, + DSGraph::DontCloneAuxCallNodes); + assert(G->getAuxFunctionCalls().empty() && "Cloned aux calls?"); + G->setPrintAuxCalls(); + G->setGlobalsGraph(GlobalsGraph); + + // Note that this graph is the graph for ALL of the function in the SCC, not + // just F. + for (DSGraph::retnodes_iterator RI = G->retnodes_begin(), + E = G->retnodes_end(); RI != E; ++RI) + if (RI->first != &F) + DSInfo[RI->first] = G; + } + return *G; +} + + +void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited, + std::vector<DSGraph*> &PostOrder) { + if (F.isExternal()) return; + DSGraph &G = getOrCreateDSGraph(F); + if (Visited.count(&G)) return; + Visited.insert(&G); + + // Recursively traverse all of the callee graphs. + for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE; ++CI){ + Instruction *CallI = CI->getCallSite().getInstruction(); + for (BUDataStructures::callee_iterator I = BUInfo->callee_begin(CallI), + E = BUInfo->callee_end(CallI); I != E; ++I) + ComputePostOrder(*I->second, Visited, PostOrder); + } + + PostOrder.push_back(&G); +} + + + + + +// releaseMemory - If the pass pipeline is done with this pass, we can release +// our memory... here... +// +// FIXME: This should be releaseMemory and will work fine, except that LoadVN +// has no way to extend the lifetime of the pass, which screws up ds-aa. +// +void TDDataStructures::releaseMyMemory() { + for (hash_map<Function*, DSGraph*>::iterator I = DSInfo.begin(), + E = DSInfo.end(); I != E; ++I) { + I->second->getReturnNodes().erase(I->first); + if (I->second->getReturnNodes().empty()) + delete I->second; + } + + // Empty map so next time memory is released, data structures are not + // re-deleted. + DSInfo.clear(); + delete GlobalsGraph; + GlobalsGraph = 0; +} + +/// 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. :( + { + DSGraph &GG = *DSG.getGlobalsGraph(); + ReachabilityCloner RC(DSG, GG, + DSGraph::DontCloneCallNodes | + DSGraph::DontCloneAuxCallNodes); + for (DSScalarMap::global_iterator + GI = DSG.getScalarMap().global_begin(), + E = DSG.getScalarMap().global_end(); GI != E; ++GI) + RC.getClonedNH(GG.getNodeForValue(*GI)); + } + + DEBUG(std::cerr << "[TD] Inlining callers into '" << DSG.getFunctionNames() + << "'\n"); + + // 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; + Function &CF = *EdgesFromCaller.back().CalledFunction; + DEBUG(std::cerr << " [TD] Inlining graph into Fn '" + << CF.getName() << "' from "); + if (CallerGraph.getReturnNodes().empty()) + DEBUG(std::cerr << "SYNTHESIZED INDIRECT GRAPH"); + else + DEBUG (std::cerr << "Fn '" + << CS.getCallSite().getInstruction()-> + getParent()->getParent()->getName() << "'"); + DEBUG(std::cerr << ": " << 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. + DSG.maskIncompleteMarkers(); + + // If any of the functions has incomplete incoming arguments, don't mark any + // of them as complete. + bool HasIncompleteArgs = false; + for (DSGraph::retnodes_iterator I = DSG.retnodes_begin(), + E = DSG.retnodes_end(); I != E; ++I) + if (ArgsRemainIncomplete.count(I->first)) { + HasIncompleteArgs = true; + break; + } + + // Recompute the Incomplete markers. Depends on whether args are complete + unsigned Flags + = HasIncompleteArgs ? DSGraph::MarkFormalArgs : DSGraph::IgnoreFormalArgs; + DSG.markIncompleteNodes(Flags | DSGraph::IgnoreGlobals); + + // Delete dead nodes. Treat globals that are unreachable as dead also. + DSG.removeDeadNodes(DSGraph::RemoveUnreachableGlobals); + + // 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()->isExternal() && + !DSG.getReturnNodes().count(CI->getCalleeFunc())) + CallerEdges[&getDSGraph(*CI->getCalleeFunc())] + .push_back(CallerCallEdge(&DSG, &*CI, CI->getCalleeFunc())); + continue; + } + + Instruction *CallI = CI->getCallSite().getInstruction(); + // For each function in the invoked function list at this call site... + BUDataStructures::callee_iterator IPI = + BUInfo->callee_begin(CallI), IPE = BUInfo->callee_end(CallI); + + // Skip over all calls to this graph (SCC calls). + while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG) + ++IPI; + + // All SCC calls? + if (IPI == IPE) continue; + + Function *FirstCallee = IPI->second; + ++IPI; + + // Skip over more SCC calls. + while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG) + ++IPI; + + // If there is exactly one callee from this call site, remember the edge in + // CallerEdges. + if (IPI == IPE) { + if (!FirstCallee->isExternal()) + CallerEdges[&getDSGraph(*FirstCallee)] + .push_back(CallerCallEdge(&DSG, &*CI, FirstCallee)); + 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::vector<Function*> Callees; + for (BUDataStructures::ActualCalleesTy::const_iterator I = + BUInfo->callee_begin(CallI), E = BUInfo->callee_end(CallI); + I != E; ++I) + if (!I->second->isExternal()) + Callees.push_back(I->second); + std::sort(Callees.begin(), Callees.end()); + + std::map<std::vector<Function*>, DSGraph*>::iterator IndCallRecI = + IndCallMap.lower_bound(Callees); + + DSGraph *IndCallGraph; + + // If we already have this graph, recycle it. + if (IndCallRecI != IndCallMap.end() && IndCallRecI->first == Callees) { + std::cerr << " [TD] *** Reuse of indcall graph for " << Callees.size() + << " callees!\n"; + IndCallGraph = IndCallRecI->second; + } else { + // Otherwise, create a new DSGraph to represent this. + IndCallGraph = new DSGraph(DSG.getGlobalECs(), DSG.getTargetData()); + + // Make a nullary dummy call site, which will eventually get some content + // merged into it. The actual callee function doesn't matter here, so we + // just pass it something to keep the ctor happy. + std::vector<DSNodeHandle> ArgDummyVec; + DSCallSite DummyCS(CI->getCallSite(), DSNodeHandle(), Callees[0]/*dummy*/, + ArgDummyVec); + IndCallGraph->getFunctionCalls().push_back(DummyCS); + + 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])); + } + } + + // Now that we know which graph to use for this, merge the caller + // information into the graph, based on information from the call site. + ReachabilityCloner RC(*IndCallGraph, DSG, 0); + RC.mergeCallSite(IndCallGraph->getFunctionCalls().front(), *CI); + } +} + + +static const Function *getFnForValue(const Value *V) { + if (const Instruction *I = dyn_cast<Instruction>(V)) + return I->getParent()->getParent(); + else if (const Argument *A = dyn_cast<Argument>(V)) + return A->getParent(); + else if (const BasicBlock *BB = dyn_cast<BasicBlock>(V)) + return BB->getParent(); + return 0; +} + +void TDDataStructures::deleteValue(Value *V) { + if (const Function *F = getFnForValue(V)) { // Function local value? + // If this is a function local value, just delete it from the scalar map! + getDSGraph(*F).getScalarMap().eraseIfExists(V); + return; + } + + if (Function *F = dyn_cast<Function>(V)) { + assert(getDSGraph(*F).getReturnNodes().size() == 1 && + "cannot handle scc's"); + delete DSInfo[F]; + DSInfo.erase(F); + return; + } + + assert(!isa<GlobalVariable>(V) && "Do not know how to delete GV's yet!"); +} + +void TDDataStructures::copyValue(Value *From, Value *To) { + if (From == To) return; + if (const Function *F = getFnForValue(From)) { // Function local value? + // If this is a function local value, just delete it from the scalar map! + getDSGraph(*F).getScalarMap().copyScalarIfExists(From, To); + return; + } + + if (Function *FromF = dyn_cast<Function>(From)) { + Function *ToF = cast<Function>(To); + assert(!DSInfo.count(ToF) && "New Function already exists!"); + DSGraph *NG = new DSGraph(getDSGraph(*FromF), GlobalECs); + DSInfo[ToF] = NG; + assert(NG->getReturnNodes().size() == 1 && "Cannot copy SCC's yet!"); + + // Change the Function* is the returnnodes map to the ToF. + DSNodeHandle Ret = NG->retnodes_begin()->second; + NG->getReturnNodes().clear(); + NG->getReturnNodes()[ToF] = Ret; + return; + } + + if (const Function *F = getFnForValue(To)) { + DSGraph &G = getDSGraph(*F); + G.getScalarMap().copyScalarIfExists(From, To); + return; + } + + std::cerr << *From; + std::cerr << *To; + assert(0 && "Do not know how to copy this yet!"); + abort(); +} |