X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fproc_cloning.c;h=2d359206fa697a8d5871c35cf338682011a38d2a;hb=4cbdab238c1bd78c11cda18f18f8a4ab676e5c56;hp=8b9093142bf1c0a81ae3fcc41b0a19294d2622c1;hpb=0fbcef83aa6060534172bb13e71cdadb04428806;p=libfirm diff --git a/ir/opt/proc_cloning.c b/ir/opt/proc_cloning.c index 8b9093142..2d359206f 100644 --- a/ir/opt/proc_cloning.c +++ b/ir/opt/proc_cloning.c @@ -1,28 +1,13 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. - * * This file is part of libFirm. - * - * This file may be distributed and/or modified under the terms of the - * GNU General Public License version 2 as published by the Free Software - * Foundation and appearing in the file LICENSE.GPL included in the - * packaging of this file. - * - * Licensees holding valid libFirm Professional Edition licenses may use - * this file in accordance with the libFirm Commercial License. - * Agreement provided with the Software. - * - * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE - * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE. + * Copyright (C) 2012 University of Karlsruhe. */ /** * @file * @brief Procedure cloning. * @author Beyhan Veliev, Michael Beck - * @version $Id$ - * @summary + * @brief * * The purpose is first to find and analyze functions, that are called * with constant parameter(s). @@ -49,16 +34,17 @@ #include "irtools.h" #include "irgmod.h" #include "array_t.h" +#include "irpass_t.h" /** * This struct contains the information quadruple for a Call, which we need to * decide if this function must be cloned. */ typedef struct quadruple { - ir_entity *ent; /**< The entity of our Call. */ - int pos; /**< Position of a constant argument of our Call. */ - tarval *tv; /**< The tarval of this argument if Const node. */ - ir_node **calls; /**< The list of all calls with the same characteristics */ + ir_entity *ent; /**< The entity of our Call. */ + size_t pos; /**< Position of a constant argument of our Call. */ + ir_tarval *tv; /**< The tarval of this argument if Const node. */ + ir_node **calls; /**< The list of all calls with the same characteristics */ } quadruple_t; /** @@ -81,9 +67,10 @@ typedef struct q_set { * * @return zero if they are identically, non-zero else */ -static int entry_cmp(const void *elt, const void *key) { - const entry_t *e1 = elt; - const entry_t *e2 = key; +static int entry_cmp(const void *elt, const void *key) +{ + const entry_t *e1 = (const entry_t*)elt; + const entry_t *e2 = (const entry_t*)key; return (e1->q.ent != e2->q.ent) || (e1->q.pos != e2->q.pos) || (e1->q.tv != e2->q.tv); } @@ -93,14 +80,16 @@ static int entry_cmp(const void *elt, const void *key) { * * @param entry The element to be hashed. */ -static int hash_entry(const entry_t *entry) { - return HASH_PTR(entry->q.ent) ^ HASH_PTR(entry->q.tv) ^ (entry->q.pos * 9); +static unsigned hash_entry(const entry_t *entry) +{ + return hash_ptr(entry->q.ent) ^ hash_ptr(entry->q.tv) ^ (unsigned)(entry->q.pos * 9); } /** * Free memory associated with a quadruplet. */ -static void kill_entry(entry_t *entry) { +static void kill_entry(entry_t *entry) +{ if (entry->q.calls) { DEL_ARR_F(entry->q.calls); entry->q.calls = NULL; @@ -114,34 +103,31 @@ static void kill_entry(entry_t *entry) { * @param callee The entity of the callee * @param hmap The quadruple-set containing the calls with constant parameters */ -static void process_call(ir_node *call, ir_entity *callee, q_set *hmap) { - ir_type *mtp; +static void process_call(ir_node *call, ir_entity *callee, q_set *hmap) +{ entry_t *key, *entry; ir_node *call_param; - int i, n_params; + size_t i, n_params; n_params = get_Call_n_params(call); - /* Beware: we cannot clone variadic parameters as well as the + /* TODO + * Beware: we cannot clone variadic parameters as well as the * last non-variadic one, which might be needed for the va_start() * magic */ - mtp = get_Call_type(call); - if (get_method_variadicity(mtp) != variadicity_non_variadic) { - n_params = get_method_first_variadic_param_index(mtp) - 1; - } /* In this for loop we collect the calls, that have an constant parameter. */ - for (i = n_params - 1; i >= 0; --i) { - call_param = get_Call_param(call, i); + for (i = n_params; i > 0;) { + call_param = get_Call_param(call, --i); if (is_Const(call_param)) { /* we have found a Call to collect and we save the informations, which we need.*/ if (! hmap->map) hmap->map = new_pset(entry_cmp, 8); - key = obstack_alloc(&hmap->obst, sizeof(*key)); + key = OALLOC(&hmap->obst, entry_t); key->q.ent = callee; key->q.pos = i; @@ -151,7 +137,7 @@ static void process_call(ir_node *call, ir_entity *callee, q_set *hmap) { key->next = NULL; /* We insert our information in the set, where we collect the calls.*/ - entry = pset_insert(hmap->map, key, hash_entry(key)); + entry = (entry_t*)pset_insert(hmap->map, key, hash_entry(key)); if (entry != key) obstack_free(&hmap->obst, key); @@ -172,8 +158,9 @@ static void process_call(ir_node *call, ir_entity *callee, q_set *hmap) { * @param call A ir_node to be checked. * @param env The quadruple-set containing the calls with constant parameters */ -static void collect_irg_calls(ir_node *call, void *env) { - q_set *hmap = env; +static void collect_irg_calls(ir_node *call, void *env) +{ + q_set *hmap = (q_set*)env; ir_node *call_ptr; ir_entity *callee; @@ -181,17 +168,17 @@ static void collect_irg_calls(ir_node *call, void *env) { if (is_Call(call)) { call_ptr = get_Call_ptr(call); - if (! is_Global(call_ptr)) + if (! is_SymConst_addr_ent(call_ptr)) return; - callee = get_Global_entity(call_ptr); + callee = get_SymConst_entity(call_ptr); - /* we can only clone calls to existing entities */ - if (get_entity_visibility(callee) == visibility_external_allocated) + /* we don't know which function gets finally bound to a weak symbol */ + if (get_entity_linkage(callee) & IR_LINKAGE_WEAK) return; - /* we cannot clone calls to weak functions */ - if (get_entity_additional_properties(callee) & mtp_property_weak) + /* we can only clone calls to existing entities */ + if (get_entity_irg(callee) == NULL) return; process_call(call, callee, hmap); @@ -207,12 +194,13 @@ static void collect_irg_calls(ir_node *call, void *env) { * @param pos The "pos" from our quadruplet. * @param nr A counter for the clones. */ -static ident *get_clone_ident(ident *id, int pos, unsigned nr) { +static ident *get_clone_ident(ident *id, size_t pos, size_t nr) +{ char clone_postfix[32]; - snprintf(clone_postfix, sizeof(clone_postfix), "_cl_%d_%u", pos, nr); + ir_snprintf(clone_postfix, sizeof(clone_postfix), "_cl_%zu_%zu", pos, nr); - return mangle(id, new_id_from_str(clone_postfix)); + return id_mangle(id, new_id_from_str(clone_postfix)); } /** @@ -223,19 +211,19 @@ static ident *get_clone_ident(ident *id, int pos, unsigned nr) { * @param irn A node from the original method graph. * @param env The clone graph. */ -static void copy_nodes(ir_node *irn, void *env) { - ir_node *arg, *irg_args, *irn_copy; - int proj_nr; - ir_graph *clone_irg = env; - - arg = get_irg_link(clone_irg); - irg_args = get_Proj_pred(arg); +static void copy_nodes(ir_node *irn, void *env) +{ + ir_graph *clone_irg = (ir_graph*)env; + ir_node *arg = (ir_node*)get_irg_link(clone_irg); + ir_node *irg_args = get_Proj_pred(arg); + ir_node *irn_copy; + long proj_nr; /* Copy all nodes except the arg. */ if (irn != arg) copy_irn_to_irg(irn, clone_irg); - irn_copy = get_irn_link(irn); + irn_copy = (ir_node*)get_irn_link(irn); /* Fix argument numbers */ if (is_Proj(irn) && get_Proj_pred(irn) == irg_args) { @@ -250,40 +238,42 @@ static void copy_nodes(ir_node *irn, void *env) { * The copied nodes are set as link of their original nodes. The links of * "irn" predecessors are the predecessors of copied node. */ -static void set_preds(ir_node *irn, void *env) { - int i; - ir_node *irn_copy, *pred, *arg; - ir_graph *clone_irg = env; +static void set_preds(ir_node *irn, void *env) +{ + ir_graph *clone_irg = (ir_graph*)env; + ir_node *arg = (ir_node*)get_irg_link(clone_irg); + int i; + ir_node *irn_copy; + ir_node *pred; - arg = get_irg_link(clone_irg); /* Arg is the method argument, that we have replaced by a constant.*/ if (arg == irn) return; - irn_copy = get_irn_link(irn); + irn_copy = (ir_node*)get_irn_link(irn); if (is_Block(irn)) { - set_Block_MacroBlock(irn_copy, get_irn_link(get_Block_MacroBlock(irn))); - for (i = get_Block_n_cfgpreds(irn) - 1; i >= 0; i--) { + ir_graph *const irg = get_Block_irg(irn); + for (i = get_Block_n_cfgpreds(irn) - 1; i >= 0; --i) { pred = get_Block_cfgpred(irn, i); /* "End" block must be handled extra, because it is not matured.*/ - if (get_irg_end_block(current_ir_graph) == irn) - add_immBlock_pred(get_irg_end_block(clone_irg), get_irn_link(pred)); + if (get_irg_end_block(irg) == irn) + add_immBlock_pred(get_irg_end_block(clone_irg), (ir_node*)get_irn_link(pred)); else - set_Block_cfgpred(irn_copy, i, get_irn_link(pred)); + set_Block_cfgpred(irn_copy, i, (ir_node*)get_irn_link(pred)); } } else { /* First we set the block our copy if it is not a block.*/ - set_nodes_block(irn_copy, get_irn_link(get_nodes_block(irn))); + set_nodes_block(irn_copy, (ir_node*)get_irn_link(get_nodes_block(irn))); if (is_End(irn)) { /* Handle the keep-alives. This must be done separately, because the End node was NOT copied */ for (i = 0; i < get_End_n_keepalives(irn); ++i) - add_End_keepalive(irn_copy, get_irn_link(get_End_keepalive(irn, i))); + add_End_keepalive(irn_copy, (ir_node*)get_irn_link(get_End_keepalive(irn, i))); } else { for (i = get_irn_arity(irn) - 1; i >= 0; i--) { pred = get_irn_n(irn, i); - set_irn_n(irn_copy, i, get_irn_link(pred)); + set_irn_n(irn_copy, i, (ir_node*)get_irn_link(pred)); } } } @@ -295,21 +285,21 @@ static void set_preds(ir_node *irn, void *env) { * @param irg irg that must be cloned. * @param pos The position of the argument. */ -static ir_node *get_irg_arg(ir_graph *irg, int pos) { +static ir_node *get_irg_arg(ir_graph *irg, size_t pos) +{ ir_node *irg_args = get_irg_args(irg), *arg = NULL; - int i; /* Call algorithm that computes the out edges */ assure_irg_outs(irg); /* Search the argument with the number pos.*/ - for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) { + for (unsigned i = get_irn_n_outs(irg_args); i-- > 0; ) { ir_node *proj = get_irn_out(irg_args, i); - if (pos == get_Proj_proj(proj)) { + if ((int)pos == get_Proj_proj(proj)) { if (arg) { /* * More than one arg node found: - * We rely on the fact the only one arg exists, so do + * We rely on the fact that only one arg exists, so do * a cheap CSE in this case. */ set_irn_out(irg_args, i, arg, 0); @@ -329,7 +319,8 @@ static ir_node *get_irg_arg(ir_graph *irg, int pos) { * @param ent The entity of the method that must be cloned. * @param q Our quadruplet. */ -static void create_clone_proc_irg(ir_entity *ent, quadruple_t *q) { +static void create_clone_proc_irg(ir_entity *ent, const quadruple_t *q) +{ ir_graph *method_irg, *clone_irg; ir_node *arg, *const_arg; @@ -340,9 +331,7 @@ static void create_clone_proc_irg(ir_entity *ent, quadruple_t *q) { arg = get_irg_arg(get_entity_irg(q->ent), q->pos); /* we will replace the argument in position "q->pos" by this constant. */ - const_arg = new_r_Const_type( - clone_irg, get_nodes_block(arg), get_irn_mode(arg), q->tv, - get_method_param_type(get_entity_type(q->ent), q->pos)); + const_arg = new_r_Const(clone_irg, q->tv); /* args copy in the cloned graph will be the const. */ set_irn_link(arg, const_arg); @@ -367,27 +356,26 @@ static void create_clone_proc_irg(ir_entity *ent, quadruple_t *q) { * @param ent The entity of the clone. * @param nr A pointer to the counter of clones. **/ -static void change_entity_type(quadruple_t *q, ir_entity *ent, unsigned *nr) { +static void change_entity_type(const quadruple_t *q, ir_entity *ent) +{ ir_type *mtp, *new_mtp, *tp; - ident *tp_name; - int i, j, n_params, n_ress; + size_t i, j, n_params, n_ress; mtp = get_entity_type(q->ent); - tp_name = get_clone_ident(get_type_ident(mtp), q->pos, (*nr)++); n_params = get_method_n_params(mtp); n_ress = get_method_n_ress(mtp); /* Create the new type for our clone. It must have one parameter less then the original.*/ - new_mtp = new_type_method(tp_name, n_params - 1, n_ress); + new_mtp = new_type_method(n_params - 1, n_ress); /* We must set the type of the methods parameters.*/ for (i = j = 0; i < n_params; ++i) { - if (i == q->pos) - /* This is the position of the argument, that we have - replaced. */ - continue; - + if (i == q->pos) { + /* This is the position of the argument, that we have + replaced. */ + continue; + } tp = get_method_param_type(mtp, i); set_method_param_type(new_mtp, j++, tp); } @@ -404,13 +392,12 @@ static void change_entity_type(quadruple_t *q, ir_entity *ent, unsigned *nr) { * * @param q Contains information for the method to clone. */ -static ir_entity *clone_method(quadruple_t *q) { +static ir_entity *clone_method(const quadruple_t *q) +{ ir_entity *new_entity; ident *clone_ident; - ir_graph *rem; - symconst_symbol sym; /* A counter for the clones.*/ - static unsigned nr = 0; + static size_t nr = 0; /* We get a new ident for our clone method.*/ clone_ident = get_clone_ident(get_entity_ident(q->ent), q->pos, nr); @@ -418,24 +405,17 @@ static ir_entity *clone_method(quadruple_t *q) { new_entity = copy_entity_name(q->ent, clone_ident); /* a cloned entity is always local */ - set_entity_visibility(new_entity, visibility_local); + set_entity_visibility(new_entity, ir_visibility_local); /* set a ld name here: Should we mangle this ? */ set_entity_ld_ident(new_entity, get_entity_ident(new_entity)); /* set a new type here. */ - change_entity_type(q, new_entity, &nr); + change_entity_type(q, new_entity); /* We need now a new ir_graph for our clone method. */ create_clone_proc_irg(new_entity, q); - /* We must set the atomic value of our "new_entity". */ - sym.entity_p = new_entity; - rem = current_ir_graph; - current_ir_graph = get_const_code_irg(); - new_entity->value = new_SymConst(mode_P_code, sym, symconst_addr_ent); - current_ir_graph = rem; - /* The "new_entity" don't have this information. */ new_entity->attr.mtd_attr.param_access = NULL; new_entity->attr.mtd_attr.param_weight = NULL; @@ -450,30 +430,29 @@ static ir_entity *clone_method(quadruple_t *q) { * @param new_entity The entity of the cloned function. * @param pos The position of the replaced parameter of this call. **/ -static ir_node *new_cl_Call(ir_node *call, ir_entity *new_entity, int pos) { +static ir_node *new_cl_Call(ir_node *call, ir_entity *new_entity, size_t pos) +{ ir_node **in; - ir_type *mtp; - int i, n_params, new_params = 0; + size_t i, n_params, new_params = 0; ir_node *callee; symconst_symbol sym; ir_graph *irg = get_irn_irg(call); ir_node *bl = get_nodes_block(call); sym.entity_p = new_entity; - callee = new_r_SymConst(irg, bl, mode_P_code, sym, symconst_addr_ent); + callee = new_r_SymConst(irg, mode_P_code, sym, symconst_addr_ent); - mtp = get_entity_type(new_entity); n_params = get_Call_n_params(call); NEW_ARR_A(ir_node *, in, n_params - 1); /* we save the parameters of the new call in the array "in" without the * parameter in position "pos", that is replaced with a constant.*/ - for (i = 0; i < n_params; i++){ + for (i = 0; i < n_params; ++i) { if (pos != i) in[new_params++] = get_Call_param(call, i); } /* Create and return the new Call. */ - return new_r_Call(irg, bl, get_Call_mem(call), + return new_r_Call(bl, get_Call_mem(call), callee, n_params - 1, in, get_entity_type(new_entity)); } @@ -484,10 +463,11 @@ static ir_node *new_cl_Call(ir_node *call, ir_entity *new_entity, int pos) { * @param cloned_ent The entity of the new function that must be called * from the new Call. */ -static void exchange_calls(quadruple_t *q, ir_entity *cloned_ent) { - int pos = q->pos; +static void exchange_calls(quadruple_t *q, ir_entity *cloned_ent) +{ + size_t pos = q->pos; ir_node *new_call, *call; - int i; + size_t i; /* We iterate the list of the "call".*/ for (i = 0; i < ARR_LEN(q->calls); ++i) { @@ -505,7 +485,8 @@ static void exchange_calls(quadruple_t *q, ir_entity *cloned_ent) { * We save one instruction in every caller and param_weight instructions * in the callee. */ -static float calculate_weight(const entry_t *entry) { +static float calculate_weight(const entry_t *entry) +{ return ARR_LEN(entry->q.calls) * (float)(get_method_param_weight(entry->q.ent, entry->q.pos) + 1); } @@ -515,10 +496,10 @@ static float calculate_weight(const entry_t *entry) { * the next cloned entity may get invalid, so we have to check * them and may even update the list of heavy uses. */ -static void reorder_weights(q_set *hmap, float threshold) { +static void reorder_weights(q_set *hmap, float threshold) +{ entry_t **adr, *p, *entry; - int i, len; - ir_entity *callee; + size_t i, len; restart: entry = hmap->heavy_uses; @@ -534,9 +515,8 @@ restart: /* we know, that a SymConst is here */ ptr = get_Call_ptr(call); - assert(is_SymConst(ptr)); - callee = get_SymConst_entity(ptr); + ir_entity *const callee = get_SymConst_entity(ptr); if (callee != entry->q.ent) { /* * This call is already changed because of a previous @@ -575,7 +555,6 @@ restart: hmap->heavy_uses = entry->next; entry->next = *adr; *adr = entry; - entry = hmap->heavy_uses; /* we have changed the list, check the next one */ goto restart; @@ -587,19 +566,24 @@ restart: * call(..., Const, ...). If the weight is bigger than threshold, * clone the entity and fix the calls. */ -void proc_cloning(float threshold) { - entry_t *entry = NULL, *p; - ir_graph *irg; - int i; +void proc_cloning(float threshold) +{ + entry_t *p; + size_t i, n; q_set hmap; + DEBUG_ONLY(firm_dbg_module_t *dbg;) + + /* register a debug mask */ + FIRM_DBG_REGISTER(dbg, "firm.opt.proc_cloning"); + obstack_init(&hmap.obst); hmap.map = NULL; hmap.heavy_uses = NULL; /* initially fill our map by visiting all irgs */ - for (i = get_irp_n_irgs() - 1; i >= 0; --i) { - irg = get_irp_irg(i); + for (i = 0, n = get_irp_n_irgs(); i < n; ++i) { + ir_graph *irg = get_irp_irg(i); irg_walk_graph(irg, collect_irg_calls, NULL, &hmap); } @@ -611,7 +595,7 @@ void proc_cloning(float threshold) { /* We iterate the set and arrange the element of the set in a list. The elements are arranged dependent of their value descending.*/ if (hmap.map) { - foreach_pset(hmap.map, entry) { + foreach_pset(hmap.map, entry_t, entry) { entry->weight = calculate_weight(entry); /* @@ -647,18 +631,22 @@ void proc_cloning(float threshold) { hmap.map = NULL; } +#ifdef DEBUG_libfirm /* Print some information about the list. */ - printf("-----------------\n"); - for (entry = hmap.heavy_uses; entry; entry = entry->next) { - printf("\nweight: is %f\n", entry->weight); - ir_printf("Call for Method %E\n", entry->q.ent); - printf("Position %i\n", entry->q.pos); - ir_printf("Value %T\n", entry->q.tv); + DB((dbg, LEVEL_2, "-----------------\n")); + for (entry_t *entry = hmap.heavy_uses; entry; entry = entry->next) { + DB((dbg, LEVEL_2, "\nweight: is %f\n", entry->weight)); + DB((dbg, LEVEL_2, "Call for Method %E\n", entry->q.ent)); + DB((dbg, LEVEL_2, "Position %zu\n", entry->q.pos)); + DB((dbg, LEVEL_2, "Value %T\n", entry->q.tv)); } - - entry = hmap.heavy_uses; +#endif + entry_t *const entry = hmap.heavy_uses; if (entry) { - ir_entity *ent = clone_method(&entry->q); + quadruple_t *qp = &entry->q; + + ir_entity *ent = clone_method(qp); + DB((dbg, LEVEL_1, "Cloned <%+F, %zu, %T> info %+F\n", qp->ent, qp->pos, qp->tv, ent)); hmap.heavy_uses = entry->next; @@ -676,3 +664,30 @@ void proc_cloning(float threshold) { } obstack_free(&hmap.obst, NULL); } + +typedef struct pass_t { + ir_prog_pass_t pass; + float threshold; +} pass_t; + +/** + * Wrapper to run proc_cloning() as an ir_prog pass. + */ +static int proc_cloning_wrapper(ir_prog *irp, void *context) +{ + pass_t *pass = (pass_t*)context; + + (void)irp; + proc_cloning(pass->threshold); + return 0; +} + +/* create a ir_prog pass */ +ir_prog_pass_t *proc_cloning_pass(const char *name, float threshold) +{ + pass_t *pass = XMALLOCZ(pass_t); + + pass->threshold = threshold; + return def_prog_pass_constructor( + &pass->pass, name ? name : "cloning", proc_cloning_wrapper); +}