[PATCH] Use an obstack for graphds graph vertices and edges

[Richard Biener]

I've noticed quite some malloc/free load coming from graphds.
The following uses an obstack for both, simplifying freeing the
graph.  This reduces the allocator load by a constant factor
as well and eventually improves cache locality.  graphds users
may use the obstack to allocate auxiliar data they hang off
vertices and edges from as well (mainly the RDG code).

Bootstrap / regtest pending on x86_64-unknown-linux-gnu.

Richard.

2013-05-02  Richard Biener  <rguent...@suse.de>

        * graphds.h (struct graph): Add obstack member.
        * graphds.c (new_graph): Initialize obstack and allocate
        vertices from it.
        (add_edge): Allocate edge from the obstack.
        (free_graph): Free the obstack instead of all edges and
        vertices.

Index: gcc/graphds.c
===================================================================
*** gcc/graphds.c       (revision 198441)
--- gcc/graphds.c       (working copy)
*************** new_graph (int n_vertices)
*** 58,65 ****
  {
    struct graph *g = XNEW (struct graph);
  
    g->n_vertices = n_vertices;
!   g->vertices = XCNEWVEC (struct vertex, n_vertices);
  
    return g;
  }
--- 58,67 ----
  {
    struct graph *g = XNEW (struct graph);
  
+   gcc_obstack_init (&g->ob);
    g->n_vertices = n_vertices;
!   g->vertices = XOBNEWVEC (&g->ob, struct vertex, n_vertices);
!   memset (g->vertices, 0, sizeof (struct vertex) * n_vertices);
  
    return g;
  }
*************** new_graph (int n_vertices)
*** 69,78 ****
  struct graph_edge *
  add_edge (struct graph *g, int f, int t)
  {
!   struct graph_edge *e = XNEW (struct graph_edge);
    struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
  
- 
    e->src = f;
    e->dest = t;
  
--- 71,79 ----
  struct graph_edge *
  add_edge (struct graph *g, int f, int t)
  {
!   struct graph_edge *e = XOBNEW (&g->ob, struct graph_edge);
    struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
  
    e->src = f;
    e->dest = t;
  
*************** for_each_edge (struct graph *g, graphds_
*** 324,343 ****
  void
  free_graph (struct graph *g)
  {
!   struct graph_edge *e, *n;
!   struct vertex *v;
!   int i;
! 
!   for (i = 0; i < g->n_vertices; i++)
!     {
!       v = &g->vertices[i];
!       for (e = v->succ; e; e = n)
!       {
!         n = e->succ_next;
!         free (e);
!       }
!     }
!   free (g->vertices);
    free (g);
  }
  
--- 325,331 ----
  void
  free_graph (struct graph *g)
  {
!   obstack_free (&g->ob, NULL);
    free (g);
  }
  
Index: gcc/graphds.h
===================================================================
*** gcc/graphds.h       (revision 198441)
--- gcc/graphds.h       (working copy)
*************** struct vertex
*** 43,51 ****
  
  struct graph
  {
!   int n_vertices;     /* Number of vertices.  */
!   struct vertex *vertices;
!                       /* The vertices.  */
  };
  
  struct graph *new_graph (int);
--- 43,51 ----
  
  struct graph
  {
!   int n_vertices;        /* Number of vertices.  */
!   struct vertex *vertices; /* The vertices.  */
!   struct obstack ob;     /* Obstack for vertex and edge allocation.  */
  };
  
  struct graph *new_graph (int);