LCOV - code coverage report
Current view: top level - gcc - tree-ssa-loop-unswitch.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.1 % 753 724
Test Date: 2025-10-18 14:39:06 Functions: 96.8 % 31 30
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Loop unswitching.
       2                 :             :    Copyright (C) 2004-2025 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it
       7                 :             : under the terms of the GNU General Public License as published by the
       8                 :             : Free Software Foundation; either version 3, or (at your option) any
       9                 :             : later version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT
      12                 :             : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : #include "config.h"
      21                 :             : #include "system.h"
      22                 :             : #include "coretypes.h"
      23                 :             : #include "backend.h"
      24                 :             : #include "tree.h"
      25                 :             : #include "gimple.h"
      26                 :             : #include "tree-pass.h"
      27                 :             : #include "ssa.h"
      28                 :             : #include "fold-const.h"
      29                 :             : #include "gimplify.h"
      30                 :             : #include "tree-cfg.h"
      31                 :             : #include "tree-ssa.h"
      32                 :             : #include "tree-ssa-loop-niter.h"
      33                 :             : #include "tree-ssa-loop.h"
      34                 :             : #include "tree-into-ssa.h"
      35                 :             : #include "cfgloop.h"
      36                 :             : #include "tree-inline.h"
      37                 :             : #include "gimple-iterator.h"
      38                 :             : #include "cfghooks.h"
      39                 :             : #include "tree-ssa-loop-manip.h"
      40                 :             : #include "tree-vectorizer.h"
      41                 :             : #include "tree-pretty-print.h"
      42                 :             : #include "gimple-range.h"
      43                 :             : #include "dbgcnt.h"
      44                 :             : #include "cfganal.h"
      45                 :             : 
      46                 :             : /* This file implements the loop unswitching, i.e. transformation of loops like
      47                 :             : 
      48                 :             :    while (A)
      49                 :             :      {
      50                 :             :        if (inv)
      51                 :             :          B;
      52                 :             : 
      53                 :             :        X;
      54                 :             : 
      55                 :             :        if (!inv)
      56                 :             :          C;
      57                 :             :      }
      58                 :             : 
      59                 :             :    where inv is the loop invariant, into
      60                 :             : 
      61                 :             :    if (inv)
      62                 :             :      {
      63                 :             :        while (A)
      64                 :             :          {
      65                 :             :            B;
      66                 :             :            X;
      67                 :             :          }
      68                 :             :      }
      69                 :             :    else
      70                 :             :      {
      71                 :             :        while (A)
      72                 :             :          {
      73                 :             :            X;
      74                 :             :            C;
      75                 :             :          }
      76                 :             :      }
      77                 :             : 
      78                 :             :    Inv is considered invariant iff the values it compares are both invariant;
      79                 :             :    tree-ssa-loop-im.cc ensures that all the suitable conditions are in this
      80                 :             :    shape.  */
      81                 :             : 
      82                 :             : /* Loop unswitching algorithm for innermost loops works in the following steps:
      83                 :             : 
      84                 :             :    1) Number of instructions is estimated for each BB that belongs to a loop.
      85                 :             :    2) Unswitching candidates are found for gcond and gswitch statements
      86                 :             :       (note that an unswitching predicate for a gswitch actually corresponds
      87                 :             :        to a non-default edge so it can contain multiple cases).
      88                 :             :    3) The so called unswitch predicates are stored in a cache where the
      89                 :             :       gimple_uid of the last stmt in a basic-block is an index to the cache.
      90                 :             :    4) We consider one by one the unswitching candidates and calculate BBs that
      91                 :             :       will be reachable in the unswitch version.
      92                 :             :    5) A selected predicate is chosen and we simplify the CFG (dead edges) in
      93                 :             :       both versions of the loop.  We utilize both Ranger for condition
      94                 :             :       simplification and also symbol equivalence.  The folded if conditions
      95                 :             :       are replaced with true/false values, while for gswitch we mark the
      96                 :             :       corresponding edges with a pass-defined unreachable flag.
      97                 :             :    6) Every time we unswitch a loop, we save unswitch_predicate to a vector
      98                 :             :       together with information if true or false edge was taken.  Doing that
      99                 :             :       we have a so called PREDICATE_PATH that is utilized for simplification
     100                 :             :       of the cloned loop.
     101                 :             :    7) The process is repeated until we reach a growth threshold or all
     102                 :             :       unswitching opportunities are taken.  */
     103                 :             : 
     104                 :             : /* A tuple that holds a GENERIC condition and value range for an unswitching
     105                 :             :    predicate.  */
     106                 :             : 
     107                 :             : struct unswitch_predicate
     108                 :             : {
     109                 :             :   /* CTOR for a switch edge predicate.  */
     110                 :         107 :   unswitch_predicate (tree cond, tree lhs_, int edge_index_, edge e,
     111                 :             :                       const int_range_max& edge_range)
     112                 :         107 :     : condition (cond), lhs (lhs_),
     113                 :         107 :       true_range (edge_range), edge_index (edge_index_), switch_p (true)
     114                 :             :   {
     115                 :         107 :     gcc_assert (!(e->flags & (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE))
     116                 :             :                 && irange::supports_p (TREE_TYPE (lhs)));
     117                 :         107 :     false_range = true_range;
     118                 :         107 :     if (!false_range.varying_p ()
     119                 :         107 :         && !false_range.undefined_p ())
     120                 :         107 :       false_range.invert ();
     121                 :         107 :     count = e->count ();
     122                 :         107 :     num = predicates->length ();
     123                 :         107 :     predicates->safe_push (this);
     124                 :         107 :   }
     125                 :             : 
     126                 :             :   /* CTOR for a GIMPLE condition statement.  */
     127                 :        2786 :   unswitch_predicate (gcond *stmt)
     128                 :        2786 :     : switch_p (false)
     129                 :             :   {
     130                 :        2786 :     basic_block bb = gimple_bb (stmt);
     131                 :        2786 :     if (EDGE_SUCC (bb, 0)->flags & EDGE_TRUE_VALUE)
     132                 :        2734 :       edge_index = 0;
     133                 :             :     else
     134                 :          52 :       edge_index = 1;
     135                 :        2786 :     lhs = gimple_cond_lhs (stmt);
     136                 :        2786 :     tree rhs = gimple_cond_rhs (stmt);
     137                 :        2786 :     enum tree_code code = gimple_cond_code (stmt);
     138                 :        2786 :     condition = build2 (code, boolean_type_node, lhs, rhs);
     139                 :        2786 :     count = profile_count::max_prefer_initialized (EDGE_SUCC (bb, 0)->count (),
     140                 :        2786 :                                                    EDGE_SUCC (bb, 1)->count ());
     141                 :        2786 :     if (irange::supports_p (TREE_TYPE (lhs)))
     142                 :             :       {
     143                 :        2617 :         auto range_op = range_op_handler (code);
     144                 :        2617 :         int_range<2> rhs_range (TREE_TYPE (rhs));
     145                 :        2617 :         if (CONSTANT_CLASS_P (rhs))
     146                 :             :           {
     147                 :        2464 :             wide_int w = wi::to_wide (rhs);
     148                 :        2464 :             rhs_range.set (TREE_TYPE (rhs), w, w);
     149                 :        2464 :           }
     150                 :        2617 :         if (!range_op.op1_range (true_range, TREE_TYPE (lhs),
     151                 :        5234 :                                  range_true (), rhs_range)
     152                 :        7851 :             || !range_op.op1_range (false_range, TREE_TYPE (lhs),
     153                 :        5234 :                                     range_false (), rhs_range))
     154                 :             :           {
     155                 :           0 :             true_range.set_varying (TREE_TYPE (lhs));
     156                 :           0 :             false_range.set_varying (TREE_TYPE (lhs));
     157                 :             :           }
     158                 :        2617 :       }
     159                 :        2786 :     num = predicates->length ();
     160                 :        2786 :     predicates->safe_push (this);
     161                 :        2786 :   }
     162                 :             : 
     163                 :             :   /* Copy ranges for purpose of usage in predicate path.  */
     164                 :             : 
     165                 :             :   inline void
     166                 :        7584 :   copy_merged_ranges ()
     167                 :             :   {
     168                 :        7584 :     merged_true_range = true_range;
     169                 :        7584 :     merged_false_range = false_range;
     170                 :        7584 :   }
     171                 :             : 
     172                 :             :   /* GENERIC unswitching expression testing LHS against CONSTANT.  */
     173                 :             :   tree condition;
     174                 :             : 
     175                 :             :   /* LHS of the expression.  */
     176                 :             :   tree lhs;
     177                 :             : 
     178                 :             :   /* Initial ranges (when the expression is true/false) for the expression.  */
     179                 :             :   int_range_max true_range = {}, false_range = {};
     180                 :             : 
     181                 :             :   /* Modified range that is part of a predicate path.  */
     182                 :             :   int_range_max merged_true_range = {}, merged_false_range = {};
     183                 :             : 
     184                 :             :   /* Index of the edge the predicate belongs to in the successor vector.  */
     185                 :             :   int edge_index;
     186                 :             : 
     187                 :             :   /* The profile count of this predicate.  */
     188                 :             :   profile_count count;
     189                 :             : 
     190                 :             :   /* Whether the predicate was created from a switch statement.  */
     191                 :             :   bool switch_p;
     192                 :             : 
     193                 :             :   /* The number of the predicate in the predicates vector below.  */
     194                 :             :   unsigned num;
     195                 :             : 
     196                 :             :   /* Vector of all used predicates, used for assigning a unique id that
     197                 :             :      can be used for bitmap operations.  */
     198                 :             :   static vec<unswitch_predicate *> *predicates;
     199                 :             : };
     200                 :             : 
     201                 :             : vec<unswitch_predicate *> *unswitch_predicate::predicates;
     202                 :             : 
     203                 :             : /* Ranger instance used in the pass.  */
     204                 :             : static gimple_ranger *ranger = NULL;
     205                 :             : 
     206                 :             : /* Cache storage for unswitch_predicate belonging to a basic block.  */
     207                 :             : static vec<vec<unswitch_predicate *>> *bb_predicates;
     208                 :             : 
     209                 :             : /* The type represents a predicate path leading to a basic block.  */
     210                 :             : typedef vec<std::pair<unswitch_predicate *, bool>> predicate_vector;
     211                 :             : 
     212                 :             : static class loop *tree_unswitch_loop (class loop *, edge, tree);
     213                 :             : static bool tree_unswitch_single_loop (class loop *, dump_user_location_t,
     214                 :             :                                        predicate_vector &predicate_path,
     215                 :             :                                        unsigned loop_size, unsigned &budget,
     216                 :             :                                        int ignored_edge_flag, bitmap,
     217                 :             :                                        unswitch_predicate * = NULL,
     218                 :             :                                        basic_block = NULL);
     219                 :             : static void
     220                 :             : find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
     221                 :             :                                     class loop *&outer_loop,
     222                 :             :                                     vec<unswitch_predicate *> &candidates,
     223                 :             :                                     unswitch_predicate *&hottest,
     224                 :             :                                     basic_block &hottest_bb);
     225                 :             : static bool tree_unswitch_outer_loop (class loop *);
     226                 :             : static edge find_loop_guard (class loop *, vec<gimple *>&);
     227                 :             : static bool empty_bb_without_guard_p (class loop *, basic_block,
     228                 :             :                                       vec<gimple *>&);
     229                 :             : static bool used_outside_loop_p (class loop *, tree, vec<gimple *>&);
     230                 :             : static void hoist_guard (class loop *, edge);
     231                 :             : static bool check_exit_phi (class loop *);
     232                 :             : static tree get_vop_from_header (class loop *);
     233                 :             : static void clean_up_after_unswitching (int);
     234                 :             : 
     235                 :             : /* Return vector of predicates that belong to a basic block.  */
     236                 :             : 
     237                 :             : static vec<unswitch_predicate *> &
     238                 :      447874 : get_predicates_for_bb (basic_block bb)
     239                 :             : {
     240                 :      447874 :   gimple *last = last_nondebug_stmt (bb);
     241                 :      447874 :   return (*bb_predicates)[last == NULL ? 0 : gimple_uid (last)];
     242                 :             : }
     243                 :             : 
     244                 :             : /* Save predicates that belong to a basic block.  */
     245                 :             : 
     246                 :             : static void
     247                 :        2819 : set_predicates_for_bb (basic_block bb, vec<unswitch_predicate *> predicates)
     248                 :             : {
     249                 :        5638 :   gimple_set_uid (last_nondebug_stmt (bb), bb_predicates->length ());
     250                 :        2819 :   bb_predicates->safe_push (predicates);
     251                 :        2819 : }
     252                 :             : 
     253                 :             : /* Initialize LOOP information reused during the unswitching pass.
     254                 :             :    Return total number of instructions in the loop.  Adjusts LOOP to
     255                 :             :    the outermost loop all candidates are invariant in.  */
     256                 :             : 
     257                 :             : static unsigned
     258                 :       61358 : init_loop_unswitch_info (class loop *&loop, unswitch_predicate *&hottest,
     259                 :             :                          basic_block &hottest_bb)
     260                 :             : {
     261                 :       61358 :   unsigned total_insns = 0;
     262                 :             : 
     263                 :       61358 :   basic_block *bbs = get_loop_body (loop);
     264                 :             : 
     265                 :             :   /* Unswitch only nests with no sibling loops.  */
     266                 :       61358 :   class loop *outer_loop = loop;
     267                 :       61358 :   unsigned max_depth = param_max_unswitch_depth;
     268                 :       61358 :   while (loop_outer (outer_loop)->num != 0
     269                 :       17388 :          && !loop_outer (outer_loop)->inner->next
     270                 :       83425 :          && --max_depth != 0)
     271                 :       11031 :     outer_loop = loop_outer (outer_loop);
     272                 :       61358 :   hottest = NULL;
     273                 :       61358 :   hottest_bb = NULL;
     274                 :             :   /* Find all unswitching candidates in the innermost loop.  */
     275                 :      283226 :   for (unsigned i = 0; i != loop->num_nodes; i++)
     276                 :             :     {
     277                 :             :       /* Find a bb to unswitch on.  */
     278                 :      221868 :       vec<unswitch_predicate *> candidates;
     279                 :      221868 :       candidates.create (1);
     280                 :      221868 :       find_unswitching_predicates_for_bb (bbs[i], loop, outer_loop, candidates,
     281                 :             :                                           hottest, hottest_bb);
     282                 :      221868 :       if (!candidates.is_empty ())
     283                 :        2819 :         set_predicates_for_bb (bbs[i], candidates);
     284                 :             :       else
     285                 :             :         {
     286                 :      219049 :           candidates.release ();
     287                 :      219049 :           gimple *last = last_nondebug_stmt (bbs[i]);
     288                 :      219049 :           if (last != NULL)
     289                 :      137249 :             gimple_set_uid (last, 0);
     290                 :             :         }
     291                 :             :     }
     292                 :             : 
     293                 :       61358 :   if (outer_loop != loop)
     294                 :             :     {
     295                 :        8370 :       free (bbs);
     296                 :        8370 :       bbs = get_loop_body (outer_loop);
     297                 :             :     }
     298                 :             : 
     299                 :             :   /* Calculate instruction count.  */
     300                 :      351638 :   for (unsigned i = 0; i < outer_loop->num_nodes; i++)
     301                 :             :     {
     302                 :      290280 :       unsigned insns = 0;
     303                 :     1586005 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
     304                 :     1005445 :            gsi_next (&gsi))
     305                 :     1005445 :         insns += estimate_num_insns (gsi_stmt (gsi), &eni_size_weights);
     306                 :             :       /* No predicates to unswitch on in the outer loops.  */
     307                 :      290280 :       if (!flow_bb_inside_loop_p (loop, bbs[i]))
     308                 :             :         {
     309                 :       68412 :           gimple *last = last_nondebug_stmt (bbs[i]);
     310                 :       68412 :           if (last != NULL)
     311                 :       40892 :             gimple_set_uid (last, 0);
     312                 :             :         }
     313                 :             : 
     314                 :      290280 :       bbs[i]->aux = (void *)(uintptr_t)insns;
     315                 :      290280 :       total_insns += insns;
     316                 :             :     }
     317                 :             : 
     318                 :       61358 :   free (bbs);
     319                 :             : 
     320                 :       61358 :   loop = outer_loop;
     321                 :       61358 :   return total_insns;
     322                 :             : }
     323                 :             : 
     324                 :             : /* Main entry point.  Perform loop unswitching on all suitable loops.  */
     325                 :             : 
     326                 :             : unsigned int
     327                 :       27524 : tree_ssa_unswitch_loops (function *fun)
     328                 :             : {
     329                 :       27524 :   bool changed_unswitch = false;
     330                 :       27524 :   bool changed_hoist = false;
     331                 :       27524 :   auto_edge_flag ignored_edge_flag (fun);
     332                 :       27524 :   mark_ssa_maybe_undefs ();
     333                 :             : 
     334                 :       27524 :   ranger = enable_ranger (fun);
     335                 :             : 
     336                 :             :   /* Go through all loops starting from innermost, hoisting guards.  */
     337                 :      161324 :   for (auto loop : loops_list (fun, LI_FROM_INNERMOST))
     338                 :             :     {
     339                 :       78752 :       if (loop->inner)
     340                 :       14226 :         changed_hoist |= tree_unswitch_outer_loop (loop);
     341                 :       27524 :     }
     342                 :             : 
     343                 :             :   /* Go through innermost loops, unswitching on invariant predicates
     344                 :             :      within those.  */
     345                 :      147098 :   for (auto loop : loops_list (fun, LI_ONLY_INNERMOST))
     346                 :             :     {
     347                 :             :       /* Perform initial tests if unswitch is eligible.  */
     348                 :       64526 :       dump_user_location_t loc = find_loop_location (loop);
     349                 :             : 
     350                 :             :       /* Do not unswitch in cold regions. */
     351                 :       64526 :       if (optimize_loop_for_size_p (loop))
     352                 :             :         {
     353                 :        1260 :           if (dump_enabled_p ())
     354                 :           0 :             dump_printf_loc (MSG_NOTE, loc,
     355                 :             :                              "Not unswitching cold loops\n");
     356                 :        3168 :           continue;
     357                 :             :         }
     358                 :             : 
     359                 :             :       /* If the loop is not expected to iterate, there is no need
     360                 :             :          for unswitching.  */
     361                 :       63266 :       HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop);
     362                 :       63266 :       if (iterations < 0)
     363                 :       37536 :         iterations = likely_max_loop_iterations_int (loop);
     364                 :       63266 :       if (iterations >= 0 && iterations <= 1)
     365                 :             :         {
     366                 :        1908 :           if (dump_enabled_p ())
     367                 :           2 :             dump_printf_loc (MSG_NOTE, loc,
     368                 :             :                              "Not unswitching, loop is not expected"
     369                 :             :                              " to iterate\n");
     370                 :        1908 :           continue;
     371                 :             :         }
     372                 :             : 
     373                 :       61358 :       bb_predicates = new vec<vec<unswitch_predicate *>> ();
     374                 :       61358 :       bb_predicates->safe_push (vec<unswitch_predicate *> ());
     375                 :       61358 :       unswitch_predicate::predicates = new vec<unswitch_predicate *> ();
     376                 :             : 
     377                 :             :       /* Unswitch loop.  */
     378                 :       61358 :       unswitch_predicate *hottest;
     379                 :       61358 :       basic_block hottest_bb;
     380                 :       61358 :       unsigned int loop_size = init_loop_unswitch_info (loop, hottest,
     381                 :             :                                                         hottest_bb);
     382                 :       61358 :       unsigned int budget = loop_size + param_max_unswitch_insns;
     383                 :             : 
     384                 :       61358 :       predicate_vector predicate_path;
     385                 :       61358 :       predicate_path.create (8);
     386                 :       61358 :       auto_bitmap handled;
     387                 :       61358 :       changed_unswitch |= tree_unswitch_single_loop (loop, loc, predicate_path,
     388                 :             :                                                      loop_size, budget,
     389                 :             :                                                      ignored_edge_flag, handled,
     390                 :             :                                                      hottest, hottest_bb);
     391                 :       61358 :       predicate_path.release ();
     392                 :             : 
     393                 :      248251 :       for (auto predlist : bb_predicates)
     394                 :       64177 :         predlist.release ();
     395                 :       61358 :       bb_predicates->release ();
     396                 :       61358 :       delete bb_predicates;
     397                 :       61358 :       bb_predicates = NULL;
     398                 :             : 
     399                 :      186967 :       for (auto pred : unswitch_predicate::predicates)
     400                 :        2893 :         delete pred;
     401                 :       61358 :       unswitch_predicate::predicates->release ();
     402                 :       61358 :       delete unswitch_predicate::predicates;
     403                 :       61358 :       unswitch_predicate::predicates = NULL;
     404                 :       61358 :     }
     405                 :             : 
     406                 :       27524 :   disable_ranger (fun);
     407                 :       27524 :   clear_aux_for_blocks ();
     408                 :             : 
     409                 :       27524 :   if (changed_unswitch)
     410                 :        1369 :     clean_up_after_unswitching (ignored_edge_flag);
     411                 :             : 
     412                 :       27524 :   if (changed_unswitch || changed_hoist)
     413                 :        1854 :     return TODO_cleanup_cfg;
     414                 :             : 
     415                 :             :   return 0;
     416                 :       27524 : }
     417                 :             : 
     418                 :             : /* Return TRUE if an SSA_NAME maybe undefined and is therefore
     419                 :             :    unsuitable for unswitching.  STMT is the statement we are
     420                 :             :    considering for unswitching and LOOP is the loop it appears in.  */
     421                 :             : 
     422                 :             : static bool
     423                 :       17421 : is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
     424                 :             : {
     425                 :             :   /* The loop header is the only block we can trivially determine that
     426                 :             :      will always be executed.  If the comparison is in the loop
     427                 :             :      header, we know it's OK to unswitch on it.  */
     428                 :           0 :   if (gimple_bb (stmt) == loop->header)
     429                 :             :     return false;
     430                 :             : 
     431                 :        8262 :   return ssa_name_maybe_undef_p (name);
     432                 :             : }
     433                 :             : 
     434                 :             : /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
     435                 :             :    basic blocks (for what it means see comments below).
     436                 :             :    All candidates all filled to the provided vector CANDIDATES.
     437                 :             :    OUTER_LOOP is updated to the innermost loop all found candidates are
     438                 :             :    invariant in.  */
     439                 :             : 
     440                 :             : static void
     441                 :      221868 : find_unswitching_predicates_for_bb (basic_block bb, class loop *loop,
     442                 :             :                                     class loop *&outer_loop,
     443                 :             :                                     vec<unswitch_predicate *> &candidates,
     444                 :             :                                     unswitch_predicate *&hottest,
     445                 :             :                                     basic_block &hottest_bb)
     446                 :             : {
     447                 :      221868 :   gimple *last, *def;
     448                 :      221868 :   tree use;
     449                 :      221868 :   basic_block def_bb;
     450                 :      221868 :   ssa_op_iter iter;
     451                 :             : 
     452                 :             :   /* BB must end in a simple conditional jump.  */
     453                 :      221868 :   last = *gsi_last_bb (bb);
     454                 :      221868 :   if (!last)
     455                 :      196372 :     return;
     456                 :             : 
     457                 :      140448 :   if (gcond *stmt = safe_dyn_cast <gcond *> (last))
     458                 :             :     {
     459                 :             :       /* To keep the things simple, we do not directly remove the conditions,
     460                 :             :          but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
     461                 :             :          loop where we would unswitch again on such a condition.  */
     462                 :      117585 :       if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
     463                 :      114799 :         return;
     464                 :             : 
     465                 :             :       /* At least the LHS needs to be symbolic.  */
     466                 :      117585 :       if (TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
     467                 :             :         return;
     468                 :             : 
     469                 :             :       /* Condition must be invariant.  */
     470                 :      134165 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     471                 :             :         {
     472                 :      131379 :           def = SSA_NAME_DEF_STMT (use);
     473                 :      131379 :           def_bb = gimple_bb (def);
     474                 :      131379 :           if (def_bb
     475                 :      131379 :               && flow_bb_inside_loop_p (loop, def_bb))
     476                 :             :             return;
     477                 :             :           /* Unswitching on undefined values would introduce undefined
     478                 :             :              behavior that the original program might never exercise.  */
     479                 :       24321 :           if (is_maybe_undefined (use, stmt, loop))
     480                 :             :             return;
     481                 :             :         }
     482                 :             :       /* Narrow OUTER_LOOP.  */
     483                 :        2786 :       if (outer_loop != loop)
     484                 :        1677 :         FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     485                 :             :           {
     486                 :         856 :             def = SSA_NAME_DEF_STMT (use);
     487                 :         856 :             def_bb = gimple_bb (def);
     488                 :         856 :             while (outer_loop != loop
     489                 :        1222 :                    && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb))
     490                 :        1535 :                        || is_maybe_undefined (use, stmt, outer_loop)))
     491                 :         366 :               outer_loop = superloop_at_depth (loop,
     492                 :         732 :                                                loop_depth (outer_loop) + 1);
     493                 :             :           }
     494                 :             : 
     495                 :        2786 :       unswitch_predicate *predicate = new unswitch_predicate (stmt);
     496                 :        2786 :       candidates.safe_push (predicate);
     497                 :             :       /* If we unswitch on this predicate we isolate both paths, so
     498                 :             :          pick the highest count for updating of the hottest predicate
     499                 :             :          to unswitch on first.  */
     500                 :        2786 :       if (!hottest || predicate->count > hottest->count)
     501                 :             :         {
     502                 :        1857 :           hottest = predicate;
     503                 :        1857 :           hottest_bb = bb;
     504                 :             :         }
     505                 :             :     }
     506                 :       25682 :   else if (gswitch *stmt = safe_dyn_cast <gswitch *> (last))
     507                 :             :     {
     508                 :         186 :       unsigned nlabels = gimple_switch_num_labels (stmt);
     509                 :         186 :       tree idx = gimple_switch_index (stmt);
     510                 :         186 :       tree idx_type = TREE_TYPE (idx);
     511                 :         186 :       if (!gimple_range_ssa_p (idx) || nlabels < 1)
     512                 :         153 :         return;
     513                 :             :       /* Index must be invariant.  */
     514                 :         185 :       def = SSA_NAME_DEF_STMT (idx);
     515                 :         185 :       def_bb = gimple_bb (def);
     516                 :         185 :       if (def_bb
     517                 :         185 :           && flow_bb_inside_loop_p (loop, def_bb))
     518                 :             :         return;
     519                 :             :       /* Unswitching on undefined values would introduce undefined
     520                 :             :          behavior that the original program might never exercise.  */
     521                 :          48 :       if (is_maybe_undefined (idx, stmt, loop))
     522                 :             :         return;
     523                 :             :       /* Narrow OUTER_LOOP.  */
     524                 :          33 :       while (outer_loop != loop
     525                 :          33 :              && ((def_bb && flow_bb_inside_loop_p (outer_loop, def_bb))
     526                 :           8 :                  || is_maybe_undefined (idx, stmt, outer_loop)))
     527                 :           0 :         outer_loop = superloop_at_depth (loop,
     528                 :           0 :                                          loop_depth (outer_loop) + 1);
     529                 :             : 
     530                 :             :       /* Build compound expression for all outgoing edges of the switch.  */
     531                 :          33 :       auto_vec<tree, 16> preds;
     532                 :          33 :       auto_vec<int_range_max> edge_range;
     533                 :          66 :       preds.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), true);
     534                 :          66 :       edge_range.safe_grow_cleared (EDGE_COUNT (gimple_bb (stmt)->succs), true);
     535                 :          33 :       edge e;
     536                 :          33 :       edge_iterator ei;
     537                 :          33 :       unsigned edge_index = 0;
     538                 :         170 :       FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
     539                 :         137 :         e->aux = (void *)(uintptr_t)edge_index++;
     540                 :         149 :       for (unsigned i = 1; i < gimple_switch_num_labels (stmt); ++i)
     541                 :             :         {
     542                 :         116 :           tree lab = gimple_switch_label (stmt, i);
     543                 :         116 :           tree cmp;
     544                 :         116 :           int_range<2> lab_range;
     545                 :         116 :           tree low = fold_convert (idx_type, CASE_LOW (lab));
     546                 :         116 :           if (CASE_HIGH (lab) != NULL_TREE)
     547                 :             :             {
     548                 :           3 :               tree high = fold_convert (idx_type, CASE_HIGH (lab));
     549                 :           3 :               tree cmp1 = fold_build2 (GE_EXPR, boolean_type_node, idx, low);
     550                 :           3 :               tree cmp2 = fold_build2 (LE_EXPR, boolean_type_node, idx, high);
     551                 :           3 :               cmp = fold_build2 (BIT_AND_EXPR, boolean_type_node, cmp1, cmp2);
     552                 :           3 :               lab_range.set (idx_type, wi::to_wide (low), wi::to_wide (high));
     553                 :             :             }
     554                 :             :           else
     555                 :             :             {
     556                 :         113 :               cmp = fold_build2 (EQ_EXPR, boolean_type_node, idx, low);
     557                 :         113 :               wide_int w = wi::to_wide (low);
     558                 :         113 :               lab_range.set (idx_type, w, w);
     559                 :         113 :             }
     560                 :             : 
     561                 :             :           /* Combine the expression with the existing one.  */
     562                 :         116 :           basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
     563                 :         116 :           e = find_edge (gimple_bb (stmt), dest);
     564                 :         116 :           tree &expr = preds[(uintptr_t)e->aux];
     565                 :         116 :           if (expr == NULL_TREE)
     566                 :         107 :             expr = cmp;
     567                 :             :           else
     568                 :           9 :             expr = fold_build2 (BIT_IOR_EXPR, boolean_type_node, expr, cmp);
     569                 :         116 :           edge_range[(uintptr_t)e->aux].union_ (lab_range);
     570                 :         116 :         }
     571                 :             : 
     572                 :             :       /* Now register the predicates.  */
     573                 :         170 :       for (edge_index = 0; edge_index < preds.length (); ++edge_index)
     574                 :             :         {
     575                 :         137 :           edge e = EDGE_SUCC (gimple_bb (stmt), edge_index);
     576                 :         137 :           e->aux = NULL;
     577                 :         137 :           if (preds[edge_index] != NULL_TREE)
     578                 :             :             {
     579                 :         107 :               unswitch_predicate *predicate
     580                 :         107 :                 = new unswitch_predicate (preds[edge_index], idx,
     581                 :             :                                           edge_index, e,
     582                 :         107 :                                           edge_range[edge_index]);
     583                 :         107 :               candidates.safe_push (predicate);
     584                 :         107 :               if (!hottest || predicate->count > hottest->count)
     585                 :             :                 {
     586                 :          27 :                   hottest = predicate;
     587                 :          27 :                   hottest_bb = bb;
     588                 :             :                 }
     589                 :             :             }
     590                 :             :         }
     591                 :          33 :     }
     592                 :             : }
     593                 :             : 
     594                 :             : /* Merge ranges for the last item of PREDICATE_PATH with a predicate
     595                 :             :    that shared the same LHS.  */
     596                 :             : 
     597                 :             : static void
     598                 :        7584 : merge_last (predicate_vector &predicate_path)
     599                 :             : {
     600                 :        7584 :   unswitch_predicate *last_predicate = predicate_path.last ().first;
     601                 :             : 
     602                 :       11380 :   for (int i = predicate_path.length () - 2; i >= 0; i--)
     603                 :             :     {
     604                 :        4818 :       unswitch_predicate *predicate = predicate_path[i].first;
     605                 :        4818 :       bool true_edge = predicate_path[i].second;
     606                 :             : 
     607                 :        4818 :       if (operand_equal_p (predicate->lhs, last_predicate->lhs, 0))
     608                 :             :         {
     609                 :        1022 :           irange &other = (true_edge ? predicate->merged_true_range
     610                 :             :                            : predicate->merged_false_range);
     611                 :        1022 :           last_predicate->merged_true_range.intersect (other);
     612                 :        1022 :           last_predicate->merged_false_range.intersect (other);
     613                 :        1022 :           return;
     614                 :             :         }
     615                 :             :     }
     616                 :             : }
     617                 :             : 
     618                 :             : /* Add PREDICATE to PREDICATE_PATH on TRUE_EDGE.  */
     619                 :             : 
     620                 :             : static void
     621                 :        7584 : add_predicate_to_path (predicate_vector &predicate_path,
     622                 :             :                        unswitch_predicate *predicate, bool true_edge)
     623                 :             : {
     624                 :        7584 :   predicate->copy_merged_ranges ();
     625                 :        7584 :   predicate_path.safe_push (std::make_pair (predicate, true_edge));
     626                 :        7584 :   merge_last (predicate_path);
     627                 :        7584 : }
     628                 :             : 
     629                 :             : static bool
     630                 :        1307 : find_range_for_lhs (predicate_vector &predicate_path, tree lhs,
     631                 :             :                     int_range_max &range)
     632                 :             : {
     633                 :        2628 :   for (int i = predicate_path.length () - 1; i >= 0; i--)
     634                 :             :     {
     635                 :        1307 :       unswitch_predicate *predicate = predicate_path[i].first;
     636                 :        1307 :       bool true_edge = predicate_path[i].second;
     637                 :             : 
     638                 :        1307 :       if (operand_equal_p (predicate->lhs, lhs, 0))
     639                 :             :         {
     640                 :        1293 :           range = (true_edge ? predicate->merged_true_range
     641                 :        1293 :                    : predicate->merged_false_range);
     642                 :        1293 :           return !range.undefined_p ();
     643                 :             :         }
     644                 :             :     }
     645                 :             : 
     646                 :             :   return false;
     647                 :             : }
     648                 :             : 
     649                 :             : /* Simplifies STMT using the predicate we unswitched on which is the last
     650                 :             :    in PREDICATE_PATH.  For switch statements add newly unreachable edges
     651                 :             :    to IGNORED_EDGES (but do not set IGNORED_EDGE_FLAG on them).  */
     652                 :             : 
     653                 :             : static tree
     654                 :       55722 : evaluate_control_stmt_using_entry_checks (gimple *stmt,
     655                 :             :                                           predicate_vector &predicate_path,
     656                 :             :                                           int ignored_edge_flag,
     657                 :             :                                           hash_set<edge> *ignored_edges)
     658                 :             : {
     659                 :       55722 :   unswitch_predicate *last_predicate = predicate_path.last ().first;
     660                 :       55722 :   bool true_edge = predicate_path.last ().second;
     661                 :             : 
     662                 :       55722 :   if (gcond *cond = dyn_cast<gcond *> (stmt))
     663                 :             :     {
     664                 :       55362 :       tree lhs = gimple_cond_lhs (cond);
     665                 :       55362 :       if (!operand_equal_p (lhs, last_predicate->lhs))
     666                 :             :         return NULL_TREE;
     667                 :             :       /* Try a symbolic match which works for floating point and fully
     668                 :             :          symbolic conditions.  */
     669                 :       17005 :       if (gimple_cond_code (cond) == TREE_CODE (last_predicate->condition)
     670                 :       33447 :           && operand_equal_p (gimple_cond_rhs (cond),
     671                 :       16442 :                               TREE_OPERAND (last_predicate->condition, 1)))
     672                 :       16034 :         return true_edge ? boolean_true_node : boolean_false_node;
     673                 :             :       /* Else try ranger if it supports LHS.  */
     674                 :         971 :       else if (irange::supports_p (TREE_TYPE (lhs)))
     675                 :             :         {
     676                 :         971 :           int_range<2> r;
     677                 :         971 :           int_range_max path_range;
     678                 :             : 
     679                 :         971 :           if (find_range_for_lhs (predicate_path, lhs, path_range)
     680                 :         971 :               && fold_range (r, cond, path_range)
     681                 :        1942 :               && r.singleton_p ())
     682                 :         364 :             return r.zero_p () ? boolean_false_node : boolean_true_node;
     683                 :         971 :         }
     684                 :             :     }
     685                 :         360 :   else if (gswitch *swtch = dyn_cast<gswitch *> (stmt))
     686                 :             :     {
     687                 :         360 :       unsigned nlabels = gimple_switch_num_labels (swtch);
     688                 :             : 
     689                 :         360 :       tree idx = gimple_switch_index (swtch);
     690                 :             : 
     691                 :             :       /* Already folded switch.  */
     692                 :         360 :       if (TREE_CONSTANT (idx))
     693                 :         191 :         return NULL_TREE;
     694                 :             : 
     695                 :         336 :       int_range_max path_range;
     696                 :         336 :       if (!find_range_for_lhs (predicate_path, idx, path_range))
     697                 :             :         return NULL_TREE;
     698                 :             : 
     699                 :             :       tree result = NULL_TREE;
     700                 :             :       edge single_edge = NULL;
     701                 :        2026 :       for (unsigned i = 0; i < nlabels; ++i)
     702                 :             :         {
     703                 :        1704 :           tree lab = gimple_switch_label (swtch, i);
     704                 :        1704 :           basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
     705                 :        1704 :           edge e = find_edge (gimple_bb (stmt), dest);
     706                 :        1704 :           if (e->flags & ignored_edge_flag)
     707                 :         398 :             continue;
     708                 :             : 
     709                 :        1312 :           int_range_max r;
     710                 :        1312 :           if (!ranger->gori ().edge_range_p (r, e, idx,
     711                 :             :                                              *get_global_range_query ()))
     712                 :           6 :             continue;
     713                 :        1306 :           r.intersect (path_range);
     714                 :        1306 :           if (r.undefined_p ())
     715                 :         643 :             ignored_edges->add (e);
     716                 :             :           else
     717                 :             :             {
     718                 :         663 :               if (!single_edge)
     719                 :             :                 {
     720                 :         320 :                   single_edge = e;
     721                 :         320 :                   result = CASE_LOW (lab);
     722                 :             :                 }
     723                 :         343 :               else if (single_edge != e)
     724                 :        1306 :                 result = NULL;
     725                 :             :             }
     726                 :        1312 :         }
     727                 :             : 
     728                 :             :       /* Only one edge from the switch is alive.  */
     729                 :         322 :       if (single_edge && result)
     730                 :             :         return result;
     731                 :         336 :     }
     732                 :             : 
     733                 :             :   return NULL_TREE;
     734                 :             : }
     735                 :             : 
     736                 :             : /* Simplify LOOP based on PREDICATE_PATH where dead edges are properly
     737                 :             :    marked.  */
     738                 :             : 
     739                 :             : static bool
     740                 :        4874 : simplify_loop_version (class loop *loop, predicate_vector &predicate_path,
     741                 :             :                        int ignored_edge_flag, bitmap handled)
     742                 :             : {
     743                 :        4874 :   bool changed = false;
     744                 :        4874 :   basic_block *bbs = get_loop_body (loop);
     745                 :             : 
     746                 :        4874 :   hash_set<edge> ignored_edges;
     747                 :       48542 :   for (unsigned i = 0; i != loop->num_nodes; i++)
     748                 :             :     {
     749                 :       43668 :       vec<unswitch_predicate *> &predicates = get_predicates_for_bb (bbs[i]);
     750                 :       43668 :       if (predicates.is_empty ())
     751                 :       33542 :         continue;
     752                 :             : 
     753                 :       10126 :       gimple *stmt = *gsi_last_bb (bbs[i]);
     754                 :       10126 :       tree folded = evaluate_control_stmt_using_entry_checks (stmt,
     755                 :             :                                                               predicate_path,
     756                 :             :                                                               ignored_edge_flag,
     757                 :             :                                                               &ignored_edges);
     758                 :             : 
     759                 :       10126 :       if (gcond *cond = dyn_cast<gcond *> (stmt))
     760                 :             :         {
     761                 :        9948 :           if (folded)
     762                 :             :             {
     763                 :             :               /* Remove path.  */
     764                 :        5534 :               if (integer_nonzerop (folded))
     765                 :        2705 :                 gimple_cond_set_condition_from_tree (cond, boolean_true_node);
     766                 :             :               else
     767                 :        2829 :                 gimple_cond_set_condition_from_tree (cond, boolean_false_node);
     768                 :             : 
     769                 :        5534 :               gcc_assert (predicates.length () == 1);
     770                 :        5534 :               bitmap_set_bit (handled, predicates[0]->num);
     771                 :             : 
     772                 :        5534 :               update_stmt (cond);
     773                 :        5534 :               changed = true;
     774                 :             :             }
     775                 :             :         }
     776                 :       43846 :       else if (gswitch *swtch = dyn_cast<gswitch *> (stmt))
     777                 :             :         {
     778                 :         178 :           edge e;
     779                 :         178 :           edge_iterator ei;
     780                 :         942 :           FOR_EACH_EDGE (e, ei, bbs[i]->succs)
     781                 :         764 :             if (ignored_edges.contains (e))
     782                 :         274 :               e->flags |= ignored_edge_flag;
     783                 :             : 
     784                 :         770 :           for (unsigned j = 0; j < predicates.length (); j++)
     785                 :             :             {
     786                 :         592 :               edge e = EDGE_SUCC (bbs[i], predicates[j]->edge_index);
     787                 :         592 :               if (ignored_edges.contains (e))
     788                 :         204 :                 bitmap_set_bit (handled, predicates[j]->num);
     789                 :             :             }
     790                 :             : 
     791                 :         178 :           if (folded)
     792                 :             :             {
     793                 :          70 :               gimple_switch_set_index (swtch, folded);
     794                 :          70 :               update_stmt (swtch);
     795                 :          70 :               changed = true;
     796                 :             :             }
     797                 :             :         }
     798                 :             :     }
     799                 :             : 
     800                 :        4874 :   free (bbs);
     801                 :        4874 :   return changed;
     802                 :        4874 : }
     803                 :             : 
     804                 :             : /* Evaluate reachable blocks in LOOP and call VISIT on them, aborting the
     805                 :             :    DFS walk if VISIT returns true.  When PREDICATE_PATH is specified then
     806                 :             :    take into account that when computing reachability, otherwise just
     807                 :             :    look at the simplified state and IGNORED_EDGE_FLAG.  */
     808                 :             : 
     809                 :             : template <typename VisitOp>
     810                 :             : static void
     811                 :       67199 : evaluate_bbs (class loop *loop, predicate_vector *predicate_path,
     812                 :             :               int ignored_edge_flag, VisitOp visit)
     813                 :             : {
     814                 :       67199 :   auto_bb_flag reachable_flag (cfun);
     815                 :       67199 :   auto_vec<basic_block, 10> worklist (loop->num_nodes);
     816                 :       67199 :   auto_vec<basic_block, 10> reachable (loop->num_nodes);
     817                 :       67199 :   hash_set<edge> ignored_edges;
     818                 :             : 
     819                 :       67199 :   loop->header->flags |= reachable_flag;
     820                 :       67199 :   worklist.quick_push (loop->header);
     821                 :       67199 :   reachable.safe_push (loop->header);
     822                 :             : 
     823                 :      607601 :   while (!worklist.is_empty ())
     824                 :             :     {
     825                 :             :       edge e;
     826                 :             :       edge_iterator ei;
     827                 :      541104 :       int flags = ignored_edge_flag;
     828                 :      541104 :       basic_block bb = worklist.pop ();
     829                 :             : 
     830                 :      541104 :       if (visit (bb))
     831                 :             :         break;
     832                 :             : 
     833                 :      540402 :       gimple *last = *gsi_last_bb (bb);
     834                 :      283745 :       if (gcond *cond = safe_dyn_cast <gcond *> (last))
     835                 :             :         {
     836                 :      256657 :           if (gimple_cond_true_p (cond))
     837                 :             :             flags = EDGE_FALSE_VALUE;
     838                 :      250351 :           else if (gimple_cond_false_p (cond))
     839                 :             :             flags = EDGE_TRUE_VALUE;
     840                 :      243075 :           else if (predicate_path)
     841                 :             :             {
     842                 :             :               tree res;
     843                 :       98599 :               if (!get_predicates_for_bb (bb).is_empty ()
     844                 :       45414 :                   && (res = evaluate_control_stmt_using_entry_checks
     845                 :       45414 :                               (cond, *predicate_path, ignored_edge_flag,
     846                 :             :                                &ignored_edges)))
     847                 :       16345 :                 flags = (integer_nonzerop (res)
     848                 :       10864 :                          ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE);
     849                 :             :             }
     850                 :             :         }
     851                 :      540869 :       else if (gswitch *swtch = safe_dyn_cast<gswitch *> (last))
     852                 :             :         if (predicate_path
     853                 :      540869 :             && !get_predicates_for_bb (bb).is_empty ())
     854                 :         182 :           evaluate_control_stmt_using_entry_checks (swtch, *predicate_path,
     855                 :             :                                                     ignored_edge_flag,
     856                 :             :                                                     &ignored_edges);
     857                 :             : 
     858                 :             :       /* Note that for the moment we do not account reachable conditions
     859                 :             :          which are simplified to take a known edge as zero size nor
     860                 :             :          are we accounting for the required addition of the versioning
     861                 :             :          condition.  Those should cancel out conservatively.  */
     862                 :             : 
     863                 :     1339745 :       FOR_EACH_EDGE (e, ei, bb->succs)
     864                 :             :         {
     865                 :      799343 :           basic_block dest = e->dest;
     866                 :             : 
     867                 :      799343 :           if (flow_bb_inside_loop_p (loop, dest)
     868                 :      692197 :               && !(dest->flags & reachable_flag)
     869                 :      496660 :               && !(e->flags & flags)
     870                 :     1273575 :               && !ignored_edges.contains (e))
     871                 :             :             {
     872                 :      473976 :               dest->flags |= reachable_flag;
     873                 :      473976 :               worklist.safe_push (dest);
     874                 :      473976 :               reachable.safe_push (dest);
     875                 :             :             }
     876                 :             :         }
     877                 :             :     }
     878                 :             : 
     879                 :             :   /* Clear the flag from basic blocks.  */
     880                 :      675573 :   while (!reachable.is_empty ())
     881                 :      541175 :     reachable.pop ()->flags &= ~reachable_flag;
     882                 :       67199 : }
     883                 :             : 
     884                 :             : /* Evaluate how many instruction will we have if we unswitch LOOP (with BBS)
     885                 :             :    based on PREDICATE predicate (using PREDICATE_PATH).  Store the
     886                 :             :    result in TRUE_SIZE and FALSE_SIZE.  */
     887                 :             : 
     888                 :             : static void
     889                 :        1355 : evaluate_loop_insns_for_predicate (class loop *loop,
     890                 :             :                                    predicate_vector &predicate_path,
     891                 :             :                                    unswitch_predicate *predicate,
     892                 :             :                                    int ignored_edge_flag,
     893                 :             :                                    unsigned *true_size, unsigned *false_size)
     894                 :             : {
     895                 :        1355 :   unsigned size = 0;
     896                 :      237036 :   auto sum_size = [&](basic_block bb) -> bool
     897                 :      235681 :     { size += (uintptr_t)bb->aux; return false; };
     898                 :             : 
     899                 :        1355 :   add_predicate_to_path (predicate_path, predicate, true);
     900                 :        1355 :   evaluate_bbs (loop, &predicate_path, ignored_edge_flag, sum_size);
     901                 :        1355 :   predicate_path.pop ();
     902                 :        1355 :   unsigned true_loop_cost = size;
     903                 :             : 
     904                 :        1355 :   size = 0;
     905                 :        1355 :   add_predicate_to_path (predicate_path, predicate, false);
     906                 :        1355 :   evaluate_bbs (loop, &predicate_path, ignored_edge_flag, sum_size);
     907                 :        1355 :   predicate_path.pop ();
     908                 :        1355 :   unsigned false_loop_cost = size;
     909                 :             : 
     910                 :        1355 :   *true_size = true_loop_cost;
     911                 :        1355 :   *false_size = false_loop_cost;
     912                 :        1355 : }
     913                 :             : 
     914                 :             : /* Unswitch single LOOP.  PREDICATE_PATH contains so far used predicates
     915                 :             :    for unswitching.  BUDGET is number of instruction for which we can increase
     916                 :             :    the loop and is updated when unswitching occurs.  If HOTTEST is not
     917                 :             :    NULL then pick this candidate as the one to unswitch on.  */
     918                 :             : 
     919                 :             : static bool
     920                 :       66232 : tree_unswitch_single_loop (class loop *loop, dump_user_location_t loc,
     921                 :             :                            predicate_vector &predicate_path,
     922                 :             :                            unsigned loop_size, unsigned &budget,
     923                 :             :                            int ignored_edge_flag, bitmap handled,
     924                 :             :                            unswitch_predicate *hottest, basic_block hottest_bb)
     925                 :             : {
     926                 :       66232 :   class loop *nloop;
     927                 :       66232 :   bool changed = false;
     928                 :       66232 :   unswitch_predicate *predicate = NULL;
     929                 :       66232 :   basic_block predicate_bb = NULL;
     930                 :       66232 :   unsigned true_size = 0, false_size = 0;
     931                 :             : 
     932                 :      371655 :   auto check_predicates = [&](basic_block bb) -> bool
     933                 :             :     {
     934                 :      329315 :       for (auto pred : get_predicates_for_bb (bb))
     935                 :             :         {
     936                 :        8422 :           if (bitmap_bit_p (handled, pred->num))
     937                 :        7067 :             continue;
     938                 :             : 
     939                 :        1355 :           evaluate_loop_insns_for_predicate (loop, predicate_path,
     940                 :             :                                              pred, ignored_edge_flag,
     941                 :             :                                              &true_size, &false_size);
     942                 :             : 
     943                 :             :           /* We'll get LOOP replaced with a simplified version according
     944                 :             :              to PRED estimated to TRUE_SIZE and a copy simplified
     945                 :             :              according to the inverted PRED estimated to FALSE_SIZE.  */
     946                 :        1355 :           if (true_size + false_size < budget + loop_size)
     947                 :             :             {
     948                 :         702 :               predicate = pred;
     949                 :         702 :               predicate_bb = bb;
     950                 :             : 
     951                 :             :               /* There are cases where true_size and false_size add up to
     952                 :             :                  less than the original loop_size.  We do not want to
     953                 :             :                  grow the remaining budget because of that.  */
     954                 :         702 :               if (true_size + false_size > loop_size)
     955                 :         702 :                 budget -= (true_size + false_size - loop_size);
     956                 :             : 
     957                 :             :               /* FIXME: right now we select first candidate, but we can
     958                 :             :                  choose the cheapest or hottest one.  */
     959                 :         702 :               return true;
     960                 :             :             }
     961                 :         653 :           else if (dump_enabled_p ())
     962                 :          13 :             dump_printf_loc (MSG_NOTE, loc,
     963                 :             :                              "not unswitching condition, cost too big "
     964                 :             :                              "(%u insns copied to %u and %u)\n", loop_size,
     965                 :             :                              true_size, false_size);
     966                 :             :         }
     967                 :             :       return false;
     968                 :       66232 :     };
     969                 :             : 
     970                 :       66232 :   if (hottest)
     971                 :             :     {
     972                 :        1743 :       predicate = hottest;
     973                 :        1743 :       predicate_bb = hottest_bb;
     974                 :             :     }
     975                 :             :   else
     976                 :             :     /* Check predicates of reachable blocks.  */
     977                 :       64489 :     evaluate_bbs (loop, NULL, ignored_edge_flag, check_predicates);
     978                 :             : 
     979                 :       66232 :   if (predicate != NULL)
     980                 :             :     {
     981                 :        2445 :       if (!dbg_cnt (loop_unswitch))
     982                 :           0 :         goto exit;
     983                 :             : 
     984                 :        2445 :       if (dump_enabled_p ())
     985                 :             :         {
     986                 :         101 :           dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
     987                 :             :                            "unswitching %sloop %d on %qs with condition: %T\n",
     988                 :         101 :                            loop->inner ? "outer " : "",
     989                 :         101 :                            loop->num, predicate->switch_p ? "switch" : "if",
     990                 :             :                            predicate->condition);
     991                 :         101 :           dump_printf_loc (MSG_NOTE, loc,
     992                 :             :                            "optimized sizes estimated to %u (true) "
     993                 :             :                            "and %u (false) from original size %u\n",
     994                 :             :                            true_size, false_size, loop_size);
     995                 :             :         }
     996                 :             : 
     997                 :        2445 :       bitmap_set_bit (handled, predicate->num);
     998                 :        2445 :       initialize_original_copy_tables ();
     999                 :             :       /* Unswitch the loop on this condition.  */
    1000                 :        2445 :       nloop = tree_unswitch_loop (loop, EDGE_SUCC (predicate_bb,
    1001                 :             :                                                    predicate->edge_index),
    1002                 :             :                                   predicate->condition);
    1003                 :        2445 :       if (!nloop)
    1004                 :             :         {
    1005                 :           8 :           free_original_copy_tables ();
    1006                 :           8 :           goto exit;
    1007                 :             :         }
    1008                 :             : 
    1009                 :             :       /* Copy BB costs.  */
    1010                 :        2437 :       basic_block *bbs2 = get_loop_body (nloop);
    1011                 :       24271 :       for (unsigned i = 0; i < nloop->num_nodes; i++)
    1012                 :       21834 :         bbs2[i]->aux = get_bb_original (bbs2[i])->aux;
    1013                 :        2437 :       free (bbs2);
    1014                 :             : 
    1015                 :        2437 :       free_original_copy_tables ();
    1016                 :             : 
    1017                 :             :       /* Update the SSA form after unswitching.  */
    1018                 :        2437 :       update_ssa (TODO_update_ssa_no_phi);
    1019                 :             : 
    1020                 :             :       /* Invoke itself on modified loops.  */
    1021                 :        2437 :       bitmap handled_copy = BITMAP_ALLOC (NULL);
    1022                 :        2437 :       bitmap_copy (handled_copy, handled);
    1023                 :        2437 :       add_predicate_to_path (predicate_path, predicate, false);
    1024                 :        2437 :       changed |= simplify_loop_version (nloop, predicate_path,
    1025                 :             :                                         ignored_edge_flag, handled_copy);
    1026                 :        2437 :       tree_unswitch_single_loop (nloop, loc, predicate_path,
    1027                 :             :                                  false_size, budget,
    1028                 :             :                                  ignored_edge_flag, handled_copy);
    1029                 :        2437 :       predicate_path.pop ();
    1030                 :        2437 :       BITMAP_FREE (handled_copy);
    1031                 :             : 
    1032                 :             :       /* FIXME: After unwinding above we have to reset all ->handled
    1033                 :             :          flags as otherwise we fail to realize unswitching opportunities
    1034                 :             :          in the below recursion.  See gcc.dg/loop-unswitch-16.c  */
    1035                 :        2437 :       add_predicate_to_path (predicate_path, predicate, true);
    1036                 :        2437 :       changed |= simplify_loop_version (loop, predicate_path,
    1037                 :             :                                         ignored_edge_flag, handled);
    1038                 :        2437 :       tree_unswitch_single_loop (loop, loc, predicate_path,
    1039                 :             :                                  true_size, budget,
    1040                 :             :                                  ignored_edge_flag, handled);
    1041                 :        2437 :       predicate_path.pop ();
    1042                 :        2437 :       changed = true;
    1043                 :             :     }
    1044                 :             : 
    1045                 :       63787 : exit:
    1046                 :       66232 :   return changed;
    1047                 :             : }
    1048                 :             : 
    1049                 :             : /* Unswitch a LOOP w.r. to given EDGE_TRUE.  We only support unswitching of
    1050                 :             :    innermost loops.  COND is the condition determining which loop is entered;
    1051                 :             :    the new loop is entered if COND is true.  Returns NULL if impossible, new
    1052                 :             :    loop otherwise.  */
    1053                 :             : 
    1054                 :             : static class loop *
    1055                 :        2445 : tree_unswitch_loop (class loop *loop, edge edge_true, tree cond)
    1056                 :             : {
    1057                 :             :   /* Some sanity checking.  */
    1058                 :        2445 :   gcc_assert (flow_bb_inside_loop_p (loop, edge_true->src));
    1059                 :        2445 :   gcc_assert (EDGE_COUNT (edge_true->src->succs) >= 2);
    1060                 :             : 
    1061                 :        2445 :   profile_probability prob_true = edge_true->probability;
    1062                 :        2445 :   return loop_version (loop, unshare_expr (cond),
    1063                 :             :                        NULL, prob_true,
    1064                 :             :                        prob_true.invert (),
    1065                 :             :                        prob_true, prob_true.invert (),
    1066                 :        2445 :                        false);
    1067                 :             : }
    1068                 :             : 
    1069                 :             : /* Unswitch outer loops by hoisting invariant guard on
    1070                 :             :    inner loop without code duplication.  */
    1071                 :             : static bool
    1072                 :       14226 : tree_unswitch_outer_loop (class loop *loop)
    1073                 :             : {
    1074                 :       14226 :   edge exit, guard;
    1075                 :       14226 :   HOST_WIDE_INT iterations;
    1076                 :             : 
    1077                 :       14226 :   gcc_assert (loop->inner);
    1078                 :       14226 :   if (loop->inner->next)
    1079                 :             :     return false;
    1080                 :             :   /* Accept loops with single exit only which is not from inner loop.  */
    1081                 :       12124 :   exit = single_exit (loop);
    1082                 :       12124 :   if (!exit || exit->src->loop_father != loop)
    1083                 :             :     return false;
    1084                 :             :   /* Check that phi argument of exit edge is not defined inside loop.  */
    1085                 :        8332 :   if (!check_exit_phi (loop))
    1086                 :             :     return false;
    1087                 :             :   /* If the loop is not expected to iterate, there is no need
    1088                 :             :       for unswitching.  */
    1089                 :        5900 :   iterations = estimated_loop_iterations_int (loop);
    1090                 :        5900 :   if (iterations < 0)
    1091                 :        3504 :     iterations = likely_max_loop_iterations_int (loop);
    1092                 :        5900 :   if (iterations >= 0 && iterations <= 1)
    1093                 :             :     {
    1094                 :         267 :       if (dump_enabled_p ())
    1095                 :           0 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, find_loop_location (loop),
    1096                 :             :                          "Not unswitching, loop is not expected"
    1097                 :             :                          " to iterate\n");
    1098                 :         267 :       return false;
    1099                 :             :     }
    1100                 :             : 
    1101                 :        5633 :   bool changed = false;
    1102                 :        5633 :   auto_vec<gimple *> dbg_to_reset;
    1103                 :        7317 :   while ((guard = find_loop_guard (loop, dbg_to_reset)))
    1104                 :             :     {
    1105                 :        1684 :       hoist_guard (loop, guard);
    1106                 :        1684 :       for (gimple *debug_stmt : dbg_to_reset)
    1107                 :             :         {
    1108                 :           0 :           gimple_debug_bind_reset_value (debug_stmt);
    1109                 :           0 :           update_stmt (debug_stmt);
    1110                 :             :         }
    1111                 :        1684 :       dbg_to_reset.truncate (0);
    1112                 :        1684 :       changed = true;
    1113                 :             :     }
    1114                 :        5633 :   return changed;
    1115                 :        5633 : }
    1116                 :             : 
    1117                 :             : /* Checks if the body of the LOOP is within an invariant guard.  If this
    1118                 :             :    is the case, returns the edge that jumps over the real body of the loop,
    1119                 :             :    otherwise returns NULL.  */
    1120                 :             : 
    1121                 :             : static edge
    1122                 :        7317 : find_loop_guard (class loop *loop, vec<gimple *> &dbg_to_reset)
    1123                 :             : {
    1124                 :        7317 :   basic_block header = loop->header;
    1125                 :        7317 :   edge guard_edge, te, fe;
    1126                 :        7317 :   basic_block *body = NULL;
    1127                 :       14450 :   unsigned i;
    1128                 :       14450 :   tree use;
    1129                 :       14450 :   ssa_op_iter iter;
    1130                 :             : 
    1131                 :             :   /* We check for the following situation:
    1132                 :             : 
    1133                 :             :      while (1)
    1134                 :             :        {
    1135                 :             :          [header]]
    1136                 :             :          loop_phi_nodes;
    1137                 :             :          something1;
    1138                 :             :          if (cond1)
    1139                 :             :            body;
    1140                 :             :          nvar = phi(orig, bvar) ... for all variables changed in body;
    1141                 :             :          [guard_end]
    1142                 :             :          something2;
    1143                 :             :          if (cond2)
    1144                 :             :            break;
    1145                 :             :          something3;
    1146                 :             :        }
    1147                 :             : 
    1148                 :             :      where:
    1149                 :             : 
    1150                 :             :      1) cond1 is loop invariant
    1151                 :             :      2) If cond1 is false, then the loop is essentially empty; i.e.,
    1152                 :             :         a) nothing in something1, something2 and something3 has side
    1153                 :             :            effects
    1154                 :             :         b) anything defined in something1, something2 and something3
    1155                 :             :            is not used outside of the loop.  */
    1156                 :             : 
    1157                 :       14450 :   gcond *cond;
    1158                 :       14450 :   do
    1159                 :             :     {
    1160                 :       14450 :       basic_block next = NULL;
    1161                 :       14450 :       if (single_succ_p (header))
    1162                 :        4374 :         next = single_succ (header);
    1163                 :             :       else
    1164                 :             :         {
    1165                 :       25629 :           cond = safe_dyn_cast <gcond *> (*gsi_last_bb (header));
    1166                 :       10074 :           if (! cond)
    1167                 :             :             return NULL;
    1168                 :       10074 :           extract_true_false_edges_from_block (header, &te, &fe);
    1169                 :             :           /* Make sure to skip earlier hoisted guards that are left
    1170                 :             :              in place as if (true).  */
    1171                 :       10074 :           if (gimple_cond_true_p (cond))
    1172                 :         324 :             next = te->dest;
    1173                 :        9750 :           else if (gimple_cond_false_p (cond))
    1174                 :        2435 :             next = fe->dest;
    1175                 :             :           else
    1176                 :             :             break;
    1177                 :             :         }
    1178                 :             :       /* Never traverse a backedge.  */
    1179                 :        7133 :       if (header->loop_father->header == next)
    1180                 :             :         return NULL;
    1181                 :             :       header = next;
    1182                 :             :     }
    1183                 :             :   while (1);
    1184                 :        7315 :   if (!flow_bb_inside_loop_p (loop, te->dest)
    1185                 :        7315 :       || !flow_bb_inside_loop_p (loop, fe->dest))
    1186                 :          77 :     return NULL;
    1187                 :             : 
    1188                 :        7238 :   if (just_once_each_iteration_p (loop, te->dest)
    1189                 :        7238 :       || (single_succ_p (te->dest)
    1190                 :        4278 :           && just_once_each_iteration_p (loop, single_succ (te->dest))))
    1191                 :             :     {
    1192                 :        3726 :       if (just_once_each_iteration_p (loop, fe->dest))
    1193                 :             :         return NULL;
    1194                 :        3716 :       guard_edge = te;
    1195                 :             :     }
    1196                 :        3512 :   else if (just_once_each_iteration_p (loop, fe->dest)
    1197                 :        3512 :            || (single_succ_p (fe->dest)
    1198                 :        1759 :                && just_once_each_iteration_p (loop, single_succ (fe->dest))))
    1199                 :        2105 :     guard_edge = fe;
    1200                 :             :   else
    1201                 :        1407 :     return NULL;
    1202                 :             : 
    1203                 :        5821 :   dump_user_location_t loc = find_loop_location (loop);
    1204                 :             : 
    1205                 :             :   /* Guard edge must skip inner loop.  */
    1206                 :        5821 :   if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
    1207                 :        5821 :       guard_edge == fe ? te->dest : fe->dest))
    1208                 :             :     {
    1209                 :        2396 :       if (dump_enabled_p ())
    1210                 :           4 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1211                 :             :                          "Guard edge %d --> %d is not around the loop!\n",
    1212                 :           4 :                          guard_edge->src->index, guard_edge->dest->index);
    1213                 :        2396 :       return NULL;
    1214                 :             :     }
    1215                 :        3425 :   if (guard_edge->dest == loop->latch)
    1216                 :             :     {
    1217                 :           0 :       if (dump_enabled_p ())
    1218                 :           0 :         dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1219                 :             :                          "Guard edge destination is loop latch.\n");
    1220                 :           0 :       return NULL;
    1221                 :             :     }
    1222                 :             : 
    1223                 :        3425 :   if (dump_enabled_p ())
    1224                 :          67 :     dump_printf_loc (MSG_NOTE, loc,
    1225                 :             :                      "Considering guard %d -> %d in loop %d\n",
    1226                 :          67 :                      guard_edge->src->index, guard_edge->dest->index,
    1227                 :             :                      loop->num);
    1228                 :             :   /* Check if condition operands do not have definitions inside loop since
    1229                 :             :      any bb copying is not performed.  */
    1230                 :        6091 :   FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
    1231                 :             :     {
    1232                 :        4251 :       gimple *def = SSA_NAME_DEF_STMT (use);
    1233                 :        4251 :       basic_block def_bb = gimple_bb (def);
    1234                 :        4251 :       if (def_bb
    1235                 :        4251 :           && flow_bb_inside_loop_p (loop, def_bb))
    1236                 :             :         {
    1237                 :        1585 :           if (dump_enabled_p ())
    1238                 :          60 :             dump_printf_loc (MSG_NOTE, loc, "guard operands have definitions"
    1239                 :             :                              " inside loop\n");
    1240                 :        1585 :           return NULL;
    1241                 :             :         }
    1242                 :             :     }
    1243                 :             : 
    1244                 :        1840 :   body = get_loop_body (loop);
    1245                 :       21126 :   for (i = 0; i < loop->num_nodes; i++)
    1246                 :             :     {
    1247                 :       19442 :       basic_block bb = body[i];
    1248                 :       19442 :       if (bb->loop_father != loop)
    1249                 :        9660 :         continue;
    1250                 :        9782 :       if (bb->flags & BB_IRREDUCIBLE_LOOP)
    1251                 :             :         {
    1252                 :           0 :           if (dump_enabled_p ())
    1253                 :           0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1254                 :             :                              "Block %d is marked as irreducible in loop\n",
    1255                 :             :                              bb->index);
    1256                 :           0 :           guard_edge = NULL;
    1257                 :           0 :           goto end;
    1258                 :             :         }
    1259                 :             :       /* If any of the not skipped blocks has side-effects or defs with
    1260                 :             :          uses outside of the loop we cannot hoist the guard.  */
    1261                 :        9782 :       if (!dominated_by_p (CDI_DOMINATORS,
    1262                 :        9782 :                            bb, guard_edge == te ? fe->dest : te->dest)
    1263                 :        9782 :           && !empty_bb_without_guard_p (loop, bb, dbg_to_reset))
    1264                 :             :         {
    1265                 :         156 :           if (dump_enabled_p ())
    1266                 :           0 :             dump_printf_loc (MSG_MISSED_OPTIMIZATION, loc,
    1267                 :             :                              "Block %d has side effects\n", bb->index);
    1268                 :         156 :           guard_edge = NULL;
    1269                 :         156 :           goto end;
    1270                 :             :         }
    1271                 :             :     }
    1272                 :             : 
    1273                 :        1684 :   if (dump_enabled_p ())
    1274                 :           7 :     dump_printf_loc (MSG_NOTE, loc,
    1275                 :             :                      "suitable to hoist\n");
    1276                 :        1677 : end:
    1277                 :        1840 :   if (body)
    1278                 :        1840 :     free (body);
    1279                 :             :   return guard_edge;
    1280                 :             : }
    1281                 :             : 
    1282                 :             : /* Returns true if
    1283                 :             :    1) no statement in BB has side effects
    1284                 :             :    2) assuming that edge GUARD is always taken, all definitions in BB
    1285                 :             :       are noy used outside of the loop.
    1286                 :             :    KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
    1287                 :             :    PROCESSED is a set of ssa names for that we already tested whether they
    1288                 :             :    are invariant or not.  Uses in debug stmts outside of the loop are
    1289                 :             :    pushed to DBG_TO_RESET.  */
    1290                 :             : 
    1291                 :             : static bool
    1292                 :        6859 : empty_bb_without_guard_p (class loop *loop, basic_block bb,
    1293                 :             :                           vec<gimple *> &dbg_to_reset)
    1294                 :             : {
    1295                 :        6859 :   basic_block exit_bb = single_exit (loop)->src;
    1296                 :        6859 :   bool may_be_used_outside = (bb == exit_bb
    1297                 :        6859 :                               || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
    1298                 :        5037 :   tree name;
    1299                 :        5037 :   ssa_op_iter op_iter;
    1300                 :             : 
    1301                 :             :   /* Phi nodes do not have side effects, but their results might be used
    1302                 :             :      outside of the loop.  */
    1303                 :        5037 :   if (may_be_used_outside)
    1304                 :             :     {
    1305                 :        5037 :       for (gphi_iterator gsi = gsi_start_phis (bb);
    1306                 :       10680 :            !gsi_end_p (gsi); gsi_next (&gsi))
    1307                 :             :         {
    1308                 :        5643 :           gphi *phi = gsi.phi ();
    1309                 :        5643 :           name = PHI_RESULT (phi);
    1310                 :       11286 :           if (virtual_operand_p (name))
    1311                 :        3603 :             continue;
    1312                 :             : 
    1313                 :        2040 :           if (used_outside_loop_p (loop, name, dbg_to_reset))
    1314                 :           0 :             return false;
    1315                 :             :         }
    1316                 :             :     }
    1317                 :             : 
    1318                 :       13718 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
    1319                 :       15978 :        !gsi_end_p (gsi); gsi_next (&gsi))
    1320                 :             :     {
    1321                 :        9275 :       gimple *stmt = gsi_stmt (gsi);
    1322                 :        9275 :       if (is_gimple_debug (stmt))
    1323                 :        1061 :         continue;
    1324                 :             : 
    1325                 :        8214 :       if (gimple_has_side_effects (stmt))
    1326                 :             :         return false;
    1327                 :             : 
    1328                 :       12126 :       if (gimple_vdef(stmt))
    1329                 :             :         return false;
    1330                 :             : 
    1331                 :       12016 :       FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
    1332                 :             :         {
    1333                 :        3958 :           if (may_be_used_outside
    1334                 :        3958 :               && used_outside_loop_p (loop, name, dbg_to_reset))
    1335                 :             :             return false;
    1336                 :             :         }
    1337                 :             :     }
    1338                 :             :   return true;
    1339                 :             : }
    1340                 :             : 
    1341                 :             : /* Return true if NAME is used outside of LOOP.  Pushes debug stmts that
    1342                 :             :    have such uses to DBG_TO_RESET but do not consider such uses.  */
    1343                 :             : 
    1344                 :             : static bool
    1345                 :        5976 : used_outside_loop_p (class loop *loop, tree name, vec<gimple *> &dbg_to_reset)
    1346                 :             : {
    1347                 :        5976 :   imm_use_iterator it;
    1348                 :        5976 :   use_operand_p use;
    1349                 :             : 
    1350                 :       17431 :   FOR_EACH_IMM_USE_FAST (use, it, name)
    1351                 :             :     {
    1352                 :       11455 :       gimple *stmt = USE_STMT (use);
    1353                 :       11455 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
    1354                 :             :         {
    1355                 :           0 :           if (!is_gimple_debug (stmt))
    1356                 :           0 :             return true;
    1357                 :           0 :           dbg_to_reset.safe_push (stmt);
    1358                 :             :         }
    1359                 :             :     }
    1360                 :             : 
    1361                 :             :   return false;
    1362                 :             : }
    1363                 :             : 
    1364                 :             : /* Return argument for loop preheader edge in header virtual phi if any.  */
    1365                 :             : 
    1366                 :             : static tree
    1367                 :        1670 : get_vop_from_header (class loop *loop)
    1368                 :             : {
    1369                 :        1670 :   for (gphi_iterator gsi = gsi_start_phis (loop->header);
    1370                 :        3360 :        !gsi_end_p (gsi); gsi_next (&gsi))
    1371                 :             :     {
    1372                 :        3360 :       gphi *phi = gsi.phi ();
    1373                 :        6720 :       if (!virtual_operand_p (gimple_phi_result (phi)))
    1374                 :        1690 :         continue;
    1375                 :        1670 :       return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
    1376                 :             :     }
    1377                 :           0 :   return NULL_TREE;
    1378                 :             : }
    1379                 :             : 
    1380                 :             : /* Move the check of GUARD outside of LOOP.  */
    1381                 :             : 
    1382                 :             : static void
    1383                 :        1684 : hoist_guard (class loop *loop, edge guard)
    1384                 :             : {
    1385                 :        1684 :   edge exit = single_exit (loop);
    1386                 :        1684 :   edge preh = loop_preheader_edge (loop);
    1387                 :        1684 :   basic_block pre_header = preh->src;
    1388                 :        1684 :   basic_block bb;
    1389                 :        1684 :   edge te, fe, e, new_edge;
    1390                 :        1684 :   gimple *stmt;
    1391                 :        1684 :   basic_block guard_bb = guard->src;
    1392                 :        1684 :   edge not_guard;
    1393                 :        1684 :   gimple_stmt_iterator gsi;
    1394                 :        1684 :   int flags = 0;
    1395                 :        1684 :   bool fix_dom_of_exit;
    1396                 :        1684 :   gcond *cond_stmt, *new_cond_stmt;
    1397                 :             : 
    1398                 :        1684 :   bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
    1399                 :        1684 :   fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
    1400                 :        1684 :   gsi = gsi_last_bb (guard_bb);
    1401                 :        1684 :   stmt = gsi_stmt (gsi);
    1402                 :        1684 :   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
    1403                 :        1684 :   cond_stmt = as_a <gcond *> (stmt);
    1404                 :        1684 :   extract_true_false_edges_from_block (guard_bb, &te, &fe);
    1405                 :             :   /* Insert guard to PRE_HEADER.  */
    1406                 :        1684 :   gsi = gsi_last_bb (pre_header);
    1407                 :             :   /* Create copy of COND_STMT.  */
    1408                 :        1684 :   new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
    1409                 :             :                                      gimple_cond_lhs (cond_stmt),
    1410                 :             :                                      gimple_cond_rhs (cond_stmt),
    1411                 :             :                                      NULL_TREE, NULL_TREE);
    1412                 :        1684 :   gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
    1413                 :             :   /* Convert COND_STMT to true/false conditional.  */
    1414                 :        1684 :   if (guard == te)
    1415                 :        1485 :     gimple_cond_make_false (cond_stmt);
    1416                 :             :   else
    1417                 :         199 :     gimple_cond_make_true (cond_stmt);
    1418                 :        1684 :   update_stmt (cond_stmt);
    1419                 :             :   /* Create new loop pre-header.  */
    1420                 :        1684 :   e = split_block (pre_header, last_nondebug_stmt (pre_header));
    1421                 :             : 
    1422                 :        1684 :   dump_user_location_t loc = find_loop_location (loop);
    1423                 :             : 
    1424                 :        1684 :   if (dump_enabled_p ())
    1425                 :             :     {
    1426                 :           7 :       char buffer[64];
    1427                 :           7 :       guard->probability.dump (buffer);
    1428                 :             : 
    1429                 :           7 :       dump_printf_loc (MSG_NOTE, loc,
    1430                 :             :                        "Moving guard %i->%i (prob %s) to bb %i, "
    1431                 :             :                        "new preheader is %i\n",
    1432                 :           7 :                        guard->src->index, guard->dest->index,
    1433                 :           7 :                        buffer, e->src->index, e->dest->index);
    1434                 :             :     }
    1435                 :             : 
    1436                 :        1684 :   gcc_assert (loop_preheader_edge (loop)->src == e->dest);
    1437                 :             : 
    1438                 :        1684 :   if (guard == fe)
    1439                 :             :     {
    1440                 :         199 :       e->flags = EDGE_TRUE_VALUE;
    1441                 :         199 :       flags |= EDGE_FALSE_VALUE;
    1442                 :         199 :       not_guard = te;
    1443                 :             :     }
    1444                 :             :   else
    1445                 :             :     {
    1446                 :        1485 :       e->flags = EDGE_FALSE_VALUE;
    1447                 :        1485 :       flags |= EDGE_TRUE_VALUE;
    1448                 :        1485 :       not_guard = fe;
    1449                 :             :     }
    1450                 :        1684 :   new_edge = make_edge (pre_header, exit->dest, flags);
    1451                 :             : 
    1452                 :             :   /* Determine the probability that we skip the loop.  Assume that loop has
    1453                 :             :      same average number of iterations regardless outcome of guard.  */
    1454                 :        1684 :   new_edge->probability = guard->probability;
    1455                 :        3368 :   profile_count skip_count = guard->src->count.nonzero_p ()
    1456                 :        3368 :                    ? guard->count ().apply_scale (pre_header->count,
    1457                 :        1684 :                                                guard->src->count)
    1458                 :           0 :                    : guard->count ().apply_probability (new_edge->probability);
    1459                 :             : 
    1460                 :        1684 :   if (skip_count > e->count ())
    1461                 :             :     {
    1462                 :           0 :       fprintf (dump_file, "  Capping count; expect profile inconsistency\n");
    1463                 :           0 :       skip_count = e->count ();
    1464                 :             :     }
    1465                 :        1684 :   if (dump_enabled_p ())
    1466                 :             :     {
    1467                 :           7 :       char buffer[64];
    1468                 :           7 :       new_edge->probability.dump (buffer);
    1469                 :             : 
    1470                 :           7 :       dump_printf_loc (MSG_NOTE, loc,
    1471                 :             :                        "Estimated probability of skipping loop is %s\n",
    1472                 :             :                        buffer);
    1473                 :             :     }
    1474                 :             : 
    1475                 :             :   /* Update profile after the transform:
    1476                 :             : 
    1477                 :             :      First decrease count of path from newly hoisted loop guard
    1478                 :             :      to loop header...  */
    1479                 :        1684 :   e->probability = new_edge->probability.invert ();
    1480                 :        1684 :   e->dest->count = e->count ();
    1481                 :             : 
    1482                 :             :   /* ... now update profile to represent that original guard will be optimized
    1483                 :             :      away ...  */
    1484                 :        1684 :   guard->probability = profile_probability::never ();
    1485                 :        1684 :   not_guard->probability = profile_probability::always ();
    1486                 :             : 
    1487                 :             :   /* ... finally scale everything in the loop except for guarded basic blocks
    1488                 :             :      where profile does not change.  */
    1489                 :        1684 :   basic_block *body = get_loop_body (loop);
    1490                 :             : 
    1491                 :       20686 :   for (unsigned int i = 0; i < loop->num_nodes; i++)
    1492                 :             :     {
    1493                 :       19002 :       basic_block bb = body[i];
    1494                 :       19002 :       if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
    1495                 :             :         {
    1496                 :        6419 :           if (dump_enabled_p ())
    1497                 :          27 :             dump_printf_loc (MSG_NOTE, loc,
    1498                 :             :                              "Scaling nonguarded BBs in loop: %i\n",
    1499                 :             :                              bb->index);
    1500                 :        6419 :           if (e->probability.initialized_p ())
    1501                 :        6419 :             scale_bbs_frequencies (&bb, 1, e->probability);
    1502                 :             :         }
    1503                 :             :     }
    1504                 :             : 
    1505                 :        1684 :   if (fix_dom_of_exit)
    1506                 :         645 :     set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
    1507                 :             :   /* Add NEW_ADGE argument for all phi in post-header block.  */
    1508                 :        1684 :   bb = exit->dest;
    1509                 :        1684 :   for (gphi_iterator gsi = gsi_start_phis (bb);
    1510                 :        3551 :        !gsi_end_p (gsi); gsi_next (&gsi))
    1511                 :             :     {
    1512                 :        1867 :       gphi *phi = gsi.phi ();
    1513                 :        1867 :       tree arg;
    1514                 :        3734 :       if (virtual_operand_p (gimple_phi_result (phi)))
    1515                 :             :         {
    1516                 :        1670 :           arg = get_vop_from_header (loop);
    1517                 :        1670 :           if (arg == NULL_TREE)
    1518                 :             :             /* Use exit edge argument.  */
    1519                 :           0 :             arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
    1520                 :        1670 :           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
    1521                 :             :         }
    1522                 :             :       else
    1523                 :             :         {
    1524                 :             :           /* Use exit edge argument.  */
    1525                 :         197 :           arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    1526                 :         197 :           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
    1527                 :             :         }
    1528                 :             :     }
    1529                 :             : 
    1530                 :        1684 :   if (dump_enabled_p ())
    1531                 :           7 :     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
    1532                 :             :                      "Guard hoisted\n");
    1533                 :             : 
    1534                 :        1684 :   free (body);
    1535                 :        1684 : }
    1536                 :             : 
    1537                 :             : /* Return true if phi argument for exit edge can be used
    1538                 :             :    for edge around loop.  */
    1539                 :             : 
    1540                 :             : static bool
    1541                 :        8332 : check_exit_phi (class loop *loop)
    1542                 :             : {
    1543                 :        8332 :   edge exit = single_exit (loop);
    1544                 :        8332 :   basic_block pre_header = loop_preheader_edge (loop)->src;
    1545                 :             : 
    1546                 :        8332 :   for (gphi_iterator gsi = gsi_start_phis (exit->dest);
    1547                 :       14358 :        !gsi_end_p (gsi); gsi_next (&gsi))
    1548                 :             :     {
    1549                 :        8458 :       gphi *phi = gsi.phi ();
    1550                 :        8458 :       tree arg;
    1551                 :        8458 :       gimple *def;
    1552                 :        8458 :       basic_block def_bb;
    1553                 :       16916 :       if (virtual_operand_p (gimple_phi_result (phi)))
    1554                 :        5887 :         continue;
    1555                 :        2571 :       arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
    1556                 :        2571 :       if (TREE_CODE (arg) != SSA_NAME)
    1557                 :          12 :         continue;
    1558                 :        2559 :       def = SSA_NAME_DEF_STMT (arg);
    1559                 :        2559 :       if (!def)
    1560                 :           0 :         continue;
    1561                 :        2559 :       def_bb = gimple_bb (def);
    1562                 :        2559 :       if (!def_bb)
    1563                 :           0 :         continue;
    1564                 :        2559 :       if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
    1565                 :             :         /* Definition inside loop!  */
    1566                 :        2432 :         return false;
    1567                 :             :       /* Check loop closed phi invariant.  */
    1568                 :         127 :       if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
    1569                 :             :         return false;
    1570                 :             :     }
    1571                 :        5900 :   return true;
    1572                 :             : }
    1573                 :             : 
    1574                 :             : /* Remove all dead cases from switches that are unswitched.  */
    1575                 :             : 
    1576                 :             : static void
    1577                 :        1369 : clean_up_after_unswitching (int ignored_edge_flag)
    1578                 :             : {
    1579                 :        1369 :   basic_block bb;
    1580                 :        1369 :   edge e;
    1581                 :        1369 :   edge_iterator ei;
    1582                 :        1369 :   bool removed_edge = false;
    1583                 :             : 
    1584                 :       73403 :   FOR_EACH_BB_FN (bb, cfun)
    1585                 :             :     {
    1586                 :      144068 :       gswitch *stmt= safe_dyn_cast <gswitch *> (*gsi_last_bb (bb));
    1587                 :         149 :       if (stmt && !CONSTANT_CLASS_P (gimple_switch_index (stmt)))
    1588                 :             :         {
    1589                 :          74 :           unsigned nlabels = gimple_switch_num_labels (stmt);
    1590                 :          74 :           unsigned index = 1;
    1591                 :          74 :           tree lab = gimple_switch_default_label (stmt);
    1592                 :         148 :           edge default_e = find_edge (gimple_bb (stmt),
    1593                 :          74 :                                       label_to_block (cfun, CASE_LABEL (lab)));
    1594                 :         329 :           for (unsigned i = 1; i < nlabels; ++i)
    1595                 :             :             {
    1596                 :         255 :               tree lab = gimple_switch_label (stmt, i);
    1597                 :         255 :               basic_block dest = label_to_block (cfun, CASE_LABEL (lab));
    1598                 :         255 :               edge e = find_edge (gimple_bb (stmt), dest);
    1599                 :         255 :               if (e == NULL)
    1600                 :             :                 ; /* The edge is already removed.  */
    1601                 :         247 :               else if (e->flags & ignored_edge_flag)
    1602                 :             :                 {
    1603                 :             :                   /* We may not remove the default label so we also have
    1604                 :             :                      to preserve its edge.  But we can remove the
    1605                 :             :                      non-default CASE sharing the edge.  */
    1606                 :          89 :                   if (e != default_e)
    1607                 :             :                     {
    1608                 :          89 :                       remove_edge (e);
    1609                 :          89 :                       removed_edge = true;
    1610                 :             :                     }
    1611                 :             :                 }
    1612                 :             :               else
    1613                 :             :                 {
    1614                 :         158 :                   gimple_switch_set_label (stmt, index, lab);
    1615                 :         158 :                   ++index;
    1616                 :             :                 }
    1617                 :             :             }
    1618                 :             : 
    1619                 :          74 :           if (index != nlabels)
    1620                 :          35 :             gimple_switch_set_num_labels (stmt, index);
    1621                 :             :         }
    1622                 :             : 
    1623                 :             :       /* Clean up the ignored_edge_flag from edges.  */
    1624                 :      173766 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1625                 :      101732 :         e->flags &= ~ignored_edge_flag;
    1626                 :             :     }
    1627                 :             : 
    1628                 :             :   /* If we removed an edge we possibly have to recompute dominators.  */
    1629                 :        1369 :   if (removed_edge)
    1630                 :          30 :     free_dominance_info (CDI_DOMINATORS);
    1631                 :        1369 : }
    1632                 :             : 
    1633                 :             : /* Loop unswitching pass.  */
    1634                 :             : 
    1635                 :             : namespace {
    1636                 :             : 
    1637                 :             : const pass_data pass_data_tree_unswitch =
    1638                 :             : {
    1639                 :             :   GIMPLE_PASS, /* type */
    1640                 :             :   "unswitch", /* name */
    1641                 :             :   OPTGROUP_LOOP, /* optinfo_flags */
    1642                 :             :   TV_TREE_LOOP_UNSWITCH, /* tv_id */
    1643                 :             :   PROP_cfg, /* properties_required */
    1644                 :             :   0, /* properties_provided */
    1645                 :             :   0, /* properties_destroyed */
    1646                 :             :   0, /* todo_flags_start */
    1647                 :             :   0, /* todo_flags_finish */
    1648                 :             : };
    1649                 :             : 
    1650                 :             : class pass_tree_unswitch : public gimple_opt_pass
    1651                 :             : {
    1652                 :             : public:
    1653                 :      289080 :   pass_tree_unswitch (gcc::context *ctxt)
    1654                 :      578160 :     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
    1655                 :             :   {}
    1656                 :             : 
    1657                 :             :   /* opt_pass methods: */
    1658                 :      240775 :   bool gate (function *) final override { return flag_unswitch_loops != 0; }
    1659                 :             :   unsigned int execute (function *) final override;
    1660                 :             : 
    1661                 :             : }; // class pass_tree_unswitch
    1662                 :             : 
    1663                 :             : unsigned int
    1664                 :       27524 : pass_tree_unswitch::execute (function *fun)
    1665                 :             : {
    1666                 :       55048 :   if (number_of_loops (fun) <= 1)
    1667                 :             :     return 0;
    1668                 :             : 
    1669                 :       27524 :   return tree_ssa_unswitch_loops (fun);
    1670                 :             : }
    1671                 :             : 
    1672                 :             : } // anon namespace
    1673                 :             : 
    1674                 :             : gimple_opt_pass *
    1675                 :      289080 : make_pass_tree_unswitch (gcc::context *ctxt)
    1676                 :             : {
    1677                 :      289080 :   return new pass_tree_unswitch (ctxt);
    1678                 :             : }
    1679                 :             : 
    1680                 :             : 
        

Generated by: LCOV version 2.1-beta

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