Improved inliner: rerun scalar_replacement() if addresses of local variables were...
[libfirm] / 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 static struct obstack  temp_obst;
1141
1142 /** Represents a possible inlinable call in a graph. */
1143 typedef struct _call_entry call_entry;
1144 struct _call_entry {
1145         ir_node    *call;   /**< the Call */
1146         ir_graph   *callee; /**< the callee called here */
1147         call_entry *next;   /**< for linking the next one */
1148         unsigned   weight;  /**< the weight of the call */
1149 };
1150
1151 /**
1152  * environment for inlining small irgs
1153  */
1154 typedef struct _inline_env_t {
1155         struct obstack obst;  /**< an obstack where call_entries are allocated on. */
1156         call_entry *head;     /**< the head of the call entry list */
1157         call_entry *tail;     /**< the tail of the call entry list */
1158 } inline_env_t;
1159
1160 /**
1161  * Returns the irg called from a Call node. If the irg is not
1162  * known, NULL is returned.
1163  *
1164  * @param call  the call node
1165  */
1166 static ir_graph *get_call_called_irg(ir_node *call) {
1167         ir_node *addr;
1168
1169         addr = get_Call_ptr(call);
1170         if (is_Global(addr)) {
1171                 ir_entity *ent = get_Global_entity(addr);
1172                 return get_entity_irg(ent);
1173         }
1174
1175         return NULL;
1176 }
1177
1178 /**
1179  * Walker: Collect all calls to known graphs inside a graph.
1180  */
1181 static void collect_calls(ir_node *call, void *env) {
1182         if (is_Call(call)) {
1183                 ir_graph *called_irg = get_call_called_irg(call);
1184
1185                 if (called_irg != NULL) {
1186                         /* The Call node calls a locally defined method.  Remember to inline. */
1187                         inline_env_t *ienv  = env;
1188                         call_entry   *entry = obstack_alloc(&ienv->obst, sizeof(*entry));
1189                         entry->call   = call;
1190                         entry->callee = called_irg;
1191                         entry->next   = NULL;
1192                         entry->weight = 0;
1193
1194                         if (ienv->tail == NULL)
1195                                 ienv->head = entry;
1196                         else
1197                                 ienv->tail->next = entry;
1198                         ienv->tail = entry;
1199                 }
1200         }
1201 }
1202
1203 /**
1204  * Inlines all small methods at call sites where the called address comes
1205  * from a Const node that references the entity representing the called
1206  * method.
1207  * The size argument is a rough measure for the code size of the method:
1208  * Methods where the obstack containing the firm graph is smaller than
1209  * size are inlined.
1210  */
1211 void inline_small_irgs(ir_graph *irg, int size) {
1212   ir_graph *rem = current_ir_graph;
1213         inline_env_t env;
1214         call_entry *entry;
1215         DEBUG_ONLY(firm_dbg_module_t *dbg;)
1216
1217         FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1218
1219         current_ir_graph = irg;
1220         /* Handle graph state */
1221         assert(get_irg_phase_state(irg) != phase_building);
1222         free_callee_info(irg);
1223
1224         /* Find Call nodes to inline.
1225            (We can not inline during a walk of the graph, as inlineing the same
1226            method several times changes the visited flag of the walked graph:
1227            after the first inlineing visited of the callee equals visited of
1228            the caller.  With the next inlineing both are increased.) */
1229         obstack_init(&env.obst);
1230         env.head = env.tail = NULL;
1231         irg_walk_graph(irg, NULL, collect_calls, &env);
1232
1233         if (env.head != NULL) {
1234                 /* There are calls to inline */
1235                 collect_phiprojs(irg);
1236                 for (entry = env.head; entry != NULL; entry = entry->next) {
1237                         ir_graph *callee = entry->callee;
1238                         if (((_obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst)) < size) ||
1239                             (get_irg_inline_property(callee) >= irg_inline_forced)) {
1240                                 inline_method(entry->call, callee);
1241                         }
1242                 }
1243         }
1244         obstack_free(&env.obst, NULL);
1245         current_ir_graph = rem;
1246 }
1247
1248 /**
1249  * Environment for inlining irgs.
1250  */
1251 typedef struct {
1252         int n_nodes;             /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
1253         int n_blocks;            /**< Number of Blocks in graph without Start and End block. */
1254         int n_nodes_orig;        /**< for statistics */
1255         call_entry *call_head;   /**< The head of the list of all call nodes in this graph. */
1256         call_entry *call_tail;   /**< The tail of the list of all call nodes in this graph .*/
1257         int n_call_nodes;        /**< Number of Call nodes in the graph. */
1258         int n_call_nodes_orig;   /**< for statistics */
1259         int n_callers;           /**< Number of known graphs that call this graphs. */
1260         int n_callers_orig;      /**< for statistics */
1261         unsigned got_inline:1;   /**< Set, if at least one call inside this graph was inlined. */
1262         unsigned local_vars:1;   /**< Set, if a inlined function gets the address of an inlined variable. */
1263         unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */
1264 } inline_irg_env;
1265
1266 /**
1267  * Allocate a new environment for inlining.
1268  */
1269 static inline_irg_env *alloc_inline_irg_env(void) {
1270         inline_irg_env *env    = obstack_alloc(&temp_obst, sizeof(*env));
1271         env->n_nodes           = -2; /* do not count count Start, End */
1272         env->n_blocks          = -2; /* do not count count Start, End Block */
1273         env->n_nodes_orig      = -2; /* do not count Start, End */
1274         env->call_head         = NULL;
1275         env->call_tail         = NULL;
1276         env->n_call_nodes      = 0;
1277         env->n_call_nodes_orig = 0;
1278         env->n_callers         = 0;
1279         env->n_callers_orig    = 0;
1280         env->got_inline        = 0;
1281         env->local_vars        = 0;
1282         env->local_weights     = NULL;
1283         return env;
1284 }
1285
1286 typedef struct walker_env {
1287         inline_irg_env *x;    /**< the inline environment */
1288         char ignore_runtime;  /**< the ignore runtime flag */
1289         char ignore_callers;  /**< if set, do change callers data */
1290 } wenv_t;
1291
1292 /**
1293  * post-walker: collect all calls in the inline-environment
1294  * of a graph and sum some statistics.
1295  */
1296 static void collect_calls2(ir_node *call, void *ctx) {
1297         wenv_t         *env = ctx;
1298         inline_irg_env *x = env->x;
1299         ir_opcode      code = get_irn_opcode(call);
1300         ir_graph       *callee;
1301         call_entry     *entry;
1302
1303         /* count meaningful nodes in irg */
1304         if (code != iro_Proj && code != iro_Tuple && code != iro_Sync) {
1305                 if (code != iro_Block) {
1306                         ++x->n_nodes;
1307                         ++x->n_nodes_orig;
1308                 } else {
1309                         ++x->n_blocks;
1310                 }
1311         }
1312
1313         if (code != iro_Call) return;
1314
1315         /* check, if it's a runtime call */
1316         if (env->ignore_runtime) {
1317                 ir_node *symc = get_Call_ptr(call);
1318
1319                 if (is_Global(symc)) {
1320                         ir_entity *ent = get_Global_entity(symc);
1321
1322                         if (get_entity_additional_properties(ent) & mtp_property_runtime)
1323                                 return;
1324                 }
1325         }
1326
1327         /* collect all call nodes */
1328         ++x->n_call_nodes;
1329         ++x->n_call_nodes_orig;
1330
1331         callee = get_call_called_irg(call);
1332         if (callee != NULL) {
1333                 if (! env->ignore_callers) {
1334                         inline_irg_env *callee_env = get_irg_link(callee);
1335                         /* count all static callers */
1336                         ++callee_env->n_callers;
1337                         ++callee_env->n_callers_orig;
1338                 }
1339
1340                 /* link it in the list of possible inlinable entries */
1341                 entry = obstack_alloc(&temp_obst, sizeof(*entry));
1342                 entry->call   = call;
1343                 entry->callee = callee;
1344                 entry->next   = NULL;
1345                 if (x->call_tail == NULL)
1346                         x->call_head = entry;
1347                 else
1348                         x->call_tail->next = entry;
1349                 x->call_tail = entry;
1350         }
1351 }
1352
1353 /**
1354  * Returns TRUE if the number of callers is 0 in the irg's environment,
1355  * hence this irg is a leave.
1356  */
1357 INLINE static int is_leave(ir_graph *irg) {
1358         inline_irg_env *env = get_irg_link(irg);
1359         return env->n_call_nodes == 0;
1360 }
1361
1362 /**
1363  * Returns TRUE if the number of nodes in the callee is
1364  * smaller then size in the irg's environment.
1365  */
1366 INLINE static int is_smaller(ir_graph *callee, int size) {
1367         inline_irg_env *env = get_irg_link(callee);
1368         return env->n_nodes < size;
1369 }
1370
1371 /**
1372  * Append the nodes of the list src to the nodes of the list in environment dst.
1373  */
1374 static void append_call_list(inline_irg_env *dst, call_entry *src) {
1375         call_entry *entry, *nentry;
1376
1377         /* Note that the src list points to Call nodes in the inlined graph, but
1378            we need Call nodes in our graph. Luckily the inliner leaves this information
1379            in the link field. */
1380         for (entry = src; entry != NULL; entry = entry->next) {
1381                 nentry = obstack_alloc(&temp_obst, sizeof(*nentry));
1382                 nentry->call   = get_irn_link(entry->call);
1383                 nentry->callee = entry->callee;
1384                 nentry->next   = NULL;
1385                 dst->call_tail->next = nentry;
1386                 dst->call_tail       = nentry;
1387         }
1388 }
1389
1390 /*
1391  * Inlines small leave methods at call sites where the called address comes
1392  * from a Const node that references the entity representing the called
1393  * method.
1394  * The size argument is a rough measure for the code size of the method:
1395  * Methods where the obstack containing the firm graph is smaller than
1396  * size are inlined.
1397  */
1398 void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_runtime) {
1399         inline_irg_env   *env;
1400         ir_graph         *irg;
1401         int              i, n_irgs;
1402         ir_graph         *rem;
1403         int              did_inline;
1404         wenv_t           wenv;
1405         call_entry       *entry, *tail;
1406         const call_entry *centry;
1407         pmap             *copied_graphs;
1408         pmap_entry       *pm_entry;
1409         DEBUG_ONLY(firm_dbg_module_t *dbg;)
1410
1411         FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1412         rem = current_ir_graph;
1413         obstack_init(&temp_obst);
1414
1415         /* a map for the copied graphs, used to inline recursive calls */
1416         copied_graphs = pmap_create();
1417
1418         /* extend all irgs by a temporary data structure for inlining. */
1419         n_irgs = get_irp_n_irgs();
1420         for (i = 0; i < n_irgs; ++i)
1421                 set_irg_link(get_irp_irg(i), alloc_inline_irg_env());
1422
1423         /* Precompute information in temporary data structure. */
1424         wenv.ignore_runtime = ignore_runtime;
1425         wenv.ignore_callers = 0;
1426         for (i = 0; i < n_irgs; ++i) {
1427                 ir_graph *irg = get_irp_irg(i);
1428
1429                 assert(get_irg_phase_state(irg) != phase_building);
1430                 free_callee_info(irg);
1431
1432                 wenv.x = get_irg_link(irg);
1433                 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1434         }
1435
1436         /* -- and now inline. -- */
1437
1438         /* Inline leaves recursively -- we might construct new leaves. */
1439         do {
1440                 did_inline = 0;
1441
1442                 for (i = 0; i < n_irgs; ++i) {
1443                         ir_node *call;
1444                         int phiproj_computed = 0;
1445
1446                         current_ir_graph = get_irp_irg(i);
1447                         env = (inline_irg_env *)get_irg_link(current_ir_graph);
1448
1449                         tail = NULL;
1450                         for (entry = env->call_head; entry != NULL; entry = entry->next) {
1451                                 ir_graph *callee;
1452
1453                                 if (env->n_nodes > maxsize) break;
1454
1455                                 call   = entry->call;
1456                                 callee = entry->callee;
1457
1458                                 if (is_leave(callee) && (
1459                                     is_smaller(callee, leavesize) || (get_irg_inline_property(callee) >= irg_inline_forced))) {
1460                                         if (!phiproj_computed) {
1461                                                 phiproj_computed = 1;
1462                                                 collect_phiprojs(current_ir_graph);
1463                                         }
1464                                         did_inline = inline_method(call, callee);
1465
1466                                         if (did_inline) {
1467                                                 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1468
1469                                                 /* was inlined, must be recomputed */
1470                                                 phiproj_computed = 0;
1471
1472                                                 /* Do some statistics */
1473                                                 env->got_inline = 1;
1474                                                 --env->n_call_nodes;
1475                                                 env->n_nodes += callee_env->n_nodes;
1476                                                 --callee_env->n_callers;
1477
1478                                                 /* remove this call from the list */
1479                                                 if (tail != NULL)
1480                                                         tail->next = entry->next;
1481                                                 else
1482                                                         env->call_head = entry->next;
1483                                                 continue;
1484                                         }
1485                                 }
1486                                 tail = entry;
1487                         }
1488                         env->call_tail = tail;
1489                 }
1490         } while (did_inline);
1491
1492         /* inline other small functions. */
1493         for (i = 0; i < n_irgs; ++i) {
1494                 ir_node *call;
1495                 int phiproj_computed = 0;
1496
1497                 current_ir_graph = get_irp_irg(i);
1498                 env = (inline_irg_env *)get_irg_link(current_ir_graph);
1499
1500                 /* note that the list of possible calls is updated during the process */
1501                 tail = NULL;
1502                 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1503                         ir_graph   *callee;
1504                         pmap_entry *e;
1505
1506                         call   = entry->call;
1507                         callee = entry->callee;
1508
1509                         e = pmap_find(copied_graphs, callee);
1510                         if (e != NULL) {
1511                                 /*
1512                                  * Remap callee if we have a copy.
1513                                  * FIXME: Should we do this only for recursive Calls ?
1514                                  */
1515                                 callee = e->value;
1516                         }
1517
1518                         if (((is_smaller(callee, size) && (env->n_nodes < maxsize)) ||    /* small function */
1519                                 (get_irg_inline_property(callee) >= irg_inline_forced))) {
1520                                 if (current_ir_graph == callee) {
1521                                         /*
1522                                          * Recursive call: we cannot directly inline because we cannot walk
1523                                          * the graph and change it. So we have to make a copy of the graph
1524                                          * first.
1525                                          */
1526
1527                                         inline_irg_env *callee_env;
1528                                         ir_graph       *copy;
1529
1530                                         /*
1531                                          * No copy yet, create one.
1532                                          * Note that recursive methods are never leaves, so it is sufficient
1533                                          * to test this condition here.
1534                                          */
1535                                         copy = create_irg_copy(callee);
1536
1537                                         /* create_irg_copy() destroys the Proj links, recompute them */
1538                                         phiproj_computed = 0;
1539
1540                                         /* allocate new environment */
1541                                         callee_env = alloc_inline_irg_env();
1542                                         set_irg_link(copy, callee_env);
1543
1544                                         wenv.x              = callee_env;
1545                                         wenv.ignore_callers = 1;
1546                                         irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1547
1548                                         /*
1549                                          * Enter the entity of the original graph. This is needed
1550                                          * for inline_method(). However, note that ent->irg still points
1551                                          * to callee, NOT to copy.
1552                                          */
1553                                         set_irg_entity(copy, get_irg_entity(callee));
1554
1555                                         pmap_insert(copied_graphs, callee, copy);
1556                                         callee = copy;
1557
1558                                         /* we have only one caller: the original graph */
1559                                         callee_env->n_callers      = 1;
1560                                         callee_env->n_callers_orig = 1;
1561                                 }
1562                                 if (! phiproj_computed) {
1563                                         phiproj_computed = 1;
1564                                         collect_phiprojs(current_ir_graph);
1565                                 }
1566                                 did_inline = inline_method(call, callee);
1567                                 if (did_inline) {
1568                                         inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1569
1570                                         /* was inlined, must be recomputed */
1571                                         phiproj_computed = 0;
1572
1573                                         /* callee was inline. Append it's call list. */
1574                                         env->got_inline = 1;
1575                                         --env->n_call_nodes;
1576                                         append_call_list(env, callee_env->call_head);
1577                                         env->n_call_nodes += callee_env->n_call_nodes;
1578                                         env->n_nodes += callee_env->n_nodes;
1579                                         --callee_env->n_callers;
1580
1581                                         /* after we have inlined callee, all called methods inside callee
1582                                            are now called once more */
1583                                         for (centry = callee_env->call_head; centry != NULL; centry = centry->next) {
1584                                                 inline_irg_env *penv = get_irg_link(centry->callee);
1585                                                 ++penv->n_callers;
1586                                         }
1587
1588                                         /* remove this call from the list */
1589                                         if (tail != NULL)
1590                                                 tail->next = entry->next;
1591                                         else
1592                                                 env->call_head = entry->next;
1593                                         continue;
1594                                 }
1595                         }
1596                         tail = entry;
1597                 }
1598                 env->call_tail = tail;
1599         }
1600
1601         for (i = 0; i < n_irgs; ++i) {
1602                 irg = get_irp_irg(i);
1603                 env = (inline_irg_env *)get_irg_link(irg);
1604
1605                 if (env->got_inline) {
1606                         /* this irg got calls inlined */
1607                         set_irg_outs_inconsistent(irg);
1608                         set_irg_doms_inconsistent(irg);
1609
1610                         optimize_graph_df(irg);
1611                         optimize_cf(irg);
1612                 }
1613                 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1614                         DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1615                         env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1616                         env->n_callers_orig, env->n_callers,
1617                         get_entity_name(get_irg_entity(irg))));
1618                 }
1619         }
1620
1621         /* kill the copied graphs: we don't need them anymore */
1622         foreach_pmap(copied_graphs, pm_entry) {
1623                 ir_graph *copy = pm_entry->value;
1624
1625                 /* reset the entity, otherwise it will be deleted in the next step ... */
1626                 set_irg_entity(copy, NULL);
1627                 free_ir_graph(copy);
1628         }
1629         pmap_destroy(copied_graphs);
1630
1631         obstack_free(&temp_obst, NULL);
1632         current_ir_graph = rem;
1633 }
1634
1635 /**
1636  * Calculate the parameter weights for transmitting the address of a local variable.
1637  */
1638 static unsigned calc_method_local_weight(ir_node *arg) {
1639         int      i, j, k;
1640         unsigned v, weight = 0;
1641
1642         for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
1643                 ir_node *succ = get_irn_out(arg, i);
1644
1645                 switch (get_irn_opcode(succ)) {
1646                 case iro_Load:
1647                 case iro_Store:
1648                         /* Loads and Store can be removed */
1649                         weight += 3;
1650                         break;
1651                 case iro_Sel:
1652                         /* check if all args are constant */
1653                         for (j = get_Sel_n_indexs(succ) - 1; j >= 0; --j) {
1654                                 ir_node *idx = get_Sel_index(succ, j);
1655                                 if (! is_Const(idx))
1656                                         return 0;
1657                         }
1658                         /* Check users on this Sel. Note: if a 0 is returned here, there was
1659                            some unsupported node. */
1660                         v = calc_method_local_weight(succ);
1661                         if (v == 0)
1662                                 return 0;
1663                         /* we can kill one Sel with constant indexes, this is cheap */
1664                         weight += v + 1;
1665                         break;
1666                 case iro_Id:
1667                         /* when looking backward we might find Id nodes */
1668                         weight += calc_method_local_weight(succ);
1669                         break;
1670                 case iro_Tuple:
1671                         /* unoptimized tuple */
1672                         for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
1673                                 ir_node *pred = get_Tuple_pred(succ, j);
1674                                 if (pred == arg) {
1675                                         /* look for Proj(j) */
1676                                         for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
1677                                                 ir_node *succ_succ = get_irn_out(succ, k);
1678                                                 if (is_Proj(succ_succ)) {
1679                                                         if (get_Proj_proj(succ_succ) == j) {
1680                                                                 /* found */
1681                                                                 weight += calc_method_local_weight(succ_succ);
1682                                                         }
1683                                                 } else {
1684                                                         /* this should NOT happen */
1685                                                         return 0;
1686                                                 }
1687                                         }
1688                                 }
1689                         }
1690                 default:
1691                         /* any other node: unsupported yet or bad. */
1692                         return 0;
1693                 }
1694         }
1695         return weight;
1696 }
1697
1698 /**
1699  * Calculate the parameter weights for transmitting the address of a local variable.
1700  */
1701 static void analyze_irg_local_weights(inline_irg_env *env, ir_graph *irg) {
1702         ir_entity *ent = get_irg_entity(irg);
1703         ir_type  *mtp;
1704         int      nparams, i, proj_nr;
1705         ir_node  *irg_args, *arg;
1706
1707         mtp      = get_entity_type(ent);
1708         nparams  = get_method_n_params(mtp);
1709
1710         /* allocate a new array. currently used as 'analysed' flag */
1711         env->local_weights = NEW_ARR_D(unsigned, &temp_obst, nparams);
1712
1713         /* If the method haven't parameters we have nothing to do. */
1714         if (nparams <= 0)
1715                 return;
1716
1717         assure_irg_outs(irg);
1718         irg_args = get_irg_args(irg);
1719         for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
1720                 arg     = get_irn_out(irg_args, i);
1721                 proj_nr = get_Proj_proj(arg);
1722                 env->local_weights[proj_nr] = calc_method_local_weight(arg);
1723         }
1724 }
1725
1726 /**
1727  * Calculate the benefice for transmitting an local variable address.
1728  * After inlining, the local variable might be transformed into a
1729  * SSA variable by scalar_replacement().
1730  */
1731 static unsigned get_method_local_adress_weight(ir_graph *callee, int pos) {
1732         inline_irg_env *env = get_irg_link(callee);
1733
1734         if (env->local_weights != NULL) {
1735                 if (pos < ARR_LEN(env->local_weights))
1736                         return env->local_weights[pos];
1737                 return 0;
1738         }
1739
1740         analyze_irg_local_weights(env, callee);
1741
1742         if (pos < ARR_LEN(env->local_weights))
1743                 return env->local_weights[pos];
1744         return 0;
1745 }
1746
1747 /**
1748  * calculate a benefice value for inlining the given call.
1749  */
1750 static int calc_inline_benefice(ir_node *call, ir_graph *callee, unsigned *local_adr) {
1751         ir_entity *ent = get_irg_entity(callee);
1752         ir_node   *frame_ptr;
1753         ir_type   *mtp;
1754         int       weight = 0;
1755         int       i, n_params;
1756         unsigned  cc, v;
1757
1758         inline_irg_env *curr_env, *callee_env;
1759
1760         if (get_entity_additional_properties(ent) & mtp_property_noreturn) {
1761                 /* do NOT inline noreturn calls */
1762                 return INT_MIN;
1763         }
1764
1765         /* costs for every passed parameter */
1766         n_params = get_Call_n_params(call);
1767         mtp      = get_entity_type(ent);
1768         cc       = get_method_calling_convention(mtp);
1769         if (cc & cc_reg_param) {
1770                 /* register parameter, smaller costs for register parameters */
1771                 int max_regs = cc & ~cc_bits;
1772
1773                 if (max_regs < n_params)
1774                         weight += max_regs * 2 + (n_params - max_regs) * 5;
1775                 else
1776                         weight += n_params * 2;
1777         } else {
1778                 /* parameters are passed an stack */
1779                 weight += 5 * n_params;
1780         }
1781
1782         /* constant parameters improve the benefice */
1783         frame_ptr = get_irg_frame(current_ir_graph);
1784         for (i = 0; i < n_params; ++i) {
1785                 ir_node *param = get_Call_param(call, i);
1786
1787                 if (is_Const(param) || is_SymConst(param))
1788                         weight += get_method_param_weight(ent, i);
1789                 else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr) {
1790                         /*
1791                          * An address of a local variable is transmitted. After inlining,
1792                          * scalar_replacement might be able to remove the local variable,
1793                          * so honor this.
1794                          */
1795                         v = get_method_local_adress_weight(callee, i);
1796                         weight += v;
1797                         if (v > 0)
1798                                 *local_adr = 1;
1799                 }
1800         }
1801
1802         callee_env = get_irg_link(callee);
1803         if (get_entity_visibility(ent) == visibility_local &&
1804             callee_env->n_callers_orig == 1 &&
1805             callee != current_ir_graph) {
1806                 /* we are the only caller, give big bonus */
1807                 weight += 5000;
1808         }
1809
1810         /* do not inline big functions */
1811         weight -= callee_env->n_nodes;
1812
1813         /* reduce the benefice if the current function is already big */
1814         curr_env = get_irg_link(current_ir_graph);
1815         weight -= curr_env->n_nodes / 100;
1816
1817         /* give a bonus for functions with one block */
1818         if (callee_env->n_blocks == 1)
1819                 weight = weight * 3 / 2;
1820
1821         return weight;
1822 }
1823
1824 /**
1825  * Heuristic inliner. Calculates a benifice value for every call and inlines
1826  * those calls with a value higher than the threshold.
1827  */
1828 void inline_functions(int inline_threshold) {
1829         inline_irg_env   *env;
1830         ir_graph         *irg;
1831         int              i, n_irgs;
1832         ir_graph         *rem;
1833         int              did_inline;
1834         wenv_t           wenv;
1835         call_entry       *entry, *tail;
1836         const call_entry *centry;
1837         pmap             *copied_graphs;
1838         pmap_entry       *pm_entry;
1839         DEBUG_ONLY(firm_dbg_module_t *dbg;)
1840
1841         FIRM_DBG_REGISTER(dbg, "firm.opt.inline");
1842         rem = current_ir_graph;
1843         obstack_init(&temp_obst);
1844
1845         /* a map for the copied graphs, used to inline recursive calls */
1846         copied_graphs = pmap_create();
1847
1848         /* extend all irgs by a temporary data structure for inlining. */
1849         n_irgs = get_irp_n_irgs();
1850         for (i = 0; i < n_irgs; ++i)
1851                 set_irg_link(get_irp_irg(i), alloc_inline_irg_env());
1852
1853         /* Precompute information in temporary data structure. */
1854         wenv.ignore_runtime = 0;
1855         wenv.ignore_callers = 0;
1856         for (i = 0; i < n_irgs; ++i) {
1857                 ir_graph *irg = get_irp_irg(i);
1858
1859                 assert(get_irg_phase_state(irg) != phase_building);
1860                 free_callee_info(irg);
1861
1862                 wenv.x = get_irg_link(irg);
1863                 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1864         }
1865
1866         /* -- and now inline. -- */
1867         for (i = 0; i < n_irgs; ++i) {
1868                 ir_node *call;
1869                 int phiproj_computed = 0;
1870
1871                 current_ir_graph = get_irp_irg(i);
1872                 env = get_irg_link(current_ir_graph);
1873
1874                 /* note that the list of possible calls is updated during the process */
1875                 tail = NULL;
1876                 for (entry = env->call_head; entry != NULL; entry = entry->next) {
1877                         ir_graph   *callee;
1878                         pmap_entry *e;
1879                         int        benefice;
1880                         unsigned   local_adr;
1881
1882                         call   = entry->call;
1883                         callee = entry->callee;
1884
1885                         /* calculate the benifice on the original call to prevent excessive inlining */
1886                         local_adr = 0;
1887                         benefice = calc_inline_benefice(call, callee, &local_adr);
1888                         DB((dbg, SET_LEVEL_2, "In %+F Call %+F has benefice %d\n", current_ir_graph, callee, benefice));
1889
1890                         e = pmap_find(copied_graphs, callee);
1891                         if (e != NULL) {
1892                                 /*
1893                                  * Remap callee if we have a copy.
1894                                  * FIXME: Should we do this only for recursive Calls ?
1895                                  */
1896                                 callee = e->value;
1897                         }
1898
1899                         if (benefice > -inline_threshold ||
1900                                 (get_irg_inline_property(callee) >= irg_inline_forced)) {
1901                                 if (current_ir_graph == callee) {
1902                                         /*
1903                                          * Recursive call: we cannot directly inline because we cannot walk
1904                                          * the graph and change it. So we have to make a copy of the graph
1905                                          * first.
1906                                          */
1907
1908                                         inline_irg_env *callee_env;
1909                                         ir_graph       *copy;
1910
1911                                         /*
1912                                          * No copy yet, create one.
1913                                          * Note that recursive methods are never leaves, so it is sufficient
1914                                          * to test this condition here.
1915                                          */
1916                                         copy = create_irg_copy(callee);
1917
1918                                         /* create_irg_copy() destroys the Proj links, recompute them */
1919                                         phiproj_computed = 0;
1920
1921                                         /* allocate new environment */
1922                                         callee_env = alloc_inline_irg_env();
1923                                         set_irg_link(copy, callee_env);
1924
1925                                         wenv.x              = callee_env;
1926                                         wenv.ignore_callers = 1;
1927                                         irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1928
1929                                         /*
1930                                          * Enter the entity of the original graph. This is needed
1931                                          * for inline_method(). However, note that ent->irg still points
1932                                          * to callee, NOT to copy.
1933                                          */
1934                                         set_irg_entity(copy, get_irg_entity(callee));
1935
1936                                         pmap_insert(copied_graphs, callee, copy);
1937                                         callee = copy;
1938
1939                                         /* we have only one caller: the original graph */
1940                                         callee_env->n_callers      = 1;
1941                                         callee_env->n_callers_orig = 1;
1942                                 }
1943                                 if (! phiproj_computed) {
1944                                         phiproj_computed = 1;
1945                                         collect_phiprojs(current_ir_graph);
1946                                 }
1947                                 did_inline = inline_method(call, callee);
1948                                 if (did_inline) {
1949                                         inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1950
1951                                         /* was inlined, must be recomputed */
1952                                         phiproj_computed = 0;
1953
1954                                         /* callee was inline. Append it's call list. */
1955                                         env->got_inline = 1;
1956                                         if (local_adr)
1957                                                 env->local_vars = 1;
1958                                         --env->n_call_nodes;
1959                                         append_call_list(env, callee_env->call_head);
1960                                         env->n_call_nodes += callee_env->n_call_nodes;
1961                                         env->n_nodes += callee_env->n_nodes;
1962                                         --callee_env->n_callers;
1963
1964                                         /* after we have inlined callee, all called methods inside callee
1965                                            are now called once more */
1966                                         for (centry = callee_env->call_head; centry != NULL; centry = centry->next) {
1967                                                 inline_irg_env *penv = get_irg_link(centry->callee);
1968                                                 ++penv->n_callers;
1969                                         }
1970
1971                                         /* remove this call from the list */
1972                                         if (tail != NULL)
1973                                                 tail->next = entry->next;
1974                                         else
1975                                                 env->call_head = entry->next;
1976                                         continue;
1977                                 }
1978                         }
1979                         tail = entry;
1980                 }
1981                 env->call_tail = tail;
1982         }
1983
1984         for (i = 0; i < n_irgs; ++i) {
1985                 irg = get_irp_irg(i);
1986                 env = (inline_irg_env *)get_irg_link(irg);
1987
1988                 if (env->got_inline) {
1989                         /* this irg got calls inlined */
1990                         set_irg_outs_inconsistent(irg);
1991                         set_irg_doms_inconsistent(irg);
1992
1993                         if (env->local_vars)
1994                                 scalar_replacement_opt(irg);
1995                         optimize_graph_df(irg);
1996                         optimize_cf(irg);
1997                 }
1998                 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1999                         DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
2000                         env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
2001                         env->n_callers_orig, env->n_callers,
2002                         get_entity_name(get_irg_entity(irg))));
2003                 }
2004         }
2005
2006         /* kill the copied graphs: we don't need them anymore */
2007         foreach_pmap(copied_graphs, pm_entry) {
2008                 ir_graph *copy = pm_entry->value;
2009
2010                 /* reset the entity, otherwise it will be deleted in the next step ... */
2011                 set_irg_entity(copy, NULL);
2012                 free_ir_graph(copy);
2013         }
2014         pmap_destroy(copied_graphs);
2015
2016         obstack_free(&temp_obst, NULL);
2017         current_ir_graph = rem;
2018 }