Lots of bug fixes, add BottomUpClosure, which has bugs, but is a start.

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

1 files changed, 188 insertions, 0 deletions

diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
new file mode 100644
index 0000000000..c8e9fc3e33
--- /dev/null
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -0,0 +1,188 @@
+//===- BottomUpClosure.cpp - Compute the bottom up interprocedure closure -===//
+//
+// This file implements the BUDataStructures class, which represents the
+// Bottom-Up Interprocedural closure of the data structure graph over the
+// program.  This is useful for applications like pool allocation, but **not**
+// applications like pointer analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/DataStructure.h"
+#include "llvm/Module.h"
+#include "llvm/DerivedTypes.h"
+#include "Support/StatisticReporter.h"
+using std::map;
+
+AnalysisID BUDataStructures::ID(AnalysisID::create<BUDataStructures>());
+
+// releaseMemory - If the pass pipeline is done with this pass, we can release
+// our memory... here...
+//
+void BUDataStructures::releaseMemory() {
+  for (map<Function*, DSGraph*>::iterator I = DSInfo.begin(),
+         E = DSInfo.end(); I != E; ++I)
+    delete I->second;
+
+  // Empty map so next time memory is released, data structures are not
+  // re-deleted.
+  DSInfo.clear();
+}
+
+// run - Calculate the bottom up data structure graphs for each function in the
+// program.
+//
+bool BUDataStructures::run(Module &M) {
+  // Simply calculate the graphs for each function...
+  for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
+    if (!I->isExternal())
+      calculateGraph(*I);
+  return false;
+}
+
+
+// ResolveArguments - Resolve the formal and actual arguments for a function
+// call.
+//
+static void ResolveArguments(std::vector<DSNodeHandle> &Call, Function &F,
+                             map<Value*, DSNodeHandle> &ValueMap) {
+  // Resolve all of the function arguments...
+  Function::aiterator AI = F.abegin();
+  for (unsigned i = 2, e = Call.size(); i != e; ++i) {
+    // Advance the argument iterator to the first pointer argument...
+    while (!isa<PointerType>(AI->getType())) ++AI;
+    
+    // Add the link from the argument scalar to the provided value
+    DSNode *NN = ValueMap[AI];
+    NN->addEdgeTo(Call[i]);
+    ++AI;
+  }
+}
+
+// MergeGlobalNodes - Merge global value nodes in the inlined graph with the
+// global value nodes in the current graph if there are duplicates.
+//
+static void MergeGlobalNodes(map<Value*, DSNodeHandle> &ValMap,
+                             map<Value*, DSNodeHandle> &OldValMap) {
+  // Loop over all of the nodes inlined, if any of them are global variable
+  // nodes, we must make sure they get properly added or merged with the ValMap.
+  //
+  for (map<Value*, DSNodeHandle>::iterator I = OldValMap.begin(),
+         E = OldValMap.end(); I != E; ++I)
+    if (isa<GlobalValue>(I->first)) {
+      DSNodeHandle &NH = ValMap[I->first];  // Look up global in ValMap.
+      if (NH == 0) {        // No entry for the global yet?
+        NH = I->second;     // Add the one just inlined...
+      } else {
+        NH->mergeWith(I->second); // Merge the two globals together.
+      }
+    }
+
+}
+
+DSGraph &BUDataStructures::calculateGraph(Function &F) {
+  // 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;
+
+  // Copy the local version into DSInfo...
+  Graph = new DSGraph(getAnalysis<LocalDataStructures>().getDSGraph(F));
+
+  // Start resolving calls...
+  std::vector<std::vector<DSNodeHandle> > &FCs = Graph->getFunctionCalls();
+
+  DEBUG(cerr << "Inlining: " << F.getName() << "\n");
+
+  bool Inlined;
+  do {
+    Inlined = false;
+    for (unsigned i = 0; i != FCs.size(); ++i) {
+      // Copy the call, because inlining graphs may invalidate the FCs vector.
+      std::vector<DSNodeHandle> Call = FCs[i];
+
+      // If the function list is not incomplete...
+      if ((Call[1]->NodeType & DSNode::Incomplete) == 0) {
+        // Start inlining all of the functions we can... some may not be
+        // inlinable if they are external...
+        //
+        std::vector<GlobalValue*> Globals(Call[1]->getGlobals());
+
+        // Loop over the functions, inlining whatever we can...
+        for (unsigned g = 0; g != Globals.size(); ++g) {
+          // Must be a function type, so this cast MUST succeed.
+          Function &FI = cast<Function>(*Globals[g]);
+          if (&FI == &F) {
+            // Self recursion... simply link up the formal arguments with the
+            // actual arguments...
+           
+            DEBUG(cerr << "Self Inlining: " << F.getName() << "\n");
+
+            if (Call[0]) // Handle the return value if present...
+              Graph->RetNode->mergeWith(Call[0]);
+
+            // Resolve the arguments in the call to the actual values...
+            ResolveArguments(Call, F, Graph->getValueMap());
+
+            // Erase the entry in the globals vector
+            Globals.erase(Globals.begin()+g--);
+          } else if (!FI.isExternal()) {
+            DEBUG(std::cerr << "In " << F.getName() << " inlining: "
+                  << FI.getName() << "\n");
+
+            // Get the data structure graph for the called function, closing it
+            // if possible (which is only impossible in the case of mutual
+            // recursion...
+            //
+            DSGraph &GI = calculateGraph(FI);  // Graph to inline
+
+            DEBUG(cerr << "Got graph for " << FI.getName() << " in: "
+                  << F.getName() << "\n");
+
+
+            
+            // Clone the called function's graph into the current graph, keeping
+            // track of where scalars in the old graph _used_ to point...
+            map<Value*, DSNodeHandle> OldValMap;
+
+            // The clone call may invalidate any of the vectors in the data
+            // structure graph.
+            DSNode *RetVal = Graph->cloneInto(GI, OldValMap);
+
+            ResolveArguments(Call, FI, OldValMap);
+
+            // Merge global value nodes in the inlined graph with the global
+            // value nodes in the current graph if there are duplicates.
+            //
+            MergeGlobalNodes(Graph->getValueMap(), OldValMap);
+
+            // Erase the entry in the globals vector
+            Globals.erase(Globals.begin()+g--);
+          }
+        }
+
+        if (Globals.empty()) {         // Inlined all of the function calls?
+          // Erase the call if it is resolvable...
+          FCs.erase(FCs.begin()+i--);  // Don't skip a the next call...
+          Inlined = true;
+        } else if (Globals.size() != Call[1]->getGlobals().size()) {
+          // Was able to inline SOME, but not all of the functions.  Construct a
+          // new global node here.
+          //
+          assert(0 && "Unimpl!");
+          Inlined = true;
+        }
+      }
+    }
+
+    // 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();
+    }
+  } while (Inlined && !FCs.empty());
+
+  return *Graph;
+}