X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_inline.c;h=522456c13fb8febcd2940ba9727ea6355e3ea1a6;hb=151f1b110fe2c1ead4ae8dd66a2521f35c324946;hp=ffc3727ab735f0286f5a5b4dd413fec9581aff00;hpb=574981e342133ec0b980c70bd432b13bf11a2486;p=libfirm diff --git a/ir/opt/opt_inline.c b/ir/opt/opt_inline.c index ffc3727ab..522456c13 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,13 +39,13 @@ #include "irgmod.h" #include "irgwalk.h" -#include "adt/array.h" -#include "adt/list.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" @@ -94,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; @@ -166,15 +164,10 @@ static void copy_node(ir_node *n, void *env) { } copy_node_attr(n, nn); -#ifdef DEBUG_libfirm - { - int copy_node_nr = env != NULL; - if (copy_node_nr) { - /* for easier debugging, we want to copy the node numbers too */ - nn->node_nr = n->node_nr; - } + if (env != NULL) { + /* for easier debugging, we want to copy the node numbers too */ + nn->node_nr = n->node_nr; } -#endif set_new_node(n, nn); hook_dead_node_elim_subst(current_ir_graph, n, nn); @@ -223,9 +216,10 @@ static void copy_preds(ir_node *n, void *env) { in array contained Bads. Now it's possible. We don't call optimize_in_place as it requires that the fields in ir_graph are set properly. */ - if ((get_opt_control_flow_straightening()) && - (get_Block_n_cfgpreds(nn) == 1) && - is_Jmp(get_Block_cfgpred(nn, 0))) { + if (!has_Block_label(nn) && + get_opt_control_flow_straightening() && + get_Block_n_cfgpreds(nn) == 1 && + is_Jmp(get_Block_cfgpred(nn, 0))) { ir_node *old = get_nodes_block(get_Block_cfgpred(nn, 0)); if (nn == old) { /* Jmp jumps into the block it is in -- deal self cycle. */ @@ -472,7 +466,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; @@ -663,7 +657,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; @@ -676,10 +670,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; @@ -773,10 +763,16 @@ static void copy_preds_inline(ir_node *n, void *env) { */ static void find_addr(ir_node *node, void *env) { int *allow_inline = env; - if (is_Proj(node) && - is_Start(get_Proj_pred(node)) && - get_Proj_proj(node) == pn_Start_P_value_arg_base) { - *allow_inline = 0; + if (is_Sel(node)) { + ir_graph *irg = current_ir_graph; + if (get_Sel_ptr(node) == get_irg_frame(irg)) { + /* access to frame */ + ir_entity *ent = get_Sel_entity(node); + if (get_entity_owner(ent) != get_irg_frame_type(irg)) { + /* access to value_type */ + *allow_inline = 0; + } + } } else if (is_Alloc(node) && get_Alloc_where(node) == stack_alloc) { /* From GCC: * Refuse to inline alloca call unless user explicitly forced so as this @@ -784,7 +780,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). * @@ -866,17 +862,16 @@ int inline_method(ir_node *call, ir_graph *called_graph) { mtp = get_entity_type(ent); ctp = get_Call_type(call); if (get_method_n_params(mtp) > get_method_n_params(ctp)) { - /* this is a bad feature of C: without a prototype, we can can call a function with less - parameters than needed. Currently we don't support this, although it would be - to use Unknown than. */ + /* this is a bad feature of C: without a prototype, we can + * call a function with less parameters than needed. Currently + * we don't support this, although we could use Unknown than. */ return 0; } /* Argh, compiling C has some bad consequences: - the call type AND the method type might be different. - It is implementation defendant what happens in that case. - We support inlining, if the bitsize of the types matches AND - the same arithmetic is used. */ + * It is implementation dependent what happens in that case. + * We support inlining, if the bitsize of the types matches AND + * the same arithmetic is used. */ n_params = get_method_n_params(mtp); for (i = n_params - 1; i >= 0; --i) { ir_type *param_tp = get_method_param_type(mtp, i); @@ -931,6 +926,7 @@ int inline_method(ir_node *call, ir_graph *called_graph) { set_irg_doms_inconsistent(irg); set_irg_loopinfo_inconsistent(irg); set_irg_callee_info_state(irg, irg_callee_info_inconsistent); + set_irg_entity_usage_state(irg, ir_entity_usage_not_computed); /* -- Check preconditions -- */ assert(is_Call(call)); @@ -983,9 +979,7 @@ int inline_method(ir_node *call, ir_graph *called_graph) { in[pn_Start_P_frame_base] = get_irg_frame(irg); in[pn_Start_P_tls] = get_irg_tls(irg); in[pn_Start_T_args] = new_Tuple(n_params, args_in); - /* in[pn_Start_P_value_arg_base] = ??? */ - assert(pn_Start_P_value_arg_base == pn_Start_max - 1 && "pn_Start_P_value_arg_base not supported, fix"); - pre_call = new_Tuple(pn_Start_max - 1, in); + pre_call = new_Tuple(pn_Start_max, in); post_call = call; /* -- @@ -1023,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) { @@ -1043,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)); @@ -1068,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 */ @@ -1169,7 +1166,9 @@ int inline_method(ir_node *call, ir_graph *called_graph) { } } if (n_exc > 0) { - new_Block(n_exc, cf_pred); /* watch it: current_block is changed! */ + ir_node *block = new_Block(n_exc, cf_pred); + set_cur_block(block); + set_Tuple_pred(call, pn_Call_X_except, new_Jmp()); /* The Phi for the memories with the exception objects */ n_exc = 0; @@ -1209,9 +1208,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); @@ -1233,28 +1232,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 { - ir_node *call; /**< the Call node */ - ir_graph *callee; /**< the callee IR-graph called here */ - list_head list; /**< for linking the next one */ - int loop_depth; /**< the loop depth of this call */ - int benefice; /**< calculated benefice of this call */ - unsigned local_adr:1; /**< Set if this calls get an address of a local variable. */ - unsigned all_const:1; /**< Set if this calls has only constant parameters. */ + 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. */ - list_head calls; /**< 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; /** @@ -1318,16 +1317,17 @@ 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); INIT_LIST_HEAD(&env.calls); irg_walk_graph(irg, NULL, collect_calls, &env); if (! list_empty(&env.calls)) { /* There are calls to inline */ + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); collect_phiprojs(irg); list_for_each_entry(call_entry, entry, &env.calls, list) { @@ -1344,6 +1344,7 @@ void inline_small_irgs(ir_graph *irg, int size) { inline_method(entry->call, callee); } } + ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); } obstack_free(&env.obst, NULL); current_ir_graph = rem; @@ -1460,7 +1461,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; } @@ -1469,7 +1470,7 @@ 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; } @@ -1550,7 +1551,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) { @@ -1577,6 +1578,7 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, current_ir_graph = get_irp_irg(i); env = get_irg_link(current_ir_graph); + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) { ir_graph *callee; irg_inline_property prop; @@ -1604,7 +1606,7 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, if (did_inline) { 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 */ @@ -1619,6 +1621,7 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, } } } + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); } } while (did_inline); @@ -1630,6 +1633,8 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, current_ir_graph = get_irp_irg(i); env = get_irg_link(current_ir_graph); + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); + /* note that the list of possible calls is updated during the process */ list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) { irg_inline_property prop; @@ -1666,6 +1671,8 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, inline_irg_env *callee_env; ir_graph *copy; + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); + /* * No copy yet, create one. * Note that recursive methods are never leaves, so it is sufficient @@ -1676,6 +1683,8 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, /* create_irg_copy() destroys the Proj links, recompute them */ phiproj_computed = 0; + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); + /* allocate new environment */ callee_env = alloc_inline_irg_env(); set_irg_link(copy, callee_env); @@ -1707,7 +1716,7 @@ 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. */ @@ -1729,6 +1738,7 @@ void inline_leave_functions(unsigned maxsize, unsigned leavesize, } } } + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); } for (i = 0; i < n_irgs; ++i) { @@ -2012,8 +2022,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); @@ -2022,8 +2031,7 @@ static ir_graph **create_irg_list(void) { } /** - * Push a call onto the priority list if its - * benefice is big enough. + * 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 @@ -2033,24 +2041,16 @@ static ir_graph **create_irg_list(void) { static void maybe_push_call(pqueue_t *pqueue, call_entry *call, int inline_threshold) { - int benefice; ir_graph *callee = call->callee; irg_inline_property prop = get_irg_inline_property(callee); + int benefice = calc_inline_benefice(call, callee); - if (prop & irg_inline_forced) { - /* give them a big benefice, so forced are inline first */ - benefice = 100000 + call->loop_depth; - call->benefice = benefice; - DB((dbg, LEVEL_2, "In %+F Call %+F to %+F is forced\n", - get_irn_irg(call->call), call->call, callee)); - } else { - 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)); - } + DB((dbg, LEVEL_2, "In %+F Call %+F to %+F has benefice %d\n", + 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); } @@ -2084,6 +2084,7 @@ static void inline_into(ir_graph *irg, unsigned maxsize, } current_ir_graph = irg; + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); /* put irgs into the pqueue */ pqueue = new_pqueue(); @@ -2100,13 +2101,12 @@ static void inline_into(ir_graph *irg, unsigned maxsize, ir_graph *callee = curr_call->callee; ir_node *call_node = curr_call->call; inline_irg_env *callee_env = get_irg_link(callee); + irg_inline_property prop = get_irg_inline_property(callee); int loop_depth; const call_entry *centry; pmap_entry *e; - /* we need a hard limit here, else it would be possible to inline - * recursive functions forever. */ - if (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; @@ -2149,6 +2149,8 @@ static void inline_into(ir_graph *irg, unsigned maxsize, if (benefice < inline_threshold) continue; + ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); + /* * No copy yet, create one. * Note that recursive methods are never leaves, so it is @@ -2159,6 +2161,8 @@ static void inline_into(ir_graph *irg, unsigned maxsize, /* create_irg_copy() destroys the Proj links, recompute them */ phiproj_computed = 0; + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); + /* allocate a new environment */ callee_env = alloc_inline_irg_env(); set_irg_link(copy, callee_env); @@ -2190,7 +2194,7 @@ static void inline_into(ir_graph *irg, unsigned maxsize, if (!did_inline) continue; - /* got inlined, must be recomputed */ + /* call was inlined, Phi/Projs for current graph must be recomputed */ phiproj_computed = 0; /* remove it from the caller list */ @@ -2228,11 +2232,11 @@ static void inline_into(ir_graph *irg, unsigned maxsize, env->n_nodes += callee_env->n_nodes; --callee_env->n_callers; } - + ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); del_pqueue(pqueue); } -/** +/* * Heuristic inliner. Calculates a benefice value for every call and inlines * those calls with a value higher than the threshold. */ @@ -2258,7 +2262,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) { @@ -2284,22 +2288,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)) {