LCOV - code coverage report
Current view: top level - gcc - tree-vectorizer.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.0 % 937 834
Test Date: 2026-11-14 16:39:50 Functions: 89.2 % 65 58
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Vectorizer
       2              :    Copyright (C) 2003-2026 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.cc - loop specific parts such as reductions, etc. These are
      31              :     used by drivers (1) and (2).
      32              :   - tree-vect-loop-manip.cc - vectorizer's loop control-flow utilities, used by
      33              :     drivers (1) and (2).
      34              :   - tree-vect-slp.cc - BB vectorization specific analysis and transformation,
      35              :     used by drivers (2) and (3).
      36              :   - tree-vect-stmts.cc - statements analysis and transformation (used by all).
      37              :   - tree-vect-data-refs.cc - vectorizer specific data-refs analysis and
      38              :     manipulations (used by all).
      39              :   - tree-vect-patterns.cc - vectorizable code patterns detector (used by all)
      40              : 
      41              :   Here's a poor attempt at illustrating that:
      42              : 
      43              :      tree-vectorizer.cc:
      44              :      loop_vect()  loop_aware_slp()  slp_vect()
      45              :           |        /           \          /
      46              :           |       /             \        /
      47              :           tree-vect-loop.cc  tree-vect-slp.cc
      48              :                 | \      \  /      /   |
      49              :                 |  \      \/      /    |
      50              :                 |   \     /\     /     |
      51              :                 |    \   /  \   /      |
      52              :          tree-vect-stmts.cc  tree-vect-data-refs.cc
      53              :                        \      /
      54              :                     tree-vect-patterns.cc
      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              : #include "tree-ssa-sccvn.h"
      85              : #include "tree-into-ssa.h"
      86              : #include "gimple-range.h"
      87              : 
      88              : /* Loop or bb location, with hotness information.  */
      89              : dump_user_location_t vect_location;
      90              : 
      91              : /* auto_purge_vect_location's dtor: reset the vect_location
      92              :    global, to avoid stale location_t values that could reference
      93              :    GC-ed blocks.  */
      94              : 
      95      1408300 : auto_purge_vect_location::~auto_purge_vect_location ()
      96              : {
      97      1408300 :   vect_location = dump_user_location_t ();
      98      1408300 : }
      99              : 
     100              : /* Dump a cost entry according to args to F.  */
     101              : 
     102              : void
     103       232638 : dump_stmt_cost (FILE *f, int count, enum vect_cost_for_stmt kind,
     104              :                 stmt_vec_info stmt_info, slp_tree node, tree,
     105              :                 int misalign, unsigned cost,
     106              :                 enum vect_cost_model_location where)
     107              : {
     108       232638 :   if (stmt_info)
     109              :     {
     110       209846 :       print_gimple_expr (f, STMT_VINFO_STMT (stmt_info), 0, TDF_SLIM);
     111       209846 :       fprintf (f, " ");
     112              :     }
     113        22792 :   else if (node)
     114        22182 :     fprintf (f, "node %p ", (void *)node);
     115              :   else
     116          610 :     fprintf (f, "<unknown> ");
     117       232638 :   fprintf (f, "%d times ", count);
     118       232638 :   const char *ks = "unknown";
     119       232638 :   switch (kind)
     120              :     {
     121        52558 :     case scalar_stmt:
     122        52558 :       ks = "scalar_stmt";
     123        52558 :       break;
     124        38710 :     case scalar_load:
     125        38710 :       ks = "scalar_load";
     126        38710 :       break;
     127        29168 :     case scalar_store:
     128        29168 :       ks = "scalar_store";
     129        29168 :       break;
     130        37626 :     case vector_stmt:
     131        37626 :       ks = "vector_stmt";
     132        37626 :       break;
     133        23411 :     case vector_load:
     134        23411 :       ks = "vector_load";
     135        23411 :       break;
     136            0 :     case vector_gather_load:
     137            0 :       ks = "vector_gather_load";
     138            0 :       break;
     139         8307 :     case unaligned_load:
     140         8307 :       ks = "unaligned_load";
     141         8307 :       break;
     142         4994 :     case unaligned_store:
     143         4994 :       ks = "unaligned_store";
     144         4994 :       break;
     145         9251 :     case vector_store:
     146         9251 :       ks = "vector_store";
     147         9251 :       break;
     148            0 :     case vector_scatter_store:
     149            0 :       ks = "vector_scatter_store";
     150            0 :       break;
     151         3697 :     case vec_to_scalar:
     152         3697 :       ks = "vec_to_scalar";
     153         3697 :       break;
     154         9795 :     case scalar_to_vec:
     155         9795 :       ks = "scalar_to_vec";
     156         9795 :       break;
     157           18 :     case cond_branch_not_taken:
     158           18 :       ks = "cond_branch_not_taken";
     159           18 :       break;
     160          560 :     case cond_branch_taken:
     161          560 :       ks = "cond_branch_taken";
     162          560 :       break;
     163         6609 :     case vec_perm:
     164         6609 :       ks = "vec_perm";
     165         6609 :       break;
     166         5558 :     case vec_promote_demote:
     167         5558 :       ks = "vec_promote_demote";
     168         5558 :       break;
     169         1251 :     case vec_construct:
     170         1251 :       ks = "vec_construct";
     171         1251 :       break;
     172         1125 :     case vec_deconstruct:
     173         1125 :       ks = "vec_deconstruct";
     174         1125 :       break;
     175              :     }
     176       232638 :   fprintf (f, "%s ", ks);
     177       232638 :   if (kind == unaligned_load || kind == unaligned_store)
     178        13301 :     fprintf (f, "(misalign %d) ", misalign);
     179       232638 :   fprintf (f, "costs %u ", cost);
     180       232638 :   const char *ws = "unknown";
     181       232638 :   switch (where)
     182              :     {
     183        24882 :     case vect_prologue:
     184        24882 :       ws = "prologue";
     185        24882 :       break;
     186       198766 :     case vect_body:
     187       198766 :       ws = "body";
     188       198766 :       break;
     189         8990 :     case vect_epilogue:
     190         8990 :       ws = "epilogue";
     191         8990 :       break;
     192              :     }
     193       232638 :   fprintf (f, "in %s\n", ws);
     194       232638 : }
     195              : 
     196              : /* For mapping simduid to vectorization factor.  */
     197              : 
     198              : class simduid_to_vf : public free_ptr_hash<simduid_to_vf>
     199              : {
     200              : public:
     201              :   unsigned int simduid;
     202              :   poly_uint64 vf;
     203              : 
     204              :   /* hash_table support.  */
     205              :   static inline hashval_t hash (const simduid_to_vf *);
     206              :   static inline int equal (const simduid_to_vf *, const simduid_to_vf *);
     207              : };
     208              : 
     209              : inline hashval_t
     210         7499 : simduid_to_vf::hash (const simduid_to_vf *p)
     211              : {
     212         7499 :   return p->simduid;
     213              : }
     214              : 
     215              : inline int
     216        13971 : simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2)
     217              : {
     218        13971 :   return p1->simduid == p2->simduid;
     219              : }
     220              : 
     221              : /* This hash maps the OMP simd array to the corresponding simduid used
     222              :    to index into it.  Like thus,
     223              : 
     224              :         _7 = GOMP_SIMD_LANE (simduid.0)
     225              :         ...
     226              :         ...
     227              :         D.1737[_7] = stuff;
     228              : 
     229              : 
     230              :    This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
     231              :    simduid.0.  */
     232              : 
     233              : struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid>
     234              : {
     235              :   tree decl;
     236              :   unsigned int simduid;
     237              : 
     238              :   /* hash_table support.  */
     239              :   static inline hashval_t hash (const simd_array_to_simduid *);
     240              :   static inline int equal (const simd_array_to_simduid *,
     241              :                            const simd_array_to_simduid *);
     242              : };
     243              : 
     244              : inline hashval_t
     245        24455 : simd_array_to_simduid::hash (const simd_array_to_simduid *p)
     246              : {
     247        24455 :   return DECL_UID (p->decl);
     248              : }
     249              : 
     250              : inline int
     251        17126 : simd_array_to_simduid::equal (const simd_array_to_simduid *p1,
     252              :                               const simd_array_to_simduid *p2)
     253              : {
     254        17126 :   return p1->decl == p2->decl;
     255              : }
     256              : 
     257              : /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
     258              :    into their corresponding constants and remove
     259              :    IFN_GOMP_SIMD_ORDERED_{START,END}.  */
     260              : 
     261              : static void
     262         7803 : adjust_simduid_builtins (hash_table<simduid_to_vf> *htab, function *fun)
     263              : {
     264         7803 :   basic_block bb;
     265              : 
     266       118287 :   FOR_EACH_BB_FN (bb, fun)
     267              :     {
     268       110484 :       gimple_stmt_iterator i;
     269              : 
     270       744337 :       for (i = gsi_start_bb (bb); !gsi_end_p (i); )
     271              :         {
     272       523369 :           poly_uint64 vf = 1;
     273       523369 :           enum internal_fn ifn;
     274       523369 :           gimple *stmt = gsi_stmt (i);
     275       523369 :           tree t;
     276       523369 :           if (!is_gimple_call (stmt)
     277       523369 :               || !gimple_call_internal_p (stmt))
     278              :             {
     279       515889 :               gsi_next (&i);
     280       516763 :               continue;
     281              :             }
     282         7480 :           ifn = gimple_call_internal_fn (stmt);
     283         7480 :           switch (ifn)
     284              :             {
     285         6606 :             case IFN_GOMP_SIMD_LANE:
     286         6606 :             case IFN_GOMP_SIMD_VF:
     287         6606 :             case IFN_GOMP_SIMD_LAST_LANE:
     288         6606 :               break;
     289          162 :             case IFN_GOMP_SIMD_ORDERED_START:
     290          162 :             case IFN_GOMP_SIMD_ORDERED_END:
     291          162 :               if (integer_onep (gimple_call_arg (stmt, 0)))
     292              :                 {
     293            6 :                   enum built_in_function bcode
     294              :                     = (ifn == IFN_GOMP_SIMD_ORDERED_START
     295           12 :                        ? BUILT_IN_GOMP_ORDERED_START
     296              :                        : BUILT_IN_GOMP_ORDERED_END);
     297           12 :                   gimple *g
     298           12 :                     = gimple_build_call (builtin_decl_explicit (bcode), 0);
     299           12 :                   gimple_move_vops (g, stmt);
     300           12 :                   gsi_replace (&i, g, true);
     301           12 :                   continue;
     302           12 :                 }
     303          150 :               gsi_remove (&i, true);
     304          150 :               unlink_stmt_vdef (stmt);
     305          150 :               continue;
     306          712 :             default:
     307          712 :               gsi_next (&i);
     308          712 :               continue;
     309          862 :             }
     310         6606 :           tree arg = gimple_call_arg (stmt, 0);
     311         6606 :           gcc_assert (arg != NULL_TREE);
     312         6606 :           gcc_assert (TREE_CODE (arg) == SSA_NAME);
     313         6606 :           simduid_to_vf *p = NULL, data;
     314         6606 :           data.simduid = DECL_UID (SSA_NAME_VAR (arg));
     315              :           /* Need to nullify loop safelen field since it's value is not
     316              :              valid after transformation.  */
     317         6606 :           if (bb->loop_father && bb->loop_father->safelen > 0)
     318         2160 :             bb->loop_father->safelen = 0;
     319         6606 :           if (htab)
     320              :             {
     321         4705 :               p = htab->find (&data);
     322         4705 :               if (p)
     323         4670 :                 vf = p->vf;
     324              :             }
     325         6606 :           switch (ifn)
     326              :             {
     327              :             case IFN_GOMP_SIMD_VF:
     328          976 :               t = build_int_cst (unsigned_type_node, vf);
     329          976 :               break;
     330         3443 :             case IFN_GOMP_SIMD_LANE:
     331         3443 :               t = build_int_cst (unsigned_type_node, 0);
     332         3443 :               break;
     333         2187 :             case IFN_GOMP_SIMD_LAST_LANE:
     334         2187 :               t = gimple_call_arg (stmt, 1);
     335         2187 :               break;
     336              :             default:
     337              :               gcc_unreachable ();
     338              :             }
     339         6606 :           tree lhs = gimple_call_lhs (stmt);
     340         6606 :           if (lhs)
     341         6554 :             replace_uses_by (lhs, t);
     342         6606 :           release_defs (stmt);
     343         6606 :           gsi_remove (&i, true);
     344              :         }
     345              :     }
     346         7803 : }
     347              : 
     348              : /* Helper structure for note_simd_array_uses.  */
     349              : 
     350              : struct note_simd_array_uses_struct
     351              : {
     352              :   hash_table<simd_array_to_simduid> **htab;
     353              :   unsigned int simduid;
     354              : };
     355              : 
     356              : /* Callback for note_simd_array_uses, called through walk_gimple_op.  */
     357              : 
     358              : static tree
     359        64444 : note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data)
     360              : {
     361        64444 :   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
     362        64444 :   struct note_simd_array_uses_struct *ns
     363              :     = (struct note_simd_array_uses_struct *) wi->info;
     364              : 
     365        64444 :   if (TYPE_P (*tp))
     366            0 :     *walk_subtrees = 0;
     367        64444 :   else if (VAR_P (*tp)
     368        12207 :            && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp))
     369        76651 :            && DECL_CONTEXT (*tp) == current_function_decl)
     370              :     {
     371        12207 :       simd_array_to_simduid data;
     372        12207 :       if (!*ns->htab)
     373         2209 :         *ns->htab = new hash_table<simd_array_to_simduid> (15);
     374        12207 :       data.decl = *tp;
     375        12207 :       data.simduid = ns->simduid;
     376        12207 :       simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT);
     377        12207 :       if (*slot == NULL)
     378              :         {
     379         5489 :           simd_array_to_simduid *p = XNEW (simd_array_to_simduid);
     380         5489 :           *p = data;
     381         5489 :           *slot = p;
     382              :         }
     383         6718 :       else if ((*slot)->simduid != ns->simduid)
     384            0 :         (*slot)->simduid = -1U;
     385        12207 :       *walk_subtrees = 0;
     386              :     }
     387        64444 :   return NULL_TREE;
     388              : }
     389              : 
     390              : /* Find "omp simd array" temporaries and map them to corresponding
     391              :    simduid.  */
     392              : 
     393              : static void
     394         7803 : note_simd_array_uses (hash_table<simd_array_to_simduid> **htab, function *fun)
     395              : {
     396         7803 :   basic_block bb;
     397         7803 :   gimple_stmt_iterator gsi;
     398         7803 :   struct walk_stmt_info wi;
     399         7803 :   struct note_simd_array_uses_struct ns;
     400              : 
     401         7803 :   memset (&wi, 0, sizeof (wi));
     402         7803 :   wi.info = &ns;
     403         7803 :   ns.htab = htab;
     404              : 
     405       102255 :   FOR_EACH_BB_FN (bb, fun)
     406       587168 :     for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     407              :       {
     408       398264 :         gimple *stmt = gsi_stmt (gsi);
     409       398264 :         if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt))
     410       391725 :           continue;
     411         7438 :         switch (gimple_call_internal_fn (stmt))
     412              :           {
     413         6570 :           case IFN_GOMP_SIMD_LANE:
     414         6570 :           case IFN_GOMP_SIMD_VF:
     415         6570 :           case IFN_GOMP_SIMD_LAST_LANE:
     416         6570 :             break;
     417          868 :           default:
     418          868 :             continue;
     419              :           }
     420         6570 :         tree lhs = gimple_call_lhs (stmt);
     421         6570 :         if (lhs == NULL_TREE)
     422           31 :           continue;
     423         6539 :         imm_use_iterator use_iter;
     424         6539 :         gimple *use_stmt;
     425         6539 :         ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0)));
     426        24431 :         FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs)
     427        17892 :           if (!is_gimple_debug (use_stmt))
     428        24339 :             walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi);
     429              :       }
     430         7803 : }
     431              : 
     432              : /* Shrink arrays with "omp simd array" attribute to the corresponding
     433              :    vectorization factor.  */
     434              : 
     435              : static void
     436         2209 : shrink_simd_arrays
     437              :   (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab,
     438              :    hash_table<simduid_to_vf> *simduid_to_vf_htab)
     439              : {
     440         5489 :   for (hash_table<simd_array_to_simduid>::iterator iter
     441         2209 :          = simd_array_to_simduid_htab->begin ();
     442         7698 :        iter != simd_array_to_simduid_htab->end (); ++iter)
     443         5489 :     if ((*iter)->simduid != -1U)
     444              :       {
     445         5489 :         tree decl = (*iter)->decl;
     446         5489 :         poly_uint64 vf = 1;
     447         5489 :         if (simduid_to_vf_htab)
     448              :           {
     449         4562 :             simduid_to_vf *p = NULL, data;
     450         4562 :             data.simduid = (*iter)->simduid;
     451         4562 :             p = simduid_to_vf_htab->find (&data);
     452         4562 :             if (p)
     453         4531 :               vf = p->vf;
     454              :           }
     455         5489 :         tree atype
     456         5489 :           = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf);
     457         5489 :         TREE_TYPE (decl) = atype;
     458         5489 :         relayout_decl (decl);
     459              :       }
     460              : 
     461         2209 :   delete simd_array_to_simduid_htab;
     462         2209 : }
     463              : 
     464              : /* Initialize the vec_info with kind KIND_IN and target cost data
     465              :    TARGET_COST_DATA_IN.  */
     466              : 
     467      2854346 : vec_info::vec_info (vec_info::vec_kind kind_in, vec_info_shared *shared_)
     468      2854346 :   : kind (kind_in),
     469      2854346 :     shared (shared_),
     470      2854346 :     stmt_vec_info_ro (false),
     471      2854346 :     bbs (NULL),
     472      2854346 :     nbbs (0),
     473      2854346 :     inv_pattern_def_seq (NULL)
     474              : {
     475      2854346 :   stmt_vec_infos.create (50);
     476      2854346 : }
     477              : 
     478      2854346 : vec_info::~vec_info ()
     479              : {
     480      5226827 :   for (slp_instance &instance : slp_instances)
     481      1200801 :     vect_free_slp_instance (instance);
     482              : 
     483      2854346 :   free_stmt_vec_infos ();
     484      2854346 : }
     485              : 
     486      2429586 : vec_info_shared::vec_info_shared ()
     487      2429586 :   : datarefs (vNULL),
     488      2429586 :     datarefs_copy (vNULL),
     489      2429586 :     ddrs (vNULL)
     490              : {
     491      2429586 : }
     492              : 
     493      2429586 : vec_info_shared::~vec_info_shared ()
     494              : {
     495      2429586 :   free_data_refs (datarefs);
     496      2429586 :   free_dependence_relations (ddrs);
     497      2429586 :   datarefs_copy.release ();
     498      2429586 : }
     499              : 
     500              : void
     501      2186810 : vec_info_shared::save_datarefs ()
     502              : {
     503      2186810 :   if (!flag_checking)
     504              :     return;
     505      3275576 :   datarefs_copy.reserve_exact (datarefs.length ());
     506     15422359 :   for (unsigned i = 0; i < datarefs.length (); ++i)
     507     11048773 :     datarefs_copy.quick_push (*datarefs[i]);
     508              : }
     509              : 
     510              : void
     511      1188222 : vec_info_shared::check_datarefs ()
     512              : {
     513      1188222 :   if (!flag_checking)
     514              :     return;
     515      3514492 :   gcc_assert (datarefs.length () == datarefs_copy.length ());
     516     14051350 :   for (unsigned i = 0; i < datarefs.length (); ++i)
     517     12863132 :     if (memcmp (&datarefs_copy[i], datarefs[i],
     518              :                 offsetof (data_reference, alt_indices)) != 0)
     519            0 :       gcc_unreachable ();
     520              : }
     521              : 
     522              : /* Record that STMT belongs to the vectorizable region.  Create and return
     523              :    an associated stmt_vec_info.  */
     524              : 
     525              : stmt_vec_info
     526     63787251 : vec_info::add_stmt (gimple *stmt)
     527              : {
     528     63787251 :   stmt_vec_info res = new_stmt_vec_info (stmt);
     529     63787251 :   set_vinfo_for_stmt (stmt, res);
     530     63787251 :   return res;
     531              : }
     532              : 
     533              : /* Record that STMT belongs to the vectorizable region.  Create a new
     534              :    stmt_vec_info and mark VECINFO as being related and return the new
     535              :    stmt_vec_info.  */
     536              : 
     537              : stmt_vec_info
     538         1114 : vec_info::add_pattern_stmt (gimple *stmt, stmt_vec_info stmt_info)
     539              : {
     540         1114 :   stmt_vec_info res = new_stmt_vec_info (stmt);
     541         1114 :   res->pattern_stmt_p = true;
     542         1114 :   set_vinfo_for_stmt (stmt, res, false);
     543         1114 :   STMT_VINFO_RELATED_STMT (res) = stmt_info;
     544         1114 :   return res;
     545              : }
     546              : 
     547              : /* If STMT was previously associated with a stmt_vec_info and STMT now resides
     548              :    at a different address than before (e.g., because STMT is a phi node that has
     549              :    been resized), update the stored address to match the new one.  It is not
     550              :    possible to use lookup_stmt () to perform this task, because that function
     551              :    returns NULL if the stored stmt pointer does not match the one being looked
     552              :    up.  */
     553              : 
     554              : stmt_vec_info
     555        11242 : vec_info::resync_stmt_addr (gimple *stmt)
     556              : {
     557        11242 :   unsigned int uid = gimple_uid (stmt);
     558        11242 :   if (uid > 0 && uid - 1 < stmt_vec_infos.length ())
     559              :     {
     560        11242 :       stmt_vec_info res = stmt_vec_infos[uid - 1];
     561        11242 :       if (res && res->stmt)
     562              :         {
     563        11242 :           res->stmt = stmt;
     564        11242 :           return res;
     565              :         }
     566              :     }
     567              :   return nullptr;
     568              : }
     569              : 
     570              : /* If STMT has an associated stmt_vec_info, return that vec_info, otherwise
     571              :    return null.  It is safe to call this function on any statement, even if
     572              :    it might not be part of the vectorizable region.  */
     573              : 
     574              : stmt_vec_info
     575    519972209 : vec_info::lookup_stmt (gimple *stmt)
     576              : {
     577    519972209 :   unsigned int uid = gimple_uid (stmt);
     578    519972209 :   if (uid > 0 && uid - 1 < stmt_vec_infos.length ())
     579              :     {
     580    321420128 :       stmt_vec_info res = stmt_vec_infos[uid - 1];
     581    321420128 :       if (res && res->stmt == stmt)
     582    321063757 :         return res;
     583              :     }
     584              :   return NULL;
     585              : }
     586              : 
     587              : /* If NAME is an SSA_NAME and its definition has an associated stmt_vec_info,
     588              :    return that stmt_vec_info, otherwise return null.  It is safe to call
     589              :    this on arbitrary operands.  */
     590              : 
     591              : stmt_vec_info
     592     60885817 : vec_info::lookup_def (tree name)
     593              : {
     594     60885817 :   if (TREE_CODE (name) == SSA_NAME
     595     60885817 :       && !SSA_NAME_IS_DEFAULT_DEF (name))
     596     55021940 :     return lookup_stmt (SSA_NAME_DEF_STMT (name));
     597              :   return NULL;
     598              : }
     599              : 
     600              : /* See whether there is a single non-debug statement that uses LHS and
     601              :    whether that statement has an associated stmt_vec_info.  Return the
     602              :    stmt_vec_info if so, otherwise return null.  */
     603              : 
     604              : stmt_vec_info
     605         2004 : vec_info::lookup_single_use (tree lhs)
     606              : {
     607         2004 :   use_operand_p dummy;
     608         2004 :   gimple *use_stmt;
     609         2004 :   if (single_imm_use (lhs, &dummy, &use_stmt))
     610         1859 :     return lookup_stmt (use_stmt);
     611              :   return NULL;
     612              : }
     613              : 
     614              : /* Return vectorization information about DR.  */
     615              : 
     616              : dr_vec_info *
     617     53006790 : vec_info::lookup_dr (data_reference *dr)
     618              : {
     619     53006790 :   stmt_vec_info stmt_info = lookup_stmt (DR_STMT (dr));
     620              :   /* DR_STMT should never refer to a stmt in a pattern replacement.  */
     621     53006790 :   gcc_checking_assert (!is_pattern_stmt_p (stmt_info));
     622     53006790 :   return STMT_VINFO_DR_INFO (stmt_info->dr_aux.stmt);
     623              : }
     624              : 
     625              : /* Record that NEW_STMT_INFO now implements the same data reference
     626              :    as OLD_STMT_INFO.  */
     627              : 
     628              : void
     629         6295 : vec_info::move_dr (stmt_vec_info new_stmt_info, stmt_vec_info old_stmt_info)
     630              : {
     631         6295 :   gcc_assert (!is_pattern_stmt_p (old_stmt_info));
     632         6295 :   STMT_VINFO_DR_INFO (old_stmt_info)->stmt = new_stmt_info;
     633         6295 :   new_stmt_info->dr_aux = old_stmt_info->dr_aux;
     634         6295 :   STMT_VINFO_DR_WRT_VEC_LOOP (new_stmt_info)
     635         6295 :     = STMT_VINFO_DR_WRT_VEC_LOOP (old_stmt_info);
     636         6295 :   STMT_VINFO_GATHER_SCATTER_P (new_stmt_info)
     637         6295 :     = STMT_VINFO_GATHER_SCATTER_P (old_stmt_info);
     638         6295 :   STMT_VINFO_STRIDED_P (new_stmt_info)
     639         6295 :     = STMT_VINFO_STRIDED_P (old_stmt_info);
     640         6295 :   STMT_VINFO_SIMD_LANE_ACCESS_P (new_stmt_info)
     641         6295 :     = STMT_VINFO_SIMD_LANE_ACCESS_P (old_stmt_info);
     642         6295 : }
     643              : 
     644              : /* Permanently remove the statement described by STMT_INFO from the
     645              :    function.  */
     646              : 
     647              : void
     648      1511027 : vec_info::remove_stmt (stmt_vec_info stmt_info)
     649              : {
     650      1511027 :   gcc_assert (!stmt_info->pattern_stmt_p);
     651      1511027 :   set_vinfo_for_stmt (stmt_info->stmt, NULL);
     652      1511027 :   unlink_stmt_vdef (stmt_info->stmt);
     653      1511027 :   gimple_stmt_iterator si = gsi_for_stmt (stmt_info->stmt);
     654      1511027 :   gsi_remove (&si, true);
     655      1511027 :   release_defs (stmt_info->stmt);
     656      1511027 :   free_stmt_vec_info (stmt_info);
     657      1511027 : }
     658              : 
     659              : /* Replace the statement at GSI by NEW_STMT, both the vectorization
     660              :    information and the function itself.  STMT_INFO describes the statement
     661              :    at GSI.  */
     662              : 
     663              : void
     664         5400 : vec_info::replace_stmt (gimple_stmt_iterator *gsi, stmt_vec_info stmt_info,
     665              :                         gimple *new_stmt)
     666              : {
     667         5400 :   gimple *old_stmt = stmt_info->stmt;
     668         5400 :   gcc_assert (!stmt_info->pattern_stmt_p && old_stmt == gsi_stmt (*gsi));
     669         5400 :   gimple_set_uid (new_stmt, gimple_uid (old_stmt));
     670         5400 :   stmt_info->stmt = new_stmt;
     671         5400 :   gsi_replace (gsi, new_stmt, true);
     672         5400 : }
     673              : 
     674              : /* Insert stmts in SEQ on the VEC_INFO region entry.  If CONTEXT is
     675              :    not NULL it specifies whether to use the sub-region entry
     676              :    determined by it, currently used for loop vectorization to insert
     677              :    on the inner loop entry vs. the outer loop entry.  */
     678              : 
     679              : void
     680       104280 : vec_info::insert_seq_on_entry (stmt_vec_info context, gimple_seq seq)
     681              : {
     682       104280 :   if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (this))
     683              :     {
     684        19334 :       class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
     685        19334 :       basic_block new_bb;
     686        19334 :       edge pe;
     687              : 
     688        19334 :       if (context && nested_in_vect_loop_p (loop, context))
     689              :         loop = loop->inner;
     690              : 
     691        19334 :       pe = loop_preheader_edge (loop);
     692        19334 :       new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
     693        19334 :       gcc_assert (!new_bb);
     694              :     }
     695              :   else
     696              :     {
     697        84946 :       gimple_stmt_iterator gsi_region_begin = gsi_after_labels (bbs[0]);
     698              :       /* If the regions starts with a returns-twice call insert afte that.  */
     699        84946 :       if (gcall *call = safe_dyn_cast <gcall *> (gsi_stmt (gsi_region_begin)))
     700         4031 :         if (gimple_call_flags (call) & ECF_RETURNS_TWICE)
     701            2 :           gsi_next (&gsi_region_begin);
     702        84946 :       gsi_insert_seq_before (&gsi_region_begin, seq, GSI_SAME_STMT);
     703              :     }
     704       104280 : }
     705              : 
     706              : /* Like insert_seq_on_entry but just inserts the single stmt NEW_STMT.  */
     707              : 
     708              : void
     709         3280 : vec_info::insert_on_entry (stmt_vec_info context, gimple *new_stmt)
     710              : {
     711         3280 :   gimple_seq seq = NULL;
     712         3280 :   gimple_stmt_iterator gsi = gsi_start (seq);
     713         3280 :   gsi_insert_before_without_update (&gsi, new_stmt, GSI_SAME_STMT);
     714         3280 :   insert_seq_on_entry (context, seq);
     715         3280 : }
     716              : 
     717              : /* Create and initialize a new stmt_vec_info struct for STMT.  */
     718              : 
     719              : stmt_vec_info
     720     63788365 : vec_info::new_stmt_vec_info (gimple *stmt)
     721              : {
     722     63788365 :   stmt_vec_info res = XCNEW (class _stmt_vec_info);
     723     63788365 :   res->stmt = stmt;
     724              : 
     725     63788365 :   STMT_VINFO_RELEVANT (res) = vect_unused_in_scope;
     726     63788365 :   STMT_VINFO_VECTORIZABLE (res) = true;
     727     63788365 :   STMT_VINFO_REDUC_TYPE (res) = TREE_CODE_REDUCTION;
     728     63788365 :   STMT_VINFO_REDUC_CODE (res) = ERROR_MARK;
     729     63788365 :   STMT_VINFO_REDUC_IDX (res) = -1;
     730     63788365 :   STMT_VINFO_REDUC_DEF (res) = NULL;
     731     63788365 :   STMT_VINFO_SLP_VECT_ONLY (res) = false;
     732              : 
     733     63788365 :   if (is_a <loop_vec_info> (this)
     734      8179651 :       && gimple_code (stmt) == GIMPLE_PHI
     735     65213717 :       && is_loop_header_bb_p (gimple_bb (stmt)))
     736      1416623 :     STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
     737              :   else
     738     62371742 :     STMT_VINFO_DEF_TYPE (res) = vect_internal_def;
     739              : 
     740     63788365 :   STMT_SLP_TYPE (res) = not_vect;
     741              : 
     742              :   /* This is really "uninitialized" until vect_compute_data_ref_alignment.  */
     743     63788365 :   res->dr_aux.misalignment = DR_MISALIGNMENT_UNINITIALIZED;
     744              : 
     745     63788365 :   return res;
     746              : }
     747              : 
     748              : /* Associate STMT with INFO.  */
     749              : 
     750              : void
     751     65299392 : vec_info::set_vinfo_for_stmt (gimple *stmt, stmt_vec_info info, bool check_ro)
     752              : {
     753     65299392 :   unsigned int uid = gimple_uid (stmt);
     754     65299392 :   if (uid == 0)
     755              :     {
     756     63788365 :       gcc_assert (!check_ro || !stmt_vec_info_ro);
     757     63788365 :       gcc_checking_assert (info);
     758     63788365 :       uid = stmt_vec_infos.length () + 1;
     759     63788365 :       gimple_set_uid (stmt, uid);
     760     63788365 :       stmt_vec_infos.safe_push (info);
     761              :     }
     762              :   else
     763              :     {
     764      1511027 :       gcc_checking_assert (info == NULL);
     765      1511027 :       stmt_vec_infos[uid - 1] = info;
     766              :     }
     767     65299392 : }
     768              : 
     769              : /* Free the contents of stmt_vec_infos.  */
     770              : 
     771              : void
     772      2854346 : vec_info::free_stmt_vec_infos (void)
     773              : {
     774     72351403 :   for (stmt_vec_info &info : stmt_vec_infos)
     775     63788365 :     if (info != NULL)
     776     62277338 :       free_stmt_vec_info (info);
     777      2854346 :   stmt_vec_infos.release ();
     778      2854346 : }
     779              : 
     780              : /* Free STMT_INFO.  */
     781              : 
     782              : void
     783     63788365 : vec_info::free_stmt_vec_info (stmt_vec_info stmt_info)
     784              : {
     785     63788365 :   if (stmt_info->pattern_stmt_p)
     786              :     {
     787      2444503 :       gimple_set_bb (stmt_info->stmt, NULL);
     788      2444503 :       tree lhs = gimple_get_lhs (stmt_info->stmt);
     789      2444503 :       if (lhs && TREE_CODE (lhs) == SSA_NAME)
     790      2049029 :         release_ssa_name (lhs);
     791              :     }
     792              : 
     793     63788365 :   free (stmt_info);
     794     63788365 : }
     795              : 
     796              : /* Returns true if S1 dominates S2.  */
     797              : 
     798              : bool
     799      1763861 : vect_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
     800              : {
     801      1763861 :   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
     802              : 
     803              :   /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
     804              :      SSA_NAME.  Assume it lives at the beginning of function and
     805              :      thus dominates everything.  */
     806      1763861 :   if (!bb1 || s1 == s2)
     807              :     return true;
     808              : 
     809              :   /* If bb2 is NULL, it doesn't dominate any stmt with a bb.  */
     810      1146562 :   if (!bb2)
     811              :     return false;
     812              : 
     813      1146562 :   if (bb1 != bb2)
     814       357829 :     return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
     815              : 
     816              :   /* PHIs in the same basic block are assumed to be
     817              :      executed all in parallel, if only one stmt is a PHI,
     818              :      it dominates the other stmt in the same basic block.  */
     819       788733 :   if (gimple_code (s1) == GIMPLE_PHI)
     820              :     return true;
     821              : 
     822       665831 :   if (gimple_code (s2) == GIMPLE_PHI)
     823              :     return false;
     824              : 
     825              :   /* Inserted vectorized stmts all have UID 0 while the original stmts
     826              :      in the IL have UID increasing within a BB.  Walk from both sides
     827              :      until we find the other stmt or a stmt with UID != 0.  */
     828       642989 :   gimple_stmt_iterator gsi1 = gsi_for_stmt (s1);
     829      1220700 :   while (gimple_uid (gsi_stmt (gsi1)) == 0)
     830              :     {
     831       698536 :       gsi_next (&gsi1);
     832       698536 :       if (gsi_end_p (gsi1))
     833              :         return false;
     834       696892 :       if (gsi_stmt (gsi1) == s2)
     835              :         return true;
     836              :     }
     837       522164 :   if (gimple_uid (gsi_stmt (gsi1)) == -1u)
     838              :     return false;
     839              : 
     840       522164 :   gimple_stmt_iterator gsi2 = gsi_for_stmt (s2);
     841      1165709 :   while (gimple_uid (gsi_stmt (gsi2)) == 0)
     842              :     {
     843       657039 :       gsi_prev (&gsi2);
     844       657039 :       if (gsi_end_p (gsi2))
     845              :         return false;
     846       643553 :       if (gsi_stmt (gsi2) == s1)
     847              :         return true;
     848              :     }
     849       508670 :   if (gimple_uid (gsi_stmt (gsi2)) == -1u)
     850              :     return false;
     851              : 
     852       508670 :   if (gimple_uid (gsi_stmt (gsi1)) <= gimple_uid (gsi_stmt (gsi2)))
     853       399672 :     return true;
     854              :   return false;
     855              : }
     856              : 
     857              : /* A helper function to free scev and LOOP niter information, as well as
     858              :    clear loop constraint LOOP_C_FINITE.  */
     859              : 
     860              : void
     861        52778 : vect_free_loop_info_assumptions (class loop *loop)
     862              : {
     863        52778 :   scev_reset_htab ();
     864              :   /* We need to explicitly reset upper bound information since they are
     865              :      used even after free_numbers_of_iterations_estimates.  */
     866        52778 :   loop->any_upper_bound = false;
     867        52778 :   loop->any_likely_upper_bound = false;
     868        52778 :   free_numbers_of_iterations_estimates (loop);
     869        52778 :   loop_constraint_clear (loop, LOOP_C_FINITE);
     870        52778 : }
     871              : 
     872              : /* If LOOP has been versioned during ifcvt, return the internal call
     873              :    guarding it.  */
     874              : 
     875              : gimple *
     876       531005 : vect_loop_vectorized_call (class loop *loop, gcond **cond)
     877              : {
     878       531005 :   basic_block bb = loop_preheader_edge (loop)->src;
     879       981400 :   gimple *g;
     880      1431795 :   do
     881              :     {
     882       981400 :       g = *gsi_last_bb (bb);
     883       626947 :       if ((g && gimple_code (g) == GIMPLE_COND)
     884      2105477 :           || !single_succ_p (bb))
     885              :         break;
     886       593072 :       if (!single_pred_p (bb))
     887              :         break;
     888       450395 :       bb = single_pred (bb);
     889              :     }
     890              :   while (1);
     891       531005 :   if (g && gimple_code (g) == GIMPLE_COND)
     892              :     {
     893       381307 :       if (cond)
     894            0 :         *cond = as_a <gcond *> (g);
     895       381307 :       gimple_stmt_iterator gsi = gsi_for_stmt (g);
     896       381307 :       gsi_prev (&gsi);
     897       381307 :       if (!gsi_end_p (gsi))
     898              :         {
     899       348442 :           g = gsi_stmt (gsi);
     900       348442 :           if (gimple_call_internal_p (g, IFN_LOOP_VECTORIZED)
     901       348442 :               && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num
     902        26937 :                   || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num))
     903        54187 :             return g;
     904              :         }
     905              :     }
     906              :   return NULL;
     907              : }
     908              : 
     909              : /* If LOOP has been versioned during loop distribution, return the gurading
     910              :    internal call.  */
     911              : 
     912              : static gimple *
     913       497296 : vect_loop_dist_alias_call (class loop *loop, function *fun)
     914              : {
     915       497296 :   basic_block bb;
     916       497296 :   basic_block entry;
     917       497296 :   class loop *outer, *orig;
     918              : 
     919       497296 :   if (loop->orig_loop_num == 0)
     920              :     return NULL;
     921              : 
     922          167 :   orig = get_loop (fun, loop->orig_loop_num);
     923          167 :   if (orig == NULL)
     924              :     {
     925              :       /* The original loop is somehow destroyed.  Clear the information.  */
     926            0 :       loop->orig_loop_num = 0;
     927            0 :       return NULL;
     928              :     }
     929              : 
     930          167 :   if (loop != orig)
     931           95 :     bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header);
     932              :   else
     933           72 :     bb = loop_preheader_edge (loop)->src;
     934              : 
     935          167 :   outer = bb->loop_father;
     936          167 :   entry = ENTRY_BLOCK_PTR_FOR_FN (fun);
     937              : 
     938              :   /* Look upward in dominance tree.  */
     939          747 :   for (; bb != entry && flow_bb_inside_loop_p (outer, bb);
     940          580 :        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
     941              :     {
     942          696 :       gimple_stmt_iterator gsi = gsi_last_bb (bb);
     943          696 :       if (!safe_is_a <gcond *> (*gsi))
     944          184 :         continue;
     945              : 
     946          512 :       gsi_prev (&gsi);
     947          512 :       if (gsi_end_p (gsi))
     948            7 :         continue;
     949              : 
     950          505 :       gimple *g = gsi_stmt (gsi);
     951              :       /* The guarding internal function call must have the same distribution
     952              :          alias id.  */
     953          505 :       if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS)
     954          505 :           && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num))
     955       497296 :         return g;
     956              :     }
     957              :   return NULL;
     958              : }
     959              : 
     960              : /* Set the uids of all the statements in basic blocks inside loop
     961              :    represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
     962              :    call guarding the loop which has been if converted.  */
     963              : static void
     964         7009 : set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call,
     965              :                   function *fun)
     966              : {
     967         7009 :   tree arg = gimple_call_arg (loop_vectorized_call, 1);
     968         7009 :   basic_block *bbs;
     969         7009 :   unsigned int i;
     970         7009 :   class loop *scalar_loop = get_loop (fun, tree_to_shwi (arg));
     971              : 
     972         7009 :   LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop;
     973         7009 :   LOOP_VINFO_SCALAR_MAIN_EXIT (loop_vinfo)
     974         7009 :     = vec_init_loop_exit_info (scalar_loop);
     975         7009 :   gcc_checking_assert (vect_loop_vectorized_call (scalar_loop)
     976              :                        == loop_vectorized_call);
     977              :   /* If we are going to vectorize outer loop, prevent vectorization
     978              :      of the inner loop in the scalar loop - either the scalar loop is
     979              :      thrown away, so it is a wasted work, or is used only for
     980              :      a few iterations.  */
     981         7009 :   if (scalar_loop->inner)
     982              :     {
     983          100 :       gimple *g = vect_loop_vectorized_call (scalar_loop->inner);
     984          100 :       if (g)
     985              :         {
     986          100 :           arg = gimple_call_arg (g, 0);
     987          100 :           get_loop (fun, tree_to_shwi (arg))->dont_vectorize = true;
     988          100 :           fold_loop_internal_call (g, boolean_false_node);
     989              :         }
     990              :     }
     991         7009 :   bbs = get_loop_body (scalar_loop);
     992        45385 :   for (i = 0; i < scalar_loop->num_nodes; i++)
     993              :     {
     994        31367 :       basic_block bb = bbs[i];
     995        31367 :       gimple_stmt_iterator gsi;
     996        61382 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     997              :         {
     998        30015 :           gimple *phi = gsi_stmt (gsi);
     999        30015 :           gimple_set_uid (phi, 0);
    1000              :         }
    1001       147990 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1002              :         {
    1003        85256 :           gimple *stmt = gsi_stmt (gsi);
    1004        85256 :           gimple_set_uid (stmt, 0);
    1005              :         }
    1006              :     }
    1007         7009 :   free (bbs);
    1008         7009 : }
    1009              : 
    1010              : /* Generate vectorized code for LOOP and its epilogues.  */
    1011              : 
    1012              : static unsigned
    1013        64392 : vect_transform_loops (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
    1014              :                       loop_p loop, gimple *loop_vectorized_call,
    1015              :                       function *fun)
    1016              : {
    1017        64392 :   loop_vec_info loop_vinfo = loop_vec_info_for_loop (loop);
    1018              : 
    1019        64392 :   if (loop_vectorized_call)
    1020         7009 :     set_uid_loop_bbs (loop_vinfo, loop_vectorized_call, fun);
    1021              : 
    1022        64392 :   unsigned HOST_WIDE_INT bytes;
    1023        64392 :   if (dump_enabled_p ())
    1024              :     {
    1025        22992 :       if (GET_MODE_SIZE (loop_vinfo->vector_mode).is_constant (&bytes))
    1026        11496 :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
    1027              :                          "%sloop vectorized using %s%wu byte vectors and"
    1028              :                          " unroll factor %u\n",
    1029        11496 :                          LOOP_VINFO_EPILOGUE_P (loop_vinfo)
    1030              :                          ? "epilogue " : "",
    1031        11496 :                          LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
    1032              :                          ? "masked " : "", bytes,
    1033              :                          (unsigned int) LOOP_VINFO_VECT_FACTOR
    1034        11496 :                                                  (loop_vinfo).to_constant ());
    1035              :       else
    1036              :         dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
    1037              :                          "%sloop vectorized using variable length vectors\n",
    1038              :                          LOOP_VINFO_EPILOGUE_P (loop_vinfo)
    1039              :                          ? "epilogue " : "");
    1040              :     }
    1041              : 
    1042        64392 :   loop_p new_loop = vect_transform_loop (loop_vinfo,
    1043              :                                          loop_vectorized_call);
    1044              :   /* Now that the loop has been vectorized, allow it to be unrolled
    1045              :      etc.  */
    1046        64392 :   loop->force_vectorize = false;
    1047              : 
    1048        64392 :   if (loop->simduid)
    1049              :     {
    1050         1899 :       simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf);
    1051         1899 :       if (!simduid_to_vf_htab)
    1052         1536 :         simduid_to_vf_htab = new hash_table<simduid_to_vf> (15);
    1053         1899 :       simduid_to_vf_data->simduid = DECL_UID (loop->simduid);
    1054         1899 :       simduid_to_vf_data->vf = loop_vinfo->vectorization_factor;
    1055         1899 :       *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT)
    1056         1899 :           = simduid_to_vf_data;
    1057              :     }
    1058              : 
    1059              :   /* We should not have to update virtual SSA form here but some
    1060              :      transforms involve creating new virtual definitions which makes
    1061              :      updating difficult.
    1062              :      We delay the actual update to the end of the pass but avoid
    1063              :      confusing ourselves by forcing need_ssa_update_p () to false.  */
    1064        64392 :   unsigned todo = 0;
    1065        64392 :   if (need_ssa_update_p (cfun))
    1066              :     {
    1067          126 :       gcc_assert (loop_vinfo->any_known_not_updated_vssa);
    1068          126 :       fun->gimple_df->ssa_renaming_needed = false;
    1069          126 :       todo |= TODO_update_ssa_only_virtuals;
    1070              :     }
    1071        64392 :   gcc_assert (!need_ssa_update_p (cfun));
    1072              : 
    1073              :   /* Epilogue of vectorized loop must be vectorized too.  */
    1074        64392 :   if (new_loop)
    1075         6946 :     todo |= vect_transform_loops (simduid_to_vf_htab, new_loop, NULL, fun);
    1076              : 
    1077        64392 :   return todo;
    1078              : }
    1079              : 
    1080              : /* Try to vectorize LOOP.  */
    1081              : 
    1082              : static unsigned
    1083       481919 : try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
    1084              :                       unsigned *num_vectorized_loops, loop_p loop,
    1085              :                       gimple *loop_vectorized_call,
    1086              :                       gimple *loop_dist_alias_call,
    1087              :                       function *fun)
    1088              : {
    1089       481919 :   unsigned ret = 0;
    1090       481919 :   vec_info_shared shared;
    1091       481919 :   auto_purge_vect_location sentinel;
    1092       481919 :   vect_location = find_loop_location (loop);
    1093              : 
    1094       481919 :   if (LOCATION_LOCUS (vect_location.get_location_t ()) != UNKNOWN_LOCATION
    1095       481919 :       && dump_enabled_p ())
    1096        15636 :     dump_printf (MSG_NOTE | MSG_PRIORITY_INTERNALS,
    1097              :                  "\nAnalyzing loop at %s:%d\n",
    1098        15636 :                  LOCATION_FILE (vect_location.get_location_t ()),
    1099        31272 :                  LOCATION_LINE (vect_location.get_location_t ()));
    1100              : 
    1101              :   /* Try to analyze the loop, retaining an opt_problem if dump_enabled_p.  */
    1102       481919 :   opt_loop_vec_info loop_vinfo = vect_analyze_loop (loop, loop_vectorized_call,
    1103              :                                                     &shared);
    1104       481919 :   loop->aux = loop_vinfo;
    1105              : 
    1106       481919 :   if (!loop_vinfo)
    1107       424469 :     if (dump_enabled_p ())
    1108         6017 :       if (opt_problem *problem = loop_vinfo.get_problem ())
    1109              :         {
    1110         6017 :           dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
    1111              :                            "couldn't vectorize loop\n");
    1112         6017 :           problem->emit_and_clear ();
    1113              :         }
    1114              : 
    1115       481919 :   if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
    1116              :     {
    1117              :       /* Free existing information if loop is analyzed with some
    1118              :          assumptions.  */
    1119       424469 :       if (loop_constraint_set_p (loop, LOOP_C_FINITE))
    1120         7404 :         vect_free_loop_info_assumptions (loop);
    1121              : 
    1122              :       /* If we applied if-conversion then try to vectorize the
    1123              :          BB of innermost loops.
    1124              :          ???  Ideally BB vectorization would learn to vectorize
    1125              :          control flow by applying if-conversion on-the-fly, the
    1126              :          following retains the if-converted loop body even when
    1127              :          only non-if-converted parts took part in BB vectorization.  */
    1128       424469 :       if (flag_tree_slp_vectorize != 0
    1129       423383 :           && loop_vectorized_call
    1130        18538 :           && ! loop->inner)
    1131              :         {
    1132        17716 :           basic_block bb = loop->header;
    1133        17716 :           bool require_loop_vectorize = false;
    1134        35432 :           for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
    1135       700265 :                !gsi_end_p (gsi); gsi_next (&gsi))
    1136              :             {
    1137       683322 :               gimple *stmt = gsi_stmt (gsi);
    1138       683322 :               gcall *call = dyn_cast <gcall *> (stmt);
    1139         1218 :               if (call && gimple_call_internal_p (call))
    1140              :                 {
    1141         1112 :                   internal_fn ifn = gimple_call_internal_fn (call);
    1142         1112 :                   if (ifn == IFN_MASK_LOAD
    1143         1112 :                       || ifn == IFN_MASK_STORE
    1144          746 :                       || ifn == IFN_MASK_CALL
    1145              :                       /* Don't keep the if-converted parts when the ifn with
    1146              :                          specific type is not supported by the backend.  */
    1147         1839 :                       || (direct_internal_fn_p (ifn)
    1148          388 :                           && !direct_internal_fn_supported_p
    1149          388 :                           (call, OPTIMIZE_FOR_SPEED)))
    1150              :                     {
    1151              :                       require_loop_vectorize = true;
    1152              :                       break;
    1153              :                     }
    1154              :                 }
    1155       682549 :               gimple_set_uid (stmt, -1);
    1156       682549 :               gimple_set_visited (stmt, false);
    1157              :             }
    1158        17716 :           if (!require_loop_vectorize)
    1159              :             {
    1160        16943 :               tree arg = gimple_call_arg (loop_vectorized_call, 1);
    1161        16943 :               class loop *scalar_loop = get_loop (fun, tree_to_shwi (arg));
    1162        16943 :               if (vect_slp_if_converted_bb (bb, scalar_loop))
    1163              :                 {
    1164           64 :                   fold_loop_internal_call (loop_vectorized_call,
    1165              :                                            boolean_true_node);
    1166           64 :                   loop_vectorized_call = NULL;
    1167           64 :                   ret |= TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
    1168              :                 }
    1169              :             }
    1170              :         }
    1171              :       /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
    1172              :          loop, don't vectorize its inner loop; we'll attempt to
    1173              :          vectorize LOOP_VECTORIZED guarded inner loop of the scalar
    1174              :          loop version.  */
    1175        19624 :       if (loop_vectorized_call && loop->inner)
    1176          824 :         loop->inner->dont_vectorize = true;
    1177              :       return ret;
    1178              :     }
    1179              : 
    1180        57450 :   if (!dbg_cnt (vect_loop))
    1181              :     {
    1182              :       /* Free existing information if loop is analyzed with some
    1183              :          assumptions.  */
    1184            4 :       if (loop_constraint_set_p (loop, LOOP_C_FINITE))
    1185            0 :         vect_free_loop_info_assumptions (loop);
    1186              :       return ret;
    1187              :     }
    1188              : 
    1189        57446 :   (*num_vectorized_loops)++;
    1190              :   /* Transform LOOP and its epilogues.  */
    1191        57446 :   ret |= vect_transform_loops (simduid_to_vf_htab, loop,
    1192              :                                loop_vectorized_call, fun);
    1193              : 
    1194        57446 :   if (loop_vectorized_call)
    1195              :     {
    1196         7009 :       fold_loop_internal_call (loop_vectorized_call, boolean_true_node);
    1197         7009 :       ret |= TODO_cleanup_cfg;
    1198              :     }
    1199        57446 :   if (loop_dist_alias_call)
    1200              :     {
    1201            8 :       tree value = gimple_call_arg (loop_dist_alias_call, 1);
    1202            8 :       fold_loop_internal_call (loop_dist_alias_call, value);
    1203            8 :       ret |= TODO_cleanup_cfg;
    1204              :     }
    1205              : 
    1206              :   return ret;
    1207       481919 : }
    1208              : 
    1209              : /* Try to vectorize LOOP.  */
    1210              : 
    1211              : static unsigned
    1212       514881 : try_vectorize_loop (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
    1213              :                     unsigned *num_vectorized_loops, loop_p loop,
    1214              :                     function *fun)
    1215              : {
    1216       514881 :   if (!((flag_tree_loop_vectorize
    1217       510195 :          && optimize_loop_nest_for_speed_p (loop))
    1218        34817 :         || loop->force_vectorize))
    1219              :     return 0;
    1220              : 
    1221       481919 :   return try_vectorize_loop_1 (simduid_to_vf_htab, num_vectorized_loops, loop,
    1222              :                                vect_loop_vectorized_call (loop),
    1223       481919 :                                vect_loop_dist_alias_call (loop, fun), fun);
    1224              : }
    1225              : 
    1226              : 
    1227              : /* Loop autovectorization.  */
    1228              : 
    1229              : namespace {
    1230              : 
    1231              : const pass_data pass_data_vectorize =
    1232              : {
    1233              :   GIMPLE_PASS, /* type */
    1234              :   "vect", /* name */
    1235              :   OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
    1236              :   TV_TREE_VECTORIZATION, /* tv_id */
    1237              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    1238              :   0, /* properties_provided */
    1239              :   0, /* properties_destroyed */
    1240              :   0, /* todo_flags_start */
    1241              :   0, /* todo_flags_finish */
    1242              : };
    1243              : 
    1244              : class pass_vectorize : public gimple_opt_pass
    1245              : {
    1246              : public:
    1247       297180 :   pass_vectorize (gcc::context *ctxt)
    1248       594360 :     : gimple_opt_pass (pass_data_vectorize, ctxt)
    1249              :   {}
    1250              : 
    1251              :   /* opt_pass methods: */
    1252       248475 :   bool gate (function *fun) final override
    1253              :     {
    1254       248475 :       return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
    1255              :     }
    1256              : 
    1257              :   unsigned int execute (function *) final override;
    1258              : 
    1259              : }; // class pass_vectorize
    1260              : 
    1261              : /* Function vectorize_loops.
    1262              : 
    1263              :    Entry point to loop vectorization phase.  */
    1264              : 
    1265              : unsigned
    1266       214143 : pass_vectorize::execute (function *fun)
    1267              : {
    1268       214143 :   unsigned int i;
    1269       214143 :   unsigned int num_vectorized_loops = 0;
    1270       214143 :   unsigned int vect_loops_num;
    1271       214143 :   hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL;
    1272       214143 :   hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
    1273       214143 :   bool any_ifcvt_loops = false;
    1274       214143 :   unsigned ret = 0;
    1275              : 
    1276       214143 :   vect_loops_num = number_of_loops (fun);
    1277              : 
    1278              :   /* Bail out if there are no loops.  */
    1279       214143 :   if (vect_loops_num <= 1)
    1280              :     return 0;
    1281              : 
    1282       214143 :   vect_slp_init ();
    1283              : 
    1284       214143 :   if (fun->has_simduid_loops)
    1285         5607 :     note_simd_array_uses (&simd_array_to_simduid_htab, fun);
    1286              : 
    1287              :   /*  ----------- Analyze loops. -----------  */
    1288       214143 :   enable_ranger (fun);
    1289              : 
    1290              :   /* If some loop was duplicated, it gets bigger number
    1291              :      than all previously defined loops.  This fact allows us to run
    1292              :      only over initial loops skipping newly generated ones.  */
    1293      1189011 :   for (auto loop : loops_list (fun, 0))
    1294       546582 :     if (loop->dont_vectorize)
    1295              :       {
    1296        32625 :         any_ifcvt_loops = true;
    1297              :         /* If-conversion sometimes versions both the outer loop
    1298              :            (for the case when outer loop vectorization might be
    1299              :            desirable) as well as the inner loop in the scalar version
    1300              :            of the loop.  So we have:
    1301              :             if (LOOP_VECTORIZED (1, 3))
    1302              :               {
    1303              :                 loop1
    1304              :                   loop2
    1305              :               }
    1306              :             else
    1307              :               loop3 (copy of loop1)
    1308              :                 if (LOOP_VECTORIZED (4, 5))
    1309              :                   loop4 (copy of loop2)
    1310              :                 else
    1311              :                   loop5 (copy of loop4)
    1312              :            If loops' iteration gives us loop3 first (which has
    1313              :            dont_vectorize set), make sure to process loop1 before loop4;
    1314              :            so that we can prevent vectorization of loop4 if loop1
    1315              :            is successfully vectorized.  */
    1316        32625 :         if (loop->inner)
    1317              :           {
    1318         2176 :             gimple *loop_vectorized_call
    1319         2176 :               = vect_loop_vectorized_call (loop);
    1320         2176 :             if (loop_vectorized_call
    1321         2176 :                 && vect_loop_vectorized_call (loop->inner))
    1322              :               {
    1323          924 :                 tree arg = gimple_call_arg (loop_vectorized_call, 0);
    1324          924 :                 class loop *vector_loop
    1325          924 :                   = get_loop (fun, tree_to_shwi (arg));
    1326          924 :                 if (vector_loop && vector_loop != loop)
    1327              :                   {
    1328              :                     /* Make sure we don't vectorize it twice.  */
    1329          924 :                     vector_loop->dont_vectorize = true;
    1330          924 :                     ret |= try_vectorize_loop (simduid_to_vf_htab,
    1331              :                                                &num_vectorized_loops,
    1332              :                                                vector_loop, fun);
    1333              :                   }
    1334              :               }
    1335              :           }
    1336              :       }
    1337              :     else
    1338       513957 :       ret |= try_vectorize_loop (simduid_to_vf_htab, &num_vectorized_loops,
    1339       214143 :                                  loop, fun);
    1340              : 
    1341       214143 :   vect_location = dump_user_location_t ();
    1342              : 
    1343       214143 :   statistics_counter_event (fun, "Vectorized loops", num_vectorized_loops);
    1344       214143 :   if (dump_enabled_p ()
    1345       214143 :       || (num_vectorized_loops > 0 && dump_enabled_p ()))
    1346        12196 :     dump_printf_loc (MSG_NOTE, vect_location,
    1347              :                      "vectorized %u loops in function.\n",
    1348              :                      num_vectorized_loops);
    1349              : 
    1350              :   /*  ----------- Finalize. -----------  */
    1351       214143 :   disable_ranger (fun);
    1352              : 
    1353       214143 :   if (any_ifcvt_loops)
    1354       289154 :     for (i = 1; i < number_of_loops (fun); i++)
    1355              :       {
    1356       123871 :         class loop *loop = get_loop (fun, i);
    1357       123871 :         if (loop && loop->dont_vectorize)
    1358              :           {
    1359        34181 :             gimple *g = vect_loop_vectorized_call (loop);
    1360        34181 :             if (g)
    1361              :               {
    1362        18804 :                 fold_loop_internal_call (g, boolean_false_node);
    1363        18804 :                 loop->dont_vectorize = false;
    1364        18804 :                 ret |= TODO_cleanup_cfg;
    1365        18804 :                 g = NULL;
    1366              :               }
    1367              :             else
    1368        15377 :               g = vect_loop_dist_alias_call (loop, fun);
    1369              : 
    1370        34181 :             if (g)
    1371              :               {
    1372           30 :                 fold_loop_internal_call (g, boolean_false_node);
    1373           30 :                 loop->dont_vectorize = false;
    1374           30 :                 ret |= TODO_cleanup_cfg;
    1375              :               }
    1376              :           }
    1377              :       }
    1378              : 
    1379              :   /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins.  */
    1380       214143 :   if (fun->has_simduid_loops)
    1381              :     {
    1382         5607 :       adjust_simduid_builtins (simduid_to_vf_htab, fun);
    1383              :       /* Avoid stale SCEV cache entries for the SIMD_LANE defs.  */
    1384         5607 :       scev_reset ();
    1385              :     }
    1386              :   /* Shrink any "omp array simd" temporary arrays to the
    1387              :      actual vectorization factors.  */
    1388       214143 :   if (simd_array_to_simduid_htab)
    1389         2205 :     shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab);
    1390       214143 :   delete simduid_to_vf_htab;
    1391       214143 :   fun->has_simduid_loops = false;
    1392              : 
    1393       214143 :   if (num_vectorized_loops > 0)
    1394              :     {
    1395              :       /* We are collecting some corner cases where we need to update
    1396              :          virtual SSA form via the TODO but delete the queued update-SSA
    1397              :          state.  Force renaming if we think that might be necessary.  */
    1398        38755 :       if (ret & TODO_update_ssa_only_virtuals)
    1399           94 :         mark_virtual_operands_for_renaming (cfun);
    1400              :       /* If we vectorized any loop only virtual SSA form needs to be updated.
    1401              :          ???  Also while we try hard to update loop-closed SSA form we fail
    1402              :          to properly do this in some corner-cases (see PR56286).  */
    1403        38755 :       rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals);
    1404        38755 :       ret |= TODO_cleanup_cfg;
    1405              :     }
    1406              : 
    1407      1916948 :   for (i = 1; i < number_of_loops (fun); i++)
    1408              :     {
    1409       744331 :       loop_vec_info loop_vinfo;
    1410       744331 :       bool has_mask_store;
    1411              : 
    1412       744331 :       class loop *loop = get_loop (fun, i);
    1413       744331 :       if (!loop || !loop->aux)
    1414       679935 :         continue;
    1415        64396 :       loop_vinfo = (loop_vec_info) loop->aux;
    1416        64396 :       has_mask_store = LOOP_VINFO_HAS_MASK_STORE (loop_vinfo);
    1417        64396 :       delete loop_vinfo;
    1418        64396 :       if (has_mask_store
    1419        64396 :           && targetm.vectorize.empty_mask_is_expensive (IFN_MASK_STORE))
    1420          499 :         optimize_mask_stores (loop);
    1421              : 
    1422        64396 :       auto_bitmap exit_bbs;
    1423              :       /* Perform local CSE, this esp. helps because we emit code for
    1424              :          predicates that need to be shared for optimal predicate usage.
    1425              :          However reassoc will re-order them and prevent CSE from working
    1426              :          as it should.  CSE only the loop body, not the entry.  */
    1427        64396 :       auto_vec<edge> exits = get_loop_exit_edges (loop);
    1428       259196 :       for (edge exit : exits)
    1429        66008 :         bitmap_set_bit (exit_bbs, exit->dest->index);
    1430              : 
    1431        64396 :       edge entry = EDGE_PRED (loop_preheader_edge (loop)->src, 0);
    1432        64396 :       do_rpo_vn (fun, entry, exit_bbs);
    1433              : 
    1434        64396 :       loop->aux = NULL;
    1435        64396 :     }
    1436              : 
    1437       214143 :   vect_slp_fini ();
    1438              : 
    1439       214143 :   return ret;
    1440              : }
    1441              : 
    1442              : } // anon namespace
    1443              : 
    1444              : gimple_opt_pass *
    1445       297180 : make_pass_vectorize (gcc::context *ctxt)
    1446              : {
    1447       297180 :   return new pass_vectorize (ctxt);
    1448              : }
    1449              : 
    1450              : /* Entry point to the simduid cleanup pass.  */
    1451              : 
    1452              : namespace {
    1453              : 
    1454              : const pass_data pass_data_simduid_cleanup =
    1455              : {
    1456              :   GIMPLE_PASS, /* type */
    1457              :   "simduid", /* name */
    1458              :   OPTGROUP_NONE, /* optinfo_flags */
    1459              :   TV_NONE, /* tv_id */
    1460              :   ( PROP_ssa | PROP_cfg ), /* properties_required */
    1461              :   0, /* properties_provided */
    1462              :   0, /* properties_destroyed */
    1463              :   0, /* todo_flags_start */
    1464              :   0, /* todo_flags_finish */
    1465              : };
    1466              : 
    1467              : class pass_simduid_cleanup : public gimple_opt_pass
    1468              : {
    1469              : public:
    1470       594360 :   pass_simduid_cleanup (gcc::context *ctxt)
    1471      1188720 :     : gimple_opt_pass (pass_data_simduid_cleanup, ctxt)
    1472              :   {}
    1473              : 
    1474              :   /* opt_pass methods: */
    1475       297180 :   opt_pass * clone () final override
    1476              :   {
    1477       297180 :     return new pass_simduid_cleanup (m_ctxt);
    1478              :   }
    1479      2580935 :   bool gate (function *fun) final override { return fun->has_simduid_loops; }
    1480              :   unsigned int execute (function *) final override;
    1481              : 
    1482              : }; // class pass_simduid_cleanup
    1483              : 
    1484              : unsigned int
    1485         2196 : pass_simduid_cleanup::execute (function *fun)
    1486              : {
    1487         2196 :   hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
    1488              : 
    1489         2196 :   note_simd_array_uses (&simd_array_to_simduid_htab, fun);
    1490              : 
    1491              :   /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins.  */
    1492         2196 :   adjust_simduid_builtins (NULL, fun);
    1493              : 
    1494              :   /* Shrink any "omp array simd" temporary arrays to the
    1495              :      actual vectorization factors.  */
    1496         2196 :   if (simd_array_to_simduid_htab)
    1497            4 :     shrink_simd_arrays (simd_array_to_simduid_htab, NULL);
    1498         2196 :   fun->has_simduid_loops = false;
    1499         2196 :   return 0;
    1500              : }
    1501              : 
    1502              : }  // anon namespace
    1503              : 
    1504              : gimple_opt_pass *
    1505       297180 : make_pass_simduid_cleanup (gcc::context *ctxt)
    1506              : {
    1507       297180 :   return new pass_simduid_cleanup (ctxt);
    1508              : }
    1509              : 
    1510              : 
    1511              : /*  Entry point to basic block SLP phase.  */
    1512              : 
    1513              : namespace {
    1514              : 
    1515              : const pass_data pass_data_slp_vectorize =
    1516              : {
    1517              :   GIMPLE_PASS, /* type */
    1518              :   "slp", /* name */
    1519              :   OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
    1520              :   TV_TREE_SLP_VECTORIZATION, /* tv_id */
    1521              :   ( PROP_ssa | PROP_cfg ), /* properties_required */
    1522              :   0, /* properties_provided */
    1523              :   0, /* properties_destroyed */
    1524              :   0, /* todo_flags_start */
    1525              :   TODO_update_ssa, /* todo_flags_finish */
    1526              : };
    1527              : 
    1528              : class pass_slp_vectorize : public gimple_opt_pass
    1529              : {
    1530              : public:
    1531       594360 :   pass_slp_vectorize (gcc::context *ctxt)
    1532      1188720 :     : gimple_opt_pass (pass_data_slp_vectorize, ctxt)
    1533              :   {}
    1534              : 
    1535              :   /* opt_pass methods: */
    1536       297180 :   opt_pass * clone () final override { return new pass_slp_vectorize (m_ctxt); }
    1537      1063023 :   bool gate (function *) final override { return flag_tree_slp_vectorize != 0; }
    1538              :   unsigned int execute (function *) final override;
    1539              : 
    1540              : }; // class pass_slp_vectorize
    1541              : 
    1542              : unsigned int
    1543       925882 : pass_slp_vectorize::execute (function *fun)
    1544              : {
    1545       925882 :   auto_purge_vect_location sentinel;
    1546       925882 :   basic_block bb;
    1547              : 
    1548       925882 :   bool in_loop_pipeline = scev_initialized_p ();
    1549       925882 :   if (!in_loop_pipeline)
    1550              :     {
    1551       713450 :       loop_optimizer_init (LOOPS_NORMAL);
    1552       713450 :       scev_initialize ();
    1553              :     }
    1554              : 
    1555              :   /* Mark all stmts as not belonging to the current region and unvisited.  */
    1556     11860734 :   FOR_EACH_BB_FN (bb, fun)
    1557              :     {
    1558     15809394 :       for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    1559      4874542 :            gsi_next (&gsi))
    1560              :         {
    1561      4874542 :           gphi *stmt = gsi.phi ();
    1562      4874542 :           gimple_set_uid (stmt, -1);
    1563      4874542 :           gimple_set_visited (stmt, false);
    1564              :         }
    1565    106298953 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    1566     84429249 :            gsi_next (&gsi))
    1567              :         {
    1568     84429249 :           gimple *stmt = gsi_stmt (gsi);
    1569     84429249 :           gimple_set_uid (stmt, -1);
    1570     84429249 :           gimple_set_visited (stmt, false);
    1571              :         }
    1572              :     }
    1573              : 
    1574       925882 :   vect_slp_init ();
    1575              : 
    1576       925882 :   vect_slp_function (fun);
    1577              : 
    1578       925882 :   vect_slp_fini ();
    1579              : 
    1580       925882 :   if (!in_loop_pipeline)
    1581              :     {
    1582       713450 :       scev_finalize ();
    1583       713450 :       loop_optimizer_finalize ();
    1584              :     }
    1585              : 
    1586      1851764 :   return 0;
    1587       925882 : }
    1588              : 
    1589              : } // anon namespace
    1590              : 
    1591              : gimple_opt_pass *
    1592       297180 : make_pass_slp_vectorize (gcc::context *ctxt)
    1593              : {
    1594       297180 :   return new pass_slp_vectorize (ctxt);
    1595              : }
    1596              : 
    1597              : 
    1598              : /* Increase alignment of global arrays to improve vectorization potential.
    1599              :    TODO:
    1600              :    - Consider also structs that have an array field.
    1601              :    - Use ipa analysis to prune arrays that can't be vectorized?
    1602              :      This should involve global alignment analysis and in the future also
    1603              :      array padding.  */
    1604              : 
    1605              : static unsigned get_vec_alignment_for_type (tree);
    1606              : static hash_map<tree, unsigned> *type_align_map;
    1607              : 
    1608              : /* Return alignment of array's vector type corresponding to scalar type.
    1609              :    0 if no vector type exists.  */
    1610              : static unsigned
    1611            0 : get_vec_alignment_for_array_type (tree type)
    1612              : {
    1613            0 :   gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
    1614            0 :   poly_uint64 array_size, vector_size;
    1615              : 
    1616            0 :   tree scalar_type = strip_array_types (type);
    1617            0 :   tree vectype = get_related_vectype_for_scalar_type (VOIDmode, scalar_type);
    1618            0 :   if (!vectype
    1619            0 :       || !poly_int_tree_p (TYPE_SIZE (type), &array_size)
    1620            0 :       || !poly_int_tree_p (TYPE_SIZE (vectype), &vector_size)
    1621            0 :       || maybe_lt (array_size, vector_size))
    1622              :     return 0;
    1623              : 
    1624            0 :   return TYPE_ALIGN (vectype);
    1625              : }
    1626              : 
    1627              : /* Return alignment of field having maximum alignment of vector type
    1628              :    corresponding to it's scalar type. For now, we only consider fields whose
    1629              :    offset is a multiple of it's vector alignment.
    1630              :    0 if no suitable field is found.  */
    1631              : static unsigned
    1632            0 : get_vec_alignment_for_record_type (tree type)
    1633              : {
    1634            0 :   gcc_assert (TREE_CODE (type) == RECORD_TYPE);
    1635              : 
    1636            0 :   unsigned max_align = 0, alignment;
    1637            0 :   HOST_WIDE_INT offset;
    1638            0 :   tree offset_tree;
    1639              : 
    1640            0 :   if (TYPE_PACKED (type))
    1641              :     return 0;
    1642              : 
    1643            0 :   unsigned *slot = type_align_map->get (type);
    1644            0 :   if (slot)
    1645            0 :     return *slot;
    1646              : 
    1647            0 :   for (tree field = first_field (type);
    1648            0 :        field != NULL_TREE;
    1649            0 :        field = DECL_CHAIN (field))
    1650              :     {
    1651              :       /* Skip if not FIELD_DECL or if alignment is set by user.  */
    1652            0 :       if (TREE_CODE (field) != FIELD_DECL
    1653            0 :           || DECL_USER_ALIGN (field)
    1654            0 :           || DECL_ARTIFICIAL (field))
    1655            0 :         continue;
    1656              : 
    1657              :       /* We don't need to process the type further if offset is variable,
    1658              :          since the offsets of remaining members will also be variable.  */
    1659            0 :       if (TREE_CODE (DECL_FIELD_OFFSET (field)) != INTEGER_CST
    1660            0 :           || TREE_CODE (DECL_FIELD_BIT_OFFSET (field)) != INTEGER_CST)
    1661              :         break;
    1662              : 
    1663              :       /* Similarly stop processing the type if offset_tree
    1664              :          does not fit in unsigned HOST_WIDE_INT.  */
    1665            0 :       offset_tree = bit_position (field);
    1666            0 :       if (!tree_fits_uhwi_p (offset_tree))
    1667              :         break;
    1668              : 
    1669            0 :       offset = tree_to_uhwi (offset_tree);
    1670            0 :       alignment = get_vec_alignment_for_type (TREE_TYPE (field));
    1671              : 
    1672              :       /* Get maximum alignment of vectorized field/array among those members
    1673              :          whose offset is multiple of the vector alignment.  */
    1674            0 :       if (alignment
    1675            0 :           && (offset % alignment == 0)
    1676            0 :           && (alignment > max_align))
    1677            0 :         max_align = alignment;
    1678              :     }
    1679              : 
    1680            0 :   type_align_map->put (type, max_align);
    1681            0 :   return max_align;
    1682              : }
    1683              : 
    1684              : /* Return alignment of vector type corresponding to decl's scalar type
    1685              :    or 0 if it doesn't exist or the vector alignment is lesser than
    1686              :    decl's alignment.  */
    1687              : static unsigned
    1688            0 : get_vec_alignment_for_type (tree type)
    1689              : {
    1690            0 :   if (type == NULL_TREE)
    1691              :     return 0;
    1692              : 
    1693            0 :   gcc_assert (TYPE_P (type));
    1694              : 
    1695            0 :   static unsigned alignment = 0;
    1696            0 :   switch (TREE_CODE (type))
    1697              :     {
    1698            0 :       case ARRAY_TYPE:
    1699            0 :         alignment = get_vec_alignment_for_array_type (type);
    1700            0 :         break;
    1701            0 :       case RECORD_TYPE:
    1702            0 :         alignment = get_vec_alignment_for_record_type (type);
    1703            0 :         break;
    1704            0 :       default:
    1705            0 :         alignment = 0;
    1706            0 :         break;
    1707              :     }
    1708              : 
    1709            0 :   return (alignment > TYPE_ALIGN (type)) ? alignment : 0;
    1710              : }
    1711              : 
    1712              : /* Entry point to increase_alignment pass.  */
    1713              : static unsigned int
    1714            0 : increase_alignment (void)
    1715              : {
    1716            0 :   varpool_node *vnode;
    1717              : 
    1718            0 :   vect_location = dump_user_location_t ();
    1719            0 :   type_align_map = new hash_map<tree, unsigned>;
    1720              : 
    1721              :   /* Increase the alignment of all global arrays for vectorization.  */
    1722            0 :   FOR_EACH_DEFINED_VARIABLE (vnode)
    1723              :     {
    1724            0 :       tree decl = vnode->decl;
    1725            0 :       unsigned int alignment;
    1726              : 
    1727            0 :       if ((decl_in_symtab_p (decl)
    1728            0 :           && !symtab_node::get (decl)->can_increase_alignment_p ())
    1729            0 :           || DECL_USER_ALIGN (decl) || DECL_ARTIFICIAL (decl))
    1730            0 :         continue;
    1731              : 
    1732            0 :       alignment = get_vec_alignment_for_type (TREE_TYPE (decl));
    1733            0 :       if (alignment && vect_can_force_dr_alignment_p (decl, alignment))
    1734              :         {
    1735            0 :           vnode->increase_alignment (alignment);
    1736            0 :           if (dump_enabled_p ())
    1737            0 :             dump_printf (MSG_NOTE, "Increasing alignment of decl: %T\n", decl);
    1738              :         }
    1739              :     }
    1740              : 
    1741            0 :   delete type_align_map;
    1742            0 :   return 0;
    1743              : }
    1744              : 
    1745              : 
    1746              : namespace {
    1747              : 
    1748              : const pass_data pass_data_ipa_increase_alignment =
    1749              : {
    1750              :   SIMPLE_IPA_PASS, /* type */
    1751              :   "increase_alignment", /* name */
    1752              :   OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
    1753              :   TV_IPA_OPT, /* tv_id */
    1754              :   0, /* properties_required */
    1755              :   0, /* properties_provided */
    1756              :   0, /* properties_destroyed */
    1757              :   0, /* todo_flags_start */
    1758              :   0, /* todo_flags_finish */
    1759              : };
    1760              : 
    1761              : class pass_ipa_increase_alignment : public simple_ipa_opt_pass
    1762              : {
    1763              : public:
    1764       297180 :   pass_ipa_increase_alignment (gcc::context *ctxt)
    1765       594360 :     : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt)
    1766              :   {}
    1767              : 
    1768              :   /* opt_pass methods: */
    1769       239073 :   bool gate (function *) final override
    1770              :     {
    1771       239073 :       return flag_section_anchors && flag_tree_loop_vectorize;
    1772              :     }
    1773              : 
    1774            0 :   unsigned int execute (function *) final override
    1775              :   {
    1776            0 :     return increase_alignment ();
    1777              :   }
    1778              : 
    1779              : }; // class pass_ipa_increase_alignment
    1780              : 
    1781              : } // anon namespace
    1782              : 
    1783              : simple_ipa_opt_pass *
    1784       297180 : make_pass_ipa_increase_alignment (gcc::context *ctxt)
    1785              : {
    1786       297180 :   return new pass_ipa_increase_alignment (ctxt);
    1787              : }
    1788              : 
    1789              : /* If the condition represented by T is a comparison or the SSA name
    1790              :    result of a comparison, extract the comparison's operands.  Represent
    1791              :    T as NE_EXPR <T, 0> otherwise.  */
    1792              : 
    1793              : void
    1794        60843 : scalar_cond_masked_key::get_cond_ops_from_tree (tree t)
    1795              : {
    1796        60843 :   if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_comparison)
    1797              :     {
    1798            0 :       this->code = TREE_CODE (t);
    1799            0 :       this->op0 = TREE_OPERAND (t, 0);
    1800            0 :       this->op1 = TREE_OPERAND (t, 1);
    1801            0 :       this->inverted_p = false;
    1802            0 :       return;
    1803              :     }
    1804              : 
    1805        60843 :   if (TREE_CODE (t) == SSA_NAME)
    1806        26616 :     if (gassign *stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (t)))
    1807              :       {
    1808        26616 :         tree_code code = gimple_assign_rhs_code (stmt);
    1809        26616 :         if (TREE_CODE_CLASS (code) == tcc_comparison)
    1810              :           {
    1811        18297 :             this->code = code;
    1812        18297 :             this->op0 = gimple_assign_rhs1 (stmt);
    1813        18297 :             this->op1 = gimple_assign_rhs2 (stmt);
    1814        18297 :             this->inverted_p = false;
    1815        18297 :             return;
    1816              :           }
    1817         8319 :         else if (code == BIT_NOT_EXPR)
    1818              :           {
    1819         3475 :             tree n_op = gimple_assign_rhs1 (stmt);
    1820         3475 :             if ((stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (n_op))))
    1821              :               {
    1822         3475 :                 code = gimple_assign_rhs_code (stmt);
    1823         3475 :                 if (TREE_CODE_CLASS (code) == tcc_comparison)
    1824              :                   {
    1825         3439 :                     this->code = code;
    1826         3439 :                     this->op0 = gimple_assign_rhs1 (stmt);
    1827         3439 :                     this->op1 = gimple_assign_rhs2 (stmt);
    1828         3439 :                     this->inverted_p = true;
    1829         3439 :                     return;
    1830              :                   }
    1831              :               }
    1832              :           }
    1833              :       }
    1834              : 
    1835        39107 :   this->code = NE_EXPR;
    1836        39107 :   this->op0 = t;
    1837        39107 :   this->op1 = build_zero_cst (TREE_TYPE (t));
    1838        39107 :   this->inverted_p = false;
    1839              : }
    1840              : 
    1841              : /* See the comment above the declaration for details.  */
    1842              : 
    1843              : unsigned int
    1844            0 : vector_costs::add_stmt_cost (int count, vect_cost_for_stmt kind,
    1845              :                              stmt_vec_info stmt_info, slp_tree,
    1846              :                              tree vectype, int misalign,
    1847              :                              vect_cost_model_location where)
    1848              : {
    1849            0 :   unsigned int cost
    1850            0 :     = builtin_vectorization_cost (kind, vectype, misalign) * count;
    1851            0 :   return record_stmt_cost (stmt_info, where, cost);
    1852              : }
    1853              : 
    1854              : unsigned int
    1855      2835405 : vector_costs::add_slp_cost (slp_tree,
    1856              :                             const array_slice<stmt_info_for_cost> &cost_vec)
    1857              : {
    1858      2835405 :   unsigned int sum = 0;
    1859      6401862 :   for (auto item : cost_vec)
    1860      3566457 :     sum += ::add_stmt_cost (this, item.count, item.kind, item.stmt_info,
    1861              :                             item.node, item.vectype, item.misalign, item.where);
    1862      2835405 :   return sum;
    1863              : }
    1864              : 
    1865              : /* See the comment above the declaration for details.  */
    1866              : 
    1867              : void
    1868      1971290 : vector_costs::finish_cost (const vector_costs *)
    1869              : {
    1870      1971290 :   gcc_assert (!m_finished);
    1871      1971290 :   m_finished = true;
    1872      1971290 : }
    1873              : 
    1874              : /* Record a base cost of COST units against WHERE.  If STMT_INFO is
    1875              :    nonnull, use it to adjust the cost based on execution frequency
    1876              :    (where appropriate).  */
    1877              : 
    1878              : unsigned int
    1879            0 : vector_costs::record_stmt_cost (stmt_vec_info stmt_info,
    1880              :                                 vect_cost_model_location where,
    1881              :                                 unsigned int cost)
    1882              : {
    1883            0 :   cost = adjust_cost_for_freq (stmt_info, where, cost);
    1884            0 :   m_costs[where] += cost;
    1885            0 :   return cost;
    1886              : }
    1887              : 
    1888              : /* COST is the base cost we have calculated for an operation in location WHERE.
    1889              :    If STMT_INFO is nonnull, use it to adjust the cost based on execution
    1890              :    frequency (where appropriate).  Return the adjusted cost.  */
    1891              : 
    1892              : unsigned int
    1893      8120880 : vector_costs::adjust_cost_for_freq (stmt_vec_info stmt_info,
    1894              :                                     vect_cost_model_location where,
    1895              :                                     unsigned int cost)
    1896              : {
    1897              :   /* Statements in an inner loop relative to the loop being
    1898              :      vectorized are weighted more heavily.  The value here is
    1899              :      arbitrary and could potentially be improved with analysis.  */
    1900      8120880 :   if (where == vect_body
    1901      8120880 :       && stmt_info
    1902      8120880 :       && stmt_in_inner_loop_p (m_vinfo, stmt_info))
    1903              :     {
    1904        11352 :       loop_vec_info loop_vinfo = as_a<loop_vec_info> (m_vinfo);
    1905        11352 :       cost *= LOOP_VINFO_INNER_LOOP_COST_FACTOR (loop_vinfo);
    1906              :     }
    1907      8120880 :   return cost;
    1908              : }
    1909              : 
    1910              : /* See the comment above the declaration for details.  */
    1911              : 
    1912              : bool
    1913        34603 : vector_costs::better_main_loop_than_p (const vector_costs *other) const
    1914              : {
    1915        34603 :   int diff = compare_inside_loop_cost (other);
    1916        34603 :   if (diff != 0)
    1917        34388 :     return diff < 0;
    1918              : 
    1919              :   /* If there's nothing to choose between the loop bodies, see whether
    1920              :      there's a difference in the prologue and epilogue costs.  */
    1921          215 :   diff = compare_outside_loop_cost (other);
    1922          215 :   if (diff != 0)
    1923          149 :     return diff < 0;
    1924              : 
    1925              :   return false;
    1926              : }
    1927              : 
    1928              : 
    1929              : /* See the comment above the declaration for details.  */
    1930              : 
    1931              : bool
    1932         1485 : vector_costs::better_epilogue_loop_than_p (const vector_costs *other,
    1933              :                                            loop_vec_info main_loop) const
    1934              : {
    1935         1485 :   loop_vec_info this_loop_vinfo = as_a<loop_vec_info> (this->m_vinfo);
    1936         1485 :   loop_vec_info other_loop_vinfo = as_a<loop_vec_info> (other->m_vinfo);
    1937              : 
    1938         1485 :   poly_int64 this_vf = LOOP_VINFO_VECT_FACTOR (this_loop_vinfo);
    1939         1485 :   poly_int64 other_vf = LOOP_VINFO_VECT_FACTOR (other_loop_vinfo);
    1940              : 
    1941         1485 :   poly_uint64 main_poly_vf = LOOP_VINFO_VECT_FACTOR (main_loop);
    1942         1485 :   unsigned HOST_WIDE_INT main_vf;
    1943         1485 :   unsigned HOST_WIDE_INT other_factor, this_factor, other_cost, this_cost;
    1944              :   /* If we can determine how many iterations are left for the epilogue
    1945              :      loop, that is if both the main loop's vectorization factor and number
    1946              :      of iterations are constant, then we use them to calculate the cost of
    1947              :      the epilogue loop together with a 'likely value' for the epilogues
    1948              :      vectorization factor.  Otherwise we use the main loop's vectorization
    1949              :      factor and the maximum poly value for the epilogue's.  If the target
    1950              :      has not provided with a sensible upper bound poly vectorization
    1951              :      factors are likely to be favored over constant ones.  */
    1952         1485 :   if (main_poly_vf.is_constant (&main_vf)
    1953         1485 :       && LOOP_VINFO_NITERS_KNOWN_P (main_loop))
    1954              :     {
    1955           91 :       unsigned HOST_WIDE_INT niters
    1956           91 :         = LOOP_VINFO_INT_NITERS (main_loop) % main_vf;
    1957           91 :       HOST_WIDE_INT other_likely_vf
    1958           91 :         = estimated_poly_value (other_vf, POLY_VALUE_LIKELY);
    1959           91 :       HOST_WIDE_INT this_likely_vf
    1960           91 :         = estimated_poly_value (this_vf, POLY_VALUE_LIKELY);
    1961              : 
    1962              :       /* If the epilogue is using partial vectors we account for the
    1963              :          partial iteration here too.  */
    1964           91 :       other_factor = niters / other_likely_vf;
    1965           91 :       if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo)
    1966            0 :           && niters % other_likely_vf != 0)
    1967            0 :         other_factor++;
    1968              : 
    1969           91 :       this_factor = niters / this_likely_vf;
    1970           91 :       if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo)
    1971            0 :           && niters % this_likely_vf != 0)
    1972            0 :         this_factor++;
    1973              :     }
    1974              :   else
    1975              :     {
    1976              :       unsigned HOST_WIDE_INT main_vf_max
    1977         1394 :         = estimated_poly_value (main_poly_vf, POLY_VALUE_MAX);
    1978         1394 :       unsigned HOST_WIDE_INT other_vf_max
    1979         1394 :         = estimated_poly_value (other_vf, POLY_VALUE_MAX);
    1980         1394 :       unsigned HOST_WIDE_INT this_vf_max
    1981         1394 :         = estimated_poly_value (this_vf, POLY_VALUE_MAX);
    1982              : 
    1983         1394 :       other_factor = CEIL (main_vf_max, other_vf_max);
    1984         1394 :       this_factor = CEIL (main_vf_max, this_vf_max);
    1985              : 
    1986              :       /* If the loop is not using partial vectors then it will iterate one
    1987              :          time less than one that does.  It is safe to subtract one here,
    1988              :          because the main loop's vf is always at least 2x bigger than that
    1989              :          of an epilogue.  */
    1990         1394 :       if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo))
    1991         1379 :         other_factor -= 1;
    1992         1394 :       if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo))
    1993         1393 :         this_factor -= 1;
    1994              :     }
    1995              : 
    1996              :   /* Compute the costs by multiplying the inside costs with the factor and
    1997              :      add the outside costs for a more complete picture.  The factor is the
    1998              :      amount of times we are expecting to iterate this epilogue.  */
    1999         1485 :   other_cost = other->body_cost () * other_factor;
    2000         1485 :   this_cost = this->body_cost () * this_factor;
    2001         1485 :   other_cost += other->outside_cost ();
    2002         1485 :   this_cost += this->outside_cost ();
    2003         1485 :   return this_cost < other_cost;
    2004              : }
    2005              : 
    2006              : /* A <=>-style subroutine of better_main_loop_than_p.  Check whether we can
    2007              :    determine the return value of better_main_loop_than_p by comparing the
    2008              :    inside (loop body) costs of THIS and OTHER.  Return:
    2009              : 
    2010              :    * -1 if better_main_loop_than_p should return true.
    2011              :    * 1 if better_main_loop_than_p should return false.
    2012              :    * 0 if we can't decide.  */
    2013              : 
    2014              : int
    2015        34603 : vector_costs::compare_inside_loop_cost (const vector_costs *other) const
    2016              : {
    2017        34603 :   loop_vec_info this_loop_vinfo = as_a<loop_vec_info> (this->m_vinfo);
    2018        34603 :   loop_vec_info other_loop_vinfo = as_a<loop_vec_info> (other->m_vinfo);
    2019              : 
    2020        34603 :   struct loop *loop = LOOP_VINFO_LOOP (this_loop_vinfo);
    2021        34603 :   gcc_assert (LOOP_VINFO_LOOP (other_loop_vinfo) == loop);
    2022              : 
    2023        34603 :   poly_int64 this_vf = LOOP_VINFO_VECT_FACTOR (this_loop_vinfo);
    2024        34603 :   poly_int64 other_vf = LOOP_VINFO_VECT_FACTOR (other_loop_vinfo);
    2025              : 
    2026              :   /* Limit the VFs to what is likely to be the maximum number of iterations,
    2027              :      to handle cases in which at least one loop_vinfo is fully-masked.  */
    2028        34603 :   HOST_WIDE_INT estimated_max_niter = likely_max_stmt_executions_int (loop);
    2029        34603 :   if (estimated_max_niter != -1)
    2030              :     {
    2031        33523 :       if (estimated_poly_value (this_vf, POLY_VALUE_MIN)
    2032              :           >= estimated_max_niter)
    2033              :         this_vf = estimated_max_niter;
    2034        33523 :       if (estimated_poly_value (other_vf, POLY_VALUE_MIN)
    2035              :           >= estimated_max_niter)
    2036              :         other_vf = estimated_max_niter;
    2037              :     }
    2038              : 
    2039              :   /* Check whether the (fractional) cost per scalar iteration is lower or
    2040              :      higher: this_inside_cost / this_vf vs. other_inside_cost / other_vf.  */
    2041        34603 :   poly_int64 rel_this = this_loop_vinfo->vector_costs->body_cost () * other_vf;
    2042        34603 :   poly_int64 rel_other
    2043        34603 :     = other_loop_vinfo->vector_costs->body_cost () * this_vf;
    2044              : 
    2045        34603 :   HOST_WIDE_INT est_rel_this_min
    2046        34603 :     = estimated_poly_value (rel_this, POLY_VALUE_MIN);
    2047        34603 :   HOST_WIDE_INT est_rel_this_max
    2048        34603 :     = estimated_poly_value (rel_this, POLY_VALUE_MAX);
    2049              : 
    2050        34603 :   HOST_WIDE_INT est_rel_other_min
    2051        34603 :     = estimated_poly_value (rel_other, POLY_VALUE_MIN);
    2052        34603 :   HOST_WIDE_INT est_rel_other_max
    2053        34603 :     = estimated_poly_value (rel_other, POLY_VALUE_MAX);
    2054              : 
    2055              :   /* Check first if we can make out an unambiguous total order from the minimum
    2056              :      and maximum estimates.  */
    2057        34603 :   if (est_rel_this_min < est_rel_other_min
    2058              :       && est_rel_this_max < est_rel_other_max)
    2059              :     return -1;
    2060              : 
    2061        33472 :   if (est_rel_other_min < est_rel_this_min
    2062              :       && est_rel_other_max < est_rel_this_max)
    2063        33257 :     return 1;
    2064              : 
    2065              :   /* When other_loop_vinfo uses a variable vectorization factor,
    2066              :      we know that it has a lower cost for at least one runtime VF.
    2067              :      However, we don't know how likely that VF is.
    2068              : 
    2069              :      One option would be to compare the costs for the estimated VFs.
    2070              :      The problem is that that can put too much pressure on the cost
    2071              :      model.  E.g. if the estimated VF is also the lowest possible VF,
    2072              :      and if other_loop_vinfo is 1 unit worse than this_loop_vinfo
    2073              :      for the estimated VF, we'd then choose this_loop_vinfo even
    2074              :      though (a) this_loop_vinfo might not actually be better than
    2075              :      other_loop_vinfo for that VF and (b) it would be significantly
    2076              :      worse at larger VFs.
    2077              : 
    2078              :      Here we go for a hacky compromise: pick this_loop_vinfo if it is
    2079              :      no more expensive than other_loop_vinfo even after doubling the
    2080              :      estimated other_loop_vinfo VF.  For all but trivial loops, this
    2081              :      ensures that we only pick this_loop_vinfo if it is significantly
    2082              :      better than other_loop_vinfo at the estimated VF.  */
    2083              :   if (est_rel_other_min != est_rel_this_min
    2084              :       || est_rel_other_max != est_rel_this_max)
    2085              :     {
    2086              :       HOST_WIDE_INT est_rel_this_likely
    2087              :         = estimated_poly_value (rel_this, POLY_VALUE_LIKELY);
    2088              :       HOST_WIDE_INT est_rel_other_likely
    2089              :         = estimated_poly_value (rel_other, POLY_VALUE_LIKELY);
    2090              : 
    2091              :       return est_rel_this_likely * 2 <= est_rel_other_likely ? -1 : 1;
    2092              :     }
    2093              : 
    2094              :   return 0;
    2095              : }
    2096              : 
    2097              : /* A <=>-style subroutine of better_main_loop_than_p, used when there is
    2098              :    nothing to choose between the inside (loop body) costs of THIS and OTHER.
    2099              :    Check whether we can determine the return value of better_main_loop_than_p
    2100              :    by comparing the outside (prologue and epilogue) costs of THIS and OTHER.
    2101              :    Return:
    2102              : 
    2103              :    * -1 if better_main_loop_than_p should return true.
    2104              :    * 1 if better_main_loop_than_p should return false.
    2105              :    * 0 if we can't decide.  */
    2106              : 
    2107              : int
    2108          215 : vector_costs::compare_outside_loop_cost (const vector_costs *other) const
    2109              : {
    2110          215 :   auto this_outside_cost = this->outside_cost ();
    2111          215 :   auto other_outside_cost = other->outside_cost ();
    2112          215 :   if (this_outside_cost != other_outside_cost)
    2113          149 :     return this_outside_cost < other_outside_cost ? -1 : 1;
    2114              : 
    2115              :   return 0;
    2116              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.