Patchwork [vectorizer] Fixing a bug in tree-vect-patterns.c in GCC vectorizer.

login
register
mail settings
Submitter Cong Hou
Date Sept. 12, 2013, 1:16 a.m.
Message ID <CAK=A3=0zML-EQEdiQb4yV1xvWPRw-8Fhmh+zTM-j8HQF5Fv3JQ@mail.gmail.com>
Download mbox | patch
Permalink /patch/274400/
State New
Headers show

Comments

Cong Hou - Sept. 12, 2013, 1:16 a.m.
Hi

There is a bug in the function vect_recog_dot_prod_pattern() in
tree-vect-patterns.c. This function checks if a loop is of dot
production pattern. Specifically, according to the comment of this
function:

/*
 Try to find the following pattern:

     type x_t, y_t;
     TYPE1 prod;
     TYPE2 sum = init;
   loop:
     sum_0 = phi <init, sum_1>
     S1  x_t = ...
     S2  y_t = ...
     S3  x_T = (TYPE1) x_t;
     S4  y_T = (TYPE1) y_t;
     S5  prod = x_T * y_T;
     [S6  prod = (TYPE2) prod;  #optional]
     S7  sum_1 = prod + sum_0;

   where 'TYPE1' is exactly double the size of type 'type', and
'TYPE2' is the same size of 'TYPE1' or bigger. This is a special case
of a reduction computation.
*/

This function should check if x_t and y_t have the same type (type)
which has the half size of TYPE1. The corresponding code is shown
below:

      oprnd0 = gimple_assign_rhs1 (stmt);
      oprnd1 = gimple_assign_rhs2 (stmt);
      if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type) ||
!types_compatible_p (TREE_TYPE (oprnd1), prod_type))
        return NULL;
      if (!type_conversion_p (oprnd0, stmt, true, &half_type0,
&def_stmt, &promotion) || !promotion)
        return NULL;
      oprnd00 = gimple_assign_rhs1 (def_stmt);

/*======================V  see here! */
      if (!type_conversion_p (oprnd0, stmt, true, &half_type1,
&def_stmt, &promotion) || !promotion)
        return NULL;
      oprnd01 = gimple_assign_rhs1 (def_stmt);
      if (!types_compatible_p (half_type0, half_type1))
        return NULL;
      if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
return NULL;

Here the function uses x_T (oprnd0) to check the type of y_t, which is
incorrect. The fix is simple: just replace it by oprnd1.

The failed test case for this bug is shown below:

int foo(short *a, int *b, int n) {
  int sum = 0;
  for (int i = 0; i < n; ++i)
    sum += a[i] * b[i];
  return sum;
}


thanks,
Cong
Xinliang David Li - Sept. 12, 2013, 1:55 a.m.
Can you add a test case to the regression suite?

When the type of arguments are unsigned short/unsigned int, GCC does
not vectorize the loop anymore -- this is worth a separate bug to
track. punpcklwd instruction can be used to do zero extension of the
short type.

David

