Change the ActualCallees callgraph from hash_multimap<Instruction,Function>

to std::set<std::pair<Inst,Func>> to avoid duplicate entries.

This speeds up the CompleteBU pass from 1.99s to .15s on povray and the
eqgraph passes from 1.5s to .16s on the same.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21031 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 40 insertions, 78 deletions

diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
index 3cb0b6eb84..834ae9738f 100644
--- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp
+++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
@@ -13,6 +13,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#define DEBUG_TYPE "cbudatastructure"
 #include "llvm/Analysis/DataStructure/DataStructure.h"
 #include "llvm/Module.h"
 #include "llvm/Analysis/DataStructure/DSGraph.h"
@@ -37,39 +38,8 @@ bool CompleteBUDataStructures::runOnModule(Module &M) {
   GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
   GlobalsGraph->setPrintAuxCalls();
 
-#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<TDDataStructures>();
-
-  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:
-  for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
-    if (MI->isExternal()) continue;
-    const std::list<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
-
-    for (std::list<DSCallSite>::const_iterator CSI = CSs.begin(), E = CSs.end();
-         CSI != E; ++CSI) {
-      Instruction *TheCall = CSI->getCallSite().getInstruction();
-
-      if (CSI->isIndirectCall()) { // indirect call: insert all callees
-        std::vector<Function*> Callees;
-        CSI->getCalleeNode()->addFullFunctionList(Callees);
-        for (unsigned i = 0, e = Callees.size(); i != e; ++i)
-          ActualCallees.insert(std::make_pair(TheCall, Callees[i]));
-      } else {        // direct call: insert the single callee directly
-        ActualCallees.insert(std::make_pair(TheCall,
-                                            CSI->getCalleeFunc()));
-      }
-    }
-  }
-#else
   // Our call graph is the same as the BU data structures call graph
   ActualCallees = BU.getActualCallees();
-#endif
 
   std::vector<DSGraph*> Stack;
   hash_map<DSGraph*, unsigned> ValMap;
@@ -150,8 +120,9 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
     Instruction *Call = CI->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)
+    ActualCalleesTy::iterator I = callee_begin(Call), E = callee_end(Call);
+    for (; I != E && I->first == Call; ++I) {
+      assert(I->first == Call && "Bad callee construction!");
       if (!I->second->isExternal()) {
         DSGraph &Callee = getOrCreateGraph(*I->second);
         unsigned M;
@@ -163,6 +134,7 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
           M = It->second;
         if (M < Min) Min = M;
       }
+    }
   }
 
   assert(ValMap[&FG] == MyID && "SCC construction assumption wrong!");
