Subversion Repositories openrisc

/* Analysis Utilities for Loop Vectorization.

   Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012

   Free Software Foundation, Inc.

   Contributed by Dorit Nuzman <dorit@il.ibm.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "ggc.h"

#include "tree.h"

#include "target.h"

#include "basic-block.h"

#include "gimple-pretty-print.h"

#include "tree-flow.h"

#include "tree-dump.h"

#include "cfgloop.h"

#include "expr.h"

#include "optabs.h"

#include "params.h"

#include "tree-data-ref.h"

#include "tree-vectorizer.h"

#include "recog.h"

#include "diagnostic-core.h"

/* Pattern recognition functions  */

static gimple vect_recog_widen_sum_pattern (VEC (gimple, heap) **, tree *,

                                            tree *);

static gimple vect_recog_widen_mult_pattern (VEC (gimple, heap) **, tree *,

                                             tree *);

static gimple vect_recog_dot_prod_pattern (VEC (gimple, heap) **, tree *,

                                           tree *);

static gimple vect_recog_pow_pattern (VEC (gimple, heap) **, tree *, tree *);

static gimple vect_recog_over_widening_pattern (VEC (gimple, heap) **, tree *,

                                                 tree *);

static gimple vect_recog_widen_shift_pattern (VEC (gimple, heap) **,

                                        tree *, tree *);

static gimple vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **,

                                                      tree *, tree *);

static gimple vect_recog_sdivmod_pow2_pattern (VEC (gimple, heap) **,

                                               tree *, tree *);

static gimple vect_recog_mixed_size_cond_pattern (VEC (gimple, heap) **,

                                                  tree *, tree *);

static gimple vect_recog_bool_pattern (VEC (gimple, heap) **, 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,

        vect_recog_over_widening_pattern,

        vect_recog_widen_shift_pattern,

        vect_recog_vector_vector_shift_pattern,

        vect_recog_sdivmod_pow2_pattern,

        vect_recog_mixed_size_cond_pattern,

        vect_recog_bool_pattern};

static inline void

append_pattern_def_seq (stmt_vec_info stmt_info, gimple stmt)

{

  gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),

                                      stmt);

}

static inline void

new_pattern_def_seq (stmt_vec_info stmt_info, gimple stmt)

{

  STMT_VINFO_PATTERN_DEF_SEQ (stmt_info) = NULL;

  append_pattern_def_seq (stmt_info, stmt);

}

/* Function widened_name_p

   Check whether NAME, an ssa-name used in USE_STMT,

   is a result of a type-promotion, such that:

     DEF_STMT: NAME = NOP (name0)

   where the type of name0 (HALF_TYPE) is smaller than the type of NAME.

   If CHECK_SIGN is TRUE, check that either both types are signed or both are

   unsigned.  */

static bool

widened_name_p (tree name, gimple use_stmt, tree *half_type, gimple *def_stmt,

                bool check_sign)

{

  tree dummy;

  gimple dummy_gimple;

  loop_vec_info loop_vinfo;

  stmt_vec_info stmt_vinfo;

  tree type = TREE_TYPE (name);

  tree oprnd0;

  enum vect_def_type dt;

  tree def;

  stmt_vinfo = vinfo_for_stmt (use_stmt);

  loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);

  if (!vect_is_simple_use (name, use_stmt, loop_vinfo, NULL, def_stmt, &def,

                           &dt))

    return false;

  if (dt != vect_internal_def

      && dt != vect_external_def && dt != vect_constant_def)

    return false;

  if (! *def_stmt)

    return false;

  if (!is_gimple_assign (*def_stmt))

    return false;

  if (gimple_assign_rhs_code (*def_stmt) != NOP_EXPR)

    return false;

  oprnd0 = gimple_assign_rhs1 (*def_stmt);

  *half_type = TREE_TYPE (oprnd0);

  if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)

      || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type)) && check_sign)

      || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))

    return false;

  if (!vect_is_simple_use (oprnd0, *def_stmt, loop_vinfo,

                           NULL, &dummy_gimple, &dummy, &dt))

    return false;

  return true;

}

