gcc/tree-vect-patterns.c

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