@@ -225,10 +197,11 @@ void CompleteBUDataStructures::processGraph(DSGraph &G) {
     // 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);
+    ActualCalleesTy::iterator I = callee_begin(TheCall),E = callee_end(TheCall);
+    unsigned TNum = 0, Num = 0;
+    DEBUG(Num = std::distance(I, E));
     for (; I != E; ++I, ++TNum) {
+      assert(I->first == TheCall && "Bad callee construction!");
       Function *CalleeFunc = I->second;
       if (!CalleeFunc->isExternal()) {
         // Merge the callee's graph into this graph.  This works for normal
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 7bad52ac3c..cd16e993ad 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -2055,7 +2055,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
       GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
 
       // Make sure that all globals are cloned over as roots.
-      if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
+      if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) {
         DSGraph::ScalarMapTy::iterator SMI = 
           GlobalsGraph->getScalarMap().find(I->first);
         if (SMI != GlobalsGraph->getScalarMap().end())
diff --git a/lib/Analysis/DataStructure/EquivClassGraphs.cpp b/lib/Analysis/DataStructure/EquivClassGraphs.cpp
index 288f594926..d3ffc5205b 100644
--- a/lib/Analysis/DataStructure/EquivClassGraphs.cpp
+++ b/lib/Analysis/DataStructure/EquivClassGraphs.cpp
@@ -339,8 +339,8 @@ processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
     Instruction *Call = CI->getCallSite().getInstruction();
 
     // Loop over all of the actually called functions...
-    ActualCalleesTy::const_iterator I, E;
-    for (tie(I, E) = getActualCallees().equal_range(Call); I != E; ++I)
+    ActualCalleesTy::const_iterator I = callee_begin(Call),E = callee_end(Call);
+    for (; I != E; ++I)
       if (!I->second->isExternal()) {
         // Process the callee as necessary.
         unsigned M = processSCC(getOrCreateGraph(*I->second),
@@ -414,8 +414,8 @@ void EquivClassGraphs::processGraph(DSGraph &G) {
     // graph so we only need to do this once.
     // 
     DSGraph* CalleeGraph = NULL;
-    ActualCalleesTy::const_iterator I, E;
-    tie(I, E) = getActualCallees().equal_range(TheCall);
+    ActualCalleesTy::const_iterator I = callee_begin(TheCall);
+    ActualCalleesTy::const_iterator E = callee_end(TheCall);
     unsigned TNum, Num;
 
     // Loop over all potential callees to find the first non-external callee.
diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp
index 747ae2fc4b..9f0574df1a 100644
--- a/lib/Analysis/DataStructure/Steensgaard.cpp
+++ b/lib/Analysis/DataStructure/Steensgaard.cpp
@@ -25,11 +25,10 @@ using namespace llvm;
 namespace {
   class Steens : public ModulePass, public AliasAnalysis {
     DSGraph *ResultGraph;
-    DSGraph *GlobalsGraph;  // FIXME: Eliminate globals graph stuff from DNE
 
     EquivalenceClasses<GlobalValue*> GlobalECs;  // Always empty
   public:
-    Steens() : ResultGraph(0), GlobalsGraph(0) {}
+    Steens() : ResultGraph(0) {}
     ~Steens() {
       releaseMyMemory();
       assert(ResultGraph == 0 && "releaseMemory not called?");
@@ -116,8 +115,7 @@ bool Steens::runOnModule(Module &M) {
 
   // Create a new, empty, graph...
   ResultGraph = new DSGraph(GlobalECs, getTargetData());
-  GlobalsGraph = new DSGraph(GlobalECs, getTargetData());
-  ResultGraph->setGlobalsGraph(GlobalsGraph);
+  ResultGraph->spliceFrom(LDS.getGlobalsGraph());
 
   // Loop over the rest of the module, merging graphs for non-external functions
   // into this graph.
@@ -186,7 +184,7 @@ bool Steens::runOnModule(Module &M) {
 
   // Remove any nodes that are dead after all of the merging we have done...
   // FIXME: We should be able to disable the globals graph for steens!
-  ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
+  //ResultGraph->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
 
   DEBUG(print(std::cerr, &M));
   return false;
diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp
index e44cea1d8e..a169ceff1d 100644
--- a/lib/Analysis/DataStructure/TopDownClosure.cpp
+++ b/lib/Analysis/DataStructure/TopDownClosure.cpp
@@ -58,9 +58,9 @@ void TDDataStructures::markReachableFunctionsExternallyAccessible(DSNode *N,
 // program.
 //
 bool TDDataStructures::runOnModule(Module &M) {
-  BUDataStructures &BU = getAnalysis<BUDataStructures>();
-  GlobalECs = BU.getGlobalECs();
-  GlobalsGraph = new DSGraph(BU.getGlobalsGraph(), GlobalECs);
+  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
@@ -95,8 +95,6 @@ bool TDDataStructures::runOnModule(Module &M) {
   // calculate a post-order traversal, then reverse it.
   hash_set<DSGraph*> VisitedGraph;
   std::vector<DSGraph*> PostOrder;
-  const BUDataStructures::ActualCalleesTy &ActualCallees = 
-    getAnalysis<BUDataStructures>().getActualCallees();
 
 #if 0
 {TIME_REGION(XXX, "td:Copy graphs");
@@ -114,11 +112,11 @@ bool TDDataStructures::runOnModule(Module &M) {
 
   // Calculate top-down from main...
   if (Function *F = M.getMainFunction())
-    ComputePostOrder(*F, VisitedGraph, PostOrder, ActualCallees);
+    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, ActualCallees);
+    ComputePostOrder(*I, VisitedGraph, PostOrder);
 
   VisitedGraph.clear();   // Release memory!
 }
@@ -167,8 +165,7 @@ DSGraph &TDDataStructures::getOrCreateDSGraph(Function &F) {
 
 
 void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
-                                        std::vector<DSGraph*> &PostOrder,
-                      const BUDataStructures::ActualCalleesTy &ActualCallees) {
+                                        std::vector<DSGraph*> &PostOrder) {
   if (F.isExternal()) return;
   DSGraph &G = getOrCreateDSGraph(F);
   if (Visited.count(&G)) return;
@@ -177,13 +174,11 @@ void TDDataStructures::ComputePostOrder(Function &F,hash_set<DSGraph*> &Visited,
   // Recursively traverse all of the callee graphs.
   for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E; ++CI) {
     Instruction *CallI = CI->getCallSite().getInstruction();
-    std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
-      BUDataStructures::ActualCalleesTy::const_iterator>
-         IP = ActualCallees.equal_range(CallI);
+    BUDataStructures::ActualCalleesTy::const_iterator I = 
+      BUInfo->callee_begin(CallI), E = BUInfo->callee_end(CallI);
 
-    for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
-         I != IP.second; ++I)
-      ComputePostOrder(*I->second, Visited, PostOrder, ActualCallees);
+    for (; I != E; ++I)
+      ComputePostOrder(*I->second, Visited, PostOrder);
   }
 
   PostOrder.push_back(&G);
@@ -315,9 +310,6 @@ void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
   // callee graphs.
   if (DSG.fc_begin() == DSG.fc_end()) return;
 
-  const BUDataStructures::ActualCalleesTy &ActualCallees =
-    getAnalysis<BUDataStructures>().getActualCallees();
-
   // 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();
@@ -334,27 +326,26 @@ void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
 
     Instruction *CallI = CI->getCallSite().getInstruction();
     // For each function in the invoked function list at this call site...
-    std::pair<BUDataStructures::ActualCalleesTy::const_iterator,
-              BUDataStructures::ActualCalleesTy::const_iterator> 
-      IP = ActualCallees.equal_range(CallI);
+    BUDataStructures::ActualCalleesTy::const_iterator IPI =
+      BUInfo->callee_begin(CallI), IPE = BUInfo->callee_end(CallI);
 
     // Skip over all calls to this graph (SCC calls).
-    while (IP.first != IP.second && &getDSGraph(*IP.first->second) == &DSG)
-      ++IP.first;
+    while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG)
+      ++IPI;
 
     // All SCC calls?
-    if (IP.first == IP.second) continue;
+    if (IPI == IPE) continue;
 
-    Function *FirstCallee = IP.first->second;
-    ++IP.first;
+    Function *FirstCallee = IPI->second;
+    ++IPI;
 
     // Skip over more SCC calls.
-    while (IP.first != IP.second && &getDSGraph(*IP.first->second) == &DSG)
-      ++IP.first;
+    while (IPI != IPE && &getDSGraph(*IPI->second) == &DSG)
+      ++IPI;
 
     // If there is exactly one callee from this call site, remember the edge in
     // CallerEdges.
-    if (IP.first == IP.second) {
+    if (IPI == IPE) {
       if (!FirstCallee->isExternal())
         CallerEdges[&getDSGraph(*FirstCallee)]
           .push_back(CallerCallEdge(&DSG, &*CI, FirstCallee));
@@ -367,9 +358,9 @@ void TDDataStructures::InlineCallersIntoGraph(DSGraph &DSG) {
     // so we build up a new, private, graph that represents the calls of all
     // calls to this set of functions.
     std::vector<Function*> Callees;
-    IP = ActualCallees.equal_range(CallI);
-    for (BUDataStructures::ActualCalleesTy::const_iterator I = IP.first;
-         I != IP.second; ++I)
+    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());