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

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