nsz Git - libfirm/blob - ir/ana/irdom.h

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irdom.h
   4  * Purpose:     Construct and access dominator tree.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     2.2002
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14  * @file irdom.h
  15  *
  16  *   This file contains routines to construct and access dominator information.
  17  *
  18  *   The dominator information is stored in three fields of block nodes:
  19  *     - idom: a reference to the block that is the immediate dominator of
  20  *       this block.
  21  *     - dom_depth: a number giving the depth of the block in the dominator
  22  *       tree.
  23  *     - pre_num:  Number in preorder traversal.
  24  *
  25  * @author Goetz Lindenmaier
  26  */
  27 #ifndef _IRDOM_H_
  28 #define _IRDOM_H_
  29
  30 #include "firm_types.h"
  31
  32
  33 /** Accessing the dominator data structure.
  34  *
  35  * These routines only work properly if the ir_graph is in state
  36  * dom_consistent or dom_inconsistent.
  37  *
  38  * If the block is not reachable from Start, returns a Bad node.
  39  */
  40 ir_node *get_Block_idom(const ir_node *bl);
  41 void set_Block_idom(ir_node *bl, ir_node *n);
  42
  43 int get_Block_dom_depth(const ir_node *bl);
  44 void set_Block_dom_depth(ir_node *bl, int depth);
  45
  46 int get_Block_dom_pre_num(const ir_node *bl);
  47 void set_Block_dom_pre_num(ir_node *bl, int num);
  48
  49 /** Accessing the post dominator data structure.
  50  *
  51  * These routines only work properly if the ir_graph is in state
  52  * dom_consistent or dom_inconsistent.
  53  *
  54  * If the block is not reachable from End, returns a Bad node.
  55  */
  56 ir_node *get_Block_ipostdom(const ir_node *bl);
  57 void set_Block_ipostdom(ir_node *bl, ir_node *n);
  58
  59 int get_Block_postdom_depth(const ir_node *bl);
  60 void set_Block_postdom_depth(ir_node *bl, int depth);
  61
  62 int get_Block_postdom_pre_num(const ir_node *bl);
  63 void set_Block_postdom_pre_num(ir_node *bl, int num);
  64
  65 /**
  66  * Get the pre-order number of a block resulting from a
  67  * Depth-First-Search walkover the dominator tree.
  68  *
  69  * @param bl The block.
  70  * @return The pre-order number.
  71  */
  72 unsigned get_Block_dom_tree_pre_num(const ir_node *bl);
  73
  74 /**
  75  * Get the largest pre-order number found in the subtree of the
  76  * dominator tree rooted at a given block.
  77  * @param bl The block.
  78  * @return The largest pre-order number of block's dominator subtree.
  79  */
  80 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl);
  81
  82 /**
  83  * Get the first node in the list of nodes dominated by a given block.
  84  *
  85  * Each node keeps a list of nodes which it immediately dominates. The
  86  * nodes are queued using the @c next pointer in the @c dom_info struct.
  87  * Each node keeps a head of this list using the pointer @c first in the
  88  * same structure.
  89  *
  90  * @param bl The block for which to get the first node dominated by @c bl.
  91  * @return The first node dominated by @p bl.
  92  */
  93 ir_node *get_Block_dominated_first(const ir_node *bl);
  94
  95 /**
  96  * Get the next node in a list of nodes which are dominated by some
  97  * other node.
  98  * @see get_Block_dominated_first().
  99  * @param dom The previous node.
 100  * @return The next node in this list or NULL if it was the last.
 101  */
 102 ir_node *get_Block_dominated_next(const ir_node *dom);
 103
 104 /**
 105  * Iterate over all nodes which are immediately dominated by a given
 106  * node.
 107  * @param bl   The block whose dominated blocks shall be iterated on.
 108  * @param curr An iterator variable of type ir_node*
 109  */
 110 #define dominates_for_each(bl,curr) \
 111         for(curr = get_Block_dominated_first(bl); curr; \
 112                         curr = get_Block_dominated_next(curr))
 113
 114 /**
 115  * Iterate over all nodes which are immediately post dominated by a given
 116  * node.
 117  * @param bl   The block whose post dominated blocks shall be iterated on.
 118  * @param curr An iterator variable of type ir_node*
 119  */
 120 #define postdominates_for_each(bl,curr) \
 121         for(curr = get_Block_postdominated_first(bl); curr; \
 122                         curr = get_Block_postdominated_next(curr))
 123
 124 /**
 125  * Check, if a block dominates another block.
 126  * @param a The first block.
 127  * @param b The second block.
 128  * @return 1, if @p a dominates @p b, else 0.
 129  */
 130 int block_dominates(const ir_node *a, const ir_node *b);
 131
 132 /**
 133  * Returns the smallest common dominator block of two nodes.
 134  * @param a A node.
 135  * @param b Another node.
 136  * @return The first block dominating @p a and @p b
 137  */
 138 ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
 139
 140 /**
 141  * Returns the smallest common dominator block of all users of a node
 142  * BEWARE: @p irn must not be a block
 143  * If on or more users are Phi nodes, one can request special handling
 144  * with @p handle_phi = 1.  In this case the cfg predecessor block
 145  * corresponding to the position of the irn in the argument list of the
 146  * Phi is determined and treated as user.
 147  *
 148  * @param irn        A node.
 149  * @param handle_phi 1 if Phis should be handled different
 150  * @return The first block dominating all users of @irn
 151  */
 152 ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi);
 153
 154 /**
 155  * Check, if a block post dominates another block.
 156  * @param a The first block.
 157  * @param b The second block.
 158  * @return 1, if @p a post dominates @p b, else 0.
 159  */
 160 int block_postdominates(const ir_node *a, const ir_node *b);
 161
 162 /**
 163  * Visit all nodes in the dominator subtree of a given node.
 164  * Call a pre-visitor before descending to the children and call a
 165  * post-visitor after returning from them.
 166  * @param n The node to start walking from.
 167  * @param pre The pre-visitor callback.
 168  * @param post The post-visitor callback.
 169  * @param env Some custom data passed to the visitors.
 170  */
 171 void dom_tree_walk(ir_node *n, irg_walk_func *pre,
 172                 irg_walk_func *post, void *env);
 173
 174 /**
 175  * Visit all nodes in the post dominator subtree of a given node.
 176  * Call a pre-visitor before descending to the children and call a
 177  * post-visitor after returning from them.
 178  * @param n The node to start walking from.
 179  * @param pre The pre-visitor callback.
 180  * @param post The post-visitor callback.
 181  * @param env Some custom data passed to the visitors.
 182  */
 183 void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
 184                 irg_walk_func *post, void *env);
 185
 186 /**
 187  * Walk over the dominator tree of an irg starting at the root.
 188  * @param irg The graph.
 189  * @param pre A pre-visitor to call.
 190  * @param post A post-visitor to call.
 191  * @param env Some private data to give to the visitors.
 192  */
 193 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 194                 irg_walk_func *post, void *env);
 195
 196 /**
 197  * Walk over the post dominator tree of an irg starting at the root.
 198  * @param irg The graph.
 199  * @param pre A pre-visitor to call.
 200  * @param post A post-visitor to call.
 201  * @param env Some private data to give to the visitors.
 202  */
 203 void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 204                 irg_walk_func *post, void *env);
 205
 206 /* ------------ Building and Removing the dominator data structure ----------- */
 207
 208 /** Computes the dominator trees.
 209  *
 210  * Sets a flag in irg to "dom_consistent".
 211  * If the control flow of the graph is changed this flag must be set to
 212  * "dom_inconsistent".
 213  * Does not compute dominator information for control dead code.  Blocks
 214  * not reachable from Start contain the following information:
 215  * @code
 216  *   idom = NULL;
 217  *   dom_depth = -1;
 218  *   pre_num = -1;
 219  * @endcode
 220  * Also constructs outs information.  As this information is correct after
 221  * the run does not free the outs information.
 222  */
 223 void compute_doms(ir_graph *irg);
 224
 225 /** Computes the dominator trees on demand */
 226 void assure_doms(ir_graph *irg);
 227
 228 /** Computes the post dominator trees.
 229  *
 230  * Sets a flag in irg to "dom_consistent".
 231  * If the control flow of the graph is changed this flag must be set to
 232  * "dom_inconsistent".
 233  * Does not compute post dominator information for endless lops.  Blocks
 234  * not reachable from End contain the following information:
 235  * @code
 236  *   idom = NULL;
 237  *   dom_depth = -1;
 238  *   pre_num = -1;
 239  * @endcode
 240  * Also constructs outs information.  As this information is correct after
 241  * the run does not free the outs information.
 242  */
 243 void compute_postdoms(ir_graph *irg);
 244
 245 /** Computes the dominator trees on demand */
 246 void assure_postdoms(ir_graph *irg);
 247
 248 /** Frees the dominator data structures.  Sets the flag in irg to "dom_none". */
 249 void free_dom(ir_graph *irg);
 250
 251 /** Frees the post dominator data structures.  Sets the flag in irg to "dom_none". */
 252 void free_postdom(ir_graph *irg);
 253
 254 #endif /* _IRDOM_H_ */