Revert the aggressive inlining for now, it doesn't handle external correctly

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

1 files changed, 78 insertions, 112 deletions

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 1a69e172a6..84405ea373 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -41,7 +41,7 @@ namespace {
   X("budatastructure", "Bottom-up Data Structure Analysis");
 }
 
-static bool GetAllCallees(const DSCallSite &CS,
+static bool GetAllCalleesN(const DSCallSite &CS,
                           std::vector<Function*> &Callees);
 
 /// BuildGlobalECs - Look at all of the nodes in the globals graph.  If any node
@@ -164,7 +164,6 @@ bool BUDataStructures::runOnModule(Module &M) {
   unsigned NextID = 1;
 
   Function *MainFunc = M.getMainFunction();
-
   if (MainFunc)
     calculateGraphs(MainFunc, Stack, NextID, ValMap);
 
@@ -216,8 +215,9 @@ bool BUDataStructures::runOnModule(Module &M) {
   if (MainFunc && !MainFunc->isExternal()) {
     DSGraph &MainGraph = getOrCreateGraph(MainFunc);
     const DSGraph &GG = *MainGraph.getGlobalsGraph();
-    ReachabilityCloner RC(MainGraph, GG, DSGraph::DontCloneCallNodes |
-			  DSGraph::DontCloneAuxCallNodes);
+    ReachabilityCloner RC(MainGraph, GG,
+                          DSGraph::DontCloneCallNodes |
+                          DSGraph::DontCloneAuxCallNodes);
 
     // Clone the global nodes into this graph.
     for (DSScalarMap::global_iterator I = GG.getScalarMap().global_begin(),
@@ -232,16 +232,16 @@ bool BUDataStructures::runOnModule(Module &M) {
     //Debug messages if along the way we didn't resolve a call site
     //also update the call graph and callsites we did find.
     for(DSGraph::afc_iterator ii = MainGraph.afc_begin(),
-	  ee = MainGraph.afc_end(); ii != ee; ++ii) {
+          ee = MainGraph.afc_end(); ii != ee; ++ii) {
       std::vector<Function*> Funcs;
-      GetAllCallees(*ii, Funcs);
+      GetAllCalleesN(*ii, Funcs);
       DEBUG(std::cerr << "Lost site\n");
       DEBUG(ii->getCallSite().getInstruction()->dump());
       for (std::vector<Function*>::iterator iif = Funcs.begin(), eef = Funcs.end();
-	   iif != eef; ++iif) {
-	AddGlobalToNode(this, *ii, *iif);
-	DEBUG(std::cerr << "Adding\n");
-	ActualCallees.insert(std::make_pair(ii->getCallSite().getInstruction(), *iif));
+           iif != eef; ++iif) {
+        AddGlobalToNode(this, *ii, *iif);
+        DEBUG(std::cerr << "Adding\n");
+        ActualCallees.insert(std::make_pair(ii->getCallSite().getInstruction(), *iif));
       }
     }
 
@@ -283,8 +283,27 @@ static bool isResolvableFunc(const Function* callee) {
   return !callee->isExternal() || isVAHackFn(callee);
 }
 
+static void GetAllCallees(const DSCallSite &CS,
+                          std::vector<Function*> &Callees) {
+  if (CS.isDirectCall()) {
+    if (isResolvableFunc(CS.getCalleeFunc()))
+      Callees.push_back(CS.getCalleeFunc());
+  } else if (!CS.getCalleeNode()->isIncomplete()) {
+    // Get all callees.
+    unsigned OldSize = Callees.size();
+    CS.getCalleeNode()->addFullFunctionList(Callees);
+
+    // If any of the callees are unresolvable, remove the whole batch!
+    for (unsigned i = OldSize, e = Callees.size(); i != e; ++i)
+      if (!isResolvableFunc(Callees[i])) {
+        Callees.erase(Callees.begin()+OldSize, Callees.end());
+        return;
+      }
+  }
+}
+
 //returns true if all callees were resolved
-static bool GetAllCallees(const DSCallSite &CS,
+static bool GetAllCalleesN(const DSCallSite &CS,
                           std::vector<Function*> &Callees) {
   if (CS.isDirectCall()) {
     if (isResolvableFunc(CS.getCalleeFunc())) {
@@ -321,7 +340,7 @@ static void GetAllAuxCallees(DSGraph &G, std::vector<Function*> &Callees) {
 unsigned BUDataStructures::calculateGraphs(Function *F,
                                            std::vector<Function*> &Stack,
                                            unsigned &NextID,
-					   hash_map<Function*, unsigned> &ValMap) {
+                                           hash_map<Function*, unsigned> &ValMap) {
   assert(!ValMap.count(F) && "Shouldn't revisit functions!");
   unsigned Min = NextID++, MyID = Min;
   ValMap[F] = Min;
@@ -369,7 +388,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
     Stack.pop_back();
     DSGraph &G = getDSGraph(*F);
     DEBUG(std::cerr << "  [BU] Calculating graph for: " << F->getName()<< "\n");
-    bool redo = calculateGraph(G);
+    calculateGraph(G);
     DEBUG(std::cerr << "  [BU] Done inlining: " << F->getName() << " ["
                     << G.getGraphSize() << "+" << G.getAuxFunctionCalls().size()
                     << "]\n");
@@ -378,7 +397,8 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
 
     // Should we revisit the graph?  Only do it if there are now new resolvable
     // callees.
-    if (redo) {
+    GetAllAuxCallees(Graph, CalleeFunctions);
+    if (!CalleeFunctions.empty()) {
       DEBUG(std::cerr << "Recalculating " << F->getName() << " due to new knowledge\n");
       ValMap.erase(F);
       return calculateGraphs(F, Stack, NextID, ValMap);
@@ -421,7 +441,7 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
     Stack.pop_back();
 
     DEBUG(std::cerr << "Calculating graph for SCC #: " << MyID << " of size: "
-          << SCCSize << "\n");
+                    << SCCSize << "\n");
 
     // Compute the Max SCC Size.
     if (MaxSCC < SCCSize)
@@ -432,14 +452,10 @@ unsigned BUDataStructures::calculateGraphs(Function *F,
 
     // Now that we have one big happy family, resolve all of the call sites in
     // the graph...
-    bool redo = calculateGraph(SCCGraph);
+    calculateGraph(SCCGraph);
     DEBUG(std::cerr << "  [BU] Done inlining SCC  [" << SCCGraph.getGraphSize()
                     << "+" << SCCGraph.getAuxFunctionCalls().size() << "]\n");
 
-    if (redo) {
-      DEBUG(std::cerr << "MISSING REDO\n");
-    }
-
     DEBUG(std::cerr << "DONE with SCC #: " << MyID << "\n");
 
     // We never have to revisit "SCC" processed functions...
@@ -493,8 +509,7 @@ DSGraph &BUDataStructures::CreateGraphForExternalFunction(const Function &Fn) {
   return *DSG;
 }
 
-
-bool BUDataStructures::calculateGraph(DSGraph &Graph) {
+void BUDataStructures::calculateGraph(DSGraph &Graph) {
   // If this graph contains the main function, clone the globals graph into this
   // graph before we inline callees and other fun stuff.
   bool ContainsMain = false;
@@ -530,27 +545,42 @@ bool BUDataStructures::calculateGraph(DSGraph &Graph) {
   std::list<DSCallSite> TempFCs;
   std::list<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls();
   TempFCs.swap(AuxCallsList);
-  //remember what we've seen (or will see)
-  unsigned oldSize = TempFCs.size();
 
   bool Printed = false;
-  bool missingNode = false;
-
+  std::vector<Function*> CalledFuncs;
   while (!TempFCs.empty()) {
     DSCallSite &CS = *TempFCs.begin();
-    Instruction *TheCall = CS.getCallSite().getInstruction();
-    DSGraph *GI;
+
+    CalledFuncs.clear();
 
     // Fast path for noop calls.  Note that we don't care about merging globals
     // in the callee with nodes in the caller here.
-    if (CS.isDirectCall()) {
-      if (!isVAHackFn(CS.getCalleeFunc()) && isResolvableFunc(CS.getCalleeFunc())) {
-        Function* Callee = CS.getCalleeFunc();
+    if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0) {
+      TempFCs.erase(TempFCs.begin());
+      continue;
+    } else if (CS.isDirectCall() && isVAHackFn(CS.getCalleeFunc())) {
+      TempFCs.erase(TempFCs.begin());
+      continue;
+    }
+
+    GetAllCallees(CS, CalledFuncs);
+
+    if (CalledFuncs.empty()) {
+      // Remember that we could not resolve this yet!
+      AuxCallsList.splice(AuxCallsList.end(), TempFCs, TempFCs.begin());
+      continue;
+    } else {
+      DSGraph *GI;
+      Instruction *TheCall = CS.getCallSite().getInstruction();
+
+      if (CalledFuncs.size() == 1) {
+        Function *Callee = CalledFuncs[0];
         ActualCallees.insert(std::make_pair(TheCall, Callee));
-	
-        assert(doneDSGraph(Callee) && "Direct calls should always be precomputed");
+
+        // Get the data structure graph for the called function.
         GI = &getDSGraph(*Callee);  // Graph to inline
         DEBUG(std::cerr << "    Inlining graph for " << Callee->getName());
+
         DEBUG(std::cerr << "[" << GI->getGraphSize() << "+"
               << GI->getAuxFunctionCalls().size() << "] into '"
               << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+"
@@ -559,38 +589,22 @@ bool BUDataStructures::calculateGraph(DSGraph &Graph) {
                            DSGraph::StripAllocaBit|DSGraph::DontCloneCallNodes);
         ++NumBUInlines;
       } else {
-        DEBUG(std::cerr << "Graph " << Graph.getFunctionNames() << " Call Site " <<
-              CS.getCallSite().getInstruction() << " never resolvable\n");
-      }
-      --oldSize;
-      TempFCs.pop_front();
-      continue;
-    } else {
-      std::vector<Function*> CalledFuncs;
-      bool resolved = GetAllCallees(CS, CalledFuncs);
-
-      if (CalledFuncs.empty()) {
-        DEBUG(std::cerr << "Graph " << Graph.getFunctionNames() << " Call Site " <<
-              CS.getCallSite().getInstruction() << " delayed\n");
-      } else {
-        DEBUG(
         if (!Printed)
           std::cerr << "In Fns: " << Graph.getFunctionNames() << "\n";
         std::cerr << "  calls " << CalledFuncs.size()
                   << " fns from site: " << CS.getCallSite().getInstruction()
                   << "  " << *CS.getCallSite().getInstruction();
         std::cerr << "   Fns =";
-        );
         unsigned NumPrinted = 0;
 
         for (std::vector<Function*>::iterator I = CalledFuncs.begin(),
                E = CalledFuncs.end(); I != E; ++I) {
-          DEBUG(if (NumPrinted++ < 8) std::cerr << " " << (*I)->getName(););
+          if (NumPrinted++ < 8) std::cerr << " " << (*I)->getName();
 
           // Add the call edges to the call graph.
           ActualCallees.insert(std::make_pair(TheCall, *I));
         }
-        DEBUG(std::cerr << "\n");
+        std::cerr << "\n";
 
         // See if we already computed a graph for this set of callees.
         std::sort(CalledFuncs.begin(), CalledFuncs.end());
@@ -602,14 +616,6 @@ bool BUDataStructures::calculateGraph(DSGraph &Graph) {
             E = CalledFuncs.end();
 
           // Start with a copy of the first graph.
-          if (!doneDSGraph(*I)) {
-            AuxCallsList.splice(AuxCallsList.end(), TempFCs, TempFCs.begin());
-            missingNode = true;
-            continue;
-          }
-
-          AddGlobalToNode(this, CS, *I);
-
           GI = IndCallGraph.first = new DSGraph(getDSGraph(**I), GlobalECs);
           GI->setGlobalsGraph(Graph.getGlobalsGraph());
           std::vector<DSNodeHandle> &Args = IndCallGraph.second;
@@ -619,17 +625,10 @@ bool BUDataStructures::calculateGraph(DSGraph &Graph) {
           GI->getFunctionArgumentsForCall(*I, Args);
 
           // Merge all of the other callees into this graph.
-          bool locMissing = false;
-          for (++I; I != E && !locMissing; ++I) {
-            AddGlobalToNode(this, CS, *I);
+          for (++I; I != E; ++I) {
             // If the graph already contains the nodes for the function, don't
             // bother merging it in again.
             if (!GI->containsFunction(*I)) {
-              if (!doneDSGraph(*I)) {
-                locMissing = true;
-                break;
-              }
-
               GI->cloneInto(getDSGraph(**I));
               ++NumBUInlines;
             }
@@ -644,44 +643,29 @@ bool BUDataStructures::calculateGraph(DSGraph &Graph) {
             for (e = NextArgs.size(); i != e; ++i)
               Args.push_back(NextArgs[i]);
           }
-          if (locMissing) {
-            AuxCallsList.splice(AuxCallsList.end(), TempFCs, TempFCs.begin());
-            missingNode = true;
-            continue;
-          }
 
           // Clean up the final graph!
           GI->removeDeadNodes(DSGraph::KeepUnreachableGlobals);
         } else {
-          DEBUG(std::cerr << "***\n*** RECYCLED GRAPH ***\n***\n");
-          for (std::vector<Function*>::iterator I = CalledFuncs.begin(), E = CalledFuncs.end(); I != E; ++I) {
-            AddGlobalToNode(this, CS, *I);
-          }
+          std::cerr << "***\n*** RECYCLED GRAPH ***\n***\n";
         }
 
         GI = IndCallGraph.first;
 
-        if (AlreadyInlined[CS.getCallSite()] != CalledFuncs) {
-         AlreadyInlined[CS.getCallSite()].swap(CalledFuncs);
-
-          // Merge the unified graph into this graph now.
-          DEBUG(std::cerr << "    Inlining multi callee graph "
-                << "[" << GI->getGraphSize() << "+"
-                << GI->getAuxFunctionCalls().size() << "] into '"
-                << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+"
-                << Graph.getAuxFunctionCalls().size() << "]\n");
-
-          Graph.mergeInGraph(CS, IndCallGraph.second, *GI,
-                             DSGraph::StripAllocaBit |
-                             DSGraph::DontCloneCallNodes);
+        // Merge the unified graph into this graph now.
+        DEBUG(std::cerr << "    Inlining multi callee graph "
+              << "[" << GI->getGraphSize() << "+"
+              << GI->getAuxFunctionCalls().size() << "] into '"
+              << Graph.getFunctionNames() << "' [" << Graph.getGraphSize() <<"+"
+              << Graph.getAuxFunctionCalls().size() << "]\n");
 
-          ++NumBUInlines;
-        } else {
-          DEBUG(std::cerr << "   Skipping already inlined graph\n");
-        }
+        Graph.mergeInGraph(CS, IndCallGraph.second, *GI,
+                           DSGraph::StripAllocaBit |
+                           DSGraph::DontCloneCallNodes);
+        ++NumBUInlines;
       }
-      AuxCallsList.splice(AuxCallsList.end(), TempFCs, TempFCs.begin());
     }
+    TempFCs.erase(TempFCs.begin());
   }
 
   // Recompute the Incomplete markers
@@ -704,24 +688,6 @@ bool BUDataStructures::calculateGraph(DSGraph &Graph) {
     RC.getClonedNH(MainSM[*I]);
 
   //Graph.writeGraphToFile(std::cerr, "bu_" + F.getName());
-  AuxCallsList.sort();
-  AuxCallsList.unique();
-  //conditionally prune the call list keeping only one copy of each actual
-  //CallSite
-  if (AuxCallsList.size() > 100) {
-    DEBUG(std::cerr << "Reducing Aux from " << AuxCallsList.size());
-    std::map<CallSite, std::list<DSCallSite>::iterator> keepers;
-    TempFCs.swap(AuxCallsList);
-    for( std::list<DSCallSite>::iterator ii = TempFCs.begin(), ee = TempFCs.end();
-         ii != ee; ++ii)
-      keepers[ii->getCallSite()] = ii;
-    for (std::map<CallSite, std::list<DSCallSite>::iterator>::iterator
-           ii = keepers.begin(), ee = keepers.end();
-         ii != ee; ++ii)
-      AuxCallsList.splice(AuxCallsList.end(), TempFCs, ii->second);
-    DEBUG(std::cerr << " to " << AuxCallsList.size() << "\n");
-  }
-  return missingNode || oldSize != AuxCallsList.size();
 }
 
 static const Function *getFnForValue(const Value *V) {