nsz Git - libfirm/blob - ir/opt/opt_inline.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Dead node elimination and Procedure Inlining.
  23  * @author   Michael Beck, Goetz Lindenmaier
  24  * @version  $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <limits.h>
  31 #include <assert.h>
  32
  33 #include "irnode_t.h"
  34 #include "irgraph_t.h"
  35 #include "irprog_t.h"
  36
  37 #include "iroptimize.h"
  38 #include "ircons_t.h"
  39 #include "iropt_t.h"
  40 #include "irgopt.h"
  41 #include "irgmod.h"
  42 #include "irgwalk.h"
  43
  44 #include "adt/array.h"
  45 #include "adt/pset.h"
  46 #include "adt/pmap.h"
  47 #include "adt/pdeq.h"
  48 #include "adt/xmalloc.h"
  49
  50 #include "irouts.h"
  51 #include "irloop_t.h"
  52 #include "irbackedge_t.h"
  53 #include "cgana.h"
  54 #include "trouts.h"
  55 #include "error.h"
  56
  57 #include "analyze_irg_args.h"
  58 #include "iredges_t.h"
  59 #include "irflag_t.h"
  60 #include "irhooks.h"
  61 #include "irtools.h"
  62
  63
  64 /*------------------------------------------------------------------*/
  65 /* Routines for dead node elimination / copying garbage collection  */
  66 /* of the obstack.                                                  */
  67 /*------------------------------------------------------------------*/
  68
  69 /**
  70  * Remember the new node in the old node by using a field all nodes have.
  71  */
  72 #define set_new_node(oldn, newn)  set_irn_link(oldn, newn)
  73
  74 /**
  75  * Get this new node, before the old node is forgotten.
  76  */
  77 #define get_new_node(oldn) get_irn_link(oldn)
  78
  79 /**
  80  * Check if a new node was set.
  81  */
  82 #define has_new_node(n) (get_new_node(n) != NULL)
  83
  84 /**
  85  * We use the block_visited flag to mark that we have computed the
  86  * number of useful predecessors for this block.
  87  * Further we encode the new arity in this flag in the old blocks.
  88  * Remembering the arity is useful, as it saves a lot of pointer
  89  * accesses.  This function is called for all Phi and Block nodes
  90  * in a Block.
  91  */
  92 static INLINE int
  93 compute_new_arity(ir_node *b) {
  94         int i, res, irn_arity;
  95         int irg_v, block_v;
  96
  97         irg_v = get_irg_block_visited(current_ir_graph);
  98         block_v = get_Block_block_visited(b);
  99         if (block_v >= irg_v) {
 100                 /* we computed the number of preds for this block and saved it in the
 101                    block_v flag */
 102                 return block_v - irg_v;
 103         } else {
 104                 /* compute the number of good predecessors */
 105                 res = irn_arity = get_irn_arity(b);
 106                 for (i = 0; i < irn_arity; i++)
 107                         if (is_Bad(get_irn_n(b, i))) res--;
 108                         /* save it in the flag. */
 109                         set_Block_block_visited(b, irg_v + res);
 110                         return res;
 111         }
 112 }
 113
 114 /**
 115  * Copies the node to the new obstack. The Ins of the new node point to
 116  * the predecessors on the old obstack.  For block/phi nodes not all
 117  * predecessors might be copied.  n->link points to the new node.
 118  * For Phi and Block nodes the function allocates in-arrays with an arity
 119  * only for useful predecessors.  The arity is determined by counting
 120  * the non-bad predecessors of the block.
 121  *
 122  * @param n    The node to be copied
 123  * @param env  if non-NULL, the node number attribute will be copied to the new node
 124  *
 125  * Note: Also used for loop unrolling.
 126  */
 127 static void copy_node(ir_node *n, void *env) {
 128         ir_node *nn, *block;
 129         int new_arity;
 130         ir_op *op = get_irn_op(n);
 131         (void) env;
 132
 133         if (op == op_Bad) {
 134                 /* node copied already */
 135                 return;
 136         } else if (op == op_Block) {
 137                 block = NULL;
 138                 new_arity = compute_new_arity(n);
 139                 n->attr.block.graph_arr = NULL;
 140         } else {
 141                 block = get_nodes_block(n);
 142                 if (op == op_Phi) {
 143                         new_arity = compute_new_arity(block);
 144                 } else {
 145                         new_arity = get_irn_arity(n);
 146                 }
 147         }
 148         nn = new_ir_node(get_irn_dbg_info(n),
 149                 current_ir_graph,
 150                 block,
 151                 op,
 152                 get_irn_mode(n),
 153                 new_arity,
 154                 get_irn_in(n) + 1);
 155         /* Copy the attributes.  These might point to additional data.  If this
 156            was allocated on the old obstack the pointers now are dangling.  This
 157            frees e.g. the memory of the graph_arr allocated in new_immBlock. */
 158         if (op == op_Block) {
 159                 /* we cannot allow blocks WITHOUT macroblock input */
 160                 set_Block_MacroBlock(nn, get_Block_MacroBlock(n));
 161         }
 162         copy_node_attr(n, nn);
 163
 164 #ifdef DEBUG_libfirm
 165         {
 166                 int copy_node_nr = env != NULL;
 167                 if (copy_node_nr) {
 168                         /* for easier debugging, we want to copy the node numbers too */
 169                         nn->node_nr = n->node_nr;
 170                 }
 171         }
 172 #endif
 173
 174         set_new_node(n, nn);
 175         hook_dead_node_elim_subst(current_ir_graph, n, nn);
 176 }
 177
 178 /**
 179  * Copies new predecessors of old node to new node remembered in link.
 180  * Spare the Bad predecessors of Phi and Block nodes.
 181  */
 182 static void copy_preds(ir_node *n, void *env) {
 183         ir_node *nn, *block;
 184         int i, j, irn_arity;
 185         (void) env;
 186
 187         nn = get_new_node(n);
 188
 189         if (is_Block(n)) {
 190                 /* copy the macro block header */
 191                 ir_node *mbh = get_Block_MacroBlock(n);
 192
 193                 if (mbh == n) {
 194                         /* this block is a macroblock header */
 195                         set_Block_MacroBlock(nn, nn);
 196                 } else {
 197                         /* get the macro block header */
 198                         ir_node *nmbh = get_new_node(mbh);
 199                         assert(nmbh != NULL);
 200                         set_Block_MacroBlock(nn, nmbh);
 201                 }
 202
 203                 /* Don't copy Bad nodes. */
 204                 j = 0;
 205                 irn_arity = get_irn_arity(n);
 206                 for (i = 0; i < irn_arity; i++) {
 207                         if (! is_Bad(get_irn_n(n, i))) {
 208                                 ir_node *pred = get_irn_n(n, i);
 209                                 set_irn_n(nn, j, get_new_node(pred));
 210                                 j++;
 211                         }
 212                 }
 213                 /* repair the block visited flag from above misuse. Repair it in both
 214                    graphs so that the old one can still be used. */
 215                 set_Block_block_visited(nn, 0);
 216                 set_Block_block_visited(n, 0);
 217                 /* Local optimization could not merge two subsequent blocks if
 218                    in array contained Bads.  Now it's possible.
 219                    We don't call optimize_in_place as it requires
 220                    that the fields in ir_graph are set properly. */
 221                 if ((get_opt_control_flow_straightening()) &&
 222                         (get_Block_n_cfgpreds(nn) == 1) &&
 223                         is_Jmp(get_Block_cfgpred(nn, 0))) {
 224                         ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0));
 225                         if (nn == old) {
 226                                 /* Jmp jumps into the block it is in -- deal self cycle. */
 227                                 assert(is_Bad(get_new_node(get_irg_bad(current_ir_graph))));
 228                                 exchange(nn, get_new_node(get_irg_bad(current_ir_graph)));
 229                         } else {
 230                                 exchange(nn, old);
 231                         }
 232                 }
 233         } else if (is_Phi(n) && get_irn_arity(n) > 0) {
 234                 /* Don't copy node if corresponding predecessor in block is Bad.
 235                    The Block itself should not be Bad. */
 236                 block = get_nodes_block(n);
 237                 set_nodes_block(nn, get_new_node(block));
 238                 j = 0;
 239                 irn_arity = get_irn_arity(n);
 240                 for (i = 0; i < irn_arity; i++) {
 241                         if (! is_Bad(get_irn_n(block, i))) {
 242                                 ir_node *pred = get_irn_n(n, i);
 243                                 set_irn_n(nn, j, get_new_node(pred));
 244                                 /*if (is_backedge(n, i)) set_backedge(nn, j);*/
 245                                 j++;
 246                         }
 247                 }
 248                 /* If the pre walker reached this Phi after the post walker visited the
 249                    block block_visited is > 0. */
 250                 set_Block_block_visited(get_nodes_block(n), 0);
 251                 /* Compacting the Phi's ins might generate Phis with only one
 252                    predecessor. */
 253                 if (get_irn_arity(nn) == 1)
 254                         exchange(nn, get_irn_n(nn, 0));
 255         } else {
 256                 irn_arity = get_irn_arity(n);
 257                 for (i = -1; i < irn_arity; i++)
 258                         set_irn_n(nn, i, get_new_node(get_irn_n(n, i)));
 259         }
 260         /* Now the new node is complete.  We can add it to the hash table for CSE.
 261            @@@ inlining aborts if we identify End. Why? */
 262         if (!is_End(nn))
 263                 add_identities(current_ir_graph->value_table, nn);
 264 }
 265
 266 /**
 267  * Copies the graph recursively, compacts the keep-alives of the end node.
 268  *
 269  * @param irg           the graph to be copied
 270  * @param copy_node_nr  If non-zero, the node number will be copied
 271  */
 272 static void copy_graph(ir_graph *irg, int copy_node_nr) {
 273         ir_node *oe, *ne, *ob, *nb, *om, *nm; /* old end, new end, old bad, new bad, old NoMem, new NoMem */
 274         ir_node *ka;      /* keep alive */
 275         int i, irn_arity;
 276         unsigned long vfl;
 277
 278         /* Some nodes must be copied by hand, sigh */
 279         vfl = get_irg_visited(irg);
 280         set_irg_visited(irg, vfl + 1);
 281
 282         oe = get_irg_end(irg);
 283         mark_irn_visited(oe);
 284         /* copy the end node by hand, allocate dynamic in array! */
 285         ne = new_ir_node(get_irn_dbg_info(oe),
 286                 irg,
 287                 NULL,
 288                 op_End,
 289                 mode_X,
 290                 -1,
 291                 NULL);
 292         /* Copy the attributes.  Well, there might be some in the future... */
 293         copy_node_attr(oe, ne);
 294         set_new_node(oe, ne);
 295
 296         /* copy the Bad node */
 297         ob = get_irg_bad(irg);
 298         mark_irn_visited(ob);
 299         nb = new_ir_node(get_irn_dbg_info(ob),
 300                 irg,
 301                 NULL,
 302                 op_Bad,
 303                 mode_T,
 304                 0,
 305                 NULL);
 306         copy_node_attr(ob, nb);
 307         set_new_node(ob, nb);
 308
 309         /* copy the NoMem node */
 310         om = get_irg_no_mem(irg);
 311         mark_irn_visited(om);
 312         nm = new_ir_node(get_irn_dbg_info(om),
 313                 irg,
 314                 NULL,
 315                 op_NoMem,
 316                 mode_M,
 317                 0,
 318                 NULL);
 319         copy_node_attr(om, nm);
 320         set_new_node(om, nm);
 321
 322         /* copy the live nodes */
 323         set_irg_visited(irg, vfl);
 324         irg_walk(get_nodes_block(oe), copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
 325
 326         /* Note: from yet, the visited flag of the graph is equal to vfl + 1 */
 327
 328         /* visit the anchors as well */
 329         for (i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
 330                 ir_node *n = get_irg_anchor(irg, i);
 331
 332                 if (n && (get_irn_visited(n) <= vfl)) {
 333                         set_irg_visited(irg, vfl);
 334                         irg_walk(n, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
 335                 }
 336         }
 337
 338         /* copy_preds for the end node ... */
 339         set_nodes_block(ne, get_new_node(get_nodes_block(oe)));
 340
 341         /*- ... and now the keep alives. -*/
 342         /* First pick the not marked block nodes and walk them.  We must pick these
 343            first as else we will oversee blocks reachable from Phis. */
 344         irn_arity = get_End_n_keepalives(oe);
 345         for (i = 0; i < irn_arity; i++) {
 346                 ka = get_End_keepalive(oe, i);
 347                 if (is_Block(ka)) {
 348                         if (get_irn_visited(ka) <= vfl) {
 349                                 /* We must keep the block alive and copy everything reachable */
 350                                 set_irg_visited(irg, vfl);
 351                                 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
 352                         }
 353                         add_End_keepalive(ne, get_new_node(ka));
 354                 }
 355         }
 356
 357         /* Now pick other nodes.  Here we will keep all! */
 358         irn_arity = get_End_n_keepalives(oe);
 359         for (i = 0; i < irn_arity; i++) {
 360                 ka = get_End_keepalive(oe, i);
 361                 if (!is_Block(ka)) {
 362                         if (get_irn_visited(ka) <= vfl) {
 363                                 /* We didn't copy the node yet.  */
 364                                 set_irg_visited(irg, vfl);
 365                                 irg_walk(ka, copy_node, copy_preds, INT_TO_PTR(copy_node_nr));
 366                         }
 367                         add_End_keepalive(ne, get_new_node(ka));
 368                 }
 369         }
 370
 371         /* start block sometimes only reached after keep alives */
 372         set_nodes_block(nb, get_new_node(get_nodes_block(ob)));
 373         set_nodes_block(nm, get_new_node(get_nodes_block(om)));
 374 }
 375
 376 /**
 377  * Copies the graph reachable from current_ir_graph->end to the obstack
 378  * in current_ir_graph and fixes the environment.
 379  * Then fixes the fields in current_ir_graph containing nodes of the
 380  * graph.
 381  *
 382  * @param copy_node_nr  If non-zero, the node number will be copied
 383  */
 384 static void
 385 copy_graph_env(int copy_node_nr) {
 386         ir_graph *irg = current_ir_graph;
 387         ir_node *old_end, *new_anchor;
 388         int i;
 389
 390         /* remove end_except and end_reg nodes */
 391         old_end = get_irg_end(irg);
 392         set_irg_end_except (irg, old_end);
 393         set_irg_end_reg    (irg, old_end);
 394
 395         /* Not all nodes remembered in irg might be reachable
 396            from the end node.  Assure their link is set to NULL, so that
 397            we can test whether new nodes have been computed. */
 398         for (i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
 399                 ir_node *n = get_irg_anchor(irg, i);
 400                 if (n != NULL)
 401                         set_new_node(n, NULL);
 402         }
 403         /* we use the block walk flag for removing Bads from Blocks ins. */
 404         inc_irg_block_visited(irg);
 405
 406         /* copy the graph */
 407         copy_graph(irg, copy_node_nr);
 408
 409         /* fix the anchor */
 410         old_end    = get_irg_end(irg);
 411         new_anchor = new_Anchor(irg);
 412
 413         for (i = get_irg_n_anchors(irg) - 1; i >= 0; --i) {
 414                 ir_node *n = get_irg_anchor(irg, i);
 415                 if (n)
 416                         set_irn_n(new_anchor, i, get_new_node(n));
 417         }
 418         free_End(old_end);
 419         irg->anchor = new_anchor;
 420
 421         /* ensure the new anchor is placed in the endblock */
 422         set_nodes_block(new_anchor, get_irg_end_block(irg));
 423 }
 424
 425 /**
 426  * Copies all reachable nodes to a new obstack.  Removes bad inputs
 427  * from block nodes and the corresponding inputs from Phi nodes.
 428  * Merges single exit blocks with single entry blocks and removes
 429  * 1-input Phis.
 430  * Adds all new nodes to a new hash table for CSE.  Does not
 431  * perform CSE, so the hash table might contain common subexpressions.
 432  */
 433 void dead_node_elimination(ir_graph *irg) {
 434         ir_graph *rem;
 435 #ifdef INTERPROCEDURAL_VIEW
 436         int rem_ipview = get_interprocedural_view();
 437 #endif
 438         struct obstack *graveyard_obst = NULL;
 439         struct obstack *rebirth_obst   = NULL;
 440         assert(! edges_activated(irg) && "dead node elimination requires disabled edges");
 441
 442         /* inform statistics that we started a dead-node elimination run */
 443         hook_dead_node_elim(irg, 1);
 444
 445         /* Remember external state of current_ir_graph. */
 446         rem = current_ir_graph;
 447         current_ir_graph = irg;
 448 #ifdef INTERPROCEDURAL_VIEW
 449         set_interprocedural_view(0);
 450 #endif
 451
 452         assert(get_irg_phase_state(irg) != phase_building);
 453
 454         /* Handle graph state */
 455         free_callee_info(irg);
 456         free_irg_outs(irg);
 457         free_trouts();
 458
 459         /* @@@ so far we loose loops when copying */
 460         free_loop_information(irg);
 461
 462         set_irg_doms_inconsistent(irg);
 463
 464         /* A quiet place, where the old obstack can rest in peace,
 465            until it will be cremated. */
 466         graveyard_obst = irg->obst;
 467
 468         /* A new obstack, where the reachable nodes will be copied to. */
 469         rebirth_obst = xmalloc(sizeof(*rebirth_obst));
 470         irg->obst = rebirth_obst;
 471         obstack_init(irg->obst);
 472         irg->last_node_idx = 0;
 473
 474         /* We also need a new value table for CSE */
 475         del_identities(irg->value_table);
 476         irg->value_table = new_identities();
 477
 478         /* Copy the graph from the old to the new obstack */
 479         copy_graph_env(/*copy_node_nr=*/1);
 480
 481         /* Free memory from old unoptimized obstack */
 482         obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
 483         xfree(graveyard_obst);            /* ... then free it.           */
 484
 485         /* inform statistics that the run is over */
 486         hook_dead_node_elim(irg, 0);
 487
 488         current_ir_graph = rem;
 489 #ifdef INTERPROCEDURAL_VIEW
 490         set_interprocedural_view(rem_ipview);
 491 #endif
 492 }
 493
 494 /**
 495  * Relink bad predecessors of a block and store the old in array to the
 496  * link field. This function is called by relink_bad_predecessors().
 497  * The array of link field starts with the block operand at position 0.
 498  * If block has bad predecessors, create a new in array without bad preds.
 499  * Otherwise let in array untouched.
 500  */
 501 static void relink_bad_block_predecessors(ir_node *n, void *env) {
 502         ir_node **new_in, *irn;
 503         int i, new_irn_n, old_irn_arity, new_irn_arity = 0;
 504         (void) env;
 505
 506         /* if link field of block is NULL, look for bad predecessors otherwise
 507            this is already done */
 508         if (is_Block(n) && get_irn_link(n) == NULL) {
 509                 /* save old predecessors in link field (position 0 is the block operand)*/
 510                 set_irn_link(n, get_irn_in(n));
 511
 512                 /* count predecessors without bad nodes */
 513                 old_irn_arity = get_irn_arity(n);
 514                 for (i = 0; i < old_irn_arity; i++)
 515                         if (!is_Bad(get_irn_n(n, i)))
 516                                 ++new_irn_arity;
 517
 518                 /* arity changing: set new predecessors without bad nodes */
 519                 if (new_irn_arity < old_irn_arity) {
 520                         /* Get new predecessor array. We do not resize the array, as we must
 521                            keep the old one to update Phis. */
 522                         new_in = NEW_ARR_D(ir_node *, current_ir_graph->obst, (new_irn_arity+1));
 523
 524                         /* set new predecessors in array */
 525                         new_in[0] = NULL;
 526                         new_irn_n = 1;
 527                         for (i = 0; i < old_irn_arity; i++) {
 528                                 irn = get_irn_n(n, i);
 529                                 if (!is_Bad(irn)) {
 530                                         new_in[new_irn_n] = irn;
 531                                         is_backedge(n, i) ? set_backedge(n, new_irn_n-1) : set_not_backedge(n, new_irn_n-1);
 532                                         ++new_irn_n;
 533                                 }
 534                         }
 535                         /* ARR_SETLEN(int, n->attr.block.backedge, new_irn_arity); */
 536                         ARR_SHRINKLEN(n->attr.block.backedge, new_irn_arity);
 537                         n->in = new_in;
 538                 } /* ir node has bad predecessors */
 539         } /* Block is not relinked */
 540 }
 541
 542 /**
 543  * Relinks Bad predecessors from Blocks and Phis called by walker
 544  * remove_bad_predecesors(). If n is a Block, call
 545  * relink_bad_block_redecessors(). If n is a Phi-node, call also the relinking
 546  * function of Phi's Block. If this block has bad predecessors, relink preds
 547  * of the Phi-node.
 548  */
 549 static void relink_bad_predecessors(ir_node *n, void *env) {
 550         ir_node *block, **old_in;
 551         int i, old_irn_arity, new_irn_arity;
 552
 553         /* relink bad predecessors of a block */
 554         if (is_Block(n))
 555                 relink_bad_block_predecessors(n, env);
 556
 557         /* If Phi node relink its block and its predecessors */
 558         if (is_Phi(n)) {
 559                 /* Relink predecessors of phi's block */
 560                 block = get_nodes_block(n);
 561                 if (get_irn_link(block) == NULL)
 562                         relink_bad_block_predecessors(block, env);
 563
 564                 old_in = (ir_node **)get_irn_link(block); /* Of Phi's Block */
 565                 old_irn_arity = ARR_LEN(old_in);
 566
 567                 /* Relink Phi predecessors if count of predecessors changed */
 568                 if (old_irn_arity != ARR_LEN(get_irn_in(block))) {
 569                         /* set new predecessors in array
 570                            n->in[0] remains the same block */
 571                         new_irn_arity = 1;
 572                         for(i = 1; i < old_irn_arity; i++)
 573                                 if (!is_Bad(old_in[i])) {
 574                                         n->in[new_irn_arity] = n->in[i];
 575                                         is_backedge(n, i) ? set_backedge(n, new_irn_arity) : set_not_backedge(n, new_irn_arity);
 576                                         ++new_irn_arity;
 577                                 }
 578
 579                                 ARR_SETLEN(ir_node *, n->in, new_irn_arity);
 580                                 ARR_SETLEN(int, n->attr.phi.u.backedge, new_irn_arity);
 581                 }
 582         } /* n is a Phi node */
 583 }
 584
 585 /*
 586  * Removes Bad Bad predecessors from Blocks and the corresponding
 587  * inputs to Phi nodes as in dead_node_elimination but without
 588  * copying the graph.
 589  * On walking up set the link field to NULL, on walking down call
 590  * relink_bad_predecessors() (This function stores the old in array
 591  * to the link field and sets a new in array if arity of predecessors
 592  * changes).
 593  */
 594 void remove_bad_predecessors(ir_graph *irg) {
 595         panic("Fix backedge handling first");
 596         irg_walk_graph(irg, firm_clear_link, relink_bad_predecessors, NULL);
 597 }
 598
 599
 600 /*
 601    __                      _  __ __
 602   (_     __    o     _    | \/  |_
 603   __)|_| | \_/ | \_/(/_   |_/\__|__
 604
 605   The following stuff implements a facility that automatically patches
 606   registered ir_node pointers to the new node when a dead node elimination occurs.
 607 */
 608
 609 struct _survive_dce_t {
 610         struct obstack obst;
 611         pmap *places;
 612         pmap *new_places;
 613         hook_entry_t dead_node_elim;
 614         hook_entry_t dead_node_elim_subst;
 615 };
 616
 617 typedef struct _survive_dce_list_t {
 618         struct _survive_dce_list_t *next;
 619         ir_node **place;
 620 } survive_dce_list_t;
 621
 622 static void dead_node_hook(void *context, ir_graph *irg, int start) {
 623         survive_dce_t *sd = context;
 624         (void) irg;
 625
 626         /* Create a new map before the dead node elimination is performed. */
 627         if (start) {
 628                 sd->new_places = pmap_create_ex(pmap_count(sd->places));
 629         } else {
 630                 /* Patch back all nodes if dead node elimination is over and something is to be done. */
 631                 pmap_destroy(sd->places);
 632                 sd->places     = sd->new_places;
 633                 sd->new_places = NULL;
 634         }
 635 }
 636
 637 /**
 638  * Hook called when dead node elimination replaces old by nw.
 639  */
 640 static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_node *nw) {
 641         survive_dce_t *sd = context;
 642         survive_dce_list_t *list = pmap_get(sd->places, old);
 643         (void) irg;
 644
 645         /* If the node is to be patched back, write the new address to all registered locations. */
 646         if (list) {
 647                 survive_dce_list_t *p;
 648
 649                 for (p = list; p; p = p->next)
 650                         *(p->place) = nw;
 651
 652                 pmap_insert(sd->new_places, nw, list);
 653         }
 654 }
 655
 656 /**
 657  * Make a new Survive DCE environment.
 658  */
 659 survive_dce_t *new_survive_dce(void) {
 660         survive_dce_t *res = xmalloc(sizeof(res[0]));
 661         obstack_init(&res->obst);
 662         res->places     = pmap_create();
 663         res->new_places = NULL;
 664
 665         res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
 666         res->dead_node_elim.context                   = res;
 667         res->dead_node_elim.next                      = NULL;
 668
 669         res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
 670         res->dead_node_elim_subst.context = res;
 671         res->dead_node_elim_subst.next    = NULL;
 672
 673 #ifndef FIRM_ENABLE_HOOKS
 674         assert(0 && "need hooks enabled");
 675 #endif
 676
 677         register_hook(hook_dead_node_elim, &res->dead_node_elim);
 678         register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
 679         return res;
 680 }
 681
 682 /**
 683  * Free a Survive DCE environment.
 684  */
 685 void free_survive_dce(survive_dce_t *sd) {
 686         obstack_free(&sd->obst, NULL);
 687         pmap_destroy(sd->places);
 688         unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
 689         unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
 690         xfree(sd);
 691 }
 692
 693 /**
 694  * Register a node pointer to be patched upon DCE.
 695  * When DCE occurs, the node pointer specified by @p place will be
 696  * patched to the new address of the node it is pointing to.
 697  *
 698  * @param sd    The Survive DCE environment.
 699  * @param place The address of the node pointer.
 700  */
 701 void survive_dce_register_irn(survive_dce_t *sd, ir_node **place) {
 702         if (*place != NULL) {
 703                 ir_node *irn      = *place;
 704                 survive_dce_list_t *curr = pmap_get(sd->places, irn);
 705                 survive_dce_list_t *nw   = obstack_alloc(&sd->obst, sizeof(nw[0]));
 706
 707                 nw->next  = curr;
 708                 nw->place = place;
 709
 710                 pmap_insert(sd->places, irn, nw);
 711         }
 712 }
 713
 714 /*--------------------------------------------------------------------*/
 715 /*  Functionality for inlining                                         */
 716 /*--------------------------------------------------------------------*/
 717
 718 /**
 719  * Copy node for inlineing.  Updates attributes that change when
 720  * inlineing but not for dead node elimination.
 721  *
 722  * Copies the node by calling copy_node() and then updates the entity if
 723  * it's a local one.  env must be a pointer of the frame type of the
 724  * inlined procedure. The new entities must be in the link field of
 725  * the entities.
 726  */
 727 static INLINE void
 728 copy_node_inline(ir_node *n, void *env) {
 729         ir_node *nn;
 730         ir_type *frame_tp = (ir_type *)env;
 731
 732         copy_node(n, NULL);
 733         if (is_Sel(n)) {
 734                 nn = get_new_node (n);
 735                 assert(is_Sel(nn));
 736                 if (get_entity_owner(get_Sel_entity(n)) == frame_tp) {
 737                         set_Sel_entity(nn, get_entity_link(get_Sel_entity(n)));
 738                 }
 739         } else if (is_Block(n)) {
 740                 nn = get_new_node (n);
 741                 nn->attr.block.irg = current_ir_graph;
 742         }
 743 }
 744
 745 /**
 746  * Walker: checks if P_value_arg_base is used.
 747  */
 748 static void find_addr(ir_node *node, void *env) {
 749         int *allow_inline = env;
 750         if (is_Proj(node) &&
 751                         is_Start(get_Proj_pred(node)) &&
 752                         get_Proj_proj(node) == pn_Start_P_value_arg_base) {
 753                 *allow_inline = 0;
 754         }
 755 }
 756
 757 /**
 758  * Check if we can inline a given call.
 759  * Currently, we cannot inline two cases:
 760  * - call with compound arguments
 761  * - graphs that take the address of a parameter
 762  *
 763  * check these conditions here
 764  */
 765 static int can_inline(ir_node *call, ir_graph *called_graph) {
 766         ir_type *call_type = get_Call_type(call);
 767         int params, ress, i, res;
 768         assert(is_Method_type(call_type));
 769
 770         params = get_method_n_params(call_type);
 771         ress   = get_method_n_ress(call_type);
 772
 773         /* check parameters for compound arguments */
 774         for (i = 0; i < params; ++i) {
 775                 ir_type *p_type = get_method_param_type(call_type, i);
 776
 777                 if (is_compound_type(p_type))
 778                         return 0;
 779         }
 780
 781         /* check results for compound arguments */
 782         for (i = 0; i < ress; ++i) {
 783                 ir_type *r_type = get_method_res_type(call_type, i);
 784
 785                 if (is_compound_type(r_type))
 786                         return 0;
 787         }
 788
 789         res = 1;
 790         irg_walk_graph(called_graph, find_addr, NULL, &res);
 791
 792         return res;
 793 }
 794
 795 enum exc_mode {
 796         exc_handler    = 0, /**< There is a handler. */
 797         exc_to_end     = 1, /**< Branches to End. */
 798         exc_no_handler = 2  /**< Exception handling not represented. */
 799 };
 800
 801 /* Inlines a method at the given call site. */
 802 int inline_method(ir_node *call, ir_graph *called_graph) {
 803         ir_node *pre_call;
 804         ir_node *post_call, *post_bl;
 805         ir_node *in[pn_Start_max];
 806         ir_node *end, *end_bl;
 807         ir_node **res_pred;
 808         ir_node **cf_pred;
 809         ir_node *ret, *phi;
 810         int arity, n_ret, n_exc, n_res, i, n, j, rem_opt, irn_arity;
 811         enum exc_mode exc_handling;
 812         ir_type *called_frame, *curr_frame;
 813         irg_inline_property prop = get_irg_inline_property(called_graph);
 814         ir_entity *ent;
 815
 816         if (prop == irg_inline_forbidden)
 817                 return 0;
 818
 819         ent = get_irg_entity(called_graph);
 820
 821         /* Do not inline variadic functions. */
 822         if (get_method_variadicity(get_entity_type(ent)) == variadicity_variadic)
 823                 return 0;
 824
 825         assert(get_method_n_params(get_entity_type(ent)) ==
 826                get_method_n_params(get_Call_type(call)));
 827
 828         /*
 829          * We cannot inline a recursive call. The graph must be copied before
 830          * the call the inline_method() using create_irg_copy().
 831          */
 832         if (called_graph == current_ir_graph)
 833                 return 0;
 834
 835         /*
 836          * currently, we cannot inline two cases:
 837          * - call with compound arguments
 838          * - graphs that take the address of a parameter
 839          */
 840         if (! can_inline(call, called_graph))
 841                 return 0;
 842
 843         /* --  Turn off optimizations, this can cause problems when allocating new nodes. -- */
 844         rem_opt = get_opt_optimize();
 845         set_optimize(0);
 846
 847         /* Handle graph state */
 848         assert(get_irg_phase_state(current_ir_graph) != phase_building);
 849         assert(get_irg_pinned(current_ir_graph) == op_pin_state_pinned);
 850         assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
 851         set_irg_outs_inconsistent(current_ir_graph);
 852         set_irg_extblk_inconsistent(current_ir_graph);
 853         set_irg_doms_inconsistent(current_ir_graph);
 854         set_irg_loopinfo_inconsistent(current_ir_graph);
 855         set_irg_callee_info_state(current_ir_graph, irg_callee_info_inconsistent);
 856
 857         /* -- Check preconditions -- */
 858         assert(is_Call(call));
 859
 860         /* here we know we WILL inline, so inform the statistics */
 861         hook_inline(call, called_graph);
 862
 863         /* -- Decide how to handle exception control flow: Is there a handler
 864            for the Call node, or do we branch directly to End on an exception?
 865            exc_handling:
 866            0 There is a handler.
 867            1 Branches to End.
 868            2 Exception handling not represented in Firm. -- */
 869         {
 870                 ir_node *proj, *Mproj = NULL, *Xproj = NULL;
 871                 for (proj = get_irn_link(call); proj; proj = get_irn_link(proj)) {
 872                         long proj_nr = get_Proj_proj(proj);
 873                         if (proj_nr == pn_Call_X_except) Xproj = proj;
 874                         if (proj_nr == pn_Call_M_except) Mproj = proj;
 875                 }
 876                 if      (Mproj) { assert(Xproj); exc_handling = exc_handler; } /*  Mproj           */
 877                 else if (Xproj) {                exc_handling = exc_to_end; } /* !Mproj &&  Xproj   */
 878                 else            {                exc_handling = exc_no_handler; } /* !Mproj && !Xproj   */
 879         }
 880
 881         /* --
 882            the procedure and later replaces the Start node of the called graph.
 883            Post_call is the old Call node and collects the results of the called
 884            graph. Both will end up being a tuple.  -- */
 885         post_bl = get_nodes_block(call);
 886         set_irg_current_block(current_ir_graph, post_bl);
 887         /* XxMxPxPxPxT of Start + parameter of Call */
 888         in[pn_Start_X_initial_exec]   = new_Jmp();
 889         in[pn_Start_M]                = get_Call_mem(call);
 890         in[pn_Start_P_frame_base]     = get_irg_frame(current_ir_graph);
 891         in[pn_Start_P_globals]        = get_irg_globals(current_ir_graph);
 892         in[pn_Start_P_tls]            = get_irg_tls(current_ir_graph);
 893         in[pn_Start_T_args]           = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call));
 894         /* in[pn_Start_P_value_arg_base] = ??? */
 895         assert(pn_Start_P_value_arg_base == pn_Start_max - 1 && "pn_Start_P_value_arg_base not supported, fix");
 896         pre_call = new_Tuple(pn_Start_max - 1, in);
 897         post_call = call;
 898
 899         /* --
 900            The new block gets the ins of the old block, pre_call and all its
 901            predecessors and all Phi nodes. -- */
 902         part_block(pre_call);
 903
 904         /* -- Prepare state for dead node elimination -- */
 905         /* Visited flags in calling irg must be >= flag in called irg.
 906            Else walker and arity computation will not work. */
 907         if (get_irg_visited(current_ir_graph) <= get_irg_visited(called_graph))
 908                 set_irg_visited(current_ir_graph, get_irg_visited(called_graph)+1);
 909         if (get_irg_block_visited(current_ir_graph)< get_irg_block_visited(called_graph))
 910                 set_irg_block_visited(current_ir_graph, get_irg_block_visited(called_graph));
 911         /* Set pre_call as new Start node in link field of the start node of
 912            calling graph and pre_calls block as new block for the start block
 913            of calling graph.
 914            Further mark these nodes so that they are not visited by the
 915            copying. */
 916         set_irn_link(get_irg_start(called_graph), pre_call);
 917         set_irn_visited(get_irg_start(called_graph), get_irg_visited(current_ir_graph));
 918         set_irn_link(get_irg_start_block(called_graph), get_nodes_block(pre_call));
 919         set_irn_visited(get_irg_start_block(called_graph), get_irg_visited(current_ir_graph));
 920         set_irn_link(get_irg_bad(called_graph), get_irg_bad(current_ir_graph));
 921         set_irn_visited(get_irg_bad(called_graph), get_irg_visited(current_ir_graph));
 922
 923         /* Initialize for compaction of in arrays */
 924         inc_irg_block_visited(current_ir_graph);
 925
 926         /* -- Replicate local entities of the called_graph -- */
 927         /* copy the entities. */
 928         called_frame = get_irg_frame_type(called_graph);
 929         curr_frame   = get_irg_frame_type(current_ir_graph);
 930         for (i = 0, n = get_class_n_members(called_frame); i < n; ++i) {
 931                 ir_entity *new_ent, *old_ent;
 932                 old_ent = get_class_member(called_frame, i);
 933                 new_ent = copy_entity_own(old_ent, curr_frame);
 934                 set_entity_link(old_ent, new_ent);
 935         }
 936
 937         /* visited is > than that of called graph.  With this trick visited will
 938            remain unchanged so that an outer walker, e.g., searching the call nodes
 939             to inline, calling this inline will not visit the inlined nodes. */
 940         set_irg_visited(current_ir_graph, get_irg_visited(current_ir_graph)-1);
 941
 942         /* -- Performing dead node elimination inlines the graph -- */
 943         /* Copies the nodes to the obstack of current_ir_graph. Updates links to new
 944            entities. */
 945         irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds,
 946                  get_irg_frame_type(called_graph));
 947
 948         /* Repair called_graph */
 949         set_irg_visited(called_graph, get_irg_visited(current_ir_graph));
 950         set_irg_block_visited(called_graph, get_irg_block_visited(current_ir_graph));
 951         set_Block_block_visited(get_irg_start_block(called_graph), 0);
 952
 953         /* -- Merge the end of the inlined procedure with the call site -- */
 954         /* We will turn the old Call node into a Tuple with the following
 955            predecessors:
 956            -1:  Block of Tuple.
 957            0: Phi of all Memories of Return statements.
 958            1: Jmp from new Block that merges the control flow from all exception
 959            predecessors of the old end block.
 960            2: Tuple of all arguments.
 961            3: Phi of Exception memories.
 962            In case the old Call directly branches to End on an exception we don't
 963            need the block merging all exceptions nor the Phi of the exception
 964            memories.
 965         */
 966
 967         /* -- Precompute some values -- */
 968         end_bl = get_new_node(get_irg_end_block(called_graph));
 969         end = get_new_node(get_irg_end(called_graph));
 970         arity = get_irn_arity(end_bl);    /* arity = n_exc + n_ret  */
 971         n_res = get_method_n_ress(get_Call_type(call));
 972
 973         res_pred = xmalloc(n_res * sizeof(*res_pred));
 974         cf_pred  = xmalloc(arity * sizeof(*res_pred));
 975
 976         set_irg_current_block(current_ir_graph, post_bl); /* just to make sure */
 977
 978         /* -- archive keepalives -- */
 979         irn_arity = get_irn_arity(end);
 980         for (i = 0; i < irn_arity; i++) {
 981                 ir_node *ka = get_End_keepalive(end, i);
 982                 if (! is_Bad(ka))
 983                         add_End_keepalive(get_irg_end(current_ir_graph), ka);
 984         }
 985
 986         /* The new end node will die.  We need not free as the in array is on the obstack:
 987            copy_node() only generated 'D' arrays. */
 988
 989         /* -- Replace Return nodes by Jump nodes. -- */
 990         n_ret = 0;
 991         for (i = 0; i < arity; i++) {
 992                 ir_node *ret;
 993                 ret = get_irn_n(end_bl, i);
 994                 if (is_Return(ret)) {
 995                         cf_pred[n_ret] = new_r_Jmp(current_ir_graph, get_nodes_block(ret));
 996                         n_ret++;
 997                 }
 998         }
 999         set_irn_in(post_bl, n_ret, cf_pred);
