gcc/domwalk.h

   1 /* Generic dominator tree walker
   2    Copyright (C) 2003-2017 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 #ifndef GCC_DOM_WALK_H
  22 #define GCC_DOM_WALK_H
  23
  24 /**
  25  * This is the main class for the dominator walker. It is expected that
  26  * consumers will have a custom class inheriting from it, which will over ride
  27  * at least one of before_dom_children and after_dom_children to implement the
  28  * custom behavior.
  29  */
  30 class dom_walker
  31 {
  32 public:
  33   static const edge STOP;
  34
  35   /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover
  36      that some edges are not executable.
  37
  38      If a client can discover that a COND, SWITCH or GOTO has a static
  39      target in the before_dom_children callback, the taken edge should
  40      be returned.  The generic walker will clear EDGE_EXECUTABLE on all
  41      edges it can determine are not executable.
  42
  43      You can provide a mapping of basic-block index to RPO if you
  44      have that readily available or you do multiple walks.  */
  45   dom_walker (cdi_direction direction, bool skip_unreachable_blocks = false,
  46               int *bb_index_to_rpo = NULL);
  47
  48   ~dom_walker ();
  49
  50   /* Walk the dominator tree.  */
  51   void walk (basic_block);
  52
  53   /* Function to call before the recursive walk of the dominator children.
  54
  55      Return value is the always taken edge if the block has multiple outgoing
  56      edges, NULL otherwise.  When skipping unreachable blocks, the walker
  57      uses the taken edge information to clear EDGE_EXECUTABLE on the other
  58      edges, exposing unreachable blocks.  A NULL return value means all
  59      outgoing edges should still be considered executable.  A return value
  60      of STOP means to stop the domwalk from processing dominated blocks from
  61      here.  This can be used to process a SEME region only (note domwalk
  62      will still do work linear in function size).  */
  63   virtual edge before_dom_children (basic_block) { return NULL; }
  64
  65   /* Function to call after the recursive walk of the dominator children.  */
  66   virtual void after_dom_children (basic_block) {}
  67
  68 private:
  69   /* This is the direction of the dominator tree we want to walk.  i.e.,
  70      if it is set to CDI_DOMINATORS, then we walk the dominator tree,
  71      if it is set to CDI_POST_DOMINATORS, then we walk the post
  72      dominator tree.  */
  73   const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
  74   bool m_skip_unreachable_blocks;
  75   bool m_user_bb_to_rpo;
  76   basic_block m_unreachable_dom;
  77   int *m_bb_to_rpo;
  78
  79   /* Query whether or not the given block is reachable or not.  */
  80   bool bb_reachable (struct function *, basic_block);
  81
  82   /* Given an unreachable block, propagate that property to outgoing
  83      and possibly incoming edges for the block.  Typically called after
  84      determining a block is unreachable in the before_dom_children
  85      callback.  */
  86   void propagate_unreachable_to_edges (basic_block, FILE *, dump_flags_t);
  87
  88 };
  89
  90 #endif