X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_inline.c;h=b12e7ef9f6fb746bc9c6875fa930f79f2e25978a;hb=c7dc950ac0cdd7d24acffb798b5867d0db5dd7c8;hp=9f8845575afd1c0f8745f5b46f75b2517debcbbe;hpb=6779c87f32214b62ed54f3e054c83aa0683fb29e;p=libfirm diff --git a/ir/opt/opt_inline.c b/ir/opt/opt_inline.c index 9f8845575..b12e7ef9f 100644 --- a/ir/opt/opt_inline.c +++ b/ir/opt/opt_inline.c @@ -838,8 +838,30 @@ int inline_method(ir_node *call, ir_graph *called_graph) { ent = get_irg_entity(called_graph); /* Do not inline variadic functions. */ - if (get_method_variadicity(get_entity_type(ent)) == variadicity_variadic) - return 0; + if (get_method_variadicity(get_entity_type(ent)) == variadicity_variadic) { + /* Arg, KR functions are marked as variadic one's, so check further */ + ir_type *mtp = get_entity_type(ent); + ir_type *ctp = get_Call_type(call); + int n_params = get_method_n_params(mtp); + int i; + + /* This is too strong, but probably ok. Function calls with a wrong number of + parameters should not be inlined. */ + if (n_params != get_method_n_params(ctp)) + return 0; + + /* check types: for K&R calls, this was not done by the compiler. Again, this is + too strong, but ok for now. */ + for (i = n_params - 1; i >= 0; --i) { + ir_type *param_tp = get_method_param_type(mtp, i); + ir_type *arg_tp = get_method_param_type(ctp, i); + + if (param_tp != arg_tp) + return 0; + } + DB((dbg, LEVEL_1, "Inlining allowed for variadic function %+F\n", called_graph)); + /* types match, fine: when the frame is access, the inliner stops at can_inline() */ + } assert(get_method_n_params(get_entity_type(ent)) == get_method_n_params(get_Call_type(call))); @@ -864,7 +886,7 @@ int inline_method(ir_node *call, ir_graph *called_graph) { rem = current_ir_graph; current_ir_graph = irg; - DB((dbg, SET_LEVEL_1, "Inlining %+F(%+F) into %+F\n", call, called_graph, irg)); + DB((dbg, LEVEL_1, "Inlining %+F(%+F) into %+F\n", call, called_graph, irg)); /* -- Turn off optimizations, this can cause problems when allocating new nodes. -- */ rem_opt = get_opt_optimize(); @@ -914,7 +936,6 @@ int inline_method(ir_node *call, ir_graph *called_graph) { in[pn_Start_X_initial_exec] = new_Jmp(); in[pn_Start_M] = get_Call_mem(call); in[pn_Start_P_frame_base] = get_irg_frame(irg); - in[pn_Start_P_globals] = get_irg_globals(irg); in[pn_Start_P_tls] = get_irg_tls(irg); in[pn_Start_T_args] = new_Tuple(get_Call_n_params(call), get_Call_param_arr(call)); /* in[pn_Start_P_value_arg_base] = ??? */ @@ -1169,10 +1190,10 @@ 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 */ - ir_graph *callee; /**< the callee called here */ - call_entry *next; /**< for linking the next one */ - unsigned weight; /**< the weight of the call */ + 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 */ }; /** @@ -1213,10 +1234,10 @@ static void collect_calls(ir_node *call, void *env) { /* The Call node calls a locally defined method. Remember to inline. */ inline_env_t *ienv = env; call_entry *entry = obstack_alloc(&ienv->obst, sizeof(*entry)); - entry->call = call; - entry->callee = called_irg; - entry->next = NULL; - entry->weight = 0; + entry->call = call; + entry->callee = called_irg; + entry->next = NULL; + entry->loop_depth = 0; if (ienv->tail == NULL) ienv->head = entry; @@ -1276,14 +1297,15 @@ typedef struct { int n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */ int n_blocks; /**< Number of Blocks in graph without Start and End block. */ int n_nodes_orig; /**< for statistics */ - 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 .*/ int n_call_nodes; /**< Number of Call nodes in the graph. */ int n_call_nodes_orig; /**< for statistics */ int n_callers; /**< Number of known graphs that call this graphs. */ int 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. */ } inline_irg_env; @@ -1303,14 +1325,16 @@ static inline_irg_env *alloc_inline_irg_env(void) { env->n_callers_orig = 0; env->got_inline = 0; env->local_vars = 0; + env->recursive = 0; env->local_weights = NULL; return env; } typedef struct walker_env { - inline_irg_env *x; /**< the inline environment */ - char ignore_runtime; /**< the ignore runtime flag */ - char ignore_callers; /**< if set, do change callers data */ + inline_irg_env *x; /**< the inline environment */ + call_entry *last_call; /**< points to the last inserted call */ + char ignore_runtime; /**< the ignore runtime flag */ + char ignore_callers; /**< if set, do change callers data */ } wenv_t; /** @@ -1360,17 +1384,44 @@ static void collect_calls2(ir_node *call, void *ctx) { ++callee_env->n_callers; ++callee_env->n_callers_orig; } + if (callee == current_ir_graph) + x->recursive = 1; /* link it in the list of possible inlinable entries */ entry = obstack_alloc(&temp_obst, sizeof(*entry)); - entry->call = call; - entry->callee = callee; - entry->next = NULL; - if (x->call_tail == NULL) + entry->call = call; + entry->callee = callee; + entry->next = NULL; + entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth; + + /* note: we use call_tail here as a pointer to the last inserted */ + if (x->call_head == NULL) { x->call_head = entry; - else - x->call_tail->next = entry; - x->call_tail = entry; + } else { + if (entry->loop_depth == env->last_call->loop_depth) { + /* same depth as the last one, enqueue after it */ + entry->next = env->last_call->next; + env->last_call->next = entry; + } else if (entry->loop_depth > x->call_head->loop_depth) { + /* put first */ + entry->next = x->call_head; + x->call_head = entry; + } else { + /* search the insertion point */ + call_entry *p; + + for (p = x->call_head; p->next != NULL; p = p->next) + if (entry->loop_depth > p->next->loop_depth) + break; + entry->next = p->next; + p->next = entry; + } + } + env->last_call = entry; + if (entry->next == NULL) { + /* keep tail up to date */ + x->call_tail = entry; + } } } @@ -1403,14 +1454,46 @@ static void append_call_list(inline_irg_env *dst, call_entry *src) { 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->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; } } +/** + * Add the nodes of the list src in front to the nodes of the list dst. + */ +static call_entry *replace_entry_by_call_list(call_entry *dst, call_entry *src) { + call_entry *entry, *nentry, *head, *tail; + + /* 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. */ + head = tail = NULL; + 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->loop_depth; + if (head == NULL) + head = nentry; + else + tail->next = nentry; + tail = nentry; + } + /* skip the head of dst */ + if (head != NULL) { + tail->next = dst->next; + } else { + head = dst->next; + } + return head; +} + /* * Inlines small leave methods at call sites where the called address comes * from a Const node that references the entity representing the called @@ -1451,6 +1534,7 @@ void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_run assert(get_irg_phase_state(irg) != phase_building); free_callee_info(irg); + assure_cf_loop(irg); wenv.x = get_irg_link(irg); irg_walk_graph(irg, NULL, collect_calls2, &wenv); } @@ -1563,6 +1647,7 @@ void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_run callee_env = alloc_inline_irg_env(); set_irg_link(copy, callee_env); + assure_cf_loop(copy); wenv.x = callee_env; wenv.ignore_callers = 1; irg_walk_graph(copy, NULL, collect_calls2, &wenv); @@ -1629,7 +1714,7 @@ void inline_leave_functions(int maxsize, int leavesize, int size, int ignore_run optimize_cf(irg); } if (env->got_inline || (env->n_callers_orig != env->n_callers)) { - DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n", + DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n", env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes, env->n_callers_orig, env->n_callers, get_entity_name(get_irg_entity(irg)))); @@ -1705,6 +1790,7 @@ static unsigned calc_method_local_weight(ir_node *arg) { } } } + break; default: /* any other node: unsupported yet or bad. */ return 0; @@ -1770,7 +1856,7 @@ static int calc_inline_benefice(ir_node *call, ir_graph *callee, unsigned *local ir_node *frame_ptr; ir_type *mtp; int weight = 0; - int i, n_params; + int i, n_params, all_const; unsigned cc, v; inline_irg_env *curr_env, *callee_env; @@ -1799,21 +1885,27 @@ static int calc_inline_benefice(ir_node *call, ir_graph *callee, unsigned *local /* constant parameters improve the benefice */ frame_ptr = get_irg_frame(current_ir_graph); + all_const = 1; for (i = 0; i < n_params; ++i) { ir_node *param = get_Call_param(call, i); - if (is_Const(param) || is_SymConst(param)) + if (is_Const(param)) weight += get_method_param_weight(ent, i); - else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr) { - /* - * An address of a local variable is transmitted. After inlining, - * scalar_replacement might be able to remove the local variable, - * so honor this. - */ - v = get_method_local_adress_weight(callee, i); - weight += v; - if (v > 0) - *local_adr = 1; + else { + all_const = 0; + if (is_SymConst(param)) + weight += get_method_param_weight(ent, i); + else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr) { + /* + * An address of a local variable is transmitted. After inlining, + * scalar_replacement might be able to remove the local variable, + * so honor this. + */ + v = get_method_local_adress_weight(callee, i); + weight += v; + if (v > 0) + *local_adr = 1; + } } } @@ -1830,26 +1922,48 @@ static int calc_inline_benefice(ir_node *call, ir_graph *callee, unsigned *local /* reduce the benefice if the current function is already big */ curr_env = get_irg_link(current_ir_graph); - weight -= curr_env->n_nodes / 100; + weight -= curr_env->n_nodes / 50; /* give a bonus for functions with one block */ if (callee_env->n_blocks == 1) weight = weight * 3 / 2; + /* and one for small non-recursive functions: we want them to be inlined in mostly every case */ + else if (callee_env->n_nodes < 20 && !callee_env->recursive) + weight += 5000; + + /* and finally for leaves: they do not increase the register pressure + because of callee safe registers */ + else if (callee_env->n_call_nodes == 0) + weight += 25; + + /* + * 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 -= 500; + + /* + * All arguments constant is probably a good sign, give an extra bonus + */ + if (all_const) + weight += 100; + return weight; } /** - * Heuristic inliner. Calculates a benifice value for every call and inlines + * Heuristic inliner. Calculates a benefice value for every call and inlines * those calls with a value higher than the threshold. */ -void inline_functions(int inline_threshold) { +void inline_functions(int maxsize, int inline_threshold) { inline_irg_env *env; int i, n_irgs; ir_graph *rem; int did_inline; wenv_t wenv; - call_entry *entry, *tail; + call_entry *curr_call, **last_call; const call_entry *centry; pmap *copied_graphs; pmap_entry *pm_entry; @@ -1874,7 +1988,9 @@ void inline_functions(int inline_threshold) { assert(get_irg_phase_state(irg) != phase_building); free_callee_info(irg); - wenv.x = get_irg_link(irg); + wenv.x = get_irg_link(irg); + wenv.last_call = NULL; + assure_cf_loop(irg); irg_walk_graph(irg, NULL, collect_calls2, &wenv); } @@ -1888,30 +2004,32 @@ void inline_functions(int inline_threshold) { env = get_irg_link(irg); /* note that the list of possible calls is updated during the process */ - tail = NULL; - for (entry = env->call_head; entry != NULL; entry = entry->next) { + last_call = &env->call_head; + for (curr_call = env->call_head; curr_call != NULL;) { ir_graph *callee; pmap_entry *e; int benefice; unsigned local_adr; - call = entry->call; - callee = entry->callee; + if (env->n_nodes > maxsize) break; - /* calculate the benifice on the original call to prevent excessive inlining */ - local_adr = 0; - benefice = calc_inline_benefice(call, callee, &local_adr); - DB((dbg, SET_LEVEL_2, "In %+F Call %+F has benefice %d\n", irg, callee, benefice)); + call = curr_call->call; + callee = curr_call->callee; e = pmap_find(copied_graphs, callee); if (e != NULL) { /* - * Remap callee if we have a copy. - * FIXME: Should we do this only for recursive Calls ? - */ + * Remap callee if we have a copy. + * FIXME: Should we do this only for recursive Calls ? + */ callee = e->value; } + /* calculate the benefice on the original call to prevent excessive inlining */ + local_adr = 0; + benefice = calc_inline_benefice(call, callee, &local_adr); + DB((dbg, LEVEL_2, "In %+F Call %+F has benefice %d\n", irg, callee, benefice)); + if (benefice > -inline_threshold || (get_irg_inline_property(callee) >= irg_inline_forced)) { if (current_ir_graph == callee) { @@ -1938,6 +2056,7 @@ void inline_functions(int inline_threshold) { callee_env = alloc_inline_irg_env(); set_irg_link(copy, callee_env); + assure_cf_loop(copy); wenv.x = callee_env; wenv.ignore_callers = 1; irg_walk_graph(copy, NULL, collect_calls2, &wenv); @@ -1967,34 +2086,31 @@ void inline_functions(int inline_threshold) { /* was inlined, 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; + } + /* callee was inline. Append it's call list. */ env->got_inline = 1; if (local_adr) env->local_vars = 1; --env->n_call_nodes; - append_call_list(env, callee_env->call_head); + curr_call = replace_entry_by_call_list(curr_call, callee_env->call_head); env->n_call_nodes += callee_env->n_call_nodes; env->n_nodes += callee_env->n_nodes; --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) { - 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; + /* remove the current call entry from the list */ + *last_call = curr_call; continue; } } - tail = entry; + last_call = &curr_call->next; + curr_call = curr_call->next; } - env->call_tail = tail; if (env->got_inline) { /* this irg got calls inlined: optimize it */ @@ -2007,11 +2123,10 @@ void inline_functions(int inline_threshold) { optimize_graph_df(irg); } } - optimize_cf(irg); } if (env->got_inline || (env->n_callers_orig != env->n_callers)) { - DB((dbg, SET_LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n", + DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n", env->n_nodes_orig, env->n_nodes, env->n_call_nodes_orig, env->n_call_nodes, env->n_callers_orig, env->n_callers, get_entity_name(get_irg_entity(irg))));