/* Helper to return a new temporary for pattern of TYPE for STMT.  If STMT

   is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */

static tree

vect_recog_temp_ssa_var (tree type, gimple stmt)

{

  tree var = create_tmp_var (type, "patt");

  add_referenced_var (var);

  var = make_ssa_name (var, stmt);

  return var;

}

/* Function vect_recog_dot_prod_pattern

   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.

   Input:

   * STMTS: Contains a stmt from which the pattern search begins.  In the

   example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7}

   will be detected.

   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:

        WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>

   Note: The dot-prod idiom is a widening reduction pattern that is

         vectorized without preserving all the intermediate results. It

         produces only N/2 (widened) results (by summing up pairs of

         intermediate results) rather than all N results.  Therefore, we

         cannot allow this pattern when we want to get all the results and in

         the correct order (as is the case when this computation is in an

         inner-loop nested in an outer-loop that us being vectorized).  */

static gimple

vect_recog_dot_prod_pattern (VEC (gimple, heap) **stmts, tree *type_in,

                             tree *type_out)

{

  gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);

  tree oprnd0, oprnd1;

  tree oprnd00, oprnd01;

  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);

  tree type, half_type;

  gimple pattern_stmt;

  tree prod_type;

  loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);

  struct loop *loop = LOOP_VINFO_LOOP (loop_info);

  tree var;

  if (!is_gimple_assign (last_stmt))

    return NULL;

  type = gimple_expr_type (last_stmt);

  /* Look for the following pattern

          DX = (TYPE1) X;

          DY = (TYPE1) Y;

          DPROD = DX * DY;

          DDPROD = (TYPE2) DPROD;

          sum_1 = DDPROD + sum_0;

     In which

     - DX is double the size of X

     - DY is double the size of Y

     - DX, DY, DPROD all have the same type

     - sum is the same size of DPROD or bigger

     - sum has been recognized as a reduction variable.

     This is equivalent to:

       DPROD = X w* Y;          #widen mult

       sum_1 = DPROD w+ sum_0;  #widen summation

     or

       DPROD = X w* Y;          #widen mult

       sum_1 = DPROD + sum_0;   #summation

   */

  /* Starting from LAST_STMT, follow the defs of its uses in search

     of the above pattern.  */

  if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)

    return NULL;

  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))

    {

      /* Has been detected as widening-summation?  */

      stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);

      type = gimple_expr_type (stmt);

      if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)

        return NULL;

      oprnd0 = gimple_assign_rhs1 (stmt);

      oprnd1 = gimple_assign_rhs2 (stmt);

      half_type = TREE_TYPE (oprnd0);

    }

  else

    {

      gimple def_stmt;

      if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)

        return NULL;

      oprnd0 = gimple_assign_rhs1 (last_stmt);

      oprnd1 = gimple_assign_rhs2 (last_stmt);

      if (!types_compatible_p (TREE_TYPE (oprnd0), type)

          || !types_compatible_p (TREE_TYPE (oprnd1), type))

        return NULL;

      stmt = last_stmt;

      if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt, true))

        {

          stmt = def_stmt;

          oprnd0 = gimple_assign_rhs1 (stmt);

        }

      else

        half_type = type;

    }

  /* So far so good.  Since last_stmt was detected as a (summation) reduction,

     we know that oprnd1 is the reduction variable (defined by a loop-header

     phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.

     Left to check that oprnd0 is defined by a (widen_)mult_expr  */

  if (TREE_CODE (oprnd0) != SSA_NAME)

    return NULL;

  prod_type = half_type;

  stmt = SSA_NAME_DEF_STMT (oprnd0);

  /* It could not be the dot_prod pattern if the stmt is outside the loop.  */

  if (!gimple_bb (stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (stmt)))

    return NULL;

  /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi

     inside the loop (in case we are analyzing an outer-loop).  */

  if (!is_gimple_assign (stmt))

    return NULL;

  stmt_vinfo = vinfo_for_stmt (stmt);

  gcc_assert (stmt_vinfo);

  if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)

    return NULL;

  if (gimple_assign_rhs_code (stmt) != MULT_EXPR)

    return NULL;

  if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))

    {

      /* Has been detected as a widening multiplication?  */

      stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);

      if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR)

        return NULL;

      stmt_vinfo = vinfo_for_stmt (stmt);

      gcc_assert (stmt_vinfo);

      gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_internal_def);

      oprnd00 = gimple_assign_rhs1 (stmt);

      oprnd01 = gimple_assign_rhs2 (stmt);

    }

  else

    {

      tree half_type0, half_type1;

      gimple def_stmt;

      tree oprnd0, oprnd1;

      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 (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt, true))

        return NULL;

      oprnd00 = gimple_assign_rhs1 (def_stmt);

      if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt, true))

        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;

    }

  half_type = TREE_TYPE (oprnd00);

  *type_in = half_type;

  *type_out = type;

  /* Pattern detected. Create a stmt to be used to replace the pattern: */

  var = vect_recog_temp_ssa_var (type, NULL);

  pattern_stmt = gimple_build_assign_with_ops3 (DOT_PROD_EXPR, var,

                                                oprnd00, oprnd01, oprnd1);

  if (vect_print_dump_info (REPORT_DETAILS))

    {

      fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");

      print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);

    }

  /* We don't allow changing the order of the computation in the inner-loop

     when doing outer-loop vectorization.  */

  gcc_assert (!nested_in_vect_loop_p (loop, last_stmt));

  return pattern_stmt;

}

