Message ID | 1297118045-19067-1-git-send-email-sebpop@gmail.com |
---|---|
State | New |
Headers | show |
On Mon, 7 Feb 2011, Sebastian Pop wrote: > Hi Richi, > > This patch detects when a reduction cycle contains other computations > than the reduction and stops the translation out of SSA for these > reductions. The patch passed regstrap on amd64-linux. Ok for trunk? Ok. Thanks, Richard. > Thanks, > Sebastian > > 2011-02-08 Sebastian Pop <sebastian.pop@amd.com> > > PR tree-optimization/46834 > PR tree-optimization/46994 > PR tree-optimization/46995 > * graphite-sese-to-poly.c (used_outside_reduction): New. > (detect_commutative_reduction): Call used_outside_reduction. > (rewrite_commutative_reductions_out_of_ssa_close_phi): Call > translate_scalar_reduction_to_array only when at least one > loop-phi/close-phi tuple has been detected. > > * gcc.dg/graphite/id-pr46834.c: New. > * gfortran.dg/graphite/id-pr46994.f90: New. > * gfortran.dg/graphite/id-pr46995.f90: New. > --- > gcc/ChangeLog | 11 ++++ > gcc/graphite-sese-to-poly.c | 56 ++++++++++++++------ > gcc/testsuite/ChangeLog | 9 +++ > gcc/testsuite/gcc.dg/graphite/id-pr46834.c | 12 +++++ > gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 | 14 +++++ > gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 | 16 ++++++ > 6 files changed, 101 insertions(+), 17 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/graphite/id-pr46834.c > create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 > create mode 100644 gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 > > diff --git a/gcc/ChangeLog b/gcc/ChangeLog > index 39baf06..6c2f652 100644 > --- a/gcc/ChangeLog > +++ b/gcc/ChangeLog > @@ -1,3 +1,14 @@ > +2011-02-08 Sebastian Pop <sebastian.pop@amd.com> > + > + PR tree-optimization/46834 > + PR tree-optimization/46994 > + PR tree-optimization/46995 > + * graphite-sese-to-poly.c (used_outside_reduction): New. > + (detect_commutative_reduction): Call used_outside_reduction. > + (rewrite_commutative_reductions_out_of_ssa_close_phi): Call > + translate_scalar_reduction_to_array only when at least one > + loop-phi/close-phi tuple has been detected. > + > 2011-02-04 Sebastian Pop <sebastian.pop@amd.com> > > PR tree-optimization/46194 > diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c > index 11a73b3..064ded3 100644 > --- a/gcc/graphite-sese-to-poly.c > +++ b/gcc/graphite-sese-to-poly.c > @@ -2898,6 +2898,30 @@ initial_value_for_loop_phi (gimple phi) > return NULL_TREE; > } > > +/* Returns true when DEF is used outside the reduction cycle of > + LOOP_PHI. */ > + > +static bool > +used_outside_reduction (tree def, gimple loop_phi) > +{ > + use_operand_p use_p; > + imm_use_iterator imm_iter; > + loop_p loop = loop_containing_stmt (loop_phi); > + > + /* In LOOP, DEF should be used only in LOOP_PHI. */ > + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) > + { > + gimple stmt = USE_STMT (use_p); > + > + if (stmt != loop_phi > + && !is_gimple_debug (stmt) > + && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) > + return true; > + } > + > + return false; > +} > + > /* Detect commutative and associative scalar reductions belonging to > the SCOP starting at the loop closed phi node STMT. Return the phi > node of the reduction cycle, or NULL. */ > @@ -2908,8 +2932,8 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, > { > if (scalar_close_phi_node_p (stmt)) > { > - tree arg = gimple_phi_arg_def (stmt, 0); > - gimple def, loop_phi; > + gimple def, loop_phi, phi, close_phi = stmt; > + tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0); > > if (TREE_CODE (arg) != SSA_NAME) > return NULL; > @@ -2917,26 +2941,24 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, > /* Note that loop close phi nodes should have a single argument > because we translated the representation into a canonical form > before Graphite: see canonicalize_loop_closed_ssa_form. */ > - gcc_assert (gimple_phi_num_args (stmt) == 1); > + gcc_assert (gimple_phi_num_args (close_phi) == 1); > > def = SSA_NAME_DEF_STMT (arg); > - if (!stmt_in_sese_p (def, SCOP_REGION (scop))) > + if (!stmt_in_sese_p (def, SCOP_REGION (scop)) > + || !(loop_phi = detect_commutative_reduction (scop, def, in, out))) > return NULL; > > - loop_phi = detect_commutative_reduction (scop, def, in, out); > + lhs = gimple_phi_result (close_phi); > + init = initial_value_for_loop_phi (loop_phi); > + phi = follow_inital_value_to_phi (init, lhs); > > - if (loop_phi) > - { > - tree lhs = gimple_phi_result (stmt); > - tree init = initial_value_for_loop_phi (loop_phi); > - gimple phi = follow_inital_value_to_phi (init, lhs); > - > - VEC_safe_push (gimple, heap, *in, loop_phi); > - VEC_safe_push (gimple, heap, *out, stmt); > - return phi; > - } > - else > + if (phi && (used_outside_reduction (lhs, phi) > + || !has_single_use (gimple_phi_result (phi)))) > return NULL; > + > + VEC_safe_push (gimple, heap, *in, loop_phi); > + VEC_safe_push (gimple, heap, *out, close_phi); > + return phi; > } > > if (gimple_code (stmt) == GIMPLE_ASSIGN) > @@ -3139,7 +3161,7 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop, > VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); > > detect_commutative_reduction (scop, close_phi, &in, &out); > - res = VEC_length (gimple, in) > 0; > + res = VEC_length (gimple, in) > 1; > if (res) > translate_scalar_reduction_to_array (scop, in, out); > > diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog > index 226fa60..3b6df36 100644 > --- a/gcc/testsuite/ChangeLog > +++ b/gcc/testsuite/ChangeLog > @@ -1,3 +1,12 @@ > +2011-02-08 Sebastian Pop <sebastian.pop@amd.com> > + > + PR tree-optimization/46834 > + PR tree-optimization/46994 > + PR tree-optimization/46995 > + * gcc.dg/graphite/id-pr46834.c: New. > + * gfortran.dg/graphite/id-pr46994.f90: New. > + * gfortran.dg/graphite/id-pr46995.f90: New. > + > 2011-02-04 Sebastian Pop <sebastian.pop@amd.com> > > PR tree-optimization/46194 > diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c > new file mode 100644 > index 0000000..8d89b8e > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c > @@ -0,0 +1,12 @@ > +/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */ > + > +void foo () > +{ > + int M0[4][4], M3[4] = {}; > + int i=-1; > + int ii, jj; > + for (; i; i++) > + for (jj = 0; jj < 4; jj++) > + for (ii = 0; ii < 4; ii++) > + M3[1] += __builtin_abs (M0[ii][0]); > +} > diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 > new file mode 100644 > index 0000000..93eff45 > --- /dev/null > +++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 > @@ -0,0 +1,14 @@ > +! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" } > + > +subroutine foo (m) > + integer :: m, i, j, k > + real :: s > + s = 0 > + do i = 1, 9 > + do j = 1, 2*m > + do k = 1, 2*m > + s = s + 1 > + end do > + end do > + end do > +end subroutine foo > diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 > new file mode 100644 > index 0000000..06cbfd3 > --- /dev/null > +++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 > @@ -0,0 +1,16 @@ > +! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" } > + > +subroutine foo (m, l, zw) > + integer :: m, i, j, k > + real, dimension(1:9) :: zw > + real :: l, s > + s = 0 > + do i = 1, 9 > + do j = 1, 2*m > + do k = 1, 2*m > + s = s + 1 > + end do > + end do > + l = l + zw(i)*s > + end do > +end subroutine foo >
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 39baf06..6c2f652 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2011-02-08 Sebastian Pop <sebastian.pop@amd.com> + + PR tree-optimization/46834 + PR tree-optimization/46994 + PR tree-optimization/46995 + * graphite-sese-to-poly.c (used_outside_reduction): New. + (detect_commutative_reduction): Call used_outside_reduction. + (rewrite_commutative_reductions_out_of_ssa_close_phi): Call + translate_scalar_reduction_to_array only when at least one + loop-phi/close-phi tuple has been detected. + 2011-02-04 Sebastian Pop <sebastian.pop@amd.com> PR tree-optimization/46194 diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 11a73b3..064ded3 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -2898,6 +2898,30 @@ initial_value_for_loop_phi (gimple phi) return NULL_TREE; } +/* Returns true when DEF is used outside the reduction cycle of + LOOP_PHI. */ + +static bool +used_outside_reduction (tree def, gimple loop_phi) +{ + use_operand_p use_p; + imm_use_iterator imm_iter; + loop_p loop = loop_containing_stmt (loop_phi); + + /* In LOOP, DEF should be used only in LOOP_PHI. */ + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) + { + gimple stmt = USE_STMT (use_p); + + if (stmt != loop_phi + && !is_gimple_debug (stmt) + && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) + return true; + } + + return false; +} + /* Detect commutative and associative scalar reductions belonging to the SCOP starting at the loop closed phi node STMT. Return the phi node of the reduction cycle, or NULL. */ @@ -2908,8 +2932,8 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, { if (scalar_close_phi_node_p (stmt)) { - tree arg = gimple_phi_arg_def (stmt, 0); - gimple def, loop_phi; + gimple def, loop_phi, phi, close_phi = stmt; + tree init, lhs, arg = gimple_phi_arg_def (close_phi, 0); if (TREE_CODE (arg) != SSA_NAME) return NULL; @@ -2917,26 +2941,24 @@ detect_commutative_reduction (scop_p scop, gimple stmt, VEC (gimple, heap) **in, /* Note that loop close phi nodes should have a single argument because we translated the representation into a canonical form before Graphite: see canonicalize_loop_closed_ssa_form. */ - gcc_assert (gimple_phi_num_args (stmt) == 1); + gcc_assert (gimple_phi_num_args (close_phi) == 1); def = SSA_NAME_DEF_STMT (arg); - if (!stmt_in_sese_p (def, SCOP_REGION (scop))) + if (!stmt_in_sese_p (def, SCOP_REGION (scop)) + || !(loop_phi = detect_commutative_reduction (scop, def, in, out))) return NULL; - loop_phi = detect_commutative_reduction (scop, def, in, out); + lhs = gimple_phi_result (close_phi); + init = initial_value_for_loop_phi (loop_phi); + phi = follow_inital_value_to_phi (init, lhs); - if (loop_phi) - { - tree lhs = gimple_phi_result (stmt); - tree init = initial_value_for_loop_phi (loop_phi); - gimple phi = follow_inital_value_to_phi (init, lhs); - - VEC_safe_push (gimple, heap, *in, loop_phi); - VEC_safe_push (gimple, heap, *out, stmt); - return phi; - } - else + if (phi && (used_outside_reduction (lhs, phi) + || !has_single_use (gimple_phi_result (phi)))) return NULL; + + VEC_safe_push (gimple, heap, *in, loop_phi); + VEC_safe_push (gimple, heap, *out, close_phi); + return phi; } if (gimple_code (stmt) == GIMPLE_ASSIGN) @@ -3139,7 +3161,7 @@ rewrite_commutative_reductions_out_of_ssa_close_phi (scop_p scop, VEC (gimple, heap) *out = VEC_alloc (gimple, heap, 10); detect_commutative_reduction (scop, close_phi, &in, &out); - res = VEC_length (gimple, in) > 0; + res = VEC_length (gimple, in) > 1; if (res) translate_scalar_reduction_to_array (scop, in, out); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 226fa60..3b6df36 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,12 @@ +2011-02-08 Sebastian Pop <sebastian.pop@amd.com> + + PR tree-optimization/46834 + PR tree-optimization/46994 + PR tree-optimization/46995 + * gcc.dg/graphite/id-pr46834.c: New. + * gfortran.dg/graphite/id-pr46994.f90: New. + * gfortran.dg/graphite/id-pr46995.f90: New. + 2011-02-04 Sebastian Pop <sebastian.pop@amd.com> PR tree-optimization/46194 diff --git a/gcc/testsuite/gcc.dg/graphite/id-pr46834.c b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c new file mode 100644 index 0000000..8d89b8e --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/id-pr46834.c @@ -0,0 +1,12 @@ +/* { dg-options "-O -fgraphite-identity -ffast-math -fno-tree-dce" } */ + +void foo () +{ + int M0[4][4], M3[4] = {}; + int i=-1; + int ii, jj; + for (; i; i++) + for (jj = 0; jj < 4; jj++) + for (ii = 0; ii < 4; ii++) + M3[1] += __builtin_abs (M0[ii][0]); +} diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 new file mode 100644 index 0000000..93eff45 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46994.f90 @@ -0,0 +1,14 @@ +! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" } + +subroutine foo (m) + integer :: m, i, j, k + real :: s + s = 0 + do i = 1, 9 + do j = 1, 2*m + do k = 1, 2*m + s = s + 1 + end do + end do + end do +end subroutine foo diff --git a/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 new file mode 100644 index 0000000..06cbfd3 --- /dev/null +++ b/gcc/testsuite/gfortran.dg/graphite/id-pr46995.f90 @@ -0,0 +1,16 @@ +! { dg-options "-O -ffast-math -fgraphite-identity -fno-tree-dce" } + +subroutine foo (m, l, zw) + integer :: m, i, j, k + real, dimension(1:9) :: zw + real :: l, s + s = 0 + do i = 1, 9 + do j = 1, 2*m + do k = 1, 2*m + s = s + 1 + end do + end do + l = l + zw(i)*s + end do +end subroutine foo