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,
 338                                tree *type_in,
 339                                tree *type_out)
 340 {
 341   tree expr;
 342   tree def_stmt0, def_stmt1;
 343   tree oprnd0, oprnd1;
 344   tree type, half_type0, half_type1;
 345   tree pattern_expr;
 346   tree vectype;
 347   tree dummy;
 348   enum tree_code dummy_code;
 349
 350   if (TREE_CODE (last_stmt) != MODIFY_EXPR)
 351     return NULL;
 352
 353   expr = TREE_OPERAND (last_stmt, 1);
 354   type = TREE_TYPE (expr);
 355
 356   /* Starting from LAST_STMT, follow the defs of its uses in search
 357      of the above pattern.  */
 358
 359   if (TREE_CODE (expr) != MULT_EXPR)
 360     return NULL;
 361
 362   oprnd0 = TREE_OPERAND (expr, 0);
 363   oprnd1 = TREE_OPERAND (expr, 1);
 364   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 365       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 366     return NULL;
 367
 368   /* Check argument 0 */
 369   if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0))
 370     return NULL;
 371   oprnd0 = TREE_OPERAND (TREE_OPERAND (def_stmt0, 1), 0);
 372
 373   /* Check argument 1 */
 374   if (!widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1))
 375     return NULL;
 376   oprnd1 = TREE_OPERAND (TREE_OPERAND (def_stmt1, 1), 0);
 377
 378   if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
 379     return NULL;
 380
 381   /* Pattern detected.  */
 382   if (vect_print_dump_info (REPORT_DETAILS))
 383     fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");
 384
 385   /* Check target support  */
 386   vectype = get_vectype_for_scalar_type (half_type0);
 387   if (!supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt, vectype,
 388                                        &dummy, &dummy, &dummy_code,
 389                                        &dummy_code))
 390     return NULL;
 391
 392   *type_in = vectype;
 393   *type_out = NULL_TREE;
 394
 395   /* Pattern supported. Create a stmt to be used to replace the pattern: */
 396   pattern_expr = build2 (WIDEN_MULT_EXPR, type, oprnd0, oprnd1);
 397   if (vect_print_dump_info (REPORT_DETAILS))
 398     print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 399   return pattern_expr;
 400 }
 401
 402
 403 /* Function vect_recog_widen_sum_pattern
 404
 405    Try to find the following pattern:
 406
 407      type x_t;
 408      TYPE x_T, sum = init;
 409    loop:
 410      sum_0 = phi <init, sum_1>
 411      S1  x_t = *p;
 412      S2  x_T = (TYPE) x_t;
 413      S3  sum_1 = x_T + sum_0;
 414
 415    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 416    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 417    a special case of a reduction computation.
 418
 419    Input:
 420
 421    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 422    when this function is called with S3, the pattern {S2,S3} will be detected.
 423
 424    Output:
 425
 426    * TYPE_IN: The type of the input arguments to the pattern.
 427
 428    * TYPE_OUT: The type of the output of this pattern.
 429
 430    * Return value: A new stmt that will be used to replace the sequence of
 431    stmts that constitute the pattern. In this case it will be:
 432         WIDEN_SUM <x_t, sum_0>
 433 */
 434
 435 static tree
 436 vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
 437 {
 438   tree stmt, expr;
 439   tree oprnd0, oprnd1;
 440   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 441   tree type, half_type;
 442   tree pattern_expr;
 443
 444   if (TREE_CODE (last_stmt) != MODIFY_EXPR)
 445     return NULL;
 446
 447   expr = TREE_OPERAND (last_stmt, 1);
 448   type = TREE_TYPE (expr);
 449
 450   /* Look for the following pattern
 451           DX = (TYPE) X;
 452           sum_1 = DX + sum_0;
 453      In which DX is at least double the size of X, and sum_1 has been
 454      recognized as a reduction variable.
 455    */
 456
 457   /* Starting from LAST_STMT, follow the defs of its uses in search
 458      of the above pattern.  */
 459
 460   if (TREE_CODE (expr) != PLUS_EXPR)
 461     return NULL;
 462
 463   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 464     return NULL;
 465
 466   oprnd0 = TREE_OPERAND (expr, 0);
 467   oprnd1 = TREE_OPERAND (expr, 1);
 468   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 469       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 470     return NULL;
 471
 472   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 473      we know that oprnd1 is the reduction variable (defined by a loop-header
 474      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 475      Left to check that oprnd0 is defined by a cast from type 'type' to type
 476      'TYPE'.  */
 477
 478   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
 479     return NULL;
 480
 481   oprnd0 = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
 482   *type_in = half_type;
 483   *type_out = type;
 484
 485   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 486   pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1);
 487   if (vect_print_dump_info (REPORT_DETAILS))
 488     {
 489       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 490       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 491     }
 492   return pattern_expr;
 493 }
 494
 495
 496 /* Function vect_pattern_recog_1
 497
 498    Input:
 499    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
 500         computation pattern.
 501    STMT: A stmt from which the pattern search should start.
 502
 503    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
 504    expression that computes the same functionality and can be used to
 505    replace the sequence of stmts that are involved in the pattern.
 506
 507    Output:
 508    This function checks if the expression returned by PATTERN_RECOG_FUNC is
 509    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
 510    relevant vector type. If 'TYPE_IN' is already a vector type, then this
 511    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
 512    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
 513    to the available target pattern.
 514
 515    This function also does some bookkeeping, as explained in the documentation
 516    for vect_recog_pattern.  */
 517
 518 static void
 519 vect_pattern_recog_1 (
 520         tree (* vect_recog_func) (tree, tree *, tree *),
 521         block_stmt_iterator si)
 522 {
 523   tree stmt = bsi_stmt (si);
 524   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 525   stmt_vec_info pattern_stmt_info;
 526   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 527   tree pattern_expr;
 528   tree pattern_vectype;
 529   tree type_in, type_out;
 530   tree pattern_type;
 531   enum tree_code code;
 532   tree var, var_name;
 533   stmt_ann_t ann;
 534
 535   pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out);
 536   if (!pattern_expr)
 537     return;
 538
 539   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
 540     {
 541       /* No need to check target support (already checked by the pattern
 542          recognition function).  */
 543       pattern_vectype = type_in;
 544     }
 545   else
 546     {
 547       enum tree_code vec_mode;
 548       enum insn_code icode;
 549       optab optab;
 550
 551       /* Check target support  */
 552       pattern_vectype = get_vectype_for_scalar_type (type_in);
 553       optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype);
 554       vec_mode = TYPE_MODE (pattern_vectype);
 555       if (!optab
 556           || (icode = optab->handlers[(int) vec_mode].insn_code) ==
 557               CODE_FOR_nothing
 558           || (type_out
 559               && (insn_data[icode].operand[0].mode !=
 560                   TYPE_MODE (get_vectype_for_scalar_type (type_out)))))
 561         return;
 562     }
 563
 564   /* Found a vectorizable pattern.  */
 565   if (vect_print_dump_info (REPORT_DETAILS))
 566     {
 567       fprintf (vect_dump, "pattern recognized: ");
 568       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 569     }
 570
 571   /* Mark the stmts that are involved in the pattern,
 572      create a new stmt to express the pattern and insert it.  */
 573   code = TREE_CODE (pattern_expr);
 574   pattern_type = TREE_TYPE (pattern_expr);
 575   var = create_tmp_var (pattern_type, "patt");
 576   add_referenced_var (var);
 577   var_name = make_ssa_name (var, NULL_TREE);
 578   pattern_expr = build2 (MODIFY_EXPR, void_type_node, var_name, pattern_expr);
 579   SSA_NAME_DEF_STMT (var_name) = pattern_expr;
 580   bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT);
 581   ann = stmt_ann (pattern_expr);
 582   set_stmt_info (ann, new_stmt_vec_info (pattern_expr, loop_vinfo));
 583   pattern_stmt_info = vinfo_for_stmt (pattern_expr);
 584
 585   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
 586   STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
 587   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
 588   STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
 589   STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr;
 590
 591   return;
 592 }
 593
 594
 595 /* Function vect_pattern_recog
 596
 597    Input:
 598    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
 599         computation idioms.
 600
 601    Output - for each computation idiom that is detected we insert a new stmt
 602         that provides the same functionality and that can be vectorized. We
 603         also record some information in the struct_stmt_info of the relevant
 604         stmts, as explained below:
 605
 606    At the entry to this function we have the following stmts, with the
 607    following initial value in the STMT_VINFO fields:
 608
 609          stmt                     in_pattern_p  related_stmt    vec_stmt
 610          S1: a_i = ....                 -       -               -
 611          S2: a_2 = ..use(a_i)..         -       -               -
 612          S3: a_1 = ..use(a_2)..         -       -               -
 613          S4: a_0 = ..use(a_1)..         -       -               -
 614          S5: ... = ..use(a_0)..         -       -               -
 615
 616    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
 617    represented by a single stmt. We then:
 618    - create a new stmt S6 that will replace the pattern.
 619    - insert the new stmt S6 before the last stmt in the pattern
 620    - fill in the STMT_VINFO fields as follows:
 621
 622                                   in_pattern_p  related_stmt    vec_stmt
 623          S1: a_i = ....                 -       -               -
 624          S2: a_2 = ..use(a_i)..         -       -               -
 625          S3: a_1 = ..use(a_2)..         -       -               -
 626        > S6: a_new = ....               -       S4              -
 627          S4: a_0 = ..use(a_1)..         true    S6              -
 628          S5: ... = ..use(a_0)..         -       -               -
 629
 630    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
 631     to each other through the RELATED_STMT field).
 632
 633    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
 634    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
 635    remain irrelevant unless used by stmts other than S4.
 636
 637    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
 638    (because they are marked as irrelevant). It will vectorize S6, and record
 639    a pointer to the new vector stmt VS6 both from S6 (as usual), and also
 640    from S4. We do that so that when we get to vectorizing stmts that use the
 641    def of S4 (like S5 that uses a_0), we'll know where to take the relevant
 642    vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
 643
 644                                   in_pattern_p  related_stmt    vec_stmt
 645          S1: a_i = ....                 -       -               -
 646          S2: a_2 = ..use(a_i)..         -       -               -
 647          S3: a_1 = ..use(a_2)..         -       -               -
 648        > VS6: va_new = ....             -       -               -
 649          S6: a_new = ....               -       S4              VS6
 650          S4: a_0 = ..use(a_1)..         true    S6              VS6
 651        > VS5: ... = ..vuse(va_new)..    -       -               -
 652          S5: ... = ..use(a_0)..         -       -               -
 653
 654    DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
 655    elsewhere), and we'll end up with:
 656
 657         VS6: va_new = ....
 658         VS5: ... = ..vuse(va_new)..
 659
 660    If vectorization does not succeed, DCE will clean S6 away (its def is
 661    not used), and we'll end up with the original sequence.
 662 */
 663
 664 void
 665 vect_pattern_recog (loop_vec_info loop_vinfo)
 666 {
 667   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 668   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
 669   unsigned int nbbs = loop->num_nodes;
 670   block_stmt_iterator si;
 671   tree stmt;
 672   unsigned int i, j;
 673   tree (* vect_recog_func_ptr) (tree, tree *, tree *);
 674
 675   if (vect_print_dump_info (REPORT_DETAILS))
 676     fprintf (vect_dump, "=== vect_pattern_recog ===");
 677
 678   /* Scan through the loop stmts, applying the pattern recognition
 679      functions starting at each stmt visited:  */
 680   for (i = 0; i < nbbs; i++)
 681     {
 682       basic_block bb = bbs[i];
 683       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 684         {
 685           stmt = bsi_stmt (si);
 686
 687           /* Scan over all generic vect_recog_xxx_pattern functions.  */
 688           for (j = 0; j < NUM_PATTERNS; j++)
 689             {
 690               vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
 691               vect_pattern_recog_1 (vect_recog_func_ptr, si);
 692             }
 693         }
 694     }
 695 }