X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firedges.c;h=e09b3220b5ccc13fe370c861698c036bc55d3fef;hb=3398ae4a8b3cbf66cb0b274ddcd85a2ea863ece1;hp=a95942fa8634a7a2f75522d2a516b2d945407d04;hpb=32ea6ea0320f551448bb66e534e3351977464d42;p=libfirm diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c index a95942fa8..e09b3220b 100644 --- a/ir/ir/iredges.c +++ b/ir/ir/iredges.c @@ -57,11 +57,14 @@ #define SetRangeEmpty(ptr,size) memset(ptr, 0, (size) * sizeof((ptr)[0])) #define hashset_init ir_edgeset_init +void ir_edgeset_init_size(ir_edgeset_t *self, size_t size); #define hashset_init_size ir_edgeset_init_size #define hashset_destroy ir_edgeset_destroy #define hashset_insert ir_edgeset_insert #define hashset_remove ir_edgeset_remove +ir_edge_t *ir_edgeset_find(const ir_edgeset_t *self, const ir_edge_t*); #define hashset_find ir_edgeset_find +size_t ir_edgeset_size(const ir_edgeset_t *self); #define hashset_size ir_edgeset_size #define hashset_iterator_init ir_edgeset_iterator_init #define hashset_iterator_next ir_edgeset_iterator_next @@ -115,7 +118,7 @@ static const ir_edge_kind_info_t edge_kind_info[EDGE_KIND_LAST] = { { "dependency", set_irn_dep, 0, get_irn_deps, get_irn_dep } }; -#define foreach_tgt(irn, i, n, kind) for(i = edge_kind_info[kind].first_idx, n = edge_kind_info[kind].get_arity(irn); i < n; ++i) +#define foreach_tgt(irn, i, n, kind) for (i = edge_kind_info[kind].first_idx, n = edge_kind_info[kind].get_arity(irn); i < n; ++i) #define get_n(irn, pos, kind) (edge_kind_info[kind].get_n(irn, pos)) #define get_kind_str(kind) (edge_kind_info[kind].name) @@ -210,7 +213,7 @@ void edges_init_graph_kind(ir_graph *irg, ir_edge_kind_t kind) size_t amount = irg->estimated_node_count * 2; edges_used = 1; - if(info->allocated) { + if (info->allocated) { amount = ir_edgeset_size(&info->edges); ir_edgeset_destroy(&info->edges); obstack_free(&info->edges_obst, NULL); @@ -253,7 +256,7 @@ const ir_edge_t *get_irn_edge_kind(ir_graph *irg, const ir_node *src, int pos, i const ir_edge_t *get_irn_edge(ir_graph *irg, const ir_node *src, int pos) { const ir_edge_t *edge; - if((edge = get_irn_edge_kind(irg, src, pos, EDGE_KIND_NORMAL)) == NULL) + if ((edge = get_irn_edge_kind(irg, src, pos, EDGE_KIND_NORMAL)) == NULL) edge = get_irn_edge_kind(irg, src, pos, EDGE_KIND_BLOCK); return(edge); } @@ -270,6 +273,7 @@ static inline void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs) info->out_count += ofs; #if 0 + ir_graph *irg = get_irn_irg(tgt); assert(info->out_count >= 0); if (info->out_count == 0 && kind == EDGE_KIND_NORMAL) { /* tgt lost it's last user */ @@ -278,12 +282,12 @@ static inline void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs) for (i = get_irn_arity(tgt) - 1; i >= -1; --i) { ir_node *prev = get_irn_n(tgt, i); - edges_notify_edge(tgt, i, NULL, prev, current_ir_graph); + edges_notify_edge(tgt, i, NULL, prev, irg); } for (i = get_irn_deps(tgt) - 1; i >= 0; --i) { ir_node *prev = get_irn_dep(tgt, i); - edges_notify_edge_kind(tgt, i, NULL, prev, EDGE_KIND_DEP, current_ir_graph); + edges_notify_edge_kind(tgt, i, NULL, prev, EDGE_KIND_DEP, irg); } } @@ -294,7 +298,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 verify_list_head(ir_node *irn, ir_edge_kind_t kind) { int err = 0; int num = 0; @@ -324,11 +328,6 @@ 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; @@ -345,7 +344,6 @@ void edges_dump_kind(ir_graph *irg, ir_edge_kind_t kind) 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, @@ -425,7 +423,7 @@ void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, ir_edge_t *edge; if (list_empty(&info->free_edges)) { - edge = obstack_alloc(&info->edges_obst, EDGE_SIZE); + edge = (ir_edge_t*)obstack_alloc(&info->edges_obst, EDGE_SIZE); } else { edge = list_entry(info->free_edges.next, ir_edge_t, list); list_del(&edge->list); @@ -458,9 +456,9 @@ void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, /* verify list heads */ if (edges_dbg) { if (tgt) - vrfy_list_head(tgt, kind); + verify_list_head(tgt, kind); if (old_tgt) - vrfy_list_head(old_tgt, kind); + verify_list_head(old_tgt, kind); } #endif @@ -474,17 +472,13 @@ void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir } if (edges_activated_kind(irg, EDGE_KIND_BLOCK) && is_Block(src)) { - if (pos == -1) { - /* a MacroBlock edge: ignore it here */ - } else { - ir_node *bl_old = old_tgt ? get_nodes_block(skip_Proj(old_tgt)) : NULL; - ir_node *bl_tgt = NULL; + ir_node *bl_old = old_tgt ? get_nodes_block(skip_Proj(old_tgt)) : NULL; + ir_node *bl_tgt = NULL; - if (tgt) - bl_tgt = is_Bad(tgt) ? tgt : get_nodes_block(skip_Proj(tgt)); + if (tgt) + bl_tgt = is_Bad(tgt) ? tgt : get_nodes_block(skip_Proj(tgt)); - edges_notify_edge_kind(src, pos, bl_tgt, bl_old, EDGE_KIND_BLOCK, irg); - } + edges_notify_edge_kind(src, pos, bl_tgt, bl_old, EDGE_KIND_BLOCK, irg); } } @@ -538,19 +532,19 @@ static void edges_node_revival_kind(ir_node *irn, ir_edge_kind_t kind, ir_graph info->edges_built = 1; } -struct build_walker { +typedef struct build_walker { ir_graph *irg; ir_edge_kind_t kind; bitset_t *reachable; unsigned problem_found; -}; +} build_walker; /** * Post-Walker: notify all edges */ static void build_edges_walker(ir_node *irn, void *data) { - struct build_walker *w = data; + build_walker *w = (build_walker*)data; int i, n; ir_edge_kind_t kind = w->kind; ir_graph *irg = w->irg; @@ -570,9 +564,9 @@ static void build_edges_walker(ir_node *irn, void *data) */ static void init_lh_walker(ir_node *irn, void *data) { - struct build_walker *w = data; - ir_edge_kind_t kind = w->kind; - list_head *head = _get_irn_outs_head(irn, kind); + build_walker *w = (build_walker*)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)->edges_built = 0; _get_irn_edge_info(irn, kind)->out_count = 0; @@ -591,10 +585,10 @@ static void init_lh_walker(ir_node *irn, void *data) */ static void init_lh_walker_dep(ir_node *irn, void *data) { - struct build_walker *w = data; - ir_edge_kind_t kind = w->kind; - list_head *head = _get_irn_outs_head(irn, kind); - int i; + build_walker *w = (build_walker*)data; + ir_edge_kind_t kind = w->kind; + list_head *head = _get_irn_outs_head(irn, kind); + int i; INIT_LIST_HEAD(head); _get_irn_edge_info(irn, kind)->edges_built = 0; @@ -622,7 +616,10 @@ typedef struct visitor_info_t { */ static void visitor(ir_node *irn, void *data) { - visitor_info_t *info = data; + visitor_info_t *info = (visitor_info_t*)data; + + if (is_Deleted(irn)) + return; if (!irn_visited_else_mark(irn)) { info->visit(irn, info->data); @@ -708,7 +705,7 @@ void edges_reroute_kind(ir_node *from, ir_node *to, ir_edge_kind_t kind, ir_grap { set_edge_func_t *set_edge = edge_kind_info[kind].set_edge; - if(set_edge && edges_activated_kind(irg, kind)) { + if (set_edge && edges_activated_kind(irg, kind)) { struct list_head *head = _get_irn_outs_head(from, kind); DBG((dbg, LEVEL_5, "reroute from %+F to %+F\n", from, to)); @@ -723,8 +720,8 @@ void edges_reroute_kind(ir_node *from, ir_node *to, ir_edge_kind_t kind, ir_grap static void verify_set_presence(ir_node *irn, void *data) { - struct build_walker *w = data; - ir_edgeset_t *edges = &_get_irg_edge_info(w->irg, w->kind)->edges; + build_walker *w = (build_walker*)data; + ir_edgeset_t *edges = &_get_irg_edge_info(w->irg, w->kind)->edges; int i, n; foreach_tgt(irn, i, n, w->kind) { @@ -734,7 +731,7 @@ static void verify_set_presence(ir_node *irn, void *data) templ.pos = i; e = ir_edgeset_find(edges, &templ); - if(e != NULL) { + if (e != NULL) { e->present = 1; } else { w->problem_found = 1; @@ -748,13 +745,13 @@ static void verify_set_presence(ir_node *irn, void *data) static void verify_list_presence(ir_node *irn, void *data) { - struct build_walker *w = data; - const ir_edge_t *e; + build_walker *w = (build_walker*)data; + const ir_edge_t *e; bitset_set(w->reachable, get_irn_idx(irn)); /* check list heads */ - vrfy_list_head(irn, w->kind); + verify_list_head(irn, w->kind); foreach_out_edge_kind(irn, e, w->kind) { ir_node *tgt; @@ -821,8 +818,8 @@ int edges_verify_kind(ir_graph *irg, ir_edge_kind_t kind) */ static void clear_links(ir_node *irn, void *env) { - struct build_walker *w = env; - bitset_t *bs; + build_walker *w = (build_walker*)env; + bitset_t *bs; if (IGNORE_NODE(irn)) { set_irn_link(irn, NULL); @@ -845,7 +842,7 @@ static void count_user(ir_node *irn, void *env) first = -1; for (i = get_irn_arity(irn) - 1; i >= first; --i) { ir_node *op = get_irn_n(irn, i); - bitset_t *bs = get_irn_link(op); + bitset_t *bs = (bitset_t*)get_irn_link(op); if (bs) bitset_set(bs, get_irn_idx(irn)); @@ -857,19 +854,19 @@ static void count_user(ir_node *irn, void *env) */ static void verify_edge_counter(ir_node *irn, void *env) { - struct build_walker *w = env; + build_walker *w = (build_walker*)env; bitset_t *bs; int list_cnt; int ref_cnt; int edge_cnt; - unsigned long idx; + size_t idx; const struct list_head *head; const struct list_head *pos; if (IGNORE_NODE(irn)) return; - bs = get_irn_link(irn); + bs = (bitset_t*)get_irn_link(irn); list_cnt = 0; ref_cnt = 0; edge_cnt = _get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count; @@ -952,18 +949,18 @@ int edges_verify(ir_graph *irg) return problem_found ? 1 : w.problem_found; } -struct pass_t { +typedef struct pass_t { ir_graph_pass_t pass; unsigned assert_on_problem; -}; +} pass_t; /** * 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); + pass_t *pass = (pass_t*)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; @@ -972,7 +969,7 @@ static int edges_verify_wrapper(ir_graph *irg, void *context) /* 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); + pass_t *pass = XMALLOCZ(pass_t); def_graph_pass_constructor( &pass->pass, name ? name : "edges_verify", edges_verify_wrapper); @@ -988,7 +985,6 @@ ir_graph_pass_t *irg_verify_edges_pass(const char *name, unsigned assert_on_prob void init_edges(void) { FIRM_DBG_REGISTER(dbg, DBG_EDGES); - /* firm_dbg_set_mask(dbg, -1); */ } void edges_init_dbg(int do_dbg) @@ -1077,22 +1073,47 @@ int (get_irn_n_edges_kind)(const ir_node *irn, ir_edge_kind_t kind) return _get_irn_n_edges_kind(irn, kind); } -void dump_all_out_edges(ir_node *irn) +static void irg_walk_edges2(ir_node *node, irg_walk_func *pre, + irg_walk_func *post, void *env) { - int i; - for (i = 0; i < EDGE_KIND_LAST; ++i) { - const ir_edge_t *edge; + const ir_edge_t *edge, *next; - printf("kind \"%s\"\n", get_kind_str(i)); - foreach_out_edge_kind(irn, edge, i) { - ir_printf("\t%+F(%d)\n", edge->src, edge->pos); - } + if (irn_visited(node)) + return; + mark_irn_visited(node); + + if (pre != NULL) + pre(node, env); + + foreach_out_edge_kind_safe(node, edge, next, EDGE_KIND_NORMAL) { + /* find the corresponding successor block. */ + ir_node *pred = get_edge_src_irn(edge); + irg_walk_edges2(pred, pre, post, env); } + + if (post != NULL) + post(node, env); +} + +void irg_walk_edges(ir_node *node, irg_walk_func *pre, irg_walk_func *post, + void *env) +{ + ir_graph *irg = get_irn_irg(node); + + assert(edges_activated(irg)); + assert(is_Block(node)); + + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); + + inc_irg_visited(irg); + irg_walk_edges2(node, pre, post, env); + + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); } -static void irg_block_edges_walk2(ir_node *bl, - irg_walk_func *pre, irg_walk_func *post, - void *env) { +static void irg_block_edges_walk2(ir_node *bl, irg_walk_func *pre, + irg_walk_func *post, void *env) +{ const ir_edge_t *edge, *next; if (!Block_block_visited(bl)) { @@ -1112,17 +1133,18 @@ static void irg_block_edges_walk2(ir_node *bl, } } -void irg_block_edges_walk(ir_node *node, - irg_walk_func *pre, irg_walk_func *post, - void *env) { +void irg_block_edges_walk(ir_node *node, irg_walk_func *pre, + irg_walk_func *post, void *env) +{ + ir_graph *irg = get_irn_irg(node); - assert(edges_activated(current_ir_graph)); + assert(edges_activated(irg)); assert(is_Block(node)); - ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_VISITED); + ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED); - inc_irg_block_visited(current_ir_graph); + inc_irg_block_visited(irg); irg_block_edges_walk2(node, pre, post, env); - ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_VISITED); + ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED); }