nsz Git - libfirm/blob - ir/ana/irouts.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Compute and access out edges (also called def-use edges).
  23  * @author   Goetz Lindenmaier, Michael Beck
  24  * @date     1.2002
  25  * @version  $Id$
  26  */
  27 #include "config.h"
  28
  29 #ifdef HAVE_STRING_H
  30 #include <string.h>
  31 #endif
  32
  33 #include "xmalloc.h"
  34 #include "irouts.h"
  35 #include "irnode_t.h"
  36 #include "irgraph_t.h"
  37 #include "irprog_t.h"
  38 #include "irgwalk.h"
  39 #include "irtools.h"
  40 #include "irprintf.h"
  41 #include "error.h"
  42
  43 #ifdef DEBUG_libfirm
  44 /* Note:  ir_node.out_valid and ir_graph.n_outs are only present when DEBUG_libfirm is defined */
  45 /* Accesses to out_valid and n_outs are fenced out to avoid breakage
  46    when compiling with neither DEBUG_libfirm or NDEBUG defined */
  47 #endif /* defined DEBUG_libfirm */
  48
  49 /*--------------------------------------------------------------------*/
  50 /** Accessing the out datastructures                                 **/
  51 /*--------------------------------------------------------------------*/
  52
  53 #ifdef DEBUG_libfirm
  54 /** Clear the outs of a node */
  55 static void reset_outs(ir_node *node, void *unused) {
  56         (void) unused;
  57         node->out       = NULL;
  58         node->out_valid = 0;
  59 }
  60 #endif
  61
  62 int get_irn_outs_computed(const ir_node *node)
  63 {
  64         return node->out != NULL;
  65 }
  66
  67 /* returns the number of successors of the node: */
  68 int get_irn_n_outs(const ir_node *node) {
  69         assert(node && node->kind == k_ir_node);
  70 #ifdef DEBUG_libfirm
  71         /* assert(node->out_valid); */
  72 #endif /* defined DEBUG_libfirm */
  73         /* we misuse the first for the size info of the out array */
  74         return node->out[0].pos;
  75 }
  76
  77 /* Access successor n */
  78 ir_node *get_irn_out(const ir_node *def, int pos) {
  79         assert(pos >= 0 && pos < get_irn_n_outs(def));
  80 #ifdef DEBUG_libfirm
  81         /* assert(def->out_valid); */
  82 #endif /* defined DEBUG_libfirm */
  83         return def->out[pos+1].use;
  84 }
  85
  86 /* Access successor n */
  87 ir_node *get_irn_out_ex(const ir_node *def, int pos, int *in_pos) {
  88         assert(pos >= 0 && pos < get_irn_n_outs(def));
  89 #ifdef DEBUG_libfirm
  90         /* assert(def->out_valid); */
  91 #endif /* defined DEBUG_libfirm */
  92         *in_pos = def->out[pos+1].pos;
  93         return def->out[pos+1].use;
  94 }
  95
  96 void set_irn_out(ir_node *def, int pos, ir_node *use, int in_pos) {
  97         assert(def && use);
  98         assert(pos >= 0 && pos < get_irn_n_outs(def));
  99 #ifdef DEBUG_libfirm
 100         def->out_valid = 1;          /* assume that this function is used correctly */
 101 #endif /* defined DEBUG_libfirm */
 102         def->out[pos+1].use = use;
 103         def->out[pos+1].pos = in_pos;
 104 }
 105
 106 /* Return the number of control flow successors, ignore keep-alives. */
 107 int get_Block_n_cfg_outs(const ir_node *bl) {
 108         int i, n_cfg_outs = 0;
 109         assert(bl && is_Block(bl));
 110 #ifdef DEBUG_libfirm
 111         assert(bl->out_valid);
 112 #endif /* defined DEBUG_libfirm */
 113         for (i = 1; i <= bl->out[0].pos; ++i) {
 114                 ir_node *succ = bl->out[i].use;
 115                 if (get_irn_mode(succ) == mode_X && !is_End(succ))
 116                         n_cfg_outs += succ->out[0].pos;
 117         }
 118         return n_cfg_outs;
 119 }
 120
 121 /* Return the number of control flow successors, honor keep-alives. */
 122 int get_Block_n_cfg_outs_ka(const ir_node *bl) {
 123         int i, n_cfg_outs = 0;
 124         assert(bl && is_Block(bl));
 125 #ifdef DEBUG_libfirm
 126         assert(bl->out_valid);
 127 #endif /* defined DEBUG_libfirm */
 128         for (i = 1; i <= bl->out[0].pos; ++i) {
 129                 ir_node *succ = bl->out[i].use;
 130                 if (get_irn_mode(succ) == mode_X) {
 131
 132                         if (is_End(succ)) {
 133                                 /* ignore End if we are in the Endblock */
 134                                 if (get_nodes_block(succ) == bl)
 135                                         continue;
 136                                 else /* count Keep-alive as one */
 137                                         n_cfg_outs += 1;
 138                         } else
 139                                 n_cfg_outs += succ->out[0].pos;
 140                 }
 141         }
 142         return n_cfg_outs;
 143 }
 144
 145 /* Access predecessor n, ignore keep-alives. */
 146 ir_node *get_Block_cfg_out(const ir_node *bl, int pos) {
 147         int i;
 148         assert(bl && is_Block(bl));
 149 #ifdef DEBUG_libfirm
 150         assert(bl->out_valid);
 151 #endif /* defined DEBUG_libfirm */
 152         for (i = 1; i <= bl->out[0].pos; ++i) {
 153                 ir_node *succ = bl->out[i].use;
 154                 if (get_irn_mode(succ) == mode_X && !is_End(succ)) {
 155                         int n_outs = succ->out[0].pos;
 156                         if (pos < n_outs)
 157                                 return succ->out[pos + 1].use;
 158                         else
 159                                 pos -= n_outs;
 160                 }
 161         }
 162         return NULL;
 163 }
 164
 165 /* Access predecessor n, honor keep-alives. */
 166 ir_node *get_Block_cfg_out_ka(const ir_node *bl, int pos) {
 167         int i, n_outs;
 168         assert(bl && is_Block(bl));
 169 #ifdef DEBUG_libfirm
 170         assert (bl->out_valid);
 171 #endif /* defined DEBUG_libfirm */
 172         for (i = 1; i <= bl->out[0].pos; ++i) {
 173                 ir_node *succ = bl->out[i].use;
 174                 if (get_irn_mode(succ) == mode_X) {
 175                         if (is_End(succ)) {
 176                                 ir_node *end_bl = get_nodes_block(succ);
 177                                 if (end_bl == bl) {
 178                                         /* ignore End if we are in the Endblock */
 179                                         continue;
 180                                 }
 181                                 if (pos == 0) {
 182                                         /* handle keep-alive here: return the Endblock instead of the End node */
 183                                         return end_bl;
 184                                 } else
 185                                         --pos;
 186                         } else {
 187                                 n_outs = succ->out[0].pos;
 188                                 if (pos < n_outs)
 189                                         return succ->out[pos + 1].use;
 190                                 else
 191                                         pos -= n_outs;
 192                         }
 193                 }
 194         }
 195         return NULL;
 196 }
 197
 198 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
 199             irg_walk_func *post, void *env) {
 200         int     i, n;
 201         ir_node *succ;
 202
 203         assert(node);
 204         assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
 205
 206         set_irn_visited(node, get_irg_visited(current_ir_graph));
 207
 208         if (pre) pre(node, env);
 209
 210         for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
 211                 succ = get_irn_out(node, i);
 212                 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 213                         irg_out_walk_2(succ, pre, post, env);
 214         }
 215
 216         if (post) post(node, env);
 217 }
 218
 219 void irg_out_walk(ir_node *node,
 220                   irg_walk_func *pre, irg_walk_func *post,
 221                   void *env) {
 222         assert(node);
 223         if (get_irg_outs_state(current_ir_graph) != outs_none) {
 224                 inc_irg_visited (current_ir_graph);
 225                 irg_out_walk_2(node, pre, post, env);
 226         }
 227 }
 228
 229 static void irg_out_block_walk2(ir_node *bl,
 230                                 irg_walk_func *pre, irg_walk_func *post,
 231                                 void *env) {
 232         int i, n;
 233
 234         if (!Block_block_visited(bl)) {
 235                 mark_Block_block_visited(bl);
 236
 237                 if (pre)
 238                         pre(bl, env);
 239
 240                 for (i = 0, n =  get_Block_n_cfg_outs(bl); i < n; ++i) {
 241                         /* find the corresponding predecessor block. */
 242                         ir_node *pred = get_Block_cfg_out(bl, i);
 243                         /* recursion */
 244                         irg_out_block_walk2(pred, pre, post, env);
 245                 }
 246
 247                 if (post)
 248                         post(bl, env);
 249         }
 250 }
 251
 252 /* Walks only over Block nodes in the graph.  Has it's own visited
 253    flag, so that it can be interleaved with the other walker.         */
 254 void irg_out_block_walk(ir_node *node,
 255                         irg_walk_func *pre, irg_walk_func *post,
 256                         void *env) {
 257
 258         assert(is_Block(node) || (get_irn_mode(node) == mode_X));
 259
 260         inc_irg_block_visited(current_ir_graph);
 261
 262         if (get_irn_mode(node) == mode_X) {
 263                 int i, n;
 264
 265                 for (i = 0, n = get_irn_n_outs(node); i < n; ++i) {
 266                         ir_node *succ = get_irn_out(node, i);
 267                         if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 268                                 irg_out_walk_2(succ, pre, post, env);
 269                 }
 270         }
 271         else {
 272                 irg_out_block_walk2(node, pre, post, env);
 273         }
 274 }
 275
 276 /*--------------------------------------------------------------------*/
 277 /** Building and Removing the out datastructure                      **/
 278 /**                                                                  **/
 279 /** The outs of a graph are allocated in a single, large array.      **/
 280 /** This allows to allocate and deallocate the memory for the outs   **/
 281 /** on demand.  The large array is separated into many small ones    **/
 282 /** for each node.  Only a single field to reference the out array   **/
 283 /** is stored in each node and a field referencing the large out     **/
 284 /** array in irgraph.  The 0 field of each out array contains the    **/
 285 /** size of this array.  This saves memory in the irnodes themselves.**/
 286 /** The construction does two passes over the graph.  The first pass **/
 287 /** counts the overall number of outs and the outs of each node.  It **/
 288 /** stores the outs of each node in the out reference of the node.   **/
 289 /** Then the large array is allocated.  The second iteration chops   **/
 290 /** the large array into smaller parts, sets the out edges and       **/
 291 /** recounts the out edges.                                          **/
 292 /** Removes Tuple nodes!                                             **/
 293 /*--------------------------------------------------------------------*/
 294
 295
 296 /** Returns the amount of out edges for not yet visited successors. */
 297 static int _count_outs(ir_node *n) {
 298         int start, i, res, irn_arity;
 299
 300         mark_irn_visited(n);
 301         n->out = INT_TO_PTR(1);     /* Space for array size. */
 302
 303         start = is_Block(n) ? 0 : -1;
 304         irn_arity = get_irn_arity(n);
 305         res = irn_arity - start + 1;  /* --1 or --0; 1 for array size. */
 306
 307         for (i = start; i < irn_arity; ++i) {
 308                 /* Optimize Tuples.  They annoy if walking the cfg. */
 309                 ir_node *pred         = get_irn_n(n, i);
 310                 ir_node *skipped_pred = skip_Tuple(pred);
 311
 312                 if (skipped_pred != pred) {
 313                         set_irn_n(n, i, skipped_pred);
 314                 }
 315
 316                 /* count Def-Use edges for predecessors */
 317                 if (!irn_visited(skipped_pred))
 318                         res += _count_outs(skipped_pred);
 319
 320                 /*count my Def-Use edges */
 321                 skipped_pred->out = INT_TO_PTR(PTR_TO_INT(skipped_pred->out) + 1);
 322         }
 323         return res;
 324 }
 325
 326
 327 /** Returns the amount of out edges for not yet visited successors.
 328  *  This version handles some special nodes like irg_frame, irg_args etc.
 329  */
 330 static int count_outs(ir_graph *irg) {
 331         ir_node *n;
 332         int     i, res;
 333
 334         inc_irg_visited(irg);
 335         res = _count_outs(get_irg_end(irg));
 336
 337         /* Now handle anchored nodes. We need the out count of those
 338            even if they are not visible. */
 339         for (i = anchor_last - 1; i >= 0; --i) {
 340                 n = get_irg_anchor(irg, i);
 341                 if (!irn_visited_else_mark(n)) {
 342                         n->out = INT_TO_PTR(1);
 343                         ++res;
 344                 }
 345         }
 346         return res;
 347 }
 348
 349 /**
 350  * Enter memory for the outs to a node.
 351  *
 352  * @param use    current node
 353  * @param free   current free address in the chunk allocated for the outs
 354  *
 355  * @return The next free address
 356  */
 357 static ir_def_use_edge *_set_out_edges(ir_node *use, ir_def_use_edge *free) {
 358         int     n_outs, start, i, irn_arity, pos;
 359
 360         mark_irn_visited(use);
 361
 362         /* Allocate my array */
 363         n_outs = PTR_TO_INT(use->out);
 364         use->out = free;
 365 #ifdef DEBUG_libfirm
 366         use->out_valid = 1;
 367 #endif /* defined DEBUG_libfirm */
 368         free += n_outs;
 369         /* We count the successors again, the space will be sufficient.
 370            We use this counter to remember the position for the next back
 371            edge. */
 372         use->out[0].pos = 0;
 373
 374         start = is_Block(use) ? 0 : -1;
 375         irn_arity = get_irn_arity(use);
 376
 377         for (i = start; i < irn_arity; ++i) {
 378                 ir_node *def = get_irn_n(use, i);
 379
 380                 /* Recursion */
 381                 if (!irn_visited(def))
 382                         free = _set_out_edges(def, free);
 383
 384                 /* Remember this Def-Use edge */
 385                 pos = def->out[0].pos + 1;
 386                 def->out[pos].use = use;
 387                 def->out[pos].pos = i;
 388
 389                 /* increase the number of Def-Use edges so far */
 390                 def->out[0].pos = pos;
 391         }
 392         return free;
 393 }
 394
 395 /**
 396  * Enter memory for the outs to a node. Handles special nodes
 397  *
 398  * @param irg    the graph
 399  * @param free   current free address in the chunk allocated for the outs
 400  *
 401  * @return The next free address
 402  */
 403 static ir_def_use_edge *set_out_edges(ir_graph *irg, ir_def_use_edge *free) {
 404         ir_node *n;
 405         int     i, n_outs;
 406
 407         inc_irg_visited(irg);
 408         free = _set_out_edges(get_irg_end(irg), free);
 409
 410         /* handle anchored nodes */
 411         for (i = anchor_last - 1; i >= 0; --i) {
 412                 n = get_irg_anchor(irg, i);
 413                 if (!irn_visited_else_mark(n)) {
 414                         n_outs = PTR_TO_INT(n->out);
 415                         n->out = free;
 416 #ifdef DEBUG_libfirm
 417                         n->out_valid = 1;
 418 #endif /* defined DEBUG_libfirm */
 419                         free += n_outs;
 420                 }
 421         }
 422
 423         return free;
 424 }
 425
 426
 427 /**
 428  * We want that the out of ProjX from Start contains the next block at
 429  * position 0, the Start block at position 1.  This is necessary for
 430  * the out block walker.
 431  */
 432 static INLINE void fix_start_proj(ir_graph *irg) {
 433         ir_node *startbl = get_irg_start_block(irg);
 434
 435         if (get_Block_n_cfg_outs(startbl)) {
 436                 ir_node *proj = get_irg_initial_exec(irg);
 437                 ir_node *irn;
 438                 int     block_pos, other_pos;
 439
 440                 if (get_irn_n_outs(proj) == 2) {
 441                         if (get_irn_out_ex(proj, 0, &block_pos) == startbl) {
 442                                 irn = get_irn_out_ex(proj, 1, &other_pos);
 443                                 set_irn_out(proj, 0, irn, other_pos);
 444                                 set_irn_out(proj, 1, startbl, block_pos);
 445                         }
 446                 } else {
 447                         assert(get_irg_phase_state(irg) == phase_backend);
 448                 }
 449         }
 450 }
 451
 452 /* compute the outs for a given graph */
 453 void compute_irg_outs(ir_graph *irg) {
 454         ir_graph        *rem = current_ir_graph;
 455         int             n_out_edges = 0;
 456         ir_def_use_edge *end = NULL;         /* Only for debugging */
 457
 458         current_ir_graph = irg;
 459
 460         /* Update graph state */
 461         assert(get_irg_phase_state(current_ir_graph) != phase_building);
 462
 463         if (current_ir_graph->outs_state != outs_none)
 464                 free_irg_outs(current_ir_graph);
 465
 466         /* This first iteration counts the overall number of out edges and the
 467            number of out edges for each node. */
 468         n_out_edges = count_outs(irg);
 469
 470         /* allocate memory for all out edges. */
 471         irg->outs = XMALLOCNZ(ir_def_use_edge, n_out_edges);
 472 #ifdef DEBUG_libfirm
 473         irg->n_outs = n_out_edges;
 474 #endif /* defined DEBUG_libfirm */
 475
 476         /* The second iteration splits the irg->outs array into smaller arrays
 477            for each node and writes the back edges into this array. */
 478         end = set_out_edges(irg, irg->outs);
 479
 480         /* Check how much memory we have used */
 481         assert (end == (irg->outs + n_out_edges));
 482
 483         /* We want that the out of ProjX from Start contains the next block at
 484            position 0, the Start block at position 1.  This is necessary for
 485            code placement (place_early() ONLY if started GCSE on graphs with dead blocks) */
 486         fix_start_proj(irg);
 487
 488         current_ir_graph->outs_state = outs_consistent;
 489         current_ir_graph = rem;
 490 }
 491
 492 void assure_irg_outs(ir_graph *irg) {
 493         if (get_irg_outs_state(irg) != outs_consistent)
 494                 compute_irg_outs(irg);
 495 }
 496
 497 void compute_irp_outs(void) {
 498         int i;
 499         for (i = get_irp_n_irgs() -1; i >= 0; --i)
 500                 compute_irg_outs(get_irp_irg(i));
 501 }
 502
 503 void free_irp_outs(void) {
 504         int i;
 505         for (i = get_irp_n_irgs() -1; i >= 0; --i)
 506                 free_irg_outs(get_irp_irg(i));
 507 }
 508
 509
 510 /*------------------------------------------------------------*
 511  *  This computes the outedges for in interprocedural graph.  *
 512  *  There is one quirk:                                       *
 513  *  The number of the outedges for each node is saved in      *
 514  *  the first member of the ir_node** array. Maybe we should  *
 515  *  change this to make it more portable...                   *
 516  *------------------------------------------------------------*/
 517
 518
 519 #ifdef INTERPROCEDURAL_VIEW
 520 /**
 521  * Inits the number of outedges for each node
 522  * before counting.
 523  */
 524 static void init_count(ir_node * node, void *env) {
 525         (void) env;
 526         node->out = (ir_node **) 1; /* 1 for the array size */
 527 }
 528
 529
 530 /**
 531  * Adjusts the out edge count for its predecessors
 532  * and adds the current arity to the overall count,
 533  * which is saved in "env"
 534  */
 535 static void node_arity_count(ir_node * node, void * env) {
 536         int *anz = (int *) env, arity, n_outs, i, start;
 537         ir_node *succ;
 538
 539         arity = get_irn_arity(node);
 540         start = (is_Block(node)) ? 0 : -1;
 541
 542         n_outs = 1 + arity + (-start);  // ((is_Block(node)) ? 0 : 1);   // Why + 1??
 543         *anz += n_outs;
 544
 545         for(i = start; i < arity; i++) {
 546                 succ = get_irn_n(node, i);
 547                 succ->out = (ir_node **)INT_TO_PTR(PTR_TO_INT(succ->out) + 1);
 548         }
 549 }
 550
 551 /*
 552  * Inits all nodes for setting the outedges
 553  * Returns the overall count of edges
 554  */
 555 int count_ip_outs(void) {
 556         int res = 0;
 557
 558         cg_walk(init_count, node_arity_count, &res);
 559
 560         return(res);
 561 }
 562
 563 static int dummy_count = 0, global_count; /* Only for debugging */
 564
 565 /**
 566  * For each node: Sets the pointer to array
 567  * in which the outedges are written later.
 568  * The current array start is transported in env
 569  */
 570 static void set_array_pointer(ir_node *node, void *env) {
 571         int n_outs;
 572         ir_node ***free = (ir_node ***) env;
 573
 574         /* Allocate my array */
 575         n_outs = PTR_TO_INT(node->out);  /* We wrote the count here in count_ip_outs */
 576         dummy_count += n_outs;
 577         assert(dummy_count <= global_count && "More outedges than initially counted!");
 578         node -> out = *free;
 579         *free = &((*free)[n_outs]);
 580         /* We count the successors again, the space will be sufficient.
 581            We use this counter to remember the position for the next back
 582            edge. */
 583         node -> out[0] = (ir_node *) 0;
 584 }
 585
 586
 587 /**
 588  * Adds an outedge from the predecessor to the
 589  * current node.
 590  */
 591 static void set_out_pointer(ir_node * node, void *env) {
 592         int i, arity = get_irn_arity(node);
 593         ir_node *succ;
 594         int start = (!is_Block(node)) ? -1 : 0;
 595         (void) env;
 596
 597         for (i = start; i < arity; ++i) {
 598                 succ = get_irn_n(node, i);
 599                 succ->out[get_irn_n_outs(succ)+1] = node;
 600                 succ->out[0] = INT_TO_PTR(get_irn_n_outs(succ) + 1);
 601         }
 602 }
 603
 604
 605 /*
 606  * Sets the outedges for all nodes.
 607  */
 608 void set_ip_outs(void) {
 609         ir_node **outedge_array = get_irp_ip_outedges();
 610         cg_walk(set_array_pointer, set_out_pointer, (void *) &outedge_array);
 611 }
 612
 613
 614
 615 /*
 616  * Counts the outedges, allocates memory to save the
 617  * outedges and fills this outedge array in interprocedural
 618  * view!
 619  */
 620 void compute_ip_outs(void) {
 621         int n_out_edges;
 622         ir_node **out_edges;
 623
 624         assert(get_irp_ip_view_state() == ip_view_valid &&
 625          "Cannot construct outs for invalid ip view.");
 626
 627         if (irp->outs_state != outs_none) {
 628                 free_ip_outs();
 629         }
 630
 631         global_count = n_out_edges = count_ip_outs();
 632         out_edges    = XMALLOCNZ(ir_node*, n_out_edges);
 633         set_irp_ip_outedges(out_edges);
 634         set_ip_outs();
 635 }
 636
 637 void free_ip_outs(void) {
 638         ir_node **out_edges = get_irp_ip_outedges();
 639         if (out_edges != NULL) {
 640                 free(out_edges);
 641                 set_irp_ip_outedges(NULL);
 642         }
 643         irp->outs_state = outs_none;
 644 }
 645 #endif
 646
 647
 648 void free_irg_outs(ir_graph *irg) {
 649         /*   current_ir_graph->outs_state = outs_none; */
 650         irg->outs_state = outs_none;
 651
 652         if (irg->outs) {
 653 #ifdef DEBUG_libfirm
 654                 memset(irg->outs, 0, irg->n_outs);
 655 #endif /* defined DEBUG_libfirm */
 656                 free(irg->outs);
 657                 irg->outs = NULL;
 658 #ifdef DEBUG_libfirm
 659                 irg->n_outs = 0;
 660 #endif /* defined DEBUG_libfirm */
 661         }
 662
 663 #ifdef DEBUG_libfirm
 664         /* when debugging, *always* reset all nodes' outs!  irg->outs might
 665            have been lying to us */
 666         irg_walk_graph (irg, reset_outs, NULL, NULL);
 667 #endif /* defined DEBUG_libfirm */
 668 }
 669
 670 static void check_out_edges(ir_node *irn, void *env) {
 671         int i, j, pos;
 672         int *pError = env;
 673         int error = *pError;
 674         int last = is_Block(irn) ? 0 : -1;
 675
 676         /* check forward: every input must have an out edge */
 677         for (i = get_irn_arity(irn) - 1; i >= last; --i) {
 678                 ir_node *pred = get_irn_n(irn, i);
 679
 680                 for (j = get_irn_n_outs(pred) - 1; j >= 0; --j) {
 681                         ir_node *user = get_irn_out_ex(pred, j, &pos);
 682
 683                         if (user == irn && pos == i) {
 684                                 break;
 685                         }
 686                 }
 687                 if (j < 0) {
 688                         ir_fprintf(stderr, "Missing out edge from %+F input %d to %+F", irn, i, pred);
 689                         ++error;
 690                 }
 691         }
 692
 693         /* checking backward */
 694         for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
 695                 ir_node *user = get_irn_out_ex(irn, i, &pos);
 696
 697                 if (get_irn_n(user, pos) != irn) {
 698                         ir_fprintf(stderr, "Spurious out edge from %+F output %d to %+F", irn, i, user);
 699                         ++error;
 700                 }
 701         }
 702         *pError = error;
 703 }
 704
 705 /* verify outs edges. */
 706 void verify_outs(ir_graph *irg) {
 707         int errors = 0;
 708         irg_walk_graph(irg, NULL, check_out_edges, &errors);
 709         if (errors > 0)
 710                 panic("Out edges are corrupt");
 711 }