* Makefile.in (tree-vect-patterns.o): Add rule for new file.

        * tree-vect-analyze.c (vect_determine_vectorization_factor): Use
        existing STMT_VINFO_VECTYPE if available.
        (vect_mark_relevant): Add special handling for stmts that are
        marked as STMT_VINFO_IN_PATTERN_P.
        (vect_analyze_loop): Call vect_pattern_recog.
        * tree-vectorizer.c (new_stmt_vec_info): Initialize new fields.
        * tree-vectorizer.h (in_pattern_p, related_stmt): New fields in
        stmt_info.
        (STMT_VINFO_IN_PATTERN_P, STMT_VINFO_RELATED_STMT): New macros.
        (vect_recog_func_ptr): New function-pointer type.
        * tree-vect-patterns.c: New file.
        (vect_recog_widen_sum_pattern, vect_recog_widen_mult_pattern):
        (vect_recog_dot_prod_pattern, vect_pattern_recog):
        (vect_pattern_recog_1): New functions.
        (vect_pattern_recog_funcs): New array of function pointers.

        * tree-vectorizer.h (ternary_op): New enum value.
        * tree-vect-transform.c (vect_create_epilog_for_reduction): Added
        declaration. Revised documentation. Removed redundant dump prints.
        Removed redundant argument. Added support for reduction patterns.
        (vectorizable_reduction): Added support for reduction patterns.
        (vect_transform_stmt): Added support for patterns.

        * expr.c (expand_expr_real_1): Added case for DOT_PROD_EXPR.
        * genopinit.c (udot_prod_optab, sdot_prod_optab): Initialize.
        * optabs.c (optab_for_tree_code): Added case for DOT_PROD_EXPR.
        (expand_widen_pattern_expr): New function.
        (init_optabs): Initialize new optabs udot_prod_optab,
        sdot_prod_optab.
        * optabs.h (OTI_sdot_prod, OTI_udot_prod): New.
        (sdot_prod_optab, udot_prod_optab): Define new optabs.
        (expand_widen_pattern_expr): New function declaration.
        * tree.def (DOT_PROD_EXPR, WIDEN_SUM_EXPR, WIDEN_MULT_EXPR): New
        tree-codes.
        * tree-inline.c (estimate_num_insns_1): Added cases for new
        tree-codes DOT_PROD_EXPR, WIDEN_SUM_EXPR, WIDEN_MULT_EXPR.
        * tree-pretty-print.c (dump_generic_node): Likewise.
        (op_prio): Likewise.
        (op_symbol): Added cases for WIDEN_SUM_EXPR, WIDEN_MULT_EXPR.
        * tree-ssa-operands.c (get_expr_operands): Added case for
        DOT_PROD_EXPR.
        * tree-vect-patterns.c (widened_name_p): New function.
        (vect_recog_dot_prod_pattern): Added function implementation.
        * tree-vect-transform.c (get_initial_def_for_reduction): Added
        cases for DOT_PROD_EXPR, WIDEN_SUM_EXPR.
        * config/rs6000/altivec.md (udot_prod<mode>, sdot_prodv8hi): New.
        * config/i386/sse.md (sdot_prodv8hi, udot_prodv4si): New.

        * expr.c (expand_expr_real_1): Added case for WIDEN_SUM_EXPR.
        * genopinit.c (widen_ssum_optab, widen_usum_optab): Initialize.
        * optabs.c (optab_for_tree_code): Added case for WIDEN_SUM_EXPR.
        (init_optabs): Initialize new optabs widen_ssum_optab,
        widen_usum_optab.
        * optabs.h (OTI_widen_ssum, OTI_widen_usum): New.
        (widen_ssum_optab, widen_usum_optab): Define new optabs.
        * tree-vect-generic.c: (expand_vector_operations_1): Check type of
        use instead of type of def.
        * tree-vect-patterns.c (vect_recog_widen_sum_pattern): Added
        function implementation.
        * config/rs6000/altivec.md (widen_usum<mode>, widen_ssumv16qi,
        widen_ssumv8hi): New.

        * doc/tm.texi (ssum_widen, usum_widen, sdot_prod, udot_prod): New
        patterns.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@109954 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 637 insertions, 0 deletions

