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;
158 if (is_parameter_entity(ent)) {
159 *allow_inline = false;
162 } else if (is_Alloc(node) && get_Alloc_where(node) == stack_alloc) {
164 * Refuse to inline alloca call unless user explicitly forced so as this
165 * may change program's memory overhead drastically when the function
166 * using alloca is called in loop. In GCC present in SPEC2000 inlining
167 * into schedule_block cause it to require 2GB of ram instead of 256MB.
169 * Sorrily this is true with our implementation also.
170 * Moreover, we cannot differentiate between alloca() and VLA yet, so
171 * this disables inlining of functions using VLA (which are completely
175 * - add a flag to the Alloc node for "real" alloca() calls
176 * - add a new Stack-Restore node at the end of a function using
179 *allow_inline = false;
184 * Check if we can inline a given call.
185 * Currently, we cannot inline two cases:
186 * - call with compound arguments
187 * - graphs that take the address of a parameter
189 * check these conditions here
191 static bool can_inline(ir_node *call, ir_graph *called_graph)
193 ir_entity *called = get_irg_entity(called_graph);
194 ir_type *called_type = get_entity_type(called);
195 ir_type *call_type = get_Call_type(call);
196 size_t n_params = get_method_n_params(called_type);
197 size_t n_arguments = get_method_n_params(call_type);
198 size_t n_res = get_method_n_ress(called_type);
199 irg_inline_property prop = get_irg_inline_property(called_graph);
203 if (prop == irg_inline_forbidden)
206 if (n_arguments != n_params) {
207 /* this is a bad feature of C: without a prototype, we can
208 * call a function with less parameters than needed. Currently
209 * we don't support this, although we could use Unknown than. */
212 if (n_res != get_method_n_ress(call_type)) {
216 /* Argh, compiling C has some bad consequences:
217 * It is implementation dependent what happens in that case.
218 * We support inlining, if the bitsize of the types matches AND
219 * the same arithmetic is used. */
220 for (i = 0; i < n_params; ++i) {
221 ir_type *param_tp = get_method_param_type(called_type, i);
222 ir_type *arg_tp = get_method_param_type(call_type, i);
224 if (param_tp != arg_tp) {
225 ir_mode *pmode = get_type_mode(param_tp);
226 ir_mode *amode = get_type_mode(arg_tp);
228 if (pmode == NULL || amode == NULL)
230 if (get_mode_size_bits(pmode) != get_mode_size_bits(amode))
232 if (get_mode_arithmetic(pmode) != get_mode_arithmetic(amode))
234 /* otherwise we can simply "reinterpret" the bits */
237 for (i = 0; i < n_res; ++i) {
238 ir_type *decl_res_tp = get_method_res_type(called_type, i);
239 ir_type *used_res_tp = get_method_res_type(call_type, i);
241 if (decl_res_tp != used_res_tp) {
242 ir_mode *decl_mode = get_type_mode(decl_res_tp);
243 ir_mode *used_mode = get_type_mode(used_res_tp);
244 if (decl_mode == NULL || used_mode == NULL)
246 if (get_mode_size_bits(decl_mode) != get_mode_size_bits(used_mode))
248 if (get_mode_arithmetic(decl_mode) != get_mode_arithmetic(used_mode))
250 /* otherwise we can "reinterpret" the bits */
254 /* check parameters for compound arguments */
255 for (i = 0; i < n_params; ++i) {
256 ir_type *p_type = get_method_param_type(call_type, i);
258 if (is_compound_type(p_type))
262 /* check results for compound arguments */
263 for (i = 0; i < n_res; ++i) {
264 ir_type *r_type = get_method_res_type(call_type, i);
266 if (is_compound_type(r_type))
271 irg_walk_graph(called_graph, find_addr, NULL, &res);
277 exc_handler, /**< There is a handler. */
278 exc_no_handler /**< Exception handling not represented. */
282 * copy all entities on the stack frame on 1 irg to the stackframe of another.
283 * Sets entity links of the old entities to the copies
285 static void copy_frame_entities(ir_graph *from, ir_graph *to)
287 ir_type *from_frame = get_irg_frame_type(from);
288 ir_type *to_frame = get_irg_frame_type(to);
289 size_t n_members = get_class_n_members(from_frame);
291 assert(from_frame != to_frame);
293 for (i = 0; i < n_members; ++i) {
294 ir_entity *old_ent = get_class_member(from_frame, i);
295 ir_entity *new_ent = copy_entity_own(old_ent, to_frame);
296 set_entity_link(old_ent, new_ent);
297 assert (!is_parameter_entity(old_ent));
301 /* Inlines a method at the given call site. */
302 int inline_method(ir_node *call, ir_graph *called_graph)
305 ir_node *post_call, *post_bl;
306 ir_node *in[pn_Start_max+1];
307 ir_node *end, *end_bl, *block;
312 int arity, n_ret, n_exc, n_res, i, j, rem_opt;
313 int irn_arity, n_params;
315 enum exc_mode exc_handling;
320 ir_graph *irg = get_irn_irg(call);
322 /* we cannot inline some types of calls */
323 if (! can_inline(call, called_graph))
326 /* We cannot inline a recursive call. The graph must be copied before
327 * the call the inline_method() using create_irg_copy(). */
328 if (called_graph == irg)
331 ent = get_irg_entity(called_graph);
332 mtp = get_entity_type(ent);
333 ctp = get_Call_type(call);
334 n_params = get_method_n_params(mtp);
335 n_res = get_method_n_ress(mtp);
337 rem = current_ir_graph;
338 current_ir_graph = irg;
340 DB((dbg, LEVEL_1, "Inlining %+F(%+F) into %+F\n", call, called_graph, irg));
342 /* optimizations can cause problems when allocating new nodes */
343 rem_opt = get_opt_optimize();
346 /* Handle graph state */
347 assert(get_irg_phase_state(irg) != phase_building);
348 assert(get_irg_pinned(irg) == op_pin_state_pinned);
349 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
350 set_irg_extblk_inconsistent(irg);
351 set_irg_doms_inconsistent(irg);
352 set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
353 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
354 edges_deactivate(irg);
356 /* here we know we WILL inline, so inform the statistics */
357 hook_inline(call, called_graph);
359 /* -- Decide how to handle exception control flow: Is there a handler
360 for the Call node, or do we branch directly to End on an exception?
362 0 There is a handler.
363 2 Exception handling not represented in Firm. -- */
365 ir_node *Xproj = NULL;
367 for (proj = (ir_node*)get_irn_link(call); proj != NULL;
368 proj = (ir_node*)get_irn_link(proj)) {
369 long proj_nr = get_Proj_proj(proj);
370 if (proj_nr == pn_Call_X_except) Xproj = proj;
372 exc_handling = Xproj != NULL ? exc_handler : exc_no_handler;
375 /* create the argument tuple */
376 args_in = ALLOCAN(ir_node*, n_params);
378 block = get_nodes_block(call);
379 for (i = n_params - 1; i >= 0; --i) {
380 ir_node *arg = get_Call_param(call, i);
381 ir_type *param_tp = get_method_param_type(mtp, i);
382 ir_mode *mode = get_type_mode(param_tp);
384 if (mode != get_irn_mode(arg)) {
385 arg = new_r_Conv(block, arg, mode);
390 /* the procedure and later replaces the Start node of the called graph.
391 * Post_call is the old Call node and collects the results of the called
392 * graph. Both will end up being a tuple. */
393 post_bl = get_nodes_block(call);
394 /* XxMxPxPxPxT of Start + parameter of Call */
395 in[pn_Start_M] = get_Call_mem(call);
396 in[pn_Start_X_initial_exec] = new_r_Jmp(post_bl);
397 in[pn_Start_P_frame_base] = get_irg_frame(irg);
398 in[pn_Start_T_args] = new_r_Tuple(post_bl, n_params, args_in);
399 pre_call = new_r_Tuple(post_bl, pn_Start_max+1, in);
403 The new block gets the ins of the old block, pre_call and all its
404 predecessors and all Phi nodes. -- */
405 part_block(pre_call);
407 /* increment visited flag for later walk */
408 inc_irg_visited(called_graph);
410 /* link some nodes to nodes in the current graph so instead of copying
411 * the linked nodes will get used.
412 * So the copier will use the created Tuple instead of copying the start
413 * node, similar for singleton nodes like NoMem and Bad.
414 * Note: this will prohibit predecessors to be copied - only do it for
415 * nodes without predecessors */
417 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 nomem = get_irg_no_mem(called_graph);
430 set_new_node(nomem, get_irg_no_mem(irg));
431 mark_irn_visited(nomem);
434 /* entitiy link is used to link entities on old stackframe to the
436 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
438 /* copy entities and nodes */
439 assert(!irn_visited(get_irg_end(called_graph)));
440 copy_frame_entities(called_graph, irg);
441 irg_walk_core(get_irg_end(called_graph), copy_node_inline, set_preds_inline,
444 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
446 /* -- Merge the end of the inlined procedure with the call site -- */
447 /* We will turn the old Call node into a Tuple with the following
450 0: Phi of all Memories of Return statements.
451 1: Jmp from new Block that merges the control flow from all exception
452 predecessors of the old end block.
453 2: Tuple of all arguments.
454 3: Phi of Exception memories.
455 In case the old Call directly branches to End on an exception we don't
456 need the block merging all exceptions nor the Phi of the exception
460 /* Precompute some values */
461 end_bl = get_new_node(get_irg_end_block(called_graph));
462 end = get_new_node(get_irg_end(called_graph));
463 arity = get_Block_n_cfgpreds(end_bl); /* arity = n_exc + n_ret */
464 n_res = get_method_n_ress(get_Call_type(call));
466 res_pred = XMALLOCN(ir_node*, n_res);
467 cf_pred = XMALLOCN(ir_node*, arity);
469 /* archive keepalives */
470 irn_arity = get_irn_arity(end);
471 for (i = 0; i < irn_arity; i++) {
472 ir_node *ka = get_End_keepalive(end, i);
474 add_End_keepalive(get_irg_end(irg), ka);
477 /* replace Return nodes by Jump nodes */
479 for (i = 0; i < arity; i++) {
481 ret = get_Block_cfgpred(end_bl, i);
482 if (is_Return(ret)) {
483 ir_node *block = get_nodes_block(ret);
484 cf_pred[n_ret] = new_r_Jmp(block);
488 set_irn_in(post_bl, n_ret, cf_pred);
490 /* build a Tuple for all results of the method.
491 * add Phi node if there was more than one Return. */
492 turn_into_tuple(post_call, pn_Call_max+1);
493 /* First the Memory-Phi */
495 for (i = 0; i < arity; i++) {
496 ret = get_Block_cfgpred(end_bl, i);
497 if (is_Return(ret)) {
498 cf_pred[n_mem_phi++] = get_Return_mem(ret);
500 /* memory output for some exceptions is directly connected to End */
502 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 3);
503 } else if (is_fragile_op(ret)) {
504 /* We rely that all cfops have the memory output at the same position. */
505 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 0);
506 } else if (is_Raise(ret)) {
507 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 1);
510 phi = new_r_Phi(post_bl, n_mem_phi, cf_pred, mode_M);
511 set_Tuple_pred(call, pn_Call_M, phi);
512 /* Conserve Phi-list for further inlinings -- but might be optimized */
513 if (get_nodes_block(phi) == post_bl) {
514 set_irn_link(phi, get_irn_link(post_bl));
515 set_irn_link(post_bl, phi);
517 /* Now the real results */
519 ir_node *result_tuple;
520 for (j = 0; j < n_res; j++) {
521 ir_type *res_type = get_method_res_type(ctp, j);
522 ir_mode *res_mode = get_type_mode(res_type);
524 for (i = 0; i < arity; i++) {
525 ret = get_Block_cfgpred(end_bl, i);
526 if (is_Return(ret)) {
527 ir_node *res = get_Return_res(ret, j);
528 if (get_irn_mode(res) != res_mode) {
529 ir_node *block = get_nodes_block(res);
530 res = new_r_Conv(block, res, res_mode);
532 cf_pred[n_ret] = res;
537 phi = new_r_Phi(post_bl, n_ret, cf_pred, res_mode);
539 phi = new_r_Bad(irg, res_mode);
542 /* Conserve Phi-list for further inlinings -- but might be optimized */
543 if (get_nodes_block(phi) == post_bl) {
544 set_Phi_next(phi, get_Block_phis(post_bl));
545 set_Block_phis(post_bl, phi);
548 result_tuple = new_r_Tuple(post_bl, n_res, res_pred);
549 set_Tuple_pred(call, pn_Call_T_result, result_tuple);
551 set_Tuple_pred(call, pn_Call_T_result, new_r_Bad(irg, mode_T));
553 /* handle the regular call */
554 set_Tuple_pred(call, pn_Call_X_regular, new_r_Jmp(post_bl));
556 /* Finally the exception control flow.
557 We have two possible situations:
558 First if the Call branches to an exception handler:
559 We need to add a Phi node to
560 collect the memory containing the exception objects. Further we need
561 to add another block to get a correct representation of this Phi. To
562 this block we add a Jmp that resolves into the X output of the Call
563 when the Call is turned into a tuple.
564 Second: There is no exception edge. Just add all inlined exception
565 branches to the End node.
567 if (exc_handling == exc_handler) {
569 for (i = 0; i < arity; i++) {
571 ret = get_Block_cfgpred(end_bl, i);
572 irn = skip_Proj(ret);
573 if (is_fragile_op(irn) || is_Raise(irn)) {
574 cf_pred[n_exc] = ret;
581 set_Tuple_pred(call, pn_Call_X_except, cf_pred[0]);
583 ir_node *block = new_r_Block(irg, n_exc, cf_pred);
584 set_Tuple_pred(call, pn_Call_X_except, new_r_Jmp(block));
587 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
590 ir_node *main_end_bl;
591 int main_end_bl_arity;
594 /* assert(exc_handling == 1 || no exceptions. ) */
596 for (i = 0; i < arity; i++) {
597 ir_node *ret = get_Block_cfgpred(end_bl, i);
598 ir_node *irn = skip_Proj(ret);
600 if (is_fragile_op(irn) || is_Raise(irn)) {
601 cf_pred[n_exc] = ret;
605 main_end_bl = get_irg_end_block(irg);
606 main_end_bl_arity = get_irn_arity(main_end_bl);
607 end_preds = XMALLOCN(ir_node*, n_exc + main_end_bl_arity);
609 for (i = 0; i < main_end_bl_arity; ++i)
610 end_preds[i] = get_irn_n(main_end_bl, i);
611 for (i = 0; i < n_exc; ++i)
612 end_preds[main_end_bl_arity + i] = cf_pred[i];
613 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
614 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
620 /* -- Turn CSE back on. -- */
621 set_optimize(rem_opt);
622 current_ir_graph = rem;
627 /********************************************************************/
628 /* Apply inlining to small methods. */
629 /********************************************************************/
631 static struct obstack temp_obst;
633 /** Represents a possible inlinable call in a graph. */
634 typedef struct call_entry {
635 ir_node *call; /**< The Call node. */
636 ir_graph *callee; /**< The callee IR-graph. */
637 list_head list; /**< List head for linking the next one. */
638 int loop_depth; /**< The loop depth of this call. */
639 int benefice; /**< The calculated benefice of this call. */
640 unsigned local_adr:1; /**< Set if this call gets an address of a local variable. */
641 unsigned all_const:1; /**< Set if this call has only constant parameters. */
645 * environment for inlining small irgs
647 typedef struct inline_env_t {
648 struct obstack obst; /**< An obstack where call_entries are allocated on. */
649 list_head calls; /**< The call entry list. */
653 * Returns the irg called from a Call node. If the irg is not
654 * known, NULL is returned.
656 * @param call the call node
658 static ir_graph *get_call_called_irg(ir_node *call)
662 addr = get_Call_ptr(call);
663 if (is_Global(addr)) {
664 ir_entity *ent = get_Global_entity(addr);
665 /* we don't know which function gets finally bound to a weak symbol */
666 if (get_entity_linkage(ent) & IR_LINKAGE_WEAK)
669 return get_entity_irg(ent);
676 * Walker: Collect all calls to known graphs inside a graph.
678 static void collect_calls(ir_node *call, void *env)
682 ir_graph *called_irg = get_call_called_irg(call);
684 if (called_irg != NULL) {
685 /* The Call node calls a locally defined method. Remember to inline. */
686 inline_env_t *ienv = (inline_env_t*)env;
687 call_entry *entry = OALLOC(&ienv->obst, call_entry);
689 entry->callee = called_irg;
690 entry->loop_depth = 0;
692 entry->local_adr = 0;
693 entry->all_const = 0;
695 list_add_tail(&entry->list, &ienv->calls);
701 * Inlines all small methods at call sites where the called address comes
702 * from a Const node that references the entity representing the called
704 * The size argument is a rough measure for the code size of the method:
705 * Methods where the obstack containing the firm graph is smaller than
708 void inline_small_irgs(ir_graph *irg, int size)
710 ir_graph *rem = current_ir_graph;
714 current_ir_graph = irg;
715 /* Handle graph state */
716 assert(get_irg_phase_state(irg) != phase_building);
717 free_callee_info(irg);
719 /* Find Call nodes to inline.
720 (We can not inline during a walk of the graph, as inlining the same
721 method several times changes the visited flag of the walked graph:
722 after the first inlining visited of the callee equals visited of
723 the caller. With the next inlining both are increased.) */
724 obstack_init(&env.obst);
725 INIT_LIST_HEAD(&env.calls);
726 irg_walk_graph(irg, NULL, collect_calls, &env);
728 if (! list_empty(&env.calls)) {
729 /* There are calls to inline */
730 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
731 collect_phiprojs(irg);
733 list_for_each_entry(call_entry, entry, &env.calls, list) {
734 ir_graph *callee = entry->callee;
735 irg_inline_property prop = get_irg_inline_property(callee);
737 if (prop == irg_inline_forbidden) {
741 if (prop >= irg_inline_forced ||
742 _obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst) < size) {
743 inline_method(entry->call, callee);
746 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
748 obstack_free(&env.obst, NULL);
749 current_ir_graph = rem;
752 typedef struct inline_small_irgs_pass_t {
753 ir_graph_pass_t pass;
755 } inline_small_irgs_pass_t;
758 * Wrapper to run inline_small_irgs() as a pass.
760 static int inline_small_irgs_wrapper(ir_graph *irg, void *context)
762 inline_small_irgs_pass_t *pass = (inline_small_irgs_pass_t*)context;
764 inline_small_irgs(irg, pass->size);
768 /* create a pass for inline_small_irgs() */
769 ir_graph_pass_t *inline_small_irgs_pass(const char *name, int size)
771 inline_small_irgs_pass_t *pass = XMALLOCZ(inline_small_irgs_pass_t);
774 return def_graph_pass_constructor(
775 &pass->pass, name ? name : "inline_small_irgs", inline_small_irgs_wrapper);
779 * Environment for inlining irgs.
782 list_head calls; /**< List of of all call nodes in this graph. */
783 unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */
784 unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
785 unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */
786 unsigned n_nodes_orig; /**< for statistics */
787 unsigned n_call_nodes; /**< Number of Call nodes in the graph. */
788 unsigned n_call_nodes_orig; /**< for statistics */
789 unsigned n_callers; /**< Number of known graphs that call this graphs. */
790 unsigned n_callers_orig; /**< for statistics */
791 unsigned got_inline:1; /**< Set, if at least one call inside this graph was inlined. */
792 unsigned recursive:1; /**< Set, if this function is self recursive. */
796 * Allocate a new environment for inlining.
798 static inline_irg_env *alloc_inline_irg_env(void)
800 inline_irg_env *env = OALLOC(&temp_obst, inline_irg_env);
801 INIT_LIST_HEAD(&env->calls);
802 env->local_weights = NULL;
803 env->n_nodes = -2; /* do not count count Start, End */
804 env->n_blocks = -2; /* do not count count Start, End Block */
805 env->n_nodes_orig = -2; /* do not count Start, End */
806 env->n_call_nodes = 0;
807 env->n_call_nodes_orig = 0;
809 env->n_callers_orig = 0;
815 typedef struct walker_env {
816 inline_irg_env *x; /**< the inline environment */
817 char ignore_runtime; /**< the ignore runtime flag */
818 char ignore_callers; /**< if set, do change callers data */
822 * post-walker: collect all calls in the inline-environment
823 * of a graph and sum some statistics.
825 static void collect_calls2(ir_node *call, void *ctx)
827 wenv_t *env = (wenv_t*)ctx;
828 inline_irg_env *x = env->x;
829 unsigned code = get_irn_opcode(call);
833 /* count meaningful nodes in irg */
834 if (code != iro_Proj && code != iro_Tuple && code != iro_Sync) {
835 if (code != iro_Block) {
843 if (code != iro_Call) return;
845 /* check, if it's a runtime call */
846 if (env->ignore_runtime) {
847 ir_node *symc = get_Call_ptr(call);
849 if (is_Global(symc)) {
850 ir_entity *ent = get_Global_entity(symc);
852 if (get_entity_additional_properties(ent) & mtp_property_runtime)
857 /* collect all call nodes */
859 ++x->n_call_nodes_orig;
861 callee = get_call_called_irg(call);
862 if (callee != NULL) {
863 if (! env->ignore_callers) {
864 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
865 /* count all static callers */
866 ++callee_env->n_callers;
867 ++callee_env->n_callers_orig;
869 if (callee == current_ir_graph)
872 /* link it in the list of possible inlinable entries */
873 entry = OALLOC(&temp_obst, call_entry);
875 entry->callee = callee;
876 entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth;
878 entry->local_adr = 0;
879 entry->all_const = 0;
881 list_add_tail(&entry->list, &x->calls);
886 * Returns TRUE if the number of callers is 0 in the irg's environment,
887 * hence this irg is a leave.
889 inline static int is_leave(ir_graph *irg)
891 inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
892 return env->n_call_nodes == 0;
896 * Returns TRUE if the number of nodes in the callee is
897 * smaller then size in the irg's environment.
899 inline static int is_smaller(ir_graph *callee, unsigned size)
901 inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
902 return env->n_nodes < size;
906 * Duplicate a call entry.
908 * @param entry the original entry to duplicate
909 * @param new_call the new call node
910 * @param loop_depth_delta
911 * delta value for the loop depth
913 static call_entry *duplicate_call_entry(const call_entry *entry,
914 ir_node *new_call, int loop_depth_delta)
916 call_entry *nentry = OALLOC(&temp_obst, call_entry);
917 nentry->call = new_call;
918 nentry->callee = entry->callee;
919 nentry->benefice = entry->benefice;
920 nentry->loop_depth = entry->loop_depth + loop_depth_delta;
921 nentry->local_adr = entry->local_adr;
922 nentry->all_const = entry->all_const;
928 * Append all call nodes of the source environment to the nodes of in the destination
931 * @param dst destination environment
932 * @param src source environment
933 * @param loop_depth the loop depth of the call that is replaced by the src list
935 static void append_call_list(inline_irg_env *dst, inline_irg_env *src, int loop_depth)
937 call_entry *entry, *nentry;
939 /* Note that the src list points to Call nodes in the inlined graph, but
940 we need Call nodes in our graph. Luckily the inliner leaves this information
941 in the link field. */
942 list_for_each_entry(call_entry, entry, &src->calls, list) {
943 nentry = duplicate_call_entry(entry, (ir_node*)get_irn_link(entry->call), loop_depth);
944 list_add_tail(&nentry->list, &dst->calls);
946 dst->n_call_nodes += src->n_call_nodes;
947 dst->n_nodes += src->n_nodes;
951 * Inlines small leave methods at call sites where the called address comes
952 * from a Const node that references the entity representing the called
954 * The size argument is a rough measure for the code size of the method:
955 * Methods where the obstack containing the firm graph is smaller than
958 void inline_leave_functions(unsigned maxsize, unsigned leavesize,
959 unsigned size, int ignore_runtime)
967 call_entry *entry, *next;
968 const call_entry *centry;
970 pmap_entry *pm_entry;
972 rem = current_ir_graph;
973 obstack_init(&temp_obst);
975 /* a map for the copied graphs, used to inline recursive calls */
976 copied_graphs = pmap_create();
978 /* extend all irgs by a temporary data structure for inlining. */
979 n_irgs = get_irp_n_irgs();
980 for (i = 0; i < n_irgs; ++i)
981 set_irg_link(get_irp_irg(i), alloc_inline_irg_env());
983 /* Pre-compute information in temporary data structure. */
984 wenv.ignore_runtime = ignore_runtime;
985 wenv.ignore_callers = 0;
986 for (i = 0; i < n_irgs; ++i) {
987 ir_graph *irg = get_irp_irg(i);
989 assert(get_irg_phase_state(irg) != phase_building);
990 free_callee_info(irg);
993 wenv.x = (inline_irg_env*)get_irg_link(irg);
994 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
997 /* -- and now inline. -- */
999 /* Inline leaves recursively -- we might construct new leaves. */
1003 for (i = 0; i < n_irgs; ++i) {
1005 int phiproj_computed = 0;
1007 current_ir_graph = get_irp_irg(i);
1008 env = (inline_irg_env*)get_irg_link(current_ir_graph);
1010 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1011 list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
1013 irg_inline_property prop;
1015 if (env->n_nodes > maxsize)
1019 callee = entry->callee;
1021 prop = get_irg_inline_property(callee);
1022 if (prop == irg_inline_forbidden) {
1026 if (is_leave(callee) && (
1027 is_smaller(callee, leavesize) || prop >= irg_inline_forced)) {
1028 if (!phiproj_computed) {
1029 phiproj_computed = 1;
1030 collect_phiprojs(current_ir_graph);
1032 did_inline = inline_method(call, callee);
1035 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1037 /* call was inlined, Phi/Projs for current graph must be recomputed */
1038 phiproj_computed = 0;
1040 /* Do some statistics */
1041 env->got_inline = 1;
1042 --env->n_call_nodes;
1043 env->n_nodes += callee_env->n_nodes;
1044 --callee_env->n_callers;
1046 /* remove this call from the list */
1047 list_del(&entry->list);
1052 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1054 } while (did_inline);
1056 /* inline other small functions. */
1057 for (i = 0; i < n_irgs; ++i) {
1059 int phiproj_computed = 0;
1061 current_ir_graph = get_irp_irg(i);
1062 env = (inline_irg_env*)get_irg_link(current_ir_graph);
1064 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1066 /* note that the list of possible calls is updated during the process */
1067 list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
1068 irg_inline_property prop;
1073 callee = entry->callee;
1075 prop = get_irg_inline_property(callee);
1076 if (prop == irg_inline_forbidden) {
1080 e = pmap_find(copied_graphs, callee);
1083 * Remap callee if we have a copy.
1084 * FIXME: Should we do this only for recursive Calls ?
1086 callee = (ir_graph*)e->value;
1089 if (prop >= irg_inline_forced ||
1090 (is_smaller(callee, size) && env->n_nodes < maxsize) /* small function */) {
1091 if (current_ir_graph == callee) {
1093 * Recursive call: we cannot directly inline because we cannot walk
1094 * the graph and change it. So we have to make a copy of the graph
1098 inline_irg_env *callee_env;
1101 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1104 * No copy yet, create one.
1105 * Note that recursive methods are never leaves, so it is sufficient
1106 * to test this condition here.
1108 copy = create_irg_copy(callee);
1110 /* create_irg_copy() destroys the Proj links, recompute them */
1111 phiproj_computed = 0;
1113 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1115 /* allocate new environment */
1116 callee_env = alloc_inline_irg_env();
1117 set_irg_link(copy, callee_env);
1119 assure_cf_loop(copy);
1120 wenv.x = callee_env;
1121 wenv.ignore_callers = 1;
1122 irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1125 * Enter the entity of the original graph. This is needed
1126 * for inline_method(). However, note that ent->irg still points
1127 * to callee, NOT to copy.
1129 set_irg_entity(copy, get_irg_entity(callee));
1131 pmap_insert(copied_graphs, callee, copy);
1134 /* we have only one caller: the original graph */
1135 callee_env->n_callers = 1;
1136 callee_env->n_callers_orig = 1;
1138 if (! phiproj_computed) {
1139 phiproj_computed = 1;
1140 collect_phiprojs(current_ir_graph);
1142 did_inline = inline_method(call, callee);
1144 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1146 /* call was inlined, Phi/Projs for current graph must be recomputed */
1147 phiproj_computed = 0;
1149 /* callee was inline. Append its call list. */
1150 env->got_inline = 1;
1151 --env->n_call_nodes;
1152 append_call_list(env, callee_env, entry->loop_depth);
1153 --callee_env->n_callers;
1155 /* after we have inlined callee, all called methods inside callee
1156 are now called once more */
1157 list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1158 inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1162 /* remove this call from the list */
1163 list_del(&entry->list);
1168 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1171 for (i = 0; i < n_irgs; ++i) {
1172 irg = get_irp_irg(i);
1173 env = (inline_irg_env*)get_irg_link(irg);
1175 if (env->got_inline) {
1176 optimize_graph_df(irg);
1179 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1180 DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1181 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1182 env->n_callers_orig, env->n_callers,
1183 get_entity_name(get_irg_entity(irg))));
1187 /* kill the copied graphs: we don't need them anymore */
1188 foreach_pmap(copied_graphs, pm_entry) {
1189 ir_graph *copy = (ir_graph*)pm_entry->value;
1191 /* reset the entity, otherwise it will be deleted in the next step ... */
1192 set_irg_entity(copy, NULL);
1193 free_ir_graph(copy);
1195 pmap_destroy(copied_graphs);
1197 obstack_free(&temp_obst, NULL);
1198 current_ir_graph = rem;
1201 typedef struct inline_leave_functions_pass_t {
1202 ir_prog_pass_t pass;
1207 } inline_leave_functions_pass_t;
1210 * Wrapper to run inline_leave_functions() as a ir_prog pass.
1212 static int inline_leave_functions_wrapper(ir_prog *irp, void *context)
1214 inline_leave_functions_pass_t *pass = (inline_leave_functions_pass_t*)context;
1217 inline_leave_functions(
1218 pass->maxsize, pass->leavesize,
1219 pass->size, pass->ignore_runtime);
1223 /* create a pass for inline_leave_functions() */
1224 ir_prog_pass_t *inline_leave_functions_pass(
1225 const char *name, unsigned maxsize, unsigned leavesize,
1226 unsigned size, int ignore_runtime)
1228 inline_leave_functions_pass_t *pass = XMALLOCZ(inline_leave_functions_pass_t);
1230 pass->maxsize = maxsize;
1231 pass->leavesize = leavesize;
1233 pass->ignore_runtime = ignore_runtime;
1235 return def_prog_pass_constructor(
1237 name ? name : "inline_leave_functions",
1238 inline_leave_functions_wrapper);
1242 * Calculate the parameter weights for transmitting the address of a local variable.
1244 static unsigned calc_method_local_weight(ir_node *arg)
1247 unsigned v, weight = 0;
1249 for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
1250 ir_node *succ = get_irn_out(arg, i);
1252 switch (get_irn_opcode(succ)) {
1255 /* Loads and Store can be removed */
1259 /* check if all args are constant */
1260 for (j = get_Sel_n_indexs(succ) - 1; j >= 0; --j) {
1261 ir_node *idx = get_Sel_index(succ, j);
1262 if (! is_Const(idx))
1265 /* Check users on this Sel. Note: if a 0 is returned here, there was
1266 some unsupported node. */
1267 v = calc_method_local_weight(succ);
1270 /* we can kill one Sel with constant indexes, this is cheap */
1274 /* when looking backward we might find Id nodes */
1275 weight += calc_method_local_weight(succ);
1278 /* unoptimized tuple */
1279 for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
1280 ir_node *pred = get_Tuple_pred(succ, j);
1282 /* look for Proj(j) */
1283 for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
1284 ir_node *succ_succ = get_irn_out(succ, k);
1285 if (is_Proj(succ_succ)) {
1286 if (get_Proj_proj(succ_succ) == j) {
1288 weight += calc_method_local_weight(succ_succ);
1291 /* this should NOT happen */
1299 /* any other node: unsupported yet or bad. */
1307 * Calculate the parameter weights for transmitting the address of a local variable.
1309 static void analyze_irg_local_weights(inline_irg_env *env, ir_graph *irg)
1311 ir_entity *ent = get_irg_entity(irg);
1316 ir_node *irg_args, *arg;
1318 mtp = get_entity_type(ent);
1319 nparams = get_method_n_params(mtp);
1321 /* allocate a new array. currently used as 'analysed' flag */
1322 env->local_weights = NEW_ARR_D(unsigned, &temp_obst, nparams);
1324 /* If the method haven't parameters we have nothing to do. */
1328 assure_irg_outs(irg);
1329 irg_args = get_irg_args(irg);
1330 for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
1331 arg = get_irn_out(irg_args, i);
1332 proj_nr = get_Proj_proj(arg);
1333 env->local_weights[proj_nr] = calc_method_local_weight(arg);
1338 * Calculate the benefice for transmitting an local variable address.
1339 * After inlining, the local variable might be transformed into a
1340 * SSA variable by scalar_replacement().
1342 static unsigned get_method_local_adress_weight(ir_graph *callee, size_t pos)
1344 inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
1346 if (env->local_weights == NULL)
1347 analyze_irg_local_weights(env, callee);
1349 if (pos < ARR_LEN(env->local_weights))
1350 return env->local_weights[pos];
1355 * Calculate a benefice value for inlining the given call.
1357 * @param call the call node we have to inspect
1358 * @param callee the called graph
1360 static int calc_inline_benefice(call_entry *entry, ir_graph *callee)
1362 ir_node *call = entry->call;
1363 ir_entity *ent = get_irg_entity(callee);
1364 ir_type *callee_frame;
1365 size_t i, n_members, n_params;
1371 irg_inline_property prop;
1373 inline_irg_env *callee_env;
1375 prop = get_irg_inline_property(callee);
1376 if (prop == irg_inline_forbidden) {
1377 DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n",
1379 return entry->benefice = INT_MIN;
1382 callee_frame = get_irg_frame_type(callee);
1383 n_members = get_class_n_members(callee_frame);
1384 for (i = 0; i < n_members; ++i) {
1385 ir_entity *frame_ent = get_class_member(callee_frame, i);
1386 if (is_parameter_entity(frame_ent)) {
1387 // TODO inliner should handle parameter entities by inserting Store operations
1388 DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden due to parameter entity\n", call, callee));
1389 set_irg_inline_property(callee, irg_inline_forbidden);
1390 return entry->benefice = INT_MIN;
1394 if (get_irg_additional_properties(callee) & mtp_property_noreturn) {
1395 DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n",
1397 return entry->benefice = INT_MIN;
1400 /* costs for every passed parameter */
1401 n_params = get_Call_n_params(call);
1402 mtp = get_entity_type(ent);
1403 cc = get_method_calling_convention(mtp);
1404 if (cc & cc_reg_param) {
1405 /* register parameter, smaller costs for register parameters */
1406 size_t max_regs = cc & ~cc_bits;
1408 if (max_regs < n_params)
1409 weight += max_regs * 2 + (n_params - max_regs) * 5;
1411 weight += n_params * 2;
1413 /* parameters are passed an stack */
1414 weight += 5 * n_params;
1417 /* constant parameters improve the benefice */
1418 frame_ptr = get_irg_frame(current_ir_graph);
1420 for (i = 0; i < n_params; ++i) {
1421 ir_node *param = get_Call_param(call, i);
1423 if (is_Const(param)) {
1424 weight += get_method_param_weight(ent, i);
1427 if (is_SymConst(param))
1428 weight += get_method_param_weight(ent, i);
1429 else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr) {
1431 * An address of a local variable is transmitted. After
1432 * inlining, scalar_replacement might be able to remove the
1433 * local variable, so honor this.
1435 v = get_method_local_adress_weight(callee, i);
1438 entry->local_adr = 1;
1442 entry->all_const = all_const;
1444 callee_env = (inline_irg_env*)get_irg_link(callee);
1445 if (callee_env->n_callers == 1 &&
1446 callee != current_ir_graph &&
1447 !entity_is_externally_visible(ent)) {
1451 /* give a bonus for functions with one block */
1452 if (callee_env->n_blocks == 1)
1453 weight = weight * 3 / 2;
1455 /* and one for small non-recursive functions: we want them to be inlined in mostly every case */
1456 if (callee_env->n_nodes < 30 && !callee_env->recursive)
1459 /* and finally for leaves: they do not increase the register pressure
1460 because of callee safe registers */
1461 if (callee_env->n_call_nodes == 0)
1464 /** it's important to inline inner loops first */
1465 if (entry->loop_depth > 30)
1466 weight += 30 * 1024;
1468 weight += entry->loop_depth * 1024;
1471 * All arguments constant is probably a good sign, give an extra bonus
1476 return entry->benefice = weight;
1479 typedef struct walk_env_t {
1485 * Callgraph walker, collect all visited graphs.
1487 static void callgraph_walker(ir_graph *irg, void *data)
1489 walk_env_t *env = (walk_env_t *)data;
1490 env->irgs[env->last_irg++] = irg;
1494 * Creates an inline order for all graphs.
1496 * @return the list of graphs.
1498 static ir_graph **create_irg_list(void)
1500 ir_entity **free_methods;
1501 size_t n_irgs = get_irp_n_irgs();
1504 cgana(&free_methods);
1505 xfree(free_methods);
1507 compute_callgraph();
1509 env.irgs = XMALLOCNZ(ir_graph*, n_irgs);
1512 callgraph_walk(NULL, callgraph_walker, &env);
1513 assert(n_irgs == env.last_irg);
1519 * Push a call onto the priority list if its benefice is big enough.
1521 * @param pqueue the priority queue of calls
1522 * @param call the call entry
1523 * @param inlien_threshold
1524 * the threshold value
1526 static void maybe_push_call(pqueue_t *pqueue, call_entry *call,
1527 int inline_threshold)
1529 ir_graph *callee = call->callee;
1530 irg_inline_property prop = get_irg_inline_property(callee);
1531 int benefice = calc_inline_benefice(call, callee);
1533 DB((dbg, LEVEL_2, "In %+F Call %+F to %+F has benefice %d\n",
1534 get_irn_irg(call->call), call->call, callee, benefice));
1536 if (prop < irg_inline_forced && benefice < inline_threshold) {
1540 pqueue_put(pqueue, call, benefice);
1544 * Try to inline calls into a graph.
1546 * @param irg the graph into which we inline
1547 * @param maxsize do NOT inline if the size of irg gets
1548 * bigger than this amount
1549 * @param inline_threshold
1550 * threshold value for inline decision
1551 * @param copied_graphs
1552 * map containing copied of recursive graphs
1554 static void inline_into(ir_graph *irg, unsigned maxsize,
1555 int inline_threshold, pmap *copied_graphs)
1557 int phiproj_computed = 0;
1558 inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
1559 call_entry *curr_call;
1563 if (env->n_call_nodes == 0)
1566 if (env->n_nodes > maxsize) {
1567 DB((dbg, LEVEL_2, "%+F: too big (%d)\n", irg, env->n_nodes));
1571 current_ir_graph = irg;
1572 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1574 /* put irgs into the pqueue */
1575 pqueue = new_pqueue();
1577 list_for_each_entry(call_entry, curr_call, &env->calls, list) {
1578 assert(is_Call(curr_call->call));
1579 maybe_push_call(pqueue, curr_call, inline_threshold);
1582 /* note that the list of possible calls is updated during the process */
1583 while (!pqueue_empty(pqueue)) {
1585 call_entry *curr_call = (call_entry*)pqueue_pop_front(pqueue);
1586 ir_graph *callee = curr_call->callee;
1587 ir_node *call_node = curr_call->call;
1588 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1589 irg_inline_property prop = get_irg_inline_property(callee);
1591 const call_entry *centry;
1594 if ((prop < irg_inline_forced) && env->n_nodes + callee_env->n_nodes > maxsize) {
1595 DB((dbg, LEVEL_2, "%+F: too big (%d) + %+F (%d)\n", irg,
1596 env->n_nodes, callee, callee_env->n_nodes));
1600 e = pmap_find(copied_graphs, callee);
1602 int benefice = curr_call->benefice;
1604 * Reduce the weight for recursive function IFF not all arguments are const.
1605 * inlining recursive functions is rarely good.
1607 if (!curr_call->all_const)
1609 if (benefice < inline_threshold)
1613 * Remap callee if we have a copy.
1615 callee = (ir_graph*)e->value;
1616 callee_env = (inline_irg_env*)get_irg_link(callee);
1619 if (current_ir_graph == callee) {
1621 * Recursive call: we cannot directly inline because we cannot
1622 * walk the graph and change it. So we have to make a copy of
1625 int benefice = curr_call->benefice;
1629 * Reduce the weight for recursive function IFF not all arguments are const.
1630 * inlining recursive functions is rarely good.
1632 if (!curr_call->all_const)
1634 if (benefice < inline_threshold)
1637 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1640 * No copy yet, create one.
1641 * Note that recursive methods are never leaves, so it is
1642 * sufficient to test this condition here.
1644 copy = create_irg_copy(callee);
1646 /* create_irg_copy() destroys the Proj links, recompute them */
1647 phiproj_computed = 0;
1649 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1651 /* allocate a new environment */
1652 callee_env = alloc_inline_irg_env();
1653 set_irg_link(copy, callee_env);
1655 assure_cf_loop(copy);
1656 memset(&wenv, 0, sizeof(wenv));
1657 wenv.x = callee_env;
1658 wenv.ignore_callers = 1;
1659 irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1662 * Enter the entity of the original graph. This is needed
1663 * for inline_method(). However, note that ent->irg still points
1664 * to callee, NOT to copy.
1666 set_irg_entity(copy, get_irg_entity(callee));
1668 pmap_insert(copied_graphs, callee, copy);
1671 /* we have only one caller: the original graph */
1672 callee_env->n_callers = 1;
1673 callee_env->n_callers_orig = 1;
1675 if (! phiproj_computed) {
1676 phiproj_computed = 1;
1677 collect_phiprojs(current_ir_graph);
1679 did_inline = inline_method(call_node, callee);
1683 /* call was inlined, Phi/Projs for current graph must be recomputed */
1684 phiproj_computed = 0;
1686 /* remove it from the caller list */
1687 list_del(&curr_call->list);
1689 /* callee was inline. Append its call list. */
1690 env->got_inline = 1;
1691 --env->n_call_nodes;
1693 /* we just generate a bunch of new calls */
1694 loop_depth = curr_call->loop_depth;
1695 list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1696 inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1698 call_entry *new_entry;
1700 /* after we have inlined callee, all called methods inside
1701 * callee are now called once more */
1704 /* Note that the src list points to Call nodes in the inlined graph,
1705 * but we need Call nodes in our graph. Luckily the inliner leaves
1706 * this information in the link field. */
1707 new_call = (ir_node*)get_irn_link(centry->call);
1708 if (get_irn_irg(new_call) != irg) {
1709 /* centry->call has not been copied, which means it is dead.
1710 * This might happen during inlining, if a const function,
1711 * which cannot be inlined is only used as an unused argument
1712 * of another function, which is inlined. */
1715 assert(is_Call(new_call));
1717 new_entry = duplicate_call_entry(centry, new_call, loop_depth);
1718 list_add_tail(&new_entry->list, &env->calls);
1719 maybe_push_call(pqueue, new_entry, inline_threshold);
1722 env->n_call_nodes += callee_env->n_call_nodes;
1723 env->n_nodes += callee_env->n_nodes;
1724 --callee_env->n_callers;
1726 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1731 * Heuristic inliner. Calculates a benefice value for every call and inlines
1732 * those calls with a value higher than the threshold.
1734 void inline_functions(unsigned maxsize, int inline_threshold,
1735 opt_ptr after_inline_opt)
1737 inline_irg_env *env;
1741 pmap *copied_graphs;
1742 pmap_entry *pm_entry;
1745 rem = current_ir_graph;
1746 obstack_init(&temp_obst);
1748 irgs = create_irg_list();
1750 /* a map for the copied graphs, used to inline recursive calls */
1751 copied_graphs = pmap_create();
1753 /* extend all irgs by a temporary data structure for inlining. */
1754 n_irgs = get_irp_n_irgs();
1755 for (i = 0; i < n_irgs; ++i)
1756 set_irg_link(irgs[i], alloc_inline_irg_env());
1758 /* Pre-compute information in temporary data structure. */
1759 wenv.ignore_runtime = 0;
1760 wenv.ignore_callers = 0;
1761 for (i = 0; i < n_irgs; ++i) {
1762 ir_graph *irg = irgs[i];
1764 free_callee_info(irg);
1766 wenv.x = (inline_irg_env*)get_irg_link(irg);
1767 assure_cf_loop(irg);
1768 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1771 /* -- and now inline. -- */
1772 for (i = 0; i < n_irgs; ++i) {
1773 ir_graph *irg = irgs[i];
1775 inline_into(irg, maxsize, inline_threshold, copied_graphs);
1778 for (i = 0; i < n_irgs; ++i) {
1779 ir_graph *irg = irgs[i];
1781 env = (inline_irg_env*)get_irg_link(irg);
1782 if (env->got_inline && after_inline_opt != NULL) {
1783 /* this irg got calls inlined: optimize it */
1784 after_inline_opt(irg);
1786 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1787 DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1788 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1789 env->n_callers_orig, env->n_callers,
1790 get_entity_name(get_irg_entity(irg))));
1794 /* kill the copied graphs: we don't need them anymore */
1795 foreach_pmap(copied_graphs, pm_entry) {
1796 ir_graph *copy = (ir_graph*)pm_entry->value;
1798 /* reset the entity, otherwise it will be deleted in the next step ... */
1799 set_irg_entity(copy, NULL);
1800 free_ir_graph(copy);
1802 pmap_destroy(copied_graphs);
1806 obstack_free(&temp_obst, NULL);
1807 current_ir_graph = rem;
1810 typedef struct inline_functions_pass_t {
1811 ir_prog_pass_t pass;
1813 int inline_threshold;
1814 opt_ptr after_inline_opt;
1815 } inline_functions_pass_t;
1818 * Wrapper to run inline_functions() as a ir_prog pass.
1820 static int inline_functions_wrapper(ir_prog *irp, void *context)
1822 inline_functions_pass_t *pass = (inline_functions_pass_t*)context;
1825 inline_functions(pass->maxsize, pass->inline_threshold,
1826 pass->after_inline_opt);
1830 /* create a ir_prog pass for inline_functions */
1831 ir_prog_pass_t *inline_functions_pass(
1832 const char *name, unsigned maxsize, int inline_threshold,
1833 opt_ptr after_inline_opt)
1835 inline_functions_pass_t *pass = XMALLOCZ(inline_functions_pass_t);
1837 pass->maxsize = maxsize;
1838 pass->inline_threshold = inline_threshold;
1839 pass->after_inline_opt = after_inline_opt;
1841 return def_prog_pass_constructor(
1842 &pass->pass, name ? name : "inline_functions",
1843 inline_functions_wrapper);
1846 void firm_init_inline(void)
1848 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");