X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firedges.c;h=c42dda2022941072770b2e7b02edbfbf80b5abdd;hb=de8269f08de3f68e62dfc6fe7f0c29c976489fdd;hp=7dfd6fe00bc5b69af2cf8743e3902624f4944ce1;hpb=22d85c0a3fd056a84c16a0772e54935c4b87f0f5;p=libfirm diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c index 7dfd6fe00..c42dda202 100644 --- a/ir/ir/iredges.c +++ b/ir/ir/iredges.c @@ -4,8 +4,20 @@ * @date 14.1.2005 */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef HAVE_ALLOCA_H +#include +#endif +#ifdef HAVE_MALLOC_H +#include +#endif + #include "irnode_t.h" #include "iredges_t.h" +#include "irgwalk.h" #include "irdump_t.h" #include "irprintf.h" #include "irhooks.h" @@ -14,6 +26,26 @@ static firm_dbg_module_t *dbg; +#if FIRM_EDGES_INPLACE + +/** + * This flag is set to 1, if the edges get initialized for an irg. + * Then register additional data is forbidden. + */ +static int edges_used = 0; + +static int edges_private_size = 0; + +int edges_register_private_data(size_t n) +{ + int res = edges_private_size; + + assert(!edges_used && "you cannot register private edge data, if edges have been initialized"); + + edges_private_size += n; + return res; +} + #define TIMES37(x) (((x) << 5) + ((x) << 2) + (x)) #define get_irn_out_list_head(irn) (&get_irn_out_info(irn)->outs) @@ -27,12 +59,7 @@ static int edge_cmp(const void *p1, const void *p2, size_t len) return !res; } -static INLINE unsigned edge_hash(const ir_edge_t *edge) -{ - unsigned result = HASH_PTR(edge->src); - result = TIMES37(result) + edge->pos; - return result; -} +#define edge_hash(edge) (TIMES37((edge)->pos) + HASH_PTR((edge)->src)) /** * Initialize the out information for a graph. @@ -44,6 +71,8 @@ void edges_init_graph(ir_graph *irg) irg_edge_info_t *info = _get_irg_edge_info(irg); int amount = 2048; + edges_used = 1; + if(info->edges) { amount = set_count(info->edges); del_set(info->edges); @@ -53,6 +82,34 @@ void edges_init_graph(ir_graph *irg) } } +#define EDGE_SIZE(src) \ + (edges_private_size + (is_Block(src) ? sizeof(ir_block_edge_t) : sizeof(ir_edge_t))) + + +/** + * Get the edge object of an outgoing edge at a node. + * @param irg The graph, the node is in. + * @param src The node at which the edge originates. + * @param pos The position of the edge. + * @return The corresponding edge object or NULL, + * if no such edge exists. + */ +const ir_edge_t *get_irn_edge(ir_graph *irg, const ir_node *src, int pos) +{ + if(edges_activated(irg)) { + irg_edge_info_t *info = _get_irg_edge_info(irg); + size_t size = EDGE_SIZE(src); + ir_edge_t *templ = alloca(size); + + memset(templ, 0, size); + templ->src = (ir_node *) src; + templ->pos = pos; + return set_find(info->edges, templ, size, edge_hash(templ)); + } + + return NULL; +} + void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir_graph *irg) { const char *msg = ""; @@ -60,40 +117,64 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir if(!edges_activated(irg)) return; +#if 0 assert(node_is_in_irgs_storage(irg, src) && "source not in irg"); +#endif /* * Only do something, if the old and new target differ. */ if(tgt != old_tgt) { + int is_block_edge = is_Block(src); set *edges = _get_irg_edge_info(irg)->edges; - ir_edge_t templ; ir_edge_t *edge; + /* + * This is scray, but: + * If two entries in a set do not have the same size, they are + * treated as unequal, ignoring the comparison function. + * So, edges from blocks have extra storage (they are + * ir_block_edge_t's). + * + * Also add the amount of registered private data to the + * size of the edge. + */ + size_t size = EDGE_SIZE(src); + ir_edge_t *templ = alloca(size); + /* Initialize the edge template to search in the set. */ + memset(templ, 0, size); #ifdef DEBUG_libfirm - templ.src_nr = get_irn_node_nr(src); + templ->src_nr = get_irn_node_nr(src); #endif - templ.src = src; - templ.pos = pos; - templ.invalid = 0; - templ.present = 0; - INIT_LIST_HEAD(&templ.list); + templ->src = src; + templ->pos = pos; + templ->invalid = 0; + templ->present = 0; /* * If the target is NULL, the edge shall be deleted. */ if(tgt == NULL) { /* search the edge in the set. */ - edge = set_find(edges, &templ, sizeof(templ), edge_hash(&templ)); + edge = set_find(edges, templ, size, edge_hash(templ)); /* mark the edge invalid if it was found */ if(edge) { + ir_block_edge_t *block_edge = (ir_block_edge_t *) edge; + msg = "deleting"; list_del(&edge->list); edge->invalid = 1; edge->pos = -2; edge->src = NULL; + + /* + * If the edge is a cf edge, we delete it also + * from the list of all block successor edges. + */ + if(is_block_edge) + list_del(&block_edge->succ_list); } /* If the edge was not found issue a warning on the debug stream */ @@ -111,9 +192,20 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir else { struct list_head *head = _get_irn_outs_head(tgt); + /* + * The list head in the block of the edges target. + * Therein all control flow edges directed at that block + * are recorded. + */ + struct list_head *succ_head = + is_block_edge ? _get_block_succ_head(get_nodes_block(tgt)) : NULL; + + ir_block_edge_t *block_edge; + +#if 0 if(!node_is_in_irgs_storage(irg, tgt)) return; - +#endif assert(head->next && head->prev && "target list head must have been initialized"); @@ -121,7 +213,8 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir * insert the edge, if it is not yet in the set or return * the instance in the set. */ - edge = set_insert(edges, &templ, sizeof(templ), edge_hash(&templ)); + edge = set_insert(edges, templ, size, edge_hash(templ)); + block_edge = (ir_block_edge_t *) edge; #ifdef DEBUG_libfirm assert(!edge->invalid && "Invalid edge encountered"); @@ -131,6 +224,11 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir if(old_tgt) { msg = "redirecting"; list_move(&edge->list, head); + + /* If the edge is a cf edge, move it from the successor list. */ + if(is_block_edge) + list_move(&block_edge->succ_list, succ_head); + _get_irn_edge_info(old_tgt)->out_count -= 1; } @@ -138,6 +236,13 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir else { msg = "adding"; list_add(&edge->list, head); + + /* + * If the edge is cf edge, enter it into the successor list + * of the target node's block. + */ + if(is_block_edge) + list_add(&block_edge->succ_list, succ_head); } _get_irn_edge_info(tgt)->out_count += 1; @@ -174,7 +279,6 @@ void edges_invalidate(ir_node *irn, ir_graph *irg) edges_node_deleted(irn, irg); } - static void build_edges_walker(ir_node *irn, void *data) { ir_graph *irg = data; @@ -185,13 +289,20 @@ static void build_edges_walker(ir_node *irn, void *data) edges_notify_edge(irn, i, get_irn_n(irn, i), NULL, irg); } +static void init_lh_walker(ir_node *irn, void *data) +{ + INIT_LIST_HEAD(_get_irn_outs_head(irn)); + if(is_Block(irn)) + INIT_LIST_HEAD(_get_block_succ_head(irn)); +} + void edges_activate(ir_graph *irg) { irg_edge_info_t *info = _get_irg_edge_info(irg); info->activated = 1; edges_init_graph(irg); - irg_walk_graph(irg, NULL, build_edges_walker, irg); + irg_walk_graph(irg, init_lh_walker, build_edges_walker, irg); } void edges_deactivate(ir_graph *irg) @@ -199,8 +310,10 @@ void edges_deactivate(ir_graph *irg) irg_edge_info_t *info = _get_irg_edge_info(irg); info->activated = 0; - if(info->edges) + if(info->edges) { del_set(info->edges); + info->edges = NULL; + } } int (edges_activated)(const ir_graph *irg) @@ -240,17 +353,19 @@ static void verify_set_presence(ir_node *irn, void *data) int i, n; for(i = 0, n = get_irn_arity(irn) + not_a_block; i < n; ++i) { - ir_edge_t templ; + ir_block_edge_t space; + ir_edge_t *templ = (ir_edge_t *) &space; ir_edge_t *e; + size_t size = not_a_block ? sizeof(ir_edge_t) : sizeof(ir_block_edge_t); - templ.src = irn; - templ.pos = i - not_a_block; + templ->src = irn; + templ->pos = i - not_a_block; - e = set_find(edges, &templ, sizeof(templ), edge_hash(&templ)); + e = set_find(edges, templ, size, edge_hash(templ)); if(e != NULL) e->present = 1; else - ir_fprintf(stderr, "edge %n,%d is missing\n", irn, templ.pos); + DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is missing\n", irn, templ->pos)); } } @@ -261,8 +376,8 @@ static void verify_list_presence(ir_node *irn, void *data) foreach_out_edge(irn, e) { ir_node *tgt = get_irn_n(e->src, e->pos); if(irn != tgt) - ir_fprintf(stderr, "edge %n,%d is no out edge of %n but of %n\n", - e->src, e->pos, irn, tgt); + DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is no out edge of %n but of %n\n", + e->src, e->pos, irn, tgt)); } } @@ -285,7 +400,7 @@ void edges_verify(ir_graph *irg) */ for(e = set_first(edges); e; e = set_next(edges)) { if(!e->invalid && !e->present) - ir_fprintf(stderr, "edge %n,%d is superfluous\n", e->src, e->pos); + DBG((dbg, LEVEL_DEFAULT, "edge %n,%d is superfluous\n", e->src, e->pos)); } } @@ -315,3 +430,11 @@ int (get_edge_src_pos)(const ir_edge_t *edge) { return _get_edge_src_pos(edge); } + +int (get_irn_n_edges)(const ir_node *irn) +{ + return _get_irn_n_edges(irn); +} + + +#endif /* FIRM_EDGES_INPLACE */