Fix infinite loop in the BU algorithm. Unfortunately this dies a serious

death when handling moderately sized SCC's, but what can you do


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

1 files changed, 177 insertions, 30 deletions

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index a19155d..36a3d17 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -46,27 +46,170 @@ void BUDataStructures::releaseMemory() {
   GlobalsGraph = 0;
 }
 
+
+// Return true if a graph was inlined
+// Can not modify the part of the AuxCallList < FirstResolvableCall.
+//
+bool BUDataStructures::ResolveFunctionCalls(DSGraph &G,
+                                            unsigned &FirstResolvableCall,
+                                   std::map<Function*, DSCallSite> &InProcess,
+                                            unsigned Indent) {
+  std::vector<DSCallSite> &FCs = G.getAuxFunctionCalls();
+  bool Changed = false;
+
+  // Loop while there are call sites that we can resolve!
+  while (FirstResolvableCall != FCs.size()) {
+    DSCallSite Call = FCs[FirstResolvableCall];
+
+    // If the function list is incomplete...
+    if (Call.getCallee().getNode()->NodeType & DSNode::Incomplete) {
+      // If incomplete, we cannot resolve it, so leave it at the beginning of
+      // the call list with the other unresolvable calls...
+      ++FirstResolvableCall;
+    } else {
+      // Start inlining all of the functions we can... some may not be
+      // inlinable if they are external...
+      //
+      const std::vector<GlobalValue*> &Callees =
+        Call.getCallee().getNode()->getGlobals();
+
+      bool hasExternalTarget = false;
+      
+      // Loop over the functions, inlining whatever we can...
+      for (unsigned c = 0, e = Callees.size(); c != e; ++c) {
+        // Must be a function type, so this cast should succeed unless something
+        // really wierd is happening.
+        Function &FI = cast<Function>(*Callees[c]);
+
+        if (FI.getName() == "printf" || FI.getName() == "sscanf" ||
+            FI.getName() == "fprintf" || FI.getName() == "open" ||
+            FI.getName() == "sprintf" || FI.getName() == "fputs") {
+          // Ignore
+        } else if (FI.isExternal()) {
+          // If the function is external, then we cannot resolve this call site!
+          hasExternalTarget = true;
+          break;
+        } else {
+          std::map<Function*, DSCallSite>::iterator I =
+            InProcess.lower_bound(&FI);
+
+          if (I != InProcess.end() && I->first == &FI) {  // Recursion detected?
+            // Merge two call sites to eliminate recursion...
+            Call.mergeWith(I->second);
+
+            DEBUG(std::cerr << std::string(Indent*2, ' ')
+                  << "* Recursion detected for function " << FI.getName()<<"\n");
+          } else {
+            DEBUG(std::cerr << std::string(Indent*2, ' ')
+                  << "Inlining: " << FI.getName() << "\n");
+            
+            // Get the data structure graph for the called function, closing it
+            // if possible...
+            //
+            DSGraph &GI = calculateGraph(FI, Indent+1);  // Graph to inline
+
+            DEBUG(std::cerr << std::string(Indent*2, ' ')
+                  << "Got graph for: " << FI.getName() << "["
+                  << GI.getGraphSize() << "+"
+                  << GI.getAuxFunctionCalls().size() << "] "
+                  << " in: " << G.getFunction().getName() << "["
+                  << G.getGraphSize() << "+"
+                  << G.getAuxFunctionCalls().size() << "]\n");
+
+            // Keep track of how many call sites are added by the inlining...
+            unsigned NumCalls = FCs.size();
+
+            // Resolve the arguments and return value
+            G.mergeInGraph(Call, GI, DSGraph::StripAllocaBit |
+                           DSGraph::DontCloneCallNodes);
+
+            // Added a call site?
+            if (FCs.size() != NumCalls) {
+              // Otherwise we need to inline the graph.  Temporarily add the
+              // current function to the InProcess map to be able to handle
+              // recursion successfully.
+              //
+              I = InProcess.insert(I, std::make_pair(&FI, Call));
+
+              // ResolveFunctionCalls - Resolve the function calls that just got
+              // inlined...
+              //
+              Changed |= ResolveFunctionCalls(G, NumCalls, InProcess, Indent+1);
+              
+              // Now that we are done processing the inlined graph, remove our
+              // cycle detector record...
+              //
+              //InProcess.erase(I);
+            }
+          }
+        }
+      }
+
+      if (hasExternalTarget) {
+        // If we cannot resolve this call site...
+        ++FirstResolvableCall;
+      } else {
+        Changed = true;
+        FCs.erase(FCs.begin()+FirstResolvableCall);
+      }
+    }
+  }
+
+  return Changed;
+}
+
 DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
   // Make sure this graph has not already been calculated, or that we don't get
   // into an infinite loop with mutually recursive functions.
   //
-  DSGraph *&Graph = DSInfo[&F];
-  if (Graph) return *Graph;
+  DSGraph *&GraphPtr = DSInfo[&F];
+  if (GraphPtr) return *GraphPtr;
 
   // Copy the local version into DSInfo...
-  Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
-  Graph->setGlobalsGraph(GlobalsGraph);
-  Graph->setPrintAuxCalls();
+  GraphPtr = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
+  DSGraph &Graph = *GraphPtr;
+
+  Graph.setGlobalsGraph(GlobalsGraph);
+  Graph.setPrintAuxCalls();
 
   // Start resolving calls...
-  std::vector<DSCallSite> &FCs = Graph->getAuxFunctionCalls();
+  std::vector<DSCallSite> &FCs = Graph.getAuxFunctionCalls();
 
   // Start with a copy of the original call sites...
-  FCs = Graph->getFunctionCalls();
+  FCs = Graph.getFunctionCalls();
 
