LCOV - code coverage report
Current view: top level - gcc - cfgloopmanip.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 765 791 96.7 %
Date: 2020-03-28 11:57:23 Functions: 29 31 93.5 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Loop manipulation code for GNU compiler.
       2                 :            :    Copyright (C) 2002-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 under
       7                 :            : the terms of the GNU General Public License as published by the Free
       8                 :            : Software Foundation; either version 3, or (at your option) any later
       9                 :            : version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : 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 "rtl.h"
      25                 :            : #include "tree.h"
      26                 :            : #include "gimple.h"
      27                 :            : #include "cfghooks.h"
      28                 :            : #include "cfganal.h"
      29                 :            : #include "cfgloop.h"
      30                 :            : #include "gimple-iterator.h"
      31                 :            : #include "gimplify-me.h"
      32                 :            : #include "tree-ssa-loop-manip.h"
      33                 :            : #include "dumpfile.h"
      34                 :            : 
      35                 :            : static void copy_loops_to (class loop **, int,
      36                 :            :                            class loop *);
      37                 :            : static void loop_redirect_edge (edge, basic_block);
      38                 :            : static void remove_bbs (basic_block *, int);
      39                 :            : static bool rpe_enum_p (const_basic_block, const void *);
      40                 :            : static int find_path (edge, basic_block **);
      41                 :            : static void fix_loop_placements (class loop *, bool *);
      42                 :            : static bool fix_bb_placement (basic_block);
      43                 :            : static void fix_bb_placements (basic_block, bool *, bitmap);
      44                 :            : 
      45                 :            : /* Checks whether basic block BB is dominated by DATA.  */
      46                 :            : static bool
      47                 :     238693 : rpe_enum_p (const_basic_block bb, const void *data)
      48                 :            : {
      49                 :     238693 :   return dominated_by_p (CDI_DOMINATORS, bb, (const_basic_block) data);
      50                 :            : }
      51                 :            : 
      52                 :            : /* Remove basic blocks BBS.  NBBS is the number of the basic blocks.  */
      53                 :            : 
      54                 :            : static void
      55                 :     238691 : remove_bbs (basic_block *bbs, int nbbs)
      56                 :            : {
      57                 :     238691 :   int i;
      58                 :            : 
      59                 :     477386 :   for (i = 0; i < nbbs; i++)
      60                 :     238695 :     delete_basic_block (bbs[i]);
      61                 :          0 : }
      62                 :            : 
      63                 :            : /* Find path -- i.e. the basic blocks dominated by edge E and put them
      64                 :            :    into array BBS, that will be allocated large enough to contain them.
      65                 :            :    E->dest must have exactly one predecessor for this to work (it is
      66                 :            :    easy to achieve and we do not put it here because we do not want to
      67                 :            :    alter anything by this function).  The number of basic blocks in the
      68                 :            :    path is returned.  */
      69                 :            : static int
      70                 :     238691 : find_path (edge e, basic_block **bbs)
      71                 :            : {
      72                 :     238691 :   gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
      73                 :            : 
      74                 :            :   /* Find bbs in the path.  */
      75                 :     238691 :   *bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
      76                 :     238691 :   return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
      77                 :     238691 :                              n_basic_blocks_for_fn (cfun), e->dest);
      78                 :            : }
      79                 :            : 
      80                 :            : /* Fix placement of basic block BB inside loop hierarchy --
      81                 :            :    Let L be a loop to that BB belongs.  Then every successor of BB must either
      82                 :            :      1) belong to some superloop of loop L, or
      83                 :            :      2) be a header of loop K such that K->outer is superloop of L
      84                 :            :    Returns true if we had to move BB into other loop to enforce this condition,
      85                 :            :    false if the placement of BB was already correct (provided that placements
      86                 :            :    of its successors are correct).  */
      87                 :            : static bool
      88                 :     135580 : fix_bb_placement (basic_block bb)
      89                 :            : {
      90                 :     135580 :   edge e;
      91                 :     135580 :   edge_iterator ei;
      92                 :     135580 :   class loop *loop = current_loops->tree_root, *act;
      93                 :            : 
      94                 :     276519 :   FOR_EACH_EDGE (e, ei, bb->succs)
      95                 :            :     {
      96                 :     140939 :       if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
      97                 :          0 :         continue;
      98                 :            : 
      99                 :     140939 :       act = e->dest->loop_father;
     100                 :     140939 :       if (act->header == e->dest)
     101                 :         40 :         act = loop_outer (act);
     102                 :            : 
     103                 :     140939 :       if (flow_loop_nested_p (loop, act))
     104                 :     108825 :         loop = act;
     105                 :            :     }
     106                 :            : 
     107                 :     135580 :   if (loop == bb->loop_father)
     108                 :            :     return false;
     109                 :            : 
     110                 :      26820 :   remove_bb_from_loops (bb);
     111                 :      26820 :   add_bb_to_loop (bb, loop);
     112                 :            : 
     113                 :      26820 :   return true;
     114                 :            : }
     115                 :            : 
     116                 :            : /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
     117                 :            :    of LOOP to that leads at least one exit edge of LOOP, and set it
     118                 :            :    as the immediate superloop of LOOP.  Return true if the immediate superloop
     119                 :            :    of LOOP changed.
     120                 :            : 
     121                 :            :    IRRED_INVALIDATED is set to true if a change in the loop structures might
     122                 :            :    invalidate the information about irreducible regions.  */
     123                 :            : 
     124                 :            : static bool
     125                 :      95754 : fix_loop_placement (class loop *loop, bool *irred_invalidated)
     126                 :            : {
     127                 :      95754 :   unsigned i;
     128                 :      95754 :   edge e;
     129                 :      95754 :   vec<edge> exits = get_loop_exit_edges (loop);
     130                 :      95754 :   class loop *father = current_loops->tree_root, *act;
     131                 :      95754 :   bool ret = false;
     132                 :            : 
     133                 :     665974 :   FOR_EACH_VEC_ELT (exits, i, e)
     134                 :            :     {
     135                 :     570220 :       act = find_common_loop (loop, e->dest->loop_father);
     136                 :     570220 :       if (flow_loop_nested_p (father, act))
     137                 :      30913 :         father = act;
     138                 :            :     }
     139                 :            : 
     140                 :     191508 :   if (father != loop_outer (loop))
     141                 :            :     {
     142                 :        137 :       for (act = loop_outer (loop); act != father; act = loop_outer (act))
     143                 :         57 :         act->num_nodes -= loop->num_nodes;
     144                 :         40 :       flow_loop_tree_node_remove (loop);
     145                 :         40 :       flow_loop_tree_node_add (father, loop);
     146                 :            : 
     147                 :            :       /* The exit edges of LOOP no longer exits its original immediate
     148                 :            :          superloops; remove them from the appropriate exit lists.  */
     149                 :         87 :       FOR_EACH_VEC_ELT (exits, i, e)
     150                 :            :         {
     151                 :            :           /* We may need to recompute irreducible loops.  */
     152                 :         47 :           if (e->flags & EDGE_IRREDUCIBLE_LOOP)
     153                 :          0 :             *irred_invalidated = true;
     154                 :         47 :           rescan_loop_exit (e, false, false);
     155                 :            :         }
     156                 :            : 
     157                 :            :       ret = true;
     158                 :            :     }
     159                 :            : 
     160                 :      95754 :   exits.release ();
     161                 :      95754 :   return ret;
     162                 :            : }
     163                 :            : 
     164                 :            : /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
     165                 :            :    enforce condition stated in description of fix_bb_placement. We
     166                 :            :    start from basic block FROM that had some of its successors removed, so that
     167                 :            :    his placement no longer has to be correct, and iteratively fix placement of
     168                 :            :    its predecessors that may change if placement of FROM changed.  Also fix
     169                 :            :    placement of subloops of FROM->loop_father, that might also be altered due
     170                 :            :    to this change; the condition for them is similar, except that instead of
     171                 :            :    successors we consider edges coming out of the loops.
     172                 :            : 
     173                 :            :    If the changes may invalidate the information about irreducible regions,
     174                 :            :    IRRED_INVALIDATED is set to true.  
     175                 :            : 
     176                 :            :    If LOOP_CLOSED_SSA_INVLIDATED is non-zero then all basic blocks with
     177                 :            :    changed loop_father are collected there. */
     178                 :            : 
     179                 :            : static void
     180                 :     310094 : fix_bb_placements (basic_block from,
     181                 :            :                    bool *irred_invalidated,
     182                 :            :                    bitmap loop_closed_ssa_invalidated)
     183                 :            : {
     184                 :     310094 :   basic_block *queue, *qtop, *qbeg, *qend;
     185                 :     310094 :   class loop *base_loop, *target_loop;
     186                 :     310094 :   edge e;
     187                 :            : 
     188                 :            :   /* We pass through blocks back-reachable from FROM, testing whether some
     189                 :            :      of their successors moved to outer loop.  It may be necessary to
     190                 :            :      iterate several times, but it is finite, as we stop unless we move
     191                 :            :      the basic block up the loop structure.  The whole story is a bit
     192                 :            :      more complicated due to presence of subloops, those are moved using
     193                 :            :      fix_loop_placement.  */
     194                 :            : 
     195                 :     310094 :   base_loop = from->loop_father;
     196                 :            :   /* If we are already in the outermost loop, the basic blocks cannot be moved
     197                 :            :      outside of it.  If FROM is the header of the base loop, it cannot be moved
     198                 :            :      outside of it, either.  In both cases, we can end now.  */
     199                 :     310094 :   if (base_loop == current_loops->tree_root
     200                 :     114416 :       || from == base_loop->header)
     201                 :     202581 :     return;
     202                 :            : 
     203                 :     215026 :   auto_sbitmap in_queue (last_basic_block_for_fn (cfun));
     204                 :     107513 :   bitmap_clear (in_queue);
     205                 :     107513 :   bitmap_set_bit (in_queue, from->index);
     206                 :            :   /* Prevent us from going out of the base_loop.  */
     207                 :     107513 :   bitmap_set_bit (in_queue, base_loop->header->index);
     208                 :            : 
     209                 :     107513 :   queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);
     210                 :     107513 :   qtop = queue + base_loop->num_nodes + 1;
     211                 :     107513 :   qbeg = queue;
     212                 :     107513 :   qend = queue + 1;
     213                 :     107513 :   *qbeg = from;
     214                 :            : 
     215                 :     243179 :   while (qbeg != qend)
     216                 :            :     {
     217                 :     135666 :       edge_iterator ei;
     218                 :     135666 :       from = *qbeg;
     219                 :     135666 :       qbeg++;
     220                 :     135666 :       if (qbeg == qtop)
     221                 :          0 :         qbeg = queue;
     222                 :     135666 :       bitmap_clear_bit (in_queue, from->index);
     223                 :            : 
     224                 :     135666 :       if (from->loop_father->header == from)
     225                 :            :         {
     226                 :            :           /* Subloop header, maybe move the loop upward.  */
     227                 :         86 :           if (!fix_loop_placement (from->loop_father, irred_invalidated))
     228                 :     108806 :             continue;
     229                 :         40 :           target_loop = loop_outer (from->loop_father);
     230                 :         40 :           if (loop_closed_ssa_invalidated)
     231                 :            :             {
     232                 :          6 :               basic_block *bbs = get_loop_body (from->loop_father);
     233                 :         21 :               for (unsigned i = 0; i < from->loop_father->num_nodes; ++i)
     234                 :         15 :                 bitmap_set_bit (loop_closed_ssa_invalidated, bbs[i]->index);
     235                 :          6 :               free (bbs);
     236                 :            :             }
     237                 :            :         }
     238                 :            :       else
     239                 :            :         {
     240                 :            :           /* Ordinary basic block.  */
     241                 :     135580 :           if (!fix_bb_placement (from))
     242                 :     108760 :             continue;
     243                 :      26820 :           target_loop = from->loop_father;
     244                 :      26820 :           if (loop_closed_ssa_invalidated)
     245                 :       9724 :             bitmap_set_bit (loop_closed_ssa_invalidated, from->index);
     246                 :            :         }
     247                 :            : 
     248                 :      39123 :       FOR_EACH_EDGE (e, ei, from->succs)
     249                 :            :         {
     250                 :      12263 :           if (e->flags & EDGE_IRREDUCIBLE_LOOP)
     251                 :          1 :             *irred_invalidated = true;
     252                 :            :         }
     253                 :            : 
     254                 :            :       /* Something has changed, insert predecessors into queue.  */
     255                 :      55367 :       FOR_EACH_EDGE (e, ei, from->preds)
     256                 :            :         {
     257                 :      28507 :           basic_block pred = e->src;
     258                 :      28507 :           class loop *nca;
     259                 :            : 
     260                 :      28507 :           if (e->flags & EDGE_IRREDUCIBLE_LOOP)
     261                 :          0 :             *irred_invalidated = true;
     262                 :            : 
     263                 :      28507 :           if (bitmap_bit_p (in_queue, pred->index))
     264                 :        354 :             continue;
     265                 :            : 
     266                 :            :           /* If it is subloop, then it either was not moved, or
     267                 :            :              the path up the loop tree from base_loop do not contain
     268                 :            :              it.  */
     269                 :      28153 :           nca = find_common_loop (pred->loop_father, base_loop);
     270                 :      28153 :           if (pred->loop_father != base_loop
     271                 :         86 :               && (nca == base_loop
     272                 :         40 :                   || nca != pred->loop_father))
     273                 :         86 :             pred = pred->loop_father->header;
     274                 :      28067 :           else if (!flow_loop_nested_p (target_loop, pred->loop_father))
     275                 :            :             {
     276                 :            :               /* If PRED is already higher in the loop hierarchy than the
     277                 :            :                  TARGET_LOOP to that we moved FROM, the change of the position
     278                 :            :                  of FROM does not affect the position of PRED, so there is no
     279                 :            :                  point in processing it.  */
     280                 :          0 :               continue;
     281                 :            :             }
     282                 :            : 
     283                 :      28153 :           if (bitmap_bit_p (in_queue, pred->index))
     284                 :          0 :             continue;
     285                 :            : 
     286                 :            :           /* Schedule the basic block.  */
     287                 :      28153 :           *qend = pred;
     288                 :      28153 :           qend++;
     289                 :      28153 :           if (qend == qtop)
     290                 :          0 :             qend = queue;
     291                 :      56660 :           bitmap_set_bit (in_queue, pred->index);
     292                 :            :         }
     293                 :            :     }
     294                 :     107513 :   free (queue);
     295                 :            : }
     296                 :            : 
     297                 :            : /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
     298                 :            :    and update loop structures and dominators.  Return true if we were able
     299                 :            :    to remove the path, false otherwise (and nothing is affected then).  */
     300                 :            : bool
     301                 :     238691 : remove_path (edge e, bool *irred_invalidated,
     302                 :            :              bitmap loop_closed_ssa_invalidated)
     303                 :            : {
     304                 :     238691 :   edge ae;
     305                 :     238691 :   basic_block *rem_bbs, *bord_bbs, from, bb;
     306                 :     238691 :   vec<basic_block> dom_bbs;
     307                 :     238691 :   int i, nrem, n_bord_bbs;
     308                 :     238691 :   bool local_irred_invalidated = false;
     309                 :     238691 :   edge_iterator ei;
     310                 :     238691 :   class loop *l, *f;
     311                 :            : 
     312                 :     238691 :   if (! irred_invalidated)
     313                 :      68660 :     irred_invalidated = &local_irred_invalidated;
     314                 :            : 
     315                 :     238691 :   if (!can_remove_branch_p (e))
     316                 :            :     return false;
     317                 :            : 
     318                 :            :   /* Keep track of whether we need to update information about irreducible
     319                 :            :      regions.  This is the case if the removed area is a part of the
     320                 :            :      irreducible region, or if the set of basic blocks that belong to a loop
     321                 :            :      that is inside an irreducible region is changed, or if such a loop is
     322                 :            :      removed.  */
     323                 :     238691 :   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
     324                 :         38 :     *irred_invalidated = true;
     325                 :            : 
     326                 :            :   /* We need to check whether basic blocks are dominated by the edge
     327                 :            :      e, but we only have basic block dominators.  This is easy to
     328                 :            :      fix -- when e->dest has exactly one predecessor, this corresponds
     329                 :            :      to blocks dominated by e->dest, if not, split the edge.  */
     330                 :     238691 :   if (!single_pred_p (e->dest))
     331                 :     238688 :     e = single_pred_edge (split_edge (e));
     332                 :            : 
     333                 :            :   /* It may happen that by removing path we remove one or more loops
     334                 :            :      we belong to.  In this case first unloop the loops, then proceed
     335                 :            :      normally.   We may assume that e->dest is not a header of any loop,
     336                 :            :      as it now has exactly one predecessor.  */
     337                 :     541229 :   for (l = e->src->loop_father; loop_outer (l); l = f)
     338                 :            :     {
     339                 :     151269 :       f = loop_outer (l);
     340                 :     151269 :       if (dominated_by_p (CDI_DOMINATORS, l->latch, e->dest))
     341                 :          0 :         unloop (l, irred_invalidated, loop_closed_ssa_invalidated);
     342                 :            :     }
     343                 :            : 
     344                 :            :   /* Identify the path.  */
     345                 :     238691 :   nrem = find_path (e, &rem_bbs);
     346                 :            : 
     347                 :     238691 :   n_bord_bbs = 0;
     348                 :     238691 :   bord_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
     349                 :     238691 :   auto_sbitmap seen (last_basic_block_for_fn (cfun));
     350                 :     238691 :   bitmap_clear (seen);
     351                 :            : 
     352                 :            :   /* Find "border" hexes -- i.e. those with predecessor in removed path.  */
     353                 :     477386 :   for (i = 0; i < nrem; i++)
     354                 :     238695 :     bitmap_set_bit (seen, rem_bbs[i]->index);
     355                 :     238691 :   if (!*irred_invalidated)
     356                 :     715886 :     FOR_EACH_EDGE (ae, ei, e->src->succs)
     357                 :     238635 :       if (ae != e && ae->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     358                 :     238635 :           && !bitmap_bit_p (seen, ae->dest->index)
     359                 :     715899 :           && ae->flags & EDGE_IRREDUCIBLE_LOOP)
     360                 :            :         {
     361                 :         13 :           *irred_invalidated = true;
     362                 :         13 :           break;
     363                 :            :         }
     364                 :            : 
     365                 :     477386 :   for (i = 0; i < nrem; i++)
     366                 :            :     {
     367                 :     477390 :       FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
     368                 :     238695 :         if (ae->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     369                 :     238695 :             && !bitmap_bit_p (seen, ae->dest->index))
     370                 :            :           {
     371                 :     238689 :             bitmap_set_bit (seen, ae->dest->index);
     372                 :     238689 :             bord_bbs[n_bord_bbs++] = ae->dest;
     373                 :            : 
     374                 :     238689 :             if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
     375                 :         38 :               *irred_invalidated = true;
     376                 :            :           }
     377                 :            :     }
     378                 :            : 
     379                 :            :   /* Remove the path.  */
     380                 :     238691 :   from = e->src;
     381                 :     238691 :   remove_branch (e);
     382                 :     238691 :   dom_bbs.create (0);
     383                 :            : 
     384                 :            :   /* Cancel loops contained in the path.  */
     385                 :     477386 :   for (i = 0; i < nrem; i++)
     386                 :     238695 :     if (rem_bbs[i]->loop_father->header == rem_bbs[i])
     387                 :          2 :       cancel_loop_tree (rem_bbs[i]->loop_father);
     388                 :            : 
     389                 :     238691 :   remove_bbs (rem_bbs, nrem);
     390                 :     238691 :   free (rem_bbs);
     391                 :            : 
     392                 :            :   /* Find blocks whose dominators may be affected.  */
     393                 :     238691 :   bitmap_clear (seen);
     394                 :     477380 :   for (i = 0; i < n_bord_bbs; i++)
     395                 :            :     {
     396                 :     238689 :       basic_block ldom;
     397                 :            : 
     398                 :     238689 :       bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
     399                 :     238689 :       if (bitmap_bit_p (seen, bb->index))
     400                 :          0 :         continue;
     401                 :     238689 :       bitmap_set_bit (seen, bb->index);
     402                 :            : 
     403                 :     238689 :       for (ldom = first_dom_son (CDI_DOMINATORS, bb);
     404                 :     773696 :            ldom;
     405                 :     535007 :            ldom = next_dom_son (CDI_DOMINATORS, ldom))
     406                 :     535007 :         if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
     407                 :     453318 :           dom_bbs.safe_push (ldom);
     408                 :            :     }
     409                 :            : 
     410                 :            :   /* Recount dominators.  */
     411                 :     238691 :   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, true);
     412                 :     238691 :   dom_bbs.release ();
     413                 :     238691 :   free (bord_bbs);
     414                 :            : 
     415                 :            :   /* Fix placements of basic blocks inside loops and the placement of
     416                 :            :      loops in the loop tree.  */
     417                 :     238691 :   fix_bb_placements (from, irred_invalidated, loop_closed_ssa_invalidated);
     418                 :     238691 :   fix_loop_placements (from->loop_father, irred_invalidated);
     419                 :            : 
     420                 :     238691 :   if (local_irred_invalidated
     421                 :     238691 :       && loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
     422                 :         30 :     mark_irreducible_loops ();
     423                 :            : 
     424                 :     238691 :   return true;
     425                 :            : }
     426                 :            : 
     427                 :            : /* Creates place for a new LOOP in loops structure of FN.  */
     428                 :            : 
     429                 :            : void
     430                 :     252445 : place_new_loop (struct function *fn, class loop *loop)
     431                 :            : {
     432                 :     252445 :   loop->num = number_of_loops (fn);
     433                 :     252445 :   vec_safe_push (loops_for_fn (fn)->larray, loop);
     434                 :     252445 : }
     435                 :            : 
     436                 :            : /* Given LOOP structure with filled header and latch, find the body of the
     437                 :            :    corresponding loop and add it to loops tree.  Insert the LOOP as a son of
     438                 :            :    outer.  */
     439                 :            : 
     440                 :            : void
     441                 :      58441 : add_loop (class loop *loop, class loop *outer)
     442                 :            : {
     443                 :      58441 :   basic_block *bbs;
     444                 :      58441 :   int i, n;
     445                 :      58441 :   class loop *subloop;
     446                 :      58441 :   edge e;
     447                 :      58441 :   edge_iterator ei;
     448                 :            : 
     449                 :            :   /* Add it to loop structure.  */
     450                 :      58441 :   place_new_loop (cfun, loop);
     451                 :      58441 :   flow_loop_tree_node_add (outer, loop);
     452                 :            : 
     453                 :            :   /* Find its nodes.  */
     454                 :      58441 :   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
     455                 :      58441 :   n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
     456                 :            : 
     457                 :     456763 :   for (i = 0; i < n; i++)
     458                 :            :     {
     459                 :     398322 :       if (bbs[i]->loop_father == outer)
     460                 :            :         {
     461                 :     263616 :           remove_bb_from_loops (bbs[i]);
     462                 :     263616 :           add_bb_to_loop (bbs[i], loop);
     463                 :     263616 :           continue;
     464                 :            :         }
     465                 :            : 
     466                 :     134706 :       loop->num_nodes++;
     467                 :            : 
     468                 :            :       /* If we find a direct subloop of OUTER, move it to LOOP.  */
     469                 :     134706 :       subloop = bbs[i]->loop_father;
     470                 :     134706 :       if (loop_outer (subloop) == outer
     471                 :     134706 :           && subloop->header == bbs[i])
     472                 :            :         {
     473                 :      16061 :           flow_loop_tree_node_remove (subloop);
     474                 :      16061 :           flow_loop_tree_node_add (loop, subloop);
     475                 :            :         }
     476                 :            :     }
     477                 :            : 
     478                 :            :   /* Update the information about loop exit edges.  */
     479                 :     456763 :   for (i = 0; i < n; i++)
     480                 :            :     {
     481                 :     974987 :       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
     482                 :            :         {
     483                 :     576665 :           rescan_loop_exit (e, false, false);
     484                 :            :         }
     485                 :            :     }
     486                 :            : 
     487                 :      58441 :   free (bbs);
     488                 :      58441 : }
     489                 :            : 
     490                 :            : /* Scale profile of loop by P.  */
     491                 :            : 
     492                 :            : void
     493                 :      58881 : scale_loop_frequencies (class loop *loop, profile_probability p)
     494                 :            : {
     495                 :      58881 :   basic_block *bbs;
     496                 :            : 
     497                 :      58881 :   bbs = get_loop_body (loop);
     498                 :      58881 :   scale_bbs_frequencies (bbs, loop->num_nodes, p);
     499                 :      58881 :   free (bbs);
     500                 :      58881 : }
     501                 :            : 
     502                 :            : /* Scale profile in LOOP by P.
     503                 :            :    If ITERATION_BOUND is non-zero, scale even further if loop is predicted
     504                 :            :    to iterate too many times.
     505                 :            :    Before caling this function, preheader block profile should be already
     506                 :            :    scaled to final count.  This is necessary because loop iterations are
     507                 :            :    determined by comparing header edge count to latch ege count and thus
     508                 :            :    they need to be scaled synchronously.  */
     509                 :            : 
     510                 :            : void
     511                 :      18715 : scale_loop_profile (class loop *loop, profile_probability p,
     512                 :            :                     gcov_type iteration_bound)
     513                 :            : {
     514                 :      18715 :   edge e, preheader_e;
     515                 :      18715 :   edge_iterator ei;
     516                 :            : 
     517                 :      18715 :   if (dump_file && (dump_flags & TDF_DETAILS))
     518                 :            :     {
     519                 :       2785 :       fprintf (dump_file, ";; Scaling loop %i with scale ",
     520                 :            :                loop->num);
     521                 :       2785 :       p.dump (dump_file);
     522                 :       2785 :       fprintf (dump_file, " bounding iterations to %i\n",
     523                 :            :                (int)iteration_bound);
     524                 :            :     }
     525                 :            : 
     526                 :            :   /* Scale the probabilities.  */
     527                 :      18715 :   scale_loop_frequencies (loop, p);
     528                 :            : 
     529                 :      18715 :   if (iteration_bound == 0)
     530                 :      18534 :     return;
     531                 :            : 
     532                 :        193 :   gcov_type iterations = expected_loop_iterations_unbounded (loop, NULL, true);
     533                 :            : 
     534                 :        193 :   if (dump_file && (dump_flags & TDF_DETAILS))
     535                 :            :     {
     536                 :        178 :       fprintf (dump_file, ";; guessed iterations after scaling %i\n",
     537                 :            :                (int)iterations);
     538                 :            :     }
     539                 :            : 
     540                 :            :   /* See if loop is predicted to iterate too many times.  */
     541                 :        193 :   if (iterations <= iteration_bound)
     542                 :            :     return;
     543                 :            : 
     544                 :        181 :   preheader_e = loop_preheader_edge (loop);
     545                 :            : 
     546                 :            :   /* We could handle also loops without preheaders, but bounding is
     547                 :            :      currently used only by optimizers that have preheaders constructed.  */
     548                 :        181 :   gcc_checking_assert (preheader_e);
     549                 :        181 :   profile_count count_in = preheader_e->count ();
     550                 :            : 
     551                 :        181 :   if (count_in > profile_count::zero ()
     552                 :        181 :       && loop->header->count.initialized_p ())
     553                 :            :     {
     554                 :        181 :       profile_count count_delta = profile_count::zero ();
     555                 :            : 
     556                 :        181 :       e = single_exit (loop);
     557                 :        181 :       if (e)
     558                 :            :         {
     559                 :        181 :           edge other_e;
     560                 :        190 :           FOR_EACH_EDGE (other_e, ei, e->src->succs)
     561                 :        190 :             if (!(other_e->flags & (EDGE_ABNORMAL | EDGE_FAKE))
     562                 :        190 :                 && e != other_e)
     563                 :            :               break;
     564                 :            : 
     565                 :            :           /* Probability of exit must be 1/iterations.  */
     566                 :        181 :           count_delta = e->count ();
     567                 :        181 :           e->probability = profile_probability::always ()
     568                 :        181 :                                     .apply_scale (1, iteration_bound);
     569                 :        181 :           other_e->probability = e->probability.invert ();
     570                 :            : 
     571                 :            :           /* In code below we only handle the following two updates.  */
     572                 :        181 :           if (other_e->dest != loop->header
     573                 :        181 :               && other_e->dest != loop->latch
     574                 :        181 :               && (dump_file && (dump_flags & TDF_DETAILS)))
     575                 :            :             {
     576                 :          0 :               fprintf (dump_file, ";; giving up on update of paths from "
     577                 :            :                        "exit condition to latch\n");
     578                 :            :             }
     579                 :            :         }
     580                 :            :       else
     581                 :          0 :         if (dump_file && (dump_flags & TDF_DETAILS))
     582                 :          0 :           fprintf (dump_file, ";; Loop has multiple exit edges; "
     583                 :            :                               "giving up on exit condition update\n");
     584                 :            : 
     585                 :            :       /* Roughly speaking we want to reduce the loop body profile by the
     586                 :            :          difference of loop iterations.  We however can do better if
     587                 :            :          we look at the actual profile, if it is available.  */
     588                 :        181 :       p = profile_probability::always ();
     589                 :            : 
     590                 :        181 :       count_in = count_in.apply_scale (iteration_bound, 1);
     591                 :        181 :       p = count_in.probability_in (loop->header->count);
     592                 :        181 :       if (!(p > profile_probability::never ()))
     593                 :          0 :         p = profile_probability::very_unlikely ();
     594                 :            : 
     595                 :        181 :       if (p == profile_probability::always ()
     596                 :        181 :           || !p.initialized_p ())
     597                 :          0 :         return;
     598                 :            : 
     599                 :            :       /* If latch exists, change its count, since we changed
     600                 :            :          probability of exit.  Theoretically we should update everything from
     601                 :            :          source of exit edge to latch, but for vectorizer this is enough.  */
     602                 :        181 :       if (loop->latch && loop->latch != e->src)
     603                 :        181 :         loop->latch->count += count_delta;
     604                 :            : 
     605                 :            :       /* Scale the probabilities.  */
     606                 :        181 :       scale_loop_frequencies (loop, p);
     607                 :            : 
     608                 :            :       /* Change latch's count back.  */
     609                 :        181 :       if (loop->latch && loop->latch != e->src)
     610                 :        181 :         loop->latch->count -= count_delta;
     611                 :            : 
     612                 :        181 :       if (dump_file && (dump_flags & TDF_DETAILS))
     613                 :        178 :         fprintf (dump_file, ";; guessed iterations are now %i\n",
     614                 :        178 :                  (int)expected_loop_iterations_unbounded (loop, NULL, true));
     615                 :            :     }
     616                 :            : }
     617                 :            : 
     618                 :            : /* Recompute dominance information for basic blocks outside LOOP.  */
     619                 :            : 
     620                 :            : static void
     621                 :       9212 : update_dominators_in_loop (class loop *loop)
     622                 :            : {
     623                 :       9212 :   vec<basic_block> dom_bbs = vNULL;
     624                 :       9212 :   basic_block *body;
     625                 :       9212 :   unsigned i;
     626                 :            : 
     627                 :       9212 :   auto_sbitmap seen (last_basic_block_for_fn (cfun));
     628                 :       9212 :   bitmap_clear (seen);
     629                 :       9212 :   body = get_loop_body (loop);
     630                 :            : 
     631                 :      50544 :   for (i = 0; i < loop->num_nodes; i++)
     632                 :      41332 :     bitmap_set_bit (seen, body[i]->index);
     633                 :            : 
     634                 :      50544 :   for (i = 0; i < loop->num_nodes; i++)
     635                 :            :     {
     636                 :      41332 :       basic_block ldom;
     637                 :            : 
     638                 :      41332 :       for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
     639                 :      82329 :            ldom;
     640                 :      40997 :            ldom = next_dom_son (CDI_DOMINATORS, ldom))
     641                 :      40997 :         if (!bitmap_bit_p (seen, ldom->index))
     642                 :            :           {
     643                 :       8877 :             bitmap_set_bit (seen, ldom->index);
     644                 :       8877 :             dom_bbs.safe_push (ldom);
     645                 :            :           }
     646                 :            :     }
     647                 :            : 
     648                 :       9212 :   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
     649                 :       9212 :   free (body);
     650                 :       9212 :   dom_bbs.release ();
     651                 :       9212 : }
     652                 :            : 
     653                 :            : /* Creates an if region as shown above. CONDITION is used to create
     654                 :            :    the test for the if.
     655                 :            : 
     656                 :            :    |
     657                 :            :    |     -------------                 -------------
     658                 :            :    |     |  pred_bb  |                 |  pred_bb  |
     659                 :            :    |     -------------                 -------------
     660                 :            :    |           |                             |
     661                 :            :    |           |                             | ENTRY_EDGE
     662                 :            :    |           | ENTRY_EDGE                  V
     663                 :            :    |           |             ====>     -------------
     664                 :            :    |           |                       |  cond_bb  |
     665                 :            :    |           |                       | CONDITION |
     666                 :            :    |           |                       -------------
     667                 :            :    |           V                        /         \
     668                 :            :    |     -------------         e_false /           \ e_true
     669                 :            :    |     |  succ_bb  |                V             V
     670                 :            :    |     -------------         -----------       -----------
     671                 :            :    |                           | false_bb |      | true_bb |
     672                 :            :    |                           -----------       -----------
     673                 :            :    |                                   \           /
     674                 :            :    |                                    \         /
     675                 :            :    |                                     V       V
     676                 :            :    |                                   -------------
     677                 :            :    |                                   |  join_bb  |
     678                 :            :    |                                   -------------
     679                 :            :    |                                         | exit_edge (result)
     680                 :            :    |                                         V
     681                 :            :    |                                    -----------
     682                 :            :    |                                    | succ_bb |
     683                 :            :    |                                    -----------
     684                 :            :    |
     685                 :            :  */
     686                 :            : 
     687                 :            : edge
     688                 :        179 : create_empty_if_region_on_edge (edge entry_edge, tree condition)
     689                 :            : {
     690                 :            : 
     691                 :        179 :   basic_block cond_bb, true_bb, false_bb, join_bb;
     692                 :        179 :   edge e_true, e_false, exit_edge;
     693                 :        179 :   gcond *cond_stmt;
     694                 :        179 :   tree simple_cond;
     695                 :        179 :   gimple_stmt_iterator gsi;
     696                 :            : 
     697                 :        179 :   cond_bb = split_edge (entry_edge);
     698                 :            : 
     699                 :            :   /* Insert condition in cond_bb.  */
     700                 :        179 :   gsi = gsi_last_bb (cond_bb);
     701                 :        179 :   simple_cond =
     702                 :        179 :     force_gimple_operand_gsi (&gsi, condition, true, NULL,
     703                 :            :                               false, GSI_NEW_STMT);
     704                 :        179 :   cond_stmt = gimple_build_cond_from_tree (simple_cond, NULL_TREE, NULL_TREE);
     705                 :        179 :   gsi = gsi_last_bb (cond_bb);
     706                 :        179 :   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
     707                 :            : 
     708                 :        179 :   join_bb = split_edge (single_succ_edge (cond_bb));
     709                 :            : 
     710                 :        179 :   e_true = single_succ_edge (cond_bb);
     711                 :        179 :   true_bb = split_edge (e_true);
     712                 :            : 
     713                 :        179 :   e_false = make_edge (cond_bb, join_bb, 0);
     714                 :        179 :   false_bb = split_edge (e_false);
     715                 :            : 
     716                 :        179 :   e_true->flags &= ~EDGE_FALLTHRU;
     717                 :        179 :   e_true->flags |= EDGE_TRUE_VALUE;
     718                 :        179 :   e_false->flags &= ~EDGE_FALLTHRU;
     719                 :        179 :   e_false->flags |= EDGE_FALSE_VALUE;
     720                 :            : 
     721                 :        179 :   set_immediate_dominator (CDI_DOMINATORS, cond_bb, entry_edge->src);
     722                 :        179 :   set_immediate_dominator (CDI_DOMINATORS, true_bb, cond_bb);
     723                 :        179 :   set_immediate_dominator (CDI_DOMINATORS, false_bb, cond_bb);
     724                 :        179 :   set_immediate_dominator (CDI_DOMINATORS, join_bb, cond_bb);
     725                 :            : 
     726                 :        179 :   exit_edge = single_succ_edge (join_bb);
     727                 :            : 
     728                 :        179 :   if (single_pred_p (exit_edge->dest))
     729                 :        179 :     set_immediate_dominator (CDI_DOMINATORS, exit_edge->dest, join_bb);
     730                 :            : 
     731                 :        179 :   return exit_edge;
     732                 :            : }
     733                 :            : 
     734                 :            : /* create_empty_loop_on_edge
     735                 :            :    |
     736                 :            :    |    - pred_bb -                   ------ pred_bb ------
     737                 :            :    |   |           |                 | iv0 = initial_value |
     738                 :            :    |    -----|-----                   ---------|-----------
     739                 :            :    |         |                       ______    | entry_edge
     740                 :            :    |         | entry_edge           /      |   |
     741                 :            :    |         |             ====>   |      -V---V- loop_header -------------
     742                 :            :    |         V                     |     | iv_before = phi (iv0, iv_after) |
     743                 :            :    |    - succ_bb -                |      ---|-----------------------------
     744                 :            :    |   |           |               |         |
     745                 :            :    |    -----------                |      ---V--- loop_body ---------------
     746                 :            :    |                               |     | iv_after = iv_before + stride   |
     747                 :            :    |                               |     | if (iv_before < upper_bound)    |
     748                 :            :    |                               |      ---|--------------\--------------
     749                 :            :    |                               |         |               \ exit_e
     750                 :            :    |                               |         V                \
     751                 :            :    |                               |       - loop_latch -      V- succ_bb -
     752                 :            :    |                               |      |              |     |           |
     753                 :            :    |                               |       /-------------       -----------
     754                 :            :    |                                \ ___ /
     755                 :            : 
     756                 :            :    Creates an empty loop as shown above, the IV_BEFORE is the SSA_NAME
     757                 :            :    that is used before the increment of IV. IV_BEFORE should be used for
     758                 :            :    adding code to the body that uses the IV.  OUTER is the outer loop in
     759                 :            :    which the new loop should be inserted.
     760                 :            : 
     761                 :            :    Both INITIAL_VALUE and UPPER_BOUND expressions are gimplified and
     762                 :            :    inserted on the loop entry edge.  This implies that this function
     763                 :            :    should be used only when the UPPER_BOUND expression is a loop
     764                 :            :    invariant.  */
     765                 :            : 
     766                 :            : class loop *
     767                 :        425 : create_empty_loop_on_edge (edge entry_edge,
     768                 :            :                            tree initial_value,
     769                 :            :                            tree stride, tree upper_bound,
     770                 :            :                            tree iv,
     771                 :            :                            tree *iv_before,
     772                 :            :                            tree *iv_after,
     773                 :            :                            class loop *outer)
     774                 :            : {
     775                 :        425 :   basic_block loop_header, loop_latch, succ_bb, pred_bb;
     776                 :        425 :   class loop *loop;
     777                 :        425 :   gimple_stmt_iterator gsi;
     778                 :        425 :   gimple_seq stmts;
     779                 :        425 :   gcond *cond_expr;
     780                 :        425 :   tree exit_test;
     781                 :        425 :   edge exit_e;
     782                 :            : 
     783                 :        425 :   gcc_assert (entry_edge && initial_value && stride && upper_bound && iv);
     784                 :            : 
     785                 :            :   /* Create header, latch and wire up the loop.  */
     786                 :        425 :   pred_bb = entry_edge->src;
     787                 :        425 :   loop_header = split_edge (entry_edge);
     788                 :        425 :   loop_latch = split_edge (single_succ_edge (loop_header));
     789                 :        425 :   succ_bb = single_succ (loop_latch);
     790                 :        425 :   make_edge (loop_header, succ_bb, 0);
     791                 :        425 :   redirect_edge_succ_nodup (single_succ_edge (loop_latch), loop_header);
     792                 :            : 
     793                 :            :   /* Set immediate dominator information.  */
     794                 :        425 :   set_immediate_dominator (CDI_DOMINATORS, loop_header, pred_bb);
     795                 :        425 :   set_immediate_dominator (CDI_DOMINATORS, loop_latch, loop_header);
     796                 :        425 :   set_immediate_dominator (CDI_DOMINATORS, succ_bb, loop_header);
     797                 :            : 
     798                 :            :   /* Initialize a loop structure and put it in a loop hierarchy.  */
     799                 :        425 :   loop = alloc_loop ();
     800                 :        425 :   loop->header = loop_header;
     801                 :        425 :   loop->latch = loop_latch;
     802                 :        425 :   add_loop (loop, outer);
     803                 :            : 
     804                 :            :   /* TODO: Fix counts.  */
     805                 :        425 :   scale_loop_frequencies (loop, profile_probability::even ());
     806                 :            : 
     807                 :            :   /* Update dominators.  */
     808                 :        425 :   update_dominators_in_loop (loop);
     809                 :            : 
     810                 :            :   /* Modify edge flags.  */
     811                 :        425 :   exit_e = single_exit (loop);
     812                 :        425 :   exit_e->flags = EDGE_LOOP_EXIT | EDGE_FALSE_VALUE;
     813                 :        425 :   single_pred_edge (loop_latch)->flags = EDGE_TRUE_VALUE;
     814                 :            : 
     815                 :            :   /* Construct IV code in loop.  */
     816                 :        425 :   initial_value = force_gimple_operand (initial_value, &stmts, true, iv);
     817                 :        425 :   if (stmts)
     818                 :            :     {
     819                 :         15 :       gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
     820                 :         15 :       gsi_commit_edge_inserts ();
     821                 :            :     }
     822                 :            : 
     823                 :        425 :   upper_bound = force_gimple_operand (upper_bound, &stmts, true, NULL);
     824                 :        425 :   if (stmts)
     825                 :            :     {
     826                 :        146 :       gsi_insert_seq_on_edge (loop_preheader_edge (loop), stmts);
     827                 :        146 :       gsi_commit_edge_inserts ();
     828                 :            :     }
     829                 :            : 
     830                 :        425 :   gsi = gsi_last_bb (loop_header);
     831                 :        425 :   create_iv (initial_value, stride, iv, loop, &gsi, false,
     832                 :            :              iv_before, iv_after);
     833                 :            : 
     834                 :            :   /* Insert loop exit condition.  */
     835                 :        425 :   cond_expr = gimple_build_cond
     836                 :        425 :     (LT_EXPR, *iv_before, upper_bound, NULL_TREE, NULL_TREE);
     837                 :            : 
     838                 :        425 :   exit_test = gimple_cond_lhs (cond_expr);
     839                 :        425 :   exit_test = force_gimple_operand_gsi (&gsi, exit_test, true, NULL,
     840                 :            :                                         false, GSI_NEW_STMT);
     841                 :        425 :   gimple_cond_set_lhs (cond_expr, exit_test);
     842                 :        425 :   gsi = gsi_last_bb (exit_e->src);
     843                 :        425 :   gsi_insert_after (&gsi, cond_expr, GSI_NEW_STMT);
     844                 :            : 
     845                 :        425 :   split_block_after_labels (loop_header);
     846                 :            : 
     847                 :        425 :   return loop;
     848                 :            : }
     849                 :            : 
     850                 :            : /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
     851                 :            :    latch to header and update loop tree and dominators
     852                 :            :    accordingly. Everything between them plus LATCH_EDGE destination must
     853                 :            :    be dominated by HEADER_EDGE destination, and back-reachable from
     854                 :            :    LATCH_EDGE source.  HEADER_EDGE is redirected to basic block SWITCH_BB,
     855                 :            :    FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
     856                 :            :    TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
     857                 :            :    Returns the newly created loop.  Frequencies and counts in the new loop
     858                 :            :    are scaled by FALSE_SCALE and in the old one by TRUE_SCALE.  */
     859                 :            : 
     860                 :            : class loop *
     861                 :       8787 : loopify (edge latch_edge, edge header_edge,
     862                 :            :          basic_block switch_bb, edge true_edge, edge false_edge,
     863                 :            :          bool redirect_all_edges, profile_probability true_scale,
     864                 :            :          profile_probability false_scale)
     865                 :            : {
     866                 :       8787 :   basic_block succ_bb = latch_edge->dest;
     867                 :       8787 :   basic_block pred_bb = header_edge->src;
     868                 :       8787 :   class loop *loop = alloc_loop ();
     869                 :       8787 :   class loop *outer = loop_outer (succ_bb->loop_father);
     870                 :       8787 :   profile_count cnt;
     871                 :            : 
     872                 :       8787 :   loop->header = header_edge->dest;
     873                 :       8787 :   loop->latch = latch_edge->src;
     874                 :            : 
     875                 :       8787 :   cnt = header_edge->count ();
     876                 :            : 
     877                 :            :   /* Redirect edges.  */
     878                 :      17574 :   loop_redirect_edge (latch_edge, loop->header);
     879                 :      17574 :   loop_redirect_edge (true_edge, succ_bb);
     880                 :            : 
     881                 :            :   /* During loop versioning, one of the switch_bb edge is already properly
     882                 :            :      set. Do not redirect it again unless redirect_all_edges is true.  */
     883                 :       8787 :   if (redirect_all_edges)
     884                 :            :     {
     885                 :          0 :       loop_redirect_edge (header_edge, switch_bb);
     886                 :          0 :       loop_redirect_edge (false_edge, loop->header);
     887                 :            : 
     888                 :            :       /* Update dominators.  */
     889                 :          0 :       set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
     890                 :          0 :       set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
     891                 :            :     }
     892                 :            : 
     893                 :       8787 :   set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
     894                 :            : 
     895                 :            :   /* Compute new loop.  */
     896                 :       8787 :   add_loop (loop, outer);
     897                 :            : 
     898                 :            :   /* Add switch_bb to appropriate loop.  */
     899                 :       8787 :   if (switch_bb->loop_father)
     900                 :       8787 :     remove_bb_from_loops (switch_bb);
     901                 :       8787 :   add_bb_to_loop (switch_bb, outer);
     902                 :            : 
     903                 :            :   /* Fix counts.  */
     904                 :       8787 :   if (redirect_all_edges)
     905                 :            :     {
     906                 :          0 :       switch_bb->count = cnt;
     907                 :            :     }
     908                 :       8787 :   scale_loop_frequencies (loop, false_scale);
     909                 :       8787 :   scale_loop_frequencies (succ_bb->loop_father, true_scale);
     910                 :       8787 :   update_dominators_in_loop (loop);
     911                 :            : 
     912                 :       8787 :   return loop;
     913                 :            : }
     914                 :            : 
     915                 :            : /* Remove the latch edge of a LOOP and update loops to indicate that
     916                 :            :    the LOOP was removed.  After this function, original loop latch will
     917                 :            :    have no successor, which caller is expected to fix somehow.
     918                 :            : 
     919                 :            :    If this may cause the information about irreducible regions to become
     920                 :            :    invalid, IRRED_INVALIDATED is set to true.  
     921                 :            : 
     922                 :            :    LOOP_CLOSED_SSA_INVALIDATED, if non-NULL, is a bitmap where we store
     923                 :            :    basic blocks that had non-trivial update on their loop_father.*/
     924                 :            : 
     925                 :            : void
     926                 :      71403 : unloop (class loop *loop, bool *irred_invalidated,
     927                 :            :         bitmap loop_closed_ssa_invalidated)
     928                 :            : {
     929                 :      71403 :   basic_block *body;
     930                 :      71403 :   class loop *ploop;
     931                 :      71403 :   unsigned i, n;
     932                 :      71403 :   basic_block latch = loop->latch;
     933                 :      71403 :   bool dummy = false;
     934                 :            : 
     935                 :      71403 :   if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
     936                 :         16 :     *irred_invalidated = true;
     937                 :            : 
     938                 :            :   /* This is relatively straightforward.  The dominators are unchanged, as
     939                 :            :      loop header dominates loop latch, so the only thing we have to care of
     940                 :            :      is the placement of loops and basic blocks inside the loop tree.  We
     941                 :            :      move them all to the loop->outer, and then let fix_bb_placements do
     942                 :            :      its work.  */
     943                 :            : 
     944                 :      71403 :   body = get_loop_body (loop);
     945                 :      71403 :   n = loop->num_nodes;
     946                 :     284305 :   for (i = 0; i < n; i++)
     947                 :     212902 :     if (body[i]->loop_father == loop)
     948                 :            :       {
     949                 :     210719 :         remove_bb_from_loops (body[i]);
     950                 :     421438 :         add_bb_to_loop (body[i], loop_outer (loop));
     951                 :            :       }
     952                 :      71403 :   free (body);
     953                 :            : 
     954                 :      72139 :   while (loop->inner)
     955                 :            :     {
     956                 :        736 :       ploop = loop->inner;
     957                 :        736 :       flow_loop_tree_node_remove (ploop);
     958                 :       1472 :       flow_loop_tree_node_add (loop_outer (loop), ploop);
     959                 :            :     }
     960                 :            : 
     961                 :            :   /* Remove the loop and free its data.  */
     962                 :      71403 :   delete_loop (loop);
     963                 :            : 
     964                 :      71403 :   remove_edge (single_succ_edge (latch));
     965                 :            : 
     966                 :            :   /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
     967                 :            :      there is an irreducible region inside the cancelled loop, the flags will
     968                 :            :      be still correct.  */
     969                 :      71403 :   fix_bb_placements (latch, &dummy, loop_closed_ssa_invalidated);
     970                 :      71403 : }
     971                 :            : 
     972                 :            : /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
     973                 :            :    condition stated in description of fix_loop_placement holds for them.
     974                 :            :    It is used in case when we removed some edges coming out of LOOP, which
     975                 :            :    may cause the right placement of LOOP inside loop tree to change.
     976                 :            : 
     977                 :            :    IRRED_INVALIDATED is set to true if a change in the loop structures might
     978                 :            :    invalidate the information about irreducible regions.  */
     979                 :            : 
     980                 :            : static void
     981                 :     238691 : fix_loop_placements (class loop *loop, bool *irred_invalidated)
     982                 :            : {
     983                 :     238691 :   class loop *outer;
     984                 :            : 
     985                 :     334359 :   while (loop_outer (loop))
     986                 :            :     {
     987                 :      95668 :       outer = loop_outer (loop);
     988                 :      95668 :       if (!fix_loop_placement (loop, irred_invalidated))
     989                 :            :         break;
     990                 :            : 
     991                 :            :       /* Changing the placement of a loop in the loop tree may alter the
     992                 :            :          validity of condition 2) of the description of fix_bb_placement
     993                 :            :          for its preheader, because the successor is the header and belongs
     994                 :            :          to the loop.  So call fix_bb_placements to fix up the placement
     995                 :            :          of the preheader and (possibly) of its predecessors.  */
     996                 :          0 :       fix_bb_placements (loop_preheader_edge (loop)->src,
     997                 :            :                          irred_invalidated, NULL);
     998                 :          0 :       loop = outer;
     999                 :            :     }
    1000                 :     238691 : }
    1001                 :            : 
    1002                 :            : /* Duplicate loop bounds and other information we store about
    1003                 :            :    the loop into its duplicate.  */
    1004                 :            : 
    1005                 :            : void
    1006                 :     190261 : copy_loop_info (class loop *loop, class loop *target)
    1007                 :            : {
    1008                 :     190261 :   gcc_checking_assert (!target->any_upper_bound && !target->any_estimate);
    1009                 :     190261 :   target->any_upper_bound = loop->any_upper_bound;
    1010                 :     190261 :   target->nb_iterations_upper_bound = loop->nb_iterations_upper_bound;
    1011                 :     190261 :   target->any_likely_upper_bound = loop->any_likely_upper_bound;
    1012                 :     190261 :   target->nb_iterations_likely_upper_bound
    1013                 :     190261 :     = loop->nb_iterations_likely_upper_bound;
    1014                 :     190261 :   target->any_estimate = loop->any_estimate;
    1015                 :     190261 :   target->nb_iterations_estimate = loop->nb_iterations_estimate;
    1016                 :     190261 :   target->estimate_state = loop->estimate_state;
    1017                 :     190261 :   target->safelen = loop->safelen;
    1018                 :     190261 :   target->simdlen = loop->simdlen;
    1019                 :     190261 :   target->constraints = loop->constraints;
    1020                 :     190261 :   target->can_be_parallel = loop->can_be_parallel;
    1021                 :     190261 :   target->warned_aggressive_loop_optimizations
    1022                 :     190261 :     |= loop->warned_aggressive_loop_optimizations;
    1023                 :     190261 :   target->dont_vectorize = loop->dont_vectorize;
    1024                 :     190261 :   target->force_vectorize = loop->force_vectorize;
    1025                 :     190261 :   target->in_oacc_kernels_region = loop->in_oacc_kernels_region;
    1026                 :     190261 :   target->unroll = loop->unroll;
    1027                 :     190261 :   target->owned_clique = loop->owned_clique;
    1028                 :     190261 : }
    1029                 :            : 
    1030                 :            : /* Copies copy of LOOP as subloop of TARGET loop, placing newly
    1031                 :            :    created loop into loops structure.  If AFTER is non-null
    1032                 :            :    the new loop is added at AFTER->next, otherwise in front of TARGETs
    1033                 :            :    sibling list.  */
    1034                 :            : class loop *
    1035                 :      14889 : duplicate_loop (class loop *loop, class loop *target, class loop *after)
    1036                 :            : {
    1037                 :      14889 :   class loop *cloop;
    1038                 :      14889 :   cloop = alloc_loop ();
    1039                 :      14889 :   place_new_loop (cfun, cloop);
    1040                 :            :  
    1041                 :      14889 :   copy_loop_info (loop, cloop);
    1042                 :            : 
    1043                 :            :   /* Mark the new loop as copy of LOOP.  */
    1044                 :      14889 :   set_loop_copy (loop, cloop);
    1045                 :            : 
    1046                 :            :   /* Add it to target.  */
    1047                 :      14889 :   flow_loop_tree_node_add (target, cloop, after);
    1048                 :            : 
    1049                 :      14889 :   return cloop;
    1050                 :            : }
    1051                 :            : 
    1052                 :            : /* Copies structure of subloops of LOOP into TARGET loop, placing
    1053                 :            :    newly created loops into loop tree at the end of TARGETs sibling
    1054                 :            :    list in the original order.  */
    1055                 :            : void
    1056                 :      14889 : duplicate_subloops (class loop *loop, class loop *target)
    1057                 :            : {
    1058                 :      14889 :   class loop *aloop, *cloop, *tail;
    1059                 :            : 
    1060                 :      14889 :   for (tail = target->inner; tail && tail->next; tail = tail->next)
    1061                 :            :     ;
    1062                 :      15153 :   for (aloop = loop->inner; aloop; aloop = aloop->next)
    1063                 :            :     {
    1064                 :        264 :       cloop = duplicate_loop (aloop, target, tail);
    1065                 :        264 :       tail = cloop;
    1066                 :        264 :       gcc_assert(!tail->next);
    1067                 :        264 :       duplicate_subloops (aloop, cloop);
    1068                 :            :     }
    1069                 :      14889 : }
    1070                 :            : 
    1071                 :            : /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
    1072                 :            :    into TARGET loop, placing newly created loops into loop tree adding
    1073                 :            :    them to TARGETs sibling list at the end in order.  */
    1074                 :            : static void
    1075                 :     283674 : copy_loops_to (class loop **copied_loops, int n, class loop *target)
    1076                 :            : {
    1077                 :     283674 :   class loop *aloop, *tail;
    1078                 :     283674 :   int i;
    1079                 :            : 
    1080                 :    4086060 :   for (tail = target->inner; tail && tail->next; tail = tail->next)
    1081                 :            :     ;
    1082                 :     285485 :   for (i = 0; i < n; i++)
    1083                 :            :     {
    1084                 :       1811 :       aloop = duplicate_loop (copied_loops[i], target, tail);
    1085                 :       1811 :       tail = aloop;
    1086                 :       1811 :       gcc_assert(!tail->next);
    1087                 :       1811 :       duplicate_subloops (copied_loops[i], aloop);
    1088                 :            :     }
    1089                 :     283674 : }
    1090                 :            : 
    1091                 :            : /* Redirects edge E to basic block DEST.  */
    1092                 :            : static void
    1093                 :      17574 : loop_redirect_edge (edge e, basic_block dest)
    1094                 :            : {
    1095                 :      17574 :   if (e->dest == dest)
    1096                 :            :     return;
    1097                 :            : 
    1098                 :       8787 :   redirect_edge_and_branch_force (e, dest);
    1099                 :            : }
    1100                 :            : 
    1101                 :            : /* Check whether LOOP's body can be duplicated.  */
    1102                 :            : bool
    1103                 :      24642 : can_duplicate_loop_p (const class loop *loop)
    1104                 :            : {
    1105                 :      24642 :   int ret;
    1106                 :      24642 :   basic_block *bbs = get_loop_body (loop);
    1107                 :            : 
    1108                 :      24642 :   ret = can_copy_bbs_p (bbs, loop->num_nodes);
    1109                 :      24642 :   free (bbs);
    1110                 :            : 
    1111                 :      24642 :   return ret;
    1112                 :            : }
    1113                 :            : 
    1114                 :            : /* Duplicates body of LOOP to given edge E NDUPL times.  Takes care of updating
    1115                 :            :    loop structure and dominators (order of inner subloops is retained).
    1116                 :            :    E's destination must be LOOP header for this to work, i.e. it must be entry
    1117                 :            :    or latch edge of this loop; these are unique, as the loops must have
    1118                 :            :    preheaders for this function to work correctly (in case E is latch, the
    1119                 :            :    function unrolls the loop, if E is entry edge, it peels the loop).  Store
    1120                 :            :    edges created by copying ORIG edge from copies corresponding to set bits in
    1121                 :            :    WONT_EXIT bitmap (bit 0 corresponds to original LOOP body, the other copies
    1122                 :            :    are numbered in order given by control flow through them) into TO_REMOVE
    1123                 :            :    array.  Returns false if duplication is
    1124                 :            :    impossible.  */
    1125                 :            : 
    1126                 :            : bool
    1127                 :     113660 : duplicate_loop_to_header_edge (class loop *loop, edge e,
    1128                 :            :                                unsigned int ndupl, sbitmap wont_exit,
    1129                 :            :                                edge orig, vec<edge> *to_remove,
    1130                 :            :                                int flags)
    1131                 :            : {
    1132                 :     113660 :   class loop *target, *aloop;
    1133                 :     113660 :   class loop **orig_loops;
    1134                 :     113660 :   unsigned n_orig_loops;
    1135                 :     113660 :   basic_block header = loop->header, latch = loop->latch;
    1136                 :     113660 :   basic_block *new_bbs, *bbs, *first_active;
    1137                 :     113660 :   basic_block new_bb, bb, first_active_latch = NULL;
    1138                 :     113660 :   edge ae, latch_edge;
    1139                 :     113660 :   edge spec_edges[2], new_spec_edges[2];
    1140                 :     113660 :   const int SE_LATCH = 0;
    1141                 :     113660 :   const int SE_ORIG = 1;
    1142                 :     113660 :   unsigned i, j, n;
    1143                 :     113660 :   int is_latch = (latch == e->src);
    1144                 :     113660 :   profile_probability *scale_step = NULL;
    1145                 :     113660 :   profile_probability scale_main = profile_probability::always ();
    1146                 :     113660 :   profile_probability scale_act = profile_probability::always ();
    1147                 :     113660 :   profile_count after_exit_num = profile_count::zero (),
    1148                 :     113660 :                 after_exit_den = profile_count::zero ();
    1149                 :     113660 :   bool scale_after_exit = false;
    1150                 :     113660 :   int add_irreducible_flag;
    1151                 :     113660 :   basic_block place_after;
    1152                 :     113660 :   bitmap bbs_to_scale = NULL;
    1153                 :     113660 :   bitmap_iterator bi;
    1154                 :            : 
    1155                 :     113660 :   gcc_assert (e->dest == loop->header);
    1156                 :     113660 :   gcc_assert (ndupl > 0);
    1157                 :            : 
    1158                 :     113660 :   if (orig)
    1159                 :            :     {
    1160                 :            :       /* Orig must be edge out of the loop.  */
    1161                 :      96837 :       gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
    1162                 :      96837 :       gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
    1163                 :            :     }
    1164                 :            : 
    1165                 :     113660 :   n = loop->num_nodes;
    1166                 :     113660 :   bbs = get_loop_body_in_dom_order (loop);
    1167                 :     113660 :   gcc_assert (bbs[0] == loop->header);
    1168                 :     113660 :   gcc_assert (bbs[n  - 1] == loop->latch);
    1169                 :            : 
    1170                 :            :   /* Check whether duplication is possible.  */
    1171                 :     113660 :   if (!can_copy_bbs_p (bbs, loop->num_nodes))
    1172                 :            :     {
    1173                 :         14 :       free (bbs);
    1174                 :         14 :       return false;
    1175                 :            :     }
    1176                 :     113646 :   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
    1177                 :            : 
    1178                 :            :   /* In case we are doing loop peeling and the loop is in the middle of
    1179                 :            :      irreducible region, the peeled copies will be inside it too.  */
    1180                 :     113646 :   add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
    1181                 :     113646 :   gcc_assert (!is_latch || !add_irreducible_flag);
    1182                 :            : 
    1183                 :            :   /* Find edge from latch.  */
    1184                 :     113646 :   latch_edge = loop_latch_edge (loop);
    1185                 :            : 
    1186                 :     113646 :   if (flags & DLTHE_FLAG_UPDATE_FREQ)
    1187                 :            :     {
    1188                 :            :       /* Calculate coefficients by that we have to scale counts
    1189                 :            :          of duplicated loop bodies.  */
    1190                 :     104859 :       profile_count count_in = header->count;
    1191                 :     104859 :       profile_count count_le = latch_edge->count ();
    1192                 :     104859 :       profile_count count_out_orig = orig ? orig->count () : count_in - count_le;
    1193                 :     104859 :       profile_probability prob_pass_thru = count_le.probability_in (count_in);
    1194                 :     104859 :       profile_probability prob_pass_wont_exit =
    1195                 :     104859 :               (count_le + count_out_orig).probability_in (count_in);
    1196                 :            : 
    1197                 :      96832 :       if (orig && orig->probability.initialized_p ()
    1198                 :     201707 :           && !(orig->probability == profile_probability::always ()))
    1199                 :            :         {
    1200                 :            :           /* The blocks that are dominated by a removed exit edge ORIG have
    1201                 :            :              frequencies scaled by this.  */
    1202                 :      96784 :           if (orig->count ().initialized_p ())
    1203                 :            :             {
    1204                 :      96781 :               after_exit_num = orig->src->count;
    1205                 :      96781 :               after_exit_den = after_exit_num - orig->count ();
    1206                 :      96781 :               scale_after_exit = true;
    1207                 :            :             }
    1208                 :      96784 :           bbs_to_scale = BITMAP_ALLOC (NULL);
    1209                 :     346721 :           for (i = 0; i < n; i++)
    1210                 :            :             {
    1211                 :     249937 :               if (bbs[i] != orig->src
    1212                 :     249937 :                   && dominated_by_p (CDI_DOMINATORS, bbs[i], orig->src))
    1213                 :     117639 :                 bitmap_set_bit (bbs_to_scale, i);
    1214                 :            :             }
    1215                 :            :         }
    1216                 :            : 
    1217                 :     104859 :       scale_step = XNEWVEC (profile_probability, ndupl);
    1218                 :            : 
    1219                 :     379746 :       for (i = 1; i <= ndupl; i++)
    1220                 :     549774 :         scale_step[i - 1] = bitmap_bit_p (wont_exit, i)
    1221                 :     274887 :                                 ? prob_pass_wont_exit
    1222                 :            :                                 : prob_pass_thru;
    1223                 :            : 
    1224                 :            :       /* Complete peeling is special as the probability of exit in last
    1225                 :            :          copy becomes 1.  */
    1226                 :     104859 :       if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
    1227                 :            :         {
    1228                 :      62074 :           profile_count wanted_count = e->count ();
    1229                 :            : 
    1230                 :      62074 :           gcc_assert (!is_latch);
    1231                 :            :           /* First copy has count of incoming edge.  Each subsequent
    1232                 :            :              count should be reduced by prob_pass_wont_exit.  Caller
    1233                 :            :              should've managed the flags so all except for original loop
    1234                 :            :              has won't exist set.  */
    1235                 :      62074 :           scale_act = wanted_count.probability_in (count_in);
    1236                 :            :           /* Now simulate the duplication adjustments and compute header
    1237                 :            :              frequency of the last copy.  */
    1238                 :     254417 :           for (i = 0; i < ndupl; i++)
    1239                 :     192343 :             wanted_count = wanted_count.apply_probability (scale_step [i]);
    1240                 :      62074 :           scale_main = wanted_count.probability_in (count_in);
    1241                 :            :         }
    1242                 :            :       /* Here we insert loop bodies inside the loop itself (for loop unrolling).
    1243                 :            :          First iteration will be original loop followed by duplicated bodies.
    1244                 :            :          It is necessary to scale down the original so we get right overall
    1245                 :            :          number of iterations.  */
    1246                 :      42785 :       else if (is_latch)
    1247                 :            :         {
    1248                 :       9213 :           profile_probability prob_pass_main = bitmap_bit_p (wont_exit, 0)
    1249                 :       9213 :                                                         ? prob_pass_wont_exit
    1250                 :       9213 :                                                         : prob_pass_thru;
    1251                 :       9213 :           profile_probability p = prob_pass_main;
    1252                 :       9213 :           profile_count scale_main_den = count_in;
    1253                 :      52497 :           for (i = 0; i < ndupl; i++)
    1254                 :            :             {
    1255                 :      43284 :               scale_main_den += count_in.apply_probability (p);
    1256                 :      43284 :               p = p * scale_step[i];
    1257                 :            :             }
    1258                 :            :           /* If original loop is executed COUNT_IN times, the unrolled
    1259                 :            :              loop will account SCALE_MAIN_DEN times.  */
    1260                 :       9213 :           scale_main = count_in.probability_in (scale_main_den);
    1261                 :       9213 :           scale_act = scale_main * prob_pass_main;
    1262                 :            :         }
    1263                 :            :       else
    1264                 :            :         {
    1265                 :      33572 :           profile_count preheader_count = e->count ();
    1266                 :      72832 :           for (i = 0; i < ndupl; i++)
    1267                 :      39260 :             scale_main = scale_main * scale_step[i];
    1268                 :      33572 :           scale_act = preheader_count.probability_in (count_in);
    1269                 :            :         }
    1270                 :            :     }
    1271                 :            : 
    1272                 :            :   /* Loop the new bbs will belong to.  */
    1273                 :     113646 :   target = e->src->loop_father;
    1274                 :            : 
    1275                 :            :   /* Original loops.  */
    1276                 :     113646 :   n_orig_loops = 0;
    1277                 :     115046 :   for (aloop = loop->inner; aloop; aloop = aloop->next)
    1278                 :       1400 :     n_orig_loops++;
    1279                 :     113646 :   orig_loops = XNEWVEC (class loop *, n_orig_loops);
    1280                 :     115046 :   for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
    1281                 :       1400 :     orig_loops[i] = aloop;
    1282                 :            : 
    1283                 :     113646 :   set_loop_copy (loop, target);
    1284                 :            : 
    1285                 :     113646 :   first_active = XNEWVEC (basic_block, n);
    1286                 :     113646 :   if (is_latch)
    1287                 :            :     {
    1288                 :       9213 :       memcpy (first_active, bbs, n * sizeof (basic_block));
    1289                 :       9213 :       first_active_latch = latch;
    1290                 :            :     }
    1291                 :            : 
    1292                 :     113646 :   spec_edges[SE_ORIG] = orig;
    1293                 :     113646 :   spec_edges[SE_LATCH] = latch_edge;
    1294                 :            : 
    1295                 :     113646 :   place_after = e->src;
    1296                 :     397320 :   for (j = 0; j < ndupl; j++)
    1297                 :            :     {
    1298                 :            :       /* Copy loops.  */
    1299                 :     283674 :       copy_loops_to (orig_loops, n_orig_loops, target);
    1300                 :            : 
    1301                 :            :       /* Copy bbs.  */
    1302                 :     283674 :       copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
    1303                 :            :                 place_after, true);
    1304                 :     283674 :       place_after = new_spec_edges[SE_LATCH]->src;
    1305                 :            : 
    1306                 :     283674 :       if (flags & DLTHE_RECORD_COPY_NUMBER)
    1307                 :     146620 :         for (i = 0; i < n; i++)
    1308                 :            :           {
    1309                 :     103844 :             gcc_assert (!new_bbs[i]->aux);
    1310                 :     103844 :             new_bbs[i]->aux = (void *)(size_t)(j + 1);
    1311                 :            :           }
    1312                 :            : 
    1313                 :            :       /* Note whether the blocks and edges belong to an irreducible loop.  */
    1314                 :     283674 :       if (add_irreducible_flag)
    1315                 :            :         {
    1316                 :        214 :           for (i = 0; i < n; i++)
    1317                 :        158 :             new_bbs[i]->flags |= BB_DUPLICATED;
    1318                 :        214 :           for (i = 0; i < n; i++)
    1319                 :            :             {
    1320                 :        158 :               edge_iterator ei;
    1321                 :        158 :               new_bb = new_bbs[i];
    1322                 :        158 :               if (new_bb->loop_father == target)
    1323                 :        158 :                 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
    1324                 :            : 
    1325                 :        418 :               FOR_EACH_EDGE (ae, ei, new_bb->succs)
    1326                 :        260 :                 if ((ae->dest->flags & BB_DUPLICATED)
    1327                 :        158 :                     && (ae->src->loop_father == target
    1328                 :          0 :                         || ae->dest->loop_father == target))
    1329                 :        158 :                   ae->flags |= EDGE_IRREDUCIBLE_LOOP;
    1330                 :            :             }
    1331                 :        214 :           for (i = 0; i < n; i++)
    1332                 :        158 :             new_bbs[i]->flags &= ~BB_DUPLICATED;
    1333                 :            :         }
    1334                 :            : 
    1335                 :            :       /* Redirect the special edges.  */
    1336                 :     283674 :       if (is_latch)
    1337                 :            :         {
    1338                 :      43284 :           redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
    1339                 :      43284 :           redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
    1340                 :            :                                           loop->header);
    1341                 :      43284 :           set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
    1342                 :      43284 :           latch = loop->latch = new_bbs[n - 1];
    1343                 :      43284 :           e = latch_edge = new_spec_edges[SE_LATCH];
    1344                 :            :         }
    1345                 :            :       else
    1346                 :            :         {
    1347                 :     240390 :           redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
    1348                 :            :                                           loop->header);
    1349                 :     240390 :           redirect_edge_and_branch_force (e, new_bbs[0]);
    1350                 :     240390 :           set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
    1351                 :     240390 :           e = new_spec_edges[SE_LATCH];
    1352                 :            :         }
    1353                 :            : 
    1354                 :            :       /* Record exit edge in this copy.  */
    1355                 :     283674 :       if (orig && bitmap_bit_p (wont_exit, j + 1))
    1356                 :            :         {
    1357                 :     229244 :           if (to_remove)
    1358                 :     229244 :             to_remove->safe_push (new_spec_edges[SE_ORIG]);
    1359                 :     229244 :           force_edge_cold (new_spec_edges[SE_ORIG], true);
    1360                 :            : 
    1361                 :            :           /* Scale the frequencies of the blocks dominated by the exit.  */
    1362                 :     229244 :           if (bbs_to_scale && scale_after_exit)
    1363                 :            :             {
    1364                 :     514044 :               EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
    1365                 :     284953 :                 scale_bbs_frequencies_profile_count (new_bbs + i, 1, after_exit_num,
    1366                 :            :                                                      after_exit_den);
    1367                 :            :             }
    1368                 :            :         }
    1369                 :            : 
    1370                 :            :       /* Record the first copy in the control flow order if it is not
    1371                 :            :          the original loop (i.e. in case of peeling).  */
    1372                 :     283674 :       if (!first_active_latch)
    1373                 :            :         {
    1374                 :     104433 :           memcpy (first_active, new_bbs, n * sizeof (basic_block));
    1375                 :     104433 :           first_active_latch = new_bbs[n - 1];
    1376                 :            :         }
    1377                 :            : 
    1378                 :            :       /* Set counts and frequencies.  */
    1379                 :     283674 :       if (flags & DLTHE_FLAG_UPDATE_FREQ)
    1380                 :            :         {
    1381                 :     274887 :           scale_bbs_frequencies (new_bbs, n, scale_act);
    1382                 :     274887 :           scale_act = scale_act * scale_step[j];
    1383                 :            :         }
    1384                 :            :     }
    1385                 :     113646 :   free (new_bbs);
    1386                 :     113646 :   free (orig_loops);
    1387                 :            : 
    1388                 :            :   /* Record the exit edge in the original loop body, and update the frequencies.  */
    1389                 :     210478 :   if (orig && bitmap_bit_p (wont_exit, 0))
    1390                 :            :     {
    1391                 :       8951 :       if (to_remove)
    1392                 :       8951 :         to_remove->safe_push (orig);
    1393                 :       8951 :       force_edge_cold (orig, true);
    1394                 :            : 
    1395                 :            :       /* Scale the frequencies of the blocks dominated by the exit.  */
    1396                 :       8951 :       if (bbs_to_scale && scale_after_exit)
    1397                 :            :         {
    1398                 :      17891 :           EXECUTE_IF_SET_IN_BITMAP (bbs_to_scale, 0, i, bi)
    1399                 :       8949 :             scale_bbs_frequencies_profile_count (bbs + i, 1, after_exit_num,
    1400                 :            :                                                  after_exit_den);
    1401                 :            :         }
    1402                 :            :     }
    1403                 :            : 
    1404                 :            :   /* Update the original loop.  */
    1405                 :     113646 :   if (!is_latch)
    1406                 :     104433 :     set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
    1407                 :     113646 :   if (flags & DLTHE_FLAG_UPDATE_FREQ)
    1408                 :            :     {
    1409                 :     104859 :       scale_bbs_frequencies (bbs, n, scale_main);
    1410                 :     104859 :       free (scale_step);
    1411                 :            :     }
    1412                 :            : 
    1413                 :            :   /* Update dominators of outer blocks if affected.  */
    1414                 :     422454 :   for (i = 0; i < n; i++)
    1415                 :            :     {
    1416                 :     308808 :       basic_block dominated, dom_bb;
    1417                 :     308808 :       vec<basic_block> dom_bbs;
    1418                 :     308808 :       unsigned j;
    1419                 :            : 
    1420                 :     308808 :       bb = bbs[i];
    1421                 :     308808 :       bb->aux = 0;
    1422                 :            : 
    1423                 :     308808 :       dom_bbs = get_dominated_by (CDI_DOMINATORS, bb);
    1424                 :     600674 :       FOR_EACH_VEC_ELT (dom_bbs, j, dominated)
    1425                 :            :         {
    1426                 :     291866 :           if (flow_bb_inside_loop_p (loop, dominated))
    1427                 :     204375 :             continue;
    1428                 :     174982 :           dom_bb = nearest_common_dominator (
    1429                 :      87491 :                         CDI_DOMINATORS, first_active[i], first_active_latch);
    1430                 :      87491 :           set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
    1431                 :            :         }
    1432                 :     488036 :       dom_bbs.release ();
    1433                 :            :     }
    1434                 :     113646 :   free (first_active);
    1435                 :            : 
    1436                 :     113646 :   free (bbs);
    1437                 :     113646 :   BITMAP_FREE (bbs_to_scale);
    1438                 :            : 
    1439                 :     113646 :   return true;
    1440                 :            : }
    1441                 :            : 
    1442                 :            : /* A callback for make_forwarder block, to redirect all edges except for
    1443                 :            :    MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
    1444                 :            :    whether to redirect it.  */
    1445                 :            : 
    1446                 :            : edge mfb_kj_edge;
    1447                 :            : bool
    1448                 :     455339 : mfb_keep_just (edge e)
    1449                 :            : {
    1450                 :     455339 :   return e != mfb_kj_edge;
    1451                 :            : }
    1452                 :            : 
    1453                 :            : /* True when a candidate preheader BLOCK has predecessors from LOOP.  */
    1454                 :            : 
    1455                 :            : static bool
    1456                 :         22 : has_preds_from_loop (basic_block block, class loop *loop)
    1457                 :            : {
    1458                 :         22 :   edge e;
    1459                 :         22 :   edge_iterator ei;
    1460                 :            : 
    1461                 :         49 :   FOR_EACH_EDGE (e, ei, block->preds)
    1462                 :         27 :     if (e->src->loop_father == loop)
    1463                 :            :       return true;
    1464                 :            :   return false;
    1465                 :            : }
    1466                 :            : 
    1467                 :            : /* Creates a pre-header for a LOOP.  Returns newly created block.  Unless
    1468                 :            :    CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
    1469                 :            :    entry; otherwise we also force preheader block to have only one successor.
    1470                 :            :    When CP_FALLTHRU_PREHEADERS is set in FLAGS, we force the preheader block
    1471                 :            :    to be a fallthru predecessor to the loop header and to have only
    1472                 :            :    predecessors from outside of the loop.
    1473                 :            :    The function also updates dominators.  */
    1474                 :            : 
    1475                 :            : basic_block
    1476                 :    8879600 : create_preheader (class loop *loop, int flags)
    1477                 :            : {
    1478                 :    8879600 :   edge e;
    1479                 :    8879600 :   basic_block dummy;
    1480                 :    8879600 :   int nentry = 0;
    1481                 :    8879600 :   bool irred = false;
    1482                 :    8879600 :   bool latch_edge_was_fallthru;
    1483                 :    8879600 :   edge one_succ_pred = NULL, single_entry = NULL;
    1484                 :    8879600 :   edge_iterator ei;
    1485                 :            : 
    1486                 :   26724200 :   FOR_EACH_EDGE (e, ei, loop->header->preds)
    1487                 :            :     {
    1488                 :   17844600 :       if (e->src == loop->latch)
    1489                 :    8879600 :         continue;
    1490                 :    8964960 :       irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
    1491                 :    8964960 :       nentry++;
    1492                 :    8964960 :       single_entry = e;
    1493                 :    8964960 :       if (single_succ_p (e->src))
    1494                 :    7403000 :         one_succ_pred = e;
    1495                 :            :     }
    1496                 :    8879600 :   gcc_assert (nentry);
    1497                 :    8879600 :   if (nentry == 1)
    1498                 :            :     {
    1499                 :    8822080 :       bool need_forwarder_block = false;
    1500                 :            : 
    1501                 :            :       /* We do not allow entry block to be the loop preheader, since we
    1502                 :            :              cannot emit code there.  */
    1503                 :    8822080 :       if (single_entry->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1504                 :            :         need_forwarder_block = true;
    1505                 :            :       else
    1506                 :            :         {
    1507                 :            :           /* If we want simple preheaders, also force the preheader to have
    1508                 :            :              just a single successor.  */
    1509                 :    8815700 :           if ((flags & CP_SIMPLE_PREHEADERS)
    1510                 :    8815700 :               && !single_succ_p (single_entry->src))
    1511                 :            :             need_forwarder_block = true;
    1512                 :            :           /* If we want fallthru preheaders, also create forwarder block when
    1513                 :            :              preheader ends with a jump or has predecessors from loop.  */
    1514                 :    7343600 :           else if ((flags & CP_FALLTHRU_PREHEADERS)
    1515                 :    7343600 :                    && (JUMP_P (BB_END (single_entry->src))
    1516                 :         22 :                        || has_preds_from_loop (single_entry->src, loop)))
    1517                 :            :             need_forwarder_block = true;
    1518                 :            :         }
    1519                 :    7343590 :       if (! need_forwarder_block)
    1520                 :    7343590 :         return NULL;
    1521                 :            :     }
    1522                 :            : 
    1523                 :    1536020 :   mfb_kj_edge = loop_latch_edge (loop);
    1524                 :    1536020 :   latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
    1525                 :    1536020 :   if (nentry == 1
    1526                 :    1478490 :       && ((flags & CP_FALLTHRU_PREHEADERS) == 0
    1527                 :         21 :           || (single_entry->flags & EDGE_CROSSING) == 0))
    1528                 :    1478490 :     dummy = split_edge (single_entry);
    1529                 :            :   else
    1530                 :            :     {
    1531                 :      57528 :       edge fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL);
    1532                 :      57528 :       dummy = fallthru->src;
    1533                 :      57528 :       loop->header = fallthru->dest;
    1534                 :            :     }
    1535                 :            : 
    1536                 :            :   /* Try to be clever in placing the newly created preheader.  The idea is to
    1537                 :            :      avoid breaking any "fallthruness" relationship between blocks.
    1538                 :            : 
    1539                 :            :      The preheader was created just before the header and all incoming edges
    1540                 :            :      to the header were redirected to the preheader, except the latch edge.
    1541                 :            :      So the only problematic case is when this latch edge was a fallthru
    1542                 :            :      edge: it is not anymore after the preheader creation so we have broken
    1543                 :            :      the fallthruness.  We're therefore going to look for a better place.  */
    1544                 :    1536020 :   if (latch_edge_was_fallthru)
    1545                 :            :     {
    1546                 :     607369 :       if (one_succ_pred)
    1547                 :      32711 :         e = one_succ_pred;
    1548                 :            :       else
    1549                 :     574658 :         e = EDGE_PRED (dummy, 0);
    1550                 :            : 
    1551                 :     607369 :       move_block_after (dummy, e->src);
    1552                 :            :     }
    1553                 :            : 
    1554                 :    1536020 :   if (irred)
    1555                 :            :     {
    1556                 :       1752 :       dummy->flags |= BB_IRREDUCIBLE_LOOP;
    1557                 :       1752 :       single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
    1558                 :            :     }
    1559                 :            : 
    1560                 :    1536020 :   if (dump_file)
    1561                 :        126 :     fprintf (dump_file, "Created preheader block for loop %i\n",
    1562                 :            :              loop->num);
    1563                 :            : 
    1564                 :    1536020 :   if (flags & CP_FALLTHRU_PREHEADERS)
    1565                 :         28 :     gcc_assert ((single_succ_edge (dummy)->flags & EDGE_FALLTHRU)
    1566                 :            :                 && !JUMP_P (BB_END (dummy)));
    1567                 :            : 
    1568                 :            :   return dummy;
    1569                 :            : }
    1570                 :            : 
    1571                 :            : /* Create preheaders for each loop; for meaning of FLAGS see create_preheader.  */
    1572                 :            : 
    1573                 :            : void
    1574                 :   18779300 : create_preheaders (int flags)
    1575                 :            : {
    1576                 :   18779300 :   class loop *loop;
    1577                 :            : 
    1578                 :   18779300 :   if (!current_loops)
    1579                 :          0 :     return;
    1580                 :            : 
    1581                 :   27658300 :   FOR_EACH_LOOP (loop, 0)
    1582                 :    8878960 :     create_preheader (loop, flags);
    1583                 :   18779300 :   loops_state_set (LOOPS_HAVE_PREHEADERS);
    1584                 :            : }
    1585                 :            : 
    1586                 :            : /* Forces all loop latches to have only single successor.  */
    1587                 :            : 
    1588                 :            : void
    1589                 :   17195700 : force_single_succ_latches (void)
    1590                 :            : {
    1591                 :   17195700 :   class loop *loop;
    1592                 :   17195700 :   edge e;
    1593                 :            : 
    1594                 :   25672700 :   FOR_EACH_LOOP (loop, 0)
    1595                 :            :     {
    1596                 :    8476990 :       if (loop->latch != loop->header && single_succ_p (loop->latch))
    1597                 :    5981910 :         continue;
    1598                 :            : 
    1599                 :    2495080 :       e = find_edge (loop->latch, loop->header);
    1600                 :    2495080 :       gcc_checking_assert (e != NULL);
    1601                 :            : 
    1602                 :    2495080 :       split_edge (e);
    1603                 :            :     }
    1604                 :   17195700 :   loops_state_set (LOOPS_HAVE_SIMPLE_LATCHES);
    1605                 :   17195700 : }
    1606                 :            : 
    1607                 :            : /* This function is called from loop_version.  It splits the entry edge
    1608                 :            :    of the loop we want to version, adds the versioning condition, and
    1609                 :            :    adjust the edges to the two versions of the loop appropriately.
    1610                 :            :    e is an incoming edge. Returns the basic block containing the
    1611                 :            :    condition.
    1612                 :            : 
    1613                 :            :    --- edge e ---- > [second_head]
    1614                 :            : 
    1615                 :            :    Split it and insert new conditional expression and adjust edges.
    1616                 :            : 
    1617                 :            :     --- edge e ---> [cond expr] ---> [first_head]
    1618                 :            :                         |
    1619                 :            :                         +---------> [second_head]
    1620                 :            : 
    1621                 :            :   THEN_PROB is the probability of then branch of the condition.
    1622                 :            :   ELSE_PROB is the probability of else branch. Note that they may be both
    1623                 :            :   REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED or
    1624                 :            :   IFN_LOOP_DIST_ALIAS.  */
    1625                 :            : 
    1626                 :            : static basic_block
    1627                 :       8787 : lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head,
    1628                 :            :                            edge e, void *cond_expr,
    1629                 :            :                            profile_probability then_prob,
    1630                 :            :                            profile_probability else_prob)
    1631                 :            : {
    1632                 :       8787 :   basic_block new_head = NULL;
    1633                 :       8787 :   edge e1;
    1634                 :            : 
    1635                 :       8787 :   gcc_assert (e->dest == second_head);
    1636                 :            : 
    1637                 :            :   /* Split edge 'e'. This will create a new basic block, where we can
    1638                 :            :      insert conditional expr.  */
    1639                 :       8787 :   new_head = split_edge (e);
    1640                 :            : 
    1641                 :       8787 :   lv_add_condition_to_bb (first_head, second_head, new_head,
    1642                 :            :                           cond_expr);
    1643                 :            : 
    1644                 :            :   /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there.  */
    1645                 :       8787 :   e = single_succ_edge (new_head);
    1646                 :       8787 :   e1 = make_edge (new_head, first_head,
    1647                 :       8787 :                   current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0);
    1648                 :       8787 :   e1->probability = then_prob;
    1649                 :       8787 :   e->probability = else_prob;
    1650                 :            : 
    1651                 :       8787 :   set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
    1652                 :       8787 :   set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
    1653                 :            : 
    1654                 :            :   /* Adjust loop header phi nodes.  */
    1655                 :       8787 :   lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
    1656                 :            : 
    1657                 :       8787 :   return new_head;
    1658                 :            : }
    1659                 :            : 
    1660                 :            : /* Main entry point for Loop Versioning transformation.
    1661                 :            : 
    1662                 :            :    This transformation given a condition and a loop, creates
    1663                 :            :    -if (condition) { loop_copy1 } else { loop_copy2 },
    1664                 :            :    where loop_copy1 is the loop transformed in one way, and loop_copy2
    1665                 :            :    is the loop transformed in another way (or unchanged). COND_EXPR
    1666                 :            :    may be a run time test for things that were not resolved by static
    1667                 :            :    analysis (overlapping ranges (anti-aliasing), alignment, etc.).
    1668                 :            : 
    1669                 :            :    If non-NULL, CONDITION_BB is set to the basic block containing the
    1670                 :            :    condition.
    1671                 :            : 
    1672                 :            :    THEN_PROB is the probability of the then edge of the if.  THEN_SCALE
    1673                 :            :    is the ratio by that the frequencies in the original loop should
    1674                 :            :    be scaled.  ELSE_SCALE is the ratio by that the frequencies in the
    1675                 :            :    new loop should be scaled.
    1676                 :            : 
    1677                 :            :    If PLACE_AFTER is true, we place the new loop after LOOP in the
    1678                 :            :    instruction stream, otherwise it is placed before LOOP.  */
    1679                 :            : 
    1680                 :            : class loop *
    1681                 :       8796 : loop_version (class loop *loop,
    1682                 :            :               void *cond_expr, basic_block *condition_bb,
    1683                 :            :               profile_probability then_prob, profile_probability else_prob,
    1684                 :            :               profile_probability then_scale, profile_probability else_scale,
    1685                 :            :               bool place_after)
    1686                 :            : {
    1687                 :       8796 :   basic_block first_head, second_head;
    1688                 :       8796 :   edge entry, latch_edge, true_edge, false_edge;
    1689                 :       8796 :   int irred_flag;
    1690                 :       8796 :   class loop *nloop;
    1691                 :       8796 :   basic_block cond_bb;
    1692                 :            : 
    1693                 :            :   /* Record entry and latch edges for the loop */
    1694                 :       8796 :   entry = loop_preheader_edge (loop);
    1695                 :       8796 :   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
    1696                 :       8796 :   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
    1697                 :            : 
    1698                 :            :   /* Note down head of loop as first_head.  */
    1699                 :       8796 :   first_head = entry->dest;
    1700                 :            : 
    1701                 :            :   /* Duplicate loop.  */
    1702                 :       8796 :   if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, 1,
    1703                 :            :                                                NULL, NULL, NULL, 0))
    1704                 :            :     {
    1705                 :          9 :       entry->flags |= irred_flag;
    1706                 :          9 :       return NULL;
    1707                 :            :     }
    1708                 :            : 
    1709                 :            :   /* After duplication entry edge now points to new loop head block.
    1710                 :            :      Note down new head as second_head.  */
    1711                 :       8787 :   second_head = entry->dest;
    1712                 :            : 
    1713                 :            :   /* Split loop entry edge and insert new block with cond expr.  */
    1714                 :       8787 :   cond_bb =  lv_adjust_loop_entry_edge (first_head, second_head,
    1715                 :            :                                         entry, cond_expr, then_prob, else_prob);
    1716                 :       8787 :   if (condition_bb)
    1717                 :       6157 :     *condition_bb = cond_bb;
    1718                 :            : 
    1719                 :       8787 :   if (!cond_bb)
    1720                 :            :     {
    1721                 :          0 :       entry->flags |= irred_flag;
    1722                 :          0 :       return NULL;
    1723                 :            :     }
    1724                 :            : 
    1725                 :       8787 :   latch_edge = single_succ_edge (get_bb_copy (loop->latch));
    1726                 :            : 
    1727                 :       8787 :   extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
    1728                 :       8787 :   nloop = loopify (latch_edge,
    1729                 :       8787 :                    single_pred_edge (get_bb_copy (loop->header)),
    1730                 :            :                    cond_bb, true_edge, false_edge,
    1731                 :            :                    false /* Do not redirect all edges.  */,
    1732                 :            :                    then_scale, else_scale);
    1733                 :            : 
    1734                 :       8787 :   copy_loop_info (loop, nloop);
    1735                 :            : 
    1736                 :            :   /* loopify redirected latch_edge. Update its PENDING_STMTS.  */
    1737                 :       8787 :   lv_flush_pending_stmts (latch_edge);
    1738                 :            : 
    1739                 :            :   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */
    1740                 :       8787 :   extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
    1741                 :       8787 :   lv_flush_pending_stmts (false_edge);
    1742                 :            :   /* Adjust irreducible flag.  */
    1743                 :       8787 :   if (irred_flag)
    1744                 :            :     {
    1745                 :         44 :       cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
    1746                 :         44 :       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
    1747                 :         44 :       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
    1748                 :         44 :       single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
    1749                 :            :     }
    1750                 :            : 
    1751                 :       8787 :   if (place_after)
    1752                 :            :     {
    1753                 :       7288 :       basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
    1754                 :       7288 :       unsigned i;
    1755                 :            : 
    1756                 :       7288 :       after = loop->latch;
    1757                 :            : 
    1758                 :      38834 :       for (i = 0; i < nloop->num_nodes; i++)
    1759                 :            :         {
    1760                 :      31546 :           move_block_after (bbs[i], after);
    1761                 :      31546 :           after = bbs[i];
    1762                 :            :         }
    1763                 :       7288 :       free (bbs);
    1764                 :            :     }
    1765                 :            : 
    1766                 :            :   /* At this point condition_bb is loop preheader with two successors,
    1767                 :            :      first_head and second_head.   Make sure that loop preheader has only
    1768                 :            :      one successor.  */
    1769                 :       8787 :   split_edge (loop_preheader_edge (loop));
    1770                 :       8787 :   split_edge (loop_preheader_edge (nloop));
    1771                 :            : 
    1772                 :       8787 :   return nloop;
    1773                 :            : }

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.