/* Handle widening operation by a constant.  At the moment we support MULT_EXPR

   and LSHIFT_EXPR.

   For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR

   we check that CONST_OPRND is less or equal to the size of HALF_TYPE.

   Otherwise, if the type of the result (TYPE) is at least 4 times bigger than

   HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE)

   that satisfies the above restrictions,  we can perform a widening opeartion

   from the intermediate type to TYPE and replace a_T = (TYPE) a_t;

   with a_it = (interm_type) a_t;  */

static bool

vect_handle_widen_op_by_const (gimple stmt, enum tree_code code,

                               tree const_oprnd, tree *oprnd,

                               VEC (gimple, heap) **stmts, tree type,

                               tree *half_type, gimple def_stmt)

{

  tree new_type, new_oprnd, tmp;

  gimple new_stmt;

  loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (vinfo_for_stmt (stmt));

  struct loop *loop = LOOP_VINFO_LOOP (loop_info);

  if (code != MULT_EXPR && code != LSHIFT_EXPR)

    return false;

  if (((code == MULT_EXPR && int_fits_type_p (const_oprnd, *half_type))

        || (code == LSHIFT_EXPR

            && compare_tree_int (const_oprnd, TYPE_PRECISION (*half_type))

                != 1))

      && TYPE_PRECISION (type) == (TYPE_PRECISION (*half_type) * 2))

    {

      /* CONST_OPRND is a constant of HALF_TYPE.  */

      *oprnd = gimple_assign_rhs1 (def_stmt);

      return true;

    }

  if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4)

      || !gimple_bb (def_stmt)

      || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))

      || !vinfo_for_stmt (def_stmt))

    return false;

  /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for

     a type 2 times bigger than HALF_TYPE.  */

  new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2,

                                             TYPE_UNSIGNED (type));

  if ((code == MULT_EXPR && !int_fits_type_p (const_oprnd, new_type))

      || (code == LSHIFT_EXPR

          && compare_tree_int (const_oprnd, TYPE_PRECISION (new_type)) == 1))

    return false;

  /* Use NEW_TYPE for widening operation.  */

  if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))

    {

      new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));

      /* Check if the already created pattern stmt is what we need.  */

      if (!is_gimple_assign (new_stmt)

          || gimple_assign_rhs_code (new_stmt) != NOP_EXPR

          || TREE_TYPE (gimple_assign_lhs (new_stmt)) != new_type)

        return false;

      VEC_safe_push (gimple, heap, *stmts, def_stmt);

      *oprnd = gimple_assign_lhs (new_stmt);

    }

  else

    {

      /* Create a_T = (NEW_TYPE) a_t;  */

      *oprnd = gimple_assign_rhs1 (def_stmt);

      tmp = create_tmp_var (new_type, NULL);

      add_referenced_var (tmp);

      new_oprnd = make_ssa_name (tmp, NULL);

      new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd, *oprnd,

                                               NULL_TREE);

      STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;

      VEC_safe_push (gimple, heap, *stmts, def_stmt);

      *oprnd = new_oprnd;

    }

  *half_type = new_type;

  return true;

}

