gcc/tree-vect-patterns.c

   1 /* Analysis Utilities for Loop Vectorization.
   2    Copyright (C) 2006-2016 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 "backend.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "ssa.h"
  29 #include "expmed.h"
  30 #include "optabs-tree.h"
  31 #include "insn-config.h"
  32 #include "recog.h"              /* FIXME: for insn_data */
  33 #include "fold-const.h"
  34 #include "stor-layout.h"
  35 #include "tree-eh.h"
  36 #include "gimplify.h"
  37 #include "gimple-iterator.h"
  38 #include "cfgloop.h"
  39 #include "tree-vectorizer.h"
  40 #include "dumpfile.h"
  41 #include "builtins.h"
  42 #include "internal-fn.h"
  43 #include "case-cfn-macros.h"
  44
  45 /* Pattern recognition functions  */
  46 static gimple *vect_recog_widen_sum_pattern (vec<gimple *> *, tree *,
  47                                             tree *);
  48 static gimple *vect_recog_widen_mult_pattern (vec<gimple *> *, tree *,
  49                                              tree *);
  50 static gimple *vect_recog_dot_prod_pattern (vec<gimple *> *, tree *,
  51                                            tree *);
  52 static gimple *vect_recog_sad_pattern (vec<gimple *> *, tree *,
  53                                       tree *);
  54 static gimple *vect_recog_pow_pattern (vec<gimple *> *, tree *, tree *);
  55 static gimple *vect_recog_over_widening_pattern (vec<gimple *> *, tree *,
  56                                                  tree *);
  57 static gimple *vect_recog_widen_shift_pattern (vec<gimple *> *,
  58                                         tree *, tree *);
  59 static gimple *vect_recog_rotate_pattern (vec<gimple *> *, tree *, tree *);
  60 static gimple *vect_recog_vector_vector_shift_pattern (vec<gimple *> *,
  61                                                       tree *, tree *);
  62 static gimple *vect_recog_divmod_pattern (vec<gimple *> *,
  63                                          tree *, tree *);
  64
  65 static gimple *vect_recog_mult_pattern (vec<gimple *> *,
  66                                        tree *, tree *);
  67
  68 static gimple *vect_recog_mixed_size_cond_pattern (vec<gimple *> *,
  69                                                   tree *, tree *);
  70 static gimple *vect_recog_bool_pattern (vec<gimple *> *, tree *, tree *);
  71 static gimple *vect_recog_mask_conversion_pattern (vec<gimple *> *, tree *, tree *);
  72
  73 struct vect_recog_func
  74 {
  75   vect_recog_func_ptr fn;
  76   const char *name;
  77 };
  78
  79 /* Note that ordering matters - the first pattern matching on a stmt
  80    is taken which means usually the more complex one needs to preceed
  81    the less comples onex (widen_sum only after dot_prod or sad for example).  */
  82 static vect_recog_func vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
  83       { vect_recog_widen_mult_pattern, "widen_mult" },
  84       { vect_recog_dot_prod_pattern, "dot_prod" },
  85       { vect_recog_sad_pattern, "sad" },
  86       { vect_recog_widen_sum_pattern, "widen_sum" },
  87       { vect_recog_pow_pattern, "pow" },
  88       { vect_recog_widen_shift_pattern, "widen_shift" },
  89       { vect_recog_over_widening_pattern, "over_widening" },
  90       { vect_recog_rotate_pattern, "rotate" },
  91       { vect_recog_vector_vector_shift_pattern, "vector_vector_shift" },
  92       { vect_recog_divmod_pattern, "divmod" },
  93       { vect_recog_mult_pattern, "mult" },
  94       { vect_recog_mixed_size_cond_pattern, "mixed_size_cond" },
  95       { vect_recog_bool_pattern, "bool" },
  96       { vect_recog_mask_conversion_pattern, "mask_conversion" }
  97 };
  98
  99 static inline void
 100 append_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt)
 101 {
 102   gimple_seq_add_stmt_without_update (&STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
 103                                       stmt);
 104 }
 105
 106 static inline void
 107 new_pattern_def_seq (stmt_vec_info stmt_info, gimple *stmt)
 108 {
 109   STMT_VINFO_PATTERN_DEF_SEQ (stmt_info) = NULL;
 110   append_pattern_def_seq (stmt_info, stmt);
 111 }
 112
 113 /* Check whether STMT2 is in the same loop or basic block as STMT1.
 114    Which of the two applies depends on whether we're currently doing
 115    loop-based or basic-block-based vectorization, as determined by
 116    the vinfo_for_stmt for STMT1 (which must be defined).
 117
 118    If this returns true, vinfo_for_stmt for STMT2 is guaranteed
 119    to be defined as well.  */
 120
 121 static bool
 122 vect_same_loop_or_bb_p (gimple *stmt1, gimple *stmt2)
 123 {
 124   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt1);
 125   return vect_stmt_in_region_p (stmt_vinfo->vinfo, stmt2);
 126 }
 127
 128 /* If the LHS of DEF_STMT has a single use, and that statement is
 129    in the same loop or basic block, return it.  */
 130
 131 static gimple *
 132 vect_single_imm_use (gimple *def_stmt)
 133 {
 134   tree lhs = gimple_assign_lhs (def_stmt);
 135   use_operand_p use_p;
 136   gimple *use_stmt;
 137
 138   if (!single_imm_use (lhs, &use_p, &use_stmt))
 139     return NULL;
 140
 141   if (!vect_same_loop_or_bb_p (def_stmt, use_stmt))
 142     return NULL;
 143
 144   return use_stmt;
 145 }
 146
 147 /* Check whether NAME, an ssa-name used in USE_STMT,
 148    is a result of a type promotion, such that:
 149      DEF_STMT: NAME = NOP (name0)
 150    If CHECK_SIGN is TRUE, check that either both types are signed or both are
 151    unsigned.  */
 152
 153 static bool
 154 type_conversion_p (tree name, gimple *use_stmt, bool check_sign,
 155                    tree *orig_type, gimple **def_stmt, bool *promotion)
 156 {
 157   gimple *dummy_gimple;
 158   stmt_vec_info stmt_vinfo;
 159   tree type = TREE_TYPE (name);
 160   tree oprnd0;
 161   enum vect_def_type dt;
 162
 163   stmt_vinfo = vinfo_for_stmt (use_stmt);
 164   if (!vect_is_simple_use (name, stmt_vinfo->vinfo, def_stmt, &dt))
 165     return false;
 166
 167   if (dt != vect_internal_def
 168       && dt != vect_external_def && dt != vect_constant_def)
 169     return false;
 170
 171   if (!*def_stmt)
 172     return false;
 173
 174   if (dt == vect_internal_def)
 175     {
 176       stmt_vec_info def_vinfo = vinfo_for_stmt (*def_stmt);
 177       if (STMT_VINFO_IN_PATTERN_P (def_vinfo))
 178         return false;
 179     }
 180
 181   if (!is_gimple_assign (*def_stmt))
 182     return false;
 183
 184   if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (*def_stmt)))
 185     return false;
 186
 187   oprnd0 = gimple_assign_rhs1 (*def_stmt);
 188
 189   *orig_type = TREE_TYPE (oprnd0);
 190   if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*orig_type)
 191       || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*orig_type)) && check_sign))
 192     return false;
 193
 194   if (TYPE_PRECISION (type) >= (TYPE_PRECISION (*orig_type) * 2))
 195     *promotion = true;
 196   else
 197     *promotion = false;
 198
 199   if (!vect_is_simple_use (oprnd0, stmt_vinfo->vinfo, &dummy_gimple, &dt))
 200     return false;
 201
 202   return true;
 203 }
 204
 205 /* Helper to return a new temporary for pattern of TYPE for STMT.  If STMT
 206    is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */
 207
 208 static tree
 209 vect_recog_temp_ssa_var (tree type, gimple *stmt)
 210 {
 211   return make_temp_ssa_name (type, stmt, "patt");
 212 }
 213
 214 /* Function vect_recog_dot_prod_pattern
 215
 216    Try to find the following pattern:
 217
 218      type x_t, y_t;
 219      TYPE1 prod;
 220      TYPE2 sum = init;
 221    loop:
 222      sum_0 = phi <init, sum_1>
 223      S1  x_t = ...
 224      S2  y_t = ...
 225      S3  x_T = (TYPE1) x_t;
 226      S4  y_T = (TYPE1) y_t;
 227      S5  prod = x_T * y_T;
 228      [S6  prod = (TYPE2) prod;  #optional]
 229      S7  sum_1 = prod + sum_0;
 230
 231    where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
 232    same size of 'TYPE1' or bigger. This is a special case of a reduction
 233    computation.
 234
 235    Input:
 236
 237    * STMTS: Contains a stmt from which the pattern search begins.  In the
 238    example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7}
 239    will be detected.
 240
 241    Output:
 242
 243    * TYPE_IN: The type of the input arguments to the pattern.
 244
 245    * TYPE_OUT: The type of the output  of this pattern.
 246
 247    * Return value: A new stmt that will be used to replace the sequence of
 248    stmts that constitute the pattern. In this case it will be:
 249         WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
 250
 251    Note: The dot-prod idiom is a widening reduction pattern that is
 252          vectorized without preserving all the intermediate results. It
 253          produces only N/2 (widened) results (by summing up pairs of
 254          intermediate results) rather than all N results.  Therefore, we
 255          cannot allow this pattern when we want to get all the results and in
 256          the correct order (as is the case when this computation is in an
 257          inner-loop nested in an outer-loop that us being vectorized).  */
 258
 259 static gimple *
 260 vect_recog_dot_prod_pattern (vec<gimple *> *stmts, tree *type_in,
 261                              tree *type_out)
 262 {
 263   gimple *stmt, *last_stmt = (*stmts)[0];
 264   tree oprnd0, oprnd1;
 265   tree oprnd00, oprnd01;
 266   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 267   tree type, half_type;
 268   gimple *pattern_stmt;
 269   tree prod_type;
 270   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 271   struct loop *loop;
 272   tree var;
 273   bool promotion;
 274
 275   if (!loop_info)
 276     return NULL;
 277
 278   loop = LOOP_VINFO_LOOP (loop_info);
 279
 280   /* We don't allow changing the order of the computation in the inner-loop
 281      when doing outer-loop vectorization.  */
 282   if (loop && nested_in_vect_loop_p (loop, last_stmt))
 283     return NULL;
 284
 285   if (!is_gimple_assign (last_stmt))
 286     return NULL;
 287
 288   type = gimple_expr_type (last_stmt);
 289
 290   /* Look for the following pattern
 291           DX = (TYPE1) X;
 292           DY = (TYPE1) Y;
 293           DPROD = DX * DY;
 294           DDPROD = (TYPE2) DPROD;
 295           sum_1 = DDPROD + sum_0;
 296      In which
 297      - DX is double the size of X
 298      - DY is double the size of Y
 299      - DX, DY, DPROD all have the same type
 300      - sum is the same size of DPROD or bigger
 301      - sum has been recognized as a reduction variable.
 302
 303      This is equivalent to:
 304        DPROD = X w* Y;          #widen mult
 305        sum_1 = DPROD w+ sum_0;  #widen summation
 306      or
 307        DPROD = X w* Y;          #widen mult
 308        sum_1 = DPROD + sum_0;   #summation
 309    */
 310
 311   /* Starting from LAST_STMT, follow the defs of its uses in search
 312      of the above pattern.  */
 313
 314   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
 315     return NULL;
 316
 317   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 318     {
 319       /* Has been detected as widening-summation?  */
 320
 321       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 322       type = gimple_expr_type (stmt);
 323       if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
 324         return NULL;
 325       oprnd0 = gimple_assign_rhs1 (stmt);
 326       oprnd1 = gimple_assign_rhs2 (stmt);
 327       half_type = TREE_TYPE (oprnd0);
 328     }
 329   else
 330     {
 331       gimple *def_stmt;
 332
 333       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def
 334           && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo))
 335         return NULL;
 336       oprnd0 = gimple_assign_rhs1 (last_stmt);
 337       oprnd1 = gimple_assign_rhs2 (last_stmt);
 338       if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 339           || !types_compatible_p (TREE_TYPE (oprnd1), type))
 340         return NULL;
 341       stmt = last_stmt;
 342
 343       if (type_conversion_p (oprnd0, stmt, true, &half_type, &def_stmt,
 344                              &promotion)
 345           && promotion)
 346         {
 347           stmt = def_stmt;
 348           oprnd0 = gimple_assign_rhs1 (stmt);
 349         }
 350       else
 351         half_type = type;
 352     }
 353
 354   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
 355      we know that oprnd1 is the reduction variable (defined by a loop-header
 356      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 357      Left to check that oprnd0 is defined by a (widen_)mult_expr  */
 358   if (TREE_CODE (oprnd0) != SSA_NAME)
 359     return NULL;
 360
 361   prod_type = half_type;
 362   stmt = SSA_NAME_DEF_STMT (oprnd0);
 363
 364   /* It could not be the dot_prod pattern if the stmt is outside the loop.  */
 365   if (!gimple_bb (stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 366     return NULL;
 367
 368   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
 369      inside the loop (in case we are analyzing an outer-loop).  */
 370   if (!is_gimple_assign (stmt))
 371     return NULL;
 372   stmt_vinfo = vinfo_for_stmt (stmt);
 373   gcc_assert (stmt_vinfo);
 374   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
 375     return NULL;
 376   if (gimple_assign_rhs_code (stmt) != MULT_EXPR)
 377     return NULL;
 378   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 379     {
 380       /* Has been detected as a widening multiplication?  */
 381
 382       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 383       if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR)
 384         return NULL;
 385       stmt_vinfo = vinfo_for_stmt (stmt);
 386       gcc_assert (stmt_vinfo);
 387       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_internal_def);
 388       oprnd00 = gimple_assign_rhs1 (stmt);
 389       oprnd01 = gimple_assign_rhs2 (stmt);
 390       STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (last_stmt))
 391           = STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo);
 392     }
 393   else
 394     {
 395       tree half_type0, half_type1;
 396       gimple *def_stmt;
 397       tree oprnd0, oprnd1;
 398
 399       oprnd0 = gimple_assign_rhs1 (stmt);
 400       oprnd1 = gimple_assign_rhs2 (stmt);
 401       if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type)
 402           || !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
 403         return NULL;
 404       if (!type_conversion_p (oprnd0, stmt, true, &half_type0, &def_stmt,
 405                               &promotion)
 406           || !promotion)
 407         return NULL;
 408       oprnd00 = gimple_assign_rhs1 (def_stmt);
 409       if (!type_conversion_p (oprnd1, stmt, true, &half_type1, &def_stmt,
 410                               &promotion)
 411           || !promotion)
 412         return NULL;
 413       oprnd01 = gimple_assign_rhs1 (def_stmt);
 414       if (!types_compatible_p (half_type0, half_type1))
 415         return NULL;
 416       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
 417         return NULL;
 418     }
 419
 420   half_type = TREE_TYPE (oprnd00);
 421   *type_in = half_type;
 422   *type_out = type;
 423
 424   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 425   var = vect_recog_temp_ssa_var (type, NULL);
 426   pattern_stmt = gimple_build_assign (var, DOT_PROD_EXPR,
 427                                       oprnd00, oprnd01, oprnd1);
 428
 429   if (dump_enabled_p ())
 430     {
 431       dump_printf_loc (MSG_NOTE, vect_location,
 432                        "vect_recog_dot_prod_pattern: detected: ");
 433       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
 434       dump_printf (MSG_NOTE, "\n");
 435     }
 436
 437   return pattern_stmt;
 438 }
 439
 440
 441 /* Function vect_recog_sad_pattern
 442
 443    Try to find the following Sum of Absolute Difference (SAD) pattern:
 444
 445      type x_t, y_t;
 446      signed TYPE1 diff, abs_diff;
 447      TYPE2 sum = init;
 448    loop:
 449      sum_0 = phi <init, sum_1>
 450      S1  x_t = ...
 451      S2  y_t = ...
 452      S3  x_T = (TYPE1) x_t;
 453      S4  y_T = (TYPE1) y_t;
 454      S5  diff = x_T - y_T;
 455      S6  abs_diff = ABS_EXPR <diff>;
 456      [S7  abs_diff = (TYPE2) abs_diff;  #optional]
 457      S8  sum_1 = abs_diff + sum_0;
 458
 459    where 'TYPE1' is at least double the size of type 'type', and 'TYPE2' is the
 460    same size of 'TYPE1' or bigger. This is a special case of a reduction
 461    computation.
 462
 463    Input:
 464
 465    * STMTS: Contains a stmt from which the pattern search begins.  In the
 466    example, when this function is called with S8, the pattern
 467    {S3,S4,S5,S6,S7,S8} will be detected.
 468
 469    Output:
 470
 471    * TYPE_IN: The type of the input arguments to the pattern.
 472
 473    * TYPE_OUT: The type of the output of this pattern.
 474
 475    * Return value: A new stmt that will be used to replace the sequence of
 476    stmts that constitute the pattern. In this case it will be:
 477         SAD_EXPR <x_t, y_t, sum_0>
 478   */
 479
 480 static gimple *
 481 vect_recog_sad_pattern (vec<gimple *> *stmts, tree *type_in,
 482                              tree *type_out)
 483 {
 484   gimple *last_stmt = (*stmts)[0];
 485   tree sad_oprnd0, sad_oprnd1;
 486   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 487   tree half_type;
 488   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 489   struct loop *loop;
 490   bool promotion;
 491
 492   if (!loop_info)
 493     return NULL;
 494
 495   loop = LOOP_VINFO_LOOP (loop_info);
 496
 497   /* We don't allow changing the order of the computation in the inner-loop
 498      when doing outer-loop vectorization.  */
 499   if (loop && nested_in_vect_loop_p (loop, last_stmt))
 500     return NULL;
 501
 502   if (!is_gimple_assign (last_stmt))
 503     return NULL;
 504
 505   tree sum_type = gimple_expr_type (last_stmt);
 506
 507   /* Look for the following pattern
 508           DX = (TYPE1) X;
 509           DY = (TYPE1) Y;
 510           DDIFF = DX - DY;
 511           DAD = ABS_EXPR <DDIFF>;
 512           DDPROD = (TYPE2) DPROD;
 513           sum_1 = DAD + sum_0;
 514      In which
 515      - DX is at least double the size of X
 516      - DY is at least double the size of Y
 517      - DX, DY, DDIFF, DAD all have the same type
 518      - sum is the same size of DAD or bigger
 519      - sum has been recognized as a reduction variable.
 520
 521      This is equivalent to:
 522        DDIFF = X w- Y;          #widen sub
 523        DAD = ABS_EXPR <DDIFF>;
 524        sum_1 = DAD w+ sum_0;    #widen summation
 525      or
 526        DDIFF = X w- Y;          #widen sub
 527        DAD = ABS_EXPR <DDIFF>;
 528        sum_1 = DAD + sum_0;     #summation
 529    */
 530
 531   /* Starting from LAST_STMT, follow the defs of its uses in search
 532      of the above pattern.  */
 533
 534   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
 535     return NULL;
 536
 537   tree plus_oprnd0, plus_oprnd1;
 538
 539   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 540     {
 541       /* Has been detected as widening-summation?  */
 542
 543       gimple *stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 544       sum_type = gimple_expr_type (stmt);
 545       if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
 546         return NULL;
 547       plus_oprnd0 = gimple_assign_rhs1 (stmt);
 548       plus_oprnd1 = gimple_assign_rhs2 (stmt);
 549       half_type = TREE_TYPE (plus_oprnd0);
 550     }
 551   else
 552     {
 553       gimple *def_stmt;
 554
 555       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def
 556           && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo))
 557         return NULL;
 558       plus_oprnd0 = gimple_assign_rhs1 (last_stmt);
 559       plus_oprnd1 = gimple_assign_rhs2 (last_stmt);
 560       if (!types_compatible_p (TREE_TYPE (plus_oprnd0), sum_type)
 561           || !types_compatible_p (TREE_TYPE (plus_oprnd1), sum_type))
 562         return NULL;
 563
 564       /* The type conversion could be promotion, demotion,
 565          or just signed -> unsigned.  */
 566       if (type_conversion_p (plus_oprnd0, last_stmt, false,
 567                              &half_type, &def_stmt, &promotion))
 568         plus_oprnd0 = gimple_assign_rhs1 (def_stmt);
 569       else
 570         half_type = sum_type;
 571     }
 572
 573   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
 574      we know that plus_oprnd1 is the reduction variable (defined by a loop-header
 575      phi), and plus_oprnd0 is an ssa-name defined by a stmt in the loop body.
 576      Then check that plus_oprnd0 is defined by an abs_expr.  */
 577
 578   if (TREE_CODE (plus_oprnd0) != SSA_NAME)
 579     return NULL;
 580
 581   tree abs_type = half_type;
 582   gimple *abs_stmt = SSA_NAME_DEF_STMT (plus_oprnd0);
 583
 584   /* It could not be the sad pattern if the abs_stmt is outside the loop.  */
 585   if (!gimple_bb (abs_stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (abs_stmt)))
 586     return NULL;
 587
 588   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
 589      inside the loop (in case we are analyzing an outer-loop).  */
 590   if (!is_gimple_assign (abs_stmt))
 591     return NULL;
 592
 593   stmt_vec_info abs_stmt_vinfo = vinfo_for_stmt (abs_stmt);
 594   gcc_assert (abs_stmt_vinfo);
 595   if (STMT_VINFO_DEF_TYPE (abs_stmt_vinfo) != vect_internal_def)
 596     return NULL;
 597   if (gimple_assign_rhs_code (abs_stmt) != ABS_EXPR)
 598     return NULL;
 599
 600   tree abs_oprnd = gimple_assign_rhs1 (abs_stmt);
 601   if (!types_compatible_p (TREE_TYPE (abs_oprnd), abs_type))
 602     return NULL;
 603   if (TYPE_UNSIGNED (abs_type))
 604     return NULL;
 605
 606   /* We then detect if the operand of abs_expr is defined by a minus_expr.  */
 607
 608   if (TREE_CODE (abs_oprnd) != SSA_NAME)
 609     return NULL;
 610
 611   gimple *diff_stmt = SSA_NAME_DEF_STMT (abs_oprnd);
 612
 613   /* It could not be the sad pattern if the diff_stmt is outside the loop.  */
 614   if (!gimple_bb (diff_stmt)
 615       || !flow_bb_inside_loop_p (loop, gimple_bb (diff_stmt)))
 616     return NULL;
 617
 618   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
 619      inside the loop (in case we are analyzing an outer-loop).  */
 620   if (!is_gimple_assign (diff_stmt))
 621     return NULL;
 622
 623   stmt_vec_info diff_stmt_vinfo = vinfo_for_stmt (diff_stmt);
 624   gcc_assert (diff_stmt_vinfo);
 625   if (STMT_VINFO_DEF_TYPE (diff_stmt_vinfo) != vect_internal_def)
 626     return NULL;
 627   if (gimple_assign_rhs_code (diff_stmt) != MINUS_EXPR)
 628     return NULL;
 629
 630   tree half_type0, half_type1;
 631   gimple *def_stmt;
 632
 633   tree minus_oprnd0 = gimple_assign_rhs1 (diff_stmt);
 634   tree minus_oprnd1 = gimple_assign_rhs2 (diff_stmt);
 635
 636   if (!types_compatible_p (TREE_TYPE (minus_oprnd0), abs_type)
 637       || !types_compatible_p (TREE_TYPE (minus_oprnd1), abs_type))
 638     return NULL;
 639   if (!type_conversion_p (minus_oprnd0, diff_stmt, false,
 640                           &half_type0, &def_stmt, &promotion)
 641       || !promotion)
 642     return NULL;
 643   sad_oprnd0 = gimple_assign_rhs1 (def_stmt);
 644
 645   if (!type_conversion_p (minus_oprnd1, diff_stmt, false,
 646                           &half_type1, &def_stmt, &promotion)
 647       || !promotion)
 648     return NULL;
 649   sad_oprnd1 = gimple_assign_rhs1 (def_stmt);
 650
 651   if (!types_compatible_p (half_type0, half_type1))
 652     return NULL;
 653   if (TYPE_PRECISION (abs_type) < TYPE_PRECISION (half_type0) * 2
 654       || TYPE_PRECISION (sum_type) < TYPE_PRECISION (half_type0) * 2)
 655     return NULL;
 656
 657   *type_in = TREE_TYPE (sad_oprnd0);
 658   *type_out = sum_type;
 659
 660   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 661   tree var = vect_recog_temp_ssa_var (sum_type, NULL);
 662   gimple *pattern_stmt = gimple_build_assign (var, SAD_EXPR, sad_oprnd0,
 663                                               sad_oprnd1, plus_oprnd1);
 664
 665   if (dump_enabled_p ())
 666     {
 667       dump_printf_loc (MSG_NOTE, vect_location,
 668                        "vect_recog_sad_pattern: detected: ");
 669       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
 670       dump_printf (MSG_NOTE, "\n");
 671     }
 672
 673   return pattern_stmt;
 674 }
 675
 676
 677 /* Handle widening operation by a constant.  At the moment we support MULT_EXPR
 678    and LSHIFT_EXPR.
 679
 680    For MULT_EXPR we check that CONST_OPRND fits HALF_TYPE, and for LSHIFT_EXPR
 681    we check that CONST_OPRND is less or equal to the size of HALF_TYPE.
 682
 683    Otherwise, if the type of the result (TYPE) is at least 4 times bigger than
 684    HALF_TYPE, and there is an intermediate type (2 times smaller than TYPE)
 685    that satisfies the above restrictions,  we can perform a widening opeartion
 686    from the intermediate type to TYPE and replace a_T = (TYPE) a_t;
 687    with a_it = (interm_type) a_t;  Store such operation in *WSTMT.  */
 688
 689 static bool
 690 vect_handle_widen_op_by_const (gimple *stmt, enum tree_code code,
 691                                tree const_oprnd, tree *oprnd,
 692                                gimple **wstmt, tree type,
 693                                tree *half_type, gimple *def_stmt)
 694 {
 695   tree new_type, new_oprnd;
 696
 697   if (code != MULT_EXPR && code != LSHIFT_EXPR)
 698     return false;
 699
 700   if (((code == MULT_EXPR && int_fits_type_p (const_oprnd, *half_type))
 701         || (code == LSHIFT_EXPR
 702             && compare_tree_int (const_oprnd, TYPE_PRECISION (*half_type))
 703                 != 1))
 704       && TYPE_PRECISION (type) == (TYPE_PRECISION (*half_type) * 2))
 705     {
 706       /* CONST_OPRND is a constant of HALF_TYPE.  */
 707       *oprnd = gimple_assign_rhs1 (def_stmt);
 708       return true;
 709     }
 710
 711   if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4))
 712     return false;
 713
 714   if (!vect_same_loop_or_bb_p (stmt, def_stmt))
 715     return false;
 716
 717   /* TYPE is 4 times bigger than HALF_TYPE, try widening operation for
 718      a type 2 times bigger than HALF_TYPE.  */
 719   new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2,
 720                                              TYPE_UNSIGNED (type));
 721   if ((code == MULT_EXPR && !int_fits_type_p (const_oprnd, new_type))
 722       || (code == LSHIFT_EXPR
 723           && compare_tree_int (const_oprnd, TYPE_PRECISION (new_type)) == 1))
 724     return false;
 725
 726   /* Use NEW_TYPE for widening operation and create a_T = (NEW_TYPE) a_t;  */
 727   *oprnd = gimple_assign_rhs1 (def_stmt);
 728   new_oprnd = make_ssa_name (new_type);
 729   *wstmt = gimple_build_assign (new_oprnd, NOP_EXPR, *oprnd);
 730   *oprnd = new_oprnd;
 731
 732   *half_type = new_type;
 733   return true;
 734 }
 735
 736
 737 /* Function vect_recog_widen_mult_pattern
 738
 739    Try to find the following pattern:
 740
 741      type1 a_t;
 742      type2 b_t;
 743      TYPE a_T, b_T, prod_T;
 744
 745      S1  a_t = ;
 746      S2  b_t = ;
 747      S3  a_T = (TYPE) a_t;
 748      S4  b_T = (TYPE) b_t;
 749      S5  prod_T = a_T * b_T;
 750
 751    where type 'TYPE' is at least double the size of type 'type1' and 'type2'.
 752
 753    Also detect unsigned cases:
 754
 755      unsigned type1 a_t;
 756      unsigned type2 b_t;
 757      unsigned TYPE u_prod_T;
 758      TYPE a_T, b_T, prod_T;
 759
 760      S1  a_t = ;
 761      S2  b_t = ;
 762      S3  a_T = (TYPE) a_t;
 763      S4  b_T = (TYPE) b_t;
 764      S5  prod_T = a_T * b_T;
 765      S6  u_prod_T = (unsigned TYPE) prod_T;
 766
 767    and multiplication by constants:
 768
 769      type a_t;
 770      TYPE a_T, prod_T;
 771
 772      S1  a_t = ;
 773      S3  a_T = (TYPE) a_t;
 774      S5  prod_T = a_T * CONST;
 775
 776    A special case of multiplication by constants is when 'TYPE' is 4 times
 777    bigger than 'type', but CONST fits an intermediate type 2 times smaller
 778    than 'TYPE'.  In that case we create an additional pattern stmt for S3
 779    to create a variable of the intermediate type, and perform widen-mult
 780    on the intermediate type as well:
 781
 782      type a_t;
 783      interm_type a_it;
 784      TYPE a_T, prod_T,  prod_T';
 785
 786      S1  a_t = ;
 787      S3  a_T = (TYPE) a_t;
 788            '--> a_it = (interm_type) a_t;
 789      S5  prod_T = a_T * CONST;
 790            '--> prod_T' = a_it w* CONST;
 791
 792    Input/Output:
 793
 794    * STMTS: Contains a stmt from which the pattern search begins.  In the
 795    example, when this function is called with S5, the pattern {S3,S4,S5,(S6)}
 796    is detected.  In case of unsigned widen-mult, the original stmt (S5) is
 797    replaced with S6 in STMTS.  In case of multiplication by a constant
 798    of an intermediate type (the last case above), STMTS also contains S3
 799    (inserted before S5).
 800
 801    Output:
 802
 803    * TYPE_IN: The type of the input arguments to the pattern.
 804
 805    * TYPE_OUT: The type of the output of this pattern.
 806
 807    * Return value: A new stmt that will be used to replace the sequence of
 808    stmts that constitute the pattern.  In this case it will be:
 809         WIDEN_MULT <a_t, b_t>
 810    If the result of WIDEN_MULT needs to be converted to a larger type, the
 811    returned stmt will be this type conversion stmt.
 812 */
 813
 814 static gimple *
 815 vect_recog_widen_mult_pattern (vec<gimple *> *stmts,
 816                                tree *type_in, tree *type_out)
 817 {
 818   gimple *last_stmt = stmts->pop ();
 819   gimple *def_stmt0, *def_stmt1;
 820   tree oprnd0, oprnd1;
 821   tree type, half_type0, half_type1;
 822   gimple *new_stmt = NULL, *pattern_stmt = NULL;
 823   tree vectype, vecitype;
 824   tree var;
 825   enum tree_code dummy_code;
 826   int dummy_int;
 827   vec<tree> dummy_vec;
 828   bool op1_ok;
 829   bool promotion;
 830
 831   if (!is_gimple_assign (last_stmt))
 832     return NULL;
 833
 834   type = gimple_expr_type (last_stmt);
 835
 836   /* Starting from LAST_STMT, follow the defs of its uses in search
 837      of the above pattern.  */
 838
 839   if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)
 840     return NULL;
 841
 842   oprnd0 = gimple_assign_rhs1 (last_stmt);
 843   oprnd1 = gimple_assign_rhs2 (last_stmt);
 844   if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 845       || !types_compatible_p (TREE_TYPE (oprnd1), type))
 846     return NULL;
 847
 848   /* Check argument 0.  */
 849   if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0,
 850                          &promotion)
 851       || !promotion)
 852      return NULL;
 853   /* Check argument 1.  */
 854   op1_ok = type_conversion_p (oprnd1, last_stmt, false, &half_type1,
 855                               &def_stmt1, &promotion);
 856
 857   if (op1_ok && promotion)
 858     {
 859       oprnd0 = gimple_assign_rhs1 (def_stmt0);
 860       oprnd1 = gimple_assign_rhs1 (def_stmt1);
 861     }
 862   else
 863     {
 864       if (TREE_CODE (oprnd1) == INTEGER_CST
 865           && TREE_CODE (half_type0) == INTEGER_TYPE
 866           && vect_handle_widen_op_by_const (last_stmt, MULT_EXPR, oprnd1,
 867                                             &oprnd0, &new_stmt, type,
 868                                             &half_type0, def_stmt0))
 869         {
 870           half_type1 = half_type0;
 871           oprnd1 = fold_convert (half_type1, oprnd1);
 872         }
 873       else
 874         return NULL;
 875     }
 876
 877   /* If the two arguments have different sizes, convert the one with
 878      the smaller type into the larger type.  */
 879   if (TYPE_PRECISION (half_type0) != TYPE_PRECISION (half_type1))
 880     {
 881       /* If we already used up the single-stmt slot give up.  */
 882       if (new_stmt)
 883         return NULL;
 884
 885       tree* oprnd = NULL;
 886       gimple *def_stmt = NULL;
 887
 888       if (TYPE_PRECISION (half_type0) < TYPE_PRECISION (half_type1))
 889         {
 890           def_stmt = def_stmt0;
 891           half_type0 = half_type1;
 892           oprnd = &oprnd0;
 893         }
 894       else
 895         {
 896           def_stmt = def_stmt1;
 897           half_type1 = half_type0;
 898           oprnd = &oprnd1;
 899         }
 900
 901       tree old_oprnd = gimple_assign_rhs1 (def_stmt);
 902       tree new_oprnd = make_ssa_name (half_type0);
 903       new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, old_oprnd);
 904       *oprnd = new_oprnd;
 905     }
 906
 907   /* Handle unsigned case.  Look for
 908      S6  u_prod_T = (unsigned TYPE) prod_T;
 909      Use unsigned TYPE as the type for WIDEN_MULT_EXPR.  */
 910   if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
 911     {
 912       gimple *use_stmt;
 913       tree use_lhs;
 914       tree use_type;
 915
 916       if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1))
 917         return NULL;
 918
 919       use_stmt = vect_single_imm_use (last_stmt);
 920       if (!use_stmt || !is_gimple_assign (use_stmt)
 921           || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
 922         return NULL;
 923
 924       use_lhs = gimple_assign_lhs (use_stmt);
 925       use_type = TREE_TYPE (use_lhs);
 926       if (!INTEGRAL_TYPE_P (use_type)
 927           || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))
 928           || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))
 929         return NULL;
 930
 931       type = use_type;
 932       last_stmt = use_stmt;
 933     }
 934
 935   if (!types_compatible_p (half_type0, half_type1))
 936     return NULL;
 937
 938   /* If TYPE is more than twice larger than HALF_TYPE, we use WIDEN_MULT
 939      to get an intermediate result of type ITYPE.  In this case we need
 940      to build a statement to convert this intermediate result to type TYPE.  */
 941   tree itype = type;
 942   if (TYPE_PRECISION (type) > TYPE_PRECISION (half_type0) * 2)
 943     itype = build_nonstandard_integer_type
 944               (GET_MODE_BITSIZE (TYPE_MODE (half_type0)) * 2,
 945                TYPE_UNSIGNED (type));
 946
 947   /* Pattern detected.  */
 948   if (dump_enabled_p ())
 949     dump_printf_loc (MSG_NOTE, vect_location,
 950                      "vect_recog_widen_mult_pattern: detected:\n");
 951
 952   /* Check target support  */
 953   vectype = get_vectype_for_scalar_type (half_type0);
 954   vecitype = get_vectype_for_scalar_type (itype);
 955   if (!vectype
 956       || !vecitype
 957       || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt,
 958                                           vecitype, vectype,
 959                                           &dummy_code, &dummy_code,
 960                                           &dummy_int, &dummy_vec))
 961     return NULL;
 962
 963   *type_in = vectype;
 964   *type_out = get_vectype_for_scalar_type (type);
 965
 966   /* Pattern supported. Create a stmt to be used to replace the pattern: */
 967   var = vect_recog_temp_ssa_var (itype, NULL);
 968   pattern_stmt = gimple_build_assign (var, WIDEN_MULT_EXPR, oprnd0, oprnd1);
 969
 970   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 971   STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
 972
 973   /* If the original two operands have different sizes, we may need to convert
 974      the smaller one into the larget type.  If this is the case, at this point
 975      the new stmt is already built.  */
 976   if (new_stmt)
 977     {
 978       append_pattern_def_seq (stmt_vinfo, new_stmt);
 979       stmt_vec_info new_stmt_info
 980         = new_stmt_vec_info (new_stmt, stmt_vinfo->vinfo);
 981       set_vinfo_for_stmt (new_stmt, new_stmt_info);
 982       STMT_VINFO_VECTYPE (new_stmt_info) = vectype;
 983     }
 984
 985   /* If ITYPE is not TYPE, we need to build a type convertion stmt to convert
 986      the result of the widen-mult operation into type TYPE.  */
 987   if (itype != type)
 988     {
 989       append_pattern_def_seq (stmt_vinfo, pattern_stmt);
 990       stmt_vec_info pattern_stmt_info
 991         = new_stmt_vec_info (pattern_stmt, stmt_vinfo->vinfo);
 992       set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
 993       STMT_VINFO_VECTYPE (pattern_stmt_info) = vecitype;
 994       pattern_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL),
 995                                           NOP_EXPR,
 996                                           gimple_assign_lhs (pattern_stmt));
 997     }
 998
 999   if (dump_enabled_p ())
