gcc/tree-vect-patterns.c

   1 /* Analysis Utilities for Loop Vectorization.
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3    Contributed by Dorit Nuzman <dorit@il.ibm.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28
  29 #include "target.h"
  30 #include "basic-block.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "expr.h"
  37 #include "optabs.h"
  38 #include "params.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-vectorizer.h"
  41 #include "recog.h"
  42 #include "toplev.h"
  43
  44 /* Function prototypes */
  45 static void vect_pattern_recog_1
  46   (tree (* ) (tree, tree *, tree *), block_stmt_iterator);
  47 static bool widened_name_p (tree, tree, tree *, tree *);
  48
  49 /* Pattern recognition functions  */
  50 static tree vect_recog_widen_sum_pattern (tree, tree *, tree *);
  51 static tree vect_recog_widen_mult_pattern (tree, tree *, tree *);
  52 static tree vect_recog_dot_prod_pattern (tree, tree *, tree *);
  53 static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
  54         vect_recog_widen_mult_pattern,
  55         vect_recog_widen_sum_pattern,
  56         vect_recog_dot_prod_pattern};
  57
  58
  59 /* Function widened_name_p
  60
  61    Check whether NAME, an ssa-name used in USE_STMT,
  62    is a result of a type-promotion, such that:
  63      DEF_STMT: NAME = NOP (name0)
  64    where the type of name0 (HALF_TYPE) is smaller than the type of NAME.
  65 */
  66
  67 static bool
  68 widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt)
  69 {
  70   tree dummy;
  71   loop_vec_info loop_vinfo;
  72   stmt_vec_info stmt_vinfo;
  73   tree expr;
  74   tree type = TREE_TYPE (name);
  75   tree oprnd0;
  76   enum vect_def_type dt;
  77   tree def;
  78
  79   stmt_vinfo = vinfo_for_stmt (use_stmt);
  80   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
  81
  82   if (!vect_is_simple_use (name, loop_vinfo, def_stmt, &def, &dt))
  83     return false;
  84
  85   if (dt != vect_loop_def
  86       && dt != vect_invariant_def && dt != vect_constant_def)
  87     return false;
  88
  89   if (! *def_stmt)
  90     return false;
  91
  92   if (TREE_CODE (*def_stmt) != MODIFY_EXPR)
  93     return false;
  94
  95   expr = TREE_OPERAND (*def_stmt, 1);
  96   if (TREE_CODE (expr) != NOP_EXPR)
  97     return false;
  98
  99   oprnd0 = TREE_OPERAND (expr, 0);
 100
 101   *half_type = TREE_TYPE (oprnd0);
 102   if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
 103       || (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type))
 104       || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
 105     return false;
 106
 107   if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy, &dummy, &dt))
 108     return false;
 109
 110   if (dt != vect_invariant_def && dt != vect_constant_def
 111       && dt != vect_loop_def)
 112     return false;
 113
 114   return true;
 115 }
 116
 117
 118 /* Function vect_recog_dot_prod_pattern
 119
 120    Try to find the following pattern:
 121
 122      type x_t, y_t;
 123      TYPE1 prod;
 124      TYPE2 sum = init;
 125    loop:
 126      sum_0 = phi <init, sum_1>
 127      S1  x_t = ...
 128      S2  y_t = ...
 129      S3  x_T = (TYPE1) x_t;
 130      S4  y_T = (TYPE1) y_t;
 131      S5  prod = x_T * y_T;
 132      [S6  prod = (TYPE2) prod;  #optional]
 133      S7  sum_1 = prod + sum_0;
 134
 135    where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
 136    same size of 'TYPE1' or bigger. This is a special case of a reduction
 137    computation.
 138
 139    Input:
 140
 141    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 142    when this function is called with S7, the pattern {S3,S4,S5,S6,S7} will be
 143    detected.
 144
 145    Output:
 146
 147    * TYPE_IN: The type of the input arguments to the pattern.
 148
 149    * TYPE_OUT: The type of the output  of this pattern.
 150
 151    * Return value: A new stmt that will be used to replace the sequence of
 152    stmts that constitute the pattern. In this case it will be:
 153         WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
 154 */
 155
 156 static tree
 157 vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out)
 158 {
 159   tree stmt, expr;
 160   tree oprnd0, oprnd1;
 161   tree oprnd00, oprnd01;
 162   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 163   tree type, half_type;
 164   tree pattern_expr;
 165   tree prod_type;
 166
 167   if (TREE_CODE (last_stmt) != MODIFY_EXPR)
 168     return NULL;
 169
 170   expr = TREE_OPERAND (last_stmt, 1);
 171   type = TREE_TYPE (expr);
 172
 173   /* Look for the following pattern
 174           DX = (TYPE1) X;
 175           DY = (TYPE1) Y;
 176           DPROD = DX * DY;
 177           DDPROD = (TYPE2) DPROD;
 178           sum_1 = DDPROD + sum_0;
 179      In which
 180      - DX is double the size of X
 181      - DY is double the size of Y
 182      - DX, DY, DPROD all have the same type
 183      - sum is the same size of DPROD or bigger
 184      - sum has been recognized as a reduction variable.
 185
 186      This is equivalent to:
 187        DPROD = X w* Y;          #widen mult
 188        sum_1 = DPROD w+ sum_0;  #widen summation
 189      or
 190        DPROD = X w* Y;          #widen mult
 191        sum_1 = DPROD + sum_0;   #summation
 192    */
 193
 194   /* Starting from LAST_STMT, follow the defs of its uses in search
 195      of the above pattern.  */
 196
 197   if (TREE_CODE (expr) != PLUS_EXPR)
 198     return NULL;
 199
 200   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 201     {
 202       /* Has been detected as widening-summation?  */
 203
 204       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 205       expr = TREE_OPERAND (stmt, 1);
 206       type = TREE_TYPE (expr);
 207       if (TREE_CODE (expr) != WIDEN_SUM_EXPR)
 208         return NULL;
 209       oprnd0 = TREE_OPERAND (expr, 0);
 210       oprnd1 = TREE_OPERAND (expr, 1);
 211       half_type = TREE_TYPE (oprnd0);
 212     }
 213   else
 214     {
 215       tree def_stmt;
 216
 217       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 218         return NULL;
 219       oprnd0 = TREE_OPERAND (expr, 0);
 220       oprnd1 = TREE_OPERAND (expr, 1);
 221       if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 222           || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 223         return NULL;
 224       stmt = last_stmt;
 225
 226       if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt))
 227         {
 228           stmt = def_stmt;
 229           expr = TREE_OPERAND (stmt, 1);
 230           oprnd0 = TREE_OPERAND (expr, 0);
 231         }
 232       else
 233         half_type = type;
 234     }
 235
 236   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 237      we know that oprnd1 is the reduction variable (defined by a loop-header
 238      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 239      Left to check that oprnd0 is defined by a (widen_)mult_expr  */
 240
 241   prod_type = half_type;
 242   stmt = SSA_NAME_DEF_STMT (oprnd0);
 243   gcc_assert (stmt);
 244   stmt_vinfo = vinfo_for_stmt (stmt);
 245   gcc_assert (stmt_vinfo);
 246   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_loop_def)
 247     return NULL;
 248   expr = TREE_OPERAND (stmt, 1);
 249   if (TREE_CODE (expr) != MULT_EXPR)
 250     return NULL;
 251   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 252     {
 253       /* Has been detected as a widening multiplication?  */
 254
 255       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 256       expr = TREE_OPERAND (stmt, 1);
 257       if (TREE_CODE (expr) != WIDEN_MULT_EXPR)
 258         return NULL;
 259       stmt_vinfo = vinfo_for_stmt (stmt);
 260       gcc_assert (stmt_vinfo);
 261       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
 262       oprnd00 = TREE_OPERAND (expr, 0);
 263       oprnd01 = TREE_OPERAND (expr, 1);
 264     }
 265   else
 266     {
 267       tree half_type0, half_type1;
 268       tree def_stmt;
 269       tree oprnd0, oprnd1;
 270
 271       oprnd0 = TREE_OPERAND (expr, 0);
 272       oprnd1 = TREE_OPERAND (expr, 1);
 273       if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0))
 274                                 != TYPE_MAIN_VARIANT (prod_type)
 275           || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1))
 276                                 != TYPE_MAIN_VARIANT (prod_type))
 277         return NULL;
 278       if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt))
 279         return NULL;
 280       oprnd00 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
 281       if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt))
 282         return NULL;
 283       oprnd01 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
 284       if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
 285         return NULL;
 286       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
 287         return NULL;
 288     }
 289
 290   half_type = TREE_TYPE (oprnd00);
 291   *type_in = half_type;
 292   *type_out = type;
 293
 294   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 295   pattern_expr = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1);
 296   if (vect_print_dump_info (REPORT_DETAILS))
 297     {
 298       fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
 299       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 300     }
 301   return pattern_expr;
 302 }
 303
 304
 305 /* Function vect_recog_widen_mult_pattern
 306
 307    Try to find the following pattern:
 308
 309      type a_t, b_t;
 310      TYPE a_T, b_T, prod_T;
 311
 312      S1  a_t = ;
 313      S2  b_t = ;
 314      S3  a_T = (TYPE) a_t;
 315      S4  b_T = (TYPE) b_t;
 316      S5  prod_T = a_T * b_T;
 317
 318    where type 'TYPE' is at least double the size of type 'type'.
 319
 320    Input:
 321
 322    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 323    when this function is called with S5, the pattern {S3,S4,S5} is be detected.
 324
 325    Output:
 326
 327    * TYPE_IN: The type of the input arguments to the pattern.
 328
 329    * TYPE_OUT: The type of the output  of this pattern.
 330
 331    * Return value: A new stmt that will be used to replace the sequence of
 332    stmts that constitute the pattern. In this case it will be:
 333         WIDEN_MULT <a_t, b_t>
 334 */
 335
 336 static tree
 337 vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED,
 338                                tree *type_in ATTRIBUTE_UNUSED,
 339                                tree *type_out ATTRIBUTE_UNUSED)
 340 {
 341   /* Yet to be implemented.   */
 342   return NULL;
 343 }
 344
 345
 346 /* Function vect_recog_widen_sum_pattern
 347
 348    Try to find the following pattern:
 349
 350      type x_t;
 351      TYPE x_T, sum = init;
 352    loop:
 353      sum_0 = phi <init, sum_1>
 354      S1  x_t = *p;
 355      S2  x_T = (TYPE) x_t;
 356      S3  sum_1 = x_T + sum_0;
 357
 358    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 359    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 360    a special case of a reduction computation.
 361
 362    Input:
 363
 364    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 365    when this function is called with S3, the pattern {S2,S3} will be detected.
 366
 367    Output:
 368
 369    * TYPE_IN: The type of the input arguments to the pattern.
 370
 371    * TYPE_OUT: The type of the output of this pattern.
 372
 373    * Return value: A new stmt that will be used to replace the sequence of
 374    stmts that constitute the pattern. In this case it will be:
 375         WIDEN_SUM <x_t, sum_0>
 376 */
 377
 378 static tree
 379 vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
 380 {
 381   tree stmt, expr;
 382   tree oprnd0, oprnd1;
 383   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 384   tree type, half_type;
 385   tree pattern_expr;
 386
 387   if (TREE_CODE (last_stmt) != MODIFY_EXPR)
 388     return NULL;
 389
 390   expr = TREE_OPERAND (last_stmt, 1);
 391   type = TREE_TYPE (expr);
 392
 393   /* Look for the following pattern
 394           DX = (TYPE) X;
 395           sum_1 = DX + sum_0;
 396      In which DX is at least double the size of X, and sum_1 has been
 397      recognized as a reduction variable.
 398    */
 399
 400   /* Starting from LAST_STMT, follow the defs of its uses in search
 401      of the above pattern.  */
 402
 403   if (TREE_CODE (expr) != PLUS_EXPR)
 404     return NULL;
 405
 406   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 407     return NULL;
 408
 409   oprnd0 = TREE_OPERAND (expr, 0);
 410   oprnd1 = TREE_OPERAND (expr, 1);
 411   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 412       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 413     return NULL;
 414
 415   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 416      we know that oprnd1 is the reduction variable (defined by a loop-header
 417      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 418      Left to check that oprnd0 is defined by a cast from type 'type' to type
 419      'TYPE'.  */
 420
 421   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
 422     return NULL;
 423
 424   oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
 425   *type_in = half_type;
 426   *type_out = type;
 427
 428   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 429   pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1);
 430   if (vect_print_dump_info (REPORT_DETAILS))
 431     {
 432       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 433       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 434     }
 435   return pattern_expr;
 436 }
 437
 438
 439 /* Function vect_pattern_recog_1
 440
 441    Input:
 442    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
 443         computation pattern.
 444    STMT: A stmt from which the pattern search should start.
 445
 446    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
 447    expression that computes the same functionality and can be used to
 448    replace the sequence of stmts that are involved in the pattern.
 449
 450    Output:
 451    This function checks if the expression returned by PATTERN_RECOG_FUNC is
 452    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
 453    relevant vector type. If 'TYPE_IN' is already a vector type, then this
 454    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
 455    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
 456    to the available target pattern.
 457
 458    This function also does some bookkeeping, as explained in the documentation
 459    for vect_recog_pattern.  */
 460
 461 static void
 462 vect_pattern_recog_1 (
 463         tree (* vect_recog_func) (tree, tree *, tree *),
 464         block_stmt_iterator si)
 465 {
 466   tree stmt = bsi_stmt (si);
 467   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 468   stmt_vec_info pattern_stmt_info;
 469   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 470   tree pattern_expr;
 471   tree pattern_vectype;
 472   tree type_in, type_out;
 473   tree pattern_type;
 474   enum tree_code code;
 475   tree var, var_name;
 476   stmt_ann_t ann;
 477
 478   pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out);
 479   if (!pattern_expr)
 480     return;
 481
 482   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
 483     {
 484       /* No need to check target support (already checked by the pattern
 485          recognition function).  */
 486       pattern_vectype = type_in;
 487     }
 488   else
 489     {
 490       enum tree_code vec_mode;
 491       enum insn_code icode;
 492       optab optab;
 493
 494       /* Check target support  */
 495       pattern_vectype = get_vectype_for_scalar_type (type_in);
 496       optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype);
 497       vec_mode = TYPE_MODE (pattern_vectype);
 498       if (!optab
 499           || (icode = optab->handlers[(int) vec_mode].insn_code) ==
 500               CODE_FOR_nothing
 501           || (type_out
 502               && (insn_data[icode].operand[0].mode !=
 503                   TYPE_MODE (get_vectype_for_scalar_type (type_out)))))
 504         return;
 505     }
 506
 507   /* Found a vectorizable pattern.  */
 508   if (vect_print_dump_info (REPORT_DETAILS))
 509     {
 510       fprintf (vect_dump, "pattern recognized: ");
 511       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 512     }
 513
 514   /* Mark the stmts that are involved in the pattern,
 515      create a new stmt to express the pattern and insert it.  */
 516   code = TREE_CODE (pattern_expr);
 517   pattern_type = TREE_TYPE (pattern_expr);
 518   var = create_tmp_var (pattern_type, "patt");
 519   add_referenced_var (var);
 520   var_name = make_ssa_name (var, NULL_TREE);
 521   pattern_expr = build2 (MODIFY_EXPR, void_type_node, var_name, pattern_expr);
 522   SSA_NAME_DEF_STMT (var_name) = pattern_expr;
 523   bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT);
 524   ann = stmt_ann (pattern_expr);
 525   set_stmt_info (ann, new_stmt_vec_info (pattern_expr, loop_vinfo));
 526   pattern_stmt_info = vinfo_for_stmt (pattern_expr);
 527
 528   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
 529   STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
 530   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
 531   STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
 532   STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr;
 533
 534   return;
 535 }
 536
 537
 538 /* Function vect_pattern_recog
 539
 540    Input:
 541    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
 542         computation idioms.
 543
 544    Output - for each computation idiom that is detected we insert a new stmt
 545         that provides the same functionality and that can be vectorized. We
 546         also record some information in the struct_stmt_info of the relevant
 547         stmts, as explained below:
 548
 549    At the entry to this function we have the following stmts, with the
 550    following initial value in the STMT_VINFO fields:
 551
 552          stmt                     in_pattern_p  related_stmt    vec_stmt
 553          S1: a_i = ....                 -       -               -
 554          S2: a_2 = ..use(a_i)..         -       -               -
 555          S3: a_1 = ..use(a_2)..         -       -               -
 556          S4: a_0 = ..use(a_1)..         -       -               -
 557          S5: ... = ..use(a_0)..         -       -               -
 558
 559    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
 560    represented by a single stmt. We then:
 561    - create a new stmt S6 that will replace the pattern.
 562    - insert the new stmt S6 before the last stmt in the pattern
 563    - fill in the STMT_VINFO fields as follows:
 564
 565                                   in_pattern_p  related_stmt    vec_stmt
 566          S1: a_i = ....                 -       -               -
 567          S2: a_2 = ..use(a_i)..         -       -               -
 568          S3: a_1 = ..use(a_2)..         -       -               -
 569        > S6: a_new = ....               -       S4              -
 570          S4: a_0 = ..use(a_1)..         true    S6              -
 571          S5: ... = ..use(a_0)..         -       -               -
 572
 573    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
 574     to each other through the RELATED_STMT field).
 575
 576    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
 577    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
 578    remain irrelevant unless used by stmts other than S4.
 579
 580    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
 581    (because they are marked as irrelevant). It will vectorize S6, and record
 582    a pointer to the new vector stmt VS6 both from S6 (as usual), and also
 583    from S4. We do that so that when we get to vectorizing stmts that use the
 584    def of S4 (like S5 that uses a_0), we'll know where to take the relevant
 585    vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
 586
 587                                   in_pattern_p  related_stmt    vec_stmt
 588          S1: a_i = ....                 -       -               -
 589          S2: a_2 = ..use(a_i)..         -       -               -
 590          S3: a_1 = ..use(a_2)..         -       -               -
 591        > VS6: va_new = ....             -       -               -
 592          S6: a_new = ....               -       S4              VS6
 593          S4: a_0 = ..use(a_1)..         true    S6              VS6
 594        > VS5: ... = ..vuse(va_new)..    -       -               -
 595          S5: ... = ..use(a_0)..         -       -               -
 596
 597    DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
 598    elsewhere), and we'll end up with:
 599
 600         VS6: va_new = ....
 601         VS5: ... = ..vuse(va_new)..
 602
 603    If vectorization does not succeed, DCE will clean S6 away (its def is
 604    not used), and we'll end up with the original sequence.
 605 */
 606
 607 void
 608 vect_pattern_recog (loop_vec_info loop_vinfo)
 609 {
 610   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 611   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
 612   unsigned int nbbs = loop->num_nodes;
 613   block_stmt_iterator si;
 614   tree stmt;
 615   unsigned int i, j;
 616   tree (* vect_recog_func_ptr) (tree, tree *, tree *);
 617
 618   if (vect_print_dump_info (REPORT_DETAILS))
 619     fprintf (vect_dump, "=== vect_pattern_recog ===");
 620
 621   /* Scan through the loop stmts, applying the pattern recognition
 622      functions starting at each stmt visited:  */
 623   for (i = 0; i < nbbs; i++)
 624     {
 625       basic_block bb = bbs[i];
 626       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 627         {
 628           stmt = bsi_stmt (si);
 629
 630           /* Scan over all generic vect_recog_xxx_pattern functions.  */
 631           for (j = 0; j < NUM_PATTERNS; j++)
 632             {
 633               vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
 634               vect_pattern_recog_1 (vect_recog_func_ptr, si);
 635             }
 636         }
 637     }
 638 }