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