Initially I had one obstack per struct graph, which was better than using
XNEW for every edge, but still obstack_init() called from new_graph() was
too frequent.
So in this iteration of the patch the obstack is static global,
initialised once and never freed. Please advise on whether this is
acceptable, and also where I should initialise the obstack once, and avoid
checking if it's NULL in every use.
Minor speed gains (couple of ms), tested with pre-C++ conversion snapshot,
I'll retest soon and post update.
Thanks,
Dimitris
2012-08-18 Dimitrios Apostolou <ji...@gmx.net>
* gcc/graphds.h: Guarded the header file. Included libiberty.h and
obstack.h.
(graph_obstack): New static obstack to allocate graphs and
graph_edges from.
(new_graph, add_edge): Add obstack argument.
(free_graph): Remove.
* gcc/graphds.c (new_graph): Allocate graph, vertices from obstack.
(add_edge): Allocate edge from obstack.
(free_graph): Remove, all graph data is now freed when freeing the
object in the obstack.
* gcc/tree-data-ref.h (free_rdg): Same.
(build_empty_rdg): Add obstack argument.
* gcc/cfgloopanal.c (mark_irreducible_loops): Initialise obstack
if it's not, use it for graph allocations.
* gcc/dominance.c (iterate_fix_dominators): Same.
* gcc/graphite-sese-to-poly.c (build_alias_set_optimal_p)
(build_base_obj_set_for_drs): Same.
* gcc/tree-data-ref.c (rdg_vertex_for_stmt)
(create_rdg_edge_for_ddr, create_rdg_edges_for_scalar)
(create_rdg_edges, create_rdg_vertices)
(known_dependences_p,build_empty_rdg, build_rdg, free_rdg): Same.
* gcc/tree-loop-distribution.c (distribute_loop): Same.
=== modified file 'gcc/cfgloopanal.c'
--- gcc/cfgloopanal.c 2012-05-31 20:19:00 +0000
+++ gcc/cfgloopanal.c 2012-08-18 16:43:02 +0000
@@ -93,8 +93,14 @@ mark_irreducible_loops (void)
e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
}
+ if (graph_obstack == NULL)
+ {
+ graph_obstack = XNEW (struct obstack);
+ obstack_init (graph_obstack);
+ }
+
/* Create the edge lists. */
- g = new_graph (last_basic_block + num);
+ g = new_graph (last_basic_block + num, graph_obstack);
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
FOR_EACH_EDGE (e, ei, act->succs)
@@ -134,7 +140,7 @@ mark_irreducible_loops (void)
src = LOOP_REPR (cloop);
}
- add_edge (g, src, dest)->data = e;
+ add_edge (g, src, dest, graph_obstack)->data = e;
}
/* Find the strongly connected components. */
@@ -161,7 +167,8 @@ mark_irreducible_loops (void)
real->src->flags |= BB_IRREDUCIBLE_LOOP;
}
- free_graph (g);
+ /* Destroy all data allocated for the graph. */
+ XOBDELETE (graph_obstack, g);
loops_state_set (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS);
return irred_loop_found;
=== modified file 'gcc/dominance.c'
--- gcc/dominance.c 2012-08-14 15:59:41 +0000
+++ gcc/dominance.c 2012-08-18 16:43:02 +0000
@@ -1341,7 +1341,13 @@ iterate_fix_dominators (enum cdi_directi
}
*pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
- g = new_graph (n + 1);
+ if (graph_obstack == NULL)
+ {
+ graph_obstack = XNEW (struct obstack);
+ obstack_init (graph_obstack);
+ }
+
+ g = new_graph (n + 1, graph_obstack);
for (y = 0; y < g->n_vertices; y++)
g->vertices[y].data = BITMAP_ALLOC (NULL);
FOR_EACH_VEC_ELT (basic_block, bbs, i, bb)
@@ -1358,7 +1364,7 @@ iterate_fix_dominators (enum cdi_directi
if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
continue;
- add_edge (g, dom_i, i);
+ add_edge (g, dom_i, i, graph_obstack);
}
}
for (y = 0; y < g->n_vertices; y++)
@@ -1392,7 +1398,8 @@ iterate_fix_dominators (enum cdi_directi
free (brother);
free (parent);
- free_graph (g);
+ /* Destroy all data allocated for the graph. */
+ XOBDELETE (graph_obstack, g);
}
void
=== modified file 'gcc/graphds.c'
--- gcc/graphds.c 2009-11-25 10:55:54 +0000
+++ gcc/graphds.c 2012-08-18 16:43:02 +0000
@@ -53,28 +53,29 @@ dump_graph (FILE *f, struct graph *g)
}
}
-/* Creates a new graph with N_VERTICES vertices. */
+/* Creates a new graph with N_VERTICES vertices from obstack O. */
struct graph *
-new_graph (int n_vertices)
+new_graph (int n_vertices, struct obstack *o)
{
- struct graph *g = XNEW (struct graph);
+ struct graph *g = XOBNEW (o, struct graph);
g->n_vertices = n_vertices;
- g->vertices = XCNEWVEC (struct vertex, n_vertices);
+ g->vertices = XOBNEWVEC (o, struct vertex, n_vertices);
+ memset (g->vertices, 0, n_vertices * sizeof (*g->vertices));
return g;
}
-/* Adds an edge from F to T to graph G. The new edge is returned. */
+/* Adds an edge from F to T to graph G. Allocations are from obstack O. The
+ new edge is returned. */
struct graph_edge *
-add_edge (struct graph *g, int f, int t)
+add_edge (struct graph *g, int f, int t, struct obstack *o)
{
- struct graph_edge *e = XNEW (struct graph_edge);
+ struct graph_edge *e = XOBNEW (o, struct graph_edge);
struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
-
e->src = f;
e->dest = t;
@@ -321,28 +322,6 @@ for_each_edge (struct graph *g, graphds_
callback (g, e);
}
-/* Releases the memory occupied by G. */
-
-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);
-}
-
/* Returns the nearest common ancestor of X and Y in tree whose parent
links are given by PARENT. MARKS is the array used to mark the
vertices of the tree, and MARK is the number currently used as a mark. */
=== modified file 'gcc/graphds.h'
--- gcc/graphds.h 2009-02-20 15:20:38 +0000
+++ gcc/graphds.h 2012-08-18 17:18:30 +0000
@@ -18,6 +18,11 @@ You should have received a copy of the G
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
+#ifndef GRAPHDS_H
+#define GRAPHDS_H
+
+#include "obstack.h"
+
/* Structure representing edge of a graph. */
struct graph_edge
@@ -28,6 +33,8 @@ struct graph_edge
void *data; /* Data attached to the edge. */
};
+static struct obstack *graph_obstack ATTRIBUTE_UNUSED;
+
/* Structure representing vertex of a graph. */
struct vertex
@@ -50,9 +57,9 @@ struct graph
htab_t indices; /* Fast lookup for indices. */
};
-struct graph *new_graph (int);
+struct graph *new_graph (int, struct obstack *);
void dump_graph (FILE *, struct graph *);
-struct graph_edge *add_edge (struct graph *, int, int);
+struct graph_edge *add_edge (struct graph *, int, int, struct obstack *);
void identify_vertices (struct graph *, int, int);
int graphds_dfs (struct graph *, int *, int,
VEC (int, heap) **, bool, bitmap);
@@ -60,4 +67,5 @@ int graphds_scc (struct graph *, bitmap)
void graphds_domtree (struct graph *, int, int *, int *, int *);
typedef void (*graphds_edge_callback) (struct graph *, struct graph_edge *);
void for_each_edge (struct graph *, graphds_edge_callback);
-void free_graph (struct graph *g);
+
+#endif /* GRAPHDS_H */
=== modified file 'gcc/graphite-sese-to-poly.c'
--- gcc/graphite-sese-to-poly.c 2012-08-16 14:27:51 +0000
+++ gcc/graphite-sese-to-poly.c 2012-08-18 16:43:02 +0000
@@ -1719,7 +1719,7 @@ static int
build_alias_set_optimal_p (VEC (data_reference_p, heap) *drs)
{
int num_vertices = VEC_length (data_reference_p, drs);
- struct graph *g = new_graph (num_vertices);
+ struct graph *g;
data_reference_p dr1, dr2;
int i, j;
int num_connected_components;
@@ -1730,12 +1730,19 @@ build_alias_set_optimal_p (VEC (data_ref
int this_component_is_clique;
int all_components_are_cliques = 1;
+ if (graph_obstack == NULL)
+ {
+ graph_obstack = XNEW (struct obstack);
+ obstack_init (graph_obstack);
+ }
+ g = new_graph (num_vertices, graph_obstack);
+
FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
for (j = i+1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
if (dr_may_alias_p (dr1, dr2, true))
{
- add_edge (g, i, j);
- add_edge (g, j, i);
+ add_edge (g, i, j, graph_obstack);
+ add_edge (g, j, i, graph_obstack);
}
all_vertices = XNEWVEC (int, num_vertices);
@@ -1795,7 +1802,7 @@ build_alias_set_optimal_p (VEC (data_ref
free (all_vertices);
free (vertices);
- free_graph (g);
+ XOBDELETE (graph_obstack, g);
return all_components_are_cliques;
}
@@ -1805,17 +1812,24 @@ static void
build_base_obj_set_for_drs (VEC (data_reference_p, heap) *drs)
{
int num_vertex = VEC_length (data_reference_p, drs);
- struct graph *g = new_graph (num_vertex);
+ struct graph *g;
data_reference_p dr1, dr2;
int i, j;
int *queue;
+ if (graph_obstack == NULL)
+ {
+ graph_obstack = XNEW (struct obstack);
+ obstack_init (graph_obstack);
+ }
+ g = new_graph (num_vertex, graph_obstack);
+
FOR_EACH_VEC_ELT (data_reference_p, drs, i, dr1)
for (j = i + 1; VEC_iterate (data_reference_p, drs, j, dr2); j++)
if (dr_same_base_object_p (dr1, dr2))
{
- add_edge (g, i, j);
- add_edge (g, j, i);
+ add_edge (g, i, j, graph_obstack);
+ add_edge (g, j, i, graph_obstack);
}
queue = XNEWVEC (int, num_vertex);
@@ -1836,7 +1850,7 @@ build_base_obj_set_for_drs (VEC (data_re
}
free (queue);
- free_graph (g);
+ XOBDELETE (graph_obstack, g);
}
/* Build the data references for PBB. */
=== modified file 'gcc/tree-data-ref.c'
--- gcc/tree-data-ref.c 2012-07-16 11:32:42 +0000
+++ gcc/tree-data-ref.c 2012-08-18 16:43:02 +0000
@@ -4936,10 +4936,10 @@ rdg_vertex_for_stmt (struct graph *rdg A
/* Creates an edge in RDG for each distance vector from DDR. The
order that we keep track of in the RDG is the order in which
- statements have to be executed. */
+ statements have to be executed. Allocation happen from obstack O. */
static void
-create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr, struct obstack *o)
{
struct graph_edge *e;
int va, vb;
@@ -4963,8 +4963,8 @@ create_rdg_edge_for_ddr (struct graph *r
if (va < 0 || vb < 0)
return;
- e = add_edge (rdg, va, vb);
- e->data = XNEW (struct rdg_edge);
+ e = add_edge (rdg, va, vb, o);
+ e->data = XOBNEW (o, struct rdg_edge);
RDGE_LEVEL (e) = level;
RDGE_RELATION (e) = ddr;
@@ -4981,10 +4981,11 @@ create_rdg_edge_for_ddr (struct graph *r
}
/* Creates dependence edges in RDG for all the uses of DEF. IDEF is
- the index of DEF in RDG. */
+ the index of DEF in RDG. Allocation happen from obstack O. */
static void
-create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
+create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef,
+ struct obstack *o)
{
use_operand_p imm_use_p;
imm_use_iterator iterator;
@@ -4997,17 +4998,18 @@ create_rdg_edges_for_scalar (struct grap
if (use < 0)
continue;
- e = add_edge (rdg, idef, use);
- e->data = XNEW (struct rdg_edge);
+ e = add_edge (rdg, idef, use, o);
+ e->data = XOBNEW (o, struct rdg_edge);
RDGE_TYPE (e) = flow_dd;
RDGE_RELATION (e) = NULL;
}
}
-/* Creates the edges of the reduced dependence graph RDG. */
+/* Creates the edges of the reduced dependence graph RDG. Allocations happen
+ from obstack O. */
static void
-create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
+create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs, struct obstack
*o)
{
int i;
struct data_dependence_relation *ddr;
@@ -5016,18 +5018,20 @@ create_rdg_edges (struct graph *rdg, VEC
FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
- create_rdg_edge_for_ddr (rdg, ddr);
+ create_rdg_edge_for_ddr (rdg, ddr, o);
for (i = 0; i < rdg->n_vertices; i++)
FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
iter, SSA_OP_DEF)
- create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
+ create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i, o);
}
-/* Build the vertices of the reduced dependence graph RDG. */
+/* Build the vertices of the reduced dependence graph RDG. Data is allocated
+ from obstack O. */
static void
-create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts, loop_p loop)
+create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts, loop_p loop,
+ struct obstack *o)
{
int i, j;
gimple stmt;
@@ -5041,7 +5045,7 @@ create_rdg_vertices (struct graph *rdg,
/* Record statement to vertex mapping. */
gimple_set_uid (stmt, i);
- v->data = XNEW (struct rdg_vertex);
+ v->data = XOBNEW (o, struct rdg_vertex);
RDGV_STMT (v) = stmt;
RDGV_DATAREFS (v) = NULL;
RDGV_HAS_MEM_WRITE (v) = false;
@@ -5115,24 +5119,30 @@ known_dependences_p (VEC (ddr_p, heap) *
/* Build the Reduced Dependence Graph (RDG) with one vertex per
statement of the loop nest, and one edge per data dependence or
- scalar dependence. */
+ scalar dependence. Allocated from obstack O. */
struct graph *
-build_empty_rdg (int n_stmts)
+build_empty_rdg (int n_stmts, struct obstack *o)
{
- struct graph *rdg = new_graph (n_stmts);
- return rdg;
+ if (graph_obstack == NULL)
+ {
+ graph_obstack = XOBNEW (o, struct obstack);
+ obstack_init (graph_obstack);
+ }
+
+ return new_graph (n_stmts, o);
}
/* Build the Reduced Dependence Graph (RDG) with one vertex per
statement of the loop nest, and one edge per data dependence or
- scalar dependence. */
+ scalar dependence. All data is allocated from obstack O. */
struct graph *
build_rdg (struct loop *loop,
VEC (loop_p, heap) **loop_nest,
VEC (ddr_p, heap) **dependence_relations,
- VEC (data_reference_p, heap) **datarefs)
+ VEC (data_reference_p, heap) **datarefs,
+ struct obstack *o)
{
struct graph *rdg = NULL;
@@ -5142,38 +5152,15 @@ build_rdg (struct loop *loop,
{
VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, 10);
stmts_from_loop (loop, &stmts);
- rdg = build_empty_rdg (VEC_length (gimple, stmts));
- create_rdg_vertices (rdg, stmts, loop);
- create_rdg_edges (rdg, *dependence_relations);
+ rdg = build_empty_rdg (VEC_length (gimple, stmts), o);
+ create_rdg_vertices (rdg, stmts, loop, o);
+ create_rdg_edges (rdg, *dependence_relations, o);
VEC_free (gimple, heap, stmts);
}
return rdg;
}
-/* Free the reduced dependence graph RDG. */
-
-void
-free_rdg (struct graph *rdg)
-{
- int i;
-
- for (i = 0; i < rdg->n_vertices; i++)
- {
- struct vertex *v = &(rdg->vertices[i]);
- struct graph_edge *e;
-
- for (e = v->succ; e; e = e->succ_next)
- free (e->data);
-
- gimple_set_uid (RDGV_STMT (v), -1);
- free_data_refs (RDGV_DATAREFS (v));
- free (v->data);
- }
-
- free_graph (rdg);
-}
-
/* Determines whether the statement from vertex V of the RDG has a
definition used outside the loop that contains this statement. */
=== modified file 'gcc/tree-data-ref.h'
--- gcc/tree-data-ref.h 2012-06-06 09:45:27 +0000
+++ gcc/tree-data-ref.h 2012-08-18 16:43:02 +0000
@@ -589,9 +589,9 @@ typedef struct rdg_edge
struct graph *build_rdg (struct loop *,
VEC (loop_p, heap) **,
VEC (ddr_p, heap) **,
- VEC (data_reference_p, heap) **);
-struct graph *build_empty_rdg (int);
-void free_rdg (struct graph *);
+ VEC (data_reference_p, heap) **,
+ struct obstack *);
+struct graph *build_empty_rdg (int, struct obstack *);
/* Return the index of the variable VAR in the LOOP_NEST array. */
=== modified file 'gcc/tree-loop-distribution.c'
--- gcc/tree-loop-distribution.c 2012-08-14 14:16:18 +0000
+++ gcc/tree-loop-distribution.c 2012-08-18 16:43:02 +0000
@@ -1393,7 +1393,14 @@ distribute_loop (struct loop *loop, VEC
datarefs = VEC_alloc (data_reference_p, heap, 10);
dependence_relations = VEC_alloc (ddr_p, heap, 100);
loop_nest = VEC_alloc (loop_p, heap, 3);
- rdg = build_rdg (loop, &loop_nest, &dependence_relations, &datarefs);
+
+ if (graph_obstack == NULL)
+ {
+ graph_obstack = XNEW (struct obstack);
+ obstack_init (graph_obstack);
+ }
+ rdg = build_rdg (loop, &loop_nest, &dependence_relations, &datarefs,
+ graph_obstack);
if (!rdg)
{
@@ -1429,7 +1436,9 @@ distribute_loop (struct loop *loop, VEC
res = ldist_gen (loop, rdg, vertices);
VEC_free (int, heap, vertices);
- free_rdg (rdg);
+
+ XOBDELETE (graph_obstack, rdg);
+
free_dependence_relations (dependence_relations);
free_data_refs (datarefs);
VEC_free (loop_p, heap, loop_nest);
