X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ffp-vrp.c;h=f365ec2dc09aea12be37439aff17f0dcd88fb2ab;hb=7ad86c1baab2fdceae2aa610bb584b30538cc5c6;hp=f642e71475150173317f37ee81ded45fee6e7700;hpb=8a98cf06c4fb193ea8025a6dfcdbe161187d143f;p=libfirm diff --git a/ir/opt/fp-vrp.c b/ir/opt/fp-vrp.c index f642e7147..f365ec2dc 100644 --- a/ir/opt/fp-vrp.c +++ b/ir/opt/fp-vrp.c @@ -21,7 +21,6 @@ * @file * @brief Data-flow driven minimal fixpoint value range propagation * @author Christoph Mallon - * @version $Id$ */ #include "config.h" @@ -44,7 +43,6 @@ #include "tv.h" #include "irpass.h" #include "irmemory.h" -#include "opt_manage.h" /* TODO: * - Implement cleared/set bit calculation for Add, Sub, Minus, Mul, Div, Mod, Shl, Shr, Shrs, Rotl @@ -197,37 +195,24 @@ unreachable_X: } else if (is_Cond(pred)) { ir_node* const selector = get_Cond_selector(pred); bitinfo* const b = get_bitinfo(selector); - if (is_undefined(b)) { + if (is_undefined(b)) goto unreachable_X; - } else if (get_irn_mode(selector) == mode_b) { - if (b->z == b->o) { - if ((b->z == t) == get_Proj_proj(irn)) { - z = o = t; - } else { - z = o = f; - } + if (b->z == b->o) { + if ((b->z == t) == get_Proj_proj(irn)) { + z = o = t; } else { - goto result_unknown_X; + z = o = f; } } else { - long const val = get_Proj_proj(irn); - if (val != get_Cond_default_proj(pred)) { - ir_tarval* const tv = new_tarval_from_long(val, get_irn_mode(selector)); - if (!tarval_is_null(tarval_andnot(tv, b->z)) || - !tarval_is_null(tarval_andnot(b->o, tv))) { - // At least one bit differs. - z = o = f; -#if 0 // TODO must handle default Proj - } else if (b->z == b->o && b->z == tv) { - z = o = t; -#endif - } else { - goto result_unknown_X; - } - } else { - goto cannot_analyse_X; - } + goto result_unknown_X; } + } else if (is_Switch(pred)) { + ir_node* const selector = get_Switch_selector(pred); + bitinfo* const b = get_bitinfo(selector); + if (is_undefined(b)) + goto unreachable_X; + /* TODO */ + goto cannot_analyse_X; } else { goto cannot_analyse_X; } @@ -450,9 +435,9 @@ undefined: ir_tarval* const rzn = tarval_or(rz, tarval_neg(rz)); // Concatenate safe lower zeroes. if (tarval_cmp(lzn, rzn) == ir_relation_less) { - z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn); + z = tarval_mul(tarval_eor(lzn, tarval_shl_unsigned(lzn, 1)), rzn); } else { - z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn); + z = tarval_mul(tarval_eor(rzn, tarval_shl_unsigned(rzn, 1)), lzn); } o = get_tarval_null(m); } @@ -705,8 +690,6 @@ static void apply_result(ir_node* const irn, void* ctx) } else if (m == mode_X) { ir_graph* const irg = get_Block_irg(block); if (z == get_tarval_b_true()) { - // Might produce an endless loop, so keep the block. - add_End_keepalive(get_irg_end(irg), block); n = new_r_Jmp(block); } else { n = new_r_Bad(irg, mode_X); @@ -729,16 +712,52 @@ exchange_only: ir_node* const r = get_And_right(irn); bitinfo const* const bl = get_bitinfo(l); bitinfo const* const br = get_bitinfo(r); - if (bl->z == bl->o) { - if (tarval_is_null(tarval_andnot(br->z, bl->z))) { - DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); - exchange(irn, r); - env->modified = 1; - } - } else if (br->z == br->o) { - if (tarval_is_null(tarval_andnot(bl->z, br->z))) { - DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); - exchange(irn, l); + if (tarval_is_null(tarval_andnot(br->z, bl->o))) { + DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); + exchange(irn, r); + env->modified = 1; + } else if (tarval_is_null(tarval_andnot(bl->z, br->o))) { + DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); + exchange(irn, l); + env->modified = 1; + } + break; + } + + case iro_Eor: { + ir_node* const l = get_Eor_left(irn); + ir_node* const r = get_Eor_right(irn); + bitinfo const* const bl = get_bitinfo(l); + bitinfo const* const br = get_bitinfo(r); + /* if each bit is guaranteed to be zero on either the left or right + * then an Add will have the same effect as the Eor. Change it for + * normalisation */ + if (tarval_is_null(tarval_and(bl->z, br->z))) { + dbg_info *dbgi = get_irn_dbg_info(irn); + ir_node *block = get_nodes_block(irn); + ir_mode *mode = get_irn_mode(irn); + ir_node *new_node = new_rd_Add(dbgi, block, l, r, mode); + bitinfo const *bi = get_bitinfo(irn); + DB((dbg, LEVEL_2, "%+F(%+F, %+F) normalised to Add\n", irn, l, r)); + set_bitinfo(new_node, bi->z, bi->o); + exchange(irn, new_node); + env->modified = 1; + } + break; + } + + case iro_Minus: { + ir_mode *mode = get_irn_mode(irn); + + /* If all bits except the highest bit are zero the Minus is superfluous. */ + if (get_mode_arithmetic(mode) == irma_twos_complement) { + ir_node *const op = get_Minus_op(irn); + bitinfo const *const b = get_bitinfo(op); + ir_tarval *const min = get_mode_min(mode); + + if (b->z == min) { + DB((dbg, LEVEL_2, "%+F(%+F) is superfluous\n", irn, op)); + exchange(irn, op); env->modified = 1; } } @@ -750,19 +769,31 @@ exchange_only: ir_node* const r = get_Or_right(irn); bitinfo const* const bl = get_bitinfo(l); bitinfo const* const br = get_bitinfo(r); - if (bl->z == bl->o) { - if (tarval_is_null(tarval_andnot(bl->o, br->o))) { - DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); - exchange(irn, r); - env->modified = 1; - } - } else if (br->z == br->o) { - if (tarval_is_null(tarval_andnot(br->o, bl->o))) { - DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); - exchange(irn, l); - env->modified = 1; - } + if (tarval_is_null(tarval_andnot(bl->z, br->o))) { + DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); + exchange(irn, r); + env->modified = 1; + } else if (tarval_is_null(tarval_andnot(br->z, bl->o))) { + DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r)); + exchange(irn, l); + env->modified = 1; } + + /* if each bit is guaranteed to be zero on either the left or right + * then an Add will have the same effect as the Or. Change it for + * normalisation */ + if (tarval_is_null(tarval_and(bl->z, br->z))) { + dbg_info *dbgi = get_irn_dbg_info(irn); + ir_node *block = get_nodes_block(irn); + ir_mode *mode = get_irn_mode(irn); + ir_node *new_node = new_rd_Add(dbgi, block, l, r, mode); + bitinfo const *bi = get_bitinfo(irn); + DB((dbg, LEVEL_2, "%+F(%+F, %+F) normalised to Add\n", irn, l, r)); + set_bitinfo(new_node, bi->z, bi->o); + exchange(irn, new_node); + env->modified = 1; + } + break; } } @@ -774,7 +805,6 @@ static void queue_users(pdeq* const q, ir_node* const n) /* When the state of a control flow node changes, not only queue its * successor blocks, but also the Phis in these blocks, because the Phis * must reconsider this input path. */ - ir_edge_t const* e; foreach_out_edge(n, e) { ir_node* const src = get_edge_src_irn(e); pdeq_putr(q, src); @@ -786,7 +816,6 @@ static void queue_users(pdeq* const q, ir_node* const n) } } } else { - ir_edge_t const* e; foreach_out_edge(n, e) { ir_node* const src = get_edge_src_irn(e); if (get_irn_mode(src) == mode_T) { @@ -813,14 +842,19 @@ static void build_phi_lists(ir_node *irn, void *env) add_Block_phi(get_nodes_block(irn), irn); } -static ir_graph_state_t do_fixpoint_vrp(ir_graph* const irg) +void fixpoint_vrp(ir_graph* const irg) { environment_t env; - ir_graph_state_t res = 0; FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp"); DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg)); + assure_irg_properties(irg, + IR_GRAPH_PROPERTY_NO_BADS + | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE + | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE + | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES); + obstack_init(&obst); ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); @@ -855,26 +889,11 @@ static ir_graph_state_t do_fixpoint_vrp(ir_graph* const irg) env.modified = 0; irg_walk_graph(irg, NULL, apply_result, &env); - if (! env.modified) { - res |= IR_GRAPH_STATE_CONSISTENT_DOMINANCE | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE; - } - ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); obstack_free(&obst, NULL); - - return res; -} - -optdesc_t opt_fpvrp = { - "fp-vrp", - IR_GRAPH_STATE_NO_BAD_BLOCKS | IR_GRAPH_STATE_NO_UNREACHABLE_BLOCKS | IR_GRAPH_STATE_CONSISTENT_DOMINANCE | IR_GRAPH_STATE_CONSISTENT_OUT_EDGES, - do_fixpoint_vrp, -}; - -void fixpoint_vrp(ir_graph* const irg) -{ - perform_irg_optimization(irg, &opt_fpvrp); + confirm_irg_properties(irg, + env.modified ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL); } ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name)