* @author Michael Beck, Goetz Lindenmaier
* @version $Id$
*/
-#ifdef HAVE_CONFIG_H
-# include "config.h"
-#endif
+#include "config.h"
#include <limits.h>
#include <assert.h>
#include "irgmod.h"
#include "irgwalk.h"
-#include "adt/array.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"
* 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;
}
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);
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. */
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;
* 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;
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;
*/
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
* 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).
*
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);
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));
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;
/* --
/* -- 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) {
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));
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 */
}
}
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;
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);
}
/********************************************************************/
-/* 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 call_entry;
-struct _call_entry {
- 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 */
- unsigned local_adr : 1;
-};
+typedef struct _call_entry {
+ 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. */
- call_entry *head; /**< the head of the call entry list */
- call_entry *tail; /**< the tail of 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;
/**
* Walker: Collect all calls to known graphs inside a graph.
*/
static void collect_calls(ir_node *call, void *env) {
+ (void) env;
if (is_Call(call)) {
ir_graph *called_irg = get_call_called_irg(call);
call_entry *entry = obstack_alloc(&ienv->obst, sizeof(*entry));
entry->call = call;
entry->callee = called_irg;
- entry->next = NULL;
entry->loop_depth = 0;
+ entry->benefice = 0;
+ entry->local_adr = 0;
+ entry->all_const = 0;
- if (ienv->tail == NULL)
- ienv->head = entry;
- else
- ienv->tail->next = entry;
- ienv->tail = entry;
+ list_add_tail(&entry->list, &ienv->calls);
}
}
}
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);
- env.head = env.tail = NULL;
+ INIT_LIST_HEAD(&env.calls);
irg_walk_graph(irg, NULL, collect_calls, &env);
- if (env.head != NULL) {
+ 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);
- for (entry = env.head; entry != NULL; entry = entry->next) {
+ list_for_each_entry(call_entry, entry, &env.calls, list) {
ir_graph *callee = entry->callee;
irg_inline_property prop = get_irg_inline_property(callee);
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;
* Environment for inlining irgs.
*/
typedef struct {
- unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
- unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */
- unsigned n_nodes_orig; /**< for statistics */
- unsigned n_call_nodes; /**< Number of Call nodes in the graph. */
- unsigned n_call_nodes_orig; /**< for statistics */
- unsigned n_callers; /**< Number of known graphs that call this graphs. */
- unsigned 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. */
+ list_head calls; /**< List of of all call nodes in this graph. */
+ unsigned *local_weights; /**< Once allocated, the beneficial weight for transmitting local addresses. */
+ unsigned n_nodes; /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
+ unsigned n_blocks; /**< Number of Blocks in graph without Start and End block. */
+ unsigned n_nodes_orig; /**< for statistics */
+ unsigned n_call_nodes; /**< Number of Call nodes in the graph. */
+ unsigned n_call_nodes_orig; /**< for statistics */
+ unsigned n_callers; /**< Number of known graphs that call this graphs. */
+ unsigned 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 an inlined function got the address of a local variable. */
+ unsigned recursive:1; /**< Set, if this function is self recursive. */
} inline_irg_env;
/**
*/
static inline_irg_env *alloc_inline_irg_env(void) {
inline_irg_env *env = obstack_alloc(&temp_obst, sizeof(*env));
+ INIT_LIST_HEAD(&env->calls);
+ env->local_weights = NULL;
env->n_nodes = -2; /* do not count count Start, End */
env->n_blocks = -2; /* do not count count Start, End Block */
env->n_nodes_orig = -2; /* do not count Start, End */
- env->call_head = NULL;
- env->call_tail = NULL;
env->n_call_nodes = 0;
env->n_call_nodes_orig = 0;
env->n_callers = 0;
env->got_inline = 0;
env->local_vars = 0;
env->recursive = 0;
- env->local_weights = NULL;
return env;
}
entry = obstack_alloc(&temp_obst, sizeof(*entry));
entry->call = call;
entry->callee = callee;
- entry->next = NULL;
entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth;
+ entry->benefice = 0;
+ entry->local_adr = 0;
+ entry->all_const = 0;
- entry->next = x->call_head;
- x->call_head = entry;
-
- if (entry->next == NULL) {
- /* keep tail up to date */
- x->call_tail = entry;
- }
+ list_add_tail(&entry->list, &x->calls);
}
}
* 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;
}
* 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;
}
/**
- * Append the nodes of the list src to the nodes of the list in environment dst.
+ * Duplicate a call entry.
+ *
+ * @param entry the original entry to duplicate
+ * @param new_call the new call node
+ * @param loop_depth_delta
+ * delta value for the loop depth
*/
-static void append_call_list(inline_irg_env *dst, call_entry *src) {
- call_entry *entry, *nentry;
-
- /* 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. */
- 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->call_tail->next = nentry;
- dst->call_tail = nentry;
- }
-}
-
static call_entry *duplicate_call_entry(const call_entry *entry,
- int loop_depth_delta, ir_node *new_call)
-{
+ ir_node *new_call, int loop_depth_delta) {
call_entry *nentry = obstack_alloc(&temp_obst, sizeof(*nentry));
nentry->call = new_call;
nentry->callee = entry->callee;
- nentry->next = NULL;
+ nentry->benefice = entry->benefice;
nentry->loop_depth = entry->loop_depth + loop_depth_delta;
+ nentry->local_adr = entry->local_adr;
+ nentry->all_const = entry->all_const;
return nentry;
}
+/**
+ * Append all call nodes of the source environment to the nodes of in the destination
+ * environment.
+ *
+ * @param dst destination environment
+ * @param src source environment
+ * @param loop_depth the loop depth of the call that is replaced by the src list
+ */
+static void append_call_list(inline_irg_env *dst, inline_irg_env *src, int loop_depth) {
+ call_entry *entry, *nentry;
+
+ /* 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. */
+ list_for_each_entry(call_entry, entry, &src->calls, list) {
+ nentry = duplicate_call_entry(entry, get_irn_link(entry->call), loop_depth);
+ list_add_tail(&nentry->list, &dst->calls);
+ }
+ dst->n_call_nodes += src->n_call_nodes;
+ dst->n_nodes += src->n_nodes;
+}
+
/*
* Inlines small leave methods at call sites where the called address comes
* from a Const node that references the entity representing the called
* size are inlined.
*/
void inline_leave_functions(unsigned maxsize, unsigned leavesize,
- unsigned size, int ignore_runtime)
+ unsigned size, int ignore_runtime)
{
inline_irg_env *env;
ir_graph *irg;
ir_graph *rem;
int did_inline;
wenv_t wenv;
- call_entry *entry, *tail;
+ call_entry *entry, *next;
const call_entry *centry;
pmap *copied_graphs;
pmap_entry *pm_entry;
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) {
int phiproj_computed = 0;
current_ir_graph = get_irp_irg(i);
- env = (inline_irg_env *)get_irg_link(current_ir_graph);
+ env = get_irg_link(current_ir_graph);
- tail = NULL;
- for (entry = env->call_head; entry != NULL; entry = entry->next) {
+ 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;
did_inline = inline_method(call, callee);
if (did_inline) {
- inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);
+ 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 */
--callee_env->n_callers;
/* remove this call from the list */
- if (tail != NULL)
- tail->next = entry->next;
- else
- env->call_head = entry->next;
+ list_del(&entry->list);
continue;
}
}
- tail = entry;
}
- env->call_tail = tail;
+ ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
}
} while (did_inline);
int phiproj_computed = 0;
current_ir_graph = get_irp_irg(i);
- env = (inline_irg_env *)get_irg_link(current_ir_graph);
+ 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 */
- tail = NULL;
- for (entry = env->call_head; entry != NULL; entry = entry->next) {
+ list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
irg_inline_property prop;
ir_graph *callee;
pmap_entry *e;
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
/* 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);
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. */
env->got_inline = 1;
--env->n_call_nodes;
- append_call_list(env, callee_env->call_head);
- env->n_call_nodes += callee_env->n_call_nodes;
- env->n_nodes += callee_env->n_nodes;
+ append_call_list(env, callee_env, entry->loop_depth);
--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) {
+ list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
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;
+ list_del(&entry->list);
continue;
}
}
- tail = entry;
}
- env->call_tail = tail;
+ ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
}
for (i = 0; i < n_irgs; ++i) {
irg = get_irp_irg(i);
- env = (inline_irg_env *)get_irg_link(irg);
+ env = get_irg_link(irg);
if (env->got_inline) {
optimize_graph_df(irg);
*
* @param call the call node we have to inspect
* @param callee the called graph
- * @param local_adr set after return if an address of a local variable is
- * transmitted as a parameter
*/
-static int calc_inline_benefice(const call_entry *entry, ir_graph *callee,
- unsigned *local_adr)
+static int calc_inline_benefice(call_entry *entry, ir_graph *callee)
{
ir_node *call = entry->call;
ir_entity *ent = get_irg_entity(callee);
if (prop == irg_inline_forbidden) {
DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n",
call, callee));
- return INT_MIN;
+ return entry->benefice = INT_MIN;
}
- if ( (get_irg_additional_properties(callee)
- | get_entity_additional_properties(ent))
- & (mtp_property_noreturn | mtp_property_weak)) {
+ if (get_irg_additional_properties(callee) & (mtp_property_noreturn | mtp_property_weak)) {
DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n",
call, callee));
- return INT_MIN;
+ return entry->benefice = INT_MIN;
}
/* costs for every passed parameter */
v = get_method_local_adress_weight(callee, i);
weight += v;
if (v > 0)
- *local_adr = 1;
+ entry->local_adr = 1;
}
}
}
+ entry->all_const = all_const;
callee_env = get_irg_link(callee);
- if (callee_env->n_callers == 1
- && callee != current_ir_graph
- && get_entity_visibility(ent) == visibility_local) {
+ if (callee_env->n_callers == 1 &&
+ callee != current_ir_graph &&
+ get_entity_visibility(ent) == visibility_local) {
weight += 700;
}
if (callee_env->n_call_nodes == 0)
weight += 400;
- /*
- * 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 -= 2000;
-
/** it's important to inline inner loops first */
if (entry->loop_depth > 30)
weight += 30 * 1024;
* All arguments constant is probably a good sign, give an extra bonus
*/
if (all_const)
- weight += 1308;
+ weight += 1024;
- return weight;
+ return entry->benefice = weight;
}
static ir_graph **irgs;
static int last_irg;
-static void callgraph_walker(ir_graph *irg, void *data)
-{
+/**
+ * Callgraph walker, collect all visited graphs.
+ */
+static void callgraph_walker(ir_graph *irg, void *data) {
(void) data;
irgs[last_irg++] = irg;
}
-static ir_graph **create_irg_list(void)
-{
+/**
+ * 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();
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);
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);
- unsigned local_adr;
- int benefice;
-
- benefice = calc_inline_benefice(call, callee, &local_adr);
- call->local_adr = local_adr;
+ 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));
+ 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);
}
+/**
+ * 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 inline_threshold, pmap *copied_graphs)
{
int phiproj_computed = 0;
inline_irg_env *env = get_irg_link(irg);
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();
- for (curr_call = env->call_head; curr_call != NULL;
- curr_call = curr_call->next) {
-
- if (is_Tuple(curr_call->call))
- continue;
+ 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;
- pmap_entry *e;
- call_entry *curr_call = pqueue_pop_front(pqueue);
- ir_graph *callee = curr_call->callee;
- ir_node *call_node = curr_call->call;
- irg_inline_property prop = get_irg_inline_property(callee);
- const call_entry *centry;
+ int did_inline;
+ call_entry *curr_call = pqueue_pop_front(pqueue);
+ ir_graph *callee = curr_call->callee;
+ ir_node *call_node = curr_call->call;
inline_irg_env *callee_env = get_irg_link(callee);
- int depth = curr_call->loop_depth;
+ 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) {
+ 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;
/*
- * Remap callee if we have a copy.
- * FIXME: Should we do this only for recursive Calls ?
- */
- callee = e->value;
+ * 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 = e->value;
+ callee_env = get_irg_link(callee);
}
if (current_ir_graph == callee) {
* 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;
+ 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.
/* create_irg_copy() destroys the Proj links, recompute them */
phiproj_computed = 0;
- /* allocate new environment */
+ 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);
if (!did_inline)
continue;
- /* was inlined, must be recomputed */
+ /* call was inlined, Phi/Projs for current graph 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;
- }
+ /* 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 */
- for (centry = callee_env->call_head; centry != NULL;
- centry = centry->next) {
- /* 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. */
+ loop_depth = curr_call->loop_depth;
+ list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
+ inline_irg_env *penv = get_irg_link(centry->callee);
+ ir_node *new_call;
+ call_entry *new_entry;
- ir_node *new_call = get_irn_link(centry->call);
- call_entry *new_entry;
+ /* after we have inlined callee, all called methods inside
+ * callee are now called once more */
+ ++penv->n_callers;
- if (!is_Call(new_call))
- continue;
+ /* 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 = get_irn_link(centry->call);
+ assert(is_Call(new_call));
- new_entry = duplicate_call_entry(centry, depth, 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_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.
*/
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) {
free_callee_info(irg);
- wenv.x = get_irg_link(irg);
+ wenv.x = get_irg_link(irg);
assure_cf_loop(irg);
irg_walk_graph(irg, NULL, collect_calls2, &wenv);
}
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)) {