[RFA][lto merge]: support for cgraph node sets

[Diego Novillo <dnovillo at google dot com>]

This patch adds support for creating callgraph node sets.  This
is used during LTO compilation to partition the callgraph into
subsets for work distribution.

This feature is currently not exercised in mainline, but I would
like to merge it early to avoid too much code drift with the
other changes coming in from pretty-ipa and other ipa work.

Jan, are you OK with this?

Tested on x86_64.


Diego.


	Merge from lto branch

	2008-08-27  Doug Kwan  <dougkwan@google.com>

		* cgraph.c (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.
		* 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.

Index: cgraph.c
===================================================================
--- cgraph.c	(revision 146277)
+++ cgraph.c	(working copy)
@@ -1527,4 +1527,172 @@ cgraph_add_new_function (tree fndecl, bo
     }
 }

+/*
+ * A call-graph set is a collection of call-graph nodes.  A node can
+ * appear in multiple sets.  Call-graph sets are garbage-collected.
+ */
+
+/* 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)
+    {
+#ifdef ENABLE_CHECKING
+      element = (cgraph_node_set_element) *slot;
+      gcc_assert (node == element->node
+		  && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
+		      == node));
+#endif
+      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;
+#ifdef ENABLE_CHECKING
+  gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
+	      == node);
+#endif
+
+  /* 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;
+#ifdef ENABLE_CHECKING
+      gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
+		  == node);
+#endif
+      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);
+}
+
 #include "gt-cgraph.h"
Index: cgraph.h
===================================================================
--- cgraph.h	(revision 146277)
+++ cgraph.h	(working copy)
@@ -189,6 +189,12 @@ struct cgraph_node GTY((chain_next ("%h.
   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);
+
 #define DEFCIFCODE(code, string)	CIF_ ## code,
 /* Reasons for inlining failures.  */
 typedef enum {
@@ -302,6 +308,40 @@ extern GTY(()) struct cgraph_node *cgrap
 extern GTY(()) struct cgraph_asm_node *cgraph_asm_nodes;
 extern GTY(()) int cgraph_order;

+/* 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;
+
+typedef struct
+{
+  cgraph_node_set set;
+  unsigned index;
+} cgraph_node_set_iterator;
+
 /* In cgraph.c  */
 void dump_cgraph (FILE *);
 void debug_cgraph (void);
@@ -341,6 +381,69 @@ enum availability cgraph_function_body_a
 void cgraph_add_new_function (tree, bool);
 const char* cgraph_inline_failed_string (cgraph_inline_failed_t);

+cgraph_node_set cgraph_node_set_new (void);
+cgraph_node_set_iterator cgraph_node_set_find (cgraph_node_set set,
+					       struct cgraph_node *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 *f, cgraph_node_set);
+void debug_cgraph_node_set (cgraph_node_set);
+const char *cgraph_inline_failed_string (cgraph_inline_failed_t);
+
+/* 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);
+}
+
 /* In cgraphunit.c  */
 void cgraph_finalize_function (tree, bool);
 void cgraph_mark_if_needed (tree);
Index: tree-pass.h
===================================================================
--- tree-pass.h	(revision 146277)
+++ tree-pass.h	(working copy)
@@ -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