LCOV - code coverage report
Current view: top level - gcc - tree-ssa-loop-split.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 579 601 96.3 %
Date: 2020-03-28 11:57:23 Functions: 28 28 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Loop splitting.
       2                 :            :    Copyright (C) 2015-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 "tree-cfg.h"
      30                 :            : #include "tree-ssa.h"
      31                 :            : #include "tree-ssa-loop-niter.h"
      32                 :            : #include "tree-ssa-loop.h"
      33                 :            : #include "tree-ssa-loop-manip.h"
      34                 :            : #include "tree-into-ssa.h"
      35                 :            : #include "tree-inline.h"
      36                 :            : #include "tree-cfgcleanup.h"
      37                 :            : #include "cfgloop.h"
      38                 :            : #include "tree-scalar-evolution.h"
      39                 :            : #include "gimple-iterator.h"
      40                 :            : #include "gimple-pretty-print.h"
      41                 :            : #include "cfghooks.h"
      42                 :            : #include "gimple-fold.h"
      43                 :            : #include "gimplify-me.h"
      44                 :            : 
      45                 :            : /* This file implements two kinds of loop splitting.
      46                 :            : 
      47                 :            :    One transformation of loops like:
      48                 :            : 
      49                 :            :    for (i = 0; i < 100; i++)
      50                 :            :      {
      51                 :            :        if (i < 50)
      52                 :            :          A;
      53                 :            :        else
      54                 :            :          B;
      55                 :            :      }
      56                 :            : 
      57                 :            :    into:
      58                 :            : 
      59                 :            :    for (i = 0; i < 50; i++)
      60                 :            :      {
      61                 :            :        A;
      62                 :            :      }
      63                 :            :    for (; i < 100; i++)
      64                 :            :      {
      65                 :            :        B;
      66                 :            :      }
      67                 :            : 
      68                 :            :    */
      69                 :            : 
      70                 :            : /* Return true when BB inside LOOP is a potential iteration space
      71                 :            :    split point, i.e. ends with a condition like "IV < comp", which
      72                 :            :    is true on one side of the iteration space and false on the other,
      73                 :            :    and the split point can be computed.  If so, also return the border
      74                 :            :    point in *BORDER and the comparison induction variable in IV.  */
      75                 :            : 
      76                 :            : static tree
      77                 :      38793 : split_at_bb_p (class loop *loop, basic_block bb, tree *border, affine_iv *iv)
      78                 :            : {
      79                 :      38793 :   gimple *last;
      80                 :      38793 :   gcond *stmt;
      81                 :      38793 :   affine_iv iv2;
      82                 :            : 
      83                 :            :   /* BB must end in a simple conditional jump.  */
      84                 :      38793 :   last = last_stmt (bb);
      85                 :      38793 :   if (!last || gimple_code (last) != GIMPLE_COND)
      86                 :            :     return NULL_TREE;
      87                 :      18010 :   stmt = as_a <gcond *> (last);
      88                 :            : 
      89                 :      18010 :   enum tree_code code = gimple_cond_code (stmt);
      90                 :            : 
      91                 :            :   /* Only handle relational comparisons, for equality and non-equality
      92                 :            :      we'd have to split the loop into two loops and a middle statement.  */
      93                 :      18010 :   switch (code)
      94                 :            :     {
      95                 :      15073 :       case LT_EXPR:
      96                 :      15073 :       case LE_EXPR:
      97                 :      15073 :       case GT_EXPR:
      98                 :      15073 :       case GE_EXPR:
      99                 :      15073 :         break;
     100                 :            :       default:
     101                 :            :         return NULL_TREE;
     102                 :            :     }
     103                 :            : 
     104                 :      15073 :   if (loop_exits_from_bb_p (loop, bb))
     105                 :            :     return NULL_TREE;
     106                 :            : 
     107                 :       5440 :   tree op0 = gimple_cond_lhs (stmt);
     108                 :       5440 :   tree op1 = gimple_cond_rhs (stmt);
     109                 :       5440 :   class loop *useloop = loop_containing_stmt (stmt);
     110                 :            : 
     111                 :       5440 :   if (!simple_iv (loop, useloop, op0, iv, false))
     112                 :            :     return NULL_TREE;
     113                 :       2217 :   if (!simple_iv (loop, useloop, op1, &iv2, false))
     114                 :            :     return NULL_TREE;
     115                 :            : 
     116                 :            :   /* Make it so that the first argument of the condition is
     117                 :            :      the looping one.  */
     118                 :        975 :   if (!integer_zerop (iv2.step))
     119                 :            :     {
     120                 :        342 :       std::swap (op0, op1);
     121                 :        342 :       std::swap (*iv, iv2);
     122                 :        342 :       code = swap_tree_comparison (code);
     123                 :        342 :       gimple_cond_set_condition (stmt, code, op0, op1);
     124                 :        342 :       update_stmt (stmt);
     125                 :            :     }
     126                 :        633 :   else if (integer_zerop (iv->step))
     127                 :            :     return NULL_TREE;
     128                 :        523 :   if (!integer_zerop (iv2.step))
     129                 :            :     return NULL_TREE;
     130                 :        523 :   if (!iv->no_overflow)
     131                 :            :     return NULL_TREE;
     132                 :            : 
     133                 :        516 :   if (dump_file && (dump_flags & TDF_DETAILS))
     134                 :            :     {
     135                 :         17 :       fprintf (dump_file, "Found potential split point: ");
     136                 :         17 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
     137                 :         17 :       fprintf (dump_file, " { ");
     138                 :         17 :       print_generic_expr (dump_file, iv->base, TDF_SLIM);
     139                 :         17 :       fprintf (dump_file, " + I*");
     140                 :         17 :       print_generic_expr (dump_file, iv->step, TDF_SLIM);
     141                 :         17 :       fprintf (dump_file, " } %s ", get_tree_code_name (code));
     142                 :         17 :       print_generic_expr (dump_file, iv2.base, TDF_SLIM);
     143                 :         17 :       fprintf (dump_file, "\n");
     144                 :            :     }
     145                 :            : 
     146                 :        516 :   *border = iv2.base;
     147                 :        516 :   return op0;
     148                 :            : }
     149                 :            : 
     150                 :            : /* Given a GUARD conditional stmt inside LOOP, which we want to make always
     151                 :            :    true or false depending on INITIAL_TRUE, and adjusted values NEXTVAL
     152                 :            :    (a post-increment IV) and NEWBOUND (the comparator) adjust the loop
     153                 :            :    exit test statement to loop back only if the GUARD statement will
     154                 :            :    also be true/false in the next iteration.  */
     155                 :            : 
     156                 :            : static void
     157                 :         52 : patch_loop_exit (class loop *loop, gcond *guard, tree nextval, tree newbound,
     158                 :            :                  bool initial_true)
     159                 :            : {
     160                 :         52 :   edge exit = single_exit (loop);
     161                 :         52 :   gcond *stmt = as_a <gcond *> (last_stmt (exit->src));
     162                 :         52 :   gimple_cond_set_condition (stmt, gimple_cond_code (guard),
     163                 :            :                              nextval, newbound);
     164                 :         52 :   update_stmt (stmt);
     165                 :            : 
     166                 :         52 :   edge stay = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit);
     167                 :            : 
     168                 :         52 :   exit->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
     169                 :         52 :   stay->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
     170                 :            : 
     171                 :         52 :   if (initial_true)
     172                 :            :     {
     173                 :         33 :       exit->flags |= EDGE_FALSE_VALUE;
     174                 :         33 :       stay->flags |= EDGE_TRUE_VALUE;
     175                 :            :     }
     176                 :            :   else
     177                 :            :     {
     178                 :         19 :       exit->flags |= EDGE_TRUE_VALUE;
     179                 :         19 :       stay->flags |= EDGE_FALSE_VALUE;
     180                 :            :     }
     181                 :         52 : }
     182                 :            : 
     183                 :            : /* Give an induction variable GUARD_IV, and its affine descriptor IV,
     184                 :            :    find the loop phi node in LOOP defining it directly, or create
     185                 :            :    such phi node.  Return that phi node.  */
     186                 :            : 
     187                 :            : static gphi *
     188                 :        516 : find_or_create_guard_phi (class loop *loop, tree guard_iv, affine_iv * /*iv*/)
     189                 :            : {
     190                 :        516 :   gimple *def = SSA_NAME_DEF_STMT (guard_iv);
     191                 :        516 :   gphi *phi;
     192                 :        516 :   if ((phi = dyn_cast <gphi *> (def))
     193                 :         52 :       && gimple_bb (phi) == loop->header)
     194                 :         52 :     return phi;
     195                 :            : 
     196                 :            :   /* XXX Create the PHI instead.  */
     197                 :            :   return NULL;
     198                 :            : }
     199                 :            : 
     200                 :            : /* Returns true if the exit values of all loop phi nodes can be
     201                 :            :    determined easily (i.e. that connect_loop_phis can determine them).  */
     202                 :            : 
     203                 :            : static bool
     204                 :      28881 : easy_exit_values (class loop *loop)
     205                 :            : {
     206                 :      28881 :   edge exit = single_exit (loop);
     207                 :      28881 :   edge latch = loop_latch_edge (loop);
     208                 :      28881 :   gphi_iterator psi;
     209                 :            : 
     210                 :            :   /* Currently we regard the exit values as easy if they are the same
     211                 :            :      as the value over the backedge.  Which is the case if the definition
     212                 :            :      of the backedge value dominates the exit edge.  */
     213                 :      95524 :   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
     214                 :            :     {
     215                 :      66664 :       gphi *phi = psi.phi ();
     216                 :      66664 :       tree next = PHI_ARG_DEF_FROM_EDGE (phi, latch);
     217                 :      66664 :       basic_block bb;
     218                 :      66664 :       if (TREE_CODE (next) == SSA_NAME
     219                 :      66313 :           && (bb = gimple_bb (SSA_NAME_DEF_STMT (next)))
     220                 :     132976 :           && !dominated_by_p (CDI_DOMINATORS, exit->src, bb))
     221                 :            :         return false;
     222                 :            :     }
     223                 :            : 
     224                 :            :   return true;
     225                 :            : }
     226                 :            : 
     227                 :            : /* This function updates the SSA form after connect_loops made a new
     228                 :            :    edge NEW_E leading from LOOP1 exit to LOOP2 (via in intermediate
     229                 :            :    conditional).  I.e. the second loop can now be entered either
     230                 :            :    via the original entry or via NEW_E, so the entry values of LOOP2
     231                 :            :    phi nodes are either the original ones or those at the exit
     232                 :            :    of LOOP1.  Insert new phi nodes in LOOP2 pre-header reflecting
     233                 :            :    this.  The loops need to fulfill easy_exit_values().  */
     234                 :            : 
     235                 :            : static void
     236                 :        501 : connect_loop_phis (class loop *loop1, class loop *loop2, edge new_e)
     237                 :            : {
     238                 :        501 :   basic_block rest = loop_preheader_edge (loop2)->src;
     239                 :        501 :   gcc_assert (new_e->dest == rest);
     240                 :        501 :   edge skip_first = EDGE_PRED (rest, EDGE_PRED (rest, 0) == new_e);
     241                 :            : 
     242                 :        501 :   edge firste = loop_preheader_edge (loop1);
     243                 :        501 :   edge seconde = loop_preheader_edge (loop2);
     244                 :        501 :   edge firstn = loop_latch_edge (loop1);
     245                 :        501 :   gphi_iterator psi_first, psi_second;
     246                 :        501 :   for (psi_first = gsi_start_phis (loop1->header),
     247                 :        501 :        psi_second = gsi_start_phis (loop2->header);
     248                 :       2322 :        !gsi_end_p (psi_first);
     249                 :       1821 :        gsi_next (&psi_first), gsi_next (&psi_second))
     250                 :            :     {
     251                 :       1821 :       tree init, next, new_init;
     252                 :       1821 :       use_operand_p op;
     253                 :       1821 :       gphi *phi_first = psi_first.phi ();
     254                 :       1821 :       gphi *phi_second = psi_second.phi ();
     255                 :            : 
     256                 :       1821 :       init = PHI_ARG_DEF_FROM_EDGE (phi_first, firste);
     257                 :       1821 :       next = PHI_ARG_DEF_FROM_EDGE (phi_first, firstn);
     258                 :       1821 :       op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_second, seconde);
     259                 :       1821 :       gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
     260                 :            : 
     261                 :            :       /* Prefer using original variable as a base for the new ssa name.
     262                 :            :          This is necessary for virtual ops, and useful in order to avoid
     263                 :            :          losing debug info for real ops.  */
     264                 :       1821 :       if (TREE_CODE (next) == SSA_NAME
     265                 :       3580 :           && useless_type_conversion_p (TREE_TYPE (next),
     266                 :       1759 :                                         TREE_TYPE (init)))
     267                 :       1759 :         new_init = copy_ssa_name (next);
     268                 :         62 :       else if (TREE_CODE (init) == SSA_NAME
     269                 :         72 :                && useless_type_conversion_p (TREE_TYPE (init),
     270                 :         10 :                                              TREE_TYPE (next)))
     271                 :         10 :         new_init = copy_ssa_name (init);
     272                 :        104 :       else if (useless_type_conversion_p (TREE_TYPE (next),
     273                 :         52 :                                           TREE_TYPE (init)))
     274                 :         52 :         new_init = make_temp_ssa_name (TREE_TYPE (next), NULL,
     275                 :            :                                        "unrinittmp");
     276                 :            :       else
     277                 :          0 :         new_init = make_temp_ssa_name (TREE_TYPE (init), NULL,
     278                 :            :                                        "unrinittmp");
     279                 :            : 
     280                 :       1821 :       gphi * newphi = create_phi_node (new_init, rest);
     281                 :       1821 :       add_phi_arg (newphi, init, skip_first, UNKNOWN_LOCATION);
     282                 :       1821 :       add_phi_arg (newphi, next, new_e, UNKNOWN_LOCATION);
     283                 :       1821 :       SET_USE (op, new_init);
     284                 :            :     }
     285                 :        501 : }
     286                 :            : 
     287                 :            : /* The two loops LOOP1 and LOOP2 were just created by loop versioning,
     288                 :            :    they are still equivalent and placed in two arms of a diamond, like so:
     289                 :            : 
     290                 :            :                .------if (cond)------.
     291                 :            :                v                     v
     292                 :            :              pre1                   pre2
     293                 :            :               |                      |
     294                 :            :         .--->h1                     h2<----.
     295                 :            :         |     |                      |     |
     296                 :            :         |    ex1---.            .---ex2    |
     297                 :            :         |    /     |            |     \    |
     298                 :            :         '---l1     X            |     l2---'
     299                 :            :                    |            |
     300                 :            :                    |            |
     301                 :            :                    '--->join<---'
     302                 :            : 
     303                 :            :    This function transforms the program such that LOOP1 is conditionally
     304                 :            :    falling through to LOOP2, or skipping it.  This is done by splitting
     305                 :            :    the ex1->join edge at X in the diagram above, and inserting a condition
     306                 :            :    whose one arm goes to pre2, resulting in this situation:
     307                 :            : 
     308                 :            :                .------if (cond)------.
     309                 :            :                v                     v
     310                 :            :              pre1       .---------->pre2
     311                 :            :               |         |            |
     312                 :            :         .--->h1         |           h2<----.
     313                 :            :         |     |         |            |     |
     314                 :            :         |    ex1---.    |       .---ex2    |
     315                 :            :         |    /     v    |       |     \    |
     316                 :            :         '---l1   skip---'       |     l2---'
     317                 :            :                    |            |
     318                 :            :                    |            |
     319                 :            :                    '--->join<---'
     320                 :            : 
     321                 :            : 
     322                 :            :    The condition used is the exit condition of LOOP1, which effectively means
     323                 :            :    that when the first loop exits (for whatever reason) but the real original
     324                 :            :    exit expression is still false the second loop will be entered.
     325                 :            :    The function returns the new edge cond->pre2.
     326                 :            : 
     327                 :            :    This doesn't update the SSA form, see connect_loop_phis for that.  */
     328                 :            : 
     329                 :            : static edge
     330                 :         52 : connect_loops (class loop *loop1, class loop *loop2)
     331                 :            : {
     332                 :         52 :   edge exit = single_exit (loop1);
     333                 :         52 :   basic_block skip_bb = split_edge (exit);
     334                 :         52 :   gcond *skip_stmt;
     335                 :         52 :   gimple_stmt_iterator gsi;
     336                 :         52 :   edge new_e, skip_e;
     337                 :            : 
     338                 :         52 :   gimple *stmt = last_stmt (exit->src);
     339                 :         52 :   skip_stmt = gimple_build_cond (gimple_cond_code (stmt),
     340                 :            :                                  gimple_cond_lhs (stmt),
     341                 :            :                                  gimple_cond_rhs (stmt),
     342                 :            :                                  NULL_TREE, NULL_TREE);
     343                 :         52 :   gsi = gsi_last_bb (skip_bb);
     344                 :         52 :   gsi_insert_after (&gsi, skip_stmt, GSI_NEW_STMT);
     345                 :            : 
     346                 :         52 :   skip_e = EDGE_SUCC (skip_bb, 0);
     347                 :         52 :   skip_e->flags &= ~EDGE_FALLTHRU;
     348                 :         52 :   new_e = make_edge (skip_bb, loop_preheader_edge (loop2)->src, 0);
     349                 :         52 :   if (exit->flags & EDGE_TRUE_VALUE)
     350                 :            :     {
     351                 :         23 :       skip_e->flags |= EDGE_TRUE_VALUE;
     352                 :         23 :       new_e->flags |= EDGE_FALSE_VALUE;
     353                 :            :     }
     354                 :            :   else
     355                 :            :     {
     356                 :         29 :       skip_e->flags |= EDGE_FALSE_VALUE;
     357                 :         29 :       new_e->flags |= EDGE_TRUE_VALUE;
     358                 :            :     }
     359                 :            : 
     360                 :         52 :   new_e->probability = profile_probability::likely ();
     361                 :         52 :   skip_e->probability = new_e->probability.invert ();
     362                 :            : 
     363                 :         52 :   return new_e;
     364                 :            : }
     365                 :            : 
     366                 :            : /* This returns the new bound for iterations given the original iteration
     367                 :            :    space in NITER, an arbitrary new bound BORDER, assumed to be some
     368                 :            :    comparison value with a different IV, the initial value GUARD_INIT of
     369                 :            :    that other IV, and the comparison code GUARD_CODE that compares
     370                 :            :    that other IV with BORDER.  We return an SSA name, and place any
     371                 :            :    necessary statements for that computation into *STMTS.
     372                 :            : 
     373                 :            :    For example for such a loop:
     374                 :            : 
     375                 :            :      for (i = beg, j = guard_init; i < end; i++, j++)
     376                 :            :        if (j < border)  // this is supposed to be true/false
     377                 :            :          ...
     378                 :            : 
     379                 :            :    we want to return a new bound (on j) that makes the loop iterate
     380                 :            :    as long as the condition j < border stays true.  We also don't want
     381                 :            :    to iterate more often than the original loop, so we have to introduce
     382                 :            :    some cut-off as well (via min/max), effectively resulting in:
     383                 :            : 
     384                 :            :      newend = min (end+guard_init-beg, border)
     385                 :            :      for (i = beg; j = guard_init; j < newend; i++, j++)
     386                 :            :        if (j < c)
     387                 :            :          ...
     388                 :            : 
     389                 :            :    Depending on the direction of the IVs and if the exit tests
     390                 :            :    are strict or non-strict we need to use MIN or MAX,
     391                 :            :    and add or subtract 1.  This routine computes newend above.  */
     392                 :            : 
     393                 :            : static tree
     394                 :         52 : compute_new_first_bound (gimple_seq *stmts, class tree_niter_desc *niter,
     395                 :            :                          tree border,
     396                 :            :                          enum tree_code guard_code, tree guard_init)
     397                 :            : {
     398                 :            :   /* The niter structure contains the after-increment IV, we need
     399                 :            :      the loop-enter base, so subtract STEP once.  */
     400                 :         52 :   tree controlbase = force_gimple_operand (niter->control.base,
     401                 :            :                                            stmts, true, NULL_TREE);
     402                 :         52 :   tree controlstep = niter->control.step;
     403                 :         52 :   tree enddiff;
     404                 :         52 :   if (POINTER_TYPE_P (TREE_TYPE (controlbase)))
     405                 :            :     {
     406                 :          1 :       controlstep = gimple_build (stmts, NEGATE_EXPR,
     407                 :          1 :                                   TREE_TYPE (controlstep), controlstep);
     408                 :          1 :       enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
     409                 :          1 :                               TREE_TYPE (controlbase),
     410                 :            :                               controlbase, controlstep);
     411                 :            :     }
     412                 :            :   else
     413                 :         51 :     enddiff = gimple_build (stmts, MINUS_EXPR,
     414                 :         51 :                             TREE_TYPE (controlbase),
     415                 :            :                             controlbase, controlstep);
     416                 :            : 
     417                 :            :   /* Compute end-beg.  */
     418                 :         52 :   gimple_seq stmts2;
     419                 :         52 :   tree end = force_gimple_operand (niter->bound, &stmts2,
     420                 :            :                                         true, NULL_TREE);
     421                 :         52 :   gimple_seq_add_seq_without_update (stmts, stmts2);
     422                 :         52 :   if (POINTER_TYPE_P (TREE_TYPE (enddiff)))
     423                 :            :     {
     424                 :          1 :       tree tem = gimple_convert (stmts, sizetype, enddiff);
     425                 :          1 :       tem = gimple_build (stmts, NEGATE_EXPR, sizetype, tem);
     426                 :          1 :       enddiff = gimple_build (stmts, POINTER_PLUS_EXPR,
     427                 :          1 :                               TREE_TYPE (enddiff),
     428                 :            :                               end, tem);
     429                 :            :     }
     430                 :            :   else
     431                 :         51 :     enddiff = gimple_build (stmts, MINUS_EXPR, TREE_TYPE (enddiff),
     432                 :            :                             end, enddiff);
     433                 :            : 
     434                 :            :   /* Compute guard_init + (end-beg).  */
     435                 :         52 :   tree newbound;
     436                 :         52 :   enddiff = gimple_convert (stmts, TREE_TYPE (guard_init), enddiff);
     437                 :         52 :   if (POINTER_TYPE_P (TREE_TYPE (guard_init)))
     438                 :            :     {
     439                 :          1 :       enddiff = gimple_convert (stmts, sizetype, enddiff);
     440                 :          1 :       newbound = gimple_build (stmts, POINTER_PLUS_EXPR,
     441                 :          1 :                                TREE_TYPE (guard_init),
     442                 :            :                                guard_init, enddiff);
     443                 :            :     }
     444                 :            :   else
     445                 :         51 :     newbound = gimple_build (stmts, PLUS_EXPR, TREE_TYPE (guard_init),
     446                 :            :                              guard_init, enddiff);
     447                 :            : 
     448                 :            :   /* Depending on the direction of the IVs the new bound for the first
     449                 :            :      loop is the minimum or maximum of old bound and border.
     450                 :            :      Also, if the guard condition isn't strictly less or greater,
     451                 :            :      we need to adjust the bound.  */ 
     452                 :         52 :   int addbound = 0;
     453                 :         52 :   enum tree_code minmax;
     454                 :         52 :   if (niter->cmp == LT_EXPR)
     455                 :            :     {
     456                 :            :       /* GT and LE are the same, inverted.  */
     457                 :         44 :       if (guard_code == GT_EXPR || guard_code == LE_EXPR)
     458                 :            :         addbound = -1;
     459                 :            :       minmax = MIN_EXPR;
     460                 :            :     }
     461                 :            :   else
     462                 :            :     {
     463                 :          8 :       gcc_assert (niter->cmp == GT_EXPR);
     464                 :          8 :       if (guard_code == GE_EXPR || guard_code == LT_EXPR)
     465                 :            :         addbound = 1;
     466                 :            :       minmax = MAX_EXPR;
     467                 :            :     }
     468                 :            : 
     469                 :            :   if (addbound)
     470                 :            :     {
     471                 :         25 :       tree type2 = TREE_TYPE (newbound);
     472                 :         25 :       if (POINTER_TYPE_P (type2))
     473                 :          0 :         type2 = sizetype;
     474                 :         50 :       newbound = gimple_build (stmts,
     475                 :         25 :                                POINTER_TYPE_P (TREE_TYPE (newbound))
     476                 :            :                                ? POINTER_PLUS_EXPR : PLUS_EXPR,
     477                 :         25 :                                TREE_TYPE (newbound),
     478                 :            :                                newbound,
     479                 :            :                                build_int_cst (type2, addbound));
     480                 :            :     }
     481                 :            : 
     482                 :         52 :   tree newend = gimple_build (stmts, minmax, TREE_TYPE (border),
     483                 :            :                               border, newbound);
     484                 :         52 :   return newend;
     485                 :            : }
     486                 :            : 
     487                 :            : /* Checks if LOOP contains an conditional block whose condition
     488                 :            :    depends on which side in the iteration space it is, and if so
     489                 :            :    splits the iteration space into two loops.  Returns true if the
     490                 :            :    loop was split.  NITER must contain the iteration descriptor for the
     491                 :            :    single exit of LOOP.  */
     492                 :            : 
     493                 :            : static bool
     494                 :      44858 : split_loop (class loop *loop1)
     495                 :            : {
     496                 :      44858 :   class tree_niter_desc niter;
     497                 :      44858 :   basic_block *bbs;
     498                 :      44858 :   unsigned i;
     499                 :      44858 :   bool changed = false;
     500                 :      44858 :   tree guard_iv;
     501                 :      44858 :   tree border = NULL_TREE;
     502                 :      44858 :   affine_iv iv;
     503                 :            : 
     504                 :      44858 :   if (!single_exit (loop1)
     505                 :            :       /* ??? We could handle non-empty latches when we split the latch edge
     506                 :            :          (not the exit edge), and put the new exit condition in the new block.
     507                 :            :          OTOH this executes some code unconditionally that might have been
     508                 :            :          skipped by the original exit before.  */
     509                 :      31908 :       || !empty_block_p (loop1->latch)
     510                 :      28881 :       || !easy_exit_values (loop1)
     511                 :      28860 :       || !number_of_iterations_exit (loop1, single_exit (loop1), &niter,
     512                 :            :                                      false, true)
     513                 :      23802 :       || niter.cmp == ERROR_MARK
     514                 :            :       /* We can't yet handle loops controlled by a != predicate.  */
     515                 :      68660 :       || niter.cmp == NE_EXPR)
     516                 :      35176 :     return false;
     517                 :            : 
     518                 :       9682 :   bbs = get_loop_body (loop1);
     519                 :            : 
     520                 :       9682 :   if (!can_copy_bbs_p (bbs, loop1->num_nodes))
     521                 :            :     {
     522                 :          1 :       free (bbs);
     523                 :          1 :       return false;
     524                 :            :     }
     525                 :            : 
     526                 :            :   /* Find a splitting opportunity.  */
     527                 :      48422 :   for (i = 0; i < loop1->num_nodes; i++)
     528                 :      38793 :     if ((guard_iv = split_at_bb_p (loop1, bbs[i], &border, &iv)))
     529                 :            :       {
     530                 :            :         /* Handling opposite steps is not implemented yet.  Neither
     531                 :            :            is handling different step sizes.  */
     532                 :        516 :         if ((tree_int_cst_sign_bit (iv.step)
     533                 :        516 :              != tree_int_cst_sign_bit (niter.control.step))
     534                 :        516 :             || !tree_int_cst_equal (iv.step, niter.control.step))
     535                 :        464 :           continue;
     536                 :            : 
     537                 :            :         /* Find a loop PHI node that defines guard_iv directly,
     538                 :            :            or create one doing that.  */
     539                 :        516 :         gphi *phi = find_or_create_guard_phi (loop1, guard_iv, &iv);
     540                 :        516 :         if (!phi)
     541                 :        464 :           continue;
     542                 :         52 :         gcond *guard_stmt = as_a<gcond *> (last_stmt (bbs[i]));
     543                 :         52 :         tree guard_init = PHI_ARG_DEF_FROM_EDGE (phi,
     544                 :            :                                                  loop_preheader_edge (loop1));
     545                 :         52 :         enum tree_code guard_code = gimple_cond_code (guard_stmt);
     546                 :            : 
     547                 :            :         /* Loop splitting is implemented by versioning the loop, placing
     548                 :            :            the new loop after the old loop, make the first loop iterate
     549                 :            :            as long as the conditional stays true (or false) and let the
     550                 :            :            second (new) loop handle the rest of the iterations.
     551                 :            : 
     552                 :            :            First we need to determine if the condition will start being true
     553                 :            :            or false in the first loop.  */
     554                 :         52 :         bool initial_true;
     555                 :         52 :         switch (guard_code)
     556                 :            :           {
     557                 :         33 :             case LT_EXPR:
     558                 :         33 :             case LE_EXPR:
     559                 :         33 :               initial_true = !tree_int_cst_sign_bit (iv.step);
     560                 :         33 :               break;
     561                 :         19 :             case GT_EXPR:
     562                 :         19 :             case GE_EXPR:
     563                 :         19 :               initial_true = tree_int_cst_sign_bit (iv.step);
     564                 :         19 :               break;
     565                 :          0 :             default:
     566                 :          0 :               gcc_unreachable ();
     567                 :            :           }
     568                 :            : 
     569                 :            :         /* Build a condition that will skip the first loop when the
     570                 :            :            guard condition won't ever be true (or false).  */
     571                 :         52 :         gimple_seq stmts2;
     572                 :         52 :         border = force_gimple_operand (border, &stmts2, true, NULL_TREE);
     573                 :         52 :         if (stmts2)
     574                 :          0 :           gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
     575                 :            :                                             stmts2);
     576                 :         52 :         tree cond = build2 (guard_code, boolean_type_node, guard_init, border);
     577                 :         52 :         if (!initial_true)
     578                 :         19 :           cond = fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, cond); 
     579                 :            : 
     580                 :            :         /* Now version the loop, placing loop2 after loop1 connecting
     581                 :            :            them, and fix up SSA form for that.  */
     582                 :         52 :         initialize_original_copy_tables ();
     583                 :         52 :         basic_block cond_bb;
     584                 :            : 
     585                 :         52 :         class loop *loop2 = loop_version (loop1, cond, &cond_bb,
     586                 :            :                                            profile_probability::always (),
     587                 :            :                                            profile_probability::always (),
     588                 :            :                                            profile_probability::always (),
     589                 :            :                                            profile_probability::always (),
     590                 :            :                                            true);
     591                 :         52 :         gcc_assert (loop2);
     592                 :         52 :         update_ssa (TODO_update_ssa);
     593                 :            : 
     594                 :         52 :         edge new_e = connect_loops (loop1, loop2);
     595                 :         52 :         connect_loop_phis (loop1, loop2, new_e);
     596                 :            : 
     597                 :            :         /* The iterations of the second loop is now already
     598                 :            :            exactly those that the first loop didn't do, but the
     599                 :            :            iteration space of the first loop is still the original one.
     600                 :            :            Compute the new bound for the guarding IV and patch the
     601                 :            :            loop exit to use it instead of original IV and bound.  */
     602                 :         52 :         gimple_seq stmts = NULL;
     603                 :         52 :         tree newend = compute_new_first_bound (&stmts, &niter, border,
     604                 :            :                                                guard_code, guard_init);
     605                 :         52 :         if (stmts)
     606                 :         50 :           gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop1),
     607                 :            :                                             stmts);
     608                 :         52 :         tree guard_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop1));
     609                 :         52 :         patch_loop_exit (loop1, guard_stmt, guard_next, newend, initial_true);
     610                 :            : 
     611                 :            :         /* Finally patch out the two copies of the condition to be always
     612                 :            :            true/false (or opposite).  */
     613                 :         52 :         gcond *force_true = as_a<gcond *> (last_stmt (bbs[i]));
     614                 :         52 :         gcond *force_false = as_a<gcond *> (last_stmt (get_bb_copy (bbs[i])));
     615                 :         52 :         if (!initial_true)
     616                 :         19 :           std::swap (force_true, force_false);
     617                 :         52 :         gimple_cond_make_true (force_true);
     618                 :         52 :         gimple_cond_make_false (force_false);
     619                 :         52 :         update_stmt (force_true);
     620                 :         52 :         update_stmt (force_false);
     621                 :            : 
     622                 :         52 :         free_original_copy_tables ();
     623                 :            : 
     624                 :            :         /* We destroyed LCSSA form above.  Eventually we might be able
     625                 :            :            to fix it on the fly, for now simply punt and use the helper.  */
     626                 :         52 :         rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
     627                 :            : 
     628                 :         52 :         changed = true;
     629                 :         52 :         if (dump_file && (dump_flags & TDF_DETAILS))
     630                 :         17 :           fprintf (dump_file, ";; Loop split.\n");
     631                 :            : 
     632                 :            :         /* Only deal with the first opportunity.  */
     633                 :         52 :         break;
     634                 :            :       }
     635                 :            : 
     636                 :       9681 :   free (bbs);
     637                 :       9681 :   return changed;
     638                 :            : }
     639                 :            : 
     640                 :            : /* Another transformation of loops like:
     641                 :            : 
     642                 :            :    for (i = INIT (); CHECK (i); i = NEXT ())
     643                 :            :      {
     644                 :            :        if (expr (a_1, a_2, ..., a_n))  // expr is pure
     645                 :            :          a_j = ...;  // change at least one a_j
     646                 :            :        else
     647                 :            :          S;          // not change any a_j
     648                 :            :      }
     649                 :            : 
     650                 :            :    into:
     651                 :            : 
     652                 :            :    for (i = INIT (); CHECK (i); i = NEXT ())
     653                 :            :      {
     654                 :            :        if (expr (a_1, a_2, ..., a_n))
     655                 :            :          a_j = ...;
     656                 :            :        else
     657                 :            :          {
     658                 :            :            S;
     659                 :            :            i = NEXT ();
     660                 :            :            break;
     661                 :            :          }
     662                 :            :      }
     663                 :            : 
     664                 :            :    for (; CHECK (i); i = NEXT ())
     665                 :            :      {
     666                 :            :        S;
     667                 :            :      }
     668                 :            : 
     669                 :            :    */
     670                 :            : 
     671                 :            : /* Data structure to hold temporary information during loop split upon
     672                 :            :    semi-invariant conditional statement.  */
     673                 :            : class split_info {
     674                 :            : public:
     675                 :            :   /* Array of all basic blocks in a loop, returned by get_loop_body().  */
     676                 :            :   basic_block *bbs;
     677                 :            : 
     678                 :            :   /* All memory store/clobber statements in a loop.  */
     679                 :            :   auto_vec<gimple *> memory_stores;
     680                 :            : 
     681                 :            :   /* Whether above memory stores vector has been filled.  */
     682                 :            :   int need_init;
     683                 :            : 
     684                 :            :   /* Control dependencies of basic blocks in a loop.  */
     685                 :            :   auto_vec<hash_set<basic_block> *> control_deps;
     686                 :            : 
     687                 :      44806 :   split_info () : bbs (NULL),  need_init (true) { }
     688                 :            : 
     689                 :      44806 :   ~split_info ()
     690                 :      45096 :     {
     691                 :      44806 :       if (bbs)
     692                 :      44806 :         free (bbs);
     693                 :            : 
     694                 :      45872 :       for (unsigned i = 0; i < control_deps.length (); i++)
     695                 :        776 :         delete control_deps[i];
     696                 :      44806 :     }
     697                 :            : };
     698                 :            : 
     699                 :            : /* Find all statements with memory-write effect in LOOP, including memory
     700                 :            :    store and non-pure function call, and keep those in a vector.  This work
     701                 :            :    is only done one time, for the vector should be constant during analysis
     702                 :            :    stage of semi-invariant condition.  */
     703                 :            : 
     704                 :            : static void
     705                 :       6070 : find_vdef_in_loop (struct loop *loop)
     706                 :            : {
     707                 :       6070 :   split_info *info = (split_info *) loop->aux;
     708                 :       6070 :   gphi *vphi = get_virtual_phi (loop->header);
     709                 :            : 
     710                 :            :   /* Indicate memory store vector has been filled.  */
     711                 :       6070 :   info->need_init = false;
     712                 :            : 
     713                 :            :   /* If loop contains memory operation, there must be a virtual PHI node in
     714                 :            :      loop header basic block.  */
     715                 :       6070 :   if (vphi == NULL)
     716                 :       1575 :     return;
     717                 :            : 
     718                 :            :   /* All virtual SSA names inside the loop are connected to be a cyclic
     719                 :            :      graph via virtual PHI nodes.  The virtual PHI node in loop header just
     720                 :            :      links the first and the last virtual SSA names, by using the last as
     721                 :            :      PHI operand to define the first.  */
     722                 :       4526 :   const edge latch = loop_latch_edge (loop);
     723                 :       4526 :   const tree first = gimple_phi_result (vphi);
     724                 :       4526 :   const tree last = PHI_ARG_DEF_FROM_EDGE (vphi, latch);
     725                 :            : 
     726                 :            :   /* The virtual SSA cyclic graph might consist of only one SSA name, who
     727                 :            :      is defined by itself.
     728                 :            : 
     729                 :            :        .MEM_1 = PHI <.MEM_2(loop entry edge), .MEM_1(latch edge)>
     730                 :            : 
     731                 :            :      This means the loop contains only memory loads, so we can skip it.  */
     732                 :       4526 :   if (first == last)
     733                 :            :     return;
     734                 :            : 
     735                 :       8990 :   auto_vec<gimple *> other_stores;
     736                 :       4495 :   auto_vec<tree> worklist;
     737                 :       8990 :   auto_bitmap visited;
     738                 :            : 
     739                 :       4495 :   bitmap_set_bit (visited, SSA_NAME_VERSION (first));
     740                 :       4495 :   bitmap_set_bit (visited, SSA_NAME_VERSION (last));
     741                 :       4495 :   worklist.safe_push (last);
     742                 :            : 
     743                 :      27635 :   do
     744                 :            :     {
     745                 :      27635 :       tree vuse = worklist.pop ();
     746                 :      27635 :       gimple *stmt = SSA_NAME_DEF_STMT (vuse);
     747                 :            : 
     748                 :            :       /* We mark the first and last SSA names as visited at the beginning,
     749                 :            :          and reversely start the process from the last SSA name towards the
     750                 :            :          first, which ensures that this do-while will not touch SSA names
     751                 :            :          defined outside the loop.  */
     752                 :      27635 :       gcc_assert (gimple_bb (stmt)
     753                 :            :                   && flow_bb_inside_loop_p (loop, gimple_bb (stmt)));
     754                 :            : 
     755                 :      27635 :       if (gimple_code (stmt) == GIMPLE_PHI)
     756                 :            :         {
     757                 :      23241 :           gphi *phi = as_a <gphi *> (stmt);
     758                 :            : 
     759                 :      23241 :           for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
     760                 :            :             {
     761                 :      15869 :               tree arg = gimple_phi_arg_def (stmt, i);
     762                 :            : 
     763                 :      15869 :               if (bitmap_set_bit (visited, SSA_NAME_VERSION (arg)))
     764                 :       9670 :                 worklist.safe_push (arg);
     765                 :            :             }
     766                 :            :         }
     767                 :            :       else
     768                 :            :         {
     769                 :      20263 :           tree prev = gimple_vuse (stmt);
     770                 :            : 
     771                 :            :           /* Non-pure call statement is conservatively assumed to impact all
     772                 :            :              memory locations.  So place call statements ahead of other memory
     773                 :            :              stores in the vector with an idea of using them as shortcut
     774                 :            :              terminators to memory alias analysis.  */
     775                 :      20263 :           if (gimple_code (stmt) == GIMPLE_CALL)
     776                 :       7385 :             info->memory_stores.safe_push (stmt);
     777                 :            :           else
     778                 :      12878 :             other_stores.safe_push (stmt);
     779                 :            : 
     780                 :      20263 :           if (bitmap_set_bit (visited, SSA_NAME_VERSION (prev)))
     781                 :      13470 :             worklist.safe_push (prev);
     782                 :            :         }
     783                 :      27635 :     } while (!worklist.is_empty ());
     784                 :            : 
     785                 :       4495 :     info->memory_stores.safe_splice (other_stores);
     786                 :            : }
     787                 :            : 
     788                 :            : /* Two basic blocks have equivalent control dependency if one dominates to
     789                 :            :    the other, and it is post-dominated by the latter.  Given a basic block
     790                 :            :    BB in LOOP, find farest equivalent dominating basic block.  For BB, there
     791                 :            :    is a constraint that BB does not post-dominate loop header of LOOP, this
     792                 :            :    means BB is control-dependent on at least one basic block in LOOP.  */
     793                 :            : 
     794                 :            : static basic_block
     795                 :        638 : get_control_equiv_head_block (struct loop *loop, basic_block bb)
     796                 :            : {
     797                 :        668 :   while (!bb->aux)
     798                 :            :     {
     799                 :        471 :       basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
     800                 :            : 
     801                 :        471 :       gcc_checking_assert (dom_bb && flow_bb_inside_loop_p (loop, dom_bb));
     802                 :            : 
     803                 :        471 :       if (!dominated_by_p (CDI_POST_DOMINATORS, dom_bb, bb))
     804                 :            :         break;
     805                 :            : 
     806                 :            :       bb = dom_bb;
     807                 :            :     }
     808                 :        638 :   return bb;
     809                 :            : }
     810                 :            : 
     811                 :            : /* Given a BB in LOOP, find out all basic blocks in LOOP that BB is control-
     812                 :            :    dependent on.  */
     813                 :            : 
     814                 :            : static hash_set<basic_block> *
     815                 :       4784 : find_control_dep_blocks (struct loop *loop, basic_block bb)
     816                 :            : {
     817                 :            :   /* BB has same control dependency as loop header, then it is not control-
     818                 :            :      dependent on any basic block in LOOP.  */
     819                 :       4784 :   if (dominated_by_p (CDI_POST_DOMINATORS, loop->header, bb))
     820                 :            :     return NULL;
     821                 :            : 
     822                 :        585 :   basic_block equiv_head = get_control_equiv_head_block (loop, bb);
     823                 :            : 
     824                 :        585 :   if (equiv_head->aux)
     825                 :            :     {
     826                 :            :       /* There is a basic block containing control dependency equivalent
     827                 :            :          to BB.  No need to recompute that, and also set this information
     828                 :            :          to other equivalent basic blocks.  */
     829                 :        197 :       for (; bb != equiv_head;
     830                 :          0 :            bb = get_immediate_dominator (CDI_DOMINATORS, bb))
     831                 :          0 :         bb->aux = equiv_head->aux;
     832                 :        197 :       return (hash_set<basic_block> *) equiv_head->aux;
     833                 :            :     }
     834                 :            : 
     835                 :            :   /* A basic block X is control-dependent on another Y iff there exists
     836                 :            :      a path from X to Y, in which every basic block other than X and Y
     837                 :            :      is post-dominated by Y, but X is not post-dominated by Y.
     838                 :            : 
     839                 :            :      According to this rule, traverse basic blocks in the loop backwards
     840                 :            :      starting from BB, if a basic block is post-dominated by BB, extend
     841                 :            :      current post-dominating path to this block, otherwise it is another
     842                 :            :      one that BB is control-dependent on.  */
     843                 :            : 
     844                 :        388 :   auto_vec<basic_block> pdom_worklist;
     845                 :        776 :   hash_set<basic_block> pdom_visited;
     846                 :        388 :   hash_set<basic_block> *dep_bbs = new hash_set<basic_block>;
     847                 :            : 
     848                 :        388 :   pdom_worklist.safe_push (equiv_head);
     849                 :            : 
     850                 :        441 :   do
     851                 :            :     {
     852                 :        441 :       basic_block pdom_bb = pdom_worklist.pop ();
     853                 :        441 :       edge_iterator ei;
     854                 :        441 :       edge e;
     855                 :            : 
     856                 :        441 :       if (pdom_visited.add (pdom_bb))
     857                 :         16 :         continue;
     858                 :            : 
     859                 :       1019 :       FOR_EACH_EDGE (e, ei, pdom_bb->preds)
     860                 :            :         {
     861                 :        594 :           basic_block pred_bb = e->src;
     862                 :            : 
     863                 :        594 :           if (!dominated_by_p (CDI_POST_DOMINATORS, pred_bb, bb))
     864                 :            :             {
     865                 :        541 :               dep_bbs->add (pred_bb);
     866                 :        594 :               continue;
     867                 :            :             }
     868                 :            : 
     869                 :         53 :           pred_bb = get_control_equiv_head_block (loop, pred_bb);
     870                 :            : 
     871                 :         53 :           if (pdom_visited.contains (pred_bb))
     872                 :          0 :             continue;
     873                 :            : 
     874                 :         53 :           if (!pred_bb->aux)
     875                 :            :             {
     876                 :         53 :               pdom_worklist.safe_push (pred_bb);
     877                 :         53 :               continue;
     878                 :            :             }
     879                 :            : 
     880                 :            :           /* If control dependency of basic block is available, fast extend
     881                 :            :              post-dominating path using the information instead of advancing
     882                 :            :              forward step-by-step.  */
     883                 :          0 :           hash_set<basic_block> *pred_dep_bbs
     884                 :            :                         = (hash_set<basic_block> *) pred_bb->aux;
     885                 :            : 
     886                 :          0 :           for (hash_set<basic_block>::iterator iter = pred_dep_bbs->begin ();
     887                 :          0 :                iter != pred_dep_bbs->end (); ++iter)
     888                 :            :             {
     889                 :          0 :               basic_block pred_dep_bb = *iter;
     890                 :            : 
     891                 :            :               /* Basic blocks can either be in control dependency of BB, or
     892                 :            :                  must be post-dominated by BB, if so, extend the path from
     893                 :            :                  these basic blocks.  */
     894                 :          0 :               if (!dominated_by_p (CDI_POST_DOMINATORS, pred_dep_bb, bb))
     895                 :          0 :                 dep_bbs->add (pred_dep_bb);
     896                 :          0 :               else if (!pdom_visited.contains (pred_dep_bb))
     897                 :          0 :                 pdom_worklist.safe_push (pred_dep_bb);
     898                 :            :             }
     899                 :            :         }
     900                 :        441 :     } while (!pdom_worklist.is_empty ());
     901                 :            : 
     902                 :            :   /* Record computed control dependencies in loop so that we can reach them
     903                 :            :      when reclaiming resources.  */
     904                 :        388 :   ((split_info *) loop->aux)->control_deps.safe_push (dep_bbs);
     905                 :            : 
     906                 :            :   /* Associate control dependence with related equivalent basic blocks.  */
     907                 :        400 :   for (equiv_head->aux = dep_bbs; bb != equiv_head;
     908                 :         12 :        bb = get_immediate_dominator (CDI_DOMINATORS, bb))
     909                 :         12 :     bb->aux = dep_bbs;
     910                 :            : 
     911                 :        388 :   return dep_bbs;
     912                 :            : }
     913                 :            : 
     914                 :            : /* Forward declaration */
     915                 :            : 
     916                 :            : static bool
     917                 :            : stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
     918                 :            :                          const_basic_block skip_head,
     919                 :            :                          hash_map<gimple *, bool> &stmt_stat);
     920                 :            : 
     921                 :            : /* Given STMT, memory load or pure call statement, check whether it is impacted
     922                 :            :    by some memory store in LOOP, excluding trace starting from SKIP_HEAD (the
     923                 :            :    trace is composed of SKIP_HEAD and those basic block dominated by it, always
     924                 :            :    corresponds to one branch of a conditional statement).  If SKIP_HEAD is
     925                 :            :    NULL, all basic blocks of LOOP are checked.  */
     926                 :            : 
     927                 :            : static bool
     928                 :      12998 : vuse_semi_invariant_p (struct loop *loop, gimple *stmt,
     929                 :            :                        const_basic_block skip_head)
     930                 :            : {
     931                 :      12998 :   split_info *info = (split_info *) loop->aux;
     932                 :      12998 :   tree rhs = NULL_TREE;
     933                 :      12998 :   ao_ref ref;
     934                 :      12998 :   gimple *store;
     935                 :      12998 :   unsigned i;
     936                 :            : 
     937                 :            :   /* Collect memory store/clobber statements if haven't done that.  */
     938                 :      12998 :   if (info->need_init)
     939                 :       6070 :     find_vdef_in_loop (loop);
     940                 :            : 
     941                 :      12998 :   if (is_gimple_assign (stmt))
     942                 :      12840 :     rhs = gimple_assign_rhs1 (stmt);
     943                 :            : 
     944                 :      12998 :   ao_ref_init (&ref, rhs);
     945                 :            : 
     946                 :      29679 :   FOR_EACH_VEC_ELT (info->memory_stores, i, store)
     947                 :            :     {
     948                 :            :       /* Skip basic blocks dominated by SKIP_HEAD, if non-NULL.  */
     949                 :      30798 :       if (skip_head
     950                 :      22243 :           && dominated_by_p (CDI_DOMINATORS, gimple_bb (store), skip_head))
     951                 :       8555 :         continue;
     952                 :            : 
     953                 :      13688 :       if (!ref.ref || stmt_may_clobber_ref_p_1 (store, &ref))
     954                 :       5562 :         return false;
     955                 :            :     }
     956                 :            : 
     957                 :            :   return true;
     958                 :            : }
     959                 :            : 
     960                 :            : /* Suppose one condition branch, led by SKIP_HEAD, is not executed since
     961                 :            :    certain iteration of LOOP, check whether an SSA name (NAME) remains
     962                 :            :    unchanged in next iteration.  We call this characteristic semi-
     963                 :            :    invariantness.  SKIP_HEAD might be NULL, if so, nothing excluded, all basic
     964                 :            :    blocks and control flows in the loop will be considered.  Semi-invariant
     965                 :            :    state of checked statement is cached in hash map STMT_STAT to avoid
     966                 :            :    redundant computation in possible following re-check.  */
     967                 :            : 
     968                 :            : static inline bool
     969                 :      66670 : ssa_semi_invariant_p (struct loop *loop, tree name,
     970                 :            :                       const_basic_block skip_head,
     971                 :            :                       hash_map<gimple *, bool> &stmt_stat)
     972                 :            : {
     973                 :      66670 :   gimple *def = SSA_NAME_DEF_STMT (name);
     974                 :      66670 :   const_basic_block def_bb = gimple_bb (def);
     975                 :            : 
     976                 :            :   /* An SSA name defined outside loop is definitely semi-invariant.  */
     977                 :      66670 :   if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
     978                 :       7071 :     return true;
     979                 :            : 
     980                 :      59599 :   return stmt_semi_invariant_p_1 (loop, def, skip_head, stmt_stat);
     981                 :            : }
     982                 :            : 
     983                 :            : /* Check whether a loop iteration PHI node (LOOP_PHI) defines a value that is
     984                 :            :    semi-invariant in LOOP.  Basic blocks dominated by SKIP_HEAD (if non-NULL),
     985                 :            :    are excluded from LOOP.  */
     986                 :            : 
     987                 :            : static bool
     988                 :      14759 : loop_iter_phi_semi_invariant_p (struct loop *loop, gphi *loop_phi,
     989                 :            :                                 const_basic_block skip_head)
     990                 :            : {
     991                 :      14759 :   const_edge latch = loop_latch_edge (loop);
     992                 :      14759 :   tree name = gimple_phi_result (loop_phi);
     993                 :      14759 :   tree from = PHI_ARG_DEF_FROM_EDGE (loop_phi, latch);
     994                 :            : 
     995                 :      14759 :   gcc_checking_assert (from);
     996                 :            : 
     997                 :            :   /* Loop iteration PHI node locates in loop header, and it has two source
     998                 :            :      operands, one is an initial value coming from outside the loop, the other
     999                 :            :      is a value through latch of the loop, which is derived in last iteration,
    1000                 :            :      we call the latter latch value.  From the PHI node to definition of latch
    1001                 :            :      value, if excluding branch trace starting from SKIP_HEAD, except copy-
    1002                 :            :      assignment or likewise, there is no other kind of value redefinition, SSA
    1003                 :            :      name defined by the PHI node is semi-invariant.
    1004                 :            : 
    1005                 :            :                          loop entry
    1006                 :            :                               |     .--- latch ---.
    1007                 :            :                               |     |             |
    1008                 :            :                               v     v             |
    1009                 :            :                   x_1 = PHI <x_0,  x_3>           |
    1010                 :            :                            |                      |
    1011                 :            :                            v                      |
    1012                 :            :               .------- if (cond) -------.         |
    1013                 :            :               |                         |         |
    1014                 :            :               |                     [ SKIP ]      |
    1015                 :            :               |                         |         |
    1016                 :            :               |                     x_2 = ...     |
    1017                 :            :               |                         |         |
    1018                 :            :               '---- T ---->.<---- F ----'         |
    1019                 :            :                            |                      |
    1020                 :            :                            v                      |
    1021                 :            :                   x_3 = PHI <x_1, x_2>            |
    1022                 :            :                            |                      |
    1023                 :            :                            '----------------------'
    1024                 :            : 
    1025                 :            :      Suppose in certain iteration, execution flow in above graph goes through
    1026                 :            :      true branch, which means that one source value to define x_3 in false
    1027                 :            :      branch (x_2) is skipped, x_3 only comes from x_1, and x_1 in next
    1028                 :            :      iterations is defined by x_3, we know that x_1 will never changed if COND
    1029                 :            :      always chooses true branch from then on.  */
    1030                 :            : 
    1031                 :      17051 :   while (from != name)
    1032                 :            :     {
    1033                 :            :       /* A new value comes from a CONSTANT.  */
    1034                 :      16554 :       if (TREE_CODE (from) != SSA_NAME)
    1035                 :            :         return false;
    1036                 :            : 
    1037                 :      16192 :       gimple *stmt = SSA_NAME_DEF_STMT (from);
    1038                 :      16192 :       const_basic_block bb = gimple_bb (stmt);
    1039                 :            : 
    1040                 :            :       /* A new value comes from outside the loop.  */
    1041                 :      16192 :       if (!bb || !flow_bb_inside_loop_p (loop, bb))
    1042                 :         16 :         return false;
    1043                 :            : 
    1044                 :      16176 :       from = NULL_TREE;
    1045                 :            : 
    1046                 :      16176 :       if (gimple_code (stmt) == GIMPLE_PHI)
    1047                 :            :         {
    1048                 :      10356 :           gphi *phi = as_a <gphi *> (stmt);
    1049                 :            : 
    1050                 :      10356 :           for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
    1051                 :            :             {
    1052                 :       8064 :               if (skip_head)
    1053                 :            :                 {
    1054                 :       7692 :                   const_edge e = gimple_phi_arg_edge (phi, i);
    1055                 :            : 
    1056                 :            :                   /* Don't consider redefinitions in excluded basic blocks.  */
    1057                 :       7692 :                   if (dominated_by_p (CDI_DOMINATORS, e->src, skip_head))
    1058                 :       2773 :                     continue;
    1059                 :            :                 }
    1060                 :            : 
    1061                 :       5291 :               tree arg = gimple_phi_arg_def (phi, i);
    1062                 :            : 
    1063                 :       5291 :               if (!from)
    1064                 :            :                 from = arg;
    1065                 :       1535 :               else if (!operand_equal_p (from, arg, 0))
    1066                 :            :                 /* There are more than one source operands that provide
    1067                 :            :                    different values to the SSA name, it is variant.  */
    1068                 :            :                 return false;
    1069                 :            :             }
    1070                 :            :         }
    1071                 :      12420 :       else if (gimple_code (stmt) == GIMPLE_ASSIGN)
    1072                 :            :         {
    1073                 :            :           /* For simple value copy, check its rhs instead.  */
    1074                 :      12389 :           if (gimple_assign_ssa_name_copy_p (stmt))
    1075                 :          0 :             from = gimple_assign_rhs1 (stmt);
    1076                 :            :         }
    1077                 :            : 
    1078                 :            :       /* Any other kind of definition is deemed to introduce a new value
    1079                 :            :          to the SSA name.  */
    1080                 :       2292 :       if (!from)
    1081                 :      12420 :         return false;
    1082                 :            :     }
    1083                 :            :   return true;
    1084                 :            : }
    1085                 :            : 
    1086                 :            : /* Check whether conditional predicates that BB is control-dependent on, are
    1087                 :            :    semi-invariant in LOOP.  Basic blocks dominated by SKIP_HEAD (if non-NULL),
    1088                 :            :    are excluded from LOOP.  Semi-invariant state of checked statement is cached
    1089                 :            :    in hash map STMT_STAT.  */
    1090                 :            : 
    1091                 :            : static bool
    1092                 :       4784 : control_dep_semi_invariant_p (struct loop *loop, basic_block bb,
    1093                 :            :                               const_basic_block skip_head,
    1094                 :            :                               hash_map<gimple *, bool> &stmt_stat)
    1095                 :            : {
    1096                 :       4784 :   hash_set<basic_block> *dep_bbs = find_control_dep_blocks (loop, bb);
    1097                 :            : 
    1098                 :       4784 :   if (!dep_bbs)
    1099                 :            :     return true;
    1100                 :            : 
    1101                 :       1344 :   for (hash_set<basic_block>::iterator iter = dep_bbs->begin ();
    1102                 :        672 :        iter != dep_bbs->end (); ++iter)
    1103                 :            :     {
    1104                 :        588 :       gimple *last = last_stmt (*iter);
    1105                 :            : 
    1106                 :        588 :       if (!last)
    1107                 :            :         return false;
    1108                 :            : 
    1109                 :            :       /* Only check condition predicates.  */
    1110                 :        588 :       if (gimple_code (last) != GIMPLE_COND
    1111                 :        588 :           && gimple_code (last) != GIMPLE_SWITCH)
    1112                 :            :         return false;
    1113                 :            : 
    1114                 :        588 :       if (!stmt_semi_invariant_p_1 (loop, last, skip_head, stmt_stat))
    1115                 :            :         return false;
    1116                 :            :     }
    1117                 :            : 
    1118                 :            :   return true;
    1119                 :            : }
    1120                 :            : 
    1121                 :            : /* Check whether STMT is semi-invariant in LOOP, iff all its operands are
    1122                 :            :    semi-invariant, consequently, all its defined values are semi-invariant.
    1123                 :            :    Basic blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.
    1124                 :            :    Semi-invariant state of checked statement is cached in hash map
    1125                 :            :    STMT_STAT.  */
    1126                 :            : 
    1127                 :            : static bool
    1128                 :      84452 : stmt_semi_invariant_p_1 (struct loop *loop, gimple *stmt,
    1129                 :            :                          const_basic_block skip_head,
    1130                 :            :                          hash_map<gimple *, bool> &stmt_stat)
    1131                 :            : {
    1132                 :      84452 :   bool existed;
    1133                 :      84452 :   bool &invar = stmt_stat.get_or_insert (stmt, &existed);
    1134                 :            : 
    1135                 :      84452 :   if (existed)
    1136                 :         85 :     return invar;
    1137                 :            : 
    1138                 :            :   /* A statement might depend on itself, which is treated as variant.  So set
    1139                 :            :      state of statement under check to be variant to ensure that.  */
    1140                 :      84367 :   invar = false;
    1141                 :            : 
    1142                 :      84367 :   if (gimple_code (stmt) == GIMPLE_PHI)
    1143                 :            :     {
    1144                 :      17388 :       gphi *phi = as_a <gphi *> (stmt);
    1145                 :            : 
    1146                 :      17388 :       if (gimple_bb (stmt) == loop->header)
    1147                 :            :         {
    1148                 :      14759 :           invar = loop_iter_phi_semi_invariant_p (loop, phi, skip_head);
    1149                 :      14759 :           return invar;
    1150                 :            :         }
    1151                 :            : 
    1152                 :            :       /* For a loop PHI node that does not locate in loop header, it is semi-
    1153                 :            :          invariant only if two conditions are met.  The first is its source
    1154                 :            :          values are derived from CONSTANT (including loop-invariant value), or
    1155                 :            :          from SSA name defined by semi-invariant loop iteration PHI node.  The
    1156                 :            :          second is its source incoming edges are control-dependent on semi-
    1157                 :            :          invariant conditional predicates.  */
    1158                 :       2703 :       for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i)
    1159                 :            :         {
    1160                 :       2699 :           const_edge e = gimple_phi_arg_edge (phi, i);
    1161                 :       2699 :           tree arg = gimple_phi_arg_def (phi, i);
    1162                 :            : 
    1163                 :       2699 :           if (TREE_CODE (arg) == SSA_NAME)
    1164                 :            :             {
    1165                 :       2509 :               if (!ssa_semi_invariant_p (loop, arg, skip_head, stmt_stat))
    1166                 :            :                 return false;
    1167                 :            : 
    1168                 :            :               /* If source value is defined in location from where the source
    1169                 :            :                  edge comes in, no need to check control dependency again
    1170                 :            :                  since this has been done in above SSA name check stage.  */
    1171                 :         54 :               if (e->src == gimple_bb (SSA_NAME_DEF_STMT (arg)))
    1172                 :          6 :                 continue;
    1173                 :            :             }
    1174                 :            : 
    1175                 :        238 :           if (!control_dep_semi_invariant_p (loop, e->src, skip_head,
    1176                 :            :                                              stmt_stat))
    1177                 :            :             return false;
    1178                 :            :         }
    1179                 :            :     }
    1180                 :            :   else
    1181                 :            :     {
    1182                 :      66979 :       ssa_op_iter iter;
    1183                 :      66979 :       tree use;
    1184                 :            : 
    1185                 :            :       /* Volatile memory load or return of normal (non-const/non-pure) call
    1186                 :            :          should not be treated as constant in each iteration of loop.  */
    1187                 :      66979 :       if (gimple_has_side_effects (stmt))
    1188                 :      62437 :         return false;
    1189                 :            : 
    1190                 :            :       /* Check if any memory store may kill memory load at this place.  */
    1191                 :     106174 :       if (gimple_vuse (stmt) && !vuse_semi_invariant_p (loop, stmt, skip_head))
    1192                 :            :         return false;
    1193                 :            : 
    1194                 :            :       /* Although operand of a statement might be SSA name, CONSTANT or
    1195                 :            :          VARDECL, here we only need to check SSA name operands.  This is
    1196                 :            :          because check on VARDECL operands, which involve memory loads,
    1197                 :            :          must have been done prior to invocation of this function in
    1198                 :            :          vuse_semi_invariant_p.  */
    1199                 :      68703 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
    1200                 :      64161 :         if (!ssa_semi_invariant_p (loop, use, skip_head, stmt_stat))
    1201                 :            :           return false;
    1202                 :            :     }
    1203                 :            : 
    1204                 :       4546 :   if (!control_dep_semi_invariant_p (loop, gimple_bb (stmt), skip_head,
    1205                 :            :                                      stmt_stat))
    1206                 :            :     return false;
    1207                 :            : 
    1208                 :            :   /* Here we SHOULD NOT use invar = true, since hash map might be changed due
    1209                 :            :      to new insertion, and thus invar may point to invalid memory.  */
    1210                 :       4215 :   stmt_stat.put (stmt, true);
    1211                 :       4215 :   return true;
    1212                 :            : }
    1213                 :            : 
    1214                 :            : /* A helper function to check whether STMT is semi-invariant in LOOP.  Basic
    1215                 :            :    blocks dominated by SKIP_HEAD (if non-NULL), are excluded from LOOP.  */
    1216                 :            : 
    1217                 :            : static bool
    1218                 :      24265 : stmt_semi_invariant_p (struct loop *loop, gimple *stmt,
    1219                 :            :                        const_basic_block skip_head)
    1220                 :            : {
    1221                 :      24265 :   hash_map<gimple *, bool> stmt_stat;
    1222                 :      24265 :   return stmt_semi_invariant_p_1 (loop, stmt, skip_head, stmt_stat);
    1223                 :            : }
    1224                 :            : 
    1225                 :            : /* Determine when conditional statement never transfers execution to one of its
    1226                 :            :    branch, whether we can remove the branch's leading basic block (BRANCH_BB)
    1227                 :            :    and those basic blocks dominated by BRANCH_BB.  */
    1228                 :            : 
    1229                 :            : static bool
    1230                 :      28572 : branch_removable_p (basic_block branch_bb)
    1231                 :            : {
    1232                 :      28572 :   edge_iterator ei;
    1233                 :      28572 :   edge e;
    1234                 :            : 
    1235                 :      28572 :   if (single_pred_p (branch_bb))
    1236                 :            :     return true;
    1237                 :            : 
    1238                 :       6939 :   FOR_EACH_EDGE (e, ei, branch_bb->preds)
    1239                 :            :     {
    1240                 :       6939 :       if (dominated_by_p (CDI_DOMINATORS, e->src, branch_bb))
    1241                 :          0 :         continue;
    1242                 :            : 
    1243                 :       6939 :       if (dominated_by_p (CDI_DOMINATORS, branch_bb, e->src))
    1244                 :       1844 :         continue;
    1245                 :            : 
    1246                 :            :        /* The branch can be reached from opposite branch, or from some
    1247                 :            :           statement not dominated by the conditional statement.  */
    1248                 :            :       return false;
    1249                 :            :     }
    1250                 :            : 
    1251                 :            :   return true;
    1252                 :            : }
    1253                 :            : 
    1254                 :            : /* Find out which branch of a conditional statement (COND) is invariant in the
    1255                 :            :    execution context of LOOP.  That is: once the branch is selected in certain
    1256                 :            :    iteration of the loop, any operand that contributes to computation of the
    1257                 :            :    conditional statement remains unchanged in all following iterations.  */
    1258                 :            : 
    1259                 :            : static edge
    1260                 :      75642 : get_cond_invariant_branch (struct loop *loop, gcond *cond)
    1261                 :            : {
    1262                 :      75642 :   basic_block cond_bb = gimple_bb (cond);
    1263                 :      75642 :   basic_block targ_bb[2];
    1264                 :      75642 :   bool invar[2];
    1265                 :      75642 :   unsigned invar_checks = 0;
    1266                 :            : 
    1267                 :     124163 :   for (unsigned i = 0; i < 2; i++)
    1268                 :            :     {
    1269                 :     109877 :       targ_bb[i] = EDGE_SUCC (cond_bb, i)->dest;
    1270                 :            : 
    1271                 :            :       /* One branch directs to loop exit, no need to perform loop split upon
    1272                 :            :          this conditional statement.  Firstly, it is trivial if the exit branch
    1273                 :            :          is semi-invariant, for the statement is just to break loop.  Secondly,
    1274                 :            :          if the opposite branch is semi-invariant, it means that the statement
    1275                 :            :          is real loop-invariant, which is covered by loop unswitch.  */
    1276                 :     109877 :       if (!flow_bb_inside_loop_p (loop, targ_bb[i]))
    1277                 :            :         return NULL;
    1278                 :            :     }
    1279                 :            : 
    1280                 :      42858 :   for (unsigned i = 0; i < 2; i++)
    1281                 :            :     {
    1282                 :      28572 :       invar[!i] = false;
    1283                 :            : 
    1284                 :      28572 :       if (!branch_removable_p (targ_bb[i]))
    1285                 :       5095 :         continue;
    1286                 :            : 
    1287                 :            :       /* Given a semi-invariant branch, if its opposite branch dominates
    1288                 :            :          loop latch, it and its following trace will only be executed in
    1289                 :            :          final iteration of loop, namely it is not part of repeated body
    1290                 :            :          of the loop.  Similar to the above case that the branch is loop
    1291                 :            :          exit, no need to split loop.  */
    1292                 :      23477 :       if (dominated_by_p (CDI_DOMINATORS, loop->latch, targ_bb[i]))
    1293                 :          0 :         continue;
    1294                 :            : 
    1295                 :      23477 :       invar[!i] = stmt_semi_invariant_p (loop, cond, targ_bb[i]);
    1296                 :      23477 :       invar_checks++;
    1297                 :            :     }
    1298                 :            : 
    1299                 :            :   /* With both branches being invariant (handled by loop unswitch) or
    1300                 :            :      variant is not what we want.  */
    1301                 :      14286 :   if (invar[0] ^ !invar[1])
    1302                 :            :     return NULL;
    1303                 :            : 
    1304                 :            :   /* Found a real loop-invariant condition, do nothing.  */
    1305                 :       1025 :   if (invar_checks < 2 && stmt_semi_invariant_p (loop, cond, NULL))
    1306                 :            :     return NULL;
    1307                 :            : 
    1308                 :        778 :   return EDGE_SUCC (cond_bb, invar[0] ? 0 : 1);
    1309                 :            : }
    1310                 :            : 
    1311                 :            : /* Calculate increased code size measured by estimated insn number if applying
    1312                 :            :    loop split upon certain branch (BRANCH_EDGE) of a conditional statement.  */
    1313                 :            : 
    1314                 :            : static int
    1315                 :        453 : compute_added_num_insns (struct loop *loop, const_edge branch_edge)
    1316                 :            : {
    1317                 :        453 :   basic_block cond_bb = branch_edge->src;
    1318                 :        453 :   unsigned branch = EDGE_SUCC (cond_bb, 1) == branch_edge;
    1319                 :        453 :   basic_block opposite_bb = EDGE_SUCC (cond_bb, !branch)->dest;
    1320                 :        453 :   basic_block *bbs = ((split_info *) loop->aux)->bbs;
    1321                 :        453 :   int num = 0;
    1322                 :            : 
    1323                 :       4218 :   for (unsigned i = 0; i < loop->num_nodes; i++)
    1324                 :            :     {
    1325                 :            :       /* Do no count basic blocks only in opposite branch.  */
    1326                 :       3765 :       if (dominated_by_p (CDI_DOMINATORS, bbs[i], opposite_bb))
    1327                 :       1616 :         continue;
    1328                 :            : 
    1329                 :       4298 :       num += estimate_num_insns_seq (bb_seq (bbs[i]), &eni_size_weights);
    1330                 :            :     }
    1331                 :            : 
    1332                 :            :   /* It is unnecessary to evaluate expression of the conditional statement
    1333                 :            :      in new loop that contains only invariant branch.  This expression should
    1334                 :            :      be constant value (either true or false).  Exclude code size of insns
    1335                 :            :      that contribute to computation of the expression.  */
    1336                 :            : 
    1337                 :        453 :   auto_vec<gimple *> worklist;
    1338                 :        906 :   hash_set<gimple *> removed;
    1339                 :        453 :   gimple *stmt = last_stmt (cond_bb);
    1340                 :            : 
    1341                 :        453 :   worklist.safe_push (stmt);
    1342                 :        453 :   removed.add (stmt);
    1343                 :        453 :   num -= estimate_num_insns (stmt, &eni_size_weights);
    1344                 :            : 
    1345                 :        532 :   do
    1346                 :            :     {
    1347                 :        532 :       ssa_op_iter opnd_iter;
    1348                 :        532 :       use_operand_p opnd_p;
    1349                 :            : 
    1350                 :        532 :       stmt = worklist.pop ();
    1351                 :       1592 :       FOR_EACH_PHI_OR_STMT_USE (opnd_p, stmt, opnd_iter, SSA_OP_USE)
    1352                 :            :         {
    1353                 :        528 :           tree opnd = USE_FROM_PTR (opnd_p);
    1354                 :            : 
    1355                 :        528 :           if (TREE_CODE (opnd) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (opnd))
    1356                 :         28 :             continue;
    1357                 :            : 
    1358                 :        511 :           gimple *opnd_stmt = SSA_NAME_DEF_STMT (opnd);
    1359                 :        511 :           use_operand_p use_p;
    1360                 :        511 :           imm_use_iterator use_iter;
    1361                 :            : 
    1362                 :        511 :           if (removed.contains (opnd_stmt)
    1363                 :        511 :               || !flow_bb_inside_loop_p (loop, gimple_bb (opnd_stmt)))
    1364                 :         11 :             continue;
    1365                 :            : 
    1366                 :        604 :           FOR_EACH_IMM_USE_FAST (use_p, use_iter, opnd)
    1367                 :            :             {
    1368                 :        525 :               gimple *use_stmt = USE_STMT (use_p);
    1369                 :            : 
    1370                 :       1043 :               if (!is_gimple_debug (use_stmt) && !removed.contains (use_stmt))
    1371                 :            :                 {
    1372                 :        421 :                   opnd_stmt = NULL;
    1373                 :        421 :                   break;
    1374                 :            :                 }
    1375                 :            :             }
    1376                 :            : 
    1377                 :        500 :           if (opnd_stmt)
    1378                 :            :             {
    1379                 :         79 :               worklist.safe_push (opnd_stmt);
    1380                 :         79 :               removed.add (opnd_stmt);
    1381                 :         79 :               num -= estimate_num_insns (opnd_stmt, &eni_size_weights);
    1382                 :            :             }
    1383                 :            :         }
    1384                 :        532 :     } while (!worklist.is_empty ());
    1385                 :            : 
    1386                 :        453 :   gcc_assert (num >= 0);
    1387                 :        453 :   return num;
    1388                 :            : }
    1389                 :            : 
    1390                 :            : /* Find out loop-invariant branch of a conditional statement (COND) if it has,
    1391                 :            :    and check whether it is eligible and profitable to perform loop split upon
    1392                 :            :    this branch in LOOP.  */
    1393                 :            : 
    1394                 :            : static edge
    1395                 :      75642 : get_cond_branch_to_split_loop (struct loop *loop, gcond *cond)
    1396                 :            : {
    1397                 :      75642 :   edge invar_branch = get_cond_invariant_branch (loop, cond);
    1398                 :      75642 :   if (!invar_branch)
    1399                 :            :     return NULL;
    1400                 :            : 
    1401                 :            :   /* When accurate profile information is available, and execution
    1402                 :            :      frequency of the branch is too low, just let it go.  */
    1403                 :        453 :   profile_probability prob = invar_branch->probability;
    1404                 :        453 :   if (prob.reliable_p ())
    1405                 :            :     {
    1406                 :          5 :       int thres = param_min_loop_cond_split_prob;
    1407                 :            : 
    1408                 :         10 :       if (prob < profile_probability::always ().apply_scale (thres, 100))
    1409                 :          0 :         return NULL;
    1410                 :            :     }
    1411                 :            : 
    1412                 :            :   /* Add a threshold for increased code size to disable loop split.  */
    1413                 :        453 :   if (compute_added_num_insns (loop, invar_branch) > param_max_peeled_insns)
    1414                 :          4 :     return NULL;
    1415                 :            : 
    1416                 :            :   return invar_branch;
    1417                 :            : }
    1418                 :            : 
    1419                 :            : /* Given a loop (LOOP1) with a loop-invariant branch (INVAR_BRANCH) of some
    1420                 :            :    conditional statement, perform loop split transformation illustrated
    1421                 :            :    as the following graph.
    1422                 :            : 
    1423                 :            :                .-------T------ if (true) ------F------.
    1424                 :            :                |                    .---------------. |
    1425                 :            :                |                    |               | |
    1426                 :            :                v                    |               v v
    1427                 :            :           pre-header                |            pre-header
    1428                 :            :                | .------------.     |                 | .------------.
    1429                 :            :                | |            |     |                 | |            |
    1430                 :            :                | v            |     |                 | v            |
    1431                 :            :              header           |     |               header           |
    1432                 :            :                |              |     |                 |              |
    1433                 :            :       .--- if (cond) ---.     |     |        .--- if (true) ---.     |
    1434                 :            :       |                 |     |     |        |                 |     |
    1435                 :            :   invariant             |     |     |    invariant             |     |
    1436                 :            :       |                 |     |     |        |                 |     |
    1437                 :            :       '---T--->.<---F---'     |     |        '---T--->.<---F---'     |
    1438                 :            :                |              |    /                  |              |
    1439                 :            :              stmts            |   /                 stmts            |
    1440                 :            :                |              F  T                    |              |
    1441                 :            :               / \             | /                    / \             |
    1442                 :            :      .-------*   *      [ if (cond) ]       .-------*   *            |
    1443                 :            :      |           |            |             |           |            |
    1444                 :            :      |         latch          |             |         latch          |
    1445                 :            :      |           |            |             |           |            |
    1446                 :            :      |           '------------'             |           '------------'
    1447                 :            :      '------------------------. .-----------'
    1448                 :            :              loop1            | |                   loop2
    1449                 :            :                               v v
    1450                 :            :                              exits
    1451                 :            : 
    1452                 :            :    In the graph, loop1 represents the part derived from original one, and
    1453                 :            :    loop2 is duplicated using loop_version (), which corresponds to the part
    1454                 :            :    of original one being splitted out.  In original latch edge of loop1, we
    1455                 :            :    insert a new conditional statement duplicated from the semi-invariant cond,
    1456                 :            :    and one of its branch goes back to loop1 header as a latch edge, and the
    1457                 :            :    other branch goes to loop2 pre-header as an entry edge.  And also in loop2,
    1458                 :            :    we abandon the variant branch of the conditional statement by setting a
    1459                 :            :    constant bool condition, based on which branch is semi-invariant.  */
    1460                 :            : 
    1461                 :            : static bool
    1462                 :        449 : do_split_loop_on_cond (struct loop *loop1, edge invar_branch)
    1463                 :            : {
    1464                 :        449 :   basic_block cond_bb = invar_branch->src;
    1465                 :        449 :   bool true_invar = !!(invar_branch->flags & EDGE_TRUE_VALUE);
    1466                 :        449 :   gcond *cond = as_a <gcond *> (last_stmt (cond_bb));
    1467                 :            : 
    1468                 :        449 :   gcc_assert (cond_bb->loop_father == loop1);
    1469                 :            : 
    1470                 :        449 :   if (dump_enabled_p ())
    1471                 :        138 :     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
    1472                 :            :                      "loop split on semi-invariant condition at %s branch\n",
    1473                 :            :                      true_invar ? "true" : "false");
    1474                 :            : 
    1475                 :        449 :   initialize_original_copy_tables ();
    1476                 :            : 
    1477                 :        449 :   struct loop *loop2 = loop_version (loop1, boolean_true_node, NULL,
    1478                 :            :                                      profile_probability::always (),
    1479                 :            :                                      profile_probability::never (),
    1480                 :            :                                      profile_probability::always (),
    1481                 :            :                                      profile_probability::always (),
    1482                 :            :                                      true);
    1483                 :        449 :   if (!loop2)
    1484                 :            :     {
    1485                 :          0 :       free_original_copy_tables ();
    1486                 :          0 :       return false;
    1487                 :            :     }
    1488                 :            : 
    1489                 :        449 :   basic_block cond_bb_copy = get_bb_copy (cond_bb);
    1490                 :        449 :   gcond *cond_copy = as_a<gcond *> (last_stmt (cond_bb_copy));
    1491                 :            : 
    1492                 :            :   /* Replace the condition in loop2 with a bool constant to let PassManager
    1493                 :            :      remove the variant branch after current pass completes.  */
    1494                 :        449 :   if (true_invar)
    1495                 :        122 :     gimple_cond_make_true (cond_copy);
    1496                 :            :   else
    1497                 :        327 :     gimple_cond_make_false (cond_copy);
    1498                 :            : 
    1499                 :        449 :   update_stmt (cond_copy);
    1500                 :            : 
    1501                 :            :   /* Insert a new conditional statement on latch edge of loop1, its condition
    1502                 :            :      is duplicated from the semi-invariant.  This statement acts as a switch
    1503                 :            :      to transfer execution from loop1 to loop2, when loop1 enters into
    1504                 :            :      invariant state.  */
    1505                 :        449 :   basic_block latch_bb = split_edge (loop_latch_edge (loop1));
    1506                 :        449 :   basic_block break_bb = split_edge (single_pred_edge (latch_bb));
    1507                 :        449 :   gimple *break_cond = gimple_build_cond (gimple_cond_code(cond),
    1508                 :            :                                           gimple_cond_lhs (cond),
    1509                 :            :                                           gimple_cond_rhs (cond),
    1510                 :            :                                           NULL_TREE, NULL_TREE);
    1511                 :            : 
    1512                 :        449 :   gimple_stmt_iterator gsi = gsi_last_bb (break_bb);
    1513                 :        449 :   gsi_insert_after (&gsi, break_cond, GSI_NEW_STMT);
    1514                 :            : 
    1515                 :        449 :   edge to_loop1 = single_succ_edge (break_bb);
    1516                 :        449 :   edge to_loop2 = make_edge (break_bb, loop_preheader_edge (loop2)->src, 0);
    1517                 :            : 
    1518                 :        449 :   to_loop1->flags &= ~EDGE_FALLTHRU;
    1519                 :        449 :   to_loop1->flags |= true_invar ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
    1520                 :        449 :   to_loop2->flags |= true_invar ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE;
    1521                 :            : 
    1522                 :        449 :   update_ssa (TODO_update_ssa);
    1523                 :            : 
    1524                 :            :   /* Due to introduction of a control flow edge from loop1 latch to loop2
    1525                 :            :      pre-header, we should update PHIs in loop2 to reflect this connection
    1526                 :            :      between loop1 and loop2.  */
    1527                 :        449 :   connect_loop_phis (loop1, loop2, to_loop2);
    1528                 :            : 
    1529                 :        449 :   free_original_copy_tables ();
    1530                 :            : 
    1531                 :        449 :   rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop1);
    1532                 :            : 
    1533                 :        449 :   return true;
    1534                 :            : }
    1535                 :            : 
    1536                 :            : /* Traverse all conditional statements in LOOP, to find out a good candidate
    1537                 :            :    upon which we can do loop split.  */
    1538                 :            : 
    1539                 :            : static bool
    1540                 :      44806 : split_loop_on_cond (struct loop *loop)
    1541                 :            : {
    1542                 :      44806 :   split_info *info = new split_info ();
    1543                 :      44806 :   basic_block *bbs = info->bbs = get_loop_body (loop);
    1544                 :      44806 :   bool do_split = false;
    1545                 :            : 
    1546                 :            :   /* Allocate an area to keep temporary info, and associate its address
    1547                 :            :      with loop aux field.  */
    1548                 :      44806 :   loop->aux = info;
    1549                 :            : 
    1550                 :     313894 :   for (unsigned i = 0; i < loop->num_nodes; i++)
    1551                 :     269088 :     bbs[i]->aux = NULL;
    1552                 :            : 
    1553                 :     310566 :   for (unsigned i = 0; i < loop->num_nodes; i++)
    1554                 :            :     {
    1555                 :     266209 :       basic_block bb = bbs[i];
    1556                 :            : 
    1557                 :            :       /* We only consider conditional statement, which be executed at most once
    1558                 :            :          in each iteration of the loop.  So skip statements in inner loops.  */
    1559                 :     266209 :       if ((bb->loop_father != loop) || (bb->flags & BB_IRREDUCIBLE_LOOP))
    1560                 :      80098 :         continue;
    1561                 :            : 
    1562                 :            :       /* Actually this check is not a must constraint.  With it, we can ensure
    1563                 :            :          conditional statement will always be executed in each iteration.  */
    1564                 :     186111 :       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    1565                 :      60536 :         continue;
    1566                 :            : 
    1567                 :     125575 :       gimple *last = last_stmt (bb);
    1568                 :            : 
    1569                 :     125575 :       if (!last || gimple_code (last) != GIMPLE_COND)
    1570                 :      49933 :         continue;
    1571                 :            : 
    1572                 :      75642 :       gcond *cond = as_a <gcond *> (last);
    1573                 :      75642 :       edge branch_edge = get_cond_branch_to_split_loop (loop, cond);
    1574                 :            : 
    1575                 :      75642 :       if (branch_edge)
    1576                 :            :         {
    1577                 :        449 :           do_split_loop_on_cond (loop, branch_edge);
    1578                 :        449 :           do_split = true;
    1579                 :        449 :           break;
    1580                 :            :         }
    1581                 :            :     }
    1582                 :            : 
    1583                 :      44806 :   delete info;
    1584                 :      44806 :   loop->aux = NULL;
    1585                 :            : 
    1586                 :      44806 :   return do_split;
    1587                 :            : }
    1588                 :            : 
    1589                 :            : /* Main entry point.  Perform loop splitting on all suitable loops.  */
    1590                 :            : 
    1591                 :            : static unsigned int
    1592                 :      17664 : tree_ssa_split_loops (void)
    1593                 :            : {
    1594                 :      17664 :   class loop *loop;
    1595                 :      17664 :   bool changed = false;
    1596                 :            : 
    1597                 :      17664 :   gcc_assert (scev_initialized_p ());
    1598                 :            : 
    1599                 :      17664 :   calculate_dominance_info (CDI_POST_DOMINATORS);
    1600                 :            : 
    1601                 :      81250 :   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
    1602                 :      63586 :     loop->aux = NULL;
    1603                 :            : 
    1604                 :            :   /* Go through all loops starting from innermost.  */
    1605                 :      63586 :   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
    1606                 :            :     {
    1607                 :      45922 :       if (loop->aux)
    1608                 :            :         {
    1609                 :            :           /* If any of our inner loops was split, don't split us,
    1610                 :            :              and mark our containing loop as having had splits as well.  */
    1611                 :        166 :           loop_outer (loop)->aux = loop;
    1612                 :        166 :           continue;
    1613                 :            :         }
    1614                 :            : 
    1615                 :      45756 :       if (optimize_loop_for_size_p (loop))
    1616                 :        898 :         continue;
    1617                 :            : 
    1618                 :      44858 :       if (split_loop (loop) || split_loop_on_cond (loop))
    1619                 :            :         {
    1620                 :            :           /* Mark our containing loop as having had some split inner loops.  */
    1621                 :        501 :           loop_outer (loop)->aux = loop;
    1622                 :        501 :           changed = true;
    1623                 :            :         }
    1624                 :            :     }
    1625                 :            : 
    1626                 :      82044 :   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
    1627                 :      64380 :     loop->aux = NULL;
    1628                 :            : 
    1629                 :      17664 :   clear_aux_for_blocks ();
    1630                 :            : 
    1631                 :      17664 :   free_dominance_info (CDI_POST_DOMINATORS);
    1632                 :            : 
    1633                 :      17664 :   if (changed)
    1634                 :        360 :     return TODO_cleanup_cfg;
    1635                 :            :   return 0;
    1636                 :            : }
    1637                 :            : 
    1638                 :            : /* Loop splitting pass.  */
    1639                 :            : 
    1640                 :            : namespace {
    1641                 :            : 
    1642                 :            : const pass_data pass_data_loop_split =
    1643                 :            : {
    1644                 :            :   GIMPLE_PASS, /* type */
    1645                 :            :   "lsplit", /* name */
    1646                 :            :   OPTGROUP_LOOP, /* optinfo_flags */
    1647                 :            :   TV_LOOP_SPLIT, /* tv_id */
    1648                 :            :   PROP_cfg, /* properties_required */
    1649                 :            :   0, /* properties_provided */
    1650                 :            :   0, /* properties_destroyed */
    1651                 :            :   0, /* todo_flags_start */
    1652                 :            :   0, /* todo_flags_finish */
    1653                 :            : };
    1654                 :            : 
    1655                 :            : class pass_loop_split : public gimple_opt_pass
    1656                 :            : {
    1657                 :            : public:
    1658                 :     200540 :   pass_loop_split (gcc::context *ctxt)
    1659                 :     401080 :     : gimple_opt_pass (pass_data_loop_split, ctxt)
    1660                 :            :   {}
    1661                 :            : 
    1662                 :            :   /* opt_pass methods: */
    1663                 :     157439 :   virtual bool gate (function *) { return flag_split_loops != 0; }
    1664                 :            :   virtual unsigned int execute (function *);
    1665                 :            : 
    1666                 :            : }; // class pass_loop_split
    1667                 :            : 
    1668                 :            : unsigned int
    1669                 :      17664 : pass_loop_split::execute (function *fun)
    1670                 :            : {
    1671                 :      35328 :   if (number_of_loops (fun) <= 1)
    1672                 :            :     return 0;
    1673                 :            : 
    1674                 :      17664 :   return tree_ssa_split_loops ();
    1675                 :            : }
    1676                 :            : 
    1677                 :            : } // anon namespace
    1678                 :            : 
    1679                 :            : gimple_opt_pass *
    1680                 :     200540 : make_pass_loop_split (gcc::context *ctxt)
    1681                 :            : {
    1682                 :     200540 :   return new pass_loop_split (ctxt);
    1683                 :            : }

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.