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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Always available outs.
   9  * @author  Sebastian Hack, Michael Beck, Andreas Schoesser
  10  * @date    14.1.2005
  11  * @brief
  12  *   This are out-edges (also called def-use edges) that are dynamically
  13  *   updated as the graph changes.
  14  */
  15 #include "config.h"
  16
  17 #include "irnode_t.h"
  18 #include "iropt_t.h"
  19 #include "iredgekinds.h"
  20 #include "iredges_t.h"
  21 #include "irgwalk.h"
  22 #include "irdump_t.h"
  23 #include "irprintf.h"
  24 #include "debug.h"
  25 #include "set.h"
  26 #include "bitset.h"
  27 #include "error.h"
  28 #include "irpass_t.h"
  29
  30 #include "iredgeset.h"
  31 #include "hashptr.h"
  32
  33 #define DO_REHASH
  34 #define SCALAR_RETURN
  35 #define HashSet                   ir_edgeset_t
  36 #define HashSetIterator           ir_edgeset_iterator_t
  37 #define ValueType                 ir_edge_t*
  38 #define NullValue                 NULL
  39 #define DeletedValue              ((ir_edge_t*)-1)
  40 #define Hash(this,key)            (hash_ptr(key->src) ^ (key->pos * 40013))
  41 #define KeysEqual(this,key1,key2) ((key1->src) == (key2->src) && (key1->pos == key2->pos))
  42 #define SetRangeEmpty(ptr,size)   memset(ptr, 0, (size) * sizeof((ptr)[0]))
  43
  44 #define hashset_init            ir_edgeset_init
  45 void ir_edgeset_init_size(ir_edgeset_t *self, size_t size);
  46 #define hashset_init_size       ir_edgeset_init_size
  47 #define hashset_destroy         ir_edgeset_destroy
  48 #define hashset_insert          ir_edgeset_insert
  49 #define hashset_remove          ir_edgeset_remove
  50 ir_edge_t *ir_edgeset_find(const ir_edgeset_t *self, const ir_edge_t*);
  51 #define hashset_find            ir_edgeset_find
  52 size_t ir_edgeset_size(const ir_edgeset_t *self);
  53 #define hashset_size            ir_edgeset_size
  54 #define hashset_iterator_init   ir_edgeset_iterator_init
  55 #define hashset_iterator_next   ir_edgeset_iterator_next
  56 #define hashset_remove_iterator ir_edgeset_remove_iterator
  57
  58 #include "hashset.c.inl"
  59
  60 /**
  61  * A function that allows for setting an edge.
  62  * This abstraction is necessary since different edge kind have
  63  * different methods of setting edges.
  64  */
  65 typedef void (set_edge_func_t)(ir_node *src, int pos, ir_node *tgt);
  66
  67 /**
  68  * A function that returns the "arity" of a given edge kind
  69  * for a node.
  70  */
  71 typedef int (get_edge_src_arity_func_t)(const ir_node *src);
  72
  73 /**
  74  * A function that returns the pos'th edge of a given edge kind for a node.
  75  */
  76 typedef ir_node *(get_edge_src_n_func_t)(const ir_node *src, int pos);
  77
  78 /**
  79  * Additional data for an edge kind.
  80  */
  81 typedef struct {
  82         const char                *name;       /**< name of this edge kind */
  83         set_edge_func_t           *set_edge;   /**< the set_edge function */
  84         int                       first_idx;   /**< index of the first possible edge */
  85         get_edge_src_arity_func_t *get_arity;  /**< the get_arity function */
  86         get_edge_src_n_func_t     *get_n;      /**< the get_n function */
  87 } ir_edge_kind_info_t;
  88
  89 /**
  90  * Get the predecessor block.
  91  */
  92 static ir_node *get_block_n(const ir_node *block, int pos)
  93 {
  94         if (is_Block(block))
  95                 return get_Block_cfgpred_block(block, pos);
  96         /* might be a Bad */
  97         return NULL;
  98 }
  99
 100 static ir_node *get_irn_safe_n(const ir_node *node, int n)
 101 {
 102         if (n == -1 && is_Block(node))
 103                 return NULL;
 104         return get_irn_n(node, n);
 105 }
 106
 107 static const ir_edge_kind_info_t edge_kind_info[EDGE_KIND_LAST] = {
 108         { "normal"     , set_irn_n,   -1, get_irn_arity,  get_irn_safe_n },
 109         { "block succs", NULL,         0, get_irn_arity,  get_block_n    },
 110         { "dependency",  set_irn_dep,  0, get_irn_deps,   get_irn_dep    }
 111 };
 112
 113 #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)
 114 #define get_n(irn, pos, kind)        (edge_kind_info[kind].get_n(irn, pos))
 115 #define get_kind_str(kind)           (edge_kind_info[kind].name)
 116
 117 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 118
 119 /**
 120  * This flag is set to 1, if the edges get initialized for an irg.
 121  * Then register additional data is forbidden.
 122  */
 123 static int edges_used = 0;
 124
 125 /**
 126  * If set to 1, the list heads are checked every time an edge is changed.
 127  */
 128 static int edges_dbg = 0;
 129
 130 /**
 131  * Returns an ID for the given edge.
 132  */
 133 static inline long edge_get_id(const ir_edge_t *e)
 134 {
 135         return (long)e;
 136 }
 137
 138 void edges_init_graph_kind(ir_graph *irg, ir_edge_kind_t kind)
 139 {
 140         if (edges_activated_kind(irg, kind)) {
 141                 irg_edge_info_t *info = get_irg_edge_info(irg, kind);
 142                 size_t amount = get_irg_last_idx(irg) * 5 / 4;
 143
 144                 edges_used = 1;
 145                 if (info->allocated) {
 146                         amount = ir_edgeset_size(&info->edges);
 147                         ir_edgeset_destroy(&info->edges);
 148                         obstack_free(&info->edges_obst, NULL);
 149                 }
 150                 obstack_init(&info->edges_obst);
 151                 INIT_LIST_HEAD(&info->free_edges);
 152                 ir_edgeset_init_size(&info->edges, amount);
 153                 info->allocated = 1;
 154         }
 155 }
 156
 157 /**
 158  * Change the out count
 159  *
 160  * @param tgt  the edge target
 161  * @param kind the kind of the edge
 162  */
 163 static inline void edge_change_cnt(ir_node *tgt, ir_edge_kind_t kind, int ofs)
 164 {
 165         irn_edge_info_t *info = get_irn_edge_info(tgt, kind);
 166         info->out_count += ofs;
 167 }
 168
 169 /**
 170  * Verify the edge list of a node, i.e. ensure it's a loop:
 171  * head -> e_1 -> ... -> e_n -> head
 172  */
 173 static inline void verify_list_head(ir_node *irn, ir_edge_kind_t kind)
 174 {
 175         int                    err     = 0;
 176         int                    num     = 0;
 177         pset                   *lh_set = pset_new_ptr(16);
 178         const struct list_head *head   = &get_irn_edge_info(irn, kind)->outs_head;
 179         const struct list_head *pos;
 180
 181         list_for_each(pos, head) {
 182                 if (pset_find_ptr(lh_set, pos)) {
 183                         const ir_edge_t *edge = list_entry(pos, ir_edge_t, list);
 184
 185                         ir_fprintf(stderr, "EDGE Verifier: edge list broken (self loop not to head) for %+F:\n", irn);
 186                         fprintf(stderr, "- at list entry %d\n", num);
 187                         if (edge->src)
 188                                 ir_fprintf(stderr, "- edge(%ld) %+F(%d)\n", edge_get_id(edge), edge->src, edge->pos);
 189                         err = 1;
 190                         break;
 191                 }
 192                 num++;
 193                 pset_insert_ptr(lh_set, pos);
 194         }
 195
 196         del_pset(lh_set);
 197
 198         assert(err == 0);
 199 }
 200
 201 void edges_dump_kind(ir_graph *irg, ir_edge_kind_t kind)
 202 {
 203         irg_edge_info_t *info;
 204         ir_edgeset_t    *edges;
 205         ir_edgeset_iterator_t iter;
 206         ir_edge_t      *e;
 207
 208         if (!edges_activated_kind(irg, kind))
 209                 return;
 210
 211         info  = get_irg_edge_info(irg, kind);
 212         edges = &info->edges;
 213         foreach_ir_edgeset(edges, e, iter) {
 214                 ir_printf("%+F %d\n", e->src, e->pos);
 215         }
 216 }
 217
 218 static void add_edge(ir_node *src, int pos, ir_node *tgt, ir_edge_kind_t kind,
 219                      ir_graph *irg)
 220 {
 221         assert(edges_activated_kind(irg, kind));
 222         irg_edge_info_t *info  = get_irg_edge_info(irg, kind);
 223         ir_edgeset_t    *edges = &info->edges;
 224
 225         struct list_head *head = &get_irn_edge_info(tgt, kind)->outs_head;
 226         assert(head->next && head->prev &&
 227                    "target list head must have been initialized");
 228
 229         /* The old target was NULL, thus, the edge is newly created. */
 230         ir_edge_t *edge;
 231         if (list_empty(&info->free_edges)) {
 232                 edge = OALLOC(&info->edges_obst, ir_edge_t);
 233         } else {
 234                 edge = list_entry(info->free_edges.next, ir_edge_t, list);
 235                 list_del(&edge->list);
 236         }
 237
 238         edge->src       = src;
 239         edge->pos       = pos;
 240 #ifdef DEBUG_libfirm
 241         edge->present   = 0;
 242 #endif
 243
 244         ir_edge_t *new_edge = ir_edgeset_insert(edges, edge);
 245         assert(new_edge == edge);
 246         (void)new_edge;
 247
 248         list_add(&edge->list, head);
 249
 250         edge_change_cnt(tgt, kind, +1);
 251 }
 252
 253 static void delete_edge(ir_node *src, int pos, ir_node *old_tgt,
 254                         ir_edge_kind_t kind, ir_graph *irg)
 255 {
 256         assert(edges_activated_kind(irg, kind));
 257
 258         irg_edge_info_t *info  = get_irg_edge_info(irg, kind);
 259         ir_edgeset_t    *edges = &info->edges;
 260
 261         /* Initialize the edge template to search in the set. */
 262         ir_edge_t templ;
 263         templ.src = src;
 264         templ.pos = pos;
 265
 266         /* search the edge in the set. */
 267         ir_edge_t *edge = ir_edgeset_find(edges, &templ);
 268
 269         /* mark the edge invalid if it was found */
 270         if (edge == NULL)
 271                 return;
 272
 273         list_del(&edge->list);
 274         ir_edgeset_remove(edges, edge);
 275         list_add(&edge->list, &info->free_edges);
 276         edge->pos = -2;
 277         edge->src = NULL;
 278         edge_change_cnt(old_tgt, kind, -1);
 279 }
 280
 281 void edges_notify_edge_kind(ir_node *src, int pos, ir_node *tgt,
 282                             ir_node *old_tgt, ir_edge_kind_t kind,
 283                             ir_graph *irg)
 284 {
 285         if (old_tgt == NULL) {
 286                 add_edge(src, pos, tgt, kind, irg);
 287                 return;
 288         } else if (tgt == NULL) {
 289                 delete_edge(src, pos, old_tgt, kind, irg);
 290                 return;
 291         }
 292
 293         /* Only do something, if the old and new target differ. */
 294         if (tgt == old_tgt)
 295                 return;
 296
 297         assert(edges_activated_kind(irg, kind));
 298         irg_edge_info_t *info  = get_irg_edge_info(irg, kind);
 299         ir_edgeset_t    *edges = &info->edges;
 300
 301         /*
 302          * The target is not NULL and the old target differs
 303          * from the new target, the edge shall be moved (if the
 304          * old target was != NULL) or added (if the old target was
 305          * NULL).
 306          */
 307         struct list_head *head = &get_irn_edge_info(tgt, kind)->outs_head;
 308
 309         assert(head->next && head->prev &&
 310                         "target list head must have been initialized");
 311
 312         /* Initialize the edge template to search in the set. */
 313         ir_edge_t templ;
 314         templ.src = src;
 315         templ.pos = pos;
 316
 317         ir_edge_t *edge = ir_edgeset_find(edges, &templ);
 318         assert(edge && "edge to redirect not found!");
 319
 320         list_move(&edge->list, head);
 321         edge_change_cnt(old_tgt, kind, -1);
 322         edge_change_cnt(tgt, kind, +1);
 323
 324 #ifndef DEBUG_libfirm
 325         /* verify list heads */
 326         if (edges_dbg) {
 327                 if (tgt)
 328                         verify_list_head(tgt, kind);
 329                 if (old_tgt)
 330                         verify_list_head(old_tgt, kind);
 331         }
 332 #endif
 333 }
 334
 335 void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt,
 336                        ir_graph *irg)
 337 {
 338         if (edges_activated_kind(irg, EDGE_KIND_NORMAL)) {
 339                 edges_notify_edge_kind(src, pos, tgt, old_tgt, EDGE_KIND_NORMAL, irg);
 340         }
 341
 342         if (edges_activated_kind(irg, EDGE_KIND_BLOCK)) {
 343                 if (is_Block(src)) {
 344                         ir_node *bl_old = old_tgt ? get_nodes_block(old_tgt) : NULL;
 345                         ir_node *bl_tgt = NULL;
 346
 347                         if (tgt)
 348                                 bl_tgt = is_Bad(tgt) ? tgt : get_nodes_block(tgt);
 349
 350                         edges_notify_edge_kind(src, pos, bl_tgt, bl_old, EDGE_KIND_BLOCK, irg);
 351                 } else if (get_irn_mode(src) == mode_X && old_tgt != NULL && is_Block(old_tgt)) {
 352                         /* moving a jump node from one block to another */
 353                         foreach_out_edge_kind_safe(old_tgt, edge, EDGE_KIND_BLOCK) {
 354                                 ir_node *succ       = get_edge_src_irn(edge);
 355                                 int      succ_pos   = get_edge_src_pos(edge);
 356                                 ir_node *block_pred = get_Block_cfgpred(succ, succ_pos);
 357                                 if (block_pred != src)
 358                                         continue;
 359                                 edges_notify_edge_kind(succ, succ_pos, tgt, old_tgt,
 360                                                        EDGE_KIND_BLOCK, irg);
 361                         }
 362                 }
 363         }
 364 }
 365
 366 /**
 367  * Delete all in edges of a given kind from the node old.
 368  *
 369  * @param old   the node
 370  * @param kind  the kind of edges to remove
 371  * @param irg   the irg of the old node
 372  */
 373 static void edges_node_deleted_kind(ir_node *old, ir_edge_kind_t kind)
 374 {
 375         int i, n;
 376         ir_graph *irg = get_irn_irg(old);
 377
 378         if (!edges_activated_kind(irg, kind))
 379                 return;
 380
 381         DBG((dbg, LEVEL_5, "node deleted (kind: %s): %+F\n", get_kind_str(kind), old));
 382
 383         foreach_tgt(old, i, n, kind) {
 384                 ir_node *old_tgt = get_n(old, i, kind);
 385                 delete_edge(old, i, old_tgt, kind, irg);
 386         }
 387 }
 388
 389 /**
 390  * A node might be revivaled by CSE. Assure its edges.
 391  *
 392  * @param irn   the node
 393  * @param kind  the kind of edges to remove
 394  * @param irg   the irg of the old node
 395  */
 396 static void edges_node_revival_kind(ir_node *irn, ir_edge_kind_t kind)
 397 {
 398         irn_edge_info_t *info;
 399         int             i, n;
 400         ir_graph        *irg = get_irn_irg(irn);
 401
 402         if (!edges_activated_kind(irg, kind))
 403                 return;
 404
 405         info = get_irn_edge_info(irn, kind);
 406         if (info->edges_built)
 407                 return;
 408
 409         DBG((dbg, LEVEL_5, "node revivaled (kind: %s): %+F\n", get_kind_str(kind), irn));
 410
 411         foreach_tgt(irn, i, n, kind) {
 412                 ir_node *tgt = get_n(irn, i, kind);
 413                 add_edge(irn, i, tgt, kind, irg);
 414         }
 415         info->edges_built = 1;
 416 }
 417
 418 typedef struct build_walker {
 419         ir_edge_kind_t kind;
 420         bitset_t       *reachable;
 421         unsigned       problem_found;
 422 } build_walker;
 423
 424 /**
 425  * Post-Walker: notify all edges
 426  */
 427 static void build_edges_walker(ir_node *irn, void *data)
 428 {
 429         build_walker          *w = (build_walker*)data;
 430         int                   i, n;
 431         ir_edge_kind_t        kind = w->kind;
 432         ir_graph              *irg = get_irn_irg(irn);
 433
 434         foreach_tgt(irn, i, n, kind) {
 435                 ir_node *pred = get_n(irn, i, kind);
 436                 if (pred != NULL)
 437                         add_edge(irn, i, pred, kind, irg);
 438         }
 439         get_irn_edge_info(irn, kind)->edges_built = 1;
 440 }
 441
 442 /**
 443  * Pre-Walker: initializes the list-heads and set the out-count
 444  * of all nodes to 0.
 445  */
 446 static void init_lh_walker(ir_node *irn, void *data)
 447 {
 448         build_walker   *w    = (build_walker*)data;
 449         ir_edge_kind_t  kind = w->kind;
 450         list_head      *head = &get_irn_edge_info(irn, kind)->outs_head;
 451         INIT_LIST_HEAD(head);
 452         get_irn_edge_info(irn, kind)->edges_built = 0;
 453         get_irn_edge_info(irn, kind)->out_count   = 0;
 454 }
 455
 456 /**
 457  * Pre-Walker: initializes the list-heads and set the out-count
 458  * of all nodes to 0.
 459  *
 460  * Additionally touches DEP nodes, as they might be DEAD.
 461  * THIS IS UGLY, but I don't find a better way until we
 462  *
 463  * a) ensure that dead nodes are not used as input
 464  * b) it might be sufficient to add those stupid NO_REG nodes
 465  * to the anchor
 466  */
 467 static void init_lh_walker_dep(ir_node *irn, void *data)
 468 {
 469         build_walker   *w    = (build_walker*)data;
 470         ir_edge_kind_t  kind = w->kind;
 471         list_head      *head = &get_irn_edge_info(irn, kind)->outs_head;
 472         int             i;
 473
 474         INIT_LIST_HEAD(head);
 475         get_irn_edge_info(irn, kind)->edges_built = 0;
 476         get_irn_edge_info(irn, kind)->out_count   = 0;
 477
 478         for (i = get_irn_deps(irn) - 1; i >= 0; --i) {
 479                 ir_node *dep = get_irn_dep(irn, i);
 480
 481                 head = &get_irn_edge_info(dep, kind)->outs_head;
 482
 483                 INIT_LIST_HEAD(head);
 484                 get_irn_edge_info(dep, kind)->edges_built = 0;
 485                 get_irn_edge_info(dep, kind)->out_count   = 0;
 486         }
 487 }
 488
 489 typedef struct visitor_info_t {
 490         irg_walk_func *visit;
 491         void *data;
 492 } visitor_info_t;
 493
 494 /**
 495  * Visitor: initializes the list-heads and set the out-count
 496  * of all nodes to 0 of nodes that are not seen so far.
 497  */
 498 static void visitor(ir_node *irn, void *data)
 499 {
 500         visitor_info_t *info = (visitor_info_t*)data;
 501
 502         if (is_Deleted(irn))
 503                 return;
 504         if (!is_Block(irn) && is_Deleted(get_nodes_block(irn)))
 505                 return;
 506
 507         if (!irn_visited_else_mark(irn)) {
 508                 info->visit(irn, info->data);
 509         }
 510 }
 511
 512 void edges_activate_kind(ir_graph *irg, ir_edge_kind_t kind)
 513 {
 514         /*
 515          * Build the initial edge set.
 516          * Beware, this is not a simple task because it suffers from two
 517          * difficulties:
 518          * - the anchor set allows access to Nodes that may not be reachable from
 519          *   the End node
 520          * - the identities add nodes to the "root set" that are not yet reachable
 521          *   from End. However, after some transformations, the CSE may revival these
 522          *   nodes
 523          *
 524          * These problems can be fixed using different strategies:
 525          * - Add an age flag to every node. Whenever the edge of a node is older
 526          *   then the current edge, invalidate the edges of this node.
 527          *   While this would help for revivaled nodes, it increases memory and runtime.
 528          * - Delete the identities set.
 529          *   Solves the revival problem, but may increase the memory consumption, as
 530          *   nodes cannot be revivaled at all.
 531          * - Manually iterate over the identities root set. This did not consume more memory
 532          *   but increase the computation time because the |identities| >= |V|
 533          *
 534          * Currently, we use the last option.
 535          */
 536         struct build_walker w;
 537         irg_edge_info_t     *info = get_irg_edge_info(irg, kind);
 538         visitor_info_t      visit;
 539
 540         w.kind = kind;
 541
 542         visit.data = &w;
 543
 544         assert(!info->activated);
 545
 546         info->activated = 1;
 547         edges_init_graph_kind(irg, kind);
 548         if (kind == EDGE_KIND_DEP) {
 549                 irg_walk_anchors(irg, init_lh_walker_dep, NULL, &w);
 550                 /* Argh: Dep nodes might be dead, so we MUST visit identities first */
 551                 visit.visit = init_lh_walker_dep;
 552                 visit_all_identities(irg, visitor, &visit);
 553                 irg_walk_anchors(irg, NULL, build_edges_walker, &w);
 554         } else {
 555                 visit.visit = init_lh_walker;
 556                 visit_all_identities(irg, visitor, &visit);
 557                 irg_walk_anchors(irg, init_lh_walker, build_edges_walker, &w);
 558         }
 559 }
 560
 561 void edges_deactivate_kind(ir_graph *irg, ir_edge_kind_t kind)
 562 {
 563         irg_edge_info_t *info = get_irg_edge_info(irg, kind);
 564
 565         info->activated = 0;
 566         if (info->allocated) {
 567                 obstack_free(&info->edges_obst, NULL);
 568                 ir_edgeset_destroy(&info->edges);
 569                 info->allocated = 0;
 570         }
 571         clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
 572 }
 573
 574 int (edges_activated_kind)(const ir_graph *irg, ir_edge_kind_t kind)
 575 {
 576         return edges_activated_kind_(irg, kind);
 577 }
 578
 579 int (edges_activated)(const ir_graph *irg)
 580 {
 581         return edges_activated_(irg);
 582 }
 583
 584 void edges_reroute_kind(ir_node *from, ir_node *to, ir_edge_kind_t kind)
 585 {
 586         ir_graph *irg = get_irn_irg(from);
 587         set_edge_func_t *set_edge = edge_kind_info[kind].set_edge;
 588
 589         if (set_edge && edges_activated_kind(irg, kind)) {
 590                 struct list_head *head = &get_irn_edge_info(from, kind)->outs_head;
 591
 592                 DBG((dbg, LEVEL_5, "reroute from %+F to %+F\n", from, to));
 593
 594                 while (head != head->next) {
 595                         ir_edge_t *edge = list_entry(head->next, ir_edge_t, list);
 596                         assert(edge->pos >= -1);
 597                         set_edge(edge->src, edge->pos, to);
 598                 }
 599         }
 600 }
 601
 602 void edges_reroute(ir_node *from, ir_node *to)
 603 {
 604         edges_reroute_kind(from, to, EDGE_KIND_NORMAL);
 605 }
 606
 607 void edges_reroute_except(ir_node *from, ir_node *to, ir_node *exception)
 608 {
 609         foreach_out_edge_safe(from, edge) {
 610                 ir_node *src = get_edge_src_irn(edge);
 611                 if (src == exception)
 612                         continue;
 613                 set_irn_n(src, edge->pos, to);
 614         }
 615 }
 616
 617 #ifdef DEBUG_libfirm
 618 static void verify_set_presence(ir_node *irn, void *data)
 619 {
 620         build_walker *w     = (build_walker*)data;
 621         ir_graph     *irg   = get_irn_irg(irn);
 622         ir_edgeset_t *edges = &get_irg_edge_info(irg, w->kind)->edges;
 623         int i, n;
 624
 625         foreach_tgt(irn, i, n, w->kind) {
 626                 ir_edge_t templ, *e;
 627
 628                 templ.src = irn;
 629                 templ.pos = i;
 630
 631                 e = ir_edgeset_find(edges, &templ);
 632                 if (e != NULL) {
 633                         e->present = 1;
 634                 } else {
 635                         w->problem_found = 1;
 636                 }
 637         }
 638 }
 639
 640 static void verify_list_presence(ir_node *irn, void *data)
 641 {
 642         build_walker *w = (build_walker*)data;
 643
 644         bitset_set(w->reachable, get_irn_idx(irn));
 645
 646         /* check list heads */
 647         verify_list_head(irn, w->kind);
 648
 649         foreach_out_edge_kind(irn, e, w->kind) {
 650                 ir_node *tgt;
 651
 652                 if (w->kind == EDGE_KIND_NORMAL && get_irn_arity(e->src) <= e->pos) {
 653                         w->problem_found = 1;
 654                         continue;
 655                 }
 656
 657                 tgt = get_n(e->src, e->pos, w->kind);
 658
 659                 if (irn != tgt) {
 660                         w->problem_found = 1;
 661                 }
 662         }
 663 }
 664 #endif
 665
 666 int edges_verify_kind(ir_graph *irg, ir_edge_kind_t kind)
 667 {
 668 #ifdef DEBUG_libfirm
 669         struct build_walker w;
 670         ir_edgeset_t        *edges = &get_irg_edge_info(irg, kind)->edges;
 671         ir_edge_t           *e;
 672         ir_edgeset_iterator_t  iter;
 673
 674         w.kind          = kind;
 675         w.reachable     = bitset_alloca(get_irg_last_idx(irg));
 676         w.problem_found = 0;
 677
 678         /* Clear the present bit in all edges available. */
 679         foreach_ir_edgeset(edges, e, iter) {
 680                 e->present = 0;
 681         }
 682
 683         irg_walk_graph(irg, verify_set_presence, verify_list_presence, &w);
 684
 685         /*
 686          * Dump all edges which are not invalid and not present.
 687          * These edges are superfluous and their presence in the
 688          * edge set is wrong.
 689          */
 690         foreach_ir_edgeset(edges, e, iter) {
 691                 if (! e->present && bitset_is_set(w.reachable, get_irn_idx(e->src))) {
 692                         w.problem_found = 1;
 693                         ir_fprintf(stderr, "Edge Verifier: edge(%ld) %+F,%d is superfluous\n", edge_get_id(e), e->src, e->pos);
 694                 }
 695         }
 696
 697         return w.problem_found;
 698 #else
 699         (void)irg;
 700         (void)kind;
 701         return 0;
 702 #endif
 703 }
 704
 705 #define IGNORE_NODE(irn) (is_Bad((irn)) || is_Block((irn)))
 706
 707 /**
 708  * Clear link field of all nodes.
 709  */
 710 static void clear_links(ir_node *irn, void *env)
 711 {
 712         bitset_t     *bs;
 713         ir_graph     *irg;
 714         (void) env;
 715
 716         if (IGNORE_NODE(irn)) {
 717                 set_irn_link(irn, NULL);
 718                 return;
 719         }
 720
 721         irg = get_irn_irg(irn);
 722         bs  = bitset_malloc(get_irg_last_idx(irg));
 723         set_irn_link(irn, bs);
 724 }
 725
 726 /**
 727  * Increases count (stored in link field) for all operands of a node.
 728  */
 729 static void count_user(ir_node *irn, void *env)
 730 {
 731         int i;
 732         int first;
 733         (void) env;
 734
 735         first = is_Block(irn) ? 0 : -1;
 736         for (i = get_irn_arity(irn) - 1; i >= first; --i) {
 737                 ir_node  *op = get_irn_n(irn, i);
 738                 bitset_t *bs = (bitset_t*)get_irn_link(op);
 739
 740                 if (bs)
 741                         bitset_set(bs, get_irn_idx(irn));
 742         }
 743 }
 744
 745 /**
 746  * Verifies if collected count, number of edges in list and stored edge count are in sync.
 747  */
 748 static void verify_edge_counter(ir_node *irn, void *env)
 749 {
 750         build_walker *w = (build_walker*)env;
 751         if (IGNORE_NODE(irn))
 752                 return;
 753
 754         bitset_t *bs       = (bitset_t*)get_irn_link(irn);
 755         int       list_cnt = 0;
 756         int       edge_cnt = get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count;
 757         const struct list_head *head
 758                 = &get_irn_edge_info(irn, EDGE_KIND_NORMAL)->outs_head;
 759
 760         /* We can iterate safely here, list heads have already been verified. */
 761         const struct list_head *pos;
 762         list_for_each(pos, head) {
 763                 ++list_cnt;
 764         }
 765
 766         /* check all nodes that reference us and count edges that point number
 767          * of ins that actually point to us */
 768         ir_graph *irg     = get_irn_irg(irn);
 769         int       ref_cnt = 0;
 770         bitset_foreach(bs, idx) {
 771                 int i, arity;
 772                 ir_node *src = get_idx_irn(irg, idx);
 773
 774                 arity = get_irn_arity(src);
 775                 for (i = 0; i < arity; ++i) {
 776                         ir_node *in = get_irn_n(src, i);
 777                         if (in == irn)
 778                                 ++ref_cnt;
 779                 }
 780         }
 781
 782         if (edge_cnt != list_cnt) {
 783                 w->problem_found = 1;
 784                 ir_fprintf(stderr, "Edge Verifier: edge count is %d, but %d edge(s) are recorded in list at %+F\n",
 785                         edge_cnt, list_cnt, irn);
 786         }
 787
 788         if (ref_cnt != list_cnt) {
 789                 w->problem_found = 1;
 790                 ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node(s), but the list contains %d edge(s)\n",
 791                         irn, ref_cnt, list_cnt);
 792         }
 793
 794         bitset_free(bs);
 795 }
 796
 797 int edges_verify(ir_graph *irg)
 798 {
 799         struct build_walker w;
 800         int    problem_found = 0;
 801
 802         /* verify normal edges only */
 803         problem_found  = edges_verify_kind(irg, EDGE_KIND_NORMAL);
 804
 805         w.kind          = EDGE_KIND_NORMAL;
 806         w.problem_found = 0;
 807
 808         /* verify counter */
 809         irg_walk_anchors(irg, clear_links, count_user, &w);
 810         irg_walk_anchors(irg, NULL, verify_edge_counter, &w);
 811
 812         return problem_found ? 1 : w.problem_found;
 813 }
 814
 815 typedef struct pass_t {
 816         ir_graph_pass_t pass;
 817         unsigned        assert_on_problem;
 818 } pass_t;
 819
 820 /**
 821  * Wrapper to edges_verify to be run as an ir_graph pass.
 822  */
 823 static int edges_verify_wrapper(ir_graph *irg, void *context)
 824 {
 825         pass_t *pass           = (pass_t*)context;
 826         int     problems_found = edges_verify(irg);
 827         /* do NOT rerun the pass if verify is ok :-) */
 828         assert(problems_found && pass->assert_on_problem);
 829         return 0;
 830 }
 831
 832 ir_graph_pass_t *irg_verify_edges_pass(const char *name, unsigned assert_on_problem)
 833 {
 834         pass_t *pass = XMALLOCZ(pass_t);
 835
 836         def_graph_pass_constructor(
 837                 &pass->pass, name ? name : "edges_verify", edges_verify_wrapper);
 838
 839         /* neither dump nor verify */
 840         pass->pass.dump_irg   = (DUMP_ON_IRG_FUNC)ir_prog_no_dump;
 841         pass->pass.verify_irg = (RUN_ON_IRG_FUNC)ir_prog_no_verify;
 842
 843         pass->assert_on_problem = assert_on_problem;
 844         return &pass->pass;
 845 }
 846
 847 void init_edges(void)
 848 {
 849         FIRM_DBG_REGISTER(dbg, "firm.ir.edges");
 850 }
 851
 852 void edges_init_dbg(int do_dbg)
 853 {
 854         edges_dbg = do_dbg;
 855 }
 856
 857 void edges_activate(ir_graph *irg)
 858 {
 859         edges_activate_kind(irg, EDGE_KIND_NORMAL);
 860         edges_activate_kind(irg, EDGE_KIND_BLOCK);
 861         edges_activate_kind(irg, EDGE_KIND_DEP);
 862 }
 863
 864 void edges_deactivate(ir_graph *irg)
 865 {
 866         edges_deactivate_kind(irg, EDGE_KIND_DEP);
 867         edges_deactivate_kind(irg, EDGE_KIND_BLOCK);
 868         edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
 869 }
 870
 871 void assure_edges(ir_graph *irg)
 872 {
 873         assure_edges_kind(irg, EDGE_KIND_BLOCK);
 874         assure_edges_kind(irg, EDGE_KIND_NORMAL);
 875         assure_edges_kind(irg, EDGE_KIND_DEP);
 876         add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
 877 }
 878
 879 void assure_edges_kind(ir_graph *irg, ir_edge_kind_t kind)
 880 {
 881         if (!edges_activated_kind(irg, kind))
 882                 edges_activate_kind(irg, kind);
 883 }
 884
 885 void edges_node_deleted(ir_node *irn)
 886 {
 887         edges_node_deleted_kind(irn, EDGE_KIND_NORMAL);
 888         edges_node_deleted_kind(irn, EDGE_KIND_BLOCK);
 889         edges_node_deleted_kind(irn, EDGE_KIND_DEP);
 890 }
 891
 892 void edges_node_revival(ir_node *irn)
 893 {
 894         edges_node_revival_kind(irn, EDGE_KIND_NORMAL);
 895         edges_node_revival_kind(irn, EDGE_KIND_BLOCK);
 896 }
 897
 898 const ir_edge_t *(get_irn_out_edge_first_kind)(const ir_node *irn, ir_edge_kind_t kind)
 899 {
 900         return get_irn_out_edge_first_kind_(irn, kind);
 901 }
 902
 903 const ir_edge_t *(get_irn_out_edge_first)(const ir_node *irn)
 904 {
 905         return get_irn_out_edge_first_kind_(irn, EDGE_KIND_NORMAL);
 906 }
 907
 908 const ir_edge_t *(get_block_succ_first)(const ir_node *block)
 909 {
 910         return get_irn_out_edge_first_kind_(block, EDGE_KIND_BLOCK);
 911 }
 912
 913 const ir_edge_t *(get_irn_out_edge_next)(const ir_node *irn, const ir_edge_t *last, ir_edge_kind_t kind)
 914 {
 915         return get_irn_out_edge_next_(irn, last, kind);
 916 }
 917
 918 ir_node *(get_edge_src_irn)(const ir_edge_t *edge)
 919 {
 920         return get_edge_src_irn_(edge);
 921 }
 922
 923 int (get_edge_src_pos)(const ir_edge_t *edge)
 924 {
 925         return get_edge_src_pos_(edge);
 926 }
 927
 928 int (get_irn_n_edges_kind)(const ir_node *irn, ir_edge_kind_t kind)
 929 {
 930         return get_irn_n_edges_kind_(irn, kind);
 931 }
 932
 933 static void irg_walk_edges2(ir_node *node, irg_walk_func *pre,
 934                             irg_walk_func *post, void *env)
 935 {
 936         if (irn_visited_else_mark(node))
 937                 return;
 938
 939         if (pre != NULL)
 940                 pre(node, env);
 941
 942         foreach_out_edge_kind_safe(node, edge, EDGE_KIND_NORMAL) {
 943                 /* find the corresponding successor block. */
 944                 ir_node *pred = get_edge_src_irn(edge);
 945                 irg_walk_edges2(pred, pre, post, env);
 946         }
 947
 948         if (post != NULL)
 949                 post(node, env);
 950 }
 951
 952 void irg_walk_edges(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 953                     void *env)
 954 {
 955         ir_graph *irg = get_irn_irg(node);
 956
 957         assert(edges_activated(irg));
 958         assert(is_Block(node));
 959
 960         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 961
 962         inc_irg_visited(irg);
 963         irg_walk_edges2(node, pre, post, env);
 964
 965         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 966 }
 967
 968 static void irg_block_edges_walk2(ir_node *bl, irg_walk_func *pre,
 969                                   irg_walk_func *post, void *env)
 970 {
 971         if (!Block_block_visited(bl)) {
 972                 mark_Block_block_visited(bl);
 973
 974                 if (pre)
 975                         pre(bl, env);
 976
 977                 foreach_out_edge_kind_safe(bl, edge, EDGE_KIND_BLOCK) {
 978                         /* find the corresponding successor block. */
 979                         ir_node *pred = get_edge_src_irn(edge);
 980                         irg_block_edges_walk2(pred, pre, post, env);
 981                 }
 982
 983                 if (post)
 984                         post(bl, env);
 985         }
 986 }
 987
 988 void irg_block_edges_walk(ir_node *node, irg_walk_func *pre,
 989                           irg_walk_func *post, void *env)
 990 {
 991         ir_graph *irg = get_irn_irg(node);
 992
 993         assert(edges_activated(irg));
 994         assert(is_Block(node));
 995
 996         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 997
 998         inc_irg_block_visited(irg);
 999         irg_block_edges_walk2(node, pre, post, env);
1000
1001         ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
1002 }