3 * File name: ir/common/firmwalk.c
4 * Purpose: Walker that touches all Firm data structures
5 * Author: Sebastian Felis
9 * Copyright: (c) 2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
33 /** obstack for firm walker */
34 static struct obstack fw_obst;
36 /** This map stores all types of firm */
37 static pmap *type_map = NULL;
38 /** This map stores all entities of firm */
39 static pmap *entity_map = NULL;
41 /** Internal data structure of firm walker to collect
42 * some information of firm ir. The collected data will be stored
43 * into the link field of ir node. All graphs have a list of its
44 * blocks and all blocks have a list of their nodes. */
46 ir_node **list; /**< List of blocks or nodes */
47 void *link; /**< Public link field. The public link field of firm nodes
48 is wrapped by set_firm_walk_link and
49 get_firm_walk_link. */
53 /** Access macros to fw_data structure */
54 #define FW_GET_DATA_LIST(s) ((s)->list)
55 #define FW_SET_DATA_LIST(s, t) ((s)->list = (t))
56 #define FW_GET_DATA_LINK(s) ((s)->link)
57 #define FW_SET_DATA_LINK(s, t) ((s)->link = (t))
60 /** Returns own data struct of the firm walker.
62 * If no structure defined (firm link is NULL) allocate a new
63 * struct to the fgd obstack. Only ir graph and block nodes
64 * will allocate this structure.
65 * - ir graph collect its block
66 * - block collect its nodes
69 fw_data *fw_get_data(void *thing)
74 switch (get_kind(thing)) {
76 data = get_irg_link(thing);
77 /* init block list of graph */
80 /* allocate new firm walk structure */
81 data = obstack_alloc(&fw_obst, sizeof(fw_data));
82 memset(data, 0, sizeof(fw_data));
83 set_irg_link(thing, data);
84 /* allocate block list */
85 FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
89 /* init node list of block */
92 data = get_irn_link(thing);
95 /* allocate new firm walk structure */
96 data = obstack_alloc(&fw_obst, sizeof(fw_data));
97 memset(data, 0, sizeof(fw_data));
98 set_irn_link(thing, data);
99 /* allocate node list */
100 FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
104 default: {} /* other kinds of firm nodes */
110 /** Free all collected data in ir graphs and nodes.
111 * An ir graph or an ir block node has a list as a
112 * dynamic array, which will be deleted here. */
114 void fw_free_data(void *thing)
116 fw_data *data = NULL;
120 switch (get_kind(thing)) {
122 data = get_irg_link(thing);
123 /* delete block list of graph */
126 DEL_ARR_F(FW_GET_DATA_LIST(data));
127 set_irg_link(thing, NULL);
131 /* delete node list of block */
134 data = get_irn_link(thing);
137 DEL_ARR_F(FW_GET_DATA_LIST(data));
138 set_irn_link(thing, NULL);
142 default: {} /* other kinds of firm nodes */
146 /* documentation in header file */
147 void set_firm_walk_link(void *thing, void *link)
152 switch (get_kind(thing)) {
154 set_entity_link(thing, link);
157 set_type_link(thing, link);
160 data = fw_get_data(thing);
161 FW_SET_DATA_LINK(data, link);
166 data = fw_get_data(thing);
167 FW_SET_DATA_LINK(data, link);
170 set_irn_link(thing, link);
173 set_mode_link(thing, link);
175 default: {} /* other kinds of firm nodes */
179 /* documentation in header file */
180 void *get_firm_walk_link(void *thing)
184 switch (get_kind(thing)) {
186 return get_entity_link(thing);
188 return get_type_link(thing);
190 data = fw_get_data(thing);
191 return FW_GET_DATA_LINK(data);
195 data = fw_get_data(thing);
196 return FW_GET_DATA_LINK(data);
199 return get_irn_link(thing);
201 return get_mode_link(thing);
207 /** Fill maps of type and entity.
208 * This function will be called by the firm walk initializer
209 * to collect all types and entities of program's firm ir.
210 * All types will be collected in the hash table type_map
211 * and all entity are stored in entity_map. The mode of an
212 * type will be collected as well.
214 * @param tore Type or entity
215 * @param env Environment pointer (currently unused)
218 void fw_collect_tore(type_or_ent *tore, void *env)
223 switch (get_kind(tore)) {
225 ent = (entity *)tore;
226 /* append entity to list */
227 set_entity_link(ent, NULL);
228 if (!pmap_contains(entity_map, ent))
229 pmap_insert(entity_map, ent, env);
234 /* append type to list */
235 set_type_link(tp, NULL);
236 if (!pmap_contains(type_map, tp))
237 pmap_insert(type_map, tp, env);
243 /** Collect all data from nodes. Block appends itself to
244 * the corresponding ir graph and other nodes appends itself
245 * to block list. Collects also the modes of each node to get
248 * @param irn IR node pointer.
249 * @param env Environment pointer (currently unused)
252 void fw_collect_irn(ir_node *irn, void *env)
258 /* add this block to ir graph's block list */
259 data = fw_get_data(get_current_ir_graph());
260 ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
262 /* non block nodes */
264 /* add this node to block's node list */
265 ir_node *block = get_nodes_block(irn);
266 data = fw_get_data(block);
267 ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
271 /** Irg walker function to free all collected data from nodes */
273 void fw_free_colleted_data(ir_node *irn, void *env)
275 /* Free node list from blocks */
282 /** Initialize all walking data.
284 * Collect all specific data like types, entities, ir graphs, blocks, nodes
285 * from current firm structures.
287 void firm_walk_init(firm_walk_flags flags)
292 obstack_init(&fw_obst);
294 /* Init map of type and entity. If map or list
295 already exists, free it. */
297 pmap_destroy(type_map);
298 type_map = pmap_create();
301 pmap_destroy(entity_map);
302 entity_map = pmap_create();
304 /* Collect all types (also unused types) if flag is set */
305 if (FW_WITH_ALL_TYPES & flags)
306 type_walk(fw_collect_tore, NULL, NULL);
308 /* for each ir graph */
309 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
310 ir_graph *irg = get_irp_irg(i);
311 set_irg_link(irg, NULL);
313 type_walk_irg(irg, fw_collect_tore, NULL, NULL);
315 irg_walk_graph(irg, firm_clear_link, fw_collect_irn, NULL);
319 /** This function should call after using the firm walker to free
320 * all collected data and frees the used obstack */
321 void firm_walk_finalize(void)
325 /* free all used maps and lists */
326 pmap_destroy(type_map);
328 pmap_destroy(entity_map);
331 /* free all collected data from ir graphs and nodes */
332 for (i = 0; i < get_irp_n_irgs(); i++)
334 ir_graph *irg = get_irp_irg(i);
336 irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
340 obstack_free(&fw_obst, NULL);
343 /** Dumps the firm ir.
345 * After initializing the firm walker by calling firm_walk_init()
346 * the firm structure could be accessed by defining the firm walk interface
347 * wif. This function could be called several times to customize the
348 * walk order or definitions.
350 * @param wif Walk interface which contains the callback function
352 * @see firm_walk_interface */
353 void firm_walk(firm_walk_interface *wif)
355 int mode_i, irg_i, block_i, block_list_len, irn_i, irn_list_len;
358 ir_node *block, **block_list, **irn_list;
359 ir_graph *saved_irg = current_ir_graph;
361 assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
363 /* walk over all modes */
364 if (wif->do_mode_init) wif->do_mode_init(wif->env);
367 for (mode_i = get_irp_n_modes() - 1; mode_i >= 0; --mode_i)
368 wif->do_mode(get_irp_mode(mode_i), wif->env);
370 if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
372 /* walk over all types */
373 if (wif->do_type_init) wif->do_type_init(wif->env);
376 for (entry = pmap_first(type_map); entry; entry = pmap_next(type_map))
377 wif->do_type((type *)entry->key, wif->env);
379 if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
381 /* walk over all entities */
382 if (wif->do_entity_init) wif->do_entity_init(wif->env);
385 for (entry = pmap_first(entity_map); entry; entry = pmap_next(entity_map))
386 wif->do_entity((entity *)entry->key, wif->env);
388 if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
391 /* Dump graphs ================================================= */
392 if (wif->do_graph_init) wif->do_graph_init(wif->env);
394 for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
396 current_ir_graph = get_irp_irg(irg_i);
398 /* walk over all ir graph */
399 if (wif->do_graph) wif->do_graph(current_ir_graph, wif->env);
401 /* walk over all irg's block nested ========================== */
402 data = fw_get_data(current_ir_graph);
403 block_list = FW_GET_DATA_LIST(data);
404 block_list_len = ARR_LEN(block_list);
405 for (block_i = 0; block_i < block_list_len; block_i++)
407 if (wif->do_block_init) wif->do_block_init(current_ir_graph, wif->env);
409 block = (ir_node *)block_list[block_i];
410 if (wif->do_block) wif->do_block(block, wif->env);
412 /* walk over all block's ir nodes nested =================== */
413 data = fw_get_data(block);
414 irn_list = FW_GET_DATA_LIST(data);
415 irn_list_len = ARR_LEN(irn_list);
417 /* call block as prefix ir node */
418 if ((wif->do_node) &&
419 (wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX)))
420 wif->do_node(block, wif->env);
422 /* do ir nodes in prefix or postfix order? */
423 if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
424 irn_i = irn_list_len-1;
428 while (irn_i >= 0 && irn_i < irn_list_len)
430 if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
432 /* do ir nodes in prefix or postfix order? */
433 if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
438 /* call block as postfix ir node */
439 if ((wif->do_node) &&
440 ((wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX))
441 == FW_DUMP_BLOCK_AS_IRN))
442 wif->do_node(block, wif->env);
444 /* wall over all block's ir nodes nested end =============== */
446 if(wif->do_block_post)
447 wif->do_block_post(block, wif->env);
449 } /* for each block */
451 if (wif->do_block_finalize)
452 wif->do_block_finalize(current_ir_graph, wif->env);
454 /* walk over all irg's block nested end ====================== */
455 if(wif->do_graph_post)
456 wif->do_graph_post(current_ir_graph, wif->env);
458 } /* for each ir graph irg */
460 if(wif->do_graph_finalize)
461 wif->do_graph_finalize(wif->env);
463 /** ### ToDo: Dump const_code_irg ?? No! Dump const code with entities, types etc. */
465 /* restore the state of current_ir_graph */
466 current_ir_graph = saved_irg;