2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Walker that touches all Firm data structures
23 * @author Sebastian Felis
48 /** obstack for firm walker */
49 static struct obstack fw_obst;
51 /** This map stores all types of firm */
52 static pmap *type_map = NULL;
53 /** This map stores all entities of firm */
54 static pmap *entity_map = NULL;
56 /** Internal data structure of firm walker to collect
57 * some information of firm ir. The collected data will be stored
58 * into the link field of ir node. All graphs have a list of its
59 * blocks and all blocks have a list of their nodes. */
61 ir_node **list; /**< List of blocks or nodes */
62 void *link; /**< Public link field. The public link field of firm nodes
63 is wrapped by set_firm_walk_link and
64 get_firm_walk_link. */
68 /** Access macros to fw_data structure */
69 #define FW_GET_DATA_LIST(s) ((s)->list)
70 #define FW_SET_DATA_LIST(s, t) ((s)->list = (t))
71 #define FW_GET_DATA_LINK(s) ((s)->link)
72 #define FW_SET_DATA_LINK(s, t) ((s)->link = (t))
75 /** Returns own data struct of the firm walker.
77 * If no structure defined (firm link is NULL) allocate a new
78 * struct to the fgd obstack. Only ir graph and block nodes
79 * will allocate this structure.
80 * - ir graph collect its block
81 * - block collect its nodes
84 fw_data *fw_get_data(void *thing)
89 switch (get_kind(thing)) {
91 data = get_irg_link(thing);
92 /* init block list of graph */
95 /* allocate new firm walk structure */
96 data = obstack_alloc(&fw_obst, sizeof(fw_data));
97 memset(data, 0, sizeof(fw_data));
98 set_irg_link(thing, data);
99 /* allocate block list */
100 FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
104 /* init node list of block */
107 data = get_irn_link(thing);
110 /* allocate new firm walk structure */
111 data = obstack_alloc(&fw_obst, sizeof(fw_data));
112 memset(data, 0, sizeof(fw_data));
113 set_irn_link(thing, data);
114 /* allocate node list */
115 FW_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0);
119 default: {} /* other kinds of firm nodes */
125 /** Free all collected data in ir graphs and nodes.
126 * An ir graph or an ir block node has a list as a
127 * dynamic array, which will be deleted here. */
129 void fw_free_data(void *thing)
131 fw_data *data = NULL;
135 switch (get_kind(thing)) {
137 data = get_irg_link(thing);
138 /* delete block list of graph */
141 DEL_ARR_F(FW_GET_DATA_LIST(data));
142 set_irg_link(thing, NULL);
146 /* delete node list of block */
149 data = get_irn_link(thing);
152 DEL_ARR_F(FW_GET_DATA_LIST(data));
153 set_irn_link(thing, NULL);
157 default: {} /* other kinds of firm nodes */
161 /* documentation in header file */
162 void set_firm_walk_link(void *thing, void *link)
167 switch (get_kind(thing)) {
169 set_entity_link(thing, link);
172 set_type_link(thing, link);
175 data = fw_get_data(thing);
176 FW_SET_DATA_LINK(data, link);
181 data = fw_get_data(thing);
182 FW_SET_DATA_LINK(data, link);
185 set_irn_link(thing, link);
188 set_mode_link(thing, link);
190 default: {} /* other kinds of firm nodes */
194 /* documentation in header file */
195 void *get_firm_walk_link(void *thing)
199 switch (get_kind(thing)) {
201 return get_entity_link(thing);
203 return get_type_link(thing);
205 data = fw_get_data(thing);
206 return FW_GET_DATA_LINK(data);
210 data = fw_get_data(thing);
211 return FW_GET_DATA_LINK(data);
214 return get_irn_link(thing);
216 return get_mode_link(thing);
222 /** Fill maps of type and entity.
223 * This function will be called by the firm walk initializer
224 * to collect all types and entities of program's firm ir.
225 * All types will be collected in the hash table type_map
226 * and all entity are stored in entity_map. The mode of an
227 * type will be collected as well.
229 * @param tore Type or entity
230 * @param env Environment pointer (currently unused)
233 void fw_collect_tore(type_or_ent *tore, void *env)
238 switch (get_kind(tore)) {
240 ent = (ir_entity *)tore;
241 /* append entity to list */
242 set_entity_link(ent, NULL);
243 if (!pmap_contains(entity_map, ent))
244 pmap_insert(entity_map, ent, env);
247 tp = (ir_type *)tore;
249 /* append type to list */
250 set_type_link(tp, NULL);
251 if (!pmap_contains(type_map, tp))
252 pmap_insert(type_map, tp, env);
258 /** Collect all data from nodes. Block appends itself to
259 * the corresponding ir graph and other nodes appends itself
260 * to block list. Collects also the modes of each node to get
263 * @param irn IR node pointer.
264 * @param env Environment pointer (currently unused)
267 void fw_collect_irn(ir_node *irn, void *env)
273 /* add this block to ir graph's block list */
274 data = fw_get_data(get_current_ir_graph());
275 ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
277 /* non block nodes */
279 /* add this node to block's node list */
280 ir_node *block = get_nodes_block(irn);
281 data = fw_get_data(block);
282 ARR_APP1(ir_node *, FW_GET_DATA_LIST(data), irn);
286 /** Irg walker function to free all collected data from nodes */
288 void fw_free_colleted_data(ir_node *irn, void *env)
290 /* Free node list from blocks */
297 /** Initialize all walking data.
299 * Collect all specific data like types, entities, ir graphs, blocks, nodes
300 * from current firm structures.
302 void firm_walk_init(firm_walk_flags flags)
307 obstack_init(&fw_obst);
309 /* Init map of type and entity. If map or list
310 already exists, free it. */
312 pmap_destroy(type_map);
313 type_map = pmap_create();
316 pmap_destroy(entity_map);
317 entity_map = pmap_create();
319 /* Collect all types (also unused types) if flag is set */
320 if (FW_WITH_ALL_TYPES & flags)
321 type_walk(fw_collect_tore, NULL, NULL);
323 /* for each ir graph */
324 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
325 ir_graph *irg = get_irp_irg(i);
326 set_irg_link(irg, NULL);
328 type_walk_irg(irg, fw_collect_tore, NULL, NULL);
330 irg_walk_graph(irg, firm_clear_link, fw_collect_irn, NULL);
334 /** This function should call after using the firm walker to free
335 * all collected data and frees the used obstack */
336 void firm_walk_finalize(void)
340 /* free all used maps and lists */
341 pmap_destroy(type_map);
343 pmap_destroy(entity_map);
346 /* free all collected data from ir graphs and nodes */
347 for (i = 0; i < get_irp_n_irgs(); i++)
349 ir_graph *irg = get_irp_irg(i);
351 irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL);
355 obstack_free(&fw_obst, NULL);
358 /** Dumps the firm ir.
360 * After initializing the firm walker by calling firm_walk_init()
361 * the firm structure could be accessed by defining the firm walk interface
362 * wif. This function could be called several times to customize the
363 * walk order or definitions.
365 * @param wif Walk interface which contains the callback function
367 * @see firm_walk_interface */
368 void firm_walk(firm_walk_interface *wif)
370 int mode_i, irg_i, block_i, block_list_len, irn_i, irn_list_len;
373 ir_node *block, **block_list, **irn_list;
374 ir_graph *saved_irg = current_ir_graph;
376 assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!");
378 /* walk over all modes */
379 if (wif->do_mode_init) wif->do_mode_init(wif->env);
382 for (mode_i = get_irp_n_modes() - 1; mode_i >= 0; --mode_i)
383 wif->do_mode(get_irp_mode(mode_i), wif->env);
385 if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env);
387 /* walk over all types */
388 if (wif->do_type_init) wif->do_type_init(wif->env);
391 for (entry = pmap_first(type_map); entry; entry = pmap_next(type_map))
392 wif->do_type((ir_type *)entry->key, wif->env);
394 if (wif->do_type_finalize) wif->do_type_finalize(wif->env);
396 /* walk over all entities */
397 if (wif->do_entity_init) wif->do_entity_init(wif->env);
400 for (entry = pmap_first(entity_map); entry; entry = pmap_next(entity_map))
401 wif->do_entity((ir_entity *)entry->key, wif->env);
403 if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env);
406 /* Dump graphs ================================================= */
407 if (wif->do_graph_init) wif->do_graph_init(wif->env);
409 for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++)
411 current_ir_graph = get_irp_irg(irg_i);
413 /* walk over all ir graph */
414 if (wif->do_graph) wif->do_graph(current_ir_graph, wif->env);
416 /* walk over all irg's block nested ========================== */
417 data = fw_get_data(current_ir_graph);
418 block_list = FW_GET_DATA_LIST(data);
419 block_list_len = ARR_LEN(block_list);
420 for (block_i = 0; block_i < block_list_len; block_i++)
422 if (wif->do_block_init) wif->do_block_init(current_ir_graph, wif->env);
424 block = (ir_node *)block_list[block_i];
425 if (wif->do_block) wif->do_block(block, wif->env);
427 /* walk over all block's ir nodes nested =================== */
428 data = fw_get_data(block);
429 irn_list = FW_GET_DATA_LIST(data);
430 irn_list_len = ARR_LEN(irn_list);
432 /* call block as prefix ir node */
433 if ((wif->do_node) &&
434 (wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX)))
435 wif->do_node(block, wif->env);
437 /* do ir nodes in prefix or postfix order? */
438 if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
439 irn_i = irn_list_len-1;
443 while (irn_i >= 0 && irn_i < irn_list_len)
445 if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env);
447 /* do ir nodes in prefix or postfix order? */
448 if (wif->flags & FW_DUMP_IRN_IN_PREFIX)
453 /* call block as postfix ir node */
454 if ((wif->do_node) &&
455 ((wif->flags & (FW_DUMP_BLOCK_AS_IRN | FW_DUMP_IRN_IN_PREFIX))
456 == FW_DUMP_BLOCK_AS_IRN))
457 wif->do_node(block, wif->env);
459 /* wall over all block's ir nodes nested end =============== */
461 if(wif->do_block_post)
462 wif->do_block_post(block, wif->env);
464 } /* for each block */
466 if (wif->do_block_finalize)
467 wif->do_block_finalize(current_ir_graph, wif->env);
469 /* walk over all irg's block nested end ====================== */
470 if(wif->do_graph_post)
471 wif->do_graph_post(current_ir_graph, wif->env);
473 } /* for each ir graph irg */
475 if(wif->do_graph_finalize)
476 wif->do_graph_finalize(wif->env);
478 /** ### ToDo: Dump const_code_irg ?? No! Dump const code with entities, types etc. */
480 /* restore the state of current_ir_graph */
481 current_ir_graph = saved_irg;