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 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 (!supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt, vectype,
 390                                        &dummy, &dummy, &dummy_code,
 391                                        &dummy_code))
 392     return NULL;
 393
 394   *type_in = vectype;
 395   *type_out = NULL_TREE;
 396
 397   /* Pattern supported. Create a stmt to be used to replace the pattern: */
 398   pattern_expr = build2 (WIDEN_MULT_EXPR, type, oprnd0, oprnd1);
 399   if (vect_print_dump_info (REPORT_DETAILS))
 400     print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 401   return pattern_expr;
 402 }
 403
 404
 405 /* Function vect_recog_pow_pattern
 406
 407    Try to find the following pattern:
 408
 409      x = POW (y, N);
 410
 411    with POW being one of pow, powf, powi, powif and N being
 412    either 2 or 0.5.
 413
 414    Input:
 415
 416    * LAST_STMT: A stmt from which the pattern search begins.
 417
 418    Output:
 419
 420    * TYPE_IN: The type of the input arguments to the pattern.
 421
 422    * TYPE_OUT: The type of the output of this pattern.
 423
 424    * Return value: A new stmt that will be used to replace the sequence of
 425    stmts that constitute the pattern. In this case it will be:
 426         x * x
 427    or
 428         sqrt (x)
 429 */
 430
 431 static tree
 432 vect_recog_pow_pattern (tree last_stmt, tree *type_in, tree *type_out)
 433 {
 434   tree expr;
 435   tree type;
 436   tree fn, arglist, base, exp;
 437
 438   if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
 439     return NULL;
 440
 441   expr = GIMPLE_STMT_OPERAND (last_stmt, 1);
 442   type = TREE_TYPE (expr);
 443
 444   if (TREE_CODE (expr) != CALL_EXPR)
 445     return NULL_TREE;
 446
 447   fn = get_callee_fndecl (expr);
 448   arglist = TREE_OPERAND (expr, 1);
 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 = TREE_VALUE (arglist);
 456       exp = TREE_VALUE (TREE_CHAIN (arglist));
 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       tree newarglist = build_tree_list (NULL_TREE, base);
 487       *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
 488       if (*type_in)
 489         {
 490           newfn = build_function_call_expr (newfn, newarglist);
 491           if (vectorizable_function (newfn, *type_in))
 492             return newfn;
 493         }
 494     }
 495
 496   return NULL_TREE;
 497 }
 498
 499
 500 /* Function vect_recog_widen_sum_pattern
 501
 502    Try to find the following pattern:
 503
 504      type x_t;
 505      TYPE x_T, sum = init;
 506    loop:
 507      sum_0 = phi <init, sum_1>
 508      S1  x_t = *p;
 509      S2  x_T = (TYPE) x_t;
 510      S3  sum_1 = x_T + sum_0;
 511
 512    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 513    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 514    a special case of a reduction computation.
 515
 516    Input:
 517
 518    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 519    when this function is called with S3, the pattern {S2,S3} will be detected.
 520
 521    Output:
 522
 523    * TYPE_IN: The type of the input arguments to the pattern.
 524
 525    * TYPE_OUT: The type of the output of this pattern.
 526
 527    * Return value: A new stmt that will be used to replace the sequence of
 528    stmts that constitute the pattern. In this case it will be:
 529         WIDEN_SUM <x_t, sum_0>
 530 */
 531
 532 static tree
 533 vect_recog_widen_sum_pattern (tree last_stmt, tree *type_in, tree *type_out)
 534 {
 535   tree stmt, expr;
 536   tree oprnd0, oprnd1;
 537   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 538   tree type, half_type;
 539   tree pattern_expr;
 540
 541   if (TREE_CODE (last_stmt) != GIMPLE_MODIFY_STMT)
 542     return NULL;
 543
 544   expr = GIMPLE_STMT_OPERAND (last_stmt, 1);
 545   type = TREE_TYPE (expr);
 546
 547   /* Look for the following pattern
 548           DX = (TYPE) X;
 549           sum_1 = DX + sum_0;
 550      In which DX is at least double the size of X, and sum_1 has been
 551      recognized as a reduction variable.
 552    */
 553
 554   /* Starting from LAST_STMT, follow the defs of its uses in search
 555      of the above pattern.  */
 556
 557   if (TREE_CODE (expr) != PLUS_EXPR)
 558     return NULL;
 559
 560   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 561     return NULL;
 562
 563   oprnd0 = TREE_OPERAND (expr, 0);
 564   oprnd1 = TREE_OPERAND (expr, 1);
 565   if (TYPE_MAIN_VARIANT (TREE_TYPE (oprnd0)) != TYPE_MAIN_VARIANT (type)
 566       || TYPE_MAIN_VARIANT (TREE_TYPE (oprnd1)) != TYPE_MAIN_VARIANT (type))
 567     return NULL;
 568
 569   /* So far so good. Since last_stmt was detected as a (summation) reduction,
 570      we know that oprnd1 is the reduction variable (defined by a loop-header
 571      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 572      Left to check that oprnd0 is defined by a cast from type 'type' to type
 573      'TYPE'.  */
 574
 575   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt))
 576     return NULL;
 577
 578   oprnd0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0);
 579   *type_in = half_type;
 580   *type_out = type;
 581
 582   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 583   pattern_expr = build2 (WIDEN_SUM_EXPR, type, oprnd0, oprnd1);
 584   if (vect_print_dump_info (REPORT_DETAILS))
 585     {
 586       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 587       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 588     }
 589   return pattern_expr;
 590 }
 591
 592
 593 /* Function vect_pattern_recog_1
 594
 595    Input:
 596    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
 597         computation pattern.
 598    STMT: A stmt from which the pattern search should start.
 599
 600    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
 601    expression that computes the same functionality and can be used to
 602    replace the sequence of stmts that are involved in the pattern.
 603
 604    Output:
 605    This function checks if the expression returned by PATTERN_RECOG_FUNC is
 606    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
 607    relevant vector type. If 'TYPE_IN' is already a vector type, then this
 608    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
 609    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
 610    to the available target pattern.
 611
 612    This function also does some bookkeeping, as explained in the documentation
 613    for vect_recog_pattern.  */
 614
 615 static void
 616 vect_pattern_recog_1 (
 617         tree (* vect_recog_func) (tree, tree *, tree *),
 618         block_stmt_iterator si)
 619 {
 620   tree stmt = bsi_stmt (si);
 621   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 622   stmt_vec_info pattern_stmt_info;
 623   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 624   tree pattern_expr;
 625   tree pattern_vectype;
 626   tree type_in, type_out;
 627   tree pattern_type;
 628   enum tree_code code;
 629   tree var, var_name;
 630   stmt_ann_t ann;
 631
 632   pattern_expr = (* vect_recog_func) (stmt, &type_in, &type_out);
 633   if (!pattern_expr)
 634     return;
 635
 636   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
 637     {
 638       /* No need to check target support (already checked by the pattern
 639          recognition function).  */
 640       pattern_vectype = type_in;
 641     }
 642   else
 643     {
 644       enum tree_code vec_mode;
 645       enum insn_code icode;
 646       optab optab;
 647
 648       /* Check target support  */
 649       pattern_vectype = get_vectype_for_scalar_type (type_in);
 650       optab = optab_for_tree_code (TREE_CODE (pattern_expr), pattern_vectype);
 651       vec_mode = TYPE_MODE (pattern_vectype);
 652       if (!optab
 653           || (icode = optab->handlers[(int) vec_mode].insn_code) ==
 654               CODE_FOR_nothing
 655           || (type_out
 656               && (insn_data[icode].operand[0].mode !=
 657                   TYPE_MODE (get_vectype_for_scalar_type (type_out)))))
 658         return;
 659     }
 660
 661   /* Found a vectorizable pattern.  */
 662   if (vect_print_dump_info (REPORT_DETAILS))
 663     {
 664       fprintf (vect_dump, "pattern recognized: ");
 665       print_generic_expr (vect_dump, pattern_expr, TDF_SLIM);
 666     }
 667
 668   /* Mark the stmts that are involved in the pattern,
 669      create a new stmt to express the pattern and insert it.  */
 670   code = TREE_CODE (pattern_expr);
 671   pattern_type = TREE_TYPE (pattern_expr);
 672   var = create_tmp_var (pattern_type, "patt");
 673   add_referenced_var (var);
 674   var_name = make_ssa_name (var, NULL_TREE);
 675   pattern_expr = build2 (GIMPLE_MODIFY_STMT, void_type_node, var_name,
 676                          pattern_expr);
 677   SSA_NAME_DEF_STMT (var_name) = pattern_expr;
 678   bsi_insert_before (&si, pattern_expr, BSI_SAME_STMT);
 679   ann = stmt_ann (pattern_expr);
 680   set_stmt_info (ann, new_stmt_vec_info (pattern_expr, loop_vinfo));
 681   pattern_stmt_info = vinfo_for_stmt (pattern_expr);
 682
 683   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = stmt;
 684   STMT_VINFO_DEF_TYPE (pattern_stmt_info) = STMT_VINFO_DEF_TYPE (stmt_info);
 685   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
 686   STMT_VINFO_IN_PATTERN_P (stmt_info) = true;
 687   STMT_VINFO_RELATED_STMT (stmt_info) = pattern_expr;
 688
 689   return;
 690 }
 691
 692
 693 /* Function vect_pattern_recog
 694
 695    Input:
 696    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
 697         computation idioms.
 698
 699    Output - for each computation idiom that is detected we insert a new stmt
 700         that provides the same functionality and that can be vectorized. We
 701         also record some information in the struct_stmt_info of the relevant
 702         stmts, as explained below:
 703
 704    At the entry to this function we have the following stmts, with the
 705    following initial value in the STMT_VINFO fields:
 706
 707          stmt                     in_pattern_p  related_stmt    vec_stmt
 708          S1: a_i = ....                 -       -               -
 709          S2: a_2 = ..use(a_i)..         -       -               -
 710          S3: a_1 = ..use(a_2)..         -       -               -
 711          S4: a_0 = ..use(a_1)..         -       -               -
 712          S5: ... = ..use(a_0)..         -       -               -
 713
 714    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
 715    represented by a single stmt. We then:
 716    - create a new stmt S6 that will replace the pattern.
 717    - insert the new stmt S6 before the last stmt in the pattern
 718    - fill in the STMT_VINFO fields as follows:
 719
 720                                   in_pattern_p  related_stmt    vec_stmt
 721          S1: a_i = ....                 -       -               -
 722          S2: a_2 = ..use(a_i)..         -       -               -
 723          S3: a_1 = ..use(a_2)..         -       -               -
 724        > S6: a_new = ....               -       S4              -
 725          S4: a_0 = ..use(a_1)..         true    S6              -
 726          S5: ... = ..use(a_0)..         -       -               -
 727
 728    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
 729     to each other through the RELATED_STMT field).
 730
 731    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
 732    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
 733    remain irrelevant unless used by stmts other than S4.
 734
 735    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
 736    (because they are marked as irrelevant). It will vectorize S6, and record
 737    a pointer to the new vector stmt VS6 both from S6 (as usual), and also
 738    from S4. We do that so that when we get to vectorizing stmts that use the
 739    def of S4 (like S5 that uses a_0), we'll know where to take the relevant
 740    vector-def from. S4 will be skipped, and S5 will be vectorized as usual:
 741
 742                                   in_pattern_p  related_stmt    vec_stmt
 743          S1: a_i = ....                 -       -               -
 744          S2: a_2 = ..use(a_i)..         -       -               -
 745          S3: a_1 = ..use(a_2)..         -       -               -
 746        > VS6: va_new = ....             -       -               -
 747          S6: a_new = ....               -       S4              VS6
 748          S4: a_0 = ..use(a_1)..         true    S6              VS6
 749        > VS5: ... = ..vuse(va_new)..    -       -               -
 750          S5: ... = ..use(a_0)..         -       -               -
 751
 752    DCE could then get rid of {S1,S2,S3,S4,S5,S6} (if their defs are not used
 753    elsewhere), and we'll end up with:
 754
 755         VS6: va_new = ....
 756         VS5: ... = ..vuse(va_new)..
 757
 758    If vectorization does not succeed, DCE will clean S6 away (its def is
 759    not used), and we'll end up with the original sequence.
 760 */
 761
 762 void
 763 vect_pattern_recog (loop_vec_info loop_vinfo)
 764 {
 765   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 766   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
 767   unsigned int nbbs = loop->num_nodes;
 768   block_stmt_iterator si;
 769   tree stmt;
 770   unsigned int i, j;
 771   tree (* vect_recog_func_ptr) (tree, tree *, tree *);
 772
 773   if (vect_print_dump_info (REPORT_DETAILS))
 774     fprintf (vect_dump, "=== vect_pattern_recog ===");
 775
 776   /* Scan through the loop stmts, applying the pattern recognition
 777      functions starting at each stmt visited:  */
 778   for (i = 0; i < nbbs; i++)
 779     {
 780       basic_block bb = bbs[i];
 781       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 782         {
 783           stmt = bsi_stmt (si);
 784
 785           /* Scan over all generic vect_recog_xxx_pattern functions.  */
 786           for (j = 0; j < NUM_PATTERNS; j++)
 787             {
 788               vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
 789               vect_pattern_recog_1 (vect_recog_func_ptr, si);
 790             }
 791         }
 792     }
 793 }