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_expr_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
2291             {
2292               switch (code)
2293                 {
2294                   case COND_EXPR:
2295                     if (op_num == 0 || op_num == 1)
2296                       {
2297                         tree cond = gimple_assign_rhs1 (stmt);
2298                         op = TREE_OPERAND (cond, op_num);
2299                       }
2300                     else
2301                       {
2302                         if (op_num == 2)
2303                           op = gimple_assign_rhs2 (stmt);
2304                         else
2305                           op = gimple_assign_rhs3 (stmt);
2306                       }
2307                     break;
2308
2309                   case CALL_EXPR:
2310                     op = gimple_call_arg (stmt, op_num);
2311                     break;
2312
2313                   default:
2314                     op = gimple_op (stmt, op_num + 1);
2315                 }
2316             }
2317
2318           if (reduc_index != -1)
2319             {
2320               loop = (gimple_bb (stmt))->loop_father;
2321               def_stmt = SSA_NAME_DEF_STMT (op);
2322
2323               gcc_assert (loop);
2324
2325               /* Get the def before the loop.  In reduction chain we have only
2326                  one initial value.  */
2327               if ((j != (number_of_copies - 1)
2328                    || (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt))
2329                        && i != 0))
2330                   && neutral_op)
2331                 op = neutral_op;
2332               else
2333                 op = PHI_ARG_DEF_FROM_EDGE (def_stmt,
2334                                             loop_preheader_edge (loop));
2335             }
2336
2337           /* Create 'vect_ = {op0,op1,...,opn}'.  */
2338           t = tree_cons (NULL_TREE, op, t);
2339
2340           number_of_places_left_in_vector--;
2341
2342           if (number_of_places_left_in_vector == 0)
2343             {
2344               number_of_places_left_in_vector = nunits;
2345
2346               if (constant_p)
2347                 vec_cst = build_vector (vector_type, t);
2348               else
2349                 vec_cst = build_constructor_from_list (vector_type, t);
2350               VEC_quick_push (tree, voprnds,
2351                               vect_init_vector (stmt, vec_cst, vector_type, NULL));
2352               t = NULL_TREE;
2353             }
2354         }
2355     }
2356
2357   /* Since the vectors are created in the reverse order, we should invert
2358      them.  */
2359   vec_num = VEC_length (tree, voprnds);
2360   for (j = vec_num - 1; j >= 0; j--)
2361     {
2362       vop = VEC_index (tree, voprnds, j);
2363       VEC_quick_push (tree, *vec_oprnds, vop);
2364     }
2365
2366   VEC_free (tree, heap, voprnds);
2367
2368   /* In case that VF is greater than the unrolling factor needed for the SLP
2369      group of stmts, NUMBER_OF_VECTORS to be created is greater than
2370      NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
2371      to replicate the vectors.  */
2372   while (number_of_vectors > VEC_length (tree, *vec_oprnds))
2373     {
2374       tree neutral_vec = NULL;
2375
2376       if (neutral_op)
2377         {
2378           if (!neutral_vec)
2379             neutral_vec = build_vector_from_val (vector_type, neutral_op);
2380
2381           VEC_quick_push (tree, *vec_oprnds, neutral_vec);
2382         }
2383       else
2384         {
2385           for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
2386             VEC_quick_push (tree, *vec_oprnds, vop);
2387         }
2388     }
2389 }
2390
2391
2392 /* Get vectorized definitions from SLP_NODE that contains corresponding
2393    vectorized def-stmts.  */
2394
2395 static void
2396 vect_get_slp_vect_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds)
2397 {
2398   tree vec_oprnd;
2399   gimple vec_def_stmt;
2400   unsigned int i;
2401
2402   gcc_assert (SLP_TREE_VEC_STMTS (slp_node));
2403
2404   FOR_EACH_VEC_ELT (gimple, SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt)
2405     {
2406       gcc_assert (vec_def_stmt);
2407       vec_oprnd = gimple_get_lhs (vec_def_stmt);
2408       VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2409     }
2410 }
2411
2412
2413 /* Get vectorized definitions for SLP_NODE.
2414    If the scalar definitions are loop invariants or constants, collect them and
2415    call vect_get_constant_vectors() to create vector stmts.
2416    Otherwise, the def-stmts must be already vectorized and the vectorized stmts
2417    must be stored in the corresponding child of SLP_NODE, and we call
2418    vect_get_slp_vect_defs () to retrieve them.  */
2419
2420 void
2421 vect_get_slp_defs (VEC (tree, heap) *ops, slp_tree slp_node,
2422                    VEC (slp_void_p, heap) **vec_oprnds, int reduc_index)
2423 {
2424   gimple first_stmt, first_def;
2425   int number_of_vects = 0, i;
2426   unsigned int child_index = 0;
2427   HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
2428   slp_tree child = NULL;
2429   VEC (tree, heap) *vec_defs;
2430   tree oprnd, def_lhs;
2431   bool vectorized_defs;
2432
2433   first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
2434   FOR_EACH_VEC_ELT (tree, ops, i, oprnd)
2435     {
2436       /* For each operand we check if it has vectorized definitions in a child
2437          node or we need to create them (for invariants and constants).  We
2438          check if the LHS of the first stmt of the next child matches OPRND.
2439          If it does, we found the correct child.  Otherwise, we call
2440          vect_get_constant_vectors (), and not advance CHILD_INDEX in order
2441          to check this child node for the next operand.  */
2442       vectorized_defs = false;
2443       if (VEC_length (slp_void_p, SLP_TREE_CHILDREN (slp_node)) > child_index)
2444         {
2445           child = (slp_tree) VEC_index (slp_void_p,
2446                                         SLP_TREE_CHILDREN (slp_node),
2447                                         child_index);
2448           first_def = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (child), 0);
2449
2450           /* In the end of a pattern sequence we have a use of the original stmt,
2451              so we need to compare OPRND with the original def.  */
2452           if (is_pattern_stmt_p (vinfo_for_stmt (first_def))
2453               && !STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (first_stmt))
2454               && !is_pattern_stmt_p (vinfo_for_stmt (first_stmt)))
2455             first_def = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (first_def));
2456
2457           if (is_gimple_call (first_def))
2458             def_lhs = gimple_call_lhs (first_def);
2459           else
2460             def_lhs = gimple_assign_lhs (first_def);
2461
2462           if (operand_equal_p (oprnd, def_lhs, 0))
2463             {
2464               /* The number of vector defs is determined by the number of
2465                  vector statements in the node from which we get those
2466                  statements.  */
2467                  number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (child);
2468                  vectorized_defs = true;
2469               child_index++;
2470             }
2471         }
2472
2473       if (!vectorized_defs)
2474         {
2475           if (i == 0)
2476             {
2477               number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
2478               /* Number of vector stmts was calculated according to LHS in
2479                  vect_schedule_slp_instance (), fix it by replacing LHS with
2480                  RHS, if necessary.  See vect_get_smallest_scalar_type () for
2481                  details.  */
2482               vect_get_smallest_scalar_type (first_stmt, &lhs_size_unit,
2483                                              &rhs_size_unit);
2484               if (rhs_size_unit != lhs_size_unit)
2485                 {
2486                   number_of_vects *= rhs_size_unit;
2487                   number_of_vects /= lhs_size_unit;
2488                 }
2489             }
2490         }
2491
2492       /* Allocate memory for vectorized defs.  */
2493       vec_defs = VEC_alloc (tree, heap, number_of_vects);
2494
2495       /* For reduction defs we call vect_get_constant_vectors (), since we are
2496          looking for initial loop invariant values.  */
2497       if (vectorized_defs && reduc_index == -1)
2498         /* The defs are already vectorized.  */
2499         vect_get_slp_vect_defs (child, &vec_defs);
2500       else
2501         /* Build vectors from scalar defs.  */
2502         vect_get_constant_vectors (oprnd, slp_node, &vec_defs, i,
2503                                    number_of_vects, reduc_index);
2504
2505       VEC_quick_push (slp_void_p, *vec_oprnds, (slp_void_p) vec_defs);
2506
2507       /* For reductions, we only need initial values.  */
2508       if (reduc_index != -1)
2509         return;
2510     }
2511 }
2512
2513
2514 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
2515    building a vector of type MASK_TYPE from it) and two input vectors placed in
2516    DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
2517    shifting by STRIDE elements of DR_CHAIN for every copy.
2518    (STRIDE is the number of vectorized stmts for NODE divided by the number of
2519    copies).
2520    VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
2521    the created stmts must be inserted.  */
2522
2523 static inline void
2524 vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
2525                            tree mask, int first_vec_indx, int second_vec_indx,
2526                            gimple_stmt_iterator *gsi, slp_tree node,
2527                            tree vectype, VEC(tree,heap) *dr_chain,
2528                            int ncopies, int vect_stmts_counter)
2529 {
2530   tree perm_dest;
2531   gimple perm_stmt = NULL;
2532   stmt_vec_info next_stmt_info;
2533   int i, stride;
2534   tree first_vec, second_vec, data_ref;
2535
2536   stride = SLP_TREE_NUMBER_OF_VEC_STMTS (node) / ncopies;
2537
2538   /* Initialize the vect stmts of NODE to properly insert the generated
2539      stmts later.  */
2540   for (i = VEC_length (gimple, SLP_TREE_VEC_STMTS (node));
2541        i < (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
2542     VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (node), NULL);
2543
2544   perm_dest = vect_create_destination_var (gimple_assign_lhs (stmt), vectype);
2545   for (i = 0; i < ncopies; i++)
2546     {
2547       first_vec = VEC_index (tree, dr_chain, first_vec_indx);
2548       second_vec = VEC_index (tree, dr_chain, second_vec_indx);
2549
2550       /* Generate the permute statement.  */
2551       perm_stmt = gimple_build_assign_with_ops3 (VEC_PERM_EXPR, perm_dest,
2552                                                  first_vec, second_vec, mask);
2553       data_ref = make_ssa_name (perm_dest, perm_stmt);
2554       gimple_set_lhs (perm_stmt, data_ref);
2555       vect_finish_stmt_generation (stmt, perm_stmt, gsi);
2556
2557       /* Store the vector statement in NODE.  */
2558       VEC_replace (gimple, SLP_TREE_VEC_STMTS (node),
2559                    stride * i + vect_stmts_counter, perm_stmt);
2560
2561       first_vec_indx += stride;
2562       second_vec_indx += stride;
2563     }
2564
2565   /* Mark the scalar stmt as vectorized.  */
2566   next_stmt_info = vinfo_for_stmt (next_scalar_stmt);
2567   STMT_VINFO_VEC_STMT (next_stmt_info) = perm_stmt;
2568 }
2569
2570
2571 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
2572    return in CURRENT_MASK_ELEMENT its equivalent in target specific
2573    representation.  Check that the mask is valid and return FALSE if not.
2574    Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
2575    the next vector, i.e., the current first vector is not needed.  */
2576
2577 static bool
2578 vect_get_mask_element (gimple stmt, int first_mask_element, int m,
2579                        int mask_nunits, bool only_one_vec, int index,
2580                        unsigned char *mask, int *current_mask_element,
2581                        bool *need_next_vector, int *number_of_mask_fixes,
2582                        bool *mask_fixed, bool *needs_first_vector)
2583 {
2584   int i;
2585
2586   /* Convert to target specific representation.  */
2587   *current_mask_element = first_mask_element + m;
2588   /* Adjust the value in case it's a mask for second and third vectors.  */
2589   *current_mask_element -= mask_nunits * (*number_of_mask_fixes - 1);
2590
2591   if (*current_mask_element < mask_nunits)
2592     *needs_first_vector = true;
2593
2594   /* We have only one input vector to permute but the mask accesses values in
2595      the next vector as well.  */
2596   if (only_one_vec && *current_mask_element >= mask_nunits)
2597     {
2598       if (vect_print_dump_info (REPORT_DETAILS))
2599         {
2600           fprintf (vect_dump, "permutation requires at least two vectors ");
2601           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2602         }
2603
2604       return false;
2605     }
2606
2607   /* The mask requires the next vector.  */
2608   if (*current_mask_element >= mask_nunits * 2)
2609     {
2610       if (*needs_first_vector || *mask_fixed)
2611         {
2612           /* We either need the first vector too or have already moved to the
2613              next vector. In both cases, this permutation needs three
2614              vectors.  */
2615           if (vect_print_dump_info (REPORT_DETAILS))
2616             {
2617               fprintf (vect_dump, "permutation requires at "
2618                                   "least three vectors ");
2619               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2620             }
2621
2622           return false;
2623         }
2624
2625       /* We move to the next vector, dropping the first one and working with
2626          the second and the third - we need to adjust the values of the mask
2627          accordingly.  */
2628       *current_mask_element -= mask_nunits * *number_of_mask_fixes;
2629
2630       for (i = 0; i < index; i++)
2631         mask[i] -= mask_nunits * *number_of_mask_fixes;
2632
2633       (*number_of_mask_fixes)++;
2634       *mask_fixed = true;
2635     }
2636
2637   *need_next_vector = *mask_fixed;
2638
2639   /* This was the last element of this mask. Start a new one.  */
2640   if (index == mask_nunits - 1)
2641     {
2642       *number_of_mask_fixes = 1;
2643       *mask_fixed = false;
2644       *needs_first_vector = false;
2645     }
2646
2647   return true;
2648 }
2649
2650
2651 /* Generate vector permute statements from a list of loads in DR_CHAIN.
2652    If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
2653    permute statements for SLP_NODE_INSTANCE.  */
2654 bool
2655 vect_transform_slp_perm_load (gimple stmt, VEC (tree, heap) *dr_chain,
2656                               gimple_stmt_iterator *gsi, int vf,
2657                               slp_instance slp_node_instance, bool analyze_only)
2658 {
2659   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2660   tree mask_element_type = NULL_TREE, mask_type;
2661   int i, j, k, nunits, vec_index = 0, scalar_index;
2662   slp_tree node;
2663   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2664   gimple next_scalar_stmt;
2665   int group_size = SLP_INSTANCE_GROUP_SIZE (slp_node_instance);
2666   int first_mask_element;
2667   int index, unroll_factor, current_mask_element, ncopies;
2668   unsigned char *mask;
2669   bool only_one_vec = false, need_next_vector = false;
2670   int first_vec_index, second_vec_index, orig_vec_stmts_num, vect_stmts_counter;
2671   int number_of_mask_fixes = 1;
2672   bool mask_fixed = false;
2673   bool needs_first_vector = false;
2674   enum machine_mode mode;
2675
2676   mode = TYPE_MODE (vectype);
2677
2678   if (!can_vec_perm_p (mode, false, NULL))
2679     {
2680       if (vect_print_dump_info (REPORT_DETAILS))
2681         {
2682           fprintf (vect_dump, "no vect permute for ");
2683           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2684         }
2685       return false;
2686     }
2687
2688   /* The generic VEC_PERM_EXPR code always uses an integral type of the
2689      same size as the vector element being permuted.  */
2690   mask_element_type
2691     = lang_hooks.types.type_for_size
2692     (TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (vectype))), 1);
2693   mask_type = get_vectype_for_scalar_type (mask_element_type);
2694   nunits = TYPE_VECTOR_SUBPARTS (vectype);
2695   mask = XALLOCAVEC (unsigned char, nunits);
2696   unroll_factor = SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
2697
2698   /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
2699      unrolling factor.  */
2700   orig_vec_stmts_num = group_size *
2701                 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance) / nunits;
2702   if (orig_vec_stmts_num == 1)
2703     only_one_vec = true;
2704
2705   /* Number of copies is determined by the final vectorization factor
2706      relatively to SLP_NODE_INSTANCE unrolling factor.  */
2707   ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
2708
2709   /* Generate permutation masks for every NODE. Number of masks for each NODE
2710      is equal to GROUP_SIZE.
2711      E.g., we have a group of three nodes with three loads from the same
2712      location in each node, and the vector size is 4. I.e., we have a
2713      a0b0c0a1b1c1... sequence and we need to create the following vectors:
2714      for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
2715      for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
2716      ...
2717
2718      The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9}.
2719      The last mask is illegal since we assume two operands for permute
2720      operation, and the mask element values can't be outside that range.
2721      Hence, the last mask must be converted into {2,5,5,5}.
2722      For the first two permutations we need the first and the second input
2723      vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
2724      we need the second and the third vectors: {b1,c1,a2,b2} and
2725      {c2,a3,b3,c3}.  */
2726
2727   FOR_EACH_VEC_ELT  (slp_tree, SLP_INSTANCE_LOADS (slp_node_instance), i, node)
2728     {
2729       scalar_index = 0;
2730       index = 0;
2731       vect_stmts_counter = 0;
2732       vec_index = 0;
2733       first_vec_index = vec_index++;
2734       if (only_one_vec)
2735         second_vec_index = first_vec_index;
2736       else
2737         second_vec_index =  vec_index++;
2738
2739       for (j = 0; j < unroll_factor; j++)
2740         {
2741           for (k = 0; k < group_size; k++)
2742             {
2743               first_mask_element = i + j * group_size;
2744               if (!vect_get_mask_element (stmt, first_mask_element, 0,
2745                                           nunits, only_one_vec, index,
2746                                           mask, &current_mask_element,
2747                                           &need_next_vector,
2748                                           &number_of_mask_fixes, &mask_fixed,
2749                                           &needs_first_vector))
2750                 return false;
2751               mask[index++] = current_mask_element;
2752
2753               if (index == nunits)
2754                 {
2755                   tree mask_vec = NULL;
2756
2757                   if (!can_vec_perm_p (mode, false, mask))
2758                     {
2759                       if (vect_print_dump_info (REPORT_DETAILS))
2760                         {
2761                           fprintf (vect_dump, "unsupported vect permute { ");
2762                           for (i = 0; i < nunits; ++i)
2763                             fprintf (vect_dump, "%d ", mask[i]);
2764                           fprintf (vect_dump, "}\n");
2765                         }
2766                       return false;
2767                     }
2768
2769                   while (--index >= 0)
2770                     {
2771                       tree t = build_int_cst (mask_element_type, mask[index]);
2772                       mask_vec = tree_cons (NULL, t, mask_vec);
2773                     }
2774                   mask_vec = build_vector (mask_type, mask_vec);
2775                   index = 0;
2776
2777                   if (!analyze_only)
2778                     {
2779                       if (need_next_vector)
2780                         {
2781                           first_vec_index = second_vec_index;
2782                           second_vec_index = vec_index;
2783                         }
2784
2785                       next_scalar_stmt = VEC_index (gimple,
2786                                 SLP_TREE_SCALAR_STMTS (node), scalar_index++);
2787
2788                       vect_create_mask_and_perm (stmt, next_scalar_stmt,
2789                                mask_vec, first_vec_index, second_vec_index,
2790                                gsi, node, vectype, dr_chain,
2791                                ncopies, vect_stmts_counter++);
2792                     }
2793                 }
2794             }
2795         }
2796     }
2797
2798   return true;
2799 }
2800
2801
2802
2803 /* Vectorize SLP instance tree in postorder.  */
2804
2805 static bool
2806 vect_schedule_slp_instance (slp_tree node, slp_instance instance,
2807                             unsigned int vectorization_factor)
2808 {
2809   gimple stmt;
2810   bool strided_store, is_store;
2811   gimple_stmt_iterator si;
2812   stmt_vec_info stmt_info;
2813   unsigned int vec_stmts_size, nunits, group_size;
2814   tree vectype;
2815   int i;
2816   slp_tree loads_node;
2817   slp_void_p child;
2818
2819   if (!node)
2820     return false;
2821
2822   FOR_EACH_VEC_ELT (slp_void_p, SLP_TREE_CHILDREN (node), i, child)
2823     vect_schedule_slp_instance ((slp_tree) child, instance,
2824                                 vectorization_factor);
2825
2826   stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
2827   stmt_info = vinfo_for_stmt (stmt);
2828
2829   /* VECTYPE is the type of the destination.  */
2830   vectype = STMT_VINFO_VECTYPE (stmt_info);
2831   nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (vectype);
2832   group_size = SLP_INSTANCE_GROUP_SIZE (instance);
2833
2834   /* For each SLP instance calculate number of vector stmts to be created
2835      for the scalar stmts in each node of the SLP tree.  Number of vector
2836      elements in one vector iteration is the number of scalar elements in
2837      one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
2838      size.  */
2839   vec_stmts_size = (vectorization_factor * group_size) / nunits;
2840
2841   /* In case of load permutation we have to allocate vectorized statements for
2842      all the nodes that participate in that permutation.  */
2843   if (SLP_INSTANCE_LOAD_PERMUTATION (instance))
2844     {
2845       FOR_EACH_VEC_ELT (slp_tree, SLP_INSTANCE_LOADS (instance), i, loads_node)
2846         {
2847           if (!SLP_TREE_VEC_STMTS (loads_node))
2848             {
2849               SLP_TREE_VEC_STMTS (loads_node) = VEC_alloc (gimple, heap,
2850                                                            vec_stmts_size);
2851               SLP_TREE_NUMBER_OF_VEC_STMTS (loads_node) = vec_stmts_size;
2852             }
2853         }
2854     }
2855
2856   if (!SLP_TREE_VEC_STMTS (node))
2857     {
2858       SLP_TREE_VEC_STMTS (node) = VEC_alloc (gimple, heap, vec_stmts_size);
2859       SLP_TREE_NUMBER_OF_VEC_STMTS (node) = vec_stmts_size;
2860     }
2861
2862   if (vect_print_dump_info (REPORT_DETAILS))
2863     {
2864       fprintf (vect_dump, "------>vectorizing SLP node starting from: ");
2865       print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2866     }
2867
2868   /* Loads should be inserted before the first load.  */
2869   if (SLP_INSTANCE_FIRST_LOAD_STMT (instance)
2870       && STMT_VINFO_STRIDED_ACCESS (stmt_info)
2871       && !REFERENCE_CLASS_P (gimple_get_lhs (stmt))
2872       && SLP_INSTANCE_LOAD_PERMUTATION (instance))
2873     si = gsi_for_stmt (SLP_INSTANCE_FIRST_LOAD_STMT (instance));
2874   else if (is_pattern_stmt_p (stmt_info))
2875     si = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
2876   else
2877     si = gsi_for_stmt (stmt);
2878
2879   /* Stores should be inserted just before the last store.  */
2880   if (STMT_VINFO_STRIDED_ACCESS (stmt_info)
2881       && REFERENCE_CLASS_P (gimple_get_lhs (stmt)))
2882     {
2883       gimple last_store = vect_find_last_store_in_slp_instance (instance);
2884       si = gsi_for_stmt (last_store);
2885     }
2886
2887   /* Mark the first element of the reduction chain as reduction to properly
2888      transform the node.  In the analysis phase only the last element of the
2889      chain is marked as reduction.  */
2890   if (GROUP_FIRST_ELEMENT (stmt_info) && !STMT_VINFO_STRIDED_ACCESS (stmt_info)
2891       && GROUP_FIRST_ELEMENT (stmt_info) == stmt)
2892     {
2893       STMT_VINFO_DEF_TYPE (stmt_info) = vect_reduction_def;
2894       STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
2895     }
2896
2897   is_store = vect_transform_stmt (stmt, &si, &strided_store, node, instance);
2898   return is_store;
2899 }
2900
2901
2902 /* Generate vector code for all SLP instances in the loop/basic block.  */
2903
2904 bool
2905 vect_schedule_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
2906 {
2907   VEC (slp_instance, heap) *slp_instances;
2908   slp_instance instance;
2909   unsigned int i, vf;
2910   bool is_store = false;
2911
2912   if (loop_vinfo)
2913     {
2914       slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2915       vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2916     }
2917   else
2918     {
2919       slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2920       vf = 1;
2921     }
2922
2923   FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
2924     {
2925       /* Schedule the tree of INSTANCE.  */
2926       is_store = vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
2927                                              instance, vf);
2928       if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS)
2929           || vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
2930         fprintf (vect_dump, "vectorizing stmts using SLP.");
2931     }
2932
2933   FOR_EACH_VEC_ELT (slp_instance, slp_instances, i, instance)
2934     {
2935       slp_tree root = SLP_INSTANCE_TREE (instance);
2936       gimple store;
2937       unsigned int j;
2938       gimple_stmt_iterator gsi;
2939
2940       for (j = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (root), j, store)
2941                   && j < SLP_INSTANCE_GROUP_SIZE (instance); j++)
2942         {
2943           if (!STMT_VINFO_DATA_REF (vinfo_for_stmt (store)))
2944             break;
2945
2946           /* Free the attached stmt_vec_info and remove the stmt.  */
2947           gsi = gsi_for_stmt (store);
2948           gsi_remove (&gsi, true);
2949           free_stmt_vec_info (store);
2950         }
2951     }
2952
2953   return is_store;
2954 }
2955
2956
2957 /* Vectorize the basic block.  */
2958
2959 void
2960 vect_slp_transform_bb (basic_block bb)
2961 {
2962   bb_vec_info bb_vinfo = vec_info_for_bb (bb);
2963   gimple_stmt_iterator si;
2964
2965   gcc_assert (bb_vinfo);
2966
2967   if (vect_print_dump_info (REPORT_DETAILS))
2968     fprintf (vect_dump, "SLPing BB\n");
2969
2970   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2971     {
2972       gimple stmt = gsi_stmt (si);
2973       stmt_vec_info stmt_info;
2974
2975       if (vect_print_dump_info (REPORT_DETAILS))
2976         {
2977           fprintf (vect_dump, "------>SLPing statement: ");
2978           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2979         }
2980
2981       stmt_info = vinfo_for_stmt (stmt);
2982       gcc_assert (stmt_info);
2983
2984       /* Schedule all the SLP instances when the first SLP stmt is reached.  */
2985       if (STMT_SLP_TYPE (stmt_info))
2986         {
2987           vect_schedule_slp (NULL, bb_vinfo);
2988           break;
2989         }
2990     }
2991
2992   mark_sym_for_renaming (gimple_vop (cfun));
2993   /* The memory tags and pointers in vectorized statements need to
2994      have their SSA forms updated.  FIXME, why can't this be delayed
2995      until all the loops have been transformed?  */
2996   update_ssa (TODO_update_ssa);
2997
2998   if (vect_print_dump_info (REPORT_DETAILS))
2999     fprintf (vect_dump, "BASIC BLOCK VECTORIZED\n");
3000
3001   destroy_bb_vec_info (bb_vinfo);
3002 }
3003