X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fldstopt.c;h=6d42668a8efa9e61619760e1413ecb2834a535eb;hb=f600524c363556c785b85c0dff8792d04f73e252;hp=726a0bc61b9e2a454eefe83bccedf6291a7bb5f6;hpb=d7230a4744192c443aac403a0b4b0b3987fc5413;p=libfirm diff --git a/ir/opt/ldstopt.c b/ir/opt/ldstopt.c index 726a0bc61..6d42668a8 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); @@ -356,7 +319,7 @@ static ir_entity *find_constant_entity(ir_node *ptr) */ static long get_Sel_array_index_long(ir_node *n, int dim) { ir_node *index = get_Sel_index(n, dim); - assert(get_irn_op(index) == op_Const); + assert(is_Const(index)); return get_tarval_long(get_Const_tarval(index)); } /* get_Sel_array_index_long */ @@ -428,7 +391,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 +435,30 @@ 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 */ + +/** + * 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. @@ -539,7 +523,7 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { if (info->projs[pn_Load_res]) exchange(info->projs[pn_Load_res], value); - exchange(load, new_Bad()); + kill_node(load); reduce_adr_usage(ptr); return res | DF_CHANGED; } @@ -588,7 +572,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; } @@ -605,8 +589,17 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { if (rel != 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; @@ -625,7 +618,7 @@ static unsigned follow_Mem_chain(ir_node *load, ir_node *curr) { for (i = get_Sync_n_preds(pred) - 1; i >= 0; --i) { res |= follow_Mem_chain(load, skip_Proj(get_Sync_pred(pred, i))); if (res) - break; + return res; } } @@ -707,7 +700,7 @@ 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; } @@ -733,7 +726,7 @@ static unsigned optimize_load(ir_node *load) if (info->projs[pn_Load_res]) exchange(info->projs[pn_Load_res], new_node); - exchange(load, new_Bad()); + kill_node(load); reduce_adr_usage(ptr); return res | DF_CHANGED; } @@ -758,79 +751,80 @@ static unsigned optimize_load(ir_node *load) res |= CF_CHANGED; } - if (variability_constant == get_entity_variability(ent) - && 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 if (variability_constant == get_entity_variability(ent)) { - 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 (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]) { - exchange(info->projs[pn_Load_res], copy_const_value(get_irn_dbg_info(load), c)); - res |= DF_CHANGED; + 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()); + kill_node(load); 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); - */ + 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; + } + kill_node(load); + 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); + */ + } } } } @@ -901,20 +895,22 @@ 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; } @@ -932,6 +928,12 @@ static unsigned follow_Mem_chain_for_Store(ir_node *store, ir_node *curr) { break; pred = skip_Proj(get_Store_mem(pred)); } else if (get_irn_op(pred) == op_Load) { + ir_alias_relation rel = get_alias_relation( + current_ir_graph, get_Load_ptr(pred), get_Load_mode(pred), + ptr, mode); + if (rel != no_alias) + break; + pred = skip_Proj(get_Load_mem(pred)); } else { /* follow only Load chains */ @@ -1200,6 +1202,7 @@ static void do_load_store_optimize(ir_node *n, void *env) { case iro_Phi: wenv->changes |= optimize_phi(n, wenv); + break; default: ; @@ -1303,9 +1306,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; @@ -1353,10 +1359,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); @@ -1372,6 +1378,7 @@ static void move_loads_in_loops(scc *pscc, loop_env *env) { if (rel != no_alias) break; } + /* only pure Calls are allowed here, so ignore them */ } if (other == NULL) { ldst_info_t *ninfo; @@ -1412,7 +1419,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. @@ -1456,8 +1463,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; @@ -1527,7 +1541,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: ; @@ -1659,6 +1673,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)) @@ -1684,7 +1699,7 @@ static void do_dfs(ir_graph *irg, loop_env *env) { /** * Initialize new phase data. We do this always explicit, so return NULL here */ -static void *init_loop_data(ir_phase *ph, ir_node *irn, void *data) { +static void *init_loop_data(ir_phase *ph, const ir_node *irn, void *data) { (void)ph; (void)irn; (void)data; @@ -1722,23 +1737,16 @@ void optimize_load_store(ir_graph *irg) { walk_env_t env; FIRM_DBG_REGISTER(dbg, "firm.opt.ldstopt"); - firm_dbg_set_mask(dbg, SET_LEVEL_4); assert(get_irg_phase_state(irg) != phase_building); assert(get_irg_pinned(irg) != op_pin_state_floats && "LoadStore optimization needs pinned graph"); - if (! get_opt_redundant_loadstore()) - return; - /* we need landing pads */ remove_critical_cf_edges(irg); edges_assure(irg); - /* loop optimizations need dominators ... */ - assure_doms(irg); - /* for Phi optimization post-dominators are needed ... */ assure_postdoms(irg);