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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/callgraph.c
   4  * Purpose:     Representation and computation of the callgraph.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     21.7.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 # include "config.h"
  14 #endif
  15
  16 #ifdef HAVE_STRING_H
  17 # include <string.h>
  18 #endif
  19 # ifdef HAVE_STDLIB_H
  20 #include <stdlib.h>
  21 #endif
  22
  23 #include "callgraph.h"
  24
  25 #include "irloop_t.h"
  26 #include "irprog_t.h"
  27 #include "irgraph_t.h"
  28 #include "irnode_t.h"
  29
  30 #include "cgana.h"
  31 #include "execution_frequency.h"
  32
  33 #include "array.h"
  34 #include "pmap.h"
  35 #include "hashptr.h"
  36
  37 #include "irgwalk.h"
  38
  39 /* For callees, we want to remember the Call nodes, too. */
  40 struct ana_entry {
  41   ir_graph  *irg;
  42   ir_node  **call_list;
  43   int        max_depth;
  44 };
  45
  46 typedef struct ana_entry ana_entry;
  47
  48 static int master_cg_visited = 0;
  49 static INLINE int  cg_irg_visited     (ir_graph *n);
  50 static INLINE void mark_cg_irg_visited(ir_graph *n);
  51 static INLINE void set_cg_irg_visited (ir_graph *n, int i);
  52
  53 irp_callgraph_state get_irp_callgraph_state(void) {
  54   return irp->callgraph_state;
  55 }
  56 void                set_irp_callgraph_state(irp_callgraph_state s) {
  57   irp->callgraph_state = s;
  58 }
  59
  60 /* The functions that call irg. */
  61 int       get_irg_n_callers(ir_graph *irg) {
  62   if (irg->callers) return ARR_LEN(irg->callers);
  63   return -1;
  64 }
  65 ir_graph *get_irg_caller(ir_graph *irg, int pos) {
  66   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  67   if (irg->callers) return irg->callers[pos];
  68   return NULL;
  69 }
  70 int       is_irg_caller_backedge(ir_graph *irg, int pos) {
  71   assert (pos >= 0 && pos < get_irg_n_callers(irg));
  72   return  irg->caller_isbe[pos];
  73 }
  74
  75 static void       set_irg_caller_backedge(ir_graph *irg, ir_graph *caller) {
  76   int i, n_callers = get_irg_n_callers(irg);
  77   for (i = 0; i < n_callers; ++i) {
  78     if (get_irg_caller(irg, i) == caller) {
  79       irg->caller_isbe[i] = 1;
  80       break;
  81     }
  82   }
  83 }
  84
  85 int       has_irg_caller_backedge(ir_graph *irg) {
  86   int i, n_callers = get_irg_n_callers(irg);
  87   for (i = 0; i < n_callers; ++i)
  88     if (is_irg_caller_backedge(irg, i)) return 1;
  89   return 0;
  90 }
  91
  92 static int reverse_pos(ir_graph *callee, int pos_caller) {
  93   ir_graph *caller = get_irg_caller(callee, pos_caller);
  94   /* search the other relation for the corresponding edge. */
  95   int pos_callee = -1;
  96   int i, n_callees = get_irg_n_callees(caller);
  97   for (i = 0; i < n_callees; ++i) {
  98     if (get_irg_callee(caller, i) == callee) {
  99       pos_callee = i;
 100       break;
 101     }
 102   }
 103
 104   assert(pos_callee >= 0);
 105
 106   return pos_callee;
 107 }
 108
 109 int get_irg_caller_loop_depth(ir_graph *irg, int pos) {
 110   ir_graph *caller     = get_irg_caller(irg, pos);
 111   int       pos_callee = reverse_pos(irg, pos);
 112
 113   return get_irg_callee_loop_depth(caller, pos_callee);
 114 }
 115
 116
 117 /* The functions called by irg. */
 118 int       get_irg_n_callees(ir_graph *irg) {
 119   if (irg->callees) return ARR_LEN(irg->callees);
 120   return -1;
 121 }
 122 ir_graph *get_irg_callee(ir_graph *irg, int pos) {
 123   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 124   if (irg->callees) return ((ana_entry *)irg->callees[pos])->irg;
 125   return NULL;
 126 }
 127 int       is_irg_callee_backedge(ir_graph *irg, int pos) {
 128   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 129   return irg->callee_isbe[pos];
 130 }
 131 int       has_irg_callee_backedge(ir_graph *irg) {
 132   int i, n_callees = get_irg_n_callees(irg);
 133   for (i = 0; i < n_callees; ++i)
 134     if (is_irg_callee_backedge(irg, i)) return 1;
 135   return 0;
 136 }
 137 void       set_irg_callee_backedge(ir_graph *irg, int pos) {
 138   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 139   irg->callee_isbe[pos] = 1;
 140 }
 141
 142 int get_irg_callee_loop_depth(ir_graph *irg, int pos) {
 143   assert (pos >= 0 && pos < get_irg_n_callees(irg));
 144   if (irg->callees) return ((ana_entry *)irg->callees[pos])->max_depth;
 145   return -1;
 146 }
 147
 148
 149
 150 double get_irg_callee_execution_frequency(ir_graph *irg, int pos) {
 151   ir_node **arr = ((ana_entry *)irg->callees[pos])->call_list;
 152   int i, n_Calls = ARR_LEN(arr);
 153   double freq = 0;
 154
 155   for (i = 0; i < n_Calls; ++i) {
 156     freq += get_irn_exec_freq(arr[i]);
 157   }
 158   return freq;
 159 }
 160
 161 double get_irg_callee_method_execution_frequency(ir_graph *irg, int pos) {
 162   double call_freq = get_irg_callee_execution_frequency(irg, pos);
 163   double meth_freq = get_irg_method_execution_frequency(irg);
 164   return call_freq * meth_freq;
 165 }
 166
 167
 168 double get_irg_caller_method_execution_frequency(ir_graph *irg, int pos) {
 169   ir_graph *caller     = get_irg_caller(irg, pos);
 170   int       pos_callee = reverse_pos(irg, pos);
 171
 172   return get_irg_callee_method_execution_frequency(caller, pos_callee);
 173 }
 174
 175
 176
 177 /* --------------------- Compute the callgraph ------------------------ */
 178
 179 /**
 180  * Walker called by compute_callgraph()
 181  */
 182 static void ana_Call(ir_node *n, void *env) {
 183   int i, n_callees;
 184   ir_graph *irg;
 185
 186   if (get_irn_op(n) != op_Call) return;
 187
 188   irg = get_irn_irg(n);
 189   n_callees = get_Call_n_callees(n);
 190   for (i = 0; i < n_callees; ++i) {
 191     entity *callee_e = get_Call_callee(n, i);
 192     ir_graph *callee = get_entity_irg(callee_e);
 193
 194     if (callee) {
 195       ana_entry buf = { callee, NULL, 0};
 196       ana_entry *found;
 197       int depth;
 198
 199       pset_insert((pset *)callee->callers, irg, HASH_PTR(irg));
 200       found = pset_find((pset *)irg->callees, &buf, HASH_PTR(callee));
 201       if (found) {  /* add Call node to list, compute new nesting. */
 202         ir_node **arr = found->call_list;
 203         ARR_APP1(ir_node *, arr, n);
 204         found->call_list = arr;
 205       } else { /* New node, add Call node and init nesting. */
 206         found = (ana_entry *) obstack_alloc (irg->obst, sizeof (ana_entry));
 207         found->irg = callee;
 208         found->call_list = NEW_ARR_F(ir_node *, 1);
 209         found->call_list[0] = n;
 210         found->max_depth = 0;
 211         pset_insert((pset *)irg->callees, found, HASH_PTR(callee));
 212       }
 213       depth = get_loop_depth(get_irn_loop(get_nodes_block(n)));
 214       found->max_depth = (depth > found->max_depth) ? depth : found->max_depth;
 215     }
 216   }
 217 }
 218
 219 /** compare two ir graphs in a ana_entry */
 220 static int ana_entry_cmp(const void *elt, const void *key) {
 221   const ana_entry *e1 = elt;
 222   const ana_entry *e2 = key;
 223   return e1->irg != e2->irg;
 224 }
 225
 226 /** compare two ir graphs */
 227 static int graph_cmp(const void *elt, const void *key) {
 228   return elt != key;
 229 }
 230
 231
 232 /* Construct and destruct the callgraph. */
 233 void compute_callgraph(void) {
 234   int i, n_irgs = get_irp_n_irgs();
 235
 236   assert(! get_interprocedural_view());  /* Else walking will not reach the Call nodes. */
 237
 238   /* initialize */
 239   free_callgraph();
 240   for (i = 0; i < n_irgs; ++i) {
 241     ir_graph *irg = get_irp_irg(i);
 242     assert(get_irg_callee_info_state(irg) == irg_callee_info_consistent);
 243     irg->callees = (ir_graph **)new_pset(ana_entry_cmp, 8);
 244     irg->callers = (ir_graph **)new_pset(graph_cmp, 8);
 245     //construct_cf_backedges(irg);
 246   }
 247
 248   /* Compute the call graph */
 249   for (i = 0; i < n_irgs; ++i) {
 250     ir_graph *irg = get_irp_irg(i);
 251     construct_cf_backedges(irg);   // We also find the maximal loop depth of a call.
 252     irg_walk_graph(irg, ana_Call, NULL, NULL);
 253   }
 254
 255   /* Change the sets to arrays. */
 256   for (i = 0; i < n_irgs; ++i) {
 257     int j, count;
 258     ir_graph *c, *irg = get_irp_irg(i);
 259     pset *callee_set, *caller_set;
 260
 261     callee_set = (pset *)irg->callees;
 262     count = pset_count(callee_set);
 263     irg->callees = NEW_ARR_F(ir_graph *, count);
 264     irg->callee_isbe = xcalloc(count, sizeof(irg->callee_isbe[0]));
 265     c = pset_first(callee_set);
 266     for (j = 0; j < count; ++j) {
 267       irg->callees[j] = c;
 268       c = pset_next(callee_set);
 269     }
 270     del_pset(callee_set);
 271     assert(c == NULL);
 272
 273     caller_set = (pset *)irg->callers;
 274     count = pset_count(caller_set);
 275     irg->callers = NEW_ARR_F(ir_graph *, count);
 276     irg->caller_isbe =  xcalloc(count, sizeof(irg->caller_isbe[0]));
 277     c = pset_first(caller_set);
 278     for (j = 0; j < count; ++j) {
 279       irg->callers[j] = c;
 280       c = pset_next(caller_set);
 281     }
 282     del_pset(caller_set);
 283     assert(c == NULL);
 284   }
 285   set_irp_callgraph_state(irp_callgraph_consistent);
 286 }
 287
 288 void free_callgraph(void) {
 289   int i, n_irgs = get_irp_n_irgs();
 290   for (i = 0; i < n_irgs; ++i) {
 291     ir_graph *irg = get_irp_irg(i);
 292     if (irg->callees) DEL_ARR_F(irg->callees);
 293     if (irg->callers) DEL_ARR_F(irg->callers);
 294     if (irg->callee_isbe) free(irg->callee_isbe);
 295     if (irg->caller_isbe) free(irg->caller_isbe);
 296     irg->callees = NULL;
 297     irg->callers = NULL;
 298     irg->callee_isbe = NULL;
 299     irg->caller_isbe = NULL;
 300   }
 301   set_irp_callgraph_state(irp_callgraph_none);
 302 }
 303
 304 /* ----------------------------------------------------------------------------------- */
 305 /* A walker for the callgraph                                                          */
 306 /* ----------------------------------------------------------------------------------- */
 307
 308
 309 static void do_walk(ir_graph *irg, callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 310   int i, n_callees;
 311
 312   if (cg_irg_visited(irg)) return;
 313   mark_cg_irg_visited(irg);
 314
 315   pre(irg, env);
 316
 317   n_callees = get_irg_n_callees(irg);
 318   for (i = 0; i < n_callees; i++) {
 319     ir_graph *m = get_irg_callee(irg, i);
 320     do_walk(m, pre, post, env);
 321   }
 322
 323   post(irg, env);
 324 }
 325
 326 void callgraph_walk(callgraph_walk_func *pre, callgraph_walk_func *post, void *env) {
 327   int i, n_irgs = get_irp_n_irgs();
 328   master_cg_visited++;
 329
 330   do_walk(get_irp_main_irg(), pre, post, env);
 331   for (i = 0; i < n_irgs; i++) {
 332     ir_graph *irg = get_irp_irg(i);
 333     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
 334       do_walk(irg, pre, post, env);
 335   }
 336   for (i = 0; i < n_irgs; i++) {
 337     ir_graph *irg = get_irp_irg(i);
 338     if (!cg_irg_visited(irg))
 339       do_walk(irg, pre, post, env);
 340   }
 341 }
 342
 343 /* ----------------------------------------------------------------------------------- */
 344 /* loop construction algorithm                                                         */
 345 /* ----------------------------------------------------------------------------------- */
 346
 347 static ir_graph *outermost_ir_graph;      /**< The outermost graph the scc is computed
 348                       for */
 349 static ir_loop *current_loop;      /**< Current cfloop construction is working
 350                       on. */
 351 static int loop_node_cnt = 0;      /**< Counts the number of allocated cfloop nodes.
 352                       Each cfloop node gets a unique number.
 353                       What for? ev. remove. @@@ */
 354 static int current_dfn = 1;        /**< Counter to generate depth first numbering
 355                       of visited nodes.  */
 356
 357
 358 /**********************************************************************/
 359 /* Node attributes                                                   **/
 360 /**********************************************************************/
 361
 362 typedef struct scc_info {
 363   int in_stack;          /**< Marks whether node is on the stack. */
 364   int dfn;               /**< Depth first search number. */
 365   int uplink;            /**< dfn number of ancestor. */
 366   int visited;
 367 } scc_info;
 368
 369 /**
 370  * allocates a new scc_info of the obstack
 371  */
 372 static INLINE scc_info *new_scc_info(void) {
 373   scc_info *info = obstack_alloc (outermost_ir_graph->obst, sizeof(*info));
 374   memset(info, 0, sizeof(*info));
 375   return info;
 376 }
 377
 378 static INLINE int
 379 cg_irg_visited(ir_graph *n) {
 380   scc_info *info = get_irg_link(n);
 381   return (info->visited >= master_cg_visited);
 382 }
 383
 384 static INLINE void
 385 mark_cg_irg_visited(ir_graph *n) {
 386   scc_info *info = get_irg_link(n);
 387   info->visited = master_cg_visited;
 388 }
 389
 390 static INLINE void
 391 set_cg_irg_visited(ir_graph *n, int i) {
 392   scc_info *info = get_irg_link(n);
 393   info->visited = i;
 394 }
 395
 396 static INLINE int
 397 get_cg_irg_visited(ir_graph *n) {
 398   scc_info *info = get_irg_link(n);
 399   return info->visited;
 400 }
 401
 402 static INLINE void
 403 mark_irg_in_stack (ir_graph *n) {
 404   scc_info *info = get_irg_link(n);
 405   assert(info);
 406   info->in_stack = 1;
 407 }
 408
 409 static INLINE void
 410 mark_irg_not_in_stack (ir_graph *n) {
 411   scc_info *info = get_irg_link(n);
 412   assert(info);
 413   info->in_stack = 0;
 414 }
 415
 416 static INLINE int
 417 irg_is_in_stack (ir_graph *n) {
 418   scc_info *info = get_irg_link(n);
 419   assert(info);
 420   return info->in_stack;
 421 }
 422
 423 static INLINE void
 424 set_irg_uplink (ir_graph *n, int uplink) {
 425   scc_info *info = get_irg_link(n);
 426   assert(info);
 427   info->uplink = uplink;
 428 }
 429
 430 static INLINE int
 431 get_irg_uplink (ir_graph *n) {
 432   scc_info *info = get_irg_link(n);
 433   assert(info);
 434   return info->uplink;
 435 }
 436
 437 static INLINE void
 438 set_irg_dfn (ir_graph *n, int dfn) {
 439   scc_info *info = get_irg_link(n);
 440   assert(info);
 441   info->dfn = dfn;
 442 }
 443
 444 static INLINE int
 445 get_irg_dfn (ir_graph *n) {
 446   scc_info *info = get_irg_link(n);
 447   assert(info);
 448   return info->dfn;
 449 }
 450
 451 /**********************************************************************/
 452 /* A stack.                                                          **/
 453 /**********************************************************************/
 454
 455 static ir_graph **stack = NULL;
 456 static int tos = 0;                /**< top of stack */
 457
 458 /**
 459  * initialize the irg stack
 460  */
 461 static INLINE void init_stack(void) {
 462   if (stack) {
 463     ARR_RESIZE (ir_graph *, stack, 1000);
 464   } else {
 465     stack = NEW_ARR_F (ir_graph *, 1000);
 466   }
 467   tos = 0;
 468 }
 469
 470 /**
 471  * push a graph on the irg stack
 472  * @param n the graph to be pushed
 473  */
 474 static INLINE void
 475 push (ir_graph *n)
 476 {
 477   if (tos == ARR_LEN (stack)) {
 478     int nlen = ARR_LEN (stack) * 2;
 479     ARR_RESIZE (ir_node *, stack, nlen);
 480   }
 481   stack [tos++] = n;
 482   mark_irg_in_stack(n);
 483 }
 484
 485 /**
 486  * return the topmost graph on the stack and pop it
 487  */
 488 static INLINE ir_graph *
 489 pop (void)
 490 {
 491   ir_graph *n = stack[--tos];
 492   mark_irg_not_in_stack(n);
 493   return n;
 494 }
 495
 496 /**
 497  * The nodes up to n belong to the current loop.
 498  * Removes them from the stack and adds them to the current loop.
 499  */
 500 static INLINE void
 501 pop_scc_to_loop (ir_graph *n)
 502 {
 503   ir_graph *m;
 504
 505   do {
 506     m = pop();
 507     loop_node_cnt++;
 508     set_irg_dfn(m, loop_node_cnt);
 509     add_loop_node(current_loop, (ir_node *)m);
 510     m->l = current_loop;
 511     //m->callgraph_loop_depth = current_loop->depth;
 512   } while(m != n);
 513 }
 514
 515 /* GL ??? my last son is my grandson???  Removes cfloops with no
 516    ir_nodes in them.  Such loops have only another loop as son. (Why
 517    can't they have two loops as sons? Does it never get that far? ) */
 518 static void close_loop (ir_loop *l)
 519 {
 520   int last = get_loop_n_elements(l) - 1;
 521   loop_element lelement = get_loop_element(l, last);
 522   ir_loop *last_son = lelement.son;
 523
 524   if (get_kind(last_son) == k_ir_loop &&
 525       get_loop_n_elements(last_son) == 1) {
 526     ir_loop *gson;
 527
 528     lelement = get_loop_element(last_son, 0);
 529     gson = lelement.son;
 530     if(get_kind(gson) == k_ir_loop) {
 531       loop_element new_last_son;
 532
 533       gson -> outer_loop = l;
 534       new_last_son.son = gson;
 535       l -> children[last] = new_last_son;
 536     }
 537   }
 538
 539   current_loop = l;
 540 }
 541
 542 /**
 543  * Removes and unmarks all nodes up to n from the stack.
 544  * The nodes must be visited once more to assign them to a scc.
 545  */
 546 static INLINE void
 547 pop_scc_unmark_visit (ir_graph *n)
 548 {
 549   ir_graph *m = NULL;
 550
 551   while (m != n) {
 552     m = pop();
 553     set_cg_irg_visited(m, 0);
 554   }
 555 }
 556
 557 /**********************************************************************/
 558 /* The loop data structure.                                          **/
 559 /**********************************************************************/
 560
 561 /**
 562  * Allocates a new loop as son of current_loop.  Sets current_loop
 563  * to the new loop and returns the father.
 564  */
 565 static ir_loop *new_loop (void) {
 566   ir_loop *father, *son;
 567
 568   father = current_loop;
 569
 570   son = obstack_alloc (outermost_ir_graph->obst, sizeof(*son));
 571   memset (son, 0, sizeof(*son));
 572   son->kind     = k_ir_loop;
 573   son->children = NEW_ARR_F (loop_element, 0);
 574   son->n_nodes  = 0;
 575   son->n_sons   = 0;
 576   if (father) {
 577     son->outer_loop = father;
 578     add_loop_son(father, son);
 579     son->depth = father->depth + 1;
 580   } else {  /* The root loop */
 581     son->outer_loop = son;
 582     son->depth      = 0;
 583   }
 584
 585 #ifdef DEBUG_libfirm
 586   son->loop_nr = get_irp_new_node_nr();
 587   son->link    = NULL;
 588 #endif
 589
 590   current_loop = son;
 591   return father;
 592 }
 593
 594 /**********************************************************************/
 595 /* Constructing and destructing the loop/backedge information.       **/
 596 /**********************************************************************/
 597
 598 /* Initialization steps. **********************************************/
 599
 600 static INLINE void
 601 init_scc (void) {
 602   int i;
 603   int n_irgs;
 604
 605   current_dfn   = 1;
 606   loop_node_cnt = 0;
 607   init_stack();
 608
 609   n_irgs = get_irp_n_irgs();
 610   for (i = 0; i < n_irgs; ++i) {
 611     ir_graph *irg = get_irp_irg(i);
 612     set_irg_link(irg, new_scc_info());
 613     irg->callgraph_recursion_depth = 0;
 614     irg->callgraph_loop_depth      = 0;
 615   }
 616 }
 617
 618 /** Returns non-zero if n is a loop header, i.e., it is a Block node
 619  *  and has predecessors within the cfloop and out of the cfloop.
 620  *
 621  *  @param root: only needed for assertion.
 622  */
 623 static int
 624 is_head (ir_graph *n, ir_graph *root)
 625 {
 626   int i, arity;
 627   int some_outof_loop = 0, some_in_loop = 0;
 628
 629   arity = get_irg_n_callees(n);
 630   for (i = 0; i < arity; i++) {
 631     ir_graph *pred = get_irg_callee(n, i);
 632     if (is_irg_callee_backedge(n, i)) continue;
 633     if (!irg_is_in_stack(pred)) {
 634       some_outof_loop = 1;
 635     } else {
 636       if (get_irg_uplink(pred) < get_irg_uplink(root))  {
 637             DDMG(pred); DDMG(root);
 638             assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 639       }
 640       some_in_loop = 1;
 641     }
 642   }
 643
 644   return some_outof_loop & some_in_loop;
 645 }
 646
 647 /**
 648  * Returns non-zero if n is possible loop head of an endless loop.
 649  * I.e., it is a Block, Phi or Filter node and has only predecessors
 650  * within the loop.
 651  * @arg root: only needed for assertion.
 652  */
 653 static int
 654 is_endless_head (ir_graph *n, ir_graph *root)
 655 {
 656   int i, arity;
 657   int some_outof_loop = 0, some_in_loop = 0;
 658
 659   arity = get_irg_n_callees(n);
 660   for (i = 0; i < arity; i++) {
 661     ir_graph *pred = get_irg_callee(n, i);
 662     assert(pred);
 663     if (is_irg_callee_backedge(n, i)) { continue; }
 664     if (!irg_is_in_stack(pred)) {
 665           some_outof_loop = 1;
 666     } else {
 667       if(get_irg_uplink(pred) < get_irg_uplink(root)) {
 668             DDMG(pred); DDMG(root);
 669             assert(get_irg_uplink(pred) >= get_irg_uplink(root));
 670       }
 671       some_in_loop = 1;
 672     }
 673   }
 674
 675   return !some_outof_loop & some_in_loop;
 676 }
 677
 678
 679 /**
 680  * Check whether there is a parallel edge in the ip control flow.
 681  * Only
 682  */
 683 static int
 684 is_ip_head (ir_graph *n, ir_graph *pred)
 685 {
 686   int is_be = 0;
 687   int iv_rem = get_interprocedural_view();
 688   set_interprocedural_view(1);
 689   {
 690     ir_node *sblock = get_irg_start_block(n);
 691     int i, arity = get_Block_n_cfgpreds(sblock);
 692
 693     //printf(" edge from "); DDMG(n);
 694     //printf(" to pred   "); DDMG(pred);
 695     //printf(" sblock    "); DDMN(sblock);
 696
 697     for (i = 0; i < arity; i++) {
 698       ir_node *pred_cfop = skip_Proj(get_Block_cfgpred(sblock, i));
 699       //printf("  "); DDMN(pred_cfop);
 700       if (get_irn_op(pred_cfop) == op_CallBegin) {  /* could be Unknown */
 701         ir_graph *ip_pred = get_irn_irg(pred_cfop);
 702         //printf("   "); DDMG(ip_pred);
 703         if ((ip_pred == pred) && is_backedge(sblock, i)) {
 704               //printf("   found\n");
 705           is_be = 1;
 706         }
 707       }
 708     }
 709   }
 710   set_interprocedural_view(iv_rem);
 711   return is_be;
 712 }
 713
 714 /**
 715  * Returns index of the predecessor with the smallest dfn number
 716  * greater-equal than limit.
 717  */
 718 static int
 719 smallest_dfn_pred (ir_graph *n, int limit)
 720 {
 721   int i, index = -2, min = -1;
 722
 723   int arity = get_irg_n_callees(n);
 724   for (i = 0; i < arity; i++) {
 725     ir_graph *pred = get_irg_callee(n, i);
 726     if (is_irg_callee_backedge(n, i) || !irg_is_in_stack(pred)) continue;
 727     if (get_irg_dfn(pred) >= limit && (min == -1 || get_irg_dfn(pred) < min)) {
 728       index = i;
 729       min = get_irg_dfn(pred);
 730     }
 731   }
 732
 733   return index;
 734 }
 735
 736 /** Returns index of the predecessor with the largest dfn number. */
 737 static int
 738 largest_dfn_pred (ir_graph *n)
 739 {
 740   int i, index = -2, max = -1;
 741
 742   int arity = get_irg_n_callees(n);
 743   for (i = 0; i < arity; i++) {
 744     ir_graph *pred = get_irg_callee(n, i);
 745     if (is_irg_callee_backedge (n, i) || !irg_is_in_stack(pred)) continue;
 746     if (get_irg_dfn(pred) > max) {
 747       index = i;
 748       max = get_irg_dfn(pred);
 749     }
 750   }
 751
 752   return index;
 753 }
 754
 755 #if 0
 756 static ir_graph *
 757 find_tail (ir_graph *n) {
 758   ir_graph *m;
 759   int i, res_index = -2;
 760
 761   /*
 762     if (!icfg && rm_cyclic_phis && remove_cyclic_phis (n)) return NULL;
 763   */
 764   m = stack[tos-1];  /* tos = top of stack */
 765   if (is_head (m, n)) {
 766     res_index = smallest_dfn_pred(m, 0);
 767     if ((res_index == -2) &&  /* no smallest dfn pred found. */
 768     (n == m))
 769       return NULL;
 770   } else {
 771     if (m == n) return NULL;    // Is this to catch Phi - self loops?
 772     for (i = tos-2; i >= 0; --i) {
 773       m = stack[i];
 774
 775       if (is_head (m, n)) {
 776             res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 777             if (res_index == -2)  /* no smallest dfn pred found. */
 778               res_index = largest_dfn_pred (m);
 779
 780             if ((m == n) && (res_index == -2)) {
 781               i = -1;
 782             }
 783             break;
 784       }
 785
 786       /* We should not walk past our selves on the stack:  The upcoming nodes
 787          are not in this loop. We assume a loop not reachable from Start. */
 788       if (m == n) {
 789             i = -1;
 790             break;
 791       }
 792
 793     }
 794
 795     if (i < 0) {
 796       /* A dead loop not reachable from Start. */
 797       for (i = tos-2; i >= 0; --i) {
 798             m = stack[i];
 799             if (is_endless_head (m, n)) {
 800               res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 801               if (res_index == -2)  /* no smallest dfn pred found. */
 802                 res_index = largest_dfn_pred (m);
 803               break;
 804             }
 805             if (m == n) { break; }  /* It's not an unreachable loop, either. */
 806       }
 807       //assert(0 && "no head found on stack");
 808     }
 809
 810   }
 811   assert (res_index > -2);
 812
 813   set_irg_callee_backedge (m, res_index);
 814   return get_irg_callee(m, res_index);
 815 }
 816 #else
 817 static ir_graph *
 818 find_tail (ir_graph *n) {
 819   ir_graph *m;
 820   int i, res_index = -2;
 821
 822   ir_graph *res;
 823   ir_graph *in_and_out    = NULL;
 824   ir_graph *only_in       = NULL;
 825   ir_graph *ip_in_and_out = NULL;
 826   ir_graph *ip_only_in    = NULL;
 827
 828   //printf("find tail for "); DDMG(n);
 829
 830   for (i = tos-1; i >= 0; --i) {
 831     ir_graph *pred = (i < tos -1) ? stack[i+1] : n;
 832     m = stack[i];
 833
 834     if (is_head (m, n)) {
 835       //printf(" found 1a! "); DDM;
 836       in_and_out = m;
 837       if (is_ip_head(pred, m)) {
 838             //printf(" found 1b! "); DDM;
 839             ip_in_and_out = m;
 840       }
 841     } else if (!ip_only_in && is_endless_head(m, n)) {
 842       only_in = m;
 843       //printf(" found 2a! "); DDM;
 844       if (is_ip_head(pred, m)) {
 845             //printf(" found 2b! "); DDM;
 846             ip_only_in = m;
 847       }
 848     } else if (is_ip_head(pred, m)) {
 849       //printf(" found 3! "); DDM;   This happens for self recursions in the second
 850       //assert(0);                   scc iteration (the one to flip the loop.)
 851     }
 852
 853     if (ip_in_and_out) break;    /* That's what we really want. */
 854
 855     if (m == n) break;   /* Don't walk past n on the stack! */
 856   }
 857
 858
 859   if (!in_and_out && !only_in)
 860     /* There is no loop */
 861     return NULL;
 862
 863
 864   /* Is there a head in the callgraph without a head in the
 865      ip cf graph? */
 866   assert(in_and_out || only_in);
 867
 868   m = (ip_in_and_out) ? ip_in_and_out : ip_only_in;
 869
 870   if (!m)
 871     m = (in_and_out) ? in_and_out : only_in;
 872
 873   //printf("*** head is "); DDMG(m);
 874
 875   res_index = smallest_dfn_pred (m, get_irg_dfn(m) + 1);
 876   if (res_index == -2)  /* no smallest dfn pred found. */
 877     res_index = largest_dfn_pred (m);
 878
 879   set_irg_callee_backedge (m, res_index);
 880   res = get_irg_callee(m, res_index);
 881   //printf("*** tail is "); DDMG(res);
 882   return res;
 883 }
 884 #endif
 885
 886
 887 /*-----------------------------------------------------------*
 888  *                   The core algorithm.                     *
 889  *-----------------------------------------------------------*/
 890
 891
 892 static void cgscc (ir_graph *n) {
 893   int i, arity;
 894
 895   if (cg_irg_visited(n)) return;
 896   mark_cg_irg_visited(n);
 897
 898   /* Initialize the node */
 899   set_irg_dfn(n, current_dfn);      /* Depth first number for this node */
 900   set_irg_uplink(n, current_dfn);   /* ... is default uplink. */
 901   current_dfn ++;
 902   push(n);
 903
 904   arity = get_irg_n_callees(n);
 905   for (i = 0; i < arity; i++) {
 906     ir_graph *m;
 907     if (is_irg_callee_backedge(n, i)) continue;
 908     m = get_irg_callee(n, i);
 909
 910     /** This marks the backedge, but does it guarantee a correct loop tree? */
 911     //if (m == n) { set_irg_callee_backedge(n, i); continue; }
 912
 913     cgscc (m);
 914     if (irg_is_in_stack(m)) {
 915       /* Uplink of m is smaller if n->m is a backedge.
 916              Propagate the uplink to mark the cfloop. */
 917       if (get_irg_uplink(m) < get_irg_uplink(n))
 918             set_irg_uplink(n, get_irg_uplink(m));
 919     }
 920   }
 921
 922   if (get_irg_dfn(n) == get_irg_uplink(n)) {
 923     /* This condition holds for
 924        1) the node with the incoming backedge.
 925        That is: We found a cfloop!
 926        2) Straight line code, because no uplink has been propagated, so the
 927        uplink still is the same as the dfn.
 928
 929        But n might not be a proper cfloop head for the analysis. Proper cfloop
 930        heads are Block and Phi nodes. find_tail searches the stack for
 931        Block's and Phi's and takes those nodes as cfloop heads for the current
 932        cfloop instead and marks the incoming edge as backedge. */
 933
 934     ir_graph *tail = find_tail(n);
 935     if (tail) {
 936       /* We have a cfloop, that is no straight line code,
 937              because we found a cfloop head!
 938              Next actions: Open a new cfloop on the cfloop tree and
 939              try to find inner cfloops */
 940
 941
 942       ir_loop *l = new_loop();
 943
 944       /* Remove the cfloop from the stack ... */
 945       pop_scc_unmark_visit (n);
 946
 947       /* The current backedge has been marked, that is temporarily eliminated,
 948              by find tail. Start the scc algorithm
 949              anew on the subgraph thats left (the current cfloop without the backedge)
 950              in order to find more inner cfloops. */
 951
 952       cgscc (tail);
 953
 954       assert (cg_irg_visited(n));
 955       close_loop(l);
 956     } else {
 957       pop_scc_to_loop(n);
 958     }
 959   }
 960 }
 961
 962
 963 /**
 964  * reset the backedge information for all callers in all irgs
 965  */
 966 static void reset_isbe(void) {
 967   int i, n_irgs = get_irp_n_irgs();
 968
 969   for (i = 0; i < n_irgs; ++i) {
 970     int j, n_cs;
 971     ir_graph *irg = get_irp_irg(i);
 972
 973     n_cs = get_irg_n_callers(irg);
 974     for (j = 0; j < n_cs; ++j) {
 975       irg->caller_isbe[j] = 0;
 976     }
 977
 978     n_cs = get_irg_n_callees(irg);
 979     for (j = 0; j < n_cs; ++j) {
 980       irg->callee_isbe[j] = 0;
 981     }
 982   }
 983 }
 984
 985
 986
 987
 988 /* ----------------------------------------------------------------------------------- */
 989 /* Another algorithm to compute recursion nesting depth                                */
 990 /* Walk the callgraph.  For each crossed edge increase the loop depth by the edge      */
 991 /* weight. Assign graphs the maximal depth.                                            */
 992 /* ----------------------------------------------------------------------------------- */
 993
 994 static void compute_loop_depth (ir_graph *irg, void *env) {
 995   int current_nesting = *(int *) env;
 996   int old_nesting = irg->callgraph_loop_depth;
 997   int old_visited = get_cg_irg_visited(irg);
 998   int i, n_callees;
 999
1000   //return ;
1001
1002   if (cg_irg_visited(irg)) return;
1003
1004   mark_cg_irg_visited(irg);
1005
1006   //printf(" old: %d new %d master %d", old_visited, get_cg_irg_visited(irg), master_cg_visited); DDMG(irg);
1007
1008
1009   if (old_nesting < current_nesting)
1010     irg->callgraph_loop_depth = current_nesting;
1011
1012   if (current_nesting > irp->max_callgraph_loop_depth)
1013     irp->max_callgraph_loop_depth = current_nesting;
1014
1015   if ((old_visited +1 < get_cg_irg_visited(irg)) ||   /* not yet visited */
1016       (old_nesting < current_nesting)) {        /* propagate larger nesting */
1017     /* Don't walk the graph, but a tree that is an unfolded graph. */
1018     n_callees = get_irg_n_callees(irg);
1019     for (i = 0; i < n_callees; i++) {
1020       ir_graph *m = get_irg_callee(irg, i);
1021       *(int *)env += get_irg_callee_loop_depth(irg, i);
1022       compute_loop_depth(m, env);
1023       *(int *)env -= get_irg_callee_loop_depth(irg, i);
1024     }
1025   }
1026
1027   set_cg_irg_visited(irg, master_cg_visited-1);
1028 }
1029
1030 /* ------------------------------------------------------------------------------------ */
1031 /* Another algorithm to compute recursion nesting depth                                 */
1032 /* Walk the callgraph.  For each crossed loop increase the nesting depth by one.        */
1033 /* Assign graphs the maximal nesting depth.   Don't increase if passing loops more than */
1034 /* once.                                                                               */
1035 /* ------------------------------------------------------------------------------------ */
1036
1037
1038 /* For callees, we want to remember the Call nodes, too. */
1039 typedef struct ana_entry2 {
1040   ir_loop **loop_stack;   /**< a stack of ir_loop entries */
1041   int tos;                /**< the top of stack entry */
1042   int recursion_nesting;
1043 } ana_entry2;
1044
1045 /**
1046  * push a loop entry on the stack
1047  */
1048 static void push2(ana_entry2 *e, ir_loop *g) {
1049   if (ARR_LEN(e->loop_stack) == e->tos) {
1050     ARR_APP1(ir_loop *, e->loop_stack, g);
1051   } else {
1052     e->loop_stack[e->tos] = g;
1053   }
1054   ++e->tos;
1055 }
1056
1057 /**
1058  * returns the top of stack and pop it
1059  */
1060 static ir_loop *pop2(ana_entry2 *e) {
1061   return e->loop_stack[--e->tos];
1062 }
1063
1064 /**
1065  * check if a loop g in on the stack. Did not check the TOS.
1066  */
1067 static int in_stack(ana_entry2 *e, ir_loop *g) {
1068   int i;
1069   for (i = e->tos-1; i >= 0; --i) {
1070     if (e->loop_stack[i] == g) return 1;
1071   }
1072   return 0;
1073 }
1074
1075 static void compute_rec_depth (ir_graph *irg, void *env) {
1076   ana_entry2 *e = (ana_entry2 *)env;
1077   ir_loop *l = irg->l;
1078   int depth, old_depth = irg->callgraph_recursion_depth;
1079   int i, n_callees;
1080   int pushed = 0;
1081
1082   if (cg_irg_visited(irg)) return;
1083   mark_cg_irg_visited(irg);
1084
1085   /* -- compute and set the new nesting value -- */
1086   if ((l != irp->outermost_cg_loop) && !in_stack(e, l)) {
1087     push2(e, l);
1088     e->recursion_nesting++;
1089     pushed = 1;
1090   }
1091   depth = e->recursion_nesting;
1092
1093   if (old_depth < depth)
1094     irg->callgraph_recursion_depth = depth;
1095
1096   if (depth > irp->max_callgraph_recursion_depth)
1097     irp->max_callgraph_recursion_depth = depth;
1098
1099   /* -- spread the nesting value -- */
1100   if (depth == 0 || old_depth < depth) {
1101     /* Don't walk the graph, but a tree that is an unfolded graph.
1102        Therefore we unset the visited flag at the end. */
1103     n_callees = get_irg_n_callees(irg);
1104     for (i = 0; i < n_callees; i++) {
1105       ir_graph *m = get_irg_callee(irg, i);
1106       compute_rec_depth(m, env);
1107     }
1108   }
1109
1110   /* -- clean up -- */
1111   if (pushed) {
1112     pop2(e);
1113     e->recursion_nesting--;
1114   }
1115   set_cg_irg_visited(irg, master_cg_visited-1);
1116 }
1117
1118
1119 /* ----------------------------------------------------------------------------------- */
1120 /* Another algorithm to compute the execution frequency of methods ignoring recursions. */
1121 /* Walk the callgraph.  Ignore backedges.  Use sum of execution frequencies of Call     */
1122 /* nodes to evaluate a callgraph edge.                                                 */
1123 /* ----------------------------------------------------------------------------------- */
1124
1125 double get_irg_method_execution_frequency (ir_graph *irg) {
1126   return irg->method_execution_frequency;
1127 }
1128
1129 void set_irg_method_execution_frequency (ir_graph *irg, double freq) {
1130   irg->method_execution_frequency = freq;
1131
1132   if (irp->max_method_execution_frequency < freq)
1133     irp->max_method_execution_frequency = freq;
1134 }
1135
1136 static void compute_method_execution_frequency (ir_graph *irg, void *env) {
1137   int i, n_callers;
1138   double freq;
1139   int    found_edge;
1140   int    n_callees;
1141
1142   if (cg_irg_visited(irg)) return;
1143
1144   /* We need the values of all predecessors (except backedges).
1145      So they must be marked.  Else we will reach the node through
1146      one of the unmarked ones. */
1147   n_callers = get_irg_n_callers(irg);
1148   for (i = 0; i < n_callers; i++) {
1149     ir_graph *m = get_irg_caller(irg, i);
1150     if (is_irg_caller_backedge(irg, i)) continue;
1151     if (!cg_irg_visited(m)) {
1152       return;
1153     }
1154   }
1155   mark_cg_irg_visited(irg);
1156
1157   /* Compute the new frequency. */
1158   freq = 0;
1159   found_edge = 0;
1160   for (i = 0; i < n_callers; i++) {
1161     if (! is_irg_caller_backedge(irg, i)) {
1162       double edge_freq = get_irg_caller_method_execution_frequency(irg, i);
1163       assert(edge_freq >= 0);
1164       freq += edge_freq;
1165       found_edge = 1;
1166     }
1167   }
1168
1169   if (!found_edge) {
1170     /* A starting point: method only called from outside,
1171        or only backedges as predecessors. */
1172     freq = 1;
1173   }
1174
1175   set_irg_method_execution_frequency(irg, freq);
1176
1177   /* recur */
1178   n_callees = get_irg_n_callees(irg);
1179   for (i = 0; i < n_callees; i++) {
1180     compute_method_execution_frequency (get_irg_callee(irg, i), NULL);
1181   }
1182 }
1183
1184
1185 /* ----------------------------------------------------------------------------------- */
1186 /* The recursion stuff driver.                                                         */
1187 /* ----------------------------------------------------------------------------------- */
1188
1189 /* Compute the backedges that represent recursions. */
1190 void find_callgraph_recursions(void) {
1191   int i, n_irgs = get_irp_n_irgs();
1192
1193   reset_isbe();
1194
1195   /* -- compute the looptree. -- */
1196
1197   /* The outermost graph.  We start here.  Then we start at all
1198      functions in irg list that are never called, then at the remaining
1199      unvisited ones. The third step is needed for functions that are not
1200      reachable from the outermost graph, but call themselves in a cycle. */
1201   assert(get_irp_main_irg());
1202   outermost_ir_graph = get_irp_main_irg();
1203   init_scc();
1204
1205   current_loop = NULL;
1206   new_loop();  /* sets current_loop */
1207
1208   master_cg_visited++;
1209   cgscc(outermost_ir_graph);
1210   for (i = 0; i < n_irgs; i++) {
1211     ir_graph *irg = get_irp_irg(i);
1212     if (!cg_irg_visited(irg) && get_irg_n_callers(irg) == 0)
1213       cgscc(irg);
1214   }
1215   for (i = 0; i < n_irgs; i++) {
1216     ir_graph *irg = get_irp_irg(i);
1217     if (!cg_irg_visited(irg))
1218       cgscc(irg);
1219   }
1220   irp->outermost_cg_loop = current_loop;
1221
1222   /* -- Reverse the backedge information. -- */
1223   for (i = 0; i < n_irgs; i++) {
1224     ir_graph *irg = get_irp_irg(i);
1225     int j, n_callees = get_irg_n_callees(irg);
1226     for (j = 0; j < n_callees; ++j) {
1227       if (is_irg_callee_backedge(irg, j))
1228         set_irg_caller_backedge(get_irg_callee(irg, j), irg);
1229     }
1230   }
1231
1232   irp->callgraph_state = irp_callgraph_and_calltree_consistent;
1233 }
1234
1235 void compute_performance_estimates(void) {
1236   int i, n_irgs = get_irp_n_irgs();
1237   int current_nesting;
1238   ana_entry2 e;
1239
1240   /* -- compute the loop depth  -- */
1241   current_nesting = 0;
1242   irp->max_callgraph_loop_depth = 0;
1243   master_cg_visited += 2;
1244   //printf (" ** starting at      "); DDMG(get_irp_main_irg());
1245   compute_loop_depth(get_irp_main_irg(), &current_nesting);
1246   for (i = 0; i < n_irgs; i++) {
1247     ir_graph *irg = get_irp_irg(i);
1248     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1249         get_irg_n_callers(irg) == 0) {
1250       compute_loop_depth(irg, &current_nesting);
1251       //printf (" ** starting at      "); DDMG(irg);
1252     }
1253   }
1254   for (i = 0; i < n_irgs; i++) {
1255     ir_graph *irg = get_irp_irg(i);
1256     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1257       compute_loop_depth(irg, &current_nesting);
1258       //printf (" ** starting at      "); DDMG(irg);
1259     }
1260   }
1261
1262
1263   /* -- compute the recursion depth -- */
1264   e.loop_stack        = NEW_ARR_F(ir_loop *, 0);
1265   e.tos               = 0;
1266   e.recursion_nesting = 0;
1267
1268   irp->max_callgraph_recursion_depth = 0;
1269
1270   master_cg_visited += 2;
1271   compute_rec_depth(get_irp_main_irg(), &e);
1272   //printf (" ++ starting at "); DDMG(get_irp_main_irg());
1273   for (i = 0; i < n_irgs; i++) {
1274     ir_graph *irg = get_irp_irg(i);
1275     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1276         get_irg_n_callers(irg) == 0) {
1277       compute_rec_depth(irg, &e);
1278       //printf (" ++ starting at "); DDMG(irg);
1279     }
1280   }
1281   for (i = 0; i < n_irgs; i++) {
1282     ir_graph *irg = get_irp_irg(i);
1283     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1284       compute_rec_depth(irg, &e);
1285       //printf (" ++ starting at "); DDMG(irg);
1286     }
1287   }
1288
1289   DEL_ARR_F(e.loop_stack);
1290
1291   /* -- compute the execution frequency -- */
1292   irp->max_method_execution_frequency = 0;
1293   master_cg_visited += 2;
1294   assert(get_irg_n_callers(get_irp_main_irg()) == 0);
1295   compute_method_execution_frequency(get_irp_main_irg(), NULL);
1296   for (i = 0; i < n_irgs; i++) {
1297     ir_graph *irg = get_irp_irg(i);
1298     if ((get_cg_irg_visited(irg) < master_cg_visited-1) &&
1299         get_irg_n_callers(irg) == 0) {
1300       compute_method_execution_frequency(irg, NULL);
1301     }
1302   }
1303   for (i = 0; i < n_irgs; i++) {
1304     ir_graph *irg = get_irp_irg(i);
1305     if (get_cg_irg_visited(irg) < master_cg_visited-1) {
1306       compute_method_execution_frequency(irg, NULL);
1307     }
1308   }
1309 }
1310
1311 /* Maximal loop depth of all paths from an external visible method to
1312     this irg. */
1313 int       get_irg_loop_depth(ir_graph *irg) {
1314   assert(irp->callgraph_state == irp_callgraph_consistent ||
1315          irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1316   return  irg->callgraph_loop_depth;
1317 }
1318
1319 /* Maximal recursion depth of all paths from an external visible method to
1320    this irg. */
1321 int       get_irg_recursion_depth(ir_graph *irg) {
1322   assert(irp->callgraph_state == irp_callgraph_and_calltree_consistent);
1323   return irg->callgraph_recursion_depth;
1324 }
1325
1326 void analyse_loop_nesting_depth(void) {
1327   entity **free_methods = NULL;
1328   int arr_len;
1329
1330   /* establish preconditions. */
1331   if (get_irp_callee_info_state() != irg_callee_info_consistent) {
1332     cgana(&arr_len, &free_methods);
1333   }
1334
1335   if (irp_callgraph_consistent != get_irp_callgraph_state()) {
1336     compute_callgraph();
1337   }
1338
1339   find_callgraph_recursions();
1340
1341   compute_performance_estimates();
1342
1343   set_irp_loop_nesting_depth_state(loop_nesting_depth_consistent);
1344 }
1345
1346
1347 loop_nesting_depth_state get_irp_loop_nesting_depth_state(void) {
1348   return irp->lnd_state;
1349 }
1350 void                     set_irp_loop_nesting_depth_state(loop_nesting_depth_state s) {
1351   irp->lnd_state = s;
1352 }
1353 void                     set_irp_loop_nesting_depth_state_inconsistent(void) {
1354   if (irp->lnd_state == loop_nesting_depth_consistent)
1355     irp->lnd_state = loop_nesting_depth_inconsistent;
1356 }