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 /* Funcion 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 sepcial 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   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
 247   expr = TREE_OPERAND (stmt, 1);
 248   if (TREE_CODE (expr) != MULT_EXPR)
 249     return NULL;
 250   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 251     {
 252       /* Has been detected as a widening multiplication?  */
 253
 254       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 255       expr = TREE_OPERAND (stmt, 1);
 256       if (TREE_CODE (expr) != WIDEN_MULT_EXPR)
 257         return NULL;
 258       stmt_vinfo = vinfo_for_stmt (stmt);
 259       gcc_assert (stmt_vinfo);
 260       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
 261       oprnd00 = TREE_OPERAND (expr, 0);
 262       oprnd01 = TREE_OPERAND (expr, 1);
 263     }
 264   else
 265     {
 266       tree half_type0, half_type1;
 267       tree def_stmt;
 268       tree oprnd0, oprnd1;
 269
 270       oprnd0 = TREE_OPERAND (expr, 0);
 271       oprnd1 = TREE_OPERAND (expr, 1);
 272       if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0))
 273                                 != TYPE_MAIN_VARIANT (prod_type)
 274           || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1))
 275                                 != TYPE_MAIN_VARIANT (prod_type))
 276         return NULL;
 277       if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt))
 278         return NULL;
 279       oprnd00 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
 280       if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt))
 281         return NULL;
 282       oprnd01 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
 283       if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
 284         return NULL;
 285       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
 286         return NULL;
 287     }
 288
 289   half_type = TREE_TYPE (oprnd00);
 290   *type_in = half_type;
 291   *type_out = type;
 292
 293   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 294   pattern_expr = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1);
 295   if (vect_print_dump_info (REPORT_DETAILS))
 296     {
 297       fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
 298       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 299     }
 300   return pattern_expr;
 301 }
 302
 303
 304 /* Function vect_recog_widen_mult_pattern
 305
 306    Try to find the following pattern:
 307
 308      type a_t, b_t;
 309      TYPE a_T, b_T, prod_T;
 310
 311      S1  a_t = ;
 312      S2  b_t = ;
 313      S3  a_T = (TYPE) a_t;
 314      S4  b_T = (TYPE) b_t;
 315      S5  prod_T = a_T * b_T;
 316
 317    where type 'TYPE' is at least double the size of type 'type'.
 318
 319    Input:
 320
 321    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 322    when this function is called with S5, the pattern {S3,S4,S5} is be detected.
 323
 324    Output:
 325
 326    * TYPE_IN: The type of the input arguments to the pattern.
 327
 328    * TYPE_OUT: The type of the output  of this pattern.
 329
 330    * Return value: A new stmt that will be used to replace the sequence of
 331    stmts that constitute the pattern. In this case it will be:
 332         WIDEN_MULT <a_t, b_t>
 333 */
 334
 335 static tree
 336 vect_recog_widen_mult_pattern (tree last_stmt ATTRIBUTE_UNUSED,
 337                                tree *type_in ATTRIBUTE_UNUSED,
 338                                tree *type_out ATTRIBUTE_UNUSED)
 339 {
 340   /* Yet to be implemented.   */
 341   return NULL;
 342 }
 343
 344
 345 /* Function vect_recog_widen_sum_pattern
 346
 347    Try to find the following pattern:
 348
 349      type x_t;
 350      TYPE x_T, sum = init;
 351    loop:
 352      sum_0 = phi <init, sum_1>
 353      S1  x_t = *p;
 354      S2  x_T = (TYPE) x_t;
 355      S3  sum_1 = x_T + sum_0;
 356
 357    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 358    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 359    a sepcial case of a reduction computation.
 360
 361    Input:
 362
 363    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 364    when this function is called with S3, the pattern {S2,S3} will be detected.
 365
 366    Output:
 367
 368    * TYPE_IN: The type of the input arguments to the pattern.
 369
 370    * TYPE_OUT: The type of the output of this pattern.
 371
 372    * Return value: A new stmt that will be used to replace the sequence of
 373    stmts that constitute the pattern. In this case it will be:
 374         WIDEN_SUM <x_t, sum_0>
 375 */
 376
 377 static tree
 378 vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
 379 {
 380   tree stmt, expr;
 381   tree oprnd0, oprnd1;
 382   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 383   tree type, half_type;
 384   tree pattern_expr;
 385
 386   if (TREE_CODE (last_stmt) != MODIFY_EXPR)
 387     return NULL;
 388
 389   expr = TREE_OPERAND (last_stmt, 1);
 390   type = TREE_TYPE (expr);
 391
 392   /* Look for the following pattern
 393           DX = (TYPE) X;
 394           sum_1 = DX + sum_0;
 395      In which DX is at least double the size of X, and sum_1 has been
 396      recognized as a reduction variable.
 397    */
 398
 399   /* Starting from LAST_STMT, follow the defs of its uses in search
 400      of the above pattern.  */
 401
 402   if (TREE_CODE (expr) != PLUS_EXPR)
 403     return NULL;
 404
 405   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 406     return NULL;
 407
 408   oprnd0 = TREE_OPERAND (expr, 0);
 409   oprnd1 = TREE_OPERAND (expr, 1);
 410   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 411       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 412     return NULL;
 413
 414   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 415      we know that oprnd1 is the reduction variable (defined by a loop-header
 416      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 417      Left to check that oprnd0 is defined by a cast from type 'type' to type
 418      'TYPE'.  */
 419
 420   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
 421     return NULL;
 422
 423   oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
 424   *type_in = half_type;
 425   *type_out = type;
 426
 427   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 428   pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1);
 429   if (vect_print_dump_info (REPORT_DETAILS))
 430     {
 431       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 432       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 433     }
 434   return pattern_expr;
 435 }
 436
 437
 438 /* Function vect_pattern_recog_1
 439
 440    Input:
 441    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
 442         computation pattern.
 443    STMT: A stmt from which the pattern search should start.
 444
 445    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
 446    expression that computes the same functionality and can be used to
 447    replace the sequence of stmts that are involved in the pattern.
 448
 449    Output:
 450    This function checks if the expression returned by PATTERN_RECOG_FUNC is
 451    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
 452    relevant vector type. If 'TYPE_IN' is already a vector type, then this
 453    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
 454    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
 455    to the available target pattern.
 456
 457    This function also does some bookeeping, as explained in the documentation
 458    for vect_recog_pattern.  */
 459
 460 static void
 461 vect_pattern_recog_1 (
 462         tree (* vect_recog_func) (tree, tree *, tree *),
 463         block_stmt_iterator si)
 464 {
 465   tree stmt = bsi_stmt (si);
 466   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 467   stmt_vec_info pattern_stmt_info;
 468   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 469   tree pattern_expr;
 470   tree pattern_vectype;
 471   tree type_in, type_out;
 472   tree pattern_type;
 473   enum tree_code code;
 474   tree var, var_name;
 475   stmt_ann_t ann;
 476
 477   pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out);
 478   if (!pattern_expr)
 479     return;
 480
 481   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
 482     {
 483       /* No need to check target support (already checked by the pattern
 484          recognition function).  */
 485       pattern_vectype = type_in;
 486     }
 487   else
 488     {
 489       enum tree_code vec_mode;
 490       enum insn_code icode;
 491       optab optab;
 492
 493       /* Check target support  */
 494       pattern_vectype = get_vectype_for_scalar_type (type_in);
 495       optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype);
 496       vec_mode = TYPE_MODE (pattern_vectype);
 497       if (!optab
 498           || (icode = optab->handlers[(int) vec_mode].insn_code) ==
 499               CODE_FOR_nothing
 500           || (type_out
 501               && (insn_data[icode].operand[0].mode !=
 502                   TYPE_MODE (get_vectype_for_scalar_type (type_out)))))
 503         return;
 504     }
 505
 506   /* Found a vectorizable pattern.  */
 507   if (vect_print_dump_info (REPORT_DETAILS))
 508     {
 509       fprintf (vect_dump, "pattern recognized: ");
 510       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 511     }
 512
 513   /* Mark the stmts that are involved in the pattern,
 514      create a new stmt to express the pattern and insert it.  */
 515   code = TREE_CODE (pattern_expr);
 516   pattern_type = TREE_TYPE (pattern_expr);
 517   var = create_tmp_var (pattern_type, "patt");
 518   add_referenced_tmp_var (var);
 519   var_name = make_ssa_name (var, NULL_TREE);
 520   pattern_expr = build2 (MODIFY_EXPR, void_type_node, var_name, pattern_expr);
 521   SSA_NAME_DEF_STMT (var_name) = pattern_expr;
 522   bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT);
 523   ann = stmt_ann (pattern_expr);
 524   set_stmt_info ((tree_ann_t)ann, new_stmt_vec_info (pattern_expr, loop_vinfo));
 525   pattern_stmt_info = vinfo_for_stmt (pattern_expr);
 526
 527   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
 528   STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
 529   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
 530   STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
 531   STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr;
 532
 533   return;
 534 }
 535
 536
 537 /* Function vect_pattern_recog
 538
 539    Input:
 540    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
 541         computation idioms.
 542
 543    Output - for each computation idiom that is detected we insert a new stmt
 544         that provides the same functionality and that can be vectorized. We
 545         also record some information in the struct_stmt_info of the relevant
 546         stmts, as explained below:
 547
 548    At the entry to this function we have the following stmts, with the
 549    following initial value in the STMT_VINFO fields:
 550
 551          stmt                     in_pattern_p  related_stmt    vec_stmt
 552          S1: a_i = ....                 -       -               -
 553          S2: a_2 = ..use(a_i)..         -       -               -
 554          S3: a_1 = ..use(a_2)..         -       -               -
 555          S4: a_0 = ..use(a_1)..         -       -               -
 556          S5: ... = ..use(a_0)..         -       -               -
 557
 558    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
 559    represented by a single stmt. We then:
 560    - create a new stmt S6 that will replace the pattern.
 561    - insert the new stmt S6 before the last stmt in the pattern
 562    - fill in the STMT_VINFO fields as follows:
 563
 564                                   in_pattern_p  related_stmt    vec_stmt
 565          S1: a_i = ....                 -       -               -
 566          S2: a_2 = ..use(a_i)..         -       -               -
 567          S3: a_1 = ..use(a_2)..         -       -               -
 568        > S6: a_new = ....               -       S4              -
 569          S4: a_0 = ..use(a_1)..         true    S6              -
 570          S5: ... = ..use(a_0)..         -       -               -
 571
 572    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
 573     to each other through the RELATED_STMT field).
 574
 575    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
 576    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
 577    remain irrelevant unless used by stmts other than S4.
 578
 579    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
 580    (because they are marked as irrelevent). It will vectorize S6, and record
 581    a pointer to the new vector stmt VS6 both from S6 (as usual), and also
 582    from S4. We do that so that when we get to vectorizing stmts that use the
 583    def of S4 (like S5 that uses a_0), we'll know where to take the relevant
 584    vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
 585
 586                                   in_pattern_p  related_stmt    vec_stmt
 587          S1: a_i = ....                 -       -               -
 588          S2: a_2 = ..use(a_i)..         -       -               -
 589          S3: a_1 = ..use(a_2)..         -       -               -
 590        > VS6: va_new = ....             -       -               -
 591          S6: a_new = ....               -       S4              VS6
 592          S4: a_0 = ..use(a_1)..         true    S6              VS6
 593        > VS5: ... = ..vuse(va_new)..    -       -               -
 594          S5: ... = ..use(a_0)..         -       -               -
 595
 596    DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
 597    elsewhere), and we'll end up with:
 598
 599         VS6: va_new = ....
 600         VS5: ... = ..vuse(va_new)..
 601
 602    If vectorization does not succeed, DCE will clean S6 away (its def is
 603    not used), and we'll end up with the original sequence.
 604 */
 605
 606 void
 607 vect_pattern_recog (loop_vec_info loop_vinfo)
 608 {
 609   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 610   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
 611   unsigned int nbbs = loop->num_nodes;
 612   block_stmt_iterator si;
 613   tree stmt;
 614   unsigned int i, j;
 615   tree (* vect_recog_func_ptr) (tree, tree *, tree *);
 616
 617   if (vect_print_dump_info (REPORT_DETAILS))
 618     fprintf (vect_dump, "=== vect_pattern_recog ===");
 619
 620   /* Scan through the loop stmts, applying the pattern recognition
 621      functions starting at each stmt visited:  */
 622   for (i = 0; i < nbbs; i++)
 623     {
 624       basic_block bb = bbs[i];
 625       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 626         {
 627           stmt = bsi_stmt (si);
 628
 629           /* Scan over all generic vect_recog_xxx_pattern functions.  */
 630           for (j = 0; j < NUM_PATTERNS; j++)
 631             {
 632               vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
 633               vect_pattern_recog_1 (vect_recog_func_ptr, si);
 634             }
 635         }
 636     }
 637 }