Abstract out the Nodes collection. Instead of providing a getNodes() method,

[oota-llvm.git] / include / llvm / Analysis / DataStructure / DSGraph.h

diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h
index b4dcb51ec88ca35f33db3fd691c1aaf3ff07a76f..7e19212abefbcfa6c890a0a9261d1b5bd96ffa3a 100644 (file)
--- a/include/llvm/Analysis/DataStructure/DSGraph.h
+++ b/include/llvm/Analysis/DataStructure/DSGraph.h
@@ -21,14 +21,78 @@ namespace llvm {
 
 class GlobalValue;
 
+//===----------------------------------------------------------------------===//
+/// DSScalarMap - An instance of this class is used to keep track of all of 
+/// which DSNode each scalar in a function points to.  This is specialized to
+/// keep track of globals with nodes in the function, and to keep track of the 
+/// unique DSNodeHandle being used by the scalar map.
+///
+/// This class is crucial to the efficiency of DSA with some large SCC's.  In 
+/// these cases, the cost of iterating over the scalar map dominates the cost
+/// of DSA.  In all of these cases, the DSA phase is really trying to identify 
+/// globals or unique node handles active in the function.
+///
+class DSScalarMap {
+  typedef hash_map<Value*, DSNodeHandle> ValueMapTy;
+  ValueMapTy ValueMap;
+
+  typedef hash_set<GlobalValue*> GlobalSetTy;
+  GlobalSetTy GlobalSet;
+public:
+
+  // Compatibility methods: provide an interface compatible with a map of 
+  // Value* to DSNodeHandle's.
+  typedef ValueMapTy::const_iterator const_iterator;
+  typedef ValueMapTy::iterator iterator;
+  iterator begin() { return ValueMap.begin(); }
+  iterator end()   { return ValueMap.end(); }
+  const_iterator begin() const { return ValueMap.begin(); }
+  const_iterator end() const { return ValueMap.end(); }
+  iterator find(Value *V) { return ValueMap.find(V); }
+  const_iterator find(Value *V) const { return ValueMap.find(V); }
+  unsigned count(Value *V) const { return ValueMap.count(V); }
+
+  void erase(Value *V) { erase(find(V)); }
+
+  DSNodeHandle &operator[](Value *V) {
+    std::pair<iterator,bool> IP = 
+      ValueMap.insert(std::make_pair(V, DSNodeHandle()));
+    if (IP.second) {  // Inserted the new entry into the map.
+      if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
+        GlobalSet.insert(GV);
+    }
+    return IP.first->second;
+  }
+
+  void erase(iterator I) { 
+    assert(I != ValueMap.end() && "Cannot erase end!");
+    if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first))
+      GlobalSet.erase(GV);
+    ValueMap.erase(I); 
+  }
+
+  void clear() {
+    ValueMap.clear();
+    GlobalSet.clear();
+  }
+
+  // Access to the global set: the set of all globals currently in the
+  // scalar map.
+  typedef GlobalSetTy::const_iterator global_iterator;
+  global_iterator global_begin() const { return GlobalSet.begin(); }
+  global_iterator global_end() const { return GlobalSet.end(); }
+};
+
+
 //===----------------------------------------------------------------------===//
 /// DSGraph - The graph that represents a function.
 ///
 struct DSGraph {
   // Public data-type declarations...
-  typedef hash_map<Value*, DSNodeHandle> ScalarMapTy;
+  typedef DSScalarMap ScalarMapTy;
   typedef hash_map<Function*, DSNodeHandle> ReturnNodesTy;
   typedef hash_set<GlobalValue*> GlobalSetTy;
+  typedef std::vector<DSNode*> NodeListTy;
 
   /// NodeMapTy - This data type is used when cloning one graph into another to
   /// keep track of the correspondence between the nodes in the old and new
@@ -38,7 +102,7 @@ private:
   DSGraph *GlobalsGraph;   // Pointer to the common graph of global objects
   bool PrintAuxCalls;      // Should this graph print the Aux calls vector?
 
-  std::vector<DSNode*> Nodes;
+  NodeListTy Nodes;
   ScalarMapTy ScalarMap;
 
   // ReturnNodes - A return value for every function merged into this graph.
@@ -107,8 +171,9 @@ public:
 
   /// getNodes - Get a vector of all the nodes in the graph
   /// 
-  const std::vector<DSNode*> &getNodes() const { return Nodes; }
-        std::vector<DSNode*> &getNodes()       { return Nodes; }
+  typedef NodeListTy::const_iterator node_iterator;
+  node_iterator node_begin() const { return Nodes.begin(); }
+  node_iterator node_end()   const { return Nodes.end(); }
 
   /// getFunctionNames - Return a space separated list of the name of the
   /// functions in this graph (if any)