gcc/tree-vect-patterns.c

   1 /* Analysis Utilities for Loop Vectorization.
   2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
   3    Free Software Foundation, Inc.
   4    Contributed by Dorit Nuzman <dorit@il.ibm.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "target.h"
  29 #include "basic-block.h"
  30 #include "gimple-pretty-print.h"
  31 #include "tree-flow.h"
  32 #include "tree-dump.h"
  33 #include "cfgloop.h"
  34 #include "expr.h"
  35 #include "optabs.h"
  36 #include "params.h"
  37 #include "tree-data-ref.h"
  38 #include "tree-vectorizer.h"
  39 #include "recog.h"
  40 #include "diagnostic-core.h"
  41
  42 /* Pattern recognition functions  */
  43 static gimple vect_recog_widen_sum_pattern (VEC (gimple, heap) **, tree *,
  44                                             tree *);
  45 static gimple vect_recog_widen_mult_pattern (VEC (gimple, heap) **, tree *,
  46                                              tree *);
  47 static gimple vect_recog_dot_prod_pattern (VEC (gimple, heap) **, tree *,
  48                                            tree *);
  49 static gimple vect_recog_pow_pattern (VEC (gimple, heap) **, tree *, tree *);
  50 static gimple vect_recog_over_widening_pattern (VEC (gimple, heap) **, tree *,
  51                                                  tree *);
  52 static vect_recog_func_ptr vect_vect_recog_func_ptrs[NUM_PATTERNS] = {
  53         vect_recog_widen_mult_pattern,
  54         vect_recog_widen_sum_pattern,
  55         vect_recog_dot_prod_pattern,
  56         vect_recog_pow_pattern,
  57         vect_recog_over_widening_pattern};
  58
  59
  60 /* Function widened_name_p
  61
  62    Check whether NAME, an ssa-name used in USE_STMT,
  63    is a result of a type-promotion, such that:
  64      DEF_STMT: NAME = NOP (name0)
  65    where the type of name0 (HALF_TYPE) is smaller than the type of NAME.
  66    If CHECK_SIGN is TRUE, check that either both types are signed or both are
  67    unsigned.  */
  68
  69 static bool
  70 widened_name_p (tree name, gimple use_stmt, tree *half_type, gimple *def_stmt,
  71                 bool check_sign)
  72 {
  73   tree dummy;
  74   gimple dummy_gimple;
  75   loop_vec_info loop_vinfo;
  76   stmt_vec_info stmt_vinfo;
  77   tree type = TREE_TYPE (name);
  78   tree oprnd0;
  79   enum vect_def_type dt;
  80   tree def;
  81
  82   stmt_vinfo = vinfo_for_stmt (use_stmt);
  83   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
  84
  85   if (!vect_is_simple_use (name, loop_vinfo, NULL, def_stmt, &def, &dt))
  86     return false;
  87
  88   if (dt != vect_internal_def
  89       && dt != vect_external_def && dt != vect_constant_def)
  90     return false;
  91
  92   if (! *def_stmt)
  93     return false;
  94
  95   if (!is_gimple_assign (*def_stmt))
  96     return false;
  97
  98   if (gimple_assign_rhs_code (*def_stmt) != NOP_EXPR)
  99     return false;
 100
 101   oprnd0 = gimple_assign_rhs1 (*def_stmt);
 102
 103   *half_type = TREE_TYPE (oprnd0);
 104   if (!INTEGRAL_TYPE_P (type) || !INTEGRAL_TYPE_P (*half_type)
 105       || ((TYPE_UNSIGNED (type) != TYPE_UNSIGNED (*half_type)) && check_sign)
 106       || (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 2)))
 107     return false;
 108
 109   if (!vect_is_simple_use (oprnd0, loop_vinfo, NULL, &dummy_gimple, &dummy,
 110                            &dt))
 111     return false;
 112
 113   return true;
 114 }
 115
 116 /* Helper to return a new temporary for pattern of TYPE for STMT.  If STMT
 117    is NULL, the caller must set SSA_NAME_DEF_STMT for the returned SSA var. */
 118
 119 static tree
 120 vect_recog_temp_ssa_var (tree type, gimple stmt)
 121 {
 122   tree var = create_tmp_var (type, "patt");
 123
 124   add_referenced_var (var);
 125   var = make_ssa_name (var, stmt);
 126   return var;
 127 }
 128
 129 /* Function vect_recog_dot_prod_pattern
 130
 131    Try to find the following pattern:
 132
 133      type x_t, y_t;
 134      TYPE1 prod;
 135      TYPE2 sum = init;
 136    loop:
 137      sum_0 = phi <init, sum_1>
 138      S1  x_t = ...
 139      S2  y_t = ...
 140      S3  x_T = (TYPE1) x_t;
 141      S4  y_T = (TYPE1) y_t;
 142      S5  prod = x_T * y_T;
 143      [S6  prod = (TYPE2) prod;  #optional]
 144      S7  sum_1 = prod + sum_0;
 145
 146    where 'TYPE1' is exactly double the size of type 'type', and 'TYPE2' is the
 147    same size of 'TYPE1' or bigger. This is a special case of a reduction
 148    computation.
 149
 150    Input:
 151
 152    * STMTS: Contains a stmt from which the pattern search begins.  In the
 153    example, when this function is called with S7, the pattern {S3,S4,S5,S6,S7}
 154    will be detected.
 155
 156    Output:
 157
 158    * TYPE_IN: The type of the input arguments to the pattern.
 159
 160    * TYPE_OUT: The type of the output  of this pattern.
 161
 162    * Return value: A new stmt that will be used to replace the sequence of
 163    stmts that constitute the pattern. In this case it will be:
 164         WIDEN_DOT_PRODUCT <x_t, y_t, sum_0>
 165
 166    Note: The dot-prod idiom is a widening reduction pattern that is
 167          vectorized without preserving all the intermediate results. It
 168          produces only N/2 (widened) results (by summing up pairs of
 169          intermediate results) rather than all N results.  Therefore, we
 170          cannot allow this pattern when we want to get all the results and in
 171          the correct order (as is the case when this computation is in an
 172          inner-loop nested in an outer-loop that us being vectorized).  */
 173
 174 static gimple
 175 vect_recog_dot_prod_pattern (VEC (gimple, heap) **stmts, tree *type_in,
 176                              tree *type_out)
 177 {
 178   gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);
 179   tree oprnd0, oprnd1;
 180   tree oprnd00, oprnd01;
 181   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 182   tree type, half_type;
 183   gimple pattern_stmt;
 184   tree prod_type;
 185   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 186   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
 187   tree var;
 188
 189   if (!is_gimple_assign (last_stmt))
 190     return NULL;
 191
 192   type = gimple_expr_type (last_stmt);
 193
 194   /* Look for the following pattern
 195           DX = (TYPE1) X;
 196           DY = (TYPE1) Y;
 197           DPROD = DX * DY;
 198           DDPROD = (TYPE2) DPROD;
 199           sum_1 = DDPROD + sum_0;
 200      In which
 201      - DX is double the size of X
 202      - DY is double the size of Y
 203      - DX, DY, DPROD all have the same type
 204      - sum is the same size of DPROD or bigger
 205      - sum has been recognized as a reduction variable.
 206
 207      This is equivalent to:
 208        DPROD = X w* Y;          #widen mult
 209        sum_1 = DPROD w+ sum_0;  #widen summation
 210      or
 211        DPROD = X w* Y;          #widen mult
 212        sum_1 = DPROD + sum_0;   #summation
 213    */
 214
 215   /* Starting from LAST_STMT, follow the defs of its uses in search
 216      of the above pattern.  */
 217
 218   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
 219     return NULL;
 220
 221   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 222     {
 223       /* Has been detected as widening-summation?  */
 224
 225       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 226       type = gimple_expr_type (stmt);
 227       if (gimple_assign_rhs_code (stmt) != WIDEN_SUM_EXPR)
 228         return NULL;
 229       oprnd0 = gimple_assign_rhs1 (stmt);
 230       oprnd1 = gimple_assign_rhs2 (stmt);
 231       half_type = TREE_TYPE (oprnd0);
 232     }
 233   else
 234     {
 235       gimple def_stmt;
 236
 237       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 238         return NULL;
 239       oprnd0 = gimple_assign_rhs1 (last_stmt);
 240       oprnd1 = gimple_assign_rhs2 (last_stmt);
 241       if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 242           || !types_compatible_p (TREE_TYPE (oprnd1), type))
 243         return NULL;
 244       stmt = last_stmt;
 245
 246       if (widened_name_p (oprnd0, stmt, &half_type, &def_stmt, true))
 247         {
 248           stmt = def_stmt;
 249           oprnd0 = gimple_assign_rhs1 (stmt);
 250         }
 251       else
 252         half_type = type;
 253     }
 254
 255   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
 256      we know that oprnd1 is the reduction variable (defined by a loop-header
 257      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 258      Left to check that oprnd0 is defined by a (widen_)mult_expr  */
 259
 260   prod_type = half_type;
 261   stmt = SSA_NAME_DEF_STMT (oprnd0);
 262
 263   /* It could not be the dot_prod pattern if the stmt is outside the loop.  */
 264   if (!gimple_bb (stmt) || !flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
 265     return NULL;
 266
 267   /* FORNOW.  Can continue analyzing the def-use chain when this stmt in a phi
 268      inside the loop (in case we are analyzing an outer-loop).  */
 269   if (!is_gimple_assign (stmt))
 270     return NULL;
 271   stmt_vinfo = vinfo_for_stmt (stmt);
 272   gcc_assert (stmt_vinfo);
 273   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_internal_def)
 274     return NULL;
 275   if (gimple_assign_rhs_code (stmt) != MULT_EXPR)
 276     return NULL;
 277   if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
 278     {
 279       /* Has been detected as a widening multiplication?  */
 280
 281       stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
 282       if (gimple_assign_rhs_code (stmt) != WIDEN_MULT_EXPR)
 283         return NULL;
 284       stmt_vinfo = vinfo_for_stmt (stmt);
 285       gcc_assert (stmt_vinfo);
 286       gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_internal_def);
 287       oprnd00 = gimple_assign_rhs1 (stmt);
 288       oprnd01 = gimple_assign_rhs2 (stmt);
 289     }
 290   else
 291     {
 292       tree half_type0, half_type1;
 293       gimple def_stmt;
 294       tree oprnd0, oprnd1;
 295
 296       oprnd0 = gimple_assign_rhs1 (stmt);
 297       oprnd1 = gimple_assign_rhs2 (stmt);
 298       if (!types_compatible_p (TREE_TYPE (oprnd0), prod_type)
 299           || !types_compatible_p (TREE_TYPE (oprnd1), prod_type))
 300         return NULL;
 301       if (!widened_name_p (oprnd0, stmt, &half_type0, &def_stmt, true))
 302         return NULL;
 303       oprnd00 = gimple_assign_rhs1 (def_stmt);
 304       if (!widened_name_p (oprnd1, stmt, &half_type1, &def_stmt, true))
 305         return NULL;
 306       oprnd01 = gimple_assign_rhs1 (def_stmt);
 307       if (!types_compatible_p (half_type0, half_type1))
 308         return NULL;
 309       if (TYPE_PRECISION (prod_type) != TYPE_PRECISION (half_type0) * 2)
 310         return NULL;
 311     }
 312
 313   half_type = TREE_TYPE (oprnd00);
 314   *type_in = half_type;
 315   *type_out = type;
 316
 317   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 318   var = vect_recog_temp_ssa_var (type, NULL);
 319   pattern_stmt = gimple_build_assign_with_ops3 (DOT_PROD_EXPR, var,
 320                                                 oprnd00, oprnd01, oprnd1);
 321
 322   if (vect_print_dump_info (REPORT_DETAILS))
 323     {
 324       fprintf (vect_dump, "vect_recog_dot_prod_pattern: detected: ");
 325       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
 326     }
 327
 328   /* We don't allow changing the order of the computation in the inner-loop
 329      when doing outer-loop vectorization.  */
 330   gcc_assert (!nested_in_vect_loop_p (loop, last_stmt));
 331
 332   return pattern_stmt;
 333 }
 334
 335
 336 /* Handle two cases of multiplication by a constant.  The first one is when
 337    the constant, CONST_OPRND, fits the type (HALF_TYPE) of the second
 338    operand (OPRND).  In that case, we can peform widen-mult from HALF_TYPE to
 339    TYPE.
 340
 341    Otherwise, if the type of the result (TYPE) is at least 4 times bigger than
 342    HALF_TYPE, and CONST_OPRND fits an intermediate type (2 times smaller than
 343    TYPE), we can perform widen-mult from the intermediate type to TYPE and
 344    replace a_T = (TYPE) a_t; with a_it - (interm_type) a_t;  */
 345
 346 static bool
 347 vect_handle_widen_mult_by_const (tree const_oprnd, tree *oprnd,
 348                                  VEC (gimple, heap) **stmts, tree type,
 349                                  tree *half_type, gimple def_stmt)
 350 {
 351   tree new_type, new_oprnd, tmp;
 352   gimple new_stmt;
 353
 354   if (int_fits_type_p (const_oprnd, *half_type))
 355     {
 356       /* CONST_OPRND is a constant of HALF_TYPE.  */
 357       *oprnd = gimple_assign_rhs1 (def_stmt);
 358       return true;
 359     }
 360
 361   if (TYPE_PRECISION (type) < (TYPE_PRECISION (*half_type) * 4)
 362       || !vinfo_for_stmt (def_stmt))
 363     return false;
 364
 365   /* TYPE is 4 times bigger than HALF_TYPE, try widen-mult for
 366      a type 2 times bigger than HALF_TYPE.  */
 367   new_type = build_nonstandard_integer_type (TYPE_PRECISION (type) / 2,
 368                                              TYPE_UNSIGNED (type));
 369   if (!int_fits_type_p (const_oprnd, new_type))
 370     return false;
 371
 372   /* Use NEW_TYPE for widen_mult.  */
 373   if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
 374     {
 375       new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
 376       /* Check if the already created pattern stmt is what we need.  */
 377       if (!is_gimple_assign (new_stmt)
 378           || gimple_assign_rhs_code (new_stmt) != NOP_EXPR
 379           || TREE_TYPE (gimple_assign_lhs (new_stmt)) != new_type)
 380         return false;
 381
 382       *oprnd = gimple_assign_lhs (new_stmt);
 383     }
 384   else
 385     {
 386       /* Create a_T = (NEW_TYPE) a_t;  */
 387       *oprnd = gimple_assign_rhs1 (def_stmt);
 388       tmp = create_tmp_var (new_type, NULL);
 389       add_referenced_var (tmp);
 390       new_oprnd = make_ssa_name (tmp, NULL);
 391       new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd, *oprnd,
 392                                                NULL_TREE);
 393       SSA_NAME_DEF_STMT (new_oprnd) = new_stmt;
 394       STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
 395       VEC_safe_push (gimple, heap, *stmts, def_stmt);
 396       *oprnd = new_oprnd;
 397     }
 398
 399   *half_type = new_type;
 400   return true;
 401 }
 402
 403
 404 /* Function vect_recog_widen_mult_pattern
 405
 406    Try to find the following pattern:
 407
 408      type a_t, b_t;
 409      TYPE a_T, b_T, prod_T;
 410
 411      S1  a_t = ;
 412      S2  b_t = ;
 413      S3  a_T = (TYPE) a_t;
 414      S4  b_T = (TYPE) b_t;
 415      S5  prod_T = a_T * b_T;
 416
 417    where type 'TYPE' is at least double the size of type 'type'.
 418
 419    Also detect unsgigned cases:
 420
 421      unsigned type a_t, b_t;
 422      unsigned TYPE u_prod_T;
 423      TYPE a_T, b_T, prod_T;
 424
 425      S1  a_t = ;
 426      S2  b_t = ;
 427      S3  a_T = (TYPE) a_t;
 428      S4  b_T = (TYPE) b_t;
 429      S5  prod_T = a_T * b_T;
 430      S6  u_prod_T = (unsigned TYPE) prod_T;
 431
 432    and multiplication by constants:
 433
 434      type a_t;
 435      TYPE a_T, prod_T;
 436
 437      S1  a_t = ;
 438      S3  a_T = (TYPE) a_t;
 439      S5  prod_T = a_T * CONST;
 440
 441    A special case of multiplication by constants is when 'TYPE' is 4 times
 442    bigger than 'type', but CONST fits an intermediate type 2 times smaller
 443    than 'TYPE'.  In that case we create an additional pattern stmt for S3
 444    to create a variable of the intermediate type, and perform widen-mult
 445    on the intermediate type as well:
 446
 447      type a_t;
 448      interm_type a_it;
 449      TYPE a_T, prod_T,  prod_T';
 450
 451      S1  a_t = ;
 452      S3  a_T = (TYPE) a_t;
 453            '--> a_it = (interm_type) a_t;
 454      S5  prod_T = a_T * CONST;
 455            '--> prod_T' = a_it w* CONST;
 456
 457    Input/Output:
 458
 459    * STMTS: Contains a stmt from which the pattern search begins.  In the
 460    example, when this function is called with S5, the pattern {S3,S4,S5,(S6)}
 461    is detected.  In case of unsigned widen-mult, the original stmt (S5) is
 462    replaced with S6 in STMTS.  In case of multiplication by a constant
 463    of an intermediate type (the last case above), STMTS also contains S3
 464    (inserted before S5).
 465
 466    Output:
 467
 468    * TYPE_IN: The type of the input arguments to the pattern.
 469
 470    * TYPE_OUT: The type of the output of this pattern.
 471
 472    * Return value: A new stmt that will be used to replace the sequence of
 473    stmts that constitute the pattern.  In this case it will be:
 474         WIDEN_MULT <a_t, b_t>
 475 */
 476
 477 static gimple
 478 vect_recog_widen_mult_pattern (VEC (gimple, heap) **stmts,
 479                                tree *type_in, tree *type_out)
 480 {
 481   gimple last_stmt = VEC_pop (gimple, *stmts);
 482   gimple def_stmt0, def_stmt1;
 483   tree oprnd0, oprnd1;
 484   tree type, half_type0, half_type1;
 485   gimple pattern_stmt;
 486   tree vectype, vectype_out = NULL_TREE;
 487   tree dummy;
 488   tree var;
 489   enum tree_code dummy_code;
 490   int dummy_int;
 491   VEC (tree, heap) *dummy_vec;
 492   bool op0_ok, op1_ok;
 493
 494   if (!is_gimple_assign (last_stmt))
 495     return NULL;
 496
 497   type = gimple_expr_type (last_stmt);
 498
 499   /* Starting from LAST_STMT, follow the defs of its uses in search
 500      of the above pattern.  */
 501
 502   if (gimple_assign_rhs_code (last_stmt) != MULT_EXPR)
 503     return NULL;
 504
 505   oprnd0 = gimple_assign_rhs1 (last_stmt);
 506   oprnd1 = gimple_assign_rhs2 (last_stmt);
 507   if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 508       || !types_compatible_p (TREE_TYPE (oprnd1), type))
 509     return NULL;
 510
 511   /* Check argument 0.  */
 512   op0_ok = widened_name_p (oprnd0, last_stmt, &half_type0, &def_stmt0, false);
 513   /* Check argument 1.  */
 514   op1_ok = widened_name_p (oprnd1, last_stmt, &half_type1, &def_stmt1, false);
 515
 516   /* In case of multiplication by a constant one of the operands may not match
 517      the pattern, but not both.  */
 518   if (!op0_ok && !op1_ok)
 519     return NULL;
 520
 521   if (op0_ok && op1_ok)
 522     {
 523       oprnd0 = gimple_assign_rhs1 (def_stmt0);
 524       oprnd1 = gimple_assign_rhs1 (def_stmt1);
 525     }
 526   else if (!op0_ok)
 527     {
 528       if (TREE_CODE (oprnd0) == INTEGER_CST
 529           && TREE_CODE (half_type1) == INTEGER_TYPE
 530           && vect_handle_widen_mult_by_const (oprnd0, &oprnd1, stmts, type,
 531                                               &half_type1, def_stmt1))
 532         half_type0 = half_type1;
 533       else
 534         return NULL;
 535     }
 536   else if (!op1_ok)
 537     {
 538       if (TREE_CODE (oprnd1) == INTEGER_CST
 539           && TREE_CODE (half_type0) == INTEGER_TYPE
 540           && vect_handle_widen_mult_by_const (oprnd1, &oprnd0, stmts, type,
 541                                               &half_type0, def_stmt0))
 542         half_type1 = half_type0;
 543       else
 544         return NULL;
 545     }
 546
 547   /* Handle unsigned case.  Look for
 548      S6  u_prod_T = (unsigned TYPE) prod_T;
 549      Use unsigned TYPE as the type for WIDEN_MULT_EXPR.  */
 550   if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (half_type0))
 551     {
 552       tree lhs = gimple_assign_lhs (last_stmt), use_lhs;
 553       imm_use_iterator imm_iter;
 554       use_operand_p use_p;
 555       int nuses = 0;
 556       gimple use_stmt = NULL;
 557       tree use_type;
 558
 559       if (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (half_type1))
 560         return NULL;
 561
 562       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
 563         {
 564           if (is_gimple_debug (USE_STMT (use_p)))
 565             continue;
 566           use_stmt = USE_STMT (use_p);
 567           nuses++;
 568         }
 569
 570       if (nuses != 1 || !is_gimple_assign (use_stmt)
 571           || gimple_assign_rhs_code (use_stmt) != NOP_EXPR)
 572         return NULL;
 573
 574       use_lhs = gimple_assign_lhs (use_stmt);
 575       use_type = TREE_TYPE (use_lhs);
 576       if (!INTEGRAL_TYPE_P (use_type)
 577           || (TYPE_UNSIGNED (type) == TYPE_UNSIGNED (use_type))
 578           || (TYPE_PRECISION (type) != TYPE_PRECISION (use_type)))
 579         return NULL;
 580
 581       type = use_type;
 582       last_stmt = use_stmt;
 583     }
 584
 585   if (!types_compatible_p (half_type0, half_type1))
 586     return NULL;
 587
 588   /* Pattern detected.  */
 589   if (vect_print_dump_info (REPORT_DETAILS))
 590     fprintf (vect_dump, "vect_recog_widen_mult_pattern: detected: ");
 591
 592   /* Check target support  */
 593   vectype = get_vectype_for_scalar_type (half_type0);
 594   vectype_out = get_vectype_for_scalar_type (type);
 595   if (!vectype
 596       || !vectype_out
 597       || !supportable_widening_operation (WIDEN_MULT_EXPR, last_stmt,
 598                                           vectype_out, vectype,
 599                                           &dummy, &dummy, &dummy_code,
 600                                           &dummy_code, &dummy_int, &dummy_vec))
 601     return NULL;
 602
 603   *type_in = vectype;
 604   *type_out = vectype_out;
 605
 606   /* Pattern supported. Create a stmt to be used to replace the pattern: */
 607   var = vect_recog_temp_ssa_var (type, NULL);
 608   pattern_stmt = gimple_build_assign_with_ops (WIDEN_MULT_EXPR, var, oprnd0,
 609                                                oprnd1);
 610   SSA_NAME_DEF_STMT (var) = pattern_stmt;
 611
 612   if (vect_print_dump_info (REPORT_DETAILS))
 613     print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
 614
 615   VEC_safe_push (gimple, heap, *stmts, last_stmt);
 616   return pattern_stmt;
 617 }
 618
 619
 620 /* Function vect_recog_pow_pattern
 621
 622    Try to find the following pattern:
 623
 624      x = POW (y, N);
 625
 626    with POW being one of pow, powf, powi, powif and N being
 627    either 2 or 0.5.
 628
 629    Input:
 630
 631    * LAST_STMT: A stmt from which the pattern search begins.
 632
 633    Output:
 634
 635    * TYPE_IN: The type of the input arguments to the pattern.
 636
 637    * TYPE_OUT: The type of the output of this pattern.
 638
 639    * Return value: A new stmt that will be used to replace the sequence of
 640    stmts that constitute the pattern. In this case it will be:
 641         x = x * x
 642    or
 643         x = sqrt (x)
 644 */
 645
 646 static gimple
 647 vect_recog_pow_pattern (VEC (gimple, heap) **stmts, tree *type_in,
 648                         tree *type_out)
 649 {
 650   gimple last_stmt = VEC_index (gimple, *stmts, 0);
 651   tree fn, base, exp = NULL;
 652   gimple stmt;
 653   tree var;
 654
 655   if (!is_gimple_call (last_stmt) || gimple_call_lhs (last_stmt) == NULL)
 656     return NULL;
 657
 658   fn = gimple_call_fndecl (last_stmt);
 659   if (fn == NULL_TREE || DECL_BUILT_IN_CLASS (fn) != BUILT_IN_NORMAL)
 660    return NULL;
 661
 662   switch (DECL_FUNCTION_CODE (fn))
 663     {
 664     case BUILT_IN_POWIF:
 665     case BUILT_IN_POWI:
 666     case BUILT_IN_POWF:
 667     case BUILT_IN_POW:
 668       base = gimple_call_arg (last_stmt, 0);
 669       exp = gimple_call_arg (last_stmt, 1);
 670       if (TREE_CODE (exp) != REAL_CST
 671           && TREE_CODE (exp) != INTEGER_CST)
 672         return NULL;
 673       break;
 674
 675     default:
 676       return NULL;
 677     }
 678
 679   /* We now have a pow or powi builtin function call with a constant
 680      exponent.  */
 681
 682   *type_out = NULL_TREE;
 683
 684   /* Catch squaring.  */
 685   if ((host_integerp (exp, 0)
 686        && tree_low_cst (exp, 0) == 2)
 687       || (TREE_CODE (exp) == REAL_CST
 688           && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconst2)))
 689     {
 690       *type_in = TREE_TYPE (base);
 691
 692       var = vect_recog_temp_ssa_var (TREE_TYPE (base), NULL);
 693       stmt = gimple_build_assign_with_ops (MULT_EXPR, var, base, base);
 694       SSA_NAME_DEF_STMT (var) = stmt;
 695       return stmt;
 696     }
 697
 698   /* Catch square root.  */
 699   if (TREE_CODE (exp) == REAL_CST
 700       && REAL_VALUES_EQUAL (TREE_REAL_CST (exp), dconsthalf))
 701     {
 702       tree newfn = mathfn_built_in (TREE_TYPE (base), BUILT_IN_SQRT);
 703       *type_in = get_vectype_for_scalar_type (TREE_TYPE (base));
 704       if (*type_in)
 705         {
 706           gimple stmt = gimple_build_call (newfn, 1, base);
 707           if (vectorizable_function (stmt, *type_in, *type_in)
 708               != NULL_TREE)
 709             {
 710               var = vect_recog_temp_ssa_var (TREE_TYPE (base), stmt);
 711               gimple_call_set_lhs (stmt, var);
 712               return stmt;
 713             }
 714         }
 715     }
 716
 717   return NULL;
 718 }
 719
 720
 721 /* Function vect_recog_widen_sum_pattern
 722
 723    Try to find the following pattern:
 724
 725      type x_t;
 726      TYPE x_T, sum = init;
 727    loop:
 728      sum_0 = phi <init, sum_1>
 729      S1  x_t = *p;
 730      S2  x_T = (TYPE) x_t;
 731      S3  sum_1 = x_T + sum_0;
 732
 733    where type 'TYPE' is at least double the size of type 'type', i.e - we're
 734    summing elements of type 'type' into an accumulator of type 'TYPE'. This is
 735    a special case of a reduction computation.
 736
 737    Input:
 738
 739    * LAST_STMT: A stmt from which the pattern search begins. In the example,
 740    when this function is called with S3, the pattern {S2,S3} will be detected.
 741
 742    Output:
 743
 744    * TYPE_IN: The type of the input arguments to the pattern.
 745
 746    * TYPE_OUT: The type of the output of this pattern.
 747
 748    * Return value: A new stmt that will be used to replace the sequence of
 749    stmts that constitute the pattern. In this case it will be:
 750         WIDEN_SUM <x_t, sum_0>
 751
 752    Note: The widening-sum idiom is a widening reduction pattern that is
 753          vectorized without preserving all the intermediate results. It
 754          produces only N/2 (widened) results (by summing up pairs of
 755          intermediate results) rather than all N results.  Therefore, we
 756          cannot allow this pattern when we want to get all the results and in
 757          the correct order (as is the case when this computation is in an
 758          inner-loop nested in an outer-loop that us being vectorized).  */
 759
 760 static gimple
 761 vect_recog_widen_sum_pattern (VEC (gimple, heap) **stmts, tree *type_in,
 762                               tree *type_out)
 763 {
 764   gimple stmt, last_stmt = VEC_index (gimple, *stmts, 0);
 765   tree oprnd0, oprnd1;
 766   stmt_vec_info stmt_vinfo = vinfo_for_stmt (last_stmt);
 767   tree type, half_type;
 768   gimple pattern_stmt;
 769   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 770   struct loop *loop = LOOP_VINFO_LOOP (loop_info);
 771   tree var;
 772
 773   if (!is_gimple_assign (last_stmt))
 774     return NULL;
 775
 776   type = gimple_expr_type (last_stmt);
 777
 778   /* Look for the following pattern
 779           DX = (TYPE) X;
 780           sum_1 = DX + sum_0;
 781      In which DX is at least double the size of X, and sum_1 has been
 782      recognized as a reduction variable.
 783    */
 784
 785   /* Starting from LAST_STMT, follow the defs of its uses in search
 786      of the above pattern.  */
 787
 788   if (gimple_assign_rhs_code (last_stmt) != PLUS_EXPR)
 789     return NULL;
 790
 791   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def)
 792     return NULL;
 793
 794   oprnd0 = gimple_assign_rhs1 (last_stmt);
 795   oprnd1 = gimple_assign_rhs2 (last_stmt);
 796   if (!types_compatible_p (TREE_TYPE (oprnd0), type)
 797       || !types_compatible_p (TREE_TYPE (oprnd1), type))
 798     return NULL;
 799
 800   /* So far so good.  Since last_stmt was detected as a (summation) reduction,
 801      we know that oprnd1 is the reduction variable (defined by a loop-header
 802      phi), and oprnd0 is an ssa-name defined by a stmt in the loop body.
 803      Left to check that oprnd0 is defined by a cast from type 'type' to type
 804      'TYPE'.  */
 805
 806   if (!widened_name_p (oprnd0, last_stmt, &half_type, &stmt, true))
 807     return NULL;
 808
 809   oprnd0 = gimple_assign_rhs1 (stmt);
 810   *type_in = half_type;
 811   *type_out = type;
 812
 813   /* Pattern detected. Create a stmt to be used to replace the pattern: */
 814   var = vect_recog_temp_ssa_var (type, NULL);
 815   pattern_stmt = gimple_build_assign_with_ops (WIDEN_SUM_EXPR, var,
 816                                                oprnd0, oprnd1);
 817   SSA_NAME_DEF_STMT (var) = pattern_stmt;
 818
 819   if (vect_print_dump_info (REPORT_DETAILS))
 820     {
 821       fprintf (vect_dump, "vect_recog_widen_sum_pattern: detected: ");
 822       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
 823     }
 824
 825   /* We don't allow changing the order of the computation in the inner-loop
 826      when doing outer-loop vectorization.  */
 827   gcc_assert (!nested_in_vect_loop_p (loop, last_stmt));
 828
 829   return pattern_stmt;
 830 }
 831
 832
 833 /* Return TRUE if the operation in STMT can be performed on a smaller type.
 834
 835    Input:
 836    STMT - a statement to check.
 837    DEF - we support operations with two operands, one of which is constant.
 838          The other operand can be defined by a demotion operation, or by a
 839          previous statement in a sequence of over-promoted operations.  In the
 840          later case DEF is used to replace that operand.  (It is defined by a
 841          pattern statement we created for the previous statement in the
 842          sequence).
 843
 844    Input/output:
 845    NEW_TYPE - Output: a smaller type that we are trying to use.  Input: if not
 846          NULL, it's the type of DEF.
 847    STMTS - additional pattern statements.  If a pattern statement (type
 848          conversion) is created in this function, its original statement is
 849          added to STMTS.
 850
 851    Output:
 852    OP0, OP1 - if the operation fits a smaller type, OP0 and OP1 are the new
 853          operands to use in the new pattern statement for STMT (will be created
 854          in vect_recog_over_widening_pattern ()).
 855    NEW_DEF_STMT - in case DEF has to be promoted, we create two pattern
 856          statements for STMT: the first one is a type promotion and the second
 857          one is the operation itself.  We return the type promotion statement
 858          in NEW_DEF_STMT and further store it in STMT_VINFO_PATTERN_DEF_STMT of
 859          the second pattern statement.  */
 860
 861 static bool
 862 vect_operation_fits_smaller_type (gimple stmt, tree def, tree *new_type,
 863                                   tree *op0, tree *op1, gimple *new_def_stmt,
 864                                   VEC (gimple, heap) **stmts)
 865 {
 866   enum tree_code code;
 867   tree const_oprnd, oprnd;
 868   tree interm_type = NULL_TREE, half_type, tmp, new_oprnd, type;
 869   gimple def_stmt, new_stmt;
 870   bool first = false;
 871
 872   *new_def_stmt = NULL;
 873
 874   if (!is_gimple_assign (stmt))
 875     return false;
 876
 877   code = gimple_assign_rhs_code (stmt);
 878   if (code != LSHIFT_EXPR && code != RSHIFT_EXPR
 879       && code != BIT_IOR_EXPR && code != BIT_XOR_EXPR && code != BIT_AND_EXPR)
 880     return false;
 881
 882   oprnd = gimple_assign_rhs1 (stmt);
 883   const_oprnd = gimple_assign_rhs2 (stmt);
 884   type = gimple_expr_type (stmt);
 885
 886   if (TREE_CODE (oprnd) != SSA_NAME
 887       || TREE_CODE (const_oprnd) != INTEGER_CST)
 888     return false;
 889
 890   /* If we are in the middle of a sequence, we use DEF from a previous
 891      statement.  Otherwise, OPRND has to be a result of type promotion.  */
 892   if (*new_type)
 893     {
 894       half_type = *new_type;
 895       oprnd = def;
 896     }
 897   else
 898     {
 899       first = true;
 900       if (!widened_name_p (oprnd, stmt, &half_type, &def_stmt, false)
 901           || !vinfo_for_stmt (def_stmt))
 902         return false;
 903     }
 904
 905   /* Can we perform the operation on a smaller type?  */
 906   switch (code)
 907     {
 908       case BIT_IOR_EXPR:
 909       case BIT_XOR_EXPR:
 910       case BIT_AND_EXPR:
 911         if (!int_fits_type_p (const_oprnd, half_type))
 912           {
 913             /* HALF_TYPE is not enough.  Try a bigger type if possible.  */
 914             if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
 915               return false;
 916
 917             interm_type = build_nonstandard_integer_type (
 918                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
 919             if (!int_fits_type_p (const_oprnd, interm_type))
 920               return false;
 921           }
 922
 923         break;
 924
 925       case LSHIFT_EXPR:
 926         /* Try intermediate type - HALF_TYPE is not enough for sure.  */
 927         if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
 928           return false;
 929
 930         /* Check that HALF_TYPE size + shift amount <= INTERM_TYPE size.
 931           (e.g., if the original value was char, the shift amount is at most 8
 932            if we want to use short).  */
 933         if (compare_tree_int (const_oprnd, TYPE_PRECISION (half_type)) == 1)
 934           return false;
 935
 936         interm_type = build_nonstandard_integer_type (
 937                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
 938
 939         if (!vect_supportable_shift (code, interm_type))
 940           return false;
 941
 942         break;
 943
 944       case RSHIFT_EXPR:
 945         if (vect_supportable_shift (code, half_type))
 946           break;
 947
 948         /* Try intermediate type - HALF_TYPE is not supported.  */
 949         if (TYPE_PRECISION (type) < (TYPE_PRECISION (half_type) * 4))
 950           return false;
 951
 952         interm_type = build_nonstandard_integer_type (
 953                         TYPE_PRECISION (half_type) * 2, TYPE_UNSIGNED (type));
 954
 955         if (!vect_supportable_shift (code, interm_type))
 956           return false;
 957
 958         break;
 959
 960       default:
 961         gcc_unreachable ();
 962     }
 963
 964   /* There are four possible cases:
 965      1. OPRND is defined by a type promotion (in that case FIRST is TRUE, it's
 966         the first statement in the sequence)
 967         a. The original, HALF_TYPE, is not enough - we replace the promotion
 968            from HALF_TYPE to TYPE with a promotion to INTERM_TYPE.
 969         b. HALF_TYPE is sufficient, OPRND is set as the RHS of the original
 970            promotion.
 971      2. OPRND is defined by a pattern statement we created.
 972         a. Its type is not sufficient for the operation, we create a new stmt:
 973            a type conversion for OPRND from HALF_TYPE to INTERM_TYPE.  We store
 974            this statement in NEW_DEF_STMT, and it is later put in
 975            STMT_VINFO_PATTERN_DEF_STMT of the pattern statement for STMT.
 976         b. OPRND is good to use in the new statement.  */
 977   if (first)
 978     {
 979       if (interm_type)
 980         {
 981           /* Replace the original type conversion HALF_TYPE->TYPE with
 982              HALF_TYPE->INTERM_TYPE.  */
 983           if (STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)))
 984             {
 985               new_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
 986               /* Check if the already created pattern stmt is what we need.  */
 987               if (!is_gimple_assign (new_stmt)
 988                   || gimple_assign_rhs_code (new_stmt) != NOP_EXPR
 989                   || TREE_TYPE (gimple_assign_lhs (new_stmt)) != interm_type)
 990                 return false;
 991
 992               oprnd = gimple_assign_lhs (new_stmt);
 993             }
 994           else
 995             {
 996               /* Create NEW_OPRND = (INTERM_TYPE) OPRND.  */
 997               oprnd = gimple_assign_rhs1 (def_stmt);
 998               tmp = create_tmp_reg (interm_type, NULL);
 999               add_referenced_var (tmp);
1000               new_oprnd = make_ssa_name (tmp, NULL);
1001               new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
1002                                                        oprnd, NULL_TREE);
1003               SSA_NAME_DEF_STMT (new_oprnd) = new_stmt;
1004               STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt)) = new_stmt;
1005               VEC_safe_push (gimple, heap, *stmts, def_stmt);
1006               oprnd = new_oprnd;
1007             }
1008         }
1009       else
1010         {
1011           /* Retrieve the operand before the type promotion.  */
1012           oprnd = gimple_assign_rhs1 (def_stmt);
1013         }
1014     }
1015   else
1016     {
1017       if (interm_type)
1018         {
1019           /* Create a type conversion HALF_TYPE->INTERM_TYPE.  */
1020           tmp = create_tmp_reg (interm_type, NULL);
1021           add_referenced_var (tmp);
1022           new_oprnd = make_ssa_name (tmp, NULL);
1023           new_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
1024                                                    oprnd, NULL_TREE);
1025           SSA_NAME_DEF_STMT (new_oprnd) = new_stmt;
1026           oprnd = new_oprnd;
1027           *new_def_stmt = new_stmt;
1028         }
1029
1030       /* Otherwise, OPRND is already set.  */
1031     }
1032
1033   if (interm_type)
1034     *new_type = interm_type;
1035   else
1036     *new_type = half_type;
1037
1038   *op0 = oprnd;
1039   *op1 = fold_convert (*new_type, const_oprnd);
1040
1041   return true;
1042 }
1043
1044
1045 /* Try to find a statement or a sequence of statements that can be performed
1046    on a smaller type:
1047
1048      type x_t;
1049      TYPE x_T, res0_T, res1_T;
1050    loop:
1051      S1  x_t = *p;
1052      S2  x_T = (TYPE) x_t;
1053      S3  res0_T = op (x_T, C0);
1054      S4  res1_T = op (res0_T, C1);
1055      S5  ... = () res1_T;  - type demotion
1056
1057    where type 'TYPE' is at least double the size of type 'type', C0 and C1 are
1058    constants.
1059    Check if S3 and S4 can be done on a smaller type than 'TYPE', it can either
1060    be 'type' or some intermediate type.  For now, we expect S5 to be a type
1061    demotion operation.  We also check that S3 and S4 have only one use.
1062 .
1063
1064 */
1065 static gimple
1066 vect_recog_over_widening_pattern (VEC (gimple, heap) **stmts,
1067                                   tree *type_in, tree *type_out)
1068 {
1069   gimple stmt = VEC_pop (gimple, *stmts);
1070   gimple pattern_stmt = NULL, new_def_stmt, prev_stmt = NULL, use_stmt = NULL;
1071   tree op0, op1, vectype = NULL_TREE, lhs, use_lhs, use_type;
1072   imm_use_iterator imm_iter;
1073   use_operand_p use_p;
1074   int nuses = 0;
1075   tree var = NULL_TREE, new_type = NULL_TREE, tmp, new_oprnd;
1076   bool first;
1077   struct loop *loop = (gimple_bb (stmt))->loop_father;
1078
1079   first = true;
1080   while (1)
1081     {
1082       if (!vinfo_for_stmt (stmt)
1083           || STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (stmt)))
1084         return NULL;
1085
1086       new_def_stmt = NULL;
1087       if (!vect_operation_fits_smaller_type (stmt, var, &new_type,
1088                                              &op0, &op1, &new_def_stmt,
1089                                              stmts))
1090         {
1091           if (first)
1092             return NULL;
1093           else
1094             break;
1095         }
1096
1097       /* STMT can be performed on a smaller type.  Check its uses.  */
1098       lhs = gimple_assign_lhs (stmt);
1099       nuses = 0;
1100       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
1101         {
1102           if (is_gimple_debug (USE_STMT (use_p)))
1103             continue;
1104           use_stmt = USE_STMT (use_p);
1105           nuses++;
1106         }
1107
1108       if (nuses != 1 || !is_gimple_assign (use_stmt)
1109           || !gimple_bb (use_stmt)
1110           || !flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
1111         return NULL;
1112
1113       /* Create pattern statement for STMT.  */
1114       vectype = get_vectype_for_scalar_type (new_type);
1115       if (!vectype)
1116         return NULL;
1117
1118       /* We want to collect all the statements for which we create pattern
1119          statetments, except for the case when the last statement in the
1120          sequence doesn't have a corresponding pattern statement.  In such
1121          case we associate the last pattern statement with the last statement
1122          in the sequence.  Therefore, we only add an original statetement to
1123          the list if we know that it is not the last.  */
1124       if (prev_stmt)
1125         VEC_safe_push (gimple, heap, *stmts, prev_stmt);
1126
1127       var = vect_recog_temp_ssa_var (new_type, NULL);
1128       pattern_stmt = gimple_build_assign_with_ops (
1129                           gimple_assign_rhs_code (stmt), var, op0, op1);
1130       SSA_NAME_DEF_STMT (var) = pattern_stmt;
1131       STMT_VINFO_RELATED_STMT (vinfo_for_stmt (stmt)) = pattern_stmt;
1132       STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (stmt)) = new_def_stmt;
1133
1134       if (vect_print_dump_info (REPORT_DETAILS))
1135         {
1136           fprintf (vect_dump, "created pattern stmt: ");
1137           print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1138         }
1139
1140       prev_stmt = stmt;
1141       stmt = use_stmt;
1142
1143       first = false;
1144     }
1145
1146   /* We got a sequence.  We expect it to end with a type demotion operation.
1147      Otherwise, we quit (for now).  There are three possible cases: the
1148      conversion is to NEW_TYPE (we don't do anything), the conversion is to
1149      a type bigger than NEW_TYPE and/or the signedness of USE_TYPE and
1150      NEW_TYPE differs (we create a new conversion statement).  */
1151   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (use_stmt)))
1152     {
1153       use_lhs = gimple_assign_lhs (use_stmt);
1154       use_type = TREE_TYPE (use_lhs);
1155       /* Support only type promotion or signedess change.  */
1156       if (!INTEGRAL_TYPE_P (use_type)
1157           || TYPE_PRECISION (new_type) > TYPE_PRECISION (use_type))
1158         return NULL;
1159
1160       if (TYPE_UNSIGNED (new_type) != TYPE_UNSIGNED (use_type)
1161           || TYPE_PRECISION (new_type) != TYPE_PRECISION (use_type))
1162         {
1163           /* Create NEW_TYPE->USE_TYPE conversion.  */
1164           tmp = create_tmp_reg (use_type, NULL);
1165           add_referenced_var (tmp);
1166           new_oprnd = make_ssa_name (tmp, NULL);
1167           pattern_stmt = gimple_build_assign_with_ops (NOP_EXPR, new_oprnd,
1168                                                        var, NULL_TREE);
1169           SSA_NAME_DEF_STMT (new_oprnd) = pattern_stmt;
1170           STMT_VINFO_RELATED_STMT (vinfo_for_stmt (use_stmt)) = pattern_stmt;
1171
1172           *type_in = get_vectype_for_scalar_type (new_type);
1173           *type_out = get_vectype_for_scalar_type (use_type);
1174
1175           /* We created a pattern statement for the last statement in the
1176              sequence, so we don't need to associate it with the pattern
1177              statement created for PREV_STMT.  Therefore, we add PREV_STMT
1178              to the list in order to mark it later in vect_pattern_recog_1.  */
1179           if (prev_stmt)
1180             VEC_safe_push (gimple, heap, *stmts, prev_stmt);
1181         }
1182       else
1183         {
1184           if (prev_stmt)
1185             STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (use_stmt))
1186                = STMT_VINFO_PATTERN_DEF_STMT (vinfo_for_stmt (prev_stmt));
1187
1188           *type_in = vectype;
1189           *type_out = NULL_TREE;
1190         }
1191
1192       VEC_safe_push (gimple, heap, *stmts, use_stmt);
1193     }
1194   else
1195     /* TODO: support general case, create a conversion to the correct type.  */
1196     return NULL;
1197
1198   /* Pattern detected.  */
1199   if (vect_print_dump_info (REPORT_DETAILS))
1200     {
1201       fprintf (vect_dump, "vect_recog_over_widening_pattern: detected: ");
1202       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1203     }
1204
1205   return pattern_stmt;
1206 }
1207
1208
1209 /* Mark statements that are involved in a pattern.  */
1210
1211 static inline void
1212 vect_mark_pattern_stmts (gimple orig_stmt, gimple pattern_stmt,
1213                          tree pattern_vectype)
1214 {
1215   stmt_vec_info pattern_stmt_info, def_stmt_info;
1216   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
1217   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (orig_stmt_info);
1218   gimple def_stmt;
1219
1220   set_vinfo_for_stmt (pattern_stmt,
1221                       new_stmt_vec_info (pattern_stmt, loop_vinfo, NULL));
1222   gimple_set_bb (pattern_stmt, gimple_bb (orig_stmt));
1223   pattern_stmt_info = vinfo_for_stmt (pattern_stmt);
1224
1225   STMT_VINFO_RELATED_STMT (pattern_stmt_info) = orig_stmt;
1226   STMT_VINFO_DEF_TYPE (pattern_stmt_info)
1227         = STMT_VINFO_DEF_TYPE (orig_stmt_info);
1228   STMT_VINFO_VECTYPE (pattern_stmt_info) = pattern_vectype;
1229   STMT_VINFO_IN_PATTERN_P (orig_stmt_info) = true;
1230   STMT_VINFO_RELATED_STMT (orig_stmt_info) = pattern_stmt;
1231   STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info)
1232         = STMT_VINFO_PATTERN_DEF_STMT (orig_stmt_info);
1233   if (STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info))
1234     {
1235       def_stmt = STMT_VINFO_PATTERN_DEF_STMT (pattern_stmt_info);
1236       set_vinfo_for_stmt (def_stmt,
1237                           new_stmt_vec_info (def_stmt, loop_vinfo, NULL));
1238       gimple_set_bb (def_stmt, gimple_bb (orig_stmt));
1239       def_stmt_info = vinfo_for_stmt (def_stmt);
1240       STMT_VINFO_RELATED_STMT (def_stmt_info) = orig_stmt;
1241       STMT_VINFO_DEF_TYPE (def_stmt_info)
1242         = STMT_VINFO_DEF_TYPE (orig_stmt_info);
1243       STMT_VINFO_VECTYPE (def_stmt_info) = pattern_vectype;
1244     }
1245 }
1246
1247 /* Function vect_pattern_recog_1
1248
1249    Input:
1250    PATTERN_RECOG_FUNC: A pointer to a function that detects a certain
1251         computation pattern.
1252    STMT: A stmt from which the pattern search should start.
1253
1254    If PATTERN_RECOG_FUNC successfully detected the pattern, it creates an
1255    expression that computes the same functionality and can be used to
1256    replace the sequence of stmts that are involved in the pattern.
1257
1258    Output:
1259    This function checks if the expression returned by PATTERN_RECOG_FUNC is
1260    supported in vector form by the target.  We use 'TYPE_IN' to obtain the
1261    relevant vector type. If 'TYPE_IN' is already a vector type, then this
1262    indicates that target support had already been checked by PATTERN_RECOG_FUNC.
1263    If 'TYPE_OUT' is also returned by PATTERN_RECOG_FUNC, we check that it fits
1264    to the available target pattern.
1265
1266    This function also does some bookkeeping, as explained in the documentation
1267    for vect_recog_pattern.  */
1268
1269 static void
1270 vect_pattern_recog_1 (
1271         gimple (* vect_recog_func) (VEC (gimple, heap) **, tree *, tree *),
1272         gimple_stmt_iterator si)
1273 {
1274   gimple stmt = gsi_stmt (si), pattern_stmt;
1275   stmt_vec_info stmt_info;
1276   loop_vec_info loop_vinfo;
1277   tree pattern_vectype;
1278   tree type_in, type_out;
1279   enum tree_code code;
1280   int i;
1281   gimple next;
1282   VEC (gimple, heap) *stmts_to_replace = VEC_alloc (gimple, heap, 1);
1283
1284   VEC_quick_push (gimple, stmts_to_replace, stmt);
1285   pattern_stmt = (* vect_recog_func) (&stmts_to_replace, &type_in, &type_out);
1286   if (!pattern_stmt)
1287     return;
1288
1289   stmt = VEC_last (gimple, stmts_to_replace);
1290   stmt_info = vinfo_for_stmt (stmt);
1291   loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1292
1293   if (VECTOR_MODE_P (TYPE_MODE (type_in)))
1294     {
1295       /* No need to check target support (already checked by the pattern
1296          recognition function).  */
1297       if (type_out)
1298         gcc_assert (VECTOR_MODE_P (TYPE_MODE (type_out)));
1299       pattern_vectype = type_out ? type_out : type_in;
1300     }
1301   else
1302     {
1303       enum machine_mode vec_mode;
1304       enum insn_code icode;
1305       optab optab;
1306
1307       /* Check target support  */
1308       type_in = get_vectype_for_scalar_type (type_in);
1309       if (!type_in)
1310         return;
1311       if (type_out)
1312         type_out = get_vectype_for_scalar_type (type_out);
1313       else
1314         type_out = type_in;
1315       if (!type_out)
1316         return;
1317       pattern_vectype = type_out;
1318
1319       if (is_gimple_assign (pattern_stmt))
1320         code = gimple_assign_rhs_code (pattern_stmt);
1321       else
1322         {
1323           gcc_assert (is_gimple_call (pattern_stmt));
1324           code = CALL_EXPR;
1325         }
1326
1327       optab = optab_for_tree_code (code, type_in, optab_default);
1328       vec_mode = TYPE_MODE (type_in);
1329       if (!optab
1330           || (icode = optab_handler (optab, vec_mode)) == CODE_FOR_nothing
1331           || (insn_data[icode].operand[0].mode != TYPE_MODE (type_out)))
1332         return;
1333     }
1334
1335   /* Found a vectorizable pattern.  */
1336   if (vect_print_dump_info (REPORT_DETAILS))
1337     {
1338       fprintf (vect_dump, "pattern recognized: ");
1339       print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1340     }
1341
1342   /* Mark the stmts that are involved in the pattern. */
1343   vect_mark_pattern_stmts (stmt, pattern_stmt, pattern_vectype);
1344
1345   /* Patterns cannot be vectorized using SLP, because they change the order of
1346      computation.  */
1347   FOR_EACH_VEC_ELT (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i, next)
1348     if (next == stmt)
1349       VEC_ordered_remove (gimple, LOOP_VINFO_REDUCTIONS (loop_vinfo), i);
1350
1351   /* It is possible that additional pattern stmts are created and inserted in
1352      STMTS_TO_REPLACE.  We create a stmt_info for each of them, and mark the
1353      relevant statements.  */
1354   for (i = 0; VEC_iterate (gimple, stmts_to_replace, i, stmt)
1355               && (unsigned) i < (VEC_length (gimple, stmts_to_replace) - 1);
1356        i++)
1357     {
1358       stmt_info = vinfo_for_stmt (stmt);
1359       pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1360       if (vect_print_dump_info (REPORT_DETAILS))
1361         {
1362           fprintf (vect_dump, "additional pattern stmt: ");
1363           print_gimple_stmt (vect_dump, pattern_stmt, 0, TDF_SLIM);
1364         }
1365
1366       vect_mark_pattern_stmts (stmt, pattern_stmt, NULL_TREE);
1367     }
1368
1369   VEC_free (gimple, heap, stmts_to_replace);
1370 }
1371
1372
1373 /* Function vect_pattern_recog
1374
1375    Input:
1376    LOOP_VINFO - a struct_loop_info of a loop in which we want to look for
1377         computation idioms.
1378
1379    Output - for each computation idiom that is detected we create a new stmt
1380         that provides the same functionality and that can be vectorized.  We
1381         also record some information in the struct_stmt_info of the relevant
1382         stmts, as explained below:
1383
1384    At the entry to this function we have the following stmts, with the
1385    following initial value in the STMT_VINFO fields:
1386
1387          stmt                     in_pattern_p  related_stmt    vec_stmt
1388          S1: a_i = ....                 -       -               -
1389          S2: a_2 = ..use(a_i)..         -       -               -
1390          S3: a_1 = ..use(a_2)..         -       -               -
1391          S4: a_0 = ..use(a_1)..         -       -               -
1392          S5: ... = ..use(a_0)..         -       -               -
1393
1394    Say the sequence {S1,S2,S3,S4} was detected as a pattern that can be
1395    represented by a single stmt.  We then:
1396    - create a new stmt S6 equivalent to the pattern (the stmt is not
1397      inserted into the code)
1398    - fill in the STMT_VINFO fields as follows:
1399
1400                                   in_pattern_p  related_stmt    vec_stmt
1401          S1: a_i = ....                 -       -               -
1402          S2: a_2 = ..use(a_i)..         -       -               -
1403          S3: a_1 = ..use(a_2)..         -       -               -
1404          S4: a_0 = ..use(a_1)..         true    S6              -
1405           '---> S6: a_new = ....        -       S4              -
1406          S5: ... = ..use(a_0)..         -       -               -
1407
1408    (the last stmt in the pattern (S4) and the new pattern stmt (S6) point
1409    to each other through the RELATED_STMT field).
1410
1411    S6 will be marked as relevant in vect_mark_stmts_to_be_vectorized instead
1412    of S4 because it will replace all its uses.  Stmts {S1,S2,S3} will
1413    remain irrelevant unless used by stmts other than S4.
1414
1415    If vectorization succeeds, vect_transform_stmt will skip over {S1,S2,S3}
1416    (because they are marked as irrelevant).  It will vectorize S6, and record
1417    a pointer to the new vector stmt VS6 from S6 (as usual).
1418    S4 will be skipped, and S5 will be vectorized as usual:
1419
1420                                   in_pattern_p  related_stmt    vec_stmt
1421          S1: a_i = ....                 -       -               -
1422          S2: a_2 = ..use(a_i)..         -       -               -
1423          S3: a_1 = ..use(a_2)..         -       -               -
1424        > VS6: va_new = ....             -       -               -
1425          S4: a_0 = ..use(a_1)..         true    S6              VS6
1426           '---> S6: a_new = ....        -       S4              VS6
1427        > VS5: ... = ..vuse(va_new)..    -       -               -
1428          S5: ... = ..use(a_0)..         -       -               -
1429
1430    DCE could then get rid of {S1,S2,S3,S4,S5} (if their defs are not used
1431    elsewhere), and we'll end up with:
1432
1433         VS6: va_new = ....
1434         VS5: ... = ..vuse(va_new)..
1435
1436    In case of more than one pattern statements, e.g., widen-mult with
1437    intermediate type:
1438
1439      S1  a_t = ;
1440      S2  a_T = (TYPE) a_t;
1441            '--> S3: a_it = (interm_type) a_t;
1442      S4  prod_T = a_T * CONST;
1443            '--> S5: prod_T' = a_it w* CONST;
1444
1445    there may be other users of a_T outside the pattern.  In that case S2 will
1446    be marked as relevant (as well as S3), and both S2 and S3 will be analyzed
1447    and vectorized.  The vector stmt VS2 will be recorded in S2, and VS3 will
1448    be recorded in S3.  */
1449
1450 void
1451 vect_pattern_recog (loop_vec_info loop_vinfo)
1452 {
1453   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1454   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1455   unsigned int nbbs = loop->num_nodes;
1456   gimple_stmt_iterator si;
1457   unsigned int i, j;
1458   gimple (* vect_recog_func_ptr) (VEC (gimple, heap) **, tree *, tree *);
1459
1460   if (vect_print_dump_info (REPORT_DETAILS))
1461     fprintf (vect_dump, "=== vect_pattern_recog ===");
1462
1463   /* Scan through the loop stmts, applying the pattern recognition
1464      functions starting at each stmt visited:  */
1465   for (i = 0; i < nbbs; i++)
1466     {
1467       basic_block bb = bbs[i];
1468       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1469         {
1470           /* Scan over all generic vect_recog_xxx_pattern functions.  */
1471           for (j = 0; j < NUM_PATTERNS; j++)
1472             {
1473               vect_recog_func_ptr = vect_vect_recog_func_ptrs[j];
1474               vect_pattern_recog_1 (vect_recog_func_ptr, si);
1475             }
1476         }
1477     }
1478 }