4 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
6 * This file is part of libFirm.
8 * This file may be distributed and/or modified under the terms of the
9 * GNU General Public License version 2 as published by the Free Software
10 * Foundation and appearing in the file LICENSE.GPL included in the
11 * packaging of this file.
13 * Licensees holding valid libFirm Professional Edition licenses may use
14 * this file in accordance with the libFirm Commercial License.
15 * Agreement provided with the Software.
17 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
18 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24 * @brief walk along memory edges
26 * @date Mon 18 Oct 2004
29 * Walk over a firm graph along its memory edges.
31 * Any number of graphs can be visited at the same time, but no graph
32 * can be traversed more than once at any time.
38 # include "irnode_t.h"
39 # include "irgwalk.h" /* for irg_walk_func */
40 # include "irprog.h" /* for get_irp_main_irg */
47 # endif /* not defined TRUE */
53 /** environment for a single memory walker */
54 typedef struct walk_mem_env_str {
55 ir_graph *graph; /**< the graph we're visiting */
56 unsigned long visited; /**< 'visited' marker
57 (unsigned long in case we walk more than 2^32 graphs) */
58 irg_walk_func *pre; /**< pre action */
59 irg_walk_func *post; /**< post action */
60 void *env; /**< user-defined environment */
62 struct walk_mem_env_str *prev; /**< link up walking instances */
70 /* Link up walking instances */
71 static walk_mem_env_t *walk_envs = NULL;
74 Walk over the firm nodes of a graph via the memory edges (only)
75 starting from a node that has a memory input.
77 static void irg_walk_mem_node (ir_node *node,
78 walk_mem_env_t *walk_env)
80 const ir_opcode op = get_irn_opcode (node);
83 if (get_irn_visited (node) >= walk_env->visited) {
86 set_irn_visited (node, walk_env->visited);
89 if (op_NoMem == get_irn_op (node)) {
90 /* We don't want to see it it if it's not memory */
95 /* We don't want to see proj nodes at all --- skip over them */
96 in = get_Proj_pred (node);
98 irg_walk_mem_node (in, walk_env);
103 /* execute the 'pre' function */
104 if (NULL != walk_env->pre) {
105 walk_env->pre (node, walk_env->env);
112 in = get_Load_mem (node);
114 irg_walk_mem_node (in, walk_env);
117 in = get_Store_mem (node);
119 irg_walk_mem_node (in, walk_env);
122 in = get_Alloc_mem (node);
124 irg_walk_mem_node (in, walk_env);
127 in = get_Free_mem (node);
129 irg_walk_mem_node (in, walk_env);
132 in = get_Raise_mem (node);
134 irg_walk_mem_node (in, walk_env);
137 in = get_Sel_mem (node);
139 irg_walk_mem_node (in, walk_env);
142 in = get_Call_mem (node);
144 irg_walk_mem_node (in, walk_env);
147 in = get_Return_mem (node);
149 irg_walk_mem_node (in, walk_env);
153 int n_ins = get_irn_arity (node);
155 for (i = 0; i < n_ins; i ++) {
156 in = get_irn_n (node, i);
158 irg_walk_mem_node (in, walk_env);
162 in = get_Div_mem (node);
164 irg_walk_mem_node (in, walk_env);
167 in = get_Quot_mem (node);
169 irg_walk_mem_node (in, walk_env);
172 in = get_Mod_mem (node);
174 irg_walk_mem_node (in, walk_env);
177 in = get_DivMod_mem (node);
179 irg_walk_mem_node (in, walk_env);
184 int n_ins = get_irn_arity (node);
186 for (i = 0; i < n_ins; i ++) {
187 ir_node *ret = get_irn_n (node, i);
189 irg_walk_mem_node (ret, walk_env);
193 fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
195 get_irn_node_nr (node),
196 get_op_name (get_irn_op (node)));
198 assert (0 && "something not handled");
202 /* execute the 'post' function */
203 if (NULL != walk_env->post) {
204 walk_env->post (node, walk_env->env);
209 See whether the given graph is being visited right now.
210 We can't be visiting a graph multiple times.
212 int get_irg_is_mem_visited (ir_graph *graph)
214 walk_mem_env_t *walk_env = walk_envs;
216 while (NULL != walk_env) {
217 if (graph == walk_env->graph) {
221 walk_env = walk_env->prev;
228 Walk over the nodes of the given graph via the memory edges (only).
229 Each graph can only be subject to this walk once at any given time.
231 void irg_walk_mem (ir_graph *graph,
232 irg_walk_func *pre, irg_walk_func *post,
235 ir_node *end_block = get_irg_end_block (graph);
236 walk_mem_env_t *walk_env = xmalloc (sizeof (walk_mem_env_t));
238 assert (! get_irg_is_mem_visited (graph));
240 walk_env->graph = graph;
241 inc_irg_visited (walk_env->graph);
242 walk_env->visited = get_irg_visited (graph);
244 walk_env->prev = walk_envs;
245 walk_envs = walk_env;
248 walk_env->post = post;
251 /* 'graph' is not actually being visited right now, so make sure it is reported that way */
252 assert (get_irg_is_mem_visited (graph));
255 The ins of the end BLOCK are either 'return's (regular exits) or
256 'ProjX'/'Raise's (exception exits). We only walk over the
257 'return' nodes, assuming that all memory-changing nodes are found
260 irg_walk_mem_node (end_block, walk_env);
262 The end NODE sometimes has some more ins. not sure whether we need to walk them.
265 /* allow only properly nested calls right now */
266 assert (walk_envs == walk_env);
267 walk_envs = walk_envs->prev;
271 assert (! get_irg_is_mem_visited (graph));
278 Revision 1.12 2007/01/16 15:45:42 beck
279 renamed type opcode to ir_opcode
281 Revision 1.11 2005/01/26 12:20:20 beck
284 Revision 1.10 2005/01/14 13:34:48 liekweg
287 Revision 1.9 2005/01/10 17:26:34 liekweg
288 fixup printfs, don't put environments on the stack
290 Revision 1.8 2004/12/22 14:43:14 beck
291 made allocations C-like
293 Revision 1.7 2004/12/21 14:25:35 beck
294 removed C99 constructs
295 make visit counter of same type as irn visit counter
297 Revision 1.6 2004/12/02 16:17:51 beck
298 fixed config.h include
300 Revision 1.5 2004/11/19 10:35:20 liekweg
303 Revision 1.4 2004/11/18 16:35:11 liekweg
304 Do not touch Proj nodes at all
306 Revision 1.3 2004/11/04 14:57:12 liekweg
307 fixed end block handling
309 Revision 1.2 2004/10/22 14:41:12 liekweg
310 execute 'pre' for a change. Also, add CVS log