/* Function vect_recog_widen_mult_pattern

   Try to find the following pattern:

     type a_t, b_t;

     TYPE a_T, b_T, prod_T;

     S1  a_t = ;

     S2  b_t = ;

     S3  a_T = (TYPE) a_t;

     S4  b_T = (TYPE) b_t;

     S5  prod_T = a_T * b_T;

   where type 'TYPE' is at least double the size of type 'type'.

   Also detect unsgigned cases:

     unsigned type a_t, b_t;

     unsigned TYPE u_prod_T;

     TYPE a_T, b_T, prod_T;

     S1  a_t = ;

     S2  b_t = ;

     S3  a_T = (TYPE) a_t;

     S4  b_T = (TYPE) b_t;

     S5  prod_T = a_T * b_T;

     S6  u_prod_T = (unsigned TYPE) prod_T;

   and multiplication by constants:

     type a_t;

     TYPE a_T, prod_T;

     S1  a_t = ;

     S3  a_T = (TYPE) a_t;

     S5  prod_T = a_T * CONST;

   A special case of multiplication by constants is when 'TYPE' is 4 times

   bigger than 'type', but CONST fits an intermediate type 2 times smaller

   than 'TYPE'.  In that case we create an additional pattern stmt for S3

   to create a variable of the intermediate type, and perform widen-mult

   on the intermediate type as well:

     type a_t;

     interm_type a_it;

     TYPE a_T, prod_T,  prod_T';

     S1  a_t = ;

     S3  a_T = (TYPE) a_t;

           '--> a_it = (interm_type) a_t;

     S5  prod_T = a_T * CONST;

           '--> prod_T' = a_it w* CONST;

   Input/Output:

   * STMTS: Contains a stmt from which the pattern search begins.  In the

   example, when this function is called with S5, the pattern {S3,S4,S5,(S6)}

   is detected.  In case of unsigned widen-mult, the original stmt (S5) is

   replaced with S6 in STMTS.  In case of multiplication by a constant

   of an intermediate type (the last case above), STMTS also contains S3

   (inserted before S5).

   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:

        WIDEN_MULT <a_t, b_t>

*/

static gimple

vect_recog_widen_mult_pattern (VEC (gimple, heap) **stmts,

                               tree *type_in, tree *type_out)

