Line data    Source code

       1              : /* Generic dominator tree walker
       2              :    Copyright (C) 2003-2026 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              :   /* An enum for determining whether the dom walk should be constrained to
      36              :      blocks reachable by executable edges.  */
      37              : 
      38              :   enum reachability
      39              :   {
      40              :     /* Walk all blocks within the CFG.  */
      41              :     ALL_BLOCKS,
      42              : 
      43              :     /* Use REACHABLE_BLOCKS when your subclass can discover that some edges
      44              :        are not executable.
      45              : 
      46              :        If a subclass can discover that a COND, SWITCH or GOTO has a static
      47              :        target in the before_dom_children callback, the taken edge should
      48              :        be returned.  The generic walker will clear EDGE_EXECUTABLE on all
      49              :        edges it can determine are not executable.
      50              : 
      51              :        With REACHABLE_BLOCKS, EDGE_EXECUTABLE will be set on every edge in
      52              :        the dom_walker ctor; the flag will then be cleared on edges that are
      53              :        determined to be not executable.  */
      54              :     REACHABLE_BLOCKS,
      55              : 
      56              :     /* Identical to REACHABLE_BLOCKS, but the initial state of EDGE_EXECUTABLE
      57              :        will instead be preserved in the ctor, allowing for information about
      58              :        non-executable edges to be merged in from an earlier analysis (and
      59              :        potentially for additional edges to be marked as non-executable).  */
      60              :     REACHABLE_BLOCKS_PRESERVING_FLAGS
      61              :   };
      62              : 
      63              :   /* You can provide a mapping of basic-block index to RPO if you
      64              :      have that readily available or you do multiple walks.  If you
      65              :      specify NULL as BB_INDEX_TO_RPO this mapping will be computed
      66              :      lazily at walk time.  If you specify -1 dominator children will
      67              :      not be walked in RPO order.  */
      68              :   dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS,
      69              :               int *bb_index_to_rpo = NULL);
      70              : 
      71              :   ~dom_walker ();
      72              : 
      73              :   /* Walk the dominator tree.  */
      74              :   void walk (basic_block);
      75              : 
      76              :   /* Function to call before the recursive walk of the dominator children.
      77              : 
      78              :      Return value is the always taken edge if the block has multiple outgoing
      79              :      edges, NULL otherwise.  When skipping unreachable blocks, the walker
      80              :      uses the taken edge information to clear EDGE_EXECUTABLE on the other
      81              :      edges, exposing unreachable blocks.  A NULL return value means all
      82              :      outgoing edges should still be considered executable.  A return value
      83              :      of STOP means to stop the domwalk from processing dominated blocks from
      84              :      here.  This can be used to process a SEME region only (note domwalk
      85              :      will still do work linear in function size).  */
      86     10219209 :   virtual edge before_dom_children (basic_block) { return NULL; }
      87              : 
      88              :   /* Function to call after the recursive walk of the dominator children.  */
      89     55238956 :   virtual void after_dom_children (basic_block) {}
      90              : 
      91              : private:
      92              :   /* This is the direction of the dominator tree we want to walk.  i.e.,
      93              :      if it is set to CDI_DOMINATORS, then we walk the dominator tree,
      94              :      if it is set to CDI_POST_DOMINATORS, then we walk the post
      95              :      dominator tree.  */
      96              :   const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
      97              :   const ENUM_BITFIELD (reachability) m_reachability : 2;
      98              :   bool m_user_bb_to_rpo;
      99              :   basic_block m_unreachable_dom;
     100              :   int *m_bb_to_rpo;
     101              : 
     102              :   /* Query whether or not the given block is reachable or not.  */
     103              :   bool bb_reachable (struct function *, basic_block);
     104              : 
     105              :   /* Given an unreachable block, propagate that property to outgoing
     106              :      and possibly incoming edges for the block.  Typically called after
     107              :      determining a block is unreachable in the before_dom_children
     108              :      callback.  */
     109              :   void propagate_unreachable_to_edges (basic_block, FILE *, dump_flags_t);
     110              : 
     111              : };
     112              : 
     113              : extern void set_all_edges_as_executable (function *fn);
     114              : 
     115              : #endif