From patchwork Fri Sep 13 08:19:17 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 274673 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]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id 902732C0151 for ; Fri, 13 Sep 2013 18:19:29 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=N9rnZ5bueQr6Mns5VNdaPZx9IN7fwKQucb96/kzJ1jcR5bTrPHyrC 7LZJ3lzjQfB0ZgIloZYwHryPsb2JTq9Q/ujlmyoVpgO49vKmnzyLRVJFRhO5713T 90cVQbdBIl3FqU64LqnMmViMIMYsY80fV16hYZTD2FiXXxSLJ4B7nY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=k5J9Eck4xRTxO0QV5NpS6S4OWLk=; b=geJtGwa+LmA1atHvT1Cx RQCUVao+dBywqbjyk21OAL3JihIfz+0S6yqTIRdHN+v8d9odAePENuU41oJbZBqd smK/C8fgGW7wKHvRQGREyJBu57HKYDdK54QOsKr1bw5pj9pJYgB2BbEXdRZpMn8A 1QlGTyEOuN0emmYvgvHA1aE= Received: (qmail 19739 invoked by alias); 13 Sep 2013 08:19:22 -0000 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 Received: (qmail 19725 invoked by uid 89); 13 Sep 2013 08:19:21 -0000 Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 13 Sep 2013 08:19:21 +0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.1 required=5.0 tests=AWL, BAYES_00, RDNS_NONE autolearn=no version=3.3.2 X-HELO: mx2.suse.de Received: from relay1.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 720DEA50E4 for ; Fri, 13 Sep 2013 10:19:18 +0200 (CEST) Date: Fri, 13 Sep 2013 10:19:17 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] More dead code removal from loop-distribution Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 This removes what loop-distribution calls "components" (SCCs of the RDG). They are not in any way useful and just an unnecessary intermediate step. Bootstrapped and tested on x86_64-unknown-linux-gnu, applied. Richard. 2013-09-13 Richard Biener * tree-loop-distribution.c (struct rdg_component, rdg_defs_used_in_other_loops_p, free_rdg_components, rdg_build_components): Remove. (stmts_from_loop): Do not record virtual PHIs. (generate_loops_for_partition): Skip virtual PHIs. (build_rdg_partition_for_component): Rename to ... (build_rdg_partition_for_vertex): ... this and adjust. (rdg_build_partitions): Take a vector of starting vertices instead of components. Remove unnecessary leftover handling. (ldist_gen): Do not build components or record other stores. (distribute_loop): Do not distribute loops containing stmts with side-effects. Index: gcc/tree-loop-distribution.c =================================================================== --- gcc/tree-loop-distribution.c (revision 202525) +++ gcc/tree-loop-distribution.c (working copy) @@ -115,14 +115,6 @@ typedef struct rdg_edge #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation -/* Strongly connected components of the reduced data dependence graph. */ - -typedef struct rdg_component -{ - int num; - vec vertices; -} *rdgc; - /* Dump vertex I in RDG to FILE. */ static void @@ -452,7 +444,8 @@ stmts_from_loop (struct loop *loop, vec< gimple stmt; for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - stmts->safe_push (gsi_stmt (bsi)); + if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi)))) + stmts->safe_push (gsi_stmt (bsi)); for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) { @@ -564,34 +557,6 @@ build_rdg (vec loop_nest) return rdg; } -/* Determines whether the statement from vertex V of the RDG has a - definition used outside the loop that contains this statement. */ - -static bool -rdg_defs_used_in_other_loops_p (struct graph *rdg, int v) -{ - gimple stmt = RDG_STMT (rdg, v); - struct loop *loop = loop_containing_stmt (stmt); - use_operand_p imm_use_p; - imm_use_iterator iterator; - ssa_op_iter it; - def_operand_p def_p; - - if (!loop) - return true; - - FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF) - { - FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p)) - { - if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop) - return true; - } - } - - return false; -} - enum partition_kind { @@ -751,7 +716,8 @@ generate_loops_for_partition (struct loo basic_block bb = bbs[i]; for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - if (!bitmap_bit_p (partition->stmts, x++)) + if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi))) + && !bitmap_bit_p (partition->stmts, x++)) reset_debug_uses (gsi_stmt (bsi)); for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) @@ -769,7 +735,8 @@ generate_loops_for_partition (struct loo basic_block bb = bbs[i]; for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);) - if (!bitmap_bit_p (partition->stmts, x++)) + if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi))) + && !bitmap_bit_p (partition->stmts, x++)) { gimple phi = gsi_stmt (bsi); if (virtual_operand_p (gimple_phi_result (phi))) @@ -1174,88 +1141,20 @@ rdg_flag_loop_exits (struct graph *rdg, conds.release (); } -/* Returns a bitmap in which all the statements needed for computing - the strongly connected component C of the RDG are flagged, also - including the loop exit conditions. */ +/* Returns a partition with all the statements needed for computing + the vertex V of the RDG, also including the loop exit conditions. */ static partition_t -build_rdg_partition_for_component (struct graph *rdg, rdgc c) +build_rdg_partition_for_vertex (struct graph *rdg, int v) { partition_t partition = partition_alloc (NULL, NULL); bitmap processed = BITMAP_ALLOC (NULL); - - /* Flag the first vertex of the component and its dependent nodes. - Other members of the component are included in its dependencies. - ??? What do we need components for again? To early merge initial - vertices that are in a SCC of the RDG? */ - rdg_flag_vertex_and_dependent (rdg, c->vertices[0], partition, processed); - + rdg_flag_vertex_and_dependent (rdg, v, partition, processed); rdg_flag_loop_exits (rdg, partition, processed); - BITMAP_FREE (processed); return partition; } -/* Free memory for COMPONENTS. */ - -static void -free_rdg_components (vec components) -{ - int i; - rdgc x; - - FOR_EACH_VEC_ELT (components, i, x) - { - x->vertices.release (); - free (x); - } - - components.release (); -} - -/* Build the COMPONENTS vector with the strongly connected components - of RDG in which the STARTING_VERTICES occur. */ - -static void -rdg_build_components (struct graph *rdg, vec starting_vertices, - vec *components) -{ - int i, v; - bitmap saved_components = BITMAP_ALLOC (NULL); - int n_components = graphds_scc (rdg, NULL); - /* ??? Macros cannot process template types with more than one - argument, so we need this typedef. */ - typedef vec vec_int_heap; - vec *all_components = XNEWVEC (vec_int_heap, n_components); - - for (i = 0; i < n_components; i++) - all_components[i].create (3); - - for (i = 0; i < rdg->n_vertices; i++) - all_components[rdg->vertices[i].component].safe_push (i); - - FOR_EACH_VEC_ELT (starting_vertices, i, v) - { - int c = rdg->vertices[v].component; - - if (bitmap_set_bit (saved_components, c)) - { - rdgc x = XCNEW (struct rdg_component); - x->num = c; - x->vertices = all_components[c]; - - components->safe_push (x); - } - } - - for (i = 0; i < n_components; i++) - if (!bitmap_bit_p (saved_components, i)) - all_components[i].release (); - - free (all_components); - BITMAP_FREE (saved_components); -} - /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP. For the moment we detect only the memset zero pattern. */ @@ -1472,23 +1371,22 @@ similar_memory_accesses (struct graph *r distributed in different loops. */ static void -rdg_build_partitions (struct graph *rdg, vec components, - vec *other_stores, - vec *partitions, bitmap processed) +rdg_build_partitions (struct graph *rdg, + vec starting_vertices, + vec *partitions) { - int i; - rdgc x; + bitmap processed = BITMAP_ALLOC (NULL); + int i, v; partition_t partition = partition_alloc (NULL, NULL); - FOR_EACH_VEC_ELT (components, i, x) + FOR_EACH_VEC_ELT (starting_vertices, i, v) { partition_t np; - int v = x->vertices[0]; if (bitmap_bit_p (processed, v)) continue; - np = build_rdg_partition_for_component (rdg, x); + np = build_rdg_partition_for_vertex (rdg, v); bitmap_ior_into (partition->stmts, np->stmts); partition->has_writes = partition_has_writes (np); bitmap_ior_into (processed, np->stmts); @@ -1507,36 +1405,23 @@ rdg_build_partitions (struct graph *rdg, } } - /* Add the nodes from the RDG that were not marked as processed, and - that are used outside the current loop. These are scalar - computations that are not yet part of previous partitions. */ - for (i = 0; i < rdg->n_vertices; i++) - if (!bitmap_bit_p (processed, i) - && rdg_defs_used_in_other_loops_p (rdg, i)) - other_stores->safe_push (i); - - /* If there are still statements left in the OTHER_STORES array, - create other components and partitions with these stores and - their dependences. */ - if (other_stores->length () > 0) - { - vec comps; - comps.create (3); - vec foo; - foo.create (3); - - rdg_build_components (rdg, *other_stores, &comps); - rdg_build_partitions (rdg, comps, &foo, partitions, processed); - - foo.release (); - free_rdg_components (comps); - } - - /* If there is something left in the last partition, save it. */ - if (bitmap_count_bits (partition->stmts) > 0) - partitions->safe_push (partition); + /* All vertices should have been assigned to at least one partition now, + other than vertices belonging to dead code. */ + + if (!bitmap_empty_p (partition->stmts)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "remaining partition:\n"); + dump_bitmap (dump_file, partition->stmts); + } + + partitions->safe_push (partition); + } else partition_free (partition); + + BITMAP_FREE (processed); } /* Dump to FILE the PARTITIONS. */ @@ -1627,42 +1512,12 @@ ldist_gen (struct loop *loop, struct gra vec starting_vertices) { int i, nbp; - vec components; - components.create (3); vec partitions; partitions.create (3); - vec other_stores; - other_stores.create (3); partition_t partition; - bitmap processed = BITMAP_ALLOC (NULL); bool any_builtin; - for (i = 0; i < rdg->n_vertices; i++) - { - /* Save in OTHER_STORES all the memory writes that are not in - STARTING_VERTICES. */ - if (RDG_MEM_WRITE_STMT (rdg, i)) - { - int v; - unsigned j; - bool found = false; - - FOR_EACH_VEC_ELT (starting_vertices, j, v) - if (i == v) - { - found = true; - break; - } - - if (!found) - other_stores.safe_push (i); - } - } - - rdg_build_components (rdg, starting_vertices, &components); - rdg_build_partitions (rdg, components, &other_stores, &partitions, - processed); - BITMAP_FREE (processed); + rdg_build_partitions (rdg, starting_vertices, &partitions); any_builtin = false; FOR_EACH_VEC_ELT (partitions, i, partition) @@ -1718,9 +1573,6 @@ ldist_gen (struct loop *loop, struct gra partitions.iterate (j, &partition); ++j) { if (!partition_builtin_p (partition) - /* ??? The following is horribly inefficient, - we are re-computing and analyzing data-references - of the stmts in the partitions all the time. */ && similar_memory_accesses (rdg, into, partition)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1786,9 +1638,7 @@ ldist_gen (struct loop *loop, struct gra FOR_EACH_VEC_ELT (partitions, i, partition) partition_free (partition); - other_stores.release (); partitions.release (); - free_rdg_components (components); return nbp; } @@ -1820,7 +1670,7 @@ distribute_loop (struct loop *loop, vec< { if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, - "FIXME: Loop %d not distributed: failed to build the RDG.\n", + "Loop %d not distributed: failed to build the RDG.\n", loop->num); loop_nest.release (); @@ -1903,6 +1753,15 @@ tree_loop_distribution (void) for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi)) { gimple stmt = gsi_stmt (gsi); + + /* If there is a stmt with side-effects bail out - we + cannot and should not distribute this loop. */ + if (gimple_has_side_effects (stmt)) + { + work_list.truncate (0); + goto out; + } + /* Distribute stmts which have defs that are used outside of the loop. */ if (stmt_has_scalar_dependences_outside_loop (loop, stmt)) @@ -1915,6 +1774,7 @@ tree_loop_distribution (void) work_list.safe_push (stmt); } } +out: free (bbs); if (work_list.length () > 0)