gcc/tree-vect-patterns.c

   1 /* Analysis Utilities for Loop Vectorization.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Dorit Nuzman <dorit@il.ibm.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 #include "target.h"
  29 #include "basic-block.h"
  30 #include "gimple-pretty-print.h"
  31 #include "tree-flow.h"
  32 #include "tree-dump.h"
  33 #include "cfgloop.h"
  34 #include "expr.h"
  35 #include "optabs.h"
  36 #include "params.h"
  37 #include "tree-data-ref.h"
  38 #include "tree-vectorizer.h"
  39 #include "recog.h"
  40 #include "diagnostic-core.h"
  41
  42 /* Pattern recognition functions  */
  43 static gimple vect_recog_widen_sum_pattern (VEC (gimple, heap) **, tree *,
  44                                             tree *);
  45 static gimple vect_recog_widen_mult_pattern (VEC (gimple, heap) **, tree *,
  46                                              tree *);
  47 static gimple vect_recog_dot_prod_pattern (VEC (gimple, heap) **, tree *,
  48                                            tree *);
  49 static gimple vect_recog_pow_pattern (VEC (gimple, heap) **, tree *, tree *);
  50 static gimple vect_recog_over_widening_pattern (VEC (gimple, heap) **, tree *,
  51                                                  tree *);
  52 static gimple vect_recog_widen_shift_pattern (VEC (gimple, heap) **,
  53                                         tree *, tree *);
  54 static gimple vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **,
  55                                                       tree *, tree *);
  56 static gimple vect_recog_mixed_size_cond_pattern (VEC (gimple, heap) **,
  57                                                   tree *, tree *);
  58 static gimple vect_recog_bool_pattern (VEC (gimple, heap) **, tree *, tree *);
  59 static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
  60         vect_recog_widen_mult_pattern,
  61         vect_recog_widen_sum_pattern,
  62         vect_recog_dot_prod_pattern,
  63         vect_recog_pow_pattern,
  64         vect_recog_over_widening_pattern,
  65         vect_recog_widen_shift_pattern,
  66         vect_recog_vector_vector_shift_pattern,
  67         vect_recog_mixed_size_cond_pattern,
  68         vect_recog_bool_pattern};
  69
  70 /* Function widened_name_p
  71
  72    Check whether NAME, an ssa-name used in USE_STMT,
  73    is a result of a type-promotion, such that:
  74      DEF_STMT: NAME = NOP (name0)
  75    where the type of name0 (HALF_TYPE) is smaller than the type of NAME.
  76    If CHECK_SIGN is TRUE, check that either both types are signed or both are
  77    unsigned.  */
  78
  79 static bool
  80 widened_name_p (tree name, gimple use_stmt, tree *half_type, gimple *def_stmt,
  81                 bool check_sign)
  82 {
  83   tree dummy;
  84   gimple dummy_gimple;
  85   loop_vec_info loop_vinfo;
  86   stmt_vec_info stmt_vinfo;
  87   tree type = TREE_TYPE (name);
  88   tree oprnd0;
  89   enum vect_def_type dt;
  90   tree def;
  91
  92   stmt_vinfo = vinfo_for_stmt (use_stmt);
  93   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
  94
  95   if (!vect_is_simple_use (name, loop_vinfo, NULL, def_stmt, &def, &dt))
  96     return false;
  97
  98   if (dt != vect_internal_def
  99       && dt != vect_external_def && dt != vect_constant_def)
 100     return false;
 101
 102   if (! *def_stmt)
 103     return false;
 104
 105   if (!is_gimple_assign (*def_stmt))
 106     return false;
 107
 108   if (gimple_assign_rhs_code (*def_stmt) != NOP_EXPR)
 109     return false;
 110
 111   oprnd0 = gimple_assign_rhs1 (*def_stmt);
 112
 113   *half_type = TREE_TYPE (oprnd0);
 114   if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
 115       || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type)) && check_sign)
 116       || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
 117     return false;
 118
 119   if (!vect_is_simple_use (oprnd0, loop_vinfo, NULL, &dummy_gimple, &dummy,
 120                            &dt))
 121     return false;
 122
 123   return true;
 124 }
 125
 126 /* Helper to return a new temporary for pattern of TYPE for STMT.  If STMT
 127    is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */
 128
 129 static tree
 130 vect_recog_temp_ssa_var (tree type, gimple stmt)
 131 {
 132   tree var = create_tmp_var (type, "patt");
 133
 134   add_referenced_var (var);
 135   var = make_ssa_name (var, stmt);
 136   return var;
 137 }
 138
 139 /* Function vect_recog_dot_prod_pattern
 140
 141    Try to find the following pattern:
 142
 143      type x_t, y_t;
 144      TYPE1 prod;
 145      TYPE2 sum = init;
 146    loop:
 147      sum_0 = phi <init, sum_1>
 148      S1  x_t = ...
 149      S2  y_t = ...
 150      S3  x_T = (TYPE1) x_t;
 151      S4  y_T = (TYPE1) y_t;
 152      S5  prod = x_T * y_T;
 153      [S6  prod = (TYPE2) prod;  #optional]
 154      S7  sum_1 = prod + sum_0;
 155
 156    where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
 157    same size of 'TYPE1' or bigger. This is a special case of a reduction
 158    computation.
 159
 160    Input:
 161
 162    * STMTS: Contains a stmt from which the pattern search begins.  In the
 163    example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7}
 164    will be detected.
 165
 166    Output:
 167
 168    * TYPE_IN: The type of the input arguments to the pattern.
 169
 170    * TYPE_OUT: The type of the output  of this pattern.
 171
 172    * Return value: A new stmt that will be used to replace the sequence of
 173    stmts that constitute the pattern. In this case it will be:
 174         WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
 175
 176    Note: The dot-prod idiom is a widening reduction pattern that is
 177          vectorized without preserving all the intermediate results. It
 178          produces only N/2 (widened) results (by summing up pairs of
 179          intermediate results) rather than all N results.  Therefore, we
 180          cannot allow this pattern when we want to get all the results and in
 181          the correct order (as is the case when this computation is in an
 182          inner-loop nested in an outer-loop that us being vectorized).  */
 183
 184 static gimple
 185 vect_recog_dot_prod_pattern (VEC (gimple, heap) **stmts, tree *type_in,
 186                              tree *type_out)
 187 {
 188   gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);
 189   tree oprnd0, oprnd1;
 190   tree oprnd00, oprnd01;
 191   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 192   tree type, half_type;
 193   gimple pattern_stmt;
 194   tree prod_type;
 195   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 196   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
 197   tree var;
 198
 199   if (!is_gimple_assign (last_stmt))
 200     return NULL;
 201
 202   type = gimple_expr_type (last_stmt);
 203
 204   /* Look for the following pattern
 205           DX = (TYPE1) X;
 206           DY = (TYPE1) Y;
 207           DPROD = DX * DY;
 208           DDPROD = (TYPE2) DPROD;
 209           sum_1 = DDPROD + sum_0;
 210      In which
 211      - DX is double the size of X
 212      - DY is double the size of Y
 213      - DX, DY, DPROD all have the same type
 214      - sum is the same size of DPROD or bigger
 215      - sum has been recognized as a reduction variable.
 216
 217      This is equivalent to:
 218        DPROD = X w* Y;          #widen mult
 219        sum_1 = DPROD w+ sum_0;  #widen summation
 220      or
 221        DPROD = X w* Y;          #widen mult
 222        sum_1 = DPROD + sum_0;   #summation
 223    */
 224
 225   /* Starting from LAST_STMT, follow the defs of its uses in search
 226      of the above pattern.  */
 227
 228   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
 229     return NULL;
 230
 231   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 232     {
 233       /* Has been detected as widening-summation?  */
 234
 235       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 236       type = gimple_expr_type (stmt);
 237       if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
 238         return NULL;
 239       oprnd0 = gimple_assign_rhs1 (stmt);
 240       oprnd1 = gimple_assign_rhs2 (stmt);
 241       half_type = TREE_TYPE (oprnd0);
 242     }
 243   else
 244     {
 245       gimple def_stmt;
 246
 247       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 248         return NULL;
 249       oprnd0 = gimple_assign_rhs1 (last_stmt);
 250       oprnd1 = gimple_assign_rhs2 (last_stmt);
 251       if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 252           || !types_compatible_p (TREE_TYPE (oprnd1), type))
 253         return NULL;
 254       stmt = last_stmt;
 255
 256       if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt, true))
 257         {
 258           stmt = def_stmt;
 259           oprnd0 = gimple_assign_rhs1 (stmt);
 260         }
 261       else
 262         half_type = type;
 263     }
 264
 265   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
 266      we know that oprnd1 is the reduction variable (defined by a loop-header
 267      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 268      Left to check that oprnd0 is defined by a (widen_)mult_expr  */
 269   if (TREE_CODE (oprnd0) != SSA_NAME)
 270     return NULL;
 271
 272   prod_type = half_type;
 273   stmt = SSA_NAME_DEF_STMT (oprnd0);
 274
 275   /* It could not be the dot_prod pattern if the stmt is outside the loop.  */
 276   if (!gimple_bb (stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 277     return NULL;
 278
 279   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
 280      inside the loop (in case we are analyzing an outer-loop).  */
 281   if (!is_gimple_assign (stmt))
 282     return NULL;
 283   stmt_vinfo = vinfo_for_stmt (stmt);
 284   gcc_assert (stmt_vinfo);
 285   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
 286     return NULL;
 287   if (gimple_assign_rhs_code (stmt) != MULT_EXPR)
 288     return NULL;
 289   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 290     {
 291       /* Has been detected as a widening multiplication?  */
 292
 293       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 294       if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR)
 295         return NULL;
 296       stmt_vinfo = vinfo_for_stmt (stmt);
 297       gcc_assert (stmt_vinfo);
 298       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_internal_def);
 299       oprnd00 = gimple_assign_rhs1 (stmt);
 300       oprnd01 = gimple_assign_rhs2 (stmt);
 301     }
 302   else
 303     {
 304       tree half_type0, half_type1;
 305       gimple def_stmt;
 306       tree oprnd0, oprnd1;
 307
 308       oprnd0 = gimple_assign_rhs1 (stmt);
 309       oprnd1 = gimple_assign_rhs2 (stmt);
 310       if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type)
 311           || !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
 312         return NULL;
 313       if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt, true))
 314         return NULL;
 315       oprnd00 = gimple_assign_rhs1 (def_stmt);
 316       if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt, true))
 317         return NULL;
 318       oprnd01 = gimple_assign_rhs1 (def_stmt);
 319       if (!types_compatible_p (half_type0, half_type1))
 320         return NULL;
 321       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
 322         return NULL;
 323     }
 324
 325   half_type = TREE_TYPE (oprnd00);
 326   *type_in = half_type;
 327   *type_out = type;
 328
 329   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 330   var = vect_recog_temp_ssa_var (type, NULL);
 331   pattern_stmt = gimple_build_assign_with_ops3 (DOT_PROD_EXPR, var,
 332                                                 oprnd00, oprnd01, oprnd1);
 333
 334   if (vect_print_dump_info (REPORT_DETAILS))
 335     {
 336       fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
 337       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
 338     }
 339
 340   /* We don't allow changing the order of the computation in the inner-loop
 341      when doing outer-loop vectorization.  */
 342   gcc_assert (!nested_in_vect_loop_p (loop, last_stmt));
 343
 344   return pattern_stmt;
 345 }
 346
 347
 348 /* Handle widening operation by a constant.  At the moment we support MULT_EXPR
 349    and LSHIFT_EXPR.
 350
 351    For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR
 352    we check that CONST_OPRND is less or equal to the size of HALF_TYPE.
 353
 354    Otherwise, if the type of the result (TYPE) is at least 4 times bigger than
 355    HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE)
 356    that satisfies the above restrictions,  we can perform a widening opeartion
 357    from the intermediate type to TYPE and replace a_T = (TYPE) a_t;
 358    with a_it = (interm_type) a_t;  */
 359
 360 static bool
 361 vect_handle_widen_op_by_const (gimple stmt, enum tree_code code,
 362                                tree const_oprnd, tree *oprnd,
 363                                VEC (gimple, heap) **stmts, tree type,
 364                                tree *half_type, gimple def_stmt)
 365 {
 366   tree new_type, new_oprnd, tmp;
 367   gimple new_stmt;
 368   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (vinfo_for_stmt (stmt));
 369   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
 370
 371   if (code != MULT_EXPR && code != LSHIFT_EXPR)
 372     return false;
 373
 374   if (((code == MULT_EXPR && int_fits_type_p (const_oprnd, *half_type))
 375         || (code == LSHIFT_EXPR
 376             && compare_tree_int (const_oprnd, TYPE_PRECISION (*half_type))
 377                 != 1))
 378       && TYPE_PRECISION (type) == (TYPE_PRECISION (*half_type) * 2))
 379     {
 380       /* CONST_OPRND is a constant of HALF_TYPE.  */
 381       *oprnd = gimple_assign_rhs1 (def_stmt);
 382       return true;
 383     }
 384
 385   if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4)
 386       || !gimple_bb (def_stmt)
 387       || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
 388       || !vinfo_for_stmt (def_stmt))
 389     return false;
 390
 391   /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for
 392      a type 2 times bigger than HALF_TYPE.  */
 393   new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2,
 394                                              TYPE_UNSIGNED (type));
 395   if ((code == MULT_EXPR && !int_fits_type_p (const_oprnd, new_type))
 396       || (code == LSHIFT_EXPR
 397           && compare_tree_int (const_oprnd, TYPE_PRECISION (new_type)) == 1))
 398     return false;
 399
 400   /* Use NEW_TYPE for widening operation.  */
 401   if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
 402     {
 403       new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
 404       /* Check if the already created pattern stmt is what we need.  */
 405       if (!is_gimple_assign (new_stmt)
 406           || gimple_assign_rhs_code (new_stmt) != NOP_EXPR
 407           || TREE_TYPE (gimple_assign_lhs (new_stmt)) != new_type)
 408         return false;
 409
 410       VEC_safe_push (gimple, heap, *stmts, def_stmt);
 411       *oprnd = gimple_assign_lhs (new_stmt);
 412     }
 413   else
 414     {
 415       /* Create a_T = (NEW_TYPE) a_t;  */
 416       *oprnd = gimple_assign_rhs1 (def_stmt);
 417       tmp = create_tmp_var (new_type, NULL);
 418       add_referenced_var (tmp);
 419       new_oprnd = make_ssa_name (tmp, NULL);
 420       new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd, *oprnd,
 421                                                NULL_TREE);
 422       STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
 423       VEC_safe_push (gimple, heap, *stmts, def_stmt);
 424       *oprnd = new_oprnd;
 425     }
 426
 427   *half_type = new_type;
 428   return true;
 429 }
 430
 431
 432 /* Function vect_recog_widen_mult_pattern
 433
 434    Try to find the following pattern:
 435
 436      type a_t, b_t;
 437      TYPE a_T, b_T, prod_T;
 438
 439      S1  a_t = ;
 440      S2  b_t = ;
 441      S3  a_T = (TYPE) a_t;
 442      S4  b_T = (TYPE) b_t;
 443      S5  prod_T = a_T * b_T;
 444
 445    where type 'TYPE' is at least double the size of type 'type'.
 446
 447    Also detect unsgigned cases:
 448
 449      unsigned type a_t, b_t;
 450      unsigned TYPE u_prod_T;
 451      TYPE a_T, b_T, prod_T;
 452
 453      S1  a_t = ;
 454      S2  b_t = ;
 455      S3  a_T = (TYPE) a_t;
 456      S4  b_T = (TYPE) b_t;
 457      S5  prod_T = a_T * b_T;
 458      S6  u_prod_T = (unsigned TYPE) prod_T;
 459
 460    and multiplication by constants:
 461
 462      type a_t;
 463      TYPE a_T, prod_T;
 464
 465      S1  a_t = ;
 466      S3  a_T = (TYPE) a_t;
 467      S5  prod_T = a_T * CONST;
 468
 469    A special case of multiplication by constants is when 'TYPE' is 4 times
 470    bigger than 'type', but CONST fits an intermediate type 2 times smaller
 471    than 'TYPE'.  In that case we create an additional pattern stmt for S3
 472    to create a variable of the intermediate type, and perform widen-mult
 473    on the intermediate type as well:
 474
 475      type a_t;
 476      interm_type a_it;
 477      TYPE a_T, prod_T,  prod_T';
 478
 479      S1  a_t = ;
 480      S3  a_T = (TYPE) a_t;
 481            '--> a_it = (interm_type) a_t;
 482      S5  prod_T = a_T * CONST;
 483            '--> prod_T' = a_it w* CONST;
 484
 485    Input/Output:
 486
 487    * STMTS: Contains a stmt from which the pattern search begins.  In the
 488    example, when this function is called with S5, the pattern {S3,S4,S5,(S6)}
 489    is detected.  In case of unsigned widen-mult, the original stmt (S5) is
 490    replaced with S6 in STMTS.  In case of multiplication by a constant
 491    of an intermediate type (the last case above), STMTS also contains S3
 492    (inserted before S5).
 493
 494    Output:
 495
 496    * TYPE_IN: The type of the input arguments to the pattern.
 497
 498    * TYPE_OUT: The type of the output of this pattern.
 499
 500    * Return value: A new stmt that will be used to replace the sequence of
 501    stmts that constitute the pattern.  In this case it will be:
 502         WIDEN_MULT <a_t, b_t>
 503 */
 504
 505 static gimple
 506 vect_recog_widen_mult_pattern (VEC (gimple, heap) **stmts,
 507                                tree *type_in, tree *type_out)
 508 {
 509   gimple last_stmt = VEC_pop (gimple, *stmts);
 510   gimple def_stmt0, def_stmt1;
 511   tree oprnd0, oprnd1;
 512   tree type, half_type0, half_type1;
 513   gimple pattern_stmt;
 514   tree vectype, vectype_out = NULL_TREE;
 515   tree dummy;
 516   tree var;
 517   enum tree_code dummy_code;
 518   int dummy_int;
 519   VEC (tree, heap) *dummy_vec;
 520   bool op1_ok;
 521
 522   if (!is_gimple_assign (last_stmt))
 523     return NULL;
 524
 525   type = gimple_expr_type (last_stmt);
 526
 527   /* Starting from LAST_STMT, follow the defs of its uses in search
 528      of the above pattern.  */
 529
 530   if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)
 531     return NULL;
 532
 533   oprnd0 = gimple_assign_rhs1 (last_stmt);
 534   oprnd1 = gimple_assign_rhs2 (last_stmt);
 535   if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 536       || !types_compatible_p (TREE_TYPE (oprnd1), type))
 537     return NULL;
 538
 539   /* Check argument 0.  */
 540   if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false))
 541     return NULL;
 542   /* Check argument 1.  */
 543   op1_ok = widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1, false);
 544
 545   if (op1_ok)
 546     {
 547       oprnd0 = gimple_assign_rhs1 (def_stmt0);
 548       oprnd1 = gimple_assign_rhs1 (def_stmt1);
 549     }
 550   else
 551     {
 552       if (TREE_CODE (oprnd1) == INTEGER_CST
 553           && TREE_CODE (half_type0) == INTEGER_TYPE
 554           && vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1,
 555                                             &oprnd0, stmts, type,
 556                                             &half_type0, def_stmt0))
 557         half_type1 = half_type0;
 558       else
 559         return NULL;
 560     }
 561
 562   /* Handle unsigned case.  Look for
 563      S6  u_prod_T = (unsigned TYPE) prod_T;
 564      Use unsigned TYPE as the type for WIDEN_MULT_EXPR.  */
 565   if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
 566     {
 567       tree lhs = gimple_assign_lhs (last_stmt), use_lhs;
 568       imm_use_iterator imm_iter;
 569       use_operand_p use_p;
 570       int nuses = 0;
 571       gimple use_stmt = NULL;
 572       tree use_type;
 573
 574       if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1))
 575         return NULL;
 576
 577       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
 578         {
 579           if (is_gimple_debug (USE_STMT (use_p)))
 580             continue;
 581           use_stmt = USE_STMT (use_p);
 582           nuses++;
 583         }
 584
 585       if (nuses != 1 || !is_gimple_assign (use_stmt)
 586           || gimple_assign_rhs_code (use_stmt) != NOP_EXPR)
 587         return NULL;
 588
 589       use_lhs = gimple_assign_lhs (use_stmt);
 590       use_type = TREE_TYPE (use_lhs);
 591       if (!INTEGRAL_TYPE_P (use_type)
 592           || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))
 593           || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))
 594         return NULL;
 595
 596       type = use_type;
 597       last_stmt = use_stmt;
 598     }
 599
 600   if (!types_compatible_p (half_type0, half_type1))
 601     return NULL;
 602
 603   /* Pattern detected.  */
 604   if (vect_print_dump_info (REPORT_DETAILS))
 605     fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");
 606
 607   /* Check target support  */
 608   vectype = get_vectype_for_scalar_type (half_type0);
 609   vectype_out = get_vectype_for_scalar_type (type);
 610   if (!vectype
 611       || !vectype_out
 612       || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt,
 613                                           vectype_out, vectype,
 614                                           &dummy, &dummy, &dummy_code,
 615                                           &dummy_code, &dummy_int, &dummy_vec))
 616     return NULL;
 617
 618   *type_in = vectype;
 619   *type_out = vectype_out;
 620
 621   /* Pattern supported. Create a stmt to be used to replace the pattern: */
 622   var = vect_recog_temp_ssa_var (type, NULL);
 623   pattern_stmt = gimple_build_assign_with_ops (WIDEN_MULT_EXPR, var, oprnd0,
 624                                                oprnd1);
 625
 626   if (vect_print_dump_info (REPORT_DETAILS))
 627     print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
 628
 629   VEC_safe_push (gimple, heap, *stmts, last_stmt);
 630   return pattern_stmt;
 631 }
 632
 633
 634 /* Function vect_recog_pow_pattern
 635
 636    Try to find the following pattern:
 637
 638      x = POW (y, N);
 639
 640    with POW being one of pow, powf, powi, powif and N being
 641    either 2 or 0.5.
 642
 643    Input:
 644
 645    * LAST_STMT: A stmt from which the pattern search begins.
 646
 647    Output:
 648
 649    * TYPE_IN: The type of the input arguments to the pattern.
 650
 651    * TYPE_OUT: The type of the output of this pattern.
 652
 653    * Return value: A new stmt that will be used to replace the sequence of
 654    stmts that constitute the pattern. In this case it will be:
 655         x = x * x
 656    or
 657         x = sqrt (x)
 658 */
 659
 660 static gimple
 661 vect_recog_pow_pattern (VEC (gimple, heap) **stmts, tree *type_in,
 662                         tree *type_out)
 663 {
 664   gimple last_stmt = VEC_index (gimple, *stmts, 0);
 665   tree fn, base, exp = NULL;
 666   gimple stmt;
 667   tree var;
 668
 669   if (!is_gimple_call (last_stmt) || gimple_call_lhs (last_stmt) == NULL)
 670     return NULL;
 671
 672   fn = gimple_call_fndecl (last_stmt);
 673   if (fn == NULL_TREE || DECL_BUILT_IN_CLASS (fn) != BUILT_IN_NORMAL)
 674    return NULL;
 675
 676   switch (DECL_FUNCTION_CODE (fn))
 677     {
 678     case BUILT_IN_POWIF:
 679     case BUILT_IN_POWI:
 680     case BUILT_IN_POWF:
 681     case BUILT_IN_POW:
 682       base = gimple_call_arg (last_stmt, 0);
 683       exp = gimple_call_arg (last_stmt, 1);
 684       if (TREE_CODE (exp) != REAL_CST
 685           && TREE_CODE (exp) != INTEGER_CST)
 686         return NULL;
 687       break;
 688
 689     default:
 690       return NULL;
 691     }
 692
 693   /* We now have a pow or powi builtin function call with a constant
 694      exponent.  */
 695
 696   *type_out = NULL_TREE;
 697
 698   /* Catch squaring.  */
 699   if ((host_integerp (exp, 0)
 700        && tree_low_cst (exp, 0) == 2)
 701       || (TREE_CODE (exp) == REAL_CST
 702           && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
 703     {
 704       *type_in = TREE_TYPE (base);
 705
 706       var = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
 707       stmt = gimple_build_assign_with_ops (MULT_EXPR, var, base, base);
 708       return stmt;
 709     }
 710
 711   /* Catch square root.  */
 712   if (TREE_CODE (exp) == REAL_CST
 713       && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconsthalf))
 714     {
 715       tree newfn = mathfn_built_in (TREE_TYPE (base), BUILT_IN_SQRT);
 716       *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
 717       if (*type_in)
 718         {
 719           gimple stmt = gimple_build_call (newfn, 1, base);
 720           if (vectorizable_function (stmt, *type_in, *type_in)
 721               != NULL_TREE)
 722             {
 723               var = vect_recog_temp_ssa_var (TREE_TYPE (base), stmt);
 724               gimple_call_set_lhs (stmt, var);
 725               return stmt;
 726             }
 727         }
 728     }
 729
 730   return NULL;
 731 }
 732
 733
 734 /* Function vect_recog_widen_sum_pattern
 735
 736    Try to find the following pattern:
 737
 738      type x_t;
 739      TYPE x_T, sum = init;
 740    loop:
 741      sum_0 = phi <init, sum_1>
 742      S1  x_t = *p;
 743      S2  x_T = (TYPE) x_t;
 744      S3  sum_1 = x_T + sum_0;
 745
 746    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 747    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 748    a special case of a reduction computation.
 749
 750    Input:
 751
 752    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 753    when this function is called with S3, the pattern {S2,S3} will be detected.
 754
 755    Output:
 756
 757    * TYPE_IN: The type of the input arguments to the pattern.
 758
 759    * TYPE_OUT: The type of the output of this pattern.
 760
 761    * Return value: A new stmt that will be used to replace the sequence of
 762    stmts that constitute the pattern. In this case it will be:
 763         WIDEN_SUM <x_t, sum_0>
 764
 765    Note: The widening-sum idiom is a widening reduction pattern that is
 766          vectorized without preserving all the intermediate results. It
 767          produces only N/2 (widened) results (by summing up pairs of
 768          intermediate results) rather than all N results.  Therefore, we
 769          cannot allow this pattern when we want to get all the results and in
 770          the correct order (as is the case when this computation is in an
 771          inner-loop nested in an outer-loop that us being vectorized).  */
 772
 773 static gimple
 774 vect_recog_widen_sum_pattern (VEC (gimple, heap) **stmts, tree *type_in,
 775                               tree *type_out)
 776 {
 777   gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);
 778   tree oprnd0, oprnd1;
 779   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 780   tree type, half_type;
 781   gimple pattern_stmt;
 782   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 783   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
 784   tree var;
 785
 786   if (!is_gimple_assign (last_stmt))
 787     return NULL;
 788
 789   type = gimple_expr_type (last_stmt);
 790
 791   /* Look for the following pattern
 792           DX = (TYPE) X;
 793           sum_1 = DX + sum_0;
 794      In which DX is at least double the size of X, and sum_1 has been
 795      recognized as a reduction variable.
 796    */
 797
 798   /* Starting from LAST_STMT, follow the defs of its uses in search
 799      of the above pattern.  */
 800
 801   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
 802     return NULL;
 803
 804   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 805     return NULL;
 806
 807   oprnd0 = gimple_assign_rhs1 (last_stmt);
 808   oprnd1 = gimple_assign_rhs2 (last_stmt);
 809   if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 810       || !types_compatible_p (TREE_TYPE (oprnd1), type))
 811     return NULL;
 812
 813   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
 814      we know that oprnd1 is the reduction variable (defined by a loop-header
 815      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 816      Left to check that oprnd0 is defined by a cast from type 'type' to type
 817      'TYPE'.  */
 818
 819   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt, true))
 820     return NULL;
 821
 822   oprnd0 = gimple_assign_rhs1 (stmt);
 823   *type_in = half_type;
 824   *type_out = type;
 825
 826   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 827   var = vect_recog_temp_ssa_var (type, NULL);
 828   pattern_stmt = gimple_build_assign_with_ops (WIDEN_SUM_EXPR, var,
 829                                                oprnd0, oprnd1);
 830
 831   if (vect_print_dump_info (REPORT_DETAILS))
 832     {
 833       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 834       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
 835     }
 836
 837   /* We don't allow changing the order of the computation in the inner-loop
 838      when doing outer-loop vectorization.  */
 839   gcc_assert (!nested_in_vect_loop_p (loop, last_stmt));
 840
 841   return pattern_stmt;
 842 }
 843
 844
 845 /* Return TRUE if the operation in STMT can be performed on a smaller type.
 846
 847    Input:
 848    STMT - a statement to check.
 849    DEF - we support operations with two operands, one of which is constant.
 850          The other operand can be defined by a demotion operation, or by a
 851          previous statement in a sequence of over-promoted operations.  In the
 852          later case DEF is used to replace that operand.  (It is defined by a
 853          pattern statement we created for the previous statement in the
 854          sequence).
 855
 856    Input/output:
 857    NEW_TYPE - Output: a smaller type that we are trying to use.  Input: if not
 858          NULL, it's the type of DEF.
 859    STMTS - additional pattern statements.  If a pattern statement (type
 860          conversion) is created in this function, its original statement is
 861          added to STMTS.
 862
 863    Output:
 864    OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new
 865          operands to use in the new pattern statement for STMT (will be created
 866          in vect_recog_over_widening_pattern ()).
 867    NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
 868          statements for STMT: the first one is a type promotion and the second
 869          one is the operation itself.  We return the type promotion statement
 870          in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_STMT of
 871          the second pattern statement.  */
 872
 873 static bool
 874 vect_operation_fits_smaller_type (gimple stmt, tree def, tree *new_type,
 875                                   tree *op0, tree *op1, gimple *new_def_stmt,
 876                                   VEC (gimple, heap) **stmts)
 877 {
 878   enum tree_code code;
 879   tree const_oprnd, oprnd;
 880   tree interm_type = NULL_TREE, half_type, tmp, new_oprnd, type;
 881   gimple def_stmt, new_stmt;
 882   bool first = false;
 883   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (vinfo_for_stmt (stmt));
 884   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
 885
 886   *new_def_stmt = NULL;
 887
 888   if (!is_gimple_assign (stmt))
 889     return false;
 890
 891   code = gimple_assign_rhs_code (stmt);
 892   if (code != LSHIFT_EXPR && code != RSHIFT_EXPR
 893       && code != BIT_IOR_EXPR && code != BIT_XOR_EXPR && code != BIT_AND_EXPR)
 894     return false;
 895
 896   oprnd = gimple_assign_rhs1 (stmt);
 897   const_oprnd = gimple_assign_rhs2 (stmt);
 898   type = gimple_expr_type (stmt);
 899
 900   if (TREE_CODE (oprnd) != SSA_NAME
 901       || TREE_CODE (const_oprnd) != INTEGER_CST)
 902     return false;
 903
 904   /* If we are in the middle of a sequence, we use DEF from a previous
 905      statement.  Otherwise, OPRND has to be a result of type promotion.  */
 906   if (*new_type)
 907     {
 908       half_type = *new_type;
 909       oprnd = def;
 910     }
 911   else
 912     {
 913       first = true;
 914       if (!widened_name_p (oprnd, stmt, &half_type, &def_stmt, false)
 915           || !gimple_bb (def_stmt)
 916           || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
 917           || !vinfo_for_stmt (def_stmt))
 918         return false;
 919     }
 920
 921   /* Can we perform the operation on a smaller type?  */
 922   switch (code)
 923     {
 924       case BIT_IOR_EXPR:
 925       case BIT_XOR_EXPR:
 926       case BIT_AND_EXPR:
 927         if (!int_fits_type_p (const_oprnd, half_type))
 928           {
 929             /* HALF_TYPE is not enough.  Try a bigger type if possible.  */
 930             if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
 931               return false;
 932
 933             interm_type = build_nonstandard_integer_type (
 934                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
 935             if (!int_fits_type_p (const_oprnd, interm_type))
 936               return false;
 937           }
 938
 939         break;
 940
 941       case LSHIFT_EXPR:
 942         /* Try intermediate type - HALF_TYPE is not enough for sure.  */
 943         if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
 944           return false;
 945
 946         /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size.
 947           (e.g., if the original value was char, the shift amount is at most 8
 948            if we want to use short).  */
 949         if (compare_tree_int (const_oprnd, TYPE_PRECISION (half_type)) == 1)
 950           return false;
 951
 952         interm_type = build_nonstandard_integer_type (
 953                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
 954
 955         if (!vect_supportable_shift (code, interm_type))
 956           return false;
 957
 958         break;
 959
 960       case RSHIFT_EXPR:
 961         if (vect_supportable_shift (code, half_type))
 962           break;
 963
 964         /* Try intermediate type - HALF_TYPE is not supported.  */
 965         if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
 966           return false;
 967
 968         interm_type = build_nonstandard_integer_type (
 969                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
 970
 971         if (!vect_supportable_shift (code, interm_type))
 972           return false;
 973
 974         break;
 975
 976       default:
 977         gcc_unreachable ();
 978     }
 979
 980   /* There are four possible cases:
 981      1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's
 982         the first statement in the sequence)
 983         a. The original, HALF_TYPE, is not enough - we replace the promotion
 984            from HALF_TYPE to TYPE with a promotion to INTERM_TYPE.
 985         b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original
 986            promotion.
 987      2. OPRND is defined by a pattern statement we created.
 988         a. Its type is not sufficient for the operation, we create a new stmt:
 989            a type conversion for OPRND from HALF_TYPE to INTERM_TYPE.  We store
 990            this statement in NEW_DEF_STMT, and it is later put in
 991            STMT_VINFO_PATTERN_DEF_STMT of the pattern statement for STMT.
 992         b. OPRND is good to use in the new statement.  */
 993   if (first)
 994     {
 995       if (interm_type)
 996         {
 997           /* Replace the original type conversion HALF_TYPE->TYPE with
 998              HALF_TYPE->INTERM_TYPE.  */
 999           if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
1000             {
1001               new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
1002               /* Check if the already created pattern stmt is what we need.  */
1003               if (!is_gimple_assign (new_stmt)
1004                   || gimple_assign_rhs_code (new_stmt) != NOP_EXPR
1005                   || TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type)
1006                 return false;
1007
1008               VEC_safe_push (gimple, heap, *stmts, def_stmt);
1009               oprnd = gimple_assign_lhs (new_stmt);
1010             }
1011           else
1012             {
1013               /* Create NEW_OPRND = (INTERM_TYPE) OPRND.  */
1014               oprnd = gimple_assign_rhs1 (def_stmt);
1015               tmp = create_tmp_reg (interm_type, NULL);
1016               add_referenced_var (tmp);
1017               new_oprnd = make_ssa_name (tmp, NULL);
1018               new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
1019                                                        oprnd, NULL_TREE);
1020               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
1021               VEC_safe_push (gimple, heap, *stmts, def_stmt);
1022               oprnd = new_oprnd;
1023             }
1024         }
1025       else
1026         {
1027           /* Retrieve the operand before the type promotion.  */
1028           oprnd = gimple_assign_rhs1 (def_stmt);
1029         }
1030     }
1031   else
1032     {
1033       if (interm_type)
1034         {
1035           /* Create a type conversion HALF_TYPE->INTERM_TYPE.  */
1036           tmp = create_tmp_reg (interm_type, NULL);
1037           add_referenced_var (tmp);
1038           new_oprnd = make_ssa_name (tmp, NULL);
1039           new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
1040                                                    oprnd, NULL_TREE);
1041           oprnd = new_oprnd;
1042           *new_def_stmt = new_stmt;
1043         }
1044
1045       /* Otherwise, OPRND is already set.  */
1046     }
1047
1048   if (interm_type)
1049     *new_type = interm_type;
1050   else
1051     *new_type = half_type;
1052
1053   *op0 = oprnd;
1054   *op1 = fold_convert (*new_type, const_oprnd);
1055
1056   return true;
1057 }
1058
1059
1060 /* Try to find a statement or a sequence of statements that can be performed
1061    on a smaller type:
1062
1063      type x_t;
1064      TYPE x_T, res0_T, res1_T;
1065    loop:
1066      S1  x_t = *p;
1067      S2  x_T = (TYPE) x_t;
1068      S3  res0_T = op (x_T, C0);
1069      S4  res1_T = op (res0_T, C1);
1070      S5  ... = () res1_T;  - type demotion
1071
1072    where type 'TYPE' is at least double the size of type 'type', C0 and C1 are
1073    constants.
1074    Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
1075    be 'type' or some intermediate type.  For now, we expect S5 to be a type
1076    demotion operation.  We also check that S3 and S4 have only one use.  */
1077
1078 static gimple
1079 vect_recog_over_widening_pattern (VEC (gimple, heap) **stmts,
1080                                   tree *type_in, tree *type_out)
1081 {
1082   gimple stmt = VEC_pop (gimple, *stmts);
1083   gimple pattern_stmt = NULL, new_def_stmt, prev_stmt = NULL, use_stmt = NULL;
1084   tree op0, op1, vectype = NULL_TREE, lhs, use_lhs, use_type;
1085   imm_use_iterator imm_iter;
1086   use_operand_p use_p;
1087   int nuses = 0;
1088   tree var = NULL_TREE, new_type = NULL_TREE, tmp, new_oprnd;
1089   bool first;
1090   struct loop *loop = (gimple_bb (stmt))->loop_father;
1091
1092   first = true;
1093   while (1)
1094     {
1095       if (!vinfo_for_stmt (stmt)
1096           || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt)))
1097         return NULL;
1098
1099       new_def_stmt = NULL;
1100       if (!vect_operation_fits_smaller_type (stmt, var, &new_type,
1101                                              &op0, &op1, &new_def_stmt,
1102                                              stmts))
1103         {
1104           if (first)
1105             return NULL;
1106           else
1107             break;
1108         }
1109
1110       /* STMT can be performed on a smaller type.  Check its uses.  */
1111       lhs = gimple_assign_lhs (stmt);
1112       nuses = 0;
1113       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1114         {
1115           if (is_gimple_debug (USE_STMT (use_p)))
1116             continue;
1117           use_stmt = USE_STMT (use_p);
1118           nuses++;
1119         }
1120
1121       if (nuses != 1 || !is_gimple_assign (use_stmt)
1122           || !gimple_bb (use_stmt)
1123           || !flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
1124         return NULL;
1125
1126       /* Create pattern statement for STMT.  */
1127       vectype = get_vectype_for_scalar_type (new_type);
1128       if (!vectype)
1129         return NULL;
1130
1131       /* We want to collect all the statements for which we create pattern
1132          statetments, except for the case when the last statement in the
1133          sequence doesn't have a corresponding pattern statement.  In such
1134          case we associate the last pattern statement with the last statement
1135          in the sequence.  Therefore, we only add the original statement to
1136          the list if we know that it is not the last.  */
1137       if (prev_stmt)
1138         VEC_safe_push (gimple, heap, *stmts, prev_stmt);
1139
1140       var = vect_recog_temp_ssa_var (new_type, NULL);
1141       pattern_stmt
1142         = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt), var,
1143                                         op0, op1);
1144       STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
1145       STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (stmt)) = new_def_stmt;
1146
1147       if (vect_print_dump_info (REPORT_DETAILS))
1148         {
1149           fprintf (vect_dump, "created pattern stmt: ");
1150           print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1151         }
1152
1153       prev_stmt = stmt;
1154       stmt = use_stmt;
1155
1156       first = false;
1157     }
1158
1159   /* We got a sequence.  We expect it to end with a type demotion operation.
1160      Otherwise, we quit (for now).  There are three possible cases: the
1161      conversion is to NEW_TYPE (we don't do anything), the conversion is to
1162      a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and
1163      NEW_TYPE differs (we create a new conversion statement).  */
1164   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1165     {
1166       use_lhs = gimple_assign_lhs (use_stmt);
1167       use_type = TREE_TYPE (use_lhs);
1168       /* Support only type promotion or signedess change.  */
1169       if (!INTEGRAL_TYPE_P (use_type)
1170           || TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type))
1171         return NULL;
1172
1173       if (TYPE_UNSIGNED (new_type) != TYPE_UNSIGNED (use_type)
1174           || TYPE_PRECISION (new_type) != TYPE_PRECISION (use_type))
1175         {
1176           /* Create NEW_TYPE->USE_TYPE conversion.  */
1177           tmp = create_tmp_reg (use_type, NULL);
1178           add_referenced_var (tmp);
1179           new_oprnd = make_ssa_name (tmp, NULL);
1180           pattern_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
1181                                                        var, NULL_TREE);
1182           STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt)) = pattern_stmt;
1183
1184           *type_in = get_vectype_for_scalar_type (new_type);
1185           *type_out = get_vectype_for_scalar_type (use_type);
1186
1187           /* We created a pattern statement for the last statement in the
1188              sequence, so we don't need to associate it with the pattern
1189              statement created for PREV_STMT.  Therefore, we add PREV_STMT
1190              to the list in order to mark it later in vect_pattern_recog_1.  */
1191           if (prev_stmt)
1192             VEC_safe_push (gimple, heap, *stmts, prev_stmt);
1193         }
1194       else
1195         {
1196           if (prev_stmt)
1197             STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (use_stmt))
1198                = STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (prev_stmt));
1199
1200           *type_in = vectype;
1201           *type_out = NULL_TREE;
1202         }
1203
1204       VEC_safe_push (gimple, heap, *stmts, use_stmt);
1205     }
1206   else
1207     /* TODO: support general case, create a conversion to the correct type.  */
1208     return NULL;
1209
1210   /* Pattern detected.  */
1211   if (vect_print_dump_info (REPORT_DETAILS))
1212     {
1213       fprintf (vect_dump, "vect_recog_over_widening_pattern: detected: ");
1214       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1215     }
1216
1217   return pattern_stmt;
1218 }
1219
1220 /* Detect widening shift pattern:
1221
1222    type a_t;
1223    TYPE a_T, res_T;
1224
1225    S1 a_t = ;
1226    S2 a_T = (TYPE) a_t;
1227    S3 res_T = a_T << CONST;
1228
1229   where type 'TYPE' is at least double the size of type 'type'.
1230
1231   Also detect unsigned cases:
1232
1233   unsigned type a_t;
1234   unsigned TYPE u_res_T;
1235   TYPE a_T, res_T;
1236
1237   S1 a_t = ;
1238   S2 a_T = (TYPE) a_t;
1239   S3 res_T = a_T << CONST;
1240   S4 u_res_T = (unsigned TYPE) res_T;
1241
1242   And a case when 'TYPE' is 4 times bigger than 'type'.  In that case we
1243   create an additional pattern stmt for S2 to create a variable of an
1244   intermediate type, and perform widen-shift on the intermediate type:
1245
1246   type a_t;
1247   interm_type a_it;
1248   TYPE a_T, res_T, res_T';
1249
1250   S1 a_t = ;
1251   S2 a_T = (TYPE) a_t;
1252       '--> a_it = (interm_type) a_t;
1253   S3 res_T = a_T << CONST;
1254       '--> res_T' = a_it <<* CONST;
1255
1256   Input/Output:
1257
1258   * STMTS: Contains a stmt from which the pattern search begins.
1259     In case of unsigned widen-shift, the original stmt (S3) is replaced with S4
1260     in STMTS.  When an intermediate type is used and a pattern statement is
1261     created for S2, we also put S2 here (before S3).
1262
1263   Output:
1264
1265   * TYPE_IN: The type of the input arguments to the pattern.
1266
1267   * TYPE_OUT: The type of the output of this pattern.
1268
1269   * Return value: A new stmt that will be used to replace the sequence of
1270     stmts that constitute the pattern.  In this case it will be:
1271     WIDEN_LSHIFT_EXPR <a_t, CONST>.  */
1272
1273 static gimple
1274 vect_recog_widen_shift_pattern (VEC (gimple, heap) **stmts,
1275                                 tree *type_in, tree *type_out)
1276 {
1277   gimple last_stmt = VEC_pop (gimple, *stmts);
1278   gimple def_stmt0;
1279   tree oprnd0, oprnd1;
1280   tree type, half_type0;
1281   gimple pattern_stmt, orig_stmt = NULL;
1282   tree vectype, vectype_out = NULL_TREE;
1283   tree dummy;
1284   tree var;
1285   enum tree_code dummy_code;
1286   int dummy_int;
1287   VEC (tree, heap) * dummy_vec;
1288   gimple use_stmt = NULL;
1289   bool over_widen = false;
1290
1291   if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt))
1292     return NULL;
1293
1294   orig_stmt = last_stmt;
1295   if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt)))
1296     {
1297       /* This statement was also detected as over-widening operation (it can't
1298          be any other pattern, because only over-widening detects shifts).
1299          LAST_STMT is the final type demotion statement, but its related
1300          statement is shift.  We analyze the related statement to catch cases:
1301
1302          orig code:
1303           type a_t;
1304           itype res;
1305           TYPE a_T, res_T;
1306
1307           S1 a_T = (TYPE) a_t;
1308           S2 res_T = a_T << CONST;
1309           S3 res = (itype)res_T;
1310
1311           (size of type * 2 <= size of itype
1312            and size of itype * 2 <= size of TYPE)
1313
1314          code after over-widening pattern detection:
1315
1316           S1 a_T = (TYPE) a_t;
1317                --> a_it = (itype) a_t;
1318           S2 res_T = a_T << CONST;
1319           S3 res = (itype)res_T;  <--- LAST_STMT
1320                --> res = a_it << CONST;
1321
1322          after widen_shift:
1323
1324           S1 a_T = (TYPE) a_t;
1325                --> a_it = (itype) a_t; - redundant
1326           S2 res_T = a_T << CONST;
1327           S3 res = (itype)res_T;
1328                --> res = a_t w<< CONST;
1329
1330       i.e., we replace the three statements with res = a_t w<< CONST.  */
1331       last_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (last_stmt));
1332       over_widen = true;
1333     }
1334
1335   if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR)
1336     return NULL;
1337
1338   oprnd0 = gimple_assign_rhs1 (last_stmt);
1339   oprnd1 = gimple_assign_rhs2 (last_stmt);
1340   if (TREE_CODE (oprnd0) != SSA_NAME || TREE_CODE (oprnd1) != INTEGER_CST)
1341     return NULL;
1342
1343   /* Check operand 0: it has to be defined by a type promotion.  */
1344   if (!widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false))
1345     return NULL;
1346
1347   /* Check operand 1: has to be positive.  We check that it fits the type
1348      in vect_handle_widen_op_by_const ().  */
1349   if (tree_int_cst_compare (oprnd1, size_zero_node) <= 0)
1350     return NULL;
1351
1352   oprnd0 = gimple_assign_rhs1 (def_stmt0);
1353   type = gimple_expr_type (last_stmt);
1354
1355   /* Check if this a widening operation.  */
1356   if (!vect_handle_widen_op_by_const (last_stmt, LSHIFT_EXPR, oprnd1,
1357                                       &oprnd0, stmts,
1358                                       type, &half_type0, def_stmt0))
1359     return NULL;
1360
1361   /* Handle unsigned case.  Look for
1362      S4  u_res_T = (unsigned TYPE) res_T;
1363      Use unsigned TYPE as the type for WIDEN_LSHIFT_EXPR.  */
1364   if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
1365     {
1366       tree lhs = gimple_assign_lhs (last_stmt), use_lhs;
1367       imm_use_iterator imm_iter;
1368       use_operand_p use_p;
1369       int nuses = 0;
1370       tree use_type;
1371
1372       if (over_widen)
1373         {
1374           /* In case of over-widening pattern, S4 should be ORIG_STMT itself.
1375              We check here that TYPE is the correct type for the operation,
1376              i.e., it's the type of the original result.  */
1377           tree orig_type = gimple_expr_type (orig_stmt);
1378           if ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (orig_type))
1379               || (TYPE_PRECISION (type) != TYPE_PRECISION (orig_type)))
1380             return NULL;
1381         }
1382       else
1383         {
1384           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1385             {
1386               if (is_gimple_debug (USE_STMT (use_p)))
1387                 continue;
1388               use_stmt = USE_STMT (use_p);
1389               nuses++;
1390             }
1391
1392           if (nuses != 1 || !is_gimple_assign (use_stmt)
1393               || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1394             return NULL;
1395
1396           use_lhs = gimple_assign_lhs (use_stmt);
1397           use_type = TREE_TYPE (use_lhs);
1398
1399           if (!INTEGRAL_TYPE_P (use_type)
1400               || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))
1401               || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))
1402             return NULL;
1403
1404           type = use_type;
1405         }
1406     }
1407
1408   /* Pattern detected.  */
1409   if (vect_print_dump_info (REPORT_DETAILS))
1410     fprintf (vect_dump, "vect_recog_widen_shift_pattern: detected: ");
1411
1412   /* Check target support.  */
1413   vectype = get_vectype_for_scalar_type (half_type0);
1414   vectype_out = get_vectype_for_scalar_type (type);
1415
1416   if (!vectype
1417       || !vectype_out
1418       || !supportable_widening_operation (WIDEN_LSHIFT_EXPR, last_stmt,
1419                                           vectype_out, vectype,
1420                                           &dummy, &dummy, &dummy_code,
1421                                           &dummy_code, &dummy_int,
1422                                           &dummy_vec))
1423     return NULL;
1424
1425   *type_in = vectype;
1426   *type_out = vectype_out;
1427
1428   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
1429   var = vect_recog_temp_ssa_var (type, NULL);
1430   pattern_stmt =
1431     gimple_build_assign_with_ops (WIDEN_LSHIFT_EXPR, var, oprnd0, oprnd1);
1432
1433   if (vect_print_dump_info (REPORT_DETAILS))
1434     print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1435
1436   if (use_stmt)
1437     last_stmt = use_stmt;
1438   else
1439     last_stmt = orig_stmt;
1440
1441   VEC_safe_push (gimple, heap, *stmts, last_stmt);
1442   return pattern_stmt;
1443 }
1444
1445 /* Detect a vector by vector shift pattern that wouldn't be otherwise
1446    vectorized:
1447
1448    type a_t;
1449    TYPE b_T, res_T;
1450
1451    S1 a_t = ;
1452    S2 b_T = ;
1453    S3 res_T = b_T op a_t;
1454
1455   where type 'TYPE' is a type with different size than 'type',
1456   and op is <<, >> or rotate.
1457
1458   Also detect cases:
1459
1460    type a_t;
1461    TYPE b_T, c_T, res_T;
1462
1463    S0 c_T = ;
1464    S1 a_t = (type) c_T;
1465    S2 b_T = ;
1466    S3 res_T = b_T op a_t;
1467
1468   Input/Output:
1469
1470   * STMTS: Contains a stmt from which the pattern search begins,
1471     i.e. the shift/rotate stmt.  The original stmt (S3) is replaced
1472     with a shift/rotate which has same type on both operands, in the
1473     second case just b_T op c_T, in the first case with added cast
1474     from a_t to c_T in STMT_VINFO_PATTERN_DEF_STMT.
1475
1476   Output:
1477
1478   * TYPE_IN: The type of the input arguments to the pattern.
1479
1480   * TYPE_OUT: The type of the output of this pattern.
1481
1482   * Return value: A new stmt that will be used to replace the shift/rotate
1483     S3 stmt.  */
1484
1485 static gimple
1486 vect_recog_vector_vector_shift_pattern (VEC (gimple, heap) **stmts,
1487                                         tree *type_in, tree *type_out)
1488 {
1489   gimple last_stmt = VEC_pop (gimple, *stmts);
1490   tree oprnd0, oprnd1, lhs, var;
1491   gimple pattern_stmt, def_stmt;
1492   enum tree_code rhs_code;
1493   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
1494   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1495   enum vect_def_type dt;
1496   tree def;
1497
1498   if (!is_gimple_assign (last_stmt))
1499     return NULL;
1500
1501   rhs_code = gimple_assign_rhs_code (last_stmt);
1502   switch (rhs_code)
1503     {
1504     case LSHIFT_EXPR:
1505     case RSHIFT_EXPR:
1506     case LROTATE_EXPR:
1507     case RROTATE_EXPR:
1508       break;
1509     default:
1510       return NULL;
1511     }
1512
1513   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
1514     return NULL;
1515
1516   lhs = gimple_assign_lhs (last_stmt);
1517   oprnd0 = gimple_assign_rhs1 (last_stmt);
1518   oprnd1 = gimple_assign_rhs2 (last_stmt);
1519   if (TREE_CODE (oprnd0) != SSA_NAME
1520       || TREE_CODE (oprnd1) != SSA_NAME
1521       || TYPE_MODE (TREE_TYPE (oprnd0)) == TYPE_MODE (TREE_TYPE (oprnd1))
1522       || TYPE_PRECISION (TREE_TYPE (oprnd1))
1523          != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (oprnd1)))
1524       || TYPE_PRECISION (TREE_TYPE (lhs))
1525          != TYPE_PRECISION (TREE_TYPE (oprnd0)))
1526     return NULL;
1527
1528   if (!vect_is_simple_use (oprnd1, loop_vinfo, NULL, &def_stmt, &def, &dt))
1529     return NULL;
1530
1531   if (dt != vect_internal_def)
1532     return NULL;
1533
1534   *type_in = get_vectype_for_scalar_type (TREE_TYPE (oprnd0));
1535   *type_out = *type_in;
1536   if (*type_in == NULL_TREE)
1537     return NULL;
1538
1539   def = NULL_TREE;
1540   if (gimple_assign_cast_p (def_stmt))
1541     {
1542       tree rhs1 = gimple_assign_rhs1 (def_stmt);
1543       if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (TREE_TYPE (oprnd0))
1544           && TYPE_PRECISION (TREE_TYPE (rhs1))
1545              == TYPE_PRECISION (TREE_TYPE (oprnd0)))
1546         def = rhs1;
1547     }
1548
1549   if (def == NULL_TREE)
1550     {
1551       def = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
1552       def_stmt = gimple_build_assign_with_ops (NOP_EXPR, def, oprnd1,
1553                                                NULL_TREE);
1554       STMT_VINFO_PATTERN_DEF_STMT (stmt_vinfo) = def_stmt;
1555     }
1556
1557   /* Pattern detected.  */
1558   if (vect_print_dump_info (REPORT_DETAILS))
1559     fprintf (vect_dump, "vect_recog_vector_vector_shift_pattern: detected: ");
1560
1561   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
1562   var = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
1563   pattern_stmt = gimple_build_assign_with_ops (rhs_code, var, oprnd0, def);
1564
1565   if (vect_print_dump_info (REPORT_DETAILS))
1566     print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1567
1568   VEC_safe_push (gimple, heap, *stmts, last_stmt);
1569   return pattern_stmt;
1570 }
1571
1572 /* Function vect_recog_mixed_size_cond_pattern
1573
1574    Try to find the following pattern:
1575
1576      type x_t, y_t;
1577      TYPE a_T, b_T, c_T;
1578    loop:
1579      S1  a_T = x_t CMP y_t ? b_T : c_T;
1580
1581    where type 'TYPE' is an integral type which has different size
1582    from 'type'.  b_T and c_T are constants and if 'TYPE' is wider
1583    than 'type', the constants need to fit into an integer type
1584    with the same width as 'type'.
1585
1586    Input:
1587
1588    * LAST_STMT: A stmt from which the pattern search begins.
1589
1590    Output:
1591
1592    * TYPE_IN: The type of the input arguments to the pattern.
1593
1594    * TYPE_OUT: The type of the output of this pattern.
1595
1596    * Return value: A new stmt that will be used to replace the pattern.
1597         Additionally a def_stmt is added.
1598
1599         a_it = x_t CMP y_t ? b_it : c_it;
1600         a_T = (TYPE) a_it;  */
1601
1602 static gimple
1603 vect_recog_mixed_size_cond_pattern (VEC (gimple, heap) **stmts, tree *type_in,
1604                                     tree *type_out)
1605 {
1606   gimple last_stmt = VEC_index (gimple, *stmts, 0);
1607   tree cond_expr, then_clause, else_clause;
1608   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt), def_stmt_info;
1609   tree type, vectype, comp_vectype, itype, vecitype;
1610   enum machine_mode cmpmode;
1611   gimple pattern_stmt, def_stmt;
1612   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1613
1614   if (!is_gimple_assign (last_stmt)
1615       || gimple_assign_rhs_code (last_stmt) != COND_EXPR
1616       || STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
1617     return NULL;
1618
1619   cond_expr = gimple_assign_rhs1 (last_stmt);
1620   then_clause = gimple_assign_rhs2 (last_stmt);
1621   else_clause = gimple_assign_rhs3 (last_stmt);
1622
1623   if (TREE_CODE (then_clause) != INTEGER_CST
1624       || TREE_CODE (else_clause) != INTEGER_CST)
1625     return NULL;
1626
1627   if (!COMPARISON_CLASS_P (cond_expr))
1628     return NULL;
1629
1630   comp_vectype
1631     = get_vectype_for_scalar_type (TREE_TYPE (TREE_OPERAND (cond_expr, 0)));
1632   if (comp_vectype == NULL_TREE)
1633     return NULL;
1634
1635   type = gimple_expr_type (last_stmt);
1636   cmpmode = GET_MODE_INNER (TYPE_MODE (comp_vectype));
1637
1638   if (GET_MODE_BITSIZE (TYPE_MODE (type)) == GET_MODE_BITSIZE (cmpmode))
1639     return NULL;
1640
1641   vectype = get_vectype_for_scalar_type (type);
1642   if (vectype == NULL_TREE)
1643     return NULL;
1644
1645   if (expand_vec_cond_expr_p (vectype, comp_vectype))
1646     return NULL;
1647
1648   itype = build_nonstandard_integer_type (GET_MODE_BITSIZE (cmpmode),
1649                                           TYPE_UNSIGNED (type));
1650   if (itype == NULL_TREE
1651       || GET_MODE_BITSIZE (TYPE_MODE (itype)) != GET_MODE_BITSIZE (cmpmode))
1652     return NULL;
1653
1654   vecitype = get_vectype_for_scalar_type (itype);
1655   if (vecitype == NULL_TREE)
1656     return NULL;
1657
1658   if (!expand_vec_cond_expr_p (vecitype, comp_vectype))
1659     return NULL;
1660
1661   if (GET_MODE_BITSIZE (TYPE_MODE (type)) > GET_MODE_BITSIZE (cmpmode))
1662     {
1663       if (!int_fits_type_p (then_clause, itype)
1664           || !int_fits_type_p (else_clause, itype))
1665         return NULL;
1666     }
1667
1668   def_stmt
1669     = gimple_build_assign_with_ops3 (COND_EXPR,
1670                                      vect_recog_temp_ssa_var (itype, NULL),
1671                                      unshare_expr (cond_expr),
1672                                      fold_convert (itype, then_clause),
1673                                      fold_convert (itype, else_clause));
1674   pattern_stmt
1675     = gimple_build_assign_with_ops (NOP_EXPR,
1676                                     vect_recog_temp_ssa_var (type, NULL),
1677                                     gimple_assign_lhs (def_stmt), NULL_TREE);
1678
1679   STMT_VINFO_PATTERN_DEF_STMT (stmt_vinfo) = def_stmt;
1680   def_stmt_info = new_stmt_vec_info (def_stmt, loop_vinfo, NULL);
1681   set_vinfo_for_stmt (def_stmt, def_stmt_info);
1682   STMT_VINFO_VECTYPE (def_stmt_info) = vecitype;
1683   *type_in = vecitype;
1684   *type_out = vectype;
1685
1686   return pattern_stmt;
1687 }
1688
1689
1690 /* Helper function of vect_recog_bool_pattern.  Called recursively, return
1691    true if bool VAR can be optimized that way.  */
1692
1693 static bool
1694 check_bool_pattern (tree var, loop_vec_info loop_vinfo)
1695 {
1696   gimple def_stmt;
1697   enum vect_def_type dt;
1698   tree def, rhs1;
1699   enum tree_code rhs_code;
1700
1701   if (!vect_is_simple_use (var, loop_vinfo, NULL, &def_stmt, &def, &dt))
1702     return false;
1703
1704   if (dt != vect_internal_def)
1705     return false;
1706
1707   if (!is_gimple_assign (def_stmt))
1708     return false;
1709
1710   if (!has_single_use (def))
1711     return false;
1712
1713   rhs1 = gimple_assign_rhs1 (def_stmt);
1714   rhs_code = gimple_assign_rhs_code (def_stmt);
1715   switch (rhs_code)
1716     {
1717     case SSA_NAME:
1718       return check_bool_pattern (rhs1, loop_vinfo);
1719
1720     CASE_CONVERT:
1721       if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
1722            || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
1723           && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
1724         return false;
1725       return check_bool_pattern (rhs1, loop_vinfo);
1726
1727     case BIT_NOT_EXPR:
1728       return check_bool_pattern (rhs1, loop_vinfo);
1729
1730     case BIT_AND_EXPR:
1731     case BIT_IOR_EXPR:
1732     case BIT_XOR_EXPR:
1733       if (!check_bool_pattern (rhs1, loop_vinfo))
1734         return false;
1735       return check_bool_pattern (gimple_assign_rhs2 (def_stmt), loop_vinfo);
1736
1737     default:
1738       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
1739         {
1740           tree vecitype, comp_vectype;
1741
1742           comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
1743           if (comp_vectype == NULL_TREE)
1744             return false;
1745
1746           if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE)
1747             {
1748               enum machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
1749               tree itype
1750                 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
1751               vecitype = get_vectype_for_scalar_type (itype);
1752               if (vecitype == NULL_TREE)
1753                 return false;
1754             }
1755           else
1756             vecitype = comp_vectype;
1757           return expand_vec_cond_expr_p (vecitype, comp_vectype);
1758         }
1759       return false;
1760     }
1761 }
1762
1763
1764 /* Helper function of adjust_bool_pattern.  Add a cast to TYPE to a previous
1765    stmt (SSA_NAME_DEF_STMT of VAR) by moving the COND_EXPR from RELATED_STMT
1766    to PATTERN_DEF_STMT and adding a cast as RELATED_STMT.  */
1767
1768 static tree
1769 adjust_bool_pattern_cast (tree type, tree var)
1770 {
1771   stmt_vec_info stmt_vinfo = vinfo_for_stmt (SSA_NAME_DEF_STMT (var));
1772   gimple cast_stmt, pattern_stmt;
1773
1774   gcc_assert (!STMT_VINFO_PATTERN_DEF_STMT (stmt_vinfo));
1775   pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
1776   STMT_VINFO_PATTERN_DEF_STMT (stmt_vinfo) = pattern_stmt;
1777   cast_stmt
1778     = gimple_build_assign_with_ops (NOP_EXPR,
1779                                     vect_recog_temp_ssa_var (type, NULL),
1780                                     gimple_assign_lhs (pattern_stmt),
1781                                     NULL_TREE);
1782   STMT_VINFO_RELATED_STMT (stmt_vinfo) = cast_stmt;
1783   return gimple_assign_lhs (cast_stmt);
1784 }
1785
1786
1787 /* Helper function of vect_recog_bool_pattern.  Do the actual transformations,
1788    recursively.  VAR is an SSA_NAME that should be transformed from bool
1789    to a wider integer type, OUT_TYPE is the desired final integer type of
1790    the whole pattern, TRUEVAL should be NULL unless optimizing
1791    BIT_AND_EXPR into a COND_EXPR with one integer from one of the operands
1792    in the then_clause, STMTS is where statements with added pattern stmts
1793    should be pushed to.  */
1794
1795 static tree
1796 adjust_bool_pattern (tree var, tree out_type, tree trueval,
1797                      VEC (gimple, heap) **stmts)
1798 {
1799   gimple stmt = SSA_NAME_DEF_STMT (var);
1800   enum tree_code rhs_code, def_rhs_code;
1801   tree itype, cond_expr, rhs1, rhs2, irhs1, irhs2;
1802   location_t loc;
1803   gimple pattern_stmt, def_stmt;
1804
1805   rhs1 = gimple_assign_rhs1 (stmt);
1806   rhs2 = gimple_assign_rhs2 (stmt);
1807   rhs_code = gimple_assign_rhs_code (stmt);
1808   loc = gimple_location (stmt);
1809   switch (rhs_code)
1810     {
1811     case SSA_NAME:
1812     CASE_CONVERT:
1813       irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
1814       itype = TREE_TYPE (irhs1);
1815       pattern_stmt
1816         = gimple_build_assign_with_ops (SSA_NAME,
1817                                         vect_recog_temp_ssa_var (itype, NULL),
1818                                         irhs1, NULL_TREE);
1819       break;
1820
1821     case BIT_NOT_EXPR:
1822       irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
1823       itype = TREE_TYPE (irhs1);
1824       pattern_stmt
1825         = gimple_build_assign_with_ops (BIT_XOR_EXPR,
1826                                         vect_recog_temp_ssa_var (itype, NULL),
1827                                         irhs1, build_int_cst (itype, 1));
1828       break;
1829
1830     case BIT_AND_EXPR:
1831       /* Try to optimize x = y & (a < b ? 1 : 0); into
1832          x = (a < b ? y : 0);
1833
1834          E.g. for:
1835            bool a_b, b_b, c_b;
1836            TYPE d_T;
1837
1838            S1  a_b = x1 CMP1 y1;
1839            S2  b_b = x2 CMP2 y2;
1840            S3  c_b = a_b & b_b;
1841            S4  d_T = (TYPE) c_b;
1842
1843          we would normally emit:
1844
1845            S1'  a_T = x1 CMP1 y1 ? 1 : 0;
1846            S2'  b_T = x2 CMP2 y2 ? 1 : 0;
1847            S3'  c_T = a_T & b_T;
1848            S4'  d_T = c_T;
1849
1850          but we can save one stmt by using the
1851          result of one of the COND_EXPRs in the other COND_EXPR and leave
1852          BIT_AND_EXPR stmt out:
1853
1854            S1'  a_T = x1 CMP1 y1 ? 1 : 0;
1855            S3'  c_T = x2 CMP2 y2 ? a_T : 0;
1856            S4'  f_T = c_T;
1857
1858          At least when VEC_COND_EXPR is implemented using masks
1859          cond ? 1 : 0 is as expensive as cond ? var : 0, in both cases it
1860          computes the comparison masks and ands it, in one case with
1861          all ones vector, in the other case with a vector register.
1862          Don't do this for BIT_IOR_EXPR, because cond ? 1 : var; is
1863          often more expensive.  */
1864       def_stmt = SSA_NAME_DEF_STMT (rhs2);
1865       def_rhs_code = gimple_assign_rhs_code (def_stmt);
1866       if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
1867         {
1868           tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1869           irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
1870           if (TYPE_PRECISION (TREE_TYPE (irhs1))
1871               == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1))))
1872             {
1873               gimple tstmt;
1874               stmt_vec_info stmt_def_vinfo = vinfo_for_stmt (def_stmt);
1875               irhs2 = adjust_bool_pattern (rhs2, out_type, irhs1, stmts);
1876               tstmt = VEC_pop (gimple, *stmts);
1877               gcc_assert (tstmt == def_stmt);
1878               VEC_quick_push (gimple, *stmts, stmt);
1879               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt))
1880                 = STMT_VINFO_RELATED_STMT (stmt_def_vinfo);
1881               gcc_assert (!STMT_VINFO_PATTERN_DEF_STMT (stmt_def_vinfo));
1882               STMT_VINFO_RELATED_STMT (stmt_def_vinfo) = NULL;
1883               return irhs2;
1884             }
1885           else
1886             irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
1887           goto and_ior_xor;
1888         }
1889       def_stmt = SSA_NAME_DEF_STMT (rhs1);
1890       def_rhs_code = gimple_assign_rhs_code (def_stmt);
1891       if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
1892         {
1893           tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
1894           irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
1895           if (TYPE_PRECISION (TREE_TYPE (irhs2))
1896               == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1))))
1897             {
1898               gimple tstmt;
1899               stmt_vec_info stmt_def_vinfo = vinfo_for_stmt (def_stmt);
1900               irhs1 = adjust_bool_pattern (rhs1, out_type, irhs2, stmts);
1901               tstmt = VEC_pop (gimple, *stmts);
1902               gcc_assert (tstmt == def_stmt);
1903               VEC_quick_push (gimple, *stmts, stmt);
1904               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt))
1905                 = STMT_VINFO_RELATED_STMT (stmt_def_vinfo);
1906               gcc_assert (!STMT_VINFO_PATTERN_DEF_STMT (stmt_def_vinfo));
1907               STMT_VINFO_RELATED_STMT (stmt_def_vinfo) = NULL;
1908               return irhs1;
1909             }
1910           else
1911             irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
1912           goto and_ior_xor;
1913         }
1914       /* FALLTHRU */
1915     case BIT_IOR_EXPR:
1916     case BIT_XOR_EXPR:
1917       irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
1918       irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
1919     and_ior_xor:
1920       if (TYPE_PRECISION (TREE_TYPE (irhs1))
1921           != TYPE_PRECISION (TREE_TYPE (irhs2)))
1922         {
1923           int prec1 = TYPE_PRECISION (TREE_TYPE (irhs1));
1924           int prec2 = TYPE_PRECISION (TREE_TYPE (irhs2));
1925           int out_prec = TYPE_PRECISION (out_type);
1926           if (absu_hwi (out_prec - prec1) < absu_hwi (out_prec - prec2))
1927             irhs2 = adjust_bool_pattern_cast (TREE_TYPE (irhs1), rhs2);
1928           else if (absu_hwi (out_prec - prec1) > absu_hwi (out_prec - prec2))
1929             irhs1 = adjust_bool_pattern_cast (TREE_TYPE (irhs2), rhs1);
1930           else
1931             {
1932               irhs1 = adjust_bool_pattern_cast (out_type, rhs1);
1933               irhs2 = adjust_bool_pattern_cast (out_type, rhs2);
1934             }
1935         }
1936       itype = TREE_TYPE (irhs1);
1937       pattern_stmt
1938         = gimple_build_assign_with_ops (rhs_code,
1939                                         vect_recog_temp_ssa_var (itype, NULL),
1940                                         irhs1, irhs2);
1941       break;
1942
1943     default:
1944       gcc_assert (TREE_CODE_CLASS (rhs_code) == tcc_comparison);
1945       if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
1946           || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
1947         {
1948           enum machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
1949           itype
1950             = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
1951         }
1952       else
1953         itype = TREE_TYPE (rhs1);
1954       cond_expr = build2_loc (loc, rhs_code, itype, rhs1, rhs2);
1955       if (trueval == NULL_TREE)
1956         trueval = build_int_cst (itype, 1);
1957       else
1958         gcc_checking_assert (useless_type_conversion_p (itype,
1959                                                         TREE_TYPE (trueval)));
1960       pattern_stmt
1961         = gimple_build_assign_with_ops3 (COND_EXPR,
1962                                          vect_recog_temp_ssa_var (itype, NULL),
1963                                          cond_expr, trueval,
1964                                          build_int_cst (itype, 0));
1965       break;
1966     }
1967
1968   VEC_safe_push (gimple, heap, *stmts, stmt);
1969   gimple_set_location (pattern_stmt, loc);
1970   STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
1971   return gimple_assign_lhs (pattern_stmt);
1972 }
1973
1974
1975 /* Function vect_recog_bool_pattern
1976
1977    Try to find pattern like following:
1978
1979      bool a_b, b_b, c_b, d_b, e_b;
1980      TYPE f_T;
1981    loop:
1982      S1  a_b = x1 CMP1 y1;
1983      S2  b_b = x2 CMP2 y2;
1984      S3  c_b = a_b & b_b;
1985      S4  d_b = x3 CMP3 y3;
1986      S5  e_b = c_b | d_b;
1987      S6  f_T = (TYPE) e_b;
1988
1989    where type 'TYPE' is an integral type.
1990
1991    Input:
1992
1993    * LAST_STMT: A stmt at the end from which the pattern
1994                 search begins, i.e. cast of a bool to
1995                 an integer type.
1996
1997    Output:
1998
1999    * TYPE_IN: The type of the input arguments to the pattern.
2000
2001    * TYPE_OUT: The type of the output of this pattern.
2002
2003    * Return value: A new stmt that will be used to replace the pattern.
2004
2005         Assuming size of TYPE is the same as size of all comparisons
2006         (otherwise some casts would be added where needed), the above
2007         sequence we create related pattern stmts:
2008         S1'  a_T = x1 CMP1 y1 ? 1 : 0;
2009         S3'  c_T = x2 CMP2 y2 ? a_T : 0;
2010         S4'  d_T = x3 CMP3 y3 ? 1 : 0;
2011         S5'  e_T = c_T | d_T;
2012         S6'  f_T = e_T;
2013
2014         Instead of the above S3' we could emit:
2015         S2'  b_T = x2 CMP2 y2 ? 1 : 0;
2016         S3'  c_T = a_T | b_T;
2017         but the above is more efficient.  */
2018
2019 static gimple
2020 vect_recog_bool_pattern (VEC (gimple, heap) **stmts, tree *type_in,
2021                          tree *type_out)
2022 {
2023   gimple last_stmt = VEC_pop (gimple, *stmts);
2024   enum tree_code rhs_code;
2025   tree var, lhs, rhs, vectype;
2026   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
2027   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2028   gimple pattern_stmt;
2029
2030   if (!is_gimple_assign (last_stmt))
2031     return NULL;
2032
2033   var = gimple_assign_rhs1 (last_stmt);
2034   lhs = gimple_assign_lhs (last_stmt);
2035
2036   if ((TYPE_PRECISION (TREE_TYPE (var)) != 1
2037        || !TYPE_UNSIGNED (TREE_TYPE (var)))
2038       && TREE_CODE (TREE_TYPE (var)) != BOOLEAN_TYPE)
2039     return NULL;
2040
2041   rhs_code = gimple_assign_rhs_code (last_stmt);
2042   if (CONVERT_EXPR_CODE_P (rhs_code))
2043     {
2044       if (TREE_CODE (TREE_TYPE (lhs)) != INTEGER_TYPE)
2045         return NULL;
2046       vectype = get_vectype_for_scalar_type (TREE_TYPE (lhs));
2047       if (vectype == NULL_TREE)
2048         return NULL;
2049
2050       if (!check_bool_pattern (var, loop_vinfo))
2051         return NULL;
2052
2053       rhs = adjust_bool_pattern (var, TREE_TYPE (lhs), NULL_TREE, stmts);
2054       lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
2055       if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2056         pattern_stmt
2057           = gimple_build_assign_with_ops (SSA_NAME, lhs, rhs, NULL_TREE);
2058       else
2059         pattern_stmt
2060           = gimple_build_assign_with_ops (NOP_EXPR, lhs, rhs, NULL_TREE);
2061       *type_out = vectype;
2062       *type_in = vectype;
2063       VEC_safe_push (gimple, heap, *stmts, last_stmt);
2064       return pattern_stmt;
2065     }
2066   else if (rhs_code == SSA_NAME
2067            && STMT_VINFO_DATA_REF (stmt_vinfo))
2068     {
2069       stmt_vec_info pattern_stmt_info;
2070       vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
2071       gcc_assert (vectype != NULL_TREE);
2072       if (!check_bool_pattern (var, loop_vinfo))
2073         return NULL;
2074
2075       rhs = adjust_bool_pattern (var, TREE_TYPE (vectype), NULL_TREE, stmts);
2076       lhs = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vectype), lhs);
2077       if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2078         {
2079           tree rhs2 = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
2080           gimple cast_stmt
2081             = gimple_build_assign_with_ops (NOP_EXPR, rhs2, rhs, NULL_TREE);
2082           STMT_VINFO_PATTERN_DEF_STMT (stmt_vinfo) = cast_stmt;
2083           rhs = rhs2;
2084         }
2085       pattern_stmt
2086         = gimple_build_assign_with_ops (SSA_NAME, lhs, rhs, NULL_TREE);
2087       pattern_stmt_info = new_stmt_vec_info (pattern_stmt, loop_vinfo, NULL);
2088       set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
2089       STMT_VINFO_DATA_REF (pattern_stmt_info)
2090         = STMT_VINFO_DATA_REF (stmt_vinfo);
2091       STMT_VINFO_DR_BASE_ADDRESS (pattern_stmt_info)
2092         = STMT_VINFO_DR_BASE_ADDRESS (stmt_vinfo);
2093       STMT_VINFO_DR_INIT (pattern_stmt_info) = STMT_VINFO_DR_INIT (stmt_vinfo);
2094       STMT_VINFO_DR_OFFSET (pattern_stmt_info)
2095         = STMT_VINFO_DR_OFFSET (stmt_vinfo);
2096       STMT_VINFO_DR_STEP (pattern_stmt_info) = STMT_VINFO_DR_STEP (stmt_vinfo);
2097       STMT_VINFO_DR_ALIGNED_TO (pattern_stmt_info)
2098         = STMT_VINFO_DR_ALIGNED_TO (stmt_vinfo);
2099       *type_out = vectype;
2100       *type_in = vectype;
2101       VEC_safe_push (gimple, heap, *stmts, last_stmt);
2102       return pattern_stmt;
2103     }
2104   else
2105     return NULL;
2106 }
2107
2108
2109 /* Mark statements that are involved in a pattern.  */
2110
2111 static inline void
2112 vect_mark_pattern_stmts (gimple orig_stmt, gimple pattern_stmt,
2113                          tree pattern_vectype)
2114 {
2115   stmt_vec_info pattern_stmt_info, def_stmt_info;
2116   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
2117   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (orig_stmt_info);
2118   gimple def_stmt;
2119
2120   pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
2121   if (pattern_stmt_info == NULL)
2122     {
2123       pattern_stmt_info = new_stmt_vec_info (pattern_stmt, loop_vinfo, NULL);
2124       set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
2125     }
2126   gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt));
2127
2128   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt;
2129   STMT_VINFO_DEF_TYPE (pattern_stmt_info)
2130     = STMT_VINFO_DEF_TYPE (orig_stmt_info);
2131   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
2132   STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true;
2133   STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt;
2134   STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info)
2135     = STMT_VINFO_PATTERN_DEF_STMT (orig_stmt_info);
2136   if (STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info))
2137     {
2138       def_stmt = STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info);
2139       def_stmt_info = vinfo_for_stmt (def_stmt);
2140       if (def_stmt_info == NULL)
2141         {
2142           def_stmt_info = new_stmt_vec_info (def_stmt, loop_vinfo, NULL);
2143           set_vinfo_for_stmt (def_stmt, def_stmt_info);
2144         }
2145       gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
2146       STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt;
2147       STMT_VINFO_DEF_TYPE (def_stmt_info)
2148         = STMT_VINFO_DEF_TYPE (orig_stmt_info);
2149       if (STMT_VINFO_VECTYPE (def_stmt_info) == NULL_TREE)
2150         STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype;
2151     }
2152 }
2153
2154 /* Function vect_pattern_recog_1
2155
2156    Input:
2157    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
2158         computation pattern.
2159    STMT: A stmt from which the pattern search should start.
2160
2161    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
2162    expression that computes the same functionality and can be used to
2163    replace the sequence of stmts that are involved in the pattern.
2164
2165    Output:
2166    This function checks if the expression returned by PATTERN_RECOG_FUNC is
2167    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
2168    relevant vector type. If 'TYPE_IN' is already a vector type, then this
2169    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
2170    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
2171    to the available target pattern.
2172
2173    This function also does some bookkeeping, as explained in the documentation
2174    for vect_recog_pattern.  */
2175
2176 static void
2177 vect_pattern_recog_1 (vect_recog_func_ptr vect_recog_func,
2178                       gimple_stmt_iterator si,
2179                       VEC (gimple, heap) **stmts_to_replace)
2180 {
2181   gimple stmt = gsi_stmt (si), pattern_stmt;
2182   stmt_vec_info stmt_info;
2183   loop_vec_info loop_vinfo;
2184   tree pattern_vectype;
2185   tree type_in, type_out;
2186   enum tree_code code;
2187   int i;
2188   gimple next;
2189
2190   VEC_truncate (gimple, *stmts_to_replace, 0);
2191   VEC_quick_push (gimple, *stmts_to_replace, stmt);
2192   pattern_stmt = (* vect_recog_func) (stmts_to_replace, &type_in, &type_out);
2193   if (!pattern_stmt)
2194     return;
2195
2196   stmt = VEC_last (gimple, *stmts_to_replace);
2197   stmt_info = vinfo_for_stmt (stmt);
2198   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2199
2200   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
2201     {
2202       /* No need to check target support (already checked by the pattern
2203          recognition function).  */
2204       pattern_vectype = type_out ? type_out : type_in;
2205     }
2206   else
2207     {
2208       enum machine_mode vec_mode;
2209       enum insn_code icode;
2210       optab optab;
2211
2212       /* Check target support  */
2213       type_in = get_vectype_for_scalar_type (type_in);
2214       if (!type_in)
2215         return;
2216       if (type_out)
2217         type_out = get_vectype_for_scalar_type (type_out);
2218       else
2219         type_out = type_in;
2220       if (!type_out)
2221         return;
2222       pattern_vectype = type_out;
2223
2224       if (is_gimple_assign (pattern_stmt))
2225         code = gimple_assign_rhs_code (pattern_stmt);
2226       else
2227         {
2228           gcc_assert (is_gimple_call (pattern_stmt));
2229           code = CALL_EXPR;
2230         }
2231
2232       optab = optab_for_tree_code (code, type_in, optab_default);
2233       vec_mode = TYPE_MODE (type_in);
2234       if (!optab
2235           || (icode = optab_handler (optab, vec_mode)) == CODE_FOR_nothing
2236           || (insn_data[icode].operand[0].mode != TYPE_MODE (type_out)))
2237         return;
2238     }
2239
2240   /* Found a vectorizable pattern.  */
2241   if (vect_print_dump_info (REPORT_DETAILS))
2242     {
2243       fprintf (vect_dump, "pattern recognized: ");
2244       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
2245     }
2246
2247   /* Mark the stmts that are involved in the pattern. */
2248   vect_mark_pattern_stmts (stmt, pattern_stmt, pattern_vectype);
2249
2250   /* Patterns cannot be vectorized using SLP, because they change the order of
2251      computation.  */
2252   FOR_EACH_VEC_ELT (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
2253     if (next == stmt)
2254       VEC_ordered_remove (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i);
2255
2256   /* It is possible that additional pattern stmts are created and inserted in
2257      STMTS_TO_REPLACE.  We create a stmt_info for each of them, and mark the
2258      relevant statements.  */
2259   for (i = 0; VEC_iterate (gimple, *stmts_to_replace, i, stmt)
2260               && (unsigned) i < (VEC_length (gimple, *stmts_to_replace) - 1);
2261        i++)
2262     {
2263       stmt_info = vinfo_for_stmt (stmt);
2264       pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
2265       if (vect_print_dump_info (REPORT_DETAILS))
2266         {
2267           fprintf (vect_dump, "additional pattern stmt: ");
2268           print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
2269         }
2270
2271       vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE);
2272     }
2273 }
2274
2275
2276 /* Function vect_pattern_recog
2277
2278    Input:
2279    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
2280         computation idioms.
2281
2282    Output - for each computation idiom that is detected we create a new stmt
2283         that provides the same functionality and that can be vectorized.  We
2284         also record some information in the struct_stmt_info of the relevant
2285         stmts, as explained below:
2286
2287    At the entry to this function we have the following stmts, with the
2288    following initial value in the STMT_VINFO fields:
2289
2290          stmt                     in_pattern_p  related_stmt    vec_stmt
2291          S1: a_i = ....                 -       -               -
2292          S2: a_2 = ..use(a_i)..         -       -               -
2293          S3: a_1 = ..use(a_2)..         -       -               -
2294          S4: a_0 = ..use(a_1)..         -       -               -
2295          S5: ... = ..use(a_0)..         -       -               -
2296
2297    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
2298    represented by a single stmt.  We then:
2299    - create a new stmt S6 equivalent to the pattern (the stmt is not
2300      inserted into the code)
2301    - fill in the STMT_VINFO fields as follows:
2302
2303                                   in_pattern_p  related_stmt    vec_stmt
2304          S1: a_i = ....                 -       -               -
2305          S2: a_2 = ..use(a_i)..         -       -               -
2306          S3: a_1 = ..use(a_2)..         -       -               -
2307          S4: a_0 = ..use(a_1)..         true    S6              -
2308           '---> S6: a_new = ....        -       S4              -
2309          S5: ... = ..use(a_0)..         -       -               -
2310
2311    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
2312    to each other through the RELATED_STMT field).
2313
2314    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
2315    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
2316    remain irrelevant unless used by stmts other than S4.
2317
2318    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
2319    (because they are marked as irrelevant).  It will vectorize S6, and record
2320    a pointer to the new vector stmt VS6 from S6 (as usual).
2321    S4 will be skipped, and S5 will be vectorized as usual:
2322
2323                                   in_pattern_p  related_stmt    vec_stmt
2324          S1: a_i = ....                 -       -               -
2325          S2: a_2 = ..use(a_i)..         -       -               -
2326          S3: a_1 = ..use(a_2)..         -       -               -
2327        > VS6: va_new = ....             -       -               -
2328          S4: a_0 = ..use(a_1)..         true    S6              VS6
2329           '---> S6: a_new = ....        -       S4              VS6
2330        > VS5: ... = ..vuse(va_new)..    -       -               -
2331          S5: ... = ..use(a_0)..         -       -               -
2332
2333    DCE could then get rid of {S1,S2,S3,S4,S5} (if their defs are not used
2334    elsewhere), and we'll end up with:
2335
2336         VS6: va_new = ....
2337         VS5: ... = ..vuse(va_new)..
2338
2339    In case of more than one pattern statements, e.g., widen-mult with
2340    intermediate type:
2341
2342      S1  a_t = ;
2343      S2  a_T = (TYPE) a_t;
2344            '--> S3: a_it = (interm_type) a_t;
2345      S4  prod_T = a_T * CONST;
2346            '--> S5: prod_T' = a_it w* CONST;
2347
2348    there may be other users of a_T outside the pattern.  In that case S2 will
2349    be marked as relevant (as well as S3), and both S2 and S3 will be analyzed
2350    and vectorized.  The vector stmt VS2 will be recorded in S2, and VS3 will
2351    be recorded in S3.  */
2352
2353 void
2354 vect_pattern_recog (loop_vec_info loop_vinfo)
2355 {
2356   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2357   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2358   unsigned int nbbs = loop->num_nodes;
2359   gimple_stmt_iterator si;
2360   unsigned int i, j;
2361   vect_recog_func_ptr vect_recog_func;
2362   VEC (gimple, heap) *stmts_to_replace = VEC_alloc (gimple, heap, 1);
2363
2364   if (vect_print_dump_info (REPORT_DETAILS))
2365     fprintf (vect_dump, "=== vect_pattern_recog ===");
2366
2367   /* Scan through the loop stmts, applying the pattern recognition
2368      functions starting at each stmt visited:  */
2369   for (i = 0; i < nbbs; i++)
2370     {
2371       basic_block bb = bbs[i];
2372       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2373         {
2374           /* Scan over all generic vect_recog_xxx_pattern functions.  */
2375           for (j = 0; j < NUM_PATTERNS; j++)
2376             {
2377               vect_recog_func = vect_vect_recog_func_ptrs[j];
2378               vect_pattern_recog_1 (vect_recog_func, si,
2379                                     &stmts_to_replace);
2380             }
2381         }
2382     }
2383
2384   VEC_free (gimple, heap, stmts_to_replace);
2385 }