X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_osr.c;h=3175ca94d6ab093c890e3411b4c2da307bb9a815;hb=555593b0aebec433b871920acc2b0a869b072055;hp=9f8043e992d96af87f63c02dc83fca603fecfaad;hpb=15ad7ccd8dff64e1808e1d093d4a8d7cda5af33e;p=libfirm diff --git a/ir/opt/opt_osr.c b/ir/opt/opt_osr.c index 9f8043e99..3175ca94d 100644 --- a/ir/opt/opt_osr.c +++ b/ir/opt/opt_osr.c @@ -22,7 +22,6 @@ * @brief Operator Strength Reduction. * @date 12.5.2006 * @author Michael Beck - * @version $Id$ * @brief * Implementation of the Operator Strength Reduction algorithm * by Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick. @@ -46,10 +45,11 @@ #include "set.h" #include "tv.h" #include "hashptr.h" +#include "util.h" #include "irtools.h" #include "irloop_t.h" #include "array.h" -#include "firmstat.h" +#include "firmstat_t.h" #include "error.h" #include "irpass_t.h" @@ -139,7 +139,7 @@ static LFTR_edge *LFTR_find(ir_node *src, iv_env *env) key.src = src; - return (LFTR_edge*)set_find(env->lftr_edges, &key, sizeof(key), HASH_PTR(src)); + return set_find(LFTR_edge, env->lftr_edges, &key, sizeof(key), hash_ptr(src)); } /* LFTR_find */ /** @@ -164,7 +164,7 @@ static void LFTR_add(ir_node *src, ir_node *dst, unsigned code, ir_node *rc, iv_ * There might be more than one edge here. This is rather bad * because we currently store only one. */ - set_insert(env->lftr_edges, &key, sizeof(key), HASH_PTR(src)); + (void)set_insert(LFTR_edge, env->lftr_edges, &key, sizeof(key), hash_ptr(src)); } /* LFTR_add */ /** @@ -253,8 +253,7 @@ static ir_node *search(unsigned code, ir_node *op1, ir_node *op2, iv_env *env) key.op1 = op1; key.op2 = op2; - entry = (quadruple_t*)set_find(env->quad_map, &key, sizeof(key), - (code * 9) ^ HASH_PTR(op1) ^HASH_PTR(op2)); + entry = set_find(quadruple_t, env->quad_map, &key, sizeof(key), (code * 9) ^ hash_ptr(op1) ^ hash_ptr(op2)); if (entry) return entry->res; return NULL; @@ -278,8 +277,7 @@ static void add(unsigned code, ir_node *op1, ir_node *op2, ir_node *result, iv_e key.op2 = op2; key.res = result; - set_insert(env->quad_map, &key, sizeof(key), - (code * 9) ^ HASH_PTR(op1) ^HASH_PTR(op2)); + (void)set_insert(quadruple_t, env->quad_map, &key, sizeof(key), (code * 9) ^ hash_ptr(op1) ^ hash_ptr(op2)); } /* add */ /** @@ -608,16 +606,13 @@ static int is_counter_iv(ir_node *iv, iv_env *env) */ static int check_users_for_reg_pressure(ir_node *iv, iv_env *env) { - ir_node *irn, *header; + ir_node *irn; ir_node *have_user = NULL; ir_node *have_cmp = NULL; node_entry *e = get_irn_ne(iv, env); scc *pscc = e->pscc; - header = e->header; for (irn = pscc->head; irn != NULL; irn = e->next) { - const ir_edge_t *edge; - foreach_out_edge(irn, edge) { ir_node *user = get_edge_src_irn(edge); node_entry *ne = get_irn_ne(user, env); @@ -761,8 +756,26 @@ static void classify_iv(scc *pscc, iv_env *env) next = e->next; switch (get_irn_opcode(irn)) { - case iro_Add: case iro_Sub: + only_phi = 0; + { + ir_node *left = get_Sub_left(irn); + node_entry *left_entry = get_irn_ne(left, env); + ir_node *right = get_Sub_right(irn); + node_entry *right_entry = get_irn_ne(right, env); + + if (left_entry->pscc != e->pscc || + (right_entry->pscc != e->pscc && !is_rc(right, header))) { + /* + * Not an induction variable. + * Region constant are only allowed on right hand side. + */ + goto fail; + } + } + break; + + case iro_Add: only_phi = 0; /* fall through */ case iro_Phi: @@ -872,7 +885,7 @@ static void remove_phi_cycle(scc *pscc, iv_env *env) int j; ir_node *out_rc; - /* check if this scc contains only Phi, Add or Sub nodes */ + /* check if this scc contains only Phi nodes */ out_rc = NULL; for (irn = pscc->head; irn; irn = next) { node_entry *e = get_irn_ne(irn, env); @@ -1156,6 +1169,12 @@ static ir_node *applyOneEdge(ir_node *iv, ir_node *rc, LFTR_edge *e, iv_env *env panic("Unsupported opcode"); } + if (tv == tarval_bad || tv_init == tarval_bad) { + tarval_set_integer_overflow_mode(ovmode); + DB((dbg, LEVEL_4, " = OVERFLOW")); + return NULL; + } + if (pscc->code == iro_Add) { tv_end = tarval_add(tv, tv_incr); } else { @@ -1165,7 +1184,7 @@ static ir_node *applyOneEdge(ir_node *iv, ir_node *rc, LFTR_edge *e, iv_env *env tarval_set_integer_overflow_mode(ovmode); - if (tv == tarval_bad || tv_init == tarval_bad || tv_end == tarval_bad) { + if (tv_end == tarval_bad) { DB((dbg, LEVEL_4, " = OVERFLOW")); return NULL; } @@ -1269,32 +1288,15 @@ static void lftr(ir_graph *irg, iv_env *env) irg_walk_graph(irg, NULL, do_lftr, env); } /* lftr */ -/** - * Pre-walker: set all node links to NULL and fix the - * block of Proj nodes. - */ -static void clear_and_fix(ir_node *irn, void *env) -{ - int *moved = (int*)env; - set_irn_link(irn, NULL); - - if (is_Proj(irn)) { - ir_node *pred = get_Proj_pred(irn); - ir_node *pred_block = get_nodes_block(pred); - - if (get_nodes_block(irn) != pred_block) { - set_nodes_block(irn, pred_block); - *moved = 1; - } - } -} /* clear_and_fix */ - - /* Remove any Phi cycles with only one real input. */ void remove_phi_cycles(ir_graph *irg) { iv_env env; - int projs_moved; + + assure_irg_properties(irg, + IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE + | IR_GRAPH_PROPERTY_CONSISTENT_OUTS + | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES); FIRM_DBG_REGISTER(dbg, "firm.opt.remove_phi"); @@ -1317,13 +1319,7 @@ void remove_phi_cycles(ir_graph *irg) * the same block as their predecessors. * This can improve the placement of new nodes. */ - projs_moved = 0; - irg_walk_graph(irg, NULL, clear_and_fix, &projs_moved); - if (projs_moved) - set_irg_outs_inconsistent(irg); - - /* we need outs for calculating the post order */ - assure_irg_outs(irg); + irg_walk_graph(irg, NULL, firm_clear_link, NULL); /* calculate the post order number for blocks. */ irg_out_block_walk(get_irg_start_block(irg), NULL, assign_po, &env); @@ -1334,13 +1330,15 @@ void remove_phi_cycles(ir_graph *irg) ir_free_resources(irg, IR_RESOURCE_IRN_LINK); if (env.replaced) { - set_irg_outs_inconsistent(irg); - DB((dbg, LEVEL_1, "remove_phi_cycles: %u Cycles removed\n\n", env.replaced)); + DB((dbg, LEVEL_1, "remove_phi_cycles: %u Cycles removed\n\n", + env.replaced)); } DEL_ARR_F(env.stack); obstack_free(&env.obst, NULL); -} /* remove_phi_cycles */ + + confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_CONTROL_FLOW); +} ir_graph_pass_t *remove_phi_cycles_pass(const char *name) { @@ -1418,12 +1416,15 @@ static void fix_adds_and_subs(ir_node *irn, void *ctx) /* Performs Operator Strength Reduction for the passed graph. */ void opt_osr(ir_graph *irg, unsigned flags) { - iv_env env; - int edges; - int projs_moved; + iv_env env; FIRM_DBG_REGISTER(dbg, "firm.opt.osr"); + assure_irg_properties(irg, + IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE + | IR_GRAPH_PROPERTY_CONSISTENT_OUTS + | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES); + DB((dbg, LEVEL_1, "Doing Operator Strength Reduction for %+F\n", irg)); obstack_init(&env.obst); @@ -1443,18 +1444,8 @@ void opt_osr(ir_graph *irg, unsigned flags) * the same block as its predecessors. * This can improve the placement of new nodes. */ - projs_moved = 0; - irg_walk_graph(irg, NULL, clear_and_fix, &projs_moved); - if (projs_moved) - set_irg_outs_inconsistent(irg); - - /* we need dominance */ - assure_doms(irg); - - edges = edges_assure(irg); + irg_walk_graph(irg, NULL, firm_clear_link, NULL); - /* calculate the post order number for blocks by walking the out edges. */ - assure_irg_outs(irg); irg_block_edges_walk(get_irg_start_block(irg), NULL, assign_po, &env); /* calculate the SCC's and drive OSR. */ @@ -1469,7 +1460,6 @@ void opt_osr(ir_graph *irg, unsigned flags) lftr(irg, &env); (void)lftr; - set_irg_outs_inconsistent(irg); DB((dbg, LEVEL_1, "Replacements: %u + %u (lftr)\n\n", env.replaced, env.lftr_replaced)); } ir_free_resources(irg, IR_RESOURCE_IRN_LINK); @@ -1479,9 +1469,8 @@ void opt_osr(ir_graph *irg, unsigned flags) DEL_ARR_F(env.stack); obstack_free(&env.obst, NULL); - if (! edges) - edges_deactivate(irg); -} /* opt_osr */ + confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE); +} typedef struct pass_t { ir_graph_pass_t pass;