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