gcc/tree-vectorizer.c

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