1000
1001         /* -- Build a Tuple for all results of the method.
1002            Add Phi node if there was more than one Return.  -- */
1003         turn_into_tuple(post_call, pn_Call_max);
1004         /* First the Memory-Phi */
1005         n_ret = 0;
1006         for (i = 0; i < arity; i++) {
1007                 ret = get_irn_n(end_bl, i);
1008                 if (is_Return(ret)) {
1009                         cf_pred[n_ret] = get_Return_mem(ret);
1010                         n_ret++;
1011                 }
1012         }
1013         phi = new_Phi(n_ret, cf_pred, mode_M);
1014         set_Tuple_pred(call, pn_Call_M_regular, phi);
1015         /* Conserve Phi-list for further inlinings -- but might be optimized */
1016         if (get_nodes_block(phi) == post_bl) {
1017                 set_irn_link(phi, get_irn_link(post_bl));
1018                 set_irn_link(post_bl, phi);
1019         }
1020         /* Now the real results */
1021         if (n_res > 0) {
1022                 for (j = 0; j < n_res; j++) {
1023                         n_ret = 0;
1024                         for (i = 0; i < arity; i++) {
1025                                 ret = get_irn_n(end_bl, i);
1026                                 if (is_Return(ret)) {
1027                                         cf_pred[n_ret] = get_Return_res(ret, j);
1028                                         n_ret++;
1029                                 }
1030                         }
1031                         if (n_ret > 0)
1032                                 phi = new_Phi(n_ret, cf_pred, get_irn_mode(cf_pred[0]));
1033                         else
1034                                 phi = new_Bad();
1035                         res_pred[j] = phi;
1036                         /* Conserve Phi-list for further inlinings -- but might be optimized */
1037                         if (get_nodes_block(phi) == post_bl) {
1038                                 set_Phi_next(phi, get_Block_phis(post_bl));
1039                                 set_Block_phis(post_bl, phi);
1040                         }
1041                 }
1042                 set_Tuple_pred(call, pn_Call_T_result, new_Tuple(n_res, res_pred));
1043         } else {
1044                 set_Tuple_pred(call, pn_Call_T_result, new_Bad());
1045         }
1046         /* handle the regular call */
1047         set_Tuple_pred(call, pn_Call_X_regular, new_Jmp());
1048
1049         /* For now, we cannot inline calls with value_base */
1050         set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
1051
1052         /* Finally the exception control flow.
1053            We have two (three) possible situations:
1054            First if the Call branches to an exception handler: We need to add a Phi node to
1055            collect the memory containing the exception objects.  Further we need
1056            to add another block to get a correct representation of this Phi.  To
1057            this block we add a Jmp that resolves into the X output of the Call
1058            when the Call is turned into a tuple.
1059            Second the Call branches to End, the exception is not handled.  Just
1060            add all inlined exception branches to the End node.
1061            Third: there is no Exception edge at all. Handle as case two. */
1062         if (exc_handling == exc_handler) {
1063                 n_exc = 0;
1064                 for (i = 0; i < arity; i++) {
1065                         ir_node *ret, *irn;
1066                         ret = get_irn_n(end_bl, i);
1067                         irn = skip_Proj(ret);
1068                         if (is_fragile_op(irn) || is_Raise(irn)) {
1069                                 cf_pred[n_exc] = ret;
1070                                 ++n_exc;
1071                         }
1072                 }
1073                 if (n_exc > 0) {
1074                         new_Block(n_exc, cf_pred);      /* watch it: current_block is changed! */
1075                         set_Tuple_pred(call, pn_Call_X_except, new_Jmp());
1076                         /* The Phi for the memories with the exception objects */
1077                         n_exc = 0;
1078                         for (i = 0; i < arity; i++) {
1079                                 ir_node *ret;
1080                                 ret = skip_Proj(get_irn_n(end_bl, i));
1081                                 if (is_Call(ret)) {
1082                                         cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 3);
1083                                         n_exc++;
1084                                 } else if (is_fragile_op(ret)) {
1085                                         /* We rely that all cfops have the memory output at the same position. */
1086                                         cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 0);
1087                                         n_exc++;
1088                                 } else if (is_Raise(ret)) {
1089                                         cf_pred[n_exc] = new_r_Proj(current_ir_graph, get_nodes_block(ret), ret, mode_M, 1);
1090                                         n_exc++;
1091                                 }
1092                         }
1093                         set_Tuple_pred(call, pn_Call_M_except, new_Phi(n_exc, cf_pred, mode_M));
1094                 } else {
1095                         set_Tuple_pred(call, pn_Call_X_except, new_Bad());
1096                         set_Tuple_pred(call, pn_Call_M_except, new_Bad());
1097                 }
1098         } else {
1099                 ir_node *main_end_bl;
1100                 int main_end_bl_arity;
1101                 ir_node **end_preds;
1102
1103                 /* assert(exc_handling == 1 || no exceptions. ) */
1104                 n_exc = 0;
1105                 for (i = 0; i < arity; i++) {
1106                         ir_node *ret = get_irn_n(end_bl, i);
1107                         ir_node *irn = skip_Proj(ret);
1108
1109                         if (is_fragile_op(irn) || is_Raise(irn)) {
1110                                 cf_pred[n_exc] = ret;
1111                                 n_exc++;
1112                         }
1113                 }
1114                 main_end_bl = get_irg_end_block(current_ir_graph);
1115                 main_end_bl_arity = get_irn_arity(main_end_bl);
1116                 end_preds =  xmalloc((n_exc + main_end_bl_arity) * sizeof(*end_preds));
1117
1118                 for (i = 0; i < main_end_bl_arity; ++i)
1119                         end_preds[i] = get_irn_n(main_end_bl, i);
1120                 for (i = 0; i < n_exc; ++i)
1121                         end_preds[main_end_bl_arity + i] = cf_pred[i];
1122                 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
1123                 set_Tuple_pred(call, pn_Call_X_except,  new_Bad());
1124                 set_Tuple_pred(call, pn_Call_M_except,  new_Bad());
1125                 free(end_preds);
1126         }
1127         free(res_pred);
1128         free(cf_pred);
1129
1130         /* --  Turn CSE back on. -- */
1131         set_optimize(rem_opt);
1132
1133         return 1;
1134 }
1135
1136 /********************************************************************/
1137 /* Apply inlineing to small methods.                                */
1138 /********************************************************************/
1139
1140 /** Represents a possible inlinable call in a graph. */
1141 typedef struct _call_entry call_entry;
1142 struct _call_entry {
1143         ir_node    *call;   /**< the Call */
1144         ir_graph   *callee; /**< the callee called here */
1145         call_entry *next;   /**< for linking the next one */
1146         unsigned   weight;  /**< the weight of the call */
1147 };
1148
1149 /**
1150  * environment for inlining small irgs
1151  */
1152 typedef struct _inline_env_t {
1153         struct obstack obst;  /**< an obstack where call_entries are allocated on. */
1154         call_entry *head;     /**< the head of the call entry list */
1155         call_entry *tail;     /**< the tail of the call entry list */
1156 } inline_env_t;
1157
1158 /**
1159  * Returns the irg called from a Call node. If the irg is not
1160  * known, NULL is returned.
1161  *
1162  * @param call  the call node
1163  */
1164 static ir_graph *get_call_called_irg(ir_node *call) {
1165         ir_node *addr;
1166
1167         addr = get_Call_ptr(call);
1168         if (is_Global(addr)) {
1169                 ir_entity *ent = get_Global_entity(addr);
1170                 return get_entity_irg(ent);
1171         }
1172
1173         return NULL;
1174 }
1175
1176 /**
1177  * Walker: Collect all calls to known graphs inside a graph.
1178  */
1179 static void collect_calls(ir_node *call, void *env) {
1180         if (is_Call(call)) {
1181                 ir_graph *called_irg = get_call_called_irg(call);
1182
1183                 if (called_irg != NULL) {
1184                         /* The Call node calls a locally defined method.  Remember to inline. */
1185                         inline_env_t *ienv  = env;
1186                         call_entry   *entry = obstack_alloc(&ienv->obst, sizeof(*entry));
1187                         entry->call   = call;
1188                         entry->callee = called_irg;
1189                         entry->next   = NULL;
1190                         entry->weight = 0;
1191
1192                         if (ienv->tail == NULL)
1193                                 ienv->head = entry;
1194                         else
1195                                 ienv->tail->next = entry;
1196                         ienv->tail = entry;
1197                 }
1198         }
1199 }
1200
1201 /**
1202  * Inlines all small methods at call sites where the called address comes
1203  * from a Const node that references the entity representing the called
1204  * method.
1205  * The size argument is a rough measure for the code size of the method:
1206  * Methods where the obstack containing the firm graph is smaller than
1207  * size are inlined.
1208  */
1209 void inline_small_irgs(ir_graph *irg, int size) {
1210   ir_graph *rem = current_ir_graph;
1211         inline_env_t env;
1212         call_entry *entry;
1213         DEBUG_ONLY(firm_dbg_module_t *dbg;)
1214
1215         FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1216
1217         current_ir_graph = irg;
1218         /* Handle graph state */
1219         assert(get_irg_phase_state(irg) != phase_building);
1220         free_callee_info(irg);
1221
1222         /* Find Call nodes to inline.
1223            (We can not inline during a walk of the graph, as inlineing the same
1224            method several times changes the visited flag of the walked graph:
1225            after the first inlineing visited of the callee equals visited of
1226            the caller.  With the next inlineing both are increased.) */
1227         obstack_init(&env.obst);
1228         env.head = env.tail = NULL;
1229         irg_walk_graph(irg, NULL, collect_calls, &env);
1230
1231         if (env.head != NULL) {
1232                 /* There are calls to inline */
1233                 collect_phiprojs(irg);
1234                 for (entry = env.head; entry != NULL; entry = entry->next) {
1235                         ir_graph *callee = entry->callee;
1236                         if (((_obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst)) < size) ||
1237                             (get_irg_inline_property(callee) >= irg_inline_forced)) {
1238                                 inline_method(entry->call, callee);
1239                         }
1240                 }
1241         }
1242         obstack_free(&env.obst, NULL);
1243         current_ir_graph = rem;
1244 }
1245
1246 /**
1247  * Environment for inlining irgs.
1248  */
1249 typedef struct {
1250         int n_nodes;             /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
1251         int n_blocks;            /**< Number of Blocks in graph without Start and End block. */
1252         int n_nodes_orig;        /**< for statistics */
1253         call_entry *call_head;   /**< The head of the list of all call nodes in this graph. */
1254         call_entry *call_tail;   /**< The tail of the list of all call nodes in this graph .*/
1255         int n_call_nodes;        /**< Number of Call nodes in the graph. */
1256         int n_call_nodes_orig;   /**< for statistics */
1257         int n_callers;           /**< Number of known graphs that call this graphs. */
1258         int n_callers_orig;      /**< for statistics */
1259         int got_inline;          /**< Set, if at leat one call inside this graph was inlined. */
1260 } inline_irg_env;
1261
1262 /**
1263  * Allocate a new environment for inlining.
1264  */
1265 static inline_irg_env *alloc_inline_irg_env(struct obstack *obst) {
1266         inline_irg_env *env    = obstack_alloc(obst, sizeof(*env));
1267         env->n_nodes           = -2; /* do not count count Start, End */
1268         env->n_blocks          = -2; /* do not count count Start, End Block */
1269         env->n_nodes_orig      = -2; /* do not count Start, End */
1270         env->call_head         = NULL;
1271         env->call_tail         = NULL;
1272         env->n_call_nodes      = 0;
1273         env->n_call_nodes_orig = 0;
1274         env->n_callers         = 0;
1275         env->n_callers_orig    = 0;
1276         env->got_inline        = 0;
1277         return env;
1278 }
1279
1280 typedef struct walker_env {
1281         struct obstack *obst; /**< the obstack for allocations. */
1282         inline_irg_env *x;    /**< the inline environment */
1283         char ignore_runtime;  /**< the ignore runtime flag */
1284         char ignore_callers;  /**< if set, do change callers data */
1285 } wenv_t;
1286
1287 /**
1288  * post-walker: collect all calls in the inline-environment
1289  * of a graph and sum some statistics.
1290  */
1291 static void collect_calls2(ir_node *call, void *ctx) {
1292         wenv_t         *env = ctx;
1293         inline_irg_env *x = env->x;
1294         ir_opcode      code = get_irn_opcode(call);
1295         ir_graph       *callee;
1296         call_entry     *entry;
1297
1298         /* count meaningful nodes in irg */
1299         if (code != iro_Proj && code != iro_Tuple && code != iro_Sync) {
1300                 if (code != iro_Block) {
1301                         ++x->n_nodes;
1302                         ++x->n_nodes_orig;
1303                 } else {
1304                         ++x->n_blocks;
1305                 }
1306         }
1307
1308         if (code != iro_Call) return;
1309
1310         /* check, if it's a runtime call */
1311         if (env->ignore_runtime) {
1312                 ir_node *symc = get_Call_ptr(call);
1313
1314                 if (is_Global(symc)) {
1315                         ir_entity *ent = get_Global_entity(symc);
1316
1317                         if (get_entity_additional_properties(ent) & mtp_property_runtime)
1318                                 return;
1319                 }
1320         }
1321
1322         /* collect all call nodes */
1323         ++x->n_call_nodes;
1324         ++x->n_call_nodes_orig;
1325
1326         callee = get_call_called_irg(call);
1327         if (callee != NULL) {
1328                 if (! env->ignore_callers) {
1329                         inline_irg_env *callee_env = get_irg_link(callee);
1330                         /* count all static callers */
1331                         ++callee_env->n_callers;
1332                         ++callee_env->n_callers_orig;
1333                 }
1334
1335                 /* link it in the list of possible inlinable entries */
1336                 entry = obstack_alloc(env->obst, sizeof(*entry));
1337                 entry->call   = call;
1338                 entry->callee = callee;
1339                 entry->next   = NULL;
1340                 if (x->call_tail == NULL)
1341                         x->call_head = entry;
1342                 else
1343                         x->call_tail->next = entry;
1344                 x->call_tail = entry;
1345         }
1346 }
1347
1348 /**
1349  * Returns TRUE if the number of callers is 0 in the irg's environment,
1350  * hence this irg is a leave.
1351  */
1352 INLINE static int is_leave(ir_graph *irg) {
1353         inline_irg_env *env = get_irg_link(irg);
1354         return env->n_call_nodes == 0;
1355 }
1356
1357 /**
1358  * Returns TRUE if the number of nodes in the callee is
1359  * smaller then size in the irg's environment.
1360  */
1361 INLINE static int is_smaller(ir_graph *callee, int size) {
1362         inline_irg_env *env = get_irg_link(callee);
1363         return env->n_nodes < size;
1364 }
1365
1366 /**
1367  * Append the nodes of the list src to the nodes of the list in environment dst.
1368  */
1369 static void append_call_list(struct obstack *obst, inline_irg_env *dst, call_entry *src) {
1370         call_entry *entry, *nentry;
1371
1372         /* Note that the src list points to Call nodes in the inlined graph, but
1373            we need Call nodes in our graph. Luckily the inliner leaves this information
1374            in the link field. */
1375         for (entry = src; entry != NULL; entry = entry->next) {
1376                 nentry = obstack_alloc(obst, sizeof(*nentry));
1377                 nentry->call   = get_irn_link(entry->call);
1378                 nentry->callee = entry->callee;
1379                 nentry->next   = NULL;
1380                 dst->call_tail->next = nentry;
1381                 dst->call_tail       = nentry;
1382         }
1383 }
1384
1385 /*
1386  * Inlines small leave methods at call sites where the called address comes
1387  * from a Const node that references the entity representing the called
1388  * method.
1389  * The size argument is a rough measure for the code size of the method:
1390  * Methods where the obstack containing the firm graph is smaller than
1391  * size are inlined.
1392  */
1393 void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_runtime) {
1394         inline_irg_env   *env;
1395         ir_graph         *irg;
1396         int              i, n_irgs;
1397         ir_graph         *rem;
1398         int              did_inline;
1399         wenv_t           wenv;
1400         call_entry       *entry, *tail;
1401         const call_entry *centry;
1402         struct obstack   obst;
1403         pmap             *copied_graphs;
1404         pmap_entry       *pm_entry;
1405         DEBUG_ONLY(firm_dbg_module_t *dbg;)
1406
1407         FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1408         rem = current_ir_graph;
1409         obstack_init(&obst);
1410
1411         /* a map for the copied graphs, used to inline recursive calls */
1412         copied_graphs = pmap_create();
1413
1414         /* extend all irgs by a temporary data structure for inlining. */
1415         n_irgs = get_irp_n_irgs();
1416         for (i = 0; i < n_irgs; ++i)
1417                 set_irg_link(get_irp_irg(i), alloc_inline_irg_env(&obst));
1418
1419         /* Precompute information in temporary data structure. */
1420         wenv.obst           = &obst;
1421         wenv.ignore_runtime = ignore_runtime;
1422         wenv.ignore_callers = 0;
1423         for (i = 0; i < n_irgs; ++i) {
1424                 ir_graph *irg = get_irp_irg(i);
1425
1426                 assert(get_irg_phase_state(irg) != phase_building);
1427                 free_callee_info(irg);
1428
1429                 wenv.x = get_irg_link(irg);
1430                 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1431         }
1432
1433         /* -- and now inline. -- */
1434
1435         /* Inline leaves recursively -- we might construct new leaves. */
1436         do {
1437                 did_inline = 0;
1438
1439                 for (i = 0; i < n_irgs; ++i) {
1440                         ir_node *call;
1441                         int phiproj_computed = 0;
1442
1443                         current_ir_graph = get_irp_irg(i);
1444                         env = (inline_irg_env *)get_irg_link(current_ir_graph);
1445
1446                         tail = NULL;
1447                         for (entry = env->call_head; entry != NULL; entry = entry->next) {
1448                                 ir_graph *callee;
1449
1450                                 if (env->n_nodes > maxsize) break;
1451
1452                                 call   = entry->call;
1453                                 callee = entry->callee;
1454
1455                                 if (is_leave(callee) && (
1456                                     is_smaller(callee, leavesize) || (get_irg_inline_property(callee) >= irg_inline_forced))) {
1457                                         if (!phiproj_computed) {
1458                                                 phiproj_computed = 1;
1459                                                 collect_phiprojs(current_ir_graph);
1460                                         }
1461                                         did_inline = inline_method(call, callee);
1462
1463                                         if (did_inline) {
1464                                                 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1465
1466                                                 /* was inlined, must be recomputed */
1467                                                 phiproj_computed = 0;
1468
1469                                                 /* Do some statistics */
1470                                                 env->got_inline = 1;
1471                                                 --env->n_call_nodes;
1472                                                 env->n_nodes += callee_env->n_nodes;
1473                                                 --callee_env->n_callers;
1474
1475                                                 /* remove this call from the list */
1476                                                 if (tail != NULL)
1477                                                         tail->next = entry->next;
1478                                                 else
1479                                                         env->call_head = entry->next;
1480                                                 continue;
1481                                         }
1482                                 }
1483                                 tail = entry;
1484                         }
1485                         env->call_tail = tail;
1486                 }
1487         } while (did_inline);
1488
1489         /* inline other small functions. */
1490         for (i = 0; i < n_irgs; ++i) {
1491                 ir_node *call;
1492                 int phiproj_computed = 0;
1493
1494                 current_ir_graph = get_irp_irg(i);
1495                 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1496
1497                 /* note that the list of possible calls is updated during the process */
1498                 tail = NULL;
1499                 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1500                         ir_graph   *callee;
1501                         pmap_entry *e;
1502
1503                         call   = entry->call;
1504                         callee = entry->callee;
1505
1506                         e = pmap_find(copied_graphs, callee);
1507                         if (e != NULL) {
1508                                 /*
1509                                  * Remap callee if we have a copy.
1510                                  * FIXME: Should we do this only for recursive Calls ?
1511                                  */
1512                                 callee = e->value;
1513                         }
1514
1515                         if (((is_smaller(callee, size) && (env->n_nodes < maxsize)) ||    /* small function */
1516                                 (get_irg_inline_property(callee) >= irg_inline_forced))) {
1517                                 if (current_ir_graph == callee) {
1518                                         /*
1519                                          * Recursive call: we cannot directly inline because we cannot walk
1520                                          * the graph and change it. So we have to make a copy of the graph
1521                                          * first.
1522                                          */
1523
1524                                         inline_irg_env *callee_env;
1525                                         ir_graph       *copy;
1526
1527                                         /*
1528                                          * No copy yet, create one.
1529                                          * Note that recursive methods are never leaves, so it is sufficient
1530                                          * to test this condition here.
1531                                          */
1532                                         copy = create_irg_copy(callee);
1533
1534                                         /* create_irg_copy() destroys the Proj links, recompute them */
1535                                         phiproj_computed = 0;
1536
1537                                         /* allocate new environment */
1538                                         callee_env = alloc_inline_irg_env(&obst);
1539                                         set_irg_link(copy, callee_env);
1540
1541                                         wenv.x              = callee_env;
1542                                         wenv.ignore_callers = 1;
1543                                         irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1544
1545                                         /*
1546                                          * Enter the entity of the original graph. This is needed
1547                                          * for inline_method(). However, note that ent->irg still points
1548                                          * to callee, NOT to copy.
1549                                          */
1550                                         set_irg_entity(copy, get_irg_entity(callee));
1551
1552                                         pmap_insert(copied_graphs, callee, copy);
1553                                         callee = copy;
1554
1555                                         /* we have only one caller: the original graph */
1556                                         callee_env->n_callers      = 1;
1557                                         callee_env->n_callers_orig = 1;
1558                                 }
1559                                 if (! phiproj_computed) {
1560                                         phiproj_computed = 1;
1561                                         collect_phiprojs(current_ir_graph);
1562                                 }
1563                                 did_inline = inline_method(call, callee);
1564                                 if (did_inline) {
1565                                         inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1566
1567                                         /* was inlined, must be recomputed */
1568                                         phiproj_computed = 0;
1569
1570                                         /* callee was inline. Append it's call list. */
1571                                         env->got_inline = 1;
1572                                         --env->n_call_nodes;
1573                                         append_call_list(&obst, env, callee_env->call_head);
1574                                         env->n_call_nodes += callee_env->n_call_nodes;
1575                                         env->n_nodes += callee_env->n_nodes;
1576                                         --callee_env->n_callers;
1577
1578                                         /* after we have inlined callee, all called methods inside callee
1579                                            are now called once more */
1580                                         for (centry = callee_env->call_head; centry != NULL; centry = centry->next) {
1581                                                 inline_irg_env *penv = get_irg_link(centry->callee);
1582                                                 ++penv->n_callers;
1583                                         }
1584
1585                                         /* remove this call from the list */
1586                                         if (tail != NULL)
1587                                                 tail->next = entry->next;
1588                                         else
1589                                                 env->call_head = entry->next;
1590                                         continue;
1591                                 }
1592                         }
1593                         tail = entry;
1594                 }
1595                 env->call_tail = tail;
1596         }
1597
1598         for (i = 0; i < n_irgs; ++i) {
1599                 irg = get_irp_irg(i);
1600                 env = (inline_irg_env *)get_irg_link(irg);
1601
1602                 if (env->got_inline) {
1603                         /* this irg got calls inlined */
1604                         set_irg_outs_inconsistent(irg);
1605                         set_irg_doms_inconsistent(irg);
1606
1607                         optimize_graph_df(irg);
1608                         optimize_cf(irg);
1609                 }
1610                 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1611                         DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1612                         env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1613                         env->n_callers_orig, env->n_callers,
1614                         get_entity_name(get_irg_entity(irg))));
1615                 }
1616         }
1617
1618         /* kill the copied graphs: we don't need them anymore */
1619         foreach_pmap(copied_graphs, pm_entry) {
1620                 ir_graph *copy = pm_entry->value;
1621
1622                 /* reset the entity, otherwise it will be deleted in the next step ... */
1623                 set_irg_entity(copy, NULL);
1624                 free_ir_graph(copy);
1625         }
1626         pmap_destroy(copied_graphs);
1627
1628         obstack_free(&obst, NULL);
1629         current_ir_graph = rem;
1630 }
1631
1632 /**
1633  * calculate a benefice value for inlining the given call.
1634  */
1635 static int calc_inline_benefice(ir_node *call, ir_graph *callee) {
1636         ir_entity *ent = get_irg_entity(callee);
1637         ir_type   *mtp;
1638         int       weight = 0;
1639         int       i, n_params;
1640         unsigned  cc;
1641
1642         inline_irg_env *curr_env, *callee_env;
1643
1644         if (get_entity_additional_properties(ent) & mtp_property_noreturn) {
1645                 /* do NOT inline noreturn calls */
1646                 return INT_MIN;
1647         }
1648
1649         /* costs for every passed parameter */
1650         n_params = get_Call_n_params(call);
1651         mtp      = get_entity_type(ent);
1652         cc       = get_method_calling_convention(mtp);
1653         if (cc & cc_reg_param) {
1654                 /* register parameter, smaller costs for register parameters */
1655                 int max_regs = cc & ~cc_bits;
1656
1657                 if (max_regs < n_params)
1658                         weight += max_regs * 2 + (n_params - max_regs) * 5;
1659                 else
1660                         weight += n_params * 2;
1661         } else {
1662                 /* parameters are passed an stack */
1663                 weight += 5 * n_params;
1664         }
1665
1666         /* constant parameters improve the benefice */
1667         for (i = 0; i < n_params; ++i) {
1668                 ir_node *param = get_Call_param(call, i);
1669
1670                 if (is_Const(param) || is_SymConst(param))
1671                         weight += get_method_param_weight(ent, i);
1672         }
1673
1674         callee_env = get_irg_link(callee);
1675         if (callee_env->n_callers_orig == 1 && callee != current_ir_graph) {
1676                 /* we are the only caller, give big bonus */
1677                 weight += 5000;
1678         }
1679
1680         /* do not inline big functions */
1681         weight -= callee_env->n_nodes;
1682
1683         /* reduce the benefice if the current function is already big */
1684         curr_env = get_irg_link(current_ir_graph);
1685         weight -= curr_env->n_nodes / 100;
1686
1687         /* give a bonus for functions with one block */
1688         if (callee_env->n_blocks == 1)
1689                 weight = weight * 3 / 2;
1690
1691         return weight;
1692 }
1693
1694 /**
1695  * Heuristic inliner. Calculates a benifice value for every call and inlines
1696  * those calls with a value higher than the threshold.
1697  */
1698 void inline_functions(int inline_threshold) {
1699         inline_irg_env   *env;
1700         ir_graph         *irg;
1701         int              i, n_irgs;
1702         ir_graph         *rem;
1703         int              did_inline;
1704         wenv_t           wenv;
1705         call_entry       *entry, *tail;
1706         const call_entry *centry;
1707         struct obstack   obst;
1708         pmap             *copied_graphs;
1709         pmap_entry       *pm_entry;
1710         DEBUG_ONLY(firm_dbg_module_t *dbg;)
1711
1712         FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1713         rem = current_ir_graph;
1714         obstack_init(&obst);
1715
1716         /* a map for the copied graphs, used to inline recursive calls */
1717         copied_graphs = pmap_create();
1718
1719         /* extend all irgs by a temporary data structure for inlining. */
1720         n_irgs = get_irp_n_irgs();
1721         for (i = 0; i < n_irgs; ++i)
1722                 set_irg_link(get_irp_irg(i), alloc_inline_irg_env(&obst));
1723
1724         /* Precompute information in temporary data structure. */
1725         wenv.obst           = &obst;
1726         wenv.ignore_runtime = 0;
1727         wenv.ignore_callers = 0;
1728         for (i = 0; i < n_irgs; ++i) {
1729                 ir_graph *irg = get_irp_irg(i);
1730
1731                 assert(get_irg_phase_state(irg) != phase_building);
1732                 free_callee_info(irg);
1733
1734                 wenv.x = get_irg_link(irg);
1735                 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1736         }
1737
1738         /* -- and now inline. -- */
1739         for (i = 0; i < n_irgs; ++i) {
1740                 ir_node *call;
1741                 int phiproj_computed = 0;
1742
1743                 current_ir_graph = get_irp_irg(i);
1744                 env = get_irg_link(current_ir_graph);
1745
1746                 /* note that the list of possible calls is updated during the process */
1747                 tail = NULL;
1748                 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1749                         ir_graph   *callee;
1750                         pmap_entry *e;
1751                         int        benefice;
1752
1753                         call   = entry->call;
1754                         callee = entry->callee;
1755
1756                         /* calculate the benifice on the original call to prevent excessive inlining */
1757                         benefice = calc_inline_benefice(call, callee);
1758                         DB((dbg, SET_LEVEL_2, "In %+F Call %+F has benefice %d\n", current_ir_graph, callee, benefice));
1759
1760                         e = pmap_find(copied_graphs, callee);
1761                         if (e != NULL) {
1762                                 /*
1763                                  * Remap callee if we have a copy.
1764                                  * FIXME: Should we do this only for recursive Calls ?
1765                                  */
1766                                 callee = e->value;
1767                         }
1768
1769                         if (benefice > -inline_threshold ||
1770                                 (get_irg_inline_property(callee) >= irg_inline_forced)) {
1771                                 if (current_ir_graph == callee) {
1772                                         /*
1773                                          * Recursive call: we cannot directly inline because we cannot walk
1774                                          * the graph and change it. So we have to make a copy of the graph
1775                                          * first.
1776                                          */
1777
1778                                         inline_irg_env *callee_env;
1779                                         ir_graph       *copy;
1780
1781                                         /*
1782                                          * No copy yet, create one.
1783                                          * Note that recursive methods are never leaves, so it is sufficient
1784                                          * to test this condition here.
1785                                          */
1786                                         copy = create_irg_copy(callee);
1787
1788                                         /* create_irg_copy() destroys the Proj links, recompute them */
1789                                         phiproj_computed = 0;
1790
1791                                         /* allocate new environment */
1792                                         callee_env = alloc_inline_irg_env(&obst);
1793                                         set_irg_link(copy, callee_env);
1794
1795                                         wenv.x              = callee_env;
1796                                         wenv.ignore_callers = 1;
1797                                         irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1798
1799                                         /*
1800                                          * Enter the entity of the original graph. This is needed
1801                                          * for inline_method(). However, note that ent->irg still points
1802                                          * to callee, NOT to copy.
1803                                          */
1804                                         set_irg_entity(copy, get_irg_entity(callee));
1805
1806                                         pmap_insert(copied_graphs, callee, copy);
1807                                         callee = copy;
1808
1809                                         /* we have only one caller: the original graph */
1810                                         callee_env->n_callers      = 1;
1811                                         callee_env->n_callers_orig = 1;
1812                                 }
1813                                 if (! phiproj_computed) {
1814                                         phiproj_computed = 1;
1815                                         collect_phiprojs(current_ir_graph);
1816                                 }
1817                                 did_inline = inline_method(call, callee);
1818                                 if (did_inline) {
1819                                         inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1820
1821                                         /* was inlined, must be recomputed */
1822                                         phiproj_computed = 0;
1823
1824                                         /* callee was inline. Append it's call list. */
1825                                         env->got_inline = 1;
1826                                         --env->n_call_nodes;
1827                                         append_call_list(&obst, env, callee_env->call_head);
1828                                         env->n_call_nodes += callee_env->n_call_nodes;
1829                                         env->n_nodes += callee_env->n_nodes;
1830                                         --callee_env->n_callers;
1831
1832                                         /* after we have inlined callee, all called methods inside callee
1833                                            are now called once more */
1834                                         for (centry = callee_env->call_head; centry != NULL; centry = centry->next) {
1835                                                 inline_irg_env *penv = get_irg_link(centry->callee);
1836                                                 ++penv->n_callers;
1837                                         }
1838
1839                                         /* remove this call from the list */
1840                                         if (tail != NULL)
1841                                                 tail->next = entry->next;
1842                                         else
1843                                                 env->call_head = entry->next;
1844                                         continue;
1845                                 }
1846                         }
1847                         tail = entry;
1848                 }
1849                 env->call_tail = tail;
1850         }
1851
1852         for (i = 0; i < n_irgs; ++i) {
1853                 irg = get_irp_irg(i);
1854                 env = (inline_irg_env *)get_irg_link(irg);
1855
1856                 if (env->got_inline) {
1857                         /* this irg got calls inlined */
1858                         set_irg_outs_inconsistent(irg);
1859                         set_irg_doms_inconsistent(irg);
1860
1861                         optimize_graph_df(irg);
1862                         optimize_cf(irg);
1863                 }
1864                 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1865                         DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1866                         env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1867                         env->n_callers_orig, env->n_callers,
1868                         get_entity_name(get_irg_entity(irg))));
1869                 }
1870         }
1871
1872         /* kill the copied graphs: we don't need them anymore */
1873         foreach_pmap(copied_graphs, pm_entry) {
1874                 ir_graph *copy = pm_entry->value;
1875
1876                 /* reset the entity, otherwise it will be deleted in the next step ... */
1877                 set_irg_entity(copy, NULL);
1878                 free_ir_graph(copy);
1879         }
1880         pmap_destroy(copied_graphs);
1881
1882         obstack_free(&obst, NULL);
1883         current_ir_graph = rem;
1884 }