nsz Git - libfirm/blob - include/libfirm/irdom.h

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