cgraph.h (cgraph_node_ptr): New type for vector functions.

	* cgraph.h (cgraph_node_ptr): New type for vector functions.
	(struct cgraph_node_set_def): New type.
	(cgraph_node_set) New type. Also declare vector functions.
	(struct cgraph_node_set_element_def): New type.
	(cgraph_node_set_element): Ditto.
	(cgraph_node_set_iterator): New iterator type.
	(cgraph_node_set_new, cgraph_node_set_find, cgraph_node_set_add,
	cgraph_node_set_remove, dump_cgraph_node_set,
	debug_cgraph_node_set): New prototypes.
	(csi_end_p, csi_next, csi_node, csi_start, cgraph_node_in_set_p,
	cgraph_node_set_size): New inlines.
	* tree-pass.h (struct cgraph_node_set_def): New decl to avoid
	including cgraph.h.
	(struct ipa_opt_pass): Add struct cgraph_node_set_def
	argument to function 'write_summary'.
	* ipa.c: Include ggc.h.
	(hash_cgraph_node_set_element,
	eq_cgraph_node_set_element, cgraph_node_set_new,
	cgraph_node_set_add, cgraph_node_set_remove,
	cgraph_node_set_find, dump_cgraph_node_set,
	debug_cgraph_node_set): New functions.
	* Makefile.in (ipa.o): Add dependency on GGC_H.

From-SVN: r146418

5 files changed, 286 insertions, 3 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 7d962a6..a25d3b0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,28 @@
+2009-04-20  Doug Kwan  <dougkwan@google.com>
+
+	* cgraph.h (cgraph_node_ptr): New type for vector functions.
+	(struct cgraph_node_set_def): New type.
+	(cgraph_node_set) New type. Also declare vector functions.
+	(struct cgraph_node_set_element_def): New type.
+	(cgraph_node_set_element): Ditto.
+	(cgraph_node_set_iterator): New iterator type.
+	(cgraph_node_set_new, cgraph_node_set_find, cgraph_node_set_add,
+	cgraph_node_set_remove, dump_cgraph_node_set,
+	debug_cgraph_node_set): New prototypes.
+	(csi_end_p, csi_next, csi_node, csi_start, cgraph_node_in_set_p,
+	cgraph_node_set_size): New inlines.
+	* tree-pass.h (struct cgraph_node_set_def): New decl to avoid
+	including cgraph.h.
+	(struct ipa_opt_pass): Add struct cgraph_node_set_def
+	argument to function 'write_summary'.
+	* ipa.c: Include ggc.h.
+	(hash_cgraph_node_set_element,
+	eq_cgraph_node_set_element, cgraph_node_set_new,
+	cgraph_node_set_add, cgraph_node_set_remove,
+	cgraph_node_set_find, dump_cgraph_node_set,
+	debug_cgraph_node_set): New functions.
+	* Makefile.in (ipa.o): Add dependency on GGC_H.
+
 2009-04-20  Ira Rosen  <irar@il.ibm.com>
 
 	PR tree-optimization/39675
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 398c096..32ea68e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -2624,7 +2624,7 @@ varpool.o : varpool.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(GGC_H) $(TIMEVAR_H) debug.h $(TARGET_H) output.h $(GIMPLE_H) \
    $(TREE_FLOW_H) gt-varpool.h
 ipa.o : ipa.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(CGRAPH_H) \
-   $(TREE_PASS_H) $(TIMEVAR_H)
+   $(TREE_PASS_H) $(TIMEVAR_H) $(GGC_H)
 ipa-prop.o : ipa-prop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
    langhooks.h $(GGC_H) $(TARGET_H) $(CGRAPH_H) $(IPA_PROP_H) $(DIAGNOSTIC_H) \
    $(TREE_FLOW_H) $(TM_H) $(TREE_PASS_H) $(FLAGS_H) $(TREE_H) \
diff --git a/gcc/cgraph.h b/gcc/cgraph.h
index 347653f..984d727 100644
--- a/gcc/cgraph.h
+++ b/gcc/cgraph.h
@@ -189,6 +189,45 @@ struct cgraph_node GTY((chain_next ("%h.next"), chain_prev ("%h.previous")))
   tree inline_decl;
 };
 
