X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDataStructure%2FCompleteBottomUp.cpp;h=b2a0f4ba9b8e355c883e8b6d6a75f2eda0e73811;hb=551ccae044b0ff658fe629dd67edd5ffe75d10e8;hp=751d5b0ff2b362a01b741733bd65ef8a3a652832;hpb=95724a4aecc8f94e7f5ce2a65fbcfb987870ade3;p=oota-llvm.git diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp index 751d5b0ff2b..b2a0f4ba9b8 100644 --- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp +++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp @@ -13,17 +13,21 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/DataStructure.h" +#include "llvm/Analysis/DataStructure/DataStructure.h" #include "llvm/Module.h" -#include "llvm/Analysis/DSGraph.h" +#include "llvm/Analysis/DataStructure/DSGraph.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/SCCIterator.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/STLExtras.h" using namespace llvm; namespace { RegisterAnalysis X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis"); + Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined"); } -using namespace DS; // run - Calculate the bottom up data structure graphs for each function in the // program. @@ -33,14 +37,13 @@ bool CompleteBUDataStructures::run(Module &M) { GlobalsGraph = new DSGraph(BU.getGlobalsGraph()); GlobalsGraph->setPrintAuxCalls(); - // Our call graph is the same as the BU data structures call graph - ActualCallees = BU.getActualCallees(); - #if 1 // REMOVE ME EVENTUALLY // FIXME: TEMPORARY (remove once finalization of indirect call sites in the // globals graph has been implemented in the BU pass) TDDataStructures &TD = getAnalysis(); + ActualCallees.clear(); + // The call graph extractable from the TD pass is _much more complete_ and // trustable than that generated by the BU pass so far. Until this is fixed, // we hack it like this: @@ -49,27 +52,176 @@ bool CompleteBUDataStructures::run(Module &M) { const std::vector &CSs = TD.getDSGraph(*MI).getFunctionCalls(); for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) { - if (CSs[CSi].isIndirectCall()) { - Instruction *TheCall = CSs[CSi].getCallSite().getInstruction(); + Instruction *TheCall = CSs[CSi].getCallSite().getInstruction(); + if (CSs[CSi].isIndirectCall()) { // indirect call: insert all callees const std::vector &Callees = CSs[CSi].getCalleeNode()->getGlobals(); for (unsigned i = 0, e = Callees.size(); i != e; ++i) if (Function *F = dyn_cast(Callees[i])) ActualCallees.insert(std::make_pair(TheCall, F)); + } else { // direct call: insert the single callee directly + ActualCallees.insert(std::make_pair(TheCall, + CSs[CSi].getCalleeFunc())); } } } +#else + // Our call graph is the same as the BU data structures call graph + ActualCallees = BU.getActualCallees(); #endif - // Start by copying all of the BU data structures graphs over, verbatim. + std::vector Stack; + hash_map ValMap; + unsigned NextID = 1; + + if (Function *Main = M.getMainFunction()) { + if (!Main->isExternal()) + calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap); + } else { + std::cerr << "CBU-DSA: No 'main' function found!\n"; + } + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!I->isExternal()) { - DSInfo[I] = new DSGraph(BU.getDSGraph(*I)); - DSInfo[I]->setGlobalsGraph(GlobalsGraph); - DSInfo[I]->setPrintAuxCalls(); + if (!I->isExternal() && !DSInfo.count(I)) + calculateSCCGraphs(getOrCreateGraph(*I), Stack, NextID, ValMap); + + GlobalsGraph->removeTriviallyDeadNodes(); + return false; +} + +DSGraph &CompleteBUDataStructures::getOrCreateGraph(Function &F) { + // Has the graph already been created? + DSGraph *&Graph = DSInfo[&F]; + if (Graph) return *Graph; + + // Copy the BU graph... + Graph = new DSGraph(getAnalysis().getDSGraph(F)); + Graph->setGlobalsGraph(GlobalsGraph); + Graph->setPrintAuxCalls(); + + // Make sure to update the DSInfo map for all of the functions currently in + // this graph! + for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin(); + I != Graph->getReturnNodes().end(); ++I) + DSInfo[I->first] = Graph; + + return *Graph; +} + + + +unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG, + std::vector &Stack, + unsigned &NextID, + hash_map &ValMap) { + assert(!ValMap.count(&FG) && "Shouldn't revisit functions!"); + unsigned Min = NextID++, MyID = Min; + ValMap[&FG] = Min; + Stack.push_back(&FG); + + // The edges out of the current node are the call site targets... + for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) { + Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction(); + + // Loop over all of the actually called functions... + ActualCalleesTy::iterator I, E; + for (tie(I, E) = ActualCallees.equal_range(Call); I != E; ++I) + if (!I->second->isExternal()) { + DSGraph &Callee = getOrCreateGraph(*I->second); + unsigned M; + // Have we visited the destination function yet? + hash_map::iterator It = ValMap.find(&Callee); + if (It == ValMap.end()) // No, visit it now. + M = calculateSCCGraphs(Callee, Stack, NextID, ValMap); + else // Yes, get it's number. + M = It->second; + if (M < Min) Min = M; + } + } + + assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!"); + if (Min != MyID) + return Min; // This is part of a larger SCC! + + // If this is a new SCC, process it now. + bool IsMultiNodeSCC = false; + while (Stack.back() != &FG) { + DSGraph *NG = Stack.back(); + ValMap[NG] = ~0U; + + DSGraph::NodeMapTy NodeMap; + FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap); + + // Update the DSInfo map and delete the old graph... + for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin(); + I != NG->getReturnNodes().end(); ++I) + DSInfo[I->first] = &FG; + delete NG; + + Stack.pop_back(); + IsMultiNodeSCC = true; + } + + // Clean up the graph before we start inlining a bunch again... + if (IsMultiNodeSCC) + FG.removeTriviallyDeadNodes(); + + Stack.pop_back(); + processGraph(FG); + ValMap[&FG] = ~0U; + return MyID; +} + + +/// processGraph - Process the BU graphs for the program in bottom-up order on +/// the SCC of the __ACTUAL__ call graph. This builds "complete" BU graphs. +void CompleteBUDataStructures::processGraph(DSGraph &G) { + hash_set calls; + + // The edges out of the current node are the call site targets... + for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) { + const DSCallSite &CS = G.getFunctionCalls()[i]; + Instruction *TheCall = CS.getCallSite().getInstruction(); + + assert(calls.insert(TheCall).second && + "Call instruction occurs multiple times in graph??"); + + + // Loop over all of the potentially called functions... + // Inline direct calls as well as indirect calls because the direct + // callee may have indirect callees and so may have changed. + // + ActualCalleesTy::iterator I, E; + tie(I, E) = ActualCallees.equal_range(TheCall); + unsigned TNum = 0, Num = std::distance(I, E); + for (; I != E; ++I, ++TNum) { + Function *CalleeFunc = I->second; + if (!CalleeFunc->isExternal()) { + // Merge the callee's graph into this graph. This works for normal + // calls or for self recursion within an SCC. + DSGraph &GI = getOrCreateGraph(*CalleeFunc); + ++NumCBUInlines; + G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits | + DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes | + DSGraph::DontCloneAuxCallNodes); + DEBUG(std::cerr << " Inlining graph [" << i << "/" << e-1 + << ":" << TNum << "/" << Num-1 << "] for " + << CalleeFunc->getName() << "[" + << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size() + << "] into '" /*<< G.getFunctionNames()*/ << "' [" + << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size() + << "]\n"); + } } + } + // Recompute the Incomplete markers + assert(G.getInlinedGlobals().empty()); + G.maskIncompleteMarkers(); + G.markIncompleteNodes(DSGraph::MarkFormalArgs); - return false; + // Delete dead nodes. Treat globals that are unreachable but that can + // reach live nodes as live. + G.removeDeadNodes(DSGraph::KeepUnreachableGlobals); }