LCOV - code coverage report
Current view: top level - gcc - tree-ssa-loop-unswitch.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 424 444 95.5 %
Date: 2020-04-04 11:58:09 Functions: 16 16 100.0 %
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-2020 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                 :            : 
      41                 :            : /* This file implements the loop unswitching, i.e. transformation of loops like
      42                 :            : 
      43                 :            :    while (A)
      44                 :            :      {
      45                 :            :        if (inv)
      46                 :            :          B;
      47                 :            : 
      48                 :            :        X;
      49                 :            : 
      50                 :            :        if (!inv)
      51                 :            :          C;
      52                 :            :      }
      53                 :            : 
      54                 :            :    where inv is the loop invariant, into
      55                 :            : 
      56                 :            :    if (inv)
      57                 :            :      {
      58                 :            :        while (A)
      59                 :            :          {
      60                 :            :            B;
      61                 :            :            X;
      62                 :            :          }
      63                 :            :      }
      64                 :            :    else
      65                 :            :      {
      66                 :            :        while (A)
      67                 :            :          {
      68                 :            :            X;
      69                 :            :            C;
      70                 :            :          }
      71                 :            :      }
      72                 :            : 
      73                 :            :    Inv is considered invariant iff the values it compares are both invariant;
      74                 :            :    tree-ssa-loop-im.c ensures that all the suitable conditions are in this
      75                 :            :    shape.  */
      76                 :            : 
      77                 :            : static class loop *tree_unswitch_loop (class loop *, basic_block, tree);
      78                 :            : static bool tree_unswitch_single_loop (class loop *, int);
      79                 :            : static tree tree_may_unswitch_on (basic_block, class loop *);
      80                 :            : static bool tree_unswitch_outer_loop (class loop *);
      81                 :            : static edge find_loop_guard (class loop *);
      82                 :            : static bool empty_bb_without_guard_p (class loop *, basic_block);
      83                 :            : static bool used_outside_loop_p (class loop *, tree);
      84                 :            : static void hoist_guard (class loop *, edge);
      85                 :            : static bool check_exit_phi (class loop *);
      86                 :            : static tree get_vop_from_header (class loop *);
      87                 :            : 
      88                 :            : /* Main entry point.  Perform loop unswitching on all suitable loops.  */
      89                 :            : 
      90                 :            : unsigned int
      91                 :      17764 : tree_ssa_unswitch_loops (void)
      92                 :            : {
      93                 :      17764 :   class loop *loop;
      94                 :      17764 :   bool changed = false;
      95                 :            : 
      96                 :            :   /* Go through all loops starting from innermost.  */
      97                 :      63318 :   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
      98                 :            :     {
      99                 :      45554 :       if (!loop->inner)
     100                 :            :         /* Unswitch innermost loop.  */
     101                 :      38011 :         changed |= tree_unswitch_single_loop (loop, 0);
     102                 :            :       else
     103                 :       7543 :         changed |= tree_unswitch_outer_loop (loop);
     104                 :            :     }
     105                 :            : 
     106                 :      17764 :   if (changed)
     107                 :       1243 :     return TODO_cleanup_cfg;
     108                 :            :   return 0;
     109                 :            : }
     110                 :            : 
     111                 :            : /* Return TRUE if an SSA_NAME maybe undefined and is therefore
     112                 :            :    unsuitable for unswitching.  STMT is the statement we are
     113                 :            :    considering for unswitching and LOOP is the loop it appears in.  */
     114                 :            : 
     115                 :            : static bool
     116                 :      14831 : is_maybe_undefined (const tree name, gimple *stmt, class loop *loop)
     117                 :            : {
     118                 :            :   /* The loop header is the only block we can trivially determine that
     119                 :            :      will always be executed.  If the comparison is in the loop
     120                 :            :      header, we know it's OK to unswitch on it.  */
     121                 :      14831 :   if (gimple_bb (stmt) == loop->header)
     122                 :            :     return false;
     123                 :            : 
     124                 :       7041 :   auto_bitmap visited_ssa;
     125                 :      14082 :   auto_vec<tree> worklist;
     126                 :       7041 :   worklist.safe_push (name);
     127                 :       7041 :   bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name));
     128                 :      15751 :   while (!worklist.is_empty ())
     129                 :            :     {
     130                 :       9289 :       tree t = worklist.pop ();
     131                 :            : 
     132                 :            :       /* If it's obviously undefined, avoid further computations.  */
     133                 :       9289 :       if (ssa_undefined_value_p (t, true))
     134                 :        579 :         return true;
     135                 :            : 
     136                 :       9055 :       if (ssa_defined_default_def_p (t))
     137                 :       8011 :         continue;
     138                 :            : 
     139                 :       7786 :       gimple *def = SSA_NAME_DEF_STMT (t);
     140                 :            : 
     141                 :            :       /* Check that all the PHI args are fully defined.  */
     142                 :       7786 :       if (gphi *phi = dyn_cast <gphi *> (def))
     143                 :            :         {
     144                 :       4695 :           for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
     145                 :            :             {
     146                 :       3191 :               tree t = gimple_phi_arg_def (phi, i);
     147                 :            :               /* If an SSA has already been seen, it may be a loop,
     148                 :            :                  but we can continue and ignore this use.  Otherwise,
     149                 :            :                  add the SSA_NAME to the queue and visit it later.  */
     150                 :       3191 :               if (TREE_CODE (t) == SSA_NAME
     151                 :       3191 :                   && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
     152                 :       2977 :                 worklist.safe_push (t);
     153                 :            :             }
     154                 :       1504 :           continue;
     155                 :            :         }
     156                 :            : 
     157                 :            :       /* Uses in stmts always executed when the region header executes
     158                 :            :          are fine.  */
     159                 :       6282 :       if (dominated_by_p (CDI_DOMINATORS, loop->header, gimple_bb (def)))
     160                 :       5238 :         continue;
     161                 :            : 
     162                 :            :       /* Handle calls and memory loads conservatively.  */
     163                 :       1044 :       if (!is_gimple_assign (def)
     164                 :       1387 :           || (gimple_assign_single_p (def)
     165                 :        343 :               && gimple_vuse (def)))
     166                 :            :         return true;
     167                 :            : 
     168                 :            :       /* Check that any SSA names used to define NAME are also fully
     169                 :            :          defined.  */
     170                 :        699 :       use_operand_p use_p;
     171                 :        699 :       ssa_op_iter iter;
     172                 :       1398 :       FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE)
     173                 :            :         {
     174                 :        699 :           tree t = USE_FROM_PTR (use_p);
     175                 :            :           /* If an SSA has already been seen, it may be a loop,
     176                 :            :              but we can continue and ignore this use.  Otherwise,
     177                 :            :              add the SSA_NAME to the queue and visit it later.  */
     178                 :        699 :           if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t)))
     179                 :        147 :             worklist.safe_push (t);
     180                 :            :         }
     181                 :            :     }
     182                 :            :   return false;
     183                 :            : }
     184                 :            : 
     185                 :            : /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
     186                 :            :    basic blocks (for what it means see comments below).  */
     187                 :            : 
     188                 :            : static tree
     189                 :     124948 : tree_may_unswitch_on (basic_block bb, class loop *loop)
     190                 :            : {
     191                 :     124948 :   gimple *last, *def;
     192                 :     124948 :   gcond *stmt;
     193                 :     124948 :   tree cond, use;
     194                 :     124948 :   basic_block def_bb;
     195                 :     124948 :   ssa_op_iter iter;
     196                 :            : 
     197                 :            :   /* BB must end in a simple conditional jump.  */
     198                 :     124948 :   last = last_stmt (bb);
     199                 :     124948 :   if (!last || gimple_code (last) != GIMPLE_COND)
     200                 :            :     return NULL_TREE;
     201                 :      66734 :   stmt = as_a <gcond *> (last);
     202                 :            : 
     203                 :            :   /* To keep the things simple, we do not directly remove the conditions,
     204                 :            :      but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
     205                 :            :      loop where we would unswitch again on such a condition.  */
     206                 :      66734 :   if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
     207                 :            :     return NULL_TREE;
     208                 :            : 
     209                 :            :   /* Condition must be invariant.  */
     210                 :      79248 :   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     211                 :            :     {
     212                 :      72831 :       def = SSA_NAME_DEF_STMT (use);
     213                 :      72831 :       def_bb = gimple_bb (def);
     214                 :      72831 :       if (def_bb
     215                 :      72831 :           && flow_bb_inside_loop_p (loop, def_bb))
     216                 :            :         return NULL_TREE;
     217                 :            :       /* Unswitching on undefined values would introduce undefined
     218                 :            :          behavior that the original program might never exercise.  */
     219                 :      14831 :       if (is_maybe_undefined (use, stmt, loop))
     220                 :            :         return NULL_TREE;
     221                 :            :     }
     222                 :            : 
     223                 :       6417 :   cond = build2 (gimple_cond_code (stmt), boolean_type_node,
     224                 :            :                  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
     225                 :            : 
     226                 :       6417 :   return cond;
     227                 :            : }
     228                 :            : 
     229                 :            : /* Simplifies COND using checks in front of the entry of the LOOP.  Just very
     230                 :            :    simplish (sufficient to prevent us from duplicating loop in unswitching
     231                 :            :    unnecessarily).  */
     232                 :            : 
     233                 :            : static tree
     234                 :       5892 : simplify_using_entry_checks (class loop *loop, tree cond)
     235                 :            : {
     236                 :       5892 :   edge e = loop_preheader_edge (loop);
     237                 :      14119 :   gimple *stmt;
     238                 :            : 
     239                 :      14119 :   while (1)
     240                 :            :     {
     241                 :      14119 :       stmt = last_stmt (e->src);
     242                 :      14119 :       if (stmt
     243                 :       8196 :           && gimple_code (stmt) == GIMPLE_COND
     244                 :       6417 :           && gimple_cond_code (stmt) == TREE_CODE (cond)
     245                 :       5464 :           && operand_equal_p (gimple_cond_lhs (stmt),
     246                 :       5464 :                               TREE_OPERAND (cond, 0), 0)
     247                 :      18019 :           && operand_equal_p (gimple_cond_rhs (stmt),
     248                 :       3900 :                               TREE_OPERAND (cond, 1), 0))
     249                 :       3542 :         return (e->flags & EDGE_TRUE_VALUE
     250                 :       3542 :                 ? boolean_true_node
     251                 :       3542 :                 : boolean_false_node);
     252                 :            : 
     253                 :      10577 :       if (!single_pred_p (e->src))
     254                 :            :         return cond;
     255                 :            : 
     256                 :       9146 :       e = single_pred_edge (e->src);
     257                 :       9146 :       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     258                 :            :         return cond;
     259                 :            :     }
     260                 :            : }
     261                 :            : 
     262                 :            : /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
     263                 :            :    it to grow too much, it is too easy to create example on that the code would
     264                 :            :    grow exponentially.  */
     265                 :            : 
     266                 :            : static bool
     267                 :      41387 : tree_unswitch_single_loop (class loop *loop, int num)
     268                 :            : {
     269                 :      41387 :   basic_block *bbs;
     270                 :      41387 :   class loop *nloop;
     271                 :      41387 :   unsigned i, found;
     272                 :      41387 :   tree cond = NULL_TREE;
     273                 :      41387 :   gimple *stmt;
     274                 :      41387 :   bool changed = false;
     275                 :      41387 :   HOST_WIDE_INT iterations;
     276                 :            : 
     277                 :            :   /* Perform initial tests if unswitch is eligible.  */
     278                 :      41387 :   if (num == 0)
     279                 :            :     {
     280                 :            :       /* Do not unswitch in cold regions. */
     281                 :      38011 :       if (optimize_loop_for_size_p (loop))
     282                 :            :         {
     283                 :        771 :           if (dump_file && (dump_flags & TDF_DETAILS))
     284                 :          0 :             fprintf (dump_file, ";; Not unswitching cold loops\n");
     285                 :        771 :           return false;
     286                 :            :         }
     287                 :            : 
     288                 :            :       /* The loop should not be too large, to limit code growth. */
     289                 :      37240 :       if (tree_num_loop_insns (loop, &eni_size_weights)
     290                 :      37240 :           > (unsigned) param_max_unswitch_insns)
     291                 :            :         {
     292                 :       1047 :           if (dump_file && (dump_flags & TDF_DETAILS))
     293                 :          0 :             fprintf (dump_file, ";; Not unswitching, loop too big\n");
     294                 :       1047 :           return false;
     295                 :            :         }
     296                 :            : 
     297                 :            :       /* If the loop is not expected to iterate, there is no need
     298                 :            :          for unswitching.  */
     299                 :      36193 :       iterations = estimated_loop_iterations_int (loop);
     300                 :      36193 :       if (iterations < 0)
     301                 :      22573 :         iterations = likely_max_loop_iterations_int (loop);
     302                 :      36193 :       if (iterations >= 0 && iterations <= 1)
     303                 :            :         {
     304                 :        699 :           if (dump_file && (dump_flags & TDF_DETAILS))
     305                 :          0 :             fprintf (dump_file, ";; Not unswitching, loop is not expected"
     306                 :            :                      " to iterate\n");
     307                 :        699 :           return false;
     308                 :            :         }
     309                 :            :     }
     310                 :            : 
     311                 :      38870 :   i = 0;
     312                 :      38870 :   bbs = get_loop_body (loop);
     313                 :      38870 :   found = loop->num_nodes;
     314                 :            : 
     315                 :     162102 :   while (1)
     316                 :            :     {
     317                 :            :       /* Find a bb to unswitch on.  */
     318                 :     280612 :       for (; i < loop->num_nodes; i++)
     319                 :     124402 :         if ((cond = tree_may_unswitch_on (bbs[i], loop)))
     320                 :            :           break;
     321                 :            : 
     322                 :      43592 :       if (i == loop->num_nodes)
     323                 :            :         {
     324                 :      37700 :           if (dump_file
     325                 :         23 :               && num > param_max_unswitch_level
     326                 :      37700 :               && (dump_flags & TDF_DETAILS))
     327                 :          0 :             fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
     328                 :            : 
     329                 :      37700 :           if (found == loop->num_nodes)
     330                 :            :             {
     331                 :      36898 :               free (bbs);
     332                 :      36898 :               return changed;
     333                 :            :             }
     334                 :            :           break;
     335                 :            :         }
     336                 :            : 
     337                 :       5892 :       cond = simplify_using_entry_checks (loop, cond);
     338                 :       5892 :       stmt = last_stmt (bbs[i]);
     339                 :       5892 :       if (integer_nonzerop (cond))
     340                 :            :         {
     341                 :            :           /* Remove false path.  */
     342                 :       1771 :           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
     343                 :            :                                                boolean_true_node);
     344                 :       1771 :           changed = true;
     345                 :            :         }
     346                 :       4121 :       else if (integer_zerop (cond))
     347                 :            :         {
     348                 :            :           /* Remove true path.  */
     349                 :       1771 :           gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
     350                 :            :                                                boolean_false_node);
     351                 :       1771 :           changed = true;
     352                 :            :         }
     353                 :            :       /* Do not unswitch too much.  */
     354                 :       2350 :       else if (num > param_max_unswitch_level)
     355                 :            :         {
     356                 :         56 :           i++;
     357                 :         56 :           continue;
     358                 :            :         }
     359                 :            :       /* In nested tree_unswitch_single_loop first optimize all conditions
     360                 :            :          using entry checks, then discover still reachable blocks in the
     361                 :            :          loop and find the condition only among those still reachable bbs.  */
     362                 :       2294 :       else if (num != 0)
     363                 :            :         {
     364                 :       1124 :           if (found == loop->num_nodes)
     365                 :        802 :             found = i;
     366                 :       1124 :           i++;
     367                 :       1124 :           continue;
     368                 :            :         }
     369                 :            :       else
     370                 :            :         {
     371                 :            :           found = i;
     372                 :            :           break;
     373                 :            :         }
     374                 :            : 
     375                 :       3542 :       update_stmt (stmt);
     376                 :       3542 :       i++;
     377                 :            :     }
     378                 :            : 
     379                 :       1972 :   if (num != 0)
     380                 :            :     {
     381                 :        802 :       basic_block *tos, *worklist;
     382                 :            : 
     383                 :            :       /* When called recursively, first do a quick discovery
     384                 :            :          of reachable bbs after the above changes and only
     385                 :            :          consider conditions in still reachable bbs.  */
     386                 :        802 :       tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
     387                 :            : 
     388                 :       6742 :       for (i = 0; i < loop->num_nodes; i++)
     389                 :       5940 :         bbs[i]->flags &= ~BB_REACHABLE;
     390                 :            : 
     391                 :            :       /* Start with marking header.  */
     392                 :        802 :       *tos++ = bbs[0];
     393                 :        802 :       bbs[0]->flags |= BB_REACHABLE;
     394                 :            : 
     395                 :            :       /* Iterate: find everything reachable from what we've already seen
     396                 :            :          within the same innermost loop.  Don't look through false edges
     397                 :            :          if condition is always true or true edges if condition is
     398                 :            :          always false.  */
     399                 :       5344 :       while (tos != worklist)
     400                 :            :         {
     401                 :       4542 :           basic_block b = *--tos;
     402                 :       4542 :           edge e;
     403                 :       4542 :           edge_iterator ei;
     404                 :       4542 :           int flags = 0;
     405                 :            : 
     406                 :       4542 :           if (EDGE_COUNT (b->succs) == 2)
     407                 :            :             {
     408                 :       2822 :               gimple *stmt = last_stmt (b);
     409                 :       2822 :               if (stmt
     410                 :       2822 :                   && gimple_code (stmt) == GIMPLE_COND)
     411                 :            :                 {
     412                 :       2812 :                   gcond *cond_stmt = as_a <gcond *> (stmt);
     413                 :       2812 :                   if (gimple_cond_true_p (cond_stmt))
     414                 :            :                     flags = EDGE_FALSE_VALUE;
     415                 :       2225 :                   else if (gimple_cond_false_p (cond_stmt))
     416                 :        597 :                     flags = EDGE_TRUE_VALUE;
     417                 :            :                 }
     418                 :            :             }
     419                 :            : 
     420                 :      11910 :           FOR_EACH_EDGE (e, ei, b->succs)
     421                 :            :             {
     422                 :       7368 :               basic_block dest = e->dest;
     423                 :            : 
     424                 :       7368 :               if (dest->loop_father == loop
     425                 :       6294 :                   && !(dest->flags & BB_REACHABLE)
     426                 :       4611 :                   && !(e->flags & flags))
     427                 :            :                 {
     428                 :       3740 :                   *tos++ = dest;
     429                 :       3740 :                   dest->flags |= BB_REACHABLE;
     430                 :            :                 }
     431                 :            :             }
     432                 :            :         }
     433                 :            : 
     434                 :        802 :       free (worklist);
     435                 :            : 
     436                 :            :       /* Find a bb to unswitch on.  */
     437                 :       1250 :       for (; found < loop->num_nodes; found++)
     438                 :        973 :         if ((bbs[found]->flags & BB_REACHABLE)
     439                 :        973 :             && (cond = tree_may_unswitch_on (bbs[found], loop)))
     440                 :            :           break;
     441                 :            : 
     442                 :        802 :       if (found == loop->num_nodes)
     443                 :            :         {
     444                 :        277 :           free (bbs);
     445                 :        277 :           return changed;
     446                 :            :         }
     447                 :            :     }
     448                 :            : 
     449                 :       1695 :   if (dump_file && (dump_flags & TDF_DETAILS))
     450                 :          7 :     fprintf (dump_file, ";; Unswitching loop\n");
     451                 :            : 
     452                 :       1695 :   initialize_original_copy_tables ();
     453                 :            :   /* Unswitch the loop on this condition.  */
     454                 :       1695 :   nloop = tree_unswitch_loop (loop, bbs[found], cond);
     455                 :       1695 :   if (!nloop)
     456                 :            :     {
     457                 :          7 :       free_original_copy_tables ();
     458                 :          7 :       free (bbs);
     459                 :          7 :       return changed;
     460                 :            :     }
     461                 :            : 
     462                 :            :   /* Update the SSA form after unswitching.  */
     463                 :       1688 :   update_ssa (TODO_update_ssa);
     464                 :       1688 :   free_original_copy_tables ();
     465                 :            : 
     466                 :            :   /* Invoke itself on modified loops.  */
     467                 :       1688 :   tree_unswitch_single_loop (nloop, num + 1);
     468                 :       1688 :   tree_unswitch_single_loop (loop, num + 1);
     469                 :       1688 :   free (bbs);
     470                 :       1688 :   return true;
     471                 :            : }
     472                 :            : 
     473                 :            : /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
     474                 :            :    unswitching of innermost loops.  COND is the condition determining which
     475                 :            :    loop is entered -- the new loop is entered if COND is true.  Returns NULL
     476                 :            :    if impossible, new loop otherwise.  */
     477                 :            : 
     478                 :            : static class loop *
     479                 :       1695 : tree_unswitch_loop (class loop *loop,
     480                 :            :                     basic_block unswitch_on, tree cond)
     481                 :            : {
     482                 :       1695 :   profile_probability prob_true;
     483                 :       1695 :   edge edge_true, edge_false;
     484                 :            : 
     485                 :            :   /* Some sanity checking.  */
     486                 :       1695 :   gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
     487                 :       1695 :   gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
     488                 :       1695 :   gcc_assert (loop->inner == NULL);
     489                 :            : 
     490                 :       1695 :   extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
     491                 :       1695 :   prob_true = edge_true->probability;
     492                 :       1695 :   return loop_version (loop, unshare_expr (cond),
     493                 :            :                        NULL, prob_true,
     494                 :            :                        prob_true.invert (),
     495                 :            :                        prob_true, prob_true.invert (),
     496                 :       1695 :                        false);
     497                 :            : }
     498                 :            : 
     499                 :            : /* Unswitch outer loops by hoisting invariant guard on
     500                 :            :    inner loop without code duplication.  */
     501                 :            : static bool
     502                 :       7543 : tree_unswitch_outer_loop (class loop *loop)
     503                 :            : {
     504                 :       7543 :   edge exit, guard;
     505                 :       7543 :   HOST_WIDE_INT iterations;
     506                 :            : 
     507                 :       7543 :   gcc_assert (loop->inner);
     508                 :       7543 :   if (loop->inner->next)
     509                 :            :     return false;
     510                 :            :   /* Accept loops with single exit only which is not from inner loop.  */
     511                 :       5676 :   exit = single_exit (loop);
     512                 :       5676 :   if (!exit || exit->src->loop_father != loop)
     513                 :            :     return false;
     514                 :            :   /* Check that phi argument of exit edge is not defined inside loop.  */
     515                 :       4087 :   if (!check_exit_phi (loop))
     516                 :            :     return false;
     517                 :            :   /* If the loop is not expected to iterate, there is no need
     518                 :            :       for unswitching.  */
     519                 :       2980 :   iterations = estimated_loop_iterations_int (loop);
     520                 :       2980 :   if (iterations < 0)
     521                 :       1930 :     iterations = likely_max_loop_iterations_int (loop);
     522                 :       2980 :   if (iterations >= 0 && iterations <= 1)
     523                 :            :     {
     524                 :        114 :       if (dump_file && (dump_flags & TDF_DETAILS))
     525                 :          0 :         fprintf (dump_file, ";; Not unswitching, loop is not expected"
     526                 :            :                  " to iterate\n");
     527                 :        114 :       return false;
     528                 :            :     }
     529                 :            : 
     530                 :            :   bool changed = false;
     531                 :       3455 :   while ((guard = find_loop_guard (loop)))
     532                 :            :     {
     533                 :        589 :       if (! changed)
     534                 :        539 :         rewrite_virtuals_into_loop_closed_ssa (loop);
     535                 :        589 :       hoist_guard (loop, guard);
     536                 :        589 :       changed = true;
     537                 :            :     }
     538                 :            :   return changed;
     539                 :            : }
     540                 :            : 
     541                 :            : /* Checks if the body of the LOOP is within an invariant guard.  If this
     542                 :            :    is the case, returns the edge that jumps over the real body of the loop,
     543                 :            :    otherwise returns NULL.  */
     544                 :            : 
     545                 :            : static edge
     546                 :       3455 : find_loop_guard (class loop *loop)
     547                 :            : {
     548                 :       3455 :   basic_block header = loop->header;
     549                 :       3455 :   edge guard_edge, te, fe;
     550                 :       3455 :   basic_block *body = NULL;
     551                 :       6187 :   unsigned i;
     552                 :       6187 :   tree use;
     553                 :       6187 :   ssa_op_iter iter;
     554                 :            : 
     555                 :            :   /* We check for the following situation:
     556                 :            : 
     557                 :            :      while (1)
     558                 :            :        {
     559                 :            :          [header]]
     560                 :            :          loop_phi_nodes;
     561                 :            :          something1;
     562                 :            :          if (cond1)
     563                 :            :            body;
     564                 :            :          nvar = phi(orig, bvar) ... for all variables changed in body;
     565                 :            :          [guard_end]
     566                 :            :          something2;
     567                 :            :          if (cond2)
     568                 :            :            break;
     569                 :            :          something3;
     570                 :            :        }
     571                 :            : 
     572                 :            :      where:
     573                 :            : 
     574                 :            :      1) cond1 is loop invariant
     575                 :            :      2) If cond1 is false, then the loop is essentially empty; i.e.,
     576                 :            :         a) nothing in something1, something2 and something3 has side
     577                 :            :            effects
     578                 :            :         b) anything defined in something1, something2 and something3
     579                 :            :            is not used outside of the loop.  */
     580                 :            : 
     581                 :       6187 :   gcond *cond;
     582                 :       6187 :   do
     583                 :            :     {
     584                 :       6187 :       basic_block next = NULL;
     585                 :       6187 :       if (single_succ_p (header))
     586                 :       2027 :         next = single_succ (header);
     587                 :            :       else
     588                 :            :         {
     589                 :       4160 :           cond = safe_dyn_cast <gcond *> (last_stmt (header));
     590                 :       4150 :           if (! cond)
     591                 :            :             return NULL;
     592                 :       4150 :           extract_true_false_edges_from_block (header, &te, &fe);
     593                 :            :           /* Make sure to skip earlier hoisted guards that are left
     594                 :            :              in place as if (true).  */
     595                 :       4150 :           if (gimple_cond_true_p (cond))
     596                 :        112 :             next = te->dest;
     597                 :       4038 :           else if (gimple_cond_false_p (cond))
     598                 :        593 :             next = fe->dest;
     599                 :            :           else
     600                 :            :             break;
     601                 :            :         }
     602                 :            :       /* Never traverse a backedge.  */
     603                 :       2732 :       if (header->loop_father->header == next)
     604                 :            :         return NULL;
     605                 :            :       header = next;
     606                 :            :     }
     607                 :            :   while (1);
     608                 :       3445 :   if (!flow_bb_inside_loop_p (loop, te->dest)
     609                 :       3445 :       || !flow_bb_inside_loop_p (loop, fe->dest))
     610                 :         24 :     return NULL;
     611                 :            : 
     612                 :       3421 :   if (just_once_each_iteration_p (loop, te->dest)
     613                 :       3421 :       || (single_succ_p (te->dest)
     614                 :       2158 :           && just_once_each_iteration_p (loop, single_succ (te->dest))))
     615                 :            :     {
     616                 :       1902 :       if (just_once_each_iteration_p (loop, fe->dest))
     617                 :            :         return NULL;
     618                 :       1896 :       guard_edge = te;
     619                 :            :     }
     620                 :       1519 :   else if (just_once_each_iteration_p (loop, fe->dest)
     621                 :       1519 :            || (single_succ_p (fe->dest)
     622                 :        886 :                && just_once_each_iteration_p (loop, single_succ (fe->dest))))
     623                 :       1156 :     guard_edge = fe;
     624                 :            :   else
     625                 :        363 :     return NULL;
     626                 :            : 
     627                 :            :   /* Guard edge must skip inner loop.  */
     628                 :       3052 :   if (!dominated_by_p (CDI_DOMINATORS, loop->inner->header,
     629                 :       3052 :       guard_edge == fe ? te->dest : fe->dest))
     630                 :            :     {
     631                 :       1423 :       if (dump_file && (dump_flags & TDF_DETAILS))
     632                 :          2 :         fprintf (dump_file, "Guard edge %d --> %d is not around the loop!\n",
     633                 :          2 :                  guard_edge->src->index, guard_edge->dest->index);
     634                 :       1423 :       return NULL;
     635                 :            :     }
     636                 :       1629 :   if (guard_edge->dest == loop->latch)
     637                 :            :     {
     638                 :          2 :       if (dump_file && (dump_flags & TDF_DETAILS))
     639                 :          0 :         fprintf (dump_file, "Guard edge destination is loop latch.\n");
     640                 :          2 :       return NULL;
     641                 :            :     }
     642                 :            : 
     643                 :       1627 :   if (dump_file && (dump_flags & TDF_DETAILS))
     644                 :          4 :     fprintf (dump_file,
     645                 :            :              "Considering guard %d -> %d in loop %d\n",
     646                 :          4 :              guard_edge->src->index, guard_edge->dest->index, loop->num);
     647                 :            :   /* Check if condition operands do not have definitions inside loop since
     648                 :            :      any bb copying is not performed.  */
     649                 :       2718 :   FOR_EACH_SSA_TREE_OPERAND (use, cond, iter, SSA_OP_USE)
     650                 :            :     {
     651                 :       2070 :       gimple *def = SSA_NAME_DEF_STMT (use);
     652                 :       2070 :       basic_block def_bb = gimple_bb (def);
     653                 :       2070 :       if (def_bb
     654                 :       2070 :           && flow_bb_inside_loop_p (loop, def_bb))
     655                 :            :         {
     656                 :        979 :           if (dump_file && (dump_flags & TDF_DETAILS))
     657                 :          0 :             fprintf (dump_file, "  guard operands have definitions"
     658                 :            :                                 " inside loop\n");
     659                 :        979 :           return NULL;
     660                 :            :         }
     661                 :            :     }
     662                 :            : 
     663                 :        648 :   body = get_loop_body (loop);
     664                 :       6229 :   for (i = 0; i < loop->num_nodes; i++)
     665                 :            :     {
     666                 :       5640 :       basic_block bb = body[i];
     667                 :       5640 :       if (bb->loop_father != loop)
     668                 :       2113 :         continue;
     669                 :       3527 :       if (bb->flags & BB_IRREDUCIBLE_LOOP)
     670                 :            :         {
     671                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
     672                 :          0 :             fprintf (dump_file, "Block %d is marked as irreducible in loop\n",
     673                 :            :                       bb->index);
     674                 :          0 :           guard_edge = NULL;
     675                 :          0 :           goto end;
     676                 :            :         }
     677                 :       3527 :       if (!empty_bb_without_guard_p (loop, bb))
     678                 :            :         {
     679                 :         59 :           if (dump_file && (dump_flags & TDF_DETAILS))
     680                 :          0 :             fprintf (dump_file, "  block %d has side effects\n", bb->index);
     681                 :         59 :           guard_edge = NULL;
     682                 :         59 :           goto end;
     683                 :            :         }
     684                 :            :     }
     685                 :            : 
     686                 :        589 :   if (dump_file && (dump_flags & TDF_DETAILS))
     687                 :          4 :     fprintf (dump_file, "  suitable to hoist\n");
     688                 :        648 : end:
     689                 :        648 :   if (body)
     690                 :        648 :     free (body);
     691                 :            :   return guard_edge;
     692                 :            : }
     693                 :            : 
     694                 :            : /* Returns true if
     695                 :            :    1) no statement in BB has side effects
     696                 :            :    2) assuming that edge GUARD is always taken, all definitions in BB
     697                 :            :       are noy used outside of the loop.
     698                 :            :    KNOWN_INVARIANTS is a set of ssa names we know to be invariant, and
     699                 :            :    PROCESSED is a set of ssa names for that we already tested whether they
     700                 :            :    are invariant or not.  */
     701                 :            : 
     702                 :            : static bool
     703                 :       3527 : empty_bb_without_guard_p (class loop *loop, basic_block bb)
     704                 :            : {
     705                 :       3527 :   basic_block exit_bb = single_exit (loop)->src;
     706                 :       3527 :   bool may_be_used_outside = (bb == exit_bb
     707                 :       3527 :                               || !dominated_by_p (CDI_DOMINATORS, bb, exit_bb));
     708                 :       2890 :   tree name;
     709                 :       2890 :   ssa_op_iter op_iter;
     710                 :            : 
     711                 :            :   /* Phi nodes do not have side effects, but their results might be used
     712                 :            :      outside of the loop.  */
     713                 :       2890 :   if (may_be_used_outside)
     714                 :            :     {
     715                 :       2890 :       for (gphi_iterator gsi = gsi_start_phis (bb);
     716                 :       4953 :            !gsi_end_p (gsi); gsi_next (&gsi))
     717                 :            :         {
     718                 :       2063 :           gphi *phi = gsi.phi ();
     719                 :       2063 :           name = PHI_RESULT (phi);
     720                 :       4126 :           if (virtual_operand_p (name))
     721                 :       1326 :             continue;
     722                 :            : 
     723                 :        737 :           if (used_outside_loop_p (loop, name))
     724                 :          0 :             return false;
     725                 :            :         }
     726                 :            :     }
     727                 :            : 
     728                 :       3527 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
     729                 :       8709 :        !gsi_end_p (gsi); gsi_next (&gsi))
     730                 :            :     {
     731                 :       5241 :       gimple *stmt = gsi_stmt (gsi);
     732                 :       5241 :       if (gimple_has_side_effects (stmt))
     733                 :            :         return false;
     734                 :            : 
     735                 :       8268 :       if (gimple_vdef(stmt))
     736                 :            :         return false;
     737                 :            : 
     738                 :       8180 :       FOR_EACH_SSA_TREE_OPERAND (name, stmt, op_iter, SSA_OP_DEF)
     739                 :            :         {
     740                 :       2998 :           if (may_be_used_outside
     741                 :       2998 :               && used_outside_loop_p (loop, name))
     742                 :            :             return false;
     743                 :            :         }
     744                 :            :     }
     745                 :       3468 :   return true;
     746                 :            : }
     747                 :            : 
     748                 :            : /* Return true if NAME is used outside of LOOP.  */
     749                 :            : 
     750                 :            : static bool
     751                 :       3725 : used_outside_loop_p (class loop *loop, tree name)
     752                 :            : {
     753                 :       3725 :   imm_use_iterator it;
     754                 :       3725 :   use_operand_p use;
     755                 :            : 
     756                 :       9781 :   FOR_EACH_IMM_USE_FAST (use, it, name)
     757                 :            :     {
     758                 :       6056 :       gimple *stmt = USE_STMT (use);
     759                 :       6056 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
     760                 :            :         return true;
     761                 :            :     }
     762                 :            : 
     763                 :            :   return false;
     764                 :            : }
     765                 :            : 
     766                 :            : /* Return argument for loop preheader edge in header virtual phi if any.  */
     767                 :            : 
     768                 :            : static tree
     769                 :        587 : get_vop_from_header (class loop *loop)
     770                 :            : {
     771                 :        587 :   for (gphi_iterator gsi = gsi_start_phis (loop->header);
     772                 :       1187 :        !gsi_end_p (gsi); gsi_next (&gsi))
     773                 :            :     {
     774                 :       1187 :       gphi *phi = gsi.phi ();
     775                 :       2374 :       if (!virtual_operand_p (gimple_phi_result (phi)))
     776                 :        600 :         continue;
     777                 :        587 :       return PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
     778                 :            :     }
     779                 :          0 :   return NULL_TREE;
     780                 :            : }
     781                 :            : 
     782                 :            : /* Move the check of GUARD outside of LOOP.  */
     783                 :            : 
     784                 :            : static void
     785                 :        589 : hoist_guard (class loop *loop, edge guard)
     786                 :            : {
     787                 :        589 :   edge exit = single_exit (loop);
     788                 :        589 :   edge preh = loop_preheader_edge (loop);
     789                 :        589 :   basic_block pre_header = preh->src;
     790                 :        589 :   basic_block bb;
     791                 :        589 :   edge te, fe, e, new_edge;
     792                 :        589 :   gimple *stmt;
     793                 :        589 :   basic_block guard_bb = guard->src;
     794                 :        589 :   edge not_guard;
     795                 :        589 :   gimple_stmt_iterator gsi;
     796                 :        589 :   int flags = 0;
     797                 :        589 :   bool fix_dom_of_exit;
     798                 :        589 :   gcond *cond_stmt, *new_cond_stmt;
     799                 :            : 
     800                 :        589 :   bb = get_immediate_dominator (CDI_DOMINATORS, exit->dest);
     801                 :        589 :   fix_dom_of_exit = flow_bb_inside_loop_p (loop, bb);
     802                 :        589 :   gsi = gsi_last_bb (guard_bb);
     803                 :        589 :   stmt = gsi_stmt (gsi);
     804                 :        589 :   gcc_assert (gimple_code (stmt) == GIMPLE_COND);
     805                 :        589 :   cond_stmt = as_a <gcond *> (stmt);
     806                 :        589 :   extract_true_false_edges_from_block (guard_bb, &te, &fe);
     807                 :            :   /* Insert guard to PRE_HEADER.  */
     808                 :        589 :   if (!empty_block_p (pre_header))
     809                 :        556 :     gsi = gsi_last_bb (pre_header);
     810                 :            :   else
     811                 :        622 :     gsi = gsi_start_bb (pre_header);
     812                 :            :   /* Create copy of COND_STMT.  */
     813                 :        589 :   new_cond_stmt = gimple_build_cond (gimple_cond_code (cond_stmt),
     814                 :            :                                      gimple_cond_lhs (cond_stmt),
     815                 :            :                                      gimple_cond_rhs (cond_stmt),
     816                 :            :                                      NULL_TREE, NULL_TREE);
     817                 :        589 :   gsi_insert_after (&gsi, new_cond_stmt, GSI_NEW_STMT);
     818                 :            :   /* Convert COND_STMT to true/false conditional.  */
     819                 :        589 :   if (guard == te)
     820                 :        503 :     gimple_cond_make_false (cond_stmt);
     821                 :            :   else
     822                 :         86 :     gimple_cond_make_true (cond_stmt);
     823                 :        589 :   update_stmt (cond_stmt);
     824                 :            :   /* Create new loop pre-header.  */
     825                 :        589 :   e = split_block (pre_header, last_stmt (pre_header));
     826                 :        589 :   if (dump_file && (dump_flags & TDF_DETAILS))
     827                 :            :     {
     828                 :          4 :       fprintf (dump_file, "  Moving guard %i->%i (prob ",
     829                 :          4 :                guard->src->index, guard->dest->index);
     830                 :          4 :       guard->probability.dump (dump_file);
     831                 :          4 :       fprintf (dump_file, ") to bb %i, new preheader is %i\n",
     832                 :          4 :                e->src->index, e->dest->index);
     833                 :            :     }
     834                 :            : 
     835                 :        589 :   gcc_assert (loop_preheader_edge (loop)->src == e->dest);
     836                 :            : 
     837                 :        589 :   if (guard == fe)
     838                 :            :     {
     839                 :         86 :       e->flags = EDGE_TRUE_VALUE;
     840                 :         86 :       flags |= EDGE_FALSE_VALUE;
     841                 :         86 :       not_guard = te;
     842                 :            :     }
     843                 :            :   else
     844                 :            :     {
     845                 :        503 :       e->flags = EDGE_FALSE_VALUE;
     846                 :        503 :       flags |= EDGE_TRUE_VALUE;
     847                 :        503 :       not_guard = fe;
     848                 :            :     }
     849                 :        589 :   new_edge = make_edge (pre_header, exit->dest, flags);
     850                 :            : 
     851                 :            :   /* Determine the probability that we skip the loop.  Assume that loop has
     852                 :            :      same average number of iterations regardless outcome of guard.  */
     853                 :        589 :   new_edge->probability = guard->probability;
     854                 :        589 :   profile_count skip_count = guard->src->count.nonzero_p ()
     855                 :        589 :                    ? guard->count ().apply_scale (pre_header->count,
     856                 :        589 :                                                guard->src->count)
     857                 :          0 :                    : guard->count ().apply_probability (new_edge->probability);
     858                 :            : 
     859                 :        589 :   if (skip_count > e->count ())
     860                 :            :     {
     861                 :          0 :       fprintf (dump_file, "  Capping count; expect profile inconsistency\n");
     862                 :          0 :       skip_count = e->count ();
     863                 :            :     }
     864                 :        589 :   if (dump_file && (dump_flags & TDF_DETAILS))
     865                 :            :     {
     866                 :          4 :       fprintf (dump_file, "  Estimated probability of skipping loop is ");
     867                 :          4 :       new_edge->probability.dump (dump_file);
     868                 :          4 :       fprintf (dump_file, "\n");
     869                 :            :     }
     870                 :            : 
     871                 :            :   /* Update profile after the transform:
     872                 :            : 
     873                 :            :      First decrease count of path from newly hoisted loop guard
     874                 :            :      to loop header...  */
     875                 :        589 :   e->probability = new_edge->probability.invert ();
     876                 :        589 :   e->dest->count = e->count ();
     877                 :            : 
     878                 :            :   /* ... now update profile to represent that original guard will be optimized
     879                 :            :      away ...  */
     880                 :        589 :   guard->probability = profile_probability::never ();
     881                 :        589 :   not_guard->probability = profile_probability::always ();
     882                 :            : 
     883                 :            :   /* ... finally scale everything in the loop except for guarded basic blocks
     884                 :            :      where profile does not change.  */
     885                 :        589 :   basic_block *body = get_loop_body (loop);
     886                 :            : 
     887                 :        589 :   if (dump_file && (dump_flags & TDF_DETAILS))
     888                 :          4 :     fprintf (dump_file, "  Scaling nonguarded BBs in loop:");
     889                 :       6052 :   for (unsigned int i = 0; i < loop->num_nodes; i++)
     890                 :            :     {
     891                 :       5463 :       basic_block bb = body[i];
     892                 :       5463 :       if (!dominated_by_p (CDI_DOMINATORS, bb, not_guard->dest))
     893                 :            :         {
     894                 :       2297 :           if (dump_file && (dump_flags & TDF_DETAILS))
     895                 :         18 :             fprintf (dump_file, " %i", bb->index);
     896                 :       2297 :           if (e->probability.initialized_p ())
     897                 :       2297 :             scale_bbs_frequencies (&bb, 1, e->probability);
     898                 :            :         }
     899                 :            :     }
     900                 :            : 
     901                 :        589 :   if (fix_dom_of_exit)
     902                 :        422 :     set_immediate_dominator (CDI_DOMINATORS, exit->dest, pre_header);
     903                 :            :   /* Add NEW_ADGE argument for all phi in post-header block.  */
     904                 :        589 :   bb = exit->dest;
     905                 :        589 :   for (gphi_iterator gsi = gsi_start_phis (bb);
     906                 :       1190 :        !gsi_end_p (gsi); gsi_next (&gsi))
     907                 :            :     {
     908                 :        601 :       gphi *phi = gsi.phi ();
     909                 :        601 :       tree arg;
     910                 :       1202 :       if (virtual_operand_p (gimple_phi_result (phi)))
     911                 :            :         {
     912                 :        587 :           arg = get_vop_from_header (loop);
     913                 :        587 :           if (arg == NULL_TREE)
     914                 :            :             /* Use exit edge argument.  */
     915                 :          0 :             arg =  PHI_ARG_DEF_FROM_EDGE (phi, exit);
     916                 :        587 :           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
     917                 :            :         }
     918                 :            :       else
     919                 :            :         {
     920                 :            :           /* Use exit edge argument.  */
     921                 :         14 :           arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
     922                 :         14 :           add_phi_arg (phi, arg, new_edge, UNKNOWN_LOCATION);
     923                 :            :         }
     924                 :            :     }
     925                 :            : 
     926                 :        589 :   if (dump_file && (dump_flags & TDF_DETAILS))
     927                 :          4 :     fprintf (dump_file, "\n  guard hoisted.\n");
     928                 :            : 
     929                 :        589 :   free (body);
     930                 :        589 : }
     931                 :            : 
     932                 :            : /* Return true if phi argument for exit edge can be used
     933                 :            :    for edge around loop.  */
     934                 :            : 
     935                 :            : static bool
     936                 :       4087 : check_exit_phi (class loop *loop)
     937                 :            : {
     938                 :       4087 :   edge exit = single_exit (loop);
     939                 :       4087 :   basic_block pre_header = loop_preheader_edge (loop)->src;
     940                 :            : 
     941                 :       4087 :   for (gphi_iterator gsi = gsi_start_phis (exit->dest);
     942                 :       5112 :        !gsi_end_p (gsi); gsi_next (&gsi))
     943                 :            :     {
     944                 :       2132 :       gphi *phi = gsi.phi ();
     945                 :       2132 :       tree arg;
     946                 :       2132 :       gimple *def;
     947                 :       2132 :       basic_block def_bb;
     948                 :       4264 :       if (virtual_operand_p (gimple_phi_result (phi)))
     949                 :        992 :         continue;
     950                 :       1140 :       arg = PHI_ARG_DEF_FROM_EDGE (phi, exit);
     951                 :       1140 :       if (TREE_CODE (arg) != SSA_NAME)
     952                 :          2 :         continue;
     953                 :       1138 :       def = SSA_NAME_DEF_STMT (arg);
     954                 :       1138 :       if (!def)
     955                 :          0 :         continue;
     956                 :       1138 :       def_bb = gimple_bb (def);
     957                 :       1138 :       if (!def_bb)
     958                 :          0 :         continue;
     959                 :       1138 :       if (!dominated_by_p (CDI_DOMINATORS, pre_header, def_bb))
     960                 :            :         /* Definition inside loop!  */
     961                 :       1107 :         return false;
     962                 :            :       /* Check loop closed phi invariant.  */
     963                 :         31 :       if (!flow_bb_inside_loop_p (def_bb->loop_father, pre_header))
     964                 :            :         return false;
     965                 :            :     }
     966                 :       2980 :   return true;
     967                 :            : }
     968                 :            : 
     969                 :            : /* Loop unswitching pass.  */
     970                 :            : 
     971                 :            : namespace {
     972                 :            : 
     973                 :            : const pass_data pass_data_tree_unswitch =
     974                 :            : {
     975                 :            :   GIMPLE_PASS, /* type */
     976                 :            :   "unswitch", /* name */
     977                 :            :   OPTGROUP_LOOP, /* optinfo_flags */
     978                 :            :   TV_TREE_LOOP_UNSWITCH, /* tv_id */
     979                 :            :   PROP_cfg, /* properties_required */
     980                 :            :   0, /* properties_provided */
     981                 :            :   0, /* properties_destroyed */
     982                 :            :   0, /* todo_flags_start */
     983                 :            :   0, /* todo_flags_finish */
     984                 :            : };
     985                 :            : 
     986                 :            : class pass_tree_unswitch : public gimple_opt_pass
     987                 :            : {
     988                 :            : public:
     989                 :     200773 :   pass_tree_unswitch (gcc::context *ctxt)
     990                 :     401546 :     : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
     991                 :            :   {}
     992                 :            : 
     993                 :            :   /* opt_pass methods: */
     994                 :     157676 :   virtual bool gate (function *) { return flag_unswitch_loops != 0; }
     995                 :            :   virtual unsigned int execute (function *);
     996                 :            : 
     997                 :            : }; // class pass_tree_unswitch
     998                 :            : 
     999                 :            : unsigned int
    1000                 :      17764 : pass_tree_unswitch::execute (function *fun)
    1001                 :            : {
    1002                 :      35528 :   if (number_of_loops (fun) <= 1)
    1003                 :            :     return 0;
    1004                 :            : 
    1005                 :      17764 :   return tree_ssa_unswitch_loops ();
    1006                 :            : }
    1007                 :            : 
    1008                 :            : } // anon namespace
    1009                 :            : 
    1010                 :            : gimple_opt_pass *
    1011                 :     200773 : make_pass_tree_unswitch (gcc::context *ctxt)
    1012                 :            : {
    1013                 :     200773 :   return new pass_tree_unswitch (ctxt);
    1014                 :            : }
    1015                 :            : 
    1016                 :            : 

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.