+ /* 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;
+}
+
+/**
+ * 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 = 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.
+ */
+static int calc_inline_benefice(ir_node *call, ir_graph *callee, unsigned *local_adr) {
+ 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;
+
+ inline_irg_env *curr_env, *callee_env;
+
+ if (get_entity_additional_properties(ent) & mtp_property_noreturn) {
+ /* do NOT inline noreturn calls */
+ return 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)
+ *local_adr = 1;
+ }
+ }
+ }
+
+ callee_env = get_irg_link(callee);
+ if (get_entity_visibility(ent) == visibility_local &&
+ callee_env->n_callers_orig == 1 &&
+ callee != current_ir_graph) {
+ /* we are the only caller, give big bonus */
+ weight += 5000;
+ }
+
+ /* do not inline big functions */
+ weight -= callee_env->n_nodes;
+
+ /* reduce the benefice if the current function is already big */
+ curr_env = get_irg_link(current_ir_graph);
+ 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 benefice value for every call and inlines
+ * those calls with a value higher than the 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 *curr_call, **last_call;
+ const call_entry *centry;
+ pmap *copied_graphs;
+ pmap_entry *pm_entry;
+
+ rem = current_ir_graph;
+ obstack_init(&temp_obst);
+
+ /* 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(get_irp_irg(i), alloc_inline_irg_env());
+
+ /* Precompute information in temporary data structure. */
+ wenv.ignore_runtime = 0;
+ wenv.ignore_callers = 0;
+ for (i = 0; i < n_irgs; ++i) {
+ ir_graph *irg = get_irp_irg(i);
+
+ assert(get_irg_phase_state(irg) != phase_building);
+ free_callee_info(irg);
+
+ wenv.x = get_irg_link(irg);
+ wenv.last_call = NULL;
+ assure_cf_loop(irg);
+ irg_walk_graph(irg, NULL, collect_calls2, &wenv);
+ }
+
+ /* -- and now inline. -- */
+ for (i = 0; i < n_irgs; ++i) {
+ int phiproj_computed = 0;
+ ir_node *call;
+ ir_graph *irg = get_irp_irg(i);
+
+ current_ir_graph = irg;
+ env = get_irg_link(irg);
+
+ /* note that the list of possible calls is updated during the process */
+ 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;
+
+ if (env->n_nodes > maxsize) break;
+
+ 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 ?
+ */
+ 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) {
+ /*
+ * 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.
+ */
+
+ inline_irg_env *callee_env;
+ ir_graph *copy;
+
+ /*
+ * 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;
+
+ /* allocate 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, callee);
+ if (did_inline) {
+ inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
+
+ /* 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;
+ 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;
+
+ /* remove the current call entry from the list */
+ *last_call = curr_call;
+ continue;
+ }
+ }
+ last_call = &curr_call->next;
+ curr_call = curr_call->next;
+ }
+
+ if (env->got_inline) {
+ /* this irg got calls inlined: optimize it */
+
+ /* scalar replacement does not work well with Tuple nodes, so optimize them away */