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 data structure.
  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
  55  * Depth-First-Search walkover the dominator tree.
  56  *
  57  * @param bl The block.
  58  * @return The pre-order number.
  59  */
  60 unsigned get_Block_dom_tree_pre_num(const ir_node *bl);
  61
  62 /**
  63  * Get the largest pre-order number found in the subtree of the
  64  * dominator tree rooted at a given block.
  65  * @param bl The block.
  66  * @return The largest pre-order number of block's dominator subtree.
  67  */
  68 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl);
  69
  70 /**
  71  * Get the first node in the list of nodes dominated by a given block.
  72  *
  73  * Each node keeps a list of nodes which it immediately dominates. The
  74  * nodes are queued using the @c next pointer in the @c dom_info struct.
  75  * Each node keeps a head of this list using the pointer @c first in the
  76  * same structure.
  77  *
  78  * @param bl The block for which to get the first node dominated by @c bl.
  79  * @return The first node dominated by @p bl.
  80  */
  81 ir_node *get_Block_dominated_first(const ir_node *bl);
  82
  83 /**
  84  * Get the next node in a list of nodes which are dominated by some
  85  * other node.
  86  * @see get_Block_dominated_first().
  87  * @param dom The previous node.
  88  * @return The next node in this list or NULL if it was the last.
  89  */
  90 ir_node *get_Block_dominated_next(const ir_node *dom);
  91
  92 /**
  93  * Iterate over all nodes which are immediately dominated by a given
  94  * node.
  95  * @param bl   The block whose dominated blocks shall be iterated on.
  96  * @param curr An iterator variable of type ir_node*
  97  */
  98 #define dominates_for_each(bl,curr) \
  99         for(curr = get_Block_dominated_first(bl); curr; \
 100                         curr = get_Block_dominated_next(curr))
 101
 102 /**
 103  * Check, if a block dominates another block.
 104  * @param a The first block.
 105  * @param b The second block.
 106  * @return 1, if @p a dominates @p b, else 0.
 107  */
 108 int block_dominates(const ir_node *a, const ir_node *b);
 109
 110 /**
 111  * Visit all nodes in the dominator subtree of a given node.
 112  * Call a pre-visitor before descending to the children and call a
 113  * post-visitor after returning from them.
 114  * @param n The node to start walking from.
 115  * @param pre The pre-visitor callback.
 116  * @param post The post-visitor callback.
 117  * @param env Some custom data passed to the visitors.
 118  */
 119 void dom_tree_walk(ir_node *n, irg_walk_func *pre,
 120                 irg_walk_func *post, void *env);
 121
 122
 123 /**
 124  * Walk over the dominator tree of an irg starting at the root.
 125  * @param irg The graph.
 126  * @param pre A pre-visitor to call.
 127  * @param post A post-visitor to call.
 128  * @param env Some private data to give to the visitors.
 129  */
 130 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 131                 irg_walk_func *post, void *env);
 132
 133 /* ------------ Building and Removing the dominator data structure ----------- */
 134
 135 /** Computes the dominator trees.
 136  *
 137  * Sets a flag in irg to "dom_consistent".
 138  * If the control flow of the graph is changed this flag must be set to
 139  * "dom_inconsistent".
 140  * Does not compute dominator information for control dead code.  Blocks
 141  * not reachable from Start contain the following information:
 142  * @code
 143  *   idom = NULL;
 144  *   dom_depth = -1;
 145  *   pre_num = -1;
 146  * @endcode
 147  * Also constructs outs information.  As this information is correct after
 148  * the run does not free the outs information.
 149  */
 150 void compute_doms(ir_graph *irg);
 151
 152 /** Frees the dominator data structures.  Sets the flag in irg to "dom_none". */
 153 void free_dom_and_peace(ir_graph *irg);
 154
 155 #endif /* _IRDOM_H_ */