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 #ifndef DEBUG_libfirm
 374         /* verify list heads */
 375         if (edges_dbg) {
 376                 if (tgt)
 377                         vrfy_list_head(tgt, kind);
 378                 if (old_tgt)
 379                         vrfy_list_head(old_tgt, kind);
 380         }
 381 #endif
 382
 383         DBG((dbg, LEVEL_5, "announce out edge: %+F %d-> %+F(%+F): %s\n", src, pos, tgt, old_tgt, msg));
 384 }
 385
 386 void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir_graph *irg)
 387 {
 388         if(edges_activated_kind(irg, EDGE_KIND_NORMAL)) {
 389                 edges_notify_edge_kind(src, pos, tgt, old_tgt, EDGE_KIND_NORMAL, irg);
 390         }
 391
 392         if (edges_activated_kind(irg, EDGE_KIND_BLOCK) && is_Block(src)) {
 393                 /* do not use get_nodes_block() here, it fails when running unpinned */
 394                 ir_node *bl_old = old_tgt ? get_irn_n(skip_Proj(old_tgt), -1) : NULL;
 395                 ir_node *bl_tgt = NULL;
 396
 397                 if (tgt)
 398                         bl_tgt = is_Bad(tgt) ? tgt : get_irn_n(skip_Proj(tgt), -1);
 399
 400                 edges_notify_edge_kind(src, pos, bl_tgt, bl_old, EDGE_KIND_BLOCK, irg);
 401         }
 402 }
 403
 404
 405 void edges_node_deleted_kind(ir_node *old, ir_edge_kind_t kind, ir_graph *irg)
 406 {
 407         int i, n;
 408
 409         if(!edges_activated_kind(irg, kind))
 410                 return;
 411
 412         DBG((dbg, LEVEL_5, "node deleted (kind: %s): %+F\n", get_kind_str(kind), old));
 413
 414         foreach_tgt(old, i, n, kind) {
 415                 ir_node *old_tgt = get_n(old, i, kind);
 416                 edges_notify_edge_kind(old, i, NULL, old_tgt, kind, irg);
 417         }
 418 }
 419
 420 struct build_walker {
 421         ir_graph       *irg;
 422         ir_edge_kind_t kind;
 423         bitset_t       *reachable;
 424         unsigned       problem_found;
 425 };
 426
 427 /**
 428  * Post-Walker: notify all edges
 429  */
 430 static void build_edges_walker(ir_node *irn, void *data) {
 431         struct build_walker *w = data;
 432         int                 i, n;
 433
 434         if (! edges_activated_kind(w->irg, w->kind))
 435                 return;
 436
 437         foreach_tgt(irn, i, n, w->kind)
 438                 edges_notify_edge_kind(irn, i, get_n(irn, i, w->kind), NULL, w->kind, w->irg);
 439 }
 440
 441 /**
 442  * Pre-Walker: initializes the list-heads and set the out-count
 443  * of all nodes to 0.
 444  */
 445 static void init_lh_walker(ir_node *irn, void *data) {
 446         struct build_walker *w = data;
 447         INIT_LIST_HEAD(_get_irn_outs_head(irn, w->kind));
 448         _get_irn_edge_info(irn, w->kind)->out_count = 0;
 449 }
 450
 451 /**
 452  * Visitor: initializes the list-heads and set the out-count
 453  * of all nodes to 0 of nodes that are not seen so far.
 454  */
 455 static void visitor(ir_node *irn, void *data) {
 456         if (irn_not_visited(irn)) {
 457                 mark_irn_visited(irn);
 458                 init_lh_walker(irn, data);
 459         }
 460 }
 461
 462 /*
 463  * Build the initial edge set.
 464  * Beware, this is not a simple task because it suffers from two
 465  * difficulties:
 466  * - the anchor set allows access to Nodes that may not be reachable from
 467  *   the End node
 468  * - the identities add nodes to the "root set" that are not yet reachable
 469  *   from End. However, after some transformations, the CSE may revival these
 470  *   nodes
 471  *
 472  * These problems can be fixed using different strategies:
 473  * - Add an age flag to every node. Whenever the edge of a node is older
 474  *   then the current edge, invalidate the edges of this node.
 475  *   While this would help for revivaled nodes, it increases memory and runtime.
 476  * - Delete the identities set.
 477  *   Solves the revival problem, but may increase the memory consumption, as
 478  *   nodes cannot be revivaled at all.
 479  * - Manually iterate over the identities root set. This did not consume more memory
 480  *   but increase the computation time because the |identities| >= |V|
 481  *
 482  * Currently, we use the last option.
 483  */
 484 void edges_activate_kind(ir_graph *irg, ir_edge_kind_t kind)
 485 {
 486         struct build_walker w;
 487         irg_edge_info_t *info = _get_irg_edge_info(irg, kind);
 488
 489         w.irg  = irg;
 490         w.kind = kind;
 491
 492         info->activated = 1;
 493         edges_init_graph_kind(irg, kind);
 494         //irg_walk_graph(irg, init_lh_walker, build_edges_walker, &w);
 495         inc_irg_visited(irg);
 496         irg_walk_anchors(irg, init_lh_walker, build_edges_walker, &w);
 497         visit_all_identities(irg, visitor, &w);
 498 }
 499
 500 void edges_deactivate_kind(ir_graph *irg, ir_edge_kind_t kind)
 501 {
 502         irg_edge_info_t *info = _get_irg_edge_info(irg, kind);
 503
 504         info->activated = 0;
 505         if (info->edges) {
 506                 del_set(info->edges);
 507                 info->edges = NULL;
 508         }
 509 }
 510
 511 int (edges_activated_kind)(const ir_graph *irg, ir_edge_kind_t kind)
 512 {
 513         return _edges_activated_kind(irg, kind);
 514 }
 515
 516
 517 /**
 518  * Reroute all use-edges from a node to another.
 519  * @param from The node whose use-edges shall be withdrawn.
 520  * @param to   The node to which all the use-edges of @p from shall be
 521  *             sent to.
 522  * @param irg  The graph.
 523  */
 524 void edges_reroute_kind(ir_node *from, ir_node *to, ir_edge_kind_t kind, ir_graph *irg)
 525 {
 526         set_edge_func_t *set_edge = edge_kind_info[kind].set_edge;
 527
 528         if(set_edge && edges_activated_kind(irg, kind)) {
 529                 struct list_head *head = _get_irn_outs_head(from, kind);
 530
 531                 DBG((dbg, LEVEL_5, "reroute from %+F to %+F\n", from, to));
 532
 533                 while(head != head->next) {
 534                         ir_edge_t *edge = list_entry(head->next, ir_edge_t, list);
 535                         assert(edge->pos >= -1);
 536                         set_edge(edge->src, edge->pos, to);
 537                 }
 538         }
 539 }
 540
 541 static void verify_set_presence(ir_node *irn, void *data)
 542 {
 543         struct build_walker *w     = data;
 544         set                 *edges = _get_irg_edge_info(w->irg, w->kind)->edges;
 545         int i, n;
 546
 547         foreach_tgt(irn, i, n, w->kind) {
 548                 ir_edge_t templ, *e;
 549
 550                 templ.src = irn;
 551                 templ.pos = i;
 552
 553                 e = set_find(edges, &templ, EDGE_SIZE, edge_hash(&templ));
 554                 if(e != NULL) {
 555                         e->present = 1;
 556                 } else {
 557                         w->problem_found = 1;
 558                         ir_fprintf(stderr, "Edge Verifier: edge %+F,%d -> %+F (kind: \"%s\") is missing\n",
 559                                 irn, i, get_n(irn, i, w->kind), get_kind_str(w->kind));
 560                 }
 561         }
 562 }
 563
 564 static void verify_list_presence(ir_node *irn, void *data)
 565 {
 566         struct build_walker *w = data;
 567         const ir_edge_t     *e;
 568
 569         bitset_set(w->reachable, get_irn_idx(irn));
 570
 571         /* check list heads */
 572         vrfy_list_head(irn, w->kind);
 573
 574         foreach_out_edge_kind(irn, e, w->kind) {
 575                 ir_node *tgt;
 576
 577                 if (w->kind == EDGE_KIND_NORMAL && get_irn_arity(e->src) <= e->pos) {
 578                         w->problem_found = 1;
 579                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F -> %+F recorded at src position %d, but src has arity %d\n",
 580                                 edge_get_id(e), e->src, irn, e->pos, get_irn_arity(e->src));
 581                         continue;
 582                 }
 583
 584                 tgt = get_n(e->src, e->pos, w->kind);
 585
 586                 if (irn != tgt) {
 587                         w->problem_found = 1;
 588                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d (kind \"%s\") is no out edge of %+F but of %+F\n",
 589                                 edge_get_id(e), e->src, e->pos, get_kind_str(w->kind), irn, tgt);
 590                 }
 591         }
 592 }
 593
 594 int edges_verify_kind(ir_graph *irg, ir_edge_kind_t kind)
 595 {
 596         struct build_walker w;
 597         set                 *edges = _get_irg_edge_info(irg, kind)->edges;
 598         ir_edge_t           *e;
 599
 600         w.irg           = irg;
 601         w.kind          = kind;
 602         w.reachable     = bitset_alloca(get_irg_last_idx(irg));
 603         w.problem_found = 0;
 604
 605         /* Clear the present bit in all edges available. */
 606         for (e = set_first(edges); e; e = set_next(edges))
 607                 e->present = 0;
 608
 609         irg_walk_graph(irg, verify_set_presence, verify_list_presence, &w);
 610
 611         /*
 612          * Dump all edges which are not invalid and not present.
 613          * These edges are superfluous and their presence in the
 614          * edge set is wrong.
 615          */
 616         for (e = set_first(edges); e; e = set_next(edges)) {
 617                 if (! e->invalid && ! e->present && bitset_is_set(w.reachable, get_irn_idx(e->src))) {
 618                         w.problem_found = 1;
 619                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d is superfluous\n", edge_get_id(e), e->src, e->pos);
 620                 }
 621         }
 622
 623         return w.problem_found;
 624 }
 625
 626 #define IGNORE_NODE(irn) (is_Bad((irn)) || is_Block((irn)))
 627
 628 /**
 629  * Clear link field of all nodes.
 630  */
 631 static void clear_links(ir_node *irn, void *env) {
 632         struct build_walker *w  = env;
 633         bitset_t            *bs;
 634
 635         if (IGNORE_NODE(irn)) {
 636                 set_irn_link(irn, NULL);
 637                 return;
 638         }
 639
 640         bs = bitset_malloc(get_irg_last_idx(w->irg));
 641         set_irn_link(irn, bs);
 642 }
 643
 644 /**
 645  * Increases count (stored in link field) for all operands of a node.
 646  */
 647 static void count_user(ir_node *irn, void *env) {
 648         int i;
 649         int first;
 650
 651         first = get_irn_first(irn);
 652         for (i = get_irn_arity(irn) - 1; i >= first; --i) {
 653                 ir_node  *op = get_irn_n(irn, i);
 654                 bitset_t *bs = get_irn_link(op);
 655
 656                 if (bs)
 657                         bitset_set(bs, get_irn_idx(irn));
 658         }
 659 }
 660
 661 /**
 662  * Verifies if collected count, number of edges in list and stored edge count are in sync.
 663  */
 664 static void verify_edge_counter(ir_node *irn, void *env) {
 665         struct build_walker    *w       = env;
 666         bitset_t               *bs;
 667         int                    list_cnt;
 668         int                    ref_cnt;
 669         int                    edge_cnt;
 670         unsigned long          idx;
 671         const struct list_head *head;
 672         const struct list_head *pos;
 673
 674         if (IGNORE_NODE(irn))
 675                 return;
 676
 677         bs       = get_irn_link(irn);
 678         list_cnt = 0;
 679         ref_cnt = 0;
 680         edge_cnt = _get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count;
 681         head     = _get_irn_outs_head(irn, EDGE_KIND_NORMAL);
 682
 683         /* We can iterate safely here, list heads have already been verified. */
 684         list_for_each(pos, head) {
 685                 list_cnt++;
 686         }
 687
 688         /* check all nodes that reference us and count edges that point number
 689          * of ins that actually point to us */
 690         ref_cnt = 0;
 691         bitset_foreach(bs, idx) {
 692                 int i, arity;
 693                 ir_node *src = get_idx_irn(w->irg, idx);
 694
 695                 arity = get_irn_arity(src);
 696                 for(i = 0; i < arity; ++i) {
 697                         ir_node *in = get_irn_n(src, i);
 698                         if(in == irn)
 699                                 ref_cnt++;
 700                 }
 701         }
 702
 703         if (edge_cnt != list_cnt) {
 704                 w->problem_found = 1;
 705                 ir_fprintf(stderr, "Edge Verifier: edge count is %d, but %d edge(s) are recorded in list at %+F\n",
 706                         edge_cnt, list_cnt, irn);
 707         }
 708
 709         if (ref_cnt != list_cnt) {
 710                 w->problem_found = 1;
 711                 ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node(s), but the list contains %d edge(s)\n",
 712                         irn, ref_cnt, list_cnt);
 713
 714                 // Matze: buggy if a node has multiple ins pointing at irn
 715 #if 0
 716                 list_for_each(pos, head) {
 717                         ir_edge_t *edge = list_entry(pos, ir_edge_t, list);
 718                         bitset_flip(bs, get_irn_idx(edge->src));
 719                 }
 720
 721                 if (ref_cnt < list_cnt)
 722                         fprintf(stderr,"               following nodes are recorded in list, but not as user:\n");
 723                 else
 724                         fprintf(stderr,"               following nodes are user, but not recorded in list:\n");
 725
 726                 fprintf(stderr,"              ");
 727                 bitset_foreach(bs, idx) {
 728                         ir_node *src = get_idx_irn(w->irg, idx);
 729                         ir_fprintf(stderr, " %+F", src);
 730                 }
 731                 fprintf(stderr, "\n");
 732 #endif
 733         }
 734
 735         bitset_free(bs);
 736 }
 737
 738 /**
 739  * Verifies the out edges of an irg.
 740  */
 741 int edges_verify(ir_graph *irg) {
 742         struct build_walker w;
 743         int    problem_found = 0;
 744
 745         /* verify normal edges only */
 746         problem_found  = edges_verify_kind(irg, EDGE_KIND_NORMAL);
 747
 748         w.irg           = irg;
 749         w.kind          = EDGE_KIND_NORMAL;
 750         w.problem_found = 0;
 751
 752         /* verify counter */
 753         inc_irg_visited(irg);
 754         irg_walk_anchors(irg, clear_links, count_user, &w);
 755         inc_irg_visited(irg);
 756         irg_walk_anchors(irg, NULL, verify_edge_counter, &w);
 757
 758         return problem_found ? 1 : w.problem_found;
 759 }
 760
 761 void init_edges(void)
 762 {
 763         FIRM_DBG_REGISTER(dbg, DBG_EDGES);
 764         /* firm_dbg_set_mask(dbg, -1); */
 765 }
 766
 767 void edges_init_dbg(int do_dbg) {
 768         edges_dbg = do_dbg;
 769 }
 770
 771 void edges_activate(ir_graph *irg)
 772 {
 773         edges_activate_kind(irg, EDGE_KIND_NORMAL);
 774         edges_activate_kind(irg, EDGE_KIND_BLOCK);
 775 }
 776
 777 void edges_deactivate(ir_graph *irg)
 778 {
 779         edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 780         edges_deactivate_kind(irg, EDGE_KIND_BLOCK);
 781 }
 782
 783 int edges_assure(ir_graph *irg)
 784 {
 785         int activated = edges_activated(irg);
 786
 787         if(!activated)
 788                 edges_activate(irg);
 789
 790         return activated;
 791 }
 792
 793 void edges_node_deleted(ir_node *irn, ir_graph *irg)
 794 {
 795         edges_node_deleted_kind(irn, EDGE_KIND_NORMAL, irg);
 796         edges_node_deleted_kind(irn, EDGE_KIND_BLOCK, irg);
 797 }
 798
 799
 800 const ir_edge_t *(get_irn_out_edge_first_kind)(const ir_node *irn, ir_edge_kind_t kind)
 801 {
 802         return _get_irn_out_edge_first_kind(irn, kind);
 803 }
 804
 805 const ir_edge_t *(get_irn_out_edge_next)(const ir_node *irn, const ir_edge_t *last)
 806 {
 807         return _get_irn_out_edge_next(irn, last);
 808 }
 809
 810 ir_node *(get_edge_src_irn)(const ir_edge_t *edge)
 811 {
 812         return _get_edge_src_irn(edge);
 813 }
 814
 815 int (get_edge_src_pos)(const ir_edge_t *edge)
 816 {
 817         return _get_edge_src_pos(edge);
 818 }
 819
 820 int (get_irn_n_edges_kind)(const ir_node *irn, ir_edge_kind_t kind)
 821 {
 822         return _get_irn_n_edges_kind(irn, kind);
 823 }
 824
 825 void dump_all_out_edges(ir_node *irn)
 826 {
 827         int i;
 828         for(i = 0; i < EDGE_KIND_LAST; ++i) {
 829                 const ir_edge_t *edge;
 830
 831                 printf("kind \"%s\"\n", get_kind_str(i));
 832                 foreach_out_edge_kind(irn, edge, i) {
 833                         ir_printf("\t%+F(%d)\n", edge->src, edge->pos);
 834                 }
 835         }
 836 }