nsz Git - libfirm/blob - include/libfirm/irgwalk.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    Traverse an ir graph
  23  * @author   Boris Boesler, Goetz Lindenmaier
  24  * @version  $Id$
  25  * @brief
  26  *  Traverse an ir graph:
  27  *  - execute the pre function before recursion
  28  *  - execute the post function after recursion
  29  *
  30  *  Uses current_ir_graph (from irgraph.h)!!! Set it to the proper
  31  *  graph before starting the walker.
  32  */
  33 #ifndef FIRM_IR_IRGWALK_H
  34 #define FIRM_IR_IRGWALK_H
  35
  36 #include "firm_types.h"
  37
  38 /**
  39  * Walks over the ir graph.
  40  *
  41  * Walks over the ir graph, starting at the node given as first argument.
  42  * Executes pre before visiting the predecessor of a node, post after.
  43  * irg_walk uses the visited flag in irg and the nodes to determine visited
  44  * nodes.  It executes inc_irg_visited(current_ir_graph) to generate a new
  45  * flag.  Therefore current_ir_graph must be set before calling the walker.
  46  * It marks the node as visited before executing pre.
  47  * The void* env can be used to pass status information between the
  48  * pre and post functions.  Does not use the link fields.
  49  *
  50  * @param node  the start node
  51  * @param pre   walker function, executed before the predecessor of a node are visited
  52  * @param post  walker function, executed after the predecessor of a node are visited
  53  * @param env   environment, passed to pre and post
  54  *
  55  */
  56 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
  57               void *env);
  58
  59 /**
  60  * core walker function. Does NOT touch current_ir_graph and does not call
  61  * inc_irg_visited before walking
  62  */
  63 void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
  64                    void *env);
  65
  66 /**
  67  * Walks over all reachable nodes in the ir graph.
  68  *
  69  * @param irg   the irg graph
  70  * @param pre   walker function, executed before the predecessor of a node are visited
  71  * @param post  walker function, executed after the predecessor of a node are visited
  72  * @param env   environment, passed to pre and post
  73  *
  74  * Like irg_walk(), but walks over all reachable nodes in the ir
  75  * graph, starting at the end operation. During the walk current_ir_graph
  76  * is set to irg.  Does not use the link field.  If interprocedural_view
  77  * is set, visits all reachable irgs.
  78  */
  79 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
  80
  81 /**
  82  * Walks over the ir graph.
  83  *
  84  * Walks over the ir graph, starting at the node given as first argument.
  85  * Executes pre before visiting the predecessor of a node, post after.
  86  * irg_walk uses the visited flag in irg and the nodes to determine visited
  87  * nodes.  It executes inc_irg_visited(current_ir_graph) to generate a new
  88  * flag.  Therefore current_ir_graph must be set before calling the walker.
  89  * It marks the node as visited before executing pre.
  90  * The void* env can be used to pass status information between the
  91  * pre and post functions.  Does not use the link fields.
  92  * This walker also follows additional dependency egdes.
  93  *
  94  * @param node  the start node
  95  * @param pre   walker function, executed before the predecessor of a node are visited
  96  * @param post  walker function, executed after the predecessor of a node are visited
  97  * @param env   environment, passed to pre and post
  98  *
  99  */
 100 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env);
 101
 102 /**
 103  * Walks over all reachable nodes in the ir graph.
 104  *
 105  * @param irg   the irg graph
 106  * @param pre   walker function, executed before the predecessor of a node are visited
 107  * @param post  walker function, executed after the predecessor of a node are visited
 108  * @param env   environment, passed to pre and post
 109  *
 110  * Like irg_walk(), but walks over all reachable nodes in the ir
 111  * graph, starting at the end operation. During the walk current_ir_graph
 112  * is set to irg.  Does not use the link field.
 113  * This walker also follows additional dependency egdes.
 114  * interprocedural_view is not yet supported.
 115  */
 116 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
 117
 118 /**
 119  * Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 120  *
 121  * @param pre   walker function, executed before the predecessor of a node are visited
 122  * @param post  walker function, executed after the predecessor of a node are visited
 123  * @param env   environment, passed to pre and post
 124  *
 125  * This function executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 126  * Sets current_ir_graph properly for each walk.  Conserves current
 127  * current_ir_graph.  In interprocedural view nodes can be visited several
 128  * times.  Does not use the link field.
 129  */
 130 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env);
 131
 132 #ifdef INTERPROCEDURAL_VIEW
 133 /**
 134  * Walks all irgs in interprocedural view.
 135  *
 136  * @param pre   walker function, executed before the predecessor of a node are visited
 137  * @param post  walker function, executed after the predecessor of a node are visited
 138  * @param env   environment, passed to pre and post
 139  *
 140  * This function walks all irgs in interprocedural view.
 141  * Visits each node only once.  Sets current_ir_graph properly. Does not use the link field.
 142  */
 143 void cg_walk(irg_walk_func *pre, irg_walk_func *post, void *env);
 144 #endif
 145
 146 /** Walks only over Block nodes in the graph.
 147  *
 148  * @param node  the start node
 149  * @param pre   walker function, executed before the predecessor of a node are visited
 150  * @param post  walker function, executed after the predecessor of a node are visited
 151  * @param env   environment, passed to pre and post
 152  *
 153  * This function Walks only over Block nodes in the graph. Has it's own visited
 154  * flag, so that it can be interleaved with the other walker.
 155  * If a none block is passed, starts at the block this node belongs to.
 156  * If end is passed also visits kept alive blocks. Does not use the link field.
 157  */
 158 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env);
 159
 160 /**
 161  * Walks only over reachable Block nodes in the graph.
 162  *
 163  * @param irg   the irg graph
 164  * @param pre   walker function, executed before the predecessor of a node are visited
 165  * @param post  walker function, executed after the predecessor of a node are visited
 166  * @param env   environment, passed to pre and post
 167  *
 168  * Like irg_block_walk(), but walks over all reachable blocks in the
 169  * ir graph, starting at the end block. Does not use the link field.
 170  */
 171 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
 172
 173 /**
 174  * Walks over all code in const_code_irg.
 175  *
 176  * @param pre   walker function, executed before the predecessor of a node are visited
 177  * @param post  walker function, executed after the predecessor of a node are visited
 178  * @param env   environment, passed to pre and post
 179  *
 180  * This function walks over all code in const_code_irg.
 181  * Uses visited flag in const_code_irg.  Does not use the link field.
 182  */
 183 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env);
 184
 185 /**
 186  * Walks over reachable nodes in block-wise topological order, i.e. visit
 187  * all nodes in a block before going to another block, starting at the end operation.
 188  * Executes pre before visiting the predecessor of a node, post after.
 189  * irg_walk_blkwise_graph() uses the visited flag in irg and the nodes to
 190  * determine visited nodes.
 191  * It executes inc_irg_visited(current_ir_graph) to generate a new
 192  * flag. It marks the node as visited before executing pre.
 193  * The void *env can be used to pass status information between the
 194  * pre and post functions.  Does not use the link fields.
 195  * Walks only intraprocedural, even in interprocedural view.
 196  *
 197  * @param irg   the irg graph
 198  * @param pre   walker function, executed before the predecessor of a node are visited
 199  * @param post  walker function, executed after the predecessor of a node are visited
 200  * @param env   environment, passed to pre and post
 201  */
 202 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
 203
 204 /**
 205  * Walks over reachable nodes in block-wise topological order, i.e. visit
 206  * all nodes in a block before going to another block, starting at the end operation.
 207  * Executes pre before visiting the predecessor of a node, post after.
 208  * irg_walk_blkwise_graph() uses the visited flag in irg and the nodes to
 209  * determine visited nodes.
 210  * It executes inc_irg_visited(current_ir_graph) to generate a new
 211  * flag. It marks the node as visited before executing pre.
 212  * The void *env can be used to pass status information between the
 213  * pre and post functions.  Does not use the link fields.
 214  * Walks only intraprocedural, even in interprocedural view.
 215  * This walker also follows dependency edges.
 216  *
 217  * @param irg   the irg graph
 218  * @param pre   walker function, executed before the predecessor of a node are visited
 219  * @param post  walker function, executed after the predecessor of a node are visited
 220  * @param env   environment, passed to pre and post
 221  */
 222 void irg_walk_in_or_dep_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
 223
 224 /**
 225  * Walks over reachable nodes in block-wise topological order, i.e. visit
 226  * all nodes in a block before going to another block, starting at the end operation.
 227  * Visit the blocks in dominator tree top-down order.
 228  * Executes pre before visiting the predecessor of a node, post after.
 229  * irg_walk_blkwise_graph() uses the visited flag in irg and the nodes to
 230  * determine visited nodes.
 231  * It executes inc_irg_visited(current_ir_graph) to generate a new
 232  * flag. It marks the node as visited before executing pre.
 233  * The void *env can be used to pass status information between the
 234  * pre and post functions.  Does not use the link fields.
 235  * Walks only intraprocedural, even in interprocedural view.
 236  *
 237  * @param irg   the irg graph
 238  * @param pre   walker function, executed before the predecessor of a node are visited
 239  * @param post  walker function, executed after the predecessor of a node are visited
 240  * @param env   environment, passed to pre and post
 241  */
 242 void irg_walk_blkwise_dom_top_down(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
 243
 244 /**
 245  * Additionally walk over all anchors.
 246  * This function visits all anchor nodes that otherwise might not been visited in a
 247  * walk, for instance the Bad() node.
 248  *
 249  * @param irg   the irg graph
 250  * @param pre   walker function, executed before the predecessor of a node are visited
 251  * @param post  walker function, executed after the predecessor of a node are visited
 252  * @param env   environment, passed to pre and post
 253  */
 254 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env);
 255
 256 /**
 257  * Walker function which does not increase the visited flag before walking.
 258  * Do not use this unless you know what you are doing.
 259  */
 260 unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 261                     void *env);
 262
 263 #endif