X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fldstopt.c;h=91347a7bea9076376bfdfabd3af816ae9dc332fa;hb=44faeb9742640d3498eb4482f98eb1255607c4d6;hp=055b6be112b22a1565d5605ca82a95056d82cfb3;hpb=0e5f781d021c0b1e20ba08f583d4971419fedb5d;p=libfirm diff --git a/ir/opt/ldstopt.c b/ir/opt/ldstopt.c index 055b6be11..91347a7be 100644 --- a/ir/opt/ldstopt.c +++ b/ir/opt/ldstopt.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -63,7 +63,7 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg;) #undef IMAX #define IMAX(a,b) ((a) > (b) ? (a) : (b)) -#define MAX_PROJ IMAX(pn_Load_max, pn_Store_max) +#define MAX_PROJ IMAX(IMAX(pn_Load_max, pn_Store_max), pn_Call_max) enum changes_t { DF_CHANGED = 1, /**< data flow changed */ @@ -78,19 +78,11 @@ typedef struct _walk_env_t { unsigned changes; /**< a bitmask of graph changes */ } walk_env_t; -/** - * flags for Load/Store - */ -enum ldst_flags_t { - LDST_VISITED = 1 /**< if set, this Load/Store is already visited */ -}; - /** A Load/Store info. */ typedef struct _ldst_info_t { ir_node *projs[MAX_PROJ]; /**< list of Proj's of this node */ ir_node *exc_block; /**< the exception block if available */ int exc_idx; /**< predecessor index in the exception block */ - unsigned flags; /**< flags */ unsigned visited; /**< visited counter for breaking loops */ } ldst_info_t; @@ -190,28 +182,20 @@ static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos) */ static void collect_nodes(ir_node *node, void *env) { - ir_op *op = get_irn_op(node); + ir_opcode opcode = get_irn_opcode(node); ir_node *pred, *blk, *pred_blk; ldst_info_t *ldst_info; walk_env_t *wenv = env; - if (op == op_Proj) { - ir_node *adr; - ir_op *op; - - pred = get_Proj_pred(node); - op = get_irn_op(pred); + if (opcode == iro_Proj) { + pred = get_Proj_pred(node); + opcode = get_irn_opcode(pred); - if (op == op_Load) { + if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) { ldst_info = get_ldst_info(pred, &wenv->obst); wenv->changes |= update_projs(ldst_info, node); - if ((ldst_info->flags & LDST_VISITED) == 0) { - adr = get_Load_ptr(pred); - ldst_info->flags |= LDST_VISITED; - } - /* * Place the Proj's to the same block as the * predecessor Load. This is always ok and prevents @@ -224,30 +208,8 @@ static void collect_nodes(ir_node *node, void *env) wenv->changes |= DF_CHANGED; set_nodes_block(node, pred_blk); } - } else if (op == op_Store) { - ldst_info = get_ldst_info(pred, &wenv->obst); - - wenv->changes |= update_projs(ldst_info, node); - - if ((ldst_info->flags & LDST_VISITED) == 0) { - adr = get_Store_ptr(pred); - ldst_info->flags |= LDST_VISITED; - } - - /* - * Place the Proj's to the same block as the - * predecessor Store. This is always ok and prevents - * "non-SSA" form after optimizations if the Proj - * is in a wrong block. - */ - blk = get_nodes_block(node); - pred_blk = get_nodes_block(pred); - if (blk != pred_blk) { - wenv->changes |= DF_CHANGED; - set_nodes_block(node, pred_blk); - } } - } else if (op == op_Block) { + } else if (opcode == iro_Block) { int i; for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) { @@ -274,7 +236,8 @@ static void collect_nodes(ir_node *node, void *env) else if (is_irn_forking(pred)) bl_info->flags |= BLOCK_HAS_COND; - if (is_exc && (get_irn_op(pred) == op_Load || get_irn_op(pred) == op_Store)) { + opcode = get_irn_opcode(pred); + if (is_exc && (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call)) { ldst_info = get_ldst_info(pred, &wenv->obst); wenv->changes |= update_exc(ldst_info, node, i); @@ -293,14 +256,12 @@ static void collect_nodes(ir_node *node, void *env) static ir_entity *find_constant_entity(ir_node *ptr) { for (;;) { - ir_op *op = get_irn_op(ptr); - - if (op == op_SymConst && (get_SymConst_kind(ptr) == symconst_addr_ent)) { + if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) { ir_entity *ent = get_SymConst_entity(ptr); if (variability_constant == get_entity_variability(ent)) return ent; return NULL; - } else if (op == op_Sel) { + } else if (is_Sel(ptr)) { ir_entity *ent = get_Sel_entity(ptr); ir_type *tp = get_entity_owner(ent); @@ -346,6 +307,31 @@ static ir_entity *find_constant_entity(ir_node *ptr) /* try next */ ptr = get_Sel_ptr(ptr); + } else if (is_Add(ptr)) { + ir_node *l = get_Add_left(ptr); + ir_node *r = get_Add_right(ptr); + + if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r)) + ptr = l; + else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l)) + ptr = r; + else + return NULL; + + /* for now, we support only one addition, reassoc should fold all others */ + if (! is_SymConst(ptr) && !is_Sel(ptr)) + return NULL; + } else if (is_Sub(ptr)) { + ir_node *l = get_Sub_left(ptr); + ir_node *r = get_Sub_right(ptr); + + if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r)) + ptr = l; + else + return NULL; + /* for now, we support only one substraction, reassoc should fold all others */ + if (! is_SymConst(ptr) && !is_Sel(ptr)) + return NULL; } else return NULL; } @@ -370,10 +356,12 @@ static long get_Sel_array_index_long(ir_node *n, int dim) { */ static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) { compound_graph_path *res = NULL; - ir_entity *root, *field; - int path_len, pos; + ir_entity *root, *field, *ent; + int path_len, pos, idx; + tarval *tv; + ir_type *tp; - if (get_irn_op(ptr) == op_SymConst) { + if (is_SymConst(ptr)) { /* a SymConst. If the depth is 0, this is an access to a global * entity and we don't need a component path, else we know * at least it's length. @@ -381,10 +369,11 @@ static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) { assert(get_SymConst_kind(ptr) == symconst_addr_ent); root = get_SymConst_entity(ptr); res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth); - } else { - assert(get_irn_op(ptr) == op_Sel); + } else if (is_Sel(ptr)) { /* it's a Sel, go up until we find the root */ res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1); + if (res == NULL) + return NULL; /* fill up the step in the path at the current position */ field = get_Sel_entity(ptr); @@ -396,17 +385,311 @@ static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) { assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented"); set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0)); } + } else if (is_Add(ptr)) { + ir_node *l = get_Add_left(ptr); + ir_node *r = get_Add_right(ptr); + ir_mode *mode = get_irn_mode(ptr); + tarval *tmp; + + if (is_Const(r) && get_irn_mode(l) == mode) { + ptr = l; + tv = get_Const_tarval(r); + } else { + ptr = r; + tv = get_Const_tarval(l); + } +ptr_arith: + mode = get_tarval_mode(tv); + tmp = tv; + + /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */ + if (is_Sel(ptr)) { + field = get_Sel_entity(ptr); + } else { + field = get_SymConst_entity(ptr); + } + idx = 0; + for (ent = field;;) { + unsigned size; + tarval *sz, *tv_index, *tlower, *tupper; + ir_node *bound; + + tp = get_entity_type(ent); + if (! is_Array_type(tp)) + break; + ent = get_array_element_entity(tp); + size = get_type_size_bytes(get_entity_type(ent)); + sz = new_tarval_from_long(size, mode); + + tv_index = tarval_div(tmp, sz); + tmp = tarval_mod(tmp, sz); + + if (tv_index == tarval_bad || tmp == tarval_bad) + return NULL; + + assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented"); + bound = get_array_lower_bound(tp, 0); + tlower = computed_value(bound); + bound = get_array_upper_bound(tp, 0); + tupper = computed_value(bound); + + if (tlower == tarval_bad || tupper == tarval_bad) + return NULL; + + if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt) + return NULL; + if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt) + return NULL; + + /* ok, bounds check finished */ + ++idx; + } + if (! tarval_is_null(tmp)) { + /* access to some struct/union member */ + return NULL; + } + + /* should be at least ONE array */ + if (idx == 0) + return NULL; + + res = rec_get_accessed_path(ptr, depth + idx); + if (res == NULL) + return NULL; + + path_len = get_compound_graph_path_length(res); + pos = path_len - depth - idx; + + for (ent = field;;) { + unsigned size; + tarval *sz, *tv_index; + long index; + + tp = get_entity_type(ent); + if (! is_Array_type(tp)) + break; + ent = get_array_element_entity(tp); + set_compound_graph_path_node(res, pos, ent); + + size = get_type_size_bytes(get_entity_type(ent)); + sz = new_tarval_from_long(size, mode); + + tv_index = tarval_div(tv, sz); + tv = tarval_mod(tv, sz); + + /* worked above, should work again */ + assert(tv_index != tarval_bad && tv != tarval_bad); + + /* bounds already checked above */ + index = get_tarval_long(tv_index); + set_compound_graph_path_array_index(res, pos, index); + ++pos; + } + } else if (is_Sub(ptr)) { + ir_node *l = get_Sub_left(ptr); + ir_node *r = get_Sub_right(ptr); + + ptr = l; + tv = get_Const_tarval(r); + tv = tarval_neg(tv); + goto ptr_arith; } return res; } /* rec_get_accessed_path */ -/** Returns an access path or NULL. The access path is only - * valid, if the graph is in phase_high and _no_ address computation is used. +/** + * Returns an access path or NULL. The access path is only + * valid, if the graph is in phase_high and _no_ address computation is used. */ static compound_graph_path *get_accessed_path(ir_node *ptr) { - return rec_get_accessed_path(ptr, 0); + compound_graph_path *gr = rec_get_accessed_path(ptr, 0); + return gr; } /* get_accessed_path */ +typedef struct path_entry { + ir_entity *ent; + struct path_entry *next; + long index; +} path_entry; + +static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next) { + path_entry entry, *p; + ir_entity *ent, *field; + ir_initializer_t *initializer; + tarval *tv; + ir_type *tp; + unsigned n; + + entry.next = next; + if (is_SymConst(ptr)) { + /* found the root */ + ent = get_SymConst_entity(ptr); + initializer = get_entity_initializer(ent); + for (p = next; p != NULL;) { + if (initializer->kind != IR_INITIALIZER_COMPOUND) + return NULL; + n = get_initializer_compound_n_entries(initializer); + tp = get_entity_type(ent); + + if (is_Array_type(tp)) { + ent = get_array_element_entity(tp); + if (ent != p->ent) { + /* a missing [0] */ + if (0 >= n) + return NULL; + initializer = get_initializer_compound_value(initializer, 0); + continue; + } + } + if (p->index >= (int) n) + return NULL; + initializer = get_initializer_compound_value(initializer, p->index); + + ent = p->ent; + p = p->next; + } + tp = get_entity_type(ent); + while (is_Array_type(tp)) { + ent = get_array_element_entity(tp); + tp = get_entity_type(ent); + /* a missing [0] */ + n = get_initializer_compound_n_entries(initializer); + if (0 >= n) + return NULL; + initializer = get_initializer_compound_value(initializer, 0); + } + + switch (initializer->kind) { + case IR_INITIALIZER_CONST: + return get_initializer_const_value(initializer); + case IR_INITIALIZER_TARVAL: + case IR_INITIALIZER_NULL: + default: + return NULL; + } + } else if (is_Sel(ptr)) { + entry.ent = field = get_Sel_entity(ptr); + tp = get_entity_owner(field); + if (is_Array_type(tp)) { + assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented"); + entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0); + } else { + int i, n_members = get_compound_n_members(tp); + for (i = 0; i < n_members; ++i) { + if (get_compound_member(tp, i) == field) + break; + } + if (i >= n_members) { + /* not found: should NOT happen */ + return NULL; + } + entry.index = i; + } + return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry); + } else if (is_Add(ptr)) { + ir_node *l = get_Add_left(ptr); + ir_node *r = get_Add_right(ptr); + ir_mode *mode; + unsigned pos; + + if (is_Const(r)) { + ptr = l; + tv = get_Const_tarval(r); + } else { + ptr = r; + tv = get_Const_tarval(l); + } +ptr_arith: + mode = get_tarval_mode(tv); + + /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */ + if (is_Sel(ptr)) { + field = get_Sel_entity(ptr); + } else { + field = get_SymConst_entity(ptr); + } + + /* count needed entries */ + pos = 0; + for (ent = field;;) { + tp = get_entity_type(ent); + if (! is_Array_type(tp)) + break; + ent = get_array_element_entity(tp); + ++pos; + } + /* should be at least ONE entry */ + if (pos == 0) + return NULL; + + /* allocate the right number of entries */ + NEW_ARR_A(path_entry, p, pos); + + /* fill them up */ + pos = 0; + for (ent = field;;) { + unsigned size; + tarval *sz, *tv_index, *tlower, *tupper; + long index; + ir_node *bound; + + tp = get_entity_type(ent); + if (! is_Array_type(tp)) + break; + ent = get_array_element_entity(tp); + p[pos].ent = ent; + p[pos].next = &p[pos + 1]; + + size = get_type_size_bytes(get_entity_type(ent)); + sz = new_tarval_from_long(size, mode); + + tv_index = tarval_div(tv, sz); + tv = tarval_mod(tv, sz); + + if (tv_index == tarval_bad || tv == tarval_bad) + return NULL; + + assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented"); + bound = get_array_lower_bound(tp, 0); + tlower = computed_value(bound); + bound = get_array_upper_bound(tp, 0); + tupper = computed_value(bound); + + if (tlower == tarval_bad || tupper == tarval_bad) + return NULL; + + if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt) + return NULL; + if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt) + return NULL; + + /* ok, bounds check finished */ + index = get_tarval_long(tv_index); + p[pos].index = index; + ++pos; + } + if (! tarval_is_null(tv)) { + /* hmm, wrong access */ + return NULL; + } + p[pos - 1].next = next; + return rec_find_compound_ent_value(ptr, p); + } else if (is_Sub(ptr)) { + ir_node *l = get_Sub_left(ptr); + ir_node *r = get_Sub_right(ptr); + + ptr = l; + tv = get_Const_tarval(r); + tv = tarval_neg(tv); + goto ptr_arith; + } + return NULL; +} + +static ir_node *find_compound_ent_value(ir_node *ptr) { + return rec_find_compound_ent_value(ptr, NULL); +} + /* forward */ static void reduce_adr_usage(ir_node *ptr); @@ -428,7 +711,7 @@ static void handle_load_update(ir_node *load) { exchange(info->projs[pn_Load_M], mem); if (info->projs[pn_Load_X_regular]) exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); - exchange(load, new_Bad()); + kill_node(load); reduce_adr_usage(ptr); } } /* handle_load_update */ @@ -472,9 +755,165 @@ static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode) { } /* can_use_stored_value */ /** - * Follow the memory chain as long as there are only Loads - * and alias free Stores and try to replace current Load or Store - * by a previous ones. + * Check whether a Call is at least pure, ie. does only read memory. + */ +static unsigned is_Call_pure(ir_node *call) { + ir_type *call_tp = get_Call_type(call); + unsigned prop = get_method_additional_properties(call_tp); + + /* check first the call type */ + if ((prop & (mtp_property_const|mtp_property_pure)) == 0) { + /* try the called entity */ + ir_node *ptr = get_Call_ptr(call); + + if (is_Global(ptr)) { + ir_entity *ent = get_Global_entity(ptr); + + prop = get_entity_additional_properties(ent); + } + } + return (prop & (mtp_property_const|mtp_property_pure)) != 0; +} /* is_Call_pure */ + +static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset) +{ + ir_mode *mode = get_irn_mode(ptr); + long offset = 0; + + /* TODO: long might not be enough, we should probably use some tarval thingy... */ + for (;;) { + if (is_Add(ptr)) { + ir_node *l = get_Add_left(ptr); + ir_node *r = get_Add_right(ptr); + + if (get_irn_mode(l) != mode || !is_Const(r)) + break; + + offset += get_tarval_long(get_Const_tarval(r)); + ptr = l; + } else if (is_Sub(ptr)) { + ir_node *l = get_Sub_left(ptr); + ir_node *r = get_Sub_right(ptr); + + if (get_irn_mode(l) != mode || !is_Const(r)) + break; + + offset -= get_tarval_long(get_Const_tarval(r)); + ptr = l; + } else if (is_Sel(ptr)) { + ir_entity *ent = get_Sel_entity(ptr); + ir_type *tp = get_entity_owner(ent); + + if (is_Array_type(tp)) { + int size; + ir_node *index; + + /* only one dimensional arrays yet */ + if (get_Sel_n_indexs(ptr) != 1) + break; + index = get_Sel_index(ptr, 0); + if (! is_Const(index)) + break; + + tp = get_entity_type(ent); + if (get_type_state(tp) != layout_fixed) + break; + + size = get_type_size_bytes(tp); + offset += size * get_tarval_long(get_Const_tarval(index)); + } else { + if (get_type_state(tp) != layout_fixed) + break; + offset += get_entity_offset(ent); + } + ptr = get_Sel_ptr(ptr); + } else + break; + } + + *pOffset = offset; + return ptr; +} + +static int try_load_after_store(ir_node *load, + ir_node *load_base_ptr, long load_offset, ir_node *store) +{ + ldst_info_t *info; + ir_node *store_ptr = get_Store_ptr(store); + long store_offset; + ir_node *store_base_ptr = get_base_and_offset(store_ptr, &store_offset); + ir_node *store_value; + ir_mode *store_mode; + ir_node *load_ptr; + ir_mode *load_mode; + long load_mode_len; + long store_mode_len; + long delta; + int res; + + if (load_base_ptr != store_base_ptr) + return 0; + + load_mode = get_Load_mode(load); + load_mode_len = get_mode_size_bytes(load_mode); + store_mode = get_irn_mode(get_Store_value(store)); + store_mode_len = get_mode_size_bytes(store_mode); + delta = load_offset - store_offset; + if (delta < 0 || delta + load_mode_len > store_mode_len) + return 0; + + if (get_mode_arithmetic(store_mode) != irma_twos_complement || + get_mode_arithmetic(load_mode) != irma_twos_complement) + return 0; + + store_value = get_Store_value(store); + + /* produce a shift to adjust offset delta */ + if (delta > 0) { + ir_node *cnst; + + /* FIXME: only true for little endian */ + cnst = new_Const_long(mode_Iu, delta * 8); + store_value = new_r_Shr(current_ir_graph, get_nodes_block(load), + store_value, cnst, store_mode); + } + + /* add an convert if needed */ + if (store_mode != load_mode) { + store_value = new_r_Conv(current_ir_graph, get_nodes_block(load), + store_value, load_mode); + } + + DBG_OPT_RAW(load, store_value); + + info = get_irn_link(load); + if (info->projs[pn_Load_M]) + exchange(info->projs[pn_Load_M], get_Load_mem(load)); + + res = 0; + /* no exception */ + if (info->projs[pn_Load_X_except]) { + exchange( info->projs[pn_Load_X_except], new_Bad()); + res |= CF_CHANGED; + } + if (info->projs[pn_Load_X_regular]) { + exchange( info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); + res |= CF_CHANGED; + } + + if (info->projs[pn_Load_res]) + exchange(info->projs[pn_Load_res], store_value); + + load_ptr = get_Load_ptr(load); + kill_node(load); + reduce_adr_usage(load_ptr); + return res | DF_CHANGED; +} + +/** + * Follow the memory chain as long as there are only Loads, + * alias free Stores, and constant Calls and try to replace the + * current Load by a previous ones. * Note that in unreachable loops it might happen that we reach * load again, as well as we can fall into a cycle. * We break such cycles using a special visited flag. @@ -482,67 +921,39 @@ static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode) { * INC_MASTER() must be called before dive into */ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { - unsigned res = 0; + unsigned res = 0; ldst_info_t *info = get_irn_link(load); - ir_node *pred; - ir_node *ptr = get_Load_ptr(load); - ir_node *mem = get_Load_mem(load); - ir_mode *load_mode = get_Load_mode(load); + ir_node *pred; + ir_node *ptr = get_Load_ptr(load); + ir_node *mem = get_Load_mem(load); + ir_mode *load_mode = get_Load_mode(load); for (pred = curr; load != pred; ) { ldst_info_t *pred_info = get_irn_link(pred); /* - * BEWARE: one might think that checking the modes is useless, because - * if the pointers are identical, they refer to the same object. - * This is only true in strong typed languages, not in C were the following - * is possible a = *(ir_type1 *)p; b = *(ir_type2 *)p ... + * a Load immediately after a Store -- a read after write. + * We may remove the Load, if both Load & Store does not have an + * exception handler OR they are in the same MacroBlock. In the latter + * case the Load cannot throw an exception when the previous Store was + * quiet. + * + * Why we need to check for Store Exception? If the Store cannot + * be executed (ROM) the exception handler might simply jump into + * the load MacroBlock :-( + * We could make it a little bit better if we would know that the + * exception handler of the Store jumps directly to the end... */ - if (is_Store(pred) && get_Store_ptr(pred) == ptr && - can_use_stored_value(get_irn_mode(get_Store_value(pred)), load_mode)) { - /* - * a Load immediately after a Store -- a read after write. - * We may remove the Load, if both Load & Store does not have an exception handler - * OR they are in the same MacroBlock. In the latter case the Load cannot - * throw an exception when the previous Store was quiet. - * - * Why we need to check for Store Exception? If the Store cannot - * be executed (ROM) the exception handler might simply jump into - * the load MacroBlock :-( - * We could make it a little bit better if we would know that the exception - * handler of the Store jumps directly to the end... - */ - if ((pred_info->projs[pn_Store_X_except] == NULL && info->projs[pn_Load_X_except] == NULL) || - get_nodes_MacroBlock(load) == get_nodes_MacroBlock(pred)) { - ir_node *value = get_Store_value(pred); - - DBG_OPT_RAW(load, value); - - /* add an convert if needed */ - if (get_irn_mode(get_Store_value(pred)) != load_mode) { - value = new_r_Conv(current_ir_graph, get_nodes_block(load), value, load_mode); - } - - if (info->projs[pn_Load_M]) - exchange(info->projs[pn_Load_M], mem); - - /* no exception */ - if (info->projs[pn_Load_X_except]) { - exchange( info->projs[pn_Load_X_except], new_Bad()); - res |= CF_CHANGED; - } - if (info->projs[pn_Load_X_regular]) { - exchange( info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); - res |= CF_CHANGED; - } - - if (info->projs[pn_Load_res]) - exchange(info->projs[pn_Load_res], value); - - exchange(load, new_Bad()); - reduce_adr_usage(ptr); - return res | DF_CHANGED; - } + if (is_Store(pred) && ((pred_info->projs[pn_Store_X_except] == NULL + && info->projs[pn_Load_X_except] == NULL) + || get_nodes_MacroBlock(load) == get_nodes_MacroBlock(pred))) + { + long load_offset; + ir_node *base_ptr = get_base_and_offset(ptr, &load_offset); + int changes = try_load_after_store(load, base_ptr, load_offset, pred); + + if (changes != 0) + return res | changes; } else if (is_Load(pred) && get_Load_ptr(pred) == ptr && can_use_stored_value(get_Load_mode(pred), load_mode)) { /* @@ -588,7 +999,7 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { res |= CF_CHANGED; } - exchange(load, new_Bad()); + kill_node(load); reduce_adr_usage(ptr); return res |= DF_CHANGED; } @@ -602,11 +1013,20 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { get_irn_mode(get_Store_value(pred)), ptr, load_mode); /* if the might be an alias, we cannot pass this Store */ - if (rel != no_alias) + if (rel != ir_no_alias) break; pred = skip_Proj(get_Store_mem(pred)); - } else if (get_irn_op(pred) == op_Load) { + } else if (is_Load(pred)) { pred = skip_Proj(get_Load_mem(pred)); + } else if (is_Call(pred)) { + if (is_Call_pure(pred)) { + /* The called graph is at least pure, so there are no Store's + in it. We can handle it like a Load and skip it. */ + pred = skip_Proj(get_Call_mem(pred)); + } else { + /* there might be Store's in the graph, stop here */ + break; + } } else { /* follow only Load chains */ break; @@ -632,6 +1052,33 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { return res; } /* follow_Mem_chain */ +/* + * Check if we can replace the load by a given const from + * the const code irg. + */ +ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c) { + ir_mode *c_mode = get_irn_mode(c); + ir_mode *l_mode = get_Load_mode(load); + ir_node *res = NULL; + + if (c_mode != l_mode) { + /* check, if the mode matches OR can be easily converted info */ + if (is_reinterpret_cast(c_mode, l_mode)) { + /* we can safely cast */ + dbg_info *dbg = get_irn_dbg_info(load); + ir_node *block = get_nodes_block(load); + + /* copy the value from the const code irg and cast it */ + res = copy_const_value(dbg, c); + res = new_rd_Conv(dbg, current_ir_graph, block, res, l_mode); + } + } else { + /* copy the value from the const code irg */ + res = copy_const_value(get_irn_dbg_info(load), c); + } + return res; +} /* can_replace_load_by_const */ + /** * optimize a Load * @@ -640,9 +1087,10 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { static unsigned optimize_load(ir_node *load) { ldst_info_t *info = get_irn_link(load); - ir_node *mem, *ptr, *new_node; - ir_entity *ent; - unsigned res = 0; + ir_node *mem, *ptr, *value; + ir_entity *ent; + long dummy; + unsigned res = 0; /* do NOT touch volatile loads for now */ if (get_Load_volatility(load) == volatility_is_volatile) @@ -660,38 +1108,22 @@ static unsigned optimize_load(ir_node *load) * like x = new O; x->t; */ if (info->projs[pn_Load_X_except]) { - if (is_Sel(ptr)) { - ir_node *mem = get_Sel_mem(ptr); - - /* FIXME: works with the current FE, but better use the base */ - if (is_Alloc(skip_Proj(mem))) { - /* ok, check the types */ - ir_entity *ent = get_Sel_entity(ptr); - ir_type *s_type = get_entity_type(ent); - ir_type *a_type = get_Alloc_type(mem); - - if (is_SubClass_of(s_type, a_type)) { - /* ok, condition met: there can't be an exception because - * Alloc guarantees that enough memory was allocated */ - - exchange(info->projs[pn_Load_X_except], new_Bad()); - info->projs[pn_Load_X_except] = NULL; - exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); - info->projs[pn_Load_X_regular] = NULL; - res |= CF_CHANGED; - } - } - } else if (is_Alloc(skip_Proj(skip_Cast(ptr)))) { - /* simple case: a direct load after an Alloc. Firm Alloc throw - * an exception in case of out-of-memory. So, there is no way for an - * exception in this load. - * This code is constructed by the "exception lowering" in the Jack compiler. - */ - exchange(info->projs[pn_Load_X_except], new_Bad()); - info->projs[pn_Load_X_except] = NULL; - exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); - info->projs[pn_Load_X_regular] = NULL; - res |= CF_CHANGED; + ir_node *addr = ptr; + + /* find base address */ + while (is_Sel(addr)) + addr = get_Sel_ptr(addr); + if (is_Alloc(skip_Proj(skip_Cast(addr)))) { + /* simple case: a direct load after an Alloc. Firm Alloc throw + * an exception in case of out-of-memory. So, there is no way for an + * exception in this load. + * This code is constructed by the "exception lowering" in the Jack compiler. + */ + exchange(info->projs[pn_Load_X_except], new_Bad()); + info->projs[pn_Load_X_except] = NULL; + exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); + info->projs[pn_Load_X_regular] = NULL; + res |= CF_CHANGED; } } @@ -707,19 +1139,71 @@ static unsigned optimize_load(ir_node *load) exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); res |= CF_CHANGED; } - exchange(load, new_Bad()); + kill_node(load); reduce_adr_usage(ptr); return res | DF_CHANGED; } /* Load from a constant polymorphic field, where we can resolve polymorphism. */ - new_node = transform_node_Load(load); - if (new_node != load) { - if (info->projs[pn_Load_M]) { - exchange(info->projs[pn_Load_M], mem); - info->projs[pn_Load_M] = NULL; + value = transform_polymorph_Load(load); + if (value == load) { + value = NULL; + /* check if we can determine the entity that will be loaded */ + ent = find_constant_entity(ptr); + if (ent != NULL) { + if ((allocation_static == get_entity_allocation(ent)) && + (visibility_external_allocated != get_entity_visibility(ent))) { + /* a static allocation that is not external: there should be NO exception + * when loading even if we cannot replace the load itself. */ + + /* no exception, clear the info field as it might be checked later again */ + if (info->projs[pn_Load_X_except]) { + exchange(info->projs[pn_Load_X_except], new_Bad()); + info->projs[pn_Load_X_except] = NULL; + res |= CF_CHANGED; + } + if (info->projs[pn_Load_X_regular]) { + exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); + info->projs[pn_Load_X_regular] = NULL; + res |= CF_CHANGED; + } + + if (variability_constant == get_entity_variability(ent)) { + if (is_atomic_entity(ent)) { + /* Might not be atomic after + lowering of Sels. In this + case we could also load, but + it's more complicated. */ + /* more simpler case: we load the content of a constant value: + * replace it by the constant itself + */ + value = get_atomic_ent_value(ent); + } else { + if (ent->has_initializer) { + /* new style initializer */ + value = find_compound_ent_value(ptr); + } else { + /* old style initializer */ + compound_graph_path *path = get_accessed_path(ptr); + + if (path != NULL) { + assert(is_proper_compound_graph_path(path, get_compound_graph_path_length(path)-1)); + + value = get_compound_ent_value_by_path(ent, path); + DB((dbg, LEVEL_1, " Constant access at %F%F resulted in %+F\n", ent, path, value)); + free_compound_graph_path(path); + } + } + } + if (value != NULL) + value = can_replace_load_by_const(load, value); + } + } } + } + if (value != NULL) { + /* we completely replace the load by this value */ if (info->projs[pn_Load_X_except]) { exchange(info->projs[pn_Load_X_except], new_Bad()); info->projs[pn_Load_X_except] = NULL; @@ -730,116 +1214,22 @@ static unsigned optimize_load(ir_node *load) info->projs[pn_Load_X_regular] = NULL; res |= CF_CHANGED; } - if (info->projs[pn_Load_res]) - exchange(info->projs[pn_Load_res], new_node); - - exchange(load, new_Bad()); - reduce_adr_usage(ptr); - return res | DF_CHANGED; - } - - /* check if we can determine the entity that will be loaded */ - ent = find_constant_entity(ptr); - if (ent) { - if ((allocation_static == get_entity_allocation(ent)) && - (visibility_external_allocated != get_entity_visibility(ent))) { - /* a static allocation that is not external: there should be NO exception - * when loading. */ - - /* no exception, clear the info field as it might be checked later again */ - if (info->projs[pn_Load_X_except]) { - exchange(info->projs[pn_Load_X_except], new_Bad()); - info->projs[pn_Load_X_except] = NULL; - res |= CF_CHANGED; - } - if (info->projs[pn_Load_X_regular]) { - exchange(info->projs[pn_Load_X_regular], new_r_Jmp(current_ir_graph, get_nodes_block(load))); - info->projs[pn_Load_X_regular] = NULL; - res |= CF_CHANGED; - } - - if (variability_constant == get_entity_variability(ent)) { - if (is_atomic_entity(ent)) { - /* Might not be atomic after - lowering of Sels. In this - case we could also load, but - it's more complicated. */ - /* more simpler case: we load the content of a constant value: - * replace it by the constant itself - */ - - /* no memory */ - if (info->projs[pn_Load_M]) { - exchange(info->projs[pn_Load_M], mem); - res |= DF_CHANGED; - } - /* no result :-) */ - if (info->projs[pn_Load_res]) { - if (is_atomic_entity(ent)) { - ir_node *c = copy_const_value(get_irn_dbg_info(load), get_atomic_ent_value(ent)); - - DBG_OPT_RC(load, c); - exchange(info->projs[pn_Load_res], c); - res |= DF_CHANGED; - } - } - exchange(load, new_Bad()); - reduce_adr_usage(ptr); - return res; - } else { - compound_graph_path *path = get_accessed_path(ptr); - - if (path) { - ir_node *c; - - assert(is_proper_compound_graph_path(path, get_compound_graph_path_length(path)-1)); - /* - { - int j; - for (j = 0; j < get_compound_graph_path_length(path); ++j) { - ir_entity *node = get_compound_graph_path_node(path, j); - fprintf(stdout, ".%s", get_entity_name(node)); - if (is_Array_type(get_entity_owner(node))) - fprintf(stdout, "[%d]", get_compound_graph_path_array_index(path, j)); - } - printf("\n"); - } - */ - - c = get_compound_ent_value_by_path(ent, path); - free_compound_graph_path(path); - - /* printf(" cons: "); DDMN(c); */ - - if (info->projs[pn_Load_M]) { - exchange(info->projs[pn_Load_M], mem); - res |= DF_CHANGED; - } - if (info->projs[pn_Load_res]) { - exchange(info->projs[pn_Load_res], copy_const_value(get_irn_dbg_info(load), c)); - res |= DF_CHANGED; - } - exchange(load, new_Bad()); - reduce_adr_usage(ptr); - return res; - } else { - /* We can not determine a correct access path. E.g., in jack, we load - a byte from an object to generate an exception. Happens in test program - Reflectiontest. - printf(">>>>>>>>>>>>> Found access to constant entity %s in function %s\n", get_entity_name(ent), - get_entity_name(get_irg_entity(current_ir_graph))); - printf(" load: "); DDMN(load); - printf(" ptr: "); DDMN(ptr); - */ - } - } - } + if (info->projs[pn_Load_M]) { + exchange(info->projs[pn_Load_M], mem); + res |= DF_CHANGED; + } + if (info->projs[pn_Load_res]) { + exchange(info->projs[pn_Load_res], value); + res |= DF_CHANGED; } + kill_node(load); + reduce_adr_usage(ptr); + return res; } /* Check, if the address of this load is used more than once. - * If not, this load cannot be removed in any case. */ - if (get_irn_n_uses(ptr) <= 1) + * If not, more load cannot be removed in any case. */ + if (get_irn_n_uses(ptr) <= 1 && get_irn_n_uses(get_base_and_offset(ptr, &dummy)) <= 1) return res; /* @@ -894,7 +1284,7 @@ static unsigned follow_Mem_chain_for_Store(ir_node *store, ir_node *curr) { get_nodes_MacroBlock(pred) == mblk && is_completely_overwritten(get_irn_mode(get_Store_value(pred)), mode)) { /* - * a Store after a Store in the same block -- a write after write. + * a Store after a Store in the same MacroBlock -- a write after write. * We may remove the first Store, if it does not have an exception handler. * * TODO: What, if both have the same exception handler ??? @@ -902,37 +1292,45 @@ static unsigned follow_Mem_chain_for_Store(ir_node *store, ir_node *curr) { if (get_Store_volatility(pred) != volatility_is_volatile && !pred_info->projs[pn_Store_X_except]) { DBG_OPT_WAW(pred, store); exchange(pred_info->projs[pn_Store_M], get_Store_mem(pred)); - exchange(pred, new_Bad()); + kill_node(pred); reduce_adr_usage(ptr); return DF_CHANGED; } } else if (is_Load(pred) && get_Load_ptr(pred) == ptr && value == pred_info->projs[pn_Load_res]) { /* - * a Store of a value after a Load -- a write after read. - * We may remove the second Store, if it does not have an exception handler. + * a Store of a value just loaded from the same address + * -- a write after read. + * We may remove the Store, if it does not have an exception + * handler. */ if (! info->projs[pn_Store_X_except]) { DBG_OPT_WAR(store, pred); exchange(info->projs[pn_Store_M], mem); - exchange(store, new_Bad()); + kill_node(store); reduce_adr_usage(ptr); return DF_CHANGED; } } if (is_Store(pred)) { - /* check if we can pass thru this store */ + /* check if we can pass through this store */ ir_alias_relation rel = get_alias_relation( current_ir_graph, get_Store_ptr(pred), get_irn_mode(get_Store_value(pred)), ptr, mode); /* if the might be an alias, we cannot pass this Store */ - if (rel != no_alias) + if (rel != ir_no_alias) break; pred = skip_Proj(get_Store_mem(pred)); - } else if (get_irn_op(pred) == op_Load) { + } else if (is_Load(pred)) { + ir_alias_relation rel = get_alias_relation( + current_ir_graph, get_Load_ptr(pred), get_Load_mode(pred), + ptr, mode); + if (rel != ir_no_alias) + break; + pred = skip_Proj(get_Load_mem(pred)); } else { /* follow only Load chains */ @@ -958,18 +1356,61 @@ static unsigned follow_Mem_chain_for_Store(ir_node *store, ir_node *curr) { return res; } /* follow_Mem_chain_for_Store */ +/** find entity used as base for an address calculation */ +static ir_entity *find_entity(ir_node *ptr) +{ + switch(get_irn_opcode(ptr)) { + case iro_SymConst: + return get_SymConst_entity(ptr); + case iro_Sel: { + ir_node *pred = get_Sel_ptr(ptr); + if (get_irg_frame(get_irn_irg(ptr)) == pred) + return get_Sel_entity(ptr); + + return find_entity(pred); + } + case iro_Sub: + case iro_Add: { + ir_node *left = get_binop_left(ptr); + ir_node *right; + if (mode_is_reference(get_irn_mode(left))) + return find_entity(left); + right = get_binop_right(ptr); + if (mode_is_reference(get_irn_mode(right))) + return find_entity(right); + return NULL; + } + default: + return NULL; + } +} + /** * optimize a Store * * @param store the Store node */ static unsigned optimize_store(ir_node *store) { - ir_node *ptr, *mem; + ir_node *ptr; + ir_node *mem; + ir_entity *entity; if (get_Store_volatility(store) == volatility_is_volatile) return 0; - ptr = get_Store_ptr(store); + ptr = get_Store_ptr(store); + entity = find_entity(ptr); + + /* a store to an entity which is never read is unnecessary */ + if (entity != NULL && !(get_entity_usage(entity) & ir_usage_read)) { + ldst_info_t *info = get_irn_link(store); + if (info->projs[pn_Store_X_except] == NULL) { + exchange(info->projs[pn_Store_M], get_Store_mem(store)); + kill_node(store); + reduce_adr_usage(ptr); + return DF_CHANGED; + } + } /* Check, if the address of this Store is used more than once. * If not, this Store cannot be removed in any case. */ @@ -980,6 +1421,7 @@ static unsigned optimize_store(ir_node *store) { /* follow the memory chain as long as there are only Loads */ INC_MASTER(); + return follow_Mem_chain_for_Store(store, skip_Proj(mem)); } /* optimize_store */ @@ -1029,7 +1471,7 @@ static unsigned optimize_phi(ir_node *phi, walk_env_t *wenv) store = skip_Proj(projM); old_store = store; - if (get_irn_op(store) != op_Store) + if (!is_Store(store)) return 0; block = get_nodes_block(store); @@ -1305,9 +1747,12 @@ struct phi_entry { }; /** - * Move loops out of loops if possible + * Move loops out of loops if possible. + * + * @param pscc the loop described by an SCC + * @param env the loop environment */ -static void move_loads_in_loops(scc *pscc, loop_env *env) { +static void move_loads_out_of_loops(scc *pscc, loop_env *env) { ir_node *phi, *load, *next, *other, *next_other; ir_entity *ent; int j; @@ -1355,10 +1800,10 @@ static void move_loads_in_loops(scc *pscc, loop_env *env) { if (info->projs[pn_Load_res] == NULL || info->projs[pn_Load_X_regular] != NULL || info->projs[pn_Load_X_except] != NULL) continue; - /* for now, we can only handle Load(SymConst) */ - if (! is_SymConst(ptr) || get_SymConst_kind(ptr) != symconst_addr_ent) + /* for now, we can only handle Load(Global) */ + if (! is_Global(ptr)) continue; - ent = get_SymConst_entity(ptr); + ent = get_Global_entity(ptr); load_mode = get_Load_mode(load); for (other = pscc->head; other != NULL; other = next_other) { node_entry *ne = get_irn_ne(other, env); @@ -1371,9 +1816,10 @@ static void move_loads_in_loops(scc *pscc, loop_env *env) { get_irn_mode(get_Store_value(other)), ptr, load_mode); /* if the might be an alias, we cannot pass this Store */ - if (rel != no_alias) + if (rel != ir_no_alias) break; } + /* only pure Calls are allowed here, so ignore them */ } if (other == NULL) { ldst_info_t *ninfo; @@ -1414,7 +1860,7 @@ static void move_loads_in_loops(scc *pscc, loop_env *env) { } } } -} /* move_loads_in_loops */ +} /* move_loads_out_of_loops */ /** * Process a loop SCC. @@ -1458,8 +1904,15 @@ static void process_loop(scc *pscc, loop_env *env) { next = e->next; switch (get_irn_opcode(irn)) { case iro_Call: + if (is_Call_pure(irn)) { + /* pure calls can be treated like loads */ + only_phi = 0; + break; + } + /* non-pure calls must be handle like may-alias Stores */ + goto fail; case iro_CopyB: - /* cannot handle Calls or CopyB yet */ + /* cannot handle CopyB yet */ goto fail; case iro_Load: process = 1; @@ -1529,7 +1982,7 @@ static void process_loop(scc *pscc, loop_env *env) { } DB((dbg, LEVEL_2, "\n")); - move_loads_in_loops(pscc, env); + move_loads_out_of_loops(pscc, env); fail: ; @@ -1661,6 +2114,7 @@ static void do_dfs(ir_graph *irg, loop_env *env) { for (i = get_Block_n_cfgpreds(endblk) - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred(endblk, i); + pred = skip_Proj(pred); if (is_Return(pred)) dfs(get_Return_mem(pred), env); else if (is_Raise(pred)) @@ -1738,8 +2192,8 @@ void optimize_load_store(ir_graph *irg) { assure_postdoms(irg); if (get_opt_alias_analysis()) { - assure_irg_address_taken_computed(irg); - assure_irp_globals_address_taken_computed(); + assure_irg_entity_usage_computed(irg); + assure_irp_globals_entity_usage_computed(); } obstack_init(&env.obst); @@ -1759,6 +2213,7 @@ void optimize_load_store(ir_graph *irg) { /* Handle graph state */ if (env.changes) { set_irg_outs_inconsistent(irg); + set_irg_entity_usage_state(irg, ir_entity_usage_not_computed); } if (env.changes & CF_CHANGED) {