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