gcc/tree-vect-slp.c

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