Re: [graphds.h] Allocate graph from obstack
Il 19/08/2012 18:55, Richard Guenther ha scritto: 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. Either an obstack per graph or the ability to specify an obstack for allocation. A global obstack with global lifetime is bad IMHO. Dimitrios's patch has a per-file obstack with per-pass lifetime, which I think is the right solution---but putting graph_obstack as a static variable in graphds.h is gly. You can just move the declaration to each file separately, and give it a better name perhaps (e.g. loop_graph_obstack). Paolo
Re: [graphds.h] Allocate graph from obstack
On Mon, Aug 20, 2012 at 2:03 PM, Paolo Bonzini bonz...@gnu.org wrote: Il 19/08/2012 18:55, Richard Guenther ha scritto: 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. Either an obstack per graph or the ability to specify an obstack for allocation. A global obstack with global lifetime is bad IMHO. Dimitrios's patch has a per-file obstack with per-pass lifetime, which I think is the right solution---but putting graph_obstack as a static variable in graphds.h is gly. You can just move the declaration to each file separately, and give it a better name perhaps (e.g. loop_graph_obstack). Well, I see that the way it is constructed is that you can at most have a single live graph at the same time (using the same obstack). That's a big limitation IMHO. Now, if the users would manage the obstack completely and instead would obstack_init()/free() them that would be different. Of course the outcome is exactly as with the initial patch having the obstack per struct graph. The present patch has too much low-level stuff exposed and does not easily allow putting other data on the same obstack. So I'd vote for managing the obstack completely in the caller for flexibility. Some may want to allocate auxiliar data on the same obstack for example. Richard. Paolo
Re: [graphds.h] Allocate graph from obstack
Hi Paolo, On Mon, 20 Aug 2012, Paolo Bonzini wrote: Il 19/08/2012 18:55, Richard Guenther ha scritto: 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. Either an obstack per graph or the ability to specify an obstack for allocation. A global obstack with global lifetime is bad IMHO. Dimitrios's patch has a per-file obstack with per-pass lifetime Notice that I never call XOBDELETE with NULL argument, I only free the first object, which means that the 4KB per obstack overhead is retained until program exit, I did that to save on malloc calls. Thanks, Dimitris
Re: [graphds.h] Allocate graph from obstack
On Sat, Aug 18, 2012 at 8:10 PM, Dimitrios Apostolou ji...@gmx.net wrote: 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. Either an obstack per graph or the ability to specify an obstack for allocation. A global obstack with global lifetime is bad IMHO. Richard. Thanks, Dimitris
[graphds.h] Allocate graph from obstack
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 + +++ gcc/cfgloopanal.c 2012-08-18 16:43:02 + @@ -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 + +++ gcc/dominance.c 2012-08-18 16:43:02 + @@ -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 + +++ gcc/graphds.c 2012-08-18 16:43:02 + @@ -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