X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fscalar_replace.c;h=dd49297e5032514ad382c23729c217586f1e1126;hb=75bdba692afeb0617e59ddc2ea08e0662c356e03;hp=7f6ed79d91f7e4822428447560a06b284bab2777;hpb=b51296cd3a2238c9e20ded9f914b34c4ac3fe304;p=libfirm diff --git a/ir/opt/scalar_replace.c b/ir/opt/scalar_replace.c index 7f6ed79d9..dd49297e5 100644 --- a/ir/opt/scalar_replace.c +++ b/ir/opt/scalar_replace.c @@ -1,30 +1,35 @@ /* - * Project: libFIRM - * File name: ir/opt/scalar_replace.c - * Purpose: scalar replacement of arrays and compounds - * Author: Beyhan Veliev - * Modified by: Michael Beck - * Created: - * CVS-ID: $Id$ - * Copyright: (c) 1998-2005 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2007 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. + */ + +/** + * @file + * @brief Scalar replacement of compounds. + * @author Beyhan Veliev, Michael Beck + * @version $Id$ */ #ifdef HAVE_CONFIG_H #include "config.h" #endif -#ifdef HAVE_ALLOCA_H -#include -#endif - -#ifdef HAVE_MALLOC_H -#include -#endif - -#ifdef HAVE_STRING_H #include -#endif +#include "iroptimize.h" #include "scalar_replace.h" #include "irflag_t.h" #include "irouts.h" @@ -38,6 +43,7 @@ #include "irgmod.h" #include "irnode_t.h" #include "irtools.h" +#include "xmalloc.h" #define SET_VNUM(node, vnum) set_irn_link(node, INT_TO_PTR(vnum)) #define GET_VNUM(node) (unsigned)PTR_TO_INT(get_irn_link(node)) @@ -48,23 +54,26 @@ * accesses like a.b.c[8].d */ typedef union { - entity *ent; + ir_entity *ent; tarval *tv; } path_elem_t; /** * An access path, used to assign value numbers - * to variables that will be scalar replaced + * to variables that will be scalar replaced. */ typedef struct _path_t { - unsigned vnum; /**< the value number */ - unsigned path_len; /**< the length of the access path */ - path_elem_t path[1]; /**< the path */ + unsigned vnum; /**< The value number. */ + unsigned path_len; /**< The length of the access path. */ + path_elem_t path[1]; /**< The path. */ } path_t; +/** The size of a path in bytes. */ +#define PATH_SIZE(p) (sizeof(*(p)) + sizeof((p)->path[0]) * ((p)->path_len - 1)) + typedef struct _scalars_t { - entity *ent; /**< A entity for scalar replacement. */ - type *ent_owner; /**< The owner of this entity. */ + ir_entity *ent; /**< A entity for scalar replacement. */ + ir_type *ent_owner; /**< The owner of this entity. */ } scalars_t; @@ -126,13 +135,45 @@ static int is_const_sel(ir_node *sel) { return 1; } +/** + * Check the mode of a Load/Store with the mode of the entity + * that is accessed. + * If the mode of the entity and the Load/Store mode do not match, we + * have the bad reinterpret case: + * + * int i; + * char b = *(char *)&i; + * + * We do NOT count this as one value and return address_taken + * in that case. + * However, we support an often used case. If the mode is two-complement + * we allow casts between signed/unsigned. + * + * @param mode the mode of the Load/Store + * @param ent_mode the mode of the accessed entity + */ +static int check_load_store_mode(ir_mode *mode, ir_mode *ent_mode) { + if (ent_mode != mode) { + if (ent_mode == NULL || + get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) || + get_mode_sort(ent_mode) != get_mode_sort(mode) || + get_mode_arithmetic(ent_mode) != irma_twos_complement || + get_mode_arithmetic(mode) != irma_twos_complement) + return 0; + } + return 1; +} + /* * Returns non-zero, if the address of an entity * represented by a Sel node (or it's successor Sels) is taken. */ int is_address_taken(ir_node *sel) { - int i; + int i; + ir_mode *emode, *mode; + ir_node *value; + ir_entity *ent; if (! is_const_sel(sel)) return 1; @@ -142,12 +183,24 @@ int is_address_taken(ir_node *sel) switch (get_irn_opcode(succ)) { case iro_Load: - /* ok, we just load from that entity */ + /* check if this load is not a hidden conversion */ + mode = get_Load_mode(succ); + ent = get_Sel_entity(sel); + emode = get_type_mode(get_entity_type(ent)); + if (! check_load_store_mode(mode, emode)) + return 1; break; case iro_Store: /* check that Sel is not the Store's value */ - if (get_Store_value(succ) == sel) + value = get_Store_value(succ); + if (value == sel) + return 1; + /* check if this Store is not a hidden conversion */ + mode = get_irn_mode(value); + ent = get_Sel_entity(sel); + emode = get_type_mode(get_entity_type(ent)); + if (! check_load_store_mode(mode, emode)) return 1; break; @@ -181,7 +234,7 @@ int is_address_taken(ir_node *sel) * @param ent the entity that will be scalar replaced * @param sel a Sel node that selects some fields of this entity */ -static void link_all_leave_sels(entity *ent, ir_node *sel) +static void link_all_leave_sels(ir_entity *ent, ir_node *sel) { int i, n, flag = 1; @@ -189,7 +242,7 @@ static void link_all_leave_sels(entity *ent, ir_node *sel) for (i = 0; i < n; ++i) { ir_node *succ = get_irn_out(sel, i); - if (get_irn_op(succ) == op_Sel) { + if (is_Sel(succ)) { link_all_leave_sels(ent, succ); flag = 0; } @@ -252,8 +305,8 @@ static int find_possible_replacements(ir_graph *irg) for (i = 0; i < n; ++i) { ir_node *succ = get_irn_out(irg_frame, i); - if (get_irn_op(succ) == op_Sel) { - entity *ent = get_Sel_entity(succ); + if (is_Sel(succ)) { + ir_entity *ent = get_Sel_entity(succ); set_entity_link(ent, NULL); } } @@ -266,13 +319,24 @@ static int find_possible_replacements(ir_graph *irg) for (i = 0; i < n; ++i) { ir_node *succ = get_irn_out(irg_frame, i); - if (get_irn_op(succ) == op_Sel) { - entity *ent = get_Sel_entity(succ); - type *ent_type; + if (is_Sel(succ)) { + ir_entity *ent = get_Sel_entity(succ); + ir_type *ent_type; if (get_entity_link(ent) == ADDRESS_TAKEN) continue; + /* + * Beware: in rare cases even entities on the frame might be + * volatile. This might happen if the entity serves as a store + * to a value that must survive a exception. Do not optimize + * such entities away. + */ + if (get_entity_volatility(ent) == volatility_is_volatile) { + set_entity_link(ent, ADDRESS_TAKEN); + continue; + } + ent_type = get_entity_type(ent); /* we can handle arrays, structs and atomic types yet */ @@ -311,7 +375,7 @@ static path_t *find_path(ir_node *sel, unsigned len) n = get_Sel_n_indexs(sel); len += n + 1; - if (get_irn_op(pred) != op_Sel) { + if (! is_Sel(pred)) { /* we found the root */ res = xmalloc(sizeof(*res) + (len - 1) * sizeof(res->path)); @@ -344,7 +408,7 @@ static path_t *find_path(ir_node *sel, unsigned len) * * @return the next free value number */ -static unsigned allocate_value_numbers(pset *sels, entity *ent, unsigned vnum, ir_mode ***modes) +static unsigned allocate_value_numbers(pset *sels, ir_entity *ent, unsigned vnum, ir_mode ***modes) { ir_node *sel, *next; path_t *key, *path; @@ -358,19 +422,17 @@ static unsigned allocate_value_numbers(pset *sels, entity *ent, unsigned vnum, i pset_insert_ptr(sels, sel); key = find_path(sel, 0); - path = set_find(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key)); + path = set_find(pathes, key, PATH_SIZE(key), path_hash(key)); if (path) SET_VNUM(sel, path->vnum); else { - unsigned i; - key->vnum = vnum++; - set_insert(pathes, key, sizeof(*key) + sizeof(key->path[0]) * key->path_len, path_hash(key)); + set_insert(pathes, key, PATH_SIZE(key), path_hash(key)); SET_VNUM(sel, key->vnum); - ARR_EXTO(ir_mode *, *modes, (key->vnum + 15) & ~15); + ARR_EXTO(ir_mode *, *modes, (int)((key->vnum + 15) & ~15)); (*modes)[key->vnum] = get_type_mode(get_entity_type(get_Sel_entity(sel))); @@ -379,7 +441,8 @@ static unsigned allocate_value_numbers(pset *sels, entity *ent, unsigned vnum, i #ifdef DEBUG_libfirm /* Debug output */ if (get_opt_scalar_replacement_verbose() && get_firm_verbosity() > 1) { - printf(" %s", get_entity_name(ent)); + unsigned i; + printf(" %s", get_entity_name(key->path[0].ent)); for (i = 1; i < key->path_len; ++i) { if (is_entity(key->path[i].ent)) printf(".%s", get_entity_name(key->path[i].ent)); @@ -419,13 +482,14 @@ typedef struct _env_t { } env_t; /** - * Walker + * topological walker. */ -static void handle_first(ir_node *node, void *ctx) +static void topologic_walker(ir_node *node, void *ctx) { env_t *env = ctx; ir_op *op = get_irn_op(node); - ir_node *adr, *block, *mem, *unk, **value_arr, **in; + ir_node *adr, *block, *mem, *unk, **value_arr, **in, *val; + ir_mode *mode; unsigned vnum; int i, j, n; list_entry_t *l; @@ -434,7 +498,7 @@ static void handle_first(ir_node *node, void *ctx) /* a load, check if we can resolve it */ adr = get_Load_ptr(node); - if (get_irn_op(adr) != op_Sel) + if (! is_Sel(adr)) return; if (! pset_find_ptr(env->sels, adr)) @@ -452,12 +516,24 @@ static void handle_first(ir_node *node, void *ctx) if (value_arr[vnum]) { mem = get_Load_mem(node); + /* Beware: A Load can contain a hidden conversion in Firm. + This happens for instance in the following code: + + int i; + unsigned j = *(unsigned *)&i; + + Handle this here. */ + val = value_arr[vnum]; + mode = get_Load_mode(node); + if (mode != get_irn_mode(val)) + val = new_d_Conv(get_irn_dbg_info(node), val, mode); + turn_into_tuple(node, pn_Load_max); - set_Tuple_pred(node, pn_Load_M, mem); - set_Tuple_pred(node, pn_Load_res, value_arr[vnum]); - set_Tuple_pred(node, pn_Load_X_except, new_Bad()); - } - else { + set_Tuple_pred(node, pn_Load_M, mem); + set_Tuple_pred(node, pn_Load_res, val); + set_Tuple_pred(node, pn_Load_X_regular, new_r_Jmp(current_ir_graph, block)); + set_Tuple_pred(node, pn_Load_X_except, new_Bad()); + } else { l = obstack_alloc(&env->obst, sizeof(*l)); l->node = node; l->vnum = vnum; @@ -465,12 +541,11 @@ static void handle_first(ir_node *node, void *ctx) set_irn_link(node, env->fix_loads); env->fix_loads = l; } - } - else if (op == op_Store) { + } else if (op == op_Store) { /* a Store always can be replaced */ adr = get_Store_ptr(node); - if (get_irn_op(adr) != op_Sel) + if (! is_Sel(adr)) return; if (! pset_find_ptr(env->sels, adr)) @@ -483,15 +558,20 @@ static void handle_first(ir_node *node, void *ctx) block = get_nodes_block(node); value_arr = get_irn_link(block); - value_arr[vnum] = get_Store_value(node); + /* Beware: A Store can contain a hidden conversion in Firm. */ + val = get_Store_value(node); + if (get_irn_mode(val) != env->modes[vnum]) + val = new_d_Conv(get_irn_dbg_info(node), val, env->modes[vnum]); + value_arr[vnum] = val; mem = get_Store_mem(node); + block = get_nodes_block(node); turn_into_tuple(node, pn_Store_max); - set_Tuple_pred(node, pn_Store_M, mem); - set_Tuple_pred(node, pn_Store_X_except, new_Bad()); - } - else if (op == op_Phi && get_irn_mode(node) == mode_M) { + set_Tuple_pred(node, pn_Store_M, mem); + set_Tuple_pred(node, pn_Store_X_regular, new_r_Jmp(current_ir_graph, block)); + set_Tuple_pred(node, pn_Store_X_except, new_Bad()); + } else if (op == op_Phi && get_irn_mode(node) == mode_M) { /* * found a memory Phi: Here, we must create new Phi nodes */ @@ -536,7 +616,7 @@ static void alloc_value_arr(ir_node *block, void *ctx) * searches through blocks beginning from block for value * vnum and return it. */ -static ir_node *find_value(ir_node *block, unsigned vnum) +static ir_node *find_vnum_value(ir_node *block, unsigned vnum) { ir_node **value_arr; int i; @@ -553,7 +633,7 @@ static ir_node *find_value(ir_node *block, unsigned vnum) for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred(block, i); - res = find_value(get_nodes_block(pred), vnum); + res = find_vnum_value(get_nodes_block(pred), vnum); if (res) return res; } @@ -579,7 +659,7 @@ static void fix_phis(env_t *env) pred = get_nodes_block(pred); inc_irg_block_visited(current_ir_graph); - val = find_value(pred, l->vnum); + val = find_vnum_value(pred, l->vnum); if (val) set_irn_n(phi, i, val); @@ -593,7 +673,8 @@ static void fix_phis(env_t *env) static void fix_loads(env_t *env) { list_entry_t *l; - ir_node *load, *block, *pred, *val, *mem; + ir_node *load, *block, *pred, *val = NULL, *mem; + ir_mode *mode; int i; for (l = env->fix_loads; l; l = get_irn_link(load)) { @@ -605,7 +686,7 @@ static void fix_loads(env_t *env) pred = get_nodes_block(pred); inc_irg_block_visited(current_ir_graph); - val = find_value(pred, l->vnum); + val = find_vnum_value(pred, l->vnum); if (val) break; @@ -616,12 +697,19 @@ static void fix_loads(env_t *env) val = new_Unknown(env->modes[l->vnum]); } - mem = get_Load_mem(load); + /* Beware: A Load can contain a hidden conversion in Firm. + Handle this here. */ + mode = get_Load_mode(load); + if (mode != get_irn_mode(val)) + val = new_d_Conv(get_irn_dbg_info(load), val, mode); + + mem = get_Load_mem(load); turn_into_tuple(load, pn_Load_max); - set_Tuple_pred(load, pn_Load_M, mem); - set_Tuple_pred(load, pn_Load_res, val); - set_Tuple_pred(load, pn_Load_X_except, new_Bad()); + set_Tuple_pred(load, pn_Load_M, mem); + set_Tuple_pred(load, pn_Load_res, val); + set_Tuple_pred(load, pn_Load_X_regular, new_r_Jmp(current_ir_graph, block)); + set_Tuple_pred(load, pn_Load_X_except, new_Bad()); } } @@ -651,7 +739,7 @@ static void do_scalar_replacements(pset *sels, int nvals, ir_mode **modes) * second step: walk over the graph blockwise in topological order * and fill the array as much as possible. */ - irg_walk_blkwise_graph(current_ir_graph, NULL, handle_first, &env); + irg_walk_blkwise_graph(current_ir_graph, NULL, topologic_walker, &env); /* third, fix the list of Phis, then the list of Loads */ fix_phis(&env); @@ -674,7 +762,7 @@ void scalar_replacement_opt(ir_graph *irg) ir_mode **modes; set *set_ent; pset *sels; - type *ent_type; + ir_type *ent_type; ir_graph *rem; if (! get_opt_scalar_replacement()) @@ -683,8 +771,7 @@ void scalar_replacement_opt(ir_graph *irg) rem = current_ir_graph; /* Call algorithm that computes the out edges */ - if (get_irg_outs_state(irg) != outs_consistent) - compute_irg_outs(irg); + assure_irg_outs(irg); /* Find possible scalar replacements */ if (find_possible_replacements(irg)) { @@ -703,8 +790,8 @@ void scalar_replacement_opt(ir_graph *irg) for (i = 0 ; i < get_irn_n_outs(irg_frame); i++) { ir_node *succ = get_irn_out(irg_frame, i); - if (get_irn_op(succ) == op_Sel) { - entity *ent = get_Sel_entity(succ); + if (is_Sel(succ)) { + ir_entity *ent = get_Sel_entity(succ); if (get_entity_link(ent) == NULL || get_entity_link(ent) == ADDRESS_TAKEN) continue;