{

  gimple last_stmt = VEC_pop (gimple, *stmts);

  gimple def_stmt0, def_stmt1;

  tree oprnd0, oprnd1;

  tree type, half_type0, half_type1;

  gimple pattern_stmt;

  tree vectype, vectype_out = NULL_TREE;

  tree dummy;

  tree var;

  enum tree_code dummy_code;

  int dummy_int;

  VEC (tree, heap) *dummy_vec;

  bool op1_ok;

  if (!is_gimple_assign (last_stmt))

    return NULL;

  type = gimple_expr_type (last_stmt);

  /* Starting from LAST_STMT, follow the defs of its uses in search

     of the above pattern.  */

  if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)

    return NULL;

  oprnd0 = gimple_assign_rhs1 (last_stmt);

  oprnd1 = gimple_assign_rhs2 (last_stmt);

  if (!types_compatible_p (TREE_TYPE (oprnd0), type)

      || !types_compatible_p (TREE_TYPE (oprnd1), type))

    return NULL;

  /* Check argument 0.  */

  if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false))

    return NULL;

  /* Check argument 1.  */

  op1_ok = widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1, false);

  if (op1_ok)

    {

      oprnd0 = gimple_assign_rhs1 (def_stmt0);

      oprnd1 = gimple_assign_rhs1 (def_stmt1);

    }

  else

    {

      if (TREE_CODE (oprnd1) == INTEGER_CST

          && TREE_CODE (half_type0) == INTEGER_TYPE

          && vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1,

                                            &oprnd0, stmts, type,

                                            &half_type0, def_stmt0))

        half_type1 = half_type0;

      else

        return NULL;

    }

  /* Handle unsigned case.  Look for

     S6  u_prod_T = (unsigned TYPE) prod_T;

     Use unsigned TYPE as the type for WIDEN_MULT_EXPR.  */

  if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))

    {

      tree lhs = gimple_assign_lhs (last_stmt), use_lhs;

      imm_use_iterator imm_iter;

      use_operand_p use_p;

      int nuses = 0;

      gimple use_stmt = NULL;

      tree use_type;

      if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1))

        return NULL;

      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)

        {

          if (is_gimple_debug (USE_STMT (use_p)))

            continue;

          use_stmt = USE_STMT (use_p);

          nuses++;

        }

      if (nuses != 1 || !is_gimple_assign (use_stmt)

          || gimple_assign_rhs_code (use_stmt) != NOP_EXPR)

        return NULL;

      use_lhs = gimple_assign_lhs (use_stmt);

      use_type = TREE_TYPE (use_lhs);

      if (!INTEGRAL_TYPE_P (use_type)

          || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))

          || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))

        return NULL;

      type = use_type;

      last_stmt = use_stmt;

    }

  if (!types_compatible_p (half_type0, half_type1))

    return NULL;

  /* Pattern detected.  */

  if (vect_print_dump_info (REPORT_DETAILS))

    fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");

  /* Check target support  */

  vectype = get_vectype_for_scalar_type (half_type0);

  vectype_out = get_vectype_for_scalar_type (type);

  if (!vectype

      || !vectype_out

      || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt,

                                          vectype_out, vectype,

                                          &dummy, &dummy, &dummy_code,

                                          &dummy_code, &dummy_int, &dummy_vec))

    return NULL;

  *type_in = vectype;

  *type_out = vectype_out;

  /* Pattern supported. Create a stmt to be used to replace the pattern: */

  var = vect_recog_temp_ssa_var (type, NULL);

  pattern_stmt = gimple_build_assign_with_ops (WIDEN_MULT_EXPR, var, oprnd0,

                                               oprnd1);

  if (vect_print_dump_info (REPORT_DETAILS))

    print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);

  VEC_safe_push (gimple, heap, *stmts, last_stmt);

  return pattern_stmt;

}

/* 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 * x

   or

        x = sqrt (x)

*/

static gimple

vect_recog_pow_pattern (VEC (gimple, heap) **stmts, tree *type_in,

                        tree *type_out)

{

  gimple last_stmt = VEC_index (gimple, *stmts, 0);

  tree fn, base, exp = NULL;

  gimple stmt;

  tree var;

  if (!is_gimple_call (last_stmt) || gimple_call_lhs (last_stmt) == NULL)

    return NULL;

  fn = gimple_call_fndecl (last_stmt);

  if (fn == NULL_TREE || DECL_BUILT_IN_CLASS (fn) != BUILT_IN_NORMAL)

   return NULL;

  switch (DECL_FUNCTION_CODE (fn))

    {

    case BUILT_IN_POWIF:

    case BUILT_IN_POWI:

    case BUILT_IN_POWF:

    case BUILT_IN_POW:

      base = gimple_call_arg (last_stmt, 0);

      exp = gimple_call_arg (last_stmt, 1);

      if (TREE_CODE (exp) != REAL_CST

          && TREE_CODE (exp) != INTEGER_CST)

        return NULL;

      break;

    default:

      return NULL;

    }

  /* We now have a pow or powi builtin function call with a constant

     exponent.  */

  *type_out = NULL_TREE;

  /* Catch squaring.  */

  if ((host_integerp (exp, 0)

       && tree_low_cst (exp, 0) == 2)