gcc/tree-vect-patterns.c

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