From da5c5a5b956a3974403b74ffacfb31cf3742066b Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 4 Mar 2004 19:16:35 +0000 Subject: [PATCH] Speed up the cbu pass from taking somewhere near the age of the universe to about 90s on povray git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@12123 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../DataStructure/CompleteBottomUp.cpp | 34 +++++++++++++++---- 1 file changed, 28 insertions(+), 6 deletions(-) diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp index df700d24f8a..b8189c522bb 100644 --- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp +++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp @@ -16,13 +16,16 @@ #include "llvm/Analysis/DataStructure.h" #include "llvm/Module.h" #include "llvm/Analysis/DSGraph.h" +#include "Support/Debug.h" #include "Support/SCCIterator.h" +#include "Support/Statistic.h" #include "Support/STLExtras.h" using namespace llvm; namespace { RegisterAnalysis X("cbudatastructure", "'Complete' Bottom-up Data Structure Analysis"); + Statistic<> NumCBUInlines("cbudatastructures", "Number of graphs inlined"); } @@ -168,26 +171,45 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG, /// 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??"); + + // The Normal BU pass will have taken care of direct calls well already, // don't worry about them. + + // FIXME: if a direct callee had indirect callees, it seems like they could + // be updated and we would have to reinline even direct calls! + if (!CS.getCallSite().getCalledFunction()) { // Loop over all of the actually called functions... ActualCalleesTy::iterator I, E; - for (tie(I, E) = ActualCallees.equal_range(TheCall); I != E; ++I) { + 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. - G.mergeInGraph(CS, *CalleeFunc, getOrCreateGraph(*CalleeFunc), - DSGraph::KeepModRefBits | - DSGraph::StripAllocaBit | - DSGraph::DontCloneCallNodes); + 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"); } } } @@ -200,5 +222,5 @@ void CompleteBUDataStructures::processGraph(DSGraph &G) { // Delete dead nodes. Treat globals that are unreachable but that can // reach live nodes as live. - G.removeDeadNodes(DSGraph::KeepUnreachableGlobals); + G.removeDeadNodes(DSGraph::RemoveUnreachableGlobals); } -- 2.34.1