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