X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firedges.c;h=84a442ee2b0b4547f8db74beae9b1f2eef1f990e;hb=92869d69702fc0fd8e77832b9b68c60cb0d3e82a;hp=4939256310e84244c4b37f88577e62237c3a6e41;hpb=d8a91549217c6efdb09a0dfd23c6803e346afea4;p=libfirm diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c index 493925631..84a442ee2 100644 --- a/ir/ir/iredges.c +++ b/ir/ir/iredges.c @@ -1,32 +1,36 @@ /* - * Project: libFIRM - * File name: ir/ir/iredges.c - * Purpose: Always available outs. - * Author: Sebastian Hack - * Modified by: Michael Beck, Andreas Schoesser - * Created: 14.1.2005 - * CVS-ID: $Id$ - * Copyright: (c) 1998-2006 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. */ /** - * Always available outs. - * @author Sebastian Hack - * @date 14.1.2005 + * @file + * @brief Always available outs. + * @author Sebastian Hack, Michael Beck, Andreas Schoesser + * @date 14.1.2005 + * @version $Id$ + * @summary + * 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 -#ifdef HAVE_ALLOCA_H -#include -#endif -#ifdef HAVE_MALLOC_H -#include -#endif - #include "irnode_t.h" #include "iropt_t.h" #include "iredgekinds.h" @@ -37,12 +41,14 @@ #include "irhooks.h" #include "debug.h" #include "set.h" +#include "bitset.h" +#include "xmalloc.h" /** -* A function that allows for setting an edge. -* This abstraction is necessary since different edge kind have -* different methods of setting edges. -*/ + * A function that allows for setting an edge. + * This abstraction is necessary since different edge kind have + * different methods of setting edges. + */ typedef void (set_edge_func_t)(ir_node *src, int pos, ir_node *tgt); typedef int (get_edge_src_arity_func_t)(const ir_node *src); @@ -52,8 +58,8 @@ typedef int (get_edge_src_first_func_t)(const ir_node *src); typedef ir_node *(get_edge_src_n_func_t)(const ir_node *src, int pos); /** -* Additional data for an edge kind. -*/ + * Additional data for an edge kind. + */ typedef struct { const char *name; set_edge_func_t *set_edge; @@ -64,6 +70,7 @@ typedef struct { static int get_zero(const ir_node *irn) { + (void) irn; return 0; } @@ -95,6 +102,10 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg;) */ static int edges_used = 0; +/** + * Summed size of all users private data + */ + static int edges_private_size = 0; #define EDGE_SIZE (sizeof(ir_edge_t) + edges_private_size) @@ -103,6 +114,27 @@ static int edges_private_size = 0; */ static int edges_dbg = 0; +#ifdef DEBUG_libfirm +/* a static variable holding the last number assigned to a new edge */ +static long last_edge_num = -1; +#endif + +static INLINE long edge_get_id(const ir_edge_t *e) { +#ifdef DEBUG_libfirm + return e->edge_nr; +#else /* DEBUG_libfirm */ + return (long)e; +#endif /* DEBUG_libfirm */ +} + +/** + * Announce to reserve extra space for each edge to be allocated. + * @Param n: Size of the space to reserve + * @ Returns: Offset at which the private data will begin + * Several users can reserve extra space for private usage. + * Each user has to remember his given offset and the size of his private data. + * To be called before FIRM is initialized. + */ int edges_register_private_data(size_t n) { int res = edges_private_size; @@ -115,16 +147,17 @@ int edges_register_private_data(size_t n) /** * 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) { irg_edge_info_t *info = _get_irg_edge_info(irg, EDGE_KIND_NORMAL); - set_entry *entry; + ir_edge_t *edge; - foreach_set(info->edges, entry) + foreach_set(info->edges, edge) { - ir_edge_t *edge = (ir_edge_t *) entry->dptr; memset(edge + sizeof(*edge) + offset, 0, size); } } @@ -137,9 +170,14 @@ static int edge_cmp(const void *p1, const void *p2, size_t len) { const ir_edge_t *e1 = p1; const ir_edge_t *e2 = p2; - int res = e1->src == e2->src && e1->pos == e2->pos; + (void) len; - return ! res; + if(e1->src != e2->src) + return 1; + if(e1->pos != e1->pos) + return 1; + + return 0; } #define edge_hash(edge) (TIMES37((edge)->pos) + HASH_PTR((edge)->src)) @@ -179,7 +217,6 @@ const ir_edge_t *get_irn_edge_kind(ir_graph *irg, const ir_node *src, int pos, i key.src = (ir_node *)src; key.pos = pos; - //return set_find(info->edges, &key, sizeof(key), edge_hash(&key)); return set_find(info->edges, &key, EDGE_SIZE, edge_hash(&key)); } @@ -225,9 +262,9 @@ static INLINE void vrfy_list_head(ir_node *irn, ir_edge_kind_t kind) { ir_fprintf(stderr, "EDGE Verifier: edge list broken (self loop not to head) for %+F:\n", irn); fprintf(stderr, "- at list entry %d\n", num); if (edge->invalid) - fprintf(stderr, "- edge is invalid\n"); - if (edge->src); - ir_fprintf(stderr, "- edge %+F(%d)\n", edge->src, edge->pos); + fprintf(stderr, "- edge(%ld) is invalid\n", edge_get_id(edge)); + if (edge->src) + ir_fprintf(stderr, "- edge(%ld) %+F(%d)\n", edge_get_id(edge), edge->src, edge->pos); err = 1; break; } @@ -241,105 +278,115 @@ static INLINE void vrfy_list_head(ir_node *irn, ir_edge_kind_t kind) { } /* 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, ir_graph *irg) +void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt, + ir_node *old_tgt, ir_edge_kind_t kind, + ir_graph *irg) { const char *msg = ""; + irg_edge_info_t *info; + set *edges; + ir_edge_t *templ; + ir_edge_t *edge; assert(edges_activated_kind(irg, kind)); /* * Only do something, if the old and new target differ. */ - if(tgt != old_tgt) { - irg_edge_info_t *info = _get_irg_edge_info(irg, kind); - set *edges = info->edges; - //ir_edge_t *templ = alloca(sizeof(templ[0])); - ir_edge_t *templ = alloca(EDGE_SIZE); - ir_edge_t *edge; - - /* Initialize the edge template to search in the set. */ - //memset(templ, 0, sizeof(templ[0])); - memset(templ, 0, EDGE_SIZE); - templ->src = src; - templ->pos = pos; - templ->invalid = 0; - templ->present = 0; - templ->kind = kind; - DEBUG_ONLY(templ->src_nr = get_irn_node_nr(src)); - - /* - * 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[0]), edge_hash(templ)); - edge = set_find(edges, templ, EDGE_SIZE, edge_hash(templ)); + if(tgt == old_tgt) + return; - /* mark the edge invalid if it was found */ - if (edge) { - msg = "deleting"; - list_del(&edge->list); - edge->invalid = 1; - edge->pos = -2; - edge->src = NULL; - edge_change_cnt(old_tgt, kind, -1); - } - - /* If the edge was not found issue a warning on the debug stream */ - else { - 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 { - struct list_head *head = _get_irn_outs_head(tgt, kind); + info = _get_irg_edge_info(irg, kind); + edges = info->edges; + templ = alloca(EDGE_SIZE); - assert(head->next && head->prev && - "target list head must have been initialized"); + /* Initialize the edge template to search in the set. */ + memset(templ, 0, EDGE_SIZE); + templ->src = src; + templ->pos = pos; + templ->invalid = 0; + templ->present = 0; + templ->kind = kind; + DEBUG_ONLY(templ->src_nr = get_irn_node_nr(src)); - /* If the old target is not null, the edge is moved. */ - if (old_tgt) { - edge = set_find(edges, templ, EDGE_SIZE, edge_hash(templ)); - assert(edge && "edge to redirect not found!"); - assert(! edge->invalid && "Invalid edge encountered"); + /* + * If the target is NULL, the edge shall be deleted. + */ + if (tgt == NULL) { + /* search the edge in the set. */ + edge = set_find(edges, templ, EDGE_SIZE, edge_hash(templ)); + + /* mark the edge invalid if it was found */ + if (edge) { + msg = "deleting"; + list_del(&edge->list); + edge->invalid = 1; + edge->pos = -2; + edge->src = NULL; +#ifdef DEBUG_libfirm + 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 { + 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 { + struct list_head *head = _get_irn_outs_head(tgt, kind); - msg = "redirecting"; + assert(head->next && head->prev && + "target list head must have been initialized"); - list_move(&edge->list, head); - edge_change_cnt(old_tgt, kind, -1); - } + /* If the old target is not null, the edge is moved. */ + if (old_tgt) { + edge = set_find(edges, templ, EDGE_SIZE, edge_hash(templ)); + assert(edge && "edge to redirect not found!"); + assert(! edge->invalid && "Invalid edge encountered"); - /* The old target was null, thus, the edge is newly created. */ - else { - edge = set_insert(edges, templ, EDGE_SIZE, edge_hash(templ)); + msg = "redirecting"; - 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"); + list_move(&edge->list, head); + edge_change_cnt(old_tgt, kind, -1); + } - msg = "adding"; - list_add(&edge->list, head); - } + /* The old target was null, thus, the edge is newly created. */ + else { + edge = set_insert(edges, templ, EDGE_SIZE, edge_hash(templ)); - edge_change_cnt(tgt, kind, +1); - } /* else */ + 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"); - /* verify list heads */ - if (edges_dbg) { - if (tgt) - vrfy_list_head(tgt, kind); - if (old_tgt) - vrfy_list_head(old_tgt, kind); + msg = "adding"; + list_add(&edge->list, head); +#ifdef DEBUG_libfirm + edge->edge_nr = ++last_edge_num; +#endif /* DEBUG_libfirm */ } + + edge_change_cnt(tgt, kind, +1); + } /* else */ + +#ifndef DEBUG_libfirm + /* verify list heads */ + if (edges_dbg) { + if (tgt) + vrfy_list_head(tgt, kind); + if (old_tgt) + vrfy_list_head(old_tgt, kind); } +#endif - /* If the target and the old target are equal, nothing is done. */ DBG((dbg, LEVEL_5, "announce out edge: %+F %d-> %+F(%+F): %s\n", src, pos, tgt, old_tgt, msg)); } @@ -380,6 +427,7 @@ void edges_node_deleted_kind(ir_node *old, ir_edge_kind_t kind, ir_graph *irg) struct build_walker { ir_graph *irg; ir_edge_kind_t kind; + bitset_t *reachable; unsigned problem_found; }; @@ -388,9 +436,9 @@ struct build_walker { */ static void build_edges_walker(ir_node *irn, void *data) { struct build_walker *w = data; - int i, n; + int i, n; - if(!edges_activated_kind(w->irg, w->kind)) + if (! edges_activated_kind(w->irg, w->kind)) return; foreach_tgt(irn, i, n, w->kind) @@ -450,8 +498,6 @@ void edges_activate_kind(ir_graph *irg, ir_edge_kind_t kind) info->activated = 1; edges_init_graph_kind(irg, kind); - //irg_walk_graph(irg, init_lh_walker, build_edges_walker, &w); - inc_irg_visited(irg); irg_walk_anchors(irg, init_lh_walker, build_edges_walker, &w); visit_all_identities(irg, visitor, &w); } @@ -509,13 +555,13 @@ static void verify_set_presence(ir_node *irn, void *data) templ.src = irn; templ.pos = i; - //e = set_find(edges, &templ, sizeof(templ), edge_hash(&templ)); e = set_find(edges, &templ, EDGE_SIZE, edge_hash(&templ)); - if(e != NULL) + if(e != NULL) { e->present = 1; - else { + } else { w->problem_found = 1; - ir_fprintf(stderr, "Edge Verifier: edge %+F,%d (kind: \"%s\") is missing\n", irn, i, get_kind_str(w->kind)); + ir_fprintf(stderr, "Edge Verifier: edge %+F,%d -> %+F (kind: \"%s\") is missing\n", + irn, i, get_n(irn, i, w->kind), get_kind_str(w->kind)); } } } @@ -525,15 +571,27 @@ static void verify_list_presence(ir_node *irn, void *data) struct build_walker *w = data; const ir_edge_t *e; + bitset_set(w->reachable, get_irn_idx(irn)); + /* check list heads */ vrfy_list_head(irn, w->kind); foreach_out_edge_kind(irn, e, w->kind) { - ir_node *tgt = get_n(e->src, e->pos, w->kind); + ir_node *tgt; + + if (w->kind == EDGE_KIND_NORMAL && get_irn_arity(e->src) <= e->pos) { + w->problem_found = 1; + ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F -> %+F recorded at src position %d, but src has arity %d\n", + edge_get_id(e), e->src, irn, e->pos, get_irn_arity(e->src)); + continue; + } + + tgt = get_n(e->src, e->pos, w->kind); + if (irn != tgt) { w->problem_found = 1; - ir_fprintf(stderr, "Edge Verifier: edge %+F,%d (kind \"%s\") is no out edge of %+F but of %+F\n", - e->src, e->pos, get_kind_str(w->kind), irn, tgt); + ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d (kind \"%s\") is no out edge of %+F but of %+F\n", + edge_get_id(e), e->src, e->pos, get_kind_str(w->kind), irn, tgt); } } } @@ -546,6 +604,7 @@ int edges_verify_kind(ir_graph *irg, ir_edge_kind_t kind) w.irg = irg; w.kind = kind; + w.reachable = bitset_alloca(get_irg_last_idx(irg)); w.problem_found = 0; /* Clear the present bit in all edges available. */ @@ -560,23 +619,31 @@ int edges_verify_kind(ir_graph *irg, ir_edge_kind_t kind) * edge set is wrong. */ for (e = set_first(edges); e; e = set_next(edges)) { - if (! e->invalid && ! e->present) { + if (! e->invalid && ! e->present && bitset_is_set(w.reachable, get_irn_idx(e->src))) { w.problem_found = 1; - ir_fprintf(stderr, "Edge Verifier: edge %+F,%d is superfluous\n", e->src, e->pos); + ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d is superfluous\n", edge_get_id(e), e->src, e->pos); } } return w.problem_found; } +#define IGNORE_NODE(irn) (is_Bad((irn)) || is_Block((irn))) + /** * Clear link field of all nodes. */ static void clear_links(ir_node *irn, void *env) { - if (is_Block(irn)) + struct build_walker *w = env; + bitset_t *bs; + + if (IGNORE_NODE(irn)) { + set_irn_link(irn, NULL); return; + } - set_irn_link(irn, 0); + bs = bitset_malloc(get_irg_last_idx(w->irg)); + set_irn_link(irn, bs); } /** @@ -584,13 +651,16 @@ static void clear_links(ir_node *irn, void *env) { */ static void count_user(ir_node *irn, void *env) { int i; + int first; + (void) env; - for (i = get_irn_arity(irn) - 1; i >= 0; --i) { - ir_node *op = get_irn_n(irn, i); - int cnt = (int)get_irn_link(op); + first = get_irn_first(irn); + 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); - cnt++; - set_irn_link(op, (void *)cnt); + if (bs) + bitset_set(bs, get_irn_idx(irn)); } } @@ -599,55 +669,95 @@ static void count_user(ir_node *irn, void *env) { */ static void verify_edge_counter(ir_node *irn, void *env) { struct build_walker *w = env; - int list_cnt = 0; - int ref_cnt = (int)get_irn_link(irn); - int edge_cnt = _get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count; - const struct list_head *head = _get_irn_outs_head(irn, EDGE_KIND_NORMAL); + bitset_t *bs; + int list_cnt; + int ref_cnt; + int edge_cnt; + unsigned long idx; + const struct list_head *head; const struct list_head *pos; - if (is_Block(irn)) + if (IGNORE_NODE(irn)) return; + bs = get_irn_link(irn); + list_cnt = 0; + ref_cnt = 0; + edge_cnt = _get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count; + head = _get_irn_outs_head(irn, EDGE_KIND_NORMAL); + /* We can iterate safely here, list heads have already been verified. */ - list_for_each(pos, head) + list_for_each(pos, head) { list_cnt++; + } + + /* check all nodes that reference us and count edges that point number + * of ins that actually point to us */ + ref_cnt = 0; + bitset_foreach(bs, idx) { + int i, arity; + ir_node *src = get_idx_irn(w->irg, idx); + + arity = get_irn_arity(src); + for(i = 0; i < arity; ++i) { + ir_node *in = get_irn_n(src, i); + if(in == irn) + ref_cnt++; + } + } if (edge_cnt != list_cnt) { w->problem_found = 1; - ir_fprintf(stderr, "Edge Verifier: edge count is %d, but %d edges are recorded in list at %+F\n", + ir_fprintf(stderr, "Edge Verifier: edge count is %d, but %d edge(s) are recorded in list at %+F\n", edge_cnt, list_cnt, irn); } if (ref_cnt != list_cnt) { w->problem_found = 1; - ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node, but %d edges recorded in list\n", + ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node(s), but the list contains %d edge(s)\n", irn, ref_cnt, list_cnt); + + /* Matze: buggy if a node has multiple ins pointing at irn */ +#if 0 + list_for_each(pos, head) { + ir_edge_t *edge = list_entry(pos, ir_edge_t, list); + bitset_flip(bs, get_irn_idx(edge->src)); + } + + if (ref_cnt < list_cnt) + fprintf(stderr," following nodes are recorded in list, but not as user:\n"); + else + fprintf(stderr," following nodes are user, but not recorded in list:\n"); + + fprintf(stderr," "); + bitset_foreach(bs, idx) { + ir_node *src = get_idx_irn(w->irg, idx); + ir_fprintf(stderr, " %+F", src); + } + fprintf(stderr, "\n"); +#endif } + + bitset_free(bs); } /** * Verifies the out edges of an irg. */ int edges_verify(ir_graph *irg) { - int i; struct build_walker w; - int problem_found = 0; + int problem_found = 0; - /* verify all edge kinds */ -// for (i = 0; i < EDGE_KIND_LAST; ++i) { -// int res = edges_verify_kind(irg, i); -// problem_found = problem_found ? 1 : res; -// } -// problem_found = edges_verify_kind(irg, EDGE_KIND_NORMAL); + /* verify normal edges only */ + problem_found = edges_verify_kind(irg, EDGE_KIND_NORMAL); w.irg = irg; w.kind = EDGE_KIND_NORMAL; w.problem_found = 0; /* verify counter */ - irg_walk_graph(irg, clear_links, count_user, NULL); - irg_walk_anchors(irg, clear_links, count_user, NULL); - irg_walk_graph(irg, NULL, verify_edge_counter, &w); + irg_walk_anchors(irg, clear_links, count_user, &w); + irg_walk_anchors(irg, NULL, verify_edge_counter, &w); return problem_found ? 1 : w.problem_found; }