gcc/domwalk.h

   1 /* Generic dominator tree walker
   2    Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 typedef void *void_p;
  23 DEF_VEC_P(void_p);
  24 DEF_VEC_ALLOC_P(void_p,heap);
  25
  26 /* This is the main data structure for the dominator walker.  It provides
  27    the callback hooks as well as a convenient place to hang block local
  28    data and pass-global data.  */
  29
  30 struct dom_walk_data
  31 {
  32   /* This is the direction of the dominator tree we want to walk.  i.e.,
  33      if it is set to CDI_DOMINATORS, then we walk the dominator tree,
  34      if it is set to CDI_POST_DOMINATORS, then we walk the post
  35      dominator tree.  */
  36   ENUM_BITFIELD (cdi_direction) dom_direction : 2;
  37
  38   /* Nonzero if the statement walker should walk the statements from
  39      last to first within a basic block instead of first to last.
  40
  41      Note this affects both statement walkers.  We haven't yet needed
  42      to use the second statement walker for anything, so it's hard to
  43      predict if we really need the ability to select their direction
  44      independently.  */
  45   BOOL_BITFIELD walk_stmts_backward : 1;
  46
  47   /* Function to initialize block local data.
  48
  49      Note that the dominator walker infrastructure may provide a new
  50      fresh, and zero'd block local data structure, or it may re-use an
  51      existing block local data structure.
  52
  53      If the block local structure has items such as virtual arrays, then
  54      that allows your optimizer to re-use those arrays rather than
  55      creating new ones.  */
  56   void (*initialize_block_local_data) (struct dom_walk_data *,
  57                                        basic_block, bool);
  58
  59   /* Function to call before the statement walk occurring before the
  60      recursive walk of the dominator children.
  61
  62      This typically initializes a block local data and pushes that
  63      data onto BLOCK_DATA_STACK.  */
  64   void (*before_dom_children_before_stmts) (struct dom_walk_data *,
  65                                             basic_block);
  66
  67   /* Function to call to walk statements before the recursive walk
  68      of the dominator children.  */
  69   void (*before_dom_children_walk_stmts) (struct dom_walk_data *,
  70                                           basic_block, block_stmt_iterator);
  71
  72   /* Function to call after the statement walk occurring before the
  73      recursive walk of the dominator children.  */
  74   void (*before_dom_children_after_stmts) (struct dom_walk_data *,
  75                                            basic_block);
  76
  77   /* Function to call before the statement walk occurring after the
  78      recursive walk of the dominator children.  */
  79   void (*after_dom_children_before_stmts) (struct dom_walk_data *,
  80                                            basic_block);
  81
  82   /* Function to call to walk statements after the recursive walk
  83      of the dominator children.  */
  84   void (*after_dom_children_walk_stmts) (struct dom_walk_data *,
  85                                          basic_block, block_stmt_iterator);
  86
  87   /* Function to call after the statement walk occurring after the
  88      recursive walk of the dominator children.
  89
  90      This typically finalizes any block local data and pops
  91      that data from BLOCK_DATA_STACK.  */
  92   void (*after_dom_children_after_stmts) (struct dom_walk_data *,
  93                                           basic_block);
  94
  95   /* Global data for a walk through the dominator tree.  */
  96   void *global_data;
  97
  98   /* Stack of any data we need to keep on a per-block basis.
  99
 100      If you have no local data, then BLOCK_DATA_STACK will be NULL.  */
 101   VEC(void_p,heap) *block_data_stack;
 102
 103   /* Size of the block local data.   If this is zero, then it is assumed
 104      you have no local data and thus no BLOCK_DATA_STACK as well.  */
 105   size_t block_local_data_size;
 106
 107   /* From here below are private data.  Please do not use this
 108      information/data outside domwalk.c.  */
 109
 110   /* Stack of available block local structures.  */
 111   VEC(void_p,heap) *free_block_data;
 112
 113   /* Interesting blocks to process.  If this field is not NULL, this
 114      set is used to determine which blocks to walk.  If we encounter
 115      block I in the dominator traversal, but block I is not present in
 116      INTERESTING_BLOCKS, then none of the callback functions are
 117      invoked on it.  This is useful when a particular traversal wants
 118      to filter out non-interesting blocks from the dominator tree.  */
 119   sbitmap interesting_blocks;
 120 };
 121
 122 void walk_dominator_tree (struct dom_walk_data *, basic_block);
 123 void init_walk_dominator_tree (struct dom_walk_data *);
 124 void fini_walk_dominator_tree (struct dom_walk_data *);