From 12efb1d75f459d7c69bfaededd398f9724ee67bb Mon Sep 17 00:00:00 2001 From: Tom de Vries Date: Tue, 28 Jul 2015 07:54:04 +0000 Subject: [PATCH] Handle double reduction in parloops 2015-07-28 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. From-SVN: r226300 --- gcc/ChangeLog | 9 +++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/autopar/uns-outer-4.c | 6 +- gcc/tree-parloops.c | 73 +++++++++++++++++++--- libgomp/ChangeLog | 4 ++ libgomp/testsuite/libgomp.c/uns-outer-4.c | 36 +++++++++++ 6 files changed, 120 insertions(+), 13 deletions(-) create mode 100644 libgomp/testsuite/libgomp.c/uns-outer-4.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c5ae23bec0d..3457af82669 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2015-07-28 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. + 2015-07-28 Richard Biener * fold-const.c (fold_comparison): Remove equality folding diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index fcf7a549f22..9c9d962ff42 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2015-07-28 Tom de Vries + + * gcc.dg/autopar/uns-outer-4.c: Remove xfail on scan for parallelizing + outer loop. + 2015-07-28 Luis Felipe Strano Moraes Manuel López-Ibáñez diff --git a/gcc/testsuite/gcc.dg/autopar/uns-outer-4.c b/gcc/testsuite/gcc.dg/autopar/uns-outer-4.c index 30ead2529ea..5eb67ea74fc 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 daf23f2532b..b06265c4bb8 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/ChangeLog b/libgomp/ChangeLog index d2189928577..4c9f690a8e7 100644 --- a/libgomp/ChangeLog +++ b/libgomp/ChangeLog @@ -1,3 +1,7 @@ +2015-07-28 Tom de Vries + + * testsuite/libgomp.c/uns-outer-4.c: New test. + 2015-07-24 Cesar Philippidis * testsuite/libgomp.c/pr66714.c: New test. 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 00000000000..cd646a54133 --- /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; +} -- 2.30.2