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
32 #include "irgraph_t.h"
35 #include "iroptimize.h"
52 #include "irbackedge_t.h"
58 #include "analyze_irg_args.h"
59 #include "iredges_t.h"
63 #include "iropt_dbg.h"
65 #include "irnodemap.h"
67 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
69 /*------------------------------------------------------------------*/
70 /* Routines for dead node elimination / copying garbage collection */
72 /*------------------------------------------------------------------*/
75 * Remember the new node in the old node by using a field all nodes have.
77 static void set_new_node(ir_node *node, ir_node *new_node)
79 set_irn_link(node, new_node);
83 * Get this new node, before the old node is forgotten.
85 static inline ir_node *get_new_node(ir_node *old_node)
87 assert(irn_visited(old_node));
88 return (ir_node*) get_irn_link(old_node);
91 /*--------------------------------------------------------------------*/
92 /* Functionality for inlining */
93 /*--------------------------------------------------------------------*/
96 * Copy node for inlineing. Updates attributes that change when
97 * inlineing but not for dead node elimination.
99 * Copies the node by calling copy_node() and then updates the entity if
100 * it's a local one. env must be a pointer of the frame type of the
101 * inlined procedure. The new entities must be in the link field of
104 static void copy_node_inline(ir_node *node, void *env)
106 ir_graph *new_irg = (ir_graph*) env;
107 ir_node *new_node = irn_copy_into_irg(node, new_irg);
109 set_new_node(node, new_node);
111 ir_graph *old_irg = get_irn_irg(node);
112 ir_type *old_frame_type = get_irg_frame_type(old_irg);
113 ir_entity *old_entity = get_Sel_entity(node);
114 assert(is_Sel(new_node));
115 /* use copied entities from the new frame */
116 if (get_entity_owner(old_entity) == old_frame_type) {
117 ir_entity *new_entity = (ir_entity*)get_entity_link(old_entity);
118 assert(new_entity != NULL);
119 set_Sel_entity(new_node, new_entity);
121 } else if (is_Block(new_node)) {
122 new_node->attr.block.irg.irg = new_irg;
126 static void set_preds_inline(ir_node *node, void *env)
130 irn_rewire_inputs(node);
132 /* move constants into start block */
133 new_node = get_new_node(node);
134 if (is_irn_constlike(new_node)) {
135 ir_graph *new_irg = (ir_graph *) env;
136 ir_node *start_block = get_irg_start_block(new_irg);
137 set_nodes_block(new_node, start_block);
142 * Walker: checks if P_value_arg_base is used.
144 static void find_addr(ir_node *node, void *env)
146 bool *allow_inline = (bool*)env;
148 if (is_Block(node) && get_Block_entity(node)) {
150 * Currently we can't handle blocks whose address was taken correctly
153 *allow_inline = false;
154 } else if (is_Sel(node)) {
155 ir_graph *irg = current_ir_graph;
156 if (get_Sel_ptr(node) == get_irg_frame(irg)) {
157 /* access to frame */
158 ir_entity *ent = get_Sel_entity(node);
159 if (get_entity_owner(ent) != get_irg_frame_type(irg)) {
160 /* access to value_type */
161 *allow_inline = false;
163 if (is_parameter_entity(ent)) {
164 *allow_inline = false;
167 } else if (is_Alloc(node) && get_Alloc_where(node) == stack_alloc) {
169 * Refuse to inline alloca call unless user explicitly forced so as this
170 * may change program's memory overhead drastically when the function
171 * using alloca is called in loop. In GCC present in SPEC2000 inlining
172 * into schedule_block cause it to require 2GB of ram instead of 256MB.
174 * Sorrily this is true with our implementation also.
175 * Moreover, we cannot differentiate between alloca() and VLA yet, so
176 * this disables inlining of functions using VLA (which are completely
180 * - add a flag to the Alloc node for "real" alloca() calls
181 * - add a new Stack-Restore node at the end of a function using
184 *allow_inline = false;
189 * Check if we can inline a given call.
190 * Currently, we cannot inline two cases:
191 * - call with compound arguments
192 * - graphs that take the address of a parameter
194 * check these conditions here
196 static bool can_inline(ir_node *call, ir_graph *called_graph)
198 ir_entity *called = get_irg_entity(called_graph);
199 ir_type *called_type = get_entity_type(called);
200 ir_type *call_type = get_Call_type(call);
201 size_t n_params = get_method_n_params(called_type);
202 size_t n_arguments = get_method_n_params(call_type);
203 size_t n_res = get_method_n_ress(called_type);
204 irg_inline_property prop = get_irg_inline_property(called_graph);
208 if (prop == irg_inline_forbidden)
211 if (n_arguments != n_params) {
212 /* this is a bad feature of C: without a prototype, we can
213 * call a function with less parameters than needed. Currently
214 * we don't support this, although we could use Unknown than. */
217 if (n_res != get_method_n_ress(call_type)) {
221 /* Argh, compiling C has some bad consequences:
222 * It is implementation dependent what happens in that case.
223 * We support inlining, if the bitsize of the types matches AND
224 * the same arithmetic is used. */
225 for (i = 0; i < n_params; ++i) {
226 ir_type *param_tp = get_method_param_type(called_type, i);
227 ir_type *arg_tp = get_method_param_type(call_type, i);
229 if (param_tp != arg_tp) {
230 ir_mode *pmode = get_type_mode(param_tp);
231 ir_mode *amode = get_type_mode(arg_tp);
233 if (pmode == NULL || amode == NULL)
235 if (get_mode_size_bits(pmode) != get_mode_size_bits(amode))
237 if (get_mode_arithmetic(pmode) != get_mode_arithmetic(amode))
239 /* otherwise we can simply "reinterpret" the bits */
242 for (i = 0; i < n_res; ++i) {
243 ir_type *decl_res_tp = get_method_res_type(called_type, i);
244 ir_type *used_res_tp = get_method_res_type(call_type, i);
246 if (decl_res_tp != used_res_tp) {
247 ir_mode *decl_mode = get_type_mode(decl_res_tp);
248 ir_mode *used_mode = get_type_mode(used_res_tp);
249 if (decl_mode == NULL || used_mode == NULL)
251 if (get_mode_size_bits(decl_mode) != get_mode_size_bits(used_mode))
253 if (get_mode_arithmetic(decl_mode) != get_mode_arithmetic(used_mode))
255 /* otherwise we can "reinterpret" the bits */
259 /* check parameters for compound arguments */
260 for (i = 0; i < n_params; ++i) {
261 ir_type *p_type = get_method_param_type(call_type, i);
263 if (is_compound_type(p_type))
267 /* check results for compound arguments */
268 for (i = 0; i < n_res; ++i) {
269 ir_type *r_type = get_method_res_type(call_type, i);
271 if (is_compound_type(r_type))
276 irg_walk_graph(called_graph, find_addr, NULL, &res);
282 exc_handler, /**< There is a handler. */
283 exc_no_handler /**< Exception handling not represented. */
287 * copy all entities on the stack frame on 1 irg to the stackframe of another.
288 * Sets entity links of the old entities to the copies
290 static void copy_frame_entities(ir_graph *from, ir_graph *to)
292 ir_type *from_frame = get_irg_frame_type(from);
293 ir_type *to_frame = get_irg_frame_type(to);
294 size_t n_members = get_class_n_members(from_frame);
296 assert(from_frame != to_frame);
298 for (i = 0; i < n_members; ++i) {
299 ir_entity *old_ent = get_class_member(from_frame, i);
300 ir_entity *new_ent = copy_entity_own(old_ent, to_frame);
301 set_entity_link(old_ent, new_ent);
302 assert (!is_parameter_entity(old_ent));
306 /* Inlines a method at the given call site. */
307 int inline_method(ir_node *call, ir_graph *called_graph)
309 /* we cannot inline some types of calls */
310 if (! can_inline(call, called_graph))
313 /* We cannot inline a recursive call. The graph must be copied before
314 * the call the inline_method() using create_irg_copy(). */
315 ir_graph *irg = get_irn_irg(call);
316 if (called_graph == irg)
319 ir_entity *ent = get_irg_entity(called_graph);
320 ir_type *mtp = get_entity_type(ent);
321 ir_type *ctp = get_Call_type(call);
322 int n_params = get_method_n_params(mtp);
324 ir_graph *rem = current_ir_graph;
325 current_ir_graph = irg;
327 DB((dbg, LEVEL_1, "Inlining %+F(%+F) into %+F\n", call, called_graph, irg));
329 /* optimizations can cause problems when allocating new nodes */
330 int rem_opt = get_opt_optimize();
333 /* Handle graph state */
334 assert(get_irg_phase_state(irg) != phase_building);
335 assert(get_irg_pinned(irg) == op_pin_state_pinned);
336 assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
337 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
338 | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
339 set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
340 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
341 edges_deactivate(irg);
343 /* here we know we WILL inline, so inform the statistics */
344 hook_inline(call, called_graph);
346 /* -- Decide how to handle exception control flow: Is there a handler
347 for the Call node, or do we branch directly to End on an exception?
349 0 There is a handler.
350 2 Exception handling not represented in Firm. -- */
351 ir_node *Xproj = NULL;
352 for (ir_node *proj = (ir_node*)get_irn_link(call); proj != NULL;
353 proj = (ir_node*)get_irn_link(proj)) {
354 long proj_nr = get_Proj_proj(proj);
355 if (proj_nr == pn_Call_X_except) Xproj = proj;
357 enum exc_mode exc_handling = Xproj != NULL ? exc_handler : exc_no_handler;
359 /* create the argument tuple */
360 ir_node **args_in = ALLOCAN(ir_node*, n_params);
362 ir_node *block = get_nodes_block(call);
363 for (int i = n_params - 1; i >= 0; --i) {
364 ir_node *arg = get_Call_param(call, i);
365 ir_type *param_tp = get_method_param_type(mtp, i);
366 ir_mode *mode = get_type_mode(param_tp);
368 if (mode != get_irn_mode(arg)) {
369 arg = new_r_Conv(block, arg, mode);
374 /* the procedure and later replaces the Start node of the called graph.
375 * Post_call is the old Call node and collects the results of the called
376 * graph. Both will end up being a tuple. */
377 ir_node *post_bl = get_nodes_block(call);
378 /* XxMxPxPxPxT of Start + parameter of Call */
379 ir_node *in[pn_Start_max+1];
380 in[pn_Start_M] = get_Call_mem(call);
381 in[pn_Start_X_initial_exec] = new_r_Jmp(post_bl);
382 in[pn_Start_P_frame_base] = get_irg_frame(irg);
383 in[pn_Start_T_args] = new_r_Tuple(post_bl, n_params, args_in);
384 ir_node *pre_call = new_r_Tuple(post_bl, pn_Start_max+1, in);
385 ir_node *post_call = call;
388 The new block gets the ins of the old block, pre_call and all its
389 predecessors and all Phi nodes. -- */
390 part_block(pre_call);
392 /* increment visited flag for later walk */
393 inc_irg_visited(called_graph);
395 /* link some nodes to nodes in the current graph so instead of copying
396 * the linked nodes will get used.
397 * So the copier will use the created Tuple instead of copying the start
398 * node, similar for singleton nodes like NoMem and Bad.
399 * Note: this will prohibit predecessors to be copied - only do it for
400 * nodes without predecessors */
401 ir_node *start_block = get_irg_start_block(called_graph);
402 set_new_node(start_block, get_nodes_block(pre_call));
403 mark_irn_visited(start_block);
405 ir_node *start = get_irg_start(called_graph);
406 set_new_node(start, pre_call);
407 mark_irn_visited(start);
409 ir_node *nomem = get_irg_no_mem(called_graph);
410 set_new_node(nomem, get_irg_no_mem(irg));
411 mark_irn_visited(nomem);
413 /* entitiy link is used to link entities on old stackframe to the
415 irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
417 /* copy entities and nodes */
418 assert(!irn_visited(get_irg_end(called_graph)));
419 copy_frame_entities(called_graph, irg);
420 irg_walk_core(get_irg_end(called_graph), copy_node_inline, set_preds_inline,
423 irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
425 /* -- Merge the end of the inlined procedure with the call site -- */
426 /* We will turn the old Call node into a Tuple with the following
429 0: Phi of all Memories of Return statements.
430 1: Jmp from new Block that merges the control flow from all exception
431 predecessors of the old end block.
432 2: Tuple of all arguments.
433 3: Phi of Exception memories.
434 In case the old Call directly branches to End on an exception we don't
435 need the block merging all exceptions nor the Phi of the exception
439 /* Precompute some values */
440 ir_node *end_bl = get_new_node(get_irg_end_block(called_graph));
441 ir_node *end = get_new_node(get_irg_end(called_graph));
442 int arity = get_Block_n_cfgpreds(end_bl); /* arity = n_exc + n_ret */
443 int n_res = get_method_n_ress(get_Call_type(call));
445 ir_node **res_pred = XMALLOCN(ir_node*, n_res);
446 ir_node **cf_pred = XMALLOCN(ir_node*, arity);
448 /* archive keepalives */
449 int irn_arity = get_irn_arity(end);
450 for (int i = 0; i < irn_arity; i++) {
451 ir_node *ka = get_End_keepalive(end, i);
453 add_End_keepalive(get_irg_end(irg), ka);
456 /* replace Return nodes by Jump nodes */
458 for (int i = 0; i < arity; i++) {
459 ir_node *ret = get_Block_cfgpred(end_bl, i);
460 if (is_Return(ret)) {
461 ir_node *block = get_nodes_block(ret);
462 cf_pred[n_ret] = new_r_Jmp(block);
466 set_irn_in(post_bl, n_ret, cf_pred);
468 /* build a Tuple for all results of the method.
469 * add Phi node if there was more than one Return. */
470 turn_into_tuple(post_call, pn_Call_max+1);
471 /* First the Memory-Phi */
473 for (int i = 0; i < arity; i++) {
474 ir_node *ret = get_Block_cfgpred(end_bl, i);
475 if (is_Return(ret)) {
476 cf_pred[n_mem_phi++] = get_Return_mem(ret);
478 /* memory output for some exceptions is directly connected to End */
480 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 3);
481 } else if (is_fragile_op(ret)) {
482 /* We rely that all cfops have the memory output at the same position. */
483 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 0);
484 } else if (is_Raise(ret)) {
485 cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 1);
488 ir_node *phi = new_r_Phi(post_bl, n_mem_phi, cf_pred, mode_M);
489 set_Tuple_pred(call, pn_Call_M, phi);
490 /* Conserve Phi-list for further inlinings -- but might be optimized */
491 if (get_nodes_block(phi) == post_bl) {
492 set_irn_link(phi, get_irn_link(post_bl));
493 set_irn_link(post_bl, phi);
495 /* Now the real results */
497 for (int j = 0; j < n_res; j++) {
498 ir_type *res_type = get_method_res_type(ctp, j);
499 ir_mode *res_mode = get_type_mode(res_type);
501 for (int i = 0; i < arity; i++) {
502 ir_node *ret = get_Block_cfgpred(end_bl, i);
503 if (is_Return(ret)) {
504 ir_node *res = get_Return_res(ret, j);
505 if (get_irn_mode(res) != res_mode) {
506 ir_node *block = get_nodes_block(res);
507 res = new_r_Conv(block, res, res_mode);
509 cf_pred[n_ret] = res;
514 phi = new_r_Phi(post_bl, n_ret, cf_pred, res_mode);
516 phi = new_r_Bad(irg, res_mode);
519 /* Conserve Phi-list for further inlinings -- but might be optimized */
520 if (get_nodes_block(phi) == post_bl) {
521 set_Phi_next(phi, get_Block_phis(post_bl));
522 set_Block_phis(post_bl, phi);
525 ir_node *result_tuple = new_r_Tuple(post_bl, n_res, res_pred);
526 set_Tuple_pred(call, pn_Call_T_result, result_tuple);
528 set_Tuple_pred(call, pn_Call_T_result, new_r_Bad(irg, mode_T));
530 /* handle the regular call */
531 set_Tuple_pred(call, pn_Call_X_regular, new_r_Jmp(post_bl));
533 /* Finally the exception control flow.
534 We have two possible situations:
535 First if the Call branches to an exception handler:
536 We need to add a Phi node to
537 collect the memory containing the exception objects. Further we need
538 to add another block to get a correct representation of this Phi. To
539 this block we add a Jmp that resolves into the X output of the Call
540 when the Call is turned into a tuple.
541 Second: There is no exception edge. Just add all inlined exception
542 branches to the End node.
544 if (exc_handling == exc_handler) {
546 for (int i = 0; i < arity; i++) {
547 ir_node *ret = get_Block_cfgpred(end_bl, i);
548 ir_node *irn = skip_Proj(ret);
549 if (is_fragile_op(irn) || is_Raise(irn)) {
550 cf_pred[n_exc] = ret;
557 set_Tuple_pred(call, pn_Call_X_except, cf_pred[0]);
559 ir_node *block = new_r_Block(irg, n_exc, cf_pred);
560 set_Tuple_pred(call, pn_Call_X_except, new_r_Jmp(block));
563 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
566 /* assert(exc_handling == 1 || no exceptions. ) */
568 for (int i = 0; i < arity; i++) {
569 ir_node *ret = get_Block_cfgpred(end_bl, i);
570 ir_node *irn = skip_Proj(ret);
572 if (is_fragile_op(irn) || is_Raise(irn)) {
573 cf_pred[n_exc] = ret;
577 ir_node *main_end_bl = get_irg_end_block(irg);
578 int main_end_bl_arity = get_irn_arity(main_end_bl);
579 ir_node **end_preds = XMALLOCN(ir_node*, n_exc+main_end_bl_arity);
581 for (int i = 0; i < main_end_bl_arity; ++i)
582 end_preds[i] = get_irn_n(main_end_bl, i);
583 for (int i = 0; i < n_exc; ++i)
584 end_preds[main_end_bl_arity + i] = cf_pred[i];
585 set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
586 set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
592 /* -- Turn CSE back on. -- */
593 set_optimize(rem_opt);
594 current_ir_graph = rem;
599 /********************************************************************/
600 /* Apply inlining to small methods. */
601 /********************************************************************/
603 static struct obstack temp_obst;
605 /** Represents a possible inlinable call in a graph. */
606 typedef struct call_entry {
607 ir_node *call; /**< The Call node. */
608 ir_graph *callee; /**< The callee IR-graph. */
609 list_head list; /**< List head for linking the next one. */
610 int loop_depth; /**< The loop depth of this call. */
611 int benefice; /**< The calculated benefice of this call. */
612 unsigned local_adr:1; /**< Set if this call gets an address of a local variable. */
613 unsigned all_const:1; /**< Set if this call has only constant parameters. */
617 * environment for inlining small irgs
619 typedef struct inline_env_t {
620 struct obstack obst; /**< An obstack where call_entries are allocated on. */
621 list_head calls; /**< The call entry list. */
625 * Returns the irg called from a Call node. If the irg is not
626 * known, NULL is returned.
628 * @param call the call node
630 static ir_graph *get_call_called_irg(ir_node *call)
634 addr = get_Call_ptr(call);
635 if (is_SymConst_addr_ent(addr)) {
636 ir_entity *ent = get_SymConst_entity(addr);
637 /* we don't know which function gets finally bound to a weak symbol */
638 if (get_entity_linkage(ent) & IR_LINKAGE_WEAK)
641 return get_entity_irg(ent);
648 * Walker: Collect all calls to known graphs inside a graph.
650 static void collect_calls(ir_node *call, void *env)
654 ir_graph *called_irg = get_call_called_irg(call);
656 if (called_irg != NULL) {
657 /* The Call node calls a locally defined method. Remember to inline. */
658 inline_env_t *ienv = (inline_env_t*)env;
659 call_entry *entry = OALLOC(&ienv->obst, call_entry);
661 entry->callee = called_irg;
662 entry->loop_depth = 0;
664 entry->local_adr = 0;
665 entry->all_const = 0;
667 list_add_tail(&entry->list, &ienv->calls);
673 * Inlines all small methods at call sites where the called address comes
674 * from a Const node that references the entity representing the called
676 * The size argument is a rough measure for the code size of the method:
677 * Methods where the obstack containing the firm graph is smaller than
680 void inline_small_irgs(ir_graph *irg, int size)
682 ir_graph *rem = current_ir_graph;
685 current_ir_graph = irg;
686 /* Handle graph state */
687 assert(get_irg_phase_state(irg) != phase_building);
688 free_callee_info(irg);
690 /* Find Call nodes to inline.
691 (We can not inline during a walk of the graph, as inlining the same
692 method several times changes the visited flag of the walked graph:
693 after the first inlining visited of the callee equals visited of
694 the caller. With the next inlining both are increased.) */
695 obstack_init(&env.obst);
696 INIT_LIST_HEAD(&env.calls);
697 irg_walk_graph(irg, NULL, collect_calls, &env);
699 if (! list_empty(&env.calls)) {
700 /* There are calls to inline */
701 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
702 collect_phiprojs(irg);
704 list_for_each_entry(call_entry, entry, &env.calls, list) {
705 ir_graph *callee = entry->callee;
706 irg_inline_property prop = get_irg_inline_property(callee);
708 if (prop == irg_inline_forbidden) {
712 if (prop >= irg_inline_forced ||
713 _obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst) < size) {
714 inline_method(entry->call, callee);
717 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
719 obstack_free(&env.obst, NULL);
720 current_ir_graph = rem;
723 typedef struct inline_small_irgs_pass_t {
724 ir_graph_pass_t pass;
726 } inline_small_irgs_pass_t;
729 * Wrapper to run inline_small_irgs() as a pass.
731 static int inline_small_irgs_wrapper(ir_graph *irg, void *context)
733 inline_small_irgs_pass_t *pass = (inline_small_irgs_pass_t*)context;
735 inline_small_irgs(irg, pass->size);
739 /* create a pass for inline_small_irgs() */
740 ir_graph_pass_t *inline_small_irgs_pass(const char *name, int size)
742 inline_small_irgs_pass_t *pass = XMALLOCZ(inline_small_irgs_pass_t);
745 return def_graph_pass_constructor(
746 &pass->pass, name ? name : "inline_small_irgs", inline_small_irgs_wrapper);
750 * Environment for inlining irgs.
753 list_head calls; /**< List of of all call nodes in this graph. */
754 unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */
755 unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
756 unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */
757 unsigned n_nodes_orig; /**< for statistics */
758 unsigned n_call_nodes; /**< Number of Call nodes in the graph. */
759 unsigned n_call_nodes_orig; /**< for statistics */
760 unsigned n_callers; /**< Number of known graphs that call this graphs. */
761 unsigned n_callers_orig; /**< for statistics */
762 unsigned got_inline:1; /**< Set, if at least one call inside this graph was inlined. */
763 unsigned recursive:1; /**< Set, if this function is self recursive. */
767 * Allocate a new environment for inlining.
769 static inline_irg_env *alloc_inline_irg_env(void)
771 inline_irg_env *env = OALLOC(&temp_obst, inline_irg_env);
772 INIT_LIST_HEAD(&env->calls);
773 env->local_weights = NULL;
774 env->n_nodes = -2; /* do not count count Start, End */
775 env->n_blocks = -2; /* do not count count Start, End Block */
776 env->n_nodes_orig = -2; /* do not count Start, End */
777 env->n_call_nodes = 0;
778 env->n_call_nodes_orig = 0;
780 env->n_callers_orig = 0;
786 typedef struct walker_env {
787 inline_irg_env *x; /**< the inline environment */
788 char ignore_runtime; /**< the ignore runtime flag */
789 char ignore_callers; /**< if set, do change callers data */
793 * post-walker: collect all calls in the inline-environment
794 * of a graph and sum some statistics.
796 static void collect_calls2(ir_node *call, void *ctx)
798 wenv_t *env = (wenv_t*)ctx;
799 inline_irg_env *x = env->x;
800 unsigned code = get_irn_opcode(call);
804 /* count meaningful nodes in irg */
805 if (code != iro_Proj && code != iro_Tuple && code != iro_Sync) {
806 if (code != iro_Block) {
814 if (code != iro_Call) return;
816 /* check, if it's a runtime call */
817 if (env->ignore_runtime) {
818 ir_node *symc = get_Call_ptr(call);
820 if (is_SymConst_addr_ent(symc)) {
821 ir_entity *ent = get_SymConst_entity(symc);
823 if (get_entity_additional_properties(ent) & mtp_property_runtime)
828 /* collect all call nodes */
830 ++x->n_call_nodes_orig;
832 callee = get_call_called_irg(call);
833 if (callee != NULL) {
834 if (! env->ignore_callers) {
835 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
836 /* count all static callers */
837 ++callee_env->n_callers;
838 ++callee_env->n_callers_orig;
840 if (callee == current_ir_graph)
843 /* link it in the list of possible inlinable entries */
844 entry = OALLOC(&temp_obst, call_entry);
846 entry->callee = callee;
847 entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth;
849 entry->local_adr = 0;
850 entry->all_const = 0;
852 list_add_tail(&entry->list, &x->calls);
857 * Returns TRUE if the number of callers is 0 in the irg's environment,
858 * hence this irg is a leaf.
860 inline static int is_leaf(ir_graph *irg)
862 inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
863 return env->n_call_nodes == 0;
867 * Returns TRUE if the number of nodes in the callee is
868 * smaller then size in the irg's environment.
870 inline static int is_smaller(ir_graph *callee, unsigned size)
872 inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
873 return env->n_nodes < size;
877 * Duplicate a call entry.
879 * @param entry the original entry to duplicate
880 * @param new_call the new call node
881 * @param loop_depth_delta
882 * delta value for the loop depth
884 static call_entry *duplicate_call_entry(const call_entry *entry,
885 ir_node *new_call, int loop_depth_delta)
887 call_entry *nentry = OALLOC(&temp_obst, call_entry);
888 nentry->call = new_call;
889 nentry->callee = entry->callee;
890 nentry->benefice = entry->benefice;
891 nentry->loop_depth = entry->loop_depth + loop_depth_delta;
892 nentry->local_adr = entry->local_adr;
893 nentry->all_const = entry->all_const;
899 * Append all call nodes of the source environment to the nodes of in the destination
902 * @param dst destination environment
903 * @param src source environment
904 * @param loop_depth the loop depth of the call that is replaced by the src list
906 static void append_call_list(inline_irg_env *dst, inline_irg_env *src, int loop_depth)
910 /* Note that the src list points to Call nodes in the inlined graph, but
911 we need Call nodes in our graph. Luckily the inliner leaves this information
912 in the link field. */
913 list_for_each_entry(call_entry, entry, &src->calls, list) {
914 nentry = duplicate_call_entry(entry, (ir_node*)get_irn_link(entry->call), loop_depth);
915 list_add_tail(&nentry->list, &dst->calls);
917 dst->n_call_nodes += src->n_call_nodes;
918 dst->n_nodes += src->n_nodes;
922 * Inlines small leaf methods at call sites where the called address comes
923 * from a Const node that references the entity representing the called
925 * The size argument is a rough measure for the code size of the method:
926 * Methods where the obstack containing the firm graph is smaller than
929 void inline_leaf_functions(unsigned maxsize, unsigned leafsize,
930 unsigned size, int ignore_runtime)
939 pmap_entry *pm_entry;
941 rem = current_ir_graph;
942 obstack_init(&temp_obst);
944 /* a map for the copied graphs, used to inline recursive calls */
945 copied_graphs = pmap_create();
947 /* extend all irgs by a temporary data structure for inlining. */
948 n_irgs = get_irp_n_irgs();
949 for (i = 0; i < n_irgs; ++i)
950 set_irg_link(get_irp_irg(i), alloc_inline_irg_env());
952 /* Pre-compute information in temporary data structure. */
953 wenv.ignore_runtime = ignore_runtime;
954 wenv.ignore_callers = 0;
955 for (i = 0; i < n_irgs; ++i) {
956 ir_graph *irg = get_irp_irg(i);
958 assert(get_irg_phase_state(irg) != phase_building);
959 free_callee_info(irg);
961 assure_irg_properties(irg,
962 IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
963 wenv.x = (inline_irg_env*)get_irg_link(irg);
964 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
965 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL);
968 /* -- and now inline. -- */
970 /* Inline leafs recursively -- we might construct new leafs. */
974 for (i = 0; i < n_irgs; ++i) {
976 int phiproj_computed = 0;
978 current_ir_graph = get_irp_irg(i);
979 env = (inline_irg_env*)get_irg_link(current_ir_graph);
981 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
982 list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
984 irg_inline_property prop;
986 if (env->n_nodes > maxsize)
990 callee = entry->callee;
992 prop = get_irg_inline_property(callee);
993 if (prop == irg_inline_forbidden) {
997 if (is_leaf(callee) && (
998 is_smaller(callee, leafsize) || prop >= irg_inline_forced)) {
999 if (!phiproj_computed) {
1000 phiproj_computed = 1;
1001 collect_phiprojs(current_ir_graph);
1003 did_inline = inline_method(call, callee);
1006 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1008 /* call was inlined, Phi/Projs for current graph must be recomputed */
1009 phiproj_computed = 0;
1011 /* Do some statistics */
1012 env->got_inline = 1;
1013 --env->n_call_nodes;
1014 env->n_nodes += callee_env->n_nodes;
1015 --callee_env->n_callers;
1017 /* remove this call from the list */
1018 list_del(&entry->list);
1023 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1025 } while (did_inline);
1027 /* inline other small functions. */
1028 for (i = 0; i < n_irgs; ++i) {
1030 int phiproj_computed = 0;
1032 current_ir_graph = get_irp_irg(i);
1033 env = (inline_irg_env*)get_irg_link(current_ir_graph);
1035 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1037 /* note that the list of possible calls is updated during the process */
1038 list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
1039 irg_inline_property prop;
1044 callee = entry->callee;
1046 prop = get_irg_inline_property(callee);
1047 if (prop == irg_inline_forbidden) {
1051 calleee = pmap_get(ir_graph, copied_graphs, callee);
1052 if (calleee != NULL) {
1054 * Remap callee if we have a copy.
1055 * FIXME: Should we do this only for recursive Calls ?
1060 if (prop >= irg_inline_forced ||
1061 (is_smaller(callee, size) && env->n_nodes < maxsize) /* small function */) {
1062 if (current_ir_graph == callee) {
1064 * Recursive call: we cannot directly inline because we cannot walk
1065 * the graph and change it. So we have to make a copy of the graph
1069 inline_irg_env *callee_env;
1072 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1075 * No copy yet, create one.
1076 * Note that recursive methods are never leafs, so it is sufficient
1077 * to test this condition here.
1079 copy = create_irg_copy(callee);
1081 /* create_irg_copy() destroys the Proj links, recompute them */
1082 phiproj_computed = 0;
1084 ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1086 /* allocate new environment */
1087 callee_env = alloc_inline_irg_env();
1088 set_irg_link(copy, callee_env);
1090 assure_irg_properties(copy,
1091 IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
1092 wenv.x = callee_env;
1093 wenv.ignore_callers = 1;
1094 irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1097 * Enter the entity of the original graph. This is needed
1098 * for inline_method(). However, note that ent->irg still points
1099 * to callee, NOT to copy.
1101 set_irg_entity(copy, get_irg_entity(callee));
1103 pmap_insert(copied_graphs, callee, copy);
1106 /* we have only one caller: the original graph */
1107 callee_env->n_callers = 1;
1108 callee_env->n_callers_orig = 1;
1110 if (! phiproj_computed) {
1111 phiproj_computed = 1;
1112 collect_phiprojs(current_ir_graph);
1114 did_inline = inline_method(call, callee);
1116 inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
1118 /* call was inlined, Phi/Projs for current graph must be recomputed */
1119 phiproj_computed = 0;
1121 /* callee was inline. Append its call list. */
1122 env->got_inline = 1;
1123 --env->n_call_nodes;
1124 append_call_list(env, callee_env, entry->loop_depth);
1125 --callee_env->n_callers;
1127 /* after we have inlined callee, all called methods inside callee
1128 are now called once more */
1129 list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1130 inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1134 /* remove this call from the list */
1135 list_del(&entry->list);
1140 ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1143 for (i = 0; i < n_irgs; ++i) {
1144 irg = get_irp_irg(i);
1145 env = (inline_irg_env*)get_irg_link(irg);
1147 if (env->got_inline) {
1148 optimize_graph_df(irg);
1151 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1152 DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1153 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1154 env->n_callers_orig, env->n_callers,
1155 get_entity_name(get_irg_entity(irg))));
1159 /* kill the copied graphs: we don't need them anymore */
1160 foreach_pmap(copied_graphs, pm_entry) {
1161 ir_graph *copy = (ir_graph*)pm_entry->value;
1163 /* reset the entity, otherwise it will be deleted in the next step ... */
1164 set_irg_entity(copy, NULL);
1165 free_ir_graph(copy);
1167 pmap_destroy(copied_graphs);
1169 obstack_free(&temp_obst, NULL);
1170 current_ir_graph = rem;
1173 typedef struct inline_leaf_functions_pass_t {
1174 ir_prog_pass_t pass;
1179 } inline_leaf_functions_pass_t;
1182 * Wrapper to run inline_leaf_functions() as a ir_prog pass.
1184 static int inline_leaf_functions_wrapper(ir_prog *irp, void *context)
1186 inline_leaf_functions_pass_t *pass = (inline_leaf_functions_pass_t*)context;
1189 inline_leaf_functions(
1190 pass->maxsize, pass->leafsize,
1191 pass->size, pass->ignore_runtime);
1195 /* create a pass for inline_leaf_functions() */
1196 ir_prog_pass_t *inline_leaf_functions_pass(
1197 const char *name, unsigned maxsize, unsigned leafsize,
1198 unsigned size, int ignore_runtime)
1200 inline_leaf_functions_pass_t *pass = XMALLOCZ(inline_leaf_functions_pass_t);
1202 pass->maxsize = maxsize;
1203 pass->leafsize = leafsize;
1205 pass->ignore_runtime = ignore_runtime;
1207 return def_prog_pass_constructor(
1209 name ? name : "inline_leaf_functions",
1210 inline_leaf_functions_wrapper);
1214 * Calculate the parameter weights for transmitting the address of a local variable.
1216 static unsigned calc_method_local_weight(ir_node *arg)
1219 unsigned v, weight = 0;
1221 for (unsigned i = get_irn_n_outs(arg); i-- > 0; ) {
1222 ir_node *succ = get_irn_out(arg, i);
1224 switch (get_irn_opcode(succ)) {
1227 /* Loads and Store can be removed */
1231 /* check if all args are constant */
1232 for (j = get_Sel_n_indexs(succ) - 1; j >= 0; --j) {
1233 ir_node *idx = get_Sel_index(succ, j);
1234 if (! is_Const(idx))
1237 /* Check users on this Sel. Note: if a 0 is returned here, there was
1238 some unsupported node. */
1239 v = calc_method_local_weight(succ);
1242 /* we can kill one Sel with constant indexes, this is cheap */
1246 /* when looking backward we might find Id nodes */
1247 weight += calc_method_local_weight(succ);
1250 /* unoptimized tuple */
1251 for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
1252 ir_node *pred = get_Tuple_pred(succ, j);
1254 /* look for Proj(j) */
1255 for (unsigned k = get_irn_n_outs(succ); k-- > 0; ) {
1256 ir_node *succ_succ = get_irn_out(succ, k);
1257 if (is_Proj(succ_succ)) {
1258 if (get_Proj_proj(succ_succ) == j) {
1260 weight += calc_method_local_weight(succ_succ);
1263 /* this should NOT happen */
1271 /* any other node: unsupported yet or bad. */
1279 * Calculate the parameter weights for transmitting the address of a local variable.
1281 static void analyze_irg_local_weights(inline_irg_env *env, ir_graph *irg)
1283 ir_entity *ent = get_irg_entity(irg);
1287 ir_node *irg_args, *arg;
1289 mtp = get_entity_type(ent);
1290 nparams = get_method_n_params(mtp);
1292 /* allocate a new array. currently used as 'analysed' flag */
1293 env->local_weights = NEW_ARR_D(unsigned, &temp_obst, nparams);
1295 /* If the method haven't parameters we have nothing to do. */
1299 assure_irg_outs(irg);
1300 irg_args = get_irg_args(irg);
1301 for (unsigned i = get_irn_n_outs(irg_args); i-- > 0; ) {
1302 arg = get_irn_out(irg_args, i);
1303 proj_nr = get_Proj_proj(arg);
1304 env->local_weights[proj_nr] = calc_method_local_weight(arg);
1309 * Calculate the benefice for transmitting an local variable address.
1310 * After inlining, the local variable might be transformed into a
1311 * SSA variable by scalar_replacement().
1313 static unsigned get_method_local_adress_weight(ir_graph *callee, size_t pos)
1315 inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
1317 if (env->local_weights == NULL)
1318 analyze_irg_local_weights(env, callee);
1320 if (pos < ARR_LEN(env->local_weights))
1321 return env->local_weights[pos];
1326 * Calculate a benefice value for inlining the given call.
1328 * @param call the call node we have to inspect
1329 * @param callee the called graph
1331 static int calc_inline_benefice(call_entry *entry, ir_graph *callee)
1333 ir_node *call = entry->call;
1334 ir_entity *ent = get_irg_entity(callee);
1335 ir_type *callee_frame;
1336 size_t i, n_members, n_params;
1342 irg_inline_property prop;
1344 inline_irg_env *callee_env;
1346 prop = get_irg_inline_property(callee);
1347 if (prop == irg_inline_forbidden) {
1348 DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n",
1350 return entry->benefice = INT_MIN;
1353 callee_frame = get_irg_frame_type(callee);
1354 n_members = get_class_n_members(callee_frame);
1355 for (i = 0; i < n_members; ++i) {
1356 ir_entity *frame_ent = get_class_member(callee_frame, i);
1357 if (is_parameter_entity(frame_ent)) {
1358 // TODO inliner should handle parameter entities by inserting Store operations
1359 DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden due to parameter entity\n", call, callee));
1360 set_irg_inline_property(callee, irg_inline_forbidden);
1361 return entry->benefice = INT_MIN;
1365 if (get_irg_additional_properties(callee) & mtp_property_noreturn) {
1366 DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n",
1368 return entry->benefice = INT_MIN;
1371 /* costs for every passed parameter */
1372 n_params = get_Call_n_params(call);
1373 mtp = get_entity_type(ent);
1374 cc = get_method_calling_convention(mtp);
1375 if (cc & cc_reg_param) {
1376 /* register parameter, smaller costs for register parameters */
1377 size_t max_regs = cc & ~cc_bits;
1379 if (max_regs < n_params)
1380 weight += max_regs * 2 + (n_params - max_regs) * 5;
1382 weight += n_params * 2;
1384 /* parameters are passed an stack */
1385 weight += 5 * n_params;
1388 /* constant parameters improve the benefice */
1389 frame_ptr = get_irg_frame(current_ir_graph);
1391 for (i = 0; i < n_params; ++i) {
1392 ir_node *param = get_Call_param(call, i);
1394 if (is_Const(param)) {
1395 weight += get_method_param_weight(ent, i);
1398 if (is_SymConst(param))
1399 weight += get_method_param_weight(ent, i);
1400 else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr) {
1402 * An address of a local variable is transmitted. After
1403 * inlining, scalar_replacement might be able to remove the
1404 * local variable, so honor this.
1406 v = get_method_local_adress_weight(callee, i);
1409 entry->local_adr = 1;
1413 entry->all_const = all_const;
1415 callee_env = (inline_irg_env*)get_irg_link(callee);
1416 if (callee_env->n_callers == 1 &&
1417 callee != current_ir_graph &&
1418 !entity_is_externally_visible(ent)) {
1422 /* give a bonus for functions with one block */
1423 if (callee_env->n_blocks == 1)
1424 weight = weight * 3 / 2;
1426 /* and one for small non-recursive functions: we want them to be inlined in mostly every case */
1427 if (callee_env->n_nodes < 30 && !callee_env->recursive)
1430 /* and finally for leafs: they do not increase the register pressure
1431 because of callee safe registers */
1432 if (callee_env->n_call_nodes == 0)
1435 /** it's important to inline inner loops first */
1436 if (entry->loop_depth > 30)
1437 weight += 30 * 1024;
1439 weight += entry->loop_depth * 1024;
1442 * All arguments constant is probably a good sign, give an extra bonus
1447 return entry->benefice = weight;
1450 typedef struct walk_env_t {
1456 * Callgraph walker, collect all visited graphs.
1458 static void callgraph_walker(ir_graph *irg, void *data)
1460 walk_env_t *env = (walk_env_t *)data;
1461 env->irgs[env->last_irg++] = irg;
1465 * Creates an inline order for all graphs.
1467 * @return the list of graphs.
1469 static ir_graph **create_irg_list(void)
1471 ir_entity **free_methods;
1472 size_t n_irgs = get_irp_n_irgs();
1475 cgana(&free_methods);
1476 xfree(free_methods);
1478 compute_callgraph();
1480 env.irgs = XMALLOCNZ(ir_graph*, n_irgs);
1483 callgraph_walk(NULL, callgraph_walker, &env);
1484 assert(n_irgs == env.last_irg);
1492 * Push a call onto the priority list if its benefice is big enough.
1494 * @param pqueue the priority queue of calls
1495 * @param call the call entry
1496 * @param inlien_threshold
1497 * the threshold value
1499 static void maybe_push_call(pqueue_t *pqueue, call_entry *call,
1500 int inline_threshold)
1502 ir_graph *callee = call->callee;
1503 irg_inline_property prop = get_irg_inline_property(callee);
1504 int benefice = calc_inline_benefice(call, callee);
1506 DB((dbg, LEVEL_2, "In %+F Call %+F to %+F has benefice %d\n",
1507 get_irn_irg(call->call), call->call, callee, benefice));
1509 if (prop < irg_inline_forced && benefice < inline_threshold) {
1513 pqueue_put(pqueue, call, benefice);
1517 * Try to inline calls into a graph.
1519 * @param irg the graph into which we inline
1520 * @param maxsize do NOT inline if the size of irg gets
1521 * bigger than this amount
1522 * @param inline_threshold
1523 * threshold value for inline decision
1524 * @param copied_graphs
1525 * map containing copied of recursive graphs
1527 static void inline_into(ir_graph *irg, unsigned maxsize,
1528 int inline_threshold, pmap *copied_graphs)
1530 int phiproj_computed = 0;
1531 inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
1535 if (env->n_call_nodes == 0)
1538 if (env->n_nodes > maxsize) {
1539 DB((dbg, LEVEL_2, "%+F: too big (%d)\n", irg, env->n_nodes));
1543 current_ir_graph = irg;
1544 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1546 /* put irgs into the pqueue */
1547 pqueue = new_pqueue();
1549 list_for_each_entry(call_entry, curr_call, &env->calls, list) {
1550 assert(is_Call(curr_call->call));
1551 maybe_push_call(pqueue, curr_call, inline_threshold);
1554 /* note that the list of possible calls is updated during the process */
1555 while (!pqueue_empty(pqueue)) {
1557 call_entry *curr_call = (call_entry*)pqueue_pop_front(pqueue);
1558 ir_graph *callee = curr_call->callee;
1559 ir_node *call_node = curr_call->call;
1560 inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1561 irg_inline_property prop = get_irg_inline_property(callee);
1565 if ((prop < irg_inline_forced) && env->n_nodes + callee_env->n_nodes > maxsize) {
1566 DB((dbg, LEVEL_2, "%+F: too big (%d) + %+F (%d)\n", irg,
1567 env->n_nodes, callee, callee_env->n_nodes));
1571 calleee = pmap_get(ir_graph, copied_graphs, callee);
1572 if (calleee != NULL) {
1573 int benefice = curr_call->benefice;
1575 * Reduce the weight for recursive function IFF not all arguments are const.
1576 * inlining recursive functions is rarely good.
1578 if (!curr_call->all_const)
1580 if (benefice < inline_threshold)
1584 * Remap callee if we have a copy.
1587 callee_env = (inline_irg_env*)get_irg_link(callee);
1590 if (current_ir_graph == callee) {
1592 * Recursive call: we cannot directly inline because we cannot
1593 * walk the graph and change it. So we have to make a copy of
1596 int benefice = curr_call->benefice;
1600 * Reduce the weight for recursive function IFF not all arguments are const.
1601 * inlining recursive functions is rarely good.
1603 if (!curr_call->all_const)
1605 if (benefice < inline_threshold)
1608 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1611 * No copy yet, create one.
1612 * Note that recursive methods are never leafs, so it is
1613 * sufficient to test this condition here.
1615 copy = create_irg_copy(callee);
1617 /* create_irg_copy() destroys the Proj links, recompute them */
1618 phiproj_computed = 0;
1620 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1622 /* allocate a new environment */
1623 callee_env = alloc_inline_irg_env();
1624 set_irg_link(copy, callee_env);
1626 assure_irg_properties(copy, IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
1627 memset(&wenv, 0, sizeof(wenv));
1628 wenv.x = callee_env;
1629 wenv.ignore_callers = 1;
1630 irg_walk_graph(copy, NULL, collect_calls2, &wenv);
1633 * Enter the entity of the original graph. This is needed
1634 * for inline_method(). However, note that ent->irg still points
1635 * to callee, NOT to copy.
1637 set_irg_entity(copy, get_irg_entity(callee));
1639 pmap_insert(copied_graphs, callee, copy);
1642 /* we have only one caller: the original graph */
1643 callee_env->n_callers = 1;
1644 callee_env->n_callers_orig = 1;
1646 if (! phiproj_computed) {
1647 phiproj_computed = 1;
1648 collect_phiprojs(current_ir_graph);
1650 did_inline = inline_method(call_node, callee);
1654 /* call was inlined, Phi/Projs for current graph must be recomputed */
1655 phiproj_computed = 0;
1657 /* remove it from the caller list */
1658 list_del(&curr_call->list);
1660 /* callee was inline. Append its call list. */
1661 env->got_inline = 1;
1662 --env->n_call_nodes;
1664 /* we just generate a bunch of new calls */
1665 loop_depth = curr_call->loop_depth;
1666 list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1667 inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1669 call_entry *new_entry;
1671 /* after we have inlined callee, all called methods inside
1672 * callee are now called once more */
1675 /* Note that the src list points to Call nodes in the inlined graph,
1676 * but we need Call nodes in our graph. Luckily the inliner leaves
1677 * this information in the link field. */
1678 new_call = (ir_node*)get_irn_link(centry->call);
1679 if (get_irn_irg(new_call) != irg) {
1680 /* centry->call has not been copied, which means it is dead.
1681 * This might happen during inlining, if a const function,
1682 * which cannot be inlined is only used as an unused argument
1683 * of another function, which is inlined. */
1686 assert(is_Call(new_call));
1688 new_entry = duplicate_call_entry(centry, new_call, loop_depth);
1689 list_add_tail(&new_entry->list, &env->calls);
1690 maybe_push_call(pqueue, new_entry, inline_threshold);
1693 env->n_call_nodes += callee_env->n_call_nodes;
1694 env->n_nodes += callee_env->n_nodes;
1695 --callee_env->n_callers;
1697 ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1702 * Heuristic inliner. Calculates a benefice value for every call and inlines
1703 * those calls with a value higher than the threshold.
1705 void inline_functions(unsigned maxsize, int inline_threshold,
1706 opt_ptr after_inline_opt)
1708 inline_irg_env *env;
1712 pmap *copied_graphs;
1713 pmap_entry *pm_entry;
1716 rem = current_ir_graph;
1717 obstack_init(&temp_obst);
1719 irgs = create_irg_list();
1721 /* a map for the copied graphs, used to inline recursive calls */
1722 copied_graphs = pmap_create();
1724 /* extend all irgs by a temporary data structure for inlining. */
1725 n_irgs = get_irp_n_irgs();
1726 for (i = 0; i < n_irgs; ++i)
1727 set_irg_link(irgs[i], alloc_inline_irg_env());
1729 /* Pre-compute information in temporary data structure. */
1730 wenv.ignore_runtime = 0;
1731 wenv.ignore_callers = 0;
1732 for (i = 0; i < n_irgs; ++i) {
1733 ir_graph *irg = irgs[i];
1735 free_callee_info(irg);
1737 wenv.x = (inline_irg_env*)get_irg_link(irg);
1738 assure_loopinfo(irg);
1739 irg_walk_graph(irg, NULL, collect_calls2, &wenv);
1742 /* -- and now inline. -- */
1743 for (i = 0; i < n_irgs; ++i) {
1744 ir_graph *irg = irgs[i];
1746 inline_into(irg, maxsize, inline_threshold, copied_graphs);
1749 for (i = 0; i < n_irgs; ++i) {
1750 ir_graph *irg = irgs[i];
1752 env = (inline_irg_env*)get_irg_link(irg);
1753 if (env->got_inline && after_inline_opt != NULL) {
1754 /* this irg got calls inlined: optimize it */
1755 after_inline_opt(irg);
1757 if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
1758 DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",
1759 env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes,
1760 env->n_callers_orig, env->n_callers,
1761 get_entity_name(get_irg_entity(irg))));
1765 /* kill the copied graphs: we don't need them anymore */
1766 foreach_pmap(copied_graphs, pm_entry) {
1767 ir_graph *copy = (ir_graph*)pm_entry->value;
1769 /* reset the entity, otherwise it will be deleted in the next step ... */
1770 set_irg_entity(copy, NULL);
1771 free_ir_graph(copy);
1773 pmap_destroy(copied_graphs);
1777 obstack_free(&temp_obst, NULL);
1778 current_ir_graph = rem;
1781 typedef struct inline_functions_pass_t {
1782 ir_prog_pass_t pass;
1784 int inline_threshold;
1785 opt_ptr after_inline_opt;
1786 } inline_functions_pass_t;
1789 * Wrapper to run inline_functions() as a ir_prog pass.
1791 static int inline_functions_wrapper(ir_prog *irp, void *context)
1793 inline_functions_pass_t *pass = (inline_functions_pass_t*)context;
1796 inline_functions(pass->maxsize, pass->inline_threshold,
1797 pass->after_inline_opt);
1801 /* create a ir_prog pass for inline_functions */
1802 ir_prog_pass_t *inline_functions_pass(
1803 const char *name, unsigned maxsize, int inline_threshold,
1804 opt_ptr after_inline_opt)
1806 inline_functions_pass_t *pass = XMALLOCZ(inline_functions_pass_t);
1808 pass->maxsize = maxsize;
1809 pass->inline_threshold = inline_threshold;
1810 pass->after_inline_opt = after_inline_opt;
1812 return def_prog_pass_constructor(
1813 &pass->pass, name ? name : "inline_functions",
1814 inline_functions_wrapper);
1817 void firm_init_inline(void)
1819 FIRM_DBG_REGISTER(dbg, "firm.opt.inline");