-  DEBUG(std::cerr << std::string(Indent*4, ' ')
+  DEBUG(std::cerr << std::string(Indent*2, ' ')
                   << "[BU] Calculating graph for: " << F.getName() << "\n");
 
+  bool Changed;
+  while (1) {
+    unsigned FirstResolvableCall = 0;
+    std::map<Function *, DSCallSite> InProcess;
+
+    // Insert a call site for self to handle self recursion...
+    std::vector<DSNodeHandle> Args;
+    Args.reserve(F.asize());
+    for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
+      if (isPointerType(I->getType()))
+        Args.push_back(Graph.getNodeForValue(I));
+
+    InProcess.insert(std::make_pair(&F, 
+           DSCallSite(*(CallInst*)0, Graph.getRetNode(),(DSNode*)0,Args)));
+
+    Changed = ResolveFunctionCalls(Graph, FirstResolvableCall, InProcess,
+                                   Indent);
+
+    if (Changed) {
+      Graph.maskIncompleteMarkers();
+      Graph.markIncompleteNodes();
+      Graph.removeDeadNodes();
+      break;
+    } else {
+      break;
+    }
+  }
+
+#if 0  
   bool Inlined;
   do {
     Inlined = false;
@@ -93,18 +236,18 @@ DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
           if (&FI == &F) {
             // Self recursion... simply link up the formal arguments with the
             // actual arguments...
-            DEBUG(std::cerr << std::string(Indent*4, ' ')
-                  << "  [BU] Self Inlining: " << F.getName() << "\n");
+            DEBUG(std::cerr << std::string(Indent*2, ' ')
+                  << "[BU] Self Inlining: " << F.getName() << "\n");
 
             // Handle self recursion by resolving the arguments and return value
-            Graph->mergeInGraph(Call, *Graph, DSGraph::StripAllocaBit);
+            Graph.mergeInGraph(Call, Graph, DSGraph::StripAllocaBit);
 
             // Erase the entry in the callees vector
             Callees.erase(Callees.begin()+c--);
 
           } else if (!FI.isExternal()) {
-            DEBUG(std::cerr << std::string(Indent*4, ' ')
-                  << "  [BU] In " << F.getName() << " inlining: "
+            DEBUG(std::cerr << std::string(Indent*2, ' ')
+                  << "[BU] In " << F.getName() << " inlining: "
                   << FI.getName() << "\n");
             
             // Get the data structure graph for the called function, closing it
@@ -113,13 +256,13 @@ DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
             //
             DSGraph &GI = calculateGraph(FI, Indent+1);  // Graph to inline
 
-            DEBUG(std::cerr << std::string(Indent*4, ' ')
-                  << "  [BU] Got graph for " << FI.getName()
+            DEBUG(std::cerr << std::string(Indent*2, ' ')
+                  << "[BU] Got graph for " << FI.getName()
                   << " in: " << F.getName() << "[" << GI.getGraphSize() << "+"
                   << GI.getAuxFunctionCalls().size() << "]\n");
 
             // Handle self recursion by resolving the arguments and return value
-            Graph->mergeInGraph(Call, GI, DSGraph::StripAllocaBit |
+            Graph.mergeInGraph(Call, GI, DSGraph::StripAllocaBit |
                                 DSGraph::DontCloneCallNodes);
 
             // Erase the entry in the Callees vector
@@ -150,23 +293,26 @@ DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
           Inlined = true;
         }
 
+
+#if 0
         // If we just inlined a function that had call nodes, chances are that
         // the call nodes are redundant with ones we already have.  Eliminate
         // those call nodes now.
         //
-        if (FCs.size() > OldNumCalls)
-          Graph->removeTriviallyDeadNodes();
+        if (FCs.size() >= OldNumCalls)
+          Graph.removeTriviallyDeadNodes();
+#endif
       }
 
       if (FCs.size() > 200) {
         std::cerr << "Aborted inlining fn: '" << F.getName() << "'!"
                   << std::endl;
-        Graph->maskIncompleteMarkers();
-        Graph->markIncompleteNodes();
-        Graph->removeDeadNodes();
-        Graph->writeGraphToFile(std::cerr, "crap."+F.getName());
+        Graph.maskIncompleteMarkers();
+        Graph.markIncompleteNodes();
+        Graph.removeDeadNodes();
+        Graph.writeGraphToFile(std::cerr, "crap."+F.getName());
         exit(1);
-        return *Graph;
+        return Graph;
       }
 
     }
@@ -174,19 +320,20 @@ DSGraph &BUDataStructures::calculateGraph(Function &F, unsigned Indent) {
     // Recompute the Incomplete markers.  If there are any function calls left
     // now that are complete, we must loop!
     if (Inlined) {
-      Graph->maskIncompleteMarkers();
-      Graph->markIncompleteNodes();
-      Graph->removeDeadNodes();
+      Graph.maskIncompleteMarkers();
+      Graph.markIncompleteNodes();
+      Graph.removeDeadNodes();
     }
     
   } while (Inlined && !FCs.empty());
+#endif
 
-  DEBUG(std::cerr << std::string(Indent*4, ' ')
+  DEBUG(std::cerr << std::string(Indent*2, ' ')
         << "[BU] Done inlining: " << F.getName() << " ["
-        << Graph->getGraphSize() << "+" << Graph->getAuxFunctionCalls().size()
+        << Graph.getGraphSize() << "+" << Graph.getAuxFunctionCalls().size()
         << "]\n");
 
-  //Graph->writeGraphToFile(std::cerr, "bu_" + F.getName());
+  Graph.writeGraphToFile(std::cerr, "bu_" + F.getName());
 
-  return *Graph;
+  return Graph;
 }