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