nsz Git - libfirm/blob - ir/ir/iredges.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/iredges.c
   4  * Purpose:     Always available outs.
   5  * Author:      Sebastian Hack
   6  * Modified by: Michael Beck, Andreas Schoesser
   7  * Created:     14.1.2005
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2006 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14  * Always available outs.
  15  * @author Sebastian Hack
  16  * @date 14.1.2005
  17  */
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include <config.h>
  21 #endif
  22
  23 #ifdef HAVE_ALLOCA_H
  24 #include <alloca.h>
  25 #endif
  26 #ifdef HAVE_MALLOC_H
  27 #include <malloc.h>
  28 #endif
  29
  30 #include "irnode_t.h"
  31 #include "iropt_t.h"
  32 #include "iredgekinds.h"
  33 #include "iredges_t.h"
  34 #include "irgwalk.h"
  35 #include "irdump_t.h"
  36 #include "irprintf.h"
  37 #include "irhooks.h"
  38 #include "debug.h"
  39 #include "set.h"
  40 #include "bitset.h"
  41
  42 /**
  43 * A function that allows for setting an edge.
  44 * This abstraction is necessary since different edge kind have
  45 * different methods of setting edges.
  46 */
  47 typedef void (set_edge_func_t)(ir_node *src, int pos, ir_node *tgt);
  48
  49 typedef int (get_edge_src_arity_func_t)(const ir_node *src);
  50
  51 typedef int (get_edge_src_first_func_t)(const ir_node *src);
  52
  53 typedef ir_node *(get_edge_src_n_func_t)(const ir_node *src, int pos);
  54
  55 /**
  56 * Additional data for an edge kind.
  57 */
  58 typedef struct {
  59         const char                *name;
  60         set_edge_func_t           *set_edge;
  61         get_edge_src_first_func_t *get_first;
  62         get_edge_src_arity_func_t *get_arity;
  63         get_edge_src_n_func_t     *get_n;
  64 } ir_edge_kind_info_t;
  65
  66 static int get_zero(const ir_node *irn)
  67 {
  68         return 0;
  69 }
  70
  71 static int get_irn_first(const ir_node *irn)
  72 {
  73         return 0 - !is_Block(irn);
  74 }
  75
  76 static ir_node *get_block_n(const ir_node *irn, int pos)
  77 {
  78         return is_Block(irn) ? get_Block_cfgpred_block((ir_node *) irn, pos) : 0;
  79 }
  80
  81 static const ir_edge_kind_info_t edge_kind_info[EDGE_KIND_LAST] = {
  82         { "normal"     , set_irn_n,   get_irn_first, get_irn_arity,  get_irn_n   },
  83         { "block succs", NULL,        get_zero,      get_irn_arity,  get_block_n },
  84         { "dependency",  set_irn_dep, get_zero,      get_irn_deps,   get_irn_dep }
  85 };
  86
  87 #define foreach_tgt(irn, i, n, kind) for(i = edge_kind_info[kind].get_first(irn), n = edge_kind_info[kind].get_arity(irn); i < n; ++i)
  88 #define get_n(irn, pos, kind)        (edge_kind_info[kind].get_n(irn, pos))
  89 #define get_kind_str(kind)           (edge_kind_info[kind].name)
  90
  91 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  92
  93 /**
  94  * This flag is set to 1, if the edges get initialized for an irg.
  95  * Then register additional data is forbidden.
  96  */
  97 static int edges_used = 0;
  98
  99 /**
 100  * Summed size of all users private data
 101  */
 102
 103 static int edges_private_size = 0;
 104 #define EDGE_SIZE (sizeof(ir_edge_t) + edges_private_size)
 105
 106 /**
 107  * If set to 1, the list heads are checked every time an edge is changed.
 108  */
 109 static int edges_dbg = 0;
 110
 111 #ifdef DEBUG_libfirm
 112 /* a static variable holding the last number assigned to a new edge */
 113 static long last_edge_num = -1;
 114 #endif
 115
 116 static INLINE long edge_get_id(const ir_edge_t *e) {
 117 #ifdef DEBUG_libfirm
 118         return e->edge_nr;
 119 #else /* DEBUG_libfirm */
 120         return (long)e;
 121 #endif /* DEBUG_libfirm */
 122 }
 123
 124 /**
 125  * Announce to reserve extra space for each edge to be allocated.
 126  * @Param n: Size of the space to reserve
 127  * @ Returns: Offset at which the private data will begin
 128  * Several users can reserve extra space for private usage.
 129  * Each user has to remember his given offset and the size of his private data.
 130  * To be called before FIRM is initialized.
 131  */
 132 int edges_register_private_data(size_t n)
 133 {
 134         int res = edges_private_size;
 135
 136         assert(!edges_used && "you cannot register private edge data, if edges have been initialized");
 137
 138         edges_private_size += n;
 139         return res;
 140 }
 141
 142 /**
 143  * Reset the user's private data at offset 'offset'
 144  * The user has to remember his offset and the size of his data!
 145  * Caution: Using wrong values here can destroy other users private data!
 146  */
 147
 148 void edges_reset_private_data(ir_graph *irg, int offset, size_t size)
 149 {
 150         irg_edge_info_t *info = _get_irg_edge_info(irg, EDGE_KIND_NORMAL);
 151         ir_edge_t       *edge;
 152
 153         foreach_set(info->edges, edge)
 154         {
 155                 memset(edge + sizeof(*edge) + offset, 0, size);
 156         }
 157 }
 158
 159 #define TIMES37(x) (((x) << 5) + ((x) << 2) + (x))
 160
 161 #define get_irn_out_list_head(irn) (&get_irn_out_info(irn)->outs)
 162
 163 static int edge_cmp(const void *p1, const void *p2, size_t len)
 164 {
 165         const ir_edge_t *e1 = p1;
 166         const ir_edge_t *e2 = p2;
 167
 168         if(e1->src != e2->src)
 169                 return 1;
 170         if(e1->pos != e1->pos)
 171                 return 1;
 172
 173         return 0;
 174 }
 175
 176 #define edge_hash(edge) (TIMES37((edge)->pos) + HASH_PTR((edge)->src))
 177
 178 /**
 179  * Initialize the out information for a graph.
 180  * @note Dead node elimination can call this on an already initialized graph.
 181  */
 182 void edges_init_graph_kind(ir_graph *irg, ir_edge_kind_t kind)
 183 {
 184         if(edges_activated_kind(irg, kind)) {
 185                 irg_edge_info_t *info = _get_irg_edge_info(irg, kind);
 186                 int amount = 2048;
 187
 188                 edges_used = 1;
 189                 if(info->edges) {
 190                         amount = set_count(info->edges);
 191                         del_set(info->edges);
 192                 }
 193                 info->edges = new_set(edge_cmp, amount);
 194         }
 195 }
 196
 197 /**
 198  * Get the edge object of an outgoing edge at a node.
 199  * @param   irg The graph, the node is in.
 200  * @param   src The node at which the edge originates.
 201  * @param   pos The position of the edge.
 202  * @return      The corresponding edge object or NULL,
 203  *              if no such edge exists.
 204  */
 205 const ir_edge_t *get_irn_edge_kind(ir_graph *irg, const ir_node *src, int pos, ir_edge_kind_t kind)
 206 {
 207         if (edges_activated_kind(irg, kind)) {
 208                 irg_edge_info_t *info = _get_irg_edge_info(irg, kind);
 209                 ir_edge_t       key;
 210
 211                 key.src = (ir_node *)src;
 212                 key.pos = pos;
 213                 return set_find(info->edges, &key, EDGE_SIZE, edge_hash(&key));
 214         }
 215
 216         return NULL;
 217 }
 218
 219 /**
 220  * Get the edge object of an outgoing edge at a node.
 221  * Looks for an edge for all kinds.
 222  */
 223
 224 const ir_edge_t *get_irn_edge(ir_graph *irg, const ir_node *src, int pos)
 225 {
 226         const ir_edge_t *edge;
 227         if((edge = get_irn_edge_kind(irg, src, pos, EDGE_KIND_NORMAL)) == NULL)
 228                 edge = get_irn_edge_kind(irg, src, pos, EDGE_KIND_BLOCK);
 229         return(edge);
 230 }
 231
 232 /**
 233  * Change the out count
 234  */
 235 static INLINE void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs) {
 236         irn_edge_info_t *info = _get_irn_edge_info(tgt, kind);
 237         info->out_count += ofs;
 238 }
 239
 240 /**
 241  * Verify the edge list of a node, ie. ensure it's a loop:
 242  * head -> e_1 -> ... -> e_n -> head
 243  */
 244 static INLINE void vrfy_list_head(ir_node *irn, ir_edge_kind_t kind) {
 245         int                    err       = 0;
 246         int                    num       = 0;
 247         pset                   *lh_set   = pset_new_ptr(16);
 248         const struct list_head *head     = _get_irn_outs_head(irn, kind);
 249         const struct list_head *pos;
 250
 251         list_for_each(pos, head) {
 252                 if (pset_find_ptr(lh_set, pos)) {
 253                         const ir_edge_t *edge = list_entry(pos, ir_edge_t, list);
 254
 255                         ir_fprintf(stderr, "EDGE Verifier: edge list broken (self loop not to head) for %+F:\n", irn);
 256                         fprintf(stderr, "- at list entry %d\n", num);
 257                         if (edge->invalid)
 258                                 fprintf(stderr, "- edge(%ld) is invalid\n", edge_get_id(edge));
 259                         if (edge->src);
 260                                 ir_fprintf(stderr, "- edge(%ld) %+F(%d)\n", edge_get_id(edge), edge->src, edge->pos);
 261                         err = 1;
 262                         break;
 263                 }
 264                 num++;
 265                 pset_insert_ptr(lh_set, pos);
 266         }
 267
 268         del_pset(lh_set);
 269
 270         assert(err == 0);
 271 }
 272
 273 /* The edge from (src, pos) -> old_tgt is redirected to tgt */
 274 void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt,
 275                             ir_node *old_tgt, ir_edge_kind_t kind,
 276                             ir_graph *irg)
 277 {
 278         const char *msg = "";
 279         irg_edge_info_t *info;
 280         set *edges;
 281         ir_edge_t *templ;
 282         ir_edge_t *edge;
 283
 284         assert(edges_activated_kind(irg, kind));
 285
 286         /*
 287          * Only do something, if the old and new target differ.
 288          */
 289         if(tgt == old_tgt)
 290                 return;
 291
 292         info  = _get_irg_edge_info(irg, kind);
 293         edges = info->edges;
 294         templ = alloca(EDGE_SIZE);
 295
 296         /* Initialize the edge template to search in the set. */
 297         memset(templ, 0, EDGE_SIZE);
 298         templ->src     = src;
 299         templ->pos     = pos;
 300         templ->invalid = 0;
 301         templ->present = 0;
 302         templ->kind    = kind;
 303         DEBUG_ONLY(templ->src_nr = get_irn_node_nr(src));
 304
 305         /*
 306          * If the target is NULL, the edge shall be deleted.
 307          */
 308         if (tgt == NULL) {
 309                 /* search the edge in the set. */
 310                 edge = set_find(edges, templ, EDGE_SIZE, edge_hash(templ));
 311
 312                 /* mark the edge invalid if it was found */
 313                 if (edge) {
 314                         msg = "deleting";
 315                         list_del(&edge->list);
 316                         edge->invalid = 1;
 317                         edge->pos = -2;
 318                         edge->src = NULL;
 319 #ifdef DEBUG_libfirm
 320                         edge->edge_nr = -1;
 321 #endif /* DEBUG_libfirm */
 322                         edge_change_cnt(old_tgt, kind, -1);
 323                 }
 324
 325                 /* If the edge was not found issue a warning on the debug stream */
 326                 else {
 327                         msg = "edge to delete not found!\n";
 328                 }
 329         } /* if */
 330
 331         /*
 332          * The target is not NULL and the old target differs
 333          * from the new target, the edge shall be moved (if the
 334          * old target was != NULL) or added (if the old target was
 335          * NULL).
 336          */
 337         else {
 338                 struct list_head *head = _get_irn_outs_head(tgt, kind);
 339
 340                 assert(head->next && head->prev &&
 341                                 "target list head must have been initialized");
 342
 343                 /* If the old target is not null, the edge is moved. */
 344                 if (old_tgt) {
 345                         edge = set_find(edges, templ, EDGE_SIZE, edge_hash(templ));
 346                         assert(edge && "edge to redirect not found!");
 347                         assert(! edge->invalid && "Invalid edge encountered");
 348
 349                         msg = "redirecting";
 350
 351                         list_move(&edge->list, head);
 352                         edge_change_cnt(old_tgt, kind, -1);
 353                 }
 354
 355                 /* The old target was null, thus, the edge is newly created. */
 356                 else {
 357                         edge = set_insert(edges, templ, EDGE_SIZE, edge_hash(templ));
 358
 359                         assert(! edge->invalid && "Freshly inserted edge is invalid?!?");
 360                         assert(edge->list.next == NULL && edge->list.prev == NULL &&
 361                                 "New edge must not have list head initialized");
 362
 363                         msg = "adding";
 364                         list_add(&edge->list, head);
 365 #ifdef DEBUG_libfirm
 366                         edge->edge_nr = ++last_edge_num;
 367 #endif /* DEBUG_libfirm */
 368                 }
 369
 370                 edge_change_cnt(tgt, kind, +1);
 371         } /* else */
 372
 373         /* verify list heads */
 374         if (edges_dbg) {
 375                 if (tgt)
 376                         vrfy_list_head(tgt, kind);
 377                 if (old_tgt)
 378                         vrfy_list_head(old_tgt, kind);
 379         }
 380
 381         DBG((dbg, LEVEL_5, "announce out edge: %+F %d-> %+F(%+F): %s\n", src, pos, tgt, old_tgt, msg));
 382 }
 383
 384 void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir_graph *irg)
 385 {
 386         if(edges_activated_kind(irg, EDGE_KIND_NORMAL)) {
 387                 edges_notify_edge_kind(src, pos, tgt, old_tgt, EDGE_KIND_NORMAL, irg);
 388         }
 389
 390         if (edges_activated_kind(irg, EDGE_KIND_BLOCK) && is_Block(src)) {
 391                 /* do not use get_nodes_block() here, it fails when running unpinned */
 392                 ir_node *bl_old = old_tgt ? get_irn_n(skip_Proj(old_tgt), -1) : NULL;
 393                 ir_node *bl_tgt = NULL;
 394
 395                 if (tgt)
 396                         bl_tgt = is_Bad(tgt) ? tgt : get_irn_n(skip_Proj(tgt), -1);
 397
 398                 edges_notify_edge_kind(src, pos, bl_tgt, bl_old, EDGE_KIND_BLOCK, irg);
 399         }
 400 }
 401
 402
 403 void edges_node_deleted_kind(ir_node *old, ir_edge_kind_t kind, ir_graph *irg)
 404 {
 405         int i, n;
 406
 407         if(!edges_activated_kind(irg, kind))
 408                 return;
 409
 410         DBG((dbg, LEVEL_5, "node deleted (kind: %s): %+F\n", get_kind_str(kind), old));
 411
 412         foreach_tgt(old, i, n, kind) {
 413                 ir_node *old_tgt = get_n(old, i, kind);
 414                 edges_notify_edge_kind(old, i, NULL, old_tgt, kind, irg);
 415         }
 416 }
 417
 418 struct build_walker {
 419         ir_graph       *irg;
 420         ir_edge_kind_t kind;
 421         bitset_t       *reachable;
 422         unsigned       problem_found;
 423 };
 424
 425 /**
 426  * Post-Walker: notify all edges
 427  */
 428 static void build_edges_walker(ir_node *irn, void *data) {
 429         struct build_walker *w = data;
 430         int                 i, n;
 431
 432         if (! edges_activated_kind(w->irg, w->kind))
 433                 return;
 434
 435         foreach_tgt(irn, i, n, w->kind)
 436                 edges_notify_edge_kind(irn, i, get_n(irn, i, w->kind), NULL, w->kind, w->irg);
 437 }
 438
 439 /**
 440  * Pre-Walker: initializes the list-heads and set the out-count
 441  * of all nodes to 0.
 442  */
 443 static void init_lh_walker(ir_node *irn, void *data) {
 444         struct build_walker *w = data;
 445         INIT_LIST_HEAD(_get_irn_outs_head(irn, w->kind));
 446         _get_irn_edge_info(irn, w->kind)->out_count = 0;
 447 }
 448
 449 /**
 450  * Visitor: initializes the list-heads and set the out-count
 451  * of all nodes to 0 of nodes that are not seen so far.
 452  */
 453 static void visitor(ir_node *irn, void *data) {
 454         if (irn_not_visited(irn)) {
 455                 mark_irn_visited(irn);
 456                 init_lh_walker(irn, data);
 457         }
 458 }
 459
 460 /*
 461  * Build the initial edge set.
 462  * Beware, this is not a simple task because it suffers from two
 463  * difficulties:
 464  * - the anchor set allows access to Nodes that may not be reachable from
 465  *   the End node
 466  * - the identities add nodes to the "root set" that are not yet reachable
 467  *   from End. However, after some transformations, the CSE may revival these
 468  *   nodes
 469  *
 470  * These problems can be fixed using different strategies:
 471  * - Add an age flag to every node. Whenever the edge of a node is older
 472  *   then the current edge, invalidate the edges of this node.
 473  *   While this would help for revivaled nodes, it increases memory and runtime.
 474  * - Delete the identities set.
 475  *   Solves the revival problem, but may increase the memory consumption, as
 476  *   nodes cannot be revivaled at all.
 477  * - Manually iterate over the identities root set. This did not consume more memory
 478  *   but increase the computation time because the |identities| >= |V|
 479  *
 480  * Currently, we use the last option.
 481  */
 482 void edges_activate_kind(ir_graph *irg, ir_edge_kind_t kind)
 483 {
 484         struct build_walker w;
 485         irg_edge_info_t *info = _get_irg_edge_info(irg, kind);
 486
 487         w.irg  = irg;
 488         w.kind = kind;
 489
 490         info->activated = 1;
 491         edges_init_graph_kind(irg, kind);
 492         //irg_walk_graph(irg, init_lh_walker, build_edges_walker, &w);
 493         inc_irg_visited(irg);
 494         irg_walk_anchors(irg, init_lh_walker, build_edges_walker, &w);
 495         visit_all_identities(irg, visitor, &w);
 496 }
 497
 498 void edges_deactivate_kind(ir_graph *irg, ir_edge_kind_t kind)
 499 {
 500         irg_edge_info_t *info = _get_irg_edge_info(irg, kind);
 501
 502         info->activated = 0;
 503         if (info->edges) {
 504                 del_set(info->edges);
 505                 info->edges = NULL;
 506         }
 507 }
 508
 509 int (edges_activated_kind)(const ir_graph *irg, ir_edge_kind_t kind)
 510 {
 511         return _edges_activated_kind(irg, kind);
 512 }
 513
 514
 515 /**
 516  * Reroute all use-edges from a node to another.
 517  * @param from The node whose use-edges shall be withdrawn.
 518  * @param to   The node to which all the use-edges of @p from shall be
 519  *             sent to.
 520  * @param irg  The graph.
 521  */
 522 void edges_reroute_kind(ir_node *from, ir_node *to, ir_edge_kind_t kind, ir_graph *irg)
 523 {
 524         set_edge_func_t *set_edge = edge_kind_info[kind].set_edge;
 525
 526         if(set_edge && edges_activated_kind(irg, kind)) {
 527                 struct list_head *head = _get_irn_outs_head(from, kind);
 528
 529                 DBG((dbg, LEVEL_5, "reroute from %+F to %+F\n", from, to));
 530
 531                 while(head != head->next) {
 532                         ir_edge_t *edge = list_entry(head->next, ir_edge_t, list);
 533                         assert(edge->pos >= -1);
 534                         set_edge(edge->src, edge->pos, to);
 535                 }
 536         }
 537 }
 538
 539 static void verify_set_presence(ir_node *irn, void *data)
 540 {
 541         struct build_walker *w     = data;
 542         set                 *edges = _get_irg_edge_info(w->irg, w->kind)->edges;
 543         int i, n;
 544
 545         foreach_tgt(irn, i, n, w->kind) {
 546                 ir_edge_t templ, *e;
 547
 548                 templ.src = irn;
 549                 templ.pos = i;
 550
 551                 e = set_find(edges, &templ, EDGE_SIZE, edge_hash(&templ));
 552                 if(e != NULL) {
 553                         e->present = 1;
 554                 } else {
 555                         w->problem_found = 1;
 556                         ir_fprintf(stderr, "Edge Verifier: edge %+F,%d -> %+F (kind: \"%s\") is missing\n",
 557                                 irn, i, get_n(irn, i, w->kind), get_kind_str(w->kind));
 558                 }
 559         }
 560 }
 561
 562 static void verify_list_presence(ir_node *irn, void *data)
 563 {
 564         struct build_walker *w = data;
 565         const ir_edge_t     *e;
 566
 567         bitset_set(w->reachable, get_irn_idx(irn));
 568
 569         /* check list heads */
 570         vrfy_list_head(irn, w->kind);
 571
 572         foreach_out_edge_kind(irn, e, w->kind) {
 573                 ir_node *tgt;
 574
 575                 if (w->kind == EDGE_KIND_NORMAL && get_irn_arity(e->src) <= e->pos) {
 576                         w->problem_found = 1;
 577                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F -> %+F recorded at src position %d, but src has arity %d\n",
 578                                 edge_get_id(e), e->src, irn, e->pos, get_irn_arity(e->src));
 579                         continue;
 580                 }
 581
 582                 tgt = get_n(e->src, e->pos, w->kind);
 583
 584                 if (irn != tgt) {
 585                         w->problem_found = 1;
 586                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d (kind \"%s\") is no out edge of %+F but of %+F\n",
 587                                 edge_get_id(e), e->src, e->pos, get_kind_str(w->kind), irn, tgt);
 588                 }
 589         }
 590 }
 591
 592 int edges_verify_kind(ir_graph *irg, ir_edge_kind_t kind)
 593 {
 594         struct build_walker w;
 595         set                 *edges = _get_irg_edge_info(irg, kind)->edges;
 596         ir_edge_t           *e;
 597
 598         w.irg           = irg;
 599         w.kind          = kind;
 600         w.reachable     = bitset_alloca(get_irg_last_idx(irg));
 601         w.problem_found = 0;
 602
 603         /* Clear the present bit in all edges available. */
 604         for (e = set_first(edges); e; e = set_next(edges))
 605                 e->present = 0;
 606
 607         irg_walk_graph(irg, verify_set_presence, verify_list_presence, &w);
 608
 609         /*
 610          * Dump all edges which are not invalid and not present.
 611          * These edges are superfluous and their presence in the
 612          * edge set is wrong.
 613          */
 614         for (e = set_first(edges); e; e = set_next(edges)) {
 615                 if (! e->invalid && ! e->present && bitset_is_set(w.reachable, get_irn_idx(e->src))) {
 616                         w.problem_found = 1;
 617                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d is superfluous\n", edge_get_id(e), e->src, e->pos);
 618                 }
 619         }
 620
 621         return w.problem_found;
 622 }
 623
 624 #define IGNORE_NODE(irn) (is_Bad((irn)) || is_Block((irn)))
 625
 626 /**
 627  * Clear link field of all nodes.
 628  */
 629 static void clear_links(ir_node *irn, void *env) {
 630         struct build_walker *w  = env;
 631         bitset_t            *bs;
 632
 633         if (IGNORE_NODE(irn)) {
 634                 set_irn_link(irn, NULL);
 635                 return;
 636         }
 637
 638         bs = bitset_malloc(get_irg_last_idx(w->irg));
 639         set_irn_link(irn, bs);
 640 }
 641
 642 /**
 643  * Increases count (stored in link field) for all operands of a node.
 644  */
 645 static void count_user(ir_node *irn, void *env) {
 646         int i;
 647         int first;
 648
 649         first = get_irn_first(irn);
 650         for (i = get_irn_arity(irn) - 1; i >= first; --i) {
 651                 ir_node  *op = get_irn_n(irn, i);
 652                 bitset_t *bs = get_irn_link(op);
 653
 654                 if (bs)
 655                         bitset_set(bs, get_irn_idx(irn));
 656         }
 657 }
 658
 659 /**
 660  * Verifies if collected count, number of edges in list and stored edge count are in sync.
 661  */
 662 static void verify_edge_counter(ir_node *irn, void *env) {
 663         struct build_walker    *w       = env;
 664         bitset_t               *bs;
 665         int                    list_cnt;
 666         int                    ref_cnt;
 667         int                    edge_cnt;
 668         unsigned long          idx;
 669         const struct list_head *head;
 670         const struct list_head *pos;
 671
 672         if (IGNORE_NODE(irn))
 673                 return;
 674
 675         bs       = get_irn_link(irn);
 676         list_cnt = 0;
 677         ref_cnt = 0;
 678         edge_cnt = _get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count;
 679         head     = _get_irn_outs_head(irn, EDGE_KIND_NORMAL);
 680
 681         /* We can iterate safely here, list heads have already been verified. */
 682         list_for_each(pos, head) {
 683                 list_cnt++;
 684         }
 685
 686         /* check all nodes that reference us and count edges that point number
 687          * of ins that actually point to us */
 688         ref_cnt = 0;
 689         bitset_foreach(bs, idx) {
 690                 int i, arity;
 691                 ir_node *src = get_idx_irn(w->irg, idx);
 692
 693                 arity = get_irn_arity(src);
 694                 for(i = 0; i < arity; ++i) {
 695                         ir_node *in = get_irn_n(src, i);
 696                         if(in == irn)
 697                                 ref_cnt++;
 698                 }
 699         }
 700
 701         if (edge_cnt != list_cnt) {
 702                 w->problem_found = 1;
 703                 ir_fprintf(stderr, "Edge Verifier: edge count is %d, but %d edge(s) are recorded in list at %+F\n",
 704                         edge_cnt, list_cnt, irn);
 705         }
 706
 707         if (ref_cnt != list_cnt) {
 708                 w->problem_found = 1;
 709                 ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node(s), but the list contains %d edge(s)\n",
 710                         irn, ref_cnt, list_cnt);
 711
 712                 // Matze: buggy if a node has multiple ins pointing at irn
 713 #if 0
 714                 list_for_each(pos, head) {
 715                         ir_edge_t *edge = list_entry(pos, ir_edge_t, list);
 716                         bitset_flip(bs, get_irn_idx(edge->src));
 717                 }
 718
 719                 if (ref_cnt < list_cnt)
 720                         fprintf(stderr,"               following nodes are recorded in list, but not as user:\n");
 721                 else
 722                         fprintf(stderr,"               following nodes are user, but not recorded in list:\n");
 723
 724                 fprintf(stderr,"              ");
 725                 bitset_foreach(bs, idx) {
 726                         ir_node *src = get_idx_irn(w->irg, idx);
 727                         ir_fprintf(stderr, " %+F", src);
 728                 }
 729                 fprintf(stderr, "\n");
 730 #endif
 731         }
 732
 733         bitset_free(bs);
 734 }
 735
 736 /**
 737  * Verifies the out edges of an irg.
 738  */
 739 int edges_verify(ir_graph *irg) {
 740         struct build_walker w;
 741         int    problem_found = 0;
 742
 743         if (! edges_dbg)
 744                 return 0;
 745
 746         /* verify normal edges only */
 747         problem_found  = edges_verify_kind(irg, EDGE_KIND_NORMAL);
 748
 749         w.irg           = irg;
 750         w.kind          = EDGE_KIND_NORMAL;
 751         w.problem_found = 0;
 752
 753         /* verify counter */
 754         inc_irg_visited(irg);
 755         irg_walk_anchors(irg, clear_links, count_user, &w);
 756         inc_irg_visited(irg);
 757         irg_walk_anchors(irg, NULL, verify_edge_counter, &w);
 758
 759         return problem_found ? 1 : w.problem_found;
 760 }
 761
 762 void init_edges(void)
 763 {
 764         FIRM_DBG_REGISTER(dbg, DBG_EDGES);
 765         /* firm_dbg_set_mask(dbg, -1); */
 766 }
 767
 768 void edges_init_dbg(int do_dbg) {
 769         edges_dbg = do_dbg;
 770 }
 771
 772 void edges_activate(ir_graph *irg)
 773 {
 774         edges_activate_kind(irg, EDGE_KIND_NORMAL);
 775         edges_activate_kind(irg, EDGE_KIND_BLOCK);
 776 }
 777
 778 void edges_deactivate(ir_graph *irg)
 779 {
 780         edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 781         edges_deactivate_kind(irg, EDGE_KIND_BLOCK);
 782 }
 783
 784 int edges_assure(ir_graph *irg)
 785 {
 786         int activated = edges_activated(irg);
 787
 788         if(!activated)
 789                 edges_activate(irg);
 790
 791         return activated;
 792 }
 793
 794 void edges_node_deleted(ir_node *irn, ir_graph *irg)
 795 {
 796         edges_node_deleted_kind(irn, EDGE_KIND_NORMAL, irg);
 797         edges_node_deleted_kind(irn, EDGE_KIND_BLOCK, irg);
 798 }
 799
 800
 801 const ir_edge_t *(get_irn_out_edge_first_kind)(const ir_node *irn, ir_edge_kind_t kind)
 802 {
 803         return _get_irn_out_edge_first_kind(irn, kind);
 804 }
 805
 806 const ir_edge_t *(get_irn_out_edge_next)(const ir_node *irn, const ir_edge_t *last)
 807 {
 808         return _get_irn_out_edge_next(irn, last);
 809 }
 810
 811 ir_node *(get_edge_src_irn)(const ir_edge_t *edge)
 812 {
 813         return _get_edge_src_irn(edge);
 814 }
 815
 816 int (get_edge_src_pos)(const ir_edge_t *edge)
 817 {
 818         return _get_edge_src_pos(edge);
 819 }
 820
 821 int (get_irn_n_edges_kind)(const ir_node *irn, ir_edge_kind_t kind)
 822 {
 823         return _get_irn_n_edges_kind(irn, kind);
 824 }
 825
 826 void dump_all_out_edges(ir_node *irn)
 827 {
 828         int i;
 829         for(i = 0; i < EDGE_KIND_LAST; ++i) {
 830                 const ir_edge_t *edge;
 831
 832                 printf("kind \"%s\"\n", get_kind_str(i));
 833                 foreach_out_edge_kind(irn, edge, i) {
 834                         ir_printf("\t%+F(%d)\n", edge->src, edge->pos);
 835                 }
 836         }
 837 }