From patchwork Sat Aug 18 18:10:16 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitrios Apostolou X-Patchwork-Id: 178482 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 7988E2C007C for ; Sun, 19 Aug 2012 04:10:46 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1345918247; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Date:From:To:cc:Subject:In-Reply-To:Message-ID:References: User-Agent:MIME-Version:Content-Type:Mailing-List:Precedence: List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=UxjELTZ5nu7RWNZavxx6P1fxrw0=; b=wmL5KZhqcg4Ifnv RgAeoy0yPAkJWhnCdgUTeo5Crd/H8d4Y4F7QIFX9A5Pe+gQe0Nwj+5EbH7ugC7kP rDF9fV8KA+tfVaUpnEQINgf+nnO4sILYayGGEH8xL4ZLfZKp3Otl5P7B5RSnf4Sr YhxHun22OpBmk6JhQbk8CxbSCrGI= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Date:From:To:cc:Subject:In-Reply-To:Message-ID:References:User-Agent:MIME-Version:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=DkchVu7/v5iVF59aM8NuBVor42fUM0yszJSQLuFNaObUXTmMHisSlTolTF1Kt0 4Qx1BJcpjBB6pjo98blOT58zN8a3ogg4JONg4J6fVKI5Y3wqm0bWiNp3I68vZlDW AEALDz0NwuNDXiLWKzF9iNV98UrAs9UFhuKDmyKUrXlWc=; Received: (qmail 9541 invoked by alias); 18 Aug 2012 18:10:41 -0000 Received: (qmail 9525 invoked by uid 22791); 18 Aug 2012 18:10:36 -0000 X-SWARE-Spam-Status: No, hits=-2.7 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, KHOP_THREADED, RCVD_IN_DNSWL_NONE, RCVD_IN_HOSTKARMA_NO, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mailout-de.gmx.net (HELO mailout-de.gmx.net) (213.165.64.23) by sourceware.org (qpsmtpd/0.43rc1) with SMTP; Sat, 18 Aug 2012 18:10:20 +0000 Received: (qmail invoked by alias); 18 Aug 2012 18:10:18 -0000 Received: from teras.ics.forth.gr (EHLO teras.ics.forth.gr) [139.91.70.93] by mail.gmx.net (mp001) with SMTP; 18 Aug 2012 20:10:18 +0200 Date: Sat, 18 Aug 2012 21:10:16 +0300 (EEST) From: Dimitrios Apostolou To: gcc-patches@gcc.gnu.org cc: Andrey Belevantsev Subject: [graphds.h] Allocate graph from obstack In-Reply-To: Message-ID: References: User-Agent: Alpine 2.02 (LNX 1266 2009-07-14) MIME-Version: 1.0 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 * 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 . */ +#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);