2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Dead node elimination and Procedure Inlining.
23 * @author Michael Beck, Goetz Lindenmaier
33 #include "irgraph_t.h"
36 #include "iroptimize.h"
53 #include "irbackedge_t.h"
59 #include "analyze_irg_args.h"
60 #include "iredges_t.h"
64 #include "iropt_dbg.h"
66 #include "irphase_t.h"
68 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
70 /*------------------------------------------------------------------*/
71 /* Routines for dead node elimination / copying garbage collection */
73 /*------------------------------------------------------------------*/
76 * Remember the new node in the old node by using a field all nodes have.
78 static void set_new_node(ir_node *node, ir_node *new_node)
80 set_irn_link(node, new_node);
84 * Get this new node, before the old node is forgotten.
86 static inline ir_node *get_new_node(ir_node *old_node)
88 assert(irn_visited(old_node));
89 return (ir_node*) get_irn_link(old_node);
92 /*--------------------------------------------------------------------*/
93 /* Functionality for inlining */
94 /*--------------------------------------------------------------------*/
97 * Copy node for inlineing. Updates attributes that change when
98 * inlineing but not for dead node elimination.
100 * Copies the node by calling copy_node() and then updates the entity if
101 * it's a local one. env must be a pointer of the frame type of the
102 * inlined procedure. The new entities must be in the link field of
105 static void copy_node_inline(ir_node *node, void *env)
107 ir_graph *new_irg = (ir_graph*) env;
108 ir_node *new_node = irn_copy_into_irg(node, new_irg);
110 set_new_node(node, new_node);
112 ir_graph *old_irg = get_irn_irg(node);
113 ir_type *old_frame_type = get_irg_frame_type(old_irg);
114 ir_entity *old_entity = get_Sel_entity(node);
115 assert(is_Sel(new_node));
116 /* use copied entities from the new frame */
117 if (get_entity_owner(old_entity) == old_frame_type) {
118 ir_entity *new_entity = (ir_entity*)get_entity_link(old_entity);
119 assert(new_entity != NULL);
120 set_Sel_entity(new_node, new_entity);
122 } else if (is_Block(new_node)) {
123 new_node->attr.block.irg.irg = new_irg;
127 static void set_preds_inline(ir_node *node, void *env)
131 irn_rewire_inputs(node);
133 /* move constants into start block */
134 new_node = get_new_node(node);
135 if (is_irn_constlike(new_node)) {
136 ir_graph *new_irg = (ir_graph *) env;
137 ir_node *start_block = get_irg_start_block(new_irg);
138 set_nodes_block(new_node, start_block);
143 * Walker: checks if P_value_arg_base is used.
145 static void find_addr(ir_node *node, void *env)
147 bool *allow_inline = (bool*)env;
150 ir_graph *irg = current_ir_graph;
151 if (get_Sel_ptr(node) == get_irg_frame(irg)) {
152 /* access to frame */
153 ir_entity *ent = get_Sel_entity(node);
154 if (get_entity_owner(ent) != get_irg_frame_type(irg)) {
155 /* access to value_type */
156 *allow_inline = false;
159 } else if (is_Alloc(node) && get_Alloc_where(node) == stack_alloc) {
161 * Refuse to inline alloca call unless user explicitly forced so as this
162 * may change program's memory overhead drastically when the function
163 * using alloca is called in loop. In GCC present in SPEC2000 inlining
164 * into schedule_block cause it to require 2GB of ram instead of 256MB.
166 * Sorrily this is true with our implementation also.
167 * Moreover, we cannot differentiate between alloca() and VLA yet, so
168 * this disables inlining of functions using VLA (which are completely
172 * - add a flag to the Alloc node for "real" alloca() calls
173 * - add a new Stack-Restore node at the end of a function using
176 *allow_inline = false;
181 * Check if we can inline a given call.
182 * Currently, we cannot inline two cases:
183 * - call with compound arguments
184 * - graphs that take the address of a parameter
186 * check these conditions here
188 static bool can_inline(ir_node *call, ir_graph *called_graph)
190 ir_entity *called = get_irg_entity(called_graph);
191 ir_type *called_type = get_entity_type(called);
192 ir_type *call_type = get_Call_type(call);
193 size_t n_params = get_method_n_params(called_type);
194 size_t n_arguments = get_method_n_params(call_type);
195 size_t n_res = get_method_n_ress(called_type);
196 irg_inline_property prop = get_irg_inline_property(called_graph);
200 if (prop == irg_inline_forbidden)
203 if (n_arguments != n_params) {
204 /* this is a bad feature of C: without a prototype, we can
205 * call a function with less parameters than needed. Currently
206 * we don't support this, although we could use Unknown than. */
209 if (n_res != get_method_n_ress(call_type)) {
213 /* Argh, compiling C has some bad consequences:
214 * It is implementation dependent what happens in that case.
215 * We support inlining, if the bitsize of the types matches AND
216 * the same arithmetic is used. */
217 for (i = 0; i < n_params; ++i) {
218 ir_type *param_tp = get_method_param_type(called_type, i);
219 ir_type *arg_tp = get_method_param_type(call_type, i);
221 if (param_tp != arg_tp) {
222 ir_mode *pmode = get_type_mode(param_tp);
223 ir_mode *amode = get_type_mode(arg_tp);
225 if (pmode == NULL || amode == NULL)
227 if (get_mode_size_bits(pmode) != get_mode_size_bits(amode))
229 if (get_mode_arithmetic(pmode) != get_mode_arithmetic(amode))
231 /* otherwise we can simply "reinterpret" the bits */
234 for (i = 0; i < n_res; ++i) {
235 ir_type *decl_res_tp = get_method_res_type(called_type, i);
236 ir_type *used_res_tp = get_method_res_type(call_type, i);
238 if (decl_res_tp != used_res_tp) {
239 ir_mode *decl_mode = get_type_mode(decl_res_tp);
240 ir_mode *used_mode = get_type_mode(used_res_tp);
241 if (decl_mode == NULL || used_mode == NULL)
243 if (get_mode_size_bits(decl_mode) != get_mode_size_bits(used_mode))
245 if (get_mode_arithmetic(decl_mode) != get_mode_arithmetic(used_mode))
247 /* otherwise we can "reinterpret" the bits */
251 /* check parameters for compound arguments */
252 for (i = 0; i < n_params; ++i) {
253 ir_type *p_type = get_method_param_type(call_type, i);
255 if (is_compound_type(p_type))
259 /* check results for compound arguments */
260 for (i = 0; i < n_res; ++i) {
261 ir_type *r_type = get_method_res_type(call_type, i);
263 if (is_compound_type(r_type))
268 irg_walk_graph(called_graph, find_addr, NULL, &res);
274 exc_handler, /**< There is a handler. */
275 exc_no_handler /**< Exception handling not represented. */
279 * copy all entities on the stack frame on 1 irg to the stackframe of another.
280 * Sets entity links of the old entities to the copies
282 static void copy_frame_entities(ir_graph *from, ir_graph *to)
284 ir_type *from_frame = get_irg_frame_type(from);
285 ir_type *to_frame = get_irg_frame_type(to);
286 size_t n_members = get_class_n_members(from_frame);
288 assert(from_frame != to_frame);
290 for (i = 0; i < n_members; ++i) {
291 ir_entity *old_ent = get_class_member(from_frame, i);
292 ir_entity *new_ent = copy_entity_own(old_ent, to_frame);
293 set_entity_link(old_ent, new_ent);
297 /* Inlines a method at the given call site. */
298 int inline_method(ir_node *call, ir_graph *called_graph)
301 ir_node *post_call, *post_bl;
302 ir_node *in[pn_Start_max];
303 ir_node *end, *end_bl, *block;
308 int arity, n_ret, n_exc, n_res, i, j, rem_opt;
309 int irn_arity, n_params;
311 enum exc_mode exc_handling;
316 ir_graph *irg = get_irn_irg(call);
318 /* we cannot inline some types of calls */
319 if (! can_inline(call, called_graph))
322 /* We cannot inline a recursive call. The graph must be copied before
323 * the call the inline_method() using create_irg_copy(). */
324 if (called_graph == irg)
327 ent = get_irg_entity(called_graph);
328 mtp = get_entity_type(ent);
329 ctp = get_Call_type(call);
330 n_params = get_method_n_params(mtp);
331 n_res = get_method_n_ress(mtp);
333 rem = current_ir_graph;
334 current_ir_graph = irg;
336 DB((dbg, LEVEL_1, "Inlining %+F(%+F) into %+F\n", call, called_graph, irg));
338 /* optimizations can cause problems when allocating new nodes */
339 rem_opt = get_opt_optimize();
342 /* Handle graph state */
343 assert(get_irg_phase_state(irg) != phase_building);
344 assert(get_irg_pinned(irg) == op_pin_state_pinned);
345 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
346 set_irg_outs_inconsistent(irg);
347 set_irg_extblk_inconsistent(irg);
348 set_irg_doms_inconsistent(irg);
349 set_irg_loopinfo_inconsistent(irg);
350 set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
351 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
352 edges_deactivate(irg);
354 /* here we know we WILL inline, so inform the statistics */
355 hook_inline(call, called_graph);
357 /* -- Decide how to handle exception control flow: Is there a handler
358 for the Call node, or do we branch directly to End on an exception?
360 0 There is a handler.
361 2 Exception handling not represented in Firm. -- */
363 ir_node *Xproj = NULL;
365 for (proj = (ir_node*)get_irn_link(call); proj != NULL;
366 proj = (ir_node*)get_irn_link(proj)) {
367 long proj_nr = get_Proj_proj(proj);
368 if (proj_nr == pn_Call_X_except) Xproj = proj;
370 exc_handling = Xproj != NULL ? exc_handler : exc_no_handler;
373 /* create the argument tuple */
374 args_in = ALLOCAN(ir_node*, n_params);
376 block = get_nodes_block(call);
377 for (i = n_params - 1; i >= 0; --i) {
378 ir_node *arg = get_Call_param(call, i);
379 ir_type *param_tp = get_method_param_type(mtp, i);
380 ir_mode *mode = get_type_mode(param_tp);
382 if (mode != get_irn_mode(arg)) {
383 arg = new_r_Conv(block, arg, mode);
388 /* the procedure and later replaces the Start node of the called graph.
389 * Post_call is the old Call node and collects the results of the called
390 * graph. Both will end up being a tuple. */
391 post_bl = get_nodes_block(call);
392 /* XxMxPxPxPxT of Start + parameter of Call */
393 in[pn_Start_M] = get_Call_mem(call);
394 in[pn_Start_X_initial_exec] = new_r_Jmp(post_bl);
395 in[pn_Start_P_frame_base] = get_irg_frame(irg);
396 in[pn_Start_P_tls] = get_irg_tls(irg);
397 in[pn_Start_T_args] = new_r_Tuple(post_bl, n_params, args_in);
398 pre_call = new_r_Tuple(post_bl, pn_Start_max, in);
402 The new block gets the ins of the old block, pre_call and all its
403 predecessors and all Phi nodes. -- */
404 part_block(pre_call);
406 /* increment visited flag for later walk */
407 inc_irg_visited(called_graph);
409 /* link some nodes to nodes in the current graph so instead of copying
410 * the linked nodes will get used.
411 * So the copier will use the created Tuple instead of copying the start
412 * node, similar for singleton nodes like NoMem and Bad.
413 * Note: this will prohibit predecessors to be copied - only do it for
414 * nodes without predecessors */
416 ir_node *start_block;
421 start_block = get_irg_start_block(called_graph);
422 set_new_node(start_block, get_nodes_block(pre_call));
423 mark_irn_visited(start_block);
425 start = get_irg_start(called_graph);
426 set_new_node(start, pre_call);
427 mark_irn_visited(start);
429 bad = get_irg_bad(called_graph);
430 set_new_node(bad, get_irg_bad(irg));
431 mark_irn_visited(bad);
433 nomem = get_irg_no_mem(called_graph);
434 set_new_node(nomem, get_irg_no_mem(irg));
435 mark_irn_visited(nomem);
438 /* entitiy link is used to link entities on old stackframe to the
440 irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK);
442 /* copy entities and nodes */
443 assert(!irn_visited(get_irg_end(called_graph)));
444 copy_frame_entities(called_graph, irg);
445 irg_walk_core(get_irg_end(called_graph), copy_node_inline, set_preds_inline,
448 irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK);
450 /* -- Merge the end of the inlined procedure with the call site -- */
451 /* We will turn the old Call node into a Tuple with the following
454 0: Phi of all Memories of Return statements.
455 1: Jmp from new Block that merges the control flow from all exception
456 predecessors of the old end block.
457 2: Tuple of all arguments.
458 3: Phi of Exception memories.
459 In case the old Call directly branches to End on an exception we don't
460 need the block merging all exceptions nor the Phi of the exception
464 /* Precompute some values */
465 end_bl = get_new_node(get_irg_end_block(called_graph));
466 end = get_new_node(get_irg_end(called_graph));
467 arity = get_Block_n_cfgpreds(end_bl); /* arity = n_exc + n_ret */
468 n_res = get_method_n_ress(get_Call_type(call));
470 res_pred = XMALLOCN(ir_node*, n_res);
471 cf_pred = XMALLOCN(ir_node*, arity);
473 /* archive keepalives */
474 irn_arity = get_irn_arity(end);
475 for (i = 0; i < irn_arity; i++) {
476 ir_node *ka = get_End_keepalive(end, i);
478 add_End_keepalive(get_irg_end(irg), ka);
481 /* replace Return nodes by Jump nodes */
483 for (i = 0; i < arity; i++) {
485 ret = get_Block_cfgpred(end_bl, i);
486 if (is_Return(ret)) {
487 ir_node *block = get_nodes_block(ret);
488 cf_pred[n_ret] = new_r_Jmp(block);
492 set_irn_in(post_bl, n_ret, cf_pred);
494 /* build a Tuple for all results of the method.
495 * add Phi node if there was more than one Return. */
496 turn_into_tuple(post_call, pn_Call_max);
497 /* First the Memory-Phi */
499 for (i = 0; i < arity; i++) {
500 ret = get_Block_cfgpred(end_bl, i);
501 if (is_Return(ret)) {
502 cf_pred[n_mem_phi++] = get_Return_mem(ret);
504 /* memory output for some exceptions is directly connected to End */
506 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 3);
507 } else if (is_fragile_op(ret)) {
508 /* We rely that all cfops have the memory output at the same position. */
509 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 0);
510 } else if (is_Raise(ret)) {
511 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 1);
514 phi = new_r_Phi(post_bl, n_mem_phi, cf_pred, mode_M);
515 set_Tuple_pred(call, pn_Call_M, phi);
516 /* Conserve Phi-list for further inlinings -- but might be optimized */
517 if (get_nodes_block(phi) == post_bl) {
518 set_irn_link(phi, get_irn_link(post_bl));
519 set_irn_link(post_bl, phi);
521 /* Now the real results */
523 ir_node *result_tuple;
524 for (j = 0; j < n_res; j++) {
525 ir_type *res_type = get_method_res_type(ctp, j);
526 ir_mode *res_mode = get_type_mode(res_type);
528 for (i = 0; i < arity; i++) {
529 ret = get_Block_cfgpred(end_bl, i);
530 if (is_Return(ret)) {
531 ir_node *res = get_Return_res(ret, j);
532 if (get_irn_mode(res) != res_mode) {
533 ir_node *block = get_nodes_block(res);
534 res = new_r_Conv(block, res, res_mode);
536 cf_pred[n_ret] = res;
541 ir_mode *mode = get_irn_mode(cf_pred[0]);
542 phi = new_r_Phi(post_bl, n_ret, cf_pred, mode);
544 phi = new_r_Bad(irg);
547 /* Conserve Phi-list for further inlinings -- but might be optimized */
548 if (get_nodes_block(phi) == post_bl) {
549 set_Phi_next(phi, get_Block_phis(post_bl));
550 set_Block_phis(post_bl, phi);
553 result_tuple = new_r_Tuple(post_bl, n_res, res_pred);
554 set_Tuple_pred(call, pn_Call_T_result, result_tuple);
556 set_Tuple_pred(call, pn_Call_T_result, new_r_Bad(irg));
558 /* handle the regular call */
559 set_Tuple_pred(call, pn_Call_X_regular, new_r_Jmp(post_bl));
561 /* For now, we cannot inline calls with value_base */
562 set_Tuple_pred(call, pn_Call_P_value_res_base, new_r_Bad(irg));
564 /* Finally the exception control flow.
565 We have two possible situations:
566 First if the Call branches to an exception handler:
567 We need to add a Phi node to
568 collect the memory containing the exception objects. Further we need
569 to add another block to get a correct representation of this Phi. To
570 this block we add a Jmp that resolves into the X output of the Call
571 when the Call is turned into a tuple.
572 Second: There is no exception edge. Just add all inlined exception
573 branches to the End node.
575 if (exc_handling == exc_handler) {
577 for (i = 0; i < arity; i++) {
579 ret = get_Block_cfgpred(end_bl, i);
580 irn = skip_Proj(ret);
581 if (is_fragile_op(irn) || is_Raise(irn)) {
582 cf_pred[n_exc] = ret;
589 set_Tuple_pred(call, pn_Call_X_except, cf_pred[0]);
591 ir_node *block = new_r_Block(irg, n_exc, cf_pred);
592 set_Tuple_pred(call, pn_Call_X_except, new_r_Jmp(block));
595 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg));
598 ir_node *main_end_bl;
599 int main_end_bl_arity;
602 /* assert(exc_handling == 1 || no exceptions. ) */
604 for (i = 0; i < arity; i++) {
605 ir_node *ret = get_Block_cfgpred(end_bl, i);
606 ir_node *irn = skip_Proj(ret);
608 if (is_fragile_op(irn) || is_Raise(irn)) {
609 cf_pred[n_exc] = ret;
613 main_end_bl = get_irg_end_block(irg);
614 main_end_bl_arity = get_irn_arity(main_end_bl);
615 end_preds = XMALLOCN(ir_node*, n_exc + main_end_bl_arity);
617 for (i = 0; i < main_end_bl_arity; ++i)
618 end_preds[i] = get_irn_n(main_end_bl, i);
619 for (i = 0; i < n_exc; ++i)
620 end_preds[main_end_bl_arity + i] = cf_pred[i];
621 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
622 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg));
628 /* -- Turn CSE back on. -- */
629 set_optimize(rem_opt);
630 current_ir_graph = rem;
635 /********************************************************************/
636 /* Apply inlining to small methods. */
637 /********************************************************************/
639 static struct obstack temp_obst;
641 /** Represents a possible inlinable call in a graph. */
642 typedef struct call_entry {
643 ir_node *call; /**< The Call node. */
644 ir_graph *callee; /**< The callee IR-graph. */
645 list_head list; /**< List head for linking the next one. */
646 int loop_depth; /**< The loop depth of this call. */
647 int benefice; /**< The calculated benefice of this call. */
648 unsigned local_adr:1; /**< Set if this call gets an address of a local variable. */
649 unsigned all_const:1; /**< Set if this call has only constant parameters. */
653 * environment for inlining small irgs
655 typedef struct inline_env_t {
656 struct obstack obst; /**< An obstack where call_entries are allocated on. */
657 list_head calls; /**< The call entry list. */
661 * Returns the irg called from a Call node. If the irg is not
662 * known, NULL is returned.
664 * @param call the call node
666 static ir_graph *get_call_called_irg(ir_node *call)
670 addr = get_Call_ptr(call);
671 if (is_Global(addr)) {
672 ir_entity *ent = get_Global_entity(addr);
673 /* we don't know which function gets finally bound to a weak symbol */
674 if (get_entity_linkage(ent) & IR_LINKAGE_WEAK)
677 return get_entity_irg(ent);
684 * Walker: Collect all calls to known graphs inside a graph.
686 static void collect_calls(ir_node *call, void *env)
690 ir_graph *called_irg = get_call_called_irg(call);
692 if (called_irg != NULL) {
693 /* The Call node calls a locally defined method. Remember to inline. */
694 inline_env_t *ienv = (inline_env_t*)env;
695 call_entry *entry = OALLOC(&ienv->obst, call_entry);
697 entry->callee = called_irg;
698 entry->loop_depth = 0;
700 entry->local_adr = 0;
701 entry->all_const = 0;
703 list_add_tail(&entry->list, &ienv->calls);
709 * Inlines all small methods at call sites where the called address comes
710 * from a Const node that references the entity representing the called
712 * The size argument is a rough measure for the code size of the method:
713 * Methods where the obstack containing the firm graph is smaller than
716 void inline_small_irgs(ir_graph *irg, int size)
718 ir_graph *rem = current_ir_graph;
722 current_ir_graph = irg;
723 /* Handle graph state */
724 assert(get_irg_phase_state(irg) != phase_building);
725 free_callee_info(irg);
727 /* Find Call nodes to inline.
728 (We can not inline during a walk of the graph, as inlining the same
729 method several times changes the visited flag of the walked graph:
730 after the first inlining visited of the callee equals visited of
731 the caller. With the next inlining both are increased.) */
732 obstack_init(&env.obst);
733 INIT_LIST_HEAD(&env.calls);
734 irg_walk_graph(irg, NULL, collect_calls, &env);
736 if (! list_empty(&env.calls)) {
737 /* There are calls to inline */
738 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
739 collect_phiprojs(irg);
741 list_for_each_entry(call_entry, entry, &env.calls, list) {
742 ir_graph *callee = entry->callee;
743 irg_inline_property prop = get_irg_inline_property(callee);
745 if (prop == irg_inline_forbidden) {
749 if (prop >= irg_inline_forced ||
750 _obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst) < size) {
751 inline_method(entry->call, callee);
754 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
756 obstack_free(&env.obst, NULL);
757 current_ir_graph = rem;
760 typedef struct inline_small_irgs_pass_t {
761 ir_graph_pass_t pass;
763 } inline_small_irgs_pass_t;
766 * Wrapper to run inline_small_irgs() as a pass.
768 static int inline_small_irgs_wrapper(ir_graph *irg, void *context)
770 inline_small_irgs_pass_t *pass = (inline_small_irgs_pass_t*)context;
772 inline_small_irgs(irg, pass->size);
776 /* create a pass for inline_small_irgs() */
777 ir_graph_pass_t *inline_small_irgs_pass(const char *name, int size)
779 inline_small_irgs_pass_t *pass = XMALLOCZ(inline_small_irgs_pass_t);
782 return def_graph_pass_constructor(
783 &pass->pass, name ? name : "inline_small_irgs", inline_small_irgs_wrapper);
787 * Environment for inlining irgs.
790 list_head calls; /**< List of of all call nodes in this graph. */
791 unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */
792 unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
793 unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */
794 unsigned n_nodes_orig; /**< for statistics */
795 unsigned n_call_nodes; /**< Number of Call nodes in the graph. */
796 unsigned n_call_nodes_orig; /**< for statistics */
797 unsigned n_callers; /**< Number of known graphs that call this graphs. */
798 unsigned n_callers_orig; /**< for statistics */
799 unsigned got_inline:1; /**< Set, if at least one call inside this graph was inlined. */
800 unsigned recursive:1; /**< Set, if this function is self recursive. */
804 * Allocate a new environment for inlining.
806 static inline_irg_env *alloc_inline_irg_env(void)
808 inline_irg_env *env = OALLOC(&temp_obst, inline_irg_env);
809 INIT_LIST_HEAD(&env->calls);
810 env->local_weights = NULL;
811 env->n_nodes = -2; /* do not count count Start, End */
812 env->n_blocks = -2; /* do not count count Start, End Block */
813 env->n_nodes_orig = -2; /* do not count Start, End */
814 env->n_call_nodes = 0;
815 env->n_call_nodes_orig = 0;
817 env->n_callers_orig = 0;
823 typedef struct walker_env {
824 inline_irg_env *x; /**< the inline environment */
825 char ignore_runtime; /**< the ignore runtime flag */
826 char ignore_callers; /**< if set, do change callers data */
830 * post-walker: collect all calls in the inline-environment
831 * of a graph and sum some statistics.
833 static void collect_calls2(ir_node *call, void *ctx)
835 wenv_t *env = (wenv_t*)ctx;
836 inline_irg_env *x = env->x;
837 unsigned code = get_irn_opcode(call);
841 /* count meaningful nodes in irg */
842 if (code != iro_Proj && code != iro_Tuple && code != iro_Sync) {
843 if (code != iro_Block) {
851 if (code != iro_Call) return;
853 /* check, if it's a runtime call */
854 if (env->ignore_runtime) {
855 ir_node *symc = get_Call_ptr(call);
857 if (is_Global(symc)) {
858 ir_entity *ent = get_Global_entity(symc);
860 if (get_entity_additional_properties(ent) & mtp_property_runtime)
865 /* collect all call nodes */
867 ++x->n_call_nodes_orig;
869 callee = get_call_called_irg(call);
870 if (callee != NULL) {
871 if (! env->ignore_callers) {
872 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
873 /* count all static callers */
874 ++callee_env->n_callers;
875 ++callee_env->n_callers_orig;
877 if (callee == current_ir_graph)
880 /* link it in the list of possible inlinable entries */
881 entry = OALLOC(&temp_obst, call_entry);
883 entry->callee = callee;
884 entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth;
886 entry->local_adr = 0;
887 entry->all_const = 0;
889 list_add_tail(&entry->list, &x->calls);
894 * Returns TRUE if the number of callers is 0 in the irg's environment,
895 * hence this irg is a leave.
897 inline static int is_leave(ir_graph *irg)
899 inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
900 return env->n_call_nodes == 0;
904 * Returns TRUE if the number of nodes in the callee is
905 * smaller then size in the irg's environment.
907 inline static int is_smaller(ir_graph *callee, unsigned size)
909 inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
910 return env->n_nodes < size;
914 * Duplicate a call entry.
916 * @param entry the original entry to duplicate
917 * @param new_call the new call node
918 * @param loop_depth_delta
919 * delta value for the loop depth
921 static call_entry *duplicate_call_entry(const call_entry *entry,
922 ir_node *new_call, int loop_depth_delta)
924 call_entry *nentry = OALLOC(&temp_obst, call_entry);
925 nentry->call = new_call;
926 nentry->callee = entry->callee;
927 nentry->benefice = entry->benefice;
928 nentry->loop_depth = entry->loop_depth + loop_depth_delta;
929 nentry->local_adr = entry->local_adr;
930 nentry->all_const = entry->all_const;
936 * Append all call nodes of the source environment to the nodes of in the destination
939 * @param dst destination environment
940 * @param src source environment
941 * @param loop_depth the loop depth of the call that is replaced by the src list
943 static void append_call_list(inline_irg_env *dst, inline_irg_env *src, int loop_depth)
945 call_entry *entry, *nentry;
947 /* Note that the src list points to Call nodes in the inlined graph, but
948 we need Call nodes in our graph. Luckily the inliner leaves this information
949 in the link field. */
950 list_for_each_entry(call_entry, entry, &src->calls, list) {
951 nentry = duplicate_call_entry(entry, (ir_node*)get_irn_link(entry->call), loop_depth);
952 list_add_tail(&nentry->list, &dst->calls);
954 dst->n_call_nodes += src->n_call_nodes;
955 dst->n_nodes += src->n_nodes;
959 * Inlines small leave methods at call sites where the called address comes
960 * from a Const node that references the entity representing the called
962 * The size argument is a rough measure for the code size of the method:
963 * Methods where the obstack containing the firm graph is smaller than
966 void inline_leave_functions(unsigned maxsize, unsigned leavesize,
967 unsigned size, int ignore_runtime)
975 call_entry *entry, *next;
976 const call_entry *centry;
978 pmap_entry *pm_entry;
980 rem = current_ir_graph;
981 obstack_init(&temp_obst);
983 /* a map for the copied graphs, used to inline recursive calls */
984 copied_graphs = pmap_create();
986 /* extend all irgs by a temporary data structure for inlining. */
987 n_irgs = get_irp_n_irgs();
988 for (i = 0; i < n_irgs; ++i)
989 set_irg_link(get_irp_irg(i), alloc_inline_irg_env());
991 /* Pre-compute information in temporary data structure. */
992 wenv.ignore_runtime = ignore_runtime;
993 wenv.ignore_callers = 0;
994 for (i = 0; i < n_irgs; ++i) {
995 ir_graph *irg = get_irp_irg(i);
997 assert(get_irg_phase_state(irg) != phase_building);
998 free_callee_info(irg);
1000 assure_cf_loop(irg);
1001 wenv.x = (inline_irg_env*)get_irg_link(irg);
1002 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1005 /* -- and now inline. -- */
1007 /* Inline leaves recursively -- we might construct new leaves. */
1011 for (i = 0; i < n_irgs; ++i) {
1013 int phiproj_computed = 0;
1015 current_ir_graph = get_irp_irg(i);
1016 env = (inline_irg_env*)get_irg_link(current_ir_graph);
1018 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1019 list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
1021 irg_inline_property prop;
1023 if (env->n_nodes > maxsize)
1027 callee = entry->callee;
1029 prop = get_irg_inline_property(callee);
1030 if (prop == irg_inline_forbidden) {
1034 if (is_leave(callee) && (
1035 is_smaller(callee, leavesize) || prop >= irg_inline_forced)) {
1036 if (!phiproj_computed) {
1037 phiproj_computed = 1;
1038 collect_phiprojs(current_ir_graph);
1040 did_inline = inline_method(call, callee);
1043 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1045 /* call was inlined, Phi/Projs for current graph must be recomputed */
1046 phiproj_computed = 0;
1048 /* Do some statistics */
1049 env->got_inline = 1;
1050 --env->n_call_nodes;
1051 env->n_nodes += callee_env->n_nodes;
1052 --callee_env->n_callers;
1054 /* remove this call from the list */
1055 list_del(&entry->list);
1060 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1062 } while (did_inline);
1064 /* inline other small functions. */
1065 for (i = 0; i < n_irgs; ++i) {
1067 int phiproj_computed = 0;
1069 current_ir_graph = get_irp_irg(i);
1070 env = (inline_irg_env*)get_irg_link(current_ir_graph);
1072 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1074 /* note that the list of possible calls is updated during the process */
1075 list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
1076 irg_inline_property prop;
1081 callee = entry->callee;
1083 prop = get_irg_inline_property(callee);
1084 if (prop == irg_inline_forbidden) {
1088 e = pmap_find(copied_graphs, callee);
1091 * Remap callee if we have a copy.
1092 * FIXME: Should we do this only for recursive Calls ?
1094 callee = (ir_graph*)e->value;
1097 if (prop >= irg_inline_forced ||
1098 (is_smaller(callee, size) && env->n_nodes < maxsize) /* small function */) {
1099 if (current_ir_graph == callee) {
1101 * Recursive call: we cannot directly inline because we cannot walk
1102 * the graph and change it. So we have to make a copy of the graph
1106 inline_irg_env *callee_env;
1109 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1112 * No copy yet, create one.
1113 * Note that recursive methods are never leaves, so it is sufficient
1114 * to test this condition here.
1116 copy = create_irg_copy(callee);
1118 /* create_irg_copy() destroys the Proj links, recompute them */
1119 phiproj_computed = 0;
1121 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1123 /* allocate new environment */
1124 callee_env = alloc_inline_irg_env();
1125 set_irg_link(copy, callee_env);
1127 assure_cf_loop(copy);
1128 wenv.x = callee_env;
1129 wenv.ignore_callers = 1;
1130 irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1133 * Enter the entity of the original graph. This is needed
1134 * for inline_method(). However, note that ent->irg still points
1135 * to callee, NOT to copy.
1137 set_irg_entity(copy, get_irg_entity(callee));
1139 pmap_insert(copied_graphs, callee, copy);
1142 /* we have only one caller: the original graph */
1143 callee_env->n_callers = 1;
1144 callee_env->n_callers_orig = 1;
1146 if (! phiproj_computed) {
1147 phiproj_computed = 1;
1148 collect_phiprojs(current_ir_graph);
1150 did_inline = inline_method(call, callee);
1152 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1154 /* call was inlined, Phi/Projs for current graph must be recomputed */
1155 phiproj_computed = 0;
1157 /* callee was inline. Append it's call list. */
1158 env->got_inline = 1;
1159 --env->n_call_nodes;
1160 append_call_list(env, callee_env, entry->loop_depth);
1161 --callee_env->n_callers;
1163 /* after we have inlined callee, all called methods inside callee
1164 are now called once more */
1165 list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1166 inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1170 /* remove this call from the list */
1171 list_del(&entry->list);
1176 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1179 for (i = 0; i < n_irgs; ++i) {
1180 irg = get_irp_irg(i);
1181 env = (inline_irg_env*)get_irg_link(irg);
1183 if (env->got_inline) {
1184 optimize_graph_df(irg);
1187 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1188 DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1189 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1190 env->n_callers_orig, env->n_callers,
1191 get_entity_name(get_irg_entity(irg))));
1195 /* kill the copied graphs: we don't need them anymore */
1196 foreach_pmap(copied_graphs, pm_entry) {
1197 ir_graph *copy = (ir_graph*)pm_entry->value;
1199 /* reset the entity, otherwise it will be deleted in the next step ... */
1200 set_irg_entity(copy, NULL);
1201 free_ir_graph(copy);
1203 pmap_destroy(copied_graphs);
1205 obstack_free(&temp_obst, NULL);
1206 current_ir_graph = rem;
1209 typedef struct inline_leave_functions_pass_t {
1210 ir_prog_pass_t pass;
1215 } inline_leave_functions_pass_t;
1218 * Wrapper to run inline_leave_functions() as a ir_prog pass.
1220 static int inline_leave_functions_wrapper(ir_prog *irp, void *context)
1222 inline_leave_functions_pass_t *pass = (inline_leave_functions_pass_t*)context;
1225 inline_leave_functions(
1226 pass->maxsize, pass->leavesize,
1227 pass->size, pass->ignore_runtime);
1231 /* create a pass for inline_leave_functions() */
1232 ir_prog_pass_t *inline_leave_functions_pass(
1233 const char *name, unsigned maxsize, unsigned leavesize,
1234 unsigned size, int ignore_runtime)
1236 inline_leave_functions_pass_t *pass = XMALLOCZ(inline_leave_functions_pass_t);
1238 pass->maxsize = maxsize;
1239 pass->leavesize = leavesize;
1241 pass->ignore_runtime = ignore_runtime;
1243 return def_prog_pass_constructor(
1245 name ? name : "inline_leave_functions",
1246 inline_leave_functions_wrapper);
1250 * Calculate the parameter weights for transmitting the address of a local variable.
1252 static unsigned calc_method_local_weight(ir_node *arg)
1255 unsigned v, weight = 0;
1257 for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
1258 ir_node *succ = get_irn_out(arg, i);
1260 switch (get_irn_opcode(succ)) {
1263 /* Loads and Store can be removed */
1267 /* check if all args are constant */
1268 for (j = get_Sel_n_indexs(succ) - 1; j >= 0; --j) {
1269 ir_node *idx = get_Sel_index(succ, j);
1270 if (! is_Const(idx))
1273 /* Check users on this Sel. Note: if a 0 is returned here, there was
1274 some unsupported node. */
1275 v = calc_method_local_weight(succ);
1278 /* we can kill one Sel with constant indexes, this is cheap */
1282 /* when looking backward we might find Id nodes */
1283 weight += calc_method_local_weight(succ);
1286 /* unoptimized tuple */
1287 for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
1288 ir_node *pred = get_Tuple_pred(succ, j);
1290 /* look for Proj(j) */
1291 for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
1292 ir_node *succ_succ = get_irn_out(succ, k);
1293 if (is_Proj(succ_succ)) {
1294 if (get_Proj_proj(succ_succ) == j) {
1296 weight += calc_method_local_weight(succ_succ);
1299 /* this should NOT happen */
1307 /* any other node: unsupported yet or bad. */
1315 * Calculate the parameter weights for transmitting the address of a local variable.
1317 static void analyze_irg_local_weights(inline_irg_env *env, ir_graph *irg)
1319 ir_entity *ent = get_irg_entity(irg);
1324 ir_node *irg_args, *arg;
1326 mtp = get_entity_type(ent);
1327 nparams = get_method_n_params(mtp);
1329 /* allocate a new array. currently used as 'analysed' flag */
1330 env->local_weights = NEW_ARR_D(unsigned, &temp_obst, nparams);
1332 /* If the method haven't parameters we have nothing to do. */
1336 assure_irg_outs(irg);
1337 irg_args = get_irg_args(irg);
1338 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
1339 arg = get_irn_out(irg_args, i);
1340 proj_nr = get_Proj_proj(arg);
1341 env->local_weights[proj_nr] = calc_method_local_weight(arg);
1346 * Calculate the benefice for transmitting an local variable address.
1347 * After inlining, the local variable might be transformed into a
1348 * SSA variable by scalar_replacement().
1350 static unsigned get_method_local_adress_weight(ir_graph *callee, size_t pos)
1352 inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
1354 if (env->local_weights == NULL)
1355 analyze_irg_local_weights(env, callee);
1357 if (pos < ARR_LEN(env->local_weights))
1358 return env->local_weights[pos];
1363 * Calculate a benefice value for inlining the given call.
1365 * @param call the call node we have to inspect
1366 * @param callee the called graph
1368 static int calc_inline_benefice(call_entry *entry, ir_graph *callee)
1370 ir_node *call = entry->call;
1371 ir_entity *ent = get_irg_entity(callee);
1375 int i, n_params, all_const;
1377 irg_inline_property prop;
1379 inline_irg_env *callee_env;
1381 prop = get_irg_inline_property(callee);
1382 if (prop == irg_inline_forbidden) {
1383 DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n",
1385 return entry->benefice = INT_MIN;
1388 if (get_irg_additional_properties(callee) & mtp_property_noreturn) {
1389 DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n",
1391 return entry->benefice = INT_MIN;
1394 /* costs for every passed parameter */
1395 n_params = get_Call_n_params(call);
1396 mtp = get_entity_type(ent);
1397 cc = get_method_calling_convention(mtp);
1398 if (cc & cc_reg_param) {
1399 /* register parameter, smaller costs for register parameters */
1400 int max_regs = cc & ~cc_bits;
1402 if (max_regs < n_params)
1403 weight += max_regs * 2 + (n_params - max_regs) * 5;
1405 weight += n_params * 2;
1407 /* parameters are passed an stack */
1408 weight += 5 * n_params;
1411 /* constant parameters improve the benefice */
1412 frame_ptr = get_irg_frame(current_ir_graph);
1414 for (i = 0; i < n_params; ++i) {
1415 ir_node *param = get_Call_param(call, i);
1417 if (is_Const(param)) {
1418 weight += get_method_param_weight(ent, i);
1421 if (is_SymConst(param))
1422 weight += get_method_param_weight(ent, i);
1423 else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr) {
1425 * An address of a local variable is transmitted. After
1426 * inlining, scalar_replacement might be able to remove the
1427 * local variable, so honor this.
1429 v = get_method_local_adress_weight(callee, i);
1432 entry->local_adr = 1;
1436 entry->all_const = all_const;
1438 callee_env = (inline_irg_env*)get_irg_link(callee);
1439 if (callee_env->n_callers == 1 &&
1440 callee != current_ir_graph &&
1441 !entity_is_externally_visible(ent)) {
1445 /* give a bonus for functions with one block */
1446 if (callee_env->n_blocks == 1)
1447 weight = weight * 3 / 2;
1449 /* and one for small non-recursive functions: we want them to be inlined in mostly every case */
1450 if (callee_env->n_nodes < 30 && !callee_env->recursive)
1453 /* and finally for leaves: they do not increase the register pressure
1454 because of callee safe registers */
1455 if (callee_env->n_call_nodes == 0)
1458 /** it's important to inline inner loops first */
1459 if (entry->loop_depth > 30)
1460 weight += 30 * 1024;
1462 weight += entry->loop_depth * 1024;
1465 * All arguments constant is probably a good sign, give an extra bonus
1470 return entry->benefice = weight;
1473 typedef struct walk_env_t {
1479 * Callgraph walker, collect all visited graphs.
1481 static void callgraph_walker(ir_graph *irg, void *data)
1483 walk_env_t *env = (walk_env_t *)data;
1484 env->irgs[env->last_irg++] = irg;
1488 * Creates an inline order for all graphs.
1490 * @return the list of graphs.
1492 static ir_graph **create_irg_list(void)
1494 ir_entity **free_methods;
1495 size_t n_irgs = get_irp_n_irgs();
1498 cgana(&free_methods);
1499 xfree(free_methods);
1501 compute_callgraph();
1503 env.irgs = XMALLOCNZ(ir_graph*, n_irgs);
1506 callgraph_walk(NULL, callgraph_walker, &env);
1507 assert(n_irgs == env.last_irg);
1513 * Push a call onto the priority list if its benefice is big enough.
1515 * @param pqueue the priority queue of calls
1516 * @param call the call entry
1517 * @param inlien_threshold
1518 * the threshold value
1520 static void maybe_push_call(pqueue_t *pqueue, call_entry *call,
1521 int inline_threshold)
1523 ir_graph *callee = call->callee;
1524 irg_inline_property prop = get_irg_inline_property(callee);
1525 int benefice = calc_inline_benefice(call, callee);
1527 DB((dbg, LEVEL_2, "In %+F Call %+F to %+F has benefice %d\n",
1528 get_irn_irg(call->call), call->call, callee, benefice));
1530 if (prop < irg_inline_forced && benefice < inline_threshold) {
1534 pqueue_put(pqueue, call, benefice);
1538 * Try to inline calls into a graph.
1540 * @param irg the graph into which we inline
1541 * @param maxsize do NOT inline if the size of irg gets
1542 * bigger than this amount
1543 * @param inline_threshold
1544 * threshold value for inline decision
1545 * @param copied_graphs
1546 * map containing copied of recursive graphs
1548 static void inline_into(ir_graph *irg, unsigned maxsize,
1549 int inline_threshold, pmap *copied_graphs)
1551 int phiproj_computed = 0;
1552 inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
1553 call_entry *curr_call;
1557 if (env->n_call_nodes == 0)
1560 if (env->n_nodes > maxsize) {
1561 DB((dbg, LEVEL_2, "%+F: too big (%d)\n", irg, env->n_nodes));
1565 current_ir_graph = irg;
1566 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1568 /* put irgs into the pqueue */
1569 pqueue = new_pqueue();
1571 list_for_each_entry(call_entry, curr_call, &env->calls, list) {
1572 assert(is_Call(curr_call->call));
1573 maybe_push_call(pqueue, curr_call, inline_threshold);
1576 /* note that the list of possible calls is updated during the process */
1577 while (!pqueue_empty(pqueue)) {
1579 call_entry *curr_call = (call_entry*)pqueue_pop_front(pqueue);
1580 ir_graph *callee = curr_call->callee;
1581 ir_node *call_node = curr_call->call;
1582 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1583 irg_inline_property prop = get_irg_inline_property(callee);
1585 const call_entry *centry;
1588 if ((prop < irg_inline_forced) && env->n_nodes + callee_env->n_nodes > maxsize) {
1589 DB((dbg, LEVEL_2, "%+F: too big (%d) + %+F (%d)\n", irg,
1590 env->n_nodes, callee, callee_env->n_nodes));
1594 e = pmap_find(copied_graphs, callee);
1596 int benefice = curr_call->benefice;
1598 * Reduce the weight for recursive function IFF not all arguments are const.
1599 * inlining recursive functions is rarely good.
1601 if (!curr_call->all_const)
1603 if (benefice < inline_threshold)
1607 * Remap callee if we have a copy.
1609 callee = (ir_graph*)e->value;
1610 callee_env = (inline_irg_env*)get_irg_link(callee);
1613 if (current_ir_graph == callee) {
1615 * Recursive call: we cannot directly inline because we cannot
1616 * walk the graph and change it. So we have to make a copy of
1619 int benefice = curr_call->benefice;
1623 * Reduce the weight for recursive function IFF not all arguments are const.
1624 * inlining recursive functions is rarely good.
1626 if (!curr_call->all_const)
1628 if (benefice < inline_threshold)
1631 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1634 * No copy yet, create one.
1635 * Note that recursive methods are never leaves, so it is
1636 * sufficient to test this condition here.
1638 copy = create_irg_copy(callee);
1640 /* create_irg_copy() destroys the Proj links, recompute them */
1641 phiproj_computed = 0;
1643 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1645 /* allocate a new environment */
1646 callee_env = alloc_inline_irg_env();
1647 set_irg_link(copy, callee_env);
1649 assure_cf_loop(copy);
1650 wenv.x = callee_env;
1651 wenv.ignore_callers = 1;
1652 irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1655 * Enter the entity of the original graph. This is needed
1656 * for inline_method(). However, note that ent->irg still points
1657 * to callee, NOT to copy.
1659 set_irg_entity(copy, get_irg_entity(callee));
1661 pmap_insert(copied_graphs, callee, copy);
1664 /* we have only one caller: the original graph */
1665 callee_env->n_callers = 1;
1666 callee_env->n_callers_orig = 1;
1668 if (! phiproj_computed) {
1669 phiproj_computed = 1;
1670 collect_phiprojs(current_ir_graph);
1672 did_inline = inline_method(call_node, callee);
1676 /* call was inlined, Phi/Projs for current graph must be recomputed */
1677 phiproj_computed = 0;
1679 /* remove it from the caller list */
1680 list_del(&curr_call->list);
1682 /* callee was inline. Append it's call list. */
1683 env->got_inline = 1;
1684 --env->n_call_nodes;
1686 /* we just generate a bunch of new calls */
1687 loop_depth = curr_call->loop_depth;
1688 list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1689 inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1691 call_entry *new_entry;
1693 /* after we have inlined callee, all called methods inside
1694 * callee are now called once more */
1697 /* Note that the src list points to Call nodes in the inlined graph,
1698 * but we need Call nodes in our graph. Luckily the inliner leaves
1699 * this information in the link field. */
1700 new_call = (ir_node*)get_irn_link(centry->call);
1701 assert(is_Call(new_call));
1703 new_entry = duplicate_call_entry(centry, new_call, loop_depth);
1704 list_add_tail(&new_entry->list, &env->calls);
1705 maybe_push_call(pqueue, new_entry, inline_threshold);
1708 env->n_call_nodes += callee_env->n_call_nodes;
1709 env->n_nodes += callee_env->n_nodes;
1710 --callee_env->n_callers;
1712 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1717 * Heuristic inliner. Calculates a benefice value for every call and inlines
1718 * those calls with a value higher than the threshold.
1720 void inline_functions(unsigned maxsize, int inline_threshold,
1721 opt_ptr after_inline_opt)
1723 inline_irg_env *env;
1727 pmap *copied_graphs;
1728 pmap_entry *pm_entry;
1731 rem = current_ir_graph;
1732 obstack_init(&temp_obst);
1734 irgs = create_irg_list();
1736 /* a map for the copied graphs, used to inline recursive calls */
1737 copied_graphs = pmap_create();
1739 /* extend all irgs by a temporary data structure for inlining. */
1740 n_irgs = get_irp_n_irgs();
1741 for (i = 0; i < n_irgs; ++i)
1742 set_irg_link(irgs[i], alloc_inline_irg_env());
1744 /* Pre-compute information in temporary data structure. */
1745 wenv.ignore_runtime = 0;
1746 wenv.ignore_callers = 0;
1747 for (i = 0; i < n_irgs; ++i) {
1748 ir_graph *irg = irgs[i];
1750 free_callee_info(irg);
1752 wenv.x = (inline_irg_env*)get_irg_link(irg);
1753 assure_cf_loop(irg);
1754 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1757 /* -- and now inline. -- */
1758 for (i = 0; i < n_irgs; ++i) {
1759 ir_graph *irg = irgs[i];
1761 inline_into(irg, maxsize, inline_threshold, copied_graphs);
1764 for (i = 0; i < n_irgs; ++i) {
1765 ir_graph *irg = irgs[i];
1767 env = (inline_irg_env*)get_irg_link(irg);
1768 if (env->got_inline && after_inline_opt != NULL) {
1769 /* this irg got calls inlined: optimize it */
1770 after_inline_opt(irg);
1772 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1773 DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1774 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1775 env->n_callers_orig, env->n_callers,
1776 get_entity_name(get_irg_entity(irg))));
1780 /* kill the copied graphs: we don't need them anymore */
1781 foreach_pmap(copied_graphs, pm_entry) {
1782 ir_graph *copy = (ir_graph*)pm_entry->value;
1784 /* reset the entity, otherwise it will be deleted in the next step ... */
1785 set_irg_entity(copy, NULL);
1786 free_ir_graph(copy);
1788 pmap_destroy(copied_graphs);
1792 obstack_free(&temp_obst, NULL);
1793 current_ir_graph = rem;
1796 typedef struct inline_functions_pass_t {
1797 ir_prog_pass_t pass;
1799 int inline_threshold;
1800 opt_ptr after_inline_opt;
1801 } inline_functions_pass_t;
1804 * Wrapper to run inline_functions() as a ir_prog pass.
1806 static int inline_functions_wrapper(ir_prog *irp, void *context)
1808 inline_functions_pass_t *pass = (inline_functions_pass_t*)context;
1811 inline_functions(pass->maxsize, pass->inline_threshold,
1812 pass->after_inline_opt);
1816 /* create a ir_prog pass for inline_functions */
1817 ir_prog_pass_t *inline_functions_pass(
1818 const char *name, unsigned maxsize, int inline_threshold,
1819 opt_ptr after_inline_opt)
1821 inline_functions_pass_t *pass = XMALLOCZ(inline_functions_pass_t);
1823 pass->maxsize = maxsize;
1824 pass->inline_threshold = inline_threshold;
1825 pass->after_inline_opt = after_inline_opt;
1827 return def_prog_pass_constructor(
1828 &pass->pass, name ? name : "inline_functions",
1829 inline_functions_wrapper);
1832 void firm_init_inline(void)
1834 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");