+ 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))));
+ }
+ }
+
+ /* kill the copied graphs: we don't need them anymore */
+ foreach_pmap(copied_graphs, pm_entry) {
+ ir_graph *copy = (ir_graph*)pm_entry->value;
+
+ /* reset the entity, otherwise it will be deleted in the next step ... */
+ set_irg_entity(copy, NULL);
+ free_ir_graph(copy);
+ }
+ pmap_destroy(copied_graphs);
+
+ obstack_free(&temp_obst, NULL);
+ current_ir_graph = rem;
+}
+
+typedef struct inline_leave_functions_pass_t {
+ ir_prog_pass_t pass;
+ unsigned maxsize;
+ unsigned leavesize;
+ unsigned size;
+ int ignore_runtime;
+} inline_leave_functions_pass_t;
+
+/**
+ * Wrapper to run inline_leave_functions() as a ir_prog pass.
+ */
+static int inline_leave_functions_wrapper(ir_prog *irp, void *context)
+{
+ inline_leave_functions_pass_t *pass = (inline_leave_functions_pass_t*)context;
+
+ (void)irp;
+ inline_leave_functions(
+ pass->maxsize, pass->leavesize,
+ pass->size, pass->ignore_runtime);
+ return 0;
+}
+
+/* create a pass for inline_leave_functions() */
+ir_prog_pass_t *inline_leave_functions_pass(
+ const char *name, unsigned maxsize, unsigned leavesize,
+ unsigned size, int ignore_runtime)
+{
+ inline_leave_functions_pass_t *pass = XMALLOCZ(inline_leave_functions_pass_t);
+
+ pass->maxsize = maxsize;
+ pass->leavesize = leavesize;
+ pass->size = size;
+ pass->ignore_runtime = ignore_runtime;
+
+ return def_prog_pass_constructor(
+ &pass->pass,
+ name ? name : "inline_leave_functions",
+ inline_leave_functions_wrapper);
+}
+
+/**
+ * Calculate the parameter weights for transmitting the address of a local variable.
+ */
+static unsigned calc_method_local_weight(ir_node *arg)
+{
+ int i, j, k;
+ unsigned v, weight = 0;
+
+ for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
+ ir_node *succ = get_irn_out(arg, i);
+
+ switch (get_irn_opcode(succ)) {
+ case iro_Load:
+ case iro_Store:
+ /* Loads and Store can be removed */
+ weight += 3;
+ break;
+ case iro_Sel:
+ /* check if all args are constant */
+ for (j = get_Sel_n_indexs(succ) - 1; j >= 0; --j) {
+ ir_node *idx = get_Sel_index(succ, j);
+ if (! is_Const(idx))
+ return 0;
+ }
+ /* Check users on this Sel. Note: if a 0 is returned here, there was
+ some unsupported node. */
+ v = calc_method_local_weight(succ);
+ if (v == 0)
+ return 0;
+ /* we can kill one Sel with constant indexes, this is cheap */
+ weight += v + 1;
+ break;
+ case iro_Id:
+ /* when looking backward we might find Id nodes */
+ weight += calc_method_local_weight(succ);
+ break;
+ case iro_Tuple:
+ /* unoptimized tuple */
+ for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
+ ir_node *pred = get_Tuple_pred(succ, j);
+ if (pred == arg) {
+ /* look for Proj(j) */
+ for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
+ ir_node *succ_succ = get_irn_out(succ, k);
+ if (is_Proj(succ_succ)) {
+ if (get_Proj_proj(succ_succ) == j) {
+ /* found */
+ weight += calc_method_local_weight(succ_succ);
+ }
+ } else {
+ /* this should NOT happen */
+ return 0;
+ }
+ }
+ }
+ }
+ break;
+ default:
+ /* any other node: unsupported yet or bad. */
+ return 0;
+ }
+ }
+ return weight;
+}
+
+/**
+ * Calculate the parameter weights for transmitting the address of a local variable.
+ */
+static void analyze_irg_local_weights(inline_irg_env *env, ir_graph *irg)
+{
+ ir_entity *ent = get_irg_entity(irg);
+ ir_type *mtp;
+ int nparams, i, proj_nr;
+ ir_node *irg_args, *arg;
+
+ mtp = get_entity_type(ent);
+ nparams = get_method_n_params(mtp);
+
+ /* allocate a new array. currently used as 'analysed' flag */
+ env->local_weights = NEW_ARR_D(unsigned, &temp_obst, nparams);
+
+ /* If the method haven't parameters we have nothing to do. */
+ if (nparams <= 0)
+ return;
+
+ assure_irg_outs(irg);
+ irg_args = get_irg_args(irg);
+ for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
+ arg = get_irn_out(irg_args, i);
+ proj_nr = get_Proj_proj(arg);
+ env->local_weights[proj_nr] = calc_method_local_weight(arg);
+ }
+}
+
+/**
+ * Calculate the benefice for transmitting an local variable address.
+ * After inlining, the local variable might be transformed into a
+ * SSA variable by scalar_replacement().
+ */
+static unsigned get_method_local_adress_weight(ir_graph *callee, int pos)
+{
+ inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
+
+ if (env->local_weights != NULL) {
+ if (pos < ARR_LEN(env->local_weights))
+ return env->local_weights[pos];
+ return 0;
+ }
+
+ analyze_irg_local_weights(env, callee);
+
+ if (pos < ARR_LEN(env->local_weights))
+ return env->local_weights[pos];
+ return 0;
+}
+
+/**
+ * Calculate a benefice value for inlining the given call.
+ *
+ * @param call the call node we have to inspect
+ * @param callee the called graph
+ */
+static int calc_inline_benefice(call_entry *entry, ir_graph *callee)
+{
+ ir_node *call = entry->call;
+ ir_entity *ent = get_irg_entity(callee);
+ ir_node *frame_ptr;
+ ir_type *mtp;
+ int weight = 0;
+ int i, n_params, all_const;
+ unsigned cc, v;
+ irg_inline_property prop;
+
+ inline_irg_env *callee_env;
+
+ prop = get_irg_inline_property(callee);
+ if (prop == irg_inline_forbidden) {
+ DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n",
+ call, callee));
+ return entry->benefice = INT_MIN;
+ }
+
+ if (get_irg_additional_properties(callee) & mtp_property_noreturn) {
+ DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n",
+ call, callee));
+ return entry->benefice = INT_MIN;
+ }
+
+ /* costs for every passed parameter */
+ n_params = get_Call_n_params(call);
+ mtp = get_entity_type(ent);
+ cc = get_method_calling_convention(mtp);
+ if (cc & cc_reg_param) {
+ /* register parameter, smaller costs for register parameters */
+ int max_regs = cc & ~cc_bits;
+
+ if (max_regs < n_params)
+ weight += max_regs * 2 + (n_params - max_regs) * 5;
+ else
+ weight += n_params * 2;
+ } else {
+ /* parameters are passed an stack */
+ weight += 5 * n_params;
+ }
+
+ /* 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)) {
+ weight += get_method_param_weight(ent, i);
+ } 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)
+ entry->local_adr = 1;
+ }
+ }
+ }
+ entry->all_const = all_const;
+
+ callee_env = (inline_irg_env*)get_irg_link(callee);
+ if (callee_env->n_callers == 1 &&
+ callee != current_ir_graph &&
+ !entity_is_externally_visible(ent)) {
+ weight += 700;
+ }
+
+ /* 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 */
+ if (callee_env->n_nodes < 30 && !callee_env->recursive)
+ weight += 2000;
+
+ /* and finally for leaves: they do not increase the register pressure
+ because of callee safe registers */
+ if (callee_env->n_call_nodes == 0)
+ weight += 400;
+
+ /** it's important to inline inner loops first */
+ if (entry->loop_depth > 30)
+ weight += 30 * 1024;
+ else
+ weight += entry->loop_depth * 1024;
+
+ /*
+ * All arguments constant is probably a good sign, give an extra bonus
+ */
+ if (all_const)
+ weight += 1024;
+
+ return entry->benefice = weight;
+}
+
+static ir_graph **irgs;
+static int last_irg;
+
+/**
+ * Callgraph walker, collect all visited graphs.
+ */
+static void callgraph_walker(ir_graph *irg, void *data)
+{
+ (void) data;
+ irgs[last_irg++] = irg;
+}
+
+/**
+ * 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();
+
+ cgana(&arr_len, &free_methods);
+ xfree(free_methods);
+
+ compute_callgraph();
+
+ last_irg = 0;
+ irgs = XMALLOCNZ(ir_graph*, n_irgs);
+
+ callgraph_walk(NULL, callgraph_walker, NULL);
+ assert(n_irgs == last_irg);
+
+ 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);
+ 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));
+
+ 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 phiproj_computed = 0;
+ inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
+ call_entry *curr_call;
+ 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));
+ return;
+ }
+
+ current_ir_graph = irg;
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
+
+ /* put irgs into the pqueue */
+ pqueue = new_pqueue();
+
+ 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;
+ call_entry *curr_call = (call_entry*)pqueue_pop_front(pqueue);
+ ir_graph *callee = curr_call->callee;
+ ir_node *call_node = curr_call->call;
+ inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
+ 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) {
+ DB((dbg, LEVEL_2, "%+F: too big (%d) + %+F (%d)\n", irg,
+ env->n_nodes, callee, callee_env->n_nodes));
+ continue;
+ }
+
+ e = pmap_find(copied_graphs, callee);
+ if (e != NULL) {
+ int benefice = curr_call->benefice;
+ /*
+ * 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 = (ir_graph*)e->value;
+ callee_env = (inline_irg_env*)get_irg_link(callee);
+ }
+
+ if (current_ir_graph == callee) {
+ /*
+ * Recursive call: we cannot directly inline because we cannot
+ * walk the graph and change it. So we have to make a copy of
+ * the graph first.
+ */
+ 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;
+
+ 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
+ * sufficient to test this condition here.
+ */
+ copy = create_irg_copy(callee);
+
+ /* 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);
+
+ assure_cf_loop(copy);
+ wenv.x = callee_env;
+ wenv.ignore_callers = 1;
+ irg_walk_graph(copy, NULL, collect_calls2, &wenv);
+
+ /*
+ * Enter the entity of the original graph. This is needed
+ * for inline_method(). However, note that ent->irg still points
+ * to callee, NOT to copy.
+ */
+ set_irg_entity(copy, get_irg_entity(callee));
+
+ pmap_insert(copied_graphs, callee, copy);
+ callee = copy;
+
+ /* we have only one caller: the original graph */
+ callee_env->n_callers = 1;
+ callee_env->n_callers_orig = 1;
+ }
+ if (! phiproj_computed) {
+ phiproj_computed = 1;
+ collect_phiprojs(current_ir_graph);
+ }
+ did_inline = inline_method(call_node, callee);
+ if (!did_inline)
+ continue;
+
+ /* call was inlined, Phi/Projs for current graph must be recomputed */
+ phiproj_computed = 0;
+
+ /* remove it from the caller list */
+ list_del(&curr_call->list);
+
+ /* callee was inline. Append it's call list. */
+ env->got_inline = 1;
+ --env->n_call_nodes;
+
+ /* we just generate a bunch of new calls */
+ loop_depth = curr_call->loop_depth;
+ list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
+ inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
+ ir_node *new_call;
+ call_entry *new_entry;
+
+ /* after we have inlined callee, all called methods inside
+ * callee are now called once more */
+ ++penv->n_callers;
+
+ /* 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 = (ir_node*)get_irn_link(centry->call);
+ assert(is_Call(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);
+ }
+
+ env->n_call_nodes += callee_env->n_call_nodes;
+ 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.
+ */
+void inline_functions(unsigned maxsize, int inline_threshold,
+ opt_ptr after_inline_opt)
+{
+ inline_irg_env *env;
+ int i, n_irgs;
+ ir_graph *rem;
+ wenv_t wenv;
+ pmap *copied_graphs;
+ pmap_entry *pm_entry;
+ ir_graph **irgs;
+
+ rem = current_ir_graph;
+ obstack_init(&temp_obst);
+
+ irgs = create_irg_list();
+
+ /* a map for the copied graphs, used to inline recursive calls */
+ copied_graphs = pmap_create();
+
+ /* extend all irgs by a temporary data structure for inlining. */
+ n_irgs = get_irp_n_irgs();
+ for (i = 0; i < n_irgs; ++i)
+ set_irg_link(irgs[i], alloc_inline_irg_env());
+
+ /* Pre-compute information in temporary data structure. */
+ wenv.ignore_runtime = 0;
+ wenv.ignore_callers = 0;
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = irgs[i];
+
+ free_callee_info(irg);
+
+ wenv.x = (inline_irg_env*)get_irg_link(irg);
+ assure_cf_loop(irg);
+ irg_walk_graph(irg, NULL, collect_calls2, &wenv);
+ }
+
+ /* -- and now inline. -- */
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = irgs[i];
+
+ inline_into(irg, maxsize, inline_threshold, copied_graphs);
+ }
+
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = irgs[i];
+
+ env = (inline_irg_env*)get_irg_link(irg);
+ if (env->got_inline && after_inline_opt != NULL) {
+ /* this irg got calls inlined: optimize it */
+ after_inline_opt(irg);
+ }
+ if (env->got_inline || (env->n_callers_orig != env->n_callers)) {
+ DB((dbg, LEVEL_1, "Nodes:%3d ->%3d, calls:%3d ->%3d, callers:%3d ->%3d, -- %s\n",