X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firedges.c;h=a7b26aaa57c728760d45ae1bb7b7ff70f5544f5e;hb=eb08138c6b80c169945568e4414f491a9bc20388;hp=6b135f5dca907ef37b4f1e4a46067979973b2b52;hpb=ab614835df920444ebc6441e72bdcdcab6a41649;p=libfirm diff --git a/ir/ir/iredges.c b/ir/ir/iredges.c index 6b135f5dc..a7b26aaa5 100644 --- a/ir/ir/iredges.c +++ b/ir/ir/iredges.c @@ -1,3 +1,22 @@ +/* + * 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. + */ + /* * Project: libFIRM * File name: ir/ir/iredges.c @@ -7,7 +26,6 @@ * Created: 14.1.2005 * CVS-ID: $Id$ * Copyright: (c) 1998-2006 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. */ /** @@ -20,13 +38,6 @@ #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" @@ -38,6 +49,7 @@ #include "debug.h" #include "set.h" #include "bitset.h" +#include "xmalloc.h" /** * A function that allows for setting an edge. @@ -108,8 +120,10 @@ 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 @@ -162,9 +176,13 @@ 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; - 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)) @@ -265,108 +283,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(EDGE_SIZE); - ir_edge_t *edge; - - /* 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 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)); + if(tgt == old_tgt) + return; + + info = _get_irg_edge_info(irg, kind); + edges = info->edges; + templ = alloca(EDGE_SIZE); - /* 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; + /* 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 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; + 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). - */ + edge_change_cnt(old_tgt, kind, -1); + } + + /* If the edge was not found issue a warning on the debug stream */ else { - struct list_head *head = _get_irn_outs_head(tgt, kind); + msg = "edge to delete not found!\n"; + } + } /* if */ - assert(head->next && head->prev && - "target list head must have been initialized"); + /* + * 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); - /* 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"); + assert(head->next && head->prev && + "target list head must have been initialized"); - msg = "redirecting"; + /* 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"); - list_move(&edge->list, head); - edge_change_cnt(old_tgt, kind, -1); - } + msg = "redirecting"; - /* The old target was null, thus, the edge is newly created. */ - else { - edge = set_insert(edges, templ, EDGE_SIZE, edge_hash(templ)); + list_move(&edge->list, head); + edge_change_cnt(old_tgt, kind, -1); + } - 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"); + /* The old target was null, thus, the edge is newly created. */ + else { + edge = set_insert(edges, templ, EDGE_SIZE, edge_hash(templ)); - msg = "adding"; - list_add(&edge->list, head); + 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; + edge->edge_nr = ++last_edge_num; #endif /* DEBUG_libfirm */ - } + } - edge_change_cnt(tgt, kind, +1); - } /* else */ + edge_change_cnt(tgt, kind, +1); + } /* else */ - /* verify list heads */ - if (edges_dbg) { - if (tgt) - vrfy_list_head(tgt, kind); - if (old_tgt) - vrfy_list_head(old_tgt, kind); - } +#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)); } @@ -538,12 +563,12 @@ static void verify_set_presence(ir_node *irn, void *data) templ.pos = i; 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)); } } } @@ -619,10 +644,10 @@ static void clear_links(ir_node *irn, void *env) { struct build_walker *w = env; bitset_t *bs; - set_irn_link(irn, NULL); - - if (IGNORE_NODE(irn)) + if (IGNORE_NODE(irn)) { + set_irn_link(irn, NULL); return; + } bs = bitset_malloc(get_irg_last_idx(w->irg)); set_irn_link(irn, bs); @@ -654,6 +679,7 @@ static void verify_edge_counter(ir_node *irn, void *env) { int list_cnt; int ref_cnt; int edge_cnt; + unsigned long idx; const struct list_head *head; const struct list_head *pos; @@ -662,15 +688,28 @@ static void verify_edge_counter(ir_node *irn, void *env) { bs = get_irn_link(irn); list_cnt = 0; - ref_cnt = bitset_popcnt(bs); + 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) { - ir_edge_t *edge = list_entry(pos, ir_edge_t, list); - if (! is_Bad(edge->src)) - list_cnt++; + 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) { @@ -680,16 +719,15 @@ static void verify_edge_counter(ir_node *irn, void *env) { } if (ref_cnt != list_cnt) { - unsigned long idx; - w->problem_found = 1; - ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node(s), but %d edge(s) 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); - if (! is_Bad(edge->src)) - bitset_flip(bs, get_irn_idx(edge->src)); + bitset_flip(bs, get_irn_idx(edge->src)); } if (ref_cnt < list_cnt) @@ -703,6 +741,7 @@ static void verify_edge_counter(ir_node *irn, void *env) { ir_fprintf(stderr, " %+F", src); } fprintf(stderr, "\n"); +#endif } bitset_free(bs); @@ -715,9 +754,6 @@ int edges_verify(ir_graph *irg) { struct build_walker w; int problem_found = 0; - if (! edges_dbg) - return 0; - /* verify normal edges only */ problem_found = edges_verify_kind(irg, EDGE_KIND_NORMAL); @@ -728,6 +764,7 @@ int edges_verify(ir_graph *irg) { /* verify counter */ inc_irg_visited(irg); irg_walk_anchors(irg, clear_links, count_user, &w); + inc_irg_visited(irg); irg_walk_anchors(irg, NULL, verify_edge_counter, &w); return problem_found ? 1 : w.problem_found;