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.
30 /** obstack for firm walker */
31 static struct obstack fw_obst;
33 /** This map stores all types of firm */
34 static pmap *mode_map = NULL;
35 /** This map stores all types of firm */
36 static pmap *type_map = NULL;
37 /** This map stores all entities of firm */
38 static pmap *entity_map = NULL;
40 /** Internal data structure of firm walker to collect
41 * some information of firm ir. The collected data will be stored
42 * into the link field of ir node. All graphs have a list of its
43 * blocks and all blocks have a list of their nodes. */
45 ir_node **list; /**< List of blocks or nodes */
46 void *link; /**< Public link field. The public link field of firm nodes
47 is wrapped by set_firm_walk_link and
48 get_firm_walk_link. */
52 /** Access macros to fw_data structure */
53 #define FW_GET_DATA_LIST(s) ((s)->list)
54 #define FW_SET_DATA_LIST(s, t) ((s)->list = (t))
55 #define FW_GET_DATA_LINK(s) ((s)->link)
56 #define FW_SET_DATA_LINK(s, t) ((s)->link = (t))
59 /** Returns own data struct of the firm walker.
61 * If no structure defined (firm link is NULL) allocate a new
62 * struct to the fgd obstack. Only ir graph and block nodes
63 * will allocate this structure.
64 * - ir graph collect its block
65 * - block collect its nodes
68 fw_data *fw_get_data(void *thing)
73 switch (get_kind(thing)) {
75 data = get_irg_link(thing);
76 /* init block list of graph */
79 /* allocate new firm walk structure */
80 data = obstack_alloc(&fw_obst, sizeof(fw_data));
81 memset(data, 0, sizeof(fw_data));
82 set_irg_link(thing, data);
83 /* allocate block list */
84 FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
88 /* init node list of block */
91 data = get_irn_link(thing);
94 /* allocate new firm walk structure */
95 data = obstack_alloc(&fw_obst, sizeof(fw_data));
96 memset(data, 0, sizeof(fw_data));
97 set_irn_link(thing, data);
98 /* allocate node list */
99 FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
103 default: {} /* other kinds of firm nodes */
109 /** Free all collected data in ir graphs and nodes.
110 * An ir graph or an ir block node has a list as a
111 * dynamic array, which will be deleted here. */
113 void fw_free_data(void *thing)
115 fw_data *data = NULL;
119 switch (get_kind(thing)) {
121 data = get_irg_link(thing);
122 /* delete block list of graph */
125 DEL_ARR_F(FW_GET_DATA_LIST(data));
126 set_irg_link(thing, NULL);
130 /* delete node list of block */
133 data = get_irn_link(thing);
136 DEL_ARR_F(FW_GET_DATA_LIST(data));
137 set_irn_link(thing, NULL);
141 default: {} /* other kinds of firm nodes */
145 /* documentation in header file */
146 void set_firm_walk_link(void *thing, void *link)
151 switch (get_kind(thing)) {
153 set_entity_link(thing, link);
156 set_type_link(thing, link);
159 data = fw_get_data(thing);
160 FW_SET_DATA_LINK(data, link);
165 data = fw_get_data(thing);
166 FW_SET_DATA_LINK(data, link);
169 set_irn_link(thing, link);
172 set_mode_link(thing, link);
174 default: {} /* other kinds of firm nodes */
178 /* documentation in header file */
179 void *get_firm_walk_link(void *thing)
183 switch (get_kind(thing)) {
185 return get_entity_link(thing);
187 return get_type_link(thing);
189 data = fw_get_data(thing);
190 return FW_GET_DATA_LINK(data);
194 data = fw_get_data(thing);
195 return FW_GET_DATA_LINK(data);
198 return get_irn_link(thing);
200 return get_mode_link(thing);
206 /** Set link field of a ir node to NULL */
208 void fw_clear_link(ir_node * node, void * env)
210 set_irn_link(node, NULL);
213 /** Fill maps of type and entity.
214 * This function will be called by the firm walk initializer
215 * to collect all types and entities of program's firm ir.
216 * All types will be colleced in the hash table type_map
217 * and all entity are stored in entity_map. The mode of an
218 * type will be collected as well.
220 * @param tore Type or entity
221 * @param env Environment pointer (currently unused)
224 void fw_collect_tore(type_or_ent *tore, void *env)
230 switch (get_kind(tore)) {
232 ent = (entity *)tore;
233 /* append entity to list */
234 set_entity_link(ent, NULL);
235 if (!pmap_contains(entity_map, ent))
236 pmap_insert(entity_map, ent, env);
240 mode = get_type_mode(tp);
241 /* append type to list */
242 set_type_link(tp, NULL);
243 if (!pmap_contains(type_map, tp))
244 pmap_insert(type_map, tp, env);
246 /* insert only modes (non atomic types, i.e. class, array or struct
247 have no mode. The link field will be cleared in the walk_do_mode()
248 callback function. */
249 if ((NULL != mode) && (!pmap_contains(mode_map, mode)))
250 pmap_insert(mode_map, mode, env);
256 /** Collect all data from nodes. Block appends itself to
257 * the corresponding ir graph and other nodes appends itself
258 * to block list. Collects also the modes of each node to get
261 * @param irn IR node pointer.
262 * @param env Environment pointer (currently unused)
265 void fw_collect_irn(ir_node *irn, void *env)
268 ir_mode *mode = get_irn_mode(irn);
270 /* The link field will be cleared in the walk_do_mode()
271 callback function. */
272 if ((NULL != mode) && (!pmap_contains(mode_map, mode)))
273 pmap_insert(mode_map, mode, env);
278 /* add this block to ir graph's block list */
279 data = fw_get_data(get_current_ir_graph());
280 ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
282 /* non block nodes */
285 /* add this node to block's node list */
286 ir_node *block = get_nodes_block(irn);
287 data = fw_get_data(block);
288 ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
292 /** Irg walker function to free all collected data from nodes */
294 void fw_free_colleted_data(ir_node *irn, void *env)
296 /* Free node list from blocks */
303 /** Initialize all walking data.
305 * Collect all specific data like types, entities, ir graphs, blocks, nodes
306 * from current firm structures.
308 void firm_walk_init(firm_walk_flags flags)
313 obstack_init(&fw_obst);
315 /* Init map of modes and lists of type and entity. If map or list
316 allready exists, free it. */
319 pmap_destroy(mode_map);
321 mode_map = pmap_create();
325 pmap_destroy(type_map);
327 type_map = pmap_create();
331 pmap_destroy(entity_map);
333 entity_map = pmap_create();
335 /* insert internal modes to mode hash. The link field will be cleared
336 in the walk_do_mode() callback function.
337 Other used modes are added by collecting types */
340 ### RG: should be done by inspection the mode of all irn
342 pmap_insert(mode_map, mode_BB, NULL);
343 pmap_insert(mode_map, mode_T, NULL);
344 pmap_insert(mode_map, mode_ANY, NULL);
345 pmap_insert(mode_map, mode_BAD, NULL);
346 pmap_insert(mode_map, mode_X, NULL);
347 pmap_insert(mode_map, mode_M, NULL);
348 pmap_insert(mode_map, mode_b, NULL);
351 /* Collect all types (also unused types) if flag is set */
352 if (FW_WITH_ALL_TYPES & flags)
353 type_walk(fw_collect_tore, NULL, NULL);
355 /* for each ir graph */
356 for (i = 0; i < get_irp_n_irgs(); i++)
358 ir_graph *irg = get_irp_irg(i);
359 set_irg_link(irg, NULL);
361 type_walk_irg(irg, fw_collect_tore, NULL, NULL);
363 irg_walk_graph(irg, fw_clear_link, fw_collect_irn, NULL);
367 /** This function should call after using the firm walker to free
368 * all collected data and frees the used obstack */
369 void firm_walk_finalize(void)
373 /* free all used maps and lists */
374 pmap_destroy(mode_map);
376 pmap_destroy(type_map);
378 pmap_destroy(entity_map);
381 /* free all collected data from ir graphs and nodes */
382 for (i = 0; i < get_irp_n_irgs(); i++)
384 ir_graph *irg = get_irp_irg(i);
386 irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
390 obstack_free(&fw_obst, NULL);
393 /** Dumps the firm ir.
395 * After initializing the firm walker by calling firm_walk_init()
396 * the firm structure could be accessed by definign the firm walk interface
397 * wif. This function could be called serveral times to customize the
398 * walk order or definitions.
400 * @param wif Walk interface which contains the callback function
402 * @see firm_walk_interface */
403 void firm_walk(firm_walk_interface *wif)
405 int irg_i, block_i, block_list_len, irn_i, irn_list_len;
408 ir_node *block, **block_list, **irn_list;
409 ir_graph *saved_irg = current_ir_graph;
411 assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
413 /* walk over all modes */
414 if (wif->do_mode_init) wif->do_mode_init(wif->env);
417 for (entry = pmap_first(mode_map); entry; entry = pmap_next(mode_map))
419 set_mode_link((ir_mode*)entry->key, NULL);
420 wif->do_mode(entry->key, wif->env);
423 if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
425 /* walk over all types */
426 if (wif->do_type_init) wif->do_type_init(wif->env);
429 for (entry = pmap_first(type_map); entry; entry = pmap_next(type_map))
430 wif->do_type((type *)entry->key, wif->env);
432 if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
434 /* walk over all entities */
435 if (wif->do_entity_init) wif->do_entity_init(wif->env);
438 for (entry = pmap_first(entity_map); entry; entry = pmap_next(entity_map))
439 wif->do_entity((entity *)entry->key, wif->env);
441 if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
444 /* Dump graphs ================================================= */
445 if (wif->do_graph_init) wif->do_graph_init(wif->env);
447 for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
449 current_ir_graph = get_irp_irg(irg_i);
451 /* walk over all ir graph */
452 if (wif->do_graph) wif->do_graph(current_ir_graph, wif->env);
454 /* walk over all irg's block nested ========================== */
455 data = fw_get_data(current_ir_graph);
456 block_list = FW_GET_DATA_LIST(data);
457 block_list_len = ARR_LEN(block_list);
458 for (block_i = 0; block_i < block_list_len; block_i++)
460 if (wif->do_block_init) wif->do_block_init(current_ir_graph, wif->env);
462 block = (ir_node *)block_list[block_i];
463 if (wif->do_block) wif->do_block(block, wif->env);
465 /* walk over all block's ir nodes nested =================== */
466 data = fw_get_data(block);
467 irn_list = FW_GET_DATA_LIST(data);
468 irn_list_len = ARR_LEN(irn_list);
470 /* call block as prefix ir node */
471 if ((wif->do_node) &&
472 (wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX)))
473 wif->do_node(block, wif->env);
475 /* do ir nodes in prefix or postfix order? */
476 if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
477 irn_i = irn_list_len-1;
481 while (irn_i >= 0 && irn_i < irn_list_len)
483 if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
485 /* do ir nodes in prefix or postfix order? */
486 if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
491 /* call block as postfix ir node */
492 if ((wif->do_node) &&
493 ((wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX))
494 == FW_DUMP_BLOCK_AS_IRN))
495 wif->do_node(block, wif->env);
497 /* wall over all block's ir nodes nested end =============== */
499 if(wif->do_block_post)
500 wif->do_block_post(block, wif->env);
502 } /* for each block */
504 if (wif->do_block_finalize)
505 wif->do_block_finalize(current_ir_graph, wif->env);
507 /* walk over all irg's block nested end ====================== */
508 if(wif->do_graph_post)
509 wif->do_graph_post(current_ir_graph, wif->env);
511 } /* for each ir graph irg */
513 if(wif->do_graph_finalize)
514 wif->do_graph_finalize(wif->env);
516 /** ### ToDo: Dump const_code_irg ?? No! Dump const code with entities, types etc. */
518 /* restore the state of current_ir_graph */
519 current_ir_graph = saved_irg;