[PATCH] Fix PR46194: fix the computation of distance vectors.

Richard Guenther richard.guenther@gmail.com
Fri Feb 4 23:10:00 GMT 2011


On Fri, Feb 4, 2011 at 4:59 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> Hi,
>
> This patch makes the computation of the classic distance vectors more
> strict with respect to multiple index variable subscripts.  The patch
> passed regstrap on amd64-linux.  Ok for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> Sebastian
>
> 2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
>
>        PR tree-optimization/46194
>        * tree-data-ref.c (analyze_miv_subscript): Remove comment.
>        (build_classic_dist_vector_1): Do not represent classic distance
>        vectors when the access functions are variating in different loops.
>
>        * gcc.dg/autopar/pr46194.c: New.
> ---
>  gcc/ChangeLog                          |    7 +++++++
>  gcc/testsuite/ChangeLog                |    5 +++++
>  gcc/testsuite/gcc.dg/autopar/pr46194.c |   24 ++++++++++++++++++++++++
>  gcc/tree-data-ref.c                    |   30 ++++++------------------------
>  4 files changed, 42 insertions(+), 24 deletions(-)
>  create mode 100644 gcc/testsuite/gcc.dg/autopar/pr46194.c
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 79a140b..d2dca11 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,10 @@
> +2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +       PR tree-optimization/46194
> +       * tree-data-ref.c (analyze_miv_subscript): Remove comment.
> +       (build_classic_dist_vector_1): Do not represent classic distance
> +       vectors when the access functions are variating in different loops.
> +
>  2011-02-02  Sebastian Pop  <sebastian.pop@amd.com>
>            Richard Guenther  <rguenther@suse.de>
>
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index c4dd8ac..de7301e 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,8 @@
> +2011-02-04  Sebastian Pop  <sebastian.pop@amd.com>
> +
> +       PR tree-optimization/46194
> +       * gcc.dg/autopar/pr46194.c: New.
> +
>  2011-02-02  Sebastian Pop  <sebastian.pop@amd.com>
>            Richard Guenther  <rguenther@suse.de>
>
> diff --git a/gcc/testsuite/gcc.dg/autopar/pr46194.c b/gcc/testsuite/gcc.dg/autopar/pr46194.c
> new file mode 100644
> index 0000000..574d6e6
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/autopar/pr46194.c
> @@ -0,0 +1,24 @@
> +/* PR tree-optimization/46194 */
> +/* { dg-do compile } */
> +/* { dg-options "-O -ftree-parallelize-loops=2 -fdump-tree-parloops-details" } */
> +
> +#define N 1000
> +int a[N];
> +
> +int foo (void)
> +{
> +  int j;
> +  int i;
> +
> +  /* This is not blocked as it is not profitable.  */
> +  for (i = 0; i < N; i++)
> +    for (j = 0; j < N; j++)
> +      a[j] = a[i] + 1;
> +
> +  return a[0];
> +}
> +
> +/* This loop cannot be parallelized due to a dependence.  */
> +
> +/* { dg-final { scan-tree-dump-times "SUCCESS: may be parallelized" 0 "parloops" } } */
> +/* { dg-final { cleanup-tree-dump "parloops" } } */
> diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
> index 9e5df7d..54cb46c 100644
> --- a/gcc/tree-data-ref.c
> +++ b/gcc/tree-data-ref.c
> @@ -2681,14 +2681,6 @@ analyze_miv_subscript (tree chrec_a,
>                       tree *last_conflicts,
>                       struct loop *loop_nest)
>  {
> -  /* FIXME:  This is a MIV subscript, not yet handled.
> -     Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
> -     (A[i] vs. A[j]).
> -
> -     In the SIV test we had to solve a Diophantine equation with two
> -     variables.  In the MIV case we have to solve a Diophantine
> -     equation with 2*n variables (if the subscript uses n IVs).
> -  */
>   tree type, difference;
>
>   dependence_stats.num_miv++;
> @@ -2960,29 +2952,19 @@ build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
>          && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
>        {
>          int dist, index;
> -         int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
> -                                           DDR_LOOP_NEST (ddr));
> -         int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
> -                                           DDR_LOOP_NEST (ddr));
> -
> -         /* The dependence is carried by the outermost loop.  Example:
> -            | loop_1
> -            |   A[{4, +, 1}_1]
> -            |   loop_2
> -            |     A[{5, +, 1}_2]
> -            |   endloop_2
> -            | endloop_1
> -            In this case, the dependence is carried by loop_1.  */
> -         index = index_a < index_b ? index_a : index_b;
> -         *index_carry = MIN (index, *index_carry);
> +         int var_a = CHREC_VARIABLE (access_fn_a);
> +         int var_b = CHREC_VARIABLE (access_fn_b);
>
> -         if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
> +         if (var_a != var_b
> +             || chrec_contains_undetermined (SUB_DISTANCE (subscript)))
>            {
>              non_affine_dependence_relation (ddr);
>              return false;
>            }
>
>          dist = int_cst_value (SUB_DISTANCE (subscript));
> +         index = index_in_loop_nest (var_a, DDR_LOOP_NEST (ddr));
> +         *index_carry = MIN (index, *index_carry);
>
>          /* This is the subscript coupling test.  If we have already
>             recorded a distance for this loop (a distance coming from
> --
> 1.7.1
>
>



More information about the Gcc-patches mailing list