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