On Wed, Sep 11, 2013 at 6:16 PM, Cong Hou <congh@google.com> wrote:
> Hi
>
> There is a bug in the function vect_recog_dot_prod_pattern() in
> tree-vect-patterns.c. This function checks if a loop is of dot
> production pattern. Specifically, according to the comment of this
> function:
>
> /*
>  Try to find the following pattern:
>
>      type x_t, y_t;
>      TYPE1 prod;
>      TYPE2 sum = init;
>    loop:
>      sum_0 = phi <init, sum_1>
>      S1  x_t = ...
>      S2  y_t = ...
>      S3  x_T = (TYPE1) x_t;
>      S4  y_T = (TYPE1) y_t;
>      S5  prod = x_T * y_T;
>      [S6  prod = (TYPE2) prod;  #optional]
>      S7  sum_1 = prod + sum_0;
>
>    where 'TYPE1' is exactly double the size of type 'type', and
> 'TYPE2' is the same size of 'TYPE1' or bigger. This is a special case
> of a reduction computation.
> */
>
> This function should check if x_t and y_t have the same type (type)
> which has the half size of TYPE1. The corresponding code is shown
> below:
>
>       oprnd0 = gimple_assign_rhs1 (stmt);
>       oprnd1 = gimple_assign_rhs2 (stmt);
>       if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type) ||
> !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
>         return NULL;
>       if (!type_conversion_p (oprnd0, stmt, true, &half_type0,
> &def_stmt, &promotion) || !promotion)
>         return NULL;
>       oprnd00 = gimple_assign_rhs1 (def_stmt);
>
> /*======================V  see here! */
>       if (!type_conversion_p (oprnd0, stmt, true, &half_type1,
> &def_stmt, &promotion) || !promotion)
>         return NULL;
>       oprnd01 = gimple_assign_rhs1 (def_stmt);
>       if (!types_compatible_p (half_type0, half_type1))
>         return NULL;
>       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
> return NULL;
>
> Here the function uses x_T (oprnd0) to check the type of y_t, which is
> incorrect. The fix is simple: just replace it by oprnd1.
>
> The failed test case for this bug is shown below:
>
> int foo(short *a, int *b, int n) {
>   int sum = 0;
>   for (int i = 0; i < n; ++i)
>     sum += a[i] * b[i];
>   return sum;
> }
>
>
> thanks,
> Cong
>
>
> Index: gcc/tree-vect-patterns.c
> ===================================================================
> --- gcc/tree-vect-patterns.c (revision 200988)
> +++ gcc/tree-vect-patterns.c (working copy)
> @@ -397,7 +397,7 @@ vect_recog_dot_prod_pattern (vec<gimple>
>            || !promotion)
>          return NULL;
>        oprnd00 = gimple_assign_rhs1 (def_stmt);
> -      if (!type_conversion_p (oprnd0, stmt, true, &half_type1, &def_stmt,
> +      if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
>                                  &promotion)
>            || !promotion)
>          return NULL;
Richard Guenther - Sept. 12, 2013, 8:14 a.m.
On Thu, Sep 12, 2013 at 3:16 AM, Cong Hou <congh@google.com> wrote:
> Hi
>
> There is a bug in the function vect_recog_dot_prod_pattern() in
> tree-vect-patterns.c. This function checks if a loop is of dot
> production pattern. Specifically, according to the comment of this
> function:
>
> /*
>  Try to find the following pattern:
>
>      type x_t, y_t;
>      TYPE1 prod;
>      TYPE2 sum = init;
>    loop:
>      sum_0 = phi <init, sum_1>
>      S1  x_t = ...
>      S2  y_t = ...
>      S3  x_T = (TYPE1) x_t;
>      S4  y_T = (TYPE1) y_t;
>      S5  prod = x_T * y_T;
>      [S6  prod = (TYPE2) prod;  #optional]
>      S7  sum_1 = prod + sum_0;
>
>    where 'TYPE1' is exactly double the size of type 'type', and
> 'TYPE2' is the same size of 'TYPE1' or bigger. This is a special case
> of a reduction computation.
> */
>
> This function should check if x_t and y_t have the same type (type)
> which has the half size of TYPE1. The corresponding code is shown
> below:
>
>       oprnd0 = gimple_assign_rhs1 (stmt);
>       oprnd1 = gimple_assign_rhs2 (stmt);
>       if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type) ||
> !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
>         return NULL;
>       if (!type_conversion_p (oprnd0, stmt, true, &half_type0,
> &def_stmt, &promotion) || !promotion)
>         return NULL;
>       oprnd00 = gimple_assign_rhs1 (def_stmt);
>
> /*======================V  see here! */
>       if (!type_conversion_p (oprnd0, stmt, true, &half_type1,
> &def_stmt, &promotion) || !promotion)
>         return NULL;
>       oprnd01 = gimple_assign_rhs1 (def_stmt);
>       if (!types_compatible_p (half_type0, half_type1))
>         return NULL;
>       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
> return NULL;
>
> Here the function uses x_T (oprnd0) to check the type of y_t, which is
> incorrect. The fix is simple: just replace it by oprnd1.
>
> The failed test case for this bug is shown below:
>
> int foo(short *a, int *b, int n) {
>   int sum = 0;
>   for (int i = 0; i < n; ++i)
>     sum += a[i] * b[i];
>   return sum;
> }

Bootstrapped and tested on ... ?

Please add a testcase that fails at runtime without the patch and
succeeds with it.

Thanks,
Richard.

>
> thanks,
> Cong
>
>
> Index: gcc/tree-vect-patterns.c
> ===================================================================
> --- gcc/tree-vect-patterns.c (revision 200988)
> +++ gcc/tree-vect-patterns.c (working copy)
> @@ -397,7 +397,7 @@ vect_recog_dot_prod_pattern (vec<gimple>
>            || !promotion)
>          return NULL;
>        oprnd00 = gimple_assign_rhs1 (def_stmt);
> -      if (!type_conversion_p (oprnd0, stmt, true, &half_type1, &def_stmt,
> +      if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
>                                  &promotion)
>            || !promotion)
>          return NULL;

Patch

Index: gcc/tree-vect-patterns.c
===================================================================
--- gcc/tree-vect-patterns.c (revision 200988)
+++ gcc/tree-vect-patterns.c (working copy)
@@ -397,7 +397,7 @@  vect_recog_dot_prod_pattern (vec<gimple>
           || !promotion)
         return NULL;
       oprnd00 = gimple_assign_rhs1 (def_stmt);
-      if (!type_conversion_p (oprnd0, stmt, true, &half_type1, &def_stmt,
+      if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
                                 &promotion)
           || !promotion)
         return NULL;