gcc/tree-vect-patterns.c

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