Make steensgaards performance not shameful

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

diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp
index c42ff73ac23a98c03d22feb4351f7ac96b12dc7f..b17846e2ecad462070a3a509ff6c311cd7d3cba8 100644 (file)
--- a/lib/Analysis/DataStructure/Steensgaard.cpp
+++ b/lib/Analysis/DataStructure/Steensgaard.cpp
@@ -13,11 +13,6 @@
 #include "llvm/Module.h"
 #include "Support/Statistic.h"
 
-namespace {
-  Statistic<> NumNoAlias  ("steens", "Number of 'no alias' replies");
-  Statistic<> NumMayAlias ("steens", "Number of 'may alias' replies");
-};
-
 namespace {
   class Steens : public Pass, public AliasAnalysis {
     DSGraph *ResultGraph;
@@ -75,7 +70,7 @@ namespace {
 
   // Register the pass...
   RegisterOpt<Steens> X("steens-aa",
-                        "Steensgaard's FlowInsensitive/ConIns alias analysis");
+                        "Steensgaard's alias analysis (DSGraph based)");
 
   // Register as an implementation of AliasAnalysis
   RegisterAnalysisGroup<AliasAnalysis, Steens> Y;
@@ -102,8 +97,6 @@ void Steens::ResolveFunctionCall(Function *F, const DSCallSite &Call,
     if (I != ValMap.end())    // If its a pointer argument...
       I->second.mergeWith(Call.getPtrArg(PtrArgIdx++));
   }
-
-  assert(PtrArgIdx == Call.getNumPtrArgs() && "Argument resolution mismatch!");
 }
 
 
@@ -118,6 +111,8 @@ bool Steens::run(Module &M) {
   ResultGraph = new DSGraph();
   GlobalsGraph = new DSGraph();
   ResultGraph->setGlobalsGraph(GlobalsGraph);
+  ResultGraph->setPrintAuxCalls();
+
   // RetValMap - Keep track of the return values for all functions that return
   // valid pointers.
   //
@@ -126,6 +121,7 @@ bool Steens::run(Module &M) {
   // Loop over the rest of the module, merging graphs for non-external functions
   // into this graph.
   //
+  unsigned Count = 0;
   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
     if (!I->isExternal()) {
       hash_map<Value*, DSNodeHandle> ValMap;
@@ -147,6 +143,9 @@ bool Steens::run(Module &M) {
       for (hash_map<Value*, DSNodeHandle>::iterator I = ValMap.begin(),
              E = ValMap.end(); I != E; ++I)
         GVM[I->first].mergeWith(I->second);
+
+      if ((++Count & 1) == 0)   // Prune nodes out every other time...
+        ResultGraph->removeTriviallyDeadNodes();
     }
 
   // FIXME: Must recalculate and use the Incomplete markers!!
@@ -165,8 +164,12 @@ bool Steens::run(Module &M) {
     DSCallSite &CurCall = Calls[i];
     
     // Loop over the called functions, eliminating as many as possible...
-    std::vector<GlobalValue*> CallTargets =
-      CurCall.getCallee().getNode()->getGlobals();
+    std::vector<GlobalValue*> CallTargets;
+    if (CurCall.isDirectCall())
+      CallTargets.push_back(CurCall.getCalleeFunc());
+    else 
+      CallTargets = CurCall.getCalleeNode()->getGlobals();
+
     for (unsigned c = 0; c != CallTargets.size(); ) {
       // If we can eliminate this function call, do so!
       bool Eliminated = false;
@@ -175,15 +178,17 @@ bool Steens::run(Module &M) {
           ResolveFunctionCall(F, CurCall, RetValMap[F]);
           Eliminated = true;
         }
-      if (Eliminated)
-        CallTargets.erase(CallTargets.begin()+c);
-      else
+      if (Eliminated) {
+        CallTargets[c] = CallTargets.back();
+        CallTargets.pop_back();
+      } else
         ++c;  // Cannot eliminate this call, skip over it...
     }
 
-    if (CallTargets.empty())          // Eliminated all calls?
-      Calls.erase(Calls.begin()+i);   // Remove from call list...
-    else
+    if (CallTargets.empty()) {        // Eliminated all calls?
+      CurCall = Calls.back();         // Remove entry
+      Calls.pop_back();
+    } else
       ++i;                            // Skip this call site...
   }
 
@@ -214,10 +219,9 @@ AliasAnalysis::Result Steens::alias(const Value *V1, const Value *V2) {
       DSNodeHandle &V2H = J->second;
       // If the two pointers point to different data structure graph nodes, they
       // cannot alias!
-      if (V1H.getNode() != V2H.getNode()) {  // FIXME: Handle incompleteness!
-        ++NumNoAlias;
+      if (V1H.getNode() != V2H.getNode())    // FIXME: Handle incompleteness!
         return NoAlias;
-      }
+
       // FIXME: If the two pointers point to the same node, and the offsets are
       // different, and the LinkIndex vector doesn't alias the section, then the
       // two pointers do not alias.  We need access size information for the two
@@ -226,9 +230,6 @@ AliasAnalysis::Result Steens::alias(const Value *V1, const Value *V2) {
     }
   }
 
-  // Since Steensgaard cannot do any better, count it as a 'may alias'
-  ++NumMayAlias;
-
   // If we cannot determine alias properties based on our graph, fall back on
   // some other AA implementation.
   //