contrib/gcc-5.0/gcc/tree-vect-slp.c

   1 /* SLP - Basic Block Vectorization
   2    Copyright (C) 2007-2015 Free Software Foundation, Inc.
   3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
   4    and Ira Rosen <irar@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 "dumpfile.h"
  26 #include "tm.h"
  27 #include "hash-set.h"
  28 #include "machmode.h"
  29 #include "vec.h"
  30 #include "double-int.h"
  31 #include "input.h"
  32 #include "alias.h"
  33 #include "symtab.h"
  34 #include "wide-int.h"
  35 #include "inchash.h"
  36 #include "tree.h"
  37 #include "fold-const.h"
  38 #include "stor-layout.h"
  39 #include "target.h"
  40 #include "predict.h"
  41 #include "hard-reg-set.h"
  42 #include "function.h"
  43 #include "basic-block.h"
  44 #include "gimple-pretty-print.h"
  45 #include "tree-ssa-alias.h"
  46 #include "internal-fn.h"
  47 #include "gimple-expr.h"
  48 #include "is-a.h"
  49 #include "gimple.h"
  50 #include "gimple-iterator.h"
  51 #include "gimple-ssa.h"
  52 #include "tree-phinodes.h"
  53 #include "ssa-iterators.h"
  54 #include "stringpool.h"
  55 #include "tree-ssanames.h"
  56 #include "tree-pass.h"
  57 #include "cfgloop.h"
  58 #include "hashtab.h"
  59 #include "rtl.h"
  60 #include "flags.h"
  61 #include "statistics.h"
  62 #include "real.h"
  63 #include "fixed-value.h"
  64 #include "insn-config.h"
  65 #include "expmed.h"
  66 #include "dojump.h"
  67 #include "explow.h"
  68 #include "calls.h"
  69 #include "emit-rtl.h"
  70 #include "varasm.h"
  71 #include "stmt.h"
  72 #include "expr.h"
  73 #include "recog.h"              /* FIXME: for insn_data */
  74 #include "insn-codes.h"
  75 #include "optabs.h"
  76 #include "tree-vectorizer.h"
  77 #include "langhooks.h"
  78 #include "gimple-walk.h"
  79
  80 /* Extract the location of the basic block in the source code.
  81    Return the basic block location if succeed and NULL if not.  */
  82
  83 source_location
  84 find_bb_location (basic_block bb)
  85 {
  86   gimple stmt = NULL;
  87   gimple_stmt_iterator si;
  88
  89   if (!bb)
  90     return UNKNOWN_LOCATION;
  91
  92   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
  93     {
  94       stmt = gsi_stmt (si);
  95       if (gimple_location (stmt) != UNKNOWN_LOCATION)
  96         return gimple_location (stmt);
  97     }
  98
  99   return UNKNOWN_LOCATION;
 100 }
 101
 102
 103 /* Recursively free the memory allocated for the SLP tree rooted at NODE.  */
 104
 105 static void
 106 vect_free_slp_tree (slp_tree node)
 107 {
 108   int i;
 109   slp_tree child;
 110
 111   if (!node)
 112     return;
 113
 114   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
 115     vect_free_slp_tree (child);
 116
 117   SLP_TREE_CHILDREN (node).release ();
 118   SLP_TREE_SCALAR_STMTS (node).release ();
 119   SLP_TREE_VEC_STMTS (node).release ();
 120   SLP_TREE_LOAD_PERMUTATION (node).release ();
 121
 122   free (node);
 123 }
 124
 125
 126 /* Free the memory allocated for the SLP instance.  */
 127
 128 void
 129 vect_free_slp_instance (slp_instance instance)
 130 {
 131   vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
 132   SLP_INSTANCE_LOADS (instance).release ();
 133   SLP_INSTANCE_BODY_COST_VEC (instance).release ();
 134   free (instance);
 135 }
 136
 137
 138 /* Create an SLP node for SCALAR_STMTS.  */
 139
 140 static slp_tree
 141 vect_create_new_slp_node (vec<gimple> scalar_stmts)
 142 {
 143   slp_tree node;
 144   gimple stmt = scalar_stmts[0];
 145   unsigned int nops;
 146
 147   if (is_gimple_call (stmt))
 148     nops = gimple_call_num_args (stmt);
 149   else if (is_gimple_assign (stmt))
 150     {
 151       nops = gimple_num_ops (stmt) - 1;
 152       if (gimple_assign_rhs_code (stmt) == COND_EXPR)
 153         nops++;
 154     }
 155   else
 156     return NULL;
 157
 158   node = XNEW (struct _slp_tree);
 159   SLP_TREE_SCALAR_STMTS (node) = scalar_stmts;
 160   SLP_TREE_VEC_STMTS (node).create (0);
 161   SLP_TREE_CHILDREN (node).create (nops);
 162   SLP_TREE_LOAD_PERMUTATION (node) = vNULL;
 163
 164   return node;
 165 }
 166
 167
 168 /* Allocate operands info for NOPS operands, and GROUP_SIZE def-stmts for each
 169    operand.  */
 170 static vec<slp_oprnd_info>
 171 vect_create_oprnd_info (int nops, int group_size)
 172 {
 173   int i;
 174   slp_oprnd_info oprnd_info;
 175   vec<slp_oprnd_info> oprnds_info;
 176
 177   oprnds_info.create (nops);
 178   for (i = 0; i < nops; i++)
 179     {
 180       oprnd_info = XNEW (struct _slp_oprnd_info);
 181       oprnd_info->def_stmts.create (group_size);
 182       oprnd_info->first_dt = vect_uninitialized_def;
 183       oprnd_info->first_op_type = NULL_TREE;
 184       oprnd_info->first_pattern = false;
 185       oprnds_info.quick_push (oprnd_info);
 186     }
 187
 188   return oprnds_info;
 189 }
 190
 191
 192 /* Free operands info.  */
 193
 194 static void
 195 vect_free_oprnd_info (vec<slp_oprnd_info> &oprnds_info)
 196 {
 197   int i;
 198   slp_oprnd_info oprnd_info;
 199
 200   FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info)
 201     {
 202       oprnd_info->def_stmts.release ();
 203       XDELETE (oprnd_info);
 204     }
 205
 206   oprnds_info.release ();
 207 }
 208
 209
 210 /* Find the place of the data-ref in STMT in the interleaving chain that starts
 211    from FIRST_STMT.  Return -1 if the data-ref is not a part of the chain.  */
 212
 213 static int
 214 vect_get_place_in_interleaving_chain (gimple stmt, gimple first_stmt)
 215 {
 216   gimple next_stmt = first_stmt;
 217   int result = 0;
 218
 219   if (first_stmt != GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
 220     return -1;
 221
 222   do
 223     {
 224       if (next_stmt == stmt)
 225         return result;
 226       result++;
 227       next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
 228     }
 229   while (next_stmt);
 230
 231   return -1;
 232 }
 233
 234
 235 /* Get the defs for the rhs of STMT (collect them in OPRNDS_INFO), check that
 236    they are of a valid type and that they match the defs of the first stmt of
 237    the SLP group (stored in OPRNDS_INFO).  If there was a fatal error
 238    return -1, if the error could be corrected by swapping operands of the
 239    operation return 1, if everything is ok return 0.  */
 240
 241 static int
 242 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 243                              gimple stmt, bool first,
 244                              vec<slp_oprnd_info> *oprnds_info)
 245 {
 246   tree oprnd;
 247   unsigned int i, number_of_oprnds;
 248   tree def;
 249   gimple def_stmt;
 250   enum vect_def_type dt = vect_uninitialized_def;
 251   struct loop *loop = NULL;
 252   bool pattern = false;
 253   slp_oprnd_info oprnd_info;
 254   int first_op_idx = 1;
 255   bool commutative = false;
 256   bool first_op_cond = false;
 257
 258   if (loop_vinfo)
 259     loop = LOOP_VINFO_LOOP (loop_vinfo);
 260
 261   if (is_gimple_call (stmt))
 262     {
 263       number_of_oprnds = gimple_call_num_args (stmt);
 264       first_op_idx = 3;
 265     }
 266   else if (is_gimple_assign (stmt))
 267     {
 268       enum tree_code code = gimple_assign_rhs_code (stmt);
 269       number_of_oprnds = gimple_num_ops (stmt) - 1;
 270       if (gimple_assign_rhs_code (stmt) == COND_EXPR)
 271         {
 272           first_op_cond = true;
 273           commutative = true;
 274           number_of_oprnds++;
 275         }
 276       else
 277         commutative = commutative_tree_code (code);
 278     }
 279   else
 280     return -1;
 281
 282   bool swapped = false;
 283   for (i = 0; i < number_of_oprnds; i++)
 284     {
 285 again:
 286       if (first_op_cond)
 287         {
 288           if (i == 0 || i == 1)
 289             oprnd = TREE_OPERAND (gimple_op (stmt, first_op_idx),
 290                                   swapped ? !i : i);
 291           else
 292             oprnd = gimple_op (stmt, first_op_idx + i - 1);
 293         }
 294       else
 295         oprnd = gimple_op (stmt, first_op_idx + (swapped ? !i : i));
 296
 297       oprnd_info = (*oprnds_info)[i];
 298
 299       if (!vect_is_simple_use (oprnd, NULL, loop_vinfo, bb_vinfo, &def_stmt,
 300                                &def, &dt)
 301           || (!def_stmt && dt != vect_constant_def))
 302         {
 303           if (dump_enabled_p ())
 304             {
 305               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 306                                "Build SLP failed: can't find def for ");
 307               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, oprnd);
 308               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 309             }
 310
 311           return -1;
 312         }
 313
 314       /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
 315          from the pattern.  Check that all the stmts of the node are in the
 316          pattern.  */
 317       if (def_stmt && gimple_bb (def_stmt)
 318           && ((loop && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt)))
 319               || (!loop && gimple_bb (def_stmt) == BB_VINFO_BB (bb_vinfo)
 320                   && gimple_code (def_stmt) != GIMPLE_PHI))
 321           && vinfo_for_stmt (def_stmt)
 322           && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt))
 323           && !STMT_VINFO_RELEVANT (vinfo_for_stmt (def_stmt))
 324           && !STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt)))
 325         {
 326           pattern = true;
 327           if (!first && !oprnd_info->first_pattern)
 328             {
 329               if (i == 0
 330                   && !swapped
 331                   && commutative)
 332                 {
 333                   swapped = true;
 334                   goto again;
 335                 }
 336
 337               if (dump_enabled_p ())
 338                 {
 339                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 340                                    "Build SLP failed: some of the stmts"
 341                                    " are in a pattern, and others are not ");
 342                   dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, oprnd);
 343                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 344                 }
 345
 346               return 1;
 347             }
 348
 349           def_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
 350           dt = STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt));
 351
 352           if (dt == vect_unknown_def_type)
 353             {
 354               if (dump_enabled_p ())
 355                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 356                                  "Unsupported pattern.\n");
 357               return -1;
 358             }
 359
 360           switch (gimple_code (def_stmt))
 361             {
 362               case GIMPLE_PHI:
 363                 def = gimple_phi_result (def_stmt);
 364                 break;
 365
 366               case GIMPLE_ASSIGN:
 367                 def = gimple_assign_lhs (def_stmt);
 368                 break;
 369
 370               default:
 371                 if (dump_enabled_p ())
 372                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 373                                    "unsupported defining stmt:\n");
 374                 return -1;
 375             }
 376         }
 377
 378       if (first)
 379         {
 380           oprnd_info->first_dt = dt;
 381           oprnd_info->first_pattern = pattern;
 382           oprnd_info->first_op_type = TREE_TYPE (oprnd);
 383         }
 384       else
 385         {
 386           /* Not first stmt of the group, check that the def-stmt/s match
 387              the def-stmt/s of the first stmt.  Allow different definition
 388              types for reduction chains: the first stmt must be a
 389              vect_reduction_def (a phi node), and the rest
 390              vect_internal_def.  */
 391           if (((oprnd_info->first_dt != dt
 392                 && !(oprnd_info->first_dt == vect_reduction_def
 393                      && dt == vect_internal_def)
 394                 && !((oprnd_info->first_dt == vect_external_def
 395                       || oprnd_info->first_dt == vect_constant_def)
 396                      && (dt == vect_external_def
 397                          || dt == vect_constant_def)))
 398                || !types_compatible_p (oprnd_info->first_op_type,
 399                                        TREE_TYPE (oprnd))))
 400             {
 401               /* Try swapping operands if we got a mismatch.  */
 402               if (i == 0
 403                   && !swapped
 404                   && commutative)
 405                 {
 406                   swapped = true;
 407                   goto again;
 408                 }
 409
 410               if (dump_enabled_p ())
 411                 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 412                                  "Build SLP failed: different types\n");
 413
 414               return 1;
 415             }
 416         }
 417
 418       /* Check the types of the definitions.  */
 419       switch (dt)
 420         {
 421         case vect_constant_def:
 422         case vect_external_def:
 423         case vect_reduction_def:
 424           break;
 425
 426         case vect_internal_def:
 427           oprnd_info->def_stmts.quick_push (def_stmt);
 428           break;
 429
 430         default:
 431           /* FORNOW: Not supported.  */
 432           if (dump_enabled_p ())
 433             {
 434               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 435                                "Build SLP failed: illegal type of def ");
 436               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, def);
 437               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 438             }
 439
 440           return -1;
 441         }
 442     }
 443
 444   /* Swap operands.  */
 445   if (swapped)
 446     {
 447       if (first_op_cond)
 448         {
 449           tree cond = gimple_assign_rhs1 (stmt);
 450           swap_ssa_operands (stmt, &TREE_OPERAND (cond, 0),
 451                              &TREE_OPERAND (cond, 1));
 452           TREE_SET_CODE (cond, swap_tree_comparison (TREE_CODE (cond)));
 453         }
 454       else
 455         swap_ssa_operands (stmt, gimple_assign_rhs1_ptr (stmt),
 456                            gimple_assign_rhs2_ptr (stmt));
 457     }
 458
 459   return 0;
 460 }
 461
 462
 463 /* Verify if the scalar stmts STMTS are isomorphic, require data
 464    permutation or are of unsupported types of operation.  Return
 465    true if they are, otherwise return false and indicate in *MATCHES
 466    which stmts are not isomorphic to the first one.  If MATCHES[0]
 467    is false then this indicates the comparison could not be
 468    carried out or the stmts will never be vectorized by SLP.  */
 469
 470 static bool
 471 vect_build_slp_tree_1 (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 472                        vec<gimple> stmts, unsigned int group_size,
 473                        unsigned nops, unsigned int *max_nunits,
 474                        unsigned int vectorization_factor, bool *matches)
 475 {
 476   unsigned int i;
 477   gimple stmt = stmts[0];
 478   enum tree_code first_stmt_code = ERROR_MARK, rhs_code = ERROR_MARK;
 479   enum tree_code first_cond_code = ERROR_MARK;
 480   tree lhs;
 481   bool need_same_oprnds = false;
 482   tree vectype, scalar_type, first_op1 = NULL_TREE;
 483   optab optab;
 484   int icode;
 485   machine_mode optab_op2_mode;
 486   machine_mode vec_mode;
 487   struct data_reference *first_dr;
 488   HOST_WIDE_INT dummy;
 489   gimple first_load = NULL, prev_first_load = NULL, old_first_load = NULL;
 490   tree cond;
 491
 492   /* For every stmt in NODE find its def stmt/s.  */
 493   FOR_EACH_VEC_ELT (stmts, i, stmt)
 494     {
 495       matches[i] = false;
 496
 497       if (dump_enabled_p ())
 498         {
 499           dump_printf_loc (MSG_NOTE, vect_location, "Build SLP for ");
 500           dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
 501           dump_printf (MSG_NOTE, "\n");
 502         }
 503
 504       /* Fail to vectorize statements marked as unvectorizable.  */
 505       if (!STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (stmt)))
 506         {
 507           if (dump_enabled_p ())
 508             {
 509               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 510                                "Build SLP failed: unvectorizable statement ");
 511               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 512               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 513             }
 514           /* Fatal mismatch.  */
 515           matches[0] = false;
 516           return false;
 517         }
 518
 519       lhs = gimple_get_lhs (stmt);
 520       if (lhs == NULL_TREE)
 521         {
 522           if (dump_enabled_p ())
 523             {
 524               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 525                                "Build SLP failed: not GIMPLE_ASSIGN nor "
 526                                "GIMPLE_CALL ");
 527               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 528               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 529             }
 530           /* Fatal mismatch.  */
 531           matches[0] = false;
 532           return false;
 533         }
 534
 535        if (is_gimple_assign (stmt)
 536            && gimple_assign_rhs_code (stmt) == COND_EXPR
 537            && (cond = gimple_assign_rhs1 (stmt))
 538            && !COMPARISON_CLASS_P (cond))
 539         {
 540           if (dump_enabled_p ())
 541             {
 542               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 543                                "Build SLP failed: condition is not "
 544                                "comparison ");
 545               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 546               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 547             }
 548           /* Fatal mismatch.  */
 549           matches[0] = false;
 550           return false;
 551         }
 552
 553       scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
 554       vectype = get_vectype_for_scalar_type (scalar_type);
 555       if (!vectype)
 556         {
 557           if (dump_enabled_p ())
 558             {
 559               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 560                                "Build SLP failed: unsupported data-type ");
 561               dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 562                                  scalar_type);
 563               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 564             }
 565           /* Fatal mismatch.  */
 566           matches[0] = false;
 567           return false;
 568         }
 569
 570       /* In case of multiple types we need to detect the smallest type.  */
 571       if (*max_nunits < TYPE_VECTOR_SUBPARTS (vectype))
 572         {
 573           *max_nunits = TYPE_VECTOR_SUBPARTS (vectype);
 574           if (bb_vinfo)
 575             vectorization_factor = *max_nunits;
 576         }
 577
 578       if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
 579         {
 580           rhs_code = CALL_EXPR;
 581           if (gimple_call_internal_p (call_stmt)
 582               || gimple_call_tail_p (call_stmt)
 583               || gimple_call_noreturn_p (call_stmt)
 584               || !gimple_call_nothrow_p (call_stmt)
 585               || gimple_call_chain (call_stmt))
 586             {
 587               if (dump_enabled_p ())
 588                 {
 589                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 590                                    "Build SLP failed: unsupported call type ");
 591                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 592                                     call_stmt, 0);
 593                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 594                 }
 595               /* Fatal mismatch.  */
 596               matches[0] = false;
 597               return false;
 598             }
 599         }
 600       else
 601         rhs_code = gimple_assign_rhs_code (stmt);
 602
 603       /* Check the operation.  */
 604       if (i == 0)
 605         {
 606           first_stmt_code = rhs_code;
 607
 608           /* Shift arguments should be equal in all the packed stmts for a
 609              vector shift with scalar shift operand.  */
 610           if (rhs_code == LSHIFT_EXPR || rhs_code == RSHIFT_EXPR
 611               || rhs_code == LROTATE_EXPR
 612               || rhs_code == RROTATE_EXPR)
 613             {
 614               vec_mode = TYPE_MODE (vectype);
 615
 616               /* First see if we have a vector/vector shift.  */
 617               optab = optab_for_tree_code (rhs_code, vectype,
 618                                            optab_vector);
 619
 620               if (!optab
 621                   || optab_handler (optab, vec_mode) == CODE_FOR_nothing)
 622                 {
 623                   /* No vector/vector shift, try for a vector/scalar shift.  */
 624                   optab = optab_for_tree_code (rhs_code, vectype,
 625                                                optab_scalar);
 626
 627                   if (!optab)
 628                     {
 629                       if (dump_enabled_p ())
 630                         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 631                                          "Build SLP failed: no optab.\n");
 632                       /* Fatal mismatch.  */
 633                       matches[0] = false;
 634                       return false;
 635                     }
 636                   icode = (int) optab_handler (optab, vec_mode);
 637                   if (icode == CODE_FOR_nothing)
 638                     {
 639                       if (dump_enabled_p ())
 640                         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 641                                          "Build SLP failed: "
 642                                          "op not supported by target.\n");
 643                       /* Fatal mismatch.  */
 644                       matches[0] = false;
 645                       return false;
 646                     }
 647                   optab_op2_mode = insn_data[icode].operand[2].mode;
 648                   if (!VECTOR_MODE_P (optab_op2_mode))
 649                     {
 650                       need_same_oprnds = true;
 651                       first_op1 = gimple_assign_rhs2 (stmt);
 652                     }
 653                 }
 654             }
 655           else if (rhs_code == WIDEN_LSHIFT_EXPR)
 656             {
 657               need_same_oprnds = true;
 658               first_op1 = gimple_assign_rhs2 (stmt);
 659             }
 660         }
 661       else
 662         {
 663           if (first_stmt_code != rhs_code
 664               && (first_stmt_code != IMAGPART_EXPR
 665                   || rhs_code != REALPART_EXPR)
 666               && (first_stmt_code != REALPART_EXPR
 667                   || rhs_code != IMAGPART_EXPR)
 668               && !(STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt))
 669                    && (first_stmt_code == ARRAY_REF
 670                        || first_stmt_code == BIT_FIELD_REF
 671                        || first_stmt_code == INDIRECT_REF
 672                        || first_stmt_code == COMPONENT_REF
 673                        || first_stmt_code == MEM_REF)))
 674             {
 675               if (dump_enabled_p ())
 676                 {
 677                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 678                                    "Build SLP failed: different operation "
 679                                    "in stmt ");
 680                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 681                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 682                 }
 683               /* Mismatch.  */
 684               continue;
 685             }
 686
 687           if (need_same_oprnds
 688               && !operand_equal_p (first_op1, gimple_assign_rhs2 (stmt), 0))
 689             {
 690               if (dump_enabled_p ())
 691                 {
 692                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 693                                    "Build SLP failed: different shift "
 694                                    "arguments in ");
 695                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 696                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 697                 }
 698               /* Mismatch.  */
 699               continue;
 700             }
 701
 702           if (rhs_code == CALL_EXPR)
 703             {
 704               gimple first_stmt = stmts[0];
 705               if (gimple_call_num_args (stmt) != nops
 706                   || !operand_equal_p (gimple_call_fn (first_stmt),
 707                                        gimple_call_fn (stmt), 0)
 708                   || gimple_call_fntype (first_stmt)
 709                      != gimple_call_fntype (stmt))
 710                 {
 711                   if (dump_enabled_p ())
 712                     {
 713                       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 714                                        "Build SLP failed: different calls in ");
 715                       dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 716                                         stmt, 0);
 717                       dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 718                     }
 719                   /* Mismatch.  */
 720                   continue;
 721                 }
 722             }
 723         }
 724
 725       /* Grouped store or load.  */
 726       if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt)))
 727         {
 728           if (REFERENCE_CLASS_P (lhs))
 729             {
 730               /* Store.  */
 731               ;
 732             }
 733           else
 734             {
 735               /* Load.  */
 736               unsigned unrolling_factor
 737                 = least_common_multiple
 738                     (*max_nunits, group_size) / group_size;
 739               /* FORNOW: Check that there is no gap between the loads
 740                  and no gap between the groups when we need to load
 741                  multiple groups at once.
 742                  ???  We should enhance this to only disallow gaps
 743                  inside vectors.  */
 744               if ((unrolling_factor > 1
 745                    && ((GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt
 746                         && GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
 747                        /* If the group is split up then GROUP_GAP
 748                           isn't correct here, nor is GROUP_FIRST_ELEMENT.  */
 749                        || GROUP_SIZE (vinfo_for_stmt (stmt)) > group_size))
 750                   || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) != stmt
 751                       && GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
 752                 {
 753                   if (dump_enabled_p ())
 754                     {
 755                       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 756                                        "Build SLP failed: grouped "
 757                                        "loads have gaps ");
 758                       dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 759                                         stmt, 0);
 760                       dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 761                     }
 762                   /* Fatal mismatch.  */
 763                   matches[0] = false;
 764                   return false;
 765                 }
 766
 767               /* Check that the size of interleaved loads group is not
 768                  greater than the SLP group size.  */
 769               unsigned ncopies
 770                 = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
 771               if (loop_vinfo
 772                   && GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)) == stmt
 773                   && ((GROUP_SIZE (vinfo_for_stmt (stmt))
 774                        - GROUP_GAP (vinfo_for_stmt (stmt)))
 775                       > ncopies * group_size))
 776                 {
 777                   if (dump_enabled_p ())
 778                     {
 779                       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 780                                        "Build SLP failed: the number "
 781                                        "of interleaved loads is greater than "
 782                                        "the SLP group size ");
 783                       dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 784                                         stmt, 0);
 785                       dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 786                     }
 787                   /* Fatal mismatch.  */
 788                   matches[0] = false;
 789                   return false;
 790                 }
 791
 792               old_first_load = first_load;
 793               first_load = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt));
 794               if (prev_first_load)
 795                 {
 796                   /* Check that there are no loads from different interleaving
 797                      chains in the same node.  */
 798                   if (prev_first_load != first_load)
 799                     {
 800                       if (dump_enabled_p ())
 801                         {
 802                           dump_printf_loc (MSG_MISSED_OPTIMIZATION,
 803                                            vect_location,
 804                                            "Build SLP failed: different "
 805                                            "interleaving chains in one node ");
 806                           dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 807                                             stmt, 0);
 808                           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 809                         }
 810                       /* Mismatch.  */
 811                       continue;
 812                     }
 813                 }
 814               else
 815                 prev_first_load = first_load;
 816
 817               /* In some cases a group of loads is just the same load
 818                  repeated N times.  Only analyze its cost once.  */
 819               if (first_load == stmt && old_first_load != first_load)
 820                 {
 821                   first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
 822                   if (vect_supportable_dr_alignment (first_dr, false)
 823                       == dr_unaligned_unsupported)
 824                     {
 825                       if (dump_enabled_p ())
 826                         {
 827                           dump_printf_loc (MSG_MISSED_OPTIMIZATION,
 828                                            vect_location,
 829                                            "Build SLP failed: unsupported "
 830                                            "unaligned load ");
 831                           dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 832                                             stmt, 0);
 833                           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 834                         }
 835                       /* Fatal mismatch.  */
 836                       matches[0] = false;
 837                       return false;
 838                     }
 839                 }
 840            }
 841         } /* Grouped access.  */
 842       else
 843         {
 844           if (TREE_CODE_CLASS (rhs_code) == tcc_reference)
 845             {
 846               /* Not grouped load.  */
 847               if (dump_enabled_p ())
 848                 {
 849                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 850                                    "Build SLP failed: not grouped load ");
 851                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 852                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 853                 }
 854
 855               /* FORNOW: Not grouped loads are not supported.  */
 856               /* Fatal mismatch.  */
 857               matches[0] = false;
 858               return false;
 859             }
 860
 861           /* Not memory operation.  */
 862           if (TREE_CODE_CLASS (rhs_code) != tcc_binary
 863               && TREE_CODE_CLASS (rhs_code) != tcc_unary
 864               && rhs_code != COND_EXPR
 865               && rhs_code != CALL_EXPR)
 866             {
 867               if (dump_enabled_p ())
 868                 {
 869                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 870                                    "Build SLP failed: operation");
 871                   dump_printf (MSG_MISSED_OPTIMIZATION, " unsupported ");
 872                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
 873                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 874                 }
 875               /* Fatal mismatch.  */
 876               matches[0] = false;
 877               return false;
 878             }
 879
 880           if (rhs_code == COND_EXPR)
 881             {
 882               tree cond_expr = gimple_assign_rhs1 (stmt);
 883
 884               if (i == 0)
 885                 first_cond_code = TREE_CODE (cond_expr);
 886               else if (first_cond_code != TREE_CODE (cond_expr))
 887                 {
 888                   if (dump_enabled_p ())
 889                     {
 890                       dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
 891                                        "Build SLP failed: different"
 892                                        " operation");
 893                       dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
 894                                         stmt, 0);
 895                       dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
 896                     }
 897                   /* Mismatch.  */
 898                   continue;
 899                 }
 900             }
 901         }
 902
 903       matches[i] = true;
 904     }
 905
 906   for (i = 0; i < group_size; ++i)
 907     if (!matches[i])
 908       return false;
 909
 910   return true;
 911 }
 912
 913 /* Recursively build an SLP tree starting from NODE.
 914    Fail (and return a value not equal to zero) if def-stmts are not
 915    isomorphic, require data permutation or are of unsupported types of
 916    operation.  Otherwise, return 0.
 917    The value returned is the depth in the SLP tree where a mismatch
 918    was found.  */
 919
 920 static bool
 921 vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 922                      slp_tree *node, unsigned int group_size,
 923                      unsigned int *max_nunits,
 924                      vec<slp_tree> *loads,
 925                      unsigned int vectorization_factor,
 926                      bool *matches, unsigned *npermutes, unsigned *tree_size,
 927                      unsigned max_tree_size)
 928 {
 929   unsigned nops, i, this_tree_size = 0;
 930   gimple stmt;
 931
 932   matches[0] = false;
 933
 934   stmt = SLP_TREE_SCALAR_STMTS (*node)[0];
 935   if (is_gimple_call (stmt))
 936     nops = gimple_call_num_args (stmt);
 937   else if (is_gimple_assign (stmt))
 938     {
 939       nops = gimple_num_ops (stmt) - 1;
 940       if (gimple_assign_rhs_code (stmt) == COND_EXPR)
 941         nops++;
 942     }
 943   else
 944     return false;
 945
 946   if (!vect_build_slp_tree_1 (loop_vinfo, bb_vinfo,
 947                               SLP_TREE_SCALAR_STMTS (*node), group_size, nops,
 948                               max_nunits, vectorization_factor, matches))
 949     return false;
 950
 951   /* If the SLP node is a load, terminate the recursion.  */
 952   if (STMT_VINFO_GROUPED_ACCESS (vinfo_for_stmt (stmt))
 953       && DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt))))
 954     {
 955       loads->safe_push (*node);
 956       return true;
 957     }
 958
 959   /* Get at the operands, verifying they are compatible.  */
 960   vec<slp_oprnd_info> oprnds_info = vect_create_oprnd_info (nops, group_size);
 961   slp_oprnd_info oprnd_info;
 962   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (*node), i, stmt)
 963     {
 964       switch (vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo,
 965                                            stmt, (i == 0), &oprnds_info))
 966         {
 967         case 0:
 968           break;
 969         case -1:
 970           matches[0] = false;
 971           vect_free_oprnd_info (oprnds_info);
 972           return false;
 973         case 1:
 974           matches[i] = false;
 975           break;
 976         }
 977     }
 978   for (i = 0; i < group_size; ++i)
 979     if (!matches[i])
 980       {
 981         vect_free_oprnd_info (oprnds_info);
 982         return false;
 983       }
 984
 985   stmt = SLP_TREE_SCALAR_STMTS (*node)[0];
 986
 987   /* Create SLP_TREE nodes for the definition node/s.  */
 988   FOR_EACH_VEC_ELT (oprnds_info, i, oprnd_info)
 989     {
 990       slp_tree child;
 991       unsigned old_nloads = loads->length ();
 992       unsigned old_max_nunits = *max_nunits;
 993
 994       if (oprnd_info->first_dt != vect_internal_def)
 995         continue;
 996
 997       if (++this_tree_size > max_tree_size)
 998         {
 999           vect_free_oprnd_info (oprnds_info);
1000           return false;
1001         }
1002
1003       child = vect_create_new_slp_node (oprnd_info->def_stmts);
1004       if (!child)
1005         {
1006           vect_free_oprnd_info (oprnds_info);
1007           return false;
1008         }
1009
1010       if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &child,
1011                                group_size, max_nunits, loads,
1012                                vectorization_factor, matches,
1013                                npermutes, &this_tree_size, max_tree_size))
1014         {
1015           oprnd_info->def_stmts = vNULL;
1016           SLP_TREE_CHILDREN (*node).quick_push (child);
1017           continue;
1018         }
1019
1020       /* If the SLP build for operand zero failed and operand zero
1021          and one can be commutated try that for the scalar stmts
1022          that failed the match.  */
1023       if (i == 0
1024           /* A first scalar stmt mismatch signals a fatal mismatch.  */
1025           && matches[0]
1026           /* ???  For COND_EXPRs we can swap the comparison operands
1027              as well as the arms under some constraints.  */
1028           && nops == 2
1029           && oprnds_info[1]->first_dt == vect_internal_def
1030           && is_gimple_assign (stmt)
1031           && commutative_tree_code (gimple_assign_rhs_code (stmt))
1032           /* Do so only if the number of not successful permutes was nor more
1033              than a cut-ff as re-trying the recursive match on
1034              possibly each level of the tree would expose exponential
1035              behavior.  */
1036           && *npermutes < 4)
1037         {
1038           unsigned int j;
1039           slp_tree grandchild;
1040
1041           /* Roll back.  */
1042           *max_nunits = old_max_nunits;
1043           loads->truncate (old_nloads);
1044           FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (child), j, grandchild)
1045             vect_free_slp_tree (grandchild);
1046           SLP_TREE_CHILDREN (child).truncate (0);
1047
1048           /* Swap mismatched definition stmts.  */
1049           dump_printf_loc (MSG_NOTE, vect_location,
1050                            "Re-trying with swapped operands of stmts ");
1051           for (j = 0; j < group_size; ++j)
1052             if (!matches[j])
1053               {
1054                 gimple tem = oprnds_info[0]->def_stmts[j];
1055                 oprnds_info[0]->def_stmts[j] = oprnds_info[1]->def_stmts[j];
1056                 oprnds_info[1]->def_stmts[j] = tem;
1057                 dump_printf (MSG_NOTE, "%d ", j);
1058               }
1059           dump_printf (MSG_NOTE, "\n");
1060           /* And try again ... */
1061           if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &child,
1062                                    group_size, max_nunits, loads,
1063                                    vectorization_factor,
1064                                    matches, npermutes, &this_tree_size,
1065                                    max_tree_size))
1066             {
1067               oprnd_info->def_stmts = vNULL;
1068               SLP_TREE_CHILDREN (*node).quick_push (child);
1069               continue;
1070             }
1071
1072           ++*npermutes;
1073         }
1074
1075       oprnd_info->def_stmts = vNULL;
1076       vect_free_slp_tree (child);
1077       vect_free_oprnd_info (oprnds_info);
1078       return false;
1079     }
1080
1081   if (tree_size)
1082     *tree_size += this_tree_size;
1083
1084   vect_free_oprnd_info (oprnds_info);
1085   return true;
1086 }
1087
1088 /* Dump a slp tree NODE using flags specified in DUMP_KIND.  */
1089
1090 static void
1091 vect_print_slp_tree (int dump_kind, slp_tree node)
1092 {
1093   int i;
1094   gimple stmt;
1095   slp_tree child;
1096
1097   if (!node)
1098     return;
1099
1100   dump_printf (dump_kind, "node ");
1101   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
1102     {
1103       dump_printf (dump_kind, "\n\tstmt %d ", i);
1104       dump_gimple_stmt (dump_kind, TDF_SLIM, stmt, 0);
1105     }
1106   dump_printf (dump_kind, "\n");
1107
1108   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1109     vect_print_slp_tree (dump_kind, child);
1110 }
1111
1112
1113 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
1114    If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
1115    J).  Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
1116    stmts in NODE are to be marked.  */
1117
1118 static void
1119 vect_mark_slp_stmts (slp_tree node, enum slp_vect_type mark, int j)
1120 {
1121   int i;
1122   gimple stmt;
1123   slp_tree child;
1124
1125   if (!node)
1126     return;
1127
1128   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
1129     if (j < 0 || i == j)
1130       STMT_SLP_TYPE (vinfo_for_stmt (stmt)) = mark;
1131
1132   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1133     vect_mark_slp_stmts (child, mark, j);
1134 }
1135
1136
1137 /* Mark the statements of the tree rooted at NODE as relevant (vect_used).  */
1138
1139 static void
1140 vect_mark_slp_stmts_relevant (slp_tree node)
1141 {
1142   int i;
1143   gimple stmt;
1144   stmt_vec_info stmt_info;
1145   slp_tree child;
1146
1147   if (!node)
1148     return;
1149
1150   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
1151     {
1152       stmt_info = vinfo_for_stmt (stmt);
1153       gcc_assert (!STMT_VINFO_RELEVANT (stmt_info)
1154                   || STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope);
1155       STMT_VINFO_RELEVANT (stmt_info) = vect_used_in_scope;
1156     }
1157
1158   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1159     vect_mark_slp_stmts_relevant (child);
1160 }
1161
1162
1163 /* Rearrange the statements of NODE according to PERMUTATION.  */
1164
1165 static void
1166 vect_slp_rearrange_stmts (slp_tree node, unsigned int group_size,
1167                           vec<unsigned> permutation)
1168 {
1169   gimple stmt;
1170   vec<gimple> tmp_stmts;
1171   unsigned int i;
1172   slp_tree child;
1173
1174   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1175     vect_slp_rearrange_stmts (child, group_size, permutation);
1176
1177   gcc_assert (group_size == SLP_TREE_SCALAR_STMTS (node).length ());
1178   tmp_stmts.create (group_size);
1179   tmp_stmts.quick_grow_cleared (group_size);
1180
1181   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
1182     tmp_stmts[permutation[i]] = stmt;
1183
1184   SLP_TREE_SCALAR_STMTS (node).release ();
1185   SLP_TREE_SCALAR_STMTS (node) = tmp_stmts;
1186 }
1187
1188
1189 /* Check if the required load permutations in the SLP instance
1190    SLP_INSTN are supported.  */
1191
1192 static bool
1193 vect_supported_load_permutation_p (slp_instance slp_instn)
1194 {
1195   unsigned int group_size = SLP_INSTANCE_GROUP_SIZE (slp_instn);
1196   unsigned int i, j, k, next;
1197   sbitmap load_index;
1198   slp_tree node;
1199   gimple stmt, load, next_load, first_load;
1200   struct data_reference *dr;
1201
1202   if (dump_enabled_p ())
1203     {
1204       dump_printf_loc (MSG_NOTE, vect_location, "Load permutation ");
1205       FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1206         if (node->load_permutation.exists ())
1207           FOR_EACH_VEC_ELT (node->load_permutation, j, next)
1208             dump_printf (MSG_NOTE, "%d ", next);
1209         else
1210           for (k = 0; k < group_size; ++k)
1211             dump_printf (MSG_NOTE, "%d ", k);
1212       dump_printf (MSG_NOTE, "\n");
1213     }
1214
1215   /* In case of reduction every load permutation is allowed, since the order
1216      of the reduction statements is not important (as opposed to the case of
1217      grouped stores).  The only condition we need to check is that all the
1218      load nodes are of the same size and have the same permutation (and then
1219      rearrange all the nodes of the SLP instance according to this
1220      permutation).  */
1221
1222   /* Check that all the load nodes are of the same size.  */
1223   /* ???  Can't we assert this? */
1224   FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1225     if (SLP_TREE_SCALAR_STMTS (node).length () != (unsigned) group_size)
1226       return false;
1227
1228   node = SLP_INSTANCE_TREE (slp_instn);
1229   stmt = SLP_TREE_SCALAR_STMTS (node)[0];
1230
1231   /* Reduction (there are no data-refs in the root).
1232      In reduction chain the order of the loads is important.  */
1233   if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt))
1234       && !GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
1235     {
1236       slp_tree load;
1237       unsigned int lidx;
1238
1239       /* Compare all the permutation sequences to the first one.  We know
1240          that at least one load is permuted.  */
1241       node = SLP_INSTANCE_LOADS (slp_instn)[0];
1242       if (!node->load_permutation.exists ())
1243         return false;
1244       for (i = 1; SLP_INSTANCE_LOADS (slp_instn).iterate (i, &load); ++i)
1245         {
1246           if (!load->load_permutation.exists ())
1247             return false;
1248           FOR_EACH_VEC_ELT (load->load_permutation, j, lidx)
1249             if (lidx != node->load_permutation[j])
1250               return false;
1251         }
1252
1253       /* Check that the loads in the first sequence are different and there
1254          are no gaps between them.  */
1255       load_index = sbitmap_alloc (group_size);
1256       bitmap_clear (load_index);
1257       FOR_EACH_VEC_ELT (node->load_permutation, i, lidx)
1258         {
1259           if (bitmap_bit_p (load_index, lidx))
1260             {
1261               sbitmap_free (load_index);
1262               return false;
1263             }
1264           bitmap_set_bit (load_index, lidx);
1265         }
1266       for (i = 0; i < group_size; i++)
1267         if (!bitmap_bit_p (load_index, i))
1268           {
1269             sbitmap_free (load_index);
1270             return false;
1271           }
1272       sbitmap_free (load_index);
1273
1274       /* This permutation is valid for reduction.  Since the order of the
1275          statements in the nodes is not important unless they are memory
1276          accesses, we can rearrange the statements in all the nodes
1277          according to the order of the loads.  */
1278       vect_slp_rearrange_stmts (SLP_INSTANCE_TREE (slp_instn), group_size,
1279                                 node->load_permutation);
1280
1281       /* We are done, no actual permutations need to be generated.  */
1282       FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1283         SLP_TREE_LOAD_PERMUTATION (node).release ();
1284       return true;
1285     }
1286
1287   /* In basic block vectorization we allow any subchain of an interleaving
1288      chain.
1289      FORNOW: not supported in loop SLP because of realignment compications.  */
1290   if (STMT_VINFO_BB_VINFO (vinfo_for_stmt (stmt)))
1291     {
1292       /* Check that for every node in the instance the loads
1293          form a subchain.  */
1294       FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1295         {
1296           next_load = NULL;
1297           FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), j, load)
1298             {
1299               if (j != 0 && next_load != load)
1300                 return false;
1301               next_load = GROUP_NEXT_ELEMENT (vinfo_for_stmt (load));
1302             }
1303         }
1304
1305       /* Check that the alignment of the first load in every subchain, i.e.,
1306          the first statement in every load node, is supported.
1307          ???  This belongs in alignment checking.  */
1308       FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1309         {
1310           first_load = SLP_TREE_SCALAR_STMTS (node)[0];
1311           if (first_load != GROUP_FIRST_ELEMENT (vinfo_for_stmt (first_load)))
1312             {
1313               dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_load));
1314               if (vect_supportable_dr_alignment (dr, false)
1315                   == dr_unaligned_unsupported)
1316                 {
1317                   if (dump_enabled_p ())
1318                     {
1319                       dump_printf_loc (MSG_MISSED_OPTIMIZATION,
1320                                        vect_location,
1321                                        "unsupported unaligned load ");
1322                       dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM,
1323                                         first_load, 0);
1324                       dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
1325                     }
1326                   return false;
1327                 }
1328             }
1329         }
1330
1331       /* We are done, no actual permutations need to be generated.  */
1332       FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1333         SLP_TREE_LOAD_PERMUTATION (node).release ();
1334       return true;
1335     }
1336
1337   /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
1338      GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
1339      well (unless it's reduction).  */
1340   if (SLP_INSTANCE_LOADS (slp_instn).length () != group_size)
1341     return false;
1342   FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1343     if (!node->load_permutation.exists ())
1344       return false;
1345
1346   load_index = sbitmap_alloc (group_size);
1347   bitmap_clear (load_index);
1348   FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1349     {
1350       unsigned int lidx = node->load_permutation[0];
1351       if (bitmap_bit_p (load_index, lidx))
1352         {
1353           sbitmap_free (load_index);
1354           return false;
1355         }
1356       bitmap_set_bit (load_index, lidx);
1357       FOR_EACH_VEC_ELT (node->load_permutation, j, k)
1358         if (k != lidx)
1359           {
1360             sbitmap_free (load_index);
1361             return false;
1362           }
1363     }
1364   for (i = 0; i < group_size; i++)
1365     if (!bitmap_bit_p (load_index, i))
1366       {
1367         sbitmap_free (load_index);
1368         return false;
1369       }
1370   sbitmap_free (load_index);
1371
1372   FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (slp_instn), i, node)
1373     if (node->load_permutation.exists ()
1374         && !vect_transform_slp_perm_load
1375               (node, vNULL, NULL,
1376                SLP_INSTANCE_UNROLLING_FACTOR (slp_instn), slp_instn, true))
1377       return false;
1378   return true;
1379 }
1380
1381
1382 /* Find the first load in the loop that belongs to INSTANCE.
1383    When loads are in several SLP nodes, there can be a case in which the first
1384    load does not appear in the first SLP node to be transformed, causing
1385    incorrect order of statements.  Since we generate all the loads together,
1386    they must be inserted before the first load of the SLP instance and not
1387    before the first load of the first node of the instance.  */
1388
1389 static gimple
1390 vect_find_first_load_in_slp_instance (slp_instance instance)
1391 {
1392   int i, j;
1393   slp_tree load_node;
1394   gimple first_load = NULL, load;
1395
1396   FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), i, load_node)
1397     FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node), j, load)
1398       first_load = get_earlier_stmt (load, first_load);
1399
1400   return first_load;
1401 }
1402
1403
1404 /* Find the last store in SLP INSTANCE.  */
1405
1406 static gimple
1407 vect_find_last_store_in_slp_instance (slp_instance instance)
1408 {
1409   int i;
1410   slp_tree node;
1411   gimple last_store = NULL, store;
1412
1413   node = SLP_INSTANCE_TREE (instance);
1414   for (i = 0; SLP_TREE_SCALAR_STMTS (node).iterate (i, &store); i++)
1415     last_store = get_later_stmt (store, last_store);
1416
1417   return last_store;
1418 }
1419
1420 /* Compute the cost for the SLP node NODE in the SLP instance INSTANCE.  */
1421
1422 static void
1423 vect_analyze_slp_cost_1 (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
1424                          slp_instance instance, slp_tree node,
1425                          stmt_vector_for_cost *prologue_cost_vec,
1426                          unsigned ncopies_for_cost)
1427 {
1428   stmt_vector_for_cost *body_cost_vec = &SLP_INSTANCE_BODY_COST_VEC (instance);
1429
1430   unsigned i;
1431   slp_tree child;
1432   gimple stmt, s;
1433   stmt_vec_info stmt_info;
1434   tree lhs;
1435   unsigned group_size = SLP_INSTANCE_GROUP_SIZE (instance);
1436
1437   /* Recurse down the SLP tree.  */
1438   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
1439     vect_analyze_slp_cost_1 (loop_vinfo, bb_vinfo,
1440                              instance, child, prologue_cost_vec,
1441                              ncopies_for_cost);
1442
1443   /* Look at the first scalar stmt to determine the cost.  */
1444   stmt = SLP_TREE_SCALAR_STMTS (node)[0];
1445   stmt_info = vinfo_for_stmt (stmt);
1446   if (STMT_VINFO_GROUPED_ACCESS (stmt_info))
1447     {
1448       if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmt_info)))
1449         vect_model_store_cost (stmt_info, ncopies_for_cost, false,
1450                                vect_uninitialized_def,
1451                                node, prologue_cost_vec, body_cost_vec);
1452       else
1453         {
1454           int i;
1455           gcc_checking_assert (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)));
1456           vect_model_load_cost (stmt_info, ncopies_for_cost, false,
1457                                 node, prologue_cost_vec, body_cost_vec);
1458           /* If the load is permuted record the cost for the permutation.
1459              ???  Loads from multiple chains are let through here only
1460              for a single special case involving complex numbers where
1461              in the end no permutation is necessary.  */
1462           FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, s)
1463             if ((STMT_VINFO_GROUP_FIRST_ELEMENT (vinfo_for_stmt (s))
1464                  == STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info))
1465                 && vect_get_place_in_interleaving_chain
1466                      (s, STMT_VINFO_GROUP_FIRST_ELEMENT (stmt_info)) != i)
1467               {
1468                 record_stmt_cost (body_cost_vec, group_size, vec_perm,
1469                                   stmt_info, 0, vect_body);
1470                 break;
1471               }
1472         }
1473     }
1474   else
1475     record_stmt_cost (body_cost_vec, ncopies_for_cost, vector_stmt,
1476                       stmt_info, 0, vect_body);
1477
1478   /* Scan operands and account for prologue cost of constants/externals.
1479      ???  This over-estimates cost for multiple uses and should be
1480      re-engineered.  */
1481   lhs = gimple_get_lhs (stmt);
1482   for (i = 0; i < gimple_num_ops (stmt); ++i)
1483     {
1484       tree def, op = gimple_op (stmt, i);
1485       gimple def_stmt;
1486       enum vect_def_type dt;
1487       if (!op || op == lhs)
1488         continue;
1489       if (vect_is_simple_use (op, NULL, loop_vinfo, bb_vinfo,
1490                               &def_stmt, &def, &dt)
1491           && (dt == vect_constant_def || dt == vect_external_def))
1492         record_stmt_cost (prologue_cost_vec, 1, vector_stmt,
1493                           stmt_info, 0, vect_prologue);
1494     }
1495 }
1496
1497 /* Compute the cost for the SLP instance INSTANCE.  */
1498
1499 static void
1500 vect_analyze_slp_cost (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
1501                        slp_instance instance, unsigned nunits)
1502 {
1503   stmt_vector_for_cost body_cost_vec, prologue_cost_vec;
1504   unsigned ncopies_for_cost;
1505   stmt_info_for_cost *si;
1506   unsigned i;
1507
1508   /* Calculate the number of vector stmts to create based on the unrolling
1509      factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
1510      GROUP_SIZE / NUNITS otherwise.  */
1511   unsigned group_size = SLP_INSTANCE_GROUP_SIZE (instance);
1512   ncopies_for_cost = least_common_multiple (nunits, group_size) / nunits;
1513
1514   prologue_cost_vec.create (10);
1515   body_cost_vec.create (10);
1516   SLP_INSTANCE_BODY_COST_VEC (instance) = body_cost_vec;
1517   vect_analyze_slp_cost_1 (loop_vinfo, bb_vinfo,
1518                            instance, SLP_INSTANCE_TREE (instance),
1519                            &prologue_cost_vec, ncopies_for_cost);
1520
1521   /* Record the prologue costs, which were delayed until we were
1522      sure that SLP was successful.  Unlike the body costs, we know
1523      the final values now regardless of the loop vectorization factor.  */
1524   void *data = (loop_vinfo ? LOOP_VINFO_TARGET_COST_DATA (loop_vinfo)
1525                 : BB_VINFO_TARGET_COST_DATA (bb_vinfo));
1526   FOR_EACH_VEC_ELT (prologue_cost_vec, i, si)
1527     {
1528       struct _stmt_vec_info *stmt_info
1529         = si->stmt ? vinfo_for_stmt (si->stmt) : NULL;
1530       (void) add_stmt_cost (data, si->count, si->kind, stmt_info,
1531                             si->misalign, vect_prologue);
1532     }
1533
1534   prologue_cost_vec.release ();
1535 }
1536
1537 /* Analyze an SLP instance starting from a group of grouped stores.  Call
1538    vect_build_slp_tree to build a tree of packed stmts if possible.
1539    Return FALSE if it's impossible to SLP any stmt in the loop.  */
1540
1541 static bool
1542 vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
1543                            gimple stmt, unsigned max_tree_size)
1544 {
1545   slp_instance new_instance;
1546   slp_tree node;
1547   unsigned int group_size = GROUP_SIZE (vinfo_for_stmt (stmt));
1548   unsigned int unrolling_factor = 1, nunits;
1549   tree vectype, scalar_type = NULL_TREE;
1550   gimple next;
1551   unsigned int vectorization_factor = 0;
1552   int i;
1553   unsigned int max_nunits = 0;
1554   vec<slp_tree> loads;
1555   struct data_reference *dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
1556   vec<gimple> scalar_stmts;
1557
1558   if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
1559     {
1560       if (dr)
1561         {
1562           scalar_type = TREE_TYPE (DR_REF (dr));
1563           vectype = get_vectype_for_scalar_type (scalar_type);
1564         }
1565       else
1566         {
1567           gcc_assert (loop_vinfo);
1568           vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1569         }
1570
1571       group_size = GROUP_SIZE (vinfo_for_stmt (stmt));
1572     }
1573   else
1574     {
1575       gcc_assert (loop_vinfo);
1576       vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1577       group_size = LOOP_VINFO_REDUCTIONS (loop_vinfo).length ();
1578     }
1579
1580   if (!vectype)
1581     {
1582       if (dump_enabled_p ())
1583         {
1584           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1585                            "Build SLP failed: unsupported data-type ");
1586           dump_generic_expr (MSG_MISSED_OPTIMIZATION, TDF_SLIM, scalar_type);
1587           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
1588         }
1589
1590       return false;
1591     }
1592
1593   nunits = TYPE_VECTOR_SUBPARTS (vectype);
1594   if (loop_vinfo)
1595     vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1596   else
1597     vectorization_factor = nunits;
1598
1599   /* Calculate the unrolling factor.  */
1600   unrolling_factor = least_common_multiple (nunits, group_size) / group_size;
1601   if (unrolling_factor != 1 && !loop_vinfo)
1602     {
1603       if (dump_enabled_p ())
1604         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1605                          "Build SLP failed: unrolling required in basic"
1606                          " block SLP\n");
1607
1608       return false;
1609     }
1610
1611   /* Create a node (a root of the SLP tree) for the packed grouped stores.  */
1612   scalar_stmts.create (group_size);
1613   next = stmt;
1614   if (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
1615     {
1616       /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS.  */
1617       while (next)
1618         {
1619           if (STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (next))
1620               && STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)))
1621             scalar_stmts.safe_push (
1622                   STMT_VINFO_RELATED_STMT (vinfo_for_stmt (next)));
1623           else
1624             scalar_stmts.safe_push (next);
1625           next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next));
1626         }
1627     }
1628   else
1629     {
1630       /* Collect reduction statements.  */
1631       vec<gimple> reductions = LOOP_VINFO_REDUCTIONS (loop_vinfo);
1632       for (i = 0; reductions.iterate (i, &next); i++)
1633         scalar_stmts.safe_push (next);
1634     }
1635
1636   node = vect_create_new_slp_node (scalar_stmts);
1637
1638   loads.create (group_size);
1639
1640   /* Build the tree for the SLP instance.  */
1641   bool *matches = XALLOCAVEC (bool, group_size);
1642   unsigned npermutes = 0;
1643   if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
1644                            &max_nunits, &loads,
1645                            vectorization_factor, matches, &npermutes, NULL,
1646                            max_tree_size))
1647     {
1648       /* Calculate the unrolling factor based on the smallest type.  */
1649       if (max_nunits > nunits)
1650         unrolling_factor = least_common_multiple (max_nunits, group_size)
1651                            / group_size;
1652
1653       if (unrolling_factor != 1 && !loop_vinfo)
1654         {
1655           if (dump_enabled_p ())
1656             dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1657                              "Build SLP failed: unrolling required in basic"
1658                              " block SLP\n");
1659           vect_free_slp_tree (node);
1660           loads.release ();
1661           return false;
1662         }
1663
1664       /* Create a new SLP instance.  */
1665       new_instance = XNEW (struct _slp_instance);
1666       SLP_INSTANCE_TREE (new_instance) = node;
1667       SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
1668       SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
1669       SLP_INSTANCE_BODY_COST_VEC (new_instance) = vNULL;
1670       SLP_INSTANCE_LOADS (new_instance) = loads;
1671       SLP_INSTANCE_FIRST_LOAD_STMT (new_instance) = NULL;
1672
1673       /* Compute the load permutation.  */
1674       slp_tree load_node;
1675       bool loads_permuted = false;
1676       FOR_EACH_VEC_ELT (loads, i, load_node)
1677         {
1678           vec<unsigned> load_permutation;
1679           int j;
1680           gimple load, first_stmt;
1681           bool this_load_permuted = false;
1682           load_permutation.create (group_size);
1683           first_stmt = GROUP_FIRST_ELEMENT
1684               (vinfo_for_stmt (SLP_TREE_SCALAR_STMTS (load_node)[0]));
1685           FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (load_node), j, load)
1686             {
1687               int load_place
1688                 = vect_get_place_in_interleaving_chain (load, first_stmt);
1689               gcc_assert (load_place != -1);
1690               if (load_place != j)
1691                 this_load_permuted = true;
1692               load_permutation.safe_push (load_place);
1693             }
1694           if (!this_load_permuted)
1695             {
1696               load_permutation.release ();
1697               continue;
1698             }
1699           SLP_TREE_LOAD_PERMUTATION (load_node) = load_permutation;
1700           loads_permuted = true;
1701         }
1702
1703       if (loads_permuted)
1704         {
1705           if (!vect_supported_load_permutation_p (new_instance))
1706             {
1707               if (dump_enabled_p ())
1708                 {
1709                   dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1710                                    "Build SLP failed: unsupported load "
1711                                    "permutation ");
1712                   dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
1713                   dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
1714                 }
1715               vect_free_slp_instance (new_instance);
1716               return false;
1717             }
1718
1719           SLP_INSTANCE_FIRST_LOAD_STMT (new_instance)
1720             = vect_find_first_load_in_slp_instance (new_instance);
1721         }
1722
1723       /* Compute the costs of this SLP instance.  */
1724       vect_analyze_slp_cost (loop_vinfo, bb_vinfo,
1725                              new_instance, TYPE_VECTOR_SUBPARTS (vectype));
1726
1727       if (loop_vinfo)
1728         LOOP_VINFO_SLP_INSTANCES (loop_vinfo).safe_push (new_instance);
1729       else
1730         BB_VINFO_SLP_INSTANCES (bb_vinfo).safe_push (new_instance);
1731
1732       if (dump_enabled_p ())
1733         vect_print_slp_tree (MSG_NOTE, node);
1734
1735       return true;
1736     }
1737
1738   /* Failed to SLP.  */
1739   /* Free the allocated memory.  */
1740   vect_free_slp_tree (node);
1741   loads.release ();
1742
1743   return false;
1744 }
1745
1746
1747 /* Check if there are stmts in the loop can be vectorized using SLP.  Build SLP
1748    trees of packed scalar stmts if SLP is possible.  */
1749
1750 bool
1751 vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
1752                   unsigned max_tree_size)
1753 {
1754   unsigned int i;
1755   vec<gimple> grouped_stores;
1756   vec<gimple> reductions = vNULL;
1757   vec<gimple> reduc_chains = vNULL;
1758   gimple first_element;
1759   bool ok = false;
1760
1761   if (dump_enabled_p ())
1762     dump_printf_loc (MSG_NOTE, vect_location, "=== vect_analyze_slp ===\n");
1763
1764   if (loop_vinfo)
1765     {
1766       grouped_stores = LOOP_VINFO_GROUPED_STORES (loop_vinfo);
1767       reduc_chains = LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo);
1768       reductions = LOOP_VINFO_REDUCTIONS (loop_vinfo);
1769     }
1770   else
1771     grouped_stores = BB_VINFO_GROUPED_STORES (bb_vinfo);
1772
1773   /* Find SLP sequences starting from groups of grouped stores.  */
1774   FOR_EACH_VEC_ELT (grouped_stores, i, first_element)
1775     if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element,
1776                                    max_tree_size))
1777       ok = true;
1778
1779   if (bb_vinfo && !ok)
1780     {
1781       if (dump_enabled_p ())
1782         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1783                          "Failed to SLP the basic block.\n");
1784
1785       return false;
1786     }
1787
1788   if (loop_vinfo
1789       && LOOP_VINFO_REDUCTION_CHAINS (loop_vinfo).length () > 0)
1790     {
1791       /* Find SLP sequences starting from reduction chains.  */
1792       FOR_EACH_VEC_ELT (reduc_chains, i, first_element)
1793         if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, first_element,
1794                                        max_tree_size))
1795           ok = true;
1796         else
1797           return false;
1798
1799       /* Don't try to vectorize SLP reductions if reduction chain was
1800          detected.  */
1801       return ok;
1802     }
1803
1804   /* Find SLP sequences starting from groups of reductions.  */
1805   if (loop_vinfo && LOOP_VINFO_REDUCTIONS (loop_vinfo).length () > 1
1806       && vect_analyze_slp_instance (loop_vinfo, bb_vinfo, reductions[0],
1807                                     max_tree_size))
1808     ok = true;
1809
1810   return true;
1811 }
1812
1813
1814 /* For each possible SLP instance decide whether to SLP it and calculate overall
1815    unrolling factor needed to SLP the loop.  Return TRUE if decided to SLP at
1816    least one instance.  */
1817
1818 bool
1819 vect_make_slp_decision (loop_vec_info loop_vinfo)
1820 {
1821   unsigned int i, unrolling_factor = 1;
1822   vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1823   slp_instance instance;
1824   int decided_to_slp = 0;
1825
1826   if (dump_enabled_p ())
1827     dump_printf_loc (MSG_NOTE, vect_location, "=== vect_make_slp_decision ==="
1828                      "\n");
1829
1830   FOR_EACH_VEC_ELT (slp_instances, i, instance)
1831     {
1832       /* FORNOW: SLP if you can.  */
1833       if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
1834         unrolling_factor = SLP_INSTANCE_UNROLLING_FACTOR (instance);
1835
1836       /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts.  Later we
1837          call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1838          loop-based vectorization.  Such stmts will be marked as HYBRID.  */
1839       vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
1840       decided_to_slp++;
1841     }
1842
1843   LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
1844
1845   if (decided_to_slp && dump_enabled_p ())
1846     dump_printf_loc (MSG_NOTE, vect_location,
1847                      "Decided to SLP %d instances. Unrolling factor %d\n",
1848                      decided_to_slp, unrolling_factor);
1849
1850   return (decided_to_slp > 0);
1851 }
1852
1853
1854 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1855    can't be SLPed) in the tree rooted at NODE.  Mark such stmts as HYBRID.  */
1856
1857 static void
1858 vect_detect_hybrid_slp_stmts (slp_tree node, unsigned i, slp_vect_type stype)
1859 {
1860   gimple stmt = SLP_TREE_SCALAR_STMTS (node)[i];
1861   imm_use_iterator imm_iter;
1862   gimple use_stmt;
1863   stmt_vec_info use_vinfo, stmt_vinfo = vinfo_for_stmt (stmt);
1864   slp_tree child;
1865   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
1866   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1867   int j;
1868
1869   /* Propagate hybrid down the SLP tree.  */
1870   if (stype == hybrid)
1871     ;
1872   else if (HYBRID_SLP_STMT (stmt_vinfo))
1873     stype = hybrid;
1874   else
1875     {
1876       /* Check if a pure SLP stmt has uses in non-SLP stmts.  */
1877       gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo));
1878       /* We always get the pattern stmt here, but for immediate
1879          uses we have to use the LHS of the original stmt.  */
1880       gcc_checking_assert (!STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
1881       if (STMT_VINFO_RELATED_STMT (stmt_vinfo))
1882         stmt = STMT_VINFO_RELATED_STMT (stmt_vinfo);
1883       if (TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
1884         FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
1885           {
1886             if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
1887               continue;
1888             use_vinfo = vinfo_for_stmt (use_stmt);
1889             if (STMT_VINFO_IN_PATTERN_P (use_vinfo)
1890                 && STMT_VINFO_RELATED_STMT (use_vinfo))
1891               use_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (use_vinfo));
1892             if (!STMT_SLP_TYPE (use_vinfo)
1893                 && (STMT_VINFO_RELEVANT (use_vinfo)
1894                     || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo)))
1895                 && !(gimple_code (use_stmt) == GIMPLE_PHI
1896                      && STMT_VINFO_DEF_TYPE (use_vinfo) == vect_reduction_def))
1897               stype = hybrid;
1898           }
1899     }
1900
1901   if (stype == hybrid)
1902     STMT_SLP_TYPE (stmt_vinfo) = hybrid;
1903
1904   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child)
1905     vect_detect_hybrid_slp_stmts (child, i, stype);
1906 }
1907
1908 /* Helpers for vect_detect_hybrid_slp walking pattern stmt uses.  */
1909
1910 static tree
1911 vect_detect_hybrid_slp_1 (tree *tp, int *, void *data)
1912 {
1913   walk_stmt_info *wi = (walk_stmt_info *)data;
1914   struct loop *loopp = (struct loop *)wi->info;
1915
1916   if (wi->is_lhs)
1917     return NULL_TREE;
1918
1919   if (TREE_CODE (*tp) == SSA_NAME
1920       && !SSA_NAME_IS_DEFAULT_DEF (*tp))
1921     {
1922       gimple def_stmt = SSA_NAME_DEF_STMT (*tp);
1923       if (flow_bb_inside_loop_p (loopp, gimple_bb (def_stmt))
1924           && PURE_SLP_STMT (vinfo_for_stmt (def_stmt)))
1925         STMT_SLP_TYPE (vinfo_for_stmt (def_stmt)) = hybrid;
1926     }
1927
1928   return NULL_TREE;
1929 }
1930
1931 static tree
1932 vect_detect_hybrid_slp_2 (gimple_stmt_iterator *gsi, bool *handled,
1933                           walk_stmt_info *)
1934 {
1935   /* If the stmt is in a SLP instance then this isn't a reason
1936      to mark use definitions in other SLP instances as hybrid.  */
1937   if (STMT_SLP_TYPE (vinfo_for_stmt (gsi_stmt (*gsi))) != loop_vect)
1938     *handled = true;
1939   return NULL_TREE;
1940 }
1941
1942 /* Find stmts that must be both vectorized and SLPed.  */
1943
1944 void
1945 vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
1946 {
1947   unsigned int i;
1948   vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1949   slp_instance instance;
1950
1951   if (dump_enabled_p ())
1952     dump_printf_loc (MSG_NOTE, vect_location, "=== vect_detect_hybrid_slp ==="
1953                      "\n");
1954
1955   /* First walk all pattern stmt in the loop and mark defs of uses as
1956      hybrid because immediate uses in them are not recorded.  */
1957   for (i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i)
1958     {
1959       basic_block bb = LOOP_VINFO_BBS (loop_vinfo)[i];
1960       for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1961            gsi_next (&gsi))
1962         {
1963           gimple stmt = gsi_stmt (gsi);
1964           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1965           if (STMT_VINFO_IN_PATTERN_P (stmt_info))
1966             {
1967               walk_stmt_info wi;
1968               memset (&wi, 0, sizeof (wi));
1969               wi.info = LOOP_VINFO_LOOP (loop_vinfo);
1970               gimple_stmt_iterator gsi2
1971                 = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
1972               walk_gimple_stmt (&gsi2, vect_detect_hybrid_slp_2,
1973                                 vect_detect_hybrid_slp_1, &wi);
1974               walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info),
1975                                vect_detect_hybrid_slp_2,
1976                                vect_detect_hybrid_slp_1, &wi);
1977             }
1978         }
1979     }
1980
1981   /* Then walk the SLP instance trees marking stmts with uses in
1982      non-SLP stmts as hybrid, also propagating hybrid down the
1983      SLP tree, collecting the above info on-the-fly.  */
1984   FOR_EACH_VEC_ELT (slp_instances, i, instance)
1985     {
1986       for (unsigned i = 0; i < SLP_INSTANCE_GROUP_SIZE (instance); ++i)
1987         vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance),
1988                                       i, pure_slp);
1989     }
1990 }
1991
1992
1993 /* Create and initialize a new bb_vec_info struct for BB, as well as
1994    stmt_vec_info structs for all the stmts in it.  */
1995
1996 static bb_vec_info
1997 new_bb_vec_info (basic_block bb)
1998 {
1999   bb_vec_info res = NULL;
2000   gimple_stmt_iterator gsi;
2001
2002   res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));
2003   BB_VINFO_BB (res) = bb;
2004
2005   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2006     {
2007       gimple stmt = gsi_stmt (gsi);
2008       gimple_set_uid (stmt, 0);
2009       set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, NULL, res));
2010     }
2011
2012   BB_VINFO_GROUPED_STORES (res).create (10);
2013   BB_VINFO_SLP_INSTANCES (res).create (2);
2014   BB_VINFO_TARGET_COST_DATA (res) = init_cost (NULL);
2015
2016   bb->aux = res;
2017   return res;
2018 }
2019
2020
2021 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
2022    stmts in the basic block.  */
2023
2024 static void
2025 destroy_bb_vec_info (bb_vec_info bb_vinfo)
2026 {
2027   vec<slp_instance> slp_instances;
2028   slp_instance instance;
2029   basic_block bb;
2030   gimple_stmt_iterator si;
2031   unsigned i;
2032
2033   if (!bb_vinfo)
2034     return;
2035
2036   bb = BB_VINFO_BB (bb_vinfo);
2037
2038   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2039     {
2040       gimple stmt = gsi_stmt (si);
2041       stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2042
2043       if (stmt_info)
2044         /* Free stmt_vec_info.  */
2045         free_stmt_vec_info (stmt);
2046     }
2047
2048   vect_destroy_datarefs (NULL, bb_vinfo);
2049   free_dependence_relations (BB_VINFO_DDRS (bb_vinfo));
2050   BB_VINFO_GROUPED_STORES (bb_vinfo).release ();
2051   slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2052   FOR_EACH_VEC_ELT (slp_instances, i, instance)
2053     vect_free_slp_instance (instance);
2054   BB_VINFO_SLP_INSTANCES (bb_vinfo).release ();
2055   destroy_cost_data (BB_VINFO_TARGET_COST_DATA (bb_vinfo));
2056   free (bb_vinfo);
2057   bb->aux = NULL;
2058 }
2059
2060
2061 /* Analyze statements contained in SLP tree node after recursively analyzing
2062    the subtree. Return TRUE if the operations are supported.  */
2063
2064 static bool
2065 vect_slp_analyze_node_operations (bb_vec_info bb_vinfo, slp_tree node)
2066 {
2067   bool dummy;
2068   int i;
2069   gimple stmt;
2070   slp_tree child;
2071
2072   if (!node)
2073     return true;
2074
2075   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
2076     if (!vect_slp_analyze_node_operations (bb_vinfo, child))
2077       return false;
2078
2079   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
2080     {
2081       stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2082       gcc_assert (stmt_info);
2083       gcc_assert (PURE_SLP_STMT (stmt_info));
2084
2085       if (!vect_analyze_stmt (stmt, &dummy, node))
2086         return false;
2087     }
2088
2089   return true;
2090 }
2091
2092
2093 /* Analyze statements in SLP instances of the basic block.  Return TRUE if the
2094    operations are supported. */
2095
2096 static bool
2097 vect_slp_analyze_operations (bb_vec_info bb_vinfo)
2098 {
2099   vec<slp_instance> slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2100   slp_instance instance;
2101   int i;
2102
2103   for (i = 0; slp_instances.iterate (i, &instance); )
2104     {
2105       if (!vect_slp_analyze_node_operations (bb_vinfo,
2106                                              SLP_INSTANCE_TREE (instance)))
2107         {
2108           vect_free_slp_instance (instance);
2109           slp_instances.ordered_remove (i);
2110         }
2111       else
2112         i++;
2113     }
2114
2115   if (!slp_instances.length ())
2116     return false;
2117
2118   return true;
2119 }
2120
2121
2122 /* Compute the scalar cost of the SLP node NODE and its children
2123    and return it.  Do not account defs that are marked in LIFE and
2124    update LIFE according to uses of NODE.  */
2125
2126 static unsigned
2127 vect_bb_slp_scalar_cost (basic_block bb,
2128                          slp_tree node, vec<bool, va_heap> *life)
2129 {
2130   unsigned scalar_cost = 0;
2131   unsigned i;
2132   gimple stmt;
2133   slp_tree child;
2134
2135   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
2136     {
2137       unsigned stmt_cost;
2138       ssa_op_iter op_iter;
2139       def_operand_p def_p;
2140       stmt_vec_info stmt_info;
2141
2142       if ((*life)[i])
2143         continue;
2144
2145       /* If there is a non-vectorized use of the defs then the scalar
2146          stmt is kept live in which case we do not account it or any
2147          required defs in the SLP children in the scalar cost.  This
2148          way we make the vectorization more costly when compared to
2149          the scalar cost.  */
2150       FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
2151         {
2152           imm_use_iterator use_iter;
2153           gimple use_stmt;
2154           FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, DEF_FROM_PTR (def_p))
2155             if (!is_gimple_debug (use_stmt)
2156                 && (gimple_code (use_stmt) == GIMPLE_PHI
2157                     || gimple_bb (use_stmt) != bb
2158                     || !STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (use_stmt))))
2159               {
2160                 (*life)[i] = true;
2161                 BREAK_FROM_IMM_USE_STMT (use_iter);
2162               }
2163         }
2164       if ((*life)[i])
2165         continue;
2166
2167       stmt_info = vinfo_for_stmt (stmt);
2168       if (STMT_VINFO_DATA_REF (stmt_info))
2169         {
2170           if (DR_IS_READ (STMT_VINFO_DATA_REF (stmt_info)))
2171             stmt_cost = vect_get_stmt_cost (scalar_load);
2172           else
2173             stmt_cost = vect_get_stmt_cost (scalar_store);
2174         }
2175       else
2176         stmt_cost = vect_get_stmt_cost (scalar_stmt);
2177
2178       scalar_cost += stmt_cost;
2179     }
2180
2181   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
2182     scalar_cost += vect_bb_slp_scalar_cost (bb, child, life);
2183
2184   return scalar_cost;
2185 }
2186
2187 /* Check if vectorization of the basic block is profitable.  */
2188
2189 static bool
2190 vect_bb_vectorization_profitable_p (bb_vec_info bb_vinfo)
2191 {
2192   vec<slp_instance> slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2193   slp_instance instance;
2194   int i, j;
2195   unsigned int vec_inside_cost = 0, vec_outside_cost = 0, scalar_cost = 0;
2196   unsigned int vec_prologue_cost = 0, vec_epilogue_cost = 0;
2197   void *target_cost_data = BB_VINFO_TARGET_COST_DATA (bb_vinfo);
2198   stmt_vec_info stmt_info = NULL;
2199   stmt_vector_for_cost body_cost_vec;
2200   stmt_info_for_cost *ci;
2201
2202   /* Calculate vector costs.  */
2203   FOR_EACH_VEC_ELT (slp_instances, i, instance)
2204     {
2205       body_cost_vec = SLP_INSTANCE_BODY_COST_VEC (instance);
2206
2207       FOR_EACH_VEC_ELT (body_cost_vec, j, ci)
2208         {
2209           stmt_info = ci->stmt ? vinfo_for_stmt (ci->stmt) : NULL;
2210           (void) add_stmt_cost (target_cost_data, ci->count, ci->kind,
2211                                 stmt_info, ci->misalign, vect_body);
2212         }
2213     }
2214
2215   /* Calculate scalar cost.  */
2216   FOR_EACH_VEC_ELT (slp_instances, i, instance)
2217     {
2218       auto_vec<bool, 20> life;
2219       life.safe_grow_cleared (SLP_INSTANCE_GROUP_SIZE (instance));
2220       scalar_cost += vect_bb_slp_scalar_cost (BB_VINFO_BB (bb_vinfo),
2221                                               SLP_INSTANCE_TREE (instance),
2222                                               &life);
2223     }
2224
2225   /* Complete the target-specific cost calculation.  */
2226   finish_cost (BB_VINFO_TARGET_COST_DATA (bb_vinfo), &vec_prologue_cost,
2227                &vec_inside_cost, &vec_epilogue_cost);
2228
2229   vec_outside_cost = vec_prologue_cost + vec_epilogue_cost;
2230
2231   if (dump_enabled_p ())
2232     {
2233       dump_printf_loc (MSG_NOTE, vect_location, "Cost model analysis: \n");
2234       dump_printf (MSG_NOTE, "  Vector inside of basic block cost: %d\n",
2235                    vec_inside_cost);
2236       dump_printf (MSG_NOTE, "  Vector prologue cost: %d\n", vec_prologue_cost);
2237       dump_printf (MSG_NOTE, "  Vector epilogue cost: %d\n", vec_epilogue_cost);
2238       dump_printf (MSG_NOTE, "  Scalar cost of basic block: %d\n", scalar_cost);
2239     }
2240
2241   /* Vectorization is profitable if its cost is less than the cost of scalar
2242      version.  */
2243   if (vec_outside_cost + vec_inside_cost >= scalar_cost)
2244     return false;
2245
2246   return true;
2247 }
2248
2249 /* Check if the basic block can be vectorized.  */
2250
2251 static bb_vec_info
2252 vect_slp_analyze_bb_1 (basic_block bb)
2253 {
2254   bb_vec_info bb_vinfo;
2255   vec<slp_instance> slp_instances;
2256   slp_instance instance;
2257   int i;
2258   int min_vf = 2;
2259   unsigned n_stmts = 0;
2260
2261   bb_vinfo = new_bb_vec_info (bb);
2262   if (!bb_vinfo)
2263     return NULL;
2264
2265   if (!vect_analyze_data_refs (NULL, bb_vinfo, &min_vf, &n_stmts))
2266     {
2267       if (dump_enabled_p ())
2268         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2269                          "not vectorized: unhandled data-ref in basic "
2270                          "block.\n");
2271
2272       destroy_bb_vec_info (bb_vinfo);
2273       return NULL;
2274     }
2275
2276   if (BB_VINFO_DATAREFS (bb_vinfo).length () < 2)
2277     {
2278       if (dump_enabled_p ())
2279         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2280                          "not vectorized: not enough data-refs in "
2281                          "basic block.\n");
2282
2283       destroy_bb_vec_info (bb_vinfo);
2284       return NULL;
2285     }
2286
2287   if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
2288     {
2289      if (dump_enabled_p ())
2290        dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2291                         "not vectorized: unhandled data access in "
2292                         "basic block.\n");
2293
2294       destroy_bb_vec_info (bb_vinfo);
2295       return NULL;
2296     }
2297
2298   vect_pattern_recog (NULL, bb_vinfo);
2299
2300   if (!vect_analyze_data_refs_alignment (NULL, bb_vinfo))
2301     {
2302       if (dump_enabled_p ())
2303         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2304                          "not vectorized: bad data alignment in basic "
2305                          "block.\n");
2306
2307       destroy_bb_vec_info (bb_vinfo);
2308       return NULL;
2309     }
2310
2311   /* Check the SLP opportunities in the basic block, analyze and build SLP
2312      trees.  */
2313   if (!vect_analyze_slp (NULL, bb_vinfo, n_stmts))
2314     {
2315       if (dump_enabled_p ())
2316         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2317                          "not vectorized: failed to find SLP opportunities "
2318                          "in basic block.\n");
2319
2320       destroy_bb_vec_info (bb_vinfo);
2321       return NULL;
2322     }
2323
2324   slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2325
2326   /* Mark all the statements that we want to vectorize as pure SLP and
2327      relevant.  */
2328   FOR_EACH_VEC_ELT (slp_instances, i, instance)
2329     {
2330       vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
2331       vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
2332     }
2333
2334   /* Mark all the statements that we do not want to vectorize.  */
2335   for (gimple_stmt_iterator gsi = gsi_start_bb (BB_VINFO_BB (bb_vinfo));
2336        !gsi_end_p (gsi); gsi_next (&gsi))
2337     {
2338       stmt_vec_info vinfo = vinfo_for_stmt (gsi_stmt (gsi));
2339       if (STMT_SLP_TYPE (vinfo) != pure_slp)
2340         STMT_VINFO_VECTORIZABLE (vinfo) = false;
2341     }
2342
2343   /* Analyze dependences.  At this point all stmts not participating in
2344      vectorization have to be marked.  Dependence analysis assumes
2345      that we either vectorize all SLP instances or none at all.  */
2346   if (!vect_slp_analyze_data_ref_dependences (bb_vinfo))
2347      {
2348        if (dump_enabled_p ())
2349          dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2350                           "not vectorized: unhandled data dependence "
2351                           "in basic block.\n");
2352
2353        destroy_bb_vec_info (bb_vinfo);
2354        return NULL;
2355      }
2356
2357   if (!vect_verify_datarefs_alignment (NULL, bb_vinfo))
2358     {
2359       if (dump_enabled_p ())
2360         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2361                          "not vectorized: unsupported alignment in basic "
2362                          "block.\n");
2363       destroy_bb_vec_info (bb_vinfo);
2364       return NULL;
2365     }
2366
2367   if (!vect_slp_analyze_operations (bb_vinfo))
2368     {
2369       if (dump_enabled_p ())
2370         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2371                          "not vectorized: bad operation in basic block.\n");
2372
2373       destroy_bb_vec_info (bb_vinfo);
2374       return NULL;
2375     }
2376
2377   /* Cost model: check if the vectorization is worthwhile.  */
2378   if (!unlimited_cost_model (NULL)
2379       && !vect_bb_vectorization_profitable_p (bb_vinfo))
2380     {
2381       if (dump_enabled_p ())
2382         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2383                          "not vectorized: vectorization is not "
2384                          "profitable.\n");
2385
2386       destroy_bb_vec_info (bb_vinfo);
2387       return NULL;
2388     }
2389
2390   if (dump_enabled_p ())
2391     dump_printf_loc (MSG_NOTE, vect_location,
2392                      "Basic block will be vectorized using SLP\n");
2393
2394   return bb_vinfo;
2395 }
2396
2397
2398 bb_vec_info
2399 vect_slp_analyze_bb (basic_block bb)
2400 {
2401   bb_vec_info bb_vinfo;
2402   int insns = 0;
2403   gimple_stmt_iterator gsi;
2404   unsigned int vector_sizes;
2405
2406   if (dump_enabled_p ())
2407     dump_printf_loc (MSG_NOTE, vect_location, "===vect_slp_analyze_bb===\n");
2408
2409   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2410     {
2411       gimple stmt = gsi_stmt (gsi);
2412       if (!is_gimple_debug (stmt)
2413           && !gimple_nop_p (stmt)
2414           && gimple_code (stmt) != GIMPLE_LABEL)
2415         insns++;
2416     }
2417
2418   if (insns > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB))
2419     {
2420       if (dump_enabled_p ())
2421         dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2422                          "not vectorized: too many instructions in "
2423                          "basic block.\n");
2424
2425       return NULL;
2426     }
2427
2428   /* Autodetect first vector size we try.  */
2429   current_vector_size = 0;
2430   vector_sizes = targetm.vectorize.autovectorize_vector_sizes ();
2431
2432   while (1)
2433     {
2434       bb_vinfo = vect_slp_analyze_bb_1 (bb);
2435       if (bb_vinfo)
2436         return bb_vinfo;
2437
2438       destroy_bb_vec_info (bb_vinfo);
2439
2440       vector_sizes &= ~current_vector_size;
2441       if (vector_sizes == 0
2442           || current_vector_size == 0)
2443         return NULL;
2444
2445       /* Try the next biggest vector size.  */
2446       current_vector_size = 1 << floor_log2 (vector_sizes);
2447       if (dump_enabled_p ())
2448         dump_printf_loc (MSG_NOTE, vect_location,
2449                          "***** Re-trying analysis with "
2450                          "vector size %d\n", current_vector_size);
2451     }
2452 }
2453
2454
2455 /* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
2456    the number of created vector stmts depends on the unrolling factor).
2457    However, the actual number of vector stmts for every SLP node depends on
2458    VF which is set later in vect_analyze_operations ().  Hence, SLP costs
2459    should be updated.  In this function we assume that the inside costs
2460    calculated in vect_model_xxx_cost are linear in ncopies.  */
2461
2462 void
2463 vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo)
2464 {
2465   unsigned int i, j, vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2466   vec<slp_instance> slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2467   slp_instance instance;
2468   stmt_vector_for_cost body_cost_vec;
2469   stmt_info_for_cost *si;
2470   void *data = LOOP_VINFO_TARGET_COST_DATA (loop_vinfo);
2471
2472   if (dump_enabled_p ())
2473     dump_printf_loc (MSG_NOTE, vect_location,
2474                      "=== vect_update_slp_costs_according_to_vf ===\n");
2475
2476   FOR_EACH_VEC_ELT (slp_instances, i, instance)
2477     {
2478       /* We assume that costs are linear in ncopies.  */
2479       int ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (instance);
2480
2481       /* Record the instance's instructions in the target cost model.
2482          This was delayed until here because the count of instructions
2483          isn't known beforehand.  */
2484       body_cost_vec = SLP_INSTANCE_BODY_COST_VEC (instance);
2485
2486       FOR_EACH_VEC_ELT (body_cost_vec, j, si)
2487         (void) add_stmt_cost (data, si->count * ncopies, si->kind,
2488                               vinfo_for_stmt (si->stmt), si->misalign,
2489                               vect_body);
2490     }
2491 }
2492
2493
2494 /* For constant and loop invariant defs of SLP_NODE this function returns
2495    (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
2496    OP_NUM determines if we gather defs for operand 0 or operand 1 of the RHS of
2497    scalar stmts.  NUMBER_OF_VECTORS is the number of vector defs to create.
2498    REDUC_INDEX is the index of the reduction operand in the statements, unless
2499    it is -1.  */
2500
2501 static void
2502 vect_get_constant_vectors (tree op, slp_tree slp_node,
2503                            vec<tree> *vec_oprnds,
2504                            unsigned int op_num, unsigned int number_of_vectors,
2505                            int reduc_index)
2506 {
2507   vec<gimple> stmts = SLP_TREE_SCALAR_STMTS (slp_node);
2508   gimple stmt = stmts[0];
2509   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2510   unsigned nunits;
2511   tree vec_cst;
2512   tree *elts;
2513   unsigned j, number_of_places_left_in_vector;
2514   tree vector_type;
2515   tree vop;
2516   int group_size = stmts.length ();
2517   unsigned int vec_num, i;
2518   unsigned number_of_copies = 1;
2519   vec<tree> voprnds;
2520   voprnds.create (number_of_vectors);
2521   bool constant_p, is_store;
2522   tree neutral_op = NULL;
2523   enum tree_code code = gimple_expr_code (stmt);
2524   gimple def_stmt;
2525   struct loop *loop;
2526   gimple_seq ctor_seq = NULL;
2527
2528   if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
2529       && reduc_index != -1)
2530     {
2531       op_num = reduc_index - 1;
2532       op = gimple_op (stmt, reduc_index);
2533       /* For additional copies (see the explanation of NUMBER_OF_COPIES below)
2534          we need either neutral operands or the original operands.  See
2535          get_initial_def_for_reduction() for details.  */
2536       switch (code)
2537         {
2538           case WIDEN_SUM_EXPR:
2539           case DOT_PROD_EXPR:
2540           case PLUS_EXPR:
2541           case MINUS_EXPR:
2542           case BIT_IOR_EXPR:
2543           case BIT_XOR_EXPR:
2544              if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
2545                neutral_op = build_real (TREE_TYPE (op), dconst0);
2546              else
2547                neutral_op = build_int_cst (TREE_TYPE (op), 0);
2548
2549              break;
2550
2551           case MULT_EXPR:
2552              if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (op)))
2553                neutral_op = build_real (TREE_TYPE (op), dconst1);
2554              else
2555                neutral_op = build_int_cst (TREE_TYPE (op), 1);
2556
2557              break;
2558
2559           case BIT_AND_EXPR:
2560             neutral_op = build_int_cst (TREE_TYPE (op), -1);
2561             break;
2562
2563           /* For MIN/MAX we don't have an easy neutral operand but
2564              the initial values can be used fine here.  Only for
2565              a reduction chain we have to force a neutral element.  */
2566           case MAX_EXPR:
2567           case MIN_EXPR:
2568             if (!GROUP_FIRST_ELEMENT (stmt_vinfo))
2569               neutral_op = NULL;
2570             else
2571               {
2572                 def_stmt = SSA_NAME_DEF_STMT (op);
2573                 loop = (gimple_bb (stmt))->loop_father;
2574                 neutral_op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
2575                                                     loop_preheader_edge (loop));
2576               }
2577             break;
2578
2579           default:
2580             neutral_op = NULL;
2581         }
2582     }
2583
2584   if (STMT_VINFO_DATA_REF (stmt_vinfo))
2585     {
2586       is_store = true;
2587       op = gimple_assign_rhs1 (stmt);
2588     }
2589   else
2590     is_store = false;
2591
2592   gcc_assert (op);
2593
2594   if (CONSTANT_CLASS_P (op))
2595     constant_p = true;
2596   else
2597     constant_p = false;
2598
2599   vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
2600   gcc_assert (vector_type);
2601   nunits = TYPE_VECTOR_SUBPARTS (vector_type);
2602
2603   /* NUMBER_OF_COPIES is the number of times we need to use the same values in
2604      created vectors. It is greater than 1 if unrolling is performed.
2605
2606      For example, we have two scalar operands, s1 and s2 (e.g., group of
2607      strided accesses of size two), while NUNITS is four (i.e., four scalars
2608      of this type can be packed in a vector).  The output vector will contain
2609      two copies of each scalar operand: {s1, s2, s1, s2}.  (NUMBER_OF_COPIES
2610      will be 2).
2611
2612      If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
2613      containing the operands.
2614
2615      For example, NUNITS is four as before, and the group size is 8
2616      (s1, s2, ..., s8).  We will create two vectors {s1, s2, s3, s4} and
2617      {s5, s6, s7, s8}.  */
2618
2619   number_of_copies = least_common_multiple (nunits, group_size) / group_size;
2620
2621   number_of_places_left_in_vector = nunits;
2622   elts = XALLOCAVEC (tree, nunits);
2623   for (j = 0; j < number_of_copies; j++)
2624     {
2625       for (i = group_size - 1; stmts.iterate (i, &stmt); i--)
2626         {
2627           if (is_store)
2628             op = gimple_assign_rhs1 (stmt);
2629           else
2630             {
2631               switch (code)
2632                 {
2633                   case COND_EXPR:
2634                     if (op_num == 0 || op_num == 1)
2635                       {
2636                         tree cond = gimple_assign_rhs1 (stmt);
2637                         op = TREE_OPERAND (cond, op_num);
2638                       }
2639                     else
2640                       {
2641                         if (op_num == 2)
2642                           op = gimple_assign_rhs2 (stmt);
2643                         else
2644                           op = gimple_assign_rhs3 (stmt);
2645                       }
2646                     break;
2647
2648                   case CALL_EXPR:
2649                     op = gimple_call_arg (stmt, op_num);
2650                     break;
2651
2652                   case LSHIFT_EXPR:
2653                   case RSHIFT_EXPR:
2654                   case LROTATE_EXPR:
2655                   case RROTATE_EXPR:
2656                     op = gimple_op (stmt, op_num + 1);
2657                     /* Unlike the other binary operators, shifts/rotates have
2658                        the shift count being int, instead of the same type as
2659                        the lhs, so make sure the scalar is the right type if
2660                        we are dealing with vectors of
2661                        long long/long/short/char.  */
2662                     if (op_num == 1 && TREE_CODE (op) == INTEGER_CST)
2663                       op = fold_convert (TREE_TYPE (vector_type), op);
2664                     break;
2665
2666                   default:
2667                     op = gimple_op (stmt, op_num + 1);
2668                     break;
2669                 }
2670             }
2671
2672           if (reduc_index != -1)
2673             {
2674               loop = (gimple_bb (stmt))->loop_father;
2675               def_stmt = SSA_NAME_DEF_STMT (op);
2676
2677               gcc_assert (loop);
2678
2679               /* Get the def before the loop.  In reduction chain we have only
2680                  one initial value.  */
2681               if ((j != (number_of_copies - 1)
2682                    || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt))
2683                        && i != 0))
2684                   && neutral_op)
2685                 op = neutral_op;
2686               else
2687                 op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
2688                                             loop_preheader_edge (loop));
2689             }
2690
2691           /* Create 'vect_ = {op0,op1,...,opn}'.  */
2692           number_of_places_left_in_vector--;
2693           if (!types_compatible_p (TREE_TYPE (vector_type), TREE_TYPE (op)))
2694             {
2695               if (CONSTANT_CLASS_P (op))
2696                 {
2697                   op = fold_unary (VIEW_CONVERT_EXPR,
2698                                    TREE_TYPE (vector_type), op);
2699                   gcc_assert (op && CONSTANT_CLASS_P (op));
2700                 }
2701               else
2702                 {
2703                   tree new_temp = make_ssa_name (TREE_TYPE (vector_type));
2704                   gimple init_stmt;
2705                   op = build1 (VIEW_CONVERT_EXPR, TREE_TYPE (vector_type), op);
2706                   init_stmt
2707                     = gimple_build_assign (new_temp, VIEW_CONVERT_EXPR, op);
2708                   gimple_seq_add_stmt (&ctor_seq, init_stmt);
2709                   op = new_temp;
2710                 }
2711             }
2712           elts[number_of_places_left_in_vector] = op;
2713           if (!CONSTANT_CLASS_P (op))
2714             constant_p = false;
2715
2716           if (number_of_places_left_in_vector == 0)
2717             {
2718               number_of_places_left_in_vector = nunits;
2719
2720               if (constant_p)
2721                 vec_cst = build_vector (vector_type, elts);
2722               else
2723                 {
2724                   vec<constructor_elt, va_gc> *v;
2725                   unsigned k;
2726                   vec_alloc (v, nunits);
2727                   for (k = 0; k < nunits; ++k)
2728                     CONSTRUCTOR_APPEND_ELT (v, NULL_TREE, elts[k]);
2729                   vec_cst = build_constructor (vector_type, v);
2730                 }
2731               voprnds.quick_push (vect_init_vector (stmt, vec_cst,
2732                                                     vector_type, NULL));
2733               if (ctor_seq != NULL)
2734                 {
2735                   gimple init_stmt = SSA_NAME_DEF_STMT (voprnds.last ());
2736                   gimple_stmt_iterator gsi = gsi_for_stmt (init_stmt);
2737                   gsi_insert_seq_before_without_update (&gsi, ctor_seq,
2738                                                         GSI_SAME_STMT);
2739                   ctor_seq = NULL;
2740                 }
2741             }
2742         }
2743     }
2744
2745   /* Since the vectors are created in the reverse order, we should invert
2746      them.  */
2747   vec_num = voprnds.length ();
2748   for (j = vec_num; j != 0; j--)
2749     {
2750       vop = voprnds[j - 1];
2751       vec_oprnds->quick_push (vop);
2752     }
2753
2754   voprnds.release ();
2755
2756   /* In case that VF is greater than the unrolling factor needed for the SLP
2757      group of stmts, NUMBER_OF_VECTORS to be created is greater than
2758      NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
2759      to replicate the vectors.  */
2760   while (number_of_vectors > vec_oprnds->length ())
2761     {
2762       tree neutral_vec = NULL;
2763
2764       if (neutral_op)
2765         {
2766           if (!neutral_vec)
2767             neutral_vec = build_vector_from_val (vector_type, neutral_op);
2768
2769           vec_oprnds->quick_push (neutral_vec);
2770         }
2771       else
2772         {
2773           for (i = 0; vec_oprnds->iterate (i, &vop) && i < vec_num; i++)
2774             vec_oprnds->quick_push (vop);
2775         }
2776     }
2777 }
2778
2779
2780 /* Get vectorized definitions from SLP_NODE that contains corresponding
2781    vectorized def-stmts.  */
2782
2783 static void
2784 vect_get_slp_vect_defs (slp_tree slp_node, vec<tree> *vec_oprnds)
2785 {
2786   tree vec_oprnd;
2787   gimple vec_def_stmt;
2788   unsigned int i;
2789
2790   gcc_assert (SLP_TREE_VEC_STMTS (slp_node).exists ());
2791
2792   FOR_EACH_VEC_ELT (SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt)
2793     {
2794       gcc_assert (vec_def_stmt);
2795       vec_oprnd = gimple_get_lhs (vec_def_stmt);
2796       vec_oprnds->quick_push (vec_oprnd);
2797     }
2798 }
2799
2800
2801 /* Get vectorized definitions for SLP_NODE.
2802    If the scalar definitions are loop invariants or constants, collect them and
2803    call vect_get_constant_vectors() to create vector stmts.
2804    Otherwise, the def-stmts must be already vectorized and the vectorized stmts
2805    must be stored in the corresponding child of SLP_NODE, and we call
2806    vect_get_slp_vect_defs () to retrieve them.  */
2807
2808 void
2809 vect_get_slp_defs (vec<tree> ops, slp_tree slp_node,
2810                    vec<vec<tree> > *vec_oprnds, int reduc_index)
2811 {
2812   gimple first_stmt;
2813   int number_of_vects = 0, i;
2814   unsigned int child_index = 0;
2815   HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
2816   slp_tree child = NULL;
2817   vec<tree> vec_defs;
2818   tree oprnd;
2819   bool vectorized_defs;
2820
2821   first_stmt = SLP_TREE_SCALAR_STMTS (slp_node)[0];
2822   FOR_EACH_VEC_ELT (ops, i, oprnd)
2823     {
2824       /* For each operand we check if it has vectorized definitions in a child
2825          node or we need to create them (for invariants and constants).  We
2826          check if the LHS of the first stmt of the next child matches OPRND.
2827          If it does, we found the correct child.  Otherwise, we call
2828          vect_get_constant_vectors (), and not advance CHILD_INDEX in order
2829          to check this child node for the next operand.  */
2830       vectorized_defs = false;
2831       if (SLP_TREE_CHILDREN (slp_node).length () > child_index)
2832         {
2833           child = SLP_TREE_CHILDREN (slp_node)[child_index];
2834
2835           /* We have to check both pattern and original def, if available.  */
2836           gimple first_def = SLP_TREE_SCALAR_STMTS (child)[0];
2837           gimple related = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def));
2838
2839           if (operand_equal_p (oprnd, gimple_get_lhs (first_def), 0)
2840               || (related
2841                   && operand_equal_p (oprnd, gimple_get_lhs (related), 0)))
2842             {
2843               /* The number of vector defs is determined by the number of
2844                  vector statements in the node from which we get those
2845                  statements.  */
2846               number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (child);
2847               vectorized_defs = true;
2848               child_index++;
2849             }
2850         }
2851
2852       if (!vectorized_defs)
2853         {
2854           if (i == 0)
2855             {
2856               number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
2857               /* Number of vector stmts was calculated according to LHS in
2858                  vect_schedule_slp_instance (), fix it by replacing LHS with
2859                  RHS, if necessary.  See vect_get_smallest_scalar_type () for
2860                  details.  */
2861               vect_get_smallest_scalar_type (first_stmt, &lhs_size_unit,
2862                                              &rhs_size_unit);
2863               if (rhs_size_unit != lhs_size_unit)
2864                 {
2865                   number_of_vects *= rhs_size_unit;
2866                   number_of_vects /= lhs_size_unit;
2867                 }
2868             }
2869         }
2870
2871       /* Allocate memory for vectorized defs.  */
2872       vec_defs = vNULL;
2873       vec_defs.create (number_of_vects);
2874
2875       /* For reduction defs we call vect_get_constant_vectors (), since we are
2876          looking for initial loop invariant values.  */
2877       if (vectorized_defs && reduc_index == -1)
2878         /* The defs are already vectorized.  */
2879         vect_get_slp_vect_defs (child, &vec_defs);
2880       else
2881         /* Build vectors from scalar defs.  */
2882         vect_get_constant_vectors (oprnd, slp_node, &vec_defs, i,
2883                                    number_of_vects, reduc_index);
2884
2885       vec_oprnds->quick_push (vec_defs);
2886
2887       /* For reductions, we only need initial values.  */
2888       if (reduc_index != -1)
2889         return;
2890     }
2891 }
2892
2893
2894 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
2895    building a vector of type MASK_TYPE from it) and two input vectors placed in
2896    DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
2897    shifting by STRIDE elements of DR_CHAIN for every copy.
2898    (STRIDE is the number of vectorized stmts for NODE divided by the number of
2899    copies).
2900    VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
2901    the created stmts must be inserted.  */
2902
2903 static inline void
2904 vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
2905                            tree mask, int first_vec_indx, int second_vec_indx,
2906                            gimple_stmt_iterator *gsi, slp_tree node,
2907                            tree vectype, vec<tree> dr_chain,
2908                            int ncopies, int vect_stmts_counter)
2909 {
2910   tree perm_dest;
2911   gimple perm_stmt = NULL;
2912   stmt_vec_info next_stmt_info;
2913   int i, stride;
2914   tree first_vec, second_vec, data_ref;
2915
2916   stride = SLP_TREE_NUMBER_OF_VEC_STMTS (node) / ncopies;
2917
2918   /* Initialize the vect stmts of NODE to properly insert the generated
2919      stmts later.  */
2920   for (i = SLP_TREE_VEC_STMTS (node).length ();
2921        i < (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
2922     SLP_TREE_VEC_STMTS (node).quick_push (NULL);
2923
2924   perm_dest = vect_create_destination_var (gimple_assign_lhs (stmt), vectype);
2925   for (i = 0; i < ncopies; i++)
2926     {
2927       first_vec = dr_chain[first_vec_indx];
2928       second_vec = dr_chain[second_vec_indx];
2929
2930       /* Generate the permute statement.  */
2931       perm_stmt = gimple_build_assign (perm_dest, VEC_PERM_EXPR,
2932                                        first_vec, second_vec, mask);
2933       data_ref = make_ssa_name (perm_dest, perm_stmt);
2934       gimple_set_lhs (perm_stmt, data_ref);
2935       vect_finish_stmt_generation (stmt, perm_stmt, gsi);
2936
2937       /* Store the vector statement in NODE.  */
2938       SLP_TREE_VEC_STMTS (node)[stride * i + vect_stmts_counter] = perm_stmt;
2939
2940       first_vec_indx += stride;
2941       second_vec_indx += stride;
2942     }
2943
2944   /* Mark the scalar stmt as vectorized.  */
2945   next_stmt_info = vinfo_for_stmt (next_scalar_stmt);
2946   STMT_VINFO_VEC_STMT (next_stmt_info) = perm_stmt;
2947 }
2948
2949
2950 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
2951    return in CURRENT_MASK_ELEMENT its equivalent in target specific
2952    representation.  Check that the mask is valid and return FALSE if not.
2953    Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
2954    the next vector, i.e., the current first vector is not needed.  */
2955
2956 static bool
2957 vect_get_mask_element (gimple stmt, int first_mask_element, int m,
2958                        int mask_nunits, bool only_one_vec, int index,
2959                        unsigned char *mask, int *current_mask_element,
2960                        bool *need_next_vector, int *number_of_mask_fixes,
2961                        bool *mask_fixed, bool *needs_first_vector)
2962 {
2963   int i;
2964
2965   /* Convert to target specific representation.  */
2966   *current_mask_element = first_mask_element + m;
2967   /* Adjust the value in case it's a mask for second and third vectors.  */
2968   *current_mask_element -= mask_nunits * (*number_of_mask_fixes - 1);
2969
2970   if (*current_mask_element < mask_nunits)
2971     *needs_first_vector = true;
2972
2973   /* We have only one input vector to permute but the mask accesses values in
2974      the next vector as well.  */
2975   if (only_one_vec && *current_mask_element >= mask_nunits)
2976     {
2977       if (dump_enabled_p ())
2978         {
2979           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2980                            "permutation requires at least two vectors ");
2981           dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
2982           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
2983         }
2984
2985       return false;
2986     }
2987
2988   /* The mask requires the next vector.  */
2989   while (*current_mask_element >= mask_nunits * 2)
2990     {
2991       if (*needs_first_vector || *mask_fixed)
2992         {
2993           /* We either need the first vector too or have already moved to the
2994              next vector. In both cases, this permutation needs three
2995              vectors.  */
2996           if (dump_enabled_p ())
2997             {
2998               dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
2999                                "permutation requires at "
3000                                "least three vectors ");
3001               dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3002               dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3003             }
3004
3005           return false;
3006         }
3007
3008       /* We move to the next vector, dropping the first one and working with
3009          the second and the third - we need to adjust the values of the mask
3010          accordingly.  */
3011       *current_mask_element -= mask_nunits * *number_of_mask_fixes;
3012
3013       for (i = 0; i < index; i++)
3014         mask[i] -= mask_nunits * *number_of_mask_fixes;
3015
3016       (*number_of_mask_fixes)++;
3017       *mask_fixed = true;
3018     }
3019
3020   *need_next_vector = *mask_fixed;
3021
3022   /* This was the last element of this mask. Start a new one.  */
3023   if (index == mask_nunits - 1)
3024     {
3025       *number_of_mask_fixes = 1;
3026       *mask_fixed = false;
3027       *needs_first_vector = false;
3028     }
3029
3030   return true;
3031 }
3032
3033
3034 /* Generate vector permute statements from a list of loads in DR_CHAIN.
3035    If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
3036    permute statements for the SLP node NODE of the SLP instance
3037    SLP_NODE_INSTANCE.  */
3038
3039 bool
3040 vect_transform_slp_perm_load (slp_tree node, vec<tree> dr_chain,
3041                               gimple_stmt_iterator *gsi, int vf,
3042                               slp_instance slp_node_instance, bool analyze_only)
3043 {
3044   gimple stmt = SLP_TREE_SCALAR_STMTS (node)[0];
3045   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3046   tree mask_element_type = NULL_TREE, mask_type;
3047   int i, j, k, nunits, vec_index = 0, scalar_index;
3048   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3049   gimple next_scalar_stmt;
3050   int group_size = SLP_INSTANCE_GROUP_SIZE (slp_node_instance);
3051   int first_mask_element;
3052   int index, unroll_factor, current_mask_element, ncopies;
3053   unsigned char *mask;
3054   bool only_one_vec = false, need_next_vector = false;
3055   int first_vec_index, second_vec_index, orig_vec_stmts_num, vect_stmts_counter;
3056   int number_of_mask_fixes = 1;
3057   bool mask_fixed = false;
3058   bool needs_first_vector = false;
3059   machine_mode mode;
3060
3061   mode = TYPE_MODE (vectype);
3062
3063   if (!can_vec_perm_p (mode, false, NULL))
3064     {
3065       if (dump_enabled_p ())
3066         {
3067           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
3068                            "no vect permute for ");
3069           dump_gimple_stmt (MSG_MISSED_OPTIMIZATION, TDF_SLIM, stmt, 0);
3070           dump_printf (MSG_MISSED_OPTIMIZATION, "\n");
3071         }
3072       return false;
3073     }
3074
3075   /* The generic VEC_PERM_EXPR code always uses an integral type of the
3076      same size as the vector element being permuted.  */
3077   mask_element_type = lang_hooks.types.type_for_mode
3078                 (int_mode_for_mode (TYPE_MODE (TREE_TYPE (vectype))), 1);
3079   mask_type = get_vectype_for_scalar_type (mask_element_type);
3080   nunits = TYPE_VECTOR_SUBPARTS (vectype);
3081   mask = XALLOCAVEC (unsigned char, nunits);
3082   unroll_factor = SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
3083
3084   /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
3085      unrolling factor.  */
3086   orig_vec_stmts_num = group_size *
3087                 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance) / nunits;
3088   if (orig_vec_stmts_num == 1)
3089     only_one_vec = true;
3090
3091   /* Number of copies is determined by the final vectorization factor
3092      relatively to SLP_NODE_INSTANCE unrolling factor.  */
3093   ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
3094
3095   if (!STMT_VINFO_GROUPED_ACCESS (stmt_info))
3096     return false;
3097
3098   /* Generate permutation masks for every NODE. Number of masks for each NODE
3099      is equal to GROUP_SIZE.
3100      E.g., we have a group of three nodes with three loads from the same
3101      location in each node, and the vector size is 4. I.e., we have a
3102      a0b0c0a1b1c1... sequence and we need to create the following vectors:
3103      for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
3104      for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
3105      ...
3106
3107      The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
3108      The last mask is illegal since we assume two operands for permute
3109      operation, and the mask element values can't be outside that range.
3110      Hence, the last mask must be converted into {2,5,5,5}.
3111      For the first two permutations we need the first and the second input
3112      vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
3113      we need the second and the third vectors: {b1,c1,a2,b2} and
3114      {c2,a3,b3,c3}.  */
3115
3116     {
3117       scalar_index = 0;
3118       index = 0;
3119       vect_stmts_counter = 0;
3120       vec_index = 0;
3121       first_vec_index = vec_index++;
3122       if (only_one_vec)
3123         second_vec_index = first_vec_index;
3124       else
3125         second_vec_index =  vec_index++;
3126
3127       for (j = 0; j < unroll_factor; j++)
3128         {
3129           for (k = 0; k < group_size; k++)
3130             {
3131               i = SLP_TREE_LOAD_PERMUTATION (node)[k];
3132               first_mask_element = i + j * group_size;
3133               if (!vect_get_mask_element (stmt, first_mask_element, 0,
3134                                           nunits, only_one_vec, index,
3135                                           mask, &current_mask_element,
3136                                           &need_next_vector,
3137                                           &number_of_mask_fixes, &mask_fixed,
3138                                           &needs_first_vector))
3139                 return false;
3140               gcc_assert (current_mask_element < 2 * nunits);
3141               mask[index++] = current_mask_element;
3142
3143               if (index == nunits)
3144                 {
3145                   index = 0;
3146                   if (!can_vec_perm_p (mode, false, mask))
3147                     {
3148                       if (dump_enabled_p ())
3149                         {
3150                           dump_printf_loc (MSG_MISSED_OPTIMIZATION,
3151                                            vect_location,
3152                                            "unsupported vect permute { ");
3153                           for (i = 0; i < nunits; ++i)
3154                             dump_printf (MSG_MISSED_OPTIMIZATION, "%d ",
3155                                          mask[i]);
3156                           dump_printf (MSG_MISSED_OPTIMIZATION, "}\n");
3157                         }
3158                       return false;
3159                     }
3160
3161                   if (!analyze_only)
3162                     {
3163                       int l;
3164                       tree mask_vec, *mask_elts;
3165                       mask_elts = XALLOCAVEC (tree, nunits);
3166                       for (l = 0; l < nunits; ++l)
3167                         mask_elts[l] = build_int_cst (mask_element_type,
3168                                                       mask[l]);
3169                       mask_vec = build_vector (mask_type, mask_elts);
3170
3171                       if (need_next_vector)
3172                         {
3173                           first_vec_index = second_vec_index;
3174                           second_vec_index = vec_index;
3175                         }
3176
3177                       next_scalar_stmt
3178                           = SLP_TREE_SCALAR_STMTS (node)[scalar_index++];
3179
3180                       vect_create_mask_and_perm (stmt, next_scalar_stmt,
3181                                mask_vec, first_vec_index, second_vec_index,
3182                                gsi, node, vectype, dr_chain,
3183                                ncopies, vect_stmts_counter++);
3184                     }
3185                 }
3186             }
3187         }
3188     }
3189
3190   return true;
3191 }
3192
3193
3194
3195 /* Vectorize SLP instance tree in postorder.  */
3196
3197 static bool
3198 vect_schedule_slp_instance (slp_tree node, slp_instance instance,
3199                             unsigned int vectorization_factor)
3200 {
3201   gimple stmt;
3202   bool grouped_store, is_store;
3203   gimple_stmt_iterator si;
3204   stmt_vec_info stmt_info;
3205   unsigned int vec_stmts_size, nunits, group_size;
3206   tree vectype;
3207   int i;
3208   slp_tree child;
3209
3210   if (!node)
3211     return false;
3212
3213   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
3214     vect_schedule_slp_instance (child, instance, vectorization_factor);
3215
3216   stmt = SLP_TREE_SCALAR_STMTS (node)[0];
3217   stmt_info = vinfo_for_stmt (stmt);
3218
3219   /* VECTYPE is the type of the destination.  */
3220   vectype = STMT_VINFO_VECTYPE (stmt_info);
3221   nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (vectype);
3222   group_size = SLP_INSTANCE_GROUP_SIZE (instance);
3223
3224   /* For each SLP instance calculate number of vector stmts to be created
3225      for the scalar stmts in each node of the SLP tree.  Number of vector
3226      elements in one vector iteration is the number of scalar elements in
3227      one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
3228      size.  */
3229   vec_stmts_size = (vectorization_factor * group_size) / nunits;
3230
3231   if (!SLP_TREE_VEC_STMTS (node).exists ())
3232     {
3233       SLP_TREE_VEC_STMTS (node).create (vec_stmts_size);
3234       SLP_TREE_NUMBER_OF_VEC_STMTS (node) = vec_stmts_size;
3235     }
3236
3237   if (dump_enabled_p ())
3238     {
3239       dump_printf_loc (MSG_NOTE,vect_location,
3240                        "------>vectorizing SLP node starting from: ");
3241       dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
3242       dump_printf (MSG_NOTE, "\n");
3243     }
3244
3245   /* Loads should be inserted before the first load.  */
3246   if (SLP_INSTANCE_FIRST_LOAD_STMT (instance)
3247       && STMT_VINFO_GROUPED_ACCESS (stmt_info)
3248       && !REFERENCE_CLASS_P (gimple_get_lhs (stmt))
3249       && SLP_TREE_LOAD_PERMUTATION (node).exists ())
3250     si = gsi_for_stmt (SLP_INSTANCE_FIRST_LOAD_STMT (instance));
3251   else if (is_pattern_stmt_p (stmt_info))
3252     si = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
3253   else
3254     si = gsi_for_stmt (stmt);
3255
3256   /* Stores should be inserted just before the last store.  */
3257   if (STMT_VINFO_GROUPED_ACCESS (stmt_info)
3258       && REFERENCE_CLASS_P (gimple_get_lhs (stmt)))
3259     {
3260       gimple last_store = vect_find_last_store_in_slp_instance (instance);
3261       if (is_pattern_stmt_p (vinfo_for_stmt (last_store)))
3262        last_store = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (last_store));
3263       si = gsi_for_stmt (last_store);
3264     }
3265
3266   /* Mark the first element of the reduction chain as reduction to properly
3267      transform the node.  In the analysis phase only the last element of the
3268      chain is marked as reduction.  */
3269   if (GROUP_FIRST_ELEMENT (stmt_info) && !STMT_VINFO_GROUPED_ACCESS (stmt_info)
3270       && GROUP_FIRST_ELEMENT (stmt_info) == stmt)
3271     {
3272       STMT_VINFO_DEF_TYPE (stmt_info) = vect_reduction_def;
3273       STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
3274     }
3275
3276   is_store = vect_transform_stmt (stmt, &si, &grouped_store, node, instance);
3277   return is_store;
3278 }
3279
3280 /* Replace scalar calls from SLP node NODE with setting of their lhs to zero.
3281    For loop vectorization this is done in vectorizable_call, but for SLP
3282    it needs to be deferred until end of vect_schedule_slp, because multiple
3283    SLP instances may refer to the same scalar stmt.  */
3284
3285 static void
3286 vect_remove_slp_scalar_calls (slp_tree node)
3287 {
3288   gimple stmt, new_stmt;
3289   gimple_stmt_iterator gsi;
3290   int i;
3291   slp_tree child;
3292   tree lhs;
3293   stmt_vec_info stmt_info;
3294
3295   if (!node)
3296     return;
3297
3298   FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), i, child)
3299     vect_remove_slp_scalar_calls (child);
3300
3301   FOR_EACH_VEC_ELT (SLP_TREE_SCALAR_STMTS (node), i, stmt)
3302     {
3303       if (!is_gimple_call (stmt) || gimple_bb (stmt) == NULL)
3304         continue;
3305       stmt_info = vinfo_for_stmt (stmt);
3306       if (stmt_info == NULL
3307           || is_pattern_stmt_p (stmt_info)
3308           || !PURE_SLP_STMT (stmt_info))
3309         continue;
3310       lhs = gimple_call_lhs (stmt);
3311       new_stmt = gimple_build_assign (lhs, build_zero_cst (TREE_TYPE (lhs)));
3312       set_vinfo_for_stmt (new_stmt, stmt_info);
3313       set_vinfo_for_stmt (stmt, NULL);
3314       STMT_VINFO_STMT (stmt_info) = new_stmt;
3315       gsi = gsi_for_stmt (stmt);
3316       gsi_replace (&gsi, new_stmt, false);
3317       SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt)) = new_stmt;
3318     }
3319 }
3320
3321 /* Generate vector code for all SLP instances in the loop/basic block.  */
3322
3323 bool
3324 vect_schedule_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
3325 {
3326   vec<slp_instance> slp_instances;
3327   slp_instance instance;
3328   unsigned int i, vf;
3329   bool is_store = false;
3330
3331   if (loop_vinfo)
3332     {
3333       slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
3334       vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3335     }
3336   else
3337     {
3338       slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
3339       vf = 1;
3340     }
3341
3342   FOR_EACH_VEC_ELT (slp_instances, i, instance)
3343     {
3344       /* Schedule the tree of INSTANCE.  */
3345       is_store = vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
3346                                              instance, vf);
3347       if (dump_enabled_p ())
3348         dump_printf_loc (MSG_NOTE, vect_location,
3349                          "vectorizing stmts using SLP.\n");
3350     }
3351
3352   FOR_EACH_VEC_ELT (slp_instances, i, instance)
3353     {
3354       slp_tree root = SLP_INSTANCE_TREE (instance);
3355       gimple store;
3356       unsigned int j;
3357       gimple_stmt_iterator gsi;
3358
3359       /* Remove scalar call stmts.  Do not do this for basic-block
3360          vectorization as not all uses may be vectorized.
3361          ???  Why should this be necessary?  DCE should be able to
3362          remove the stmts itself.
3363          ???  For BB vectorization we can as well remove scalar
3364          stmts starting from the SLP tree root if they have no
3365          uses.  */
3366       if (loop_vinfo)
3367         vect_remove_slp_scalar_calls (root);
3368
3369       for (j = 0; SLP_TREE_SCALAR_STMTS (root).iterate (j, &store)
3370                   && j < SLP_INSTANCE_GROUP_SIZE (instance); j++)
3371         {
3372           if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store)))
3373             break;
3374
3375          if (is_pattern_stmt_p (vinfo_for_stmt (store)))
3376            store = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (store));
3377           /* Free the attached stmt_vec_info and remove the stmt.  */
3378           gsi = gsi_for_stmt (store);
3379           unlink_stmt_vdef (store);
3380           gsi_remove (&gsi, true);
3381           release_defs (store);
3382           free_stmt_vec_info (store);
3383         }
3384     }
3385
3386   return is_store;
3387 }
3388
3389
3390 /* Vectorize the basic block.  */
3391
3392 void
3393 vect_slp_transform_bb (basic_block bb)
3394 {
3395   bb_vec_info bb_vinfo = vec_info_for_bb (bb);
3396   gimple_stmt_iterator si;
3397
3398   gcc_assert (bb_vinfo);
3399
3400   if (dump_enabled_p ())
3401     dump_printf_loc (MSG_NOTE, vect_location, "SLPing BB\n");
3402
3403   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
3404     {
3405       gimple stmt = gsi_stmt (si);
3406       stmt_vec_info stmt_info;
3407
3408       if (dump_enabled_p ())
3409         {
3410           dump_printf_loc (MSG_NOTE, vect_location,
3411                            "------>SLPing statement: ");
3412           dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0);
3413           dump_printf (MSG_NOTE, "\n");
3414         }
3415
3416       stmt_info = vinfo_for_stmt (stmt);
3417       gcc_assert (stmt_info);
3418
3419       /* Schedule all the SLP instances when the first SLP stmt is reached.  */
3420       if (STMT_SLP_TYPE (stmt_info))
3421         {
3422           vect_schedule_slp (NULL, bb_vinfo);
3423           break;
3424         }
3425     }
3426
3427   if (dump_enabled_p ())
3428     dump_printf_loc (MSG_NOTE, vect_location,
3429                      "BASIC BLOCK VECTORIZED\n");
3430
3431   destroy_bb_vec_info (bb_vinfo);
3432 }