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