Graphs that are part of equivalence sets can be multi-function SCC's

[oota-llvm.git] / lib / Analysis / DataStructure / CompleteBottomUp.cpp

diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
index 95c9d3cf5db9a33114604ecbd32fa14982047536..3cd2bb0eef5f7b46e5c8510da0c074664b5aeadc 100644 (file)
--- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp
+++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
@@ -13,13 +13,13 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Analysis/DataStructure.h"
+#include "llvm/Analysis/DataStructure/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"
+#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 {
@@ -32,19 +32,18 @@ namespace {
 // run - Calculate the bottom up data structure graphs for each function in the
 // program.
 //
-bool CompleteBUDataStructures::run(Module &M) {
+bool CompleteBUDataStructures::runOnModule(Module &M) {
   BUDataStructures &BU = getAnalysis<BUDataStructures>();
   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<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:
@@ -53,17 +52,23 @@ bool CompleteBUDataStructures::run(Module &M) {
     const std::vector<DSCallSite> &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<GlobalValue*> &Callees =
           CSs[CSi].getCalleeNode()->getGlobals();
         for (unsigned i = 0, e = Callees.size(); i != e; ++i)
           if (Function *F = dyn_cast<Function>(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
 
   std::vector<DSGraph*> Stack;
@@ -71,7 +76,8 @@ bool CompleteBUDataStructures::run(Module &M) {
   unsigned NextID = 1;
 
   if (Function *Main = M.getMainFunction()) {
-    calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
+    if (!Main->isExternal())
+      calculateSCCGraphs(getOrCreateGraph(*Main), Stack, NextID, ValMap);
   } else {
     std::cerr << "CBU-DSA: No 'main' function found!\n";
   }
@@ -151,6 +157,9 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
     for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
          I != NG->getReturnNodes().end(); ++I)
       DSInfo[I->first] = &FG;
+
+    // Remove NG from the ValMap since the pointer may get recycled.
+    ValMap.erase(NG);
     delete NG;
     
     Stack.pop_back();
@@ -182,35 +191,30 @@ void CompleteBUDataStructures::processGraph(DSGraph &G) {
            "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;
-      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");
-        }
+    // 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");
       }
     }
   }