gcc/tree-vect-slp.c

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