gcc/tree-vect-patterns.c

   1 /* Analysis Utilities for Loop Vectorization.
   2    Copyright (C) 2006, 2007 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 tree vect_recog_pow_pattern (tree, tree *, tree *);
  54 static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
  55         vect_recog_widen_mult_pattern,
  56         vect_recog_widen_sum_pattern,
  57         vect_recog_dot_prod_pattern,
  58         vect_recog_pow_pattern};
  59
  60
  61 /* Function widened_name_p
  62
  63    Check whether NAME, an ssa-name used in USE_STMT,
  64    is a result of a type-promotion, such that:
  65      DEF_STMT: NAME = NOP (name0)
  66    where the type of name0 (HALF_TYPE) is smaller than the type of NAME.
  67 */
  68
  69 static bool
  70 widened_name_p (tree name, tree use_stmt, tree *half_type, tree *def_stmt)
  71 {
  72   tree dummy;
  73   loop_vec_info loop_vinfo;
  74   stmt_vec_info stmt_vinfo;
  75   tree expr;
  76   tree type = TREE_TYPE (name);
  77   tree oprnd0;
  78   enum vect_def_type dt;
  79   tree def;
  80
  81   stmt_vinfo = vinfo_for_stmt (use_stmt);
  82   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
  83
  84   if (!vect_is_simple_use (name, loop_vinfo, def_stmt, &def, &dt))
  85     return false;
  86
  87   if (dt != vect_loop_def
  88       && dt != vect_invariant_def && dt != vect_constant_def)
  89     return false;
  90
  91   if (! *def_stmt)
  92     return false;
  93
  94   if (TREE_CODE (*def_stmt) != GIMPLE_MODIFY_STMT)
  95     return false;
  96
  97   expr = GIMPLE_STMT_OPERAND (*def_stmt, 1);
  98   if (TREE_CODE (expr) != NOP_EXPR)
  99     return false;
 100
 101   oprnd0 = TREE_OPERAND (expr, 0);
 102
 103   *half_type = TREE_TYPE (oprnd0);
 104   if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
 105       || (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type))
 106       || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
 107     return false;
 108
 109   if (!vect_is_simple_use (oprnd0, loop_vinfo, &dummy, &dummy, &dt))
 110     return false;
 111
 112   return true;
 113 }
 114
 115
 116 /* Function vect_recog_dot_prod_pattern
 117
 118    Try to find the following pattern:
 119
 120      type x_t, y_t;
 121      TYPE1 prod;
 122      TYPE2 sum = init;
 123    loop:
 124      sum_0 = phi <init, sum_1>
 125      S1  x_t = ...
 126      S2  y_t = ...
 127      S3  x_T = (TYPE1) x_t;
 128      S4  y_T = (TYPE1) y_t;
 129      S5  prod = x_T * y_T;
 130      [S6  prod = (TYPE2) prod;  #optional]
 131      S7  sum_1 = prod + sum_0;
 132
 133    where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
 134    same size of 'TYPE1' or bigger. This is a special case of a reduction
 135    computation.
 136
 137    Input:
 138
 139    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 140    when this function is called with S7, the pattern {S3,S4,S5,S6,S7} will be
 141    detected.
 142
 143    Output:
 144
 145    * TYPE_IN: The type of the input arguments to the pattern.
 146
 147    * TYPE_OUT: The type of the output  of this pattern.
 148
 149    * Return value: A new stmt that will be used to replace the sequence of
 150    stmts that constitute the pattern. In this case it will be:
 151         WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
 152 */
 153
 154 static tree
 155 vect_recog_dot_prod_pattern (tree last_stmt, tree *type_in, tree *type_out)
 156 {
 157   tree stmt, expr;
 158   tree oprnd0, oprnd1;
 159   tree oprnd00, oprnd01;
 160   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 161   tree type, half_type;
 162   tree pattern_expr;
 163   tree prod_type;
 164
 165   if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
 166     return NULL;
 167
 168   expr = GIMPLE_STMT_OPERAND (last_stmt, 1);
 169   type = TREE_TYPE (expr);
 170
 171   /* Look for the following pattern
 172           DX = (TYPE1) X;
 173           DY = (TYPE1) Y;
 174           DPROD = DX * DY;
 175           DDPROD = (TYPE2) DPROD;
 176           sum_1 = DDPROD + sum_0;
 177      In which
 178      - DX is double the size of X
 179      - DY is double the size of Y
 180      - DX, DY, DPROD all have the same type
 181      - sum is the same size of DPROD or bigger
 182      - sum has been recognized as a reduction variable.
 183
 184      This is equivalent to:
 185        DPROD = X w* Y;          #widen mult
 186        sum_1 = DPROD w+ sum_0;  #widen summation
 187      or
 188        DPROD = X w* Y;          #widen mult
 189        sum_1 = DPROD + sum_0;   #summation
 190    */
 191
 192   /* Starting from LAST_STMT, follow the defs of its uses in search
 193      of the above pattern.  */
 194
 195   if (TREE_CODE (expr) != PLUS_EXPR)
 196     return NULL;
 197
 198   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 199     {
 200       /* Has been detected as widening-summation?  */
 201
 202       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 203       expr = GIMPLE_STMT_OPERAND (stmt, 1);
 204       type = TREE_TYPE (expr);
 205       if (TREE_CODE (expr) != WIDEN_SUM_EXPR)
 206         return NULL;
 207       oprnd0 = TREE_OPERAND (expr, 0);
 208       oprnd1 = TREE_OPERAND (expr, 1);
 209       half_type = TREE_TYPE (oprnd0);
 210     }
 211   else
 212     {
 213       tree def_stmt;
 214
 215       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 216         return NULL;
 217       oprnd0 = TREE_OPERAND (expr, 0);
 218       oprnd1 = TREE_OPERAND (expr, 1);
 219       if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 220           || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 221         return NULL;
 222       stmt = last_stmt;
 223
 224       if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt))
 225         {
 226           stmt = def_stmt;
 227           expr = GIMPLE_STMT_OPERAND (stmt, 1);
 228           oprnd0 = TREE_OPERAND (expr, 0);
 229         }
 230       else
 231         half_type = type;
 232     }
 233
 234   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 235      we know that oprnd1 is the reduction variable (defined by a loop-header
 236      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 237      Left to check that oprnd0 is defined by a (widen_)mult_expr  */
 238
 239   prod_type = half_type;
 240   stmt = SSA_NAME_DEF_STMT (oprnd0);
 241   gcc_assert (stmt);
 242   stmt_vinfo = vinfo_for_stmt (stmt);
 243   gcc_assert (stmt_vinfo);
 244   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_loop_def)
 245     return NULL;
 246   expr = GIMPLE_STMT_OPERAND (stmt, 1);
 247   if (TREE_CODE (expr) != MULT_EXPR)
 248     return NULL;
 249   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 250     {
 251       /* Has been detected as a widening multiplication?  */
 252
 253       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 254       expr = GIMPLE_STMT_OPERAND (stmt, 1);
 255       if (TREE_CODE (expr) != WIDEN_MULT_EXPR)
 256         return NULL;
 257       stmt_vinfo = vinfo_for_stmt (stmt);
 258       gcc_assert (stmt_vinfo);
 259       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_loop_def);
 260       oprnd00 = TREE_OPERAND (expr, 0);
 261       oprnd01 = TREE_OPERAND (expr, 1);
 262     }
 263   else
 264     {
 265       tree half_type0, half_type1;
 266       tree def_stmt;
 267       tree oprnd0, oprnd1;
 268
 269       oprnd0 = TREE_OPERAND (expr, 0);
 270       oprnd1 = TREE_OPERAND (expr, 1);
 271       if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0))
 272                                 != TYPE_MAIN_VARIANT (prod_type)
 273           || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1))
 274                                 != TYPE_MAIN_VARIANT (prod_type))
 275         return NULL;
 276       if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt))
 277         return NULL;
 278       oprnd00 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
 279       if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt))
 280         return NULL;
 281       oprnd01 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
 282       if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
 283         return NULL;
 284       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
 285         return NULL;
 286     }
 287
 288   half_type = TREE_TYPE (oprnd00);
 289   *type_in = half_type;
 290   *type_out = type;
 291
 292   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 293   pattern_expr = build3 (DOT_PROD_EXPR, type, oprnd00, oprnd01, oprnd1);
 294   if (vect_print_dump_info (REPORT_DETAILS))
 295     {
 296       fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
 297       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 298     }
 299   return pattern_expr;
 300 }
 301
 302
 303 /* Function vect_recog_widen_mult_pattern
 304
 305    Try to find the following pattern:
 306
 307      type a_t, b_t;
 308      TYPE a_T, b_T, prod_T;
 309
 310      S1  a_t = ;
 311      S2  b_t = ;
 312      S3  a_T = (TYPE) a_t;
 313      S4  b_T = (TYPE) b_t;
 314      S5  prod_T = a_T * b_T;
 315
 316    where type 'TYPE' is at least double the size of type 'type'.
 317
 318    Input:
 319
 320    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 321    when this function is called with S5, the pattern {S3,S4,S5} is be detected.
 322
 323    Output:
 324
 325    * TYPE_IN: The type of the input arguments to the pattern.
 326
 327    * TYPE_OUT: The type of the output  of this pattern.
 328
 329    * Return value: A new stmt that will be used to replace the sequence of
 330    stmts that constitute the pattern. In this case it will be:
 331         WIDEN_MULT <a_t, b_t>
 332 */
 333
 334 static tree
 335 vect_recog_widen_mult_pattern (tree last_stmt,
 336                                tree *type_in,
 337                                tree *type_out)
 338 {
 339   tree expr;
 340   tree def_stmt0, def_stmt1;
 341   tree oprnd0, oprnd1;
 342   tree type, half_type0, half_type1;
 343   tree pattern_expr;
 344   tree vectype;
 345   tree dummy;
 346   enum tree_code dummy_code;
 347
 348   if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
 349     return NULL;
 350
 351   expr = GIMPLE_STMT_OPERAND (last_stmt, 1);
 352   type = TREE_TYPE (expr);
 353
 354   /* Starting from LAST_STMT, follow the defs of its uses in search
 355      of the above pattern.  */
 356
 357   if (TREE_CODE (expr) != MULT_EXPR)
 358     return NULL;
 359
 360   oprnd0 = TREE_OPERAND (expr, 0);
 361   oprnd1 = TREE_OPERAND (expr, 1);
 362   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 363       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 364     return NULL;
 365
 366   /* Check argument 0 */
 367   if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0))
 368     return NULL;
 369   oprnd0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt0, 1), 0);
 370
 371   /* Check argument 1 */
 372   if (!widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1))
 373     return NULL;
 374   oprnd1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt1, 1), 0);
 375
 376   if (TYPE_MAIN_VARIANT (half_type0) != TYPE_MAIN_VARIANT (half_type1))
 377     return NULL;
 378
 379   /* Pattern detected.  */
 380   if (vect_print_dump_info (REPORT_DETAILS))
 381     fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");
 382
 383   /* Check target support  */
 384   vectype = get_vectype_for_scalar_type (half_type0);
 385   if (!vectype
 386       || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt, vectype,
 387                                        &dummy, &dummy, &dummy_code,
 388                                        &dummy_code))
 389     return NULL;
 390
 391   *type_in = vectype;
 392   *type_out = NULL_TREE;
 393
 394   /* Pattern supported. Create a stmt to be used to replace the pattern: */
 395   pattern_expr = build2 (WIDEN_MULT_EXPR, type, oprnd0, oprnd1);
 396   if (vect_print_dump_info (REPORT_DETAILS))
 397     print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 398   return pattern_expr;
 399 }
 400
 401
 402 /* Function vect_recog_pow_pattern
 403
 404    Try to find the following pattern:
 405
 406      x = POW (y, N);
 407
 408    with POW being one of pow, powf, powi, powif and N being
 409    either 2 or 0.5.
 410
 411    Input:
 412
 413    * LAST_STMT: A stmt from which the pattern search begins.
 414
 415    Output:
 416
 417    * TYPE_IN: The type of the input arguments to the pattern.
 418
 419    * TYPE_OUT: The type of the output of this pattern.
 420
 421    * Return value: A new stmt that will be used to replace the sequence of
 422    stmts that constitute the pattern. In this case it will be:
 423         x * x
 424    or
 425         sqrt (x)
 426 */
 427
 428 static tree
 429 vect_recog_pow_pattern (tree last_stmt, tree *type_in, tree *type_out)
 430 {
 431   tree expr;
 432   tree type;
 433   tree fn, base, exp;
 434
 435   if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
 436     return NULL;
 437
 438   expr = GIMPLE_STMT_OPERAND (last_stmt, 1);
 439   type = TREE_TYPE (expr);
 440
 441   if (TREE_CODE (expr) != CALL_EXPR)
 442     return NULL_TREE;
 443
 444   fn = get_callee_fndecl (expr);
 445   switch (DECL_FUNCTION_CODE (fn))
 446     {
 447     case BUILT_IN_POWIF:
 448     case BUILT_IN_POWI:
 449     case BUILT_IN_POWF:
 450     case BUILT_IN_POW:
 451       base = CALL_EXPR_ARG (expr, 0);
 452       exp = CALL_EXPR_ARG (expr, 1);
 453       if (TREE_CODE (exp) != REAL_CST
 454           && TREE_CODE (exp) != INTEGER_CST)
 455         return NULL_TREE;
 456       break;
 457
 458     default:;
 459       return NULL_TREE;
 460     }
 461
 462   /* We now have a pow or powi builtin function call with a constant
 463      exponent.  */
 464
 465   *type_out = NULL_TREE;
 466
 467   /* Catch squaring.  */
 468   if ((host_integerp (exp, 0)
 469        && tree_low_cst (exp, 0) == 2)
 470       || (TREE_CODE (exp) == REAL_CST
 471           && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
 472     {
 473       *type_in = TREE_TYPE (base);
 474       return build2 (MULT_EXPR, TREE_TYPE (base), base, base);
 475     }
 476
 477   /* Catch square root.  */
 478   if (TREE_CODE (exp) == REAL_CST
 479       && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconsthalf))
 480     {
 481       tree newfn = mathfn_built_in (TREE_TYPE (base), BUILT_IN_SQRT);
 482       *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
 483       if (*type_in)
 484         {
 485           newfn = build_call_expr (newfn, 1, base);
 486           if (vectorizable_function (newfn, *type_in, *type_in) != NULL_TREE)
 487             return newfn;
 488         }
 489     }
 490
 491   return NULL_TREE;
 492 }
 493
 494
 495 /* Function vect_recog_widen_sum_pattern
 496
 497    Try to find the following pattern:
 498
 499      type x_t;
 500      TYPE x_T, sum = init;
 501    loop:
 502      sum_0 = phi <init, sum_1>
 503      S1  x_t = *p;
 504      S2  x_T = (TYPE) x_t;
 505      S3  sum_1 = x_T + sum_0;
 506
 507    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 508    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 509    a special case of a reduction computation.
 510
 511    Input:
 512
 513    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 514    when this function is called with S3, the pattern {S2,S3} will be detected.
 515
 516    Output:
 517
 518    * TYPE_IN: The type of the input arguments to the pattern.
 519
 520    * TYPE_OUT: The type of the output of this pattern.
 521
 522    * Return value: A new stmt that will be used to replace the sequence of
 523    stmts that constitute the pattern. In this case it will be:
 524         WIDEN_SUM <x_t, sum_0>
 525 */
 526
 527 static tree
 528 vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
 529 {
 530   tree stmt, expr;
 531   tree oprnd0, oprnd1;
 532   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 533   tree type, half_type;
 534   tree pattern_expr;
 535
 536   if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
 537     return NULL;
 538
 539   expr = GIMPLE_STMT_OPERAND (last_stmt, 1);
 540   type = TREE_TYPE (expr);
 541
 542   /* Look for the following pattern
 543           DX = (TYPE) X;
 544           sum_1 = DX + sum_0;
 545      In which DX is at least double the size of X, and sum_1 has been
 546      recognized as a reduction variable.
 547    */
 548
 549   /* Starting from LAST_STMT, follow the defs of its uses in search
 550      of the above pattern.  */
 551
 552   if (TREE_CODE (expr) != PLUS_EXPR)
 553     return NULL;
 554
 555   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 556     return NULL;
 557
 558   oprnd0 = TREE_OPERAND (expr, 0);
 559   oprnd1 = TREE_OPERAND (expr, 1);
 560   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 561       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 562     return NULL;
 563
 564   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 565      we know that oprnd1 is the reduction variable (defined by a loop-header
 566      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 567      Left to check that oprnd0 is defined by a cast from type 'type' to type
 568      'TYPE'.  */
 569
 570   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
 571     return NULL;
 572
 573   oprnd0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0);
 574   *type_in = half_type;
 575   *type_out = type;
 576
 577   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 578   pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1);
 579   if (vect_print_dump_info (REPORT_DETAILS))
 580     {
 581       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 582       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 583     }
 584   return pattern_expr;
 585 }
 586
 587
 588 /* Function vect_pattern_recog_1
 589
 590    Input:
 591    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
 592         computation pattern.
 593    STMT: A stmt from which the pattern search should start.
 594
 595    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
 596    expression that computes the same functionality and can be used to
 597    replace the sequence of stmts that are involved in the pattern.
 598
 599    Output:
 600    This function checks if the expression returned by PATTERN_RECOG_FUNC is
 601    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
 602    relevant vector type. If 'TYPE_IN' is already a vector type, then this
 603    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
 604    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
 605    to the available target pattern.
 606
 607    This function also does some bookkeeping, as explained in the documentation
 608    for vect_recog_pattern.  */
 609
 610 static void
 611 vect_pattern_recog_1 (
 612         tree (* vect_recog_func) (tree, tree *, tree *),
 613         block_stmt_iterator si)
 614 {
 615   tree stmt = bsi_stmt (si);
 616   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 617   stmt_vec_info pattern_stmt_info;
 618   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 619   tree pattern_expr;
 620   tree pattern_vectype;
 621   tree type_in, type_out;
 622   tree pattern_type;
 623   enum tree_code code;
 624   tree var, var_name;
 625   stmt_ann_t ann;
 626
 627   pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out);
 628   if (!pattern_expr)
 629     return;
 630
 631   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
 632     {
 633       /* No need to check target support (already checked by the pattern
 634          recognition function).  */
 635       pattern_vectype = type_in;
 636     }
 637   else
 638     {
 639       enum tree_code vec_mode;
 640       enum insn_code icode;
 641       optab optab;
 642
 643       /* Check target support  */
 644       pattern_vectype = get_vectype_for_scalar_type (type_in);
 645       if (!pattern_vectype)
 646         return;
 647
 648       optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype);
 649       vec_mode = TYPE_MODE (pattern_vectype);
 650       if (!optab
 651           || (icode = optab->handlers[(int) vec_mode].insn_code) ==
 652               CODE_FOR_nothing
 653           || (type_out
 654               && (!get_vectype_for_scalar_type (type_out)
 655                   || (insn_data[icode].operand[0].mode !=
 656                       TYPE_MODE (get_vectype_for_scalar_type (type_out))))))
 657         return;
 658     }
 659
 660   /* Found a vectorizable pattern.  */
 661   if (vect_print_dump_info (REPORT_DETAILS))
 662     {
 663       fprintf (vect_dump, "pattern recognized: ");
 664       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 665     }
 666
 667   /* Mark the stmts that are involved in the pattern,
 668      create a new stmt to express the pattern and insert it.  */
 669   code = TREE_CODE (pattern_expr);
 670   pattern_type = TREE_TYPE (pattern_expr);
 671   var = create_tmp_var (pattern_type, "patt");
 672   add_referenced_var (var);
 673   var_name = make_ssa_name (var, NULL_TREE);
 674   pattern_expr = build_gimple_modify_stmt (var_name, pattern_expr);
 675   SSA_NAME_DEF_STMT (var_name) = pattern_expr;
 676   bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT);
 677   ann = stmt_ann (pattern_expr);
 678   set_stmt_info (ann, new_stmt_vec_info (pattern_expr, loop_vinfo));
 679   pattern_stmt_info = vinfo_for_stmt (pattern_expr);
 680
 681   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
 682   STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
 683   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
 684   STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
 685   STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr;
 686
 687   return;
 688 }
 689
 690
 691 /* Function vect_pattern_recog
 692
 693    Input:
 694    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
 695         computation idioms.
 696
 697    Output - for each computation idiom that is detected we insert a new stmt
 698         that provides the same functionality and that can be vectorized. We
 699         also record some information in the struct_stmt_info of the relevant
 700         stmts, as explained below:
 701
 702    At the entry to this function we have the following stmts, with the
 703    following initial value in the STMT_VINFO fields:
 704
 705          stmt                     in_pattern_p  related_stmt    vec_stmt
 706          S1: a_i = ....                 -       -               -
 707          S2: a_2 = ..use(a_i)..         -       -               -
 708          S3: a_1 = ..use(a_2)..         -       -               -
 709          S4: a_0 = ..use(a_1)..         -       -               -
 710          S5: ... = ..use(a_0)..         -       -               -
 711
 712    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
 713    represented by a single stmt. We then:
 714    - create a new stmt S6 that will replace the pattern.
 715    - insert the new stmt S6 before the last stmt in the pattern
 716    - fill in the STMT_VINFO fields as follows:
 717
 718                                   in_pattern_p  related_stmt    vec_stmt
 719          S1: a_i = ....                 -       -               -
 720          S2: a_2 = ..use(a_i)..         -       -               -
 721          S3: a_1 = ..use(a_2)..         -       -               -
 722        > S6: a_new = ....               -       S4              -
 723          S4: a_0 = ..use(a_1)..         true    S6              -
 724          S5: ... = ..use(a_0)..         -       -               -
 725
 726    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
 727     to each other through the RELATED_STMT field).
 728
 729    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
 730    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
 731    remain irrelevant unless used by stmts other than S4.
 732
 733    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
 734    (because they are marked as irrelevant). It will vectorize S6, and record
 735    a pointer to the new vector stmt VS6 both from S6 (as usual), and also
 736    from S4. We do that so that when we get to vectorizing stmts that use the
 737    def of S4 (like S5 that uses a_0), we'll know where to take the relevant
 738    vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
 739
 740                                   in_pattern_p  related_stmt    vec_stmt
 741          S1: a_i = ....                 -       -               -
 742          S2: a_2 = ..use(a_i)..         -       -               -
 743          S3: a_1 = ..use(a_2)..         -       -               -
 744        > VS6: va_new = ....             -       -               -
 745          S6: a_new = ....               -       S4              VS6
 746          S4: a_0 = ..use(a_1)..         true    S6              VS6
 747        > VS5: ... = ..vuse(va_new)..    -       -               -
 748          S5: ... = ..use(a_0)..         -       -               -
 749
 750    DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
 751    elsewhere), and we'll end up with:
 752
 753         VS6: va_new = ....
 754         VS5: ... = ..vuse(va_new)..
 755
 756    If vectorization does not succeed, DCE will clean S6 away (its def is
 757    not used), and we'll end up with the original sequence.
 758 */
 759
 760 void
 761 vect_pattern_recog (loop_vec_info loop_vinfo)
 762 {
 763   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 764   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
 765   unsigned int nbbs = loop->num_nodes;
 766   block_stmt_iterator si;
 767   tree stmt;
 768   unsigned int i, j;
 769   tree (* vect_recog_func_ptr) (tree, tree *, tree *);
 770
 771   if (vect_print_dump_info (REPORT_DETAILS))
 772     fprintf (vect_dump, "=== vect_pattern_recog ===");
 773
 774   /* Scan through the loop stmts, applying the pattern recognition
 775      functions starting at each stmt visited:  */
 776   for (i = 0; i < nbbs; i++)
 777     {
 778       basic_block bb = bbs[i];
 779       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 780         {
 781           stmt = bsi_stmt (si);
 782
 783           /* Scan over all generic vect_recog_xxx_pattern functions.  */
 784           for (j = 0; j < NUM_PATTERNS; j++)
 785             {
 786               vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
 787               vect_pattern_recog_1 (vect_recog_func_ptr, si);
 788             }
 789         }
 790     }
 791 }