From 02aeb1d1145b379c4e82e0a9f055ee3ca66fa5ef Mon Sep 17 00:00:00 2001 From: Sebastian Felis Date: Mon, 14 Jul 2003 09:54:34 +0000 Subject: [PATCH] A walker that visites all firm constructs. [r1475] --- ir/common/firmwalk.c | 476 +++++++++++++++++++++++++++++++++++++++++++ ir/common/firmwalk.h | 196 ++++++++++++++++++ 2 files changed, 672 insertions(+) create mode 100644 ir/common/firmwalk.c create mode 100644 ir/common/firmwalk.h diff --git a/ir/common/firmwalk.c b/ir/common/firmwalk.c new file mode 100644 index 000000000..bc9796116 --- /dev/null +++ b/ir/common/firmwalk.c @@ -0,0 +1,476 @@ + +#ifdef HAVE_CONFIG_H +# include +#endif + +#include "firmwalk.h" +#include "pmap.h" +#include "entity.h" +#include "irprog.h" +#include "irgwalk.h" +#include "array.h" +#include "obst.h" +#include + +/** obstack for firm walker */ +static struct obstack fw_obst; + +/** This map stores all types of firm */ +static pmap *mode_map = NULL; +/** This list stores all types of firm */ +static type **type_list = NULL; +/** This list stores all entities of firm */ +static entity **entity_list = NULL; + +/** Internal data structure of firm walker to collect + * some information of firm ir. The collected data will be stored + * into the link field of ir node. All graphs have a list of its + * blocks and all blocks have a list of their nodes. */ +typedef struct { + ir_node **list; /**< List of blocks or nodes */ + void *link; /**< Public link field. The public link field of firm nodes + is wrapped by set_firm_walk_link and + get_firm_walk_link. */ +} fw_data; + +//@{ +/** Access macros to fw_data structure */ +#define FGD_GET_DATA_LIST(s) ((s)->list) +#define FGD_SET_DATA_LIST(s, t) ((s)->list = (t)) +#define FGD_GET_DATA_LINK(s) ((s)->link) +#define FGD_SET_DATA_LINK(s, t) ((s)->link = (t)) +//@} + +/** Returns own data struct of the firm walker. + * + * If no structure defined (firm link is NULL) allocate a new + * struct to the fgd obstack. Only ir graph and block nodes + * will allocate this structure. + * - ir graph collect its block + * - block collect its nodes + */ +static +fw_data *fw_get_data(void *thing) +{ + fw_data *data = NULL; + + assert(thing); + switch (get_kind(thing)) { + case k_ir_graph: + data = get_irg_link(thing); + /* init block list of graph */ + if (NULL == data) + { + /* allocate new firm walk structure */ + data = obstack_alloc(&fw_obst, sizeof(fw_data)); + memset(data, 0, sizeof(fw_data)); + set_irg_link(thing, data); + /* allocate block list */ + FGD_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0); + } + break; + case k_ir_node: + /* init node list of block */ + if (is_Block(thing)) + { + data = get_irn_link(thing); + if (NULL == data) + { + /* allocate new firm walk structure */ + data = obstack_alloc(&fw_obst, sizeof(fw_data)); + memset(data, 0, sizeof(fw_data)); + set_irn_link(thing, data); + /* allocate node list */ + FGD_GET_DATA_LIST(data) = NEW_ARR_F(ir_node *, 0); + } + } + break; + default: {} // other kinds of firm nodes + } + + return data; +} + +/** Free all collected data in ir graphs and nodes. */ +static +void fw_free_data(void *thing) +{ + fw_data *data = NULL; + + assert(thing); + + switch (get_kind(thing)) { + case k_ir_graph: + data = get_irg_link(thing); + /* delete block list of graph */ + if (NULL != data) + { + DEL_ARR_F(FGD_GET_DATA_LIST(data)); + set_irg_link(thing, NULL); + } + break; + case k_ir_node: + /* delete node list of block */ + if (is_Block(thing)) + { + data = get_irn_link(thing); + if (NULL != data) + { + DEL_ARR_F(FGD_GET_DATA_LIST(data)); + set_irn_link(thing, NULL); + } + } + break; + default: {} // other kinds of firm nodes + } +} + +// documentation in header file +void set_firm_walk_link(void *thing, void *link) +{ + fw_data *data; + + assert(thing); + switch (get_kind(thing)) { + case k_entity: + set_entity_link(thing, link); + break; + case k_type: + set_type_link(thing, link); + break; + case k_ir_graph: + data = fw_get_data(thing); + FGD_SET_DATA_LINK(data, link); + break; + case k_ir_node: + if (is_Block(thing)) + { + data = fw_get_data(thing); + FGD_SET_DATA_LINK(data, link); + } + else + set_irn_link(thing, link); + break; + case k_ir_mode: + set_mode_link(thing, link); + break; + default: {} // other kinds of firm nodes + } +} + +// documentation in header file +void *get_firm_walk_link(void *thing) +{ + fw_data *data; + assert(thing); + switch (get_kind(thing)) { + case k_entity: + return get_entity_link(thing); + case k_type: + return get_type_link(thing); + case k_ir_graph: + data = fw_get_data(thing); + return FGD_GET_DATA_LINK(data); + case k_ir_node: + if (is_Block(thing)) + { + data = fw_get_data(thing); + return FGD_GET_DATA_LINK(data); + } + else + return get_irn_link(thing); + case k_ir_mode: + return get_mode_link(thing); + default: + return NULL; + } +} + +/** Set link field of a ir node to NULL */ +static +void fw_clear_link(ir_node * node, void * env) +{ + set_irn_link(node, NULL); +} + +/** Fill maps of type and entity + * This function will be called by the firm walk initializer + * to collect all types and entities of program's firm ir. + * All types will be colleced in the hash table type_map + * and all entity are stored in entity_map. + * + * @param tore Type or entity + * @param env Environment pointer (currently unused) + */ +static +void fw_collect_tore(type_or_ent *tore, void *env) +{ + ir_mode *mode; + type *tp; + entity *ent; + + switch (get_kind(tore)) { + case k_entity: + ent = (entity *)tore; + // append entity to list + set_entity_link(ent, NULL); + ARR_APP1(entity *, entity_list, ent); + break; + case k_type: + tp = (type *)tore; + mode = get_type_mode(tp); + // append type to list + set_type_link(tp, NULL); + ARR_APP1(type *, type_list, tp); + + /* insert only modes (non atomic types, i.e. class, array or struct + have no mode. The link field will be cleared in the walk_do_mode() + callback function. */ + if ((NULL != mode) && (!pmap_contains(mode_map, mode))) + pmap_insert(mode_map, mode, env); + break; + default: break; + } +} + +/** Collect all data from nodes. Block appends itself to + * the corresponding ir graph and other nodes appends itself + * to block list. + * + * @param irn IR node pointer. +f * @param env Environment pointer (currently unused) + */ +static +void fw_collect_irn(ir_node *irn, void *env) +{ + fw_data *data; + /* block nodes. */ + if (is_Block(irn)) + { + /* add this block to ir graph's block list */ + data = fw_get_data(get_current_ir_graph()); + ARR_APP1(ir_node *, FGD_GET_DATA_LIST(data), irn); + } + /* non block nodes */ + else + { + /* add this node to block's node list */ + ir_node *block = get_nodes_Block(irn); + data = fw_get_data(block); + ARR_APP1(ir_node *, FGD_GET_DATA_LIST(data), irn); + } +} + +/** Irg walker function to free all collected data from nodes */ +static +void fw_free_colleted_data(ir_node *irn, void *env) +{ + /* Free node list from blocks */ + if (is_Block(irn)) + { + fw_free_data(irn); + } +} + +/** Initialize all walking data. + * + * Collect all specific data like types, entities, ir graphs, blocks, nodes + * from current firm structures. + */ +void firm_walk_init(firm_walk_flags flags) +{ + int i; + + /* init obstack */ + obstack_init(&fw_obst); + + /* Init map of modes and lists of type and entity. If map or list + allready exists, free it. */ + if (mode_map) + { + pmap_destroy(mode_map); + } + mode_map = pmap_create(); + + if (type_list) + { + DEL_ARR_F(type_list); + } + type_list = NEW_ARR_F(type *, 0); + + if (entity_list) + { + DEL_ARR_F(entity_list); + } + entity_list = NEW_ARR_F(entity *, 0); + + /* insert internal modes to mode hash. The link field will be cleared + in the walk_do_mode() callback function. + Other used modes are added by collecting types */ + pmap_insert(mode_map, mode_BB, NULL); + pmap_insert(mode_map, mode_T, NULL); + pmap_insert(mode_map, mode_ANY, NULL); + pmap_insert(mode_map, mode_BAD, NULL); + pmap_insert(mode_map, mode_X, NULL); + pmap_insert(mode_map, mode_M, NULL); + pmap_insert(mode_map, mode_b, NULL); + + // Collect all types (also unused types) if flag is set + if (FGD_WITH_ALL_TYPES & flags) + type_walk(fw_collect_tore, NULL, NULL); + + // for each ir graph + for (i = 0; i < get_irp_n_irgs(); i++) + { + ir_graph *irg = get_irp_irg(i); + set_irg_link(irg, NULL); + + type_walk_irg(irg, fw_collect_tore, NULL, NULL); + + irg_walk_graph(irg, fw_clear_link, fw_collect_irn, NULL); + } +} + +/** This function should call after using the firm walker to free + * all collected data and frees the used obstack */ +void firm_walk_finalize(void) +{ + int i; + + /* free all used maps and lists */ + pmap_destroy(mode_map); + mode_map = NULL; + DEL_ARR_F(type_list); + type_list = NULL; + DEL_ARR_F(entity_list); + entity_list = NULL; + + // free all collected data from ir graphs and nodes + for (i = 0; i < get_irp_n_irgs(); i++) + { + ir_graph *irg = get_irp_irg(i); + fw_free_data(irg); + irg_walk_graph(get_irp_irg(i), NULL, fw_free_colleted_data, NULL); + } + + /* free obstack */ + obstack_free(&fw_obst, NULL); +} + +/** Dumps the firm ir. + * + * After initializing the firm walker by calling firm_walk_init() + * the firm structure could be accessed by definign the firm walk interface + * wif. This function could be called serveral times to customize the + * walk order or definitions. + * + * @param wif Walk interface which contains the callback function + * + * @see firm_walk_interface */ +void firm_walk(firm_walk_interface *wif) +{ + int irg_i, block_i, block_list_len, irn_i, irn_list_len; + pmap_entry *entry; + fw_data *data; + ir_graph *irg; + ir_node *block, **block_list, **irn_list; + + assert(wif && "firm_walk() in firmwalk.c: No walking interface defined!"); + + /* walk over all modes */ + if (wif->do_mode_init) wif->do_mode_init(wif->env); + if (wif->do_mode) + { + for (entry = pmap_first(mode_map); entry; entry = pmap_next(mode_map)) + { + set_mode_link((ir_mode*)entry->key, NULL); + wif->do_mode(entry->key, wif->env); + } + } + if (wif->do_mode_finalize) wif->do_mode_finalize(wif->env); + + /* walk over all types */ + if (wif->do_type_init) wif->do_type_init(wif->env); + if (wif->do_type) + { + int type_i, type_list_len = ARR_LEN(type_list); + for (type_i = 0; type_i < type_list_len; type_i++) + wif->do_type(type_list[type_i], wif->env); + } + if (wif->do_type_finalize) wif->do_type_finalize(wif->env); + + /* walk over all entities */ + if (wif->do_entity_init) wif->do_entity_init(wif->env); + if (wif->do_entity) + { + int entity_i, entity_list_len = ARR_LEN(entity_list); + for (entity_i = 0; entity_i < entity_list_len; entity_i++) + wif->do_entity(entity_list[entity_i], wif->env); + } + if (wif->do_entity_finalize) wif->do_entity_finalize(wif->env); + + + /* Dump graphs ================================================= */ + if (wif->do_graph_init) wif->do_graph_init(wif->env); + + for (irg_i = 0; irg_i < get_irp_n_irgs(); irg_i++) + { + irg = get_irp_irg(irg_i); + + /* walk over all ir graph */ + if (wif->do_graph) wif->do_graph(irg, wif->env); + + /* walk over all irg's block nested ========================== */ + data = fw_get_data(irg); + block_list = FGD_GET_DATA_LIST(data); + block_list_len = ARR_LEN(block_list); + for (block_i = 0; block_i < block_list_len; block_i++) + { + if (wif->do_block_init) wif->do_block_init(irg, wif->env); + + block = (ir_node *)block_list[block_i]; + if (wif->do_block) wif->do_block(block, wif->env); + + /* walk over all block's ir nodes nested =================== */ + data = fw_get_data(block); + irn_list = FGD_GET_DATA_LIST(data); + irn_list_len = ARR_LEN(irn_list); + + // call block as prefix ir node + if ((wif->do_node) && + (wif->flags & FGD_DUMP_BLOCK_AS_IRN & !FGD_DUMP_IRN_IN_PREFIX)) + wif->do_node(block, wif->env); + + // do ir nodes in prefix or postfix order? + if (wif->flags & FGD_DUMP_IRN_IN_PREFIX) + irn_i = irn_list_len-1; + else + irn_i = 0; + + while (irn_i >= 0 && irn_i < irn_list_len) + { + if (wif->do_node) wif->do_node((ir_node *)irn_list[irn_i], wif->env); + + // do ir nodes in prefix or postfix order? + if (wif->flags & FGD_DUMP_IRN_IN_PREFIX) + irn_i--; + else + irn_i++; + } + // call block as postfix ir node + if ((wif->do_node) && + (wif->flags & (FGD_DUMP_BLOCK_AS_IRN | FGD_DUMP_IRN_IN_PREFIX))) + wif->do_node(block, wif->env); + + /* wall over all block's ir nodes nested end =============== */ + + if (wif->do_block_finalize) wif->do_block_finalize(irg, wif->env); + } // for each block + + /* walk over all irg's block nested end ====================== */ + + } // for each ir graph irg + if (wif->do_graph_finalize) wif->do_graph_finalize(wif->env); + + /** ### ToDo: Dump const_code_irg ?? */ +} diff --git a/ir/common/firmwalk.h b/ir/common/firmwalk.h new file mode 100644 index 000000000..76b31faef --- /dev/null +++ b/ir/common/firmwalk.h @@ -0,0 +1,196 @@ +/** + * @file firmwalk.h + * + * Firm walker over intermediate representation. + * + * To initialize the walker, call firm_walk_init(). This function + * collects all specific data from the firm represenation. After + * building the walker information firm_walk() could be called + * serveral times with different flags (options) from specific walker + * or dumper. At least firm_walk_finalizer() should be called to free + * the stored data. + * + * This walker could be used for a dumper e.g. a vcg or xml dumper. + * + * @note If a specific walker or dumper which uses the link field + * of any firm node, the the wrapper functions set_firm_walk_link() + * and get_firm_walk_link() should be used, because the firm walker + * make use of the link field to store its own data. + */ +#ifndef _FIRM_WALK_H_ +#define _FIRM_WALK_H_ + +#include "type.h" +#include "irgraph.h" +#include "typewalk.h" + +/** Returns the link of a firm node. + * Possible firm structures are: entity, type, ir_graph, ir_node and + * ir_mode. Otherwise this function has no effect + * + * Derived walker or dumper have to call this function to store data + * to a firm structure. The real link field of firm structure is used + * by this firm walker to collect walking data. + * + * @param thing Pointer to a firm structure + * @retrun Link pointer + * + * @note After calling firm_walk_finalize() the stored link + * information may be invalid. */ +void *get_firm_walk_link(void *thing); + +/** Set the link field of a firm structure. + * Possible firm structures are: entity, type, ir_graph, ir_node and + * ir_mode. Otherwise this function has no effect + * + * Derived walker or dumper have to call this function to store data + * to a firm structure. The real link field of firm structure is used + * by this firm walker to collect walking data. + * + * @param thing firm structur + * @param link Pointer to link field + * + * @note After calling firm_walk_finalize() the stored link + * information may be invalid. */ +void set_firm_walk_link(void *thing, void *link); + +/** Initialisation function for firm walker callbacks */ +typedef void firm_walk_init_func(void *env); +/** Finalisation function for firm walker callbacks */ +typedef void firm_walk_finalize_func(void *env); + +/** Mode callback function definition */ +typedef void firm_walk_mode_func(ir_mode *mode, void *env); +/** Type callback function definition */ +typedef void firm_walk_type_func(type *tp, void *env); +/** Entity callback function definition */ +typedef void firm_walk_entity_func(entity *ent, void *env); +/** Graph callback function definition */ +typedef void firm_walk_graph_func(ir_graph *irg, void *env); +//@{ +/** Block callback function definition */ +typedef void firm_walk_block_init_func(ir_graph *irg, void *env); +typedef void firm_walk_block_func(ir_node *block, void *env); +typedef void firm_walk_block_finalize_func(ir_graph *irg, void *env); +//@} +/** Node callback function definition */ +typedef void firm_walk_node_func (ir_node *irn, void *env); + +/** @enum firm_walk_flags + * + * Flags for the firm walker to modify some dumping behavior + */ +typedef enum +{ + FGD_WITH_ALL_TYPES = 1<<0, /**< Collect and dump all types, especially + unused types. + @note This flag could be set in + firm_dumper_init() and is unused in + firm_dump() */ + FGD_WITH_DOMINATOR = 1<<1, /**< nyi */ + FGD_WITH_OUTEDGES = 1<<2, /**< nyi */ + FGD_WITH_LOOPS = 1<<3, /**< nyi */ + FGD_DUMP_BLOCK_AS_IRN = 1<<4, /**< Dump all block nodes as irn nodes + additionally */ + FGD_DUMP_IRN_IN_PREFIX = 1<<5, /**< Dumps all ir nodes in prefix order + according to the internal firm graph + structure */ +} firm_walk_flags; + +/** Interface of the firm walker */ +typedef struct +{ + //@{ + /** Interface function to dump all used and internal modes. + Internal modes are: BB, X, M and T */ + firm_walk_init_func *do_mode_init; + firm_walk_mode_func *do_mode; + firm_walk_finalize_func *do_mode_finalize; + //@} + + //@{ + /** Interface to dump all collected types. + * + * @node To dump all (not only used types by default) a special walk + * flag must be set for the walker initializer */ + firm_walk_init_func *do_type_init; + firm_walk_type_func *do_type; + firm_walk_finalize_func *do_type_finalize; + //@} + + //@{ + /** Dumping interface for entities */ + firm_walk_init_func *do_entity_init; + firm_walk_entity_func *do_entity; + firm_walk_finalize_func *do_entity_finalize; + //@} + + /** Dumps all graphs and subnodes. + * + * The firm walker dump a graph with its blocks and nodes nested. + * Fist do_graph_init will be called (if defined). For each graph + * do_graph will be call in a loop. After dumped all graphs, + * do_graph_finalize will be called. + * + * Within do_graph each block will be dumped. First do_block_init, + * for each block do_block and after all dumped blocks + * do_block_finalize. + * + * The ir nodes are dumped nested in their blocks as well. Within + * do_block, for each ir node do_node is called in postfix order + * according to the internal firm representation. By changing the + * walking flag, a prefix order is also possible. */ + firm_walk_init_func *do_graph_init; + firm_walk_graph_func *do_graph; + firm_walk_finalize_func *do_graph_finalize; + + //@{ + /** Dumping interface for blocks. If blocks should be handled like + * like a normal ir node, a special walker flag could be set. + * @see do_graph */ + firm_walk_block_init_func *do_block_init; + firm_walk_block_func *do_block; + firm_walk_block_finalize_func *do_block_finalize; + //@} + + /** Dumping interface for ir nodes + * @see do_graph */ + firm_walk_node_func *do_node; + /* dominator */ + /* procedures */ + /* loop */ + firm_walk_flags flags; + /* pointer to environment of interface */ + void *env; +} firm_walk_interface; + + +/** Initialize the dumper und collect all data from the firm intermediate + * representation + * + * @param flags flags */ +void firm_walk_init(firm_walk_flags flags); + +/** Walker of the firm intermediate representation. + * + * The callback functions of the interface will be called nested, e.g. for + * each block: init function of block, do_block, nested function of nodes, + * finalize function of block. + * + * - modes + * - types + * - entities + * - ir graphs + * - procedures + * - blocks + * - nodes. Options: dominator, outedges + * + * @param wif Stucture of walker interface. In this struct the used callback + * functions are defined. + */ +void firm_walk(firm_walk_interface *wif); + +/** Finalize the walker and frees all stored data for dumping */ +void firm_walk_finalize(void); + +#endif /* _FIRM_WALK_H_ */ -- 2.20.1