LCOV - code coverage report
Current view: top level - gcc - domwalk.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 115 117 98.3 %
Date: 2020-03-28 11:57:23 Functions: 8 8 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Generic dominator tree walker
       2                 :            :    Copyright (C) 2003-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Diego Novillo <dnovillo@redhat.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it 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,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public 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                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "cfganal.h"
      26                 :            : #include "domwalk.h"
      27                 :            : #include "dumpfile.h"
      28                 :            : 
      29                 :            : /* This file implements a generic walker for dominator trees.
      30                 :            : 
      31                 :            :   To understand the dominator walker one must first have a grasp of dominators,
      32                 :            :   immediate dominators and the dominator tree.
      33                 :            : 
      34                 :            :   Dominators
      35                 :            :     A block B1 is said to dominate B2 if every path from the entry to B2 must
      36                 :            :     pass through B1.  Given the dominance relationship, we can proceed to
      37                 :            :     compute immediate dominators.  Note it is not important whether or not
      38                 :            :     our definition allows a block to dominate itself.
      39                 :            : 
      40                 :            :   Immediate Dominators:
      41                 :            :     Every block in the CFG has no more than one immediate dominator.  The
      42                 :            :     immediate dominator of block BB must dominate BB and must not dominate
      43                 :            :     any other dominator of BB and must not be BB itself.
      44                 :            : 
      45                 :            :   Dominator tree:
      46                 :            :     If we then construct a tree where each node is a basic block and there
      47                 :            :     is an edge from each block's immediate dominator to the block itself, then
      48                 :            :     we have a dominator tree.
      49                 :            : 
      50                 :            : 
      51                 :            :   [ Note this walker can also walk the post-dominator tree, which is
      52                 :            :     defined in a similar manner.  i.e., block B1 is said to post-dominate
      53                 :            :     block B2 if all paths from B2 to the exit block must pass through
      54                 :            :     B1.  ]
      55                 :            : 
      56                 :            :   For example, given the CFG
      57                 :            : 
      58                 :            :                    1
      59                 :            :                    |
      60                 :            :                    2
      61                 :            :                   / \
      62                 :            :                  3   4
      63                 :            :                     / \
      64                 :            :        +---------->5   6
      65                 :            :        |          / \ /
      66                 :            :        |    +--->8   7
      67                 :            :        |    |   /    |
      68                 :            :        |    +--9    11
      69                 :            :        |      /      |
      70                 :            :        +--- 10 ---> 12
      71                 :            : 
      72                 :            : 
      73                 :            :   We have a dominator tree which looks like
      74                 :            : 
      75                 :            :                    1
      76                 :            :                    |
      77                 :            :                    2
      78                 :            :                   / \
      79                 :            :                  /   \
      80                 :            :                 3     4
      81                 :            :                    / / \ \
      82                 :            :                    | | | |
      83                 :            :                    5 6 7 12
      84                 :            :                    |   |
      85                 :            :                    8   11
      86                 :            :                    |
      87                 :            :                    9
      88                 :            :                    |
      89                 :            :                   10
      90                 :            : 
      91                 :            : 
      92                 :            : 
      93                 :            :   The dominator tree is the basis for a number of analysis, transformation
      94                 :            :   and optimization algorithms that operate on a semi-global basis.
      95                 :            : 
      96                 :            :   The dominator walker is a generic routine which visits blocks in the CFG
      97                 :            :   via a depth first search of the dominator tree.  In the example above
      98                 :            :   the dominator walker might visit blocks in the following order
      99                 :            :   1, 2, 3, 4, 5, 8, 9, 10, 6, 7, 11, 12.
     100                 :            : 
     101                 :            :   The dominator walker has a number of callbacks to perform actions
     102                 :            :   during the walk of the dominator tree.  There are two callbacks
     103                 :            :   which walk statements, one before visiting the dominator children,
     104                 :            :   one after visiting the dominator children.  There is a callback
     105                 :            :   before and after each statement walk callback.  In addition, the
     106                 :            :   dominator walker manages allocation/deallocation of data structures
     107                 :            :   which are local to each block visited.
     108                 :            : 
     109                 :            :   The dominator walker is meant to provide a generic means to build a pass
     110                 :            :   which can analyze or transform/optimize a function based on walking
     111                 :            :   the dominator tree.  One simply fills in the dominator walker data
     112                 :            :   structure with the appropriate callbacks and calls the walker.
     113                 :            : 
     114                 :            :   We currently use the dominator walker to prune the set of variables
     115                 :            :   which might need PHI nodes (which can greatly improve compile-time
     116                 :            :   performance in some cases).
     117                 :            : 
     118                 :            :   We also use the dominator walker to rewrite the function into SSA form
     119                 :            :   which reduces code duplication since the rewriting phase is inherently
     120                 :            :   a walk of the dominator tree.
     121                 :            : 
     122                 :            :   And (of course), we use the dominator walker to drive our dominator
     123                 :            :   optimizer, which is a semi-global optimizer.
     124                 :            : 
     125                 :            :   TODO:
     126                 :            : 
     127                 :            :     Walking statements is based on the block statement iterator abstraction,
     128                 :            :     which is currently an abstraction over walking tree statements.  Thus
     129                 :            :     the dominator walker is currently only useful for trees.  */
     130                 :            : 
     131                 :            : static int
     132                 :   97268500 : cmp_bb_postorder (const void *a, const void *b, void *data)
     133                 :            : {
     134                 :   97268500 :   basic_block bb1 = *(const basic_block *)(a);
     135                 :   97268500 :   basic_block bb2 = *(const basic_block *)(b);
     136                 :   97268500 :   int *bb_postorder = (int *)data;
     137                 :            :   /* Place higher completion number first (pop off lower number first).  */
     138                 :   97268500 :   return bb_postorder[bb2->index] - bb_postorder[bb1->index];
     139                 :            : }
     140                 :            : 
     141                 :            : /* Permute array BBS of N basic blocks in postorder,
     142                 :            :    i.e. by descending number in BB_POSTORDER array.  */
     143                 :            : 
     144                 :            : static void
     145                 :   83437000 : sort_bbs_postorder (basic_block *bbs, int n, int *bb_postorder)
     146                 :            : {
     147                 :   83437000 :   if (__builtin_expect (n == 2, true))
     148                 :            :     {
     149                 :   61906700 :       basic_block bb0 = bbs[0], bb1 = bbs[1];
     150                 :   61906700 :       if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
     151                 :   27838700 :         bbs[0] = bb1, bbs[1] = bb0;
     152                 :            :     }
     153                 :   21530300 :   else if (__builtin_expect (n == 3, true))
     154                 :            :     {
     155                 :   18935700 :       basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2];
     156                 :   18935700 :       if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
     157                 :    4060040 :         std::swap (bb0, bb1);
     158                 :   18935700 :       if (bb_postorder[bb1->index] < bb_postorder[bb2->index])
     159                 :            :         {
     160                 :   15191000 :           std::swap (bb1, bb2);
     161                 :   15191000 :           if (bb_postorder[bb0->index] < bb_postorder[bb1->index])
     162                 :    1585180 :             std::swap (bb0, bb1);
     163                 :            :         }
     164                 :   18935700 :       bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2;
     165                 :            :     }
     166                 :            :   else
     167                 :    2594590 :     gcc_sort_r (bbs, n, sizeof *bbs, cmp_bb_postorder, bb_postorder);
     168                 :   83437000 : }
     169                 :            : 
     170                 :            : /* Set EDGE_EXECUTABLE on every edge within FN's CFG.  */
     171                 :            : 
     172                 :            : void
     173                 :    2716790 : set_all_edges_as_executable (function *fn)
     174                 :            : {
     175                 :    2716790 :   basic_block bb;
     176                 :   36099900 :   FOR_ALL_BB_FN (bb, fn)
     177                 :            :     {
     178                 :   33383100 :       edge_iterator ei;
     179                 :   33383100 :       edge e;
     180                 :   75203800 :       FOR_EACH_EDGE (e, ei, bb->succs)
     181                 :   41820800 :         e->flags |= EDGE_EXECUTABLE;
     182                 :            :     }
     183                 :    2716790 : }
     184                 :            : 
     185                 :            : /* Constructor for a dom walker.  */
     186                 :            : 
     187                 :   33941600 : dom_walker::dom_walker (cdi_direction direction,
     188                 :            :                         enum reachability reachability,
     189                 :   33941600 :                         int *bb_index_to_rpo)
     190                 :   33941600 :   : m_dom_direction (direction),
     191                 :   33941600 :     m_reachability (reachability),
     192                 :   33941600 :     m_user_bb_to_rpo (bb_index_to_rpo != NULL),
     193                 :            :     m_unreachable_dom (NULL),
     194                 :   33941600 :     m_bb_to_rpo (bb_index_to_rpo)
     195                 :            : {
     196                 :   33941600 : }
     197                 :            : 
     198                 :            : /* Destructor.  */
     199                 :            : 
     200                 :   67883300 : dom_walker::~dom_walker ()
     201                 :            : {
     202                 :   33941600 :   if (! m_user_bb_to_rpo)
     203                 :   33941400 :     free (m_bb_to_rpo);
     204                 :   33941600 : }
     205                 :            : 
     206                 :            : /* Return TRUE if BB is reachable, false otherwise.  */
     207                 :            : 
     208                 :            : bool
     209                 :  665706000 : dom_walker::bb_reachable (struct function *fun, basic_block bb)
     210                 :            : {
     211                 :            :   /* If we're not skipping unreachable blocks, then assume everything
     212                 :            :      is reachable.  */
     213                 :  665706000 :   if (m_reachability == ALL_BLOCKS)
     214                 :            :     return true;
     215                 :            : 
     216                 :            :   /* If any of the predecessor edges that do not come from blocks dominated
     217                 :            :      by us are still marked as possibly executable consider this block
     218                 :            :      reachable.  */
     219                 :   61332600 :   bool reachable = false;
     220                 :   61332600 :   if (!m_unreachable_dom)
     221                 :            :     {
     222                 :   61305800 :       reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
     223                 :   61305800 :       edge_iterator ei;
     224                 :   61305800 :       edge e;
     225                 :  139617000 :       FOR_EACH_EDGE (e, ei, bb->preds)
     226                 :   78311100 :         if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
     227                 :   75412200 :           reachable |= (e->flags & EDGE_EXECUTABLE);
     228                 :            :     }
     229                 :            : 
     230                 :            :   return reachable;
     231                 :            : }
     232                 :            : 
     233                 :            : /* BB has been determined to be unreachable.  Propagate that property
     234                 :            :    to incoming and outgoing edges of BB as appropriate.  */
     235                 :            : 
     236                 :            : void
     237                 :      21777 : dom_walker::propagate_unreachable_to_edges (basic_block bb,
     238                 :            :                                             FILE *dump_file,
     239                 :            :                                             dump_flags_t dump_flags)
     240                 :            : {
     241                 :      21777 :   if (dump_file && (dump_flags & TDF_DETAILS))
     242                 :         13 :     fprintf (dump_file, "Marking all outgoing edges of unreachable "
     243                 :            :              "BB %d as not executable\n", bb->index);
     244                 :            : 
     245                 :      21777 :   edge_iterator ei;
     246                 :      21777 :   edge e;
     247                 :      35752 :   FOR_EACH_EDGE (e, ei, bb->succs)
     248                 :      13975 :     e->flags &= ~EDGE_EXECUTABLE;
     249                 :            : 
     250                 :      46613 :   FOR_EACH_EDGE (e, ei, bb->preds)
     251                 :            :     {
     252                 :      24836 :       if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
     253                 :            :         {
     254                 :        258 :           if (dump_file && (dump_flags & TDF_DETAILS))
     255                 :          0 :             fprintf (dump_file, "Marking backedge from BB %d into "
     256                 :            :                      "unreachable BB %d as not executable\n",
     257                 :          0 :                      e->src->index, bb->index);
     258                 :        258 :           e->flags &= ~EDGE_EXECUTABLE;
     259                 :            :         }
     260                 :            :     }
     261                 :            : 
     262                 :      21777 :   if (!m_unreachable_dom)
     263                 :      16844 :     m_unreachable_dom = bb;
     264                 :      21777 : }
     265                 :            : 
     266                 :            : const edge dom_walker::STOP = (edge)-1;
     267                 :            : 
     268                 :            : /* Recursively walk the dominator tree.
     269                 :            :    BB is the basic block we are currently visiting.  */
     270                 :            : 
     271                 :            : void
     272                 :   30184800 : dom_walker::walk (basic_block bb)
     273                 :            : {
     274                 :            :   /* Compute the basic-block index to RPO mapping lazily.  */
     275                 :   30184800 :   if (!m_bb_to_rpo
     276                 :   30184600 :       && m_dom_direction == CDI_DOMINATORS)
     277                 :            :     {
     278                 :   27246500 :       int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
     279                 :   27246500 :       int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
     280                 :            :                                                           true);
     281                 :   27246500 :       m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
     282                 :  371932000 :       for (int i = 0; i < postorder_num; ++i)
     283                 :  344686000 :         m_bb_to_rpo[postorder[i]] = i;
     284                 :   27246500 :       free (postorder);
     285                 :            :     }
     286                 :            : 
     287                 :            :   /* Set up edge flags if need be.  */
     288                 :   30184800 :   if (m_reachability == REACHABLE_BLOCKS)
     289                 :    2660100 :     set_all_edges_as_executable (cfun);
     290                 :            : 
     291                 :   30184800 :   basic_block dest;
     292                 :   30184800 :   basic_block *worklist = XNEWVEC (basic_block,
     293                 :            :                                    n_basic_blocks_for_fn (cfun) * 2);
     294                 :   30184800 :   int sp = 0;
     295                 :            : 
     296                 :  635522000 :   while (true)
     297                 :            :     {
     298                 :            :       /* Don't worry about unreachable blocks.  */
     299                 :  332853000 :       if (EDGE_COUNT (bb->preds) > 0
     300                 :   26131900 :           || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
     301                 :  306825000 :           || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
     302                 :            :         {
     303                 :  332853000 :           edge taken_edge = NULL;
     304                 :            : 
     305                 :            :           /* Callback for subclasses to do custom things before we have walked
     306                 :            :              the dominator children, but before we walk statements.  */
     307                 :  332853000 :           if (this->bb_reachable (cfun, bb))
     308                 :            :             {
     309                 :  332831000 :               taken_edge = before_dom_children (bb);
     310                 :  332831000 :               if (taken_edge && taken_edge != STOP)
     311                 :            :                 {
     312                 :     460063 :                   edge_iterator ei;
     313                 :     460063 :                   edge e;
     314                 :    1030180 :                   FOR_EACH_EDGE (e, ei, bb->succs)
     315                 :     570118 :                     if (e != taken_edge)
     316                 :     110055 :                       e->flags &= ~EDGE_EXECUTABLE;
     317                 :            :                 }
     318                 :            :             }
     319                 :            :           else
     320                 :      21777 :             propagate_unreachable_to_edges (bb, dump_file, dump_flags);
     321                 :            : 
     322                 :            :           /* Mark the current BB to be popped out of the recursion stack
     323                 :            :              once children are processed.  */
     324                 :  332853000 :           worklist[sp++] = bb;
     325                 :  332853000 :           worklist[sp++] = NULL;
     326                 :            : 
     327                 :            :           /* If the callback returned NONE then we are supposed to
     328                 :            :              stop and not even propagate EDGE_EXECUTABLE further.  */
     329                 :  332853000 :           if (taken_edge != STOP)
     330                 :            :             {
     331                 :  332853000 :               int saved_sp = sp;
     332                 :  332853000 :               for (dest = first_dom_son (m_dom_direction, bb);
     333                 :  635522000 :                    dest; dest = next_dom_son (m_dom_direction, dest))
     334                 :  302668000 :                 worklist[sp++] = dest;
     335                 :            :               /* Sort worklist after RPO order if requested.  */
     336                 :  332853000 :               if (sp - saved_sp > 1
     337                 :   86976700 :                   && m_dom_direction == CDI_DOMINATORS
     338                 :   83437000 :                   && m_bb_to_rpo)
     339                 :   83437000 :                 sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp,
     340                 :            :                                     m_bb_to_rpo);
     341                 :            :             }
     342                 :            :         }
     343                 :            :       /* NULL is used to mark pop operations in the recursion stack.  */
     344                 :  665706000 :       while (sp > 0 && !worklist[sp - 1])
     345                 :            :         {
     346                 :  332853000 :           --sp;
     347                 :  332853000 :           bb = worklist[--sp];
     348                 :            : 
     349                 :            :           /* Callback allowing subclasses to do custom things after we have
     350                 :            :              walked dominator children, but before we walk statements.  */
     351                 :  332853000 :           if (bb_reachable (cfun, bb))
     352                 :  332831000 :             after_dom_children (bb);
     353                 :      21777 :           else if (m_unreachable_dom == bb)
     354                 :      16844 :             m_unreachable_dom = NULL;
     355                 :            :         }
     356                 :  332853000 :       if (sp)
     357                 :  302668000 :         bb = worklist[--sp];
     358                 :            :       else
     359                 :            :         break;
     360                 :  302668000 :     }
     361                 :   30184800 :   free (worklist);
     362                 :   30184800 : }

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.