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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irscc.c
   4  * Purpose:     Compute the strongly connected regions and build
   5  *              backedge/loop datastructures.
   6  *              A variation on the Tarjan algorithm. See also [Trapp:99],
   7  *              Chapter 5.2.1.2.
   8  * Author:      Goetz Lindenmaier
   9  * Modified by:
  10  * Created:     7.2002
  11  * CVS-ID:      $Id$
  12  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  13  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  14  */
  15
  16 #ifdef HAVE_CONFIG_H
  17 #include "config.h"
  18 #endif
  19
  20 #include <string.h>
  21
  22 #include "irloop_t.h"
  23 #include "irnode_t.h"
  24 #include "irgraph_t.h"
  25 #include "array.h"
  26 #include "pmap.h"
  27 #include "irgwalk.h"
  28 #include "irprog_t.h"
  29 #include "irdump.h"
  30
  31 ir_graph *outermost_ir_graph;      /* The outermost graph the scc is computed
  32                       for */
  33 static ir_loop *current_loop;      /* Current loop construction is working
  34                       on. */
  35 static int loop_node_cnt = 0;      /* Counts the number of allocated loop nodes.
  36                       Each loop node gets a unique number.
  37                       What for? ev. remove. @@@ */
  38 static int current_dfn = 1;        /* Counter to generate depth first numbering
  39                       of visited nodes.  */
  40
  41 void link_to_reg_end (ir_node *n, void *env);
  42 void set_projx_link(ir_node *cb_projx, ir_node *end_projx);
  43 ir_node *get_projx_link(ir_node *cb_projx);
  44
  45 /**********************************************************************/
  46 /* Node attributes                                                   **/
  47 /**********************************************************************/
  48
  49 /* A map to get from irnodes to loop nodes. */
  50 static pmap *node_loop_map = NULL;
  51
  52 /**********************************************************************/
  53 /* Node attributes needed for the construction.                      **/
  54 /**********************************************************************/
  55
  56 typedef struct scc_info {
  57   bool in_stack;         /* Marks whether node is on the stack. */
  58   int dfn;               /* Depth first search number. */
  59   int uplink;            /* dfn number of ancestor. */
  60   /*  ir_loop *loop;         *//* Refers to the containing loop. */
  61   /*
  62       struct section *section;
  63       xset def;
  64       xset use;
  65   */
  66 } scc_info;
  67
  68 static INLINE scc_info* new_scc_info(void) {
  69   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof (scc_info));
  70   memset (info, 0, sizeof (scc_info));
  71   return info;
  72 }
  73
  74 static INLINE void
  75 mark_irn_in_stack (ir_node *n) {
  76   assert(get_irn_link(n));
  77   /*  to slow */
  78   /* ((scc_info *)get_irn_link(n))->in_stack = true; */
  79   ((scc_info *)n->link)->in_stack = true;
  80 }
  81
  82 static INLINE void
  83 mark_irn_not_in_stack (ir_node *n) {
  84   assert(get_irn_link(n));
  85   /*  to slow */
  86   /* ((scc_info *)get_irn_link(n))->in_stack = false; */
  87   ((scc_info *)n->link)->in_stack = false;
  88 }
  89
  90 static INLINE bool
  91 irn_is_in_stack (ir_node *n) {
  92   assert(get_irn_link(n));
  93   /*  to slow */
  94   /* return ((scc_info *)get_irn_link(n))->in_stack; */
  95   return ((scc_info *)n->link)->in_stack;
  96 }
  97
  98 static INLINE void
  99 set_irn_uplink (ir_node *n, int uplink) {
 100   assert(get_irn_link(n));
 101   /*  to slow */
 102   /* ((scc_info *)get_irn_link(n))->uplink = uplink; */
 103   ((scc_info *)n->link)->uplink = uplink;
 104 }
 105
 106 static INLINE int
 107 get_irn_uplink (ir_node *n) {
 108   assert(get_irn_link(n));
 109   /*  from fast to slow */
 110   /* return ((scc_info *)get_irn_link(n))->uplink; */
 111   return ((scc_info *)n->link)->uplink;
 112 }
 113
 114 static INLINE void
 115 set_irn_dfn (ir_node *n, int dfn) {
 116   assert(get_irn_link(n));
 117   /*  to slow */
 118   /* ((scc_info *)get_irn_link(n))->dfn = dfn; */
 119   ((scc_info *)n->link)->dfn = dfn;
 120 }
 121
 122 static INLINE int
 123 get_irn_dfn (ir_node *n) {
 124   assert(get_irn_link(n));
 125   /*  to slow */
 126   /* return ((scc_info *)get_irn_link(n))->dfn; */
 127   return ((scc_info *)n->link)->dfn;
 128 }
 129
 130 #if 0
 131 /* Replaced node loop map by real field as hash access dominates runtime
 132  * of the algorithm. ! */
 133 /* Uses temporary information to set the loop */
 134 INLINE void
 135 set_irn_loop (ir_node *n, ir_loop* loop) {
 136   assert(node_loop_map && "not initialized!");
 137   pmap_insert(node_loop_map, (void *)n, (void *)loop);
 138 }
 139
 140 /* Uses temporary information to get the loop */
 141 INLINE ir_loop *
 142 get_irn_loop (ir_node *n) {
 143   ir_loop *res = NULL;
 144   if (!node_loop_map) return NULL;
 145
 146   if (pmap_contains(node_loop_map, (void *)n))
 147     res = (ir_loop *) pmap_get(node_loop_map, (void *)n);
 148
 149   return res;
 150 }
 151 #else
 152 INLINE void
 153 set_irn_loop (ir_node *n, ir_loop* loop) {
 154   n->loop = loop;
 155 }
 156
 157 /* Uses temporary information to get the loop */
 158 INLINE ir_loop *
 159 get_irn_loop (ir_node *n) {
 160   return n->loop;
 161 }
 162 #endif
 163
 164
 165 #if 0
 166 static ir_loop *find_nodes_loop (ir_node *n, ir_loop *l) {
 167   int i;
 168   ir_loop *res = NULL;
 169
 170   /* Test whether n is contained in this loop. */
 171   for (i = 0; i < get_loop_n_nodes(l); i++)
 172     if (n == get_loop_node(l, i)) return l;
 173
 174   /* Is this a leave in the loop tree? If so loop not found. */
 175   if (get_loop_n_sons(l) == 0) return NULL;
 176
 177   /* Else descend in the loop tree. */
 178   for (i = 0; i < get_loop_n_sons(l); i++) {
 179     res = find_nodes_loop(n, get_loop_son(l, i));
 180     if (res) break;
 181   }
 182   return res;
 183 }
 184
 185 /* @@@ temporary implementation, costly!!! */
 186 ir_loop * get_irn_loop(ir_node *n) {
 187   ir_loop *l = get_irg_loop(current_ir_graph);
 188   l = find_nodes_loop(n, l);
 189   return l;
 190 }
 191 #endif
 192
 193 /**********************************************************************/
 194 /* A stack.                                                          **/
 195 /**********************************************************************/
 196
 197 static ir_node **stack = NULL;
 198 static int tos = 0;                /* top of stack */
 199
 200 static INLINE void init_stack(void) {
 201   if (stack) {
 202     ARR_RESIZE (ir_node *, stack, 1000);
 203   } else {
 204     stack = NEW_ARR_F (ir_node *, 1000);
 205   }
 206   tos = 0;
 207 }
 208
 209 #if 0
 210 static INLINE void free_stack(void) {
 211   DEL_ARR_F(stack);
 212   stack = NULL;
 213   tos = 0;
 214 }
 215 #endif
 216
 217 static INLINE void
 218 push (ir_node *n)
 219 {
 220   /*DDMN(n);*/
 221
 222   if (tos == ARR_LEN (stack)) {
 223     int nlen = ARR_LEN (stack) * 2;
 224     ARR_RESIZE (ir_node *, stack, nlen);
 225   }
 226   stack [tos++] = n;
 227   mark_irn_in_stack(n);
 228 }
 229
 230 static INLINE ir_node *
 231 pop (void)
 232 {
 233   ir_node *n = stack[--tos];
 234   mark_irn_not_in_stack(n);
 235   return n;
 236 }
 237
 238 /* The nodes up to n belong to the current loop.
 239    Removes them from the stack and adds them to the current loop. */
 240 static INLINE void
 241 pop_scc_to_loop (ir_node *n)
 242 {
 243   ir_node *m;
 244   int i = 0;
 245
 246   /*for (;;) {*/
 247   do
 248     {
 249     m = pop();
 250     loop_node_cnt++;
 251     set_irn_dfn(m, loop_node_cnt);
 252     add_loop_node(current_loop, m);
 253     set_irn_loop(m, current_loop);
 254     i++;
 255     /*    if (m==n) break;*/
 256     } while(m != n);
 257
 258   if(i > 1)
 259     printf("Mehr als eine Iteration!!!!!!!!!!!!!!!!!!!!!!!!!!!!11111\n");
 260 }
 261
 262 /* GL ??? my last son is my grandson???  Removes loops with no
 263    ir_nodes in them.  Such loops have only another loop as son. (Why
 264    can't they have two loops as sons? Does it never get that far? ) */
 265 static void close_loop (ir_loop *l)
 266 {
 267   int last = get_loop_n_elements(l) - 1;
 268   loop_element lelement = get_loop_element(l, last);
 269   ir_loop *last_son = lelement.son;
 270
 271   if (get_kind(last_son) == k_ir_loop &&
 272       get_loop_n_elements(last_son) == 1)
 273     {
 274       ir_loop *gson;
 275
 276       lelement = get_loop_element(last_son, 0);
 277       gson = lelement.son;
 278       if(get_kind(gson) == k_ir_loop)
 279     {
 280           loop_element new_last_son;
 281
 282       gson -> outer_loop = l;
 283           new_last_son.son = gson;
 284       l -> children[last] = new_last_son;
 285     }
 286     }
 287
 288   current_loop = l;
 289 }
 290
 291 /* Removes and unmarks all nodes up to n from the stack.
 292    The nodes must be visited once more to assign them to a scc. */
 293 static INLINE void
 294 pop_scc_unmark_visit (ir_node *n)
 295 {
 296   ir_node *m = NULL;
 297
 298   while (m != n) {
 299     m = pop();
 300     set_irn_visited(m, 0);
 301   }
 302 }
 303
 304 /**********************************************************************/
 305 /* The loop datastructure.                                           **/
 306 /**********************************************************************/
 307
 308 /* Allocates a new loop as son of current_loop.  Sets current_loop
 309    to the new loop and returns the father. */
 310 ir_loop *new_loop (void) {
 311   ir_loop *father, *son;
 312
 313   father = current_loop;
 314
 315   son = (ir_loop *) obstack_alloc (outermost_ir_graph->obst, sizeof (ir_loop));
 316   memset (son, 0, sizeof (ir_loop));
 317   son->kind = k_ir_loop;
 318   son->children = NEW_ARR_F (loop_element, 0);
 319   son->n_nodes = 0;
 320   son->n_sons=0;
 321   if (father) {
 322     son->outer_loop = father;
 323     add_loop_son(father, son);
 324     son->depth = father->depth+1;
 325   } else {  /* The root loop */
 326     son->outer_loop = son;
 327     son->depth = 0;
 328   }
 329
 330 #ifdef DEBUG_libfirm
 331   son->loop_nr = get_irp_new_node_nr();
 332   son->link = NULL;
 333 #endif
 334
 335   current_loop = son;
 336   return father;
 337 }
 338
 339 #if 0
 340 /* Finishes the datastructures, copies the arrays to the obstack
 341    of current_ir_graph.
 342    A. Schoesser: Caution: loop -> sons is gone. */
 343 static void mature_loop (ir_loop *loop) {
 344   ir_loop **new_sons;
 345
 346   new_sons = NEW_ARR_D (ir_loop *, current_ir_graph->obst, ARR_LEN(loop->sons));
 347   memcpy (new_sons, loop->sons, sizeof (ir_loop *) * ARR_LEN(loop->sons));
 348   DEL_ARR_F(loop->sons);
 349   loop->sons = new_sons;
 350 }
 351 #endif
 352
 353 /* Returns outer loop, itself if outermost. */
 354 ir_loop *get_loop_outer_loop (ir_loop *loop) {
 355   assert(loop && loop->kind == k_ir_loop);
 356   return loop->outer_loop;
 357 }
 358
 359 /* Returns nesting depth of this loop */
 360 int get_loop_depth (ir_loop *loop) {
 361   assert(loop); assert(loop->kind == k_ir_loop);
 362   return loop->depth;
 363 }
 364
 365 /* Returns the number of inner loops */
 366 int      get_loop_n_sons (ir_loop *loop) {
 367   assert(loop && loop->kind == k_ir_loop);
 368   return(loop -> n_sons);
 369 }
 370
 371 /* Returns the pos`th loop_node-child              *
 372  * TODO: This method isn`t very efficient !        *
 373  * Returns NULL if there isnt`t a pos`th loop_node */
 374 ir_loop *get_loop_son (ir_loop *loop, int pos) {
 375   int child_nr = 0, loop_nr = -1;
 376
 377   assert(loop && loop->kind == k_ir_loop);
 378   while(child_nr < ARR_LEN(loop->children))
 379    {
 380     if(*(loop -> children[child_nr].kind) == k_ir_loop)
 381       loop_nr++;
 382     if(loop_nr == pos)
 383       return(loop -> children[child_nr].son);
 384     child_nr++;
 385    }
 386   return NULL;
 387 }
 388
 389 /* Use EXCLUSIVELY this function to add sons, otherwise the loop->n_sons
 390    is invalid! */
 391
 392 INLINE void
 393 add_loop_son(ir_loop *loop, ir_loop *son) {
 394   loop_element lson;
 395   lson.son = son;
 396   assert(loop && loop->kind == k_ir_loop);
 397   assert(get_kind(son) == k_ir_loop);
 398   ARR_APP1 (loop_element, loop->children, lson);
 399   loop -> n_sons++;
 400 }
 401
 402 /* Returns the number of nodes in the loop */
 403 int      get_loop_n_nodes (ir_loop *loop) {
 404   assert(loop); assert(loop->kind == k_ir_loop);
 405   return loop -> n_nodes;
 406 /*  return ARR_LEN(loop->nodes); */
 407 }
 408
 409 /* Returns the pos`th ir_node-child                *
 410  * TODO: This method isn`t very efficient !        *
 411  * Returns NULL if there isnt`t a pos`th ir_node   */
 412 ir_node *get_loop_node (ir_loop *loop, int pos) {
 413   int child_nr, node_nr = -1;
 414
 415   assert(loop && loop->kind == k_ir_loop);
 416   assert(pos < get_loop_n_nodes(loop));
 417
 418   for (child_nr = 0; child_nr < ARR_LEN(loop->children); child_nr++) {
 419     if(*(loop -> children[child_nr].kind) == k_ir_node)
 420       node_nr++;
 421     if(node_nr == pos)
 422       return(loop -> children[child_nr].node);
 423   }
 424   DDML(loop);
 425   printf("pos: %d\n", pos);
 426   assert(0 && "no child at pos found");
 427   return NULL;
 428 }
 429
 430 /* Use EXCLUSIVELY this function to add nodes, otherwise the loop->n_nodes
 431    is invalid! */
 432
 433 INLINE void
 434 add_loop_node(ir_loop *loop, ir_node *n) {
 435   loop_element ln;
 436   ln.node = n;
 437   assert(loop && loop->kind == k_ir_loop);
 438   assert(get_kind(n) == k_ir_node);
 439   ARR_APP1 (loop_element, loop->children, ln);
 440   loop->n_nodes++;
 441 }
 442
 443 /** Returns the number of elements contained in loop.  */
 444 int get_loop_n_elements (ir_loop *loop) {
 445   assert(loop && loop->kind == k_ir_loop);
 446   return(ARR_LEN(loop->children));
 447 }
 448
 449 /*
 450  Returns the pos`th loop element.
 451  This may be a loop_node or a ir_node. The caller of this function has
 452  to check the *(loop_element.kind) field for "k_ir_node" or "k_ir_loop"
 453  and then select the apropriate "loop_element.node" or "loop_element.son".
 454 */
 455
 456 loop_element get_loop_element (ir_loop *loop, int pos) {
 457   assert(loop && loop->kind == k_ir_loop && pos < ARR_LEN(loop->children));
 458
 459   return(loop -> children[pos]);
 460 }
 461
 462 int get_loop_element_pos(ir_loop *loop, void *le) {
 463   int i;
 464   assert(loop && loop->kind == k_ir_loop);
 465
 466   for (i = 0; i < get_loop_n_elements(loop); i++)
 467     if (get_loop_element(loop, i).node == le) return i;
 468   return -1;
 469 }
 470
 471 int get_loop_loop_nr(ir_loop *loop) {
 472   assert(loop && loop->kind == k_ir_loop);
 473 #ifdef DEBUG_libfirm
 474   return loop->loop_nr;
 475 #else
 476   return (int)loop;
 477 #endif
 478 }
 479
 480
 481 /** A field to connect additional information to a loop.  Only valid
 482     if libfirm_debug is set. */
 483 void  set_loop_link (ir_loop *loop, void *link) {
 484   assert(loop && loop->kind == k_ir_loop);
 485 #ifdef DEBUG_libfirm
 486   loop->link = link;
 487 #endif
 488 }
 489 void *get_loop_link (const ir_loop *loop) {
 490   assert(loop && loop->kind == k_ir_loop);
 491 #ifdef DEBUG_libfirm
 492   return loop->link;
 493 #else
 494   return NULL;
 495 #endif
 496 }
 497
 498 /* The outermost loop is remarked in the surrounding graph. */
 499 void     set_irg_loop(ir_graph *irg, ir_loop *loop) {
 500   assert(irg);
 501   irg->loop = loop;
 502 }
 503 ir_loop *get_irg_loop(ir_graph *irg) {
 504   assert(irg);
 505   return irg->loop;
 506 }
 507
 508
 509 /**********************************************************************/
 510 /* Constructing and destructing the loop/backedge information.       **/
 511 /**********************************************************************/
 512
 513 /* Initialization steps. **********************************************/
 514
 515 static INLINE void
 516 init_node (ir_node *n, void *env) {
 517   set_irn_link (n, new_scc_info());
 518   clear_backedges(n);
 519 #if 0
 520   /* Also init nodes not visible in intraproc_view. */
 521     /* @@@ init_node is called for too many nodes -- this wastes memory!.
 522        The mem is not lost as its on the obstack. */
 523   if (get_irn_op(n) == op_Filter) {
 524     for (i = 0; i < get_Filter_n_cg_preds(n); i++)
 525       init_node(get_Filter_cg_pred(n, i), NULL);
 526   }
 527   if (get_irn_op(n) == op_Block) {
 528     for (i = 0; i < get_Block_cg_n_cfgpreds(n); i++) {
 529       init_node(get_Block_cg_cfgpred(n, i), NULL);
 530     }
 531   }
 532   /* The following pattern matches only after a call from above pattern. */
 533   if ((get_irn_op(n) == op_Proj) /*&& (get_Proj_proj(n) == 0)*/) {
 534     /* @@@ init_node is called for every proj -- this wastes memory!.
 535        The mem is not lost as its on the obstack. */
 536     ir_node *cb = get_Proj_pred(n);
 537     if ((get_irn_op(cb) == op_CallBegin) ||
 538     (get_irn_op(cb) == op_EndReg) ||
 539     (get_irn_op(cb) == op_EndExcept)) {
 540       init_node(cb, NULL);
 541       init_node(get_nodes_Block(cb), NULL);
 542     }
 543   }
 544 #endif
 545 }
 546
 547 static INLINE void
 548 init_scc_common (void) {
 549   current_dfn = 1;
 550   loop_node_cnt = 0;
 551   if (!node_loop_map) node_loop_map = pmap_create();
 552   init_stack();
 553 }
 554
 555 static INLINE void
 556 init_scc (ir_graph *irg) {
 557   init_scc_common();
 558   irg_walk_graph (irg, init_node, NULL, NULL);
 559   /*
 560   irg_walk (irg, link_to_reg_end, NULL, NULL);
 561   */
 562 }
 563
 564 static INLINE void
 565 init_ip_scc (void) {
 566   init_scc_common();
 567   cg_walk (init_node, NULL, NULL);
 568
 569 #if EXPERIMENTAL_LOOP_TREE
 570   cg_walk (link_to_reg_end, NULL, NULL);
 571 #endif
 572 }
 573
 574 /* Condition for breaking the recursion. */
 575 static bool is_outermost_Start(ir_node *n) {
 576   /* Test whether this is the outermost Start node.  If so
 577      recursion must end. */
 578   if ((get_irn_op(n) == op_Block)     &&
 579       (get_Block_n_cfgpreds(n) == 1)  &&
 580       (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Start) &&
 581       (get_nodes_Block(skip_Proj(get_Block_cfgpred(n, 0))) == n)) {
 582     return true;
 583   }
 584 #if 0
 585   /*  @@@ Bad condition:
 586       not possible in interprocedural view as outermost_graph is
 587       not necessarily the only with a dead-end start block.
 588       Besides current_ir_graph is not set properly. */
 589   if ((get_irn_op(n) == op_Block) &&
 590       (n == get_irg_start_block(current_ir_graph))) {
 591     if ((!interprocedural_view)  ||
 592     (current_ir_graph == outermost_ir_graph))
 593       return true;
 594   }
 595 #endif
 596   return false;
 597 }
 598
 599 /* When to walk from nodes to blocks. Only for Control flow operations? */
 600 static INLINE int
 601 get_start_index(ir_node *n) {
 602 #undef BLOCK_BEFORE_NODE
 603 #define BLOCK_BEFORE_NODE 1
 604
 605 #if BLOCK_BEFORE_NODE
 606
 607   /* This version assures, that all nodes are ordered absolutely.  This allows
 608      to undef all nodes in the heap analysis if the block is false, which means
 609      not reachable.
 610      I.e., with this code, the order on the loop tree is correct. But a (single)
 611      test showed the loop tree is deeper.   */
 612   if (get_irn_op(n) == op_Phi   ||
 613       get_irn_op(n) == op_Block ||
 614       (get_irn_op(n) == op_Filter && interprocedural_view) ||
 615       (get_irg_pinned(get_irn_irg(n)) == floats &&
 616        get_op_pinned(get_irn_op(n)) == floats))
 617     // Here we could test for backedge at -1 which is illegal
 618     return 0;
 619   else
 620     return -1;
 621
 622 #else
 623
 624   /* This version causes deeper loop trees (at least we verified this
 625      for Polymor).
 626      But it guarantees that Blocks are analysed before nodes contained in the
 627      block.  If so, we can set the value to undef if the block is not \
 628      executed. */
 629    if (is_cfop(n) || is_fragile_op(n) || get_irn_op(n) == op_Start)
 630      return -1;
 631    else
 632      return 0;
 633
 634 #endif
 635 }
 636
 637
 638 #if 0
 639 /* Returns current_ir_graph and set it to the irg of predecessor index
 640    of node n. */
 641 static INLINE ir_graph *
 642 switch_irg (ir_node *n, int index) {
 643   ir_graph *old_current = current_ir_graph;
 644
 645   if (interprocedural_view) {
 646     /* Only Filter and Block nodes can have predecessors in other graphs. */
 647     if (get_irn_op(n) == op_Filter)
 648       n = get_nodes_Block(n);
 649     if (get_irn_op(n) == op_Block) {
 650       ir_node *cfop = skip_Proj(get_Block_cfgpred(n, index));
 651       if (is_ip_cfop(cfop)) {
 652     current_ir_graph = get_irn_irg(cfop);
 653     set_irg_visited(current_ir_graph, get_max_irg_visited());
 654       }
 655     }
 656   }
 657
 658   return old_current;
 659 }
 660
 661 /* Walks up the stack passing n and then finding the node
 662    where we walked into the irg n is contained in.
 663    Here we switch the irg. */
 664 static ir_graph *
 665 find_irg_on_stack (ir_node *n) {
 666   ir_node *m;
 667   ir_graph *old_current = current_ir_graph;
 668   int i;
 669
 670   if (interprocedural_view) {
 671     for (i = tos; i >= 0; i--) {
 672       if (stack[i] == n) break;
 673     }
 674     if (i < 0) i = tos;
 675
 676     assert (i >= 0);
 677     for (; i >= 0; i--) {
 678       m = stack[i];
 679       /*printf(" Visiting %d ", i); DDMN(m);*/
 680       if (is_ip_cfop(m)) {
 681     current_ir_graph = get_irn_irg(m);
 682     break;
 683       }
 684       if (get_irn_op(m) == op_Filter) {
 685     /* Find the corresponding ip_cfop */
 686     ir_node *pred = stack[i+1];
 687     int j;
 688     for (j = 0; j < get_Filter_n_cg_preds(m); j++)
 689       if (get_Filter_cg_pred(m, j) == pred) break;
 690     if (j >= get_Filter_n_cg_preds(m))
 691       /* It is a filter we didn't pass as the predecessors are marked. */
 692       continue;
 693     assert(get_Filter_cg_pred(m, j) == pred);
 694     switch_irg(m, j);
 695     break;
 696       }
 697     }
 698   }
 699
 700   return old_current;
 701 }
 702 #endif
 703
 704 #if 0
 705 static void test(ir_node *pred, ir_node *root, ir_node *this) {
 706   int i;
 707   if (get_irn_uplink(pred) >= get_irn_uplink(root)) return;
 708
 709   printf("this: %d ", get_irn_uplink(this)); DDMN(this);
 710   printf("pred: %d ", get_irn_uplink(pred)); DDMN(pred);
 711   printf("root: %d ", get_irn_uplink(root)); DDMN(root);
 712
 713   printf("tos: %d\n", tos);
 714
 715   for (i = tos; i >= 0; i--) {
 716     ir_node *n = stack[i];
 717     if (!n) continue;
 718     printf(" uplink: %d, pos: %d ", get_irn_uplink(n), i); DDMN(n);
 719   }
 720 }
 721 #endif
 722
 723 /* Test for legal loop header: Block, Phi, ... */
 724 INLINE static bool is_possible_loop_head(ir_node *n) {
 725   ir_op *op = get_irn_op(n);
 726   return ((op == op_Block) ||
 727           (op == op_Phi) ||
 728           ((op == op_Filter) && interprocedural_view));
 729 }
 730
 731 /* Returns true if n is a loop header, i.e., it is a Block, Phi
 732    or Filter node and has predecessors within the loop and out
 733    of the loop.
 734    @arg root: only needed for assertion. */
 735 static bool
 736 is_head (ir_node *n, ir_node *root)
 737 {
 738   int i, arity;
 739   int some_outof_loop = 0, some_in_loop = 0;
 740
 741   /* Test for legal loop header: Block, Phi, ... */
 742   if (!is_possible_loop_head(n))
 743     return false;
 744
 745   if (!is_outermost_Start(n)) {
 746     arity = get_irn_arity(n);
 747     for (i = get_start_index(n); i < arity; i++) {
 748       ir_node *pred = get_irn_n(n, i);
 749       assert(pred);
 750       if (is_backedge(n, i)) continue;
 751       if (!irn_is_in_stack(pred)) {
 752         some_outof_loop = 1;
 753       } else {
 754         if(get_irn_uplink(pred) < get_irn_uplink(root))
 755           {
 756             DDMN(pred); DDMN(root);
 757           }
 758         assert(get_irn_uplink(pred) >= get_irn_uplink(root));
 759         some_in_loop = 1;
 760       }
 761     }
 762   }
 763   return some_outof_loop && some_in_loop;
 764 }
 765
 766 /* Returns index of the predecessor with the smallest dfn number
 767    greater-equal than limit. */
 768 static int
 769 smallest_dfn_pred (ir_node *n, int limit)
 770 {
 771   int i, index = -2, min = -1;
 772
 773   if (!is_outermost_Start(n)) {
 774     int arity = get_irn_arity(n);
 775     for (i = get_start_index(n); i < arity; i++) {
 776       ir_node *pred = get_irn_n(n, i);
 777       assert(pred);
 778       if (is_backedge(n, i) || !irn_is_in_stack(pred)) continue;
 779       if (get_irn_dfn(pred) >= limit && (min == -1 || get_irn_dfn(pred) < min)) {
 780         index = i;
 781         min = get_irn_dfn(pred);
 782       }
 783     }
 784   }
 785   return index;
 786 }
 787
 788 /* Returns index of the predecessor with the largest dfn number. */
 789 static int
 790 largest_dfn_pred (ir_node *n)
 791 {
 792   int i, index = -2, max = -1;
 793
 794   if (!is_outermost_Start(n)) {
 795     int arity = get_irn_arity(n);
 796     for (i = get_start_index(n); i < arity; i++) {
 797       ir_node *pred = get_irn_n(n, i);
 798       if (is_backedge (n, i) || !irn_is_in_stack(pred)) continue;
 799       if (get_irn_dfn(pred) > max) {
 800         index = i;
 801         max = get_irn_dfn(pred);
 802       }
 803     }
 804   }
 805   return index;
 806 }
 807
 808 /* Searches the stack for possible loop heads.  Tests these for backedges.
 809    If it finds a head with an unmarked backedge it marks this edge and
 810    returns the tail of the loop.
 811    If it finds no backedge returns NULL.
 812    ("disable_backedge" in fiasco) */
 813
 814 static ir_node *
 815 find_tail (ir_node *n) {
 816   ir_node *m;
 817   int i, res_index = -2;
 818
 819   /*
 820     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 821   */
 822
 823   m = stack[tos-1];  /* tos = top of stack */
 824   if (is_head (m, n)) {
 825     res_index = smallest_dfn_pred(m, 0);
 826     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 827     (n ==  m))
 828       return NULL;
 829   } else {
 830     if (m == n) return NULL;
 831     for (i = tos-2; ; --i) {
 832       m = stack[i];
 833       if (is_head (m, n)) {
 834         res_index = smallest_dfn_pred (m, get_irn_dfn(m) + 1);
 835         if (res_index == -2)  /* no smallest dfn pred found. */
 836           res_index = largest_dfn_pred (m);
 837         break;
 838       }
 839     }
 840   }
 841   assert (res_index > -2);
 842
 843   set_backedge (m, res_index);
 844   return is_outermost_Start(n) ? NULL : get_irn_n(m, res_index);
 845 }
 846
 847
 848 #if EXPERIMENTAL_LOOP_TREE
 849
 850 /*  ----------------------------------------------------------------
 851     AS:  This is experimantal code to build loop trees suitable for
 852     the heap analysis. Does not work correctly right now... :-(
 853
 854
 855     Search in stack for the corresponding first Call-End-ProjX that
 856     corresponds to one of the control flow predecessors of the given
 857     block, that is the possible callers.
 858     returns: the control predecessor to chose\
 859     or       -1 if no corresponding Call-End-Node could be found
 860              on the stack.
 861     - -------------------------------------------------------------- */
 862
 863 int search_endproj_in_stack(ir_node *start_block)
 864 {
 865   int i, j;
 866   assert(is_Block(start_block));
 867   for(i = tos - 1; i >= 0; --i)
 868     {
 869       DDMN(stack[i]);
 870       if(get_irn_op(stack[i]) == op_Proj && get_irn_mode(stack[i]) == mode_X &&
 871          get_irn_op(get_irn_n(stack[i], 0)) == op_EndReg)
 872         {
 873           printf("FOUND PROJ!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
 874           ir_node *end_projx = stack[i];
 875
 876           for(j = 0; j < get_irn_arity(start_block); j++)
 877             {
 878               ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
 879               DDMN(begin_projx);
 880               if(get_irn_n(start_block, j) == begin_projx)
 881                 {
 882                   printf("FOUND IT!!!!!!!!!!!!!!!!!!\n");
 883                   return(j);
 884                 }
 885             }
 886         }
 887     }
 888   return(-1);
 889 }
 890
 891
 892 static pmap *projx_link = NULL;
 893
 894 void link_to_reg_end (ir_node *n, void *env) {
 895   if(get_irn_op(n) == op_Proj && get_irn_mode(n) == mode_X && get_irn_op(get_irn_n(n, 0)) == op_EndReg)
 896     {
 897       /* Reg End Projx -> Find the CallBegin Projx and hash it */
 898       ir_node *end_projx = n;
 899       ir_node *begin_projx = get_Block_cfgpred(get_irg_start_block(get_irn_irg(end_projx)), get_Proj_proj(end_projx));
 900       printf("Linked the following ProjxNodes:\n");
 901       DDMN(begin_projx);
 902       DDMN(end_projx);
 903       set_projx_link(begin_projx, end_projx);
 904     }
 905 }
 906
 907 void set_projx_link(ir_node *cb_projx, ir_node *end_projx)
 908 {
 909   if(projx_link == NULL)
 910     projx_link = pmap_create();
 911   pmap_insert(projx_link, (void *)cb_projx, (void *)end_projx);
 912 }
 913
 914 ir_node *get_projx_link(ir_node *cb_projx)
 915 {
 916   return((ir_node *) pmap_get(projx_link, (void *)cb_projx));
 917 }
 918
 919 #endif
 920
 921
 922
 923 /*-----------------------------------------------------------*
 924  *                   The core algorithm.                     *
 925  *-----------------------------------------------------------*/
 926
 927
 928 static void scc (ir_node *n) {
 929   int i;
 930   if (irn_visited(n)) return;
 931   mark_irn_visited(n);
 932
 933   /* Initialize the node */
 934   set_irn_dfn(n, current_dfn);      /* Depth first number for this node */
 935   set_irn_uplink(n, current_dfn);   /* ... is default uplink. */
 936   set_irn_loop(n, NULL);
 937   current_dfn ++;
 938   push(n);
 939
 940   /* AS: get_start_index might return -1 for Control Flow Nodes, and thus a negative
 941      array index would be passed to is_backedge(). But CFG Nodes dont't have a backedge array,
 942      so is_backedge does not access array[-1] but correctly returns false! */
 943
 944   if (!is_outermost_Start(n)) {
 945     int arity = get_irn_arity(n);
 946
 947 #if EXPERIMENTAL_LOOP_TREE
 948
 949     /* This is meant to be used with the experimenatl code above.
 950        If the above code is not used any more, this can be deleted, too.... */
 951
 952     if(interprocedural_view &&
 953        is_Block(n) &&
 954        get_irn_op(get_irn_n(n, 0)) == op_Proj &&
 955        get_irn_op(get_irn_n(get_irn_n(n, 0), 0)) == op_CallBegin)
 956       {
 957         /* We are at the start node of a function:
 958            Walk to the callers in the correct order! */
 959         DDMN(n);
 960         DDMN(get_irn_n(get_irn_n(n, 0), 0));
 961         for(i = 0; i < arity; i++)
 962           {
 963             int pred_nr;
 964             ir_node *m;
 965
 966             pred_nr = search_endproj_in_stack(n);
 967             assert(pred_nr >= 0);
 968             if(is_backedge(n, pred_nr))
 969               continue;
 970             m = get_irn_n(n, pred_nr);
 971             scc(m);
 972
 973             if (irn_is_in_stack(m)) {
 974               /* Uplink of m is smaller if n->m is a backedge.
 975                  Propagate the uplink to mark the loop. */
 976               if (get_irn_uplink(m) < get_irn_uplink(n))
 977                 set_irn_uplink(n, get_irn_uplink(m));
 978             }
 979           }
 980       }
 981     else
 982
 983 #endif
 984
 985       {
 986         for (i = get_start_index(n); i < arity; i++) {
 987           ir_node *m;
 988           if (is_backedge(n, i)) continue;
 989           /*      printf("i: %d\n", i); */
 990           m = get_irn_n(n, i); /* get_irn_ip_pred(n, i); */
 991           /* if ((!m) || (get_irn_op(m) == op_Unknown)) continue; */
 992           scc (m);
 993           if (irn_is_in_stack(m)) {
 994             /* Uplink of m is smaller if n->m is a backedge.
 995                Propagate the uplink to mark the loop. */
 996             if (get_irn_uplink(m) < get_irn_uplink(n))
 997               set_irn_uplink(n, get_irn_uplink(m));
 998           }
 999         }
1000       }
1001   }
1002
1003   if (get_irn_dfn(n) == get_irn_uplink(n)) {
1004     /* This condition holds for
1005        1) the node with the incoming backedge.
1006           That is: We found a loop!
1007        2) Straight line code, because no uplink has been propagated, so the
1008           uplink still is the same as the dfn.
1009
1010        But n might not be a proper loop head for the analysis. Proper loop
1011        heads are Block and Phi nodes. find_tail searches the stack for
1012        Block's and Phi's and takes those nodes as loop heads for the current
1013        loop instead and marks the incoming edge as backedge. */
1014
1015     ir_node *tail = find_tail(n);
1016     if (tail) {
1017       /* We have a loop, that is no straight line code,
1018          because we found a loop head!
1019          Next actions: Open a new loop on the loop tree and
1020                        try to find inner loops */
1021
1022
1023 #define NO_LOOPS_WITHOUT_HEAD 1
1024 #if NO_LOOPS_WITHOUT_HEAD
1025
1026       /* This is an adaption of the algorithm from fiasco / optscc to
1027        * avoid loops without Block or Phi as first node.  This should
1028        * severely reduce the number of evaluations of nodes to detect
1029        * a fixpoint in the heap analysis.
1030        * Further it avoids loops without firm nodes that cause errors
1031        * in the heap analyses. */
1032
1033       ir_loop *l;
1034       int close;
1035       if (get_loop_n_elements(current_loop) > 0) {
1036         l = new_loop();
1037         close = 1;
1038       } else {
1039         l = current_loop;
1040         close = 0;
1041       }
1042
1043 #else
1044
1045       ir_loop *l = new_loop();
1046
1047 #endif
1048
1049       /* Remove the loop from the stack ... */
1050       pop_scc_unmark_visit (n);
1051
1052       /*  GL @@@ remove experimental stuff rem = find_irg_on_stack(tail); */
1053
1054       /* The current backedge has been marked, that is temporarily eliminated,
1055          by find tail. Start the scc algorithm
1056          anew on the subgraph thats left (the current loop without the backedge)
1057          in order to find more inner loops. */
1058
1059       scc (tail);
1060
1061       /*  GL @@@ remove experimental stuff current_ir_graph = rem; */
1062
1063       assert (irn_visited(n));
1064 #if NO_LOOPS_WITHOUT_HEAD
1065       if (close)
1066 #endif
1067         close_loop(l);
1068     }
1069     else
1070       {
1071         /* AS: No loop head was found, that is we have straightline code.
1072                Pop all nodes from the stack to the current loop. */
1073       pop_scc_to_loop(n);
1074     }
1075   }
1076 }
1077
1078 /* Constructs backedge information for irg. In interprocedural view constructs
1079    backedges for all methods called by irg, too. */
1080 void construct_backedges(ir_graph *irg) {
1081   ir_graph *rem = current_ir_graph;
1082   ir_loop *head_rem;
1083
1084   assert(!interprocedural_view &&
1085      "not implemented, use construct_ip_backedges");
1086
1087   current_ir_graph = irg;
1088   outermost_ir_graph = irg;
1089
1090   init_scc(current_ir_graph);
1091
1092   current_loop = NULL;
1093   new_loop();  /* sets current_loop */
1094   head_rem = current_loop; /* Just for assertion */
1095
1096   if (interprocedural_view) {
1097     set_irg_visited(current_ir_graph, inc_max_irg_visited());
1098     init_ip_walk ();
1099   } else {
1100     inc_irg_visited(current_ir_graph);
1101   }
1102
1103   scc(get_irg_end(current_ir_graph));
1104
1105   if (interprocedural_view) finish_ip_walk();
1106
1107   assert(head_rem == current_loop);
1108   set_irg_loop(current_ir_graph, current_loop);
1109   set_irg_loopinfo_state(current_ir_graph, loopinfo_consistent);
1110   assert(get_irg_loop(current_ir_graph)->kind == k_ir_loop);
1111   /*
1112   irg->loops = current_loop;
1113   if (icfg == 1) {
1114     int count = 0;
1115     int depth = 0;
1116     count_loop (the_loop, &count, &depth);
1117     }
1118   }
1119   */
1120   current_ir_graph = rem;
1121 }
1122
1123
1124 #if 0
1125 void construct_ip_backedges (void) {
1126   ir_graph *rem = current_ir_graph;
1127   int rem_ipv = interprocedural_view;
1128   int i, j;
1129
1130   outermost_ir_graph = get_irp_main_irg();
1131
1132   init_ip_scc();
1133
1134   current_loop = NULL;
1135   new_loop();  /* sets current_loop */
1136   interprocedural_view = 1;
1137
1138   inc_max_irg_visited();
1139   for (i = 0; i < get_irp_n_irgs(); i++)
1140     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1141
1142   for (i = 0; i < get_irp_n_irgs(); i++) {
1143     ir_node *sb;
1144     current_ir_graph = get_irp_irg(i);
1145     /* Find real entry points */
1146     sb = get_irg_start_block(current_ir_graph);
1147     if ((get_Block_n_cfgpreds(sb) > 1) ||
1148     (get_nodes_Block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1149     /* Compute scc for this graph */
1150     outermost_ir_graph = current_ir_graph;
1151     set_irg_visited(outermost_ir_graph, get_max_irg_visited());
1152     scc(get_irg_end(current_ir_graph));
1153     for (j = 0; j < get_End_n_keepalives(get_irg_end(outermost_ir_graph)); j++)
1154       scc(get_End_keepalive(get_irg_end(outermost_ir_graph), j));
1155   }
1156
1157   set_irg_loop(outermost_ir_graph, current_loop);
1158   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1159   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1160
1161   current_ir_graph = rem;
1162   interprocedural_view = rem_ipv;
1163 }
1164 #else
1165 void construct_ip_backedges (void) {
1166   ir_graph *rem = current_ir_graph;
1167   int rem_ipv = interprocedural_view;
1168   int i;
1169
1170   assert(get_irp_ip_view_state() == ip_view_valid);
1171
1172   outermost_ir_graph = get_irp_main_irg();
1173
1174   init_ip_scc();
1175
1176   current_loop = NULL;
1177   new_loop();  /* sets current_loop */
1178   interprocedural_view = 1;
1179
1180   inc_max_irg_visited();
1181   for (i = 0; i < get_irp_n_irgs(); i++)
1182     set_irg_visited(get_irp_irg(i), get_max_irg_visited());
1183
1184   /** We have to start the walk at the same nodes as cg_walk. **/
1185   /* Walk starting at unreachable procedures. Only these
1186    * have End blocks visible in interprocedural view. */
1187   for (i = 0; i < get_irp_n_irgs(); i++) {
1188     ir_node *sb;
1189     current_ir_graph = get_irp_irg(i);
1190
1191     sb = get_irg_start_block(current_ir_graph);
1192
1193     if ((get_Block_n_cfgpreds(sb) > 1) ||
1194     (get_nodes_block(get_Block_cfgpred(sb, 0)) != sb)) continue;
1195
1196     scc(get_irg_end(current_ir_graph));
1197   }
1198
1199   /* Check whether we walked all procedures: there could be procedures
1200      with cyclic calls but no call from the outside. */
1201   for (i = 0; i < get_irp_n_irgs(); i++) {
1202     ir_node *sb;
1203     current_ir_graph = get_irp_irg(i);
1204
1205     /* Test start block: if inner procedure end and end block are not
1206      * visible and therefore not marked. */
1207     sb = get_irg_start_block(current_ir_graph);
1208     if (get_irn_visited(sb) < get_irg_visited(current_ir_graph)) scc(sb);
1209   }
1210
1211   /* Walk all endless loops in inner procedures.
1212    * We recognize an inner procedure if the End node is not visited. */
1213   for (i = 0; i < get_irp_n_irgs(); i++) {
1214     ir_node *e;
1215     current_ir_graph = get_irp_irg(i);
1216
1217     e = get_irg_end(current_ir_graph);
1218     if (get_irn_visited(e) < get_irg_visited(current_ir_graph)) {
1219       int j;
1220       /* Don't visit the End node. */
1221       for (j = 0; j < get_End_n_keepalives(e); j++) scc(get_End_keepalive(e, j));
1222     }
1223   }
1224
1225   set_irg_loop(outermost_ir_graph, current_loop);
1226   set_irg_loopinfo_state(current_ir_graph, loopinfo_ip_consistent);
1227   assert(get_irg_loop(outermost_ir_graph)->kind == k_ir_loop);
1228
1229   current_ir_graph = rem;
1230   interprocedural_view = rem_ipv;
1231 }
1232 #endif
1233
1234 static void reset_backedges(ir_node *n) {
1235   if (is_possible_loop_head(n)) {
1236     int rem = interprocedural_view;
1237     interprocedural_view = 1;
1238     clear_backedges(n);
1239     interprocedural_view = 0;
1240     clear_backedges(n);
1241     interprocedural_view = rem;
1242   }
1243 }
1244
1245 static void loop_reset_backedges(ir_loop *l) {
1246   int i;
1247   reset_backedges(get_loop_node(l, 0));
1248   for (i = 0; i < get_loop_n_nodes(l); ++i)
1249     set_irn_loop(get_loop_node(l, i), NULL);
1250   for (i = 0; i < get_loop_n_sons(l); ++i) {
1251     loop_reset_backedges(get_loop_son(l, i));
1252   }
1253 }
1254
1255 /** Removes all loop information.
1256     Resets all backedges */
1257 void free_loop_information(ir_graph *irg) {
1258   if (get_irg_loop(irg))
1259     loop_reset_backedges(get_irg_loop(irg));
1260   set_irg_loop(irg, NULL);
1261   set_irg_loopinfo_state(current_ir_graph, loopinfo_none);
1262   /* We cannot free the loop nodes, they are on the obstack. */
1263 }
1264
1265
1266 void free_all_loop_information (void) {
1267   int i;
1268   int rem = interprocedural_view;
1269   interprocedural_view = 1;  /* To visit all filter nodes */
1270   for (i = 0; i < get_irp_n_irgs(); i++) {
1271     free_loop_information(get_irp_irg(i));
1272   }
1273   pmap_destroy(node_loop_map);
1274   node_loop_map = NULL;
1275   interprocedural_view = rem;
1276 }
1277
1278
1279
1280
1281
1282 /* Debug stuff *************************************************/
1283
1284 static int test_loop_node(ir_loop *l) {
1285   int i, has_node = 0, found_problem = 0;
1286   loop_element le;
1287
1288   assert(l && l->kind == k_ir_loop);
1289
1290   if (get_loop_n_elements(l) == 0) {
1291     printf(" Loop completely empty! "); DDML(l);
1292     found_problem = 1;
1293     dump_loop(l, "-ha");
1294   }
1295
1296   le = get_loop_element(l, 0);
1297   if (*(le.kind) != k_ir_node) {
1298     assert(le.kind && *(le.kind) == k_ir_loop);
1299     printf(" First loop element is not a node! "); DDML(l);
1300     printf("                                   "); DDML(le.son);
1301
1302     found_problem = 1;
1303     dump_loop(l, "-ha");
1304   }
1305
1306   if ((*(le.kind) == k_ir_node) && !is_possible_loop_head(le.node)) {
1307     printf(" Wrong node as head! "); DDML(l);
1308     printf("                     "); DDMN(le.node);
1309     found_problem = 1;
1310     dump_loop(l, "-ha");
1311   }
1312
1313   if ((get_loop_depth(l) != 0) &&
1314       (*(le.kind) == k_ir_node) && !has_backedges(le.node)) {
1315     printf(" Loop head has no backedges! "); DDML(l);
1316     printf("                             "); DDMN(le.node);
1317     found_problem = 1;
1318     dump_loop(l, "-ha");
1319   }
1320
1321   /* Recur */
1322   has_node = 0;
1323   for (i = 0; i < get_loop_n_elements(l); ++i) {
1324     le = get_loop_element(l, i);
1325     if (*(le.kind) == k_ir_node)
1326       has_node++;
1327     else
1328       if (test_loop_node(le.son)) found_problem = 1;
1329   }
1330
1331   if (has_node == 0) {
1332     printf(" Loop has no firm node! "); DDML(l);
1333     found_problem = 1;
1334     dump_loop(l, "-ha");
1335   }
1336
1337   if (get_loop_loop_nr(l) == 11819)
1338     dump_loop(l, "-ha-debug");
1339
1340   return found_problem;
1341 }
1342
1343 /** Prints all loop nodes that
1344  *  - do not have any firm nodes, only loop sons
1345  *  - the header is not a Phi, Block or Filter.
1346  */
1347 void find_strange_loop_nodes(ir_loop *l) {
1348   int found_problem = 0;
1349   printf("\nTesting loop "); DDML(l);
1350   found_problem = test_loop_node(l);
1351   printf("Finished Test\n\n");
1352   if (found_problem) exit(0);
1353
1354 }