X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_inline.c;h=bf36024b0d177d2fc7e851f98adb866c9c71102a;hb=188a17803798f8d78b1c02c3b68976056bce33d9;hp=0344ccff8771be5a4fb05488b42cf0adf64fadc1;hpb=07545437eaa406c0412aef501926ce08fa26a1e5;p=libfirm diff --git a/ir/opt/opt_inline.c b/ir/opt/opt_inline.c index 0344ccff8..bf36024b0 100644 --- a/ir/opt/opt_inline.c +++ b/ir/opt/opt_inline.c @@ -23,9 +23,7 @@ * @author Michael Beck, Goetz Lindenmaier * @version $Id$ */ -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif +#include "config.h" #include #include @@ -41,12 +39,13 @@ #include "irgmod.h" #include "irgwalk.h" -#include "adt/array.h" -#include "adt/pset.h" -#include "adt/pmap.h" -#include "adt/pdeq.h" -#include "adt/xmalloc.h" -#include "adt/pqueue.h" +#include "array_t.h" +#include "list.h" +#include "pset.h" +#include "pmap.h" +#include "pdeq.h" +#include "xmalloc.h" +#include "pqueue.h" #include "irouts.h" #include "irloop_t.h" @@ -93,7 +92,7 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg;) * accesses. This function is called for all Phi and Block nodes * in a Block. */ -static INLINE int +static inline int compute_new_arity(ir_node *b) { int i, res, irn_arity; int irg_v, block_v; @@ -471,7 +470,7 @@ void dead_node_elimination(ir_graph *irg) { graveyard_obst = irg->obst; /* A new obstack, where the reachable nodes will be copied to. */ - rebirth_obst = xmalloc(sizeof(*rebirth_obst)); + rebirth_obst = XMALLOC(struct obstack); irg->obst = rebirth_obst; obstack_init(irg->obst); irg->last_node_idx = 0; @@ -662,7 +661,7 @@ static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_ * Make a new Survive DCE environment. */ survive_dce_t *new_survive_dce(void) { - survive_dce_t *res = xmalloc(sizeof(res[0])); + survive_dce_t *res = XMALLOC(survive_dce_t); obstack_init(&res->obst); res->places = pmap_create(); res->new_places = NULL; @@ -675,10 +674,6 @@ survive_dce_t *new_survive_dce(void) { res->dead_node_elim_subst.context = res; res->dead_node_elim_subst.next = NULL; -#ifndef FIRM_ENABLE_HOOKS - assert(0 && "need hooks enabled"); -#endif - register_hook(hook_dead_node_elim, &res->dead_node_elim); register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst); return res; @@ -783,7 +778,7 @@ static void find_addr(ir_node *node, void *env) { * using alloca is called in loop. In GCC present in SPEC2000 inlining * into schedule_block cause it to require 2GB of ram instead of 256MB. * - * Sorryly this is true with our implementation also. + * Sorrily this is true with our implementation also. * Moreover, we cannot differentiate between alloca() and VLA yet, so this * disables inlining of functions using VLA (with are completely save). * @@ -1022,6 +1017,7 @@ int inline_method(ir_node *call, ir_graph *called_graph) { /* -- Replicate local entities of the called_graph -- */ /* copy the entities. */ + irp_reserve_resources(irp, IR_RESOURCE_ENTITY_LINK); called_frame = get_irg_frame_type(called_graph); curr_frame = get_irg_frame_type(irg); for (i = 0, n = get_class_n_members(called_frame); i < n; ++i) { @@ -1042,6 +1038,8 @@ int inline_method(ir_node *call, ir_graph *called_graph) { irg_walk(get_irg_end(called_graph), copy_node_inline, copy_preds_inline, get_irg_frame_type(called_graph)); + irp_free_resources(irp, IR_RESOURCE_ENTITY_LINK); + /* Repair called_graph */ set_irg_visited(called_graph, get_irg_visited(irg)); set_irg_block_visited(called_graph, get_irg_block_visited(irg)); @@ -1067,8 +1065,8 @@ int inline_method(ir_node *call, ir_graph *called_graph) { arity = get_Block_n_cfgpreds(end_bl); /* arity = n_exc + n_ret */ n_res = get_method_n_ress(get_Call_type(call)); - res_pred = xmalloc(n_res * sizeof(*res_pred)); - cf_pred = xmalloc(arity * sizeof(*res_pred)); + res_pred = XMALLOCN(ir_node*, n_res); + cf_pred = XMALLOCN(ir_node*, arity); set_irg_current_block(irg, post_bl); /* just to make sure */ @@ -1208,9 +1206,9 @@ int inline_method(ir_node *call, ir_graph *called_graph) { n_exc++; } } - main_end_bl = get_irg_end_block(irg); + main_end_bl = get_irg_end_block(irg); main_end_bl_arity = get_irn_arity(main_end_bl); - end_preds = xmalloc((n_exc + main_end_bl_arity) * sizeof(*end_preds)); + end_preds = XMALLOCN(ir_node*, n_exc + main_end_bl_arity); for (i = 0; i < main_end_bl_arity; ++i) end_preds[i] = get_irn_n(main_end_bl, i); @@ -1232,28 +1230,28 @@ int inline_method(ir_node *call, ir_graph *called_graph) { } /********************************************************************/ -/* Apply inlineing to small methods. */ +/* Apply inlining to small methods. */ /********************************************************************/ static struct obstack temp_obst; /** Represents a possible inlinable call in a graph. */ -typedef struct _call_entry call_entry; -struct _call_entry { - ir_node *call; /**< the Call node */ - ir_graph *callee; /**< the callee IR-graph called here */ - call_entry *next; /**< for linking the next one */ - int loop_depth; /**< the loop depth of this call */ - unsigned local_adr : 1; -}; +typedef struct _call_entry { + ir_node *call; /**< The Call node. */ + ir_graph *callee; /**< The callee IR-graph. */ + list_head list; /**< List head for linking the next one. */ + int loop_depth; /**< The loop depth of this call. */ + int benefice; /**< The calculated benefice of this call. */ + unsigned local_adr:1; /**< Set if this call gets an address of a local variable. */ + unsigned all_const:1; /**< Set if this call has only constant parameters. */ +} call_entry; /** * environment for inlining small irgs */ typedef struct _inline_env_t { - struct obstack obst; /**< an obstack where call_entries are allocated on. */ - call_entry *head; /**< the head of the call entry list */ - call_entry *tail; /**< the tail of the call entry list */ + struct obstack obst; /**< An obstack where call_entries are allocated on. */ + list_head calls; /**< The call entry list. */ } inline_env_t; /** @@ -1278,6 +1276,7 @@ static ir_graph *get_call_called_irg(ir_node *call) { * Walker: Collect all calls to known graphs inside a graph. */ static void collect_calls(ir_node *call, void *env) { + (void) env; if (is_Call(call)) { ir_graph *called_irg = get_call_called_irg(call); @@ -1287,14 +1286,12 @@ static void collect_calls(ir_node *call, void *env) { call_entry *entry = obstack_alloc(&ienv->obst, sizeof(*entry)); entry->call = call; entry->callee = called_irg; - entry->next = NULL; entry->loop_depth = 0; + entry->benefice = 0; + entry->local_adr = 0; + entry->all_const = 0; - if (ienv->tail == NULL) - ienv->head = entry; - else - ienv->tail->next = entry; - ienv->tail = entry; + list_add_tail(&entry->list, &ienv->calls); } } } @@ -1318,19 +1315,19 @@ void inline_small_irgs(ir_graph *irg, int size) { free_callee_info(irg); /* Find Call nodes to inline. - (We can not inline during a walk of the graph, as inlineing the same + (We can not inline during a walk of the graph, as inlining the same method several times changes the visited flag of the walked graph: - after the first inlineing visited of the callee equals visited of - the caller. With the next inlineing both are increased.) */ + after the first inlining visited of the callee equals visited of + the caller. With the next inlining both are increased.) */ obstack_init(&env.obst); - env.head = env.tail = NULL; + INIT_LIST_HEAD(&env.calls); irg_walk_graph(irg, NULL, collect_calls, &env); - if (env.head != NULL) { + if (! list_empty(&env.calls)) { /* There are calls to inline */ collect_phiprojs(irg); - for (entry = env.head; entry != NULL; entry = entry->next) { + list_for_each_entry(call_entry, entry, &env.calls, list) { ir_graph *callee = entry->callee; irg_inline_property prop = get_irg_inline_property(callee); @@ -1353,19 +1350,18 @@ void inline_small_irgs(ir_graph *irg, int size) { * Environment for inlining irgs. */ typedef struct { - unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */ - unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */ - unsigned n_nodes_orig; /**< for statistics */ - unsigned n_call_nodes; /**< Number of Call nodes in the graph. */ - unsigned n_call_nodes_orig; /**< for statistics */ - unsigned n_callers; /**< Number of known graphs that call this graphs. */ - unsigned n_callers_orig; /**< for statistics */ - unsigned got_inline:1; /**< Set, if at least one call inside this graph was inlined. */ - unsigned local_vars:1; /**< Set, if a inlined function gets the address of an inlined variable. */ - unsigned recursive:1; /**< Set, if this function is self recursive. */ - call_entry *call_head; /**< The head of the list of all call nodes in this graph. */ - call_entry *call_tail; /**< The tail of the list of all call nodes in this graph .*/ - unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */ + list_head calls; /**< List of of all call nodes in this graph. */ + unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */ + unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */ + unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */ + unsigned n_nodes_orig; /**< for statistics */ + unsigned n_call_nodes; /**< Number of Call nodes in the graph. */ + unsigned n_call_nodes_orig; /**< for statistics */ + unsigned n_callers; /**< Number of known graphs that call this graphs. */ + unsigned n_callers_orig; /**< for statistics */ + unsigned got_inline:1; /**< Set, if at least one call inside this graph was inlined. */ + unsigned local_vars:1; /**< Set, if an inlined function got the address of a local variable. */ + unsigned recursive:1; /**< Set, if this function is self recursive. */ } inline_irg_env; /** @@ -1373,11 +1369,11 @@ typedef struct { */ static inline_irg_env *alloc_inline_irg_env(void) { inline_irg_env *env = obstack_alloc(&temp_obst, sizeof(*env)); + INIT_LIST_HEAD(&env->calls); + env->local_weights = NULL; env->n_nodes = -2; /* do not count count Start, End */ env->n_blocks = -2; /* do not count count Start, End Block */ env->n_nodes_orig = -2; /* do not count Start, End */ - env->call_head = NULL; - env->call_tail = NULL; env->n_call_nodes = 0; env->n_call_nodes_orig = 0; env->n_callers = 0; @@ -1385,7 +1381,6 @@ static inline_irg_env *alloc_inline_irg_env(void) { env->got_inline = 0; env->local_vars = 0; env->recursive = 0; - env->local_weights = NULL; return env; } @@ -1449,16 +1444,12 @@ static void collect_calls2(ir_node *call, void *ctx) { entry = obstack_alloc(&temp_obst, sizeof(*entry)); entry->call = call; entry->callee = callee; - entry->next = NULL; entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth; + entry->benefice = 0; + entry->local_adr = 0; + entry->all_const = 0; - entry->next = x->call_head; - x->call_head = entry; - - if (entry->next == NULL) { - /* keep tail up to date */ - x->call_tail = entry; - } + list_add_tail(&entry->list, &x->calls); } } @@ -1466,7 +1457,7 @@ static void collect_calls2(ir_node *call, void *ctx) { * Returns TRUE if the number of callers is 0 in the irg's environment, * hence this irg is a leave. */ -INLINE static int is_leave(ir_graph *irg) { +inline static int is_leave(ir_graph *irg) { inline_irg_env *env = get_irg_link(irg); return env->n_call_nodes == 0; } @@ -1475,43 +1466,54 @@ INLINE static int is_leave(ir_graph *irg) { * Returns TRUE if the number of nodes in the callee is * smaller then size in the irg's environment. */ -INLINE static int is_smaller(ir_graph *callee, unsigned size) { +inline static int is_smaller(ir_graph *callee, unsigned size) { inline_irg_env *env = get_irg_link(callee); return env->n_nodes < size; } /** - * Append the nodes of the list src to the nodes of the list in environment dst. + * Duplicate a call entry. + * + * @param entry the original entry to duplicate + * @param new_call the new call node + * @param loop_depth_delta + * delta value for the loop depth */ -static void append_call_list(inline_irg_env *dst, call_entry *src) { - call_entry *entry, *nentry; - - /* Note that the src list points to Call nodes in the inlined graph, but - we need Call nodes in our graph. Luckily the inliner leaves this information - in the link field. */ - for (entry = src; entry != NULL; entry = entry->next) { - nentry = obstack_alloc(&temp_obst, sizeof(*nentry)); - nentry->call = get_irn_link(entry->call); - nentry->callee = entry->callee; - nentry->next = NULL; - nentry->loop_depth = entry->loop_depth; - dst->call_tail->next = nentry; - dst->call_tail = nentry; - } -} - static call_entry *duplicate_call_entry(const call_entry *entry, - int loop_depth_delta, ir_node *new_call) -{ + ir_node *new_call, int loop_depth_delta) { call_entry *nentry = obstack_alloc(&temp_obst, sizeof(*nentry)); nentry->call = new_call; nentry->callee = entry->callee; - nentry->next = NULL; + nentry->benefice = entry->benefice; nentry->loop_depth = entry->loop_depth + loop_depth_delta; + nentry->local_adr = entry->local_adr; + nentry->all_const = entry->all_const; return nentry; } +/** + * Append all call nodes of the source environment to the nodes of in the destination + * environment. + * + * @param dst destination environment + * @param src source environment + * @param loop_depth the loop depth of the call that is replaced by the src list + */ +static void append_call_list(inline_irg_env *dst, inline_irg_env *src, int loop_depth) { + call_entry *entry, *nentry; + + /* Note that the src list points to Call nodes in the inlined graph, but + we need Call nodes in our graph. Luckily the inliner leaves this information + in the link field. */ + list_for_each_entry(call_entry, entry, &src->calls, list) { + nentry = duplicate_call_entry(entry, get_irn_link(entry->call), loop_depth); + list_add_tail(&nentry->list, &dst->calls); + } + dst->n_call_nodes += src->n_call_nodes; + dst->n_nodes += src->n_nodes; +} + /* * Inlines small leave methods at call sites where the called address comes * from a Const node that references the entity representing the called @@ -1521,7 +1523,7 @@ static call_entry *duplicate_call_entry(const call_entry *entry, * size are inlined. */ void inline_leave_functions(unsigned maxsize, unsigned leavesize, - unsigned size, int ignore_runtime) + unsigned size, int ignore_runtime) { inline_irg_env *env; ir_graph *irg; @@ -1529,7 +1531,7 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, ir_graph *rem; int did_inline; wenv_t wenv; - call_entry *entry, *tail; + call_entry *entry, *next; const call_entry *centry; pmap *copied_graphs; pmap_entry *pm_entry; @@ -1545,7 +1547,7 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, for (i = 0; i < n_irgs; ++i) set_irg_link(get_irp_irg(i), alloc_inline_irg_env()); - /* Precompute information in temporary data structure. */ + /* Pre-compute information in temporary data structure. */ wenv.ignore_runtime = ignore_runtime; wenv.ignore_callers = 0; for (i = 0; i < n_irgs; ++i) { @@ -1570,10 +1572,9 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, int phiproj_computed = 0; current_ir_graph = get_irp_irg(i); - env = (inline_irg_env *)get_irg_link(current_ir_graph); + env = get_irg_link(current_ir_graph); - tail = NULL; - for (entry = env->call_head; entry != NULL; entry = entry->next) { + list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) { ir_graph *callee; irg_inline_property prop; @@ -1598,9 +1599,9 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, did_inline = inline_method(call, callee); if (did_inline) { - inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee); + inline_irg_env *callee_env = get_irg_link(callee); - /* was inlined, must be recomputed */ + /* call was inlined, Phi/Projs for current graph must be recomputed */ phiproj_computed = 0; /* Do some statistics */ @@ -1610,16 +1611,11 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, --callee_env->n_callers; /* remove this call from the list */ - if (tail != NULL) - tail->next = entry->next; - else - env->call_head = entry->next; + list_del(&entry->list); continue; } } - tail = entry; } - env->call_tail = tail; } } while (did_inline); @@ -1629,11 +1625,10 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, int phiproj_computed = 0; current_ir_graph = get_irp_irg(i); - env = (inline_irg_env *)get_irg_link(current_ir_graph); + env = get_irg_link(current_ir_graph); /* note that the list of possible calls is updated during the process */ - tail = NULL; - for (entry = env->call_head; entry != NULL; entry = entry->next) { + list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) { irg_inline_property prop; ir_graph *callee; pmap_entry *e; @@ -1709,40 +1704,33 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, if (did_inline) { inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee); - /* was inlined, must be recomputed */ + /* call was inlined, Phi/Projs for current graph must be recomputed */ phiproj_computed = 0; /* callee was inline. Append it's call list. */ env->got_inline = 1; --env->n_call_nodes; - append_call_list(env, callee_env->call_head); - env->n_call_nodes += callee_env->n_call_nodes; - env->n_nodes += callee_env->n_nodes; + append_call_list(env, callee_env, entry->loop_depth); --callee_env->n_callers; /* after we have inlined callee, all called methods inside callee are now called once more */ - for (centry = callee_env->call_head; centry != NULL; centry = centry->next) { + list_for_each_entry(call_entry, centry, &callee_env->calls, list) { inline_irg_env *penv = get_irg_link(centry->callee); ++penv->n_callers; } /* remove this call from the list */ - if (tail != NULL) - tail->next = entry->next; - else - env->call_head = entry->next; + list_del(&entry->list); continue; } } - tail = entry; } - env->call_tail = tail; } for (i = 0; i < n_irgs; ++i) { irg = get_irp_irg(i); - env = (inline_irg_env *)get_irg_link(irg); + env = get_irg_link(irg); if (env->got_inline) { optimize_graph_df(irg); @@ -1888,11 +1876,8 @@ static unsigned get_method_local_adress_weight(ir_graph *callee, int pos) { * * @param call the call node we have to inspect * @param callee the called graph - * @param local_adr set after return if an address of a local variable is - * transmitted as a parameter */ -static int calc_inline_benefice(const call_entry *entry, ir_graph *callee, - unsigned *local_adr) +static int calc_inline_benefice(call_entry *entry, ir_graph *callee) { ir_node *call = entry->call; ir_entity *ent = get_irg_entity(callee); @@ -1909,15 +1894,13 @@ static int calc_inline_benefice(const call_entry *entry, ir_graph *callee, if (prop == irg_inline_forbidden) { DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n", call, callee)); - return INT_MIN; + return entry->benefice = INT_MIN; } - if ( (get_irg_additional_properties(callee) - | get_entity_additional_properties(ent)) - & (mtp_property_noreturn | mtp_property_weak)) { + if (get_irg_additional_properties(callee) & (mtp_property_noreturn | mtp_property_weak)) { DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n", call, callee)); - return INT_MIN; + return entry->benefice = INT_MIN; } /* costs for every passed parameter */ @@ -1958,15 +1941,16 @@ static int calc_inline_benefice(const call_entry *entry, ir_graph *callee, v = get_method_local_adress_weight(callee, i); weight += v; if (v > 0) - *local_adr = 1; + entry->local_adr = 1; } } } + entry->all_const = all_const; callee_env = get_irg_link(callee); - if (callee_env->n_callers == 1 - && callee != current_ir_graph - && get_entity_visibility(ent) == visibility_local) { + if (callee_env->n_callers == 1 && + callee != current_ir_graph && + get_entity_visibility(ent) == visibility_local) { weight += 700; } @@ -1983,13 +1967,6 @@ static int calc_inline_benefice(const call_entry *entry, ir_graph *callee, if (callee_env->n_call_nodes == 0) weight += 400; - /* - * Reduce the weight for recursive function IFF not all arguments are const. - * inlining recursive functions is rarely good. - */ - if (callee_env->recursive && !all_const) - weight -= 2000; - /** it's important to inline inner loops first */ if (entry->loop_depth > 30) weight += 30 * 1024; @@ -2000,22 +1977,28 @@ static int calc_inline_benefice(const call_entry *entry, ir_graph *callee, * All arguments constant is probably a good sign, give an extra bonus */ if (all_const) - weight += 1308; + weight += 1024; - return weight; + return entry->benefice = weight; } static ir_graph **irgs; static int last_irg; -static void callgraph_walker(ir_graph *irg, void *data) -{ +/** + * Callgraph walker, collect all visited graphs. + */ +static void callgraph_walker(ir_graph *irg, void *data) { (void) data; irgs[last_irg++] = irg; } -static ir_graph **create_irg_list(void) -{ +/** + * Creates an inline order for all graphs. + * + * @return the list of graphs. + */ +static ir_graph **create_irg_list(void) { ir_entity **free_methods; int arr_len; int n_irgs = get_irp_n_irgs(); @@ -2026,8 +2009,7 @@ static ir_graph **create_irg_list(void) compute_callgraph(); last_irg = 0; - irgs = xmalloc(n_irgs * sizeof(*irgs)); - memset(irgs, 0, sizeof(n_irgs * sizeof(*irgs))); + irgs = XMALLOCNZ(ir_graph*, n_irgs); callgraph_walk(NULL, callgraph_walker, NULL); assert(n_irgs == last_irg); @@ -2035,33 +2017,53 @@ static ir_graph **create_irg_list(void) return irgs; } +/** + * Push a call onto the priority list if its benefice is big enough. + * + * @param pqueue the priority queue of calls + * @param call the call entry + * @param inlien_threshold + * the threshold value + */ static void maybe_push_call(pqueue_t *pqueue, call_entry *call, int inline_threshold) { - ir_graph *callee = call->callee; - irg_inline_property prop = get_irg_inline_property(callee); - unsigned local_adr; - int benefice; - - benefice = calc_inline_benefice(call, callee, &local_adr); - call->local_adr = local_adr; + ir_graph *callee = call->callee; + irg_inline_property prop = get_irg_inline_property(callee); + int benefice = calc_inline_benefice(call, callee); DB((dbg, LEVEL_2, "In %+F Call %+F to %+F has benefice %d\n", - get_irn_irg(call->call), call->call, callee, benefice)); + get_irn_irg(call->call), call->call, callee, benefice)); - if (benefice < inline_threshold && !(prop & irg_inline_forced)) + if (prop < irg_inline_forced && benefice < inline_threshold) { return; + } pqueue_put(pqueue, call, benefice); } +/** + * Try to inline calls into a graph. + * + * @param irg the graph into which we inline + * @param maxsize do NOT inline if the size of irg gets + * bigger than this amount + * @param inline_threshold + * threshold value for inline decision + * @param copied_graphs + * map containing copied of recursive graphs + */ static void inline_into(ir_graph *irg, unsigned maxsize, - int inline_threshold, pmap *copied_graphs) + int inline_threshold, pmap *copied_graphs) { - int phiproj_computed = 0; + int phiproj_computed = 0; inline_irg_env *env = get_irg_link(irg); call_entry *curr_call; - wenv_t wenv; + wenv_t wenv; + pqueue_t *pqueue; + + if (env->n_call_nodes == 0) + return; if (env->n_nodes > maxsize) { DB((dbg, LEVEL_2, "%+F: too big (%d)\n", irg, env->n_nodes)); @@ -2071,32 +2073,26 @@ static void inline_into(ir_graph *irg, unsigned maxsize, current_ir_graph = irg; /* put irgs into the pqueue */ - pqueue_t *pqueue = new_pqueue(); - - for (curr_call = env->call_head; curr_call != NULL; - curr_call = curr_call->next) { + pqueue = new_pqueue(); - if (is_Tuple(curr_call->call)) - continue; + list_for_each_entry(call_entry, curr_call, &env->calls, list) { assert(is_Call(curr_call->call)); - maybe_push_call(pqueue, curr_call, inline_threshold); } /* note that the list of possible calls is updated during the process */ while (!pqueue_empty(pqueue)) { - int did_inline; - pmap_entry *e; - call_entry *curr_call = pqueue_pop_front(pqueue); - ir_graph *callee = curr_call->callee; - ir_node *call_node = curr_call->call; - irg_inline_property prop = get_irg_inline_property(callee); - const call_entry *centry; + int did_inline; + call_entry *curr_call = pqueue_pop_front(pqueue); + ir_graph *callee = curr_call->callee; + ir_node *call_node = curr_call->call; inline_irg_env *callee_env = get_irg_link(callee); - int depth = curr_call->loop_depth; + irg_inline_property prop = get_irg_inline_property(callee); + int loop_depth; + const call_entry *centry; + pmap_entry *e; - if (! (prop & irg_inline_forced) - && env->n_nodes + callee_env->n_nodes > maxsize) { + if ((prop < irg_inline_forced) && env->n_nodes + callee_env->n_nodes > maxsize) { DB((dbg, LEVEL_2, "%+F: too big (%d) + %+F (%d)\n", irg, env->n_nodes, callee, callee_env->n_nodes)); continue; @@ -2104,11 +2100,21 @@ static void inline_into(ir_graph *irg, unsigned maxsize, e = pmap_find(copied_graphs, callee); if (e != NULL) { + int benefice = curr_call->benefice; /* - * Remap callee if we have a copy. - * FIXME: Should we do this only for recursive Calls ? - */ - callee = e->value; + * Reduce the weight for recursive function IFF not all arguments are const. + * inlining recursive functions is rarely good. + */ + if (!curr_call->all_const) + benefice -= 2000; + if (benefice < inline_threshold) + continue; + + /* + * Remap callee if we have a copy. + */ + callee = e->value; + callee_env = get_irg_link(callee); } if (current_ir_graph == callee) { @@ -2117,8 +2123,17 @@ static void inline_into(ir_graph *irg, unsigned maxsize, * walk the graph and change it. So we have to make a copy of * the graph first. */ - inline_irg_env *callee_env; - ir_graph *copy; + int benefice = curr_call->benefice; + ir_graph *copy; + + /* + * Reduce the weight for recursive function IFF not all arguments are const. + * inlining recursive functions is rarely good. + */ + if (!curr_call->all_const) + benefice -= 2000; + if (benefice < inline_threshold) + continue; /* * No copy yet, create one. @@ -2130,7 +2145,7 @@ static void inline_into(ir_graph *irg, unsigned maxsize, /* create_irg_copy() destroys the Proj links, recompute them */ phiproj_computed = 0; - /* allocate new environment */ + /* allocate a new environment */ callee_env = alloc_inline_irg_env(); set_irg_link(copy, callee_env); @@ -2161,16 +2176,11 @@ static void inline_into(ir_graph *irg, unsigned maxsize, if (!did_inline) continue; - /* was inlined, must be recomputed */ + /* call was inlined, Phi/Projs for current graph must be recomputed */ phiproj_computed = 0; - /* after we have inlined callee, all called methods inside - * callee are now called once more */ - for (centry = callee_env->call_head; centry != NULL; - centry = centry->next) { - inline_irg_env *penv = get_irg_link(centry->callee); - ++penv->n_callers; - } + /* remove it from the caller list */ + list_del(&curr_call->list); /* callee was inline. Append it's call list. */ env->got_inline = 1; @@ -2179,19 +2189,24 @@ static void inline_into(ir_graph *irg, unsigned maxsize, --env->n_call_nodes; /* we just generate a bunch of new calls */ - for (centry = callee_env->call_head; centry != NULL; - centry = centry->next) { - /* Note that the src list points to Call nodes in the inlined graph, - * but we need Call nodes in our graph. Luckily the inliner leaves - * this information in the link field. */ + loop_depth = curr_call->loop_depth; + list_for_each_entry(call_entry, centry, &callee_env->calls, list) { + inline_irg_env *penv = get_irg_link(centry->callee); + ir_node *new_call; + call_entry *new_entry; - ir_node *new_call = get_irn_link(centry->call); - call_entry *new_entry; + /* after we have inlined callee, all called methods inside + * callee are now called once more */ + ++penv->n_callers; - if (!is_Call(new_call)) - continue; + /* Note that the src list points to Call nodes in the inlined graph, + * but we need Call nodes in our graph. Luckily the inliner leaves + * this information in the link field. */ + new_call = get_irn_link(centry->call); + assert(is_Call(new_call)); - new_entry = duplicate_call_entry(centry, depth, new_call); + new_entry = duplicate_call_entry(centry, new_call, loop_depth); + list_add_tail(&new_entry->list, &env->calls); maybe_push_call(pqueue, new_entry, inline_threshold); } @@ -2203,7 +2218,7 @@ static void inline_into(ir_graph *irg, unsigned maxsize, del_pqueue(pqueue); } -/** +/* * Heuristic inliner. Calculates a benefice value for every call and inlines * those calls with a value higher than the threshold. */ @@ -2229,7 +2244,7 @@ void inline_functions(unsigned maxsize, int inline_threshold) { for (i = 0; i < n_irgs; ++i) set_irg_link(irgs[i], alloc_inline_irg_env()); - /* Precompute information in temporary data structure. */ + /* Pre-compute information in temporary data structure. */ wenv.ignore_runtime = 0; wenv.ignore_callers = 0; for (i = 0; i < n_irgs; ++i) { @@ -2237,7 +2252,7 @@ void inline_functions(unsigned maxsize, int inline_threshold) { free_callee_info(irg); - wenv.x = get_irg_link(irg); + wenv.x = get_irg_link(irg); assure_cf_loop(irg); irg_walk_graph(irg, NULL, collect_calls2, &wenv); } @@ -2255,22 +2270,18 @@ void inline_functions(unsigned maxsize, int inline_threshold) { env = get_irg_link(irg); if (env->got_inline) { /* this irg got calls inlined: optimize it */ - - if (0) { - /* scalar replacement does not work well with Tuple nodes, so optimize them away */ - optimize_graph_df(irg); - + if (get_opt_combo()) { + if (env->local_vars) { + scalar_replacement_opt(irg); + } + combo(irg); + } else { if (env->local_vars) { if (scalar_replacement_opt(irg)) { optimize_graph_df(irg); } } optimize_cf(irg); - } else { - if (env->local_vars) { - scalar_replacement_opt(irg); - } - combo(irg); } } if (env->got_inline || (env->n_callers_orig != env->n_callers)) {