gcc/tree-vectorizer.c

   1 /* Vectorizer
   2    Copyright (C) 2003-2018 Free Software Foundation, Inc.
   3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Loop and basic block vectorizer.
  22
  23   This file contains drivers for the three vectorizers:
  24   (1) loop vectorizer (inter-iteration parallelism),
  25   (2) loop-aware SLP (intra-iteration parallelism) (invoked by the loop
  26       vectorizer)
  27   (3) BB vectorizer (out-of-loops), aka SLP
  28
  29   The rest of the vectorizer's code is organized as follows:
  30   - tree-vect-loop.c - loop specific parts such as reductions, etc. These are
  31     used by drivers (1) and (2).
  32   - tree-vect-loop-manip.c - vectorizer's loop control-flow utilities, used by
  33     drivers (1) and (2).
  34   - tree-vect-slp.c - BB vectorization specific analysis and transformation,
  35     used by drivers (2) and (3).
  36   - tree-vect-stmts.c - statements analysis and transformation (used by all).
  37   - tree-vect-data-refs.c - vectorizer specific data-refs analysis and
  38     manipulations (used by all).
  39   - tree-vect-patterns.c - vectorizable code patterns detector (used by all)
  40
  41   Here's a poor attempt at illustrating that:
  42
  43      tree-vectorizer.c:
  44      loop_vect()  loop_aware_slp()  slp_vect()
  45           |        /           \          /
  46           |       /             \        /
  47           tree-vect-loop.c  tree-vect-slp.c
  48                 | \      \  /      /   |
  49                 |  \      \/      /    |
  50                 |   \     /\     /     |
  51                 |    \   /  \   /      |
  52          tree-vect-stmts.c  tree-vect-data-refs.c
  53                        \      /
  54                     tree-vect-patterns.c
  55 */
  56
  57 #include "config.h"
  58 #include "system.h"
  59 #include "coretypes.h"
  60 #include "backend.h"
  61 #include "tree.h"
  62 #include "gimple.h"
  63 #include "predict.h"
  64 #include "tree-pass.h"
  65 #include "ssa.h"
  66 #include "cgraph.h"
  67 #include "fold-const.h"
  68 #include "stor-layout.h"
  69 #include "gimple-iterator.h"
  70 #include "gimple-walk.h"
  71 #include "tree-ssa-loop-manip.h"
  72 #include "tree-ssa-loop-niter.h"
  73 #include "tree-cfg.h"
  74 #include "cfgloop.h"
  75 #include "tree-vectorizer.h"
  76 #include "tree-ssa-propagate.h"
  77 #include "dbgcnt.h"
  78 #include "tree-scalar-evolution.h"
  79 #include "stringpool.h"
  80 #include "attribs.h"
  81 #include "gimple-pretty-print.h"
  82
  83
  84 /* Loop or bb location, with hotness information.  */
  85 dump_user_location_t vect_location;
  86
  87 /* Dump a cost entry according to args to F.  */
  88
  89 void
  90 dump_stmt_cost (FILE *f, void *data, int count, enum vect_cost_for_stmt kind,
  91                 stmt_vec_info stmt_info, int misalign,
  92                 enum vect_cost_model_location where)
  93 {
  94   fprintf (f, "%p ", data);
  95   if (stmt_info)
  96     {
  97       print_gimple_expr (f, STMT_VINFO_STMT (stmt_info), 0, TDF_SLIM);
  98       fprintf (f, " ");
  99     }
 100   else
 101     fprintf (f, "<unknown> ");
 102   fprintf (f, "%d times ", count);
 103   const char *ks = "unknown";
 104   switch (kind)
 105     {
 106     case scalar_stmt:
 107       ks = "scalar_stmt";
 108       break;
 109     case scalar_load:
 110       ks = "scalar_load";
 111       break;
 112     case scalar_store:
 113       ks = "scalar_store";
 114       break;
 115     case vector_stmt:
 116       ks = "vector_stmt";
 117       break;
 118     case vector_load:
 119       ks = "vector_load";
 120       break;
 121     case vector_gather_load:
 122       ks = "vector_gather_load";
 123       break;
 124     case unaligned_load:
 125       ks = "unaligned_load";
 126       break;
 127     case unaligned_store:
 128       ks = "unaligned_store";
 129       break;
 130     case vector_store:
 131       ks = "unaligned_store";
 132       break;
 133     case vector_scatter_store:
 134       ks = "unaligned_store";
 135       break;
 136     case vec_to_scalar:
 137       ks = "unaligned_store";
 138       break;
 139     case scalar_to_vec:
 140       ks = "unaligned_store";
 141       break;
 142     case cond_branch_not_taken:
 143       ks = "unaligned_store";
 144       break;
 145     case cond_branch_taken:
 146       ks = "unaligned_store";
 147       break;
 148     case vec_perm:
 149       ks = "unaligned_store";
 150       break;
 151     case vec_promote_demote:
 152       ks = "unaligned_store";
 153       break;
 154     case vec_construct:
 155       ks = "unaligned_store";
 156       break;
 157     }
 158   fprintf (f, "%s ", ks);
 159   if (kind == unaligned_load || kind == unaligned_store)
 160     fprintf (f, "(misalign %d) ", misalign);
 161   const char *ws = "unknown";
 162   switch (where)
 163     {
 164     case vect_prologue:
 165       ws = "prologue";
 166       break;
 167     case vect_body:
 168       ws = "body";
 169       break;
 170     case vect_epilogue:
 171       ws = "epilogue";
 172       break;
 173     }
 174   fprintf (f, "in %s\n", ws);
 175 }
 176 \f
 177 /* For mapping simduid to vectorization factor.  */
 178
 179 struct simduid_to_vf : free_ptr_hash<simduid_to_vf>
 180 {
 181   unsigned int simduid;
 182   poly_uint64 vf;
 183
 184   /* hash_table support.  */
 185   static inline hashval_t hash (const simduid_to_vf *);
 186   static inline int equal (const simduid_to_vf *, const simduid_to_vf *);
 187 };
 188
 189 inline hashval_t
 190 simduid_to_vf::hash (const simduid_to_vf *p)
 191 {
 192   return p->simduid;
 193 }
 194
 195 inline int
 196 simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2)
 197 {
 198   return p1->simduid == p2->simduid;
 199 }
 200
 201 /* This hash maps the OMP simd array to the corresponding simduid used
 202    to index into it.  Like thus,
 203
 204         _7 = GOMP_SIMD_LANE (simduid.0)
 205         ...
 206         ...
 207         D.1737[_7] = stuff;
 208
 209
 210    This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
 211    simduid.0.  */
 212
 213 struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid>
 214 {
 215   tree decl;
 216   unsigned int simduid;
 217
 218   /* hash_table support.  */
 219   static inline hashval_t hash (const simd_array_to_simduid *);
 220   static inline int equal (const simd_array_to_simduid *,
 221                            const simd_array_to_simduid *);
 222 };
 223
 224 inline hashval_t
 225 simd_array_to_simduid::hash (const simd_array_to_simduid *p)
 226 {
 227   return DECL_UID (p->decl);
 228 }
 229
 230 inline int
 231 simd_array_to_simduid::equal (const simd_array_to_simduid *p1,
 232                               const simd_array_to_simduid *p2)
 233 {
 234   return p1->decl == p2->decl;
 235 }
 236
 237 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
 238    into their corresponding constants and remove
 239    IFN_GOMP_SIMD_ORDERED_{START,END}.  */
 240
 241 static void
 242 adjust_simduid_builtins (hash_table<simduid_to_vf> *htab)
 243 {
 244   basic_block bb;
 245
 246   FOR_EACH_BB_FN (bb, cfun)
 247     {
 248       gimple_stmt_iterator i;
 249
 250       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
 251         {
 252           poly_uint64 vf = 1;
 253           enum internal_fn ifn;
 254           gimple *stmt = gsi_stmt (i);
 255           tree t;
 256           if (!is_gimple_call (stmt)
 257               || !gimple_call_internal_p (stmt))
 258             {
 259               gsi_next (&i);
 260               continue;
 261             }
 262           ifn = gimple_call_internal_fn (stmt);
 263           switch (ifn)
 264             {
 265             case IFN_GOMP_SIMD_LANE:
 266             case IFN_GOMP_SIMD_VF:
 267             case IFN_GOMP_SIMD_LAST_LANE:
 268               break;
 269             case IFN_GOMP_SIMD_ORDERED_START:
 270             case IFN_GOMP_SIMD_ORDERED_END:
 271               if (integer_onep (gimple_call_arg (stmt, 0)))
 272                 {
 273                   enum built_in_function bcode
 274                     = (ifn == IFN_GOMP_SIMD_ORDERED_START
 275                        ? BUILT_IN_GOMP_ORDERED_START
 276                        : BUILT_IN_GOMP_ORDERED_END);
 277                   gimple *g
 278                     = gimple_build_call (builtin_decl_explicit (bcode), 0);
 279                   tree vdef = gimple_vdef (stmt);
 280                   gimple_set_vdef (g, vdef);
 281                   SSA_NAME_DEF_STMT (vdef) = g;
 282                   gimple_set_vuse (g, gimple_vuse (stmt));
 283                   gsi_replace (&i, g, true);
 284                   continue;
 285                 }
 286               gsi_remove (&i, true);
 287               unlink_stmt_vdef (stmt);
 288               continue;
 289             default:
 290               gsi_next (&i);
 291               continue;
 292             }
 293           tree arg = gimple_call_arg (stmt, 0);
 294           gcc_assert (arg != NULL_TREE);
 295           gcc_assert (TREE_CODE (arg) == SSA_NAME);
 296           simduid_to_vf *p = NULL, data;
 297           data.simduid = DECL_UID (SSA_NAME_VAR (arg));
 298           /* Need to nullify loop safelen field since it's value is not
 299              valid after transformation.  */
 300           if (bb->loop_father && bb->loop_father->safelen > 0)
 301             bb->loop_father->safelen = 0;
 302           if (htab)
 303             {
 304               p = htab->find (&data);
 305               if (p)
 306                 vf = p->vf;
 307             }
 308           switch (ifn)
 309             {
 310             case IFN_GOMP_SIMD_VF:
 311               t = build_int_cst (unsigned_type_node, vf);
 312               break;
 313             case IFN_GOMP_SIMD_LANE:
 314               t = build_int_cst (unsigned_type_node, 0);
 315               break;
 316             case IFN_GOMP_SIMD_LAST_LANE:
 317               t = gimple_call_arg (stmt, 1);
 318               break;
 319             default:
 320               gcc_unreachable ();
 321             }
 322           tree lhs = gimple_call_lhs (stmt);
 323           if (lhs)
 324             replace_uses_by (lhs, t);
 325           release_defs (stmt);
 326           gsi_remove (&i, true);
 327         }
 328     }
 329 }
 330
 331 /* Helper structure for note_simd_array_uses.  */
 332
 333 struct note_simd_array_uses_struct
 334 {
 335   hash_table<simd_array_to_simduid> **htab;
 336   unsigned int simduid;
 337 };
 338
 339 /* Callback for note_simd_array_uses, called through walk_gimple_op.  */
 340
 341 static tree
 342 note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data)
 343 {
 344   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
 345   struct note_simd_array_uses_struct *ns
 346     = (struct note_simd_array_uses_struct *) wi->info;
 347
 348   if (TYPE_P (*tp))
 349     *walk_subtrees = 0;
 350   else if (VAR_P (*tp)
 351            && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp))
 352            && DECL_CONTEXT (*tp) == current_function_decl)
 353     {
 354       simd_array_to_simduid data;
 355       if (!*ns->htab)
 356         *ns->htab = new hash_table<simd_array_to_simduid> (15);
 357       data.decl = *tp;
 358       data.simduid = ns->simduid;
 359       simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT);
 360       if (*slot == NULL)
 361         {
 362           simd_array_to_simduid *p = XNEW (simd_array_to_simduid);
 363           *p = data;
 364           *slot = p;
 365         }
 366       else if ((*slot)->simduid != ns->simduid)
 367         (*slot)->simduid = -1U;
 368       *walk_subtrees = 0;
 369     }
 370   return NULL_TREE;
 371 }
 372
 373 /* Find "omp simd array" temporaries and map them to corresponding
 374    simduid.  */
 375
 376 static void
 377 note_simd_array_uses (hash_table<simd_array_to_simduid> **htab)
 378 {
 379   basic_block bb;
 380   gimple_stmt_iterator gsi;
 381   struct walk_stmt_info wi;
 382   struct note_simd_array_uses_struct ns;
 383
 384   memset (&wi, 0, sizeof (wi));
 385   wi.info = &ns;
 386   ns.htab = htab;
 387
 388   FOR_EACH_BB_FN (bb, cfun)
 389     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 390       {
 391         gimple *stmt = gsi_stmt (gsi);
 392         if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt))
 393           continue;
 394         switch (gimple_call_internal_fn (stmt))
 395           {
 396           case IFN_GOMP_SIMD_LANE:
 397           case IFN_GOMP_SIMD_VF:
 398           case IFN_GOMP_SIMD_LAST_LANE:
 399             break;
 400           default:
 401             continue;
 402           }
 403         tree lhs = gimple_call_lhs (stmt);
 404         if (lhs == NULL_TREE)
 405           continue;
 406         imm_use_iterator use_iter;
 407         gimple *use_stmt;
 408         ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0)));
 409         FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs)
 410           if (!is_gimple_debug (use_stmt))
 411             walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi);
 412       }
 413 }
 414
 415 /* Shrink arrays with "omp simd array" attribute to the corresponding
 416    vectorization factor.  */
 417
 418 static void
 419 shrink_simd_arrays
 420   (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab,
 421    hash_table<simduid_to_vf> *simduid_to_vf_htab)
 422 {
 423   for (hash_table<simd_array_to_simduid>::iterator iter
 424          = simd_array_to_simduid_htab->begin ();
 425        iter != simd_array_to_simduid_htab->end (); ++iter)
 426     if ((*iter)->simduid != -1U)
 427       {
 428         tree decl = (*iter)->decl;
 429         poly_uint64 vf = 1;
 430         if (simduid_to_vf_htab)
 431           {
 432             simduid_to_vf *p = NULL, data;
 433             data.simduid = (*iter)->simduid;
 434             p = simduid_to_vf_htab->find (&data);
 435             if (p)
 436               vf = p->vf;
 437           }
 438         tree atype
 439           = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf);
 440         TREE_TYPE (decl) = atype;
 441         relayout_decl (decl);
 442       }
 443
 444   delete simd_array_to_simduid_htab;
 445 }
 446 \f
 447 /* Initialize the vec_info with kind KIND_IN and target cost data
 448    TARGET_COST_DATA_IN.  */
 449
 450 vec_info::vec_info (vec_info::vec_kind kind_in, void *target_cost_data_in,
 451                     vec_info_shared *shared_)
 452   : kind (kind_in),
 453     shared (shared_),
 454     target_cost_data (target_cost_data_in)
 455 {
 456   stmt_vec_infos.create (50);
 457 }
 458
 459 vec_info::~vec_info ()
 460 {
 461   slp_instance instance;
 462   unsigned int i;
 463
 464   FOR_EACH_VEC_ELT (slp_instances, i, instance)
 465     vect_free_slp_instance (instance, true);
 466
 467   destroy_cost_data (target_cost_data);
 468   free_stmt_vec_infos ();
 469 }
 470
 471 vec_info_shared::vec_info_shared ()
 472   : datarefs (vNULL),
 473     datarefs_copy (vNULL),
 474     ddrs (vNULL)
 475 {
 476 }
 477
 478 vec_info_shared::~vec_info_shared ()
 479 {
 480   free_data_refs (datarefs);
 481   free_dependence_relations (ddrs);
 482   datarefs_copy.release ();
 483 }
 484
 485 void
 486 vec_info_shared::save_datarefs ()
 487 {
 488   if (!flag_checking)
 489     return;
 490   datarefs_copy.reserve_exact (datarefs.length ());
 491   for (unsigned i = 0; i < datarefs.length (); ++i)
 492     datarefs_copy.quick_push (*datarefs[i]);
 493 }
 494
 495 void
 496 vec_info_shared::check_datarefs ()
 497 {
 498   if (!flag_checking)
 499     return;
 500   gcc_assert (datarefs.length () == datarefs_copy.length ());
 501   for (unsigned i = 0; i < datarefs.length (); ++i)
 502     if (memcmp (&datarefs_copy[i], datarefs[i], sizeof (data_reference)) != 0)
 503       gcc_unreachable ();
 504 }
 505
 506 /* Record that STMT belongs to the vectorizable region.  Create and return
 507    an associated stmt_vec_info.  */
 508
 509 stmt_vec_info
 510 vec_info::add_stmt (gimple *stmt)
 511 {
 512   stmt_vec_info res = new_stmt_vec_info (stmt);
 513   set_vinfo_for_stmt (stmt, res);
 514   return res;
 515 }
 516
 517 /* If STMT has an associated stmt_vec_info, return that vec_info, otherwise
 518    return null.  It is safe to call this function on any statement, even if
 519    it might not be part of the vectorizable region.  */
 520
 521 stmt_vec_info
 522 vec_info::lookup_stmt (gimple *stmt)
 523 {
 524   unsigned int uid = gimple_uid (stmt);
 525   if (uid > 0 && uid - 1 < stmt_vec_infos.length ())
 526     {
 527       stmt_vec_info res = stmt_vec_infos[uid - 1];
 528       if (res && res->stmt == stmt)
 529         return res;
 530     }
 531   return NULL;
 532 }
 533
 534 /* If NAME is an SSA_NAME and its definition has an associated stmt_vec_info,
 535    return that stmt_vec_info, otherwise return null.  It is safe to call
 536    this on arbitrary operands.  */
 537
 538 stmt_vec_info
 539 vec_info::lookup_def (tree name)
 540 {
 541   if (TREE_CODE (name) == SSA_NAME
 542       && !SSA_NAME_IS_DEFAULT_DEF (name))
 543     return lookup_stmt (SSA_NAME_DEF_STMT (name));
 544   return NULL;
 545 }
 546
 547 /* See whether there is a single non-debug statement that uses LHS and
 548    whether that statement has an associated stmt_vec_info.  Return the
 549    stmt_vec_info if so, otherwise return null.  */
 550
 551 stmt_vec_info
 552 vec_info::lookup_single_use (tree lhs)
 553 {
 554   use_operand_p dummy;
 555   gimple *use_stmt;
 556   if (single_imm_use (lhs, &dummy, &use_stmt))
 557     return lookup_stmt (use_stmt);
 558   return NULL;
 559 }
 560
 561 /* Return vectorization information about DR.  */
 562
 563 dr_vec_info *
 564 vec_info::lookup_dr (data_reference *dr)
 565 {
 566   stmt_vec_info stmt_info = lookup_stmt (DR_STMT (dr));
 567   /* DR_STMT should never refer to a stmt in a pattern replacement.  */
 568   gcc_checking_assert (!is_pattern_stmt_p (stmt_info));
 569   return STMT_VINFO_DR_INFO (stmt_info->dr_aux.stmt);
 570 }
 571
 572 /* Record that NEW_STMT_INFO now implements the same data reference
 573    as OLD_STMT_INFO.  */
 574
 575 void
 576 vec_info::move_dr (stmt_vec_info new_stmt_info, stmt_vec_info old_stmt_info)
 577 {
 578   gcc_assert (!is_pattern_stmt_p (old_stmt_info));
 579   STMT_VINFO_DR_INFO (old_stmt_info)->stmt = new_stmt_info;
 580   new_stmt_info->dr_aux = old_stmt_info->dr_aux;
 581   STMT_VINFO_DR_WRT_VEC_LOOP (new_stmt_info)
 582     = STMT_VINFO_DR_WRT_VEC_LOOP (old_stmt_info);
 583   STMT_VINFO_GATHER_SCATTER_P (new_stmt_info)
 584     = STMT_VINFO_GATHER_SCATTER_P (old_stmt_info);
 585 }
 586
 587 /* Permanently remove the statement described by STMT_INFO from the
 588    function.  */
 589
 590 void
 591 vec_info::remove_stmt (stmt_vec_info stmt_info)
 592 {
 593   gcc_assert (!stmt_info->pattern_stmt_p);
 594   set_vinfo_for_stmt (stmt_info->stmt, NULL);
 595   gimple_stmt_iterator si = gsi_for_stmt (stmt_info->stmt);
 596   unlink_stmt_vdef (stmt_info->stmt);
 597   gsi_remove (&si, true);
 598   release_defs (stmt_info->stmt);
 599   free_stmt_vec_info (stmt_info);
 600 }
 601
 602 /* Replace the statement at GSI by NEW_STMT, both the vectorization
 603    information and the function itself.  STMT_INFO describes the statement
 604    at GSI.  */
 605
 606 void
 607 vec_info::replace_stmt (gimple_stmt_iterator *gsi, stmt_vec_info stmt_info,
 608                         gimple *new_stmt)
 609 {
 610   gimple *old_stmt = stmt_info->stmt;
 611   gcc_assert (!stmt_info->pattern_stmt_p && old_stmt == gsi_stmt (*gsi));
 612   set_vinfo_for_stmt (old_stmt, NULL);
 613   set_vinfo_for_stmt (new_stmt, stmt_info);
 614   stmt_info->stmt = new_stmt;
 615   gsi_replace (gsi, new_stmt, true);
 616 }
 617
 618 /* Create and initialize a new stmt_vec_info struct for STMT.  */
 619
 620 stmt_vec_info
 621 vec_info::new_stmt_vec_info (gimple *stmt)
 622 {
 623   stmt_vec_info res = XCNEW (struct _stmt_vec_info);
 624   res->vinfo = this;
 625   res->stmt = stmt;
 626
 627   STMT_VINFO_TYPE (res) = undef_vec_info_type;
 628   STMT_VINFO_RELEVANT (res) = vect_unused_in_scope;
 629   STMT_VINFO_VECTORIZABLE (res) = true;
 630   STMT_VINFO_VEC_REDUCTION_TYPE (res) = TREE_CODE_REDUCTION;
 631   STMT_VINFO_VEC_CONST_COND_REDUC_CODE (res) = ERROR_MARK;
 632
 633   if (gimple_code (stmt) == GIMPLE_PHI
 634       && is_loop_header_bb_p (gimple_bb (stmt)))
 635     STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
 636   else
 637     STMT_VINFO_DEF_TYPE (res) = vect_internal_def;
 638
 639   STMT_VINFO_SAME_ALIGN_REFS (res).create (0);
 640   STMT_SLP_TYPE (res) = loop_vect;
 641
 642   /* This is really "uninitialized" until vect_compute_data_ref_alignment.  */
 643   res->dr_aux.misalignment = DR_MISALIGNMENT_UNINITIALIZED;
 644
 645   return res;
 646 }
 647
 648 /* Associate STMT with INFO.  */
 649
 650 void
 651 vec_info::set_vinfo_for_stmt (gimple *stmt, stmt_vec_info info)
 652 {
 653   unsigned int uid = gimple_uid (stmt);
 654   if (uid == 0)
 655     {
 656       gcc_checking_assert (info);
 657       uid = stmt_vec_infos.length () + 1;
 658       gimple_set_uid (stmt, uid);
 659       stmt_vec_infos.safe_push (info);
 660     }
 661   else
 662     {
 663       gcc_checking_assert (info == NULL);
 664       stmt_vec_infos[uid - 1] = info;
 665     }
 666 }
 667
 668 /* Free the contents of stmt_vec_infos.  */
 669
 670 void
 671 vec_info::free_stmt_vec_infos (void)
 672 {
 673   unsigned int i;
 674   stmt_vec_info info;
 675   FOR_EACH_VEC_ELT (stmt_vec_infos, i, info)
 676     if (info != NULL)
 677       free_stmt_vec_info (info);
 678   stmt_vec_infos.release ();
 679 }
 680
 681 /* Free STMT_INFO.  */
 682
 683 void
 684 vec_info::free_stmt_vec_info (stmt_vec_info stmt_info)
 685 {
 686   if (stmt_info->pattern_stmt_p)
 687     {
 688       gimple_set_bb (stmt_info->stmt, NULL);
 689       tree lhs = gimple_get_lhs (stmt_info->stmt);
 690       if (lhs && TREE_CODE (lhs) == SSA_NAME)
 691         release_ssa_name (lhs);
 692     }
 693
 694   STMT_VINFO_SAME_ALIGN_REFS (stmt_info).release ();
 695   STMT_VINFO_SIMD_CLONE_INFO (stmt_info).release ();
 696   free (stmt_info);
 697 }
 698
 699 /* A helper function to free scev and LOOP niter information, as well as
 700    clear loop constraint LOOP_C_FINITE.  */
 701
 702 void
 703 vect_free_loop_info_assumptions (struct loop *loop)
 704 {
 705   scev_reset_htab ();
 706   /* We need to explicitly reset upper bound information since they are
 707      used even after free_numbers_of_iterations_estimates.  */
 708   loop->any_upper_bound = false;
 709   loop->any_likely_upper_bound = false;
 710   free_numbers_of_iterations_estimates (loop);
 711   loop_constraint_clear (loop, LOOP_C_FINITE);
 712 }
 713
 714 /* If LOOP has been versioned during ifcvt, return the internal call
 715    guarding it.  */
 716
 717 static gimple *
 718 vect_loop_vectorized_call (struct loop *loop)
 719 {
 720   basic_block bb = loop_preheader_edge (loop)->src;
 721   gimple *g;
 722   do
 723     {
 724       g = last_stmt (bb);
 725       if (g)
 726         break;
 727       if (!single_pred_p (bb))
 728         break;
 729       bb = single_pred (bb);
 730     }
 731   while (1);
 732   if (g && gimple_code (g) == GIMPLE_COND)
 733     {
 734       gimple_stmt_iterator gsi = gsi_for_stmt (g);
 735       gsi_prev (&gsi);
 736       if (!gsi_end_p (gsi))
 737         {
 738           g = gsi_stmt (gsi);
 739           if (gimple_call_internal_p (g, IFN_LOOP_VECTORIZED)
 740               && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num
 741                   || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num))
 742             return g;
 743         }
 744     }
 745   return NULL;
 746 }
 747
 748 /* If LOOP has been versioned during loop distribution, return the gurading
 749    internal call.  */
 750
 751 static gimple *
 752 vect_loop_dist_alias_call (struct loop *loop)
 753 {
 754   basic_block bb;
 755   basic_block entry;
 756   struct loop *outer, *orig;
 757   gimple_stmt_iterator gsi;
 758   gimple *g;
 759
 760   if (loop->orig_loop_num == 0)
 761     return NULL;
 762
 763   orig = get_loop (cfun, loop->orig_loop_num);
 764   if (orig == NULL)
 765     {
 766       /* The original loop is somehow destroyed.  Clear the information.  */
 767       loop->orig_loop_num = 0;
 768       return NULL;
 769     }
 770
 771   if (loop != orig)
 772     bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header);
 773   else
 774     bb = loop_preheader_edge (loop)->src;
 775
 776   outer = bb->loop_father;
 777   entry = ENTRY_BLOCK_PTR_FOR_FN (cfun);
 778
 779   /* Look upward in dominance tree.  */
 780   for (; bb != entry && flow_bb_inside_loop_p (outer, bb);
 781        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
 782     {
 783       g = last_stmt (bb);
 784       if (g == NULL || gimple_code (g) != GIMPLE_COND)
 785         continue;
 786
 787       gsi = gsi_for_stmt (g);
 788       gsi_prev (&gsi);
 789       if (gsi_end_p (gsi))
 790         continue;
 791
 792       g = gsi_stmt (gsi);
 793       /* The guarding internal function call must have the same distribution
 794          alias id.  */
 795       if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS)
 796           && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num))
 797         return g;
 798     }
 799   return NULL;
 800 }
 801
 802 /* Set the uids of all the statements in basic blocks inside loop
 803    represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
 804    call guarding the loop which has been if converted.  */
 805 static void
 806 set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call)
 807 {
 808   tree arg = gimple_call_arg (loop_vectorized_call, 1);
 809   basic_block *bbs;
 810   unsigned int i;
 811   struct loop *scalar_loop = get_loop (cfun, tree_to_shwi (arg));
 812
 813   LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop;
 814   gcc_checking_assert (vect_loop_vectorized_call (scalar_loop)
 815                        == loop_vectorized_call);
 816   /* If we are going to vectorize outer loop, prevent vectorization
 817      of the inner loop in the scalar loop - either the scalar loop is
 818      thrown away, so it is a wasted work, or is used only for
 819      a few iterations.  */
 820   if (scalar_loop->inner)
 821     {
 822       gimple *g = vect_loop_vectorized_call (scalar_loop->inner);
 823       if (g)
 824         {
 825           arg = gimple_call_arg (g, 0);
 826           get_loop (cfun, tree_to_shwi (arg))->dont_vectorize = true;
 827           fold_loop_internal_call (g, boolean_false_node);
 828         }
 829     }
 830   bbs = get_loop_body (scalar_loop);
 831   for (i = 0; i < scalar_loop->num_nodes; i++)
 832     {
 833       basic_block bb = bbs[i];
 834       gimple_stmt_iterator gsi;
 835       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 836         {
 837           gimple *phi = gsi_stmt (gsi);
 838           gimple_set_uid (phi, 0);
 839         }
 840       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 841         {
 842           gimple *stmt = gsi_stmt (gsi);
 843           gimple_set_uid (stmt, 0);
 844         }
 845     }
 846   free (bbs);
 847 }
 848
 849 /* Try to vectorize LOOP.  */
 850
 851 static unsigned
 852 try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
 853                       unsigned *num_vectorized_loops,
 854                       loop_p loop, loop_vec_info orig_loop_vinfo,
 855                       gimple *loop_vectorized_call,
 856                       gimple *loop_dist_alias_call)
 857 {
 858   unsigned ret = 0;
 859   vec_info_shared shared;
 860   vect_location = find_loop_location (loop);
 861   if (LOCATION_LOCUS (vect_location.get_location_t ()) != UNKNOWN_LOCATION
 862       && dump_enabled_p ())
 863     dump_printf (MSG_NOTE, "\nAnalyzing loop at %s:%d\n",
 864                  LOCATION_FILE (vect_location.get_location_t ()),
 865                  LOCATION_LINE (vect_location.get_location_t ()));
 866
 867   loop_vec_info loop_vinfo = vect_analyze_loop (loop, orig_loop_vinfo, &shared);
 868   loop->aux = loop_vinfo;
 869
 870   if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
 871     {
 872       /* Free existing information if loop is analyzed with some
 873          assumptions.  */
 874       if (loop_constraint_set_p (loop, LOOP_C_FINITE))
 875         vect_free_loop_info_assumptions (loop);
 876
 877       /* If we applied if-conversion then try to vectorize the
 878          BB of innermost loops.
 879          ???  Ideally BB vectorization would learn to vectorize
 880          control flow by applying if-conversion on-the-fly, the
 881          following retains the if-converted loop body even when
 882          only non-if-converted parts took part in BB vectorization.  */
 883       if (flag_tree_slp_vectorize != 0
 884           && loop_vectorized_call
 885           && ! loop->inner)
 886         {
 887           basic_block bb = loop->header;
 888           bool has_mask_load_store = false;
 889           for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
 890                !gsi_end_p (gsi); gsi_next (&gsi))
 891             {
 892               gimple *stmt = gsi_stmt (gsi);
 893               if (is_gimple_call (stmt)
 894                   && gimple_call_internal_p (stmt)
 895                   && (gimple_call_internal_fn (stmt) == IFN_MASK_LOAD
 896                       || gimple_call_internal_fn (stmt) == IFN_MASK_STORE))
 897                 {
 898                   has_mask_load_store = true;
 899                   break;
 900                 }
 901               gimple_set_uid (stmt, -1);
 902               gimple_set_visited (stmt, false);
 903             }
 904           if (! has_mask_load_store && vect_slp_bb (bb))
 905             {
 906               dump_printf_loc (MSG_NOTE, vect_location,
 907                                "basic block vectorized\n");
 908               fold_loop_internal_call (loop_vectorized_call,
 909                                        boolean_true_node);
 910               loop_vectorized_call = NULL;
 911               ret |= TODO_cleanup_cfg;
 912             }
 913         }
 914       /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
 915          loop, don't vectorize its inner loop; we'll attempt to
 916          vectorize LOOP_VECTORIZED guarded inner loop of the scalar
 917          loop version.  */
 918       if (loop_vectorized_call && loop->inner)
 919         loop->inner->dont_vectorize = true;
 920       return ret;
 921     }
 922
 923   if (!dbg_cnt (vect_loop))
 924     {
 925       /* Free existing information if loop is analyzed with some
 926          assumptions.  */
 927       if (loop_constraint_set_p (loop, LOOP_C_FINITE))
 928         vect_free_loop_info_assumptions (loop);
 929       return ret;
 930     }
 931
 932   if (loop_vectorized_call)
 933     set_uid_loop_bbs (loop_vinfo, loop_vectorized_call);
 934
 935   unsigned HOST_WIDE_INT bytes;
 936   if (current_vector_size.is_constant (&bytes))
 937     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
 938                      "loop vectorized vectorized using "
 939                      HOST_WIDE_INT_PRINT_UNSIGNED " byte "
 940                      "vectors\n", bytes);
 941   else
 942     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
 943                      "loop vectorized using variable length vectors\n");
 944
 945   loop_p new_loop = vect_transform_loop (loop_vinfo);
 946   (*num_vectorized_loops)++;
 947   /* Now that the loop has been vectorized, allow it to be unrolled
 948      etc.  */
 949   loop->force_vectorize = false;
 950
 951   if (loop->simduid)
 952     {
 953       simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf);
 954       if (!simduid_to_vf_htab)
 955         simduid_to_vf_htab = new hash_table<simduid_to_vf> (15);
 956       simduid_to_vf_data->simduid = DECL_UID (loop->simduid);
 957       simduid_to_vf_data->vf = loop_vinfo->vectorization_factor;
 958       *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT)
 959           = simduid_to_vf_data;
 960     }
 961
 962   if (loop_vectorized_call)
 963     {
 964       fold_loop_internal_call (loop_vectorized_call, boolean_true_node);
 965       loop_vectorized_call = NULL;
 966       ret |= TODO_cleanup_cfg;
 967     }
 968   if (loop_dist_alias_call)
 969     {
 970       tree value = gimple_call_arg (loop_dist_alias_call, 1);
 971       fold_loop_internal_call (loop_dist_alias_call, value);
 972       loop_dist_alias_call = NULL;
 973       ret |= TODO_cleanup_cfg;
 974     }
 975
 976   /* Epilogue of vectorized loop must be vectorized too.  */
 977   if (new_loop)
 978     ret |= try_vectorize_loop_1 (simduid_to_vf_htab, num_vectorized_loops,
 979                                  new_loop, loop_vinfo, NULL, NULL);
 980
 981   return ret;
 982 }
 983
 984 /* Try to vectorize LOOP.  */
 985
 986 static unsigned
 987 try_vectorize_loop (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
 988                     unsigned *num_vectorized_loops, loop_p loop)
 989 {
 990   if (!((flag_tree_loop_vectorize
 991          && optimize_loop_nest_for_speed_p (loop))
 992         || loop->force_vectorize))
 993     return 0;
 994
 995   return try_vectorize_loop_1 (simduid_to_vf_htab, num_vectorized_loops,
 996                                loop, NULL,
 997                                vect_loop_vectorized_call (loop),
 998                                vect_loop_dist_alias_call (loop));
 999 }
