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