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