+typedef struct cgraph_node *cgraph_node_ptr;
+
+DEF_VEC_P(cgraph_node_ptr);
+DEF_VEC_ALLOC_P(cgraph_node_ptr,heap);
+DEF_VEC_ALLOC_P(cgraph_node_ptr,gc);
+
+/* A cgraph node set is a collection of cgraph nodes.  A cgraph node
+   can appear in multiple sets.  */
+struct cgraph_node_set_def GTY(())
+{
+  htab_t GTY((param_is (struct cgraph_node_set_element_def))) hashtab;
+  VEC(cgraph_node_ptr, gc) *nodes;
+  PTR GTY ((skip)) aux;
+};
+
+typedef struct cgraph_node_set_def *cgraph_node_set;
+
+DEF_VEC_P(cgraph_node_set);
+DEF_VEC_ALLOC_P(cgraph_node_set,gc);
+DEF_VEC_ALLOC_P(cgraph_node_set,heap);
+
+/* A cgraph node set element contains an index in the vector of nodes in
+   the set.  */
+struct cgraph_node_set_element_def GTY(())
+{
+  struct cgraph_node *node;
+  HOST_WIDE_INT index;
+};
+
+typedef struct cgraph_node_set_element_def *cgraph_node_set_element;
+typedef const struct cgraph_node_set_element_def *const_cgraph_node_set_element;
+
+/* Iterator structure for cgraph node sets.  */
+typedef struct
+{
+  cgraph_node_set set;
+  unsigned index;
+} cgraph_node_set_iterator;
+
 #define DEFCIFCODE(code, string)	CIF_ ## code,
 /* Reasons for inlining failures.  */
 typedef enum {
@@ -397,11 +436,19 @@ int compute_call_stmt_bb_frequency (basic_block bb);
 /* In ipa.c  */
 bool cgraph_remove_unreachable_nodes (bool, FILE *);
 int cgraph_postorder (struct cgraph_node **);
+cgraph_node_set cgraph_node_set_new (void);
+cgraph_node_set_iterator cgraph_node_set_find (cgraph_node_set,
+					       struct cgraph_node *);
+void cgraph_node_set_add (cgraph_node_set, struct cgraph_node *);
+void cgraph_node_set_remove (cgraph_node_set, struct cgraph_node *);
+void dump_cgraph_node_set (FILE *, cgraph_node_set);
+void debug_cgraph_node_set (cgraph_node_set);
+
 
+/* In predict.c  */
 bool cgraph_maybe_hot_edge_p (struct cgraph_edge *e);
 
 /* In varpool.c  */
-
 extern GTY(()) struct varpool_node *varpool_nodes_queue;
 extern GTY(()) struct varpool_node *varpool_nodes;
 
@@ -466,4 +513,54 @@ unsigned int compute_inline_parameters (struct cgraph_node *);
 /* Create a new static variable of type TYPE.  */
 tree add_new_static_var (tree type);
 
+
+/* Return true if iterator CSI points to nothing.  */
+static inline bool
+csi_end_p (cgraph_node_set_iterator csi)
+{
+  return csi.index >= VEC_length (cgraph_node_ptr, csi.set->nodes);
+}
+
+/* Advance iterator CSI.  */
+static inline void
+csi_next (cgraph_node_set_iterator *csi)
+{
+  csi->index++;
+}
+
+/* Return the node pointed to by CSI.  */
+static inline struct cgraph_node *
+csi_node (cgraph_node_set_iterator csi)
+{
+  return VEC_index (cgraph_node_ptr, csi.set->nodes, csi.index);
+}
+
+/* Return an iterator to the first node in SET.  */
+static inline cgraph_node_set_iterator
+csi_start (cgraph_node_set set)
+{
+  cgraph_node_set_iterator csi;
+
+  csi.set = set;
+  csi.index = 0;
+  return csi;
+}
+
+/* Return true if SET contains NODE.  */
+static inline bool
+cgraph_node_in_set_p (struct cgraph_node *node, cgraph_node_set set)
+{
+  cgraph_node_set_iterator csi;
+  csi = cgraph_node_set_find (set, node);
+  return !csi_end_p (csi);
+}
+
+/* Return number of nodes in SET.  */
+static inline size_t
+cgraph_node_set_size (cgraph_node_set set)
+{
+  return htab_elements (set->hashtab);
+}
+
+
 #endif  /* GCC_CGRAPH_H  */
diff --git a/gcc/ipa.c b/gcc/ipa.c
index 0e2cb2d..b486b93 100644
--- a/gcc/ipa.c
+++ b/gcc/ipa.c
@@ -25,6 +25,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "cgraph.h"
 #include "tree-pass.h"
 #include "timevar.h"
+#include "ggc.h"
 
 /* Fill array order with all nodes with output flag set in the reverse
    topological order.  */
@@ -285,3 +286,162 @@ struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
  }
 };
