X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firedges.c;h=062cb7119c1ec8414d39a187fb491fb734ef8ad8;hb=8bae7e4a8cf8f1a323ccf7b60c4091da49324f94;hp=eca308d26cee9de8730bfae347b579595cdd2d0e;hpb=e07b61c6ed5d198a484761f8a40a4f26520d964d;p=libfirm diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c index eca308d26..062cb7119 100644 --- a/ir/ir/iredges.c +++ b/ir/ir/iredges.c @@ -23,13 +23,11 @@ * @author Sebastian Hack, Michael Beck, Andreas Schoesser * @date 14.1.2005 * @version $Id$ - * @summary + * @brief * This are out-edges (also called def-use edges) that are dynamically * updated as the graph changes. */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include "irnode_t.h" #include "iropt_t.h" @@ -38,10 +36,11 @@ #include "irgwalk.h" #include "irdump_t.h" #include "irprintf.h" -#include "irhooks.h" #include "debug.h" #include "set.h" #include "bitset.h" +#include "error.h" +#include "irpass_t.h" #include "iredgeset.h" #include "hashptr.h" @@ -77,8 +76,15 @@ */ typedef void (set_edge_func_t)(ir_node *src, int pos, ir_node *tgt); +/** + * A function that returns the "arity" of a given edge kind + * for a node. + */ typedef int (get_edge_src_arity_func_t)(const ir_node *src); +/** + * A function that returns the pos'th edge of a given edge kind for a node. + */ typedef ir_node *(get_edge_src_n_func_t)(const ir_node *src, int pos); /** @@ -95,9 +101,9 @@ typedef struct { /** * Get the predecessor block. */ -static ir_node *get_block_n(const ir_node *irn, int pos) { - if (is_Block(irn)) - return get_Block_cfgpred_block(irn, pos); +static ir_node *get_block_n(const ir_node *block, int pos) { + if (is_Block(block)) + return get_Block_cfgpred_block(block, pos); /* might be a Bad */ return NULL; } @@ -137,7 +143,10 @@ static int edges_dbg = 0; static long last_edge_num = -1; #endif -static INLINE long edge_get_id(const ir_edge_t *e) { +/** + * Returns an ID for the given edge. + */ +static inline long edge_get_id(const ir_edge_t *e) { #ifdef DEBUG_libfirm return e->edge_nr; #else /* DEBUG_libfirm */ @@ -165,12 +174,12 @@ int edges_register_private_data(size_t n) { return res; } -/** +/* * Reset the user's private data at offset 'offset' * The user has to remember his offset and the size of his data! * Caution: Using wrong values here can destroy other users private data! */ -void edges_reset_private_data(ir_graph *irg, int offset, size_t size) { +void edges_reset_private_data(ir_graph *irg, int offset, unsigned size) { irg_edge_info_t *info = _get_irg_edge_info(irg, EDGE_KIND_NORMAL); ir_edge_t *edge; ir_edgeset_iterator_t iter; @@ -202,6 +211,7 @@ void edges_init_graph_kind(ir_graph *irg, ir_edge_kind_t kind) { obstack_free(&info->edges_obst, NULL); } obstack_init(&info->edges_obst); + INIT_LIST_HEAD(&info->free_edges); ir_edgeset_init_size(&info->edges, amount); info->allocated = 1; } @@ -209,9 +219,10 @@ void edges_init_graph_kind(ir_graph *irg, ir_edge_kind_t kind) { /** * 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. + * @param irg The graph, the node is in. + * @param src The node at which the edge originates. + * @param pos The position of the edge. + * @param kind The kind of the edge. * @return The corresponding edge object or NULL, * if no such edge exists. */ @@ -247,7 +258,7 @@ const ir_edge_t *get_irn_edge(ir_graph *irg, const ir_node *src, int pos) { * @param tgt the edge target * @param kind the kind of the edge */ -static INLINE void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs) { +static inline void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs) { irn_edge_info_t *info = _get_irn_edge_info(tgt, kind); info->out_count += ofs; @@ -276,7 +287,7 @@ static INLINE void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs) { * Verify the edge list of a node, ie. ensure it's a loop: * head -> e_1 -> ... -> e_n -> head */ -static INLINE void vrfy_list_head(ir_node *irn, ir_edge_kind_t kind) { +static inline void vrfy_list_head(ir_node *irn, ir_edge_kind_t kind) { int err = 0; int num = 0; pset *lh_set = pset_new_ptr(16); @@ -305,6 +316,29 @@ static INLINE void vrfy_list_head(ir_node *irn, ir_edge_kind_t kind) { assert(err == 0); } +#ifdef DEBUG_libfirm +/** + * Helper function to dump the edge set of a graph, + * unused in normal code. + */ +void edges_dump_kind(ir_graph *irg, ir_edge_kind_t kind) +{ + irg_edge_info_t *info; + ir_edgeset_t *edges; + ir_edgeset_iterator_t iter; + ir_edge_t *e; + + if (!edges_activated_kind(irg, kind)) + return; + + info = _get_irg_edge_info(irg, kind); + edges = &info->edges; + foreach_ir_edgeset(edges, e, iter) { + ir_printf("%+F %d %d\n", e->src, e->pos, e->invalid); + } +} +#endif + /* The edge from (src, pos) -> old_tgt is redirected to tgt */ void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir_edge_kind_t kind, @@ -342,6 +376,8 @@ void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, if (edge) { msg = "deleting"; list_del(&edge->list); + ir_edgeset_remove(edges, edge); + list_add(&edge->list, &info->free_edges); edge->invalid = 1; edge->pos = -2; edge->src = NULL; @@ -349,21 +385,17 @@ void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, edge->edge_nr = -1; #endif /* DEBUG_libfirm */ edge_change_cnt(old_tgt, kind, -1); - } - - /* If the edge was not found issue a warning on the debug stream */ - else { + } else { + /* If the edge was not found issue a warning on the debug stream */ msg = "edge to delete not found!\n"; } - } /* if */ - - /* - * The target is not NULL and the old target differs - * from the new target, the edge shall be moved (if the - * old target was != NULL) or added (if the old target was - * NULL). - */ - else { + } else { + /* + * The target is not NULL and the old target differs + * from the new target, the edge shall be moved (if the + * old target was != NULL) or added (if the old target was + * NULL). + */ struct list_head *head = _get_irn_outs_head(tgt, kind); assert(head->next && head->prev && @@ -379,33 +411,36 @@ void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, list_move(&edge->list, head); edge_change_cnt(old_tgt, kind, -1); - } - - /* The old target was null, thus, the edge is newly created. */ - else { + } else { + /* The old target was NULL, thus, the edge is newly created. */ ir_edge_t *new_edge; - ir_edge_t *edge - = obstack_alloc(&info->edges_obst, EDGE_SIZE); - memset(edge, 0, EDGE_SIZE); - edge->src = src; - edge->pos = pos; - edge->kind = kind; + ir_edge_t *edge; + + if (list_empty(&info->free_edges)) { + edge = obstack_alloc(&info->edges_obst, EDGE_SIZE); + } else { + edge = list_entry(info->free_edges.next, ir_edge_t, list); + list_del(&edge->list); + } + + edge->src = src; + edge->pos = pos; + edge->invalid = 0; + edge->present = 0; + edge->kind = kind; + edge->list.next = NULL; + edge->list.prev = NULL; + memset(edge + 1, 0, edges_private_size); DEBUG_ONLY(edge->src_nr = get_irn_node_nr(src)); new_edge = ir_edgeset_insert(edges, edge); - if(new_edge != edge) { - obstack_free(&info->edges_obst, edge); + if (new_edge != edge) { + panic("new edge exists already"); } - assert(! edge->invalid && "Freshly inserted edge is invalid?!?"); - assert(edge->list.next == NULL && edge->list.prev == NULL && - "New edge must not have list head initialized"); - msg = "adding"; list_add(&edge->list, head); -#ifdef DEBUG_libfirm - edge->edge_nr = ++last_edge_num; -#endif /* DEBUG_libfirm */ + DEBUG_ONLY(edge->edge_nr = ++last_edge_num); } edge_change_cnt(tgt, kind, +1); @@ -467,6 +502,34 @@ static void edges_node_deleted_kind(ir_node *old, ir_edge_kind_t kind, ir_graph } } +/** + * A node might be revivaled by CSE. Assure its edges. + * + * @param irn the node + * @param kind the kind of edges to remove + * @param irg the irg of the old node + */ +static void edges_node_revival_kind(ir_node *irn, ir_edge_kind_t kind, ir_graph *irg) +{ + irn_edge_info_t *info; + int i, n; + + if (!edges_activated_kind(irg, kind)) + return; + + info = _get_irn_edge_info(irn, kind); + if (info->edges_built) + return; + + DBG((dbg, LEVEL_5, "node revivaled (kind: %s): %+F\n", get_kind_str(kind), irn)); + + foreach_tgt(irn, i, n, kind) { + ir_node *tgt = get_n(irn, i, kind); + edges_notify_edge_kind(irn, i, tgt, NULL, kind, irg); + } + info->edges_built = 1; +} + struct build_walker { ir_graph *irg; ir_edge_kind_t kind; @@ -489,6 +552,7 @@ static void build_edges_walker(ir_node *irn, void *data) { ir_node *pred = get_n(irn, i, kind); edges_notify_edge_kind(irn, i, pred, NULL, kind, irg); } + _get_irn_edge_info(irn, kind)->edges_built = 1; } /** @@ -500,7 +564,8 @@ static void init_lh_walker(ir_node *irn, void *data) { ir_edge_kind_t kind = w->kind; list_head *head = _get_irn_outs_head(irn, kind); INIT_LIST_HEAD(head); - _get_irn_edge_info(irn, kind)->out_count = 0; + _get_irn_edge_info(irn, kind)->edges_built = 0; + _get_irn_edge_info(irn, kind)->out_count = 0; } /** @@ -521,7 +586,8 @@ static void init_lh_walker_dep(ir_node *irn, void *data) { int i; INIT_LIST_HEAD(head); - _get_irn_edge_info(irn, kind)->out_count = 0; + _get_irn_edge_info(irn, kind)->edges_built = 0; + _get_irn_edge_info(irn, kind)->out_count = 0; for (i = get_irn_deps(irn) - 1; i >= 0; --i) { ir_node *dep = get_irn_dep(irn, i); @@ -529,7 +595,8 @@ static void init_lh_walker_dep(ir_node *irn, void *data) { head = _get_irn_outs_head(dep, kind); INIT_LIST_HEAD(head); - _get_irn_edge_info(dep, kind)->out_count = 0; + _get_irn_edge_info(dep, kind)->edges_built = 0; + _get_irn_edge_info(dep, kind)->out_count = 0; } } @@ -545,8 +612,7 @@ typedef struct visitor_info_t { static void visitor(ir_node *irn, void *data) { visitor_info_t *info = data; - if (irn_not_visited(irn)) { - mark_irn_visited(irn); + if (!irn_visited_else_mark(irn)) { info->visit(irn, info->data); } } @@ -584,6 +650,8 @@ void edges_activate_kind(ir_graph *irg, ir_edge_kind_t kind) visit.data = &w; + assert(!info->activated); + info->activated = 1; edges_init_graph_kind(irg, kind); if (kind == EDGE_KIND_DEP) { @@ -868,6 +936,37 @@ int edges_verify(ir_graph *irg) { return problem_found ? 1 : w.problem_found; } +struct pass_t { + ir_graph_pass_t pass; + unsigned assert_on_problem; +}; + +/** + * Wrapper to edges_verify to be run as an ir_graph pass. + */ +static int edges_verify_wrapper(ir_graph *irg, void *context) { + struct pass_t *pass = context; + int problems_found = edges_verify(irg); + /* do NOT rerun the pass if verify is ok :-) */ + assert(problems_found && pass->assert_on_problem); + return 0; +} + +/* Creates an ir_graph pass for edges_verify(). */ +ir_graph_pass_t *irg_verify_edges_pass(const char *name, unsigned assert_on_problem) { + struct pass_t *pass = XMALLOCZ(struct pass_t); + + def_graph_pass_constructor( + &pass->pass, name ? name : "edges_verify", edges_verify_wrapper); + + /* neither dump nor verify */ + pass->pass.dump_irg = (DUMP_ON_IRG_FUNC)ir_prog_no_dump; + pass->pass.verify_irg = (RUN_ON_IRG_FUNC)ir_prog_no_verify; + + pass->assert_on_problem = assert_on_problem; + return &pass->pass; +} + void init_edges(void) { FIRM_DBG_REGISTER(dbg, DBG_EDGES); /* firm_dbg_set_mask(dbg, -1); */ @@ -891,11 +990,20 @@ void edges_deactivate(ir_graph *irg) { edges_deactivate_kind(irg, EDGE_KIND_NORMAL); } -int edges_assure(ir_graph *irg) { - int activated = edges_activated(irg); +int edges_assure(ir_graph *irg) +{ + int activated = 0; - if (!activated) - edges_activate(irg); + if (edges_activated_kind(irg, EDGE_KIND_BLOCK)) { + activated = 1; + } else { + edges_activate_kind(irg, EDGE_KIND_BLOCK); + } + if (edges_activated_kind(irg, EDGE_KIND_NORMAL)) { + activated = 1; + } else { + edges_activate_kind(irg, EDGE_KIND_NORMAL); + } return activated; } @@ -914,6 +1022,10 @@ void edges_node_deleted(ir_node *irn, ir_graph *irg) { edges_node_deleted_kind(irn, EDGE_KIND_BLOCK, irg); } +void edges_node_revival(ir_node *irn, ir_graph *irg) { + edges_node_revival_kind(irn, EDGE_KIND_NORMAL, irg); + edges_node_revival_kind(irn, EDGE_KIND_BLOCK, irg); +} const ir_edge_t *(get_irn_out_edge_first_kind)(const ir_node *irn, ir_edge_kind_t kind) { return _get_irn_out_edge_first_kind(irn, kind);