+#define IGNORE_NODE(irn) (is_Bad((irn)) || is_Block((irn)))
+
+/**
+ * Clear link field of all nodes.
+ */
+static void clear_links(ir_node *irn, void *env) {
+ struct build_walker *w = env;
+ bitset_t *bs;
+
+ if (IGNORE_NODE(irn)) {
+ set_irn_link(irn, NULL);
+ return;
+ }
+
+ bs = bitset_malloc(get_irg_last_idx(w->irg));
+ set_irn_link(irn, bs);
+}
+
+/**
+ * Increases count (stored in link field) for all operands of a node.
+ */
+static void count_user(ir_node *irn, void *env) {
+ int i;
+ int first;
+ (void) env;
+
+ first = -1;
+ for (i = get_irn_arity(irn) - 1; i >= first; --i) {
+ ir_node *op = get_irn_n(irn, i);
+ bitset_t *bs = get_irn_link(op);
+
+ if (bs)
+ bitset_set(bs, get_irn_idx(irn));
+ }
+}
+
+/**
+ * Verifies if collected count, number of edges in list and stored edge count are in sync.
+ */
+static void verify_edge_counter(ir_node *irn, void *env) {
+ struct build_walker *w = env;
+ bitset_t *bs;
+ int list_cnt;
+ int ref_cnt;
+ int edge_cnt;
+ unsigned long idx;
+ const struct list_head *head;
+ const struct list_head *pos;
+
+ if (IGNORE_NODE(irn))
+ return;
+
+ bs = get_irn_link(irn);
+ list_cnt = 0;
+ ref_cnt = 0;
+ edge_cnt = _get_irn_edge_info(irn, EDGE_KIND_NORMAL)->out_count;
+ head = _get_irn_outs_head(irn, EDGE_KIND_NORMAL);
+
+ /* We can iterate safely here, list heads have already been verified. */
+ list_for_each(pos, head) {
+ ++list_cnt;
+ }
+
+ /* check all nodes that reference us and count edges that point number
+ * of ins that actually point to us */
+ ref_cnt = 0;
+ bitset_foreach(bs, idx) {
+ int i, arity;
+ ir_node *src = get_idx_irn(w->irg, idx);
+
+ arity = get_irn_arity(src);
+ for (i = 0; i < arity; ++i) {
+ ir_node *in = get_irn_n(src, i);
+ if (in == irn)
+ ++ref_cnt;
+ }
+ }
+
+ if (edge_cnt != list_cnt) {
+ w->problem_found = 1;
+ ir_fprintf(stderr, "Edge Verifier: edge count is %d, but %d edge(s) are recorded in list at %+F\n",
+ edge_cnt, list_cnt, irn);
+ }
+
+ if (ref_cnt != list_cnt) {
+ w->problem_found = 1;
+ ir_fprintf(stderr, "Edge Verifier: %+F reachable by %d node(s), but the list contains %d edge(s)\n",
+ irn, ref_cnt, list_cnt);
+
+ /* Matze: buggy if a node has multiple ins pointing at irn */
+#if 0
+ list_for_each(pos, head) {
+ ir_edge_t *edge = list_entry(pos, ir_edge_t, list);
+ bitset_flip(bs, get_irn_idx(edge->src));
+ }
+
+ if (ref_cnt < list_cnt)
+ fprintf(stderr," following nodes are recorded in list, but not as user:\n");
+ else
+ fprintf(stderr," following nodes are user, but not recorded in list:\n");
+
+ fprintf(stderr," ");
+ bitset_foreach(bs, idx) {
+ ir_node *src = get_idx_irn(w->irg, idx);
+ ir_fprintf(stderr, " %+F", src);
+ }
+ fprintf(stderr, "\n");
+#endif
+ }
+
+ bitset_free(bs);
+}
+
+/**
+ * Verifies the out edges of an irg.
+ */
+int edges_verify(ir_graph *irg) {
+ struct build_walker w;
+ int problem_found = 0;
+
+ /* verify normal edges only */
+ problem_found = edges_verify_kind(irg, EDGE_KIND_NORMAL);
+
+ w.irg = irg;
+ w.kind = EDGE_KIND_NORMAL;
+ w.problem_found = 0;
+
+ /* verify counter */
+ irg_walk_anchors(irg, clear_links, count_user, &w);
+ irg_walk_anchors(irg, NULL, verify_edge_counter, &w);
+
+ return problem_found ? 1 : w.problem_found;
+}
+
+void init_edges(void) {
+ FIRM_DBG_REGISTER(dbg, DBG_EDGES);