+
+
+/* Hash a cgraph node set element.  */
+
+static hashval_t
+hash_cgraph_node_set_element (const void *p)
+{
+  const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
+  return htab_hash_pointer (element->node);
+}
+
+/* Compare two cgraph node set elements.  */
+
+static int
+eq_cgraph_node_set_element (const void *p1, const void *p2)
+{
+  const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
+  const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
+
+  return e1->node == e2->node;
+}
+
+/* Create a new cgraph node set.  */
+
+cgraph_node_set
+cgraph_node_set_new (void)
+{
+  cgraph_node_set new_node_set;
+
+  new_node_set = GGC_NEW (struct cgraph_node_set_def);
+  new_node_set->hashtab = htab_create_ggc (10,
+					   hash_cgraph_node_set_element,
+					   eq_cgraph_node_set_element,
+					   NULL);
+  new_node_set->nodes = NULL;
+  return new_node_set;
+}
+
+/* Add cgraph_node NODE to cgraph_node_set SET.  */
+
+void
+cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
+{
+  void **slot;
+  cgraph_node_set_element element;
+  struct cgraph_node_set_element_def dummy;
+
+  dummy.node = node;
+  slot = htab_find_slot (set->hashtab, &dummy, INSERT);
+
+  if (*slot != HTAB_EMPTY_ENTRY)
+    {
+      element = (cgraph_node_set_element) *slot;
+      gcc_assert (node == element->node
+		  && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
+		      == node));
+      return;
+    }
+
+  /* Insert node into hash table.  */
+  element =
+    (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
+  element->node = node;
+  element->index = VEC_length (cgraph_node_ptr, set->nodes);
+  *slot = element;
+
+  /* Insert into node vector.  */
+  VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
+}
+
+/* Remove cgraph_node NODE from cgraph_node_set SET.  */
+
+void
+cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
+{
+  void **slot, **last_slot;
+  cgraph_node_set_element element, last_element;
+  struct cgraph_node *last_node;
+  struct cgraph_node_set_element_def dummy;
+
+  dummy.node = node;
+  slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
+  if (slot == NULL)
+    return;
+
+  element = (cgraph_node_set_element) *slot;
+  gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
+	      == node);
+
+  /* Remove from vector. We do this by swapping node with the last element
+     of the vector.  */
+  last_node = VEC_pop (cgraph_node_ptr, set->nodes);
+  if (last_node != node)
+    {
+      dummy.node = last_node;
+      last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
+      last_element = (cgraph_node_set_element) *last_slot;
+      gcc_assert (last_element);
+
+      /* Move the last element to the original spot of NODE.  */
+      last_element->index = element->index;
+      VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
+		   last_node);
+    }
+  
+  /* Remove element from hash table.  */
+  htab_clear_slot (set->hashtab, slot);
+  ggc_free (element);
+}
+
+/* Find NODE in SET and return an iterator to it if found.  A null iterator
+   is returned if NODE is not in SET.  */
+
+cgraph_node_set_iterator
+cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
+{
+  void **slot;
+  struct cgraph_node_set_element_def dummy;
+  cgraph_node_set_element element;
+  cgraph_node_set_iterator csi;
+
+  dummy.node = node;
+  slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
+  if (slot == NULL)
+    csi.index = (unsigned) ~0;
+  else
+    {
+      element = (cgraph_node_set_element) *slot;
+      gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
+		  == node);
+      csi.index = element->index;
+    }
+  csi.set = set;
+
+  return csi;
+}
+
+/* Dump content of SET to file F.  */
+
+void
+dump_cgraph_node_set (FILE *f, cgraph_node_set set)
+{
+  cgraph_node_set_iterator iter;
+
+  for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
+    {
+      struct cgraph_node *node = csi_node (iter);
+      dump_cgraph_node (f, node);
+    }
+}
+
+/* Dump content of SET to stderr.  */
+
+void
+debug_cgraph_node_set (cgraph_node_set set)
+{
+  dump_cgraph_node_set (stderr, set);
+}
+
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index f0ae58a..c74ed1b 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -155,6 +155,7 @@ struct rtl_opt_pass
 
 struct varpool_node;
 struct cgraph_node;
+struct cgraph_node_set_def;
 
 /* Description of IPA pass with generate summary, write, execute, read and
    transform stages.  */
@@ -167,7 +168,7 @@ struct ipa_opt_pass
   void (*generate_summary) (void);
 
   /* This hook is used to serialize IPA summaries on disk.  */
-  void (*write_summary) (void);
+  void (*write_summary) (struct cgraph_node_set_def *);
 
   /* For most ipa passes, the information can only be deserialized in
      one chunk.  However, function bodies are read function at a time