LCOV - code coverage report
Current view: top level - gcc - cfgloop.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 846 936 90.4 %
Date: 2020-04-04 11:58:09 Functions: 68 71 95.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Natural loop discovery code for GNU compiler.
       2                 :            :    Copyright (C) 2000-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 "gimple-ssa.h"
      29                 :            : #include "diagnostic-core.h"
      30                 :            : #include "cfganal.h"
      31                 :            : #include "cfgloop.h"
      32                 :            : #include "gimple-iterator.h"
      33                 :            : #include "dumpfile.h"
      34                 :            : 
      35                 :            : static void flow_loops_cfg_dump (FILE *);
      36                 :            : 
      37                 :            : /* Dump loop related CFG information.  */
      38                 :            : 
      39                 :            : static void
      40                 :       4416 : flow_loops_cfg_dump (FILE *file)
      41                 :            : {
      42                 :       4416 :   basic_block bb;
      43                 :            : 
      44                 :       4416 :   if (!file)
      45                 :            :     return;
      46                 :            : 
      47                 :      22250 :   FOR_EACH_BB_FN (bb, cfun)
      48                 :            :     {
      49                 :      17834 :       edge succ;
      50                 :      17834 :       edge_iterator ei;
      51                 :            : 
      52                 :      17834 :       fprintf (file, ";; %d succs { ", bb->index);
      53                 :      41653 :       FOR_EACH_EDGE (succ, ei, bb->succs)
      54                 :      23819 :         fprintf (file, "%d ", succ->dest->index);
      55                 :      17834 :       fprintf (file, "}\n");
      56                 :            :     }
      57                 :            : }
      58                 :            : 
      59                 :            : /* Return nonzero if the nodes of LOOP are a subset of OUTER.  */
      60                 :            : 
      61                 :            : bool
      62                 :  419977000 : flow_loop_nested_p (const class loop *outer, const class loop *loop)
      63                 :            : {
      64                 :  419977000 :   unsigned odepth = loop_depth (outer);
      65                 :            : 
      66                 :  419977000 :   return (loop_depth (loop) > odepth
      67                 :  419977000 :           && (*loop->superloops)[odepth] == outer);
      68                 :            : }
      69                 :            : 
      70                 :            : /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
      71                 :            :    loops within LOOP.  */
      72                 :            : 
      73                 :            : class loop *
      74                 :   13025800 : superloop_at_depth (class loop *loop, unsigned depth)
      75                 :            : {
      76                 :   13025800 :   unsigned ldepth = loop_depth (loop);
      77                 :            : 
      78                 :   13025800 :   gcc_assert (depth <= ldepth);
      79                 :            : 
      80                 :   13025800 :   if (depth == ldepth)
      81                 :            :     return loop;
      82                 :            : 
      83                 :    3803320 :   return (*loop->superloops)[depth];
      84                 :            : }
      85                 :            : 
      86                 :            : /* Returns the list of the latch edges of LOOP.  */
      87                 :            : 
      88                 :            : static vec<edge> 
      89                 :     126956 : get_loop_latch_edges (const class loop *loop)
      90                 :            : {
      91                 :     126956 :   edge_iterator ei;
      92                 :     126956 :   edge e;
      93                 :     126956 :   vec<edge> ret = vNULL;
      94                 :            : 
      95                 :     567113 :   FOR_EACH_EDGE (e, ei, loop->header->preds)
      96                 :            :     {
      97                 :     440157 :       if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
      98                 :     305492 :         ret.safe_push (e);
      99                 :            :     }
     100                 :            : 
     101                 :     126956 :   return ret;
     102                 :            : }
     103                 :            : 
     104                 :            : /* Dump the loop information specified by LOOP to the stream FILE
     105                 :            :    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
     106                 :            : 
     107                 :            : void
     108                 :       5981 : flow_loop_dump (const class loop *loop, FILE *file,
     109                 :            :                 void (*loop_dump_aux) (const class loop *, FILE *, int),
     110                 :            :                 int verbose)
     111                 :            : {
     112                 :       5981 :   basic_block *bbs;
     113                 :       5981 :   unsigned i;
     114                 :       5981 :   vec<edge> latches;
     115                 :       5981 :   edge e;
     116                 :            : 
     117                 :       5981 :   if (! loop || ! loop->header)
     118                 :       5981 :     return;
     119                 :            : 
     120                 :       5981 :   fprintf (file, ";;\n;; Loop %d\n", loop->num);
     121                 :            : 
     122                 :       5981 :   fprintf (file, ";;  header %d, ", loop->header->index);
     123                 :       5981 :   if (loop->latch)
     124                 :       5977 :     fprintf (file, "latch %d\n", loop->latch->index);
     125                 :            :   else
     126                 :            :     {
     127                 :          4 :       fprintf (file, "multiple latches:");
     128                 :          4 :       latches = get_loop_latch_edges (loop);
     129                 :         12 :       FOR_EACH_VEC_ELT (latches, i, e)
     130                 :          8 :         fprintf (file, " %d", e->src->index);
     131                 :          4 :       latches.release ();
     132                 :          4 :       fprintf (file, "\n");
     133                 :            :     }
     134                 :            : 
     135                 :       7525 :   fprintf (file, ";;  depth %d, outer %ld\n",
     136                 :       5981 :            loop_depth (loop), (long) (loop_outer (loop)
     137                 :       1544 :                                       ? loop_outer (loop)->num : -1));
     138                 :            : 
     139                 :       5981 :   if (loop->latch)
     140                 :            :     {
     141                 :       5977 :       bool read_profile_p;
     142                 :       5977 :       gcov_type nit = expected_loop_iterations_unbounded (loop, &read_profile_p);
     143                 :       5977 :       if (read_profile_p && !loop->any_estimate)
     144                 :          2 :         fprintf (file, ";;  profile-based iteration count: %" PRIu64 "\n",
     145                 :            :                  (uint64_t) nit);
     146                 :            :     }
     147                 :            : 
     148                 :       5981 :   fprintf (file, ";;  nodes:");
     149                 :       5981 :   bbs = get_loop_body (loop);
     150                 :      38274 :   for (i = 0; i < loop->num_nodes; i++)
     151                 :      32293 :     fprintf (file, " %d", bbs[i]->index);
     152                 :       5981 :   free (bbs);
     153                 :       5981 :   fprintf (file, "\n");
     154                 :            : 
     155                 :       5981 :   if (loop_dump_aux)
     156                 :          0 :     loop_dump_aux (loop, file, verbose);
     157                 :            : }
     158                 :            : 
     159                 :            : /* Dump the loop information about loops to the stream FILE,
     160                 :            :    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
     161                 :            : 
     162                 :            : void
     163                 :   31020200 : flow_loops_dump (FILE *file, void (*loop_dump_aux) (const class loop *, FILE *, int), int verbose)
     164                 :            : {
     165                 :   31020200 :   class loop *loop;
     166                 :            : 
     167                 :   31020200 :   if (!current_loops || ! file)
     168                 :   31015700 :     return;
     169                 :            : 
     170                 :       8874 :   fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
     171                 :            : 
     172                 :      10347 :   FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
     173                 :            :     {
     174                 :       5910 :       flow_loop_dump (loop, file, loop_dump_aux, verbose);
     175                 :            :     }
     176                 :            : 
     177                 :       4437 :   if (verbose)
     178                 :       4416 :     flow_loops_cfg_dump (file);
     179                 :            : }
     180                 :            : 
     181                 :            : /* Free data allocated for LOOP.  */
     182                 :            : 
     183                 :            : void
     184                 :    9426400 : flow_loop_free (class loop *loop)
     185                 :            : {
     186                 :    9426400 :   struct loop_exit *exit, *next;
     187                 :            : 
     188                 :    9426400 :   vec_free (loop->superloops);
     189                 :            : 
     190                 :            :   /* Break the list of the loop exit records.  They will be freed when the
     191                 :            :      corresponding edge is rescanned or removed, and this avoids
     192                 :            :      accessing the (already released) head of the list stored in the
     193                 :            :      loop structure.  */
     194                 :    9435240 :   for (exit = loop->exits->next; exit != loop->exits; exit = next)
     195                 :            :     {
     196                 :       8844 :       next = exit->next;
     197                 :       8844 :       exit->next = exit;
     198                 :       8844 :       exit->prev = exit;
     199                 :            :     }
     200                 :            : 
     201                 :    9426400 :   ggc_free (loop->exits);
     202                 :    9426400 :   ggc_free (loop);
     203                 :    9426400 : }
     204                 :            : 
     205                 :            : /* Free all the memory allocated for LOOPS.  */
     206                 :            : 
     207                 :            : void
     208                 :    6444380 : flow_loops_free (struct loops *loops)
     209                 :            : {
     210                 :    6444380 :   if (loops->larray)
     211                 :            :     {
     212                 :            :       unsigned i;
     213                 :            :       loop_p loop;
     214                 :            : 
     215                 :            :       /* Free the loop descriptors.  */
     216                 :   15918100 :       FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
     217                 :            :         {
     218                 :    9473680 :           if (!loop)
     219                 :     178050 :             continue;
     220                 :            : 
     221                 :    9295640 :           flow_loop_free (loop);
     222                 :            :         }
     223                 :            : 
     224                 :   12888800 :       vec_free (loops->larray);
     225                 :            :     }
     226                 :    6444380 : }
     227                 :            : 
     228                 :            : /* Find the nodes contained within the LOOP with header HEADER.
     229                 :            :    Return the number of nodes within the loop.  */
     230                 :            : 
     231                 :            : int
     232                 :   11186500 : flow_loop_nodes_find (basic_block header, class loop *loop)
     233                 :            : {
     234                 :   11186500 :   vec<basic_block> stack = vNULL;
     235                 :   11186500 :   int num_nodes = 1;
     236                 :   11186500 :   edge latch;
     237                 :   11186500 :   edge_iterator latch_ei;
     238                 :            : 
     239                 :   11186500 :   header->loop_father = loop;
     240                 :            : 
     241                 :   34081200 :   FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
     242                 :            :     {
     243                 :   36692500 :       if (latch->src->loop_father == loop
     244                 :   22894700 :           || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
     245                 :   13797800 :         continue;
     246                 :            : 
     247                 :    9096900 :       num_nodes++;
     248                 :    9096900 :       stack.safe_push (latch->src);
     249                 :    9096900 :       latch->src->loop_father = loop;
     250                 :            : 
     251                 :   71308600 :       while (!stack.is_empty ())
     252                 :            :         {
     253                 :   62211700 :           basic_block node;
     254                 :   62211700 :           edge e;
     255                 :   62211700 :           edge_iterator ei;
     256                 :            : 
     257                 :   62211700 :           node = stack.pop ();
     258                 :            : 
     259                 :  147839000 :           FOR_EACH_EDGE (e, ei, node->preds)
     260                 :            :             {
     261                 :   85627300 :               basic_block ancestor = e->src;
     262                 :            : 
     263                 :   85627300 :               if (ancestor->loop_father != loop)
     264                 :            :                 {
     265                 :   53114800 :                   ancestor->loop_father = loop;
     266                 :   53114800 :                   num_nodes++;
     267                 :   53114800 :                   stack.safe_push (ancestor);
     268                 :            :                 }
     269                 :            :             }
     270                 :            :         }
     271                 :            :     }
     272                 :   11186500 :   stack.release ();
     273                 :            : 
     274                 :   11186500 :   return num_nodes;
     275                 :            : }
     276                 :            : 
     277                 :            : /* Records the vector of superloops of the loop LOOP, whose immediate
     278                 :            :    superloop is FATHER.  */
     279                 :            : 
     280                 :            : static void
     281                 :   11542400 : establish_preds (class loop *loop, class loop *father)
     282                 :            : {
     283                 :   11542400 :   loop_p ploop;
     284                 :   11542400 :   unsigned depth = loop_depth (father) + 1;
     285                 :   11542400 :   unsigned i;
     286                 :            : 
     287                 :   11542400 :   loop->superloops = 0;
     288                 :   11542400 :   vec_alloc (loop->superloops, depth);
     289                 :   16898100 :   FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
     290                 :    5355710 :     loop->superloops->quick_push (ploop);
     291                 :   11542400 :   loop->superloops->quick_push (father);
     292                 :            : 
     293                 :   11592400 :   for (ploop = loop->inner; ploop; ploop = ploop->next)
     294                 :      50016 :     establish_preds (ploop, loop);
     295                 :   11542400 : }
     296                 :            : 
     297                 :            : /* Add LOOP to the loop hierarchy tree where FATHER is father of the
     298                 :            :    added loop.  If LOOP has some children, take care of that their
     299                 :            :    pred field will be initialized correctly.  If AFTER is non-null
     300                 :            :    then it's expected it's a pointer into FATHERs inner sibling
     301                 :            :    list and LOOP is added behind AFTER, otherwise it's added in front
     302                 :            :    of FATHERs siblings.  */
     303                 :            : 
     304                 :            : void
     305                 :   11492400 : flow_loop_tree_node_add (class loop *father, class loop *loop,
     306                 :            :                          class loop *after)
     307                 :            : {
     308                 :   11492400 :   if (after)
     309                 :            :     {
     310                 :       1881 :       loop->next = after->next;
     311                 :       1881 :       after->next = loop;
     312                 :            :     }
     313                 :            :   else
     314                 :            :     {
     315                 :   11490500 :       loop->next = father->inner;
     316                 :   11490500 :       father->inner = loop;
     317                 :            :     }
     318                 :            : 
     319                 :   11492400 :   establish_preds (loop, father);
     320                 :   11492400 : }
     321                 :            : 
     322                 :            : /* Remove LOOP from the loop hierarchy tree.  */
     323                 :            : 
     324                 :            : void
     325                 :    8629590 : flow_loop_tree_node_remove (class loop *loop)
     326                 :            : {
     327                 :    8629590 :   class loop *prev, *father;
     328                 :            : 
     329                 :    8629590 :   father = loop_outer (loop);
     330                 :            : 
     331                 :            :   /* Remove loop from the list of sons.  */
     332                 :    8629590 :   if (father->inner == loop)
     333                 :    4515980 :     father->inner = loop->next;
     334                 :            :   else
     335                 :            :     {
     336                 :   59535900 :       for (prev = father->inner; prev->next != loop; prev = prev->next)
     337                 :   55422200 :         continue;
     338                 :    4113620 :       prev->next = loop->next;
     339                 :            :     }
     340                 :            : 
     341                 :    8629590 :   loop->superloops = NULL;
     342                 :    8629590 : }
     343                 :            : 
     344                 :            : /* Allocates and returns new loop structure.  */
     345                 :            : 
     346                 :            : class loop *
     347                 :    9528170 : alloc_loop (void)
     348                 :            : {
     349                 :    9528170 :   class loop *loop = ggc_cleared_alloc<class loop> ();
     350                 :            : 
     351                 :    9528170 :   loop->exits = ggc_cleared_alloc<loop_exit> ();
     352                 :    9528170 :   loop->exits->next = loop->exits->prev = loop->exits;
     353                 :    9528170 :   loop->can_be_parallel = false;
     354                 :    9528170 :   loop->constraints = 0;
     355                 :    9528170 :   loop->nb_iterations_upper_bound = 0;
     356                 :    9528170 :   loop->nb_iterations_likely_upper_bound = 0;
     357                 :    9528170 :   loop->nb_iterations_estimate = 0;
     358                 :    9528170 :   return loop;
     359                 :            : }
     360                 :            : 
     361                 :            : /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
     362                 :            :    (including the root of the loop tree).  */
     363                 :            : 
     364                 :            : void
     365                 :    6534640 : init_loops_structure (struct function *fn,
     366                 :            :                       struct loops *loops, unsigned num_loops)
     367                 :            : {
     368                 :    6534640 :   class loop *root;
     369                 :            : 
     370                 :    6534640 :   memset (loops, 0, sizeof *loops);
     371                 :    6534640 :   vec_alloc (loops->larray, num_loops);
     372                 :            : 
     373                 :            :   /* Dummy loop containing whole function.  */
     374                 :    6534640 :   root = alloc_loop ();
     375                 :    6534640 :   root->num_nodes = n_basic_blocks_for_fn (fn);
     376                 :    6534640 :   root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
     377                 :    6534640 :   root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
     378                 :    6534640 :   ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
     379                 :    6534640 :   EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
     380                 :            : 
     381                 :    6534640 :   loops->larray->quick_push (root);
     382                 :    6534640 :   loops->tree_root = root;
     383                 :    6534640 : }
     384                 :            : 
     385                 :            : /* Returns whether HEADER is a loop header.  */
     386                 :            : 
     387                 :            : bool
     388                 : 2195950000 : bb_loop_header_p (basic_block header)
     389                 :            : {
     390                 : 2195950000 :   edge_iterator ei;
     391                 : 2195950000 :   edge e;
     392                 :            : 
     393                 :            :   /* If we have an abnormal predecessor, do not consider the
     394                 :            :      loop (not worth the problems).  */
     395                 : 2195950000 :   if (bb_has_abnormal_pred (header))
     396                 :            :     return false;
     397                 :            : 
     398                 :            :   /* Look for back edges where a predecessor is dominated
     399                 :            :      by this block.  A natural loop has a single entry
     400                 :            :      node (header) that dominates all the nodes in the
     401                 :            :      loop.  It also has single back edge to the header
     402                 :            :      from a latch node.  */
     403                 : 5075310000 :   FOR_EACH_EDGE (e, ei, header->preds)
     404                 :            :     {
     405                 : 3107170000 :       basic_block latch = e->src;
     406                 : 3107170000 :       if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     407                 : 3107170000 :           && dominated_by_p (CDI_DOMINATORS, latch, header))
     408                 :            :         return true;
     409                 :            :     }
     410                 :            : 
     411                 :            :   return false;
     412                 :            : }
     413                 :            : 
     414                 :            : /* Find all the natural loops in the function and save in LOOPS structure and
     415                 :            :    recalculate loop_father information in basic block structures.
     416                 :            :    If LOOPS is non-NULL then the loop structures for already recorded loops
     417                 :            :    will be re-used and their number will not change.  We assume that no
     418                 :            :    stale loops exist in LOOPS.
     419                 :            :    When LOOPS is NULL it is allocated and re-built from scratch.
     420                 :            :    Return the built LOOPS structure.  */
     421                 :            : 
     422                 :            : struct loops *
     423                 :   13483600 : flow_loops_find (struct loops *loops)
     424                 :            : {
     425                 :   13483600 :   bool from_scratch = (loops == NULL);
     426                 :   13483600 :   int *rc_order;
     427                 :   13483600 :   int b;
     428                 :   13483600 :   unsigned i;
     429                 :            : 
     430                 :            :   /* Ensure that the dominators are computed.  */
     431                 :   13483600 :   calculate_dominance_info (CDI_DOMINATORS);
     432                 :            : 
     433                 :   13483600 :   if (!loops)
     434                 :            :     {
     435                 :    6411960 :       loops = ggc_cleared_alloc<struct loops> ();
     436                 :    6411960 :       init_loops_structure (cfun, loops, 1);
     437                 :            :     }
     438                 :            : 
     439                 :            :   /* Ensure that loop exits were released.  */
     440                 :   13483600 :   gcc_assert (loops->exits == NULL);
     441                 :            : 
     442                 :            :   /* Taking care of this degenerate case makes the rest of
     443                 :            :      this code simpler.  */
     444                 :   13483600 :   if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
     445                 :            :     return loops;
     446                 :            : 
     447                 :            :   /* The root loop node contains all basic-blocks.  */
     448                 :   13355400 :   loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun);
     449                 :            : 
     450                 :            :   /* Compute depth first search order of the CFG so that outer
     451                 :            :      natural loops will be found before inner natural loops.  */
     452                 :   13355400 :   rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
     453                 :   13355400 :   pre_and_rev_post_order_compute (NULL, rc_order, false);
     454                 :            : 
     455                 :            :   /* Gather all loop headers in reverse completion order and allocate
     456                 :            :      loop structures for loops that are not already present.  */
     457                 :   13355400 :   auto_vec<loop_p> larray (loops->larray->length ());
     458                 :  204893000 :   for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
     459                 :            :     {
     460                 :  191538000 :       basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
     461                 :  191538000 :       if (bb_loop_header_p (header))
     462                 :            :         {
     463                 :   11186500 :           class loop *loop;
     464                 :            : 
     465                 :            :           /* The current active loop tree has valid loop-fathers for
     466                 :            :              header blocks.  */
     467                 :   11186500 :           if (!from_scratch
     468                 :    8462200 :               && header->loop_father->header == header)
     469                 :            :             {
     470                 :    8446610 :               loop = header->loop_father;
     471                 :            :               /* If we found an existing loop remove it from the
     472                 :            :                  loop tree.  It is going to be inserted again
     473                 :            :                  below.  */
     474                 :    8446610 :               flow_loop_tree_node_remove (loop);
     475                 :            :             }
     476                 :            :           else
     477                 :            :             {
     478                 :            :               /* Otherwise allocate a new loop structure for the loop.  */
     479                 :    2739890 :               loop = alloc_loop ();
     480                 :            :               /* ???  We could re-use unused loop slots here.  */
     481                 :    2739890 :               loop->num = loops->larray->length ();
     482                 :    2739890 :               vec_safe_push (loops->larray, loop);
     483                 :    2739890 :               loop->header = header;
     484                 :            : 
     485                 :    2739890 :               if (!from_scratch
     486                 :    2739890 :                   && dump_file && (dump_flags & TDF_DETAILS))
     487                 :         14 :                 fprintf (dump_file, "flow_loops_find: discovered new "
     488                 :            :                          "loop %d with header %d\n",
     489                 :            :                          loop->num, header->index);
     490                 :            :             }
     491                 :            :           /* Reset latch, we recompute it below.  */
     492                 :   11186500 :           loop->latch = NULL;
     493                 :   11186500 :           larray.safe_push (loop);
     494                 :            :         }
     495                 :            : 
     496                 :            :       /* Make blocks part of the loop root node at start.  */
     497                 :  191538000 :       header->loop_father = loops->tree_root;
     498                 :            :     }
     499                 :            : 
     500                 :   13355400 :   free (rc_order);
     501                 :            : 
     502                 :            :   /* Now iterate over the loops found, insert them into the loop tree
     503                 :            :      and assign basic-block ownership.  */
     504                 :   49083800 :   for (i = 0; i < larray.length (); ++i)
     505                 :            :     {
     506                 :   11186500 :       class loop *loop = larray[i];
     507                 :   11186500 :       basic_block header = loop->header;
     508                 :   11186500 :       edge_iterator ei;
     509                 :   11186500 :       edge e;
     510                 :            : 
     511                 :   11186500 :       flow_loop_tree_node_add (header->loop_father, loop);
     512                 :   11186500 :       loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
     513                 :            : 
     514                 :            :       /* Look for the latch for this header block, if it has just a
     515                 :            :          single one.  */
     516                 :   33824300 :       FOR_EACH_EDGE (e, ei, header->preds)
     517                 :            :         {
     518                 :   22805600 :           basic_block latch = e->src;
     519                 :            : 
     520                 :   22805600 :           if (flow_bb_inside_loop_p (loop, latch))
     521                 :            :             {
     522                 :   11354400 :               if (loop->latch != NULL)
     523                 :            :                 {
     524                 :            :                   /* More than one latch edge.  */
     525                 :     167851 :                   loop->latch = NULL;
     526                 :     167851 :                   break;
     527                 :            :                 }
     528                 :   11186500 :               loop->latch = latch;
     529                 :            :             }
     530                 :            :         }
     531                 :            :     }
     532                 :            : 
     533                 :   13355400 :   return loops;
     534                 :            : }
     535                 :            : 
     536                 :            : /* qsort helper for sort_sibling_loops.  */
     537                 :            : 
     538                 :            : static int *sort_sibling_loops_cmp_rpo;
     539                 :            : static int
     540                 :       2381 : sort_sibling_loops_cmp (const void *la_, const void *lb_)
     541                 :            : {
     542                 :       2381 :   const class loop *la = *(const class loop * const *)la_;
     543                 :       2381 :   const class loop *lb = *(const class loop * const *)lb_;
     544                 :       2381 :   return (sort_sibling_loops_cmp_rpo[la->header->index]
     545                 :       2381 :           - sort_sibling_loops_cmp_rpo[lb->header->index]);
     546                 :            : }
     547                 :            : 
     548                 :            : /* Sort sibling loops in RPO order.  */
     549                 :            : 
     550                 :            : void
     551                 :        548 : sort_sibling_loops (function *fn)
     552                 :            : {
     553                 :            :   /* Match flow_loops_find in the order we sort sibling loops.  */
     554                 :        548 :   sort_sibling_loops_cmp_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
     555                 :        548 :   int *rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
     556                 :        548 :   pre_and_rev_post_order_compute_fn (fn, NULL, rc_order, false);
     557                 :       7606 :   for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
     558                 :       7058 :     sort_sibling_loops_cmp_rpo[rc_order[i]] = i;
     559                 :        548 :   free (rc_order);
     560                 :            : 
     561                 :        548 :   auto_vec<loop_p, 3> siblings;
     562                 :        548 :   loop_p loop;
     563                 :       2421 :   FOR_EACH_LOOP_FN (fn, loop, LI_INCLUDE_ROOT)
     564                 :       1873 :     if (loop->inner && loop->inner->next)
     565                 :            :       {
     566                 :        213 :         loop_p sibling = loop->inner;
     567                 :        560 :         do
     568                 :            :           {
     569                 :        560 :             siblings.safe_push (sibling);
     570                 :        560 :             sibling = sibling->next;
     571                 :            :           }
     572                 :        560 :         while (sibling);
     573                 :        213 :         siblings.qsort (sort_sibling_loops_cmp);
     574                 :        213 :         loop_p *siblingp = &loop->inner;
     575                 :       1546 :         for (unsigned i = 0; i < siblings.length (); ++i)
     576                 :            :           {
     577                 :        560 :             *siblingp = siblings[i];
     578                 :        560 :             siblingp = &(*siblingp)->next;
     579                 :            :           }
     580                 :        213 :         *siblingp = NULL;
     581                 :        213 :         siblings.truncate (0);
     582                 :            :       }
     583                 :            : 
     584                 :        548 :   free (sort_sibling_loops_cmp_rpo);
     585                 :        548 :   sort_sibling_loops_cmp_rpo = NULL;
     586                 :        548 : }
     587                 :            : 
     588                 :            : /* Ratio of frequencies of edges so that one of more latch edges is
     589                 :            :    considered to belong to inner loop with same header.  */
     590                 :            : #define HEAVY_EDGE_RATIO 8
     591                 :            : 
     592                 :            : /* Minimum number of samples for that we apply
     593                 :            :    find_subloop_latch_edge_by_profile heuristics.  */
     594                 :            : #define HEAVY_EDGE_MIN_SAMPLES 10
     595                 :            : 
     596                 :            : /* If the profile info is available, finds an edge in LATCHES that much more
     597                 :            :    frequent than the remaining edges.  Returns such an edge, or NULL if we do
     598                 :            :    not find one.
     599                 :            : 
     600                 :            :    We do not use guessed profile here, only the measured one.  The guessed
     601                 :            :    profile is usually too flat and unreliable for this (and it is mostly based
     602                 :            :    on the loop structure of the program, so it does not make much sense to
     603                 :            :    derive the loop structure from it).  */
     604                 :            : 
     605                 :            : static edge
     606                 :      61924 : find_subloop_latch_edge_by_profile (vec<edge> latches)
     607                 :            : {
     608                 :      61924 :   unsigned i;
     609                 :      61924 :   edge e, me = NULL;
     610                 :      61924 :   profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
     611                 :            : 
     612                 :     215258 :   FOR_EACH_VEC_ELT (latches, i, e)
     613                 :            :     {
     614                 :     153334 :       if (e->count ()> mcount)
     615                 :            :         {
     616                 :      51803 :           me = e;
     617                 :      51803 :           mcount = e->count();
     618                 :            :         }
     619                 :     153334 :       tcount += e->count();
     620                 :            :     }
     621                 :            : 
     622                 :      61924 :   if (!tcount.initialized_p () || !(tcount.ipa () > HEAVY_EDGE_MIN_SAMPLES)
     623                 :      61952 :       || (tcount - mcount).apply_scale (HEAVY_EDGE_RATIO, 1) > tcount)
     624                 :      61902 :     return NULL;
     625                 :            : 
     626                 :         22 :   if (dump_file)
     627                 :          0 :     fprintf (dump_file,
     628                 :            :              "Found latch edge %d -> %d using profile information.\n",
     629                 :          0 :              me->src->index, me->dest->index);
     630                 :            :   return me;
     631                 :            : }
     632                 :            : 
     633                 :            : /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
     634                 :            :    on the structure of induction variables.  Returns this edge, or NULL if we
     635                 :            :    do not find any.
     636                 :            : 
     637                 :            :    We are quite conservative, and look just for an obvious simple innermost
     638                 :            :    loop (which is the case where we would lose the most performance by not
     639                 :            :    disambiguating the loop).  More precisely, we look for the following
     640                 :            :    situation: The source of the chosen latch edge dominates sources of all
     641                 :            :    the other latch edges.  Additionally, the header does not contain a phi node
     642                 :            :    such that the argument from the chosen edge is equal to the argument from
     643                 :            :    another edge.  */
     644                 :            : 
     645                 :            : static edge
     646                 :      61165 : find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
     647                 :            : {
     648                 :      61165 :   edge e, latch = latches[0];
     649                 :      61165 :   unsigned i;
     650                 :      61165 :   gphi *phi;
     651                 :      61165 :   gphi_iterator psi;
     652                 :      61165 :   tree lop;
     653                 :      61165 :   basic_block bb;
     654                 :            : 
     655                 :            :   /* Find the candidate for the latch edge.  */
     656                 :     151726 :   for (i = 1; latches.iterate (i, &e); i++)
     657                 :      90561 :     if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
     658                 :      21871 :       latch = e;
     659                 :            : 
     660                 :            :   /* Verify that it dominates all the latch edges.  */
     661                 :     164767 :   FOR_EACH_VEC_ELT (latches, i, e)
     662                 :     135696 :     if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
     663                 :            :       return NULL;
     664                 :            : 
     665                 :            :   /* Check for a phi node that would deny that this is a latch edge of
     666                 :            :      a subloop.  */
     667                 :      49533 :   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
     668                 :            :     {
     669                 :      45895 :       phi = psi.phi ();
     670                 :      45895 :       lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
     671                 :            : 
     672                 :            :       /* Ignore the values that are not changed inside the subloop.  */
     673                 :      55783 :       if (TREE_CODE (lop) != SSA_NAME
     674                 :      45895 :           || SSA_NAME_DEF_STMT (lop) == phi)
     675                 :       9888 :         continue;
     676                 :      36007 :       bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
     677                 :      36007 :       if (!bb || !flow_bb_inside_loop_p (loop, bb))
     678                 :         13 :         continue;
     679                 :            : 
     680                 :      78007 :       FOR_EACH_VEC_ELT (latches, i, e)
     681                 :      57545 :         if (e != latch
     682                 :      57545 :             && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
     683                 :            :           return NULL;
     684                 :            :     }
     685                 :            : 
     686                 :       3638 :   if (dump_file)
     687                 :          0 :     fprintf (dump_file,
     688                 :            :              "Found latch edge %d -> %d using iv structure.\n",
     689                 :          0 :              latch->src->index, latch->dest->index);
     690                 :            :   return latch;
     691                 :            : }
     692                 :            : 
     693                 :            : /* If we can determine that one of the several latch edges of LOOP behaves
     694                 :            :    as a latch edge of a separate subloop, returns this edge.  Otherwise
     695                 :            :    returns NULL.  */
     696                 :            : 
     697                 :            : static edge
     698                 :      65306 : find_subloop_latch_edge (class loop *loop)
     699                 :            : {
     700                 :      65306 :   vec<edge> latches = get_loop_latch_edges (loop);
     701                 :      65306 :   edge latch = NULL;
     702                 :            : 
     703                 :      65306 :   if (latches.length () > 1)
     704                 :            :     {
     705                 :      61924 :       latch = find_subloop_latch_edge_by_profile (latches);
     706                 :            : 
     707                 :      61924 :       if (!latch
     708                 :            :           /* We consider ivs to guess the latch edge only in SSA.  Perhaps we
     709                 :            :              should use cfghook for this, but it is hard to imagine it would
     710                 :            :              be useful elsewhere.  */
     711                 :      61924 :           && current_ir_type () == IR_GIMPLE)
     712                 :      61165 :         latch = find_subloop_latch_edge_by_ivs (loop, latches);
     713                 :            :     }
     714                 :            : 
     715                 :      65306 :   latches.release ();
     716                 :      65306 :   return latch;
     717                 :            : }
     718                 :            : 
     719                 :            : /* Callback for make_forwarder_block.  Returns true if the edge E is marked
     720                 :            :    in the set MFB_REIS_SET.  */
     721                 :            : 
     722                 :            : static hash_set<edge> *mfb_reis_set;
     723                 :            : static bool
     724                 :     219087 : mfb_redirect_edges_in_set (edge e)
     725                 :            : {
     726                 :     219087 :   return mfb_reis_set->contains (e);
     727                 :            : }
     728                 :            : 
     729                 :            : /* Creates a subloop of LOOP with latch edge LATCH.  */
     730                 :            : 
     731                 :            : static void
     732                 :       3660 : form_subloop (class loop *loop, edge latch)
     733                 :            : {
     734                 :       3660 :   edge_iterator ei;
     735                 :       3660 :   edge e, new_entry;
     736                 :       3660 :   class loop *new_loop;
     737                 :            : 
     738                 :       3660 :   mfb_reis_set = new hash_set<edge>;
     739                 :      15353 :   FOR_EACH_EDGE (e, ei, loop->header->preds)
     740                 :            :     {
     741                 :      11693 :       if (e != latch)
     742                 :       8033 :         mfb_reis_set->add (e);
     743                 :            :     }
     744                 :       3660 :   new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
     745                 :            :                                     NULL);
     746                 :       7320 :   delete mfb_reis_set;
     747                 :            : 
     748                 :       3660 :   loop->header = new_entry->src;
     749                 :            : 
     750                 :            :   /* Find the blocks and subloops that belong to the new loop, and add it to
     751                 :            :      the appropriate place in the loop tree.  */
     752                 :       3660 :   new_loop = alloc_loop ();
     753                 :       3660 :   new_loop->header = new_entry->dest;
     754                 :       3660 :   new_loop->latch = latch->src;
     755                 :       3660 :   add_loop (new_loop, loop);
     756                 :       3660 : }
     757                 :            : 
     758                 :            : /* Make all the latch edges of LOOP to go to a single forwarder block --
     759                 :            :    a new latch of LOOP.  */
     760                 :            : 
     761                 :            : static void
     762                 :      61646 : merge_latch_edges (class loop *loop)
     763                 :            : {
     764                 :      61646 :   vec<edge> latches = get_loop_latch_edges (loop);
     765                 :      61646 :   edge latch, e;
     766                 :      61646 :   unsigned i;
     767                 :            : 
     768                 :      61646 :   gcc_assert (latches.length () > 0);
     769                 :            : 
     770                 :      61646 :   if (latches.length () == 1)
     771                 :       3382 :     loop->latch = latches[0]->src;
     772                 :            :   else
     773                 :            :     {
     774                 :      58264 :       if (dump_file)
     775                 :         11 :         fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
     776                 :            : 
     777                 :      58264 :       mfb_reis_set = new hash_set<edge>;
     778                 :     203650 :       FOR_EACH_VEC_ELT (latches, i, e)
     779                 :     145386 :         mfb_reis_set->add (e);
     780                 :      58264 :       latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
     781                 :            :                                     NULL);
     782                 :     116528 :       delete mfb_reis_set;
     783                 :            : 
     784                 :      58264 :       loop->header = latch->dest;
     785                 :      58264 :       loop->latch = latch->src;
     786                 :            :     }
     787                 :            : 
     788                 :      61646 :   latches.release ();
     789                 :      61646 : }
     790                 :            : 
     791                 :            : /* LOOP may have several latch edges.  Transform it into (possibly several)
     792                 :            :    loops with single latch edge.  */
     793                 :            : 
     794                 :            : static void
     795                 :      61646 : disambiguate_multiple_latches (class loop *loop)
     796                 :            : {
     797                 :      61646 :   edge e;
     798                 :            : 
     799                 :            :   /* We eliminate the multiple latches by splitting the header to the forwarder
     800                 :            :      block F and the rest R, and redirecting the edges.  There are two cases:
     801                 :            : 
     802                 :            :      1) If there is a latch edge E that corresponds to a subloop (we guess
     803                 :            :         that based on profile -- if it is taken much more often than the
     804                 :            :         remaining edges; and on trees, using the information about induction
     805                 :            :         variables of the loops), we redirect E to R, all the remaining edges to
     806                 :            :         F, then rescan the loops and try again for the outer loop.
     807                 :            :      2) If there is no such edge, we redirect all latch edges to F, and the
     808                 :            :         entry edges to R, thus making F the single latch of the loop.  */
     809                 :            : 
     810                 :      61646 :   if (dump_file)
     811                 :         11 :     fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
     812                 :            :              loop->num);
     813                 :            : 
     814                 :            :   /* During latch merging, we may need to redirect the entry edges to a new
     815                 :            :      block.  This would cause problems if the entry edge was the one from the
     816                 :            :      entry block.  To avoid having to handle this case specially, split
     817                 :            :      such entry edge.  */
     818                 :      61646 :   e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
     819                 :      61646 :   if (e)
     820                 :       1070 :     split_edge (e);
     821                 :            : 
     822                 :      68966 :   while (1)
     823                 :            :     {
     824                 :      65306 :       e = find_subloop_latch_edge (loop);
     825                 :      65306 :       if (!e)
     826                 :            :         break;
     827                 :            : 
     828                 :       3660 :       form_subloop (loop, e);
     829                 :            :     }
     830                 :            : 
     831                 :      61646 :   merge_latch_edges (loop);
     832                 :      61646 : }
     833                 :            : 
     834                 :            : /* Split loops with multiple latch edges.  */
     835                 :            : 
     836                 :            : void
     837                 :   17746000 : disambiguate_loops_with_multiple_latches (void)
     838                 :            : {
     839                 :   17746000 :   class loop *loop;
     840                 :            : 
     841                 :   26969500 :   FOR_EACH_LOOP (loop, 0)
     842                 :            :     {
     843                 :    9223540 :       if (!loop->latch)
     844                 :      61646 :         disambiguate_multiple_latches (loop);
     845                 :            :     }
     846                 :   17746000 : }
     847                 :            : 
     848                 :            : /* Return nonzero if basic block BB belongs to LOOP.  */
     849                 :            : bool
     850                 : 1657030000 : flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
     851                 :            : {
     852                 : 1657030000 :   class loop *source_loop;
     853                 :            : 
     854                 : 1657030000 :   if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
     855                 : 1657010000 :       || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
     856                 :            :     return 0;
     857                 :            : 
     858                 : 1645360000 :   source_loop = bb->loop_father;
     859                 : 1645360000 :   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
     860                 :            : }
     861                 :            : 
     862                 :            : /* Enumeration predicate for get_loop_body_with_size.  */
     863                 :            : static bool
     864                 :  678060000 : glb_enum_p (const_basic_block bb, const void *glb_loop)
     865                 :            : {
     866                 :  678060000 :   const class loop *const loop = (const class loop *) glb_loop;
     867                 :  678060000 :   return (bb != loop->header
     868                 :  678060000 :           && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
     869                 :            : }
     870                 :            : 
     871                 :            : /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
     872                 :            :    order against direction of edges from latch.  Specially, if
     873                 :            :    header != latch, latch is the 1-st block.  LOOP cannot be the fake
     874                 :            :    loop tree root, and its size must be at most MAX_SIZE.  The blocks
     875                 :            :    in the LOOP body are stored to BODY, and the size of the LOOP is
     876                 :            :    returned.  */
     877                 :            : 
     878                 :            : unsigned
     879                 :  110369000 : get_loop_body_with_size (const class loop *loop, basic_block *body,
     880                 :            :                          unsigned max_size)
     881                 :            : {
     882                 :  110369000 :   return dfs_enumerate_from (loop->header, 1, glb_enum_p,
     883                 :  110369000 :                              body, max_size, loop);
     884                 :            : }
     885                 :            : 
     886                 :            : /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
     887                 :            :    order against direction of edges from latch.  Specially, if
     888                 :            :    header != latch, latch is the 1-st block.  */
     889                 :            : 
     890                 :            : basic_block *
     891                 :    9753410 : get_loop_body (const class loop *loop)
     892                 :            : {
     893                 :    9753410 :   basic_block *body, bb;
     894                 :    9753410 :   unsigned tv = 0;
     895                 :            : 
     896                 :    9753410 :   gcc_assert (loop->num_nodes);
     897                 :            : 
     898                 :    9753410 :   body = XNEWVEC (basic_block, loop->num_nodes);
     899                 :            : 
     900                 :    9753410 :   if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
     901                 :            :     {
     902                 :            :       /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
     903                 :            :          special-case the fake loop that contains the whole function.  */
     904                 :       4552 :       gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
     905                 :       4552 :       body[tv++] = loop->header;
     906                 :       4552 :       body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
     907                 :      22717 :       FOR_EACH_BB_FN (bb, cfun)
     908                 :      18165 :         body[tv++] = bb;
     909                 :            :     }
     910                 :            :   else
     911                 :    9748860 :     tv = get_loop_body_with_size (loop, body, loop->num_nodes);
     912                 :            : 
     913                 :    9753410 :   gcc_assert (tv == loop->num_nodes);
     914                 :    9753410 :   return body;
     915                 :            : }
     916                 :            : 
     917                 :            : /* Fills dominance descendants inside LOOP of the basic block BB into
     918                 :            :    array TOVISIT from index *TV.  */
     919                 :            : 
     920                 :            : static void
     921                 :    6451230 : fill_sons_in_loop (const class loop *loop, basic_block bb,
     922                 :            :                    basic_block *tovisit, int *tv)
     923                 :            : {
     924                 :    9874070 :   basic_block son, postpone = NULL;
     925                 :            : 
     926                 :    9874070 :   tovisit[(*tv)++] = bb;
     927                 :    9874070 :   for (son = first_dom_son (CDI_DOMINATORS, bb);
     928                 :   20177000 :        son;
     929                 :   10302900 :        son = next_dom_son (CDI_DOMINATORS, son))
     930                 :            :     {
     931                 :   10302900 :       if (!flow_bb_inside_loop_p (loop, son))
     932                 :    2031590 :         continue;
     933                 :            : 
     934                 :    8271360 :       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
     935                 :            :         {
     936                 :    3422840 :           postpone = son;
     937                 :    3422840 :           continue;
     938                 :            :         }
     939                 :    4848520 :       fill_sons_in_loop (loop, son, tovisit, tv);
     940                 :            :     }
     941                 :            : 
     942                 :    9874070 :   if (postpone)
     943                 :            :     fill_sons_in_loop (loop, postpone, tovisit, tv);
     944                 :    6451230 : }
     945                 :            : 
     946                 :            : /* Gets body of a LOOP (that must be different from the outermost loop)
     947                 :            :    sorted by dominance relation.  Additionally, if a basic block s dominates
     948                 :            :    the latch, then only blocks dominated by s are be after it.  */
     949                 :            : 
     950                 :            : basic_block *
     951                 :    1602710 : get_loop_body_in_dom_order (const class loop *loop)
     952                 :            : {
     953                 :    1602710 :   basic_block *tovisit;
     954                 :    1602710 :   int tv;
     955                 :            : 
     956                 :    1602710 :   gcc_assert (loop->num_nodes);
     957                 :            : 
     958                 :    1602710 :   tovisit = XNEWVEC (basic_block, loop->num_nodes);
     959                 :            : 
     960                 :    1602710 :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
     961                 :            : 
     962                 :    1602710 :   tv = 0;
     963                 :    1602710 :   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
     964                 :            : 
     965                 :    1602710 :   gcc_assert (tv == (int) loop->num_nodes);
     966                 :            : 
     967                 :    1602710 :   return tovisit;
     968                 :            : }
     969                 :            : 
     970                 :            : /* Gets body of a LOOP sorted via provided BB_COMPARATOR.  */
     971                 :            : 
     972                 :            : basic_block *
     973                 :         50 : get_loop_body_in_custom_order (const class loop *loop,
     974                 :            :                                int (*bb_comparator) (const void *, const void *))
     975                 :            : {
     976                 :         50 :   basic_block *bbs = get_loop_body (loop);
     977                 :            : 
     978                 :         50 :   qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
     979                 :            : 
     980                 :         50 :   return bbs;
     981                 :            : }
     982                 :            : 
     983                 :            : /* Same as above, but use gcc_sort_r instead of qsort.  */
     984                 :            : 
     985                 :            : basic_block *
     986                 :      92520 : get_loop_body_in_custom_order (const class loop *loop, void *data,
     987                 :            :                                int (*bb_comparator) (const void *, const void *, void *))
     988                 :            : {
     989                 :      92520 :   basic_block *bbs = get_loop_body (loop);
     990                 :            : 
     991                 :      92520 :   gcc_sort_r (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator, data);
     992                 :            : 
     993                 :      92520 :   return bbs;
     994                 :            : }
     995                 :            : 
     996                 :            : /* Get body of a LOOP in breadth first sort order.  */
     997                 :            : 
     998                 :            : basic_block *
     999                 :       4932 : get_loop_body_in_bfs_order (const class loop *loop)
    1000                 :            : {
    1001                 :       4932 :   basic_block *blocks;
    1002                 :       4932 :   basic_block bb;
    1003                 :       4932 :   unsigned int i = 1;
    1004                 :       4932 :   unsigned int vc = 0;
    1005                 :            : 
    1006                 :       4932 :   gcc_assert (loop->num_nodes);
    1007                 :       4932 :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
    1008                 :            : 
    1009                 :       4932 :   blocks = XNEWVEC (basic_block, loop->num_nodes);
    1010                 :       4932 :   auto_bitmap visited;
    1011                 :       4932 :   blocks[0] = loop->header;
    1012                 :       4932 :   bitmap_set_bit (visited, loop->header->index);
    1013                 :      28107 :   while (i < loop->num_nodes)
    1014                 :            :     {
    1015                 :      23175 :       edge e;
    1016                 :      23175 :       edge_iterator ei;
    1017                 :      23175 :       gcc_assert (i > vc);
    1018                 :      23175 :       bb = blocks[vc++];
    1019                 :            : 
    1020                 :      58942 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1021                 :            :         {
    1022                 :      35767 :           if (flow_bb_inside_loop_p (loop, e->dest))
    1023                 :            :             {
    1024                 :            :               /* This bb is now visited.  */
    1025                 :      30850 :               if (bitmap_set_bit (visited, e->dest->index))
    1026                 :      24141 :                 blocks[i++] = e->dest;
    1027                 :            :             }
    1028                 :            :         }
    1029                 :            :     }
    1030                 :            : 
    1031                 :       4932 :   return blocks;
    1032                 :            : }
    1033                 :            : 
    1034                 :            : /* Hash function for struct loop_exit.  */
    1035                 :            : 
    1036                 :            : hashval_t
    1037                 :   71308800 : loop_exit_hasher::hash (loop_exit *exit)
    1038                 :            : {
    1039                 :   71308800 :   return htab_hash_pointer (exit->e);
    1040                 :            : }
    1041                 :            : 
    1042                 :            : /* Equality function for struct loop_exit.  Compares with edge.  */
    1043                 :            : 
    1044                 :            : bool
    1045                 :  101473000 : loop_exit_hasher::equal (loop_exit *exit, edge e)
    1046                 :            : {
    1047                 :  101473000 :   return exit->e == e;
    1048                 :            : }
    1049                 :            : 
    1050                 :            : /* Frees the list of loop exit descriptions EX.  */
    1051                 :            : 
    1052                 :            : void
    1053                 :   10753700 : loop_exit_hasher::remove (loop_exit *exit)
    1054                 :            : {
    1055                 :   22532100 :   loop_exit *next;
    1056                 :   22532100 :   for (; exit; exit = next)
    1057                 :            :     {
    1058                 :   11778400 :       next = exit->next_e;
    1059                 :            : 
    1060                 :   11778400 :       exit->next->prev = exit->prev;
    1061                 :   11778400 :       exit->prev->next = exit->next;
    1062                 :            : 
    1063                 :   11778400 :       ggc_free (exit);
    1064                 :            :     }
    1065                 :   10753700 : }
    1066                 :            : 
    1067                 :            : /* Returns the list of records for E as an exit of a loop.  */
    1068                 :            : 
    1069                 :            : static struct loop_exit *
    1070                 :   19336300 : get_exit_descriptions (edge e)
    1071                 :            : {
    1072                 :   19336300 :   return current_loops->exits->find_with_hash (e, htab_hash_pointer (e));
    1073                 :            : }
    1074                 :            : 
    1075                 :            : /* Updates the lists of loop exits in that E appears.
    1076                 :            :    If REMOVED is true, E is being removed, and we
    1077                 :            :    just remove it from the lists of exits.
    1078                 :            :    If NEW_EDGE is true and E is not a loop exit, we
    1079                 :            :    do not try to remove it from loop exit lists.  */
    1080                 :            : 
    1081                 :            : void
    1082                 :  309278000 : rescan_loop_exit (edge e, bool new_edge, bool removed)
    1083                 :            : {
    1084                 :  309278000 :   struct loop_exit *exits = NULL, *exit;
    1085                 :  309278000 :   class loop *aloop, *cloop;
    1086                 :            : 
    1087                 :  309278000 :   if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    1088                 :            :     return;
    1089                 :            : 
    1090                 :  151878000 :   if (!removed
    1091                 :  143883000 :       && e->src->loop_father != NULL
    1092                 :  143883000 :       && e->dest->loop_father != NULL
    1093                 :  294187000 :       && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
    1094                 :            :     {
    1095                 :   22397900 :       cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
    1096                 :   22397900 :       for (aloop = e->src->loop_father;
    1097                 :   34176400 :            aloop != cloop;
    1098                 :   11778400 :            aloop = loop_outer (aloop))
    1099                 :            :         {
    1100                 :   11778400 :           exit = ggc_alloc<loop_exit> ();
    1101                 :   11778400 :           exit->e = e;
    1102                 :            : 
    1103                 :   11778400 :           exit->next = aloop->exits->next;
    1104                 :   11778400 :           exit->prev = aloop->exits;
    1105                 :   11778400 :           exit->next->prev = exit;
    1106                 :   11778400 :           exit->prev->next = exit;
    1107                 :            : 
    1108                 :   11778400 :           exit->next_e = exits;
    1109                 :   11778400 :           exits = exit;
    1110                 :            :         }
    1111                 :            :     }
    1112                 :            : 
    1113                 :  151878000 :   if (!exits && new_edge)
    1114                 :            :     return;
    1115                 :            : 
    1116                 :   21029000 :   loop_exit **slot
    1117                 :   31304300 :     = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
    1118                 :            :                                                  exits ? INSERT : NO_INSERT);
    1119                 :   21029000 :   if (!slot)
    1120                 :            :     return;
    1121                 :            : 
    1122                 :   11454700 :   if (exits)
    1123                 :            :     {
    1124                 :   10753700 :       if (*slot)
    1125                 :     152228 :         loop_exit_hasher::remove (*slot);
    1126                 :   10753700 :       *slot = exits;
    1127                 :            :     }
    1128                 :            :   else
    1129                 :     701073 :     current_loops->exits->clear_slot (slot);
    1130                 :            : }
    1131                 :            : 
    1132                 :            : /* For each loop, record list of exit edges, and start maintaining these
    1133                 :            :    lists.  */
    1134                 :            : 
    1135                 :            : void
    1136                 :   11217900 : record_loop_exits (void)
    1137                 :            : {
    1138                 :   11217900 :   basic_block bb;
    1139                 :   11217900 :   edge_iterator ei;
    1140                 :   11217900 :   edge e;
    1141                 :            : 
    1142                 :   11217900 :   if (!current_loops)
    1143                 :          0 :     return;
    1144                 :            : 
    1145                 :   11217900 :   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    1146                 :            :     return;
    1147                 :   11217900 :   loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
    1148                 :            : 
    1149                 :   11217900 :   gcc_assert (current_loops->exits == NULL);
    1150                 :   11217900 :   current_loops->exits
    1151                 :   22435700 :     = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
    1152                 :            : 
    1153                 :  105488000 :   FOR_EACH_BB_FN (bb, cfun)
    1154                 :            :     {
    1155                 :  226689000 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1156                 :            :         {
    1157                 :  132418000 :           rescan_loop_exit (e, true, false);
    1158                 :            :         }
    1159                 :            :     }
    1160                 :            : }
    1161                 :            : 
    1162                 :            : /* Dumps information about the exit in *SLOT to FILE.
    1163                 :            :    Callback for htab_traverse.  */
    1164                 :            : 
    1165                 :            : int
    1166                 :          0 : dump_recorded_exit (loop_exit **slot, FILE *file)
    1167                 :            : {
    1168                 :          0 :   struct loop_exit *exit = *slot;
    1169                 :          0 :   unsigned n = 0;
    1170                 :          0 :   edge e = exit->e;
    1171                 :            : 
    1172                 :          0 :   for (; exit != NULL; exit = exit->next_e)
    1173                 :          0 :     n++;
    1174                 :            : 
    1175                 :          0 :   fprintf (file, "Edge %d->%d exits %u loops\n",
    1176                 :          0 :            e->src->index, e->dest->index, n);
    1177                 :            : 
    1178                 :          0 :   return 1;
    1179                 :            : }
    1180                 :            : 
    1181                 :            : /* Dumps the recorded exits of loops to FILE.  */
    1182                 :            : 
    1183                 :            : extern void dump_recorded_exits (FILE *);
    1184                 :            : void
    1185                 :          0 : dump_recorded_exits (FILE *file)
    1186                 :            : {
    1187                 :          0 :   if (!current_loops->exits)
    1188                 :            :     return;
    1189                 :          0 :   current_loops->exits->traverse<FILE *, dump_recorded_exit> (file);
    1190                 :            : }
    1191                 :            : 
    1192                 :            : /* Releases lists of loop exits.  */
    1193                 :            : 
    1194                 :            : void
    1195                 :   11217900 : release_recorded_exits (function *fn)
    1196                 :            : {
    1197                 :   11217900 :   gcc_assert (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS));
    1198                 :   11217900 :   loops_for_fn (fn)->exits->empty ();
    1199                 :   11217900 :   loops_for_fn (fn)->exits = NULL;
    1200                 :   11217900 :   loops_state_clear (fn, LOOPS_HAVE_RECORDED_EXITS);
    1201                 :   11217900 : }
    1202                 :            : 
    1203                 :            : /* Returns the list of the exit edges of a LOOP.  */
    1204                 :            : 
    1205                 :            : vec<edge> 
    1206                 :   12104800 : get_loop_exit_edges (const class loop *loop, basic_block *body)
    1207                 :            : {
    1208                 :   12104800 :   vec<edge> edges = vNULL;
    1209                 :   12104800 :   edge e;
    1210                 :   12104800 :   unsigned i;
    1211                 :   12104800 :   edge_iterator ei;
    1212                 :   12104800 :   struct loop_exit *exit;
    1213                 :            : 
    1214                 :   12104800 :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
    1215                 :            : 
    1216                 :            :   /* If we maintain the lists of exits, use them.  Otherwise we must
    1217                 :            :      scan the body of the loop.  */
    1218                 :   12104800 :   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    1219                 :            :     {
    1220                 :   39654300 :       for (exit = loop->exits->next; exit->e; exit = exit->next)
    1221                 :   27793200 :         edges.safe_push (exit->e);
    1222                 :            :     }
    1223                 :            :   else
    1224                 :            :     {
    1225                 :     243805 :       bool body_from_caller = true;
    1226                 :     243805 :       if (!body)
    1227                 :            :         {
    1228                 :          0 :           body = get_loop_body (loop);
    1229                 :          0 :           body_from_caller = false;
    1230                 :            :         }
    1231                 :    1818530 :       for (i = 0; i < loop->num_nodes; i++)
    1232                 :    4082890 :         FOR_EACH_EDGE (e, ei, body[i]->succs)
    1233                 :            :           {
    1234                 :    2508170 :             if (!flow_bb_inside_loop_p (loop, e->dest))
    1235                 :     521535 :               edges.safe_push (e);
    1236                 :            :           }
    1237                 :     243805 :       if (!body_from_caller)
    1238                 :          0 :         free (body);
    1239                 :            :     }
    1240                 :            : 
    1241                 :   12104800 :   return edges;
    1242                 :            : }
    1243                 :            : 
    1244                 :            : /* Counts the number of conditional branches inside LOOP.  */
    1245                 :            : 
    1246                 :            : unsigned
    1247                 :         43 : num_loop_branches (const class loop *loop)
    1248                 :            : {
    1249                 :         43 :   unsigned i, n;
    1250                 :         43 :   basic_block * body;
    1251                 :            : 
    1252                 :         43 :   gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
    1253                 :            : 
    1254                 :         43 :   body = get_loop_body (loop);
    1255                 :         43 :   n = 0;
    1256                 :        135 :   for (i = 0; i < loop->num_nodes; i++)
    1257                 :        136 :     if (EDGE_COUNT (body[i]->succs) >= 2)
    1258                 :         44 :       n++;
    1259                 :         43 :   free (body);
    1260                 :            : 
    1261                 :         43 :   return n;
    1262                 :            : }
    1263                 :            : 
    1264                 :            : /* Adds basic block BB to LOOP.  */
    1265                 :            : void
    1266                 :   24303500 : add_bb_to_loop (basic_block bb, class loop *loop)
    1267                 :            : {
    1268                 :   24303500 :   unsigned i;
    1269                 :   24303500 :   loop_p ploop;
    1270                 :   24303500 :   edge_iterator ei;
    1271                 :   24303500 :   edge e;
    1272                 :            : 
    1273                 :   24303500 :   gcc_assert (bb->loop_father == NULL);
    1274                 :   24303500 :   bb->loop_father = loop;
    1275                 :   24303500 :   loop->num_nodes++;
    1276                 :   35344200 :   FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
    1277                 :   11040600 :     ploop->num_nodes++;
    1278                 :            : 
    1279                 :   50189300 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1280                 :            :     {
    1281                 :   25885800 :       rescan_loop_exit (e, true, false);
    1282                 :            :     }
    1283                 :   40644900 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1284                 :            :     {
    1285                 :   16341400 :       rescan_loop_exit (e, true, false);
    1286                 :            :     }
    1287                 :   24303500 : }
    1288                 :            : 
    1289                 :            : /* Remove basic block BB from loops.  */
    1290                 :            : void
    1291                 :   29903800 : remove_bb_from_loops (basic_block bb)
    1292                 :            : {
    1293                 :   29903800 :   unsigned i;
    1294                 :   29903800 :   class loop *loop = bb->loop_father;
    1295                 :   29903800 :   loop_p ploop;
    1296                 :   29903800 :   edge_iterator ei;
    1297                 :   29903800 :   edge e;
    1298                 :            : 
    1299                 :   29903800 :   gcc_assert (loop != NULL);
    1300                 :   29903800 :   loop->num_nodes--;
    1301                 :   41442700 :   FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
    1302                 :   11538900 :     ploop->num_nodes--;
    1303                 :   29903800 :   bb->loop_father = NULL;
    1304                 :            : 
    1305                 :   45942800 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1306                 :            :     {
    1307                 :   16039000 :       rescan_loop_exit (e, false, true);
    1308                 :            :     }
    1309                 :   41021200 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1310                 :            :     {
    1311                 :   11117400 :       rescan_loop_exit (e, false, true);
    1312                 :            :     }
    1313                 :   29903800 : }
    1314                 :            : 
    1315                 :            : /* Finds nearest common ancestor in loop tree for given loops.  */
    1316                 :            : class loop *
    1317                 :  109772000 : find_common_loop (class loop *loop_s, class loop *loop_d)
    1318                 :            : {
    1319                 :  109772000 :   unsigned sdepth, ddepth;
    1320                 :            : 
    1321                 :  109772000 :   if (!loop_s) return loop_d;
    1322                 :  109771000 :   if (!loop_d) return loop_s;
    1323                 :            : 
    1324                 :  109771000 :   sdepth = loop_depth (loop_s);
    1325                 :  109771000 :   ddepth = loop_depth (loop_d);
    1326                 :            : 
    1327                 :  109771000 :   if (sdepth < ddepth)
    1328                 :    3393980 :     loop_d = (*loop_d->superloops)[sdepth];
    1329                 :  106377000 :   else if (sdepth > ddepth)
    1330                 :   49685400 :     loop_s = (*loop_s->superloops)[ddepth];
    1331                 :            : 
    1332                 :  110223000 :   while (loop_s != loop_d)
    1333                 :            :     {
    1334                 :     452024 :       loop_s = loop_outer (loop_s);
    1335                 :     452024 :       loop_d = loop_outer (loop_d);
    1336                 :            :     }
    1337                 :            :   return loop_s;
    1338                 :            : }
    1339                 :            : 
    1340                 :            : /* Removes LOOP from structures and frees its data.  */
    1341                 :            : 
    1342                 :            : void
    1343                 :      79498 : delete_loop (class loop *loop)
    1344                 :            : {
    1345                 :            :   /* Remove the loop from structure.  */
    1346                 :      79498 :   flow_loop_tree_node_remove (loop);
    1347                 :            : 
    1348                 :            :   /* Remove loop from loops array.  */
    1349                 :      79498 :   (*current_loops->larray)[loop->num] = NULL;
    1350                 :            : 
    1351                 :            :   /* Free loop data.  */
    1352                 :      79498 :   flow_loop_free (loop);
    1353                 :      79498 : }
    1354                 :            : 
    1355                 :            : /* Cancels the LOOP; it must be innermost one.  */
    1356                 :            : 
    1357                 :            : static void
    1358                 :       7949 : cancel_loop (class loop *loop)
    1359                 :            : {
    1360                 :       7949 :   basic_block *bbs;
    1361                 :       7949 :   unsigned i;
    1362                 :       7949 :   class loop *outer = loop_outer (loop);
    1363                 :            : 
    1364                 :       7949 :   gcc_assert (!loop->inner);
    1365                 :            : 
    1366                 :            :   /* Move blocks up one level (they should be removed as soon as possible).  */
    1367                 :       7949 :   bbs = get_loop_body (loop);
    1368                 :      25212 :   for (i = 0; i < loop->num_nodes; i++)
    1369                 :      17263 :     bbs[i]->loop_father = outer;
    1370                 :            : 
    1371                 :       7949 :   free (bbs);
    1372                 :       7949 :   delete_loop (loop);
    1373                 :       7949 : }
    1374                 :            : 
    1375                 :            : /* Cancels LOOP and all its subloops.  */
    1376                 :            : void
    1377                 :       7949 : cancel_loop_tree (class loop *loop)
    1378                 :            : {
    1379                 :       8394 :   while (loop->inner)
    1380                 :        445 :     cancel_loop_tree (loop->inner);
    1381                 :       7949 :   cancel_loop (loop);
    1382                 :       7949 : }
    1383                 :            : 
    1384                 :            : /* Disable warnings about missing quoting in GCC diagnostics for
    1385                 :            :    the verification errors.  Their format strings don't follow GCC
    1386                 :            :    diagnostic conventions and the calls are ultimately followed by
    1387                 :            :    a deliberate ICE triggered by a failed assertion.  */
    1388                 :            : #if __GNUC__ >= 10
    1389                 :            : #  pragma GCC diagnostic push
    1390                 :            : #  pragma GCC diagnostic ignored "-Wformat-diag"
    1391                 :            : #endif
    1392                 :            : 
    1393                 :            : /* Checks that information about loops is correct
    1394                 :            :      -- sizes of loops are all right
    1395                 :            :      -- results of get_loop_body really belong to the loop
    1396                 :            :      -- loop header have just single entry edge and single latch edge
    1397                 :            :      -- loop latches have only single successor that is header of their loop
    1398                 :            :      -- irreducible loops are correctly marked
    1399                 :            :      -- the cached loop depth and loop father of each bb is correct
    1400                 :            :   */
    1401                 :            : DEBUG_FUNCTION void
    1402                 :  217612000 : verify_loop_structure (void)
    1403                 :            : {
    1404                 :  217612000 :   unsigned *sizes, i, j;
    1405                 :  217612000 :   basic_block bb, *bbs;
    1406                 :  217612000 :   class loop *loop;
    1407                 :  217612000 :   int err = 0;
    1408                 :  217612000 :   edge e;
    1409                 :  217612000 :   unsigned num = number_of_loops (cfun);
    1410                 :  217612000 :   struct loop_exit *exit, *mexit;
    1411                 :  217612000 :   bool dom_available = dom_info_available_p (CDI_DOMINATORS);
    1412                 :            : 
    1413                 :  217612000 :   if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
    1414                 :            :     {
    1415                 :          0 :       error ("loop verification on loop tree that needs fixup");
    1416                 :          0 :       err = 1;
    1417                 :            :     }
    1418                 :            : 
    1419                 :            :   /* We need up-to-date dominators, compute or verify them.  */
    1420                 :  217612000 :   if (!dom_available)
    1421                 :   52460700 :     calculate_dominance_info (CDI_DOMINATORS);
    1422                 :            :   else
    1423                 :  165151000 :     verify_dominators (CDI_DOMINATORS);
    1424                 :            : 
    1425                 :            :   /* Check the loop tree root.  */
    1426                 :  217612000 :   if (current_loops->tree_root->header != ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1427                 :  217612000 :       || current_loops->tree_root->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
    1428                 :  217612000 :       || (current_loops->tree_root->num_nodes
    1429                 :  217612000 :           != (unsigned) n_basic_blocks_for_fn (cfun)))
    1430                 :            :     {
    1431                 :          0 :       error ("corrupt loop tree root");
    1432                 :          0 :       err = 1;
    1433                 :            :     }
    1434                 :            : 
    1435                 :            :   /* Check the headers.  */
    1436                 : 2096870000 :   FOR_EACH_BB_FN (bb, cfun)
    1437                 : 1879260000 :     if (bb_loop_header_p (bb))
    1438                 :            :       {
    1439                 :  100547000 :         if (bb->loop_father->header == NULL)
    1440                 :            :           {
    1441                 :          0 :             error ("loop with header %d marked for removal", bb->index);
    1442                 :          0 :             err = 1;
    1443                 :            :           }
    1444                 :  100547000 :         else if (bb->loop_father->header != bb)
    1445                 :            :           {
    1446                 :          0 :             error ("loop with header %d not in loop tree", bb->index);
    1447                 :          0 :             err = 1;
    1448                 :            :           }
    1449                 :            :       }
    1450                 : 1778710000 :     else if (bb->loop_father->header == bb)
    1451                 :            :       {
    1452                 :          0 :         error ("non-loop with header %d not marked for removal", bb->index);
    1453                 :          0 :         err = 1;
    1454                 :            :       }
    1455                 :            : 
    1456                 :            :   /* Check the recorded loop father and sizes of loops.  */
    1457                 :  217612000 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
    1458                 :  217612000 :   bitmap_clear (visited);
    1459                 :  217612000 :   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
    1460                 :  318159000 :   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
    1461                 :            :     {
    1462                 :  100547000 :       unsigned n;
    1463                 :            : 
    1464                 :  100547000 :       if (loop->header == NULL)
    1465                 :            :         {
    1466                 :          0 :           error ("removed loop %d in loop tree", loop->num);
    1467                 :          0 :           err = 1;
    1468                 :          0 :           continue;
    1469                 :            :         }
    1470                 :            : 
    1471                 :  100547000 :       n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
    1472                 :  100547000 :       if (loop->num_nodes != n)
    1473                 :            :         {
    1474                 :          0 :           error ("size of loop %d should be %d, not %d",
    1475                 :            :                  loop->num, n, loop->num_nodes);
    1476                 :          0 :           err = 1;
    1477                 :            :         }
    1478                 :            : 
    1479                 :  719550000 :       for (j = 0; j < n; j++)
    1480                 :            :         {
    1481                 :  619003000 :           bb = bbs[j];
    1482                 :            : 
    1483                 :  619003000 :           if (!flow_bb_inside_loop_p (loop, bb))
    1484                 :            :             {
    1485                 :          0 :               error ("bb %d does not belong to loop %d",
    1486                 :            :                      bb->index, loop->num);
    1487                 :          0 :               err = 1;
    1488                 :            :             }
    1489                 :            : 
    1490                 :            :           /* Ignore this block if it is in an inner loop.  */
    1491                 :  619003000 :           if (bitmap_bit_p (visited, bb->index))
    1492                 :  155256000 :             continue;
    1493                 :  463747000 :           bitmap_set_bit (visited, bb->index);
    1494                 :            : 
    1495                 :  463747000 :           if (bb->loop_father != loop)
    1496                 :            :             {
    1497                 :          0 :               error ("bb %d has father loop %d, should be loop %d",
    1498                 :            :                      bb->index, bb->loop_father->num, loop->num);
    1499                 :          0 :               err = 1;
    1500                 :            :             }
    1501                 :            :         }
    1502                 :            :     }
    1503                 :  217612000 :   free (bbs);
    1504                 :            : 
    1505                 :            :   /* Check headers and latches.  */
    1506                 :  318159000 :   FOR_EACH_LOOP (loop, 0)
    1507                 :            :     {
    1508                 :  100547000 :       i = loop->num;
    1509                 :  100547000 :       if (loop->header == NULL)
    1510                 :          0 :         continue;
    1511                 :  100547000 :       if (!bb_loop_header_p (loop->header))
    1512                 :            :         {
    1513                 :          0 :           error ("loop %d%'s header is not a loop header", i);
    1514                 :          0 :           err = 1;
    1515                 :            :         }
    1516                 :  100547000 :       if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
    1517                 :  100547000 :           && EDGE_COUNT (loop->header->preds) != 2)
    1518                 :            :         {
    1519                 :          0 :           error ("loop %d%'s header does not have exactly 2 entries", i);
    1520                 :          0 :           err = 1;
    1521                 :            :         }
    1522                 :  100547000 :       if (loop->latch)
    1523                 :            :         {
    1524                 :   99967800 :           if (!find_edge (loop->latch, loop->header))
    1525                 :            :             {
    1526                 :          0 :               error ("loop %d%'s latch does not have an edge to its header", i);
    1527                 :          0 :               err = 1;
    1528                 :            :             }
    1529                 :   99967800 :           if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
    1530                 :            :             {
    1531                 :          0 :               error ("loop %d%'s latch is not dominated by its header", i);
    1532                 :          0 :               err = 1;
    1533                 :            :             }
    1534                 :            :         }
    1535                 :  100547000 :       if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
    1536                 :            :         {
    1537                 :   13877500 :           if (!single_succ_p (loop->latch))
    1538                 :            :             {
    1539                 :          0 :               error ("loop %d%'s latch does not have exactly 1 successor", i);
    1540                 :          0 :               err = 1;
    1541                 :            :             }
    1542                 :   13877500 :           if (single_succ (loop->latch) != loop->header)
    1543                 :            :             {
    1544                 :          0 :               error ("loop %d%'s latch does not have header as successor", i);
    1545                 :          0 :               err = 1;
    1546                 :            :             }
    1547                 :   13877500 :           if (loop->latch->loop_father != loop)
    1548                 :            :             {
    1549                 :          0 :               error ("loop %d%'s latch does not belong directly to it", i);
    1550                 :          0 :               err = 1;
    1551                 :            :             }
    1552                 :            :         }
    1553                 :  100547000 :       if (loop->header->loop_father != loop)
    1554                 :            :         {
    1555                 :          0 :           error ("loop %d%'s header does not belong directly to it", i);
    1556                 :          0 :           err = 1;
    1557                 :            :         }
    1558                 :  100547000 :       if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
    1559                 :  100547000 :           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
    1560                 :            :         {
    1561                 :          0 :           error ("loop %d%'s latch is marked as part of irreducible region", i);
    1562                 :          0 :           err = 1;
    1563                 :            :         }
    1564                 :            :     }
    1565                 :            : 
    1566                 :            :   /* Check irreducible loops.  */
    1567                 :  217612000 :   if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
    1568                 :            :     {
    1569                 :   34774500 :       auto_edge_flag saved_irr_mask (cfun);
    1570                 :            :       /* Record old info.  */
    1571                 :   34774500 :       auto_sbitmap irreds (last_basic_block_for_fn (cfun));
    1572                 :  200718000 :       FOR_EACH_BB_FN (bb, cfun)
    1573                 :            :         {
    1574                 :  183331000 :           edge_iterator ei;
    1575                 :  183331000 :           if (bb->flags & BB_IRREDUCIBLE_LOOP)
    1576                 :     296558 :             bitmap_set_bit (irreds, bb->index);
    1577                 :            :           else
    1578                 :  183035000 :             bitmap_clear_bit (irreds, bb->index);
    1579                 :  438910000 :           FOR_EACH_EDGE (e, ei, bb->succs)
    1580                 :  255579000 :             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
    1581                 :     455081 :               e->flags |= saved_irr_mask;
    1582                 :            :         }
    1583                 :            : 
    1584                 :            :       /* Recount it.  */
    1585                 :   17387200 :       mark_irreducible_loops ();
    1586                 :            : 
    1587                 :            :       /* Compare.  */
    1588                 :  200718000 :       FOR_EACH_BB_FN (bb, cfun)
    1589                 :            :         {
    1590                 :  183331000 :           edge_iterator ei;
    1591                 :            : 
    1592                 :  183331000 :           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
    1593                 :  183331000 :               && !bitmap_bit_p (irreds, bb->index))
    1594                 :            :             {
    1595                 :          0 :               error ("basic block %d should be marked irreducible", bb->index);
    1596                 :          0 :               err = 1;
    1597                 :            :             }
    1598                 :  183331000 :           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
    1599                 :  183331000 :               && bitmap_bit_p (irreds, bb->index))
    1600                 :            :             {
    1601                 :          0 :               error ("basic block %d should not be marked irreducible", bb->index);
    1602                 :          0 :               err = 1;
    1603                 :            :             }
    1604                 :  438910000 :           FOR_EACH_EDGE (e, ei, bb->succs)
    1605                 :            :             {
    1606                 :  255579000 :               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
    1607                 :  255579000 :                   && !(e->flags & saved_irr_mask))
    1608                 :            :                 {
    1609                 :          0 :                   error ("edge from %d to %d should be marked irreducible",
    1610                 :          0 :                          e->src->index, e->dest->index);
    1611                 :          0 :                   err = 1;
    1612                 :            :                 }
    1613                 :  255579000 :               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
    1614                 :  255579000 :                        && (e->flags & saved_irr_mask))
    1615                 :            :                 {
    1616                 :          0 :                   error ("edge from %d to %d should not be marked irreducible",
    1617                 :          0 :                          e->src->index, e->dest->index);
    1618                 :          0 :                   err = 1;
    1619                 :            :                 }
    1620                 :  255579000 :               e->flags &= ~saved_irr_mask;
    1621                 :            :             }
    1622                 :            :         }
    1623                 :            :     }
    1624                 :            : 
    1625                 :            :   /* Check the recorded loop exits.  */
    1626                 :  318159000 :   FOR_EACH_LOOP (loop, 0)
    1627                 :            :     {
    1628                 :  100547000 :       if (!loop->exits || loop->exits->e != NULL)
    1629                 :            :         {
    1630                 :          0 :           error ("corrupted head of the exits list of loop %d",
    1631                 :            :                  loop->num);
    1632                 :          0 :           err = 1;
    1633                 :            :         }
    1634                 :            :       else
    1635                 :            :         {
    1636                 :            :           /* Check that the list forms a cycle, and all elements except
    1637                 :            :              for the head are nonnull.  */
    1638                 :  100547000 :           for (mexit = loop->exits, exit = mexit->next, i = 0;
    1639                 :  121718000 :                exit->e && exit != mexit;
    1640                 :   21171000 :                exit = exit->next)
    1641                 :            :             {
    1642                 :   21171000 :               if (i++ & 1)
    1643                 :    6660600 :                 mexit = mexit->next;
    1644                 :            :             }
    1645                 :            : 
    1646                 :  100547000 :           if (exit != loop->exits)
    1647                 :            :             {
    1648                 :          0 :               error ("corrupted exits list of loop %d", loop->num);
    1649                 :          0 :               err = 1;
    1650                 :            :             }
    1651                 :            :         }
    1652                 :            : 
    1653                 :  100547000 :       if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    1654                 :            :         {
    1655                 :   89831100 :           if (loop->exits->next != loop->exits)
    1656                 :            :             {
    1657                 :          0 :               error ("nonempty exits list of loop %d, but exits are not recorded",
    1658                 :            :                      loop->num);
    1659                 :          0 :               err = 1;
    1660                 :            :             }
    1661                 :            :         }
    1662                 :            :     }
    1663                 :            : 
    1664                 :  217612000 :   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    1665                 :            :     {
    1666                 :   15169900 :       unsigned n_exits = 0, eloops;
    1667                 :            : 
    1668                 :   15169900 :       sizes = XCNEWVEC (unsigned, num);
    1669                 :   15169900 :       memset (sizes, 0, sizeof (unsigned) * num);
    1670                 :  186656000 :       FOR_EACH_BB_FN (bb, cfun)
    1671                 :            :         {
    1672                 :  171486000 :           edge_iterator ei;
    1673                 :  171486000 :           if (bb->loop_father == current_loops->tree_root)
    1674                 :  118793000 :             continue;
    1675                 :  134877000 :           FOR_EACH_EDGE (e, ei, bb->succs)
    1676                 :            :             {
    1677                 :   82183600 :               if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
    1678                 :   62847300 :                 continue;
    1679                 :            : 
    1680                 :   19336300 :               n_exits++;
    1681                 :   19336300 :               exit = get_exit_descriptions (e);
    1682                 :   19336300 :               if (!exit)
    1683                 :            :                 {
    1684                 :          0 :                   error ("exit %d->%d not recorded",
    1685                 :          0 :                          e->src->index, e->dest->index);
    1686                 :          0 :                   err = 1;
    1687                 :            :                 }
    1688                 :   19336300 :               eloops = 0;
    1689                 :   40507300 :               for (; exit; exit = exit->next_e)
    1690                 :   21171000 :                 eloops++;
    1691                 :            : 
    1692                 :   19336300 :               for (loop = bb->loop_father;
    1693                 :   40507300 :                    loop != e->dest->loop_father
    1694                 :            :                    /* When a loop exit is also an entry edge which
    1695                 :            :                       can happen when avoiding CFG manipulations
    1696                 :            :                       then the last loop exited is the outer loop
    1697                 :            :                       of the loop entered.  */
    1698                 :   43691300 :                    && loop != loop_outer (e->dest->loop_father);
    1699                 :   21171000 :                    loop = loop_outer (loop))
    1700                 :            :                 {
    1701                 :   21171000 :                   eloops--;
    1702                 :   21171000 :                   sizes[loop->num]++;
    1703                 :            :                 }
    1704                 :            : 
    1705                 :   19336300 :               if (eloops != 0)
    1706                 :            :                 {
    1707                 :          0 :                   error ("wrong list of exited loops for edge %d->%d",
    1708                 :          0 :                          e->src->index, e->dest->index);
    1709                 :          0 :                   err = 1;
    1710                 :            :                 }
    1711                 :            :             }
    1712                 :            :         }
    1713                 :            : 
    1714                 :   15169900 :       if (n_exits != current_loops->exits->elements ())
    1715                 :            :         {
    1716                 :          0 :           error ("too many loop exits recorded");
    1717                 :          0 :           err = 1;
    1718                 :            :         }
    1719                 :            : 
    1720                 :   25886000 :       FOR_EACH_LOOP (loop, 0)
    1721                 :            :         {
    1722                 :   10716100 :           eloops = 0;
    1723                 :   31887100 :           for (exit = loop->exits->next; exit->e; exit = exit->next)
    1724                 :   21171000 :             eloops++;
    1725                 :   10716100 :           if (eloops != sizes[loop->num])
    1726                 :            :             {
    1727                 :          0 :               error ("%d exits recorded for loop %d (having %d exits)",
    1728                 :            :                      eloops, loop->num, sizes[loop->num]);
    1729                 :          0 :               err = 1;
    1730                 :            :             }
    1731                 :            :         }
    1732                 :            : 
    1733                 :   15169900 :       free (sizes);
    1734                 :            :     }
    1735                 :            : 
    1736                 :  217612000 :   gcc_assert (!err);
    1737                 :            : 
    1738                 :  217612000 :   if (!dom_available)
    1739                 :   52460700 :     free_dominance_info (CDI_DOMINATORS);
    1740                 :  217612000 : }
    1741                 :            : 
    1742                 :            : #if __GNUC__ >= 10
    1743                 :            : #  pragma GCC diagnostic pop
    1744                 :            : #endif
    1745                 :            : 
    1746                 :            : /* Returns latch edge of LOOP.  */
    1747                 :            : edge
    1748                 :   16731000 : loop_latch_edge (const class loop *loop)
    1749                 :            : {
    1750                 :   16731000 :   return find_edge (loop->latch, loop->header);
    1751                 :            : }
    1752                 :            : 
    1753                 :            : /* Returns preheader edge of LOOP.  */
    1754                 :            : edge
    1755                 :  207273000 : loop_preheader_edge (const class loop *loop)
    1756                 :            : {
    1757                 :  207273000 :   edge e;
    1758                 :  207273000 :   edge_iterator ei;
    1759                 :            : 
    1760                 :  207273000 :   gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
    1761                 :            :               && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
    1762                 :            : 
    1763                 :  249327000 :   FOR_EACH_EDGE (e, ei, loop->header->preds)
    1764                 :  248961000 :     if (e->src != loop->latch)
    1765                 :            :       break;
    1766                 :            : 
    1767                 :  207273000 :   if (! e)
    1768                 :            :     {
    1769                 :     366134 :       gcc_assert (! loop_outer (loop));
    1770                 :     366134 :       return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
    1771                 :            :     }
    1772                 :            : 
    1773                 :            :   return e;
    1774                 :            : }
    1775                 :            : 
    1776                 :            : /* Returns true if E is an exit of LOOP.  */
    1777                 :            : 
    1778                 :            : bool
    1779                 :   30252300 : loop_exit_edge_p (const class loop *loop, const_edge e)
    1780                 :            : {
    1781                 :   30252300 :   return (flow_bb_inside_loop_p (loop, e->src)
    1782                 :   30252300 :           && !flow_bb_inside_loop_p (loop, e->dest));
    1783                 :            : }
    1784                 :            : 
    1785                 :            : /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
    1786                 :            :    or more than one exit.  If loops do not have the exits recorded, NULL
    1787                 :            :    is returned always.  */
    1788                 :            : 
    1789                 :            : edge
    1790                 :   18913900 : single_exit (const class loop *loop)
    1791                 :            : {
    1792                 :   18913900 :   struct loop_exit *exit = loop->exits->next;
    1793                 :            : 
    1794                 :   18913900 :   if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
    1795                 :            :     return NULL;
    1796                 :            : 
    1797                 :   18120400 :   if (exit->e && exit->next == loop->exits)
    1798                 :            :     return exit->e;
    1799                 :            :   else
    1800                 :    5586890 :     return NULL;
    1801                 :            : }
    1802                 :            : 
    1803                 :            : /* Returns true when BB has an incoming edge exiting LOOP.  */
    1804                 :            : 
    1805                 :            : bool
    1806                 :          0 : loop_exits_to_bb_p (class loop *loop, basic_block bb)
    1807                 :            : {
    1808                 :          0 :   edge e;
    1809                 :          0 :   edge_iterator ei;
    1810                 :            : 
    1811                 :          0 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1812                 :          0 :     if (loop_exit_edge_p (loop, e))
    1813                 :            :       return true;
    1814                 :            : 
    1815                 :            :   return false;
    1816                 :            : }
    1817                 :            : 
    1818                 :            : /* Returns true when BB has an outgoing edge exiting LOOP.  */
    1819                 :            : 
    1820                 :            : bool
    1821                 :     231483 : loop_exits_from_bb_p (class loop *loop, basic_block bb)
    1822                 :            : {
    1823                 :     231483 :   edge e;
    1824                 :     231483 :   edge_iterator ei;
    1825                 :            : 
    1826                 :     383731 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1827                 :     372515 :     if (loop_exit_edge_p (loop, e))
    1828                 :            :       return true;
    1829                 :            : 
    1830                 :            :   return false;
    1831                 :            : }
    1832                 :            : 
    1833                 :            : /* Return location corresponding to the loop control condition if possible.  */
    1834                 :            : 
    1835                 :            : dump_user_location_t
    1836                 :      23195 : get_loop_location (class loop *loop)
    1837                 :            : {
    1838                 :      23195 :   rtx_insn *insn = NULL;
    1839                 :      23195 :   class niter_desc *desc = NULL;
    1840                 :      23195 :   edge exit;
    1841                 :            : 
    1842                 :            :   /* For a for or while loop, we would like to return the location
    1843                 :            :      of the for or while statement, if possible.  To do this, look
    1844                 :            :      for the branch guarding the loop back-edge.  */
    1845                 :            : 
    1846                 :            :   /* If this is a simple loop with an in_edge, then the loop control
    1847                 :            :      branch is typically at the end of its source.  */
    1848                 :      23195 :   desc = get_simple_loop_desc (loop);
    1849                 :      23195 :   if (desc->in_edge)
    1850                 :            :     {
    1851                 :      43378 :       FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
    1852                 :            :         {
    1853                 :      48987 :           if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
    1854                 :      18248 :             return insn;
    1855                 :            :         }
    1856                 :            :     }
    1857                 :            :   /* If loop has a single exit, then the loop control branch
    1858                 :            :      must be at the end of its source.  */
    1859                 :       4947 :   if ((exit = single_exit (loop)))
    1860                 :            :     {
    1861                 :       6392 :       FOR_BB_INSNS_REVERSE (exit->src, insn)
    1862                 :            :         {
    1863                 :       6705 :           if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
    1864                 :       2416 :             return insn;
    1865                 :            :         }
    1866                 :            :     }
    1867                 :            :   /* Next check the latch, to see if it is non-empty.  */
    1868                 :      10159 :   FOR_BB_INSNS_REVERSE (loop->latch, insn)
    1869                 :            :     {
    1870                 :       4664 :       if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
    1871                 :        423 :         return insn;
    1872                 :            :     }
    1873                 :            :   /* Finally, if none of the above identifies the loop control branch,
    1874                 :            :      return the first location in the loop header.  */
    1875                 :      13728 :   FOR_BB_INSNS (loop->header, insn)
    1876                 :            :     {
    1877                 :       8495 :       if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
    1878                 :       1349 :         return insn;
    1879                 :            :     }
    1880                 :            :   /* If all else fails, simply return the current function location.  */
    1881                 :        759 :   return dump_user_location_t::from_function_decl (current_function_decl);
    1882                 :            : }
    1883                 :            : 
    1884                 :            : /* Records that every statement in LOOP is executed I_BOUND times.
    1885                 :            :    REALISTIC is true if I_BOUND is expected to be close to the real number
    1886                 :            :    of iterations.  UPPER is true if we are sure the loop iterates at most
    1887                 :            :    I_BOUND times.  */
    1888                 :            : 
    1889                 :            : void
    1890                 :    8630540 : record_niter_bound (class loop *loop, const widest_int &i_bound,
    1891                 :            :                     bool realistic, bool upper)
    1892                 :            : {
    1893                 :            :   /* Update the bounds only when there is no previous estimation, or when the
    1894                 :            :      current estimation is smaller.  */
    1895                 :    8630540 :   if (upper
    1896                 :    8630540 :       && (!loop->any_upper_bound
    1897                 :    7822480 :           || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound)))
    1898                 :            :     {
    1899                 :     618414 :       loop->any_upper_bound = true;
    1900                 :     618414 :       loop->nb_iterations_upper_bound = i_bound;
    1901                 :     618414 :       if (!loop->any_likely_upper_bound)
    1902                 :            :         {
    1903                 :     302579 :           loop->any_likely_upper_bound = true;
    1904                 :     302579 :           loop->nb_iterations_likely_upper_bound = i_bound;
    1905                 :            :         }
    1906                 :            :     }
    1907                 :    8630540 :   if (realistic
    1908                 :    8630540 :       && (!loop->any_estimate
    1909                 :    1106450 :           || wi::ltu_p (i_bound, loop->nb_iterations_estimate)))
    1910                 :            :     {
    1911                 :     220652 :       loop->any_estimate = true;
    1912                 :     220652 :       loop->nb_iterations_estimate = i_bound;
    1913                 :            :     }
    1914                 :    8630540 :   if (!realistic
    1915                 :    8630540 :       && (!loop->any_likely_upper_bound
    1916                 :    7385450 :           || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound)))
    1917                 :            :     {
    1918                 :     221800 :       loop->any_likely_upper_bound = true;
    1919                 :     221800 :       loop->nb_iterations_likely_upper_bound = i_bound;
    1920                 :            :     }
    1921                 :            : 
    1922                 :            :   /* If an upper bound is smaller than the realistic estimate of the
    1923                 :            :      number of iterations, use the upper bound instead.  */
    1924                 :    8630540 :   if (loop->any_upper_bound
    1925                 :    8630540 :       && loop->any_estimate
    1926                 :   12516400 :       && wi::ltu_p (loop->nb_iterations_upper_bound,
    1927                 :    3885840 :                     loop->nb_iterations_estimate))
    1928                 :       4467 :     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
    1929                 :    8630540 :   if (loop->any_upper_bound
    1930                 :    8630540 :       && loop->any_likely_upper_bound
    1931                 :   17250400 :       && wi::ltu_p (loop->nb_iterations_upper_bound,
    1932                 :    8619860 :                     loop->nb_iterations_likely_upper_bound))
    1933                 :      92685 :     loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
    1934                 :    8630540 : }
    1935                 :            : 
    1936                 :            : /* Similar to get_estimated_loop_iterations, but returns the estimate only
    1937                 :            :    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
    1938                 :            :    on the number of iterations of LOOP could not be derived, returns -1.  */
    1939                 :            : 
    1940                 :            : HOST_WIDE_INT
    1941                 :        168 : get_estimated_loop_iterations_int (class loop *loop)
    1942                 :            : {
    1943                 :        168 :   widest_int nit;
    1944                 :        168 :   HOST_WIDE_INT hwi_nit;
    1945                 :            : 
    1946                 :        168 :   if (!get_estimated_loop_iterations (loop, &nit))
    1947                 :            :     return -1;
    1948                 :            : 
    1949                 :         52 :   if (!wi::fits_shwi_p (nit))
    1950                 :            :     return -1;
    1951                 :         52 :   hwi_nit = nit.to_shwi ();
    1952                 :            : 
    1953                 :         52 :   return hwi_nit < 0 ? -1 : hwi_nit;
    1954                 :            : }
    1955                 :            : 
    1956                 :            : /* Returns an upper bound on the number of executions of statements
    1957                 :            :    in the LOOP.  For statements before the loop exit, this exceeds
    1958                 :            :    the number of execution of the latch by one.  */
    1959                 :            : 
    1960                 :            : HOST_WIDE_INT
    1961                 :     148078 : max_stmt_executions_int (class loop *loop)
    1962                 :            : {
    1963                 :     148078 :   HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
    1964                 :     148078 :   HOST_WIDE_INT snit;
    1965                 :            : 
    1966                 :     148078 :   if (nit == -1)
    1967                 :            :     return -1;
    1968                 :            : 
    1969                 :     146780 :   snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
    1970                 :            : 
    1971                 :            :   /* If the computation overflows, return -1.  */
    1972                 :     146780 :   return snit < 0 ? -1 : snit;
    1973                 :            : }
    1974                 :            : 
    1975                 :            : /* Returns an likely upper bound on the number of executions of statements
    1976                 :            :    in the LOOP.  For statements before the loop exit, this exceeds
    1977                 :            :    the number of execution of the latch by one.  */
    1978                 :            : 
    1979                 :            : HOST_WIDE_INT
    1980                 :    3306990 : likely_max_stmt_executions_int (class loop *loop)
    1981                 :            : {
    1982                 :    3306990 :   HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
    1983                 :    3306990 :   HOST_WIDE_INT snit;
    1984                 :            : 
    1985                 :    3306990 :   if (nit == -1)
    1986                 :            :     return -1;
    1987                 :            : 
    1988                 :    2788520 :   snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
    1989                 :            : 
    1990                 :            :   /* If the computation overflows, return -1.  */
    1991                 :    2788520 :   return snit < 0 ? -1 : snit;
    1992                 :            : }
    1993                 :            : 
    1994                 :            : /* Sets NIT to the estimated number of executions of the latch of the
    1995                 :            :    LOOP.  If we have no reliable estimate, the function returns false, otherwise
    1996                 :            :    returns true.  */
    1997                 :            : 
    1998                 :            : bool
    1999                 :    5642320 : get_estimated_loop_iterations (class loop *loop, widest_int *nit)
    2000                 :            : {
    2001                 :            :   /* Even if the bound is not recorded, possibly we can derrive one from
    2002                 :            :      profile.  */
    2003                 :    5642320 :   if (!loop->any_estimate)
    2004                 :            :     {
    2005                 :    3522290 :       if (loop->header->count.reliable_p ())
    2006                 :            :         {
    2007                 :          4 :           *nit = gcov_type_to_wide_int
    2008                 :          2 :                    (expected_loop_iterations_unbounded (loop) + 1);
    2009                 :          2 :           return true;
    2010                 :            :         }
    2011                 :            :       return false;
    2012                 :            :     }
    2013                 :            : 
    2014                 :    2120030 :   *nit = loop->nb_iterations_estimate;
    2015                 :    2120030 :   return true;
    2016                 :            : }
    2017                 :            : 
    2018                 :            : /* Sets NIT to an upper bound for the maximum number of executions of the
    2019                 :            :    latch of the LOOP.  If we have no reliable estimate, the function returns
    2020                 :            :    false, otherwise returns true.  */
    2021                 :            : 
    2022                 :            : bool
    2023                 :   10025800 : get_max_loop_iterations (const class loop *loop, widest_int *nit)
    2024                 :            : {
    2025                 :   10025800 :   if (!loop->any_upper_bound)
    2026                 :            :     return false;
    2027                 :            : 
    2028                 :    8789930 :   *nit = loop->nb_iterations_upper_bound;
    2029                 :    8789930 :   return true;
    2030                 :            : }
    2031                 :            : 
    2032                 :            : /* Similar to get_max_loop_iterations, but returns the estimate only
    2033                 :            :    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
    2034                 :            :    on the number of iterations of LOOP could not be derived, returns -1.  */
    2035                 :            : 
    2036                 :            : HOST_WIDE_INT
    2037                 :     230107 : get_max_loop_iterations_int (const class loop *loop)
    2038                 :            : {
    2039                 :     230107 :   widest_int nit;
    2040                 :     230107 :   HOST_WIDE_INT hwi_nit;
    2041                 :            : 
    2042                 :     230107 :   if (!get_max_loop_iterations (loop, &nit))
    2043                 :            :     return -1;
    2044                 :            : 
    2045                 :     209556 :   if (!wi::fits_shwi_p (nit))
    2046                 :            :     return -1;
    2047                 :     206347 :   hwi_nit = nit.to_shwi ();
    2048                 :            : 
    2049                 :     206347 :   return hwi_nit < 0 ? -1 : hwi_nit;
    2050                 :            : }
    2051                 :            : 
    2052                 :            : /* Sets NIT to an upper bound for the maximum number of executions of the
    2053                 :            :    latch of the LOOP.  If we have no reliable estimate, the function returns
    2054                 :            :    false, otherwise returns true.  */
    2055                 :            : 
    2056                 :            : bool
    2057                 :    3547980 : get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
    2058                 :            : {
    2059                 :    3547980 :   if (!loop->any_likely_upper_bound)
    2060                 :            :     return false;
    2061                 :            : 
    2062                 :    3137880 :   *nit = loop->nb_iterations_likely_upper_bound;
    2063                 :    3137880 :   return true;
    2064                 :            : }
    2065                 :            : 
    2066                 :            : /* Similar to get_max_loop_iterations, but returns the estimate only
    2067                 :            :    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
    2068                 :            :    on the number of iterations of LOOP could not be derived, returns -1.  */
    2069                 :            : 
    2070                 :            : HOST_WIDE_INT
    2071                 :    3308110 : get_likely_max_loop_iterations_int (class loop *loop)
    2072                 :            : {
    2073                 :    3308110 :   widest_int nit;
    2074                 :    3308110 :   HOST_WIDE_INT hwi_nit;
    2075                 :            : 
    2076                 :    3308110 :   if (!get_likely_max_loop_iterations (loop, &nit))
    2077                 :            :     return -1;
    2078                 :            : 
    2079                 :    2987840 :   if (!wi::fits_shwi_p (nit))
    2080                 :            :     return -1;
    2081                 :    2789140 :   hwi_nit = nit.to_shwi ();
    2082                 :            : 
    2083                 :    2789140 :   return hwi_nit < 0 ? -1 : hwi_nit;
    2084                 :            : }
    2085                 :            : 
    2086                 :            : /* Returns the loop depth of the loop BB belongs to.  */
    2087                 :            : 
    2088                 :            : int
    2089                 :   41100500 : bb_loop_depth (const_basic_block bb)
    2090                 :            : {
    2091                 :   52194200 :   return bb->loop_father ? loop_depth (bb->loop_father) : 0;
    2092                 :            : }
    2093                 :            : 
    2094                 :            : /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP.  */
    2095                 :            : 
    2096                 :            : void
    2097                 :      45527 : mark_loop_for_removal (loop_p loop)
    2098                 :            : {
    2099                 :      45527 :   if (loop->header == NULL)
    2100                 :            :     return;
    2101                 :      45527 :   loop->former_header = loop->header;
    2102                 :      45527 :   loop->header = NULL;
    2103                 :      45527 :   loop->latch = NULL;
    2104                 :      45527 :   loops_state_set (LOOPS_NEED_FIXUP);
    2105                 :            : }

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.