1000     dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
1001
1002   stmts->safe_push (last_stmt);
1003   return pattern_stmt;
1004 }
1005
1006
1007 /* Function vect_recog_pow_pattern
1008
1009    Try to find the following pattern:
1010
1011      x = POW (y, N);
1012
1013    with POW being one of pow, powf, powi, powif and N being
1014    either 2 or 0.5.
1015
1016    Input:
1017
1018    * LAST_STMT: A stmt from which the pattern search begins.
1019
1020    Output:
1021
1022    * TYPE_IN: The type of the input arguments to the pattern.
1023
1024    * TYPE_OUT: The type of the output of this pattern.
1025
1026    * Return value: A new stmt that will be used to replace the sequence of
1027    stmts that constitute the pattern. In this case it will be:
1028         x = x * x
1029    or
1030         x = sqrt (x)
1031 */
1032
1033 static gimple *
1034 vect_recog_pow_pattern (vec<gimple *> *stmts, tree *type_in,
1035                         tree *type_out)
1036 {
1037   gimple *last_stmt = (*stmts)[0];
1038   tree base, exp = NULL;
1039   gimple *stmt;
1040   tree var;
1041
1042   if (!is_gimple_call (last_stmt) || gimple_call_lhs (last_stmt) == NULL)
1043     return NULL;
1044
1045   switch (gimple_call_combined_fn (last_stmt))
1046     {
1047     CASE_CFN_POW:
1048     CASE_CFN_POWI:
1049       base = gimple_call_arg (last_stmt, 0);
1050       exp = gimple_call_arg (last_stmt, 1);
1051       if (TREE_CODE (exp) != REAL_CST
1052           && TREE_CODE (exp) != INTEGER_CST)
1053         return NULL;
1054       break;
1055
1056     default:
1057       return NULL;
1058     }
1059
1060   /* We now have a pow or powi builtin function call with a constant
1061      exponent.  */
1062
1063   *type_out = NULL_TREE;
1064
1065   /* Catch squaring.  */
1066   if ((tree_fits_shwi_p (exp)
1067        && tree_to_shwi (exp) == 2)
1068       || (TREE_CODE (exp) == REAL_CST
1069           && real_equal (&TREE_REAL_CST (exp), &dconst2)))
1070     {
1071       *type_in = TREE_TYPE (base);
1072
1073       var = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
1074       stmt = gimple_build_assign (var, MULT_EXPR, base, base);
1075       return stmt;
1076     }
1077
1078   /* Catch square root.  */
1079   if (TREE_CODE (exp) == REAL_CST
1080       && real_equal (&TREE_REAL_CST (exp), &dconsthalf))
1081     {
1082       *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
1083       if (*type_in
1084           && direct_internal_fn_supported_p (IFN_SQRT, *type_in,
1085                                              OPTIMIZE_FOR_SPEED))
1086         {
1087           gcall *stmt = gimple_build_call_internal (IFN_SQRT, 1, base);
1088           var = vect_recog_temp_ssa_var (TREE_TYPE (base), stmt);
1089           gimple_call_set_lhs (stmt, var);
1090           return stmt;
1091         }
1092     }
1093
1094   return NULL;
1095 }
1096
1097
1098 /* Function vect_recog_widen_sum_pattern
1099
1100    Try to find the following pattern:
1101
1102      type x_t;
1103      TYPE x_T, sum = init;
1104    loop:
1105      sum_0 = phi <init, sum_1>
1106      S1  x_t = *p;
1107      S2  x_T = (TYPE) x_t;
1108      S3  sum_1 = x_T + sum_0;
1109
1110    where type 'TYPE' is at least double the size of type 'type', i.e - we're
1111    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
1112    a special case of a reduction computation.
1113
1114    Input:
1115
1116    * LAST_STMT: A stmt from which the pattern search begins. In the example,
1117    when this function is called with S3, the pattern {S2,S3} will be detected.
1118
1119    Output:
1120
1121    * TYPE_IN: The type of the input arguments to the pattern.
1122
1123    * TYPE_OUT: The type of the output of this pattern.
1124
1125    * Return value: A new stmt that will be used to replace the sequence of
1126    stmts that constitute the pattern. In this case it will be:
1127         WIDEN_SUM <x_t, sum_0>
1128
1129    Note: The widening-sum idiom is a widening reduction pattern that is
1130          vectorized without preserving all the intermediate results. It
1131          produces only N/2 (widened) results (by summing up pairs of
1132          intermediate results) rather than all N results.  Therefore, we
1133          cannot allow this pattern when we want to get all the results and in
1134          the correct order (as is the case when this computation is in an
1135          inner-loop nested in an outer-loop that us being vectorized).  */
1136
1137 static gimple *
1138 vect_recog_widen_sum_pattern (vec<gimple *> *stmts, tree *type_in,
1139                               tree *type_out)
1140 {
1141   gimple *stmt, *last_stmt = (*stmts)[0];
1142   tree oprnd0, oprnd1;
1143   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
1144   tree type, half_type;
1145   gimple *pattern_stmt;
1146   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1147   struct loop *loop;
1148   tree var;
1149   bool promotion;
1150
1151   if (!loop_info)
1152     return NULL;
1153
1154   loop = LOOP_VINFO_LOOP (loop_info);
1155
1156   /* We don't allow changing the order of the computation in the inner-loop
1157      when doing outer-loop vectorization.  */
1158   if (loop && nested_in_vect_loop_p (loop, last_stmt))
1159     return NULL;
1160
1161   if (!is_gimple_assign (last_stmt))
1162     return NULL;
1163
1164   type = gimple_expr_type (last_stmt);
1165
1166   /* Look for the following pattern
1167           DX = (TYPE) X;
1168           sum_1 = DX + sum_0;
1169      In which DX is at least double the size of X, and sum_1 has been
1170      recognized as a reduction variable.
1171    */
1172
1173   /* Starting from LAST_STMT, follow the defs of its uses in search
1174      of the above pattern.  */
1175
1176   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
1177     return NULL;
1178
1179   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def
1180       && ! STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_vinfo))
1181     return NULL;
1182
1183   oprnd0 = gimple_assign_rhs1 (last_stmt);
1184   oprnd1 = gimple_assign_rhs2 (last_stmt);
1185   if (!types_compatible_p (TREE_TYPE (oprnd0), type)
1186       || !types_compatible_p (TREE_TYPE (oprnd1), type))
1187     return NULL;
1188
1189   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
1190      we know that oprnd1 is the reduction variable (defined by a loop-header
1191      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
1192      Left to check that oprnd0 is defined by a cast from type 'type' to type
1193      'TYPE'.  */
1194
1195   if (!type_conversion_p (oprnd0, last_stmt, true, &half_type, &stmt,
1196                           &promotion)
1197       || !promotion)
1198      return NULL;
1199
1200   oprnd0 = gimple_assign_rhs1 (stmt);
1201   *type_in = half_type;
1202   *type_out = type;
1203
1204   /* Pattern detected. Create a stmt to be used to replace the pattern: */
1205   var = vect_recog_temp_ssa_var (type, NULL);
1206   pattern_stmt = gimple_build_assign (var, WIDEN_SUM_EXPR, oprnd0, oprnd1);
1207
1208   if (dump_enabled_p ())
1209     {
1210       dump_printf_loc (MSG_NOTE, vect_location,
1211                        "vect_recog_widen_sum_pattern: detected: ");
1212       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
1213       dump_printf (MSG_NOTE, "\n");
1214     }
1215
1216   return pattern_stmt;
1217 }
1218
1219
1220 /* Return TRUE if the operation in STMT can be performed on a smaller type.
1221
1222    Input:
1223    STMT - a statement to check.
1224    DEF - we support operations with two operands, one of which is constant.
1225          The other operand can be defined by a demotion operation, or by a
1226          previous statement in a sequence of over-promoted operations.  In the
1227          later case DEF is used to replace that operand.  (It is defined by a
1228          pattern statement we created for the previous statement in the
1229          sequence).
1230
1231    Input/output:
1232    NEW_TYPE - Output: a smaller type that we are trying to use.  Input: if not
1233          NULL, it's the type of DEF.
1234    STMTS - additional pattern statements.  If a pattern statement (type
1235          conversion) is created in this function, its original statement is
1236          added to STMTS.
1237
1238    Output:
1239    OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new
1240          operands to use in the new pattern statement for STMT (will be created
1241          in vect_recog_over_widening_pattern ()).
1242    NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
1243          statements for STMT: the first one is a type promotion and the second
1244          one is the operation itself.  We return the type promotion statement
1245          in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_SEQ of
1246          the second pattern statement.  */
1247
1248 static bool
1249 vect_operation_fits_smaller_type (gimple *stmt, tree def, tree *new_type,
1250                                   tree *op0, tree *op1, gimple **new_def_stmt,
1251                                   vec<gimple *> *stmts)
1252 {
1253   enum tree_code code;
1254   tree const_oprnd, oprnd;
1255   tree interm_type = NULL_TREE, half_type, new_oprnd, type;
1256   gimple *def_stmt, *new_stmt;
1257   bool first = false;
1258   bool promotion;
1259
1260   *op0 = NULL_TREE;
1261   *op1 = NULL_TREE;
1262   *new_def_stmt = NULL;
1263
1264   if (!is_gimple_assign (stmt))
1265     return false;
1266
1267   code = gimple_assign_rhs_code (stmt);
1268   if (code != LSHIFT_EXPR && code != RSHIFT_EXPR
1269       && code != BIT_IOR_EXPR && code != BIT_XOR_EXPR && code != BIT_AND_EXPR)
1270     return false;
1271
1272   oprnd = gimple_assign_rhs1 (stmt);
1273   const_oprnd = gimple_assign_rhs2 (stmt);
1274   type = gimple_expr_type (stmt);
1275
1276   if (TREE_CODE (oprnd) != SSA_NAME
1277       || TREE_CODE (const_oprnd) != INTEGER_CST)
1278     return false;
1279
1280   /* If oprnd has other uses besides that in stmt we cannot mark it
1281      as being part of a pattern only.  */
1282   if (!has_single_use (oprnd))
1283     return false;
1284
1285   /* If we are in the middle of a sequence, we use DEF from a previous
1286      statement.  Otherwise, OPRND has to be a result of type promotion.  */
1287   if (*new_type)
1288     {
1289       half_type = *new_type;
1290       oprnd = def;
1291     }
1292   else
1293     {
1294       first = true;
1295       if (!type_conversion_p (oprnd, stmt, false, &half_type, &def_stmt,
1296                               &promotion)
1297           || !promotion
1298           || !vect_same_loop_or_bb_p (stmt, def_stmt))
1299         return false;
1300     }
1301
1302   /* Can we perform the operation on a smaller type?  */
1303   switch (code)
1304     {
1305       case BIT_IOR_EXPR:
1306       case BIT_XOR_EXPR:
1307       case BIT_AND_EXPR:
1308         if (!int_fits_type_p (const_oprnd, half_type))
1309           {
1310             /* HALF_TYPE is not enough.  Try a bigger type if possible.  */
1311             if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
1312               return false;
1313
1314             interm_type = build_nonstandard_integer_type (
1315                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
1316             if (!int_fits_type_p (const_oprnd, interm_type))
1317               return false;
1318           }
1319
1320         break;
1321
1322       case LSHIFT_EXPR:
1323         /* Try intermediate type - HALF_TYPE is not enough for sure.  */
1324         if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
1325           return false;
1326
1327         /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size.
1328           (e.g., if the original value was char, the shift amount is at most 8
1329            if we want to use short).  */
1330         if (compare_tree_int (const_oprnd, TYPE_PRECISION (half_type)) == 1)
1331           return false;
1332
1333         interm_type = build_nonstandard_integer_type (
1334                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
1335
1336         if (!vect_supportable_shift (code, interm_type))
1337           return false;
1338
1339         break;
1340
1341       case RSHIFT_EXPR:
1342         if (vect_supportable_shift (code, half_type))
1343           break;
1344
1345         /* Try intermediate type - HALF_TYPE is not supported.  */
1346         if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
1347           return false;
1348
1349         interm_type = build_nonstandard_integer_type (
1350                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
1351
1352         if (!vect_supportable_shift (code, interm_type))
1353           return false;
1354
1355         break;
1356
1357       default:
1358         gcc_unreachable ();
1359     }
1360
1361   /* There are four possible cases:
1362      1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's
1363         the first statement in the sequence)
1364         a. The original, HALF_TYPE, is not enough - we replace the promotion
1365            from HALF_TYPE to TYPE with a promotion to INTERM_TYPE.
1366         b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original
1367            promotion.
1368      2. OPRND is defined by a pattern statement we created.
1369         a. Its type is not sufficient for the operation, we create a new stmt:
1370            a type conversion for OPRND from HALF_TYPE to INTERM_TYPE.  We store
1371            this statement in NEW_DEF_STMT, and it is later put in
1372            STMT_VINFO_PATTERN_DEF_SEQ of the pattern statement for STMT.
1373         b. OPRND is good to use in the new statement.  */
1374   if (first)
1375     {
1376       if (interm_type)
1377         {
1378           /* Replace the original type conversion HALF_TYPE->TYPE with
1379              HALF_TYPE->INTERM_TYPE.  */
1380           if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
1381             {
1382               new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
1383               /* Check if the already created pattern stmt is what we need.  */
1384               if (!is_gimple_assign (new_stmt)
1385                   || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (new_stmt))
1386                   || TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type)
1387                 return false;
1388
1389               stmts->safe_push (def_stmt);
1390               oprnd = gimple_assign_lhs (new_stmt);
1391             }
1392           else
1393             {
1394               /* Create NEW_OPRND = (INTERM_TYPE) OPRND.  */
1395               oprnd = gimple_assign_rhs1 (def_stmt);
1396               new_oprnd = make_ssa_name (interm_type);
1397               new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, oprnd);
1398               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
1399               stmts->safe_push (def_stmt);
1400               oprnd = new_oprnd;
1401             }
1402         }
1403       else
1404         {
1405           /* Retrieve the operand before the type promotion.  */
1406           oprnd = gimple_assign_rhs1 (def_stmt);
1407         }
1408     }
1409   else
1410     {
1411       if (interm_type)
1412         {
1413           /* Create a type conversion HALF_TYPE->INTERM_TYPE.  */
1414           new_oprnd = make_ssa_name (interm_type);
1415           new_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, oprnd);
1416           oprnd = new_oprnd;
1417           *new_def_stmt = new_stmt;
1418         }
1419
1420       /* Otherwise, OPRND is already set.  */
1421     }
1422
1423   if (interm_type)
1424     *new_type = interm_type;
1425   else
1426     *new_type = half_type;
1427
1428   *op0 = oprnd;
1429   *op1 = fold_convert (*new_type, const_oprnd);
1430
1431   return true;
1432 }
1433
1434
1435 /* Try to find a statement or a sequence of statements that can be performed
1436    on a smaller type:
1437
1438      type x_t;
1439      TYPE x_T, res0_T, res1_T;
1440    loop:
1441      S1  x_t = *p;
1442      S2  x_T = (TYPE) x_t;
1443      S3  res0_T = op (x_T, C0);
1444      S4  res1_T = op (res0_T, C1);
1445      S5  ... = () res1_T;  - type demotion
1446
1447    where type 'TYPE' is at least double the size of type 'type', C0 and C1 are
1448    constants.
1449    Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
1450    be 'type' or some intermediate type.  For now, we expect S5 to be a type
1451    demotion operation.  We also check that S3 and S4 have only one use.  */
1452
1453 static gimple *
1454 vect_recog_over_widening_pattern (vec<gimple *> *stmts,
1455                                   tree *type_in, tree *type_out)
1456 {
1457   gimple *stmt = stmts->pop ();
1458   gimple *pattern_stmt = NULL, *new_def_stmt, *prev_stmt = NULL,
1459          *use_stmt = NULL;
1460   tree op0, op1, vectype = NULL_TREE, use_lhs, use_type;
1461   tree var = NULL_TREE, new_type = NULL_TREE, new_oprnd;
1462   bool first;
1463   tree type = NULL;
1464
1465   first = true;
1466   while (1)
1467     {
1468       if (!vinfo_for_stmt (stmt)
1469           || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt)))
1470         return NULL;
1471
1472       new_def_stmt = NULL;
1473       if (!vect_operation_fits_smaller_type (stmt, var, &new_type,
1474                                              &op0, &op1, &new_def_stmt,
1475                                              stmts))
1476         {
1477           if (first)
1478             return NULL;
1479           else
1480             break;
1481         }
1482
1483       /* STMT can be performed on a smaller type.  Check its uses.  */
1484       use_stmt = vect_single_imm_use (stmt);
1485       if (!use_stmt || !is_gimple_assign (use_stmt))
1486         return NULL;
1487
1488       /* Create pattern statement for STMT.  */
1489       vectype = get_vectype_for_scalar_type (new_type);
1490       if (!vectype)
1491         return NULL;
1492
1493       /* We want to collect all the statements for which we create pattern
1494          statetments, except for the case when the last statement in the
1495          sequence doesn't have a corresponding pattern statement.  In such
1496          case we associate the last pattern statement with the last statement
1497          in the sequence.  Therefore, we only add the original statement to
1498          the list if we know that it is not the last.  */
1499       if (prev_stmt)
1500         stmts->safe_push (prev_stmt);
1501
1502       var = vect_recog_temp_ssa_var (new_type, NULL);
1503       pattern_stmt
1504         = gimple_build_assign (var, gimple_assign_rhs_code (stmt), op0, op1);
1505       STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
1506       new_pattern_def_seq (vinfo_for_stmt (stmt), new_def_stmt);
1507
1508       if (dump_enabled_p ())
1509         {
1510           dump_printf_loc (MSG_NOTE, vect_location,
1511                            "created pattern stmt: ");
1512           dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
1513           dump_printf (MSG_NOTE, "\n");
1514         }
1515
1516       type = gimple_expr_type (stmt);
1517       prev_stmt = stmt;
1518       stmt = use_stmt;
1519
1520       first = false;
1521     }
1522
1523   /* We got a sequence.  We expect it to end with a type demotion operation.
1524      Otherwise, we quit (for now).  There are three possible cases: the
1525      conversion is to NEW_TYPE (we don't do anything), the conversion is to
1526      a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and
1527      NEW_TYPE differs (we create a new conversion statement).  */
1528   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1529     {
1530       use_lhs = gimple_assign_lhs (use_stmt);
1531       use_type = TREE_TYPE (use_lhs);
1532       /* Support only type demotion or signedess change.  */
1533       if (!INTEGRAL_TYPE_P (use_type)
1534           || TYPE_PRECISION (type) <= TYPE_PRECISION (use_type))
1535         return NULL;
1536
1537       /* Check that NEW_TYPE is not bigger than the conversion result.  */
1538       if (TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type))
1539         return NULL;
1540
1541       if (TYPE_UNSIGNED (new_type) != TYPE_UNSIGNED (use_type)
1542           || TYPE_PRECISION (new_type) != TYPE_PRECISION (use_type))
1543         {
1544           /* Create NEW_TYPE->USE_TYPE conversion.  */
1545           new_oprnd = make_ssa_name (use_type);
1546           pattern_stmt = gimple_build_assign (new_oprnd, NOP_EXPR, var);
1547           STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt)) = pattern_stmt;
1548
1549           *type_in = get_vectype_for_scalar_type (new_type);
1550           *type_out = get_vectype_for_scalar_type (use_type);
1551
1552           /* We created a pattern statement for the last statement in the
1553              sequence, so we don't need to associate it with the pattern
1554              statement created for PREV_STMT.  Therefore, we add PREV_STMT
1555              to the list in order to mark it later in vect_pattern_recog_1.  */
1556           if (prev_stmt)
1557             stmts->safe_push (prev_stmt);
1558         }
1559       else
1560         {
1561           if (prev_stmt)
1562             STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (use_stmt))
1563                = STMT_VINFO_PATTERN_DEF_SEQ (vinfo_for_stmt (prev_stmt));
1564
1565           *type_in = vectype;
1566           *type_out = NULL_TREE;
1567         }
1568
1569       stmts->safe_push (use_stmt);
1570     }
1571   else
1572     /* TODO: support general case, create a conversion to the correct type.  */
1573     return NULL;
1574
1575   /* Pattern detected.  */
1576   if (dump_enabled_p ())
1577     {
1578       dump_printf_loc (MSG_NOTE, vect_location,
1579                        "vect_recog_over_widening_pattern: detected: ");
1580       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
1581       dump_printf (MSG_NOTE, "\n");
1582     }
1583
1584   return pattern_stmt;
1585 }
1586
1587 /* Detect widening shift pattern:
1588
1589    type a_t;
1590    TYPE a_T, res_T;
1591
1592    S1 a_t = ;
1593    S2 a_T = (TYPE) a_t;
1594    S3 res_T = a_T << CONST;
1595
1596   where type 'TYPE' is at least double the size of type 'type'.
1597
1598   Also detect cases where the shift result is immediately converted
1599   to another type 'result_type' that is no larger in size than 'TYPE'.
1600   In those cases we perform a widen-shift that directly results in
1601   'result_type', to avoid a possible over-widening situation:
1602
1603   type a_t;
1604   TYPE a_T, res_T;
1605   result_type res_result;
1606
1607   S1 a_t = ;
1608   S2 a_T = (TYPE) a_t;
1609   S3 res_T = a_T << CONST;
1610   S4 res_result = (result_type) res_T;
1611       '--> res_result' = a_t w<< CONST;
1612
1613   And a case when 'TYPE' is 4 times bigger than 'type'.  In that case we
1614   create an additional pattern stmt for S2 to create a variable of an
1615   intermediate type, and perform widen-shift on the intermediate type:
1616
1617   type a_t;
1618   interm_type a_it;
1619   TYPE a_T, res_T, res_T';
1620
1621   S1 a_t = ;
1622   S2 a_T = (TYPE) a_t;
1623       '--> a_it = (interm_type) a_t;
1624   S3 res_T = a_T << CONST;
1625       '--> res_T' = a_it <<* CONST;
1626
1627   Input/Output:
1628
1629   * STMTS: Contains a stmt from which the pattern search begins.
1630     In case of unsigned widen-shift, the original stmt (S3) is replaced with S4
1631     in STMTS.  When an intermediate type is used and a pattern statement is
1632     created for S2, we also put S2 here (before S3).
1633
1634   Output:
1635
1636   * TYPE_IN: The type of the input arguments to the pattern.
1637
1638   * TYPE_OUT: The type of the output of this pattern.
1639
1640   * Return value: A new stmt that will be used to replace the sequence of
1641     stmts that constitute the pattern.  In this case it will be:
1642     WIDEN_LSHIFT_EXPR <a_t, CONST>.  */
1643
1644 static gimple *
1645 vect_recog_widen_shift_pattern (vec<gimple *> *stmts,
1646                                 tree *type_in, tree *type_out)
1647 {
1648   gimple *last_stmt = stmts->pop ();
1649   gimple *def_stmt0;
1650   tree oprnd0, oprnd1;
1651   tree type, half_type0;
1652   gimple *pattern_stmt;
1653   tree vectype, vectype_out = NULL_TREE;
1654   tree var;
1655   enum tree_code dummy_code;
1656   int dummy_int;
1657   vec<tree>  dummy_vec;
1658   gimple *use_stmt;
1659   bool promotion;
1660
1661   if (!is_gimple_assign (last_stmt) || !vinfo_for_stmt (last_stmt))
1662     return NULL;
1663
1664   if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (last_stmt)))
1665     return NULL;
1666
1667   if (gimple_assign_rhs_code (last_stmt) != LSHIFT_EXPR)
1668     return NULL;
1669
1670   oprnd0 = gimple_assign_rhs1 (last_stmt);
1671   oprnd1 = gimple_assign_rhs2 (last_stmt);
1672   if (TREE_CODE (oprnd0) != SSA_NAME || TREE_CODE (oprnd1) != INTEGER_CST)
1673     return NULL;
1674
1675   /* Check operand 0: it has to be defined by a type promotion.  */
1676   if (!type_conversion_p (oprnd0, last_stmt, false, &half_type0, &def_stmt0,
1677                           &promotion)
1678       || !promotion)
1679      return NULL;
1680
1681   /* Check operand 1: has to be positive.  We check that it fits the type
1682      in vect_handle_widen_op_by_const ().  */
1683   if (tree_int_cst_compare (oprnd1, size_zero_node) <= 0)
1684     return NULL;
1685
1686   oprnd0 = gimple_assign_rhs1 (def_stmt0);
1687   type = gimple_expr_type (last_stmt);
1688
1689   /* Check for subsequent conversion to another type.  */
1690   use_stmt = vect_single_imm_use (last_stmt);
1691   if (use_stmt && is_gimple_assign (use_stmt)
1692       && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt))
1693       && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (use_stmt)))
1694     {
1695       tree use_lhs = gimple_assign_lhs (use_stmt);
1696       tree use_type = TREE_TYPE (use_lhs);
1697
1698       if (INTEGRAL_TYPE_P (use_type)
1699           && TYPE_PRECISION (use_type) <= TYPE_PRECISION (type))
1700         {
1701           last_stmt = use_stmt;
1702           type = use_type;
1703         }
1704     }
1705
1706   /* Check if this a widening operation.  */
1707   gimple *wstmt = NULL;
1708   if (!vect_handle_widen_op_by_const (last_stmt, LSHIFT_EXPR, oprnd1,
1709                                       &oprnd0, &wstmt,
1710                                       type, &half_type0, def_stmt0))
1711     return NULL;
1712
1713   /* Pattern detected.  */
1714   if (dump_enabled_p ())
1715     dump_printf_loc (MSG_NOTE, vect_location,
1716                      "vect_recog_widen_shift_pattern: detected:\n");
1717
1718   /* Check target support.  */
1719   vectype = get_vectype_for_scalar_type (half_type0);
1720   vectype_out = get_vectype_for_scalar_type (type);
1721
1722   if (!vectype
1723       || !vectype_out
1724       || !supportable_widening_operation (WIDEN_LSHIFT_EXPR, last_stmt,
1725                                           vectype_out, vectype,
1726                                           &dummy_code, &dummy_code,
1727                                           &dummy_int, &dummy_vec))
1728     return NULL;
1729
1730   *type_in = vectype;
1731   *type_out = vectype_out;
1732
1733   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
1734   var = vect_recog_temp_ssa_var (type, NULL);
1735   pattern_stmt =
1736     gimple_build_assign (var, WIDEN_LSHIFT_EXPR, oprnd0, oprnd1);
1737   if (wstmt)
1738     {
1739       stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
1740       new_pattern_def_seq (stmt_vinfo, wstmt);
1741       stmt_vec_info new_stmt_info
1742         = new_stmt_vec_info (wstmt, stmt_vinfo->vinfo);
1743       set_vinfo_for_stmt (wstmt, new_stmt_info);
1744       STMT_VINFO_VECTYPE (new_stmt_info) = vectype;
1745     }
1746
1747   if (dump_enabled_p ())
1748     dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
1749
1750   stmts->safe_push (last_stmt);
1751   return pattern_stmt;
1752 }
1753
1754 /* Detect a rotate pattern wouldn't be otherwise vectorized:
1755
1756    type a_t, b_t, c_t;
1757
1758    S0 a_t = b_t r<< c_t;
1759
1760   Input/Output:
1761
1762   * STMTS: Contains a stmt from which the pattern search begins,
1763     i.e. the shift/rotate stmt.  The original stmt (S0) is replaced
1764     with a sequence:
1765
1766    S1 d_t = -c_t;
1767    S2 e_t = d_t & (B - 1);
1768    S3 f_t = b_t << c_t;
1769    S4 g_t = b_t >> e_t;
1770    S0 a_t = f_t | g_t;
1771
1772     where B is element bitsize of type.
1773
1774   Output:
1775
1776   * TYPE_IN: The type of the input arguments to the pattern.
1777
1778   * TYPE_OUT: The type of the output of this pattern.
1779
1780   * Return value: A new stmt that will be used to replace the rotate
1781     S0 stmt.  */
1782
1783 static gimple *
1784 vect_recog_rotate_pattern (vec<gimple *> *stmts, tree *type_in, tree *type_out)
1785 {
1786   gimple *last_stmt = stmts->pop ();
1787   tree oprnd0, oprnd1, lhs, var, var1, var2, vectype, type, stype, def, def2;
1788   gimple *pattern_stmt, *def_stmt;
1789   enum tree_code rhs_code;
1790   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
1791   vec_info *vinfo = stmt_vinfo->vinfo;
1792   enum vect_def_type dt;
1793   optab optab1, optab2;
1794   edge ext_def = NULL;
1795
1796   if (!is_gimple_assign (last_stmt))
1797     return NULL;
1798
1799   rhs_code = gimple_assign_rhs_code (last_stmt);
1800   switch (rhs_code)
1801     {
1802     case LROTATE_EXPR:
1803     case RROTATE_EXPR:
1804       break;
1805     default:
1806       return NULL;
1807     }
1808
1809   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
1810     return NULL;
1811
1812   lhs = gimple_assign_lhs (last_stmt);
1813   oprnd0 = gimple_assign_rhs1 (last_stmt);
1814   type = TREE_TYPE (oprnd0);
1815   oprnd1 = gimple_assign_rhs2 (last_stmt);
1816   if (TREE_CODE (oprnd0) != SSA_NAME
1817       || TYPE_PRECISION (TREE_TYPE (lhs)) != TYPE_PRECISION (type)
1818       || !INTEGRAL_TYPE_P (type)
1819       || !TYPE_UNSIGNED (type))
1820     return NULL;
1821
1822   if (!vect_is_simple_use (oprnd1, vinfo, &def_stmt, &dt))
1823     return NULL;
1824
1825   if (dt != vect_internal_def
1826       && dt != vect_constant_def
1827       && dt != vect_external_def)
1828     return NULL;
1829
1830   vectype = get_vectype_for_scalar_type (type);
1831   if (vectype == NULL_TREE)
1832     return NULL;
1833
1834   /* If vector/vector or vector/scalar rotate is supported by the target,
1835      don't do anything here.  */
1836   optab1 = optab_for_tree_code (rhs_code, vectype, optab_vector);
1837   if (optab1
1838       && optab_handler (optab1, TYPE_MODE (vectype)) != CODE_FOR_nothing)
1839     return NULL;
1840
1841   if (is_a <bb_vec_info> (vinfo) || dt != vect_internal_def)
1842     {
1843       optab2 = optab_for_tree_code (rhs_code, vectype, optab_scalar);
1844       if (optab2
1845           && optab_handler (optab2, TYPE_MODE (vectype)) != CODE_FOR_nothing)
1846         return NULL;
1847     }
1848
1849   /* If vector/vector or vector/scalar shifts aren't supported by the target,
1850      don't do anything here either.  */
1851   optab1 = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_vector);
1852   optab2 = optab_for_tree_code (RSHIFT_EXPR, vectype, optab_vector);
1853   if (!optab1
1854       || optab_handler (optab1, TYPE_MODE (vectype)) == CODE_FOR_nothing
1855       || !optab2
1856       || optab_handler (optab2, TYPE_MODE (vectype)) == CODE_FOR_nothing)
1857     {
1858       if (! is_a <bb_vec_info> (vinfo) && dt == vect_internal_def)
1859         return NULL;
1860       optab1 = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_scalar);
1861       optab2 = optab_for_tree_code (RSHIFT_EXPR, vectype, optab_scalar);
1862       if (!optab1
1863           || optab_handler (optab1, TYPE_MODE (vectype)) == CODE_FOR_nothing
1864           || !optab2
1865           || optab_handler (optab2, TYPE_MODE (vectype)) == CODE_FOR_nothing)
1866         return NULL;
1867     }
1868
1869   *type_in = vectype;
1870   *type_out = vectype;
1871   if (*type_in == NULL_TREE)
1872     return NULL;
1873
1874   if (dt == vect_external_def
1875       && TREE_CODE (oprnd1) == SSA_NAME
1876       && is_a <loop_vec_info> (vinfo))
1877     {
1878       struct loop *loop = as_a <loop_vec_info> (vinfo)->loop;
1879       ext_def = loop_preheader_edge (loop);
1880       if (!SSA_NAME_IS_DEFAULT_DEF (oprnd1))
1881         {
1882           basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (oprnd1));
1883           if (bb == NULL
1884               || !dominated_by_p (CDI_DOMINATORS, ext_def->dest, bb))
1885             ext_def = NULL;
1886         }
1887     }
1888
1889   def = NULL_TREE;
1890   if (TREE_CODE (oprnd1) == INTEGER_CST
1891       || TYPE_MODE (TREE_TYPE (oprnd1)) == TYPE_MODE (type))
1892     def = oprnd1;
1893   else if (def_stmt && gimple_assign_cast_p (def_stmt))
1894     {
1895       tree rhs1 = gimple_assign_rhs1 (def_stmt);
1896       if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (type)
1897           && TYPE_PRECISION (TREE_TYPE (rhs1))
1898              == TYPE_PRECISION (type))
1899         def = rhs1;
1900     }
1901
1902   STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
1903   if (def == NULL_TREE)
1904     {
1905       def = vect_recog_temp_ssa_var (type, NULL);
1906       def_stmt = gimple_build_assign (def, NOP_EXPR, oprnd1);
1907       if (ext_def)
1908         {
1909           basic_block new_bb
1910             = gsi_insert_on_edge_immediate (ext_def, def_stmt);
1911           gcc_assert (!new_bb);
1912         }
1913       else
1914         append_pattern_def_seq (stmt_vinfo, def_stmt);
1915     }
1916   stype = TREE_TYPE (def);
1917
1918   if (TREE_CODE (def) == INTEGER_CST)
1919     {
1920       if (!tree_fits_uhwi_p (def)
1921           || tree_to_uhwi (def) >= GET_MODE_PRECISION (TYPE_MODE (type))
1922           || integer_zerop (def))
1923         return NULL;
1924       def2 = build_int_cst (stype,
1925                             GET_MODE_PRECISION (TYPE_MODE (type))
1926                             - tree_to_uhwi (def));
1927     }
1928   else
1929     {
1930       tree vecstype = get_vectype_for_scalar_type (stype);
1931       stmt_vec_info def_stmt_vinfo;
1932
1933       if (vecstype == NULL_TREE)
1934         return NULL;
1935       def2 = vect_recog_temp_ssa_var (stype, NULL);
1936       def_stmt = gimple_build_assign (def2, NEGATE_EXPR, def);
1937       if (ext_def)
1938         {
1939           basic_block new_bb
1940             = gsi_insert_on_edge_immediate (ext_def, def_stmt);
1941           gcc_assert (!new_bb);
1942         }
1943       else
1944         {
1945           def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
1946           set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
1947           STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype;
1948           append_pattern_def_seq (stmt_vinfo, def_stmt);
1949         }
1950
1951       def2 = vect_recog_temp_ssa_var (stype, NULL);
1952       tree mask
1953         = build_int_cst (stype, GET_MODE_PRECISION (TYPE_MODE (stype)) - 1);
1954       def_stmt = gimple_build_assign (def2, BIT_AND_EXPR,
1955                                       gimple_assign_lhs (def_stmt), mask);
1956       if (ext_def)
1957         {
1958           basic_block new_bb
1959             = gsi_insert_on_edge_immediate (ext_def, def_stmt);
1960           gcc_assert (!new_bb);
1961         }
1962       else
1963         {
1964           def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
1965           set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
1966           STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecstype;
1967           append_pattern_def_seq (stmt_vinfo, def_stmt);
1968         }
1969     }
1970
1971   var1 = vect_recog_temp_ssa_var (type, NULL);
1972   def_stmt = gimple_build_assign (var1, rhs_code == LROTATE_EXPR
1973                                         ? LSHIFT_EXPR : RSHIFT_EXPR,
1974                                   oprnd0, def);
1975   append_pattern_def_seq (stmt_vinfo, def_stmt);
1976
1977   var2 = vect_recog_temp_ssa_var (type, NULL);
1978   def_stmt = gimple_build_assign (var2, rhs_code == LROTATE_EXPR
1979                                         ? RSHIFT_EXPR : LSHIFT_EXPR,
1980                                   oprnd0, def2);
1981   append_pattern_def_seq (stmt_vinfo, def_stmt);
1982
1983   /* Pattern detected.  */
1984   if (dump_enabled_p ())
1985     dump_printf_loc (MSG_NOTE, vect_location,
1986                      "vect_recog_rotate_pattern: detected:\n");
1987
1988   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
1989   var = vect_recog_temp_ssa_var (type, NULL);
1990   pattern_stmt = gimple_build_assign (var, BIT_IOR_EXPR, var1, var2);
1991
1992   if (dump_enabled_p ())
1993     dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
1994
1995   stmts->safe_push (last_stmt);
1996   return pattern_stmt;
1997 }
1998
1999 /* Detect a vector by vector shift pattern that wouldn't be otherwise
2000    vectorized:
2001
2002    type a_t;
2003    TYPE b_T, res_T;
2004
2005    S1 a_t = ;
2006    S2 b_T = ;
2007    S3 res_T = b_T op a_t;
2008
2009   where type 'TYPE' is a type with different size than 'type',
2010   and op is <<, >> or rotate.
2011
2012   Also detect cases:
2013
2014    type a_t;
2015    TYPE b_T, c_T, res_T;
2016
2017    S0 c_T = ;
2018    S1 a_t = (type) c_T;
2019    S2 b_T = ;
2020    S3 res_T = b_T op a_t;
2021
2022   Input/Output:
2023
2024   * STMTS: Contains a stmt from which the pattern search begins,
2025     i.e. the shift/rotate stmt.  The original stmt (S3) is replaced
2026     with a shift/rotate which has same type on both operands, in the
2027     second case just b_T op c_T, in the first case with added cast
2028     from a_t to c_T in STMT_VINFO_PATTERN_DEF_SEQ.
2029
2030   Output:
2031
2032   * TYPE_IN: The type of the input arguments to the pattern.
2033
2034   * TYPE_OUT: The type of the output of this pattern.
2035
2036   * Return value: A new stmt that will be used to replace the shift/rotate
2037     S3 stmt.  */
2038
2039 static gimple *
2040 vect_recog_vector_vector_shift_pattern (vec<gimple *> *stmts,
2041                                         tree *type_in, tree *type_out)
2042 {
2043   gimple *last_stmt = stmts->pop ();
2044   tree oprnd0, oprnd1, lhs, var;
2045   gimple *pattern_stmt, *def_stmt;
2046   enum tree_code rhs_code;
2047   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
2048   vec_info *vinfo = stmt_vinfo->vinfo;
2049   enum vect_def_type dt;
2050
2051   if (!is_gimple_assign (last_stmt))
2052     return NULL;
2053
2054   rhs_code = gimple_assign_rhs_code (last_stmt);
2055   switch (rhs_code)
2056     {
2057     case LSHIFT_EXPR:
2058     case RSHIFT_EXPR:
2059     case LROTATE_EXPR:
2060     case RROTATE_EXPR:
2061       break;
2062     default:
2063       return NULL;
2064     }
2065
2066   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
2067     return NULL;
2068
2069   lhs = gimple_assign_lhs (last_stmt);
2070   oprnd0 = gimple_assign_rhs1 (last_stmt);
2071   oprnd1 = gimple_assign_rhs2 (last_stmt);
2072   if (TREE_CODE (oprnd0) != SSA_NAME
2073       || TREE_CODE (oprnd1) != SSA_NAME
2074       || TYPE_MODE (TREE_TYPE (oprnd0)) == TYPE_MODE (TREE_TYPE (oprnd1))
2075       || TYPE_PRECISION (TREE_TYPE (oprnd1))
2076          != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (oprnd1)))
2077       || TYPE_PRECISION (TREE_TYPE (lhs))
2078          != TYPE_PRECISION (TREE_TYPE (oprnd0)))
2079     return NULL;
2080
2081   if (!vect_is_simple_use (oprnd1, vinfo, &def_stmt, &dt))
2082     return NULL;
2083
2084   if (dt != vect_internal_def)
2085     return NULL;
2086
2087   *type_in = get_vectype_for_scalar_type (TREE_TYPE (oprnd0));
2088   *type_out = *type_in;
2089   if (*type_in == NULL_TREE)
2090     return NULL;
2091
2092   tree def = NULL_TREE;
2093   if (gimple_assign_cast_p (def_stmt))
2094     {
2095       tree rhs1 = gimple_assign_rhs1 (def_stmt);
2096       if (TYPE_MODE (TREE_TYPE (rhs1)) == TYPE_MODE (TREE_TYPE (oprnd0))
2097           && TYPE_PRECISION (TREE_TYPE (rhs1))
2098              == TYPE_PRECISION (TREE_TYPE (oprnd0)))
2099         def = rhs1;
2100     }
2101
2102   if (def == NULL_TREE)
2103     {
2104       def = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
2105       def_stmt = gimple_build_assign (def, NOP_EXPR, oprnd1);
2106       new_pattern_def_seq (stmt_vinfo, def_stmt);
2107     }
2108
2109   /* Pattern detected.  */
2110   if (dump_enabled_p ())
2111     dump_printf_loc (MSG_NOTE, vect_location,
2112                      "vect_recog_vector_vector_shift_pattern: detected:\n");
2113
2114   /* Pattern supported.  Create a stmt to be used to replace the pattern.  */
2115   var = vect_recog_temp_ssa_var (TREE_TYPE (oprnd0), NULL);
2116   pattern_stmt = gimple_build_assign (var, rhs_code, oprnd0, def);
2117
2118   if (dump_enabled_p ())
2119     dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt, 0);
2120
2121   stmts->safe_push (last_stmt);
2122   return pattern_stmt;
2123 }
2124
2125 /* Detect multiplication by constant which are postive or negatives of power 2,
2126    and convert them to shift patterns.
2127
2128    Mult with constants that are postive power of two.
2129    type a_t;
2130    type b_t
2131    S1: b_t = a_t * n
2132
2133    or
2134
2135    Mult with constants that are negative power of two.
2136    S2: b_t = a_t * -n
2137
2138    Input/Output:
2139
2140    STMTS: Contains a stmt from which the pattern search begins,
2141    i.e. the mult stmt.  Convert the mult operation to LSHIFT if
2142    constant operand is a power of 2.
2143    type a_t, b_t
2144    S1': b_t = a_t << log2 (n)
2145
2146    Convert the mult operation to LSHIFT and followed by a NEGATE
2147    if constant operand is a negative power of 2.
2148    type a_t, b_t, res_T;
2149    S2': b_t = a_t << log2 (n)
2150    S3': res_T  = - (b_t)
2151
2152  Output:
2153
2154   * TYPE_IN: The type of the input arguments to the pattern.
2155
2156   * TYPE_OUT: The type of the output of this pattern.
2157
2158   * Return value: A new stmt that will be used to replace the multiplication
2159     S1 or S2 stmt.  */
2160
2161 static gimple *
2162 vect_recog_mult_pattern (vec<gimple *> *stmts,
2163                          tree *type_in, tree *type_out)
2164 {
2165   gimple *last_stmt = stmts->pop ();
2166   tree oprnd0, oprnd1, vectype, itype;
2167   gimple *pattern_stmt, *def_stmt;
2168   optab optab;
2169   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
2170   int power2_val, power2_neg_val;
2171   tree shift;
2172
2173   if (!is_gimple_assign (last_stmt))
2174     return NULL;
2175
2176   if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)
2177     return NULL;
2178
2179   oprnd0 = gimple_assign_rhs1 (last_stmt);
2180   oprnd1 = gimple_assign_rhs2 (last_stmt);
2181   itype = TREE_TYPE (oprnd0);
2182
2183   if (TREE_CODE (oprnd0) != SSA_NAME
2184       || TREE_CODE (oprnd1) != INTEGER_CST
2185       || !INTEGRAL_TYPE_P (itype)
2186       || TYPE_PRECISION (itype) != GET_MODE_PRECISION (TYPE_MODE (itype)))
2187     return NULL;
2188
2189   vectype = get_vectype_for_scalar_type (itype);
2190   if (vectype == NULL_TREE)
2191     return NULL;
2192
2193   /* If the target can handle vectorized multiplication natively,
2194      don't attempt to optimize this.  */
2195   optab = optab_for_tree_code (MULT_EXPR, vectype, optab_default);
2196   if (optab != unknown_optab)
2197     {
2198       machine_mode vec_mode = TYPE_MODE (vectype);
2199       int icode = (int) optab_handler (optab, vec_mode);
2200       if (icode != CODE_FOR_nothing)
2201         return NULL;
2202     }
2203
2204   /* If target cannot handle vector left shift then we cannot
2205      optimize and bail out.  */
2206   optab = optab_for_tree_code (LSHIFT_EXPR, vectype, optab_vector);
2207   if (!optab
2208       || optab_handler (optab, TYPE_MODE (vectype)) == CODE_FOR_nothing)
2209     return NULL;
2210
2211   power2_val = wi::exact_log2 (oprnd1);
2212   power2_neg_val = wi::exact_log2 (wi::neg (oprnd1));
2213
2214   /* Handle constant operands that are postive or negative powers of 2.  */
2215   if (power2_val != -1)
2216     {
2217       shift = build_int_cst (itype, power2_val);
2218       pattern_stmt
2219         = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2220                                LSHIFT_EXPR, oprnd0, shift);
2221     }
2222   else if (power2_neg_val != -1)
2223     {
2224       /* If the target cannot handle vector NEGATE then we cannot
2225          do the optimization.  */
2226       optab = optab_for_tree_code (NEGATE_EXPR, vectype, optab_vector);
2227       if (!optab
2228           || optab_handler (optab, TYPE_MODE (vectype)) == CODE_FOR_nothing)
2229         return NULL;
2230
2231       shift = build_int_cst (itype, power2_neg_val);
2232       def_stmt
2233         = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2234                                LSHIFT_EXPR, oprnd0, shift);
2235       new_pattern_def_seq (stmt_vinfo, def_stmt);
2236       pattern_stmt
2237          = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2238                                 NEGATE_EXPR, gimple_assign_lhs (def_stmt));
2239     }
2240   else
2241     return NULL;
2242
2243   /* Pattern detected.  */
2244   if (dump_enabled_p ())
2245     dump_printf_loc (MSG_NOTE, vect_location,
2246                      "vect_recog_mult_pattern: detected:\n");
2247
2248   if (dump_enabled_p ())
2249     dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM,
2250                           pattern_stmt,0);
2251
2252   stmts->safe_push (last_stmt);
2253   *type_in = vectype;
2254   *type_out = vectype;
2255
2256   return pattern_stmt;
2257 }
2258
2259 /* Detect a signed division by a constant that wouldn't be
2260    otherwise vectorized:
2261
2262    type a_t, b_t;
2263
2264    S1 a_t = b_t / N;
2265
2266   where type 'type' is an integral type and N is a constant.
2267
2268   Similarly handle modulo by a constant:
2269
2270    S4 a_t = b_t % N;
2271
2272   Input/Output:
2273
2274   * STMTS: Contains a stmt from which the pattern search begins,
2275     i.e. the division stmt.  S1 is replaced by if N is a power
2276     of two constant and type is signed:
2277   S3  y_t = b_t < 0 ? N - 1 : 0;
2278   S2  x_t = b_t + y_t;
2279   S1' a_t = x_t >> log2 (N);
2280
2281     S4 is replaced if N is a power of two constant and
2282     type is signed by (where *_T temporaries have unsigned type):
2283   S9  y_T = b_t < 0 ? -1U : 0U;
2284   S8  z_T = y_T >> (sizeof (type_t) * CHAR_BIT - log2 (N));
2285   S7  z_t = (type) z_T;
2286   S6  w_t = b_t + z_t;
2287   S5  x_t = w_t & (N - 1);
2288   S4' a_t = x_t - z_t;
2289
2290   Output:
2291
2292   * TYPE_IN: The type of the input arguments to the pattern.
2293
2294   * TYPE_OUT: The type of the output of this pattern.
2295
2296   * Return value: A new stmt that will be used to replace the division
2297     S1 or modulo S4 stmt.  */
2298
2299 static gimple *
2300 vect_recog_divmod_pattern (vec<gimple *> *stmts,
2301                            tree *type_in, tree *type_out)
2302 {
2303   gimple *last_stmt = stmts->pop ();
2304   tree oprnd0, oprnd1, vectype, itype, cond;
2305   gimple *pattern_stmt, *def_stmt;
2306   enum tree_code rhs_code;
2307   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
2308   vec_info *vinfo = stmt_vinfo->vinfo;
2309   optab optab;
2310   tree q;
2311   int dummy_int, prec;
2312   stmt_vec_info def_stmt_vinfo;
2313
2314   if (!is_gimple_assign (last_stmt))
2315     return NULL;
2316
2317   rhs_code = gimple_assign_rhs_code (last_stmt);
2318   switch (rhs_code)
2319     {
2320     case TRUNC_DIV_EXPR:
2321     case TRUNC_MOD_EXPR:
2322       break;
2323     default:
2324       return NULL;
2325     }
2326
2327   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
2328     return NULL;
2329
2330   oprnd0 = gimple_assign_rhs1 (last_stmt);
2331   oprnd1 = gimple_assign_rhs2 (last_stmt);
2332   itype = TREE_TYPE (oprnd0);
2333   if (TREE_CODE (oprnd0) != SSA_NAME
2334       || TREE_CODE (oprnd1) != INTEGER_CST
2335       || TREE_CODE (itype) != INTEGER_TYPE
2336       || TYPE_PRECISION (itype) != GET_MODE_PRECISION (TYPE_MODE (itype)))
2337     return NULL;
2338
2339   vectype = get_vectype_for_scalar_type (itype);
2340   if (vectype == NULL_TREE)
2341     return NULL;
2342
2343   /* If the target can handle vectorized division or modulo natively,
2344      don't attempt to optimize this.  */
2345   optab = optab_for_tree_code (rhs_code, vectype, optab_default);
2346   if (optab != unknown_optab)
2347     {
2348       machine_mode vec_mode = TYPE_MODE (vectype);
2349       int icode = (int) optab_handler (optab, vec_mode);
2350       if (icode != CODE_FOR_nothing)
2351         return NULL;
2352     }
2353
2354   prec = TYPE_PRECISION (itype);
2355   if (integer_pow2p (oprnd1))
2356     {
2357       if (TYPE_UNSIGNED (itype) || tree_int_cst_sgn (oprnd1) != 1)
2358         return NULL;
2359
2360       /* Pattern detected.  */
2361       if (dump_enabled_p ())
2362         dump_printf_loc (MSG_NOTE, vect_location,
2363                          "vect_recog_divmod_pattern: detected:\n");
2364
2365       cond = build2 (LT_EXPR, boolean_type_node, oprnd0,
2366                      build_int_cst (itype, 0));
2367       if (rhs_code == TRUNC_DIV_EXPR)
2368         {
2369           tree var = vect_recog_temp_ssa_var (itype, NULL);
2370           tree shift;
2371           def_stmt
2372             = gimple_build_assign (var, COND_EXPR, cond,
2373                                    fold_build2 (MINUS_EXPR, itype, oprnd1,
2374                                                 build_int_cst (itype, 1)),
2375                                    build_int_cst (itype, 0));
2376           new_pattern_def_seq (stmt_vinfo, def_stmt);
2377           var = vect_recog_temp_ssa_var (itype, NULL);
2378           def_stmt
2379             = gimple_build_assign (var, PLUS_EXPR, oprnd0,
2380                                    gimple_assign_lhs (def_stmt));
2381           append_pattern_def_seq (stmt_vinfo, def_stmt);
2382
2383           shift = build_int_cst (itype, tree_log2 (oprnd1));
2384           pattern_stmt
2385             = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2386                                    RSHIFT_EXPR, var, shift);
2387         }
2388       else
2389         {
2390           tree signmask;
2391           STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
2392           if (compare_tree_int (oprnd1, 2) == 0)
2393             {
2394               signmask = vect_recog_temp_ssa_var (itype, NULL);
2395               def_stmt = gimple_build_assign (signmask, COND_EXPR, cond,
2396                                               build_int_cst (itype, 1),
2397                                               build_int_cst (itype, 0));
2398               append_pattern_def_seq (stmt_vinfo, def_stmt);
2399             }
2400           else
2401             {
2402               tree utype
2403                 = build_nonstandard_integer_type (prec, 1);
2404               tree vecutype = get_vectype_for_scalar_type (utype);
2405               tree shift
2406                 = build_int_cst (utype, GET_MODE_BITSIZE (TYPE_MODE (itype))
2407                                         - tree_log2 (oprnd1));
2408               tree var = vect_recog_temp_ssa_var (utype, NULL);
2409
2410               def_stmt = gimple_build_assign (var, COND_EXPR, cond,
2411                                               build_int_cst (utype, -1),
2412                                               build_int_cst (utype, 0));
2413               def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
2414               set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
2415               STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype;
2416               append_pattern_def_seq (stmt_vinfo, def_stmt);
2417               var = vect_recog_temp_ssa_var (utype, NULL);
2418               def_stmt = gimple_build_assign (var, RSHIFT_EXPR,
2419                                               gimple_assign_lhs (def_stmt),
2420                                               shift);
2421               def_stmt_vinfo = new_stmt_vec_info (def_stmt, vinfo);
2422               set_vinfo_for_stmt (def_stmt, def_stmt_vinfo);
2423               STMT_VINFO_VECTYPE (def_stmt_vinfo) = vecutype;
2424               append_pattern_def_seq (stmt_vinfo, def_stmt);
2425               signmask = vect_recog_temp_ssa_var (itype, NULL);
2426               def_stmt
2427                 = gimple_build_assign (signmask, NOP_EXPR, var);
2428               append_pattern_def_seq (stmt_vinfo, def_stmt);
2429             }
2430           def_stmt
2431             = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2432                                    PLUS_EXPR, oprnd0, signmask);
2433           append_pattern_def_seq (stmt_vinfo, def_stmt);
2434           def_stmt
2435             = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2436                                    BIT_AND_EXPR, gimple_assign_lhs (def_stmt),
2437                                    fold_build2 (MINUS_EXPR, itype, oprnd1,
2438                                                 build_int_cst (itype, 1)));
2439           append_pattern_def_seq (stmt_vinfo, def_stmt);
2440
2441           pattern_stmt
2442             = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2443                                    MINUS_EXPR, gimple_assign_lhs (def_stmt),
2444                                    signmask);
2445         }
2446
2447       if (dump_enabled_p ())
2448         dump_gimple_stmt_loc (MSG_NOTE, vect_location, TDF_SLIM, pattern_stmt,
2449                               0);
2450
2451       stmts->safe_push (last_stmt);
2452
2453       *type_in = vectype;
2454       *type_out = vectype;
2455       return pattern_stmt;
2456     }
2457
2458   if (prec > HOST_BITS_PER_WIDE_INT
2459       || integer_zerop (oprnd1))
2460     return NULL;
2461
2462   if (!can_mult_highpart_p (TYPE_MODE (vectype), TYPE_UNSIGNED (itype)))
2463     return NULL;
2464
2465   STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo) = NULL;
2466
2467   if (TYPE_UNSIGNED (itype))
2468     {
2469       unsigned HOST_WIDE_INT mh, ml;
2470       int pre_shift, post_shift;
2471       unsigned HOST_WIDE_INT d = (TREE_INT_CST_LOW (oprnd1)
2472                                   & GET_MODE_MASK (TYPE_MODE (itype)));
2473       tree t1, t2, t3, t4;
2474
2475       if (d >= ((unsigned HOST_WIDE_INT) 1 << (prec - 1)))
2476         /* FIXME: Can transform this into oprnd0 >= oprnd1 ? 1 : 0.  */
2477         return NULL;
2478
2479       /* Find a suitable multiplier and right shift count
2480          instead of multiplying with D.  */
2481       mh = choose_multiplier (d, prec, prec, &ml, &post_shift, &dummy_int);
2482
2483       /* If the suggested multiplier is more than SIZE bits, we can do better
2484          for even divisors, using an initial right shift.  */
2485       if (mh != 0 && (d & 1) == 0)
2486         {
2487           pre_shift = floor_log2 (d & -d);
2488           mh = choose_multiplier (d >> pre_shift, prec, prec - pre_shift,
2489                                   &ml, &post_shift, &dummy_int);
2490           gcc_assert (!mh);
2491         }
2492       else
2493         pre_shift = 0;
2494
2495       if (mh != 0)
2496         {
2497           if (post_shift - 1 >= prec)
2498             return NULL;
2499
2500           /* t1 = oprnd0 h* ml;
2501              t2 = oprnd0 - t1;
2502              t3 = t2 >> 1;
2503              t4 = t1 + t3;
2504              q = t4 >> (post_shift - 1);  */
2505           t1 = vect_recog_temp_ssa_var (itype, NULL);
2506           def_stmt = gimple_build_assign (t1, MULT_HIGHPART_EXPR, oprnd0,
2507                                           build_int_cst (itype, ml));
2508           append_pattern_def_seq (stmt_vinfo, def_stmt);
2509
2510           t2 = vect_recog_temp_ssa_var (itype, NULL);
2511           def_stmt
2512             = gimple_build_assign (t2, MINUS_EXPR, oprnd0, t1);
2513           append_pattern_def_seq (stmt_vinfo, def_stmt);
2514
2515           t3 = vect_recog_temp_ssa_var (itype, NULL);
2516           def_stmt
2517             = gimple_build_assign (t3, RSHIFT_EXPR, t2, integer_one_node);
2518           append_pattern_def_seq (stmt_vinfo, def_stmt);
2519
2520           t4 = vect_recog_temp_ssa_var (itype, NULL);
2521           def_stmt
2522             = gimple_build_assign (t4, PLUS_EXPR, t1, t3);
2523
2524           if (post_shift != 1)
2525             {
2526               append_pattern_def_seq (stmt_vinfo, def_stmt);
2527
2528               q = vect_recog_temp_ssa_var (itype, NULL);
2529               pattern_stmt
2530                 = gimple_build_assign (q, RSHIFT_EXPR, t4,
2531                                        build_int_cst (itype, post_shift - 1));
2532             }
2533           else
2534             {
2535               q = t4;
2536               pattern_stmt = def_stmt;
2537             }
2538         }
2539       else
2540         {
2541           if (pre_shift >= prec || post_shift >= prec)
2542             return NULL;
2543
2544           /* t1 = oprnd0 >> pre_shift;
2545              t2 = t1 h* ml;
2546              q = t2 >> post_shift;  */
2547           if (pre_shift)
2548             {
2549               t1 = vect_recog_temp_ssa_var (itype, NULL);
2550               def_stmt
2551                 = gimple_build_assign (t1, RSHIFT_EXPR, oprnd0,
2552                                        build_int_cst (NULL, pre_shift));
2553               append_pattern_def_seq (stmt_vinfo, def_stmt);
2554             }
2555           else
2556             t1 = oprnd0;
2557
2558           t2 = vect_recog_temp_ssa_var (itype, NULL);
2559           def_stmt = gimple_build_assign (t2, MULT_HIGHPART_EXPR, t1,
2560                                           build_int_cst (itype, ml));
2561
2562           if (post_shift)
2563             {
2564               append_pattern_def_seq (stmt_vinfo, def_stmt);
2565
2566               q = vect_recog_temp_ssa_var (itype, NULL);
2567               def_stmt
2568                 = gimple_build_assign (q, RSHIFT_EXPR, t2,
2569                                        build_int_cst (itype, post_shift));
2570             }
2571           else
2572             q = t2;
2573
2574           pattern_stmt = def_stmt;
2575         }
2576     }
2577   else
2578     {
2579       unsigned HOST_WIDE_INT ml;
2580       int post_shift;
2581       HOST_WIDE_INT d = TREE_INT_CST_LOW (oprnd1);
2582       unsigned HOST_WIDE_INT abs_d;
2583       bool add = false;
2584       tree t1, t2, t3, t4;
2585
2586       /* Give up for -1.  */
2587       if (d == -1)
2588         return NULL;
2589
2590       /* Since d might be INT_MIN, we have to cast to
2591          unsigned HOST_WIDE_INT before negating to avoid
2592          undefined signed overflow.  */
2593       abs_d = (d >= 0
2594                ? (unsigned HOST_WIDE_INT) d
2595                : - (unsigned HOST_WIDE_INT) d);
2596
2597       /* n rem d = n rem -d */
2598       if (rhs_code == TRUNC_MOD_EXPR && d < 0)
2599         {
2600           d = abs_d;
2601           oprnd1 = build_int_cst (itype, abs_d);
2602         }
2603       else if (HOST_BITS_PER_WIDE_INT >= prec
2604                && abs_d == (unsigned HOST_WIDE_INT) 1 << (prec - 1))
2605         /* This case is not handled correctly below.  */
2606         return NULL;
2607
2608       choose_multiplier (abs_d, prec, prec - 1, &ml, &post_shift, &dummy_int);
2609       if (ml >= (unsigned HOST_WIDE_INT) 1 << (prec - 1))
2610         {
2611           add = true;
2612           ml |= (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
2613         }
2614       if (post_shift >= prec)
2615         return NULL;
2616
2617       /* t1 = oprnd0 h* ml;  */
2618       t1 = vect_recog_temp_ssa_var (itype, NULL);
2619       def_stmt = gimple_build_assign (t1, MULT_HIGHPART_EXPR, oprnd0,
2620                                       build_int_cst (itype, ml));
2621
2622       if (add)
2623         {
2624           /* t2 = t1 + oprnd0;  */
2625           append_pattern_def_seq (stmt_vinfo, def_stmt);
2626           t2 = vect_recog_temp_ssa_var (itype, NULL);
2627           def_stmt = gimple_build_assign (t2, PLUS_EXPR, t1, oprnd0);
2628         }
2629       else
2630         t2 = t1;
2631
2632       if (post_shift)
2633         {
2634           /* t3 = t2 >> post_shift;  */
2635           append_pattern_def_seq (stmt_vinfo, def_stmt);
2636           t3 = vect_recog_temp_ssa_var (itype, NULL);
2637           def_stmt = gimple_build_assign (t3, RSHIFT_EXPR, t2,
2638                                           build_int_cst (itype, post_shift));
2639         }
2640       else
2641         t3 = t2;
2642
2643       wide_int oprnd0_min, oprnd0_max;
2644       int msb = 1;
2645       if (get_range_info (oprnd0, &oprnd0_min, &oprnd0_max) == VR_RANGE)
2646         {
2647           if (!wi::neg_p (oprnd0_min, TYPE_SIGN (itype)))
2648             msb = 0;
2649           else if (wi::neg_p (oprnd0_max, TYPE_SIGN (itype)))
2650             msb = -1;
2651         }
2652
2653       if (msb == 0 && d >= 0)
2654         {
2655           /* q = t3;  */
2656           q = t3;
2657           pattern_stmt = def_stmt;
2658         }
2659       else
2660         {
2661           /* t4 = oprnd0 >> (prec - 1);
2662              or if we know from VRP that oprnd0 >= 0
2663              t4 = 0;
2664              or if we know from VRP that oprnd0 < 0
2665              t4 = -1;  */
2666           append_pattern_def_seq (stmt_vinfo, def_stmt);
2667           t4 = vect_recog_temp_ssa_var (itype, NULL);
2668           if (msb != 1)
2669             def_stmt = gimple_build_assign (t4, INTEGER_CST,
2670                                             build_int_cst (itype, msb));
2671           else
2672             def_stmt = gimple_build_assign (t4, RSHIFT_EXPR, oprnd0,
2673                                             build_int_cst (itype, prec - 1));
2674           append_pattern_def_seq (stmt_vinfo, def_stmt);
2675
2676           /* q = t3 - t4;  or q = t4 - t3;  */
2677           q = vect_recog_temp_ssa_var (itype, NULL);
2678           pattern_stmt = gimple_build_assign (q, MINUS_EXPR, d < 0 ? t4 : t3,
2679                                               d < 0 ? t3 : t4);
2680         }
2681     }
2682
2683   if (rhs_code == TRUNC_MOD_EXPR)
2684     {
2685       tree r, t1;
2686
2687       /* We divided.  Now finish by:
2688          t1 = q * oprnd1;
2689          r = oprnd0 - t1;  */
2690       append_pattern_def_seq (stmt_vinfo, pattern_stmt);
2691
2692       t1 = vect_recog_temp_ssa_var (itype, NULL);
2693       def_stmt = gimple_build_assign (t1, MULT_EXPR, q, oprnd1);
2694       append_pattern_def_seq (stmt_vinfo, def_stmt);
2695
2696       r = vect_recog_temp_ssa_var (itype, NULL);
2697       pattern_stmt = gimple_build_assign (r, MINUS_EXPR, oprnd0, t1);
2698     }
2699
2700   /* Pattern detected.  */
2701   if (dump_enabled_p ())
2702     {
2703       dump_printf_loc (MSG_NOTE, vect_location,
2704                        "vect_recog_divmod_pattern: detected: ");
2705       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
2706       dump_printf (MSG_NOTE, "\n");
2707     }
2708
2709   stmts->safe_push (last_stmt);
2710
2711   *type_in = vectype;
2712   *type_out = vectype;
2713   return pattern_stmt;
2714 }
2715
2716 /* Function vect_recog_mixed_size_cond_pattern
2717
2718    Try to find the following pattern:
2719
2720      type x_t, y_t;
2721      TYPE a_T, b_T, c_T;
2722    loop:
2723      S1  a_T = x_t CMP y_t ? b_T : c_T;
2724
2725    where type 'TYPE' is an integral type which has different size
2726    from 'type'.  b_T and c_T are either constants (and if 'TYPE' is wider
2727    than 'type', the constants need to fit into an integer type
2728    with the same width as 'type') or results of conversion from 'type'.
2729
2730    Input:
2731
2732    * LAST_STMT: A stmt from which the pattern search begins.
2733
2734    Output:
2735
2736    * TYPE_IN: The type of the input arguments to the pattern.
2737
2738    * TYPE_OUT: The type of the output of this pattern.
2739
2740    * Return value: A new stmt that will be used to replace the pattern.
2741         Additionally a def_stmt is added.
2742
2743         a_it = x_t CMP y_t ? b_it : c_it;
2744         a_T = (TYPE) a_it;  */
2745
2746 static gimple *
2747 vect_recog_mixed_size_cond_pattern (vec<gimple *> *stmts, tree *type_in,
2748                                     tree *type_out)
2749 {
2750   gimple *last_stmt = (*stmts)[0];
2751   tree cond_expr, then_clause, else_clause;
2752   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt), def_stmt_info;
2753   tree type, vectype, comp_vectype, itype = NULL_TREE, vecitype;
2754   gimple *pattern_stmt, *def_stmt;
2755   vec_info *vinfo = stmt_vinfo->vinfo;
2756   tree orig_type0 = NULL_TREE, orig_type1 = NULL_TREE;
2757   gimple *def_stmt0 = NULL, *def_stmt1 = NULL;
2758   bool promotion;
2759   tree comp_scalar_type;
2760
2761   if (!is_gimple_assign (last_stmt)
2762       || gimple_assign_rhs_code (last_stmt) != COND_EXPR
2763       || STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
2764     return NULL;
2765
2766   cond_expr = gimple_assign_rhs1 (last_stmt);
2767   then_clause = gimple_assign_rhs2 (last_stmt);
2768   else_clause = gimple_assign_rhs3 (last_stmt);
2769
2770   if (!COMPARISON_CLASS_P (cond_expr))
2771     return NULL;
2772
2773   comp_scalar_type = TREE_TYPE (TREE_OPERAND (cond_expr, 0));
2774   comp_vectype = get_vectype_for_scalar_type (comp_scalar_type);
2775   if (comp_vectype == NULL_TREE)
2776     return NULL;
2777
2778   type = gimple_expr_type (last_stmt);
2779   if (types_compatible_p (type, comp_scalar_type)
2780       || ((TREE_CODE (then_clause) != INTEGER_CST
2781            || TREE_CODE (else_clause) != INTEGER_CST)
2782           && !INTEGRAL_TYPE_P (comp_scalar_type))
2783       || !INTEGRAL_TYPE_P (type))
2784     return NULL;
2785
2786   if ((TREE_CODE (then_clause) != INTEGER_CST
2787        && !type_conversion_p (then_clause, last_stmt, false, &orig_type0,
2788                               &def_stmt0, &promotion))
2789       || (TREE_CODE (else_clause) != INTEGER_CST
2790           && !type_conversion_p (else_clause, last_stmt, false, &orig_type1,
2791                                  &def_stmt1, &promotion)))
2792     return NULL;
2793
2794   if (orig_type0 && orig_type1
2795       && !types_compatible_p (orig_type0, orig_type1))
2796     return NULL;
2797
2798   if (orig_type0)
2799     {
2800       if (!types_compatible_p (orig_type0, comp_scalar_type))
2801         return NULL;
2802       then_clause = gimple_assign_rhs1 (def_stmt0);
2803       itype = orig_type0;
2804     }
2805
2806   if (orig_type1)
2807     {
2808       if (!types_compatible_p (orig_type1, comp_scalar_type))
2809         return NULL;
2810       else_clause = gimple_assign_rhs1 (def_stmt1);
2811       itype = orig_type1;
2812     }
2813
2814
2815   HOST_WIDE_INT cmp_mode_size
2816     = GET_MODE_UNIT_BITSIZE (TYPE_MODE (comp_vectype));
2817
2818   if (GET_MODE_BITSIZE (TYPE_MODE (type)) == cmp_mode_size)
2819     return NULL;
2820
2821   vectype = get_vectype_for_scalar_type (type);
2822   if (vectype == NULL_TREE)
2823     return NULL;
2824
2825   if (expand_vec_cond_expr_p (vectype, comp_vectype))
2826     return NULL;
2827
2828   if (itype == NULL_TREE)
2829     itype = build_nonstandard_integer_type (cmp_mode_size,
2830                                             TYPE_UNSIGNED (type));
2831
2832   if (itype == NULL_TREE
2833       || GET_MODE_BITSIZE (TYPE_MODE (itype)) != cmp_mode_size)
2834     return NULL;
2835
2836   vecitype = get_vectype_for_scalar_type (itype);
2837   if (vecitype == NULL_TREE)
2838     return NULL;
2839
2840   if (!expand_vec_cond_expr_p (vecitype, comp_vectype))
2841     return NULL;
2842
2843   if (GET_MODE_BITSIZE (TYPE_MODE (type)) > cmp_mode_size)
2844     {
2845       if ((TREE_CODE (then_clause) == INTEGER_CST
2846            && !int_fits_type_p (then_clause, itype))
2847           || (TREE_CODE (else_clause) == INTEGER_CST
2848               && !int_fits_type_p (else_clause, itype)))
2849         return NULL;
2850     }
2851
2852   def_stmt = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
2853                                   COND_EXPR, unshare_expr (cond_expr),
2854                                   fold_convert (itype, then_clause),
2855                                   fold_convert (itype, else_clause));
2856   pattern_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL),
2857                                       NOP_EXPR, gimple_assign_lhs (def_stmt));
2858
2859   new_pattern_def_seq (stmt_vinfo, def_stmt);
2860   def_stmt_info = new_stmt_vec_info (def_stmt, vinfo);
2861   set_vinfo_for_stmt (def_stmt, def_stmt_info);
2862   STMT_VINFO_VECTYPE (def_stmt_info) = vecitype;
2863   *type_in = vecitype;
2864   *type_out = vectype;
2865
2866   if (dump_enabled_p ())
2867     dump_printf_loc (MSG_NOTE, vect_location,
2868                      "vect_recog_mixed_size_cond_pattern: detected:\n");
2869
2870   return pattern_stmt;
2871 }
2872
2873
2874 /* Helper function of vect_recog_bool_pattern.  Called recursively, return
2875    true if bool VAR can and should be optimized that way.  Assume it shouldn't
2876    in case it's a result of a comparison which can be directly vectorized into
2877    a vector comparison.  */
2878
2879 static bool
2880 check_bool_pattern (tree var, vec_info *vinfo)
2881 {
2882   gimple *def_stmt;
2883   enum vect_def_type dt;
2884   tree rhs1;
2885   enum tree_code rhs_code;
2886
2887   if (!vect_is_simple_use (var, vinfo, &def_stmt, &dt))
2888     return false;
2889
2890   if (dt != vect_internal_def)
2891     return false;
2892
2893   if (!is_gimple_assign (def_stmt))
2894     return false;
2895
2896   if (!has_single_use (var))
2897     return false;
2898
2899   rhs1 = gimple_assign_rhs1 (def_stmt);
2900   rhs_code = gimple_assign_rhs_code (def_stmt);
2901   switch (rhs_code)
2902     {
2903     case SSA_NAME:
2904       return check_bool_pattern (rhs1, vinfo);
2905
2906     CASE_CONVERT:
2907       if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2908            || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2909           && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
2910         return false;
2911       return check_bool_pattern (rhs1, vinfo);
2912
2913     case BIT_NOT_EXPR:
2914       return check_bool_pattern (rhs1, vinfo);
2915
2916     case BIT_AND_EXPR:
2917     case BIT_IOR_EXPR:
2918     case BIT_XOR_EXPR:
2919       if (!check_bool_pattern (rhs1, vinfo))
2920         return false;
2921       return check_bool_pattern (gimple_assign_rhs2 (def_stmt), vinfo);
2922
2923     default:
2924       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
2925         {
2926           tree vecitype, comp_vectype, mask_type;
2927
2928           /* If the comparison can throw, then is_gimple_condexpr will be
2929              false and we can't make a COND_EXPR/VEC_COND_EXPR out of it.  */
2930           if (stmt_could_throw_p (def_stmt))
2931             return false;
2932
2933           comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
2934           if (comp_vectype == NULL_TREE)
2935             return false;
2936
2937           mask_type = get_mask_type_for_scalar_type (TREE_TYPE (rhs1));
2938           if (mask_type
2939               && expand_vec_cmp_expr_p (comp_vectype, mask_type))
2940             return false;
2941
2942           if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE)
2943             {
2944               machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
2945               tree itype
2946                 = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
2947               vecitype = get_vectype_for_scalar_type (itype);
2948               if (vecitype == NULL_TREE)
2949                 return false;
2950             }
2951           else
2952             vecitype = comp_vectype;
2953           return expand_vec_cond_expr_p (vecitype, comp_vectype);
2954         }
2955       return false;
2956     }
2957 }
2958
2959
2960 /* Helper function of adjust_bool_pattern.  Add a cast to TYPE to a previous
2961    stmt (SSA_NAME_DEF_STMT of VAR) by moving the COND_EXPR from RELATED_STMT
2962    to PATTERN_DEF_SEQ and adding a cast as RELATED_STMT.  */
2963
2964 static tree
2965 adjust_bool_pattern_cast (tree type, tree var)
2966 {
2967   stmt_vec_info stmt_vinfo = vinfo_for_stmt (SSA_NAME_DEF_STMT (var));
2968   gimple *cast_stmt, *pattern_stmt;
2969
2970   gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_vinfo));
2971   pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
2972   new_pattern_def_seq (stmt_vinfo, pattern_stmt);
2973   cast_stmt = gimple_build_assign (vect_recog_temp_ssa_var (type, NULL),
2974                                    NOP_EXPR, gimple_assign_lhs (pattern_stmt));
2975   STMT_VINFO_RELATED_STMT (stmt_vinfo) = cast_stmt;
2976   return gimple_assign_lhs (cast_stmt);
2977 }
2978
2979
2980 /* Helper function of vect_recog_bool_pattern.  Do the actual transformations,
2981    recursively.  VAR is an SSA_NAME that should be transformed from bool
2982    to a wider integer type, OUT_TYPE is the desired final integer type of
2983    the whole pattern, TRUEVAL should be NULL unless optimizing
2984    BIT_AND_EXPR into a COND_EXPR with one integer from one of the operands
2985    in the then_clause, STMTS is where statements with added pattern stmts
2986    should be pushed to.  */
2987
2988 static tree
2989 adjust_bool_pattern (tree var, tree out_type, tree trueval,
2990                      vec<gimple *> *stmts)
2991 {
2992   gimple *stmt = SSA_NAME_DEF_STMT (var);
2993   enum tree_code rhs_code, def_rhs_code;
2994   tree itype, cond_expr, rhs1, rhs2, irhs1, irhs2;
2995   location_t loc;
2996   gimple *pattern_stmt, *def_stmt;
2997
2998   rhs1 = gimple_assign_rhs1 (stmt);
2999   rhs2 = gimple_assign_rhs2 (stmt);
3000   rhs_code = gimple_assign_rhs_code (stmt);
3001   loc = gimple_location (stmt);
3002   switch (rhs_code)
3003     {
3004     case SSA_NAME:
3005     CASE_CONVERT:
3006       irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
3007       itype = TREE_TYPE (irhs1);
3008       pattern_stmt
3009         = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
3010                                SSA_NAME, irhs1);
3011       break;
3012
3013     case BIT_NOT_EXPR:
3014       irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
3015       itype = TREE_TYPE (irhs1);
3016       pattern_stmt
3017         = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
3018                                BIT_XOR_EXPR, irhs1, build_int_cst (itype, 1));
3019       break;
3020
3021     case BIT_AND_EXPR:
3022       /* Try to optimize x = y & (a < b ? 1 : 0); into
3023          x = (a < b ? y : 0);
3024
3025          E.g. for:
3026            bool a_b, b_b, c_b;
3027            TYPE d_T;
3028
3029            S1  a_b = x1 CMP1 y1;
3030            S2  b_b = x2 CMP2 y2;
3031            S3  c_b = a_b & b_b;
3032            S4  d_T = (TYPE) c_b;
3033
3034          we would normally emit:
3035
3036            S1'  a_T = x1 CMP1 y1 ? 1 : 0;
3037            S2'  b_T = x2 CMP2 y2 ? 1 : 0;
3038            S3'  c_T = a_T & b_T;
3039            S4'  d_T = c_T;
3040
3041          but we can save one stmt by using the
3042          result of one of the COND_EXPRs in the other COND_EXPR and leave
3043          BIT_AND_EXPR stmt out:
3044
3045            S1'  a_T = x1 CMP1 y1 ? 1 : 0;
3046            S3'  c_T = x2 CMP2 y2 ? a_T : 0;
3047            S4'  f_T = c_T;
3048
3049          At least when VEC_COND_EXPR is implemented using masks
3050          cond ? 1 : 0 is as expensive as cond ? var : 0, in both cases it
3051          computes the comparison masks and ands it, in one case with
3052          all ones vector, in the other case with a vector register.
3053          Don't do this for BIT_IOR_EXPR, because cond ? 1 : var; is
3054          often more expensive.  */
3055       def_stmt = SSA_NAME_DEF_STMT (rhs2);
3056       def_rhs_code = gimple_assign_rhs_code (def_stmt);
3057       if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
3058         {
3059           tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
3060           irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
3061           if (TYPE_PRECISION (TREE_TYPE (irhs1))
3062               == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1))))
3063             {
3064               gimple *tstmt;
3065               stmt_vec_info stmt_def_vinfo = vinfo_for_stmt (def_stmt);
3066               irhs2 = adjust_bool_pattern (rhs2, out_type, irhs1, stmts);
3067               tstmt = stmts->pop ();
3068               gcc_assert (tstmt == def_stmt);
3069               stmts->quick_push (stmt);
3070               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt))
3071                 = STMT_VINFO_RELATED_STMT (stmt_def_vinfo);
3072               gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_def_vinfo));
3073               STMT_VINFO_RELATED_STMT (stmt_def_vinfo) = NULL;
3074               return irhs2;
3075             }
3076           else
3077             irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
3078           goto and_ior_xor;
3079         }
3080       def_stmt = SSA_NAME_DEF_STMT (rhs1);
3081       def_rhs_code = gimple_assign_rhs_code (def_stmt);
3082       if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
3083         {
3084           tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
3085           irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
3086           if (TYPE_PRECISION (TREE_TYPE (irhs2))
3087               == GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (def_rhs1))))
3088             {
3089               gimple *tstmt;
3090               stmt_vec_info stmt_def_vinfo = vinfo_for_stmt (def_stmt);
3091               irhs1 = adjust_bool_pattern (rhs1, out_type, irhs2, stmts);
3092               tstmt = stmts->pop ();
3093               gcc_assert (tstmt == def_stmt);
3094               stmts->quick_push (stmt);
3095               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt))
3096                 = STMT_VINFO_RELATED_STMT (stmt_def_vinfo);
3097               gcc_assert (!STMT_VINFO_PATTERN_DEF_SEQ (stmt_def_vinfo));
3098               STMT_VINFO_RELATED_STMT (stmt_def_vinfo) = NULL;
3099               return irhs1;
3100             }
3101           else
3102             irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
3103           goto and_ior_xor;
3104         }
3105       /* FALLTHRU */
3106     case BIT_IOR_EXPR:
3107     case BIT_XOR_EXPR:
3108       irhs1 = adjust_bool_pattern (rhs1, out_type, NULL_TREE, stmts);
3109       irhs2 = adjust_bool_pattern (rhs2, out_type, NULL_TREE, stmts);
3110     and_ior_xor:
3111       if (TYPE_PRECISION (TREE_TYPE (irhs1))
3112           != TYPE_PRECISION (TREE_TYPE (irhs2)))
3113         {
3114           int prec1 = TYPE_PRECISION (TREE_TYPE (irhs1));
3115           int prec2 = TYPE_PRECISION (TREE_TYPE (irhs2));
3116           int out_prec = TYPE_PRECISION (out_type);
3117           if (absu_hwi (out_prec - prec1) < absu_hwi (out_prec - prec2))
3118             irhs2 = adjust_bool_pattern_cast (TREE_TYPE (irhs1), rhs2);
3119           else if (absu_hwi (out_prec - prec1) > absu_hwi (out_prec - prec2))
3120             irhs1 = adjust_bool_pattern_cast (TREE_TYPE (irhs2), rhs1);
3121           else
3122             {
3123               irhs1 = adjust_bool_pattern_cast (out_type, rhs1);
3124               irhs2 = adjust_bool_pattern_cast (out_type, rhs2);
3125             }
3126         }
3127       itype = TREE_TYPE (irhs1);
3128       pattern_stmt
3129         = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
3130                                rhs_code, irhs1, irhs2);
3131       break;
3132
3133     default:
3134       gcc_assert (TREE_CODE_CLASS (rhs_code) == tcc_comparison);
3135       if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
3136           || !TYPE_UNSIGNED (TREE_TYPE (rhs1))
3137           || (TYPE_PRECISION (TREE_TYPE (rhs1))
3138               != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1)))))
3139         {
3140           machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
3141           itype
3142             = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
3143         }
3144       else
3145         itype = TREE_TYPE (rhs1);
3146       cond_expr = build2_loc (loc, rhs_code, itype, rhs1, rhs2);
3147       if (trueval == NULL_TREE)
3148         trueval = build_int_cst (itype, 1);
3149       else
3150         gcc_checking_assert (useless_type_conversion_p (itype,
3151                                                         TREE_TYPE (trueval)));
3152       pattern_stmt
3153         = gimple_build_assign (vect_recog_temp_ssa_var (itype, NULL),
3154                                COND_EXPR, cond_expr, trueval,
3155                                build_int_cst (itype, 0));
3156       break;
3157     }
3158
3159   stmts->safe_push (stmt);
3160   gimple_set_location (pattern_stmt, loc);
3161   STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
3162   return gimple_assign_lhs (pattern_stmt);
3163 }
3164
3165
3166 /* Return the proper type for converting bool VAR into
3167    an integer value or NULL_TREE if no such type exists.
3168    The type is chosen so that converted value has the
3169    same number of elements as VAR's vector type.  */
3170
3171 static tree
3172 search_type_for_mask (tree var, vec_info *vinfo)
3173 {
3174   gimple *def_stmt;
3175   enum vect_def_type dt;
3176   tree rhs1;
3177   enum tree_code rhs_code;
3178   tree res = NULL_TREE, res2;
3179
3180   if (TREE_CODE (var) != SSA_NAME)
3181     return NULL_TREE;
3182
3183   if ((TYPE_PRECISION (TREE_TYPE (var)) != 1
3184        || !TYPE_UNSIGNED (TREE_TYPE (var)))
3185       && TREE_CODE (TREE_TYPE (var)) != BOOLEAN_TYPE)
3186     return NULL_TREE;
3187
3188   if (!vect_is_simple_use (var, vinfo, &def_stmt, &dt))
3189     return NULL_TREE;
3190
3191   if (dt != vect_internal_def)
3192     return NULL_TREE;
3193
3194   if (!is_gimple_assign (def_stmt))
3195     return NULL_TREE;
3196
3197   rhs_code = gimple_assign_rhs_code (def_stmt);
3198   rhs1 = gimple_assign_rhs1 (def_stmt);
3199
3200   switch (rhs_code)
3201     {
3202     case SSA_NAME:
3203     case BIT_NOT_EXPR:
3204     CASE_CONVERT:
3205       res = search_type_for_mask (rhs1, vinfo);
3206       break;
3207
3208     case BIT_AND_EXPR:
3209     case BIT_IOR_EXPR:
3210     case BIT_XOR_EXPR:
3211       res = search_type_for_mask (rhs1, vinfo);
3212       res2 = search_type_for_mask (gimple_assign_rhs2 (def_stmt), vinfo);
3213       if (!res || (res2 && TYPE_PRECISION (res) > TYPE_PRECISION (res2)))
3214         res = res2;
3215       break;
3216
3217     default:
3218       if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
3219         {
3220           tree comp_vectype, mask_type;
3221
3222           comp_vectype = get_vectype_for_scalar_type (TREE_TYPE (rhs1));
3223           if (comp_vectype == NULL_TREE)
3224             return NULL_TREE;
3225
3226           mask_type = get_mask_type_for_scalar_type (TREE_TYPE (rhs1));
3227           if (!mask_type
3228               || !expand_vec_cmp_expr_p (comp_vectype, mask_type))
3229             return NULL_TREE;
3230
3231           if (TREE_CODE (TREE_TYPE (rhs1)) != INTEGER_TYPE
3232               || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
3233             {
3234               machine_mode mode = TYPE_MODE (TREE_TYPE (rhs1));
3235               res = build_nonstandard_integer_type (GET_MODE_BITSIZE (mode), 1);
3236             }
3237           else
3238             res = TREE_TYPE (rhs1);
3239         }
3240     }
3241
3242   return res;
3243 }
3244
3245
3246 /* Function vect_recog_bool_pattern
3247
3248    Try to find pattern like following:
3249
3250      bool a_b, b_b, c_b, d_b, e_b;
3251      TYPE f_T;
3252    loop:
3253      S1  a_b = x1 CMP1 y1;
3254      S2  b_b = x2 CMP2 y2;
3255      S3  c_b = a_b & b_b;
3256      S4  d_b = x3 CMP3 y3;
3257      S5  e_b = c_b | d_b;
3258      S6  f_T = (TYPE) e_b;
3259
3260    where type 'TYPE' is an integral type.  Or a similar pattern
3261    ending in
3262
3263      S6  f_Y = e_b ? r_Y : s_Y;
3264
3265    as results from if-conversion of a complex condition.
3266
3267    Input:
3268
3269    * LAST_STMT: A stmt at the end from which the pattern
3270                 search begins, i.e. cast of a bool to
3271                 an integer type.
3272
3273    Output:
3274
3275    * TYPE_IN: The type of the input arguments to the pattern.
3276
3277    * TYPE_OUT: The type of the output of this pattern.
3278
3279    * Return value: A new stmt that will be used to replace the pattern.
3280
3281         Assuming size of TYPE is the same as size of all comparisons
3282         (otherwise some casts would be added where needed), the above
3283         sequence we create related pattern stmts:
3284         S1'  a_T = x1 CMP1 y1 ? 1 : 0;
3285         S3'  c_T = x2 CMP2 y2 ? a_T : 0;
3286         S4'  d_T = x3 CMP3 y3 ? 1 : 0;
3287         S5'  e_T = c_T | d_T;
3288         S6'  f_T = e_T;
3289
3290         Instead of the above S3' we could emit:
3291         S2'  b_T = x2 CMP2 y2 ? 1 : 0;
3292         S3'  c_T = a_T | b_T;
3293         but the above is more efficient.  */
3294
3295 static gimple *
3296 vect_recog_bool_pattern (vec<gimple *> *stmts, tree *type_in,
3297                          tree *type_out)
3298 {
3299   gimple *last_stmt = stmts->pop ();
3300   enum tree_code rhs_code;
3301   tree var, lhs, rhs, vectype;
3302   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
3303   stmt_vec_info new_stmt_info;
3304   vec_info *vinfo = stmt_vinfo->vinfo;
3305   gimple *pattern_stmt;
3306
3307   if (!is_gimple_assign (last_stmt))
3308     return NULL;
3309
3310   var = gimple_assign_rhs1 (last_stmt);
3311   lhs = gimple_assign_lhs (last_stmt);
3312
3313   if ((TYPE_PRECISION (TREE_TYPE (var)) != 1
3314        || !TYPE_UNSIGNED (TREE_TYPE (var)))
3315       && TREE_CODE (TREE_TYPE (var)) != BOOLEAN_TYPE)
3316     return NULL;
3317
3318   rhs_code = gimple_assign_rhs_code (last_stmt);
3319   if (CONVERT_EXPR_CODE_P (rhs_code))
3320     {
3321       if (TREE_CODE (TREE_TYPE (lhs)) != INTEGER_TYPE
3322           || TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
3323         return NULL;
3324       vectype = get_vectype_for_scalar_type (TREE_TYPE (lhs));
3325       if (vectype == NULL_TREE)
3326         return NULL;
3327
3328       if (check_bool_pattern (var, vinfo))
3329         {
3330           rhs = adjust_bool_pattern (var, TREE_TYPE (lhs), NULL_TREE, stmts);
3331           lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3332           if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3333             pattern_stmt = gimple_build_assign (lhs, SSA_NAME, rhs);
3334           else
3335             pattern_stmt
3336               = gimple_build_assign (lhs, NOP_EXPR, rhs);
3337         }
3338       else
3339         {
3340           tree type = search_type_for_mask (var, vinfo);
3341           tree cst0, cst1, tmp;
3342
3343           if (!type)
3344             return NULL;
3345
3346           /* We may directly use cond with narrowed type to avoid
3347              multiple cond exprs with following result packing and
3348              perform single cond with packed mask instead.  In case
3349              of widening we better make cond first and then extract
3350              results.  */
3351           if (TYPE_MODE (type) == TYPE_MODE (TREE_TYPE (lhs)))
3352             type = TREE_TYPE (lhs);
3353
3354           cst0 = build_int_cst (type, 0);
3355           cst1 = build_int_cst (type, 1);
3356           tmp = vect_recog_temp_ssa_var (type, NULL);
3357           pattern_stmt = gimple_build_assign (tmp, COND_EXPR, var, cst1, cst0);
3358
3359           if (!useless_type_conversion_p (type, TREE_TYPE (lhs)))
3360             {
3361               tree new_vectype = get_vectype_for_scalar_type (type);
3362               new_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
3363               set_vinfo_for_stmt (pattern_stmt, new_stmt_info);
3364               STMT_VINFO_VECTYPE (new_stmt_info) = new_vectype;
3365               new_pattern_def_seq (stmt_vinfo, pattern_stmt);
3366
3367               lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3368               pattern_stmt = gimple_build_assign (lhs, CONVERT_EXPR, tmp);
3369             }
3370         }
3371
3372       *type_out = vectype;
3373       *type_in = vectype;
3374       stmts->safe_push (last_stmt);
3375       if (dump_enabled_p ())
3376         dump_printf_loc (MSG_NOTE, vect_location,
3377                          "vect_recog_bool_pattern: detected:\n");
3378
3379       return pattern_stmt;
3380     }
3381   else if (rhs_code == COND_EXPR
3382            && TREE_CODE (var) == SSA_NAME)
3383     {
3384       vectype = get_vectype_for_scalar_type (TREE_TYPE (lhs));
3385       if (vectype == NULL_TREE)
3386         return NULL;
3387
3388       /* Build a scalar type for the boolean result that when
3389          vectorized matches the vector type of the result in
3390          size and number of elements.  */
3391       unsigned prec
3392         = wi::udiv_trunc (TYPE_SIZE (vectype),
3393                           TYPE_VECTOR_SUBPARTS (vectype)).to_uhwi ();
3394       tree type
3395         = build_nonstandard_integer_type (prec,
3396                                           TYPE_UNSIGNED (TREE_TYPE (var)));
3397       if (get_vectype_for_scalar_type (type) == NULL_TREE)
3398         return NULL;
3399
3400       if (!check_bool_pattern (var, vinfo))
3401         return NULL;
3402
3403       rhs = adjust_bool_pattern (var, type, NULL_TREE, stmts);
3404
3405       lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3406       pattern_stmt
3407           = gimple_build_assign (lhs, COND_EXPR,
3408                                  build2 (NE_EXPR, boolean_type_node,
3409                                          rhs, build_int_cst (type, 0)),
3410                                  gimple_assign_rhs2 (last_stmt),
3411                                  gimple_assign_rhs3 (last_stmt));
3412       *type_out = vectype;
3413       *type_in = vectype;
3414       stmts->safe_push (last_stmt);
3415       if (dump_enabled_p ())
3416         dump_printf_loc (MSG_NOTE, vect_location,
3417                          "vect_recog_bool_pattern: detected:\n");
3418
3419       return pattern_stmt;
3420     }
3421   else if (rhs_code == SSA_NAME
3422            && STMT_VINFO_DATA_REF (stmt_vinfo))
3423     {
3424       stmt_vec_info pattern_stmt_info;
3425       vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
3426       gcc_assert (vectype != NULL_TREE);
3427       if (!VECTOR_MODE_P (TYPE_MODE (vectype)))
3428         return NULL;
3429
3430       if (check_bool_pattern (var, vinfo))
3431         rhs = adjust_bool_pattern (var, TREE_TYPE (vectype),
3432                                    NULL_TREE, stmts);
3433       else
3434         {
3435           tree type = search_type_for_mask (var, vinfo);
3436           tree cst0, cst1, new_vectype;
3437
3438           if (!type)
3439             return NULL;
3440
3441           if (TYPE_MODE (type) == TYPE_MODE (TREE_TYPE (vectype)))
3442             type = TREE_TYPE (vectype);
3443
3444           cst0 = build_int_cst (type, 0);
3445           cst1 = build_int_cst (type, 1);
3446           new_vectype = get_vectype_for_scalar_type (type);
3447
3448           rhs = vect_recog_temp_ssa_var (type, NULL);
3449           pattern_stmt = gimple_build_assign (rhs, COND_EXPR, var, cst1, cst0);
3450
3451           pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
3452           set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
3453           STMT_VINFO_VECTYPE (pattern_stmt_info) = new_vectype;
3454           append_pattern_def_seq (stmt_vinfo, pattern_stmt);
3455         }
3456
3457       lhs = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vectype), lhs);
3458       if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3459         {
3460           tree rhs2 = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3461           gimple *cast_stmt = gimple_build_assign (rhs2, NOP_EXPR, rhs);
3462           append_pattern_def_seq (stmt_vinfo, cast_stmt);
3463           rhs = rhs2;
3464         }
3465       pattern_stmt = gimple_build_assign (lhs, SSA_NAME, rhs);
3466       pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
3467       set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
3468       STMT_VINFO_DATA_REF (pattern_stmt_info)
3469         = STMT_VINFO_DATA_REF (stmt_vinfo);
3470       STMT_VINFO_DR_BASE_ADDRESS (pattern_stmt_info)
3471         = STMT_VINFO_DR_BASE_ADDRESS (stmt_vinfo);
3472       STMT_VINFO_DR_INIT (pattern_stmt_info) = STMT_VINFO_DR_INIT (stmt_vinfo);
3473       STMT_VINFO_DR_OFFSET (pattern_stmt_info)
3474         = STMT_VINFO_DR_OFFSET (stmt_vinfo);
3475       STMT_VINFO_DR_STEP (pattern_stmt_info) = STMT_VINFO_DR_STEP (stmt_vinfo);
3476       STMT_VINFO_DR_ALIGNED_TO (pattern_stmt_info)
3477         = STMT_VINFO_DR_ALIGNED_TO (stmt_vinfo);
3478       DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt;
3479       *type_out = vectype;
3480       *type_in = vectype;
3481       stmts->safe_push (last_stmt);
3482       if (dump_enabled_p ())
3483         dump_printf_loc (MSG_NOTE, vect_location,
3484                          "vect_recog_bool_pattern: detected:\n");
3485       return pattern_stmt;
3486     }
3487   else
3488     return NULL;
3489 }
3490
3491
3492 /* A helper for vect_recog_mask_conversion_pattern.  Build
3493    conversion of MASK to a type suitable for masking VECTYPE.
3494    Built statement gets required vectype and is appended to
3495    a pattern sequence of STMT_VINFO.
3496
3497    Return converted mask.  */
3498
3499 static tree
3500 build_mask_conversion (tree mask, tree vectype, stmt_vec_info stmt_vinfo,
3501                        vec_info *vinfo)
3502 {
3503   gimple *stmt;
3504   tree masktype, tmp;
3505   stmt_vec_info new_stmt_info;
3506
3507   masktype = build_same_sized_truth_vector_type (vectype);
3508   tmp = vect_recog_temp_ssa_var (TREE_TYPE (masktype), NULL);
3509   stmt = gimple_build_assign (tmp, CONVERT_EXPR, mask);
3510   new_stmt_info = new_stmt_vec_info (stmt, vinfo);
3511   set_vinfo_for_stmt (stmt, new_stmt_info);
3512   STMT_VINFO_VECTYPE (new_stmt_info) = masktype;
3513   append_pattern_def_seq (stmt_vinfo, stmt);
3514
3515   return tmp;
3516 }
3517
3518
3519 /* Function vect_recog_mask_conversion_pattern
3520
3521    Try to find statements which require boolean type
3522    converison.  Additional conversion statements are
3523    added to handle such cases.  For example:
3524
3525    bool m_1, m_2, m_3;
3526    int i_4, i_5;
3527    double d_6, d_7;
3528    char c_1, c_2, c_3;
3529
3530    S1   m_1 = i_4 > i_5;
3531    S2   m_2 = d_6 < d_7;
3532    S3   m_3 = m_1 & m_2;
3533    S4   c_1 = m_3 ? c_2 : c_3;
3534
3535    Will be transformed into:
3536
3537    S1   m_1 = i_4 > i_5;
3538    S2   m_2 = d_6 < d_7;
3539    S3'' m_2' = (_Bool[bitsize=32])m_2
3540    S3'  m_3' = m_1 & m_2';
3541    S4'' m_3'' = (_Bool[bitsize=8])m_3'
3542    S4'  c_1' = m_3'' ? c_2 : c_3;  */
3543
3544 static gimple *
3545 vect_recog_mask_conversion_pattern (vec<gimple *> *stmts, tree *type_in,
3546                                     tree *type_out)
3547 {
3548   gimple *last_stmt = stmts->pop ();
3549   enum tree_code rhs_code;
3550   tree lhs, rhs1, rhs2, tmp, rhs1_type, rhs2_type, vectype1, vectype2;
3551   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
3552   stmt_vec_info pattern_stmt_info;
3553   vec_info *vinfo = stmt_vinfo->vinfo;
3554   gimple *pattern_stmt;
3555
3556   /* Check for MASK_LOAD ans MASK_STORE calls requiring mask conversion.  */
3557   if (is_gimple_call (last_stmt)
3558       && gimple_call_internal_p (last_stmt)
3559       && (gimple_call_internal_fn (last_stmt) == IFN_MASK_STORE
3560           || gimple_call_internal_fn (last_stmt) == IFN_MASK_LOAD))
3561     {
3562       bool load = (gimple_call_internal_fn (last_stmt) == IFN_MASK_LOAD);
3563
3564       if (load)
3565         {
3566           lhs = gimple_call_lhs (last_stmt);
3567           vectype1 = get_vectype_for_scalar_type (TREE_TYPE (lhs));
3568         }
3569       else
3570         {
3571           rhs2 = gimple_call_arg (last_stmt, 3);
3572           vectype1 = get_vectype_for_scalar_type (TREE_TYPE (rhs2));
3573         }
3574
3575       rhs1 = gimple_call_arg (last_stmt, 2);
3576       rhs1_type = search_type_for_mask (rhs1, vinfo);
3577       if (!rhs1_type)
3578         return NULL;
3579       vectype2 = get_mask_type_for_scalar_type (rhs1_type);
3580
3581       if (!vectype1 || !vectype2
3582           || TYPE_VECTOR_SUBPARTS (vectype1) == TYPE_VECTOR_SUBPARTS (vectype2))
3583         return NULL;
3584
3585       tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo);
3586
3587       if (load)
3588         {
3589           lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3590           pattern_stmt
3591             = gimple_build_call_internal (IFN_MASK_LOAD, 3,
3592                                           gimple_call_arg (last_stmt, 0),
3593                                           gimple_call_arg (last_stmt, 1),
3594                                           tmp);
3595           gimple_call_set_lhs (pattern_stmt, lhs);
3596         }
3597       else
3598           pattern_stmt
3599             = gimple_build_call_internal (IFN_MASK_STORE, 4,
3600                                           gimple_call_arg (last_stmt, 0),
3601                                           gimple_call_arg (last_stmt, 1),
3602                                           tmp,
3603                                           gimple_call_arg (last_stmt, 3));
3604
3605
3606       pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
3607       set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
3608       STMT_VINFO_DATA_REF (pattern_stmt_info)
3609         = STMT_VINFO_DATA_REF (stmt_vinfo);
3610       STMT_VINFO_DR_BASE_ADDRESS (pattern_stmt_info)
3611         = STMT_VINFO_DR_BASE_ADDRESS (stmt_vinfo);
3612       STMT_VINFO_DR_INIT (pattern_stmt_info) = STMT_VINFO_DR_INIT (stmt_vinfo);
3613       STMT_VINFO_DR_OFFSET (pattern_stmt_info)
3614         = STMT_VINFO_DR_OFFSET (stmt_vinfo);
3615       STMT_VINFO_DR_STEP (pattern_stmt_info) = STMT_VINFO_DR_STEP (stmt_vinfo);
3616       STMT_VINFO_DR_ALIGNED_TO (pattern_stmt_info)
3617         = STMT_VINFO_DR_ALIGNED_TO (stmt_vinfo);
3618       DR_STMT (STMT_VINFO_DATA_REF (stmt_vinfo)) = pattern_stmt;
3619
3620       *type_out = vectype1;
3621       *type_in = vectype1;
3622       stmts->safe_push (last_stmt);
3623       if (dump_enabled_p ())
3624         dump_printf_loc (MSG_NOTE, vect_location,
3625                          "vect_recog_mask_conversion_pattern: detected:\n");
3626
3627       return pattern_stmt;
3628     }
3629
3630   if (!is_gimple_assign (last_stmt))
3631     return NULL;
3632
3633   lhs = gimple_assign_lhs (last_stmt);
3634   rhs1 = gimple_assign_rhs1 (last_stmt);
3635   rhs_code = gimple_assign_rhs_code (last_stmt);
3636
3637   /* Check for cond expression requiring mask conversion.  */
3638   if (rhs_code == COND_EXPR)
3639     {
3640       /* vect_recog_mixed_size_cond_pattern could apply.
3641          Do nothing then.  */
3642       if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
3643         return NULL;
3644
3645       vectype1 = get_vectype_for_scalar_type (TREE_TYPE (lhs));
3646
3647       if (TREE_CODE (rhs1) == SSA_NAME)
3648         {
3649           rhs1_type = search_type_for_mask (rhs1, vinfo);
3650           if (!rhs1_type)
3651             return NULL;
3652         }
3653       else
3654         rhs1_type = TREE_TYPE (TREE_OPERAND (rhs1, 0));
3655
3656       vectype2 = get_mask_type_for_scalar_type (rhs1_type);
3657
3658       if (!vectype1 || !vectype2
3659           || TYPE_VECTOR_SUBPARTS (vectype1) == TYPE_VECTOR_SUBPARTS (vectype2))
3660         return NULL;
3661
3662       /* If rhs1 is a comparison we need to move it into a
3663          separate statement.  */
3664       if (TREE_CODE (rhs1) != SSA_NAME)
3665         {
3666           tmp = vect_recog_temp_ssa_var (TREE_TYPE (rhs1), NULL);
3667           pattern_stmt = gimple_build_assign (tmp, rhs1);
3668           rhs1 = tmp;
3669
3670           pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
3671           set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
3672           STMT_VINFO_VECTYPE (pattern_stmt_info) = vectype2;
3673           append_pattern_def_seq (stmt_vinfo, pattern_stmt);
3674         }
3675
3676       tmp = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo);
3677
3678       lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3679       pattern_stmt = gimple_build_assign (lhs, COND_EXPR, tmp,
3680                                           gimple_assign_rhs2 (last_stmt),
3681                                           gimple_assign_rhs3 (last_stmt));
3682
3683       *type_out = vectype1;
3684       *type_in = vectype1;
3685       stmts->safe_push (last_stmt);
3686       if (dump_enabled_p ())
3687         dump_printf_loc (MSG_NOTE, vect_location,
3688                          "vect_recog_mask_conversion_pattern: detected:\n");
3689
3690       return pattern_stmt;
3691     }
3692
3693   /* Now check for binary boolean operations requiring conversion for
3694      one of operands.  */
3695   if (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE)
3696     return NULL;
3697
3698   if (rhs_code != BIT_IOR_EXPR
3699       && rhs_code != BIT_XOR_EXPR
3700       && rhs_code != BIT_AND_EXPR)
3701     return NULL;
3702
3703   rhs2 = gimple_assign_rhs2 (last_stmt);
3704
3705   rhs1_type = search_type_for_mask (rhs1, vinfo);
3706   rhs2_type = search_type_for_mask (rhs2, vinfo);
3707
3708   if (!rhs1_type || !rhs2_type
3709       || TYPE_PRECISION (rhs1_type) == TYPE_PRECISION (rhs2_type))
3710     return NULL;
3711
3712   if (TYPE_PRECISION (rhs1_type) < TYPE_PRECISION (rhs2_type))
3713     {
3714       vectype1 = get_mask_type_for_scalar_type (rhs1_type);
3715       if (!vectype1)
3716         return NULL;
3717       rhs2 = build_mask_conversion (rhs2, vectype1, stmt_vinfo, vinfo);
3718     }
3719   else
3720     {
3721       vectype1 = get_mask_type_for_scalar_type (rhs2_type);
3722       if (!vectype1)
3723         return NULL;
3724       rhs1 = build_mask_conversion (rhs1, vectype1, stmt_vinfo, vinfo);
3725     }
3726
3727   lhs = vect_recog_temp_ssa_var (TREE_TYPE (lhs), NULL);
3728   pattern_stmt = gimple_build_assign (lhs, rhs_code, rhs1, rhs2);
3729
3730   *type_out = vectype1;
3731   *type_in = vectype1;
3732   stmts->safe_push (last_stmt);
3733   if (dump_enabled_p ())
3734     dump_printf_loc (MSG_NOTE, vect_location,
3735                      "vect_recog_mask_conversion_pattern: detected:\n");
3736
3737   return pattern_stmt;
3738 }
3739
3740
3741 /* Mark statements that are involved in a pattern.  */
3742
3743 static inline void
3744 vect_mark_pattern_stmts (gimple *orig_stmt, gimple *pattern_stmt,
3745                          tree pattern_vectype)
3746 {
3747   stmt_vec_info pattern_stmt_info, def_stmt_info;
3748   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
3749   vec_info *vinfo = orig_stmt_info->vinfo;
3750   gimple *def_stmt;
3751
3752   pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
3753   if (pattern_stmt_info == NULL)
3754     {
3755       pattern_stmt_info = new_stmt_vec_info (pattern_stmt, vinfo);
3756       set_vinfo_for_stmt (pattern_stmt, pattern_stmt_info);
3757     }
3758   gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt));
3759
3760   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt;
3761   STMT_VINFO_DEF_TYPE (pattern_stmt_info)
3762     = STMT_VINFO_DEF_TYPE (orig_stmt_info);
3763   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
3764   STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true;
3765   STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt;
3766   STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info)
3767     = STMT_VINFO_PATTERN_DEF_SEQ (orig_stmt_info);
3768   if (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info))
3769     {
3770       gimple_stmt_iterator si;
3771       for (si = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (pattern_stmt_info));
3772            !gsi_end_p (si); gsi_next (&si))
3773         {
3774           def_stmt = gsi_stmt (si);
3775           def_stmt_info = vinfo_for_stmt (def_stmt);
3776           if (def_stmt_info == NULL)
3777             {
3778               def_stmt_info = new_stmt_vec_info (def_stmt, vinfo);
3779               set_vinfo_for_stmt (def_stmt, def_stmt_info);
3780             }
3781           gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
3782           STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt;
3783           STMT_VINFO_DEF_TYPE (def_stmt_info) = vect_internal_def;
3784           if (STMT_VINFO_VECTYPE (def_stmt_info) == NULL_TREE)
3785             STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype;
3786         }
3787     }
3788 }
3789
3790 /* Function vect_pattern_recog_1
3791
3792    Input:
3793    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
3794         computation pattern.
3795    STMT: A stmt from which the pattern search should start.
3796
3797    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
3798    expression that computes the same functionality and can be used to
3799    replace the sequence of stmts that are involved in the pattern.
3800
3801    Output:
3802    This function checks if the expression returned by PATTERN_RECOG_FUNC is
3803    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
3804    relevant vector type. If 'TYPE_IN' is already a vector type, then this
3805    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
3806    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
3807    to the available target pattern.
3808
3809    This function also does some bookkeeping, as explained in the documentation
3810    for vect_recog_pattern.  */
3811
3812 static bool
3813 vect_pattern_recog_1 (vect_recog_func *recog_func,
3814                       gimple_stmt_iterator si,
3815                       vec<gimple *> *stmts_to_replace)
3816 {
3817   gimple *stmt = gsi_stmt (si), *pattern_stmt;
3818   stmt_vec_info stmt_info;
3819   loop_vec_info loop_vinfo;
3820   tree pattern_vectype;
3821   tree type_in, type_out;
3822   enum tree_code code;
3823   int i;
3824   gimple *next;
3825
3826   stmts_to_replace->truncate (0);
3827   stmts_to_replace->quick_push (stmt);
3828   pattern_stmt = recog_func->fn (stmts_to_replace, &type_in, &type_out);
3829   if (!pattern_stmt)
3830     return false;
3831
3832   stmt = stmts_to_replace->last ();
3833   stmt_info = vinfo_for_stmt (stmt);
3834   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3835
3836   if (VECTOR_BOOLEAN_TYPE_P (type_in)
3837       || VECTOR_MODE_P (TYPE_MODE (type_in)))
3838     {
3839       /* No need to check target support (already checked by the pattern
3840          recognition function).  */
3841       pattern_vectype = type_out ? type_out : type_in;
3842     }
3843   else
3844     {
3845       machine_mode vec_mode;
3846       enum insn_code icode;
3847       optab optab;
3848
3849       /* Check target support  */
3850       type_in = get_vectype_for_scalar_type (type_in);
3851       if (!type_in)
3852         return false;
3853       if (type_out)
3854         type_out = get_vectype_for_scalar_type (type_out);
3855       else
3856         type_out = type_in;
3857       if (!type_out)
3858         return false;
3859       pattern_vectype = type_out;
3860
3861       if (is_gimple_assign (pattern_stmt))
3862         code = gimple_assign_rhs_code (pattern_stmt);
3863       else
3864         {
3865           gcc_assert (is_gimple_call (pattern_stmt));
3866           code = CALL_EXPR;
3867         }
3868
3869       optab = optab_for_tree_code (code, type_in, optab_default);
3870       vec_mode = TYPE_MODE (type_in);
3871       if (!optab
3872           || (icode = optab_handler (optab, vec_mode)) == CODE_FOR_nothing
3873           || (insn_data[icode].operand[0].mode != TYPE_MODE (type_out)))
3874         return false;
3875     }
3876
3877   /* Found a vectorizable pattern.  */
3878   if (dump_enabled_p ())
3879     {
3880       dump_printf_loc (MSG_NOTE, vect_location,
3881                        "%s pattern recognized: ", recog_func->name);
3882       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
3883     }
3884
3885   /* Mark the stmts that are involved in the pattern. */
3886   vect_mark_pattern_stmts (stmt, pattern_stmt, pattern_vectype);
3887
3888   /* Patterns cannot be vectorized using SLP, because they change the order of
3889      computation.  */
3890   if (loop_vinfo)
3891     FOR_EACH_VEC_ELT (LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
3892       if (next == stmt)
3893         LOOP_VINFO_REDUCTIONS (loop_vinfo).ordered_remove (i);
3894
3895   /* It is possible that additional pattern stmts are created and inserted in
3896      STMTS_TO_REPLACE.  We create a stmt_info for each of them, and mark the
3897      relevant statements.  */
3898   for (i = 0; stmts_to_replace->iterate (i, &stmt)
3899               && (unsigned) i < (stmts_to_replace->length () - 1);
3900        i++)
3901     {
3902       stmt_info = vinfo_for_stmt (stmt);
3903       pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
3904       if (dump_enabled_p ())
3905         {
3906           dump_printf_loc (MSG_NOTE, vect_location,
3907                            "additional pattern stmt: ");
3908           dump_gimple_stmt (MSG_NOTE, TDF_SLIM, pattern_stmt, 0);
3909         }
3910
3911       vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE);
3912     }
3913
3914   return true;
3915 }
3916
3917
3918 /* Function vect_pattern_recog
3919
3920    Input:
3921    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
3922         computation idioms.
3923
3924    Output - for each computation idiom that is detected we create a new stmt
3925         that provides the same functionality and that can be vectorized.  We
3926         also record some information in the struct_stmt_info of the relevant
3927         stmts, as explained below:
3928
3929    At the entry to this function we have the following stmts, with the
3930    following initial value in the STMT_VINFO fields:
3931
3932          stmt                     in_pattern_p  related_stmt    vec_stmt
3933          S1: a_i = ....                 -       -               -
3934          S2: a_2 = ..use(a_i)..         -       -               -
3935          S3: a_1 = ..use(a_2)..         -       -               -
3936          S4: a_0 = ..use(a_1)..         -       -               -
3937          S5: ... = ..use(a_0)..         -       -               -
3938
3939    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
3940    represented by a single stmt.  We then:
3941    - create a new stmt S6 equivalent to the pattern (the stmt is not
3942      inserted into the code)
3943    - fill in the STMT_VINFO fields as follows:
3944
3945                                   in_pattern_p  related_stmt    vec_stmt
3946          S1: a_i = ....                 -       -               -
3947          S2: a_2 = ..use(a_i)..         -       -               -
3948          S3: a_1 = ..use(a_2)..         -       -               -
3949          S4: a_0 = ..use(a_1)..         true    S6              -
3950           '---> S6: a_new = ....        -       S4              -
3951          S5: ... = ..use(a_0)..         -       -               -
3952
3953    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
3954    to each other through the RELATED_STMT field).
3955
3956    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
3957    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
3958    remain irrelevant unless used by stmts other than S4.
3959
3960    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
3961    (because they are marked as irrelevant).  It will vectorize S6, and record
3962    a pointer to the new vector stmt VS6 from S6 (as usual).
3963    S4 will be skipped, and S5 will be vectorized as usual:
3964
3965                                   in_pattern_p  related_stmt    vec_stmt
3966          S1: a_i = ....                 -       -               -
3967          S2: a_2 = ..use(a_i)..         -       -               -
3968          S3: a_1 = ..use(a_2)..         -       -               -
3969        > VS6: va_new = ....             -       -               -
3970          S4: a_0 = ..use(a_1)..         true    S6              VS6
3971           '---> S6: a_new = ....        -       S4              VS6
3972        > VS5: ... = ..vuse(va_new)..    -       -               -
3973          S5: ... = ..use(a_0)..         -       -               -
3974
3975    DCE could then get rid of {S1,S2,S3,S4,S5} (if their defs are not used
3976    elsewhere), and we'll end up with:
3977
3978         VS6: va_new = ....
3979         VS5: ... = ..vuse(va_new)..
3980
3981    In case of more than one pattern statements, e.g., widen-mult with
3982    intermediate type:
3983
3984      S1  a_t = ;
3985      S2  a_T = (TYPE) a_t;
3986            '--> S3: a_it = (interm_type) a_t;
3987      S4  prod_T = a_T * CONST;
3988            '--> S5: prod_T' = a_it w* CONST;
3989
3990    there may be other users of a_T outside the pattern.  In that case S2 will
3991    be marked as relevant (as well as S3), and both S2 and S3 will be analyzed
3992    and vectorized.  The vector stmt VS2 will be recorded in S2, and VS3 will
3993    be recorded in S3.  */
3994
3995 void
3996 vect_pattern_recog (vec_info *vinfo)
3997 {
3998   struct loop *loop;
3999   basic_block *bbs;
4000   unsigned int nbbs;
4001   gimple_stmt_iterator si;
4002   unsigned int i, j;
4003   auto_vec<gimple *, 1> stmts_to_replace;
4004   gimple *stmt;
4005
4006   if (dump_enabled_p ())
4007     dump_printf_loc (MSG_NOTE, vect_location,
4008                      "=== vect_pattern_recog ===\n");
4009
4010   if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
4011     {
4012       loop = LOOP_VINFO_LOOP (loop_vinfo);
4013       bbs = LOOP_VINFO_BBS (loop_vinfo);
4014       nbbs = loop->num_nodes;
4015
4016       /* Scan through the loop stmts, applying the pattern recognition
4017          functions starting at each stmt visited:  */
4018       for (i = 0; i < nbbs; i++)
4019         {
4020           basic_block bb = bbs[i];
4021           for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
4022             {
4023               /* Scan over all generic vect_recog_xxx_pattern functions.  */
4024               for (j = 0; j < NUM_PATTERNS; j++)
4025                 if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si,
4026                                           &stmts_to_replace))
4027                   break;
4028             }
4029         }
4030     }
4031   else
4032     {
4033       bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo);
4034       for (si = bb_vinfo->region_begin;
4035            gsi_stmt (si) != gsi_stmt (bb_vinfo->region_end); gsi_next (&si))
4036         {
4037           if ((stmt = gsi_stmt (si))
4038               && vinfo_for_stmt (stmt)
4039               && !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)))
4040             continue;
4041
4042           /* Scan over all generic vect_recog_xxx_pattern functions.  */
4043           for (j = 0; j < NUM_PATTERNS; j++)
4044             if (vect_pattern_recog_1 (&vect_vect_recog_func_ptrs[j], si,
4045                                       &stmts_to_replace))
4046               break;
4047         }
4048     }
4049 }