gcc/tree-vect-patterns.c

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