gcc/tree-vect-slp.c

   1 /* SLP - Basic Block Vectorization
   2    Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
   3    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 "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "cfgloop.h"
  35 #include "cfglayout.h"
  36 #include "expr.h"
  37 #include "recog.h"
  38 #include "optabs.h"
  39 #include "tree-vectorizer.h"
  40
  41 /* Extract the location of the basic block in the source code.
  42    Return the basic block location if succeed and NULL if not.  */
  43
  44 LOC
  45 find_bb_location (basic_block bb)
  46 {
  47   gimple stmt = NULL;
  48   gimple_stmt_iterator si;
  49
  50   if (!bb)
  51     return UNKNOWN_LOC;
  52
  53   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
  54     {
  55       stmt = gsi_stmt (si);
  56       if (gimple_location (stmt) != UNKNOWN_LOC)
  57         return gimple_location (stmt);
  58     }
  59
  60   return UNKNOWN_LOC;
  61 }
  62
  63
  64 /* Recursively free the memory allocated for the SLP tree rooted at NODE.  */
  65
  66 static void
  67 vect_free_slp_tree (slp_tree node)
  68 {
  69   if (!node)
  70     return;
  71
  72   if (SLP_TREE_LEFT (node))
  73     vect_free_slp_tree (SLP_TREE_LEFT (node));
  74
  75   if (SLP_TREE_RIGHT (node))
  76     vect_free_slp_tree (SLP_TREE_RIGHT (node));
  77
  78   VEC_free (gimple, heap, SLP_TREE_SCALAR_STMTS (node));
  79
  80   if (SLP_TREE_VEC_STMTS (node))
  81     VEC_free (gimple, heap, SLP_TREE_VEC_STMTS (node));
  82
  83   free (node);
  84 }
  85
  86
  87 /* Free the memory allocated for the SLP instance.  */
  88
  89 void
  90 vect_free_slp_instance (slp_instance instance)
  91 {
  92   vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
  93   VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (instance));
  94   VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
  95 }
  96
  97
  98 /* Get the defs for the rhs of STMT (collect them in DEF_STMTS0/1), check that
  99    they are of a legal type and that they match the defs of the first stmt of
 100    the SLP group (stored in FIRST_STMT_...).  */
 101
 102 static bool
 103 vect_get_and_check_slp_defs (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 104                              slp_tree slp_node, gimple stmt,
 105                              VEC (gimple, heap) **def_stmts0,
 106                              VEC (gimple, heap) **def_stmts1,
 107                              enum vect_def_type *first_stmt_dt0,
 108                              enum vect_def_type *first_stmt_dt1,
 109                              tree *first_stmt_def0_type,
 110                              tree *first_stmt_def1_type,
 111                              tree *first_stmt_const_oprnd,
 112                              int ncopies_for_cost,
 113                              bool *pattern0, bool *pattern1)
 114 {
 115   tree oprnd;
 116   unsigned int i, number_of_oprnds;
 117   tree def;
 118   gimple def_stmt;
 119   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
 120   stmt_vec_info stmt_info =
 121     vinfo_for_stmt (VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0));
 122   enum gimple_rhs_class rhs_class;
 123   struct loop *loop = NULL;
 124
 125   if (loop_vinfo)
 126     loop = LOOP_VINFO_LOOP (loop_vinfo);
 127
 128   rhs_class = get_gimple_rhs_class (gimple_assign_rhs_code (stmt));
 129   number_of_oprnds = gimple_num_ops (stmt) - 1; /* RHS only */
 130
 131   for (i = 0; i < number_of_oprnds; i++)
 132     {
 133       oprnd = gimple_op (stmt, i + 1);
 134
 135       if (!vect_is_simple_use (oprnd, loop_vinfo, bb_vinfo, &def_stmt, &def,
 136                                &dt[i])
 137           || (!def_stmt && dt[i] != vect_constant_def))
 138         {
 139           if (vect_print_dump_info (REPORT_SLP))
 140             {
 141               fprintf (vect_dump, "Build SLP failed: can't find def for ");
 142               print_generic_expr (vect_dump, oprnd, TDF_SLIM);
 143             }
 144
 145           return false;
 146         }
 147
 148       /* Check if DEF_STMT is a part of a pattern in LOOP and get the def stmt
 149          from the pattern. Check that all the stmts of the node are in the
 150          pattern.  */
 151       if (loop && def_stmt && gimple_bb (def_stmt)
 152           && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
 153           && vinfo_for_stmt (def_stmt)
 154           && STMT_VINFO_IN_PATTERN_P (vinfo_for_stmt (def_stmt)))
 155         {
 156           if (!*first_stmt_dt0)
 157             *pattern0 = true;
 158           else
 159             {
 160               if (i == 1 && !*first_stmt_dt1)
 161                 *pattern1 = true;
 162               else if ((i == 0 && !*pattern0) || (i == 1 && !*pattern1))
 163                 {
 164                   if (vect_print_dump_info (REPORT_DETAILS))
 165                     {
 166                       fprintf (vect_dump, "Build SLP failed: some of the stmts"
 167                                      " are in a pattern, and others are not ");
 168                       print_generic_expr (vect_dump, oprnd, TDF_SLIM);
 169                     }
 170
 171                   return false;
 172                 }
 173             }
 174
 175           def_stmt = STMT_VINFO_RELATED_STMT (vinfo_for_stmt (def_stmt));
 176           dt[i] = STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def_stmt));
 177
 178           if (*dt == vect_unknown_def_type)
 179             {
 180               if (vect_print_dump_info (REPORT_DETAILS))
 181                 fprintf (vect_dump, "Unsupported pattern.");
 182               return false;
 183             }
 184
 185           switch (gimple_code (def_stmt))
 186             {
 187               case GIMPLE_PHI:
 188                 def = gimple_phi_result (def_stmt);
 189                 break;
 190
 191               case GIMPLE_ASSIGN:
 192                 def = gimple_assign_lhs (def_stmt);
 193                 break;
 194
 195               default:
 196                 if (vect_print_dump_info (REPORT_DETAILS))
 197                   fprintf (vect_dump, "unsupported defining stmt: ");
 198                 return false;
 199             }
 200         }
 201
 202       if (!*first_stmt_dt0)
 203         {
 204           /* op0 of the first stmt of the group - store its info.  */
 205           *first_stmt_dt0 = dt[i];
 206           if (def)
 207             *first_stmt_def0_type = TREE_TYPE (def);
 208           else
 209             *first_stmt_const_oprnd = oprnd;
 210
 211           /* Analyze costs (for the first stmt of the group only).  */
 212           if (rhs_class != GIMPLE_SINGLE_RHS)
 213             /* Not memory operation (we don't call this functions for loads).  */
 214             vect_model_simple_cost (stmt_info, ncopies_for_cost, dt, slp_node);
 215           else
 216             /* Store.  */
 217             vect_model_store_cost (stmt_info, ncopies_for_cost, dt[0], slp_node);
 218         }
 219
 220       else
 221         {
 222           if (!*first_stmt_dt1 && i == 1)
 223             {
 224               /* op1 of the first stmt of the group - store its info.  */
 225               *first_stmt_dt1 = dt[i];
 226               if (def)
 227                 *first_stmt_def1_type = TREE_TYPE (def);
 228               else
 229                 {
 230                   /* We assume that the stmt contains only one constant
 231                      operand. We fail otherwise, to be on the safe side.  */
 232                   if (*first_stmt_const_oprnd)
 233                     {
 234                       if (vect_print_dump_info (REPORT_SLP))
 235                         fprintf (vect_dump, "Build SLP failed: two constant "
 236                                  "oprnds in stmt");
 237                       return false;
 238                     }
 239                   *first_stmt_const_oprnd = oprnd;
 240                 }
 241             }
 242           else
 243             {
 244               /* Not first stmt of the group, check that the def-stmt/s match
 245                  the def-stmt/s of the first stmt.  */
 246               if ((i == 0
 247                    && (*first_stmt_dt0 != dt[i]
 248                        || (*first_stmt_def0_type && def
 249                            && *first_stmt_def0_type != TREE_TYPE (def))))
 250                   || (i == 1
 251                       && (*first_stmt_dt1 != dt[i]
 252                           || (*first_stmt_def1_type && def
 253                               && *first_stmt_def1_type != TREE_TYPE (def))))
 254                   || (!def
 255                       && TREE_TYPE (*first_stmt_const_oprnd)
 256                       != TREE_TYPE (oprnd)))
 257                 {
 258                   if (vect_print_dump_info (REPORT_SLP))
 259                     fprintf (vect_dump, "Build SLP failed: different types ");
 260
 261                   return false;
 262                 }
 263             }
 264         }
 265
 266       /* Check the types of the definitions.  */
 267       switch (dt[i])
 268         {
 269         case vect_constant_def:
 270         case vect_external_def:
 271           break;
 272
 273         case vect_internal_def:
 274           if (i == 0)
 275             VEC_safe_push (gimple, heap, *def_stmts0, def_stmt);
 276           else
 277             VEC_safe_push (gimple, heap, *def_stmts1, def_stmt);
 278           break;
 279
 280         default:
 281           /* FORNOW: Not supported.  */
 282           if (vect_print_dump_info (REPORT_SLP))
 283             {
 284               fprintf (vect_dump, "Build SLP failed: illegal type of def ");
 285               print_generic_expr (vect_dump, def, TDF_SLIM);
 286             }
 287
 288           return false;
 289         }
 290     }
 291
 292   return true;
 293 }
 294
 295
 296 /* Recursively build an SLP tree starting from NODE.
 297    Fail (and return FALSE) if def-stmts are not isomorphic, require data
 298    permutation or are of unsupported types of operation. Otherwise, return
 299    TRUE.  */
 300
 301 static bool
 302 vect_build_slp_tree (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 303                      slp_tree *node, unsigned int group_size,
 304                      int *inside_cost, int *outside_cost,
 305                      int ncopies_for_cost, unsigned int *max_nunits,
 306                      VEC (int, heap) **load_permutation,
 307                      VEC (slp_tree, heap) **loads,
 308                      unsigned int vectorization_factor)
 309 {
 310   VEC (gimple, heap) *def_stmts0 = VEC_alloc (gimple, heap, group_size);
 311   VEC (gimple, heap) *def_stmts1 =  VEC_alloc (gimple, heap, group_size);
 312   unsigned int i;
 313   VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (*node);
 314   gimple stmt = VEC_index (gimple, stmts, 0);
 315   enum vect_def_type first_stmt_dt0 = vect_uninitialized_def;
 316   enum vect_def_type first_stmt_dt1 = vect_uninitialized_def;
 317   enum tree_code first_stmt_code = ERROR_MARK, rhs_code;
 318   tree first_stmt_def1_type = NULL_TREE, first_stmt_def0_type = NULL_TREE;
 319   tree lhs;
 320   bool stop_recursion = false, need_same_oprnds = false;
 321   tree vectype, scalar_type, first_op1 = NULL_TREE;
 322   unsigned int ncopies;
 323   optab optab;
 324   int icode;
 325   enum machine_mode optab_op2_mode;
 326   enum machine_mode vec_mode;
 327   tree first_stmt_const_oprnd = NULL_TREE;
 328   struct data_reference *first_dr;
 329   bool pattern0 = false, pattern1 = false;
 330   HOST_WIDE_INT dummy;
 331   bool permutation = false;
 332   unsigned int load_place;
 333   gimple first_load;
 334
 335   /* For every stmt in NODE find its def stmt/s.  */
 336   for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
 337     {
 338       if (vect_print_dump_info (REPORT_SLP))
 339         {
 340           fprintf (vect_dump, "Build SLP for ");
 341           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 342         }
 343
 344       lhs = gimple_get_lhs (stmt);
 345       if (lhs == NULL_TREE)
 346         {
 347           if (vect_print_dump_info (REPORT_SLP))
 348             {
 349               fprintf (vect_dump,
 350                        "Build SLP failed: not GIMPLE_ASSIGN nor GIMPLE_CALL");
 351               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 352             }
 353
 354           return false;
 355         }
 356
 357       scalar_type = vect_get_smallest_scalar_type (stmt, &dummy, &dummy);
 358       vectype = get_vectype_for_scalar_type (scalar_type);
 359       if (!vectype)
 360         {
 361           if (vect_print_dump_info (REPORT_SLP))
 362             {
 363               fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
 364               print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
 365             }
 366           return false;
 367         }
 368
 369       ncopies = vectorization_factor / TYPE_VECTOR_SUBPARTS (vectype);
 370       if (ncopies != 1)
 371         {
 372           if (vect_print_dump_info (REPORT_SLP))
 373             fprintf (vect_dump, "SLP with multiple types ");
 374
 375           /* FORNOW: multiple types are unsupported in BB SLP.  */
 376           if (bb_vinfo)
 377             return false;
 378         }
 379
 380       /* In case of multiple types we need to detect the smallest type.  */
 381       if (*max_nunits < TYPE_VECTOR_SUBPARTS (vectype))
 382         *max_nunits = TYPE_VECTOR_SUBPARTS (vectype);
 383
 384       if (is_gimple_call (stmt))
 385         rhs_code = CALL_EXPR;
 386       else
 387         rhs_code = gimple_assign_rhs_code (stmt);
 388
 389       /* Check the operation.  */
 390       if (i == 0)
 391         {
 392           first_stmt_code = rhs_code;
 393
 394           /* Shift arguments should be equal in all the packed stmts for a
 395              vector shift with scalar shift operand.  */
 396           if (rhs_code == LSHIFT_EXPR || rhs_code == RSHIFT_EXPR
 397               || rhs_code == LROTATE_EXPR
 398               || rhs_code == RROTATE_EXPR)
 399             {
 400               vec_mode = TYPE_MODE (vectype);
 401
 402               /* First see if we have a vector/vector shift.  */
 403               optab = optab_for_tree_code (rhs_code, vectype,
 404                                            optab_vector);
 405
 406               if (!optab
 407                   || (optab->handlers[(int) vec_mode].insn_code
 408                       == CODE_FOR_nothing))
 409                 {
 410                   /* No vector/vector shift, try for a vector/scalar shift.  */
 411                   optab = optab_for_tree_code (rhs_code, vectype,
 412                                                optab_scalar);
 413
 414                   if (!optab)
 415                     {
 416                       if (vect_print_dump_info (REPORT_SLP))
 417                         fprintf (vect_dump, "Build SLP failed: no optab.");
 418                       return false;
 419                     }
 420                   icode = (int) optab->handlers[(int) vec_mode].insn_code;
 421                   if (icode == CODE_FOR_nothing)
 422                     {
 423                       if (vect_print_dump_info (REPORT_SLP))
 424                         fprintf (vect_dump, "Build SLP failed: "
 425                                             "op not supported by target.");
 426                       return false;
 427                     }
 428                   optab_op2_mode = insn_data[icode].operand[2].mode;
 429                   if (!VECTOR_MODE_P (optab_op2_mode))
 430                     {
 431                       need_same_oprnds = true;
 432                       first_op1 = gimple_assign_rhs2 (stmt);
 433                     }
 434                 }
 435             }
 436         }
 437       else
 438         {
 439           if (first_stmt_code != rhs_code
 440               && (first_stmt_code != IMAGPART_EXPR
 441                   || rhs_code != REALPART_EXPR)
 442               && (first_stmt_code != REALPART_EXPR
 443                   || rhs_code != IMAGPART_EXPR))
 444             {
 445               if (vect_print_dump_info (REPORT_SLP))
 446                 {
 447                   fprintf (vect_dump,
 448                            "Build SLP failed: different operation in stmt ");
 449                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 450                 }
 451
 452               return false;
 453             }
 454
 455           if (need_same_oprnds
 456               && !operand_equal_p (first_op1, gimple_assign_rhs2 (stmt), 0))
 457             {
 458               if (vect_print_dump_info (REPORT_SLP))
 459                 {
 460                   fprintf (vect_dump,
 461                            "Build SLP failed: different shift arguments in ");
 462                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 463                 }
 464
 465               return false;
 466             }
 467         }
 468
 469       /* Strided store or load.  */
 470       if (STMT_VINFO_STRIDED_ACCESS (vinfo_for_stmt (stmt)))
 471         {
 472           if (REFERENCE_CLASS_P (lhs))
 473             {
 474               /* Store.  */
 475               if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node,
 476                                                 stmt, &def_stmts0, &def_stmts1,
 477                                                 &first_stmt_dt0,
 478                                                 &first_stmt_dt1,
 479                                                 &first_stmt_def0_type,
 480                                                 &first_stmt_def1_type,
 481                                                 &first_stmt_const_oprnd,
 482                                                 ncopies_for_cost,
 483                                                 &pattern0, &pattern1))
 484                 return false;
 485             }
 486             else
 487               {
 488                 /* Load.  */
 489                 /* FORNOW: Check that there is no gap between the loads.  */
 490                 if ((DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) == stmt
 491                      && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 0)
 492                     || (DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt)) != stmt
 493                         && DR_GROUP_GAP (vinfo_for_stmt (stmt)) != 1))
 494                   {
 495                     if (vect_print_dump_info (REPORT_SLP))
 496                       {
 497                         fprintf (vect_dump, "Build SLP failed: strided "
 498                                             "loads have gaps ");
 499                         print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 500                       }
 501
 502                     return false;
 503                   }
 504
 505                 /* Check that the size of interleaved loads group is not
 506                    greater than the SLP group size.  */
 507                 if (DR_GROUP_SIZE (vinfo_for_stmt (stmt))
 508                     > ncopies * group_size)
 509                   {
 510                     if (vect_print_dump_info (REPORT_SLP))
 511                       {
 512                         fprintf (vect_dump, "Build SLP failed: the number of "
 513                                             "interleaved loads is greater than"
 514                                             " the SLP group size ");
 515                         print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 516                       }
 517
 518                     return false;
 519                   }
 520
 521                 first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
 522
 523               if (first_load == stmt)
 524                 {
 525                   first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt));
 526                   if (vect_supportable_dr_alignment (first_dr)
 527                       == dr_unaligned_unsupported)
 528                     {
 529                       if (vect_print_dump_info (REPORT_SLP))
 530                         {
 531                           fprintf (vect_dump, "Build SLP failed: unsupported "
 532                                               "unaligned load ");
 533                           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 534                         }
 535
 536                       return false;
 537                     }
 538
 539                   /* Analyze costs (for the first stmt in the group).  */
 540                   vect_model_load_cost (vinfo_for_stmt (stmt),
 541                                         ncopies_for_cost, *node);
 542                 }
 543
 544               /* Store the place of this load in the interleaving chain. In
 545                  case that permutation is needed we later decide if a specific
 546                  permutation is supported.  */
 547               load_place = vect_get_place_in_interleaving_chain (stmt,
 548                                                                  first_load);
 549               if (load_place != i)
 550                 permutation = true;
 551
 552               VEC_safe_push (int, heap, *load_permutation, load_place);
 553
 554               /* We stop the tree when we reach a group of loads.  */
 555               stop_recursion = true;
 556              continue;
 557            }
 558         } /* Strided access.  */
 559       else
 560         {
 561           if (TREE_CODE_CLASS (rhs_code) == tcc_reference)
 562             {
 563               /* Not strided load. */
 564               if (vect_print_dump_info (REPORT_SLP))
 565                 {
 566                   fprintf (vect_dump, "Build SLP failed: not strided load ");
 567                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 568                 }
 569
 570               /* FORNOW: Not strided loads are not supported.  */
 571               return false;
 572             }
 573
 574           /* Not memory operation.  */
 575           if (TREE_CODE_CLASS (rhs_code) != tcc_binary
 576               && TREE_CODE_CLASS (rhs_code) != tcc_unary)
 577             {
 578               if (vect_print_dump_info (REPORT_SLP))
 579                 {
 580                   fprintf (vect_dump, "Build SLP failed: operation");
 581                   fprintf (vect_dump, " unsupported ");
 582                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 583                 }
 584
 585               return false;
 586             }
 587
 588           /* Find the def-stmts.  */
 589           if (!vect_get_and_check_slp_defs (loop_vinfo, bb_vinfo, *node, stmt,
 590                                             &def_stmts0, &def_stmts1,
 591                                             &first_stmt_dt0, &first_stmt_dt1,
 592                                             &first_stmt_def0_type,
 593                                             &first_stmt_def1_type,
 594                                             &first_stmt_const_oprnd,
 595                                             ncopies_for_cost,
 596                                             &pattern0, &pattern1))
 597             return false;
 598         }
 599     }
 600
 601   /* Add the costs of the node to the overall instance costs.  */
 602   *inside_cost += SLP_TREE_INSIDE_OF_LOOP_COST (*node);
 603   *outside_cost += SLP_TREE_OUTSIDE_OF_LOOP_COST (*node);
 604
 605   /* Strided loads were reached - stop the recursion.  */
 606   if (stop_recursion)
 607     {
 608       if (permutation)
 609         {
 610           VEC_safe_push (slp_tree, heap, *loads, *node);
 611           *inside_cost += TARG_VEC_PERMUTE_COST * group_size;
 612         }
 613
 614       return true;
 615     }
 616
 617   /* Create SLP_TREE nodes for the definition node/s.  */
 618   if (first_stmt_dt0 == vect_internal_def)
 619     {
 620       slp_tree left_node = XNEW (struct _slp_tree);
 621       SLP_TREE_SCALAR_STMTS (left_node) = def_stmts0;
 622       SLP_TREE_VEC_STMTS (left_node) = NULL;
 623       SLP_TREE_LEFT (left_node) = NULL;
 624       SLP_TREE_RIGHT (left_node) = NULL;
 625       SLP_TREE_OUTSIDE_OF_LOOP_COST (left_node) = 0;
 626       SLP_TREE_INSIDE_OF_LOOP_COST (left_node) = 0;
 627       if (!vect_build_slp_tree (loop_vinfo, bb_vinfo, &left_node, group_size,
 628                                 inside_cost, outside_cost, ncopies_for_cost,
 629                                 max_nunits, load_permutation, loads,
 630                                 vectorization_factor))
 631         return false;
 632
 633       SLP_TREE_LEFT (*node) = left_node;
 634     }
 635
 636   if (first_stmt_dt1 == vect_internal_def)
 637     {
 638       slp_tree right_node = XNEW (struct _slp_tree);
 639       SLP_TREE_SCALAR_STMTS (right_node) = def_stmts1;
 640       SLP_TREE_VEC_STMTS (right_node) = NULL;
 641       SLP_TREE_LEFT (right_node) = NULL;
 642       SLP_TREE_RIGHT (right_node) = NULL;
 643       SLP_TREE_OUTSIDE_OF_LOOP_COST (right_node) = 0;
 644       SLP_TREE_INSIDE_OF_LOOP_COST (right_node) = 0;
 645       if (!vect_build_slp_tree (loop_vinfo, bb_vinfo, &right_node, group_size,
 646                                 inside_cost, outside_cost, ncopies_for_cost,
 647                                 max_nunits, load_permutation, loads,
 648                                 vectorization_factor))
 649         return false;
 650
 651       SLP_TREE_RIGHT (*node) = right_node;
 652     }
 653
 654   return true;
 655 }
 656
 657
 658 static void
 659 vect_print_slp_tree (slp_tree node)
 660 {
 661   int i;
 662   gimple stmt;
 663
 664   if (!node)
 665     return;
 666
 667   fprintf (vect_dump, "node ");
 668   for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
 669     {
 670       fprintf (vect_dump, "\n\tstmt %d ", i);
 671       print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 672     }
 673   fprintf (vect_dump, "\n");
 674
 675   vect_print_slp_tree (SLP_TREE_LEFT (node));
 676   vect_print_slp_tree (SLP_TREE_RIGHT (node));
 677 }
 678
 679
 680 /* Mark the tree rooted at NODE with MARK (PURE_SLP or HYBRID).
 681    If MARK is HYBRID, it refers to a specific stmt in NODE (the stmt at index
 682    J). Otherwise, MARK is PURE_SLP and J is -1, which indicates that all the
 683    stmts in NODE are to be marked.  */
 684
 685 static void
 686 vect_mark_slp_stmts (slp_tree node, enum slp_vect_type mark, int j)
 687 {
 688   int i;
 689   gimple stmt;
 690
 691   if (!node)
 692     return;
 693
 694   for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
 695     if (j < 0 || i == j)
 696       STMT_SLP_TYPE (vinfo_for_stmt (stmt)) = mark;
 697
 698   vect_mark_slp_stmts (SLP_TREE_LEFT (node), mark, j);
 699   vect_mark_slp_stmts (SLP_TREE_RIGHT (node), mark, j);
 700 }
 701
 702
 703 /* Mark the statements of the tree rooted at NODE as relevant (vect_used).  */
 704
 705 static void
 706 vect_mark_slp_stmts_relevant (slp_tree node)
 707 {
 708   int i;
 709   gimple stmt;
 710   stmt_vec_info stmt_info;
 711
 712   if (!node)
 713     return;
 714
 715   for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
 716     {
 717       stmt_info = vinfo_for_stmt (stmt);
 718       gcc_assert (!STMT_VINFO_RELEVANT (stmt_info)
 719                   || STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_scope);
 720       STMT_VINFO_RELEVANT (stmt_info) = vect_used_in_scope;
 721     }
 722
 723   vect_mark_slp_stmts_relevant (SLP_TREE_LEFT (node));
 724   vect_mark_slp_stmts_relevant (SLP_TREE_RIGHT (node));
 725 }
 726
 727
 728 /* Check if the permutation required by the SLP INSTANCE is supported.
 729    Reorganize the SLP nodes stored in SLP_INSTANCE_LOADS if needed.  */
 730
 731 static bool
 732 vect_supported_slp_permutation_p (slp_instance instance)
 733 {
 734   slp_tree node = VEC_index (slp_tree, SLP_INSTANCE_LOADS (instance), 0);
 735   gimple stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
 736   gimple first_load = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt));
 737   VEC (slp_tree, heap) *sorted_loads = NULL;
 738   int index;
 739   slp_tree *tmp_loads = NULL;
 740   int group_size = SLP_INSTANCE_GROUP_SIZE (instance), i, j;
 741   slp_tree load;
 742
 743   /* FORNOW: The only supported loads permutation is loads from the same
 744      location in all the loads in the node, when the data-refs in
 745      nodes of LOADS constitute an interleaving chain.
 746      Sort the nodes according to the order of accesses in the chain.  */
 747   tmp_loads = (slp_tree *) xmalloc (sizeof (slp_tree) * group_size);
 748   for (i = 0, j = 0;
 749        VEC_iterate (int, SLP_INSTANCE_LOAD_PERMUTATION (instance), i, index)
 750        && VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), j, load);
 751        i += group_size, j++)
 752     {
 753       gimple scalar_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (load), 0);
 754       /* Check that the loads are all in the same interleaving chain.  */
 755       if (DR_GROUP_FIRST_DR (vinfo_for_stmt (scalar_stmt)) != first_load)
 756         {
 757           if (vect_print_dump_info (REPORT_DETAILS))
 758             {
 759               fprintf (vect_dump, "Build SLP failed: unsupported data "
 760                                    "permutation ");
 761               print_gimple_stmt (vect_dump, scalar_stmt, 0, TDF_SLIM);
 762             }
 763
 764           free (tmp_loads);
 765           return false;
 766         }
 767
 768       tmp_loads[index] = load;
 769     }
 770
 771   sorted_loads = VEC_alloc (slp_tree, heap, group_size);
 772   for (i = 0; i < group_size; i++)
 773      VEC_safe_push (slp_tree, heap, sorted_loads, tmp_loads[i]);
 774
 775   VEC_free (slp_tree, heap, SLP_INSTANCE_LOADS (instance));
 776   SLP_INSTANCE_LOADS (instance) = sorted_loads;
 777   free (tmp_loads);
 778
 779   if (!vect_transform_slp_perm_load (stmt, NULL, NULL,
 780                                      SLP_INSTANCE_UNROLLING_FACTOR (instance),
 781                                      instance, true))
 782     return false;
 783
 784   return true;
 785 }
 786
 787
 788 /* Check if the required load permutation is supported.
 789    LOAD_PERMUTATION contains a list of indices of the loads.
 790    In SLP this permutation is relative to the order of strided stores that are
 791    the base of the SLP instance.  */
 792
 793 static bool
 794 vect_supported_load_permutation_p (slp_instance slp_instn, int group_size,
 795                                    VEC (int, heap) *load_permutation)
 796 {
 797   int i = 0, j, prev = -1, next, k;
 798   bool supported;
 799   sbitmap load_index;
 800
 801   /* FORNOW: permutations are only supported in SLP.  */
 802   if (!slp_instn)
 803     return false;
 804
 805   if (vect_print_dump_info (REPORT_SLP))
 806     {
 807       fprintf (vect_dump, "Load permutation ");
 808       for (i = 0; VEC_iterate (int, load_permutation, i, next); i++)
 809         fprintf (vect_dump, "%d ", next);
 810     }
 811
 812   /* FORNOW: the only supported permutation is 0..01..1.. of length equal to
 813      GROUP_SIZE and where each sequence of same drs is of GROUP_SIZE length as
 814      well.  */
 815   if (VEC_length (int, load_permutation)
 816       != (unsigned int) (group_size * group_size))
 817     return false;
 818
 819   supported = true;
 820   load_index = sbitmap_alloc (group_size);
 821   sbitmap_zero (load_index);
 822   for (j = 0; j < group_size; j++)
 823     {
 824       for (i = j * group_size, k = 0;
 825            VEC_iterate (int, load_permutation, i, next) && k < group_size;
 826            i++, k++)
 827        {
 828          if (i != j * group_size && next != prev)
 829           {
 830             supported = false;
 831             break;
 832           }
 833
 834          prev = next;
 835        }
 836
 837       if (TEST_BIT (load_index, prev))
 838         {
 839           supported = false;
 840           break;
 841         }
 842
 843       SET_BIT (load_index, prev);
 844     }
 845
 846   sbitmap_free (load_index);
 847
 848   if (supported && i == group_size * group_size
 849       && vect_supported_slp_permutation_p (slp_instn))
 850     return true;
 851
 852   return false;
 853 }
 854
 855
 856 /* Find the first load in the loop that belongs to INSTANCE.
 857    When loads are in several SLP nodes, there can be a case in which the first
 858    load does not appear in the first SLP node to be transformed, causing
 859    incorrect order of statements. Since we generate all the loads together,
 860    they must be inserted before the first load of the SLP instance and not
 861    before the first load of the first node of the instance.  */
 862 static gimple
 863 vect_find_first_load_in_slp_instance (slp_instance instance)
 864 {
 865   int i, j;
 866   slp_tree load_node;
 867   gimple first_load = NULL, load;
 868
 869   for (i = 0;
 870        VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, load_node);
 871        i++)
 872     for (j = 0;
 873          VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (load_node), j, load);
 874          j++)
 875       first_load = get_earlier_stmt (load, first_load);
 876
 877   return first_load;
 878 }
 879
 880
 881 /* Analyze an SLP instance starting from a group of strided stores. Call
 882    vect_build_slp_tree to build a tree of packed stmts if possible.
 883    Return FALSE if it's impossible to SLP any stmt in the loop.  */
 884
 885 static bool
 886 vect_analyze_slp_instance (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo,
 887                            gimple stmt)
 888 {
 889   slp_instance new_instance;
 890   slp_tree node = XNEW (struct _slp_tree);
 891   unsigned int group_size = DR_GROUP_SIZE (vinfo_for_stmt (stmt));
 892   unsigned int unrolling_factor = 1, nunits;
 893   tree vectype, scalar_type;
 894   gimple next;
 895   unsigned int vectorization_factor = 0;
 896   int inside_cost = 0, outside_cost = 0, ncopies_for_cost;
 897   unsigned int max_nunits = 0;
 898   VEC (int, heap) *load_permutation;
 899   VEC (slp_tree, heap) *loads;
 900
 901   scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (
 902                                              vinfo_for_stmt (stmt))));
 903   vectype = get_vectype_for_scalar_type (scalar_type);
 904   if (!vectype)
 905     {
 906       if (vect_print_dump_info (REPORT_SLP))
 907         {
 908           fprintf (vect_dump, "Build SLP failed: unsupported data-type ");
 909           print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
 910         }
 911       return false;
 912     }
 913
 914   nunits = TYPE_VECTOR_SUBPARTS (vectype);
 915   if (loop_vinfo)
 916     vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
 917   else
 918     /* No multitypes in BB SLP.  */
 919     vectorization_factor = nunits;
 920
 921   /* Calculate the unrolling factor.  */
 922   unrolling_factor = least_common_multiple (nunits, group_size) / group_size;
 923   if (unrolling_factor != 1 && !loop_vinfo)
 924     {
 925       if (vect_print_dump_info (REPORT_SLP))
 926         fprintf (vect_dump, "Build SLP failed: unrolling required in basic"
 927                             " block SLP");
 928
 929       return false;
 930     }
 931
 932   /* Create a node (a root of the SLP tree) for the packed strided stores.  */
 933   SLP_TREE_SCALAR_STMTS (node) = VEC_alloc (gimple, heap, group_size);
 934   next = stmt;
 935   /* Collect the stores and store them in SLP_TREE_SCALAR_STMTS.  */
 936   while (next)
 937     {
 938       VEC_safe_push (gimple, heap, SLP_TREE_SCALAR_STMTS (node), next);
 939       next = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
 940     }
 941
 942   SLP_TREE_VEC_STMTS (node) = NULL;
 943   SLP_TREE_NUMBER_OF_VEC_STMTS (node) = 0;
 944   SLP_TREE_LEFT (node) = NULL;
 945   SLP_TREE_RIGHT (node) = NULL;
 946   SLP_TREE_OUTSIDE_OF_LOOP_COST (node) = 0;
 947   SLP_TREE_INSIDE_OF_LOOP_COST (node) = 0;
 948
 949   /* Calculate the number of vector stmts to create based on the unrolling
 950      factor (number of vectors is 1 if NUNITS >= GROUP_SIZE, and is
 951      GROUP_SIZE / NUNITS otherwise.  */
 952   ncopies_for_cost = unrolling_factor * group_size / nunits;
 953
 954   load_permutation = VEC_alloc (int, heap, group_size * group_size);
 955   loads = VEC_alloc (slp_tree, heap, group_size);
 956
 957   /* Build the tree for the SLP instance.  */
 958   if (vect_build_slp_tree (loop_vinfo, bb_vinfo, &node, group_size,
 959                            &inside_cost, &outside_cost, ncopies_for_cost,
 960                            &max_nunits, &load_permutation, &loads,
 961                            vectorization_factor))
 962     {
 963       /* Create a new SLP instance.  */
 964       new_instance = XNEW (struct _slp_instance);
 965       SLP_INSTANCE_TREE (new_instance) = node;
 966       SLP_INSTANCE_GROUP_SIZE (new_instance) = group_size;
 967       /* Calculate the unrolling factor based on the smallest type in the
 968          loop.  */
 969       if (max_nunits > nunits)
 970         unrolling_factor = least_common_multiple (max_nunits, group_size)
 971                            / group_size;
 972
 973       SLP_INSTANCE_UNROLLING_FACTOR (new_instance) = unrolling_factor;
 974       SLP_INSTANCE_OUTSIDE_OF_LOOP_COST (new_instance) = outside_cost;
 975       SLP_INSTANCE_INSIDE_OF_LOOP_COST (new_instance) = inside_cost;
 976       SLP_INSTANCE_LOADS (new_instance) = loads;
 977       SLP_INSTANCE_FIRST_LOAD_STMT (new_instance) = NULL;
 978       SLP_INSTANCE_LOAD_PERMUTATION (new_instance) = load_permutation;
 979       if (VEC_length (slp_tree, loads))
 980         {
 981           if (!vect_supported_load_permutation_p (new_instance, group_size,
 982                                                   load_permutation))
 983             {
 984               if (vect_print_dump_info (REPORT_SLP))
 985                 {
 986                   fprintf (vect_dump, "Build SLP failed: unsupported load "
 987                                       "permutation ");
 988                   print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 989                 }
 990
 991               vect_free_slp_instance (new_instance);
 992               return false;
 993             }
 994
 995           SLP_INSTANCE_FIRST_LOAD_STMT (new_instance)
 996              = vect_find_first_load_in_slp_instance (new_instance);
 997         }
 998       else
 999         VEC_free (int, heap, SLP_INSTANCE_LOAD_PERMUTATION (new_instance));
1000
1001       if (loop_vinfo)
1002         VEC_safe_push (slp_instance, heap,
1003                        LOOP_VINFO_SLP_INSTANCES (loop_vinfo),
1004                        new_instance);
1005       else
1006         VEC_safe_push (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo),
1007                        new_instance);
1008
1009       if (vect_print_dump_info (REPORT_SLP))
1010         vect_print_slp_tree (node);
1011
1012       return true;
1013     }
1014
1015   /* Failed to SLP.  */
1016   /* Free the allocated memory.  */
1017   vect_free_slp_tree (node);
1018   VEC_free (int, heap, load_permutation);
1019   VEC_free (slp_tree, heap, loads);
1020
1021   return false;
1022 }
1023
1024
1025 /* Check if there are stmts in the loop can be vectorized using SLP. Build SLP
1026    trees of packed scalar stmts if SLP is possible.  */
1027
1028 bool
1029 vect_analyze_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
1030 {
1031   unsigned int i;
1032   VEC (gimple, heap) *strided_stores;
1033   gimple store;
1034   bool ok = false;
1035
1036   if (vect_print_dump_info (REPORT_SLP))
1037     fprintf (vect_dump, "=== vect_analyze_slp ===");
1038
1039   if (loop_vinfo)
1040     strided_stores = LOOP_VINFO_STRIDED_STORES (loop_vinfo);
1041   else
1042     strided_stores = BB_VINFO_STRIDED_STORES (bb_vinfo);
1043
1044   for (i = 0; VEC_iterate (gimple, strided_stores, i, store); i++)
1045     if (vect_analyze_slp_instance (loop_vinfo, bb_vinfo, store))
1046       ok = true;
1047
1048   if (bb_vinfo && !ok)
1049     {
1050       if (vect_print_dump_info (REPORT_SLP))
1051         fprintf (vect_dump, "Failed to SLP the basic block.");
1052
1053       return false;
1054     }
1055
1056   return true;
1057 }
1058
1059
1060 /* For each possible SLP instance decide whether to SLP it and calculate overall
1061    unrolling factor needed to SLP the loop.  */
1062
1063 void
1064 vect_make_slp_decision (loop_vec_info loop_vinfo)
1065 {
1066   unsigned int i, unrolling_factor = 1;
1067   VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1068   slp_instance instance;
1069   int decided_to_slp = 0;
1070
1071   if (vect_print_dump_info (REPORT_SLP))
1072     fprintf (vect_dump, "=== vect_make_slp_decision ===");
1073
1074   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1075     {
1076       /* FORNOW: SLP if you can.  */
1077       if (unrolling_factor < SLP_INSTANCE_UNROLLING_FACTOR (instance))
1078         unrolling_factor = SLP_INSTANCE_UNROLLING_FACTOR (instance);
1079
1080       /* Mark all the stmts that belong to INSTANCE as PURE_SLP stmts. Later we
1081          call vect_detect_hybrid_slp () to find stmts that need hybrid SLP and
1082          loop-based vectorization. Such stmts will be marked as HYBRID.  */
1083       vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
1084       decided_to_slp++;
1085     }
1086
1087   LOOP_VINFO_SLP_UNROLLING_FACTOR (loop_vinfo) = unrolling_factor;
1088
1089   if (decided_to_slp && vect_print_dump_info (REPORT_SLP))
1090     fprintf (vect_dump, "Decided to SLP %d instances. Unrolling factor %d",
1091              decided_to_slp, unrolling_factor);
1092 }
1093
1094
1095 /* Find stmts that must be both vectorized and SLPed (since they feed stmts that
1096    can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID.  */
1097
1098 static void
1099 vect_detect_hybrid_slp_stmts (slp_tree node)
1100 {
1101   int i;
1102   gimple stmt;
1103   imm_use_iterator imm_iter;
1104   gimple use_stmt;
1105   stmt_vec_info stmt_vinfo;
1106
1107   if (!node)
1108     return;
1109
1110   for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
1111     if (PURE_SLP_STMT (vinfo_for_stmt (stmt))
1112         && TREE_CODE (gimple_op (stmt, 0)) == SSA_NAME)
1113       FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, gimple_op (stmt, 0))
1114         if ((stmt_vinfo = vinfo_for_stmt (use_stmt))
1115             && !STMT_SLP_TYPE (stmt_vinfo)
1116             && (STMT_VINFO_RELEVANT (stmt_vinfo)
1117                 || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (stmt_vinfo))))
1118           vect_mark_slp_stmts (node, hybrid, i);
1119
1120   vect_detect_hybrid_slp_stmts (SLP_TREE_LEFT (node));
1121   vect_detect_hybrid_slp_stmts (SLP_TREE_RIGHT (node));
1122 }
1123
1124
1125 /* Find stmts that must be both vectorized and SLPed.  */
1126
1127 void
1128 vect_detect_hybrid_slp (loop_vec_info loop_vinfo)
1129 {
1130   unsigned int i;
1131   VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1132   slp_instance instance;
1133
1134   if (vect_print_dump_info (REPORT_SLP))
1135     fprintf (vect_dump, "=== vect_detect_hybrid_slp ===");
1136
1137   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1138     vect_detect_hybrid_slp_stmts (SLP_INSTANCE_TREE (instance));
1139 }
1140
1141
1142 /* Create and initialize a new bb_vec_info struct for BB, as well as
1143    stmt_vec_info structs for all the stmts in it.  */
1144
1145 static bb_vec_info
1146 new_bb_vec_info (basic_block bb)
1147 {
1148   bb_vec_info res = NULL;
1149   gimple_stmt_iterator gsi;
1150
1151   res = (bb_vec_info) xcalloc (1, sizeof (struct _bb_vec_info));
1152   BB_VINFO_BB (res) = bb;
1153
1154   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1155     {
1156       gimple stmt = gsi_stmt (gsi);
1157       gimple_set_uid (stmt, 0);
1158       set_vinfo_for_stmt (stmt, new_stmt_vec_info (stmt, NULL, res));
1159     }
1160
1161   BB_VINFO_STRIDED_STORES (res) = VEC_alloc (gimple, heap, 10);
1162   BB_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 2);
1163
1164   bb->aux = res;
1165   return res;
1166 }
1167
1168
1169 /* Free BB_VINFO struct, as well as all the stmt_vec_info structs of all the
1170    stmts in the basic block.  */
1171
1172 static void
1173 destroy_bb_vec_info (bb_vec_info bb_vinfo)
1174 {
1175   basic_block bb;
1176   gimple_stmt_iterator si;
1177
1178   if (!bb_vinfo)
1179     return;
1180
1181   bb = BB_VINFO_BB (bb_vinfo);
1182
1183   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1184     {
1185       gimple stmt = gsi_stmt (si);
1186       stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1187
1188       if (stmt_info)
1189         /* Free stmt_vec_info.  */
1190         free_stmt_vec_info (stmt);
1191     }
1192
1193   VEC_free (gimple, heap, BB_VINFO_STRIDED_STORES (bb_vinfo));
1194   VEC_free (slp_instance, heap, BB_VINFO_SLP_INSTANCES (bb_vinfo));
1195   free (bb_vinfo);
1196   bb->aux = NULL;
1197 }
1198
1199
1200 /* Analyze statements contained in SLP tree node after recursively analyzing
1201    the subtree. Return TRUE if the operations are supported.  */
1202
1203 static bool
1204 vect_slp_analyze_node_operations (bb_vec_info bb_vinfo, slp_tree node)
1205 {
1206   bool dummy;
1207   int i;
1208   gimple stmt;
1209
1210   if (!node)
1211     return true;
1212
1213   if (!vect_slp_analyze_node_operations (bb_vinfo, SLP_TREE_LEFT (node))
1214       || !vect_slp_analyze_node_operations (bb_vinfo, SLP_TREE_RIGHT (node)))
1215     return false;
1216
1217   for (i = 0; VEC_iterate (gimple, SLP_TREE_SCALAR_STMTS (node), i, stmt); i++)
1218     {
1219       stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1220       gcc_assert (stmt_info);
1221       gcc_assert (PURE_SLP_STMT (stmt_info));
1222
1223       if (!vect_analyze_stmt (stmt, &dummy, node))
1224         return false;
1225     }
1226
1227   return true;
1228 }
1229
1230
1231 /* Analyze statements in SLP instances of the basic block. Return TRUE if the
1232    operations are supported. */
1233
1234 static bool
1235 vect_slp_analyze_operations (bb_vec_info bb_vinfo)
1236 {
1237   VEC (slp_instance, heap) *slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
1238   slp_instance instance;
1239   int i;
1240
1241   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); )
1242     {
1243       if (!vect_slp_analyze_node_operations (bb_vinfo,
1244                                              SLP_INSTANCE_TREE (instance)))
1245         {
1246           vect_free_slp_instance (instance);
1247           VEC_ordered_remove (slp_instance, slp_instances, i);
1248         }
1249       else
1250         i++;
1251     }
1252
1253   if (!VEC_length (slp_instance, slp_instances))
1254     return false;
1255
1256   return true;
1257 }
1258
1259
1260 /* Cheick if the basic block can be vectorized.  */
1261
1262 bb_vec_info
1263 vect_slp_analyze_bb (basic_block bb)
1264 {
1265   bb_vec_info bb_vinfo;
1266   VEC (ddr_p, heap) *ddrs;
1267   VEC (slp_instance, heap) *slp_instances;
1268   slp_instance instance;
1269   int i, insns = 0;
1270   gimple_stmt_iterator gsi;
1271
1272   if (vect_print_dump_info (REPORT_DETAILS))
1273     fprintf (vect_dump, "===vect_slp_analyze_bb===\n");
1274
1275   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1276     {
1277       gimple stmt = gsi_stmt (gsi);
1278       if (!is_gimple_debug (stmt)
1279           && !gimple_nop_p (stmt)
1280           && gimple_code (stmt) != GIMPLE_LABEL)
1281         insns++;
1282     }
1283
1284   if (insns > PARAM_VALUE (PARAM_SLP_MAX_INSNS_IN_BB))
1285     {
1286       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1287         fprintf (vect_dump, "not vectorized: too many instructions in basic "
1288                             "block.\n");
1289
1290       return NULL;
1291     }
1292
1293   bb_vinfo = new_bb_vec_info (bb);
1294   if (!bb_vinfo)
1295     return NULL;
1296
1297   if (!vect_analyze_data_refs (NULL, bb_vinfo))
1298     {
1299       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1300         fprintf (vect_dump, "not vectorized: unhandled data-ref in basic "
1301                             "block.\n");
1302
1303       destroy_bb_vec_info (bb_vinfo);
1304       return NULL;
1305     }
1306
1307   ddrs = BB_VINFO_DDRS (bb_vinfo);
1308   if (!VEC_length (ddr_p, ddrs))
1309     {
1310       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1311         fprintf (vect_dump, "not vectorized: not enough data-refs in basic "
1312                             "block.\n");
1313
1314       destroy_bb_vec_info (bb_vinfo);
1315       return NULL;
1316     }
1317
1318   if (!vect_analyze_data_refs_alignment (NULL, bb_vinfo))
1319     {
1320       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1321         fprintf (vect_dump, "not vectorized: bad data alignment in basic "
1322                             "block.\n");
1323
1324       destroy_bb_vec_info (bb_vinfo);
1325       return NULL;
1326     }
1327
1328    if (!vect_analyze_data_ref_dependences (NULL, bb_vinfo))
1329     {
1330      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1331        fprintf (vect_dump, "not vectorized: unhandled data dependence in basic"
1332                            " block.\n");
1333
1334       destroy_bb_vec_info (bb_vinfo);
1335       return NULL;
1336     }
1337
1338   if (!vect_analyze_data_ref_accesses (NULL, bb_vinfo))
1339     {
1340      if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1341        fprintf (vect_dump, "not vectorized: unhandled data access in basic "
1342                            "block.\n");
1343
1344       destroy_bb_vec_info (bb_vinfo);
1345       return NULL;
1346     }
1347
1348    if (!vect_verify_datarefs_alignment (NULL, bb_vinfo))
1349     {
1350       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1351         fprintf (vect_dump, "not vectorized: unsupported alignment in basic "
1352                             "block.\n");
1353
1354       destroy_bb_vec_info (bb_vinfo);
1355       return NULL;
1356     }
1357
1358   /* Check the SLP opportunities in the basic block, analyze and build SLP
1359      trees.  */
1360   if (!vect_analyze_slp (NULL, bb_vinfo))
1361     {
1362       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1363         fprintf (vect_dump, "not vectorized: failed to find SLP opportunities "
1364                             "in basic block.\n");
1365
1366       destroy_bb_vec_info (bb_vinfo);
1367       return NULL;
1368     }
1369
1370   slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
1371
1372   /* Mark all the statements that we want to vectorize as pure SLP and
1373      relevant.  */
1374   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1375     {
1376       vect_mark_slp_stmts (SLP_INSTANCE_TREE (instance), pure_slp, -1);
1377       vect_mark_slp_stmts_relevant (SLP_INSTANCE_TREE (instance));
1378     }
1379
1380   if (!vect_slp_analyze_operations (bb_vinfo))
1381     {
1382       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
1383         fprintf (vect_dump, "not vectorized: bad operation in basic block.\n");
1384
1385       destroy_bb_vec_info (bb_vinfo);
1386       return NULL;
1387     }
1388
1389   if (vect_print_dump_info (REPORT_DETAILS))
1390     fprintf (vect_dump, "Basic block will be vectorized using SLP\n");
1391
1392   return bb_vinfo;
1393 }
1394
1395
1396 /* SLP costs are calculated according to SLP instance unrolling factor (i.e.,
1397    the number of created vector stmts depends on the unrolling factor). However,
1398    the actual number of vector stmts for every SLP node depends on VF which is
1399    set later in vect_analyze_operations(). Hence, SLP costs should be updated.
1400    In this function we assume that the inside costs calculated in
1401    vect_model_xxx_cost are linear in ncopies.  */
1402
1403 void
1404 vect_update_slp_costs_according_to_vf (loop_vec_info loop_vinfo)
1405 {
1406   unsigned int i, vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1407   VEC (slp_instance, heap) *slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1408   slp_instance instance;
1409
1410   if (vect_print_dump_info (REPORT_SLP))
1411     fprintf (vect_dump, "=== vect_update_slp_costs_according_to_vf ===");
1412
1413   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
1414     /* We assume that costs are linear in ncopies.  */
1415     SLP_INSTANCE_INSIDE_OF_LOOP_COST (instance) *= vf
1416       / SLP_INSTANCE_UNROLLING_FACTOR (instance);
1417 }
1418
1419
1420 /* For constant and loop invariant defs of SLP_NODE this function returns
1421    (vector) defs (VEC_OPRNDS) that will be used in the vectorized stmts.
1422    OP_NUM determines if we gather defs for operand 0 or operand 1 of the scalar
1423    stmts. NUMBER_OF_VECTORS is the number of vector defs to create.  */
1424
1425 static void
1426 vect_get_constant_vectors (slp_tree slp_node, VEC(tree,heap) **vec_oprnds,
1427                            unsigned int op_num, unsigned int number_of_vectors)
1428 {
1429   VEC (gimple, heap) *stmts = SLP_TREE_SCALAR_STMTS (slp_node);
1430   gimple stmt = VEC_index (gimple, stmts, 0);
1431   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
1432   int nunits;
1433   tree vec_cst;
1434   tree t = NULL_TREE;
1435   int j, number_of_places_left_in_vector;
1436   tree vector_type;
1437   tree op, vop;
1438   int group_size = VEC_length (gimple, stmts);
1439   unsigned int vec_num, i;
1440   int number_of_copies = 1;
1441   VEC (tree, heap) *voprnds = VEC_alloc (tree, heap, number_of_vectors);
1442   bool constant_p, is_store;
1443
1444   if (STMT_VINFO_DATA_REF (stmt_vinfo))
1445     {
1446       is_store = true;
1447       op = gimple_assign_rhs1 (stmt);
1448     }
1449   else
1450     {
1451       is_store = false;
1452       op = gimple_op (stmt, op_num + 1);
1453     }
1454
1455   if (CONSTANT_CLASS_P (op))
1456     constant_p = true;
1457   else
1458     constant_p = false;
1459
1460   vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
1461   gcc_assert (vector_type);
1462
1463   nunits = TYPE_VECTOR_SUBPARTS (vector_type);
1464
1465   /* NUMBER_OF_COPIES is the number of times we need to use the same values in
1466      created vectors. It is greater than 1 if unrolling is performed.
1467
1468      For example, we have two scalar operands, s1 and s2 (e.g., group of
1469      strided accesses of size two), while NUNITS is four (i.e., four scalars
1470      of this type can be packed in a vector). The output vector will contain
1471      two copies of each scalar operand: {s1, s2, s1, s2}. (NUMBER_OF_COPIES
1472      will be 2).
1473
1474      If GROUP_SIZE > NUNITS, the scalars will be split into several vectors
1475      containing the operands.
1476
1477      For example, NUNITS is four as before, and the group size is 8
1478      (s1, s2, ..., s8). We will create two vectors {s1, s2, s3, s4} and
1479      {s5, s6, s7, s8}.  */
1480
1481   number_of_copies = least_common_multiple (nunits, group_size) / group_size;
1482
1483   number_of_places_left_in_vector = nunits;
1484   for (j = 0; j < number_of_copies; j++)
1485     {
1486       for (i = group_size - 1; VEC_iterate (gimple, stmts, i, stmt); i--)
1487         {
1488           if (is_store)
1489             op = gimple_assign_rhs1 (stmt);
1490           else
1491             op = gimple_op (stmt, op_num + 1);
1492
1493           /* Create 'vect_ = {op0,op1,...,opn}'.  */
1494           t = tree_cons (NULL_TREE, op, t);
1495
1496           number_of_places_left_in_vector--;
1497
1498           if (number_of_places_left_in_vector == 0)
1499             {
1500               number_of_places_left_in_vector = nunits;
1501
1502               if (constant_p)
1503                 vec_cst = build_vector (vector_type, t);
1504               else
1505                 vec_cst = build_constructor_from_list (vector_type, t);
1506               VEC_quick_push (tree, voprnds,
1507                               vect_init_vector (stmt, vec_cst, vector_type, NULL));
1508               t = NULL_TREE;
1509             }
1510         }
1511     }
1512
1513   /* Since the vectors are created in the reverse order, we should invert
1514      them.  */
1515   vec_num = VEC_length (tree, voprnds);
1516   for (j = vec_num - 1; j >= 0; j--)
1517     {
1518       vop = VEC_index (tree, voprnds, j);
1519       VEC_quick_push (tree, *vec_oprnds, vop);
1520     }
1521
1522   VEC_free (tree, heap, voprnds);
1523
1524   /* In case that VF is greater than the unrolling factor needed for the SLP
1525      group of stmts, NUMBER_OF_VECTORS to be created is greater than
1526      NUMBER_OF_SCALARS/NUNITS or NUNITS/NUMBER_OF_SCALARS, and hence we have
1527      to replicate the vectors.  */
1528   while (number_of_vectors > VEC_length (tree, *vec_oprnds))
1529     {
1530       for (i = 0; VEC_iterate (tree, *vec_oprnds, i, vop) && i < vec_num; i++)
1531         VEC_quick_push (tree, *vec_oprnds, vop);
1532     }
1533 }
1534
1535
1536 /* Get vectorized definitions from SLP_NODE that contains corresponding
1537    vectorized def-stmts.  */
1538
1539 static void
1540 vect_get_slp_vect_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds)
1541 {
1542   tree vec_oprnd;
1543   gimple vec_def_stmt;
1544   unsigned int i;
1545
1546   gcc_assert (SLP_TREE_VEC_STMTS (slp_node));
1547
1548   for (i = 0;
1549        VEC_iterate (gimple, SLP_TREE_VEC_STMTS (slp_node), i, vec_def_stmt);
1550        i++)
1551     {
1552       gcc_assert (vec_def_stmt);
1553       vec_oprnd = gimple_get_lhs (vec_def_stmt);
1554       VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
1555     }
1556 }
1557
1558
1559 /* Get vectorized definitions for SLP_NODE.
1560    If the scalar definitions are loop invariants or constants, collect them and
1561    call vect_get_constant_vectors() to create vector stmts.
1562    Otherwise, the def-stmts must be already vectorized and the vectorized stmts
1563    must be stored in the LEFT/RIGHT node of SLP_NODE, and we call
1564    vect_get_slp_vect_defs() to retrieve them.
1565    If VEC_OPRNDS1 is NULL, don't get vector defs for the second operand (from
1566    the right node. This is used when the second operand must remain scalar.  */
1567
1568 void
1569 vect_get_slp_defs (slp_tree slp_node, VEC (tree,heap) **vec_oprnds0,
1570                    VEC (tree,heap) **vec_oprnds1)
1571 {
1572   gimple first_stmt;
1573   enum tree_code code;
1574   int number_of_vects;
1575   HOST_WIDE_INT lhs_size_unit, rhs_size_unit;
1576
1577   first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
1578   /* The number of vector defs is determined by the number of vector statements
1579      in the node from which we get those statements.  */
1580   if (SLP_TREE_LEFT (slp_node))
1581     number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_LEFT (slp_node));
1582   else
1583     {
1584       number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
1585       /* Number of vector stmts was calculated according to LHS in
1586          vect_schedule_slp_instance(), fix it by replacing LHS with RHS, if
1587          necessary. See vect_get_smallest_scalar_type() for details.  */
1588       vect_get_smallest_scalar_type (first_stmt, &lhs_size_unit,
1589                                      &rhs_size_unit);
1590       if (rhs_size_unit != lhs_size_unit)
1591         {
1592           number_of_vects *= rhs_size_unit;
1593           number_of_vects /= lhs_size_unit;
1594         }
1595     }
1596
1597   /* Allocate memory for vectorized defs.  */
1598   *vec_oprnds0 = VEC_alloc (tree, heap, number_of_vects);
1599
1600   /* SLP_NODE corresponds either to a group of stores or to a group of
1601      unary/binary operations. We don't call this function for loads.  */
1602   if (SLP_TREE_LEFT (slp_node))
1603     /* The defs are already vectorized.  */
1604     vect_get_slp_vect_defs (SLP_TREE_LEFT (slp_node), vec_oprnds0);
1605   else
1606     /* Build vectors from scalar defs.  */
1607     vect_get_constant_vectors (slp_node, vec_oprnds0, 0, number_of_vects);
1608
1609   if (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt)))
1610     /* Since we don't call this function with loads, this is a group of
1611        stores.  */
1612     return;
1613
1614   code = gimple_assign_rhs_code (first_stmt);
1615   if (get_gimple_rhs_class (code) != GIMPLE_BINARY_RHS || !vec_oprnds1)
1616     return;
1617
1618   /* The number of vector defs is determined by the number of vector statements
1619      in the node from which we get those statements.  */
1620   if (SLP_TREE_RIGHT (slp_node))
1621     number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (SLP_TREE_RIGHT (slp_node));
1622   else
1623     number_of_vects = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
1624
1625   *vec_oprnds1 = VEC_alloc (tree, heap, number_of_vects);
1626
1627   if (SLP_TREE_RIGHT (slp_node))
1628     /* The defs are already vectorized.  */
1629     vect_get_slp_vect_defs (SLP_TREE_RIGHT (slp_node), vec_oprnds1);
1630   else
1631     /* Build vectors from scalar defs.  */
1632     vect_get_constant_vectors (slp_node, vec_oprnds1, 1, number_of_vects);
1633 }
1634
1635
1636 /* Create NCOPIES permutation statements using the mask MASK_BYTES (by
1637    building a vector of type MASK_TYPE from it) and two input vectors placed in
1638    DR_CHAIN at FIRST_VEC_INDX and SECOND_VEC_INDX for the first copy and
1639    shifting by STRIDE elements of DR_CHAIN for every copy.
1640    (STRIDE is the number of vectorized stmts for NODE divided by the number of
1641    copies).
1642    VECT_STMTS_COUNTER specifies the index in the vectorized stmts of NODE, where
1643    the created stmts must be inserted.  */
1644
1645 static inline void
1646 vect_create_mask_and_perm (gimple stmt, gimple next_scalar_stmt,
1647                            tree mask, int first_vec_indx, int second_vec_indx,
1648                            gimple_stmt_iterator *gsi, slp_tree node,
1649                            tree builtin_decl, tree vectype,
1650                            VEC(tree,heap) *dr_chain,
1651                            int ncopies, int vect_stmts_counter)
1652 {
1653   tree perm_dest;
1654   gimple perm_stmt = NULL;
1655   stmt_vec_info next_stmt_info;
1656   int i, stride;
1657   tree first_vec, second_vec, data_ref;
1658   VEC (tree, heap) *params = NULL;
1659
1660   stride = SLP_TREE_NUMBER_OF_VEC_STMTS (node) / ncopies;
1661
1662   /* Initialize the vect stmts of NODE to properly insert the generated
1663      stmts later.  */
1664   for (i = VEC_length (gimple, SLP_TREE_VEC_STMTS (node));
1665        i < (int) SLP_TREE_NUMBER_OF_VEC_STMTS (node); i++)
1666     VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (node), NULL);
1667
1668   perm_dest = vect_create_destination_var (gimple_assign_lhs (stmt), vectype);
1669   for (i = 0; i < ncopies; i++)
1670     {
1671       first_vec = VEC_index (tree, dr_chain, first_vec_indx);
1672       second_vec = VEC_index (tree, dr_chain, second_vec_indx);
1673
1674       /* Build argument list for the vectorized call.  */
1675       VEC_free (tree, heap, params);
1676       params = VEC_alloc (tree, heap, 3);
1677       VEC_quick_push (tree, params, first_vec);
1678       VEC_quick_push (tree, params, second_vec);
1679       VEC_quick_push (tree, params, mask);
1680
1681       /* Generate the permute statement.  */
1682       perm_stmt = gimple_build_call_vec (builtin_decl, params);
1683       data_ref = make_ssa_name (perm_dest, perm_stmt);
1684       gimple_call_set_lhs (perm_stmt, data_ref);
1685       vect_finish_stmt_generation (stmt, perm_stmt, gsi);
1686
1687       /* Store the vector statement in NODE.  */
1688       VEC_replace (gimple, SLP_TREE_VEC_STMTS (node),
1689                    stride * i + vect_stmts_counter, perm_stmt);
1690
1691       first_vec_indx += stride;
1692       second_vec_indx += stride;
1693     }
1694
1695   /* Mark the scalar stmt as vectorized.  */
1696   next_stmt_info = vinfo_for_stmt (next_scalar_stmt);
1697   STMT_VINFO_VEC_STMT (next_stmt_info) = perm_stmt;
1698 }
1699
1700
1701 /* Given FIRST_MASK_ELEMENT - the mask element in element representation,
1702    return in CURRENT_MASK_ELEMENT its equivalent in target specific
1703    representation. Check that the mask is valid and return FALSE if not.
1704    Return TRUE in NEED_NEXT_VECTOR if the permutation requires to move to
1705    the next vector, i.e., the current first vector is not needed.  */
1706
1707 static bool
1708 vect_get_mask_element (gimple stmt, int first_mask_element, int m,
1709                        int mask_nunits, bool only_one_vec, int index,
1710                        int *mask, int *current_mask_element,
1711                        bool *need_next_vector)
1712 {
1713   int i;
1714   static int number_of_mask_fixes = 1;
1715   static bool mask_fixed = false;
1716   static bool needs_first_vector = false;
1717
1718   /* Convert to target specific representation.  */
1719   *current_mask_element = first_mask_element + m;
1720   /* Adjust the value in case it's a mask for second and third vectors.  */
1721   *current_mask_element -= mask_nunits * (number_of_mask_fixes - 1);
1722
1723   if (*current_mask_element < mask_nunits)
1724     needs_first_vector = true;
1725
1726   /* We have only one input vector to permute but the mask accesses values in
1727      the next vector as well.  */
1728   if (only_one_vec && *current_mask_element >= mask_nunits)
1729     {
1730       if (vect_print_dump_info (REPORT_DETAILS))
1731         {
1732           fprintf (vect_dump, "permutation requires at least two vectors ");
1733           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1734         }
1735
1736       return false;
1737     }
1738
1739   /* The mask requires the next vector.  */
1740   if (*current_mask_element >= mask_nunits * 2)
1741     {
1742       if (needs_first_vector || mask_fixed)
1743         {
1744           /* We either need the first vector too or have already moved to the
1745              next vector. In both cases, this permutation needs three
1746              vectors.  */
1747           if (vect_print_dump_info (REPORT_DETAILS))
1748             {
1749               fprintf (vect_dump, "permutation requires at "
1750                                   "least three vectors ");
1751               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1752             }
1753
1754           return false;
1755         }
1756
1757       /* We move to the next vector, dropping the first one and working with
1758          the second and the third - we need to adjust the values of the mask
1759          accordingly.  */
1760       *current_mask_element -= mask_nunits * number_of_mask_fixes;
1761
1762       for (i = 0; i < index; i++)
1763         mask[i] -= mask_nunits * number_of_mask_fixes;
1764
1765       (number_of_mask_fixes)++;
1766       mask_fixed = true;
1767     }
1768
1769   *need_next_vector = mask_fixed;
1770
1771   /* This was the last element of this mask. Start a new one.  */
1772   if (index == mask_nunits - 1)
1773     {
1774       number_of_mask_fixes = 1;
1775       mask_fixed = false;
1776       needs_first_vector = false;
1777     }
1778
1779   return true;
1780 }
1781
1782
1783 /* Generate vector permute statements from a list of loads in DR_CHAIN.
1784    If ANALYZE_ONLY is TRUE, only check that it is possible to create valid
1785    permute statements for SLP_NODE_INSTANCE.  */
1786 bool
1787 vect_transform_slp_perm_load (gimple stmt, VEC (tree, heap) *dr_chain,
1788                               gimple_stmt_iterator *gsi, int vf,
1789                               slp_instance slp_node_instance, bool analyze_only)
1790 {
1791   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1792   tree mask_element_type = NULL_TREE, mask_type;
1793   int i, j, k, m, scale, mask_nunits, nunits, vec_index = 0, scalar_index;
1794   slp_tree node;
1795   tree vectype = STMT_VINFO_VECTYPE (stmt_info), builtin_decl;
1796   gimple next_scalar_stmt;
1797   int group_size = SLP_INSTANCE_GROUP_SIZE (slp_node_instance);
1798   int first_mask_element;
1799   int index, unroll_factor, *mask, current_mask_element, ncopies;
1800   bool only_one_vec = false, need_next_vector = false;
1801   int first_vec_index, second_vec_index, orig_vec_stmts_num, vect_stmts_counter;
1802
1803   if (!targetm.vectorize.builtin_vec_perm)
1804     {
1805       if (vect_print_dump_info (REPORT_DETAILS))
1806         {
1807           fprintf (vect_dump, "no builtin for vect permute for ");
1808           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1809         }
1810
1811        return false;
1812     }
1813
1814   builtin_decl = targetm.vectorize.builtin_vec_perm (vectype,
1815                                                      &mask_element_type);
1816   if (!builtin_decl || !mask_element_type)
1817     {
1818       if (vect_print_dump_info (REPORT_DETAILS))
1819         {
1820           fprintf (vect_dump, "no builtin for vect permute for ");
1821           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
1822         }
1823
1824        return false;
1825     }
1826
1827   mask_type = get_vectype_for_scalar_type (mask_element_type);
1828   mask_nunits = TYPE_VECTOR_SUBPARTS (mask_type);
1829   mask = (int *) xmalloc (sizeof (int) * mask_nunits);
1830   nunits = TYPE_VECTOR_SUBPARTS (vectype);
1831   scale = mask_nunits / nunits;
1832   unroll_factor = SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
1833
1834   /* The number of vector stmts to generate based only on SLP_NODE_INSTANCE
1835      unrolling factor.  */
1836   orig_vec_stmts_num = group_size *
1837                 SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance) / nunits;
1838   if (orig_vec_stmts_num == 1)
1839     only_one_vec = true;
1840
1841   /* Number of copies is determined by the final vectorization factor
1842      relatively to SLP_NODE_INSTANCE unrolling factor.  */
1843   ncopies = vf / SLP_INSTANCE_UNROLLING_FACTOR (slp_node_instance);
1844
1845   /* Generate permutation masks for every NODE. Number of masks for each NODE
1846      is equal to GROUP_SIZE.
1847      E.g., we have a group of three nodes with three loads from the same
1848      location in each node, and the vector size is 4. I.e., we have a
1849      a0b0c0a1b1c1... sequence and we need to create the following vectors:
1850      for a's: a0a0a0a1 a1a1a2a2 a2a3a3a3
1851      for b's: b0b0b0b1 b1b1b2b2 b2b3b3b3
1852      ...
1853
1854      The masks for a's should be: {0,0,0,3} {3,3,6,6} {6,9,9,9} (in target
1855      scpecific type, e.g., in bytes for Altivec.
1856      The last mask is illegal since we assume two operands for permute
1857      operation, and the mask element values can't be outside that range. Hence,
1858      the last mask must be converted into {2,5,5,5}.
1859      For the first two permutations we need the first and the second input
1860      vectors: {a0,b0,c0,a1} and {b1,c1,a2,b2}, and for the last permutation
1861      we need the second and the third vectors: {b1,c1,a2,b2} and
1862      {c2,a3,b3,c3}.  */
1863
1864   for (i = 0;
1865        VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (slp_node_instance),
1866                     i, node);
1867        i++)
1868     {
1869       scalar_index = 0;
1870       index = 0;
1871       vect_stmts_counter = 0;
1872       vec_index = 0;
1873       first_vec_index = vec_index++;
1874       if (only_one_vec)
1875         second_vec_index = first_vec_index;
1876       else
1877         second_vec_index =  vec_index++;
1878
1879       for (j = 0; j < unroll_factor; j++)
1880         {
1881           for (k = 0; k < group_size; k++)
1882             {
1883               first_mask_element = (i + j * group_size) * scale;
1884               for (m = 0; m < scale; m++)
1885                 {
1886                   if (!vect_get_mask_element (stmt, first_mask_element, m,
1887                                    mask_nunits, only_one_vec, index, mask,
1888                                    &current_mask_element, &need_next_vector))
1889                     return false;
1890
1891                   mask[index++] = current_mask_element;
1892                 }
1893
1894               if (index == mask_nunits)
1895                 {
1896                   tree mask_vec = NULL;
1897
1898                   while (--index >= 0)
1899                     {
1900                       tree t = build_int_cst (mask_element_type, mask[index]);
1901                       mask_vec = tree_cons (NULL, t, mask_vec);
1902                     }
1903                   mask_vec = build_vector (mask_type, mask_vec);
1904                   index = 0;
1905
1906                   if (!targetm.vectorize.builtin_vec_perm_ok (vectype,
1907                                                               mask_vec))
1908                     {
1909                       if (vect_print_dump_info (REPORT_DETAILS))
1910                         {
1911                           fprintf (vect_dump, "unsupported vect permute ");
1912                           print_generic_expr (vect_dump, mask_vec, 0);
1913                         }
1914                       free (mask);
1915                       return false;
1916                     }
1917
1918                   if (!analyze_only)
1919                     {
1920                       if (need_next_vector)
1921                         {
1922                           first_vec_index = second_vec_index;
1923                           second_vec_index = vec_index;
1924                         }
1925
1926                       next_scalar_stmt = VEC_index (gimple,
1927                                 SLP_TREE_SCALAR_STMTS (node), scalar_index++);
1928
1929                       vect_create_mask_and_perm (stmt, next_scalar_stmt,
1930                                mask_vec, first_vec_index, second_vec_index,
1931                                gsi, node, builtin_decl, vectype, dr_chain,
1932                                ncopies, vect_stmts_counter++);
1933                     }
1934                 }
1935             }
1936         }
1937     }
1938
1939   free (mask);
1940   return true;
1941 }
1942
1943
1944
1945 /* Vectorize SLP instance tree in postorder.  */
1946
1947 static bool
1948 vect_schedule_slp_instance (slp_tree node, slp_instance instance,
1949                             unsigned int vectorization_factor)
1950 {
1951   gimple stmt;
1952   bool strided_store, is_store;
1953   gimple_stmt_iterator si;
1954   stmt_vec_info stmt_info;
1955   unsigned int vec_stmts_size, nunits, group_size;
1956   tree vectype;
1957   int i;
1958   slp_tree loads_node;
1959
1960   if (!node)
1961     return false;
1962
1963   vect_schedule_slp_instance (SLP_TREE_LEFT (node), instance,
1964                               vectorization_factor);
1965   vect_schedule_slp_instance (SLP_TREE_RIGHT (node), instance,
1966                               vectorization_factor);
1967
1968   stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (node), 0);
1969   stmt_info = vinfo_for_stmt (stmt);
1970
1971   /* VECTYPE is the type of the destination.  */
1972   vectype = get_vectype_for_scalar_type (TREE_TYPE (gimple_assign_lhs (stmt)));
1973   nunits = (unsigned int) TYPE_VECTOR_SUBPARTS (vectype);
1974   group_size = SLP_INSTANCE_GROUP_SIZE (instance);
1975
1976   /* For each SLP instance calculate number of vector stmts to be created
1977      for the scalar stmts in each node of the SLP tree. Number of vector
1978      elements in one vector iteration is the number of scalar elements in
1979      one scalar iteration (GROUP_SIZE) multiplied by VF divided by vector
1980      size.  */
1981   vec_stmts_size = (vectorization_factor * group_size) / nunits;
1982
1983   /* In case of load permutation we have to allocate vectorized statements for
1984      all the nodes that participate in that permutation.  */
1985   if (SLP_INSTANCE_LOAD_PERMUTATION (instance))
1986     {
1987       for (i = 0;
1988            VEC_iterate (slp_tree, SLP_INSTANCE_LOADS (instance), i, loads_node);
1989            i++)
1990         {
1991           if (!SLP_TREE_VEC_STMTS (loads_node))
1992             {
1993               SLP_TREE_VEC_STMTS (loads_node) = VEC_alloc (gimple, heap,
1994                                                            vec_stmts_size);
1995               SLP_TREE_NUMBER_OF_VEC_STMTS (loads_node) = vec_stmts_size;
1996             }
1997         }
1998     }
1999
2000   if (!SLP_TREE_VEC_STMTS (node))
2001     {
2002       SLP_TREE_VEC_STMTS (node) = VEC_alloc (gimple, heap, vec_stmts_size);
2003       SLP_TREE_NUMBER_OF_VEC_STMTS (node) = vec_stmts_size;
2004     }
2005
2006   if (vect_print_dump_info (REPORT_DETAILS))
2007     {
2008       fprintf (vect_dump, "------>vectorizing SLP node starting from: ");
2009       print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2010     }
2011
2012   /* Loads should be inserted before the first load.  */
2013   if (SLP_INSTANCE_FIRST_LOAD_STMT (instance)
2014       && STMT_VINFO_STRIDED_ACCESS (stmt_info)
2015       && !REFERENCE_CLASS_P (gimple_get_lhs (stmt)))
2016     si = gsi_for_stmt (SLP_INSTANCE_FIRST_LOAD_STMT (instance));
2017   else
2018     si = gsi_for_stmt (stmt);
2019
2020   is_store = vect_transform_stmt (stmt, &si, &strided_store, node, instance);
2021   if (is_store)
2022     {
2023       if (DR_GROUP_FIRST_DR (stmt_info))
2024         /* If IS_STORE is TRUE, the vectorization of the
2025            interleaving chain was completed - free all the stores in
2026            the chain.  */
2027         vect_remove_stores (DR_GROUP_FIRST_DR (stmt_info));
2028       else
2029         /* FORNOW: SLP originates only from strided stores.  */
2030         gcc_unreachable ();
2031
2032       return true;
2033     }
2034
2035   /* FORNOW: SLP originates only from strided stores.  */
2036   return false;
2037 }
2038
2039
2040 bool
2041 vect_schedule_slp (loop_vec_info loop_vinfo, bb_vec_info bb_vinfo)
2042 {
2043   VEC (slp_instance, heap) *slp_instances;
2044   slp_instance instance;
2045   unsigned int i, vf;
2046   bool is_store = false;
2047
2048   if (loop_vinfo)
2049     {
2050       slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
2051       vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2052     }
2053   else
2054     {
2055       slp_instances = BB_VINFO_SLP_INSTANCES (bb_vinfo);
2056       vf = 1;
2057     }
2058
2059   for (i = 0; VEC_iterate (slp_instance, slp_instances, i, instance); i++)
2060     {
2061       /* Schedule the tree of INSTANCE.  */
2062       is_store = vect_schedule_slp_instance (SLP_INSTANCE_TREE (instance),
2063                                              instance, vf);
2064       if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS)
2065           || vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
2066         fprintf (vect_dump, "vectorizing stmts using SLP.");
2067     }
2068
2069   return is_store;
2070 }
2071
2072
2073 /* Vectorize the basic block.  */
2074
2075 void
2076 vect_slp_transform_bb (basic_block bb)
2077 {
2078   bb_vec_info bb_vinfo = vec_info_for_bb (bb);
2079   gimple_stmt_iterator si;
2080
2081   gcc_assert (bb_vinfo);
2082
2083   if (vect_print_dump_info (REPORT_DETAILS))
2084     fprintf (vect_dump, "SLPing BB\n");
2085
2086   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
2087     {
2088       gimple stmt = gsi_stmt (si);
2089       stmt_vec_info stmt_info;
2090
2091       if (vect_print_dump_info (REPORT_DETAILS))
2092         {
2093           fprintf (vect_dump, "------>SLPing statement: ");
2094           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
2095         }
2096
2097       stmt_info = vinfo_for_stmt (stmt);
2098       gcc_assert (stmt_info);
2099
2100       /* Schedule all the SLP instances when the first SLP stmt is reached.  */
2101       if (STMT_SLP_TYPE (stmt_info))
2102         {
2103           vect_schedule_slp (NULL, bb_vinfo);
2104           break;
2105         }
2106     }
2107
2108   mark_sym_for_renaming (gimple_vop (cfun));
2109   /* The memory tags and pointers in vectorized statements need to
2110      have their SSA forms updated.  FIXME, why can't this be delayed
2111      until all the loops have been transformed?  */
2112   update_ssa (TODO_update_ssa);
2113
2114   if (vect_print_dump_info (REPORT_DETAILS))
2115     fprintf (vect_dump, "BASIC BLOCK VECTORIZED\n");
2116
2117   destroy_bb_vec_info (bb_vinfo);
2118 }
2119