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)));
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();
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] = ??? */
/** 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 */
};
/**
/* 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;
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;
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;
/**
++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;
+ }
}
}
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
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);
}
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);
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))));
}
}
}
+ break;
default:
/* any other node: unsupported yet or bad. */
return 0;
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;
/* 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;
+ }
}
}
/* 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;
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);
}
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) {
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);
/* 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 */
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))));
projects / libfirm / blobdiff