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