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