nsz Git - libfirm/blob - include/libfirm/irgwalk.h

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