LCOV - code coverage report
Current view: top level - gcc - cfganal.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 573 675 84.9 %
Date: 2020-03-28 11:57:23 Functions: 36 41 87.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Control flow graph analysis 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 various simple utilities to analyze the CFG.  */
      21                 :            : 
      22                 :            : #include "config.h"
      23                 :            : #include "system.h"
      24                 :            : #include "coretypes.h"
      25                 :            : #include "backend.h"
      26                 :            : #include "cfghooks.h"
      27                 :            : #include "timevar.h"
      28                 :            : #include "cfganal.h"
      29                 :            : #include "cfgloop.h"
      30                 :            : 
      31                 :            : namespace {
      32                 :            : /* Store the data structures necessary for depth-first search.  */
      33                 :            : class depth_first_search
      34                 :            :   {
      35                 :            : public:
      36                 :            :     depth_first_search ();
      37                 :            : 
      38                 :            :     basic_block execute (basic_block);
      39                 :            :     void add_bb (basic_block);
      40                 :            : 
      41                 :            : private:
      42                 :            :   /* stack for backtracking during the algorithm */
      43                 :            :   auto_vec<basic_block, 20> m_stack;
      44                 :            : 
      45                 :            :   /* record of basic blocks already seen by depth-first search */
      46                 :            :   auto_sbitmap m_visited_blocks;
      47                 :            : };
      48                 :            : }
      49                 :            : 
      50                 :            : /* Mark the back edges in DFS traversal.
      51                 :            :    Return nonzero if a loop (natural or otherwise) is present.
      52                 :            :    Inspired by Depth_First_Search_PP described in:
      53                 :            : 
      54                 :            :      Advanced Compiler Design and Implementation
      55                 :            :      Steven Muchnick
      56                 :            :      Morgan Kaufmann, 1997
      57                 :            : 
      58                 :            :    and heavily borrowed from pre_and_rev_post_order_compute.  */
      59                 :            : 
      60                 :            : bool
      61                 :   16615800 : mark_dfs_back_edges (void)
      62                 :            : {
      63                 :   16615800 :   int *pre;
      64                 :   16615800 :   int *post;
      65                 :   16615800 :   int prenum = 1;
      66                 :   16615800 :   int postnum = 1;
      67                 :   16615800 :   bool found = false;
      68                 :            : 
      69                 :            :   /* Allocate the preorder and postorder number arrays.  */
      70                 :   16615800 :   pre = XCNEWVEC (int, last_basic_block_for_fn (cfun));
      71                 :   16615800 :   post = XCNEWVEC (int, last_basic_block_for_fn (cfun));
      72                 :            : 
      73                 :            :   /* Allocate stack for back-tracking up CFG.  */
      74                 :   16615800 :   auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
      75                 :            : 
      76                 :            :   /* Allocate bitmap to track nodes that have been visited.  */
      77                 :   33231600 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
      78                 :            : 
      79                 :            :   /* None of the nodes in the CFG have been visited yet.  */
      80                 :   16615800 :   bitmap_clear (visited);
      81                 :            : 
      82                 :            :   /* Push the first edge on to the stack.  */
      83                 :   16615800 :   stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
      84                 :            : 
      85                 :  452504000 :   while (!stack.is_empty ())
      86                 :            :     {
      87                 :  435888000 :       basic_block src;
      88                 :  435888000 :       basic_block dest;
      89                 :            : 
      90                 :            :       /* Look at the edge on the top of the stack.  */
      91                 :  435888000 :       edge_iterator ei = stack.last ();
      92                 :  435888000 :       src = ei_edge (ei)->src;
      93                 :  435888000 :       dest = ei_edge (ei)->dest;
      94                 :  435888000 :       ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
      95                 :            : 
      96                 :            :       /* Check if the edge destination has been visited yet.  */
      97                 :  854343000 :       if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && ! bitmap_bit_p (visited,
      98                 :  418455000 :                                                                   dest->index))
      99                 :            :         {
     100                 :            :           /* Mark that we have visited the destination.  */
     101                 :  174796000 :           bitmap_set_bit (visited, dest->index);
     102                 :            : 
     103                 :  174796000 :           pre[dest->index] = prenum++;
     104                 :  174796000 :           if (EDGE_COUNT (dest->succs) > 0)
     105                 :            :             {
     106                 :            :               /* Since the DEST node has been visited for the first
     107                 :            :                  time, check its successors.  */
     108                 :  164909000 :               stack.quick_push (ei_start (dest->succs));
     109                 :            :             }
     110                 :            :           else
     111                 :    9886480 :             post[dest->index] = postnum++;
     112                 :            :         }
     113                 :            :       else
     114                 :            :         {
     115                 :  261092000 :           if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     116                 :  243659000 :               && src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     117                 :  227043000 :               && pre[src->index] >= pre[dest->index]
     118                 :   55018800 :               && post[dest->index] == 0)
     119                 :    8603290 :             ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
     120                 :            : 
     121                 :  261092000 :           if (ei_one_before_end_p (ei)
     122                 :  261092000 :               && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
     123                 :  164909000 :             post[src->index] = postnum++;
     124                 :            : 
     125                 :  261092000 :           if (!ei_one_before_end_p (ei))
     126                 :   79566700 :             ei_next (&stack.last ());
     127                 :            :           else
     128                 :  181525000 :             stack.pop ();
     129                 :            :         }
     130                 :            :     }
     131                 :            : 
     132                 :   16615800 :   free (pre);
     133                 :   16615800 :   free (post);
     134                 :            : 
     135                 :   16615800 :   return found;
     136                 :            : }
     137                 :            : 
     138                 :            : /* Find unreachable blocks.  An unreachable block will have 0 in
     139                 :            :    the reachable bit in block->flags.  A nonzero value indicates the
     140                 :            :    block is reachable.  */
     141                 :            : 
     142                 :            : void
     143                 :   47056200 : find_unreachable_blocks (void)
     144                 :            : {
     145                 :   47056200 :   edge e;
     146                 :   47056200 :   edge_iterator ei;
     147                 :   47056200 :   basic_block *tos, *worklist, bb;
     148                 :            : 
     149                 :   47056200 :   tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
     150                 :            : 
     151                 :            :   /* Clear all the reachability flags.  */
     152                 :            : 
     153                 :  638692000 :   FOR_EACH_BB_FN (bb, cfun)
     154                 :  591636000 :     bb->flags &= ~BB_REACHABLE;
     155                 :            : 
     156                 :            :   /* Add our starting points to the worklist.  Almost always there will
     157                 :            :      be only one.  It isn't inconceivable that we might one day directly
     158                 :            :      support Fortran alternate entry points.  */
     159                 :            : 
     160                 :   94112300 :   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
     161                 :            :     {
     162                 :   47056200 :       *tos++ = e->dest;
     163                 :            : 
     164                 :            :       /* Mark the block reachable.  */
     165                 :   47056200 :       e->dest->flags |= BB_REACHABLE;
     166                 :            :     }
     167                 :            : 
     168                 :            :   /* Iterate: find everything reachable from what we've already seen.  */
     169                 :            : 
     170                 :  642041000 :   while (tos != worklist)
     171                 :            :     {
     172                 :  594985000 :       basic_block b = *--tos;
     173                 :            : 
     174                 : 1453070000 :       FOR_EACH_EDGE (e, ei, b->succs)
     175                 :            :         {
     176                 :  858083000 :           basic_block dest = e->dest;
     177                 :            : 
     178                 :  858083000 :           if (!(dest->flags & BB_REACHABLE))
     179                 :            :             {
     180                 :  547929000 :               *tos++ = dest;
     181                 :  547929000 :               dest->flags |= BB_REACHABLE;
     182                 :            :             }
     183                 :            :         }
     184                 :            :     }
     185                 :            : 
     186                 :   47056200 :   free (worklist);
     187                 :   47056200 : }
     188                 :            : 
     189                 :            : /* Verify that there are no unreachable blocks in the current function.  */
     190                 :            : 
     191                 :            : void
     192                 :   27556400 : verify_no_unreachable_blocks (void)
     193                 :            : {
     194                 :   27556400 :   find_unreachable_blocks ();
     195                 :            : 
     196                 :   27556400 :   basic_block bb;
     197                 :  365611000 :   FOR_EACH_BB_FN (bb, cfun)
     198                 :  338055000 :     gcc_assert ((bb->flags & BB_REACHABLE) != 0);
     199                 :   27556400 : }
     200                 :            : 
     201                 :            : 
     202                 :            : /* Functions to access an edge list with a vector representation.
     203                 :            :    Enough data is kept such that given an index number, the
     204                 :            :    pred and succ that edge represents can be determined, or
     205                 :            :    given a pred and a succ, its index number can be returned.
     206                 :            :    This allows algorithms which consume a lot of memory to
     207                 :            :    represent the normally full matrix of edge (pred,succ) with a
     208                 :            :    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
     209                 :            :    wasted space in the client code due to sparse flow graphs.  */
     210                 :            : 
     211                 :            : /* This functions initializes the edge list. Basically the entire
     212                 :            :    flowgraph is processed, and all edges are assigned a number,
     213                 :            :    and the data structure is filled in.  */
     214                 :            : 
     215                 :            : struct edge_list *
     216                 :     347405 : create_edge_list (void)
     217                 :            : {
     218                 :     347405 :   struct edge_list *elist;
     219                 :     347405 :   edge e;
     220                 :     347405 :   int num_edges;
     221                 :     347405 :   basic_block bb;
     222                 :     347405 :   edge_iterator ei;
     223                 :            : 
     224                 :            :   /* Determine the number of edges in the flow graph by counting successor
     225                 :            :      edges on each basic block.  */
     226                 :     347405 :   num_edges = 0;
     227                 :    6853800 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     228                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     229                 :            :     {
     230                 :   13012200 :       num_edges += EDGE_COUNT (bb->succs);
     231                 :            :     }
     232                 :            : 
     233                 :     347405 :   elist = XNEW (struct edge_list);
     234                 :     347405 :   elist->num_edges = num_edges;
     235                 :     347405 :   elist->index_to_edge = XNEWVEC (edge, num_edges);
     236                 :            : 
     237                 :     347405 :   num_edges = 0;
     238                 :            : 
     239                 :            :   /* Follow successors of blocks, and register these edges.  */
     240                 :    6853800 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     241                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     242                 :   16217100 :     FOR_EACH_EDGE (e, ei, bb->succs)
     243                 :    9710740 :       elist->index_to_edge[num_edges++] = e;
     244                 :            : 
     245                 :     347405 :   return elist;
     246                 :            : }
     247                 :            : 
     248                 :            : /* This function free's memory associated with an edge list.  */
     249                 :            : 
     250                 :            : void
     251                 :     347405 : free_edge_list (struct edge_list *elist)
     252                 :            : {
     253                 :     347405 :   if (elist)
     254                 :            :     {
     255                 :     347405 :       free (elist->index_to_edge);
     256                 :     347405 :       free (elist);
     257                 :            :     }
     258                 :     347405 : }
     259                 :            : 
     260                 :            : /* This function provides debug output showing an edge list.  */
     261                 :            : 
     262                 :            : DEBUG_FUNCTION void
     263                 :          0 : print_edge_list (FILE *f, struct edge_list *elist)
     264                 :            : {
     265                 :          0 :   int x;
     266                 :            : 
     267                 :          0 :   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
     268                 :          0 :            n_basic_blocks_for_fn (cfun), elist->num_edges);
     269                 :            : 
     270                 :          0 :   for (x = 0; x < elist->num_edges; x++)
     271                 :            :     {
     272                 :          0 :       fprintf (f, " %-4d - edge(", x);
     273                 :          0 :       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     274                 :          0 :         fprintf (f, "entry,");
     275                 :            :       else
     276                 :          0 :         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
     277                 :            : 
     278                 :          0 :       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR_FOR_FN (cfun))
     279                 :          0 :         fprintf (f, "exit)\n");
     280                 :            :       else
     281                 :          0 :         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
     282                 :            :     }
     283                 :          0 : }
     284                 :            : 
     285                 :            : /* This function provides an internal consistency check of an edge list,
     286                 :            :    verifying that all edges are present, and that there are no
     287                 :            :    extra edges.  */
     288                 :            : 
     289                 :            : DEBUG_FUNCTION void
     290                 :          0 : verify_edge_list (FILE *f, struct edge_list *elist)
     291                 :            : {
     292                 :          0 :   int pred, succ, index;
     293                 :          0 :   edge e;
     294                 :          0 :   basic_block bb, p, s;
     295                 :          0 :   edge_iterator ei;
     296                 :            : 
     297                 :          0 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     298                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     299                 :            :     {
     300                 :          0 :       FOR_EACH_EDGE (e, ei, bb->succs)
     301                 :            :         {
     302                 :          0 :           pred = e->src->index;
     303                 :          0 :           succ = e->dest->index;
     304                 :          0 :           index = EDGE_INDEX (elist, e->src, e->dest);
     305                 :          0 :           if (index == EDGE_INDEX_NO_EDGE)
     306                 :            :             {
     307                 :          0 :               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
     308                 :          0 :               continue;
     309                 :            :             }
     310                 :            : 
     311                 :          0 :           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
     312                 :          0 :             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
     313                 :            :                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
     314                 :          0 :           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
     315                 :          0 :             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
     316                 :            :                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
     317                 :            :         }
     318                 :            :     }
     319                 :            : 
     320                 :            :   /* We've verified that all the edges are in the list, now lets make sure
     321                 :            :      there are no spurious edges in the list.  This is an expensive check!  */
     322                 :            : 
     323                 :          0 :   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     324                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     325                 :          0 :     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
     326                 :            :       {
     327                 :          0 :         int found_edge = 0;
     328                 :            : 
     329                 :          0 :         FOR_EACH_EDGE (e, ei, p->succs)
     330                 :          0 :           if (e->dest == s)
     331                 :            :             {
     332                 :            :               found_edge = 1;
     333                 :            :               break;
     334                 :            :             }
     335                 :            : 
     336                 :          0 :         FOR_EACH_EDGE (e, ei, s->preds)
     337                 :          0 :           if (e->src == p)
     338                 :            :             {
     339                 :            :               found_edge = 1;
     340                 :            :               break;
     341                 :            :             }
     342                 :            : 
     343                 :          0 :         if (EDGE_INDEX (elist, p, s)
     344                 :          0 :             == EDGE_INDEX_NO_EDGE && found_edge != 0)
     345                 :          0 :           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
     346                 :            :                    p->index, s->index);
     347                 :          0 :         if (EDGE_INDEX (elist, p, s)
     348                 :          0 :             != EDGE_INDEX_NO_EDGE && found_edge == 0)
     349                 :          0 :           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
     350                 :            :                    p->index, s->index, EDGE_INDEX (elist, p, s));
     351                 :            :       }
     352                 :          0 : }
     353                 :            : 
     354                 :            : 
     355                 :            : /* Functions to compute control dependences.  */
     356                 :            : 
     357                 :            : /* Indicate block BB is control dependent on an edge with index EDGE_INDEX.  */
     358                 :            : void
     359                 :   25718900 : control_dependences::set_control_dependence_map_bit (basic_block bb,
     360                 :            :                                                      int edge_index)
     361                 :            : {
     362                 :   25718900 :   if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     363                 :            :     return;
     364                 :   25718900 :   gcc_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     365                 :   25718900 :   bitmap_set_bit (control_dependence_map[bb->index], edge_index);
     366                 :            : }
     367                 :            : 
     368                 :            : /* Clear all control dependences for block BB.  */
     369                 :            : void
     370                 :          0 : control_dependences::clear_control_dependence_bitmap (basic_block bb)
     371                 :            : {
     372                 :          0 :   bitmap_clear (control_dependence_map[bb->index]);
     373                 :          0 : }
     374                 :            : 
     375                 :            : /* Find the immediate postdominator PDOM of the specified basic block BLOCK.
     376                 :            :    This function is necessary because some blocks have negative numbers.  */
     377                 :            : 
     378                 :            : static inline basic_block
     379                 :   54425800 : find_pdom (basic_block block)
     380                 :            : {
     381                 :   54425800 :   gcc_assert (block != ENTRY_BLOCK_PTR_FOR_FN (cfun));
     382                 :            : 
     383                 :   54425800 :   if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
     384                 :            :     return EXIT_BLOCK_PTR_FOR_FN (cfun);
     385                 :            :   else
     386                 :            :     {
     387                 :   54425800 :       basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
     388                 :   54425800 :       if (! bb)
     389                 :          0 :         return EXIT_BLOCK_PTR_FOR_FN (cfun);
     390                 :            :       return bb;
     391                 :            :     }
     392                 :            : }
     393                 :            : 
     394                 :            : /* Determine all blocks' control dependences on the given edge with edge_list
     395                 :            :    EL index EDGE_INDEX, ala Morgan, Section 3.6.  */
     396                 :            : 
     397                 :            : void
     398                 :   31078300 : control_dependences::find_control_dependence (int edge_index)
     399                 :            : {
     400                 :   31078300 :   basic_block current_block;
     401                 :   31078300 :   basic_block ending_block;
     402                 :            : 
     403                 :   31078300 :   gcc_assert (get_edge_src (edge_index) != EXIT_BLOCK_PTR_FOR_FN (cfun));
     404                 :            : 
     405                 :            :   /* For abnormal edges, we don't make current_block control
     406                 :            :      dependent because instructions that throw are always necessary
     407                 :            :      anyway.  */
     408                 :   31078300 :   edge e = find_edge (get_edge_src (edge_index), get_edge_dest (edge_index));
     409                 :   31078300 :   if (e->flags & EDGE_ABNORMAL)
     410                 :            :     return;
     411                 :            : 
     412                 :   31067500 :   if (get_edge_src (edge_index) == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     413                 :    2360610 :     ending_block = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
     414                 :            :   else
     415                 :   28706900 :     ending_block = find_pdom (get_edge_src (edge_index));
     416                 :            : 
     417                 :   31067500 :   for (current_block = get_edge_dest (edge_index);
     418                 :            :        current_block != ending_block
     419                 :   56786400 :        && current_block != EXIT_BLOCK_PTR_FOR_FN (cfun);
     420                 :   25718900 :        current_block = find_pdom (current_block))
     421                 :   25718900 :     set_control_dependence_map_bit (current_block, edge_index);
     422                 :            : }
     423                 :            : 
     424                 :            : /* Record all blocks' control dependences on all edges in the edge
     425                 :            :    list EL, ala Morgan, Section 3.6.  */
     426                 :            : 
     427                 :    2360610 : control_dependences::control_dependences ()
     428                 :            : {
     429                 :    2360610 :   timevar_push (TV_CONTROL_DEPENDENCES);
     430                 :            : 
     431                 :            :   /* Initialize the edge list.  */
     432                 :    2360610 :   int num_edges = 0;
     433                 :    2360610 :   basic_block bb;
     434                 :   25266600 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     435                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     436                 :   45300600 :     num_edges += EDGE_COUNT (bb->succs);
     437                 :    2360610 :   m_el.create (num_edges);
     438                 :    2360610 :   edge e;
     439                 :    2360610 :   edge_iterator ei;
     440                 :   25266600 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     441                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     442                 :   53984300 :     FOR_EACH_EDGE (e, ei, bb->succs)
     443                 :   31078300 :       m_el.quick_push (std::make_pair (e->src->index, e->dest->index));
     444                 :            : 
     445                 :    2360610 :   control_dependence_map.create (last_basic_block_for_fn (cfun));
     446                 :   27989100 :   for (int i = 0; i < last_basic_block_for_fn (cfun); ++i)
     447                 :   25628400 :     control_dependence_map.quick_push (BITMAP_ALLOC (NULL));
     448                 :   33438900 :   for (int i = 0; i < num_edges; ++i)
     449                 :   31078300 :     find_control_dependence (i);
     450                 :            : 
     451                 :    2360610 :   timevar_pop (TV_CONTROL_DEPENDENCES);
     452                 :    2360610 : }
     453                 :            : 
     454                 :            : /* Free control dependences and the associated edge list.  */
     455                 :            : 
     456                 :    4721220 : control_dependences::~control_dependences ()
     457                 :            : {
     458                 :   55978100 :   for (unsigned i = 0; i < control_dependence_map.length (); ++i)
     459                 :   25628400 :     BITMAP_FREE (control_dependence_map[i]);
     460                 :    2360610 :   control_dependence_map.release ();
     461                 :    2360610 :   m_el.release ();
     462                 :    2360610 : }
     463                 :            : 
     464                 :            : /* Returns the bitmap of edges the basic-block I is dependent on.  */
     465                 :            : 
     466                 :            : bitmap
     467                 :   19358700 : control_dependences::get_edges_dependent_on (int i)
     468                 :            : {
     469                 :   19358700 :   return control_dependence_map[i];
     470                 :            : }
     471                 :            : 
     472                 :            : /* Returns the edge source with index I from the edge list.  */
     473                 :            : 
     474                 :            : basic_block
     475                 :  146651000 : control_dependences::get_edge_src (int i)
     476                 :            : {
     477                 :  146651000 :   return BASIC_BLOCK_FOR_FN (cfun, m_el[i].first);
     478                 :            : }
     479                 :            : 
     480                 :            : /* Returns the edge destination with index I from the edge list.  */
     481                 :            : 
     482                 :            : basic_block
     483                 :   62145800 : control_dependences::get_edge_dest (int i)
     484                 :            : {
     485                 :   62145800 :   return BASIC_BLOCK_FOR_FN (cfun, m_el[i].second);
     486                 :            : }
     487                 :            : 
     488                 :            : 
     489                 :            : /* Given PRED and SUCC blocks, return the edge which connects the blocks.
     490                 :            :    If no such edge exists, return NULL.  */
     491                 :            : 
     492                 :            : edge
     493                 :  396539000 : find_edge (basic_block pred, basic_block succ)
     494                 :            : {
     495                 :  396539000 :   edge e;
     496                 :  396539000 :   edge_iterator ei;
     497                 :            : 
     498                 : 1083020000 :   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
     499                 :            :     {
     500                 :  404240000 :       FOR_EACH_EDGE (e, ei, pred->succs)
     501                 :  300156000 :         if (e->dest == succ)
     502                 :  193181000 :           return e;
     503                 :            :     }
     504                 :            :   else
     505                 :            :     {
     506                 :  110865000 :       FOR_EACH_EDGE (e, ei, succ->preds)
     507                 :   61499900 :         if (e->src == pred)
     508                 :   49908900 :           return e;
     509                 :            :     }
     510                 :            : 
     511                 :            :   return NULL;
     512                 :            : }
     513                 :            : 
     514                 :            : /* This routine will determine what, if any, edge there is between
     515                 :            :    a specified predecessor and successor.  */
     516                 :            : 
     517                 :            : int
     518                 :         29 : find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
     519                 :            : {
     520                 :         29 :   int x;
     521                 :            : 
     522                 :        170 :   for (x = 0; x < NUM_EDGES (edge_list); x++)
     523                 :        170 :     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
     524                 :         53 :         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
     525                 :         29 :       return x;
     526                 :            : 
     527                 :            :   return (EDGE_INDEX_NO_EDGE);
     528                 :            : }
     529                 :            : 
     530                 :            : /* This routine will remove any fake predecessor edges for a basic block.
     531                 :            :    When the edge is removed, it is also removed from whatever successor
     532                 :            :    list it is in.  */
     533                 :            : 
     534                 :            : static void
     535                 :    4125570 : remove_fake_predecessors (basic_block bb)
     536                 :            : {
     537                 :    4125570 :   edge e;
     538                 :    4125570 :   edge_iterator ei;
     539                 :            : 
     540                 :   10620600 :   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
     541                 :            :     {
     542                 :    6495000 :       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
     543                 :    2346800 :         remove_edge (e);
     544                 :            :       else
     545                 :    4148200 :         ei_next (&ei);
     546                 :            :     }
     547                 :    4125570 : }
     548                 :            : 
     549                 :            : /* This routine will remove all fake edges from the flow graph.  If
     550                 :            :    we remove all fake successors, it will automatically remove all
     551                 :            :    fake predecessors.  */
     552                 :            : 
     553                 :            : void
     554                 :       2044 : remove_fake_edges (void)
     555                 :            : {
     556                 :       2044 :   basic_block bb;
     557                 :            : 
     558                 :      13836 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, NULL, next_bb)
     559                 :      11792 :     remove_fake_predecessors (bb);
     560                 :       2044 : }
     561                 :            : 
     562                 :            : /* This routine will remove all fake edges to the EXIT_BLOCK.  */
     563                 :            : 
     564                 :            : void
     565                 :    4113770 : remove_fake_exit_edges (void)
     566                 :            : {
     567                 :    4113770 :   remove_fake_predecessors (EXIT_BLOCK_PTR_FOR_FN (cfun));
     568                 :    4113770 : }
     569                 :            : 
     570                 :            : 
     571                 :            : /* This function will add a fake edge between any block which has no
     572                 :            :    successors, and the exit block. Some data flow equations require these
     573                 :            :    edges to exist.  */
     574                 :            : 
     575                 :            : void
     576                 :    2785310 : add_noreturn_fake_exit_edges (void)
     577                 :            : {
     578                 :    2785310 :   basic_block bb;
     579                 :            : 
     580                 :   26785000 :   FOR_EACH_BB_FN (bb, cfun)
     581                 :   23999600 :     if (EDGE_COUNT (bb->succs) == 0)
     582                 :    1479610 :       make_single_succ_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
     583                 :    2785310 : }
     584                 :            : 
     585                 :            : /* This function adds a fake edge between any infinite loops to the
     586                 :            :    exit block.  Some optimizations require a path from each node to
     587                 :            :    the exit node.
     588                 :            : 
     589                 :            :    See also Morgan, Figure 3.10, pp. 82-83.
     590                 :            : 
     591                 :            :    The current implementation is ugly, not attempting to minimize the
     592                 :            :    number of inserted fake edges.  To reduce the number of fake edges
     593                 :            :    to insert, add fake edges from _innermost_ loops containing only
     594                 :            :    nodes not reachable from the exit block.  */
     595                 :            : 
     596                 :            : void
     597                 :    3119580 : connect_infinite_loops_to_exit (void)
     598                 :            : {
     599                 :            :   /* Perform depth-first search in the reverse graph to find nodes
     600                 :            :      reachable from the exit block.  */
     601                 :    6239170 :   depth_first_search dfs;
     602                 :    3119580 :   dfs.add_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
     603                 :            : 
     604                 :            :   /* Repeatedly add fake edges, updating the unreachable nodes.  */
     605                 :    3119580 :   basic_block unvisited_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
     606                 :    4920900 :   while (1)
     607                 :            :     {
     608                 :    4020240 :       unvisited_block = dfs.execute (unvisited_block);
     609                 :    4020240 :       if (!unvisited_block)
     610                 :            :         break;
     611                 :            : 
     612                 :     900658 :       basic_block deadend_block = dfs_find_deadend (unvisited_block);
     613                 :     900658 :       edge e = make_edge (deadend_block, EXIT_BLOCK_PTR_FOR_FN (cfun),
     614                 :            :                           EDGE_FAKE);
     615                 :     900658 :       e->probability = profile_probability::never ();
     616                 :     900658 :       dfs.add_bb (deadend_block);
     617                 :     900658 :     }
     618                 :    3119580 : }
     619                 :            : 
     620                 :            : /* Compute reverse top sort order.  This is computing a post order
     621                 :            :    numbering of the graph.  If INCLUDE_ENTRY_EXIT is true, then
     622                 :            :    ENTRY_BLOCK and EXIT_BLOCK are included.  If DELETE_UNREACHABLE is
     623                 :            :    true, unreachable blocks are deleted.  */
     624                 :            : 
     625                 :            : int
     626                 :   25495800 : post_order_compute (int *post_order, bool include_entry_exit,
     627                 :            :                     bool delete_unreachable)
     628                 :            : {
     629                 :   25495800 :   int post_order_num = 0;
     630                 :   25495800 :   int count;
     631                 :            : 
     632                 :   25495800 :   if (include_entry_exit)
     633                 :   24209000 :     post_order[post_order_num++] = EXIT_BLOCK;
     634                 :            : 
     635                 :            :   /* Allocate stack for back-tracking up CFG.  */
     636                 :   25495800 :   auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
     637                 :            : 
     638                 :            :   /* Allocate bitmap to track nodes that have been visited.  */
     639                 :   50991600 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
     640                 :            : 
     641                 :            :   /* None of the nodes in the CFG have been visited yet.  */
     642                 :   25495800 :   bitmap_clear (visited);
     643                 :            : 
     644                 :            :   /* Push the first edge on to the stack.  */
     645                 :   25495800 :   stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs));
     646                 :            : 
     647                 :  788236000 :   while (!stack.is_empty ())
     648                 :            :     {
     649                 :  762740000 :       basic_block src;
     650                 :  762740000 :       basic_block dest;
     651                 :            : 
     652                 :            :       /* Look at the edge on the top of the stack.  */
     653                 :  762740000 :       edge_iterator ei = stack.last ();
     654                 :  762740000 :       src = ei_edge (ei)->src;
     655                 :  762740000 :       dest = ei_edge (ei)->dest;
     656                 :            : 
     657                 :            :       /* Check if the edge destination has been visited yet.  */
     658                 :  762740000 :       if (dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     659                 :  762740000 :           && ! bitmap_bit_p (visited, dest->index))
     660                 :            :         {
     661                 :            :           /* Mark that we have visited the destination.  */
     662                 :  299853000 :           bitmap_set_bit (visited, dest->index);
     663                 :            : 
     664                 :  299853000 :           if (EDGE_COUNT (dest->succs) > 0)
     665                 :            :             /* Since the DEST node has been visited for the first
     666                 :            :                time, check its successors.  */
     667                 :  284594000 :             stack.quick_push (ei_start (dest->succs));
     668                 :            :           else
     669                 :   15259500 :             post_order[post_order_num++] = dest->index;
     670                 :            :         }
     671                 :            :       else
     672                 :            :         {
     673                 :  462887000 :           if (ei_one_before_end_p (ei)
     674                 :  462887000 :               && src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
     675                 :  284594000 :             post_order[post_order_num++] = src->index;
     676                 :            : 
     677                 :  462887000 :           if (!ei_one_before_end_p (ei))
     678                 :  152797000 :             ei_next (&stack.last ());
     679                 :            :           else
     680                 :  310090000 :             stack.pop ();
     681                 :            :         }
     682                 :            :     }
     683                 :            : 
     684                 :   25495800 :   if (include_entry_exit)
     685                 :            :     {
     686                 :   24209000 :       post_order[post_order_num++] = ENTRY_BLOCK;
     687                 :   24209000 :       count = post_order_num;
     688                 :            :     }
     689                 :            :   else
     690                 :    1286810 :     count = post_order_num + 2;
     691                 :            : 
     692                 :            :   /* Delete the unreachable blocks if some were found and we are
     693                 :            :      supposed to do it.  */
     694                 :   25495800 :   if (delete_unreachable && (count != n_basic_blocks_for_fn (cfun)))
     695                 :            :     {
     696                 :       6496 :       basic_block b;
     697                 :       6496 :       basic_block next_bb;
     698                 :       6496 :       for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
     699                 :     858218 :            != EXIT_BLOCK_PTR_FOR_FN (cfun); b = next_bb)
     700                 :            :         {
     701                 :     851722 :           next_bb = b->next_bb;
     702                 :            : 
     703                 :     851722 :           if (!(bitmap_bit_p (visited, b->index)))
     704                 :      13132 :             delete_basic_block (b);
     705                 :            :         }
     706                 :            : 
     707                 :       6496 :       tidy_fallthru_edges ();
     708                 :            :     }
     709                 :            : 
     710                 :   25495800 :   return post_order_num;
     711                 :            : }
     712                 :            : 
     713                 :            : 
     714                 :            : /* Helper routine for inverted_post_order_compute
     715                 :            :    flow_dfs_compute_reverse_execute, and the reverse-CFG
     716                 :            :    deapth first search in dominance.c.
     717                 :            :    BB has to belong to a region of CFG
     718                 :            :    unreachable by inverted traversal from the exit.
     719                 :            :    i.e. there's no control flow path from ENTRY to EXIT
     720                 :            :    that contains this BB.
     721                 :            :    This can happen in two cases - if there's an infinite loop
     722                 :            :    or if there's a block that has no successor
     723                 :            :    (call to a function with no return).
     724                 :            :    Some RTL passes deal with this condition by
     725                 :            :    calling connect_infinite_loops_to_exit () and/or
     726                 :            :    add_noreturn_fake_exit_edges ().
     727                 :            :    However, those methods involve modifying the CFG itself
     728                 :            :    which may not be desirable.
     729                 :            :    Hence, we deal with the infinite loop/no return cases
     730                 :            :    by identifying a unique basic block that can reach all blocks
     731                 :            :    in such a region by inverted traversal.
     732                 :            :    This function returns a basic block that guarantees
     733                 :            :    that all blocks in the region are reachable
     734                 :            :    by starting an inverted traversal from the returned block.  */
     735                 :            : 
     736                 :            : basic_block
     737                 :    1154520 : dfs_find_deadend (basic_block bb)
     738                 :            : {
     739                 :    1154520 :   auto_bitmap visited;
     740                 :    1154520 :   basic_block next = bb;
     741                 :            : 
     742                 :    2008700 :   for (;;)
     743                 :            :     {
     744                 :    2008700 :       if (EDGE_COUNT (next->succs) == 0)
     745                 :     887371 :         return next;
     746                 :            : 
     747                 :    1121330 :       if (! bitmap_set_bit (visited, next->index))
     748                 :     267148 :         return bb;
     749                 :            : 
     750                 :     854184 :       bb = next;
     751                 :            :       /* If we are in an analyzed cycle make sure to try exiting it.
     752                 :            :          Note this is a heuristic only and expected to work when loop
     753                 :            :          fixup is needed as well.  */
     754                 :     854184 :       if (! bb->loop_father
     755                 :    1115290 :           || ! loop_outer (bb->loop_father))
     756                 :     593080 :         next = EDGE_SUCC (bb, 0)->dest;
     757                 :            :       else
     758                 :            :         {
     759                 :     261104 :           edge_iterator ei;
     760                 :     261104 :           edge e;
     761                 :     554213 :           FOR_EACH_EDGE (e, ei, bb->succs)
     762                 :     320217 :             if (loop_exit_edge_p (bb->loop_father, e))
     763                 :            :               break;
     764                 :     261104 :           next = e ? e->dest : EDGE_SUCC (bb, 0)->dest;
     765                 :            :         }
     766                 :            :     }
     767                 :            : 
     768                 :            :   gcc_unreachable ();
     769                 :            : }
     770                 :            : 
     771                 :            : 
     772                 :            : /* Compute the reverse top sort order of the inverted CFG
     773                 :            :    i.e. starting from the exit block and following the edges backward
     774                 :            :    (from successors to predecessors).
     775                 :            :    This ordering can be used for forward dataflow problems among others.
     776                 :            : 
     777                 :            :    Optionally if START_POINTS is specified, start from exit block and all
     778                 :            :    basic blocks in START_POINTS.  This is used by CD-DCE.
     779                 :            : 
     780                 :            :    This function assumes that all blocks in the CFG are reachable
     781                 :            :    from the ENTRY (but not necessarily from EXIT).
     782                 :            : 
     783                 :            :    If there's an infinite loop,
     784                 :            :    a simple inverted traversal starting from the blocks
     785                 :            :    with no successors can't visit all blocks.
     786                 :            :    To solve this problem, we first do inverted traversal
     787                 :            :    starting from the blocks with no successor.
     788                 :            :    And if there's any block left that's not visited by the regular
     789                 :            :    inverted traversal from EXIT,
     790                 :            :    those blocks are in such problematic region.
     791                 :            :    Among those, we find one block that has
     792                 :            :    any visited predecessor (which is an entry into such a region),
     793                 :            :    and start looking for a "dead end" from that block
     794                 :            :    and do another inverted traversal from that block.  */
     795                 :            : 
     796                 :            : void
     797                 :   27556700 : inverted_post_order_compute (vec<int> *post_order,
     798                 :            :                              sbitmap *start_points)
     799                 :            : {
     800                 :   27556700 :   basic_block bb;
     801                 :   27556700 :   post_order->reserve_exact (n_basic_blocks_for_fn (cfun));
     802                 :            : 
     803                 :   27556700 :   if (flag_checking)
     804                 :   27556400 :     verify_no_unreachable_blocks ();
     805                 :            : 
     806                 :            :   /* Allocate stack for back-tracking up CFG.  */
     807                 :   27556700 :   auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (cfun) + 1);
     808                 :            : 
     809                 :            :   /* Allocate bitmap to track nodes that have been visited.  */
     810                 :   55113400 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
     811                 :            : 
     812                 :            :   /* None of the nodes in the CFG have been visited yet.  */
     813                 :   27556700 :   bitmap_clear (visited);
     814                 :            : 
     815                 :   27556700 :   if (start_points)
     816                 :            :     {
     817                 :     533947 :       FOR_ALL_BB_FN (bb, cfun)
     818                 :     518550 :         if (bitmap_bit_p (*start_points, bb->index)
     819                 :     518550 :             && EDGE_COUNT (bb->preds) > 0)
     820                 :            :           {
     821                 :     343127 :             stack.quick_push (ei_start (bb->preds));
     822                 :     861677 :             bitmap_set_bit (visited, bb->index);
     823                 :            :           }
     824                 :      15397 :       if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds))
     825                 :            :         {
     826                 :      14486 :           stack.quick_push (ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds));
     827                 :      14486 :           bitmap_set_bit (visited, EXIT_BLOCK_PTR_FOR_FN (cfun)->index);
     828                 :            :         }
     829                 :            :     }
     830                 :            :   else
     831                 :            :   /* Put all blocks that have no successor into the initial work list.  */
     832                 :  420193000 :   FOR_ALL_BB_FN (bb, cfun)
     833                 :  392652000 :     if (EDGE_COUNT (bb->succs) == 0)
     834                 :            :       {
     835                 :            :         /* Push the initial edge on to the stack.  */
     836                 :   43503400 :         if (EDGE_COUNT (bb->preds) > 0)
     837                 :            :           {
     838                 :   42847900 :             stack.quick_push (ei_start (bb->preds));
     839                 :  435500000 :             bitmap_set_bit (visited, bb->index);
     840                 :            :           }
     841                 :            :       }
     842                 :            : 
     843                 :   27744400 :   do
     844                 :            :     {
     845                 :   27744400 :       bool has_unvisited_bb = false;
     846                 :            : 
     847                 :            :       /* The inverted traversal loop. */
     848                 :  897905000 :       while (!stack.is_empty ())
     849                 :            :         {
     850                 :  870160000 :           edge_iterator ei;
     851                 :  870160000 :           basic_block pred;
     852                 :            : 
     853                 :            :           /* Look at the edge on the top of the stack.  */
     854                 :  870160000 :           ei = stack.last ();
     855                 :  870160000 :           bb = ei_edge (ei)->dest;
     856                 :  870160000 :           pred = ei_edge (ei)->src;
     857                 :            : 
     858                 :            :           /* Check if the predecessor has been visited yet.  */
     859                 :  870160000 :           if (! bitmap_bit_p (visited, pred->index))
     860                 :            :             {
     861                 :            :               /* Mark that we have visited the destination.  */
     862                 :  349121000 :               bitmap_set_bit (visited, pred->index);
     863                 :            : 
     864                 :  349121000 :               if (EDGE_COUNT (pred->preds) > 0)
     865                 :            :                 /* Since the predecessor node has been visited for the first
     866                 :            :                    time, check its predecessors.  */
     867                 :  321564000 :                 stack.quick_push (ei_start (pred->preds));
     868                 :            :               else
     869                 :  897717000 :                 post_order->quick_push (pred->index);
     870                 :            :             }
     871                 :            :           else
     872                 :            :             {
     873                 :  521040000 :               if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
     874                 :  521040000 :                   && ei_one_before_end_p (ei))
     875                 :  338057000 :                 post_order->quick_push (bb->index);
     876                 :            : 
     877                 :  521040000 :               if (!ei_one_before_end_p (ei))
     878                 :  156083000 :                 ei_next (&stack.last ());
     879                 :            :               else
     880                 :  364957000 :                 stack.pop ();
     881                 :            :             }
     882                 :            :         }
     883                 :            : 
     884                 :            :       /* Detect any infinite loop and activate the kludge.
     885                 :            :          Note that this doesn't check EXIT_BLOCK itself
     886                 :            :          since EXIT_BLOCK is always added after the outer do-while loop.  */
     887                 :  394528000 :       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
     888                 :            :                       EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
     889                 :  366911000 :         if (!bitmap_bit_p (visited, bb->index))
     890                 :            :           {
     891                 :     614602 :             has_unvisited_bb = true;
     892                 :            : 
     893                 :  367338000 :             if (EDGE_COUNT (bb->preds) > 0)
     894                 :            :               {
     895                 :     554959 :                 edge_iterator ei;
     896                 :     554959 :                 edge e;
     897                 :     554959 :                 basic_block visited_pred = NULL;
     898                 :            : 
     899                 :            :                 /* Find an already visited predecessor.  */
     900                 :    1358120 :                 FOR_EACH_EDGE (e, ei, bb->preds)
     901                 :            :                   {
     902                 :     803164 :                     if (bitmap_bit_p (visited, e->src->index))
     903                 :     135790 :                       visited_pred = e->src;
     904                 :            :                   }
     905                 :            : 
     906                 :     554959 :                 if (visited_pred)
     907                 :            :                   {
     908                 :     128051 :                     basic_block be = dfs_find_deadend (bb);
     909                 :     128051 :                     gcc_assert (be != NULL);
     910                 :     128051 :                     bitmap_set_bit (visited, be->index);
     911                 :     128051 :                     stack.quick_push (ei_start (be->preds));
     912                 :     128051 :                     break;
     913                 :            :                   }
     914                 :            :               }
     915                 :            :           }
     916                 :            : 
     917                 :   27744400 :       if (has_unvisited_bb && stack.is_empty ())
     918                 :            :         {
     919                 :            :           /* No blocks are reachable from EXIT at all.
     920                 :            :              Find a dead-end from the ENTRY, and restart the iteration. */
     921                 :      59643 :           basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR_FOR_FN (cfun));
     922                 :      59643 :           gcc_assert (be != NULL);
     923                 :      59643 :           bitmap_set_bit (visited, be->index);
     924                 :      59643 :           stack.quick_push (ei_start (be->preds));
     925                 :            :         }
     926                 :            : 
     927                 :            :       /* The only case the below while fires is
     928                 :            :          when there's an infinite loop.  */
     929                 :            :     }
     930                 :   27744400 :   while (!stack.is_empty ());
     931                 :            : 
     932                 :            :   /* EXIT_BLOCK is always included.  */
     933                 :   27556700 :   post_order->quick_push (EXIT_BLOCK);
     934                 :   27556700 : }
     935                 :            : 
     936                 :            : /* Compute the depth first search order of FN and store in the array
     937                 :            :    PRE_ORDER if nonzero.  If REV_POST_ORDER is nonzero, return the
     938                 :            :    reverse completion number for each node.  Returns the number of nodes
     939                 :            :    visited.  A depth first search tries to get as far away from the starting
     940                 :            :    point as quickly as possible.
     941                 :            : 
     942                 :            :    In case the function has unreachable blocks the number of nodes
     943                 :            :    visited does not include them.
     944                 :            : 
     945                 :            :    pre_order is a really a preorder numbering of the graph.
     946                 :            :    rev_post_order is really a reverse postorder numbering of the graph.  */
     947                 :            : 
     948                 :            : int
     949                 :   67588900 : pre_and_rev_post_order_compute_fn (struct function *fn,
     950                 :            :                                    int *pre_order, int *rev_post_order,
     951                 :            :                                    bool include_entry_exit)
     952                 :            : {
     953                 :   67588900 :   int pre_order_num = 0;
     954                 :   67588900 :   int rev_post_order_num = n_basic_blocks_for_fn (fn) - 1;
     955                 :            : 
     956                 :            :   /* Allocate stack for back-tracking up CFG.  */
     957                 :   67588900 :   auto_vec<edge_iterator, 20> stack (n_basic_blocks_for_fn (fn) + 1);
     958                 :            : 
     959                 :   67588900 :   if (include_entry_exit)
     960                 :            :     {
     961                 :   27386200 :       if (pre_order)
     962                 :          0 :         pre_order[pre_order_num] = ENTRY_BLOCK;
     963                 :   27386200 :       pre_order_num++;
     964                 :   27386200 :       if (rev_post_order)
     965                 :   27386200 :         rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
     966                 :            :     }
     967                 :            :   else
     968                 :   40202700 :     rev_post_order_num -= NUM_FIXED_BLOCKS;
     969                 :            : 
     970                 :            :   /* BB flag to track nodes that have been visited.  */
     971                 :  135178000 :   auto_bb_flag visited (fn);
     972                 :            : 
     973                 :            :   /* Push the first edge on to the stack.  */
     974                 :   67588900 :   stack.quick_push (ei_start (ENTRY_BLOCK_PTR_FOR_FN (fn)->succs));
     975                 :            : 
     976                 : 1939300000 :   while (!stack.is_empty ())
     977                 :            :     {
     978                 : 1871710000 :       basic_block src;
     979                 : 1871710000 :       basic_block dest;
     980                 :            : 
     981                 :            :       /* Look at the edge on the top of the stack.  */
     982                 : 1871710000 :       edge_iterator ei = stack.last ();
     983                 : 1871710000 :       src = ei_edge (ei)->src;
     984                 : 1871710000 :       dest = ei_edge (ei)->dest;
     985                 :            : 
     986                 :            :       /* Check if the edge destination has been visited yet.  */
     987                 : 1871710000 :       if (dest != EXIT_BLOCK_PTR_FOR_FN (fn)
     988                 : 1871710000 :           && ! (dest->flags & visited))
     989                 :            :         {
     990                 :            :           /* Mark that we have visited the destination.  */
     991                 :  744321000 :           dest->flags |= visited;
     992                 :            : 
     993                 :  744321000 :           if (pre_order)
     994                 :          0 :             pre_order[pre_order_num] = dest->index;
     995                 :            : 
     996                 :  744321000 :           pre_order_num++;
     997                 :            : 
     998                 :  744321000 :           if (EDGE_COUNT (dest->succs) > 0)
     999                 :            :             /* Since the DEST node has been visited for the first
    1000                 :            :                time, check its successors.  */
    1001                 :  697926000 :             stack.quick_push (ei_start (dest->succs));
    1002                 :   46395200 :           else if (rev_post_order)
    1003                 :            :             /* There are no successors for the DEST node so assign
    1004                 :            :                its reverse completion number.  */
    1005                 :   46395200 :             rev_post_order[rev_post_order_num--] = dest->index;
    1006                 :            :         }
    1007                 :            :       else
    1008                 :            :         {
    1009                 : 1127390000 :           if (ei_one_before_end_p (ei)
    1010                 :  765515000 :               && src != ENTRY_BLOCK_PTR_FOR_FN (fn)
    1011                 : 1825310000 :               && rev_post_order)
    1012                 :            :             /* There are no more successors for the SRC node
    1013                 :            :                so assign its reverse completion number.  */
    1014                 :  697926000 :             rev_post_order[rev_post_order_num--] = src->index;
    1015                 :            : 
    1016                 : 1127390000 :           if (!ei_one_before_end_p (ei))
    1017                 :  361872000 :             ei_next (&stack.last ());
    1018                 :            :           else
    1019                 :  765515000 :             stack.pop ();
    1020                 :            :         }
    1021                 :            :     }
    1022                 :            : 
    1023                 :   67588900 :   if (include_entry_exit)
    1024                 :            :     {
    1025                 :   27386200 :       if (pre_order)
    1026                 :          0 :         pre_order[pre_order_num] = EXIT_BLOCK;
    1027                 :   27386200 :       pre_order_num++;
    1028                 :   27386200 :       if (rev_post_order)
    1029                 :   27386200 :         rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
    1030                 :            :     }
    1031                 :            : 
    1032                 :            :   /* Clear the temporarily allocated flag.  */
    1033                 :   67588900 :   if (!rev_post_order)
    1034                 :          0 :     rev_post_order = pre_order;
    1035                 :  866683000 :   for (int i = 0; i < pre_order_num; ++i)
    1036                 :  799094000 :     BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags &= ~visited;
    1037                 :            : 
    1038                 :   67588900 :   return pre_order_num;
    1039                 :            : }
    1040                 :            : 
    1041                 :            : /* Like pre_and_rev_post_order_compute_fn but operating on the
    1042                 :            :    current function and asserting that all nodes were visited.  */
    1043                 :            : 
    1044                 :            : int
    1045                 :   56815600 : pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
    1046                 :            :                                 bool include_entry_exit)
    1047                 :            : {
    1048                 :   56815600 :   int pre_order_num
    1049                 :   56815600 :     = pre_and_rev_post_order_compute_fn (cfun, pre_order, rev_post_order,
    1050                 :            :                                          include_entry_exit);
    1051                 :   56815600 :   if (include_entry_exit)
    1052                 :            :     /* The number of nodes visited should be the number of blocks.  */
    1053                 :   27247100 :     gcc_assert (pre_order_num == n_basic_blocks_for_fn (cfun));
    1054                 :            :   else
    1055                 :            :     /* The number of nodes visited should be the number of blocks minus
    1056                 :            :        the entry and exit blocks which are not visited here.  */
    1057                 :   29568500 :     gcc_assert (pre_order_num
    1058                 :            :                 == (n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS));
    1059                 :            : 
    1060                 :   56815600 :   return pre_order_num;
    1061                 :            : }
    1062                 :            : 
    1063                 :            : /* Unlike pre_and_rev_post_order_compute we fill rev_post_order backwards
    1064                 :            :    so iterating in RPO order needs to start with rev_post_order[n - 1]
    1065                 :            :    going to rev_post_order[0].  If FOR_ITERATION is true then try to
    1066                 :            :    make CFG cycles fit into small contiguous regions of the RPO order.
    1067                 :            :    When FOR_ITERATION is true this requires up-to-date loop structures.  */
    1068                 :            : 
    1069                 :            : int
    1070                 :    3756850 : rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry,
    1071                 :            :                                        bitmap exit_bbs, bool for_iteration,
    1072                 :            :                                        int *rev_post_order)
    1073                 :            : {
    1074                 :    3756850 :   int pre_order_num = 0;
    1075                 :    3756850 :   int rev_post_order_num = 0;
    1076                 :            : 
    1077                 :            :   /* Allocate stack for back-tracking up CFG.  Worst case we need
    1078                 :            :      O(n^2) edges but the following should suffice in practice without
    1079                 :            :      a need to re-allocate.  */
    1080                 :    3756850 :   auto_vec<edge, 20> stack (2 * n_basic_blocks_for_fn (fn));
    1081                 :            : 
    1082                 :    3756850 :   int *pre = XNEWVEC (int, 2 * last_basic_block_for_fn (fn));
    1083                 :    3756850 :   int *post = pre + last_basic_block_for_fn (fn);
    1084                 :            : 
    1085                 :            :   /* BB flag to track nodes that have been visited.  */
    1086                 :    7513700 :   auto_bb_flag visited (fn);
    1087                 :            :   /* BB flag to track which nodes have post[] assigned to avoid
    1088                 :            :      zeroing post.  */
    1089                 :    7513700 :   auto_bb_flag post_assigned (fn);
    1090                 :            : 
    1091                 :            :   /* Push the first edge on to the stack.  */
    1092                 :    3756850 :   stack.quick_push (entry);
    1093                 :            : 
    1094                 :   81715100 :   while (!stack.is_empty ())
    1095                 :            :     {
    1096                 :   77958300 :       basic_block src;
    1097                 :   77958300 :       basic_block dest;
    1098                 :            : 
    1099                 :            :       /* Look at the edge on the top of the stack.  */
    1100                 :   77958300 :       int idx = stack.length () - 1;
    1101                 :   77958300 :       edge e = stack[idx];
    1102                 :   77958300 :       src = e->src;
    1103                 :   77958300 :       dest = e->dest;
    1104                 :   77958300 :       e->flags &= ~EDGE_DFS_BACK;
    1105                 :            : 
    1106                 :            :       /* Check if the edge destination has been visited yet.  */
    1107                 :   77958300 :       if (! bitmap_bit_p (exit_bbs, dest->index)
    1108                 :   77958300 :           && ! (dest->flags & visited))
    1109                 :            :         {
    1110                 :            :           /* Mark that we have visited the destination.  */
    1111                 :   31194600 :           dest->flags |= visited;
    1112                 :            : 
    1113                 :   31194600 :           pre[dest->index] = pre_order_num++;
    1114                 :            : 
    1115                 :   31194600 :           if (EDGE_COUNT (dest->succs) > 0)
    1116                 :            :             {
    1117                 :            :               /* Since the DEST node has been visited for the first
    1118                 :            :                  time, check its successors.  */
    1119                 :            :               /* Push the edge vector in reverse to match previous behavior.  */
    1120                 :   29118900 :               stack.reserve (EDGE_COUNT (dest->succs));
    1121                 :  101245000 :               for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i)
    1122                 :   43006800 :                 stack.quick_push (EDGE_SUCC (dest, i));
    1123                 :            :               /* Generalize to handle more successors?  */
    1124                 :   29118900 :               if (for_iteration
    1125                 :   29118900 :                   && EDGE_COUNT (dest->succs) == 2)
    1126                 :            :                 {
    1127                 :   27324700 :                   edge &e1 = stack[stack.length () - 2];
    1128                 :   13662400 :                   if (loop_exit_edge_p (e1->src->loop_father, e1))
    1129                 :   82915600 :                     std::swap (e1, stack.last ());
    1130                 :            :                 }
    1131                 :            :             }
    1132                 :            :           else
    1133                 :            :             {
    1134                 :            :               /* There are no successors for the DEST node so assign
    1135                 :            :                  its reverse completion number.  */
    1136                 :    2075650 :               post[dest->index] = rev_post_order_num;
    1137                 :    2075650 :               dest->flags |= post_assigned;
    1138                 :    2075650 :               rev_post_order[rev_post_order_num] = dest->index;
    1139                 :    2075650 :               rev_post_order_num++;
    1140                 :            :             }
    1141                 :            :         }
    1142                 :            :       else
    1143                 :            :         {
    1144                 :   46763700 :           if (dest->flags & visited
    1145                 :   42835500 :               && src != entry->src
    1146                 :   39078600 :               && pre[src->index] >= pre[dest->index]
    1147                 :   56406300 :               && !(dest->flags & post_assigned))
    1148                 :    1516820 :             e->flags |= EDGE_DFS_BACK;
    1149                 :            : 
    1150                 :   46763700 :           if (idx != 0 && stack[idx - 1]->src != src)
    1151                 :            :             {
    1152                 :            :               /* There are no more successors for the SRC node
    1153                 :            :                  so assign its reverse completion number.  */
    1154                 :   29118900 :               post[src->index] = rev_post_order_num;
    1155                 :   29118900 :               src->flags |= post_assigned;
    1156                 :   29118900 :               rev_post_order[rev_post_order_num] = src->index;
    1157                 :   29118900 :               rev_post_order_num++;
    1158                 :            :             }
    1159                 :            : 
    1160                 :   46763700 :           stack.pop ();
    1161                 :            :         }
    1162                 :            :     }
    1163                 :            : 
    1164                 :    3756850 :   XDELETEVEC (pre);
    1165                 :            : 
    1166                 :            :   /* Clear the temporarily allocated flags.  */
    1167                 :   34951400 :   for (int i = 0; i < rev_post_order_num; ++i)
    1168                 :   62389200 :     BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags
    1169                 :   31194600 :       &= ~(post_assigned|visited);
    1170                 :            : 
    1171                 :    3756850 :   return rev_post_order_num;
    1172                 :            : }
    1173                 :            : 
    1174                 :            : 
    1175                 :            : 
    1176                 :            : /* Compute the depth first search order on the _reverse_ graph and
    1177                 :            :    store it in the array DFS_ORDER, marking the nodes visited in VISITED.
    1178                 :            :    Returns the number of nodes visited.
    1179                 :            : 
    1180                 :            :    The computation is split into three pieces:
    1181                 :            : 
    1182                 :            :    flow_dfs_compute_reverse_init () creates the necessary data
    1183                 :            :    structures.
    1184                 :            : 
    1185                 :            :    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
    1186                 :            :    structures.  The block will start the search.
    1187                 :            : 
    1188                 :            :    flow_dfs_compute_reverse_execute () continues (or starts) the
    1189                 :            :    search using the block on the top of the stack, stopping when the
    1190                 :            :    stack is empty.
    1191                 :            : 
    1192                 :            :    flow_dfs_compute_reverse_finish () destroys the necessary data
    1193                 :            :    structures.
    1194                 :            : 
    1195                 :            :    Thus, the user will probably call ..._init(), call ..._add_bb() to
    1196                 :            :    add a beginning basic block to the stack, call ..._execute(),
    1197                 :            :    possibly add another bb to the stack and again call ..._execute(),
    1198                 :            :    ..., and finally call _finish().  */
    1199                 :            : 
    1200                 :            : /* Initialize the data structures used for depth-first search on the
    1201                 :            :    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
    1202                 :            :    added to the basic block stack.  DATA is the current depth-first
    1203                 :            :    search context.  If INITIALIZE_STACK is nonzero, there is an
    1204                 :            :    element on the stack.  */
    1205                 :            : 
    1206                 :    3119580 : depth_first_search::depth_first_search () :
    1207                 :    3119580 :   m_stack (n_basic_blocks_for_fn (cfun)),
    1208                 :    3119580 :   m_visited_blocks (last_basic_block_for_fn (cfun))
    1209                 :            : {
    1210                 :    3119580 :   bitmap_clear (m_visited_blocks);
    1211                 :    3119580 : }
    1212                 :            : 
    1213                 :            : /* Add the specified basic block to the top of the dfs data
    1214                 :            :    structures.  When the search continues, it will start at the
    1215                 :            :    block.  */
    1216                 :            : 
    1217                 :            : void
    1218                 :   34642000 : depth_first_search::add_bb (basic_block bb)
    1219                 :            : {
    1220                 :   34642000 :   m_stack.quick_push (bb);
    1221                 :   34642000 :   bitmap_set_bit (m_visited_blocks, bb->index);
    1222                 :   34642000 : }
    1223                 :            : 
    1224                 :            : /* Continue the depth-first search through the reverse graph starting with the
    1225                 :            :    block at the stack's top and ending when the stack is empty.  Visited nodes
    1226                 :            :    are marked.  Returns an unvisited basic block, or NULL if there is none
    1227                 :            :    available.  */
    1228                 :            : 
    1229                 :            : basic_block
    1230                 :    4020240 : depth_first_search::execute (basic_block last_unvisited)
    1231                 :            : {
    1232                 :   38662200 :   basic_block bb;
    1233                 :   38662200 :   edge e;
    1234                 :   38662200 :   edge_iterator ei;
    1235                 :            : 
    1236                 :   38662200 :   while (!m_stack.is_empty ())
    1237                 :            :     {
    1238                 :   34642000 :       bb = m_stack.pop ();
    1239                 :            : 
    1240                 :            :       /* Perform depth-first search on adjacent vertices.  */
    1241                 :   76293300 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1242                 :   41651300 :         if (!bitmap_bit_p (m_visited_blocks, e->src->index))
    1243                 :   30621700 :           add_bb (e->src);
    1244                 :            :     }
    1245                 :            : 
    1246                 :            :   /* Determine if there are unvisited basic blocks.  */
    1247                 :   38662200 :   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
    1248                 :   35542600 :     if (!bitmap_bit_p (m_visited_blocks, bb->index))
    1249                 :     900658 :       return bb;
    1250                 :            : 
    1251                 :            :   return NULL;
    1252                 :            : }
    1253                 :            : 
    1254                 :            : /* Performs dfs search from BB over vertices satisfying PREDICATE;
    1255                 :            :    if REVERSE, go against direction of edges.  Returns number of blocks
    1256                 :            :    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
    1257                 :            : int
    1258                 :  110377000 : dfs_enumerate_from (basic_block bb, int reverse,
    1259                 :            :                     bool (*predicate) (const_basic_block, const void *),
    1260                 :            :                     basic_block *rslt, int rslt_max, const void *data)
    1261                 :            : {
    1262                 :  110377000 :   basic_block *st, lbb;
    1263                 :  110377000 :   int sp = 0, tv = 0;
    1264                 :            : 
    1265                 :  110377000 :   auto_bb_flag visited (cfun);
    1266                 :            : 
    1267                 :            : #define MARK_VISITED(BB) ((BB)->flags |= visited)
    1268                 :            : #define UNMARK_VISITED(BB) ((BB)->flags &= ~visited)
    1269                 :            : #define VISITED_P(BB) (((BB)->flags & visited) != 0)
    1270                 :            : 
    1271                 :  110377000 :   st = XNEWVEC (basic_block, rslt_max);
    1272                 :  110377000 :   rslt[tv++] = st[sp++] = bb;
    1273                 :  110377000 :   MARK_VISITED (bb);
    1274                 :  787181000 :   while (sp)
    1275                 :            :     {
    1276                 :  676804000 :       edge e;
    1277                 :  676804000 :       edge_iterator ei;
    1278                 :  676804000 :       lbb = st[--sp];
    1279                 :  676804000 :       if (reverse)
    1280                 :            :         {
    1281                 : 1650730000 :           FOR_EACH_EDGE (e, ei, lbb->preds)
    1282                 :  974276000 :             if (!VISITED_P (e->src) && predicate (e->src, data))
    1283                 :            :               {
    1284                 :  566366000 :                 gcc_assert (tv != rslt_max);
    1285                 :  566366000 :                 rslt[tv++] = st[sp++] = e->src;
    1286                 :  566366000 :                 MARK_VISITED (e->src);
    1287                 :            :               }
    1288                 :            :         }
    1289                 :            :       else
    1290                 :            :         {
    1291                 :     764478 :           FOR_EACH_EDGE (e, ei, lbb->succs)
    1292                 :     410553 :             if (!VISITED_P (e->dest) && predicate (e->dest, data))
    1293                 :            :               {
    1294                 :      60580 :                 gcc_assert (tv != rslt_max);
    1295                 :      60580 :                 rslt[tv++] = st[sp++] = e->dest;
    1296                 :      60580 :                 MARK_VISITED (e->dest);
    1297                 :            :               }
    1298                 :            :         }
    1299                 :            :     }
    1300                 :  110377000 :   free (st);
    1301                 :  787181000 :   for (sp = 0; sp < tv; sp++)
    1302                 :  676804000 :     UNMARK_VISITED (rslt[sp]);
    1303                 :  110377000 :   return tv;
    1304                 :            : #undef MARK_VISITED
    1305                 :            : #undef UNMARK_VISITED
    1306                 :            : #undef VISITED_P
    1307                 :            : }
    1308                 :            : 
    1309                 :            : 
    1310                 :            : /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
    1311                 :            : 
    1312                 :            :    This algorithm can be found in Timothy Harvey's PhD thesis, at
    1313                 :            :    http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
    1314                 :            :    dominance algorithms.
    1315                 :            : 
    1316                 :            :    First, we identify each join point, j (any node with more than one
    1317                 :            :    incoming edge is a join point).
    1318                 :            : 
    1319                 :            :    We then examine each predecessor, p, of j and walk up the dominator tree
    1320                 :            :    starting at p.
    1321                 :            : 
    1322                 :            :    We stop the walk when we reach j's immediate dominator - j is in the
    1323                 :            :    dominance frontier of each of  the nodes in the walk, except for j's
    1324                 :            :    immediate dominator. Intuitively, all of the rest of j's dominators are
    1325                 :            :    shared by j's predecessors as well.
    1326                 :            :    Since they dominate j, they will not have j in their dominance frontiers.
    1327                 :            : 
    1328                 :            :    The number of nodes touched by this algorithm is equal to the size
    1329                 :            :    of the dominance frontiers, no more, no less.
    1330                 :            : */
    1331                 :            : 
    1332                 :            : void
    1333                 :    5333720 : compute_dominance_frontiers (bitmap_head *frontiers)
    1334                 :            : {
    1335                 :    5333720 :   timevar_push (TV_DOM_FRONTIERS);
    1336                 :            : 
    1337                 :    5333720 :   edge p;
    1338                 :    5333720 :   edge_iterator ei;
    1339                 :    5333720 :   basic_block b;
    1340                 :   88382100 :   FOR_EACH_BB_FN (b, cfun)
    1341                 :            :     {
    1342                 :  102408000 :       if (EDGE_COUNT (b->preds) >= 2)
    1343                 :            :         {
    1344                 :   19359800 :           basic_block domsb = get_immediate_dominator (CDI_DOMINATORS, b);
    1345                 :   72071300 :           FOR_EACH_EDGE (p, ei, b->preds)
    1346                 :            :             {
    1347                 :   52711500 :               basic_block runner = p->src;
    1348                 :   52711500 :               if (runner == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1349                 :      16398 :                 continue;
    1350                 :            : 
    1351                 :  140445000 :               while (runner != domsb)
    1352                 :            :                 {
    1353                 :  101110000 :                   if (!bitmap_set_bit (&frontiers[runner->index], b->index))
    1354                 :            :                     break;
    1355                 :   87749700 :                   runner = get_immediate_dominator (CDI_DOMINATORS, runner);
    1356                 :            :                 }
    1357                 :            :             }
    1358                 :            :         }
    1359                 :            :     }
    1360                 :            : 
    1361                 :    5333720 :   timevar_pop (TV_DOM_FRONTIERS);
    1362                 :    5333720 : }
    1363                 :            : 
    1364                 :            : /* Given a set of blocks with variable definitions (DEF_BLOCKS),
    1365                 :            :    return a bitmap with all the blocks in the iterated dominance
    1366                 :            :    frontier of the blocks in DEF_BLOCKS.  DFS contains dominance
    1367                 :            :    frontier information as returned by compute_dominance_frontiers.
    1368                 :            : 
    1369                 :            :    The resulting set of blocks are the potential sites where PHI nodes
    1370                 :            :    are needed.  The caller is responsible for freeing the memory
    1371                 :            :    allocated for the return value.  */
    1372                 :            : 
    1373                 :            : bitmap
    1374                 :   15277200 : compute_idf (bitmap def_blocks, bitmap_head *dfs)
    1375                 :            : {
    1376                 :   15277200 :   bitmap_iterator bi;
    1377                 :   15277200 :   unsigned bb_index, i;
    1378                 :   15277200 :   bitmap phi_insertion_points;
    1379                 :            : 
    1380                 :   15277200 :   phi_insertion_points = BITMAP_ALLOC (NULL);
    1381                 :            : 
    1382                 :            :   /* Seed the work set with all the blocks in DEF_BLOCKS.  */
    1383                 :   15277200 :   auto_bitmap work_set;
    1384                 :   15277200 :   bitmap_copy (work_set, def_blocks);
    1385                 :   15277200 :   bitmap_tree_view (work_set);
    1386                 :            : 
    1387                 :            :   /* Pop a block off the workset, add every block that appears in
    1388                 :            :      the original block's DF that we have not already processed to
    1389                 :            :      the workset.  Iterate until the workset is empty.   Blocks
    1390                 :            :      which are added to the workset are potential sites for
    1391                 :            :      PHI nodes.  */
    1392                 :   80378700 :   while (!bitmap_empty_p (work_set))
    1393                 :            :     {
    1394                 :            :       /* The dominance frontier of a block is blocks after it so iterating
    1395                 :            :          on earlier blocks first is better.
    1396                 :            :          ???  Basic blocks are by no means guaranteed to be ordered in
    1397                 :            :          optimal order for this iteration.  */
    1398                 :   65101500 :       bb_index = bitmap_first_set_bit (work_set);
    1399                 :   65101500 :       bitmap_clear_bit (work_set, bb_index);
    1400                 :            : 
    1401                 :            :       /* Since the registration of NEW -> OLD name mappings is done
    1402                 :            :          separately from the call to update_ssa, when updating the SSA
    1403                 :            :          form, the basic blocks where new and/or old names are defined
    1404                 :            :          may have disappeared by CFG cleanup calls.  In this case,
    1405                 :            :          we may pull a non-existing block from the work stack.  */
    1406                 :   65101500 :       gcc_checking_assert (bb_index
    1407                 :            :                            < (unsigned) last_basic_block_for_fn (cfun));
    1408                 :            : 
    1409                 :   94398100 :       EXECUTE_IF_AND_COMPL_IN_BITMAP (&dfs[bb_index], phi_insertion_points,
    1410                 :            :                                       0, i, bi)
    1411                 :            :         {
    1412                 :   29296500 :           bitmap_set_bit (work_set, i);
    1413                 :   29296500 :           bitmap_set_bit (phi_insertion_points, i);
    1414                 :            :         }
    1415                 :            :     }
    1416                 :            : 
    1417                 :   15277200 :   return phi_insertion_points;
    1418                 :            : }
    1419                 :            : 
    1420                 :            : /* Intersection and union of preds/succs for sbitmap based data flow
    1421                 :            :    solvers.  All four functions defined below take the same arguments:
    1422                 :            :    B is the basic block to perform the operation for.  DST is the
    1423                 :            :    target sbitmap, i.e. the result.  SRC is an sbitmap vector of size
    1424                 :            :    last_basic_block so that it can be indexed with basic block indices.
    1425                 :            :    DST may be (but does not have to be) SRC[B->index].  */
    1426                 :            : 
    1427                 :            : /* Set the bitmap DST to the intersection of SRC of successors of
    1428                 :            :    basic block B.  */
    1429                 :            : 
    1430                 :            : void
    1431                 :    6784170 : bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b)
    1432                 :            : {
    1433                 :    6784170 :   unsigned int set_size = dst->size;
    1434                 :    6784170 :   edge e;
    1435                 :    6784170 :   unsigned ix;
    1436                 :            : 
    1437                 :   13569300 :   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
    1438                 :            :     {
    1439                 :    6732630 :       e = EDGE_SUCC (b, ix);
    1440                 :    6732630 :       if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1441                 :       1118 :         continue;
    1442                 :            : 
    1443                 :    6731520 :       bitmap_copy (dst, src[e->dest->index]);
    1444                 :    6731520 :       break;
    1445                 :            :     }
    1446                 :            : 
    1447                 :    6784170 :   if (e == 0)
    1448                 :      51540 :     bitmap_ones (dst);
    1449                 :            :   else
    1450                 :   21569800 :     for (++ix; ix < EDGE_COUNT (b->succs); ix++)
    1451                 :            :       {
    1452                 :    4052270 :         unsigned int i;
    1453                 :    4052270 :         SBITMAP_ELT_TYPE *p, *r;
    1454                 :            : 
    1455                 :    4052270 :         e = EDGE_SUCC (b, ix);
    1456                 :    4052270 :         if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1457                 :          0 :           continue;
    1458                 :            : 
    1459                 :    4052270 :         p = src[e->dest->index]->elms;
    1460                 :    4052270 :         r = dst->elms;
    1461                 :   14893400 :         for (i = 0; i < set_size; i++)
    1462                 :   10841100 :           *r++ &= *p++;
    1463                 :            :       }
    1464                 :    6784170 : }
    1465                 :            : 
    1466                 :            : /* Set the bitmap DST to the intersection of SRC of predecessors of
    1467                 :            :    basic block B.  */
    1468                 :            : 
    1469                 :            : void
    1470                 :   34065800 : bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b)
    1471                 :            : {
    1472                 :   34065800 :   unsigned int set_size = dst->size;
    1473                 :   34065800 :   edge e;
    1474                 :   34065800 :   unsigned ix;
    1475                 :            : 
    1476                 :   68131600 :   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
    1477                 :            :     {
    1478                 :   34065800 :       e = EDGE_PRED (b, ix);
    1479                 :   34065800 :       if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1480                 :          0 :         continue;
    1481                 :            : 
    1482                 :   34065800 :       bitmap_copy (dst, src[e->src->index]);
    1483                 :   34065800 :       break;
    1484                 :            :     }
    1485                 :            : 
    1486                 :   34065800 :   if (e == 0)
    1487                 :          0 :     bitmap_ones (dst);
    1488                 :            :   else
    1489                 :  166760000 :     for (++ix; ix < EDGE_COUNT (b->preds); ix++)
    1490                 :            :       {
    1491                 :   49314400 :         unsigned int i;
    1492                 :   49314400 :         SBITMAP_ELT_TYPE *p, *r;
    1493                 :            : 
    1494                 :   49314400 :         e = EDGE_PRED (b, ix);
    1495                 :   49314400 :         if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1496                 :          0 :           continue;
    1497                 :            : 
    1498                 :   49314400 :         p = src[e->src->index]->elms;
    1499                 :   49314400 :         r = dst->elms;
    1500                 :  496402000 :         for (i = 0; i < set_size; i++)
    1501                 :  447088000 :           *r++ &= *p++;
    1502                 :            :       }
    1503                 :   34065800 : }
    1504                 :            : 
    1505                 :            : /* Set the bitmap DST to the union of SRC of successors of
    1506                 :            :    basic block B.  */
    1507                 :            : 
    1508                 :            : void
    1509                 :          0 : bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b)
    1510                 :            : {
    1511                 :          0 :   unsigned int set_size = dst->size;
    1512                 :          0 :   edge e;
    1513                 :          0 :   unsigned ix;
    1514                 :            : 
    1515                 :          0 :   for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
    1516                 :            :     {
    1517                 :          0 :       e = EDGE_SUCC (b, ix);
    1518                 :          0 :       if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1519                 :          0 :         continue;
    1520                 :            : 
    1521                 :          0 :       bitmap_copy (dst, src[e->dest->index]);
    1522                 :          0 :       break;
    1523                 :            :     }
    1524                 :            : 
    1525                 :          0 :   if (ix == EDGE_COUNT (b->succs))
    1526                 :          0 :     bitmap_clear (dst);
    1527                 :            :   else
    1528                 :          0 :     for (ix++; ix < EDGE_COUNT (b->succs); ix++)
    1529                 :            :       {
    1530                 :          0 :         unsigned int i;
    1531                 :          0 :         SBITMAP_ELT_TYPE *p, *r;
    1532                 :            : 
    1533                 :          0 :         e = EDGE_SUCC (b, ix);
    1534                 :          0 :         if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1535                 :          0 :           continue;
    1536                 :            : 
    1537                 :          0 :         p = src[e->dest->index]->elms;
    1538                 :          0 :         r = dst->elms;
    1539                 :          0 :         for (i = 0; i < set_size; i++)
    1540                 :          0 :           *r++ |= *p++;
    1541                 :            :       }
    1542                 :          0 : }
    1543                 :            : 
    1544                 :            : /* Set the bitmap DST to the union of SRC of predecessors of
    1545                 :            :    basic block B.  */
    1546                 :            : 
    1547                 :            : void
    1548                 :          0 : bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b)
    1549                 :            : {
    1550                 :          0 :   unsigned int set_size = dst->size;
    1551                 :          0 :   edge e;
    1552                 :          0 :   unsigned ix;
    1553                 :            : 
    1554                 :          0 :   for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
    1555                 :            :     {
    1556                 :          0 :       e = EDGE_PRED (b, ix);
    1557                 :          0 :       if (e->src== ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1558                 :          0 :         continue;
    1559                 :            : 
    1560                 :          0 :       bitmap_copy (dst, src[e->src->index]);
    1561                 :          0 :       break;
    1562                 :            :     }
    1563                 :            : 
    1564                 :          0 :   if (ix == EDGE_COUNT (b->preds))
    1565                 :          0 :     bitmap_clear (dst);
    1566                 :            :   else
    1567                 :          0 :     for (ix++; ix < EDGE_COUNT (b->preds); ix++)
    1568                 :            :       {
    1569                 :          0 :         unsigned int i;
    1570                 :          0 :         SBITMAP_ELT_TYPE *p, *r;
    1571                 :            : 
    1572                 :          0 :         e = EDGE_PRED (b, ix);
    1573                 :          0 :         if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1574                 :          0 :           continue;
    1575                 :            : 
    1576                 :          0 :         p = src[e->src->index]->elms;
    1577                 :          0 :         r = dst->elms;
    1578                 :          0 :         for (i = 0; i < set_size; i++)
    1579                 :          0 :           *r++ |= *p++;
    1580                 :            :       }
    1581                 :          0 : }
    1582                 :            : 
    1583                 :            : /* Returns the list of basic blocks in the function in an order that guarantees
    1584                 :            :    that if a block X has just a single predecessor Y, then Y is after X in the
    1585                 :            :    ordering.  */
    1586                 :            : 
    1587                 :            : basic_block *
    1588                 :    5010000 : single_pred_before_succ_order (void)
    1589                 :            : {
    1590                 :    5010000 :   basic_block x, y;
    1591                 :    5010000 :   basic_block *order = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
    1592                 :    5010000 :   unsigned n = n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS;
    1593                 :    5010000 :   unsigned np, i;
    1594                 :    5010000 :   auto_sbitmap visited (last_basic_block_for_fn (cfun));
    1595                 :            : 
    1596                 :            : #define MARK_VISITED(BB) (bitmap_set_bit (visited, (BB)->index))
    1597                 :            : #define VISITED_P(BB) (bitmap_bit_p (visited, (BB)->index))
    1598                 :            : 
    1599                 :    5010000 :   bitmap_clear (visited);
    1600                 :            : 
    1601                 :    5010000 :   MARK_VISITED (ENTRY_BLOCK_PTR_FOR_FN (cfun));
    1602                 :   45036800 :   FOR_EACH_BB_FN (x, cfun)
    1603                 :            :     {
    1604                 :   40026800 :       if (VISITED_P (x))
    1605                 :     780771 :         continue;
    1606                 :            : 
    1607                 :            :       /* Walk the predecessors of x as long as they have precisely one
    1608                 :            :          predecessor and add them to the list, so that they get stored
    1609                 :            :          after x.  */
    1610                 :     780771 :       for (y = x, np = 1;
    1611                 :   70096300 :            single_pred_p (y) && !VISITED_P (single_pred (y));
    1612                 :     780771 :            y = single_pred (y))
    1613                 :     780771 :         np++;
    1614                 :   39246100 :       for (y = x, i = n - np;
    1615                 :   70096300 :            single_pred_p (y) && !VISITED_P (single_pred (y));
    1616                 :     780771 :            y = single_pred (y), i++)
    1617                 :            :         {
    1618                 :     780771 :           order[i] = y;
    1619                 :     780771 :           MARK_VISITED (y);
    1620                 :            :         }
    1621                 :   39246100 :       order[i] = y;
    1622                 :   39246100 :       MARK_VISITED (y);
    1623                 :            : 
    1624                 :   39246100 :       gcc_assert (i == n - 1);
    1625                 :            :       n -= np;
    1626                 :            :     }
    1627                 :            : 
    1628                 :    5010000 :   gcc_assert (n == 0);
    1629                 :    5010000 :   return order;
    1630                 :            : 
    1631                 :            : #undef MARK_VISITED
    1632                 :            : #undef VISITED_P
    1633                 :            : }
    1634                 :            : 
    1635                 :            : /* Ignoring loop backedges, if BB has precisely one incoming edge then
    1636                 :            :    return that edge.  Otherwise return NULL.
    1637                 :            : 
    1638                 :            :    When IGNORE_NOT_EXECUTABLE is true, also ignore edges that are not marked
    1639                 :            :    as executable.  */
    1640                 :            : 
    1641                 :            : edge
    1642                 :   56048600 : single_pred_edge_ignoring_loop_edges (basic_block bb,
    1643                 :            :                                       bool ignore_not_executable)
    1644                 :            : {
    1645                 :   56048600 :   edge retval = NULL;
    1646                 :   56048600 :   edge e;
    1647                 :   56048600 :   edge_iterator ei;
    1648                 :            : 
    1649                 :  109696000 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1650                 :            :     {
    1651                 :            :       /* A loop back edge can be identified by the destination of
    1652                 :            :          the edge dominating the source of the edge.  */
    1653                 :   63136900 :       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
    1654                 :    2526700 :         continue;
    1655                 :            : 
    1656                 :            :       /* We can safely ignore edges that are not executable.  */
    1657                 :   60610200 :       if (ignore_not_executable
    1658                 :   16216900 :           && (e->flags & EDGE_EXECUTABLE) == 0)
    1659                 :      29042 :         continue;
    1660                 :            : 
    1661                 :            :       /* If we have already seen a non-loop edge, then we must have
    1662                 :            :          multiple incoming non-loop edges and thus we return NULL.  */
    1663                 :   60581200 :       if (retval)
    1664                 :            :         return NULL;
    1665                 :            : 
    1666                 :            :       /* This is the first non-loop incoming edge we have found.  Record
    1667                 :            :          it.  */
    1668                 :   51091500 :       retval = e;
    1669                 :            :     }
    1670                 :            : 
    1671                 :            :   return retval;
    1672                 :            : }

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.