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

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