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