* Make some methods more const correct.

* Change the FunctionCalls and AuxFunctionCalls vectors into std::lists.
  This makes many operations on these lists much more natural, and avoids
  *exteremely* expensive copying of DSCallSites (e.g. moving nodes around
  between lists, erasing a node from not the end of the vector, etc).

With a profile build of analyze, this speeds up BU DS from 25.14s to
12.59s on 176.gcc.  I expect that it would help TD even more, but I don't
have data for it.

This effectively eliminates removeIdenticalCalls and children from the
profile, going from 6.53 to 0.27s.


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

12 files changed, 267 insertions, 231 deletions

diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h
index bc5f8242c1..49c71f0b3d 100644
--- a/include/llvm/Analysis/DataStructure/DSGraph.h
+++ b/include/llvm/Analysis/DataStructure/DSGraph.h
@@ -17,6 +17,7 @@
 
 #include "llvm/Analysis/DataStructure/DSNode.h"
 #include "llvm/ADT/hash_map"
+#include <list>
 
 namespace llvm {
 
@@ -136,19 +137,19 @@ private:
   //
   ReturnNodesTy ReturnNodes;
 
-  // FunctionCalls - This vector maintains a single entry for each call
+  // FunctionCalls - This list maintains a single entry for each call
   // instruction in the current graph.  The first entry in the vector is the
   // scalar that holds the return value for the call, the second is the function
   // scalar being invoked, and the rest are pointer arguments to the function.
   // This vector is built by the Local graph and is never modified after that.
   //
-  std::vector<DSCallSite> FunctionCalls;
+  std::list<DSCallSite> FunctionCalls;
 
   // AuxFunctionCalls - This vector contains call sites that have been processed
   // by some mechanism.  In pratice, the BU Analysis uses this vector to hold
   // the _unresolved_ call sites, because it cannot modify FunctionCalls.
   //
-  std::vector<DSCallSite> AuxFunctionCalls;
+  std::list<DSCallSite> AuxFunctionCalls;
 
   // InlinedGlobals - This set records which globals have been inlined from
   // other graphs (callers or callees, depending on the pass) into this one.
@@ -222,20 +223,30 @@ public:
   /// getFunctionCalls - Return the list of call sites in the original local
   /// graph...
   ///
-  const std::vector<DSCallSite> &getFunctionCalls() const {
-    return FunctionCalls;
-  }
+  const std::list<DSCallSite> &getFunctionCalls() const { return FunctionCalls;}
+  std::list<DSCallSite> &getFunctionCalls() { return FunctionCalls;}
 
   /// getAuxFunctionCalls - Get the call sites as modified by whatever passes
   /// have been run.
   ///
-  std::vector<DSCallSite> &getAuxFunctionCalls() {
-    return AuxFunctionCalls;
-  }
-  const std::vector<DSCallSite> &getAuxFunctionCalls() const {
+  std::list<DSCallSite> &getAuxFunctionCalls() { return AuxFunctionCalls; }
+  const std::list<DSCallSite> &getAuxFunctionCalls() const {
     return AuxFunctionCalls;
   }
 
+  // Function Call iteration
+  typedef std::list<DSCallSite>::const_iterator fc_iterator;
+  fc_iterator fc_begin() const { return FunctionCalls.begin(); }
+  fc_iterator fc_end() const { return FunctionCalls.end(); }
+
+
+  // Aux Function Call iteration
+  typedef std::list<DSCallSite>::const_iterator afc_iterator;
+  afc_iterator afc_begin() const { return AuxFunctionCalls.begin(); }
+  afc_iterator afc_end() const { return AuxFunctionCalls.end(); }
+
+
+
   /// getInlinedGlobals - Get the set of globals that are have been inlined
   /// (from callees in BU or from callers in TD) into the current graph.
   ///
diff --git a/include/llvm/Analysis/DataStructure/DSNode.h b/include/llvm/Analysis/DataStructure/DSNode.h
index 27e1a5077c..05e9cf641c 100644
--- a/include/llvm/Analysis/DataStructure/DSNode.h
+++ b/include/llvm/Analysis/DataStructure/DSNode.h
@@ -349,7 +349,7 @@ public:
   /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
   /// adds to the set, which allows it to only traverse visited nodes once.
   ///
-  void markReachableNodes(hash_set<DSNode*> &ReachableNodes);
+  void markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const;
 
 private:
   friend class DSNodeHandle;
diff --git a/include/llvm/Analysis/DataStructure/DSSupport.h b/include/llvm/Analysis/DataStructure/DSSupport.h
index 07fe159781..08bb3ee17e 100644
--- a/include/llvm/Analysis/DataStructure/DSSupport.h
+++ b/include/llvm/Analysis/DataStructure/DSSupport.h
@@ -289,7 +289,7 @@ public:
   /// DSNodes, marking any nodes which are reachable.  All reachable nodes it
   /// adds to the set, which allows it to only traverse visited nodes once.
   ///
-  void markReachableNodes(hash_set<DSNode*> &Nodes);
+  void markReachableNodes(hash_set<const DSNode*> &Nodes) const;
 
   bool operator<(const DSCallSite &CS) const {
     if (isDirectCall()) {      // This must sort by callee first!
diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp
index 5e6d5f39eb..0b4d5c1f58 100644
--- a/lib/Analysis/DataStructure/BottomUpClosure.cpp
+++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp
@@ -247,23 +247,23 @@ void BUDataStructures::releaseMemory() {
 void BUDataStructures::calculateGraph(DSGraph &Graph) {
   // Move our call site list into TempFCs so that inline call sites go into the
   // new call site list and doesn't invalidate our iterators!
-  std::vector<DSCallSite> TempFCs;
-  std::vector<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls();
+  std::list<DSCallSite> TempFCs;
+  std::list<DSCallSite> &AuxCallsList = Graph.getAuxFunctionCalls();
   TempFCs.swap(AuxCallsList);
 
   DSGraph::ReturnNodesTy &ReturnNodes = Graph.getReturnNodes();
 
   // Loop over all of the resolvable call sites
-  unsigned LastCallSiteIdx = ~0U;
-  for (DSCallSiteIterator I = DSCallSiteIterator::begin(TempFCs),
-         E = DSCallSiteIterator::end(TempFCs); I != E; ++I) {
-    // If we skipped over any call sites, they must be unresolvable, copy them
-    // to the real call site list.
-    LastCallSiteIdx++;
-    for (; LastCallSiteIdx < I.getCallSiteIdx(); ++LastCallSiteIdx)
-      AuxCallsList.push_back(TempFCs[LastCallSiteIdx]);
-    LastCallSiteIdx = I.getCallSiteIdx();
+  DSCallSiteIterator I = DSCallSiteIterator::begin(TempFCs);
+  DSCallSiteIterator E = DSCallSiteIterator::end(TempFCs);
+
+  // If DSCallSiteIterator skipped over any call sites, they are unresolvable:
+  // move them back to the AuxCallsList.
+  std::list<DSCallSite>::iterator LastCallSiteIdx = TempFCs.begin();
+  while (LastCallSiteIdx != I.getCallSiteIdx())
+    AuxCallsList.splice(AuxCallsList.end(), TempFCs, LastCallSiteIdx++);
     
+  while (I != E) {
     // Resolve the current call...
     Function *Callee = *I;
     DSCallSite CS = I.getCallSite();
@@ -301,11 +301,23 @@ void BUDataStructures::calculateGraph(DSGraph &Graph) {
                              Callee->getName());
 #endif
     }
-  }
 
-  // Make sure to catch any leftover unresolvable calls...
-  for (++LastCallSiteIdx; LastCallSiteIdx < TempFCs.size(); ++LastCallSiteIdx)
-    AuxCallsList.push_back(TempFCs[LastCallSiteIdx]);
+    LastCallSiteIdx = I.getCallSiteIdx();
+    ++I;  // Move to the next call site.
+
+    if (I.getCallSiteIdx() != LastCallSiteIdx) {
+      ++LastCallSiteIdx;   // Skip over the site we already processed.
+
+      // If there are call sites that get skipped over, move them to the aux
+      // calls list: they are not resolvable.
+      if (I != E)
+        while (LastCallSiteIdx != I.getCallSiteIdx())
+          AuxCallsList.splice(AuxCallsList.end(), TempFCs, LastCallSiteIdx++);
+      else
+        while (LastCallSiteIdx != TempFCs.end())
+          AuxCallsList.splice(AuxCallsList.end(), TempFCs, LastCallSiteIdx++);
+    }
+  }
 
   TempFCs.clear();
 
diff --git a/lib/Analysis/DataStructure/CompleteBottomUp.cpp b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
index 3cd2bb0eef..2dba93158f 100644
--- a/lib/Analysis/DataStructure/CompleteBottomUp.cpp
+++ b/lib/Analysis/DataStructure/CompleteBottomUp.cpp
@@ -49,20 +49,21 @@ bool CompleteBUDataStructures::runOnModule(Module &M) {
   // we hack it like this:
   for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
     if (MI->isExternal()) continue;
-    const std::vector<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
+    const std::list<DSCallSite> &CSs = TD.getDSGraph(*MI).getFunctionCalls();
 
-    for (unsigned CSi = 0, e = CSs.size(); CSi != e; ++CSi) {
-      Instruction *TheCall = CSs[CSi].getCallSite().getInstruction();
+    for (std::list<DSCallSite>::const_iterator CSI = CSs.begin(), E = CSs.end();
+         CSI != E; ++CSI) {
+      Instruction *TheCall = CSI->getCallSite().getInstruction();
 
-      if (CSs[CSi].isIndirectCall()) { // indirect call: insert all callees
+      if (CSI->isIndirectCall()) { // indirect call: insert all callees
         const std::vector<GlobalValue*> &Callees =
-          CSs[CSi].getCalleeNode()->getGlobals();
+          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()));
+                                            CSI->getCalleeFunc()));
       }
     }
   }
@@ -121,8 +122,8 @@ unsigned CompleteBUDataStructures::calculateSCCGraphs(DSGraph &FG,
   Stack.push_back(&FG);
 
   // The edges out of the current node are the call site targets...
-  for (unsigned i = 0, e = FG.getFunctionCalls().size(); i != e; ++i) {
-    Instruction *Call = FG.getFunctionCalls()[i].getCallSite().getInstruction();
+  for (DSGraph::fc_iterator CI = FG.fc_begin(), E = FG.fc_end(); CI != E; ++CI){
+    Instruction *Call = CI->getCallSite().getInstruction();
 
     // Loop over all of the actually called functions...
     ActualCalleesTy::iterator I, E;
@@ -183,8 +184,10 @@ void CompleteBUDataStructures::processGraph(DSGraph &G) {
   hash_set<Instruction*> calls;
 
   // The edges out of the current node are the call site targets...
-  for (unsigned i = 0, e = G.getFunctionCalls().size(); i != e; ++i) {
-    const DSCallSite &CS = G.getFunctionCalls()[i];
+  unsigned i = 0;
+  for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E;
+       ++CI, ++i) {
+    const DSCallSite &CS = *CI;
     Instruction *TheCall = CS.getCallSite().getInstruction();
 
     assert(calls.insert(TheCall).second &&
@@ -208,7 +211,8 @@ void CompleteBUDataStructures::processGraph(DSGraph &G) {
         G.mergeInGraph(CS, *CalleeFunc, GI, DSGraph::KeepModRefBits |
                        DSGraph::StripAllocaBit | DSGraph::DontCloneCallNodes |
                        DSGraph::DontCloneAuxCallNodes);
-        DEBUG(std::cerr << "    Inlining graph [" << i << "/" << e-1
+        DEBUG(std::cerr << "    Inlining graph [" << i << "/"
+              << G.getFunctionCalls().size()-1
               << ":" << TNum << "/" << Num-1 << "] for "
               << CalleeFunc->getName() << "["
               << GI.getGraphSize() << "+" << GI.getAuxFunctionCalls().size()
diff --git a/lib/Analysis/DataStructure/DSCallSiteIterator.h b/lib/Analysis/DataStructure/DSCallSiteIterator.h
index 1fcbc03bd8..bc51fcf3ca 100644
--- a/lib/Analysis/DataStructure/DSCallSiteIterator.h
+++ b/lib/Analysis/DataStructure/DSCallSiteIterator.h
@@ -23,18 +23,18 @@ namespace llvm {
 
 struct DSCallSiteIterator {
   // FCs are the edges out of the current node are the call site targets...
-  const std::vector<DSCallSite> *FCs;
-  unsigned CallSite;
+  std::list<DSCallSite> *FCs;
+  std::list<DSCallSite>::iterator CallSite;
   unsigned CallSiteEntry;
 
-  DSCallSiteIterator(const std::vector<DSCallSite> &CS) : FCs(&CS) {
-    CallSite = 0; CallSiteEntry = 0;
+  DSCallSiteIterator(std::list<DSCallSite> &CS) : FCs(&CS) {
+    CallSite = CS.begin(); CallSiteEntry = 0;
     advanceToValidCallee();
   }
 
-  // End iterator ctor...
-  DSCallSiteIterator(const std::vector<DSCallSite> &CS, bool) : FCs(&CS) {
-    CallSite = FCs->size(); CallSiteEntry = 0;
+  // End iterator ctor.
+  DSCallSiteIterator(std::list<DSCallSite> &CS, bool) : FCs(&CS) {
+    CallSite = CS.end(); CallSiteEntry = 0;
   }
 
   static bool isVAHackFn(const Function *F) {
@@ -52,13 +52,13 @@ struct DSCallSiteIterator {
   } 
 
   void advanceToValidCallee() {
-    while (CallSite < FCs->size()) {
-      if ((*FCs)[CallSite].isDirectCall()) {
+    while (CallSite != FCs->end()) {
+      if (CallSite->isDirectCall()) {
         if (CallSiteEntry == 0 &&        // direct call only has one target...
-            ! isUnresolvableFunc((*FCs)[CallSite].getCalleeFunc()))
+            ! isUnresolvableFunc(CallSite->getCalleeFunc()))
           return;                       // and not an unresolvable external func
       } else {
-        DSNode *CalleeNode = (*FCs)[CallSite].getCalleeNode();
+        DSNode *CalleeNode = CallSite->getCalleeNode();
         if (CallSiteEntry || isCompleteNode(CalleeNode)) {
           const std::vector<GlobalValue*> &Callees = CalleeNode->getGlobals();
           while (CallSiteEntry < Callees.size()) {
@@ -98,8 +98,8 @@ public:
   static DSCallSiteIterator end_std(DSGraph &G) {
     return DSCallSiteIterator(G.getFunctionCalls(), true);
   }
-  static DSCallSiteIterator begin(std::vector<DSCallSite> &CSs) { return CSs; }
-  static DSCallSiteIterator end(std::vector<DSCallSite> &CSs) {
+  static DSCallSiteIterator begin(std::list<DSCallSite> &CSs) { return CSs; }
+  static DSCallSiteIterator end(std::list<DSCallSite> &CSs) {
     return DSCallSiteIterator(CSs, true);
   }
   bool operator==(const DSCallSiteIterator &CSI) const {
@@ -109,14 +109,14 @@ public:
     return !operator==(CSI);
   }
 
-  unsigned getCallSiteIdx() const { return CallSite; }
-  const DSCallSite &getCallSite() const { return (*FCs)[CallSite]; }
+  std::list<DSCallSite>::iterator getCallSiteIdx() const { return CallSite; }
+  const DSCallSite &getCallSite() const { return *CallSite; }
 
   Function *operator*() const {
-    if ((*FCs)[CallSite].isDirectCall()) {
-      return (*FCs)[CallSite].getCalleeFunc();
+    if (CallSite->isDirectCall()) {
+      return CallSite->getCalleeFunc();
     } else {
-      DSNode *Node = (*FCs)[CallSite].getCalleeNode();
+      DSNode *Node = CallSite->getCalleeNode();
       return cast<Function>(Node->getGlobals()[CallSiteEntry]);
     }
   }
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 3860826d77..35d9c47d29 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -1201,19 +1201,15 @@ void DSGraph::cloneInto(const DSGraph &G, DSScalarMap &OldValMap,
   }
 
   if (!(CloneFlags & DontCloneCallNodes)) {
-    // Copy the function calls list...
-    unsigned FC = FunctionCalls.size();  // FirstCall
-    FunctionCalls.reserve(FC+G.FunctionCalls.size());
-    for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i)
-      FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap));
+    // Copy the function calls list.
+    for (fc_iterator I = G.fc_begin(), E = G.fc_end(); I != E; ++I)
+      FunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
   }
 
   if (!(CloneFlags & DontCloneAuxCallNodes)) {
-    // Copy the auxiliary function calls list...
-    unsigned FC = AuxFunctionCalls.size();  // FirstCall
-    AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size());
-    for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i)
-      AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap));
+    // Copy the auxiliary function calls list.
+    for (afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I)
+      AuxFunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
   }
 
   // Map the return node pointers over...
@@ -1289,20 +1285,14 @@ void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
 
     // If requested, copy all of the calls.
     if (!(CloneFlags & DontCloneCallNodes)) {
-      // Copy the function calls list...
-      FunctionCalls.reserve(FunctionCalls.size()+Graph.FunctionCalls.size());
-      for (unsigned i = 0, ei = Graph.FunctionCalls.size(); i != ei; ++i)
-        FunctionCalls.push_back(DSCallSite(Graph.FunctionCalls[i], RC));
+      // Copy the function calls list.
+      for (fc_iterator I = Graph.fc_begin(), E = Graph.fc_end(); I != E; ++I)
+        FunctionCalls.push_back(DSCallSite(*I, RC));
     }
 
     // If the user has us copying aux calls (the normal case), set up a data
     // structure to keep track of which ones we've copied over.
-    std::vector<bool> CopiedAuxCall;
-    if (!(CloneFlags & DontCloneAuxCallNodes)) {
-      AuxFunctionCalls.reserve(AuxFunctionCalls.size()+
-                               Graph.AuxFunctionCalls.size());
-      CopiedAuxCall.resize(Graph.AuxFunctionCalls.size());
-    }
+    std::set<const DSCallSite*> CopiedAuxCall;
     
     // Clone over all globals that appear in the caller and callee graphs.
     hash_set<GlobalVariable*> NonCopiedGlobals;
@@ -1341,17 +1331,15 @@ void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
 
       // If requested, copy any aux calls that can reach copied nodes.
       if (!(CloneFlags & DontCloneAuxCallNodes)) {
-        for (unsigned i = 0, ei = Graph.AuxFunctionCalls.size(); i != ei; ++i)
-          if (!CopiedAuxCall[i] &&
-              PathExistsToClonedNode(Graph.AuxFunctionCalls[i], RC)) {
-            AuxFunctionCalls.push_back(DSCallSite(Graph.AuxFunctionCalls[i],
-                                                  RC));
-            CopiedAuxCall[i] = true;
+        for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
+          if (CopiedAuxCall.insert(&*I).second &&
+              PathExistsToClonedNode(*I, RC)) {
+            AuxFunctionCalls.push_back(DSCallSite(*I, RC));
             MadeChange = true;
           }
       }
     }
-
+    
   } else {
     DSNodeHandle RetVal = getReturnNodeFor(F);
 
@@ -1458,7 +1446,7 @@ static void markIncomplete(DSCallSite &Call) {
 // added to the NodeType.
 //
 void DSGraph::markIncompleteNodes(unsigned Flags) {
-  // Mark any incoming arguments as incomplete...
+  // Mark any incoming arguments as incomplete.
   if (Flags & DSGraph::MarkFormalArgs)
     for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
          FI != E; ++FI) {
@@ -1469,14 +1457,15 @@ void DSGraph::markIncompleteNodes(unsigned Flags) {
             markIncompleteNode(getNodeForValue(I).getNode());
     }
 
-  // Mark stuff passed into functions calls as being incomplete...
+  // Mark stuff passed into functions calls as being incomplete.
   if (!shouldPrintAuxCalls())
-    for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
-      markIncomplete(FunctionCalls[i]);
+    for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(),
+           E = FunctionCalls.end(); I != E; ++I)
+      markIncomplete(*I);
   else
-    for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
-      markIncomplete(AuxFunctionCalls[i]);
-    
+    for (std::list<DSCallSite>::iterator I = AuxFunctionCalls.begin(),
+           E = AuxFunctionCalls.end(); I != E; ++I)
+      markIncomplete(*I);
 
   // Mark all global nodes as incomplete...
   if ((Flags & DSGraph::IgnoreGlobals) == 0)
@@ -1504,22 +1493,21 @@ static inline bool nodeContainsExternalFunction(const DSNode *N) {
   return false;
 }
 
-static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
+static void removeIdenticalCalls(std::list<DSCallSite> &Calls) {
   // Remove trivially identical function calls
-  unsigned NumFns = Calls.size();
-  std::sort(Calls.begin(), Calls.end());  // Sort by callee as primary key!
+  Calls.sort();  // Sort by callee as primary key!
 
-#if 1
   // Scan the call list cleaning it up as necessary...
   DSNode   *LastCalleeNode = 0;
   Function *LastCalleeFunc = 0;
   unsigned NumDuplicateCalls = 0;
   bool LastCalleeContainsExternalFunction = false;
 
-  std::vector<unsigned> CallsToDelete;
-
-  for (unsigned i = 0; i != Calls.size(); ++i) {
-    DSCallSite &CS = Calls[i];
+  unsigned NumDeleted = 0;
+  for (std::list<DSCallSite>::iterator I = Calls.begin(), E = Calls.end();
+       I != E;) {
+    DSCallSite &CS = *I;
+    std::list<DSCallSite>::iterator OldIt = I++;
 
     // If the Callee is a useless edge, this must be an unreachable call site,
     // eliminate it.
@@ -1529,78 +1517,106 @@ static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
 #ifndef NDEBUG
       std::cerr << "WARNING: Useless call site found.\n";
 #endif
-      CallsToDelete.push_back(i);
-    } else {
-      // If the return value or any arguments point to a void node with no
-      // information at all in it, and the call node is the only node to point
-      // to it, remove the edge to the node (killing the node).
-      //
-      killIfUselessEdge(CS.getRetVal());
-      for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
-        killIfUselessEdge(CS.getPtrArg(a));
+      Calls.erase(OldIt);
+      ++NumDeleted;
+      continue;
+    }
+
+    // If the return value or any arguments point to a void node with no
+    // information at all in it, and the call node is the only node to point
+    // to it, remove the edge to the node (killing the node).
+    //
+    killIfUselessEdge(CS.getRetVal());
+    for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
+      killIfUselessEdge(CS.getPtrArg(a));
+    
+#if 0
+    // If this call site calls the same function as the last call site, and if
+    // the function pointer contains an external function, this node will
+    // never be resolved.  Merge the arguments of the call node because no
+    // information will be lost.
+    //
+    if ((CS.isDirectCall()   && CS.getCalleeFunc() == LastCalleeFunc) ||
+        (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
+      ++NumDuplicateCalls;
+      if (NumDuplicateCalls == 1) {
+        if (LastCalleeNode)
+          LastCalleeContainsExternalFunction =
+            nodeContainsExternalFunction(LastCalleeNode);
+        else
+          LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
+      }
       
-      // If this call site calls the same function as the last call site, and if
-      // the function pointer contains an external function, this node will
-      // never be resolved.  Merge the arguments of the call node because no
-      // information will be lost.
-      //
-      if ((CS.isDirectCall()   && CS.getCalleeFunc() == LastCalleeFunc) ||
-          (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
-        ++NumDuplicateCalls;
-        if (NumDuplicateCalls == 1) {
-          if (LastCalleeNode)
-            LastCalleeContainsExternalFunction =
-              nodeContainsExternalFunction(LastCalleeNode);
-          else
-            LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
-        }
-     
-        // It is not clear why, but enabling this code makes DSA really
-        // sensitive to node forwarding.  Basically, with this enabled, DSA
-        // performs different number of inlinings based on which nodes are
-        // forwarding or not.  This is clearly a problem, so this code is
-        // disabled until this can be resolved.
+      // It is not clear why, but enabling this code makes DSA really
+      // sensitive to node forwarding.  Basically, with this enabled, DSA
+      // performs different number of inlinings based on which nodes are
+      // forwarding or not.  This is clearly a problem, so this code is
+      // disabled until this can be resolved.
 #if 1
-        if (LastCalleeContainsExternalFunction
+      if (LastCalleeContainsExternalFunction
 #if 0
-            ||
-            // This should be more than enough context sensitivity!
-            // FIXME: Evaluate how many times this is tripped!
-            NumDuplicateCalls > 20
+          ||
+          // This should be more than enough context sensitivity!
+          // FIXME: Evaluate how many times this is tripped!
+          NumDuplicateCalls > 20
 #endif
-            ) {
-          DSCallSite &OCS = Calls[i-1];
-          OCS.mergeWith(CS);
-          
-          // No need to keep this call anymore.
-          CallsToDelete.push_back(i);
-        }
+          ) {
+        
+        std::list<DSCallSite>::iterator PrevIt = OldIt;
+        --PrevIt;
+        PrevIt->mergeWith(CS);
+        
+        // No need to keep this call anymore.
+        Calls.erase(OldIt);
+        ++NumDeleted;
+        continue;
+      }
 #endif
+    } else {
+      if (CS.isDirectCall()) {
+        LastCalleeFunc = CS.getCalleeFunc();
+        LastCalleeNode = 0;
       } else {
-        if (CS.isDirectCall()) {
-          LastCalleeFunc = CS.getCalleeFunc();
-          LastCalleeNode = 0;
-        } else {
-          LastCalleeNode = CS.getCalleeNode();
-          LastCalleeFunc = 0;
-        }
-        NumDuplicateCalls = 0;
+        LastCalleeNode = CS.getCalleeNode();
+        LastCalleeFunc = 0;
       }
+      NumDuplicateCalls = 0;
     }
-  }
 #endif
 
-  unsigned NumDeleted = 0;
-  for (unsigned i = 0, e = CallsToDelete.size(); i != e; ++i)
-    Calls.erase(Calls.begin()+CallsToDelete[i]-NumDeleted++);
+    if (I != Calls.end() && CS == *I) {
+      Calls.erase(OldIt);
+      ++NumDeleted;
+      continue;
+    }
+  }
+
+  // Resort now that we simplified things.
+  Calls.sort();
+
+  // Now that we are in sorted order, eliminate duplicates.
+  std::list<DSCallSite>::iterator I = Calls.begin(), E = Calls.end();
+  if (I != E)
+    while (1) {
+      std::list<DSCallSite>::iterator OldIt = I++;
+      if (I == E) break;
+
+      // If this call site is now the same as the previous one, we can delete it
+      // as a duplicate.
+      if (*OldIt == *I) {
+        Calls.erase(I);
+        I = OldIt;
+        ++NumDeleted;
+      }
+    }
 
-  Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
+  //Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
 
   // Track the number of call nodes merged away...
-  NumCallNodesMerged += NumFns-Calls.size();
+  NumCallNodesMerged += NumDeleted;
 
-  DEBUG(if (NumFns != Calls.size())
-          std::cerr << "Merged " << (NumFns-Calls.size()) << " call nodes.\n";);
+  DEBUG(if (NumDeleted)
+          std::cerr << "Merged " << NumDeleted << " call nodes.\n";);
 }
 
 
@@ -1698,7 +1714,7 @@ void DSGraph::removeTriviallyDeadNodes() {
 /// DSNodes, marking any nodes which are reachable.  All reachable nodes it adds
 /// to the set, which allows it to only traverse visited nodes once.
 ///
-void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) {
+void DSNode::markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const {
   if (this == 0) return;
   assert(getForwardNode() == 0 && "Cannot mark a forwarded node!");
   if (ReachableNodes.insert(this).second)        // Is newly reachable?
@@ -1706,7 +1722,7 @@ void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) {
       getLink(i).getNode()->markReachableNodes(ReachableNodes);
 }
 
-void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) {
+void DSCallSite::markReachableNodes(hash_set<const DSNode*> &Nodes) const {
   getRetVal().getNode()->markReachableNodes(Nodes);
   if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);
   
@@ -1719,8 +1735,8 @@ void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) {
 // true, otherwise return false.  If an alive node is reachable, this node is
 // marked as alive...
 //
-static bool CanReachAliveNodes(DSNode *N, hash_set<DSNode*> &Alive,
-                               hash_set<DSNode*> &Visited,
+static bool CanReachAliveNodes(DSNode *N, hash_set<const DSNode*> &Alive,
+                               hash_set<const DSNode*> &Visited,
                                bool IgnoreGlobals) {
   if (N == 0) return false;
   assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!");
@@ -1749,8 +1765,9 @@ static bool CanReachAliveNodes(DSNode *N, hash_set<DSNode*> &Alive,
 // CallSiteUsesAliveArgs - Return true if the specified call site can reach any
 // alive nodes.
 //
-static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set<DSNode*> &Alive,
-                                  hash_set<DSNode*> &Visited,
+static bool CallSiteUsesAliveArgs(const DSCallSite &CS,
+                                  hash_set<const DSNode*> &Alive,
+                                  hash_set<const DSNode*> &Visited,
                                   bool IgnoreGlobals) {
   if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited,
                          IgnoreGlobals))
@@ -1783,7 +1800,7 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
   // FIXME: Merge non-trivially identical call nodes...
 
   // Alive - a set that holds all nodes found to be reachable/alive.
-  hash_set<DSNode*> Alive;
+  hash_set<const DSNode*> Alive;
   std::vector<std::pair<Value*, DSNode*> > GlobalNodes;
 
   // Copy and merge all information about globals to the GlobalsGraph if this is
@@ -1843,16 +1860,16 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
     I->second.getNode()->markReachableNodes(Alive);
 
   // Mark any nodes reachable by primary calls as alive...
-  for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
-    FunctionCalls[i].markReachableNodes(Alive);
+  for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
+    I->markReachableNodes(Alive);
 
 
   // Now find globals and aux call nodes that are already live or reach a live
   // value (which makes them live in turn), and continue till no more are found.
   // 
   bool Iterate;
-  hash_set<DSNode*> Visited;
-  std::vector<unsigned char> AuxFCallsAlive(AuxFunctionCalls.size());
+  hash_set<const DSNode*> Visited;
+  hash_set<const DSCallSite*> AuxFCallsAlive;
   do {
     Visited.clear();
     // If any global node points to a non-global that is "alive", the global is
@@ -1873,36 +1890,32 @@ void DSGraph::removeDeadNodes(unsigned Flags) {
     // call nodes that get resolved will be difficult to remove from that graph.
     // The final unresolved call nodes must be handled specially at the end of
     // the BU pass (i.e., in main or other roots of the call graph).
-    for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
-      if (!AuxFCallsAlive[i] &&
-          (AuxFunctionCalls[i].isIndirectCall()
-           || CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited,
+    for (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI)
+      if (AuxFCallsAlive.insert(&*CI).second &&
+          (CI->isIndirectCall()
+           || CallSiteUsesAliveArgs(*CI, Alive, Visited,
                                   Flags & DSGraph::RemoveUnreachableGlobals))) {
-        AuxFunctionCalls[i].markReachableNodes(Alive);
-        AuxFCallsAlive[i] = true;
+        CI->markReachableNodes(Alive);
         Iterate = true;
       }
   } while (Iterate);
 
   // Move dead aux function calls to the end of the list
   unsigned CurIdx = 0;
-  for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
-    if (AuxFCallsAlive[i])
-      AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]);
-
-  // Copy and merge all global nodes and dead aux call nodes into the
-  // GlobalsGraph, and all nodes reachable from those nodes
-  // 
-  if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
-    // Copy the unreachable call nodes to the globals graph, updating their
-    // target pointers using the GGCloner
-    for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i)
-      GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(AuxFunctionCalls[i],
-                                                          GGCloner));
-  }
-  // Crop all the useless ones out...
-  AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx,
-                         AuxFunctionCalls.end());
+  for (std::list<DSCallSite>::iterator CI = AuxFunctionCalls.begin(),
+         E = AuxFunctionCalls.end(); CI != E; )
+    if (AuxFCallsAlive.count(&*CI))
+      ++CI;
+    else {
+      // Copy and merge global nodes and dead aux call nodes into the
+      // GlobalsGraph, and all nodes reachable from those nodes.  Update their
+      // target pointers using the GGCloner.
+      // 
+      if (!(Flags & DSGraph::RemoveUnreachableGlobals))
+        GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner));
+
+      AuxFunctionCalls.erase(CI++);
+    }
 
   // We are finally done with the GGCloner so we can destroy it.
   GGCloner.destroy();
@@ -1962,12 +1975,12 @@ void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const {
 }
 
 void DSGraph::AssertCallNodesInGraph() const {
-  for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
-    AssertCallSiteInGraph(FunctionCalls[i]);
+  for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
+    AssertCallSiteInGraph(*I);
 }
 void DSGraph::AssertAuxCallNodesInGraph() const {
-  for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
-    AssertCallSiteInGraph(AuxFunctionCalls[i]);
+  for (afc_iterator I = afc_begin(), E = afc_end(); I != E; ++I)
+    AssertCallSiteInGraph(*I);
 }
 
 void DSGraph::AssertGraphOK() const {
diff --git a/lib/Analysis/DataStructure/DataStructureStats.cpp b/lib/Analysis/DataStructure/DataStructureStats.cpp
index 330362ee8f..3f8b6a93b8 100644
--- a/lib/Analysis/DataStructure/DataStructureStats.cpp
+++ b/lib/Analysis/DataStructure/DataStructureStats.cpp
@@ -75,19 +75,19 @@ static bool isIndirectCallee(Value *V) {
 void DSGraphStats::countCallees(const Function& F) {
   unsigned numIndirectCalls = 0, totalNumCallees = 0;