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 /**
  34  * @ingroup irana
  35  * @defgroup irdom Dominance Information
  36  *
  37  *   The dominator information is stored in three fields of block nodes:
  38  *     - idom: a reference to the block that is the immediate dominator of
  39  *       this block.
  40  *     - dom_depth: a number giving the depth of the block in the dominator
  41  *       tree.
  42  *     - pre_num:  Number in preorder traversal.
  43  *
  44  * We generally presume (like Tarjan) that endless loops do not exist. The
  45  * implementation assumes a control dependency from End to loop header.
  46  *
  47  * @{
  48  */
  49
  50 /** return immediate dominator of block */
  51 FIRM_API ir_node *get_Block_idom(const ir_node *block);
  52
  53 /** return immediate postdominator of a block */
  54 FIRM_API ir_node *get_Block_ipostdom(const ir_node *block);
  55
  56 /**
  57  * Check, if a block dominates another block.
  58  *
  59  * @param a   The potential dominator block.
  60  * @param b   The potentially dominated block.
  61  *
  62  * @return 1, if @p a dominates @p b, else 0.
  63  */
  64 FIRM_API int block_dominates(const ir_node *a, const ir_node *b);
  65
  66 /**
  67  * Check, if a block strictly dominates another block, i.e. a != b.
  68  *
  69  * @param a The potential dominator block.
  70  * @param b The potentially dominated block.
  71  *
  72  * @return 1, if @p a strictly dominates @p b, else 0.
  73  */
  74 FIRM_API int block_strictly_dominates(const ir_node *a, const ir_node *b);
  75
  76 /**
  77  * Check, if a block post dominates another block.
  78  *
  79  * @param a The potential post dominator block.
  80  * @param b The potentially post dominated block.
  81  *
  82  * @return 1, if @p a post dominates @p b, else 0.
  83  */
  84 FIRM_API int block_postdominates(const ir_node *a, const ir_node *b);
  85
  86 /**
  87  * Check, if a block strictly post dominates another block, i.e. a != b.
  88  *
  89  * @param a The potential post dominator block.
  90  * @param b The potentially post dominated block.
  91  *
  92  * @return 1, if @p a strictly post dominates @p b, else 0.
  93  */
  94 FIRM_API int block_strictly_postdominates(const ir_node *a, const ir_node *b);
  95
  96 /**
  97  * Returns the first node in the list of nodes dominated by a given block.
  98  *
  99  * Each node keeps a list of nodes which it immediately dominates. The
 100  * nodes are queued using the @c next pointer in the @c dom_info struct.
 101  * Each node keeps a head of this list using the pointer @c first in the
 102  * same structure.
 103  *
 104  * @param block The block for which to get the first node dominated by @c bl.
 105  * @return The first node dominated by @p bl.
 106  */
 107 FIRM_API ir_node *get_Block_dominated_first(const ir_node *block);
 108 /**
 109  * Returns the first node in the list of nodes postdominated by a given blcok.
 110  */
 111 FIRM_API ir_node *get_Block_postdominated_first(const ir_node *bl);
 112
 113 /**
 114  * Returns the next node in a list of nodes which are dominated by some
 115  * other node.
 116  * @see get_Block_dominated_first().
 117  * @param node The previous node.
 118  * @return The next node in this list or NULL if it was the last.
 119  */
 120 FIRM_API ir_node *get_Block_dominated_next(const ir_node *node);
 121 /**
 122  * Returns the next node in a list of nodes which are postdominated by another node
 123  */
 124 FIRM_API ir_node *get_Block_postdominated_next(const ir_node *node);
 125
 126 /**
 127  * Iterate over all nodes which are immediately dominated by a given
 128  * node.
 129  * @param bl   The block whose dominated blocks shall be iterated on.
 130  * @param curr An iterator variable of type ir_node*
 131  */
 132 #define dominates_for_each(bl,curr) \
 133         for(curr = get_Block_dominated_first(bl); curr; \
 134                         curr = get_Block_dominated_next(curr))
 135
 136 /**
 137  * Iterate over all nodes which are immediately post dominated by a given
 138  * node.
 139  * @param bl   The block whose post dominated blocks shall be iterated on.
 140  * @param curr An iterator variable of type ir_node*
 141  */
 142 #define postdominates_for_each(bl,curr) \
 143         for(curr = get_Block_postdominated_first(bl); curr; \
 144                         curr = get_Block_postdominated_next(curr))
 145
 146 /**
 147  * Returns the smallest common dominator block of two nodes.
 148  * @param a A node.
 149  * @param b Another node.
 150  * @return The first block dominating @p a and @p b
 151  */
 152 FIRM_API ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b);
 153
 154 /**
 155  * Visit all nodes in the dominator subtree of a given node.
 156  * Call a pre-visitor before descending to the children and call a
 157  * post-visitor after returning from them.
 158  * @param n The node to start walking from.
 159  * @param pre The pre-visitor callback.
 160  * @param post The post-visitor callback.
 161  * @param env Some custom data passed to the visitors.
 162  */
 163 FIRM_API void dom_tree_walk(ir_node *n, irg_walk_func *pre,
 164                             irg_walk_func *post, void *env);
 165
 166 /**
 167  * Visit all nodes in the post dominator subtree of a given node.
 168  * Call a pre-visitor before descending to the children and call a
 169  * post-visitor after returning from them.
 170  * @param n The node to start walking from.
 171  * @param pre The pre-visitor callback.
 172  * @param post The post-visitor callback.
 173  * @param env Some custom data passed to the visitors.
 174  */
 175 FIRM_API void postdom_tree_walk(ir_node *n, irg_walk_func *pre,
 176                                 irg_walk_func *post, void *env);
 177
 178 /**
 179  * Walk over the dominator tree of an irg starting at the root.
 180  * @param irg The graph.
 181  * @param pre A pre-visitor to call.
 182  * @param post A post-visitor to call.
 183  * @param env Some private data to give to the visitors.
 184  */
 185 FIRM_API void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 186                                 irg_walk_func *post, void *env);
 187
 188 /**
 189  * Walk over the post dominator tree of an irg starting at the root.
 190  * @param irg The graph.
 191  * @param pre A pre-visitor to call.
 192  * @param post A post-visitor to call.
 193  * @param env Some private data to give to the visitors.
 194  */
 195 FIRM_API void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 196                                     irg_walk_func *post, void *env);
 197
 198 /** Computes the dominance relation for all basic blocks of a given graph.
 199  *
 200  * Sets a flag in irg to "dom_consistent".
 201  * If the control flow of the graph is changed this flag must be set to
 202  * "dom_inconsistent".
 203  * Does not compute dominator information for control dead code.  Blocks
 204  * not reachable from Start contain the following information:
 205  * @code
 206  *   idom = NULL;
 207  *   dom_depth = -1;
 208  *   pre_num = -1;
 209  * @endcode
 210  * Also constructs outs information.  As this information is correct after
 211  * the run does not free the outs information.
 212  */
 213 FIRM_API void compute_doms(ir_graph *irg);
 214
 215 /** Recomputes dominator relation of a graph if necessary */
 216 FIRM_API void assure_doms(ir_graph *irg);
 217
 218 /** Computes the post dominance relation for all basic blocks of a given graph.
 219  *
 220  * Sets a flag in irg to "dom_consistent".
 221  * If the control flow of the graph is changed this flag must be set to
 222  * "dom_inconsistent".
 223  * Does not compute post dominator information for endless lops.  Blocks
 224  * not reachable from End contain the following information:
 225  * @code
 226  *   idom = NULL;
 227  *   dom_depth = -1;
 228  *   pre_num = -1;
 229  * @endcode
 230  * Also constructs outs information.  As this information is correct after
 231  * the run does not free the outs information.
 232  */
 233 FIRM_API void compute_postdoms(ir_graph *irg);
 234
 235 /** Recompute postdominance relation if necessary */
 236 FIRM_API void assure_postdoms(ir_graph *irg);
 237
 238 /** Frees the dominance data structures.  Sets the flag in irg to "dom_none". */
 239 FIRM_API void free_dom(ir_graph *irg);
 240
 241 /**
 242  * Frees the postdominance data structures. Sets the flag in irg to "dom_none".
 243  */
 244 FIRM_API void free_postdom(ir_graph *irg);
 245
 246 /** @} */
 247
 248 #include "end.h"
 249
 250 #endif