LCOV - code coverage report
Current view: top level - gcc - tree-vectorizer.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 80.1 % 918 735
Test Date: 2024-03-23 14:05:01 Functions: 81.0 % 63 51
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

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

Generated by: LCOV version 2.0-1

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.