gcc/tree-vect-slp.c

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