nsz Git - libfirm/blob - ir/ana/irdom.h

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irdom.h
   4  * Purpose:     Construct and access dominator tree.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     2.2002
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14 * @file irdom.h
  15 *
  16 *   This file contains routines to construct and access dominator information.
  17 *
  18 *   The dominator information is stored in three fields of block nodes:
  19 *     - idom: a reference to the block that is the immediate dominator of
  20 *       this block.
  21 *     - dom_depth: a number giving the depth of the block in the dominator
  22 *       tree.
  23 *     - pre_num:  Number in preorder traversal.
  24 *
  25 * @author Goetz Lindenmaier
  26 */
  27
  28
  29 # ifndef _IRDOM_H_
  30 # define _IRDOM_H_
  31
  32 # include "irgraph.h"
  33 # include "irgwalk.h"
  34 # include "irnode.h"
  35
  36
  37 /** Accessing the dominator datastructure.
  38  *
  39  * These routines only work properly if the ir_graph is in state
  40  * dom_consistent or dom_inconsistent.
  41  *
  42  * If the block is not reachable from Start, returns a Bad node.
  43  */
  44 ir_node *get_Block_idom(const ir_node *bl);
  45 void set_Block_idom(ir_node *bl, ir_node *n);
  46
  47 int get_Block_dom_depth(const ir_node *bl);
  48 void set_Block_dom_depth(ir_node *bl, int depth);
  49
  50 int get_Block_pre_num(const ir_node *bl);
  51 void set_Block_pre_num(ir_node *bl, int num);
  52
  53 /**
  54  * Get the pre-order number of a block resulting from a dfs walk
  55  * over the dominator tree.
  56  * @param bl The block.
  57  * @return The pre-order number.
  58  */
  59 unsigned get_Block_dom_tree_pre_num(const ir_node *bl);
  60
  61 /**
  62  * Get the largest pre-order number found in the subtree of the
  63  * dominator tree rooted at a given block.
  64  * @param bl The block.
  65  * @return The largest pre-order number of block's dominator subtree.
  66  */
  67 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl);
  68
  69 /**
  70  * Get the first node in the list of nodes dominated by a given block.
  71  *
  72  * Each node keeps a list of nodes which it immediately dominates. The
  73  * nodes are queued using the @c next pointer in the @c dom_info struct.
  74  * Each node keeps a head of this list using the pointer @c first in the
  75  * same structure.
  76  *
  77  * @param bl The block for which to get the first node dominated by @c bl.
  78  * @return The first node dominated by @p bl.
  79  */
  80 ir_node *get_Block_dominated_first(const ir_node *bl);
  81
  82 /**
  83  * Get the next node in a list of nodes which are dominated by some
  84  * other node.
  85  * @see get_Block_dominated_first().
  86  * @param dom The previous node.
  87  * @return The next node in this list or NULL if it was the last.
  88  */
  89 ir_node *get_Block_dominated_next(const ir_node *dom);
  90
  91 /**
  92  * Iterate over all nodes which are immediately dominated by a given
  93  * node.
  94  * @param bl The block whose dominated blocks shall be iterated on.
  95  * @param curr An iterator variable of type ir_node*
  96  */
  97 #define dominates_for_each(bl,curr) \
  98         for(curr = get_Block_dominated_first(bl); curr; \
  99                         curr = get_Block_dominated_next(curr))
 100
 101 /**
 102  * Check, if a block dominates another block.
 103  * @param a The first block.
 104  * @param b The second block.
 105  * @return 1, if @p a dominates @p b, else 0.
 106  */
 107 int block_dominates(const ir_node *a, const ir_node *b);
 108
 109 /**
 110  * Visit all nodes in the dominator subtree of a given node.
 111  * Call a pre-visitor before descending to the children and call a
 112  * post-visitor after returning from them.
 113  * @param n The node to start walking from.
 114  * @param pre The pre-visitor callback.
 115  * @param post The post-visitor callback.
 116  * @param env Some custom data passed to the visitors.
 117  */
 118 void dom_tree_walk(ir_node *n, irg_walk_func *pre,
 119                 irg_walk_func *post, void *env);
 120
 121
 122 /**
 123  * Walk over the dominator tree of an irg starting at the root.
 124  * @param irg The graph.
 125  * @param pre A pre-visitor to call.
 126  * @param post A post-visitor to call.
 127  * @param env Some private data to give to the visitors.
 128  */
 129 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 130                 irg_walk_func *post, void *env);
 131
 132 /* ------------ Building and Removing the dominator datasturcture ----------- */
 133
 134 /** Computes the dominator trees.
 135  *
 136  * Sets a flag in irg to "dom_consistent".
 137  * If the control flow of the graph is changed this flag must be set to
 138  * "dom_inconsistent".
 139  * Does not compute dominator information for control dead code.  Blocks
 140  * not reachable from Start contain the following information:
 141  *   idom = NULL;
 142  *   dom_depth = -1;
 143  *   pre_num = -1;
 144  * Also constructs outs information.  As this information is correct after
 145  * the run does not free the outs information.
 146  */
 147 void compute_doms(ir_graph *irg);
 148
 149 /** Frees the dominator datastructures.  Sets the flag in irg to "dom_none". */
 150 void free_dom_and_peace(ir_graph *irg);
 151
 152 #endif /* _IRDOM_H_ */