From patchwork Mon Jul 27 22:32:31 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 500871 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 23F63140307 for ; Tue, 28 Jul 2015 08:33:08 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=M9AzWT+z; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; q=dns; s=default; b=s1A1rQRcAcTrkre+C UHGhcACQ6JuUSAU4YYbBHocuDcyXSETNfn4DjM8MF7eoOZ/2IuN2YEHQ5R0o6F3o hEqT5jsHssdjyNAtjkr2eBhomuRDguDAHvPvOY0an68fYDHlj6eWPHKg4iEothlW a4vQnb76LCgLvL6HJzxCfKuUqc= 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 :message-id:date:from:mime-version:to:subject:references :in-reply-to:content-type; s=default; bh=YBevLigggPNzIr+kCR+Cbbe MJRw=; b=M9AzWT+zJGoeegFn/1PJRTQM4qm/MJDEIY98xC9HK3yM9has+B9B7Tx ikbF9M3QF2E6nSYWP0UY2ea3g0so9oOaOvNSDN276zC+w0TvsPBUHrWYtxAb7xLk Zf5iYct3/MtKM/DmD6fpG2J7s6JPcIKPbEoh6A9UeKjEdnVWL5yI= Received: (qmail 110090 invoked by alias); 27 Jul 2015 22:33:01 -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 110072 invoked by uid 89); 27 Jul 2015 22:33:01 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.6 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 X-HELO: fencepost.gnu.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (208.118.235.10) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Mon, 27 Jul 2015 22:32:59 +0000 Received: from eggs.gnu.org ([2001:4830:134:3::10]:55376) by fencepost.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ZJqx7-00022d-I9 for gcc-patches@gnu.org; Mon, 27 Jul 2015 18:32:57 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZJqx4-0002Wl-0F for gcc-patches@gnu.org; Mon, 27 Jul 2015 18:32:57 -0400 Received: from relay1.mentorg.com ([192.94.38.131]:64777) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZJqx3-0002WU-Oh for gcc-patches@gnu.org; Mon, 27 Jul 2015 18:32:53 -0400 Received: from nat-ies.mentorg.com ([192.94.31.2] helo=SVR-IES-FEM-01.mgc.mentorg.com) by relay1.mentorg.com with esmtp id 1ZJqx1-0001KW-Om from Tom_deVries@mentor.com for gcc-patches@gnu.org; Mon, 27 Jul 2015 15:32:52 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.3.224.2; Mon, 27 Jul 2015 23:32:50 +0100 Message-ID: <55B6B17F.2030702@mentor.com> Date: Tue, 28 Jul 2015 00:32:31 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: "gcc-patches@gnu.org" Subject: Re: [PING][PATCH, PR66851] Handle double reduction in parloops References: <55A3D170.6080304@mentor.com> <55B213DD.4050602@mentor.com> In-Reply-To: <55B213DD.4050602@mentor.com> X-detected-operating-system: by eggs.gnu.org: Windows NT kernel [generic] [fuzzy] X-Received-From: 192.94.38.131 On 24/07/15 12:30, Tom de Vries wrote: > On 13/07/15 16:55, Tom de Vries wrote: >> Hi, >> >> this patch fixes PR66851. >> >> In parloops, we manage to parallelize outer loops, but not if the inner >> loop contains a reduction. There is an xfail in autopar/outer-4.c for >> this: >> ... >> /* { dg-final { scan-tree-dump-times "parallelizing outer loop" 1 >> "parloops" { xfail *-*-* } } } */ >> ... >> >> This patch allows outer loops with a reduction in the inner loop to be >> parallelized. >> Updated patch checks that we actually have an inner reduction that we can parallelize. So, uns-outer-4.c with unsigned int reduction will be paralellized, while outer-4.c with signed int reduction will not be paralellized. Bootstrapped on x86_64, reg-test in progress. OK for trunk? Thanks, - Tom Handle double reduction in parloops 2015-07-27 Tom de Vries * tree-parloops.c (reduc_stmt_res): New function. (initialize_reductions, add_field_for_reduction) (create_phi_for_local_result, create_loads_for_reductions) (create_stores_for_reduction, build_new_reduction): Handle case that reduc_stmt is a phi. (gather_scalar_reductions): Allow double_reduc reductions. * gcc.dg/autopar/uns-outer-4.c: Remove xfail on scan for parallelizing outer loop. * testsuite/libgomp.c/uns-outer-4.c: New test. --- gcc/testsuite/gcc.dg/autopar/uns-outer-4.c | 6 +-- gcc/tree-parloops.c | 73 ++++++++++++++++++++++++++---- libgomp/testsuite/libgomp.c/uns-outer-4.c | 36 +++++++++++++++ 3 files changed, 102 insertions(+), 13 deletions(-) create mode 100644 libgomp/testsuite/libgomp.c/uns-outer-4.c diff --git a/gcc/testsuite/gcc.dg/autopar/uns-outer-4.c b/gcc/testsuite/gcc.dg/autopar/uns-outer-4.c index 30ead25..5eb67ea 100644 --- a/gcc/testsuite/gcc.dg/autopar/uns-outer-4.c +++ b/gcc/testsuite/gcc.dg/autopar/uns-outer-4.c @@ -12,9 +12,7 @@ parloop (int N) int i, j; unsigned int sum; - /* Double reduction is currently not supported, outer loop is not - parallelized. Inner reduction is detected, inner loop is - parallelized. */ + /* Double reduction is detected, outer loop is parallelized. */ sum = 0; for (i = 0; i < N; i++) for (j = 0; j < N; j++) @@ -23,5 +21,5 @@ parloop (int N) g_sum = sum; } -/* { dg-final { scan-tree-dump-times "parallelizing outer loop" 1 "parloops" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "parallelizing outer loop" 1 "parloops" } } */ /* { dg-final { scan-tree-dump-times "loopfn" 4 "optimized" } } */ diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index daf23f2..b06265c 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -549,6 +549,14 @@ take_address_of (tree obj, tree type, edge entry, return name; } +static tree +reduc_stmt_res (gimple stmt) +{ + return (gimple_code (stmt) == GIMPLE_PHI + ? gimple_phi_result (stmt) + : gimple_assign_lhs (stmt)); +} + /* Callback for htab_traverse. Create the initialization statement for reduction described in SLOT, and place it at the preheader of the loop described in DATA. */ @@ -575,7 +583,7 @@ initialize_reductions (reduction_info **slot, struct loop *loop) c = build_omp_clause (gimple_location (reduc->reduc_stmt), OMP_CLAUSE_REDUCTION); OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code; - OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)); + OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (reduc_stmt_res (reduc->reduc_stmt)); init = omp_reduction_init (c, TREE_TYPE (bvar)); reduc->init = init; @@ -982,7 +990,7 @@ add_field_for_reduction (reduction_info **slot, tree type) { struct reduction_info *const red = *slot; - tree var = gimple_assign_lhs (red->reduc_stmt); + tree var = reduc_stmt_res (red->reduc_stmt); tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL, SSA_NAME_IDENTIFIER (var), TREE_TYPE (var)); @@ -1042,12 +1050,12 @@ create_phi_for_local_result (reduction_info **slot, struct loop *loop) e = EDGE_PRED (store_bb, 1); else e = EDGE_PRED (store_bb, 0); - local_res = copy_ssa_name (gimple_assign_lhs (reduc->reduc_stmt)); + tree lhs = reduc_stmt_res (reduc->reduc_stmt); + local_res = copy_ssa_name (lhs); locus = gimple_location (reduc->reduc_stmt); new_phi = create_phi_node (local_res, store_bb); add_phi_arg (new_phi, reduc->init, e, locus); - add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt), - FALLTHRU_EDGE (loop->latch), locus); + add_phi_arg (new_phi, lhs, FALLTHRU_EDGE (loop->latch), locus); reduc->new_phi = new_phi; return 1; @@ -1140,7 +1148,7 @@ create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data) struct reduction_info *const red = *slot; gimple stmt; gimple_stmt_iterator gsi; - tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt)); + tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt)); tree load_struct; tree name; tree x; @@ -1205,7 +1213,7 @@ create_stores_for_reduction (reduction_info **slot, struct clsn_data *clsn_data) tree t; gimple stmt; gimple_stmt_iterator gsi; - tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt)); + tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt)); gsi = gsi_last_bb (clsn_data->store_bb); t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE); @@ -2330,6 +2338,7 @@ build_new_reduction (reduction_info_table_type *reduction_list, { reduction_info **slot; struct reduction_info *new_reduction; + enum tree_code reduction_code; gcc_assert (reduc_stmt); @@ -2341,12 +2350,22 @@ build_new_reduction (reduction_info_table_type *reduction_list, fprintf (dump_file, "\n"); } + if (gimple_code (reduc_stmt) == GIMPLE_PHI) + { + tree op1 = PHI_ARG_DEF (reduc_stmt, 0); + gimple def1 = SSA_NAME_DEF_STMT (op1); + reduction_code = gimple_assign_rhs_code (def1); + } + + else + reduction_code = gimple_assign_rhs_code (reduc_stmt); + new_reduction = XCNEW (struct reduction_info); new_reduction->reduc_stmt = reduc_stmt; new_reduction->reduc_phi = phi; new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi)); - new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt); + new_reduction->reduction_code = reduction_code; slot = reduction_list->find_slot (new_reduction, INSERT); *slot = new_reduction; } @@ -2368,6 +2387,8 @@ gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list { gphi_iterator gsi; loop_vec_info simple_loop_info; + loop_vec_info simple_inner_loop_info = NULL; + bool allow_double_reduc = true; simple_loop_info = vect_analyze_loop_form (loop); if (simple_loop_info == NULL) @@ -2389,12 +2410,46 @@ gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list gimple reduc_stmt = vect_force_simple_reduction (simple_loop_info, phi, true, &double_reduc, true); - if (!reduc_stmt || double_reduc) + if (!reduc_stmt) continue; + if (double_reduc) + { + if (!allow_double_reduc + || loop->inner->inner != NULL) + continue; + + if (!simple_inner_loop_info) + { + simple_inner_loop_info = vect_analyze_loop_form (loop->inner); + if (!simple_inner_loop_info) + { + allow_double_reduc = false; + continue; + } + } + + use_operand_p use_p; + gimple inner_stmt; + bool single_use_p = single_imm_use (res, &use_p, &inner_stmt); + gcc_assert (single_use_p); + gphi *inner_phi = as_a (inner_stmt); + if (simple_iv (loop->inner, loop->inner, PHI_RESULT (inner_phi), + &iv, true)) + continue; + + gimple inner_reduc_stmt + = vect_force_simple_reduction (simple_inner_loop_info, inner_phi, + true, &double_reduc, true); + gcc_assert (!double_reduc); + if (inner_reduc_stmt == NULL) + continue; + } + build_new_reduction (reduction_list, reduc_stmt, phi); } destroy_loop_vec_info (simple_loop_info, true); + destroy_loop_vec_info (simple_inner_loop_info, true); /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts diff --git a/libgomp/testsuite/libgomp.c/uns-outer-4.c b/libgomp/testsuite/libgomp.c/uns-outer-4.c new file mode 100644 index 0000000..cd646a5 --- /dev/null +++ b/libgomp/testsuite/libgomp.c/uns-outer-4.c @@ -0,0 +1,36 @@ +/* { dg-do run } */ +/* { dg-additional-options "-ftree-parallelize-loops=2" } */ + +void abort (void); + +unsigned int g_sum = 1; + +unsigned int x[500][500]; + +void __attribute__((noinline,noclone)) +parloop (int N) +{ + int i, j; + unsigned int sum; + + /* Double reduction is detected, outer loop is parallelized. */ + sum = 0; + for (i = 0; i < N; i++) + for (j = 0; j < N; j++) + sum += x[i][j]; + + g_sum = sum; +} + +int +main (void) +{ + x[234][432] = 2; + + parloop (500); + + if (g_sum != 2) + abort (); + + return 0; +} -- 1.9.1