diff --git a/gcc/tree-vect-patterns.c b/gcc/tree-vect-patterns.c
new file mode 100644
index 00000000000..0ef76fe311a
--- /dev/null
+++ b/gcc/tree-vect-patterns.c
@@ -0,0 +1,637 @@
+/* Analysis Utilities for Loop Vectorization.
+   Copyright (C) 2006 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 2, 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 COPYING.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+#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 "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.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 "toplev.h"
+
+/* Funcion prototypes */
+static void vect_pattern_recog_1 
+  (tree (* ) (tree, tree *, tree *), block_stmt_iterator);
+static bool widened_name_p (tree, tree, tree *, tree *);
+
+/* Pattern recognition functions  */
+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
+
+   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. 
+*/
+
+static bool
+widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt)
+{
+  tree dummy;
+  loop_vec_info loop_vinfo;
+  stmt_vec_info stmt_vinfo;
+  tree expr;
+  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, loop_vinfo, def_stmt, &def, &dt))
+    return false;
+
+  if (dt != vect_loop_def
+      && dt != vect_invariant_def && dt != vect_constant_def)
+    return false;
+
+  if (! *def_stmt)
+    return false;
+
+  if (TREE_CODE (*def_stmt) != MODIFY_EXPR)
+    return false;
+
+  expr = TREE_OPERAND (*def_stmt, 1);
+  if (TREE_CODE (expr) != NOP_EXPR)
+    return false;
+
+  oprnd0 = TREE_OPERAND (expr, 0);
+
+  *half_type = TREE_TYPE (oprnd0);
+  if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
+      || (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type))
+      || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
+    return false;
+
+  if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy, &dummy, &dt))
+    return false;
+
+  if (dt != vect_invariant_def && dt != vect_constant_def
+      && dt != vect_loop_def)
+    return false;
+
+  return true;
+}
+
+
+/* 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 sepcial case of a reduction 
+   computation.
+      
+   Input:
+
+   * LAST_STMT: 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>
+*/
+
+static tree
+vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out)
+{
+  tree stmt, expr;
+  tree oprnd0, oprnd1;
+  tree oprnd00, oprnd01;
+  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
+  tree type, half_type;
+  tree pattern_expr;
+  tree prod_type;
+
+  if (TREE_CODE (last_stmt) != MODIFY_EXPR)
+    return NULL;
+
+  expr = TREE_OPERAND (last_stmt, 1);
+  type = TREE_TYPE (expr);
+
+  /* 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 (TREE_CODE (expr) != 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);
+      expr = TREE_OPERAND (stmt, 1);
+      type = TREE_TYPE (expr);
+      if (TREE_CODE (expr) != WIDEN_SUM_EXPR)
+        return NULL;
+      oprnd0 = TREE_OPERAND (expr, 0);
+      oprnd1 = TREE_OPERAND (expr, 1);
+      half_type = TREE_TYPE (oprnd0);
+    }
+  else
+    {
+      tree def_stmt;
+
+      if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
+        return NULL;
+      oprnd0 = TREE_OPERAND (expr, 0);
+      oprnd1 = TREE_OPERAND (expr, 1);
+      if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
+          || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
+        return NULL;
+      stmt = last_stmt;
+
+      if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt))
+        {
+          stmt = def_stmt;
+          expr = TREE_OPERAND (stmt, 1);
+          oprnd0 = TREE_OPERAND (expr, 0);
+        }
+      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  */
+
+  prod_type = half_type;
+  stmt = SSA_NAME_DEF_STMT (oprnd0);
+  gcc_assert (stmt);
+  stmt_vinfo = vinfo_for_stmt (stmt);
+  gcc_assert (stmt_vinfo);
+  gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
+  expr = TREE_OPERAND (stmt, 1);
+  if (TREE_CODE (expr) != 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);
+      expr = TREE_OPERAND (stmt, 1);
+      if (TREE_CODE (expr) != WIDEN_MULT_EXPR)
+        return NULL;
+      stmt_vinfo = vinfo_for_stmt (stmt);
+      gcc_assert (stmt_vinfo);
+      gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
+      oprnd00 = TREE_OPERAND (expr, 0);
+      oprnd01 = TREE_OPERAND (expr, 1);
+    }
+  else
+    {
+      tree half_type0, half_type1;
+      tree def_stmt;
+      tree oprnd0, oprnd1;
+
+      oprnd0 = TREE_OPERAND (expr, 0);
+      oprnd1 = TREE_OPERAND (expr, 1);
+      if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) 
+				!= TYPE_MAIN_VARIANT (prod_type)
+          || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) 
+				!= TYPE_MAIN_VARIANT (prod_type))
+        return NULL;
+      if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt))
+        return NULL;
+      oprnd00 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
+      if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt))
+        return NULL;
+      oprnd01 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
+      if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (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: */
+  pattern_expr = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1);
+  if (vect_print_dump_info (REPORT_DETAILS))
+    {
+      fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
+      print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
+    }
+  return pattern_expr;
+}
+
+
+/* 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'.
+
+   Input:
+
+   * LAST_STMT: A stmt from which the pattern search begins. In the example,
+   when this function is called with S5, the pattern {S3,S4,S5} is 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_MULT <a_t, b_t>
+*/
+
+static tree
+vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED, 
+			       tree *type_in ATTRIBUTE_UNUSED, 
+			       tree *type_out ATTRIBUTE_UNUSED)
+{
+  /* Yet to be implemented.   */
+  return NULL;
+}
+
+
+/* Function vect_recog_widen_sum_pattern
+
+   Try to find the following pattern:
+
+     type x_t; 
+     TYPE x_T, sum = init;
+   loop:
+     sum_0 = phi <init, sum_1>
+     S1  x_t = *p;
+     S2  x_T = (TYPE) x_t;
+     S3  sum_1 = x_T + sum_0;
+
+   where type 'TYPE' is at least double the size of type 'type', i.e - we're 
+   summing elements of type 'type' into an accumulator of type 'TYPE'. This is
+   a sepcial case of a reduction computation.
+
+   Input:
+
+   * LAST_STMT: A stmt from which the pattern search begins. In the example,
+   when this function is called with S3, the pattern {S2,S3} 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_SUM <x_t, sum_0>
+*/
+
+static tree
+vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
+{
+  tree stmt, expr;
+  tree oprnd0, oprnd1;
+  stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
+  tree type, half_type;
+  tree pattern_expr;
+
+  if (TREE_CODE (last_stmt) != MODIFY_EXPR)
+    return NULL;
+
+  expr = TREE_OPERAND (last_stmt, 1);
+  type = TREE_TYPE (expr);
+
+  /* Look for the following pattern
+          DX = (TYPE) X;
+          sum_1 = DX + sum_0;
+     In which DX is at least double the size of X, and sum_1 has been
+     recognized as a reduction variable.
+   */
+
+  /* Starting from LAST_STMT, follow the defs of its uses in search
+     of the above pattern.  */
+
+  if (TREE_CODE (expr) != PLUS_EXPR)
+    return NULL;
+
+  if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
+    return NULL;
+
+  oprnd0 = TREE_OPERAND (expr, 0);
+  oprnd1 = TREE_OPERAND (expr, 1);
+  if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
+      || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
+    return NULL;
+
+  /* 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 cast from type 'type' to type
+     'TYPE'.  */
+
+  if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
+    return NULL;
+
+  oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
+  *type_in = half_type;
+  *type_out = type;
+
+  /* Pattern detected. Create a stmt to be used to replace the pattern: */
+  pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1);
+  if (vect_print_dump_info (REPORT_DETAILS))
+    {
+      fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
+      print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
+    }
+  return pattern_expr;
+}
+
+
+/* Function vect_pattern_recog_1 
+
+   Input:
+   PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
+        computation pattern.
+   STMT: A stmt from which the pattern search should start.
+
+   If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
+   expression that computes the same functionality and can be used to 
+   replace the sequence of stmts that are involved in the pattern. 
+
+   Output:
+   This function checks if the expression returned by PATTERN_RECOG_FUNC is 
+   supported in vector form by the target.  We use 'TYPE_IN' to obtain the 
+   relevant vector type. If 'TYPE_IN' is already a vector type, then this 
+   indicates that target support had already been checked by PATTERN_RECOG_FUNC.
+   If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
+   to the available target pattern.
+
+   This function also does some bookeeping, as explained in the documentation 
+   for vect_recog_pattern.  */
+
+static void
+vect_pattern_recog_1 (
+	tree (* vect_recog_func_ptr) (tree, tree *, tree *),
+	block_stmt_iterator si)
+{
+  tree stmt = bsi_stmt (si);
+  stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
+  stmt_vec_info pattern_stmt_info;
+  loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
+  tree pattern_expr;
+  tree pattern_vectype;
+  tree type_in, type_out;
+  tree pattern_type;
+  enum tree_code code;
+  tree var, var_name;
+  stmt_ann_t ann;
+
+  pattern_expr = (* vect_recog_func_ptr) (stmt, &type_in, &type_out);
+  if (!pattern_expr) 
+    return; 
+ 
+  if (VECTOR_MODE_P (TYPE_MODE (type_in))) 
+    { 
+      /* No need to check target support (already checked by the pattern 
+         recognition function).  */ 
+      pattern_vectype = type_in;
+    }
+  else
+    {
+      enum tree_code vec_mode;
+      enum insn_code icode;
+      optab optab;
+
+      /* Check target support  */
+      pattern_vectype = get_vectype_for_scalar_type (type_in);
+      optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype);
+      vec_mode = TYPE_MODE (pattern_vectype);
+      if (!optab
+          || (icode = optab->handlers[(int) vec_mode].insn_code) ==
+              CODE_FOR_nothing
+          || (type_out
+              && (insn_data[icode].operand[0].mode !=
+                  TYPE_MODE (get_vectype_for_scalar_type (type_out)))))
+	return;
+    }
+
+  /* Found a vectorizable pattern.  */
+  if (vect_print_dump_info (REPORT_DETAILS))
+    {
+      fprintf (vect_dump, "pattern recognized: "); 
+      print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
+    }
+  
+  /* Mark the stmts that are involved in the pattern,
+     create a new stmt to express the pattern and insert it.  */
+  code = TREE_CODE (pattern_expr);
+  pattern_type = TREE_TYPE (pattern_expr);
+  var = create_tmp_var (pattern_type, "patt");
+  add_referenced_tmp_var (var);
+  var_name = make_ssa_name (var, NULL_TREE);
+  pattern_expr = build2 (MODIFY_EXPR, void_type_node, var_name, pattern_expr);
+  SSA_NAME_DEF_STMT (var_name) = pattern_expr;
+  bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT);
+  ann = stmt_ann (pattern_expr);
+  set_stmt_info ((tree_ann_t)ann, new_stmt_vec_info (pattern_expr, loop_vinfo));
+  pattern_stmt_info = vinfo_for_stmt (pattern_expr);
+  
+  STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
+  STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
+  STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
+  STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
+  STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr;
+
+  return;
+}
+
+
+/* Function vect_pattern_recog
+
+   Input:
+   LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
+        computation idioms.
+
+   Output - for each computation idiom that is detected we insert a new stmt
+        that provides the same functionality and that can be vectorized. We
+        also record some information in the struct_stmt_info of the relevant
+        stmts, as explained below:
+
+   At the entry to this function we have the following stmts, with the
+   following initial value in the STMT_VINFO fields:
+
+         stmt                     in_pattern_p  related_stmt    vec_stmt
+         S1: a_i = ....                 -       -               -
+         S2: a_2 = ..use(a_i)..         -       -               -
+         S3: a_1 = ..use(a_2)..         -       -               -
+         S4: a_0 = ..use(a_1)..         -       -               -
+         S5: ... = ..use(a_0)..         -       -               -
+
+   Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
+   represented by a single stmt. We then:
+   - create a new stmt S6 that will replace the pattern.
+   - insert the new stmt S6 before the last stmt in the pattern
+   - fill in the STMT_VINFO fields as follows:
+
+                                  in_pattern_p  related_stmt    vec_stmt
+         S1: a_i = ....                 -       -               -       
+         S2: a_2 = ..use(a_i)..         -       -               -
+         S3: a_1 = ..use(a_2)..         -       -               -
+       > S6: a_new = ....               -       S4              -
+         S4: a_0 = ..use(a_1)..         true    S6              -
+         S5: ... = ..use(a_0)..         -       -               -
+
+   (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
+    to each other through the RELATED_STMT field).
+
+   S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
+   of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
+   remain irrelevant unless used by stmts other than S4.
+
+   If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
+   (because they are marked as irrelevent). It will vectorize S6, and record
+   a pointer to the new vector stmt VS6 both from S6 (as usual), and also 
+   from S4. We do that so that when we get to vectorizing stmts that use the
+   def of S4 (like S5 that uses a_0), we'll know where to take the relevant
+   vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
+
+                                  in_pattern_p  related_stmt    vec_stmt
+         S1: a_i = ....                 -       -               -
+         S2: a_2 = ..use(a_i)..         -       -               -
+         S3: a_1 = ..use(a_2)..         -       -               -
+       > VS6: va_new = ....             -       -               -
+         S6: a_new = ....               -       S4              VS6
+         S4: a_0 = ..use(a_1)..         true    S6              VS6
+       > VS5: ... = ..vuse(va_new)..    -       -               -
+         S5: ... = ..use(a_0)..         -       -               -
+
+   DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
+   elsewhere), and we'll end up with:
+
+        VS6: va_new = .... 
+        VS5: ... = ..vuse(va_new)..
+
+   If vectorization does not succeed, DCE will clean S6 away (its def is
+   not used), and we'll end up with the original sequence.
+*/
+
+void
+vect_pattern_recog (loop_vec_info loop_vinfo)
+{
+  struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+  basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
+  unsigned int nbbs = loop->num_nodes;
+  block_stmt_iterator si;
+  tree stmt;
+  unsigned int i, j;
+  tree (* vect_recog_func_ptr) (tree, tree *, tree *);
+
+  if (vect_print_dump_info (REPORT_DETAILS))
+    fprintf (vect_dump, "=== vect_pattern_recog ===");
+
+  /* Scan through the loop stmts, applying the pattern recognition
+     functions starting at each stmt visited:  */
+  for (i = 0; i < nbbs; i++)
+    {
+      basic_block bb = bbs[i];
+      for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+        {
+          stmt = bsi_stmt (si);
+
+          /* Scan over all generic vect_recog_xxx_pattern functions.  */
+          for (j = 0; j < NUM_PATTERNS; j++)
+            {
+              vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
+              vect_pattern_recog_1 (vect_recog_func_ptr, si);
+            }
+        }
+    }
+}