X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Ffp-vrp.c;h=8f286223faef3ddb92cecff9e44460b9cc9985b4;hb=4e0288d4c454f3cded36e0b81e97be03dca528db;hp=90562918c5d04c3d9427673a039056bf2f96270c;hpb=d5358b95c8dcf2c101181e9cd293953960e8c58d;p=libfirm diff --git a/ir/opt/fp-vrp.c b/ir/opt/fp-vrp.c index 90562918c..8f286223f 100644 --- a/ir/opt/fp-vrp.c +++ b/ir/opt/fp-vrp.c @@ -1,30 +1,16 @@ /* - * Copyright (C) 1995-2010 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. + * Copyright (C) 2012 University of Karlsruhe. */ /** * @file * @brief Data-flow driven minimal fixpoint value range propagation * @author Christoph Mallon - * @version $Id$ */ #include "config.h" +#include #include #include "adt/pdeq.h" @@ -35,9 +21,9 @@ #include "irdom.h" #include "iredges.h" #include "irgmod.h" -#include "irgraph.h" +#include "irgraph_t.h" #include "irgwalk.h" -#include "irnode.h" +#include "irnode_t.h" #include "iroptimize.h" #include "irtools.h" #include "tv.h" @@ -151,6 +137,10 @@ static int set_bitinfo(ir_node* const irn, ir_tarval* const z, ir_tarval* const set_irn_link(irn, b); } else if (z == b->z && o == b->o) { return 0; + } else { + /* Assert monotonicity. */ + assert(tarval_is_null(tarval_andnot(b->z, z))); + assert(tarval_is_null(tarval_andnot(o, b->o))); } b->z = z; b->o = o; @@ -171,6 +161,8 @@ static int transfer(ir_node* const irn) ir_tarval* z; ir_tarval* o; + if (is_Bad(irn)) return 0; + if (m == mode_X) { bitinfo* const b = get_bitinfo(get_nodes_block(irn)); @@ -189,37 +181,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; } @@ -270,7 +249,7 @@ result_unknown_X: DB((dbg, LEVEL_3, "transfer %+F\n", irn)); - if (b->z == f) { + if (b == NULL || b->z == f) { undefined: z = get_tarval_null(m); o = get_tarval_all_one(m); @@ -316,6 +295,11 @@ undefined: /* TODO Use bound and relation. */ z = b->z; o = b->o; + if ((get_Confirm_relation(irn) & ~ir_relation_unordered) == ir_relation_equal) { + bitinfo* const bound_b = get_bitinfo(get_Confirm_bound(irn)); + z = tarval_and(z, bound_b->z); + o = tarval_or( o, bound_b->o); + } break; } @@ -437,9 +421,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); } @@ -627,6 +611,18 @@ static void first_round(ir_node* const irn, void* const env) } } +static ir_node *make_bad_block(ir_graph *irg) +{ + ir_node *bad = new_r_Bad(irg, mode_BB); + bitinfo *bb = get_bitinfo(bad); + if (bb == NULL) { + ir_tarval* const f = get_tarval_b_false(); + ir_tarval* const t = get_tarval_b_true(); + set_bitinfo(bad, f, t); /* Undefined. */ + } + return bad; +} + static void apply_result(ir_node* const irn, void* ctx) { environment_t* env = (environment_t*)ctx; @@ -640,7 +636,8 @@ static void apply_result(ir_node* const irn, void* ctx) block_b = get_bitinfo(irn); /* Trivially unreachable blocks have no info. */ if (block_b == NULL || block_b->z == get_tarval_b_false()) { - exchange(irn, get_irg_bad(get_Block_irg(irn))); + ir_node *bad = make_bad_block(get_irn_irg(irn)); + exchange(irn, bad); env->modified = 1; } return; @@ -651,7 +648,10 @@ static void apply_result(ir_node* const irn, void* ctx) /* Trivially unreachable blocks have no info. */ if (block_b == NULL || block_b->z == get_tarval_b_false()) { /* Unreachable blocks might be replaced before the nodes in them. */ - exchange(irn, is_Bad(block) ? block : get_irg_bad(get_Block_irg(block))); + ir_mode *mode = get_irn_mode(irn); + ir_graph *irg = get_irn_irg(irn); + ir_node *bad = new_r_Bad(irg, mode); + exchange(irn, bad); env->modified = 1; return; } @@ -676,11 +676,9 @@ 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); + n = new_r_Bad(irg, mode_X); /* Transferring analysis information to the bad node makes it a * candidate for replacement. */ goto exchange_only; @@ -700,16 +698,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; } } @@ -721,19 +755,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; } } @@ -745,7 +791,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); @@ -757,7 +802,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) { @@ -791,27 +835,26 @@ void fixpoint_vrp(ir_graph* const irg) FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp"); DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg)); - obstack_init(&obst); - - /* HACK: to avoid finding dead code */ - edges_deactivate(irg); - edges_activate(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); - edges_assure(irg); - assure_doms(irg); + obstack_init(&obst); ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); { pdeq* const q = new_pdeq(); - /* We need this extra step because the dom tree does not contain unreachable - blocks in Firm. Moreover build phi list. */ + /* We need this extra step because the dom tree does not contain + * unreachable blocks in Firm. Moreover build phi list. */ irg_walk_anchors(irg, clear_links, build_phi_lists, NULL); - { ir_tarval* const f = get_tarval_b_false(); + { + ir_tarval* const f = get_tarval_b_false(); ir_tarval* const t = get_tarval_b_true(); - set_bitinfo(get_irg_bad(irg), f, t); /* Undefined. */ set_bitinfo(get_irg_end_block(irg), t, f); /* Reachable. */ } @@ -832,18 +875,11 @@ void fixpoint_vrp(ir_graph* const irg) env.modified = 0; irg_walk_graph(irg, NULL, apply_result, &env); - if (env.modified) { - /* control flow might changed */ - set_irg_outs_inconsistent(irg); - set_irg_extblk_inconsistent(irg); - set_irg_doms_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); - set_irg_entity_usage_state(irg, ir_entity_usage_not_computed); - } - ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); obstack_free(&obst, NULL); + 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)