gcc/domwalk.c

   1 /* Generic dominator tree walker
   2    Copyright (C) 2003-2016 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 *bb_postorder;
 132
 133 static int
 134 cmp_bb_postorder (const void *a, const void *b)
 135 {
 136   basic_block bb1 = *(basic_block *)const_cast<void *>(a);
 137   basic_block bb2 = *(basic_block *)const_cast<void *>(b);
 138   if (bb1->index == bb2->index)
 139     return 0;
 140   /* Place higher completion number first (pop off lower number first).  */
 141   if (bb_postorder[bb1->index] > bb_postorder[bb2->index])
 142     return -1;
 143   return 1;
 144 }
 145
 146 /* Constructor for a dom walker.
 147
 148    If SKIP_UNREACHBLE_BLOCKS is true, then we need to set
 149    EDGE_EXECUTABLE on every edge in the CFG. */
 150 dom_walker::dom_walker (cdi_direction direction,
 151                         bool skip_unreachable_blocks)
 152   : m_dom_direction (direction),
 153     m_skip_unreachable_blocks (skip_unreachable_blocks),
 154     m_unreachable_dom (NULL)
 155 {
 156   /* If we are not skipping unreachable blocks, then there is nothing
 157      to do.  */
 158   if (!m_skip_unreachable_blocks)
 159     return;
 160
 161   basic_block bb;
 162   FOR_ALL_BB_FN (bb, cfun)
 163     {
 164       edge_iterator ei;
 165       edge e;
 166       FOR_EACH_EDGE (e, ei, bb->succs)
 167         e->flags |= EDGE_EXECUTABLE;
 168     }
 169 }
 170
 171 /* Return TRUE if BB is reachable, false otherwise.  */
 172
 173 bool
 174 dom_walker::bb_reachable (struct function *fun, basic_block bb)
 175 {
 176   /* If we're not skipping unreachable blocks, then assume everything
 177      is reachable.  */
 178   if (!m_skip_unreachable_blocks)
 179     return true;
 180
 181   /* If any of the predecessor edges that do not come from blocks dominated
 182      by us are still marked as possibly executable consider this block
 183      reachable.  */
 184   bool reachable = false;
 185   if (!m_unreachable_dom)
 186     {
 187       reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (fun);
 188       edge_iterator ei;
 189       edge e;
 190       FOR_EACH_EDGE (e, ei, bb->preds)
 191         if (!dominated_by_p (CDI_DOMINATORS, e->src, bb))
 192           reachable |= (e->flags & EDGE_EXECUTABLE);
 193     }
 194
 195   return reachable;
 196 }
 197
 198 /* BB has been determined to be unreachable.  Propagate that property
 199    to incoming and outgoing edges of BB as appropriate.  */
 200
 201 void
 202 dom_walker::propagate_unreachable_to_edges (basic_block bb,
 203                                             FILE *dump_file,
 204                                             int dump_flags)
 205 {
 206   if (dump_file && (dump_flags & TDF_DETAILS))
 207     fprintf (dump_file, "Marking all outgoing edges of unreachable "
 208              "BB %d as not executable\n", bb->index);
 209
 210   edge_iterator ei;
 211   edge e;
 212   FOR_EACH_EDGE (e, ei, bb->succs)
 213     e->flags &= ~EDGE_EXECUTABLE;
 214
 215   FOR_EACH_EDGE (e, ei, bb->preds)
 216     {
 217       if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
 218         {
 219           if (dump_file && (dump_flags & TDF_DETAILS))
 220             fprintf (dump_file, "Marking backedge from BB %d into "
 221                      "unreachable BB %d as not executable\n",
 222                      e->src->index, bb->index);
 223           e->flags &= ~EDGE_EXECUTABLE;
 224         }
 225     }
 226
 227   if (!m_unreachable_dom)
 228     m_unreachable_dom = bb;
 229 }
 230
 231 /* Recursively walk the dominator tree.
 232    BB is the basic block we are currently visiting.  */
 233
 234 void
 235 dom_walker::walk (basic_block bb)
 236 {
 237   basic_block dest;
 238   basic_block *worklist = XNEWVEC (basic_block,
 239                                    n_basic_blocks_for_fn (cfun) * 2);
 240   int sp = 0;
 241   int *postorder, postorder_num;
 242
 243   if (m_dom_direction == CDI_DOMINATORS)
 244     {
 245       postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
 246       postorder_num = inverted_post_order_compute (postorder);
 247       bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
 248       for (int i = 0; i < postorder_num; ++i)
 249         bb_postorder[postorder[i]] = i;
 250       free (postorder);
 251     }
 252
 253   while (true)
 254     {
 255       /* Don't worry about unreachable blocks.  */
 256       if (EDGE_COUNT (bb->preds) > 0
 257           || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
 258           || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
 259         {
 260
 261           /* Callback for subclasses to do custom things before we have walked
 262              the dominator children, but before we walk statements.  */
 263           if (this->bb_reachable (cfun, bb))
 264             {
 265               edge taken_edge = before_dom_children (bb);
 266               if (taken_edge)
 267                 {
 268                   edge_iterator ei;
 269                   edge e;
 270                   FOR_EACH_EDGE (e, ei, bb->succs)
 271                     if (e != taken_edge)
 272                       e->flags &= ~EDGE_EXECUTABLE;
 273                 }
 274             }
 275           else
 276             propagate_unreachable_to_edges (bb, dump_file, dump_flags);
 277
 278           /* Mark the current BB to be popped out of the recursion stack
 279              once children are processed.  */
 280           worklist[sp++] = bb;
 281           worklist[sp++] = NULL;
 282
 283           int saved_sp = sp;
 284           for (dest = first_dom_son (m_dom_direction, bb);
 285                dest; dest = next_dom_son (m_dom_direction, dest))
 286             worklist[sp++] = dest;
 287           if (m_dom_direction == CDI_DOMINATORS)
 288             switch (sp - saved_sp)
 289               {
 290               case 0:
 291               case 1:
 292                 break;
 293               default:
 294                 qsort (&worklist[saved_sp], sp - saved_sp,
 295                        sizeof (basic_block), cmp_bb_postorder);
 296               }
 297         }
 298       /* NULL is used to mark pop operations in the recursion stack.  */
 299       while (sp > 0 && !worklist[sp - 1])
 300         {
 301           --sp;
 302           bb = worklist[--sp];
 303
 304           /* Callback allowing subclasses to do custom things after we have
 305              walked dominator children, but before we walk statements.  */
 306           if (bb_reachable (cfun, bb))
 307             after_dom_children (bb);
 308           else if (m_unreachable_dom == bb)
 309             m_unreachable_dom = NULL;
 310         }
 311       if (sp)
 312         bb = worklist[--sp];
 313       else
 314         break;
 315     }
 316   if (m_dom_direction == CDI_DOMINATORS)
 317     {
 318       free (bb_postorder);
 319       bb_postorder = NULL;
 320     }
 321   free (worklist);
 322 }