LCOV - code coverage report
Current view: top level - gcc - cfg.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 487 528 92.2 %
Date: 2020-05-30 12:51:24 Functions: 44 56 78.6 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Control flow graph manipulation code for GNU compiler.
       2                 :            :    Copyright (C) 1987-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                 :            : /* This file contains low level functions to manipulate the CFG and
      21                 :            :    analyze it.  All other modules should not transform the data structure
      22                 :            :    directly and use abstraction instead.  The file is supposed to be
      23                 :            :    ordered bottom-up and should not contain any code dependent on a
      24                 :            :    particular intermediate language (RTL or trees).
      25                 :            : 
      26                 :            :    Available functionality:
      27                 :            :      - Initialization/deallocation
      28                 :            :          init_flow, clear_edges
      29                 :            :      - Low level basic block manipulation
      30                 :            :          alloc_block, expunge_block
      31                 :            :      - Edge manipulation
      32                 :            :          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
      33                 :            :          - Low level edge redirection (without updating instruction chain)
      34                 :            :              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
      35                 :            :      - Dumping and debugging
      36                 :            :          dump_flow_info, debug_flow_info, dump_edge_info
      37                 :            :      - Allocation of AUX fields for basic blocks
      38                 :            :          alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
      39                 :            :      - clear_bb_flags
      40                 :            :      - Consistency checking
      41                 :            :          verify_flow_info
      42                 :            :      - Dumping and debugging
      43                 :            :          print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
      44                 :            : 
      45                 :            :    TODO: Document these "Available functionality" functions in the files
      46                 :            :    that implement them.
      47                 :            :  */
      48                 :            : 
      49                 :            : #include "config.h"
      50                 :            : #include "system.h"
      51                 :            : #include "coretypes.h"
      52                 :            : #include "backend.h"
      53                 :            : #include "hard-reg-set.h"
      54                 :            : #include "tree.h"
      55                 :            : #include "cfghooks.h"
      56                 :            : #include "df.h"
      57                 :            : #include "cfganal.h"
      58                 :            : #include "cfgloop.h" /* FIXME: For struct loop.  */
      59                 :            : #include "dumpfile.h"
      60                 :            : 
      61                 :            : 
      62                 :            : 
      63                 :            : /* Called once at initialization time.  */
      64                 :            : 
      65                 :            : void
      66                 :    2142310 : init_flow (struct function *the_fun)
      67                 :            : {
      68                 :    2142310 :   if (!the_fun->cfg)
      69                 :    2142310 :     the_fun->cfg = ggc_cleared_alloc<control_flow_graph> ();
      70                 :    2142310 :   n_edges_for_fn (the_fun) = 0;
      71                 :    2142310 :   the_fun->cfg->count_max = profile_count::uninitialized ();
      72                 :    2142310 :   ENTRY_BLOCK_PTR_FOR_FN (the_fun)
      73                 :    2142310 :     = alloc_block ();
      74                 :    2142310 :   ENTRY_BLOCK_PTR_FOR_FN (the_fun)->index = ENTRY_BLOCK;
      75                 :    2142310 :   EXIT_BLOCK_PTR_FOR_FN (the_fun)
      76                 :    2142310 :     = alloc_block ();
      77                 :    2142310 :   EXIT_BLOCK_PTR_FOR_FN (the_fun)->index = EXIT_BLOCK;
      78                 :    2142310 :   ENTRY_BLOCK_PTR_FOR_FN (the_fun)->next_bb
      79                 :    2142310 :     = EXIT_BLOCK_PTR_FOR_FN (the_fun);
      80                 :    2142310 :   EXIT_BLOCK_PTR_FOR_FN (the_fun)->prev_bb
      81                 :    2142310 :     = ENTRY_BLOCK_PTR_FOR_FN (the_fun);
      82                 :    2142310 :   the_fun->cfg->edge_flags_allocated = EDGE_ALL_FLAGS;
      83                 :    2142310 :   the_fun->cfg->bb_flags_allocated = BB_ALL_FLAGS;
      84                 :    2142310 : }
      85                 :            : 
      86                 :            : /* Helper function for remove_edge and clear_edges.  Frees edge structure
      87                 :            :    without actually removing it from the pred/succ arrays.  */
      88                 :            : 
      89                 :            : static void
      90                 :   50199600 : free_edge (function *fn, edge e)
      91                 :            : {
      92                 :   50199600 :   n_edges_for_fn (fn)--;
      93                 :          0 :   ggc_free (e);
      94                 :          0 : }
      95                 :            : 
      96                 :            : /* Free the memory associated with the edge structures.  */
      97                 :            : 
      98                 :            : void
      99                 :    1091940 : clear_edges (struct function *fn)
     100                 :            : {
     101                 :    1091940 :   basic_block bb;
     102                 :    1091940 :   edge e;
     103                 :    1091940 :   edge_iterator ei;
     104                 :            : 
     105                 :    3886690 :   FOR_EACH_BB_FN (bb, fn)
     106                 :            :     {
     107                 :    6216130 :       FOR_EACH_EDGE (e, ei, bb->succs)
     108                 :    3421390 :         free_edge (fn, e);
     109                 :    2794740 :       vec_safe_truncate (bb->succs, 0);
     110                 :    5589490 :       vec_safe_truncate (bb->preds, 0);
     111                 :            :     }
     112                 :            : 
     113                 :    2183890 :   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (fn)->succs)
     114                 :    1091940 :     free_edge (fn, e);
     115                 :    1091940 :   vec_safe_truncate (EXIT_BLOCK_PTR_FOR_FN (fn)->preds, 0);
     116                 :    1091940 :   vec_safe_truncate (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs, 0);
     117                 :            : 
     118                 :    1091940 :   gcc_assert (!n_edges_for_fn (fn));
     119                 :    1091940 : }
     120                 :            : 
     121                 :            : /* Allocate memory for basic_block.  */
     122                 :            : 
     123                 :            : basic_block
     124                 :   51423900 : alloc_block (void)
     125                 :            : {
     126                 :   51423900 :   basic_block bb;
     127                 :   51423900 :   bb = ggc_cleared_alloc<basic_block_def> ();
     128                 :   51423900 :   bb->count = profile_count::uninitialized ();
     129                 :   51423900 :   return bb;
     130                 :            : }
     131                 :            : 
     132                 :            : /* Link block B to chain after AFTER.  */
     133                 :            : void
     134                 :   49392000 : link_block (basic_block b, basic_block after)
     135                 :            : {
     136                 :   49392000 :   b->next_bb = after->next_bb;
     137                 :   49392000 :   b->prev_bb = after;
     138                 :   49392000 :   after->next_bb = b;
     139                 :   49392000 :   b->next_bb->prev_bb = b;
     140                 :   49392000 : }
     141                 :            : 
     142                 :            : /* Unlink block B from chain.  */
     143                 :            : void
     144                 :   37215400 : unlink_block (basic_block b)
     145                 :            : {
     146                 :   37215400 :   b->next_bb->prev_bb = b->prev_bb;
     147                 :   37215400 :   b->prev_bb->next_bb = b->next_bb;
     148                 :   37215400 :   b->prev_bb = NULL;
     149                 :   37215400 :   b->next_bb = NULL;
     150                 :   37215400 : }
     151                 :            : 
     152                 :            : /* Sequentially order blocks and compact the arrays.  */
     153                 :            : void
     154                 :   32810200 : compact_blocks (void)
     155                 :            : {
     156                 :   32810200 :   int i;
     157                 :            : 
     158                 :   32810200 :   SET_BASIC_BLOCK_FOR_FN (cfun, ENTRY_BLOCK, ENTRY_BLOCK_PTR_FOR_FN (cfun));
     159                 :   32810200 :   SET_BASIC_BLOCK_FOR_FN (cfun, EXIT_BLOCK, EXIT_BLOCK_PTR_FOR_FN (cfun));
     160                 :            : 
     161                 :   32810200 :   if (df)
     162                 :   11866500 :     df_compact_blocks ();
     163                 :            :   else
     164                 :            :     {
     165                 :   20943700 :       basic_block bb;
     166                 :            : 
     167                 :   20943700 :       i = NUM_FIXED_BLOCKS;
     168                 :  234849000 :       FOR_EACH_BB_FN (bb, cfun)
     169                 :            :         {
     170                 :  213905000 :           SET_BASIC_BLOCK_FOR_FN (cfun, i, bb);
     171                 :  213905000 :           bb->index = i;
     172                 :  213905000 :           i++;
     173                 :            :         }
     174                 :   20943700 :       gcc_assert (i == n_basic_blocks_for_fn (cfun));
     175                 :            : 
     176                 :   55229000 :       for (; i < last_basic_block_for_fn (cfun); i++)
     177                 :   34285200 :         SET_BASIC_BLOCK_FOR_FN (cfun, i, NULL);
     178                 :            :     }
     179                 :   32810200 :   last_basic_block_for_fn (cfun) = n_basic_blocks_for_fn (cfun);
     180                 :   32810200 : }
     181                 :            : 
     182                 :            : /* Remove block B from the basic block array.  */
     183                 :            : 
     184                 :            : void
     185                 :   34619400 : expunge_block (basic_block b)
     186                 :            : {
     187                 :   34619400 :   unlink_block (b);
     188                 :   34619400 :   SET_BASIC_BLOCK_FOR_FN (cfun, b->index, NULL);
     189                 :   34619400 :   n_basic_blocks_for_fn (cfun)--;
     190                 :            :   /* We should be able to ggc_free here, but we are not.
     191                 :            :      The dead SSA_NAMES are left pointing to dead statements that are pointing
     192                 :            :      to dead basic blocks making garbage collector to die.
     193                 :            :      We should be able to release all dead SSA_NAMES and at the same time we should
     194                 :            :      clear out BB pointer of dead statements consistently.  */
     195                 :   34619400 : }
     196                 :            : 
     197                 :            : /* Connect E to E->src.  */
     198                 :            : 
     199                 :            : static inline void
     200                 :   66747700 : connect_src (edge e)
     201                 :            : {
     202                 :   66747700 :   vec_safe_push (e->src->succs, e);
     203                 :   66747700 :   df_mark_solutions_dirty ();
     204                 :            : }
     205                 :            : 
     206                 :            : /* Connect E to E->dest.  */
     207                 :            : 
     208                 :            : static inline void
     209                 :  111401000 : connect_dest (edge e)
     210                 :            : {
     211                 :  111401000 :   basic_block dest = e->dest;
     212                 :  111401000 :   vec_safe_push (dest->preds, e);
     213                 :  111401000 :   e->dest_idx = EDGE_COUNT (dest->preds) - 1;
     214                 :  111401000 :   df_mark_solutions_dirty ();
     215                 :  111401000 : }
     216                 :            : 
     217                 :            : /* Disconnect edge E from E->src.  */
     218                 :            : 
     219                 :            : static inline void
     220                 :   47084900 : disconnect_src (edge e)
     221                 :            : {
     222                 :   47084900 :   basic_block src = e->src;
     223                 :   47084900 :   edge_iterator ei;
     224                 :   47084900 :   edge tmp;
     225                 :            : 
     226                 :   48790300 :   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
     227                 :            :     {
     228                 :   48790300 :       if (tmp == e)
     229                 :            :         {
     230                 :   47084900 :           src->succs->unordered_remove (ei.index);
     231                 :   47084900 :           df_mark_solutions_dirty ();
     232                 :   47084900 :           return;
     233                 :            :         }
     234                 :            :       else
     235                 :    1705400 :         ei_next (&ei);
     236                 :            :     }
     237                 :            : 
     238                 :          0 :   gcc_unreachable ();
     239                 :            : }
     240                 :            : 
     241                 :            : /* Disconnect edge E from E->dest.  */
     242                 :            : 
     243                 :            : static inline void
     244                 :            : disconnect_dest (edge e)
     245                 :            : {
     246                 :            :   basic_block dest = e->dest;
     247                 :            :   unsigned int dest_idx = e->dest_idx;
     248                 :            : 
     249                 :            :   dest->preds->unordered_remove (dest_idx);
     250                 :            : 
     251                 :            :   /* If we removed an edge in the middle of the edge vector, we need
     252                 :            :      to update dest_idx of the edge that moved into the "hole".  */
     253                 :            :   if (dest_idx < EDGE_COUNT (dest->preds))
     254                 :            :     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
     255                 :            :   df_mark_solutions_dirty ();
     256                 :            : }
     257                 :            : 
     258                 :            : /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
     259                 :            :    created edge.  Use this only if you are sure that this edge can't
     260                 :            :    possibly already exist.  */
     261                 :            : 
     262                 :            : edge
     263                 :   65349100 : unchecked_make_edge (basic_block src, basic_block dst, int flags)
     264                 :            : {
     265                 :   65349100 :   edge e;
     266                 :   65349100 :   e = ggc_cleared_alloc<edge_def> ();
     267                 :   65349100 :   n_edges_for_fn (cfun)++;
     268                 :            : 
     269                 :   65349100 :   e->probability = profile_probability::uninitialized ();
     270                 :   65349100 :   e->src = src;
     271                 :   65349100 :   e->dest = dst;
     272                 :   65349100 :   e->flags = flags;
     273                 :            : 
     274                 :   65349100 :   connect_src (e);
     275                 :   65349100 :   connect_dest (e);
     276                 :            : 
     277                 :   65349100 :   execute_on_growing_pred (e);
     278                 :   65349100 :   return e;
     279                 :            : }
     280                 :            : 
     281                 :            : /* Create an edge connecting SRC and DST with FLAGS optionally using
     282                 :            :    edge cache CACHE.  Return the new edge, NULL if already exist.  */
     283                 :            : 
     284                 :            : edge
     285                 :   24204100 : cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
     286                 :            : {
     287                 :   24204100 :   if (edge_cache == NULL
     288                 :     167462 :       || src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
     289                 :     167462 :       || dst == EXIT_BLOCK_PTR_FOR_FN (cfun))
     290                 :   24052600 :     return make_edge (src, dst, flags);
     291                 :            : 
     292                 :            :   /* Does the requested edge already exist?  */
     293                 :     151467 :   if (! bitmap_bit_p (edge_cache, dst->index))
     294                 :            :     {
     295                 :            :       /* The edge does not exist.  Create one and update the
     296                 :            :          cache.  */
     297                 :      20775 :       bitmap_set_bit (edge_cache, dst->index);
     298                 :      20775 :       return unchecked_make_edge (src, dst, flags);
     299                 :            :     }
     300                 :            : 
     301                 :            :   /* At this point, we know that the requested edge exists.  Adjust
     302                 :            :      flags if necessary.  */
     303                 :     130692 :   if (flags)
     304                 :            :     {
     305                 :      61592 :       edge e = find_edge (src, dst);
     306                 :      61592 :       e->flags |= flags;
     307                 :            :     }
     308                 :            : 
     309                 :            :   return NULL;
     310                 :            : }
     311                 :            : 
     312                 :            : /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
     313                 :            :    created edge or NULL if already exist.  */
     314                 :            : 
     315                 :            : edge
     316                 :   85621100 : make_edge (basic_block src, basic_block dest, int flags)
     317                 :            : {
     318                 :   85621100 :   edge e = find_edge (src, dest);
     319                 :            : 
     320                 :            :   /* Make sure we don't add duplicate edges.  */
     321                 :   85621100 :   if (e)
     322                 :            :     {
     323                 :   23866600 :       e->flags |= flags;
     324                 :   23866600 :       return NULL;
     325                 :            :     }
     326                 :            : 
     327                 :   61754500 :   return unchecked_make_edge (src, dest, flags);
     328                 :            : }
     329                 :            : 
     330                 :            : /* Create an edge connecting SRC to DEST and set probability by knowing
     331                 :            :    that it is the single edge leaving SRC.  */
     332                 :            : 
     333                 :            : edge
     334                 :   23216100 : make_single_succ_edge (basic_block src, basic_block dest, int flags)
     335                 :            : {
     336                 :   23216100 :   edge e = make_edge (src, dest, flags);
     337                 :            : 
     338                 :   23216100 :   e->probability = profile_probability::always ();
     339                 :   23216100 :   return e;
     340                 :            : }
     341                 :            : 
     342                 :            : /* This function will remove an edge from the flow graph.  */
     343                 :            : 
     344                 :            : void
     345                 :   45686300 : remove_edge_raw (edge e)
     346                 :            : {
     347                 :   45686300 :   remove_predictions_associated_with_edge (e);
     348                 :   45686300 :   execute_on_shrinking_pred (e);
     349                 :            : 
     350                 :   45686300 :   disconnect_src (e);
     351                 :   45686300 :   disconnect_dest (e);
     352                 :            : 
     353                 :   45686300 :   free_edge (cfun, e);
     354                 :   45686300 : }
     355                 :            : 
     356                 :            : /* Redirect an edge's successor from one block to another.  */
     357                 :            : 
     358                 :            : void
     359                 :   46051500 : redirect_edge_succ (edge e, basic_block new_succ)
     360                 :            : {
     361                 :   46051500 :   execute_on_shrinking_pred (e);
     362                 :            : 
     363                 :   46051500 :   disconnect_dest (e);
     364                 :            : 
     365                 :   46051500 :   e->dest = new_succ;
     366                 :            : 
     367                 :            :   /* Reconnect the edge to the new successor block.  */
     368                 :   46051500 :   connect_dest (e);
     369                 :            : 
     370                 :   46051500 :   execute_on_growing_pred (e);
     371                 :   46051500 : }
     372                 :            : 
     373                 :            : /* Redirect an edge's predecessor from one block to another.  */
     374                 :            : 
     375                 :            : void
     376                 :    1398580 : redirect_edge_pred (edge e, basic_block new_pred)
     377                 :            : {
     378                 :    1398580 :   disconnect_src (e);
     379                 :            : 
     380                 :    1398580 :   e->src = new_pred;
     381                 :            : 
     382                 :            :   /* Reconnect the edge to the new predecessor block.  */
     383                 :    1398580 :   connect_src (e);
     384                 :    1398580 : }
     385                 :            : 
     386                 :            : /* Clear all basic block flags that do not have to be preserved.  */
     387                 :            : void
     388                 :    3639820 : clear_bb_flags (void)
     389                 :            : {
     390                 :    3639820 :   basic_block bb;
     391                 :    3639820 :   int flags_to_preserve = BB_FLAGS_TO_PRESERVE;
     392                 :    3639820 :   if (current_loops
     393                 :    3639820 :       && loops_state_satisfies_p (cfun, LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
     394                 :            :     flags_to_preserve |= BB_IRREDUCIBLE_LOOP;
     395                 :            : 
     396                 :   50330900 :   FOR_ALL_BB_FN (bb, cfun)
     397                 :   46691000 :     bb->flags &= flags_to_preserve;
     398                 :    3639820 : }
     399                 :            : 
     400                 :            : /* Check the consistency of profile information.  We can't do that
     401                 :            :    in verify_flow_info, as the counts may get invalid for incompletely
     402                 :            :    solved graphs, later eliminating of conditionals or roundoff errors.
     403                 :            :    It is still practical to have them reported for debugging of simple
     404                 :            :    testcases.  */
     405                 :            : static void
     406                 :       6212 : check_bb_profile (basic_block bb, FILE * file, int indent)
     407                 :            : {
     408                 :       6212 :   edge e;
     409                 :       6212 :   edge_iterator ei;
     410                 :       6212 :   struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
     411                 :       6212 :   char *s_indent = (char *) alloca ((size_t) indent + 1);
     412                 :       6212 :   memset ((void *) s_indent, ' ', (size_t) indent);
     413                 :       6212 :   s_indent[indent] = '\0';
     414                 :            : 
     415                 :       6212 :   if (profile_status_for_fn (fun) == PROFILE_ABSENT)
     416                 :       2298 :     return;
     417                 :            : 
     418                 :       3914 :   if (bb != EXIT_BLOCK_PTR_FOR_FN (fun))
     419                 :            :     {
     420                 :       3914 :       bool found = false;
     421                 :       3914 :       profile_probability sum = profile_probability::never ();
     422                 :       3914 :       int isum = 0;
     423                 :            : 
     424                 :       9144 :       FOR_EACH_EDGE (e, ei, bb->succs)
     425                 :            :         {
     426                 :       5230 :           if (!(e->flags & (EDGE_EH | EDGE_FAKE)))
     427                 :       5230 :             found = true;
     428                 :       5230 :           sum += e->probability;
     429                 :       5230 :           if (e->probability.initialized_p ())
     430                 :       5230 :             isum += e->probability.to_reg_br_prob_base ();
     431                 :            :         }
     432                 :            :       /* Only report mismatches for non-EH control flow. If there are only EH
     433                 :            :          edges it means that the BB ends by noreturn call.  Here the control
     434                 :            :          flow may just terminate.  */
     435                 :       3914 :       if (found)
     436                 :            :         {
     437                 :       3851 :           if (sum.differs_from_p (profile_probability::always ()))
     438                 :            :             {
     439                 :          0 :               fprintf (file,
     440                 :            :                        ";; %sInvalid sum of outgoing probabilities ",
     441                 :            :                        s_indent);
     442                 :          0 :               sum.dump (file);
     443                 :          0 :               fprintf (file, "\n");
     444                 :            :             }
     445                 :            :           /* Probabilities caps to 100% and thus the previous test will never
     446                 :            :              fire if the sum of probabilities is too large.  */
     447                 :       3851 :           else if (isum > REG_BR_PROB_BASE + 100)
     448                 :            :             {
     449                 :        182 :               fprintf (file,
     450                 :            :                        ";; %sInvalid sum of outgoing probabilities %.1f%%\n",
     451                 :        182 :                        s_indent, isum * 100.0 / REG_BR_PROB_BASE);
     452                 :            :             }
     453                 :            :         }
     454                 :            :     }
     455                 :       3914 :   if (bb != ENTRY_BLOCK_PTR_FOR_FN (fun))
     456                 :            :     {
     457                 :       3914 :       profile_count sum = profile_count::zero ();
     458                 :       9145 :       FOR_EACH_EDGE (e, ei, bb->preds)
     459                 :       5231 :         sum += e->count ();
     460                 :       3914 :       if (sum.differs_from_p (bb->count))
     461                 :            :         {
     462                 :        427 :           fprintf (file, ";; %sInvalid sum of incoming counts ",
     463                 :            :                    s_indent);
     464                 :        427 :           sum.dump (file);
     465                 :        427 :           fprintf (file, ", should be ");
     466                 :        427 :           bb->count.dump (file);
     467                 :        427 :           fprintf (file, "\n");
     468                 :            :         }
     469                 :            :     }
     470                 :       3914 :   if (BB_PARTITION (bb) == BB_COLD_PARTITION)
     471                 :            :     {
     472                 :            :       /* Warn about inconsistencies in the partitioning that are
     473                 :            :          currently caused by profile insanities created via optimization.  */
     474                 :          1 :       if (!probably_never_executed_bb_p (fun, bb))
     475                 :          0 :         fprintf (file, ";; %sBlock in cold partition with hot count\n",
     476                 :            :                  s_indent);
     477                 :          2 :       FOR_EACH_EDGE (e, ei, bb->preds)
     478                 :            :         {
     479                 :          1 :           if (!probably_never_executed_edge_p (fun, e))
     480                 :          0 :             fprintf (file,
     481                 :            :                      ";; %sBlock in cold partition with incoming hot edge\n",
     482                 :            :                      s_indent);
     483                 :            :         }
     484                 :            :     }
     485                 :            : }
     486                 :            : 
     487                 :            : void
     488                 :      47664 : dump_edge_info (FILE *file, edge e, dump_flags_t flags, int do_succ)
     489                 :            : {
     490                 :      47664 :   basic_block side = (do_succ ? e->dest : e->src);
     491                 :      47664 :   bool do_details = false;
     492                 :            :   
     493                 :      47664 :   if ((flags & TDF_DETAILS) != 0
     494                 :      47664 :       && (flags & TDF_SLIM) == 0)
     495                 :            :     do_details = true;
     496                 :            : 
     497                 :      47664 :   if (side->index == ENTRY_BLOCK)
     498                 :       3203 :     fputs (" ENTRY", file);
     499                 :      44461 :   else if (side->index == EXIT_BLOCK)
     500                 :       3129 :     fputs (" EXIT", file);
     501                 :            :   else
     502                 :      41332 :     fprintf (file, " %d", side->index);
     503                 :            : 
     504                 :      47664 :   if (e->probability.initialized_p () && do_details)
     505                 :            :     {
     506                 :      17660 :       fprintf (file, " [");
     507                 :      17660 :       e->probability.dump (file);
     508                 :      17660 :       fprintf (file, "] ");
     509                 :            :     }
     510                 :            : 
     511                 :      47664 :   if (e->count ().initialized_p () && do_details)
     512                 :            :     {
     513                 :      13920 :       fputs (" count:", file);
     514                 :      13920 :       e->count ().dump (file);
     515                 :            :     }
     516                 :            : 
     517                 :      47664 :   if (e->flags && do_details)
     518                 :            :     {
     519                 :      19341 :       static const char * const bitnames[] =
     520                 :            :         {
     521                 :            : #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
     522                 :            : #include "cfg-flags.def"
     523                 :            :           NULL
     524                 :            : #undef DEF_EDGE_FLAG
     525                 :            :         };
     526                 :      19341 :       bool comma = false;
     527                 :      19341 :       int i, flags = e->flags;
     528                 :            : 
     529                 :      19341 :       gcc_assert (e->flags <= EDGE_ALL_FLAGS);
     530                 :      19341 :       fputs (" (", file);
     531                 :     133666 :       for (i = 0; flags; i++)
     532                 :     114325 :         if (flags & (1 << i))
     533                 :            :           {
     534                 :      28069 :             flags &= ~(1 << i);
     535                 :            : 
     536                 :      28069 :             if (comma)
     537                 :       8728 :               fputc (',', file);
     538                 :      28069 :             fputs (bitnames[i], file);
     539                 :      28069 :             comma = true;
     540                 :            :           }
     541                 :            : 
     542                 :      19341 :       fputc (')', file);
     543                 :            :     }
     544                 :      47664 : }
     545                 :            : 
     546                 :            : DEBUG_FUNCTION void
     547                 :          0 : debug (edge_def &ref)
     548                 :            : {
     549                 :          0 :   fprintf (stderr, "<edge (%d -> %d)>\n",
     550                 :          0 :            ref.src->index, ref.dest->index);
     551                 :          0 :   dump_edge_info (stderr, &ref, TDF_DETAILS, false);
     552                 :          0 :   fprintf (stderr, "\n");
     553                 :          0 : }
     554                 :            : 
     555                 :            : DEBUG_FUNCTION void
     556                 :          0 : debug (edge_def *ptr)
     557                 :            : {
     558                 :          0 :   if (ptr)
     559                 :          0 :     debug (*ptr);
     560                 :            :   else
     561                 :          0 :     fprintf (stderr, "<nil>\n");
     562                 :          0 : }
     563                 :            : 
     564                 :            : static void
     565                 :          0 : debug_slim (edge e)
     566                 :            : {
     567                 :          0 :   fprintf (stderr, "<edge 0x%p (%d -> %d)>", (void *) e,
     568                 :          0 :            e->src->index, e->dest->index);
     569                 :          0 : }
     570                 :            : 
     571                 :          0 : DEFINE_DEBUG_VEC (edge)
     572                 :          0 : DEFINE_DEBUG_HASH_SET (edge)
     573                 :            : 
     574                 :            : /* Simple routines to easily allocate AUX fields of basic blocks.  */
     575                 :            : 
     576                 :            : static struct obstack block_aux_obstack;
     577                 :            : static void *first_block_aux_obj = 0;
     578                 :            : static struct obstack edge_aux_obstack;
     579                 :            : static void *first_edge_aux_obj = 0;
     580                 :            : 
     581                 :            : /* Allocate a memory block of SIZE as BB->aux.  The obstack must
     582                 :            :    be first initialized by alloc_aux_for_blocks.  */
     583                 :            : 
     584                 :            : static void
     585                 :   40659800 : alloc_aux_for_block (basic_block bb, int size)
     586                 :            : {
     587                 :            :   /* Verify that aux field is clear.  */
     588                 :   40659800 :   gcc_assert (!bb->aux && first_block_aux_obj);
     589                 :   40659800 :   bb->aux = obstack_alloc (&block_aux_obstack, size);
     590                 :   40659800 :   memset (bb->aux, 0, size);
     591                 :   40659800 : }
     592                 :            : 
     593                 :            : /* Initialize the block_aux_obstack and if SIZE is nonzero, call
     594                 :            :    alloc_aux_for_block for each basic block.  */
     595                 :            : 
     596                 :            : void
     597                 :    3446290 : alloc_aux_for_blocks (int size)
     598                 :            : {
     599                 :    3446290 :   static int initialized;
     600                 :            : 
     601                 :    3446290 :   if (!initialized)
     602                 :            :     {
     603                 :     113240 :       gcc_obstack_init (&block_aux_obstack);
     604                 :     113240 :       initialized = 1;
     605                 :            :     }
     606                 :            :   else
     607                 :            :     /* Check whether AUX data are still allocated.  */
     608                 :    3333050 :     gcc_assert (!first_block_aux_obj);
     609                 :            : 
     610                 :    3446290 :   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
     611                 :    3446290 :   if (size)
     612                 :            :     {
     613                 :    3446290 :       basic_block bb;
     614                 :            : 
     615                 :   44106100 :       FOR_ALL_BB_FN (bb, cfun)
     616                 :   40659800 :         alloc_aux_for_block (bb, size);
     617                 :            :     }
     618                 :    3446290 : }
     619                 :            : 
     620                 :            : /* Clear AUX pointers of all blocks.  */
     621                 :            : 
     622                 :            : void
     623                 :    8664020 : clear_aux_for_blocks (void)
     624                 :            : {
     625                 :    8664020 :   basic_block bb;
     626                 :            : 
     627                 :  127292000 :   FOR_ALL_BB_FN (bb, cfun)
     628                 :  118628000 :     bb->aux = NULL;
     629                 :    8664020 : }
     630                 :            : 
     631                 :            : /* Free data allocated in block_aux_obstack and clear AUX pointers
     632                 :            :    of all blocks.  */
     633                 :            : 
     634                 :            : void
     635                 :    3446290 : free_aux_for_blocks (void)
     636                 :            : {
     637                 :    3446290 :   gcc_assert (first_block_aux_obj);
     638                 :    3446290 :   obstack_free (&block_aux_obstack, first_block_aux_obj);
     639                 :    3446290 :   first_block_aux_obj = NULL;
     640                 :            : 
     641                 :    3446290 :   clear_aux_for_blocks ();
     642                 :    3446290 : }
     643                 :            : 
     644                 :            : /* Allocate a memory edge of SIZE as E->aux.  The obstack must
     645                 :            :    be first initialized by alloc_aux_for_edges.  */
     646                 :            : 
     647                 :            : void
     648                 :   17489200 : alloc_aux_for_edge (edge e, int size)
     649                 :            : {
     650                 :            :   /* Verify that aux field is clear.  */
     651                 :   17489200 :   gcc_assert (!e->aux && first_edge_aux_obj);
     652                 :   17489200 :   e->aux = obstack_alloc (&edge_aux_obstack, size);
     653                 :   17489200 :   memset (e->aux, 0, size);
     654                 :   17489200 : }
     655                 :            : 
     656                 :            : /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
     657                 :            :    alloc_aux_for_edge for each basic edge.  */
     658                 :            : 
     659                 :            : void
     660                 :    2077820 : alloc_aux_for_edges (int size)
     661                 :            : {
     662                 :    2077820 :   static int initialized;
     663                 :            : 
     664                 :    2077820 :   if (!initialized)
     665                 :            :     {
     666                 :     108543 :       gcc_obstack_init (&edge_aux_obstack);
     667                 :     108543 :       initialized = 1;
     668                 :            :     }
     669                 :            :   else
     670                 :            :     /* Check whether AUX data are still allocated.  */
     671                 :    1969280 :     gcc_assert (!first_edge_aux_obj);
     672                 :            : 
     673                 :    2077820 :   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
     674                 :    2077820 :   if (size)
     675                 :            :     {
     676                 :    1759660 :       basic_block bb;
     677                 :            : 
     678                 :   14471400 :       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     679                 :            :                       EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     680                 :            :         {
     681                 :   12711700 :           edge e;
     682                 :   12711700 :           edge_iterator ei;
     683                 :            : 
     684                 :   30189300 :           FOR_EACH_EDGE (e, ei, bb->succs)
     685                 :   17477600 :             alloc_aux_for_edge (e, size);
     686                 :            :         }
     687                 :            :     }
     688                 :    2077820 : }
     689                 :            : 
     690                 :            : /* Clear AUX pointers of all edges.  */
     691                 :            : 
     692                 :            : void
     693                 :    4162920 : clear_aux_for_edges (void)
     694                 :            : {
     695                 :    4162920 :   basic_block bb;
     696                 :    4162920 :   edge e;
     697                 :            : 
     698                 :   66486500 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     699                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     700                 :            :     {
     701                 :   62323600 :       edge_iterator ei;
     702                 :  151699000 :       FOR_EACH_EDGE (e, ei, bb->succs)
     703                 :   89374900 :         e->aux = NULL;
     704                 :            :     }
     705                 :    4162920 : }
     706                 :            : 
     707                 :            : /* Free data allocated in edge_aux_obstack and clear AUX pointers
     708                 :            :    of all edges.  */
     709                 :            : 
     710                 :            : void
     711                 :    2077820 : free_aux_for_edges (void)
     712                 :            : {
     713                 :    2077820 :   gcc_assert (first_edge_aux_obj);
     714                 :    2077820 :   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
     715                 :    2077820 :   first_edge_aux_obj = NULL;
     716                 :            : 
     717                 :    2077820 :   clear_aux_for_edges ();
     718                 :    2077820 : }
     719                 :            : 
     720                 :            : DEBUG_FUNCTION void
     721                 :          0 : debug_bb (basic_block bb)
     722                 :            : {
     723                 :          0 :   dump_bb (stderr, bb, 0, dump_flags);
     724                 :          0 : }
     725                 :            : 
     726                 :            : DEBUG_FUNCTION basic_block
     727                 :          0 : debug_bb_n (int n)
     728                 :            : {
     729                 :          0 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
     730                 :          0 :   debug_bb (bb);
     731                 :          0 :   return bb;
     732                 :            : }
     733                 :            : 
     734                 :            : /* Dumps cfg related information about basic block BB to OUTF.
     735                 :            :    If HEADER is true, dump things that appear before the instructions
     736                 :            :    contained in BB.  If FOOTER is true, dump things that appear after.
     737                 :            :    Flags are the TDF_* masks as documented in dumpfile.h.
     738                 :            :    NB: With TDF_DETAILS, it is assumed that cfun is available, so
     739                 :            :    that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.  */
     740                 :            : 
     741                 :            : void
     742                 :      51836 : dump_bb_info (FILE *outf, basic_block bb, int indent, dump_flags_t flags,
     743                 :            :               bool do_header, bool do_footer)
     744                 :            : {
     745                 :      51836 :   edge_iterator ei;
     746                 :      51836 :   edge e;
     747                 :      51836 :   static const char * const bb_bitnames[] =
     748                 :            :     {
     749                 :            : #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
     750                 :            : #include "cfg-flags.def"
     751                 :            :       NULL
     752                 :            : #undef DEF_BASIC_BLOCK_FLAG
     753                 :            :     };
     754                 :      51836 :   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
     755                 :      51836 :   bool first;
     756                 :      51836 :   char *s_indent = (char *) alloca ((size_t) indent + 1);
     757                 :      51836 :   memset ((void *) s_indent, ' ', (size_t) indent);
     758                 :      51836 :   s_indent[indent] = '\0';
     759                 :            : 
     760                 :      51836 :   gcc_assert (bb->flags <= BB_ALL_FLAGS);
     761                 :            : 
     762                 :      51836 :   if (do_header)
     763                 :            :     {
     764                 :      26000 :       unsigned i;
     765                 :            : 
     766                 :      26000 :       fputs (";; ", outf);
     767                 :      26000 :       fprintf (outf, "%sbasic block %d, loop depth %d",
     768                 :            :                s_indent, bb->index, bb_loop_depth (bb));
     769                 :      26000 :       if (flags & TDF_DETAILS)
     770                 :            :         {
     771                 :       6212 :           struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
     772                 :       6212 :           if (bb->count.initialized_p ())
     773                 :            :             {
     774                 :       4957 :               fputs (", count ", outf);
     775                 :       4957 :               bb->count.dump (outf);
     776                 :            :             }
     777                 :       6212 :           if (maybe_hot_bb_p (fun, bb))
     778                 :       5403 :             fputs (", maybe hot", outf);
     779                 :       6212 :           if (probably_never_executed_bb_p (fun, bb))
     780                 :        775 :             fputs (", probably never executed", outf);
     781                 :            :         }
     782                 :      26000 :       fputc ('\n', outf);
     783                 :            : 
     784                 :      26000 :       if (flags & TDF_DETAILS)
     785                 :            :         {
     786                 :       6212 :           check_bb_profile (bb, outf, indent);
     787                 :       6212 :           fputs (";; ", outf);
     788                 :       6212 :           fprintf (outf, "%s prev block ", s_indent);
     789                 :       6212 :           if (bb->prev_bb)
     790                 :       6182 :             fprintf (outf, "%d", bb->prev_bb->index);
     791                 :            :           else
     792                 :         30 :             fprintf (outf, "(nil)");
     793                 :       6212 :           fprintf (outf, ", next block ");
     794                 :       6212 :           if (bb->next_bb)
     795                 :       6182 :             fprintf (outf, "%d", bb->next_bb->index);
     796                 :            :           else
     797                 :         30 :             fprintf (outf, "(nil)");
     798                 :            : 
     799                 :       6212 :           fputs (", flags:", outf);
     800                 :       6212 :           first = true;
     801                 :     105604 :           for (i = 0; i < n_bitnames; i++)
     802                 :      99392 :             if (bb->flags & (1 << i))
     803                 :            :               {
     804                 :      12959 :                 if (first)
     805                 :       6212 :                   fputs (" (", outf);
     806                 :            :                 else
     807                 :       6747 :                   fputs (", ", outf);
     808                 :      12959 :                 first = false;
     809                 :      12959 :                 fputs (bb_bitnames[i], outf);
     810                 :            :               }
     811                 :       6212 :           if (!first)
     812                 :       6212 :             fputc (')', outf);
     813                 :       6212 :           fputc ('\n', outf);
     814                 :            :         }
     815                 :            : 
     816                 :      26000 :       fputs (";; ", outf);
     817                 :      26000 :       fprintf (outf, "%s pred:      ", s_indent);
     818                 :      26000 :       first = true;
     819                 :      39593 :       FOR_EACH_EDGE (e, ei, bb->preds)
     820                 :            :         {
     821                 :      13593 :           if (! first)
     822                 :            :             {
     823                 :       2963 :               fputs (";; ", outf);
     824                 :       2963 :               fprintf (outf, "%s            ", s_indent);
     825                 :            :             }
     826                 :      13593 :           first = false;
     827                 :      13593 :           dump_edge_info (outf, e, flags, 0);
     828                 :      13593 :           fputc ('\n', outf);
     829                 :            :         }
     830                 :      26000 :       if (first)
     831                 :      15370 :         fputc ('\n', outf);
     832                 :            :     }
     833                 :            : 
     834                 :      51836 :   if (do_footer)
     835                 :            :     {
     836                 :      26000 :       fputs (";; ", outf);
     837                 :      26000 :       fprintf (outf, "%s succ:      ", s_indent);
     838                 :      26000 :       first = true;
     839                 :      50880 :       FOR_EACH_EDGE (e, ei, bb->succs)
     840                 :            :         {
     841                 :      24880 :           if (! first)
     842                 :            :             {
     843                 :       3949 :               fputs (";; ", outf);
     844                 :       3949 :               fprintf (outf, "%s            ", s_indent);
     845                 :            :             }
     846                 :      24880 :           first = false;
     847                 :      24880 :           dump_edge_info (outf, e, flags, 1);
     848                 :      24880 :           fputc ('\n', outf);
     849                 :            :         }
     850                 :      26000 :       if (first)
     851                 :       5069 :         fputc ('\n', outf);
     852                 :            :     }
     853                 :      51836 : }
     854                 :            : 
     855                 :            : /* Dumps a brief description of cfg to FILE.  */
     856                 :            : 
     857                 :            : void
     858                 :         22 : brief_dump_cfg (FILE *file, dump_flags_t flags)
     859                 :            : {
     860                 :         22 :   basic_block bb;
     861                 :            : 
     862                 :        186 :   FOR_EACH_BB_FN (bb, cfun)
     863                 :            :     {
     864                 :        164 :       dump_bb_info (file, bb, 0, flags & TDF_DETAILS, true, true);
     865                 :            :     }
     866                 :         22 : }
     867                 :            : 
     868                 :            : /* An edge originally destinating BB of COUNT has been proved to
     869                 :            :    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
     870                 :            :    redirected to destination of TAKEN_EDGE.
     871                 :            : 
     872                 :            :    This function may leave the profile inconsistent in the case TAKEN_EDGE
     873                 :            :    frequency or count is believed to be lower than COUNT
     874                 :            :    respectively.  */
     875                 :            : void
     876                 :     147206 : update_bb_profile_for_threading (basic_block bb, 
     877                 :            :                                  profile_count count, edge taken_edge)
     878                 :            : {
     879                 :     147206 :   edge c;
     880                 :     147206 :   profile_probability prob;
     881                 :     147206 :   edge_iterator ei;
     882                 :            : 
     883                 :     147206 :   if (bb->count < count)
     884                 :            :     {
     885                 :        385 :       if (dump_file)
     886                 :          0 :         fprintf (dump_file, "bb %i count became negative after threading",
     887                 :            :                  bb->index);
     888                 :            :     }
     889                 :     147206 :   bb->count -= count;
     890                 :            : 
     891                 :            :   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
     892                 :            :      Watch for overflows.  */
     893                 :     147206 :   if (bb->count.nonzero_p ())
     894                 :     129969 :     prob = count.probability_in (bb->count);
     895                 :            :   else
     896                 :      17237 :     prob = profile_probability::never ();
     897                 :     147206 :   if (prob > taken_edge->probability)
     898                 :            :     {
     899                 :      73141 :       if (dump_file)
     900                 :            :         {
     901                 :         17 :           fprintf (dump_file, "Jump threading proved probability of edge "
     902                 :            :                    "%i->%i too small (it is ",
     903                 :         17 :                    taken_edge->src->index, taken_edge->dest->index);        
     904                 :         17 :           taken_edge->probability.dump (dump_file);
     905                 :         17 :           fprintf (dump_file, " should be ");
     906                 :         17 :           prob.dump (dump_file);
     907                 :         17 :           fprintf (dump_file, ")\n");
     908                 :            :         }
     909                 :      73141 :       prob = taken_edge->probability.apply_scale (6, 8);
     910                 :            :     }
     911                 :            : 
     912                 :            :   /* Now rescale the probabilities.  */
     913                 :     147206 :   taken_edge->probability -= prob;
     914                 :     147206 :   prob = prob.invert ();
     915                 :     147206 :   if (prob == profile_probability::never ())
     916                 :            :     {
     917                 :          0 :       if (dump_file)
     918                 :          0 :         fprintf (dump_file, "Edge probabilities of bb %i has been reset, "
     919                 :            :                  "count of block should end up being 0, it is non-zero\n",
     920                 :            :                  bb->index);
     921                 :          0 :       EDGE_SUCC (bb, 0)->probability = profile_probability::guessed_always ();
     922                 :          0 :       ei = ei_start (bb->succs);
     923                 :          0 :       ei_next (&ei);
     924                 :          0 :       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
     925                 :          0 :         c->probability = profile_probability::guessed_never ();
     926                 :            :     }
     927                 :     165645 :   else if (!(prob == profile_probability::always ()))
     928                 :            :     {
     929                 :     389383 :       FOR_EACH_EDGE (c, ei, bb->succs)
     930                 :     260616 :         c->probability /= prob;
     931                 :            :     }
     932                 :            : 
     933                 :     147206 :   gcc_assert (bb == taken_edge->src);
     934                 :     147206 : }
     935                 :            : 
     936                 :            : /* Multiply all frequencies of basic blocks in array BBS of length NBBS
     937                 :            :    by NUM/DEN, in profile_count arithmetic.  More accurate than previous
     938                 :            :    function but considerably slower.  */
     939                 :            : void
     940                 :     870677 : scale_bbs_frequencies_profile_count (basic_block *bbs, int nbbs,
     941                 :            :                                      profile_count num, profile_count den)
     942                 :            : {
     943                 :     870677 :   int i;
     944                 :    1747270 :   if (num == profile_count::zero () || den.nonzero_p ())
     945                 :    1768490 :     for (i = 0; i < nbbs; i++)
     946                 :     898249 :       bbs[i]->count = bbs[i]->count.apply_scale (num, den);
     947                 :     870677 : }
     948                 :            : 
     949                 :            : /* Multiply all frequencies of basic blocks in array BBS of length NBBS
     950                 :            :    by NUM/DEN, in profile_count arithmetic.  More accurate than previous
     951                 :            :    function but considerably slower.  */
     952                 :            : void
     953                 :     486566 : scale_bbs_frequencies (basic_block *bbs, int nbbs,
     954                 :            :                        profile_probability p)
     955                 :            : {
     956                 :     486566 :   int i;
     957                 :            : 
     958                 :    1676230 :   for (i = 0; i < nbbs; i++)
     959                 :    1189660 :     bbs[i]->count = bbs[i]->count.apply_probability (p);
     960                 :     486566 : }
     961                 :            : 
     962                 :            : /* Helper types for hash tables.  */
     963                 :            : 
     964                 :            : struct htab_bb_copy_original_entry
     965                 :            : {
     966                 :            :   /* Block we are attaching info to.  */
     967                 :            :   int index1;
     968                 :            :   /* Index of original or copy (depending on the hashtable) */
     969                 :            :   int index2;
     970                 :            : };
     971                 :            : 
     972                 :            : struct bb_copy_hasher : nofree_ptr_hash <htab_bb_copy_original_entry>
     973                 :            : {
     974                 :            :   static inline hashval_t hash (const htab_bb_copy_original_entry *);
     975                 :            :   static inline bool equal (const htab_bb_copy_original_entry *existing,
     976                 :            :                             const htab_bb_copy_original_entry * candidate);
     977                 :            : };
     978                 :            : 
     979                 :            : inline hashval_t
     980                 :   31314000 : bb_copy_hasher::hash (const htab_bb_copy_original_entry *data)
     981                 :            : {
     982                 :   31314000 :   return data->index1;
     983                 :            : }
     984                 :            : 
     985                 :            : inline bool
     986                 :   21069500 : bb_copy_hasher::equal (const htab_bb_copy_original_entry *data,
     987                 :            :                        const htab_bb_copy_original_entry *data2)
     988                 :            : {
     989                 :   21069500 :   return data->index1 == data2->index1;
     990                 :            : }
     991                 :            : 
     992                 :            : /* Data structures used to maintain mapping between basic blocks and
     993                 :            :    copies.  */
     994                 :            : static hash_table<bb_copy_hasher> *bb_original;
     995                 :            : static hash_table<bb_copy_hasher> *bb_copy;
     996                 :            : 
     997                 :            : /* And between loops and copies.  */
     998                 :            : static hash_table<bb_copy_hasher> *loop_copy;
     999                 :            : static object_allocator<htab_bb_copy_original_entry> *original_copy_bb_pool;
    1000                 :            : 
    1001                 :            : /* Initialize the data structures to maintain mapping between blocks
    1002                 :            :    and its copies.  */
    1003                 :            : void
    1004                 :    3680460 : initialize_original_copy_tables (void)
    1005                 :            : {
    1006                 :    7360920 :   original_copy_bb_pool = new object_allocator<htab_bb_copy_original_entry>
    1007                 :    3680460 :     ("original_copy");
    1008                 :    3680460 :   bb_original = new hash_table<bb_copy_hasher> (10);
    1009                 :    3680460 :   bb_copy = new hash_table<bb_copy_hasher> (10);
    1010                 :    3680460 :   loop_copy = new hash_table<bb_copy_hasher> (10);
    1011                 :    3680460 : }
    1012                 :            : 
    1013                 :            : /* Reset the data structures to maintain mapping between blocks and
    1014                 :            :    its copies.  */
    1015                 :            : 
    1016                 :            : void
    1017                 :        194 : reset_original_copy_tables (void)
    1018                 :            : {
    1019                 :        194 :   gcc_assert (original_copy_bb_pool);
    1020                 :        194 :   bb_original->empty ();
    1021                 :        194 :   bb_copy->empty ();
    1022                 :        194 :   loop_copy->empty ();
    1023                 :        194 : }
    1024                 :            : 
    1025                 :            : /* Free the data structures to maintain mapping between blocks and
    1026                 :            :    its copies.  */
    1027                 :            : void
    1028                 :    3680460 : free_original_copy_tables (void)
    1029                 :            : {
    1030                 :    3680460 :   gcc_assert (original_copy_bb_pool);
    1031                 :    3680460 :   delete bb_copy;
    1032                 :    3680460 :   bb_copy = NULL;
    1033                 :    3680460 :   delete bb_original;
    1034                 :    3680460 :   bb_original = NULL;
    1035                 :    3680460 :   delete loop_copy;
    1036                 :    3680460 :   loop_copy = NULL;
    1037                 :    7360920 :   delete original_copy_bb_pool;
    1038                 :    3680460 :   original_copy_bb_pool = NULL;
    1039                 :    3680460 : }
    1040                 :            : 
    1041                 :            : /* Return true iff we have had a call to initialize_original_copy_tables
    1042                 :            :    without a corresponding call to free_original_copy_tables.  */
    1043                 :            : 
    1044                 :            : bool
    1045                 :    2084510 : original_copy_tables_initialized_p (void)
    1046                 :            : {
    1047                 :    2084510 :   return original_copy_bb_pool != NULL;
    1048                 :            : }
    1049                 :            : 
    1050                 :            : /* Removes the value associated with OBJ from table TAB.  */
    1051                 :            : 
    1052                 :            : static void
    1053                 :     841363 : copy_original_table_clear (hash_table<bb_copy_hasher> *tab, unsigned obj)
    1054                 :            : {
    1055                 :     841363 :   htab_bb_copy_original_entry **slot;
    1056                 :     841363 :   struct htab_bb_copy_original_entry key, *elt;
    1057                 :            : 
    1058                 :     841363 :   if (!original_copy_bb_pool)
    1059                 :          0 :     return;
    1060                 :            : 
    1061                 :     841363 :   key.index1 = obj;
    1062                 :     841363 :   slot = tab->find_slot (&key, NO_INSERT);
    1063                 :     841363 :   if (!slot)
    1064                 :            :     return;
    1065                 :            : 
    1066                 :     841363 :   elt = *slot;
    1067                 :     841363 :   tab->clear_slot (slot);
    1068                 :     841363 :   original_copy_bb_pool->remove (elt);
    1069                 :            : }
    1070                 :            : 
    1071                 :            : /* Sets the value associated with OBJ in table TAB to VAL.
    1072                 :            :    Do nothing when data structures are not initialized.  */
    1073                 :            : 
    1074                 :            : static void
    1075                 :    5526970 : copy_original_table_set (hash_table<bb_copy_hasher> *tab,
    1076                 :            :                          unsigned obj, unsigned val)
    1077                 :            : {
    1078                 :    5526970 :   struct htab_bb_copy_original_entry **slot;
    1079                 :    5526970 :   struct htab_bb_copy_original_entry key;
    1080                 :            : 
    1081                 :    5526970 :   if (!original_copy_bb_pool)
    1082                 :      38994 :     return;
    1083                 :            : 
    1084                 :    5487970 :   key.index1 = obj;
    1085                 :    5487970 :   slot = tab->find_slot (&key, INSERT);
    1086                 :    5487970 :   if (!*slot)
    1087                 :            :     {
    1088                 :    4874340 :       *slot = original_copy_bb_pool->allocate ();
    1089                 :    4874340 :       (*slot)->index1 = obj;
    1090                 :            :     }
    1091                 :    5487970 :   (*slot)->index2 = val;
    1092                 :            : }
    1093                 :            : 
    1094                 :            : /* Set original for basic block.  Do nothing when data structures are not
    1095                 :            :    initialized so passes not needing this don't need to care.  */
    1096                 :            : void
    1097                 :    2039030 : set_bb_original (basic_block bb, basic_block original)
    1098                 :            : {
    1099                 :    2039030 :   copy_original_table_set (bb_original, bb->index, original->index);
    1100                 :    2039030 : }
    1101                 :            : 
    1102                 :            : /* Get the original basic block.  */
    1103                 :            : basic_block
    1104                 :    1300220 : get_bb_original (basic_block bb)
    1105                 :            : {
    1106                 :    1300220 :   struct htab_bb_copy_original_entry *entry;
    1107                 :    1300220 :   struct htab_bb_copy_original_entry key;
    1108                 :            : 
    1109                 :    1300220 :   gcc_assert (original_copy_bb_pool);
    1110                 :            : 
    1111                 :    1300220 :   key.index1 = bb->index;
    1112                 :    1300220 :   entry = bb_original->find (&key);
    1113                 :    1300220 :   if (entry)
    1114                 :    1270500 :     return BASIC_BLOCK_FOR_FN (cfun, entry->index2);
    1115                 :            :   else
    1116                 :            :     return NULL;
    1117                 :            : }
    1118                 :            : 
    1119                 :            : /* Set copy for basic block.  Do nothing when data structures are not
    1120                 :            :    initialized so passes not needing this don't need to care.  */
    1121                 :            : void
    1122                 :    2039030 : set_bb_copy (basic_block bb, basic_block copy)
    1123                 :            : {
    1124                 :    2039030 :   copy_original_table_set (bb_copy, bb->index, copy->index);
    1125                 :    2039030 : }
    1126                 :            : 
    1127                 :            : /* Get the copy of basic block.  */
    1128                 :            : basic_block
    1129                 :    1991460 : get_bb_copy (basic_block bb)
    1130                 :            : {
    1131                 :    1991460 :   struct htab_bb_copy_original_entry *entry;
    1132                 :    1991460 :   struct htab_bb_copy_original_entry key;
    1133                 :            : 
    1134                 :    1991460 :   gcc_assert (original_copy_bb_pool);
    1135                 :            : 
    1136                 :    1991460 :   key.index1 = bb->index;
    1137                 :    1991460 :   entry = bb_copy->find (&key);
    1138                 :    1991460 :   if (entry)
    1139                 :    1986830 :     return BASIC_BLOCK_FOR_FN (cfun, entry->index2);
    1140                 :            :   else
    1141                 :            :     return NULL;
    1142                 :            : }
    1143                 :            : 
    1144                 :            : /* Set copy for LOOP to COPY.  Do nothing when data structures are not
    1145                 :            :    initialized so passes not needing this don't need to care.  */
    1146                 :            : 
    1147                 :            : void
    1148                 :    2290270 : set_loop_copy (class loop *loop, class loop *copy)
    1149                 :            : {
    1150                 :    2290270 :   if (!copy)
    1151                 :     841363 :     copy_original_table_clear (loop_copy, loop->num);
    1152                 :            :   else
    1153                 :    1448910 :     copy_original_table_set (loop_copy, loop->num, copy->num);
    1154                 :    2290270 : }
    1155                 :            : 
    1156                 :            : /* Get the copy of LOOP.  */
    1157                 :            : 
    1158                 :            : class loop *
    1159                 :    1888360 : get_loop_copy (class loop *loop)
    1160                 :            : {
    1161                 :    1888360 :   struct htab_bb_copy_original_entry *entry;
    1162                 :    1888360 :   struct htab_bb_copy_original_entry key;
    1163                 :            : 
    1164                 :    1888360 :   gcc_assert (original_copy_bb_pool);
    1165                 :            : 
    1166                 :    1888360 :   key.index1 = loop->num;
    1167                 :    1888360 :   entry = loop_copy->find (&key);
    1168                 :    1888360 :   if (entry)
    1169                 :    1451330 :     return get_loop (cfun, entry->index2);
    1170                 :            :   else
    1171                 :            :     return NULL;
    1172                 :            : }

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.