Re: [PATCH][RFC] Do some vectorizer-friendly canonicalization before vectorization

[Dorit Nuzman <DORIT at il dot ibm dot com>]

Richard Guenther <rguenther@suse.de> wrote on 23/11/2006 00:38:20:

...
> >
> > There are a few issues here:
> >
> > (1) The tests fail on ppc because there's no vector support for
doubles, so
> > vectorization gives up even before it gets to the pattern_recog pass.
If
> > you want to leave the test as is (operating on doubles) you should
probably
> > add this:
> >       /* { dg-require-effective-target vect_double } */
>
> I see.  The testcases are only for testing the pattern recognition, so
> I can easily switch to float here.
>

(in which case you'd need to add
      /* { dg-require-effective-target vect_float } */
instead, but at least it will be applicable to more targets).

As for the rest - I'll sleep on it...

dorit

> > (3) With respect to checking target support for the pattern: the
general
> > scheme of things is that each 'vect_recog_X_pattern' function does one
of
> > the following (this is documented in the code, but maybe not clearly
> > enough):
> > - option1 (should be the default): leave it for the caller -
> > 'vect_pattern_recog_1' - to check target support. In this case
> > 'vect_recog_X_pattern' initializes 'type_in' to the original (scalar)
type
> > of the arguments of the pattern.
> > - option2: if the above is not applicable, the 'vect_recog_X_pattern'
> > function verifies target support for the pattern by itself, and
initializes
> > 'type_in' to the relevant vector_type.
> >
> > What you have in 'vect_recog_pow_pattern' is that you don't check
target
> > support, but you do initialize 'type_in' to a vector type:
> >       *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
> > which in turn makes 'vect_pattern_recog_1' think that it doesn't need
to
> > check target support for you.
> > I think in your case the first option applies for the mult, but the
second
> > option applies for the sqrt (cause the target-support check in
> > 'vect_pattern_recog_1' is not general enough - doesn't handle a
> > pattern_expr that is a function call).
>
> I didn't see the docs because they are at the vect_pattern_recog_1
> function.  I'll do a followup patch to address the issues.
>
> Looking closer at vect_pattern_recog_1 I see that it is somewhat tailored
> to new tree-codes (for which you need to check target support).  I was
> thinking about how to recognize for example
>
>    x_2 = sqrtf (y_2);
>    x_3 = 1.0/x_2;
>
> as rsqrt.  As this would be target dependent a suitable way would be
> to have a target hook that matches the vect_recog_X_pattern API.  It
> can then simply return a target builtin function recognized by the
> target function vectorized hook later.
>
> Also to recognizing pow (x, 1.5) as sqrt (x) * x with the current
> machinery seems impossible (I would need to insert an extra statement
> or have a non-gimple one gimplified).  Do you have an idea on how to
> best do this?
>
> > (4) Another bit to consider: if you want to check only whether a
pattern
> > was detected, regardless of available target support, you'd want to
have
> > another printout before the target-support check, like the other
> > 'vect_recog_X_pattern' functions have (otherwise you may need to add a
> > target keyword to be able to expect on which targets the tests succeed
or
> > not).
>
> I defer detecting support for the sqrt function to the function
> vectorizing machinery (which has the patch still pending) which seemed
> to work nicely with the support available and not, this case should
> work always (given support for double vector types).  So I'll just
> fix the prerequesites and operate on floats.
>
> Richard.
>
> > So, taking the last two points into account, a fix to the
> > tree-vect-patterns.c part of your patch would look something like the
> > following (this code was not built/tested):
> >
> > Index: tree-vect-patterns.c
> > ===================================================================
> > --- tree-vect-patterns.c        (revision 119088)
> > +++ tree-vect-patterns.c        (working copy)
> > @@ -434,6 +434,7 @@
> >    tree expr;
> >    tree type;
> >    tree fn, arglist, base, exp;
> > +  tree pattern_expr;
> >
> >    if (TREE_CODE (last_stmt) != MODIFY_EXPR)
> >      return NULL;
> > @@ -474,7 +475,16 @@
> >         && tree_low_cst (exp, 0) == 2)
> >        || (TREE_CODE (exp) == REAL_CST
> >            && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
> > -    return build2 (MULT_EXPR, TREE_TYPE (base), base, base);
> > +    {
> > +      pattern_expr =  build2 (MULT_EXPR, TREE_TYPE (base), base,
base);
> > +      if (vect_print_dump_info (REPORT_DETAILS))
> > +       {
> > +         fprintf (vect_dump, "vect_recog_pow_pattern: detected: ");
> > +         print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
> > +       }
> > +     *type_in = TREE_TYPE (base);
> > +     return pattern_expr;
> > +   }
> >
> >    /* Catch square root.  */
> >    if (TREE_CODE (exp) == REAL_CST
> > @@ -482,10 +492,22 @@
> >      {
> >        tree newfn = mathfn_built_in (TREE_TYPE (base), BUILT_IN_SQRT);
> >        tree newarglist = build_tree_list (NULL_TREE, base);
> > -      return build_function_call_expr (newfn, newarglist);
> > +
> > +      pattern_expr = build_function_call_expr (newfn, newarglist);
> > +      if (vect_print_dump_info (REPORT_DETAILS))
> > +       {
> > +         fprintf (vect_dump, "vect_recog_pow_pattern: detected: ");
> > +         print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
> > +       }
> > +
> > +      if ( supported by target ) /* TODO */
> > +       {
> > +         *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
> > +         return pattern_expr;
> > +       }
> >      }
> >
> >    return NULL_TREE;
> >
> >
> > and then in your testcases you can choose to have this change if you
don't
> > care about actual target support:
> >
> > @@ -10,5 +11,5 @@
> >      x[i] = __builtin_pow (x[i], 0.5);
> >  }
> >
> > -/* { dg-final { scan-tree-dump "pattern recognized" "vect" } } */
> > +/* { dg-final { scan-tree-dump "vect_recog_pow_pattern: detected"
"vect" }
> > } */
> >  /* { dg-final { cleanup-tree-dump "vect" } } */
> >
> > (or leave it as is if you do).
> >
> > Sorry I didn't notice these points before. I can test the fixed patch
on
> > ppc if that helps.
> >
> > dorit
> >
> >
> > > dorit
> > >
> > > > The sqrt transformation
> > > > will only be recognized after someone approves the vectorization
> > > > of builtins and I dig out my i386 backend patch to enable the
> > > > use of __builtin_ia32_sqrtpd and other SSE intrinsics we have
there.
> > > >
> > > > Richard.
> > > >
> > > > 2006-11-21  Richard Guenther  <rguenther@suse.de>
> > > >
> > > >    * tree-vectorizer.h (NUM_PATTERNS): Increase.
> > > >    * tree-vect-patterns.c (vect_vect_recog_func_ptrs): Add
> > > >    vect_recog_pow_pattern.
> > > >    (vect_recog_pow_pattern): New function.
> > > >
> > > >    * gcc.dg/vect/vect-pow-1.c: New testcase.
> > > >    * gcc.dg/vect/vect-pow-2.c: Likewise.
> > > >
> > > > Index: tree-vect-patterns.c
> > > > ===================================================================
> > > > *** tree-vect-patterns.c   (revision 119016)
> > > > --- tree-vect-patterns.c   (working copy)
> > > > *************** static bool widened_name_p (tree, tree,
> > > > *** 50,59 ****
> > > >   static tree vect_recog_widen_sum_pattern (tree, tree *, tree *);
> > > >   static tree vect_recog_widen_mult_pattern (tree, tree *, tree *);
> > > >   static tree vect_recog_dot_prod_pattern (tree, tree *, tree *);
> > > >   static vect_recog_func_ptr
vect_vect_recog_func_ptrs[NUM_PATTERNS] =
> > {
> > > >      vect_recog_widen_mult_pattern,
> > > >      vect_recog_widen_sum_pattern,
> > > > !    vect_recog_dot_prod_pattern};
> > > >
> > > >
> > > >   /* Function widened_name_p
> > > > --- 50,61 ----
> > > >   static tree vect_recog_widen_sum_pattern (tree, tree *, tree *);
> > > >   static tree vect_recog_widen_mult_pattern (tree, tree *, tree *);
> > > >   static tree vect_recog_dot_prod_pattern (tree, tree *, tree *);
> > > > + static tree vect_recog_pow_pattern (tree, tree *, tree *);
> > > >   static vect_recog_func_ptr
vect_vect_recog_func_ptrs[NUM_PATTERNS] =
> > {
> > > >      vect_recog_widen_mult_pattern,
> > > >      vect_recog_widen_sum_pattern,
> > > > !    vect_recog_dot_prod_pattern,
> > > > !    vect_recog_pow_pattern};
> > > >
> > > >
> > > >   /* Function widened_name_p
> > > > *************** vect_recog_widen_mult_pattern (tree last
> > > > *** 400,405 ****
> > > > --- 402,494 ----
> > > >   }
> > > >
> > > >
> > > > + /* Function vect_recog_pow_pattern
> > > > +
> > > > +    Try to find the following pattern:
> > > > +
> > > > +      x = POW (y, N);
> > > > +
> > > > +    with POW being one of pow, powf, powi, powif and N being
> > > > +    either 2 or 0.5.
> > > > +
> > > > +    Input:
> > > > +
> > > > +    * LAST_STMT: A stmt from which the pattern search begins.
> > > > +
> > > > +    Output:
> > > > +
> > > > +    * TYPE_IN: The type of the input arguments to the pattern.
> > > > +
> > > > +    * TYPE_OUT: The type of the output of this pattern.
> > > > +
> > > > +    * Return value: A new stmt that will be used to replace the
> > sequence
> > > of
> > > > +    stmts that constitute the pattern. In this case it will be:
> > > > +         x * x
> > > > +    or
> > > > +    sqrt (x)
> > > > + */
> > > > +
> > > > + static tree
> > > > + vect_recog_pow_pattern (tree last_stmt, tree *type_in, tree
> > *type_out)
> > > > + {
> > > > +   tree expr;
> > > > +   tree type;
> > > > +   tree fn, arglist, base, exp;
> > > > +
> > > > +   if (TREE_CODE (last_stmt) != MODIFY_EXPR)
> > > > +     return NULL;
> > > > +
> > > > +   expr = TREE_OPERAND (last_stmt, 1);
> > > > +   type = TREE_TYPE (expr);
> > > > +
> > > > +   if (TREE_CODE (expr) != CALL_EXPR)
> > > > +     return NULL_TREE;
> > > > +
> > > > +   fn = get_callee_fndecl (expr);
> > > > +   arglist = TREE_OPERAND (expr, 1);
> > > > +   switch (DECL_FUNCTION_CODE (fn))
> > > > +     {
> > > > +     case BUILT_IN_POWIF:
> > > > +     case BUILT_IN_POWI:
> > > > +     case BUILT_IN_POWF:
> > > > +     case BUILT_IN_POW:
> > > > +       base = TREE_VALUE (arglist);
> > > > +       exp = TREE_VALUE (TREE_CHAIN (arglist));
> > > > +       if (TREE_CODE (exp) != REAL_CST
> > > > +      && TREE_CODE (exp) != INTEGER_CST)
> > > > +         return NULL_TREE;
> > > > +       break;
> > > > +
> > > > +     default:;
> > > > +       return NULL_TREE;
> > > > +     }
> > > > +
> > > > +   /* We now have a pow or powi builtin function call with a
constant
> > > > +      exponent.  */
> > > > +
> > > > +   *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
> > > > +   *type_out = NULL_TREE;
> > > > +
> > > > +   /* Catch squaring.  */
> > > > +   if ((host_integerp (exp, 0)
> > > > +        && TREE_INT_CST_LOW (exp) == 2)
> > > > +       || (TREE_CODE (exp) == REAL_CST
> > > > +           && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
> > > > +     return build2 (MULT_EXPR, TREE_TYPE (base), base, base);
> > > > +
> > > > +   /* Catch square root.  */
> > > > +   if (TREE_CODE (exp) == REAL_CST
> > > > +       && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconsthalf))
> > > > +     {
> > > > +       tree newfn = mathfn_built_in (TREE_TYPE (base),
BUILT_IN_SQRT);
> > > > +       tree newarglist = build_tree_list (NULL_TREE, base);
> > > > +       return build_function_call_expr (newfn, newarglist);
> > > > +     }
> > > > +
> > > > +   return NULL_TREE;
> > > > + }
> > > > +
> > > > +
> > > >   /* Function vect_recog_widen_sum_pattern
> > > >
> > > >      Try to find the following pattern:
> > > > Index: tree-vectorizer.h
> > > > ===================================================================
> > > > *** tree-vectorizer.h   (revision 119016)
> > > > --- tree-vectorizer.h   (working copy)
> > > > *************** extern loop_vec_info vect_analyze_loop (
> > > > *** 357,363 ****
> > > >      Additional pattern recognition functions can (and will) be
added
> > > >      in the future.  */
> > > >   typedef tree (* vect_recog_func_ptr) (tree, tree *, tree *);
> > > > ! #define NUM_PATTERNS 3
> > > >   void vect_pattern_recog (loop_vec_info);
> > > >
> > > >
> > > > --- 357,363 ----
> > > >      Additional pattern recognition functions can (and will) be
added
> > > >      in the future.  */
> > > >   typedef tree (* vect_recog_func_ptr) (tree, tree *, tree *);
> > > > ! #define NUM_PATTERNS 4
> > > >   void vect_pattern_recog (loop_vec_info);
> > > >
> > > >
> > > > Index: testsuite/gcc.dg/vect/vect-pow-1.c
> > > > ===================================================================
> > > > *** testsuite/gcc.dg/vect/vect-pow-1.c   (revision 0)
> > > > --- testsuite/gcc.dg/vect/vect-pow-1.c   (revision 0)
> > > > ***************
> > > > *** 0 ****
> > > > --- 1,14 ----
> > > > + /* { dg-do compile } */
> > > > + /* { dg-options "-O2 -ftree-vectorize -ffast-math -fdump-tree-
> > > > vect-details" } */
> > > > +
> > > > + double x[256];
> > > > +
> > > > + void foo(void)
> > > > + {
> > > > +   int i;
> > > > +   for (i=0; i<256; ++i)
> > > > +     x[i] = x[i] * x[i];
> > > > + }
> > > > +
> > > > + /* { dg-final { scan-tree-dump "pattern recognized" "vect" } } */
> > > > + /* { dg-final { cleanup-tree-dump "vect" } } */
> > > > Index: testsuite/gcc.dg/vect/vect-pow-2.c
> > > > ===================================================================
> > > > *** testsuite/gcc.dg/vect/vect-pow-2.c   (revision 0)
> > > > --- testsuite/gcc.dg/vect/vect-pow-2.c   (revision 0)
> > > > ***************
> > > > *** 0 ****
> > > > --- 1,14 ----
> > > > + /* { dg-do compile } */
> > > > + /* { dg-options "-O2 -ftree-vectorize -fno-math-errno
-fdump-tree-
> > > > vect-details" } */
> > > > +
> > > > + double x[256];
> > > > +
> > > > + void foo(void)
> > > > + {
> > > > +   int i;
> > > > +   for (i=0; i<256; ++i)
> > > > +     x[i] = __builtin_pow (x[i], 0.5);
> > > > + }
> > > > +
> > > > + /* { dg-final { scan-tree-dump "pattern recognized" "vect" } } */
> > > > + /* { dg-final { cleanup-tree-dump "vect" } } */
> > >
> >
> >
>
> --
> Richard Guenther <rguenther@suse.de>
> Novell / SUSE Labs