1000
1001
1002 /* Function vectorize_loops.
1003
1004    Entry point to loop vectorization phase.  */
1005
1006 unsigned
1007 vectorize_loops (void)
1008 {
1009   unsigned int i;
1010   unsigned int num_vectorized_loops = 0;
1011   unsigned int vect_loops_num;
1012   struct loop *loop;
1013   hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL;
1014   hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
1015   bool any_ifcvt_loops = false;
1016   unsigned ret = 0;
1017
1018   vect_loops_num = number_of_loops (cfun);
1019
1020   /* Bail out if there are no loops.  */
1021   if (vect_loops_num <= 1)
1022     return 0;
1023
1024   if (cfun->has_simduid_loops)
1025     note_simd_array_uses (&simd_array_to_simduid_htab);
1026
1027   /*  ----------- Analyze loops. -----------  */
1028
1029   /* If some loop was duplicated, it gets bigger number
1030      than all previously defined loops.  This fact allows us to run
1031      only over initial loops skipping newly generated ones.  */
1032   FOR_EACH_LOOP (loop, 0)
1033     if (loop->dont_vectorize)
1034       {
1035         any_ifcvt_loops = true;
1036         /* If-conversion sometimes versions both the outer loop
1037            (for the case when outer loop vectorization might be
1038            desirable) as well as the inner loop in the scalar version
1039            of the loop.  So we have:
1040             if (LOOP_VECTORIZED (1, 3))
1041               {
1042                 loop1
1043                   loop2
1044               }
1045             else
1046               loop3 (copy of loop1)
1047                 if (LOOP_VECTORIZED (4, 5))
1048                   loop4 (copy of loop2)
1049                 else
1050                   loop5 (copy of loop4)
1051            If FOR_EACH_LOOP gives us loop3 first (which has
1052            dont_vectorize set), make sure to process loop1 before loop4;
1053            so that we can prevent vectorization of loop4 if loop1
1054            is successfully vectorized.  */
1055         if (loop->inner)
1056           {
1057             gimple *loop_vectorized_call
1058               = vect_loop_vectorized_call (loop);
1059             if (loop_vectorized_call
1060                 && vect_loop_vectorized_call (loop->inner))
1061               {
1062                 tree arg = gimple_call_arg (loop_vectorized_call, 0);
1063                 struct loop *vector_loop
1064                   = get_loop (cfun, tree_to_shwi (arg));
1065                 if (vector_loop && vector_loop != loop)
1066                   {
1067                     /* Make sure we don't vectorize it twice.  */
1068                     vector_loop->dont_vectorize = true;
1069                     ret |= try_vectorize_loop (simduid_to_vf_htab,
1070                                                &num_vectorized_loops,
1071                                                vector_loop);
1072                   }
1073               }
1074           }
1075       }
1076     else
1077       ret |= try_vectorize_loop (simduid_to_vf_htab, &num_vectorized_loops,
1078                                  loop);
1079
1080   vect_location = dump_user_location_t ();
1081
1082   statistics_counter_event (cfun, "Vectorized loops", num_vectorized_loops);
1083   if (dump_enabled_p ()
1084       || (num_vectorized_loops > 0 && dump_enabled_p ()))
1085     dump_printf_loc (MSG_NOTE, vect_location,
1086                      "vectorized %u loops in function.\n",
1087                      num_vectorized_loops);
1088
1089   /*  ----------- Finalize. -----------  */
1090
1091   if (any_ifcvt_loops)
1092     for (i = 1; i < number_of_loops (cfun); i++)
1093       {
1094         loop = get_loop (cfun, i);
1095         if (loop && loop->dont_vectorize)
1096           {
1097             gimple *g = vect_loop_vectorized_call (loop);
1098             if (g)
1099               {
1100                 fold_loop_internal_call (g, boolean_false_node);
1101                 ret |= TODO_cleanup_cfg;
1102                 g = NULL;
1103               }
1104             else
1105               g = vect_loop_dist_alias_call (loop);
1106
1107             if (g)
1108               {
1109                 fold_loop_internal_call (g, boolean_false_node);
1110                 ret |= TODO_cleanup_cfg;
1111               }
1112           }
1113       }
1114
1115   for (i = 1; i < number_of_loops (cfun); i++)
1116     {
1117       loop_vec_info loop_vinfo;
1118       bool has_mask_store;
1119
1120       loop = get_loop (cfun, i);
1121       if (!loop || !loop->aux)
1122         continue;
1123       loop_vinfo = (loop_vec_info) loop->aux;
1124       has_mask_store = LOOP_VINFO_HAS_MASK_STORE (loop_vinfo);
1125       delete loop_vinfo;
1126       if (has_mask_store
1127           && targetm.vectorize.empty_mask_is_expensive (IFN_MASK_STORE))
1128         optimize_mask_stores (loop);
1129       loop->aux = NULL;
1130     }
1131
1132   /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins.  */
1133   if (cfun->has_simduid_loops)
1134     adjust_simduid_builtins (simduid_to_vf_htab);
1135
1136   /* Shrink any "omp array simd" temporary arrays to the
1137      actual vectorization factors.  */
1138   if (simd_array_to_simduid_htab)
1139     shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab);
1140   delete simduid_to_vf_htab;
1141   cfun->has_simduid_loops = false;
1142
1143   if (num_vectorized_loops > 0)
1144     {
1145       /* If we vectorized any loop only virtual SSA form needs to be updated.
1146          ???  Also while we try hard to update loop-closed SSA form we fail
1147          to properly do this in some corner-cases (see PR56286).  */
1148       rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals);
1149       return TODO_cleanup_cfg;
1150     }
1151
1152   return ret;
1153 }
1154
1155
1156 /* Entry point to the simduid cleanup pass.  */
1157
1158 namespace {
1159
1160 const pass_data pass_data_simduid_cleanup =
1161 {
1162   GIMPLE_PASS, /* type */
1163   "simduid", /* name */
1164   OPTGROUP_NONE, /* optinfo_flags */
1165   TV_NONE, /* tv_id */
1166   ( PROP_ssa | PROP_cfg ), /* properties_required */
1167   0, /* properties_provided */
1168   0, /* properties_destroyed */
1169   0, /* todo_flags_start */
1170   0, /* todo_flags_finish */
1171 };
1172
1173 class pass_simduid_cleanup : public gimple_opt_pass
1174 {
1175 public:
1176   pass_simduid_cleanup (gcc::context *ctxt)
1177     : gimple_opt_pass (pass_data_simduid_cleanup, ctxt)
1178   {}
1179
1180   /* opt_pass methods: */
1181   opt_pass * clone () { return new pass_simduid_cleanup (m_ctxt); }
1182   virtual bool gate (function *fun) { return fun->has_simduid_loops; }
1183   virtual unsigned int execute (function *);
1184
1185 }; // class pass_simduid_cleanup
1186
1187 unsigned int
1188 pass_simduid_cleanup::execute (function *fun)
1189 {
1190   hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
1191
1192   note_simd_array_uses (&simd_array_to_simduid_htab);
1193
1194   /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins.  */
1195   adjust_simduid_builtins (NULL);
1196
1197   /* Shrink any "omp array simd" temporary arrays to the
1198      actual vectorization factors.  */
1199   if (simd_array_to_simduid_htab)
1200     shrink_simd_arrays (simd_array_to_simduid_htab, NULL);
1201   fun->has_simduid_loops = false;
1202   return 0;
1203 }
1204
1205 }  // anon namespace
1206
1207 gimple_opt_pass *
1208 make_pass_simduid_cleanup (gcc::context *ctxt)
1209 {
1210   return new pass_simduid_cleanup (ctxt);
1211 }
1212
1213
1214 /*  Entry point to basic block SLP phase.  */
1215
1216 namespace {
1217
1218 const pass_data pass_data_slp_vectorize =
1219 {
1220   GIMPLE_PASS, /* type */
1221   "slp", /* name */
1222   OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1223   TV_TREE_SLP_VECTORIZATION, /* tv_id */
1224   ( PROP_ssa | PROP_cfg ), /* properties_required */
1225   0, /* properties_provided */
1226   0, /* properties_destroyed */
1227   0, /* todo_flags_start */
1228   TODO_update_ssa, /* todo_flags_finish */
1229 };
1230
1231 class pass_slp_vectorize : public gimple_opt_pass
1232 {
1233 public:
1234   pass_slp_vectorize (gcc::context *ctxt)
1235     : gimple_opt_pass (pass_data_slp_vectorize, ctxt)
1236   {}
1237
1238   /* opt_pass methods: */
1239   opt_pass * clone () { return new pass_slp_vectorize (m_ctxt); }
1240   virtual bool gate (function *) { return flag_tree_slp_vectorize != 0; }
1241   virtual unsigned int execute (function *);
1242
1243 }; // class pass_slp_vectorize
1244
1245 unsigned int
1246 pass_slp_vectorize::execute (function *fun)
1247 {
1248   basic_block bb;
1249
1250   bool in_loop_pipeline = scev_initialized_p ();
1251   if (!in_loop_pipeline)
1252     {
1253       loop_optimizer_init (LOOPS_NORMAL);
1254       scev_initialize ();
1255     }
1256
1257   /* Mark all stmts as not belonging to the current region and unvisited.  */
1258   FOR_EACH_BB_FN (bb, fun)
1259     {
1260       for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1261            gsi_next (&gsi))
1262         {
1263           gimple *stmt = gsi_stmt (gsi);
1264           gimple_set_uid (stmt, -1);
1265           gimple_set_visited (stmt, false);
1266         }
1267     }
1268
1269   FOR_EACH_BB_FN (bb, fun)
1270     {
1271       if (vect_slp_bb (bb))
1272         dump_printf_loc (MSG_NOTE, vect_location, "basic block vectorized\n");
1273     }
1274
1275   if (!in_loop_pipeline)
1276     {
1277       scev_finalize ();
1278       loop_optimizer_finalize ();
1279     }
1280
1281   return 0;
1282 }
1283
1284 } // anon namespace
1285
1286 gimple_opt_pass *
1287 make_pass_slp_vectorize (gcc::context *ctxt)
1288 {
1289   return new pass_slp_vectorize (ctxt);
1290 }
1291
1292
1293 /* Increase alignment of global arrays to improve vectorization potential.
1294    TODO:
1295    - Consider also structs that have an array field.
1296    - Use ipa analysis to prune arrays that can't be vectorized?
1297      This should involve global alignment analysis and in the future also
1298      array padding.  */
1299
1300 static unsigned get_vec_alignment_for_type (tree);
1301 static hash_map<tree, unsigned> *type_align_map;
1302
1303 /* Return alignment of array's vector type corresponding to scalar type.
1304    0 if no vector type exists.  */
1305 static unsigned
1306 get_vec_alignment_for_array_type (tree type)
1307 {
1308   gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
1309   poly_uint64 array_size, vector_size;
1310
1311   tree vectype = get_vectype_for_scalar_type (strip_array_types (type));
1312   if (!vectype
1313       || !poly_int_tree_p (TYPE_SIZE (type), &array_size)
1314       || !poly_int_tree_p (TYPE_SIZE (vectype), &vector_size)
1315       || maybe_lt (array_size, vector_size))
1316     return 0;
1317
1318   return TYPE_ALIGN (vectype);
1319 }
1320
1321 /* Return alignment of field having maximum alignment of vector type
1322    corresponding to it's scalar type. For now, we only consider fields whose
1323    offset is a multiple of it's vector alignment.
1324    0 if no suitable field is found.  */
1325 static unsigned
1326 get_vec_alignment_for_record_type (tree type)
1327 {
1328   gcc_assert (TREE_CODE (type) == RECORD_TYPE);
1329
1330   unsigned max_align = 0, alignment;
1331   HOST_WIDE_INT offset;
1332   tree offset_tree;
1333
1334   if (TYPE_PACKED (type))
1335     return 0;
1336
1337   unsigned *slot = type_align_map->get (type);
1338   if (slot)
1339     return *slot;
1340
1341   for (tree field = first_field (type);
1342        field != NULL_TREE;
1343        field = DECL_CHAIN (field))
1344     {
1345       /* Skip if not FIELD_DECL or if alignment is set by user.  */
1346       if (TREE_CODE (field) != FIELD_DECL
1347           || DECL_USER_ALIGN (field)
1348           || DECL_ARTIFICIAL (field))
1349         continue;
1350
1351       /* We don't need to process the type further if offset is variable,
1352          since the offsets of remaining members will also be variable.  */
1353       if (TREE_CODE (DECL_FIELD_OFFSET (field)) != INTEGER_CST
1354           || TREE_CODE (DECL_FIELD_BIT_OFFSET (field)) != INTEGER_CST)
1355         break;
1356
1357       /* Similarly stop processing the type if offset_tree
1358          does not fit in unsigned HOST_WIDE_INT.  */
1359       offset_tree = bit_position (field);
1360       if (!tree_fits_uhwi_p (offset_tree))
1361         break;
1362
1363       offset = tree_to_uhwi (offset_tree);
1364       alignment = get_vec_alignment_for_type (TREE_TYPE (field));
1365
1366       /* Get maximum alignment of vectorized field/array among those members
1367          whose offset is multiple of the vector alignment.  */
1368       if (alignment
1369           && (offset % alignment == 0)
1370           && (alignment > max_align))
1371         max_align = alignment;
1372     }
1373
1374   type_align_map->put (type, max_align);
1375   return max_align;
1376 }
1377
1378 /* Return alignment of vector type corresponding to decl's scalar type
1379    or 0 if it doesn't exist or the vector alignment is lesser than
1380    decl's alignment.  */
1381 static unsigned
1382 get_vec_alignment_for_type (tree type)
1383 {
1384   if (type == NULL_TREE)
1385     return 0;
1386
1387   gcc_assert (TYPE_P (type));
1388
1389   static unsigned alignment = 0;
1390   switch (TREE_CODE (type))
1391     {
1392       case ARRAY_TYPE:
1393         alignment = get_vec_alignment_for_array_type (type);
1394         break;
1395       case RECORD_TYPE:
1396         alignment = get_vec_alignment_for_record_type (type);
1397         break;
1398       default:
1399         alignment = 0;
1400         break;
1401     }
1402
1403   return (alignment > TYPE_ALIGN (type)) ? alignment : 0;
1404 }
1405
1406 /* Entry point to increase_alignment pass.  */
1407 static unsigned int
1408 increase_alignment (void)
1409 {
1410   varpool_node *vnode;
1411
1412   vect_location = dump_user_location_t ();
1413   type_align_map = new hash_map<tree, unsigned>;
1414
1415   /* Increase the alignment of all global arrays for vectorization.  */
1416   FOR_EACH_DEFINED_VARIABLE (vnode)
1417     {
1418       tree decl = vnode->decl;
1419       unsigned int alignment;
1420
1421       if ((decl_in_symtab_p (decl)
1422           && !symtab_node::get (decl)->can_increase_alignment_p ())
1423           || DECL_USER_ALIGN (decl) || DECL_ARTIFICIAL (decl))
1424         continue;
1425
1426       alignment = get_vec_alignment_for_type (TREE_TYPE (decl));
1427       if (alignment && vect_can_force_dr_alignment_p (decl, alignment))
1428         {
1429           vnode->increase_alignment (alignment);
1430           dump_printf (MSG_NOTE, "Increasing alignment of decl: ");
1431           dump_generic_expr (MSG_NOTE, TDF_SLIM, decl);
1432           dump_printf (MSG_NOTE, "\n");
1433         }
1434     }
1435
1436   delete type_align_map;
1437   return 0;
1438 }
1439
1440
1441 namespace {
1442
1443 const pass_data pass_data_ipa_increase_alignment =
1444 {
1445   SIMPLE_IPA_PASS, /* type */
1446   "increase_alignment", /* name */
1447   OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1448   TV_IPA_OPT, /* tv_id */
1449   0, /* properties_required */
1450   0, /* properties_provided */
1451   0, /* properties_destroyed */
1452   0, /* todo_flags_start */
1453   0, /* todo_flags_finish */
1454 };
1455
1456 class pass_ipa_increase_alignment : public simple_ipa_opt_pass
1457 {
1458 public:
1459   pass_ipa_increase_alignment (gcc::context *ctxt)
1460     : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt)
1461   {}
1462
1463   /* opt_pass methods: */
1464   virtual bool gate (function *)
1465     {
1466       return flag_section_anchors && flag_tree_loop_vectorize;
1467     }
1468
1469   virtual unsigned int execute (function *) { return increase_alignment (); }
1470
1471 }; // class pass_ipa_increase_alignment
1472
1473 } // anon namespace
1474
1475 simple_ipa_opt_pass *
1476 make_pass_ipa_increase_alignment (gcc::context *ctxt)
1477 {
1478   return new pass_ipa_increase_alignment (ctxt);
1479 }