LCOV - code coverage report
Current view: top level - gcc - dominance.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 639 687 93.0 %
Date: 2020-04-04 11:58:09 Functions: 47 50 94.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Calculate (post)dominators in slightly super-linear time.
       2                 :            :    Copyright (C) 2000-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Michael Matz (matz@ifh.de).
       4                 :            : 
       5                 :            :    This file is part of GCC.
       6                 :            : 
       7                 :            :    GCC is free software; you can redistribute it and/or modify it
       8                 :            :    under the terms of the GNU General Public License as published by
       9                 :            :    the Free Software Foundation; either version 3, or (at your option)
      10                 :            :    any later version.
      11                 :            : 
      12                 :            :    GCC is distributed in the hope that it will be useful, but WITHOUT
      13                 :            :    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
      14                 :            :    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
      15                 :            :    License for more details.
      16                 :            : 
      17                 :            :    You should have received a copy of the GNU General Public License
      18                 :            :    along with GCC; see the file COPYING3.  If not see
      19                 :            :    <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : /* This file implements the well known algorithm from Lengauer and Tarjan
      22                 :            :    to compute the dominators in a control flow graph.  A basic block D is said
      23                 :            :    to dominate another block X, when all paths from the entry node of the CFG
      24                 :            :    to X go also over D.  The dominance relation is a transitive reflexive
      25                 :            :    relation and its minimal transitive reduction is a tree, called the
      26                 :            :    dominator tree.  So for each block X besides the entry block exists a
      27                 :            :    block I(X), called the immediate dominator of X, which is the parent of X
      28                 :            :    in the dominator tree.
      29                 :            : 
      30                 :            :    The algorithm computes this dominator tree implicitly by computing for
      31                 :            :    each block its immediate dominator.  We use tree balancing and path
      32                 :            :    compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
      33                 :            :    slowly growing functional inverse of the Ackerman function.  */
      34                 :            : 
      35                 :            : #include "config.h"
      36                 :            : #include "system.h"
      37                 :            : #include "coretypes.h"
      38                 :            : #include "backend.h"
      39                 :            : #include "timevar.h"
      40                 :            : #include "diagnostic-core.h"
      41                 :            : #include "cfganal.h"
      42                 :            : #include "et-forest.h"
      43                 :            : #include "graphds.h"
      44                 :            : 
      45                 :            : /* We name our nodes with integers, beginning with 1.  Zero is reserved for
      46                 :            :    'undefined' or 'end of list'.  The name of each node is given by the dfs
      47                 :            :    number of the corresponding basic block.  Please note, that we include the
      48                 :            :    artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
      49                 :            :    support multiple entry points.  Its dfs number is of course 1.  */
      50                 :            : 
      51                 :            : /* Type of Basic Block aka. TBB */
      52                 :            : typedef unsigned int TBB;
      53                 :            : 
      54                 :            : namespace {
      55                 :            : 
      56                 :            : /* This class holds various arrays reflecting the (sub)structure of the
      57                 :            :    flowgraph.  Most of them are of type TBB and are also indexed by TBB.  */
      58                 :            : 
      59                 :            : class dom_info
      60                 :            : {
      61                 :            : public:
      62                 :            :   dom_info (function *, cdi_direction);
      63                 :            :   dom_info (vec <basic_block>, cdi_direction);
      64                 :            :   ~dom_info ();
      65                 :            :   void calc_dfs_tree ();
      66                 :            :   void calc_idoms ();
      67                 :            : 
      68                 :            :   inline basic_block get_idom (basic_block);
      69                 :            : private:
      70                 :            :   void calc_dfs_tree_nonrec (basic_block);
      71                 :            :   void compress (TBB);
      72                 :            :   void dom_init (void);
      73                 :            :   TBB eval (TBB);
      74                 :            :   void link_roots (TBB, TBB);
      75                 :            : 
      76                 :            :   /* The parent of a node in the DFS tree.  */
      77                 :            :   TBB *m_dfs_parent;
      78                 :            :   /* For a node x m_key[x] is roughly the node nearest to the root from which
      79                 :            :      exists a way to x only over nodes behind x.  Such a node is also called
      80                 :            :      semidominator.  */
      81                 :            :   TBB *m_key;
      82                 :            :   /* The value in m_path_min[x] is the node y on the path from x to the root of
      83                 :            :      the tree x is in with the smallest m_key[y].  */
      84                 :            :   TBB *m_path_min;
      85                 :            :   /* m_bucket[x] points to the first node of the set of nodes having x as
      86                 :            :      key.  */
      87                 :            :   TBB *m_bucket;
      88                 :            :   /* And m_next_bucket[x] points to the next node.  */
      89                 :            :   TBB *m_next_bucket;
      90                 :            :   /* After the algorithm is done, m_dom[x] contains the immediate dominator
      91                 :            :      of x.  */
      92                 :            :   TBB *m_dom;
      93                 :            : 
      94                 :            :   /* The following few fields implement the structures needed for disjoint
      95                 :            :      sets.  */
      96                 :            :   /* m_set_chain[x] is the next node on the path from x to the representative
      97                 :            :      of the set containing x.  If m_set_chain[x]==0 then x is a root.  */
      98                 :            :   TBB *m_set_chain;
      99                 :            :   /* m_set_size[x] is the number of elements in the set named by x.  */
     100                 :            :   unsigned int *m_set_size;
     101                 :            :   /* m_set_child[x] is used for balancing the tree representing a set.  It can
     102                 :            :      be understood as the next sibling of x.  */
     103                 :            :   TBB *m_set_child;
     104                 :            : 
     105                 :            :   /* If b is the number of a basic block (BB->index), m_dfs_order[b] is the
     106                 :            :      number of that node in DFS order counted from 1.  This is an index
     107                 :            :      into most of the other arrays in this structure.  */
     108                 :            :   TBB *m_dfs_order;
     109                 :            :   /* Points to last element in m_dfs_order array.  */
     110                 :            :   TBB *m_dfs_last;
     111                 :            :   /* If x is the DFS-index of a node which corresponds with a basic block,
     112                 :            :      m_dfs_to_bb[x] is that basic block.  Note, that in our structure there are
     113                 :            :      more nodes that basic blocks, so only
     114                 :            :      m_dfs_to_bb[m_dfs_order[bb->index]]==bb is true for every basic block bb,
     115                 :            :      but not the opposite.  */
     116                 :            :   basic_block *m_dfs_to_bb;
     117                 :            : 
     118                 :            :   /* This is the next free DFS number when creating the DFS tree.  */
     119                 :            :   unsigned int m_dfsnum;
     120                 :            :   /* The number of nodes in the DFS tree (==m_dfsnum-1).  */
     121                 :            :   unsigned int m_nodes;
     122                 :            : 
     123                 :            :   /* Blocks with bits set here have a fake edge to EXIT.  These are used
     124                 :            :      to turn a DFS forest into a proper tree.  */
     125                 :            :   bitmap m_fake_exit_edge;
     126                 :            : 
     127                 :            :   /* Number of basic blocks in the function being compiled.  */
     128                 :            :   unsigned m_n_basic_blocks;
     129                 :            : 
     130                 :            :   /* True, if we are computing postdominators (rather than dominators).  */
     131                 :            :   bool m_reverse;
     132                 :            : 
     133                 :            :   /* Start block (the entry block for forward problem, exit block for backward
     134                 :            :      problem).  */
     135                 :            :   basic_block m_start_block;
     136                 :            :   /* Ending block.  */
     137                 :            :   basic_block m_end_block;
     138                 :            : };
     139                 :            : 
     140                 :            : } // anonymous namespace
     141                 :            : 
     142                 :            : void debug_dominance_info (cdi_direction);
     143                 :            : void debug_dominance_tree (cdi_direction, basic_block);
     144                 :            : 
     145                 :            : /* Allocate and zero-initialize NUM elements of type T (T must be a
     146                 :            :    POD-type).  Note: after transition to C++11 or later,
     147                 :            :    `x = new_zero_array <T> (num);' can be replaced with
     148                 :            :    `x = new T[num] {};'.  */
     149                 :            : 
     150                 :            : template<typename T>
     151                 : 4666480000 : inline T *new_zero_array (unsigned num)
     152                 :            : {
     153                 : 4666480000 :   T *result = new T[num];
     154                 : 4666480000 :   memset (result, 0, sizeof (T) * num);
     155                 : 4666480000 :   return result;
     156                 :            : }
     157                 :            : 
     158                 :            : /* Helper function for constructors to initialize a part of class members.  */
     159                 :            : 
     160                 :            : void
     161                 :  583310000 : dom_info::dom_init (void)
     162                 :            : {
     163                 :  583310000 :   unsigned num = m_n_basic_blocks;
     164                 :            : 
     165                 :  583310000 :   m_dfs_parent = new_zero_array <TBB> (num);
     166                 :  583310000 :   m_dom = new_zero_array <TBB> (num);
     167                 :            : 
     168                 :  583310000 :   m_path_min = new TBB[num];
     169                 :  583310000 :   m_key = new TBB[num];
     170                 :  583310000 :   m_set_size = new unsigned int[num];
     171                 : 6932860000 :   for (unsigned i = 0; i < num; i++)
     172                 :            :     {
     173                 : 6349550000 :       m_path_min[i] = m_key[i] = i;
     174                 : 6349550000 :       m_set_size[i] = 1;
     175                 :            :     }
     176                 :            : 
     177                 :  583310000 :   m_bucket = new_zero_array <TBB> (num);
     178                 :  583310000 :   m_next_bucket = new_zero_array <TBB> (num);
     179                 :            : 
     180                 :  583310000 :   m_set_chain = new_zero_array <TBB> (num);
     181                 :  583310000 :   m_set_child = new_zero_array <TBB> (num);
     182                 :            : 
     183                 :  583310000 :   m_dfs_to_bb = new_zero_array <basic_block> (num);
     184                 :            : 
     185                 :  583310000 :   m_dfsnum = 1;
     186                 :  583310000 :   m_nodes = 0;
     187                 :  583310000 : }
     188                 :            : 
     189                 :            : /* Allocate all needed memory in a pessimistic fashion (so we round up).  */
     190                 :            : 
     191                 :  583305000 : dom_info::dom_info (function *fn, cdi_direction dir)
     192                 :            : {
     193                 :  583305000 :   m_n_basic_blocks = n_basic_blocks_for_fn (fn);
     194                 :            : 
     195                 :  583305000 :   dom_init ();
     196                 :            : 
     197                 :  583305000 :   unsigned last_bb_index = last_basic_block_for_fn (fn);
     198                 :  583305000 :   m_dfs_order = new_zero_array <TBB> (last_bb_index + 1);
     199                 :  583305000 :   m_dfs_last = &m_dfs_order[last_bb_index];
     200                 :            : 
     201                 :  583305000 :   switch (dir)
     202                 :            :     {
     203                 :  567133000 :       case CDI_DOMINATORS:
     204                 :  567133000 :         m_reverse = false;
     205                 :  567133000 :         m_fake_exit_edge = NULL;
     206                 :  567133000 :         m_start_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
     207                 :  567133000 :         m_end_block = EXIT_BLOCK_PTR_FOR_FN (fn);
     208                 :  567133000 :         break;
     209                 :   16172400 :       case CDI_POST_DOMINATORS:
     210                 :   16172400 :         m_reverse = true;
     211                 :   16172400 :         m_fake_exit_edge = BITMAP_ALLOC (NULL);
     212                 :   16172400 :         m_start_block = EXIT_BLOCK_PTR_FOR_FN (fn);
     213                 :   16172400 :         m_end_block = ENTRY_BLOCK_PTR_FOR_FN (fn);
     214                 :   16172400 :         break;
     215                 :          0 :       default:
     216                 :          0 :         gcc_unreachable ();
     217                 :            :     }
     218                 :  583305000 : }
     219                 :            : 
     220                 :            : /* Constructor for reducible region REGION.  */
     221                 :            : 
     222                 :       4799 : dom_info::dom_info (vec<basic_block> region, cdi_direction dir)
     223                 :            : {
     224                 :       4799 :   m_n_basic_blocks = region.length ();
     225                 :       4799 :   unsigned nm1 = m_n_basic_blocks - 1;
     226                 :            : 
     227                 :       4799 :   dom_init ();
     228                 :            : 
     229                 :            :   /* Determine max basic block index in region.  */
     230                 :       4799 :   int max_index = region[0]->index;
     231                 :      37632 :   for (unsigned i = 1; i <= nm1; i++)
     232                 :      32833 :     if (region[i]->index > max_index)
     233                 :            :       max_index = region[i]->index;
     234                 :       4799 :   max_index += 1;  /* set index on the first bb out of region.  */
     235                 :            : 
     236                 :       4799 :   m_dfs_order = new_zero_array <TBB> (max_index + 1);
     237                 :       4799 :   m_dfs_last = &m_dfs_order[max_index];
     238                 :            : 
     239                 :       4799 :   m_fake_exit_edge = NULL; /* Assume that region is reducible.  */
     240                 :            : 
     241                 :       4799 :   switch (dir)
     242                 :            :     {
     243                 :          0 :       case CDI_DOMINATORS:
     244                 :          0 :         m_reverse = false;
     245                 :          0 :         m_start_block = region[0];
     246                 :          0 :         m_end_block = region[nm1];
     247                 :          0 :         break;
     248                 :       4799 :       case CDI_POST_DOMINATORS:
     249                 :       4799 :         m_reverse = true;
     250                 :       4799 :         m_start_block = region[nm1];
     251                 :       4799 :         m_end_block = region[0];
     252                 :       4799 :         break;
     253                 :          0 :       default:
     254                 :          0 :         gcc_unreachable ();
     255                 :            :     }
     256                 :       4799 : }
     257                 :            : 
     258                 :            : inline basic_block
     259                 : 5182940000 : dom_info::get_idom (basic_block bb)
     260                 :            : {
     261                 : 5182940000 :   TBB d = m_dom[m_dfs_order[bb->index]];
     262                 : 5182940000 :   return m_dfs_to_bb[d];
     263                 :            : }
     264                 :            : 
     265                 :            : /* Map dominance calculation type to array index used for various
     266                 :            :    dominance information arrays.  This version is simple -- it will need
     267                 :            :    to be modified, obviously, if additional values are added to
     268                 :            :    cdi_direction.  */
     269                 :            : 
     270                 :            : static inline unsigned int
     271                 :20690700000 : dom_convert_dir_to_idx (cdi_direction dir)
     272                 :            : {
     273                 :          0 :   gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
     274                 :20690700000 :   return dir - 1;
     275                 :            : }
     276                 :            : 
     277                 :            : /* Free all allocated memory in dom_info.  */
     278                 :            : 
     279                 : 1166620000 : dom_info::~dom_info ()
     280                 :            : {
     281                 :  583310000 :   delete[] m_dfs_parent;
     282                 :  583310000 :   delete[] m_path_min;
     283                 :  583310000 :   delete[] m_key;
     284                 :  583310000 :   delete[] m_dom;
     285                 :  583310000 :   delete[] m_bucket;
     286                 :  583310000 :   delete[] m_next_bucket;
     287                 :  583310000 :   delete[] m_set_chain;
     288                 :  583310000 :   delete[] m_set_size;
     289                 :  583310000 :   delete[] m_set_child;
     290                 :  583310000 :   delete[] m_dfs_order;
     291                 :  583310000 :   delete[] m_dfs_to_bb;
     292                 :  583310000 :   BITMAP_FREE (m_fake_exit_edge);
     293                 :  583310000 : }
     294                 :            : 
     295                 :            : /* The nonrecursive variant of creating a DFS tree.  BB is the starting basic
     296                 :            :    block for this tree and m_reverse is true, if predecessors should be visited
     297                 :            :    instead of successors of a node.  After this is done all nodes reachable
     298                 :            :    from BB were visited, have assigned their dfs number and are linked together
     299                 :            :    to form a tree.  */
     300                 :            : 
     301                 :            : void
     302                 :  590572000 : dom_info::calc_dfs_tree_nonrec (basic_block bb)
     303                 :            : {
     304                 :  590572000 :   edge_iterator *stack = new edge_iterator[m_n_basic_blocks + 1];
     305                 :  590572000 :   int sp = 0;
     306                 :  590572000 :   unsigned d_i = dom_convert_dir_to_idx (m_reverse ? CDI_POST_DOMINATORS
     307                 :            :                                          : CDI_DOMINATORS);
     308                 :            : 
     309                 :            :   /* Initialize the first edge.  */
     310                 :   23439000 :   edge_iterator ei = m_reverse ? ei_start (bb->preds)
     311                 :  590572000 :                                : ei_start (bb->succs);
     312                 :            : 
     313                 :            :   /* When the stack is empty we break out of this loop.  */
     314                 :18811800000 :   while (1)
     315                 :            :     {
     316                 :13636200000 :       basic_block bn;
     317                 :13636200000 :       edge_iterator einext;
     318                 :            : 
     319                 :            :       /* This loop traverses edges e in depth first manner, and fills the
     320                 :            :          stack.  */
     321                 :27272300000 :       while (!ei_end_p (ei))
     322                 :            :         {
     323                 : 7869940000 :           edge e = ei_edge (ei);
     324                 :            : 
     325                 :            :           /* Deduce from E the current and the next block (BB and BN), and the
     326                 :            :              next edge.  */
     327                 : 7869940000 :           if (m_reverse)
     328                 :            :             {
     329                 :  191740000 :               bn = e->src;
     330                 :            : 
     331                 :            :               /* If the next node BN is either already visited or a border
     332                 :            :                  block or out of region the current edge is useless, and simply
     333                 :            :                  overwritten with the next edge out of the current node.  */
     334                 :  191740000 :               if (bn == m_end_block || bn->dom[d_i] == NULL
     335                 :  175562000 :                   || m_dfs_order[bn->index])
     336                 :            :                 {
     337                 :   74045500 :                   ei_next (&ei);
     338                 :   74045500 :                   continue;
     339                 :            :                 }
     340                 :  117695000 :               bb = e->dest;
     341                 :  117695000 :               einext = ei_start (bn->preds);
     342                 :            :             }
     343                 :            :           else
     344                 :            :             {
     345                 : 7678200000 :               bn = e->dest;
     346                 : 7678200000 :               if (bn == m_end_block || bn->dom[d_i] == NULL
     347                 : 7119040000 :                   || m_dfs_order[bn->index])
     348                 :            :                 {
     349                 : 2620230000 :                   ei_next (&ei);
     350                 : 2620230000 :                   continue;
     351                 :            :                 }
     352                 : 5057970000 :               bb = e->src;
     353                 : 5057970000 :               einext = ei_start (bn->succs);
     354                 :            :             }
     355                 :            : 
     356                 : 5175660000 :           gcc_assert (bn != m_start_block);
     357                 :            : 
     358                 :            :           /* Fill the DFS tree info calculatable _before_ recursing.  */
     359                 : 5175660000 :           TBB my_i;
     360                 : 5175660000 :           if (bb != m_start_block)
     361                 : 4591800000 :             my_i = m_dfs_order[bb->index];
     362                 :            :           else
     363                 :  583868000 :             my_i = *m_dfs_last;
     364                 : 5175660000 :           TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
     365                 : 5175660000 :           m_dfs_to_bb[child_i] = bn;
     366                 : 5175660000 :           m_dfs_parent[child_i] = my_i;
     367                 :            : 
     368                 :            :           /* Save the current point in the CFG on the stack, and recurse.  */
     369                 : 5175660000 :           stack[sp++] = ei;
     370                 : 5175660000 :           ei = einext;
     371                 :            :         }
     372                 :            : 
     373                 : 5766240000 :       if (!sp)
     374                 :            :         break;
     375                 : 5175660000 :       ei = stack[--sp];
     376                 :            : 
     377                 :            :       /* OK.  The edge-list was exhausted, meaning normally we would
     378                 :            :          end the recursion.  After returning from the recursive call,
     379                 :            :          there were (may be) other statements which were run after a
     380                 :            :          child node was completely considered by DFS.  Here is the
     381                 :            :          point to do it in the non-recursive variant.
     382                 :            :          E.g. The block just completed is in e->dest for forward DFS,
     383                 :            :          the block not yet completed (the parent of the one above)
     384                 :            :          in e->src.  This could be used e.g. for computing the number of
     385                 :            :          descendants or the tree depth.  */
     386                 : 5175660000 :       ei_next (&ei);
     387                 : 5175660000 :     }
     388                 :  590572000 :   delete[] stack;
     389                 :  590572000 : }
     390                 :            : 
     391                 :            : /* The main entry for calculating the DFS tree or forest.  m_reverse is true,
     392                 :            :    if we are interested in the reverse flow graph.  In that case the result is
     393                 :            :    not necessarily a tree but a forest, because there may be nodes from which
     394                 :            :    the EXIT_BLOCK is unreachable.  */
     395                 :            : 
     396                 :            : void
     397                 :  583310000 : dom_info::calc_dfs_tree ()
     398                 :            : {
     399                 :  583310000 :   *m_dfs_last = m_dfsnum;
     400                 :  583310000 :   m_dfs_to_bb[m_dfsnum] = m_start_block;
     401                 :  583310000 :   m_dfsnum++;
     402                 :            : 
     403                 :  583310000 :   calc_dfs_tree_nonrec (m_start_block);
     404                 :            : 
     405                 :  583310000 :   if (m_fake_exit_edge)
     406                 :            :     {
     407                 :            :       /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
     408                 :            :          They are reverse-unreachable.  In the dom-case we disallow such
     409                 :            :          nodes, but in post-dom we have to deal with them.
     410                 :            : 
     411                 :            :          There are two situations in which this occurs.  First, noreturn
     412                 :            :          functions.  Second, infinite loops.  In the first case we need to
     413                 :            :          pretend that there is an edge to the exit block.  In the second
     414                 :            :          case, we wind up with a forest.  We need to process all noreturn
     415                 :            :          blocks before we know if we've got any infinite loops.  */
     416                 :            : 
     417                 :   16172400 :       basic_block b;
     418                 :   16172400 :       bool saw_unconnected = false;
     419                 :            : 
     420                 :  141101000 :       FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
     421                 :            :         {
     422                 :  124929000 :           if (EDGE_COUNT (b->succs) > 0)
     423                 :            :             {
     424                 :  117735000 :               if (m_dfs_order[b->index] == 0)
     425                 :     502262 :                 saw_unconnected = true;
     426                 :  117735000 :               continue;
     427                 :            :             }
     428                 :    7193600 :           bitmap_set_bit (m_fake_exit_edge, b->index);
     429                 :    7193600 :           m_dfs_order[b->index] = m_dfsnum;
     430                 :    7193600 :           m_dfs_to_bb[m_dfsnum] = b;
     431                 :    7193600 :           m_dfs_parent[m_dfsnum] = *m_dfs_last;
     432                 :    7193600 :           m_dfsnum++;
     433                 :    7193600 :           calc_dfs_tree_nonrec (b);
     434                 :            :         }
     435                 :            : 
     436                 :   16172400 :       if (saw_unconnected)
     437                 :            :         {
     438                 :    3828110 :           FOR_BB_BETWEEN (b, m_start_block->prev_bb, m_end_block, prev_bb)
     439                 :            :             {
     440                 :    3715840 :               if (m_dfs_order[b->index])
     441                 :    3647570 :                 continue;
     442                 :      68272 :               basic_block b2 = dfs_find_deadend (b);
     443                 :      68272 :               gcc_checking_assert (m_dfs_order[b2->index] == 0);
     444                 :      68272 :               bitmap_set_bit (m_fake_exit_edge, b2->index);
     445                 :      68272 :               m_dfs_order[b2->index] = m_dfsnum;
     446                 :      68272 :               m_dfs_to_bb[m_dfsnum] = b2;
     447                 :      68272 :               m_dfs_parent[m_dfsnum] = *m_dfs_last;
     448                 :      68272 :               m_dfsnum++;
     449                 :      68272 :               calc_dfs_tree_nonrec (b2);
     450                 :      68272 :               gcc_checking_assert (m_dfs_order[b->index]);
     451                 :            :             }
     452                 :            :         }
     453                 :            :     }
     454                 :            : 
     455                 :  583310000 :   m_nodes = m_dfsnum - 1;
     456                 :            : 
     457                 :            :   /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
     458                 :  583310000 :   gcc_assert (m_nodes == (unsigned int) m_n_basic_blocks - 1);
     459                 :  583310000 : }
     460                 :            : 
     461                 :            : /* Compress the path from V to the root of its set and update path_min at the
     462                 :            :    same time.  After compress(di, V) set_chain[V] is the root of the set V is
     463                 :            :    in and path_min[V] is the node with the smallest key[] value on the path
     464                 :            :    from V to that root.  */
     465                 :            : 
     466                 :            : void
     467                 : 1939460000 : dom_info::compress (TBB v)
     468                 :            : {
     469                 :            :   /* Btw. It's not worth to unrecurse compress() as the depth is usually not
     470                 :            :      greater than 5 even for huge graphs (I've not seen call depth > 4).
     471                 :            :      Also performance wise compress() ranges _far_ behind eval().  */
     472                 : 1939460000 :   TBB parent = m_set_chain[v];
     473                 : 1939460000 :   if (m_set_chain[parent])
     474                 :            :     {
     475                 : 1070980000 :       compress (parent);
     476                 : 1070980000 :       if (m_key[m_path_min[parent]] < m_key[m_path_min[v]])
     477                 :  706560000 :         m_path_min[v] = m_path_min[parent];
     478                 : 1070980000 :       m_set_chain[v] = m_set_chain[parent];
     479                 :            :     }
     480                 : 1939460000 : }
     481                 :            : 
     482                 :            : /* Compress the path from V to the set root of V if needed (when the root has
     483                 :            :    changed since the last call).  Returns the node with the smallest key[]
     484                 :            :    value on the path from V to the root.  */
     485                 :            : 
     486                 :            : inline TBB
     487                 : 6814100000 : dom_info::eval (TBB v)
     488                 :            : {
     489                 :            :   /* The representative of the set V is in, also called root (as the set
     490                 :            :      representation is a tree).  */
     491                 : 6814100000 :   TBB rep = m_set_chain[v];
     492                 :            : 
     493                 :            :   /* V itself is the root.  */
     494                 : 6814100000 :   if (!rep)
     495                 : 1512840000 :     return m_path_min[v];
     496                 :            : 
     497                 :            :   /* Compress only if necessary.  */
     498                 : 5301260000 :   if (m_set_chain[rep])
     499                 :            :     {
     500                 :  868483000 :       compress (v);
     501                 :  868483000 :       rep = m_set_chain[v];
     502                 :            :     }
     503                 :            : 
     504                 : 5301260000 :   if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]])
     505                 :            :     return m_path_min[v];
     506                 :            :   else
     507                 :  933755000 :     return m_path_min[rep];
     508                 :            : }
     509                 :            : 
     510                 :            : /* This essentially merges the two sets of V and W, giving a single set with
     511                 :            :    the new root V.  The internal representation of these disjoint sets is a
     512                 :            :    balanced tree.  Currently link(V,W) is only used with V being the parent
     513                 :            :    of W.  */
     514                 :            : 
     515                 :            : void
     516                 : 5182930000 : dom_info::link_roots (TBB v, TBB w)
     517                 :            : {
     518                 : 5182930000 :   TBB s = w;
     519                 :            : 
     520                 :            :   /* Rebalance the tree.  */
     521                 : 7738060000 :   while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
     522                 :            :     {
     523                 : 2555130000 :       if (m_set_size[s] + m_set_size[m_set_child[m_set_child[s]]]
     524                 : 2555130000 :           >= 2 * m_set_size[m_set_child[s]])
     525                 :            :         {
     526                 :  872838000 :           m_set_chain[m_set_child[s]] = s;
     527                 :  872838000 :           m_set_child[s] = m_set_child[m_set_child[s]];
     528                 :            :         }
     529                 :            :       else
     530                 :            :         {
     531                 : 1682290000 :           m_set_size[m_set_child[s]] = m_set_size[s];
     532                 : 1682290000 :           s = m_set_chain[s] = m_set_child[s];
     533                 :            :         }
     534                 :            :     }
     535                 :            : 
     536                 : 5182930000 :   m_path_min[s] = m_path_min[w];
     537                 : 5182930000 :   m_set_size[v] += m_set_size[w];
     538                 : 5182930000 :   if (m_set_size[v] < 2 * m_set_size[w])
     539                 : 3043860000 :     std::swap (m_set_child[v], s);
     540                 :            : 
     541                 :            :   /* Merge all subtrees.  */
     542                 : 7495720000 :   while (s)
     543                 :            :     {
     544                 : 2312790000 :       m_set_chain[s] = v;
     545                 : 2312790000 :       s = m_set_child[s];
     546                 :            :     }
     547                 : 5182930000 : }
     548                 :            : 
     549                 :            : /* This calculates the immediate dominators (or post-dominators). THIS is our
     550                 :            :    working structure and should hold the DFS forest.
     551                 :            :    On return the immediate dominator to node V is in m_dom[V].  */
     552                 :            : 
     553                 :            : void
     554                 :  583310000 : dom_info::calc_idoms ()
     555                 :            : {
     556                 :            :   /* Go backwards in DFS order, to first look at the leafs.  */
     557                 : 5766240000 :   for (TBB v = m_nodes; v > 1; v--)
     558                 :            :     {
     559                 : 5182930000 :       basic_block bb = m_dfs_to_bb[v];
     560                 : 5182930000 :       edge e;
     561                 :            : 
     562                 : 5182930000 :       TBB par = m_dfs_parent[v];
     563                 : 5182930000 :       TBB k = v;
     564                 :            : 
     565                 :  124957000 :       edge_iterator ei = m_reverse ? ei_start (bb->succs)
     566                 : 5182930000 :                                    : ei_start (bb->preds);
     567                 : 5182930000 :       edge_iterator einext;
     568                 :            : 
     569                 : 5182930000 :       if (m_fake_exit_edge)
     570                 :            :         {
     571                 :            :           /* If this block has a fake edge to exit, process that first.  */
     572                 :  124929000 :           if (bitmap_bit_p (m_fake_exit_edge, bb->index))
     573                 :            :             {
     574                 :    7261880 :               einext = ei;
     575                 :    7261880 :               einext.index = 0;
     576                 :    7261880 :               goto do_fake_exit_edge;
     577                 :            :             }
     578                 :            :         }
     579                 :            : 
     580                 :            :       /* Search all direct predecessors for the smallest node with a path
     581                 :            :          to them.  That way we have the smallest node with also a path to
     582                 :            :          us only over nodes behind us.  In effect we search for our
     583                 :            :          semidominator.  */
     584                 :24955100000 :       while (!ei_end_p (ei))
     585                 :            :         {
     586                 : 7294600000 :           basic_block b;
     587                 : 7294600000 :           TBB k1;
     588                 :            : 
     589                 : 7294600000 :           e = ei_edge (ei);
     590                 : 7294600000 :           b = m_reverse ? e->dest : e->src;
     591                 : 7294600000 :           einext = ei;
     592                 : 7294600000 :           ei_next (&einext);
     593                 :            : 
     594                 : 7294600000 :           if (b == m_start_block)
     595                 :            :             {
     596                 :  583868000 :             do_fake_exit_edge:
     597                 :  591130000 :               k1 = *m_dfs_last;
     598                 :            :             }
     599                 :            :           else
     600                 : 6710730000 :             k1 = m_dfs_order[b->index];
     601                 :            : 
     602                 :            :           /* Call eval() only if really needed.  If k1 is above V in DFS tree,
     603                 :            :              then we know, that eval(k1) == k1 and key[k1] == k1.  */
     604                 : 7301860000 :           if (k1 > v)
     605                 : 1631180000 :             k1 = m_key[eval (k1)];
     606                 : 7301860000 :           if (k1 < k)
     607                 :            :             k = k1;
     608                 :            : 
     609                 : 7301860000 :           ei = einext;
     610                 :            :         }
     611                 :            : 
     612                 : 5182930000 :       m_key[v] = k;
     613                 : 5182930000 :       link_roots (par, v);
     614                 : 5182930000 :       m_next_bucket[v] = m_bucket[k];
     615                 : 5182930000 :       m_bucket[k] = v;
     616                 :            : 
     617                 :            :       /* Transform semidominators into dominators.  */
     618                 :10365900000 :       for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
     619                 :            :         {
     620                 : 5182930000 :           k = eval (w);
     621                 : 5182930000 :           if (m_key[k] < m_key[w])
     622                 :   21094700 :             m_dom[w] = k;
     623                 :            :           else
     624                 : 5161830000 :             m_dom[w] = par;
     625                 :            :         }
     626                 :            :       /* We don't need to cleanup next_bucket[].  */
     627                 : 5182930000 :       m_bucket[par] = 0;
     628                 :            :     }
     629                 :            : 
     630                 :            :   /* Explicitly define the dominators.  */
     631                 :  583310000 :   m_dom[1] = 0;
     632                 : 5766240000 :   for (TBB v = 2; v <= m_nodes; v++)
     633                 : 5182930000 :     if (m_dom[v] != m_key[v])
     634                 :   21094700 :       m_dom[v] = m_dom[m_dom[v]];
     635                 :  583310000 : }
     636                 :            : 
     637                 :            : /* Assign dfs numbers starting from NUM to NODE and its sons.  */
     638                 :            : 
     639                 :            : static void
     640                 : 1490300000 : assign_dfs_numbers (struct et_node *node, int *num)
     641                 :            : {
     642                 : 1490300000 :   struct et_node *son;
     643                 :            : 
     644                 : 1490300000 :   node->dfs_num_in = (*num)++;
     645                 :            : 
     646                 : 1490300000 :   if (node->son)
     647                 :            :     {
     648                 :  729173000 :       assign_dfs_numbers (node->son, num);
     649                 : 1217380000 :       for (son = node->son->right; son != node->son; son = son->right)
     650                 :  488209000 :         assign_dfs_numbers (son, num);
     651                 :            :     }
     652                 :            : 
     653                 : 1490300000 :   node->dfs_num_out = (*num)++;
     654                 : 1490300000 : }
     655                 :            : 
     656                 :            : /* Compute the data necessary for fast resolving of dominator queries in a
     657                 :            :    static dominator tree.  */
     658                 :            : 
     659                 :            : static void
     660                 :  136459000 : compute_dom_fast_query (enum cdi_direction dir)
     661                 :            : {
     662                 :  136459000 :   int num = 0;
     663                 :  136459000 :   basic_block bb;
     664                 :  136459000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     665                 :            : 
     666                 :  136459000 :   gcc_checking_assert (dom_info_available_p (dir));
     667                 :            : 
     668                 :  136459000 :   if (dom_computed[dir_index] == DOM_OK)
     669                 :          0 :     return;
     670                 :            : 
     671                 : 1626760000 :   FOR_ALL_BB_FN (bb, cfun)
     672                 :            :     {
     673                 : 1490300000 :       if (!bb->dom[dir_index]->father)
     674                 :  272918000 :         assign_dfs_numbers (bb->dom[dir_index], &num);
     675                 :            :     }
     676                 :            : 
     677                 :  136459000 :   dom_computed[dir_index] = DOM_OK;
     678                 :            : }
     679                 :            : 
     680                 :            : /* Analogous to the previous function but compute the data for reducible
     681                 :            :    region REGION.  */
     682                 :            : 
     683                 :            : static void
     684                 :       4799 : compute_dom_fast_query_in_region (enum cdi_direction dir,
     685                 :            :                                   vec<basic_block> region)
     686                 :            : {
     687                 :       4799 :   int num = 0;
     688                 :       4799 :   basic_block bb;
     689                 :       4799 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     690                 :            : 
     691                 :       4799 :   gcc_checking_assert (dom_info_available_p (dir));
     692                 :            : 
     693                 :       4799 :   if (dom_computed[dir_index] == DOM_OK)
     694                 :          0 :     return;
     695                 :            : 
     696                 :            :   /* Assign dfs numbers for region nodes except for entry and exit nodes.  */
     697                 :      65666 :   for (unsigned int i = 1; i < region.length () - 1; i++)
     698                 :            :     {
     699                 :      28034 :       bb = region[i];
     700                 :      28034 :       if (!bb->dom[dir_index]->father)
     701                 :          0 :         assign_dfs_numbers (bb->dom[dir_index], &num);
     702                 :            :     }
     703                 :            : 
     704                 :       4799 :   dom_computed[dir_index] = DOM_OK;
     705                 :            : }
     706                 :            : 
     707                 :            : /* The main entry point into this module.  DIR is set depending on whether
     708                 :            :    we want to compute dominators or postdominators.  */
     709                 :            : 
     710                 :            : void
     711                 :  294647000 : calculate_dominance_info (cdi_direction dir)
     712                 :            : {
     713                 :  294647000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     714                 :            : 
     715                 :  294647000 :   if (dom_computed[dir_index] == DOM_OK)
     716                 :            :     {
     717                 :  158188000 :       checking_verify_dominators (dir);
     718                 :  158188000 :       return;
     719                 :            :     }
     720                 :            : 
     721                 :  136459000 :   timevar_push (TV_DOMINANCE);
     722                 :  136459000 :   if (!dom_info_available_p (dir))
     723                 :            :     {
     724                 :  127948000 :       gcc_assert (!n_bbs_in_dom_tree[dir_index]);
     725                 :            : 
     726                 :  127948000 :       basic_block b;
     727                 : 1383510000 :       FOR_ALL_BB_FN (b, cfun)
     728                 :            :         {
     729                 : 1255560000 :           b->dom[dir_index] = et_new_tree (b);
     730                 :            :         }
     731                 :  127948000 :       n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
     732                 :            : 
     733                 :  127948000 :       dom_info di (cfun, dir);
     734                 :  127948000 :       di.calc_dfs_tree ();
     735                 :  127948000 :       di.calc_idoms ();
     736                 :            : 
     737                 : 1127610000 :       FOR_EACH_BB_FN (b, cfun)
     738                 :            :         {
     739                 :  999665000 :           if (basic_block d = di.get_idom (b))
     740                 :  999665000 :             et_set_father (b->dom[dir_index], d->dom[dir_index]);
     741                 :            :         }
     742                 :            : 
     743                 :  127948000 :       dom_computed[dir_index] = DOM_NO_FAST_QUERY;
     744                 :            :     }
     745                 :            :   else
     746                 :    8510730 :     checking_verify_dominators (dir);
     747                 :            : 
     748                 :  136459000 :   compute_dom_fast_query (dir);
     749                 :            : 
     750                 :  136459000 :   timevar_pop (TV_DOMINANCE);
     751                 :            : }
     752                 :            : 
     753                 :            : /* Analogous to the previous function but compute dominance info for regions
     754                 :            :    which are single entry, multiple exit regions for CDI_DOMINATORs and
     755                 :            :    multiple entry, single exit regions for CDI_POST_DOMINATORs.  */
     756                 :            : 
     757                 :            : void
     758                 :       4799 : calculate_dominance_info_for_region (cdi_direction dir,
     759                 :            :                                      vec<basic_block> region)
     760                 :            : {
     761                 :       4799 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     762                 :       4799 :   basic_block bb;
     763                 :       4799 :   unsigned int i;
     764                 :            : 
     765                 :       4799 :   if (dom_computed[dir_index] == DOM_OK)
     766                 :          0 :     return;
     767                 :            : 
     768                 :       4799 :   timevar_push (TV_DOMINANCE);
     769                 :            :   /* Assume that dom info is not partially computed.  */
     770                 :       4799 :   gcc_assert (!dom_info_available_p (dir));
     771                 :            : 
     772                 :      42431 :   FOR_EACH_VEC_ELT (region, i, bb)
     773                 :            :     {
     774                 :      37632 :       bb->dom[dir_index] = et_new_tree (bb);
     775                 :            :     }
     776                 :       4799 :   dom_info di (region, dir);
     777                 :       4799 :   di.calc_dfs_tree ();
     778                 :       4799 :   di.calc_idoms ();
     779                 :            : 
     780                 :      42431 :   FOR_EACH_VEC_ELT (region, i, bb)
     781                 :      37632 :     if (basic_block d = di.get_idom (bb))
     782                 :      28034 :       et_set_father (bb->dom[dir_index], d->dom[dir_index]);
     783                 :            : 
     784                 :       4799 :   dom_computed[dir_index] = DOM_NO_FAST_QUERY;
     785                 :       4799 :   compute_dom_fast_query_in_region (dir, region);
     786                 :            : 
     787                 :       4799 :   timevar_pop (TV_DOMINANCE);
     788                 :            : }
     789                 :            : 
     790                 :            : /* Free dominance information for direction DIR.  */
     791                 :            : void
     792                 :  247434000 : free_dominance_info (function *fn, enum cdi_direction dir)
     793                 :            : {
     794                 :  247434000 :   basic_block bb;
     795                 :  247434000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     796                 :            : 
     797                 :  247434000 :   if (!dom_info_available_p (fn, dir))
     798                 :            :     return;
     799                 :            : 
     800                 : 1373680000 :   FOR_ALL_BB_FN (bb, fn)
     801                 :            :     {
     802                 : 1245780000 :       et_free_tree_force (bb->dom[dir_index]);
     803                 : 1245780000 :       bb->dom[dir_index] = NULL;
     804                 :            :     }
     805                 :  127898000 :   et_free_pools ();
     806                 :            : 
     807                 :  127898000 :   fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
     808                 :            : 
     809                 :  127898000 :   fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
     810                 :            : }
     811                 :            : 
     812                 :            : void
     813                 :  152783000 : free_dominance_info (enum cdi_direction dir)
     814                 :            : {
     815                 :  152783000 :   free_dominance_info (cfun, dir);
     816                 :  152783000 : }
     817                 :            : 
     818                 :            : /* Free dominance information for direction DIR in region REGION.  */
     819                 :            : 
     820                 :            : void
     821                 :       4799 : free_dominance_info_for_region (function *fn,
     822                 :            :                                 enum cdi_direction dir,
     823                 :            :                                 vec<basic_block> region)
     824                 :            : {
     825                 :       4799 :   basic_block bb;
     826                 :       4799 :   unsigned int i;
     827                 :       4799 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     828                 :            : 
     829                 :       4799 :   if (!dom_info_available_p (dir))
     830                 :       4799 :     return;
     831                 :            : 
     832                 :      42431 :   FOR_EACH_VEC_ELT (region, i, bb)
     833                 :            :     {
     834                 :      37632 :       et_free_tree_force (bb->dom[dir_index]);
     835                 :      37632 :       bb->dom[dir_index] = NULL;
     836                 :            :     }
     837                 :       4799 :   et_free_pools ();
     838                 :            : 
     839                 :       4799 :   fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
     840                 :            : 
     841                 :       4799 :   fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
     842                 :            : }
     843                 :            : 
     844                 :            : /* Return the immediate dominator of basic block BB.  */
     845                 :            : basic_block
     846                 : 4785520000 : get_immediate_dominator (enum cdi_direction dir, basic_block bb)
     847                 :            : {
     848                 : 4785520000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     849                 : 4785520000 :   struct et_node *node = bb->dom[dir_index];
     850                 :            : 
     851                 : 4785520000 :   gcc_checking_assert (dom_computed[dir_index]);
     852                 :            : 
     853                 : 4785520000 :   if (!node->father)
     854                 :            :     return NULL;
     855                 :            : 
     856                 : 4777690000 :   return (basic_block) node->father->data;
     857                 :            : }
     858                 :            : 
     859                 :            : /* Set the immediate dominator of the block possibly removing
     860                 :            :    existing edge.  NULL can be used to remove any edge.  */
     861                 :            : void
     862                 :   34464600 : set_immediate_dominator (enum cdi_direction dir, basic_block bb,
     863                 :            :                          basic_block dominated_by)
     864                 :            : {
     865                 :   34464600 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     866                 :   34464600 :   struct et_node *node = bb->dom[dir_index];
     867                 :            : 
     868                 :   34464600 :   gcc_checking_assert (dom_computed[dir_index]);
     869                 :            : 
     870                 :   34464600 :   if (node->father)
     871                 :            :     {
     872                 :   18587400 :       if (node->father->data == dominated_by)
     873                 :            :         return;
     874                 :    7635580 :       et_split (node);
     875                 :            :     }
     876                 :            : 
     877                 :   23512800 :   if (dominated_by)
     878                 :   22647700 :     et_set_father (node, dominated_by->dom[dir_index]);
     879                 :            : 
     880                 :   23512800 :   if (dom_computed[dir_index] == DOM_OK)
     881                 :     745564 :     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
     882                 :            : }
     883                 :            : 
     884                 :            : /* Returns the list of basic blocks immediately dominated by BB, in the
     885                 :            :    direction DIR.  */
     886                 :            : vec<basic_block> 
     887                 :     326947 : get_dominated_by (enum cdi_direction dir, basic_block bb)
     888                 :            : {
     889                 :     326947 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     890                 :     326947 :   struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
     891                 :     326947 :   vec<basic_block> bbs = vNULL;
     892                 :            : 
     893                 :     326947 :   gcc_checking_assert (dom_computed[dir_index]);
     894                 :            : 
     895                 :     326947 :   if (!son)
     896                 :     137880 :     return vNULL;
     897                 :            : 
     898                 :     189067 :   bbs.safe_push ((basic_block) son->data);
     899                 :     310193 :   for (ason = son->right; ason != son; ason = ason->right)
     900                 :     121126 :     bbs.safe_push ((basic_block) ason->data);
     901                 :            : 
     902                 :     189067 :   return bbs;
     903                 :            : }
     904                 :            : 
     905                 :            : /* Returns the list of basic blocks that are immediately dominated (in
     906                 :            :    direction DIR) by some block between N_REGION ones stored in REGION,
     907                 :            :    except for blocks in the REGION itself.  */
     908                 :            : 
     909                 :            : vec<basic_block> 
     910                 :     209139 : get_dominated_by_region (enum cdi_direction dir, basic_block *region,
     911                 :            :                          unsigned n_region)
     912                 :            : {
     913                 :     209139 :   unsigned i;
     914                 :     209139 :   basic_block dom;
     915                 :     209139 :   vec<basic_block> doms = vNULL;
     916                 :            : 
     917                 :     842141 :   for (i = 0; i < n_region; i++)
     918                 :     633002 :     region[i]->flags |= BB_DUPLICATED;
     919                 :     842141 :   for (i = 0; i < n_region; i++)
     920                 :     633002 :     for (dom = first_dom_son (dir, region[i]);
     921                 :    1443460 :          dom;
     922                 :     810461 :          dom = next_dom_son (dir, dom))
     923                 :     810461 :       if (!(dom->flags & BB_DUPLICATED))
     924                 :     386598 :         doms.safe_push (dom);
     925                 :     842141 :   for (i = 0; i < n_region; i++)
     926                 :     633002 :     region[i]->flags &= ~BB_DUPLICATED;
     927                 :            : 
     928                 :     209139 :   return doms;
     929                 :            : }
     930                 :            : 
     931                 :            : /* Returns the list of basic blocks including BB dominated by BB, in the
     932                 :            :    direction DIR up to DEPTH in the dominator tree.  The DEPTH of zero will
     933                 :            :    produce a vector containing all dominated blocks.  The vector will be sorted
     934                 :            :    in preorder.  */
     935                 :            : 
     936                 :            : vec<basic_block> 
     937                 :    6160670 : get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
     938                 :            : {
     939                 :    6160670 :   vec<basic_block> bbs = vNULL;
     940                 :    6160670 :   unsigned i;
     941                 :    6160670 :   unsigned next_level_start;
     942                 :            : 
     943                 :    6160670 :   i = 0;
     944                 :    6160670 :   bbs.safe_push (bb);
     945                 :    6160670 :   next_level_start = 1; /* = bbs.length (); */
     946                 :            : 
     947                 :   59541700 :   do
     948                 :            :     {
     949                 :   59541700 :       basic_block son;
     950                 :            : 
     951                 :   59541700 :       bb = bbs[i++];
     952                 :   59541700 :       for (son = first_dom_son (dir, bb);
     953                 :  113015000 :            son;
     954                 :   53472800 :            son = next_dom_son (dir, son))
     955                 :   53472800 :         bbs.safe_push (son);
     956                 :            : 
     957                 :   59541700 :       if (i == next_level_start && --depth)
     958                 :   26803200 :         next_level_start = bbs.length ();
     959                 :            :     }
     960                 :   59541700 :   while (i < next_level_start);
     961                 :            : 
     962                 :    6160670 :   return bbs;
     963                 :            : }
     964                 :            : 
     965                 :            : /* Returns the list of basic blocks including BB dominated by BB, in the
     966                 :            :    direction DIR.  The vector will be sorted in preorder.  */
     967                 :            : 
     968                 :            : vec<basic_block> 
     969                 :    5923070 : get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
     970                 :            : {
     971                 :    5923070 :   return get_dominated_to_depth (dir, bb, 0);
     972                 :            : }
     973                 :            : 
     974                 :            : /* Redirect all edges pointing to BB to TO.  */
     975                 :            : void
     976                 :    9491670 : redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
     977                 :            :                                basic_block to)
     978                 :            : {
     979                 :    9491670 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
     980                 :    9491670 :   struct et_node *bb_node, *to_node, *son;
     981                 :            : 
     982                 :    9491670 :   bb_node = bb->dom[dir_index];
     983                 :    9491670 :   to_node = to->dom[dir_index];
     984                 :            : 
     985                 :    9491670 :   gcc_checking_assert (dom_computed[dir_index]);
     986                 :            : 
     987                 :    9491670 :   if (!bb_node->son)
     988                 :            :     return;
     989                 :            : 
     990                 :   16399700 :   while (bb_node->son)
     991                 :            :     {
     992                 :    9551530 :       son = bb_node->son;
     993                 :            : 
     994                 :    9551530 :       et_split (son);
     995                 :    9551530 :       et_set_father (son, to_node);
     996                 :            :     }
     997                 :            : 
     998                 :    6848120 :   if (dom_computed[dir_index] == DOM_OK)
     999                 :    1431450 :     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
    1000                 :            : }
    1001                 :            : 
    1002                 :            : /* Find first basic block in the tree dominating both BB1 and BB2.  */
    1003                 :            : basic_block
    1004                 :   62088000 : nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
    1005                 :            : {
    1006                 :   62088000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1007                 :            : 
    1008                 :   62088000 :   gcc_checking_assert (dom_computed[dir_index]);
    1009                 :            : 
    1010                 :   62088000 :   if (!bb1)
    1011                 :            :     return bb2;
    1012                 :   60833100 :   if (!bb2)
    1013                 :            :     return bb1;
    1014                 :            : 
    1015                 :   60833100 :   return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
    1016                 :            : }
    1017                 :            : 
    1018                 :            : 
    1019                 :            : /* Find the nearest common dominator for the basic blocks in BLOCKS,
    1020                 :            :    using dominance direction DIR.  */
    1021                 :            : 
    1022                 :            : basic_block
    1023                 :    6455520 : nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
    1024                 :            : {
    1025                 :    6455520 :   unsigned i, first;
    1026                 :    6455520 :   bitmap_iterator bi;
    1027                 :    6455520 :   basic_block dom;
    1028                 :            : 
    1029                 :    6455520 :   first = bitmap_first_set_bit (blocks);
    1030                 :    6455520 :   dom = BASIC_BLOCK_FOR_FN (cfun, first);
    1031                 :   41214700 :   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
    1032                 :   34759200 :     if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
    1033                 :   28148600 :       dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
    1034                 :            : 
    1035                 :    6455520 :   return dom;
    1036                 :            : }
    1037                 :            : 
    1038                 :            : /*  Given a dominator tree, we can determine whether one thing
    1039                 :            :     dominates another in constant time by using two DFS numbers:
    1040                 :            : 
    1041                 :            :     1. The number for when we visit a node on the way down the tree
    1042                 :            :     2. The number for when we visit a node on the way back up the tree
    1043                 :            : 
    1044                 :            :     You can view these as bounds for the range of dfs numbers the
    1045                 :            :     nodes in the subtree of the dominator tree rooted at that node
    1046                 :            :     will contain.
    1047                 :            : 
    1048                 :            :     The dominator tree is always a simple acyclic tree, so there are
    1049                 :            :     only three possible relations two nodes in the dominator tree have
    1050                 :            :     to each other:
    1051                 :            : 
    1052                 :            :     1. Node A is above Node B (and thus, Node A dominates node B)
    1053                 :            : 
    1054                 :            :      A
    1055                 :            :      |
    1056                 :            :      C
    1057                 :            :     / \
    1058                 :            :    B   D
    1059                 :            : 
    1060                 :            : 
    1061                 :            :    In the above case, DFS_Number_In of A will be <= DFS_Number_In of
    1062                 :            :    B, and DFS_Number_Out of A will be >= DFS_Number_Out of B.  This is
    1063                 :            :    because we must hit A in the dominator tree *before* B on the walk
    1064                 :            :    down, and we will hit A *after* B on the walk back up
    1065                 :            : 
    1066                 :            :    2. Node A is below node B (and thus, node B dominates node A)
    1067                 :            : 
    1068                 :            : 
    1069                 :            :      B
    1070                 :            :      |
    1071                 :            :      A
    1072                 :            :     / \
    1073                 :            :    C   D
    1074                 :            : 
    1075                 :            :    In the above case, DFS_Number_In of A will be >= DFS_Number_In of
    1076                 :            :    B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
    1077                 :            : 
    1078                 :            :    This is because we must hit A in the dominator tree *after* B on
    1079                 :            :    the walk down, and we will hit A *before* B on the walk back up
    1080                 :            : 
    1081                 :            :    3. Node A and B are siblings (and thus, neither dominates the other)
    1082                 :            : 
    1083                 :            :      C
    1084                 :            :      |
    1085                 :            :      D
    1086                 :            :     / \
    1087                 :            :    A   B
    1088                 :            : 
    1089                 :            :    In the above case, DFS_Number_In of A will *always* be <=
    1090                 :            :    DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
    1091                 :            :    DFS_Number_Out of B.  This is because we will always finish the dfs
    1092                 :            :    walk of one of the subtrees before the other, and thus, the dfs
    1093                 :            :    numbers for one subtree can't intersect with the range of dfs
    1094                 :            :    numbers for the other subtree.  If you swap A and B's position in
    1095                 :            :    the dominator tree, the comparison changes direction, but the point
    1096                 :            :    is that both comparisons will always go the same way if there is no
    1097                 :            :    dominance relationship.
    1098                 :            : 
    1099                 :            :    Thus, it is sufficient to write
    1100                 :            : 
    1101                 :            :    A_Dominates_B (node A, node B)
    1102                 :            :    {
    1103                 :            :      return DFS_Number_In(A) <= DFS_Number_In(B)
    1104                 :            :             && DFS_Number_Out (A) >= DFS_Number_Out(B);
    1105                 :            :    }
    1106                 :            : 
    1107                 :            :    A_Dominated_by_B (node A, node B)
    1108                 :            :    {
    1109                 :            :      return DFS_Number_In(A) >= DFS_Number_In(B)
    1110                 :            :             && DFS_Number_Out (A) <= DFS_Number_Out(B);
    1111                 :            :    }  */
    1112                 :            : 
    1113                 :            : /* Return TRUE in case BB1 is dominated by BB2.  */
    1114                 :            : bool
    1115                 : 9829950000 : dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block bb2)
    1116                 :            : {
    1117                 : 9829950000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1118                 : 9829950000 :   struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
    1119                 :            : 
    1120                 : 9829950000 :   gcc_checking_assert (dom_computed[dir_index]);
    1121                 :            : 
    1122                 : 9829950000 :   if (dom_computed[dir_index] == DOM_OK)
    1123                 : 9507210000 :     return (n1->dfs_num_in >= n2->dfs_num_in
    1124                 :16446400000 :             && n1->dfs_num_out <= n2->dfs_num_out);
    1125                 :            : 
    1126                 :  322744000 :   return et_below (n1, n2);
    1127                 :            : }
    1128                 :            : 
    1129                 :            : /* Returns the entry dfs number for basic block BB, in the direction DIR.  */
    1130                 :            : 
    1131                 :            : unsigned
    1132                 :   47335600 : bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
    1133                 :            : {
    1134                 :   47335600 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1135                 :   47335600 :   struct et_node *n = bb->dom[dir_index];
    1136                 :            : 
    1137                 :   47335600 :   gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
    1138                 :   47335600 :   return n->dfs_num_in;
    1139                 :            : }
    1140                 :            : 
    1141                 :            : /* Returns the exit dfs number for basic block BB, in the direction DIR.  */
    1142                 :            : 
    1143                 :            : unsigned
    1144                 :   27230200 : bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
    1145                 :            : {
    1146                 :   27230200 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1147                 :   27230200 :   struct et_node *n = bb->dom[dir_index];
    1148                 :            : 
    1149                 :   27230200 :   gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
    1150                 :   27230200 :   return n->dfs_num_out;
    1151                 :            : }
    1152                 :            : 
    1153                 :            : /* Verify invariants of dominator structure.  */
    1154                 :            : DEBUG_FUNCTION void
    1155                 :  455357000 : verify_dominators (cdi_direction dir)
    1156                 :            : {
    1157                 :  455357000 :   gcc_assert (dom_info_available_p (dir));
    1158                 :            : 
    1159                 :  910714000 :   dom_info di (cfun, dir);
    1160                 :  455357000 :   di.calc_dfs_tree ();
    1161                 :  455357000 :   di.calc_idoms ();
    1162                 :            : 
    1163                 :  455357000 :   bool err = false;
    1164                 :  455357000 :   basic_block bb;
    1165                 : 4638590000 :   FOR_EACH_BB_FN (bb, cfun)
    1166                 :            :     {
    1167                 : 4183230000 :       basic_block imm_bb = get_immediate_dominator (dir, bb);
    1168                 : 4183230000 :       if (!imm_bb)
    1169                 :            :         {
    1170                 :          0 :           error ("dominator of %d status unknown", bb->index);
    1171                 :          0 :           err = true;
    1172                 :          0 :           continue;
    1173                 :            :         }
    1174                 :            : 
    1175                 : 4183230000 :       basic_block imm_bb_correct = di.get_idom (bb);
    1176                 : 4183230000 :       if (imm_bb != imm_bb_correct)
    1177                 :            :         {
    1178                 :          0 :           error ("dominator of %d should be %d, not %d",
    1179                 :            :                  bb->index, imm_bb_correct->index, imm_bb->index);
    1180                 :          0 :           err = true;
    1181                 :            :         }
    1182                 :            :     }
    1183                 :            : 
    1184                 :  455357000 :   gcc_assert (!err);
    1185                 :  455357000 : }
    1186                 :            : 
    1187                 :            : /* Determine immediate dominator (or postdominator, according to DIR) of BB,
    1188                 :            :    assuming that dominators of other blocks are correct.  We also use it to
    1189                 :            :    recompute the dominators in a restricted area, by iterating it until it
    1190                 :            :    reaches a fixed point.  */
    1191                 :            : 
    1192                 :            : basic_block
    1193                 :     436265 : recompute_dominator (enum cdi_direction dir, basic_block bb)
    1194                 :            : {
    1195                 :     436265 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1196                 :     436265 :   basic_block dom_bb = NULL;
    1197                 :     436265 :   edge e;
    1198                 :     436265 :   edge_iterator ei;
    1199                 :            : 
    1200                 :     436265 :   gcc_checking_assert (dom_computed[dir_index]);
    1201                 :            : 
    1202                 :     436265 :   if (dir == CDI_DOMINATORS)
    1203                 :            :     {
    1204                 :    2329990 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1205                 :            :         {
    1206                 :    1893730 :           if (!dominated_by_p (dir, e->src, bb))
    1207                 :    1716580 :             dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
    1208                 :            :         }
    1209                 :            :     }
    1210                 :            :   else
    1211                 :            :     {
    1212                 :          0 :       FOR_EACH_EDGE (e, ei, bb->succs)
    1213                 :            :         {
    1214                 :          0 :           if (!dominated_by_p (dir, e->dest, bb))
    1215                 :          0 :             dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
    1216                 :            :         }
    1217                 :            :     }
    1218                 :            : 
    1219                 :     436265 :   return dom_bb;
    1220                 :            : }
    1221                 :            : 
    1222                 :            : /* Use simple heuristics (see iterate_fix_dominators) to determine dominators
    1223                 :            :    of BBS.  We assume that all the immediate dominators except for those of the
    1224                 :            :    blocks in BBS are correct.  If CONSERVATIVE is true, we also assume that the
    1225                 :            :    currently recorded immediate dominators of blocks in BBS really dominate the
    1226                 :            :    blocks.  The basic blocks for that we determine the dominator are removed
    1227                 :            :    from BBS.  */
    1228                 :            : 
    1229                 :            : static void
    1230                 :     727920 : prune_bbs_to_update_dominators (vec<basic_block> bbs,
    1231                 :            :                                 bool conservative)
    1232                 :            : {
    1233                 :     727920 :   unsigned i;
    1234                 :     727920 :   bool single;
    1235                 :     727920 :   basic_block bb, dom = NULL;
    1236                 :     727920 :   edge_iterator ei;
    1237                 :     727920 :   edge e;
    1238                 :            : 
    1239                 :     727920 :   for (i = 0; bbs.iterate (i, &bb);)
    1240                 :            :     {
    1241                 :    1672080 :       if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1242                 :          0 :         goto succeed;
    1243                 :            : 
    1244                 :    1672080 :       if (single_pred_p (bb))
    1245                 :            :         {
    1246                 :     612339 :           set_immediate_dominator (CDI_DOMINATORS, bb, single_pred (bb));
    1247                 :     612339 :           goto succeed;
    1248                 :            :         }
    1249                 :            : 
    1250                 :    1059740 :       if (!conservative)
    1251                 :     630320 :         goto fail;
    1252                 :            : 
    1253                 :     429423 :       single = true;
    1254                 :     429423 :       dom = NULL;
    1255                 :    9296110 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1256                 :            :         {
    1257                 :    8866690 :           if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
    1258                 :      12791 :             continue;
    1259                 :            : 
    1260                 :    8853900 :           if (!dom)
    1261                 :     429423 :             dom = e->src;
    1262                 :            :           else
    1263                 :            :             {
    1264                 :    8424470 :               single = false;
    1265                 :    8424470 :               dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
    1266                 :            :             }
    1267                 :            :         }
    1268                 :            : 
    1269                 :     429423 :       gcc_assert (dom != NULL);
    1270                 :     429423 :       if (single
    1271                 :     429423 :           || find_edge (dom, bb))
    1272                 :            :         {
    1273                 :     296331 :           set_immediate_dominator (CDI_DOMINATORS, bb, dom);
    1274                 :     296331 :           goto succeed;
    1275                 :            :         }
    1276                 :            : 
    1277                 :     763412 : fail:
    1278                 :     763412 :       i++;
    1279                 :     763412 :       continue;
    1280                 :            : 
    1281                 :     908670 : succeed:
    1282                 :    3308670 :       bbs.unordered_remove (i);
    1283                 :            :     }
    1284                 :     727920 : }
    1285                 :            : 
    1286                 :            : /* Returns root of the dominance tree in the direction DIR that contains
    1287                 :            :    BB.  */
    1288                 :            : 
    1289                 :            : static basic_block
    1290                 :    3889010 : root_of_dom_tree (enum cdi_direction dir, basic_block bb)
    1291                 :            : {
    1292                 :    3889010 :   return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
    1293                 :            : }
    1294                 :            : 
    1295                 :            : /* See the comment in iterate_fix_dominators.  Finds the immediate dominators
    1296                 :            :    for the sons of Y, found using the SON and BROTHER arrays representing
    1297                 :            :    the dominance tree of graph G.  BBS maps the vertices of G to the basic
    1298                 :            :    blocks.  */
    1299                 :            : 
    1300                 :            : static void
    1301                 :     960729 : determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
    1302                 :            :                                int y, int *son, int *brother)
    1303                 :            : {
    1304                 :     960729 :   bitmap gprime;
    1305                 :     960729 :   int i, a, nc;
    1306                 :     960729 :   vec<int> *sccs;
    1307                 :     960729 :   basic_block bb, dom, ybb;
    1308                 :     960729 :   unsigned si;
    1309                 :     960729 :   edge e;
    1310                 :     960729 :   edge_iterator ei;
    1311                 :            : 
    1312                 :     960729 :   if (son[y] == -1)
    1313                 :     777739 :     return;
    1314                 :     873410 :   if (y == (int) bbs.length ())
    1315                 :     309827 :     ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
    1316                 :            :   else
    1317                 :     126878 :     ybb = bbs[y];
    1318                 :            : 
    1319                 :     436705 :   if (brother[son[y]] == -1)
    1320                 :            :     {
    1321                 :            :       /* Handle the common case Y has just one son specially.  */
    1322                 :     253715 :       bb = bbs[son[y]];
    1323                 :     253715 :       set_immediate_dominator (CDI_DOMINATORS, bb,
    1324                 :            :                                recompute_dominator (CDI_DOMINATORS, bb));
    1325                 :     253715 :       identify_vertices (g, y, son[y]);
    1326                 :     253715 :       return;
    1327                 :            :     }
    1328                 :            : 
    1329                 :     182990 :   gprime = BITMAP_ALLOC (NULL);
    1330                 :     580177 :   for (a = son[y]; a != -1; a = brother[a])
    1331                 :     397187 :     bitmap_set_bit (gprime, a);
    1332                 :            : 
    1333                 :     182990 :   nc = graphds_scc (g, gprime);
    1334                 :     182990 :   BITMAP_FREE (gprime);
    1335                 :            : 
    1336                 :            :   /* ???  Needed to work around the pre-processor confusion with
    1337                 :            :      using a multi-argument template type as macro argument.  */
    1338                 :     182990 :   typedef vec<int> vec_int_heap;
    1339                 :     182990 :   sccs = XCNEWVEC (vec_int_heap, nc);
    1340                 :     580177 :   for (a = son[y]; a != -1; a = brother[a])
    1341                 :     397187 :     sccs[g->vertices[a].component].safe_push (a);
    1342                 :            : 
    1343                 :     579248 :   for (i = nc - 1; i >= 0; i--)
    1344                 :            :     {
    1345                 :            :       dom = NULL;
    1346                 :    1189700 :       FOR_EACH_VEC_ELT (sccs[i], si, a)
    1347                 :            :         {
    1348                 :     397187 :           bb = bbs[a];
    1349                 :    2056500 :           FOR_EACH_EDGE (e, ei, bb->preds)
    1350                 :            :             {
    1351                 :    1659320 :               if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
    1352                 :     169119 :                 continue;
    1353                 :            : 
    1354                 :    1490200 :               dom = nearest_common_dominator (CDI_DOMINATORS, dom, e->src);
    1355                 :            :             }
    1356                 :            :         }
    1357                 :            : 
    1358                 :     396258 :       gcc_assert (dom != NULL);
    1359                 :    1189700 :       FOR_EACH_VEC_ELT (sccs[i], si, a)
    1360                 :            :         {
    1361                 :     397187 :           bb = bbs[a];
    1362                 :     397187 :           set_immediate_dominator (CDI_DOMINATORS, bb, dom);
    1363                 :            :         }
    1364                 :            :     }
    1365                 :            : 
    1366                 :     579248 :   for (i = 0; i < nc; i++)
    1367                 :     792516 :     sccs[i].release ();
    1368                 :     182990 :   free (sccs);
    1369                 :            : 
    1370                 :     580177 :   for (a = son[y]; a != -1; a = brother[a])
    1371                 :     397187 :     identify_vertices (g, y, a);
    1372                 :            : }
    1373                 :            : 
    1374                 :            : /* Recompute dominance information for basic blocks in the set BBS.  The
    1375                 :            :    function assumes that the immediate dominators of all the other blocks
    1376                 :            :    in CFG are correct, and that there are no unreachable blocks.
    1377                 :            : 
    1378                 :            :    If CONSERVATIVE is true, we additionally assume that all the ancestors of
    1379                 :            :    a block of BBS in the current dominance tree dominate it.  */
    1380                 :            : 
    1381                 :            : void
    1382                 :     727920 : iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
    1383                 :            :                         bool conservative)
    1384                 :            : {
    1385                 :     727920 :   unsigned i;
    1386                 :     727920 :   basic_block bb, dom;
    1387                 :     727920 :   struct graph *g;
    1388                 :     727920 :   int n, y;
    1389                 :     727920 :   size_t dom_i;
    1390                 :     727920 :   edge e;
    1391                 :     727920 :   edge_iterator ei;
    1392                 :     727920 :   int *parent, *son, *brother;
    1393                 :     727920 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1394                 :            : 
    1395                 :            :   /* We only support updating dominators.  There are some problems with
    1396                 :            :      updating postdominators (need to add fake edges from infinite loops
    1397                 :            :      and noreturn functions), and since we do not currently use
    1398                 :            :      iterate_fix_dominators for postdominators, any attempt to handle these
    1399                 :            :      problems would be unused, untested, and almost surely buggy.  We keep
    1400                 :            :      the DIR argument for consistency with the rest of the dominator analysis
    1401                 :            :      interface.  */
    1402                 :     727920 :   gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
    1403                 :            : 
    1404                 :            :   /* The algorithm we use takes inspiration from the following papers, although
    1405                 :            :      the details are quite different from any of them:
    1406                 :            : 
    1407                 :            :      [1] G. Ramalingam, T. Reps, An Incremental Algorithm for Maintaining the
    1408                 :            :          Dominator Tree of a Reducible Flowgraph
    1409                 :            :      [2]  V. C. Sreedhar, G. R. Gao, Y.-F. Lee: Incremental computation of
    1410                 :            :           dominator trees
    1411                 :            :      [3]  K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance
    1412                 :            :           Algorithm
    1413                 :            : 
    1414                 :            :      First, we use the following heuristics to decrease the size of the BBS
    1415                 :            :      set:
    1416                 :            :        a) if BB has a single predecessor, then its immediate dominator is this
    1417                 :            :           predecessor
    1418                 :            :        additionally, if CONSERVATIVE is true:
    1419                 :            :        b) if all the predecessors of BB except for one (X) are dominated by BB,
    1420                 :            :           then X is the immediate dominator of BB
    1421                 :            :        c) if the nearest common ancestor of the predecessors of BB is X and
    1422                 :            :           X -> BB is an edge in CFG, then X is the immediate dominator of BB
    1423                 :            : 
    1424                 :            :      Then, we need to establish the dominance relation among the basic blocks
    1425                 :            :      in BBS.  We split the dominance tree by removing the immediate dominator
    1426                 :            :      edges from BBS, creating a forest F.  We form a graph G whose vertices
    1427                 :            :      are BBS and ENTRY and X -> Y is an edge of G if there exists an edge
    1428                 :            :      X' -> Y in CFG such that X' belongs to the tree of the dominance forest
    1429                 :            :      whose root is X.  We then determine dominance tree of G.  Note that
    1430                 :            :      for X, Y in BBS, X dominates Y in CFG if and only if X dominates Y in G.
    1431                 :            :      In this step, we can use arbitrary algorithm to determine dominators.
    1432                 :            :      We decided to prefer the algorithm [3] to the algorithm of
    1433                 :            :      Lengauer and Tarjan, since the set BBS is usually small (rarely exceeding
    1434                 :            :      10 during gcc bootstrap), and [3] should perform better in this case.
    1435                 :            : 
    1436                 :            :      Finally, we need to determine the immediate dominators for the basic
    1437                 :            :      blocks of BBS.  If the immediate dominator of X in G is Y, then
    1438                 :            :      the immediate dominator of X in CFG belongs to the tree of F rooted in
    1439                 :            :      Y.  We process the dominator tree T of G recursively, starting from leaves.
    1440                 :            :      Suppose that X_1, X_2, ..., X_k are the sons of Y in T, and that the
    1441                 :            :      subtrees of the dominance tree of CFG rooted in X_i are already correct.
    1442                 :            :      Let G' be the subgraph of G induced by {X_1, X_2, ..., X_k}.  We make
    1443                 :            :      the following observations:
    1444                 :            :        (i) the immediate dominator of all blocks in a strongly connected
    1445                 :            :            component of G' is the same
    1446                 :            :        (ii) if X has no predecessors in G', then the immediate dominator of X
    1447                 :            :             is the nearest common ancestor of the predecessors of X in the
    1448                 :            :             subtree of F rooted in Y
    1449                 :            :      Therefore, it suffices to find the topological ordering of G', and
    1450                 :            :      process the nodes X_i in this order using the rules (i) and (ii).
    1451                 :            :      Then, we contract all the nodes X_i with Y in G, so that the further
    1452                 :            :      steps work correctly.  */
    1453                 :            : 
    1454                 :     727920 :   if (!conservative)
    1455                 :            :     {
    1456                 :            :       /* Split the tree now.  If the idoms of blocks in BBS are not
    1457                 :            :          conservatively correct, setting the dominators using the
    1458                 :            :          heuristics in prune_bbs_to_update_dominators could
    1459                 :            :          create cycles in the dominance "tree", and cause ICE.  */
    1460                 :    1458910 :       FOR_EACH_VEC_ELT (bbs, i, bb)
    1461                 :     811677 :         set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
    1462                 :            :     }
    1463                 :            : 
    1464                 :     727920 :   prune_bbs_to_update_dominators (bbs, conservative);
    1465                 :     727920 :   n = bbs.length ();
    1466                 :            : 
    1467                 :     727920 :   if (n == 0)
    1468                 :     418093 :     return;
    1469                 :            : 
    1470                 :     422337 :   if (n == 1)
    1471                 :            :     {
    1472                 :     112510 :       bb = bbs[0];
    1473                 :     112510 :       set_immediate_dominator (CDI_DOMINATORS, bb,
    1474                 :            :                                recompute_dominator (CDI_DOMINATORS, bb));
    1475                 :     112510 :       return;
    1476                 :            :     }
    1477                 :            : 
    1478                 :     309827 :   timevar_push (TV_DOMINANCE);
    1479                 :            : 
    1480                 :            :   /* Construct the graph G.  */
    1481                 :     619654 :   hash_map<basic_block, int> map (251);
    1482                 :    1270560 :   FOR_EACH_VEC_ELT (bbs, i, bb)
    1483                 :            :     {
    1484                 :            :       /* If the dominance tree is conservatively correct, split it now.  */
    1485                 :     650902 :       if (conservative)
    1486                 :      53442 :         set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
    1487                 :     650902 :       map.put (bb, i);
    1488                 :            :     }
    1489                 :     309827 :   map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
    1490                 :            : 
    1491                 :     309827 :   g = new_graph (n + 1);
    1492                 :    1270560 :   for (y = 0; y < g->n_vertices; y++)
    1493                 :     960729 :     g->vertices[y].data = BITMAP_ALLOC (NULL);
    1494                 :    1270560 :   FOR_EACH_VEC_ELT (bbs, i, bb)
    1495                 :            :     {
    1496                 :    2880600 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1497                 :            :         {
    1498                 :    2229690 :           dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
    1499                 :    2229690 :           if (dom == bb)
    1500                 :     234889 :             continue;
    1501                 :            : 
    1502                 :    1994800 :           dom_i = *map.get (dom);
    1503                 :            : 
    1504                 :            :           /* Do not include parallel edges to G.  */
    1505                 :    1994800 :           if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
    1506                 :    1067640 :             continue;
    1507                 :            : 
    1508                 :     927168 :           add_edge (g, dom_i, i);
    1509                 :            :         }
    1510                 :            :     }
    1511                 :    1270560 :   for (y = 0; y < g->n_vertices; y++)
    1512                 :     960729 :     BITMAP_FREE (g->vertices[y].data);
    1513                 :            : 
    1514                 :            :   /* Find the dominator tree of G.  */
    1515                 :     309827 :   son = XNEWVEC (int, n + 1);
    1516                 :     309827 :   brother = XNEWVEC (int, n + 1);
    1517                 :     309827 :   parent = XNEWVEC (int, n + 1);
    1518                 :     309827 :   graphds_domtree (g, n, parent, son, brother);
    1519                 :            : 
    1520                 :            :   /* Finally, traverse the tree and find the immediate dominators.  */
    1521                 :     746516 :   for (y = n; son[y] != -1; y = son[y])
    1522                 :     436689 :     continue;
    1523                 :    1270560 :   while (y != -1)
    1524                 :            :     {
    1525                 :     960729 :       determine_dominators_for_sons (g, bbs, y, son, brother);
    1526                 :            : 
    1527                 :     960729 :       if (brother[y] != -1)
    1528                 :            :         {
    1529                 :            :           y = brother[y];
    1530                 :     214213 :           while (son[y] != -1)
    1531                 :            :             y = son[y];
    1532                 :            :         }
    1533                 :            :       else
    1534                 :     746532 :         y = parent[y];
    1535                 :            :     }
    1536                 :            : 
    1537                 :     309827 :   free (son);
    1538                 :     309827 :   free (brother);
    1539                 :     309827 :   free (parent);
    1540                 :            : 
    1541                 :     309827 :   free_graph (g);
    1542                 :            : 
    1543                 :     310127 :   timevar_pop (TV_DOMINANCE);
    1544                 :            : }
    1545                 :            : 
    1546                 :            : void
    1547                 :   15879900 : add_to_dominance_info (enum cdi_direction dir, basic_block bb)
    1548                 :            : {
    1549                 :   15879900 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1550                 :            : 
    1551                 :   15879900 :   gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
    1552                 :            : 
    1553                 :   15879900 :   n_bbs_in_dom_tree[dir_index]++;
    1554                 :            : 
    1555                 :   15879900 :   bb->dom[dir_index] = et_new_tree (bb);
    1556                 :            : 
    1557                 :   15879900 :   if (dom_computed[dir_index] == DOM_OK)
    1558                 :    2634000 :     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
    1559                 :   15879900 : }
    1560                 :            : 
    1561                 :            : void
    1562                 :   25331400 : delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
    1563                 :            : {
    1564                 :   25331400 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1565                 :            : 
    1566                 :   25331400 :   gcc_checking_assert (dom_computed[dir_index]);
    1567                 :            : 
    1568                 :   25331400 :   et_free_tree (bb->dom[dir_index]);
    1569                 :   25331400 :   bb->dom[dir_index] = NULL;
    1570                 :   25331400 :   n_bbs_in_dom_tree[dir_index]--;
    1571                 :            : 
    1572                 :   25331400 :   if (dom_computed[dir_index] == DOM_OK)
    1573                 :    2596160 :     dom_computed[dir_index] = DOM_NO_FAST_QUERY;
    1574                 :   25331400 : }
    1575                 :            : 
    1576                 :            : /* Returns the first son of BB in the dominator or postdominator tree
    1577                 :            :    as determined by DIR.  */
    1578                 :            : 
    1579                 :            : basic_block
    1580                 :  495630000 : first_dom_son (enum cdi_direction dir, basic_block bb)
    1581                 :            : {
    1582                 :  495630000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1583                 :  495630000 :   struct et_node *son = bb->dom[dir_index]->son;
    1584                 :            : 
    1585                 :  495630000 :   return (basic_block) (son ? son->data : NULL);
    1586                 :            : }
    1587                 :            : 
    1588                 :            : /* Returns the next dominance son after BB in the dominator or postdominator
    1589                 :            :    tree as determined by DIR, or NULL if it was the last one.  */
    1590                 :            : 
    1591                 :            : basic_block
    1592                 :  444036000 : next_dom_son (enum cdi_direction dir, basic_block bb)
    1593                 :            : {
    1594                 :  444036000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1595                 :  444036000 :   struct et_node *next = bb->dom[dir_index]->right;
    1596                 :            : 
    1597                 :  444036000 :   return (basic_block) (next->father->son == next ? NULL : next->data);
    1598                 :            : }
    1599                 :            : 
    1600                 :            : /* Return dominance availability for dominance info DIR.  */
    1601                 :            : 
    1602                 :            : enum dom_state
    1603                 : 3617040000 : dom_info_state (function *fn, enum cdi_direction dir)
    1604                 :            : {
    1605                 : 3617040000 :   if (!fn->cfg)
    1606                 :            :     return DOM_NONE;
    1607                 :            : 
    1608                 : 3518570000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1609                 : 3518570000 :   return fn->cfg->x_dom_computed[dir_index];
    1610                 :            : }
    1611                 :            : 
    1612                 :            : enum dom_state
    1613                 :  300010000 : dom_info_state (enum cdi_direction dir)
    1614                 :            : {
    1615                 :  300010000 :   return dom_info_state (cfun, dir);
    1616                 :            : }
    1617                 :            : 
    1618                 :            : /* Set the dominance availability for dominance info DIR to NEW_STATE.  */
    1619                 :            : 
    1620                 :            : void
    1621                 :  120700000 : set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
    1622                 :            : {
    1623                 :  120700000 :   unsigned int dir_index = dom_convert_dir_to_idx (dir);
    1624                 :            : 
    1625                 :  120700000 :   dom_computed[dir_index] = new_state;
    1626                 :  120700000 : }
    1627                 :            : 
    1628                 :            : /* Returns true if dominance information for direction DIR is available.  */
    1629                 :            : 
    1630                 :            : bool
    1631                 : 1478220000 : dom_info_available_p (function *fn, enum cdi_direction dir)
    1632                 :            : {
    1633                 : 1478220000 :   return dom_info_state (fn, dir) != DOM_NONE;
    1634                 :            : }
    1635                 :            : 
    1636                 :            : bool
    1637                 : 1228630000 : dom_info_available_p (enum cdi_direction dir)
    1638                 :            : {
    1639                 : 1228630000 :   return dom_info_available_p (cfun, dir);
    1640                 :            : }
    1641                 :            : 
    1642                 :            : DEBUG_FUNCTION void
    1643                 :          0 : debug_dominance_info (enum cdi_direction dir)
    1644                 :            : {
    1645                 :          0 :   basic_block bb, bb2;
    1646                 :          0 :   FOR_EACH_BB_FN (bb, cfun)
    1647                 :          0 :     if ((bb2 = get_immediate_dominator (dir, bb)))
    1648                 :          0 :       fprintf (stderr, "%i %i\n", bb->index, bb2->index);
    1649                 :          0 : }
    1650                 :            : 
    1651                 :            : /* Prints to stderr representation of the dominance tree (for direction DIR)
    1652                 :            :    rooted in ROOT, indented by INDENT tabulators.  If INDENT_FIRST is false,
    1653                 :            :    the first line of the output is not indented.  */
    1654                 :            : 
    1655                 :            : static void
    1656                 :          0 : debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
    1657                 :            :                         unsigned indent, bool indent_first)
    1658                 :            : {
    1659                 :          0 :   basic_block son;
    1660                 :          0 :   unsigned i;
    1661                 :          0 :   bool first = true;
    1662                 :            : 
    1663                 :          0 :   if (indent_first)
    1664                 :          0 :     for (i = 0; i < indent; i++)
    1665                 :          0 :       fprintf (stderr, "\t");
    1666                 :          0 :   fprintf (stderr, "%d\t", root->index);
    1667                 :            : 
    1668                 :          0 :   for (son = first_dom_son (dir, root);
    1669                 :          0 :        son;
    1670                 :          0 :        son = next_dom_son (dir, son))
    1671                 :            :     {
    1672                 :          0 :       debug_dominance_tree_1 (dir, son, indent + 1, !first);
    1673                 :          0 :       first = false;
    1674                 :            :     }
    1675                 :            : 
    1676                 :          0 :   if (first)
    1677                 :          0 :     fprintf (stderr, "\n");
    1678                 :          0 : }
    1679                 :            : 
    1680                 :            : /* Prints to stderr representation of the dominance tree (for direction DIR)
    1681                 :            :    rooted in ROOT.  */
    1682                 :            : 
    1683                 :            : DEBUG_FUNCTION void
    1684                 :          0 : debug_dominance_tree (enum cdi_direction dir, basic_block root)
    1685                 :            : {
    1686                 :          0 :   debug_dominance_tree_1 (dir, root, 0, false);
    1687                 :          0 : }

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.