X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fvrp.c;h=ac200f40d061464616c677d89770a277723d190c;hb=3c3425a50a1d721b74a015c6812257e32feeac85;hp=10d1896795e9aff2568e526056a291cf27f25197;hpb=8b5aac95f0921dc70b53f2526f7a7413df3f6f85;p=libfirm diff --git a/ir/ana/vrp.c b/ir/ana/vrp.c index 10d189679..ac200f40d 100644 --- a/ir/ana/vrp.c +++ b/ir/ana/vrp.c @@ -21,7 +21,6 @@ * @file * @brief analyze graph to provide value range information * @author Jonas Fietz - * @version $Id$ */ #include "config.h" @@ -37,23 +36,47 @@ #include "tv.h" #include "irop.h" #include "pdeq.h" -#include "irphase_t.h" +#include "irnodemap.h" +#include "irhooks.h" #include "bitset.h" #include "debug.h" -DEBUG_ONLY(static firm_dbg_module_t *dbg); +DEBUG_ONLY(static firm_dbg_module_t *dbg;) typedef struct vrp_env_t { - waitq *workqueue; - bitset_t *visited; + waitq *workqueue; + bitset_t *visited; + ir_vrp_info *info; } vrp_env_t; -static vrp_attr *get_vrp_attr(const ir_node *node) +static vrp_attr *vrp_get_or_set_info(ir_vrp_info *info, const ir_node *node) { - return (vrp_attr*) get_or_set_irn_phase_info(node, PHASE_VRP); + vrp_attr *attr = ir_nodemap_get(vrp_attr, &info->infos, node); + if (attr == NULL) { + ir_mode *mode = get_irn_mode(node); + assert(mode_is_int(mode)); + + attr = OALLOCZ(&info->obst, vrp_attr); + attr->range_type = VRP_UNDEFINED; + attr->bits_set = get_mode_null(mode); + attr->bits_not_set = get_mode_all_one(mode); + attr->range_bottom = get_tarval_top(); + attr->range_top = get_tarval_top(); + + ir_nodemap_insert(&info->infos, node, attr); + } + return attr; } -static int vrp_update_node(ir_node *node) +vrp_attr *vrp_get_info(const ir_node *node) +{ + ir_graph *irg = get_irn_irg(node); + if (irg->vrp.infos.data == NULL) + return NULL; + return ir_nodemap_get(vrp_attr, &irg->vrp.infos, node); +} + +static int vrp_update_node(ir_vrp_info *info, ir_node *node) { ir_tarval *new_bits_set = get_tarval_bad(); ir_tarval *new_bits_not_set = get_tarval_bad(); @@ -67,7 +90,7 @@ static int vrp_update_node(ir_node *node) return 0; /* we don't optimize for non-int-nodes*/ } - vrp = get_vrp_attr(node); + vrp = vrp_get_or_set_info(info, node); /* TODO: Check if all predecessors have valid VRP information*/ @@ -87,8 +110,8 @@ static int vrp_update_node(ir_node *node) left = get_And_left(node); right = get_And_right(node); - vrp_left = get_vrp_attr(left); - vrp_right = get_vrp_attr(right); + vrp_left = vrp_get_or_set_info(info, left); + vrp_right = vrp_get_or_set_info(info, right); new_bits_set = tarval_and(vrp_left->bits_set, vrp_right->bits_set); new_bits_not_set = tarval_and(vrp_left->bits_not_set, vrp_right->bits_not_set); @@ -99,8 +122,8 @@ static int vrp_update_node(ir_node *node) int overflow_top, overflow_bottom; ir_tarval *new_top, *new_bottom; const vrp_attr *vrp_left, *vrp_right; - vrp_left = get_vrp_attr(get_Add_left(node)); - vrp_right = get_vrp_attr(get_Add_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Add_left(node)); + vrp_right = vrp_get_or_set_info(info, get_Add_right(node)); if (vrp_left->range_type == VRP_UNDEFINED || vrp_right->range_type == VRP_UNDEFINED || vrp_left->range_type == VRP_VARYING || @@ -128,11 +151,17 @@ static int vrp_update_node(ir_node *node) } case iro_Sub: { + ir_node *left = get_Sub_left(node); + ir_node *right = get_Sub_right(node); int overflow_top, overflow_bottom; ir_tarval *new_top, *new_bottom; const vrp_attr *vrp_left, *vrp_right; - vrp_left = get_vrp_attr(get_Sub_left(node)); - vrp_right = get_vrp_attr(get_Sub_right(node)); + + if (!mode_is_int(get_irn_mode(left))) + return 0; + + vrp_left = vrp_get_or_set_info(info, left); + vrp_right = vrp_get_or_set_info(info, right); if (vrp_left->range_type == VRP_UNDEFINED || vrp_right->range_type == VRP_UNDEFINED || vrp_left->range_type == VRP_VARYING || @@ -161,8 +190,8 @@ static int vrp_update_node(ir_node *node) case iro_Or: { const vrp_attr *vrp_left, *vrp_right; - vrp_left = get_vrp_attr(get_Or_left(node)); - vrp_right = get_vrp_attr(get_Or_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Or_left(node)); + vrp_right = vrp_get_or_set_info(info, get_Or_right(node)); new_bits_set = tarval_or(vrp_left->bits_set, vrp_right->bits_set); new_bits_not_set = tarval_or(vrp_left->bits_not_set, vrp_right->bits_not_set); @@ -171,26 +200,23 @@ static int vrp_update_node(ir_node *node) } case iro_Rotl: { - const vrp_attr *vrp_left, *vrp_right; + const vrp_attr *vrp_left; const ir_node *right = get_Rotl_right(node); - vrp_left = get_vrp_attr(get_Rotl_left(node)); - vrp_right = get_vrp_attr(get_Rotl_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Rotl_left(node)); /* We can only compute this if the right value is a constant*/ if (is_Const(right)) { - ir_tarval *bits_set, *bits_not_set; - bits_set = tarval_rotl(vrp_left->bits_set, get_Const_tarval(right)); - bits_not_set = tarval_rotl(vrp_left->bits_not_set, get_Const_tarval(right)); + new_bits_set = tarval_rotl(vrp_left->bits_set, get_Const_tarval(right)); + new_bits_not_set = tarval_rotl(vrp_left->bits_not_set, get_Const_tarval(right)); } break; } case iro_Shl: { - const vrp_attr *vrp_left, *vrp_right; + const vrp_attr *vrp_left; const ir_node *right = get_Shl_right(node); - vrp_left = get_vrp_attr(get_Shl_left(node)); - vrp_right = get_vrp_attr(get_Shl_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Shl_left(node)); /* We can only compute this if the right value is a constant*/ if (is_Const(right)) { @@ -201,11 +227,10 @@ static int vrp_update_node(ir_node *node) } case iro_Shr: { - const vrp_attr *vrp_left, *vrp_right; + const vrp_attr *vrp_left; const ir_node *right = get_Shr_right(node); - vrp_left = get_vrp_attr(get_Shr_left(node)); - vrp_right = get_vrp_attr(get_Shr_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Shr_left(node)); /* We can only compute this if the right value is a constant*/ if (is_Const(right)) { @@ -216,11 +241,10 @@ static int vrp_update_node(ir_node *node) } case iro_Shrs: { - const vrp_attr *vrp_left, *vrp_right; + const vrp_attr *vrp_left; const ir_node *right = get_Shrs_right(node); - vrp_left = get_vrp_attr(get_Shrs_left(node)); - vrp_right = get_vrp_attr(get_Shrs_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Shrs_left(node)); /* We can only compute this if the right value is a constant*/ if (is_Const(right)) { @@ -233,8 +257,8 @@ static int vrp_update_node(ir_node *node) case iro_Eor: { const vrp_attr *vrp_left, *vrp_right; - vrp_left = get_vrp_attr(get_Eor_left(node)); - vrp_right = get_vrp_attr(get_Eor_right(node)); + vrp_left = vrp_get_or_set_info(info, get_Eor_left(node)); + vrp_right = vrp_get_or_set_info(info, get_Eor_right(node)); new_bits_set = tarval_or( tarval_and(vrp_left->bits_set, tarval_not(vrp_right->bits_not_set)), @@ -249,7 +273,7 @@ static int vrp_update_node(ir_node *node) } case iro_Id: { - const vrp_attr *vrp_pred = get_vrp_attr(get_Id_pred(node)); + const vrp_attr *vrp_pred = vrp_get_or_set_info(info, get_Id_pred(node)); new_bits_set = vrp_pred->bits_set; new_bits_not_set = vrp_pred->bits_not_set; new_range_top = vrp_pred->range_top; @@ -259,7 +283,7 @@ static int vrp_update_node(ir_node *node) } case iro_Not: { - const vrp_attr *vrp_pred = get_vrp_attr(get_Not_op(node)); + const vrp_attr *vrp_pred = vrp_get_or_set_info(info, get_Not_op(node)); new_bits_set = tarval_not(vrp_pred->bits_not_set); new_bits_not_set = tarval_not(vrp_pred->bits_set); break; @@ -268,13 +292,14 @@ static int vrp_update_node(ir_node *node) case iro_Conv: { const ir_node *pred = get_Conv_op(node); ir_mode *old_mode = get_irn_mode(pred); - const vrp_attr *vrp_pred = get_vrp_attr(pred); + const vrp_attr *vrp_pred; ir_mode *new_mode; if (!mode_is_int(old_mode)) return 0; + vrp_pred = vrp_get_or_set_info(info, pred); new_mode = get_irn_mode(node); /* The second and is needed if target type is smaller*/ @@ -283,29 +308,31 @@ static int vrp_update_node(ir_node *node) new_bits_set = tarval_and( new_bits_not_set, tarval_convert_to(vrp_pred->bits_set, new_mode)); - if (tarval_cmp(vrp_pred->range_top, get_mode_max(new_mode)) == pn_Cmp_Le) { + /* Matze: TODO, BUGGY, tarval_cmp never returns ir_relation_less_equal */ + if (tarval_cmp(vrp_pred->range_top, get_mode_max(new_mode)) == ir_relation_less_equal) { vrp->range_top = vrp_pred->range_top; } - if (tarval_cmp(vrp_pred->range_bottom, get_mode_min(new_mode)) == pn_Cmp_Ge) { + /* Matze: TODO, BUGGY, tarval_cmp never returns ir_relation_greater_equal */ + if (tarval_cmp(vrp_pred->range_bottom, get_mode_min(new_mode)) == ir_relation_greater_equal) { vrp->range_bottom = vrp_pred->range_bottom; } break; } case iro_Confirm: { - const pn_Cmp cmp = get_Confirm_cmp(node); - const ir_node *bound = get_Confirm_bound(node); + const ir_relation relation = get_Confirm_relation(node); + const ir_node *bound = get_Confirm_bound(node); - if (cmp == pn_Cmp_Lg) { + if (relation == ir_relation_less_greater) { /** @todo: Handle non-Const bounds */ if (is_Const(bound)) { new_range_type = VRP_ANTIRANGE; new_range_top = get_Const_tarval(bound); new_range_bottom = get_Const_tarval(bound); } - } else if (cmp == pn_Cmp_Le) { + } else if (relation == ir_relation_less_equal) { if (is_Const(bound)) { new_range_type = VRP_RANGE; new_range_top = get_Const_tarval(bound); @@ -319,11 +346,11 @@ static int vrp_update_node(ir_node *node) /* combine all ranges*/ int num = get_Phi_n_preds(node); - pn_Cmp cmp; + ir_relation relation; int i; const ir_node *pred = get_Phi_pred(node,0); - const vrp_attr *vrp_pred = get_vrp_attr(pred); + const vrp_attr *vrp_pred = vrp_get_or_set_info(info, pred); new_range_top = vrp_pred->range_top; new_range_bottom = vrp_pred->range_bottom; new_range_type = vrp_pred->range_type; @@ -334,15 +361,15 @@ static int vrp_update_node(ir_node *node) for (i = 1; i < num; i++) { pred = get_Phi_pred(node, i); - vrp_pred = get_vrp_attr(pred); + vrp_pred = vrp_get_or_set_info(info, pred); if (new_range_type == VRP_RANGE && vrp_pred->range_type == VRP_RANGE) { - cmp = tarval_cmp(new_range_top, vrp_pred->range_top); - if (cmp == pn_Cmp_Lt) { + relation = tarval_cmp(new_range_top, vrp_pred->range_top); + if (relation == ir_relation_less) { new_range_top = vrp_pred->range_top; } - cmp = tarval_cmp(new_range_bottom, vrp_pred->range_bottom); - if (cmp == pn_Cmp_Gt) { + relation = tarval_cmp(new_range_bottom, vrp_pred->range_bottom); + if (relation == ir_relation_greater) { new_range_bottom = vrp_pred->range_bottom; } } else { @@ -370,7 +397,7 @@ static int vrp_update_node(ir_node *node) is_End(node) is_Free(node) is_IJmp(node) is_InstOf(node) is_Jmp(node) is_Load(node) is_Minus(node) is_Mod(node) is_Mul(node) is_Mulh(node) is_Mux(node) is_NoMem(node) - is_Pin(node) is_Proj(node) is_Quot(node) + is_Pin(node) is_Proj(node) is_Raise(node) is_Return(node) is_Sel(node) is_Start(node) is_Store(node) is_SymConst(node) is_Sync(node) is_Tuple(node) */ @@ -395,7 +422,7 @@ static int vrp_update_node(ir_node *node) /* Merge the newly calculated values with those that might already exist*/ if (new_bits_set != tarval_bad) { new_bits_set = tarval_or(new_bits_set, vrp->bits_set); - if (tarval_cmp(new_bits_set, vrp->bits_set) != pn_Cmp_Eq) { + if (new_bits_set != vrp->bits_set) { something_changed = 1; vrp->bits_set = new_bits_set; } @@ -403,7 +430,7 @@ static int vrp_update_node(ir_node *node) if (new_bits_not_set != tarval_bad) { new_bits_not_set = tarval_and(new_bits_not_set, vrp->bits_not_set); - if (tarval_cmp(new_bits_not_set, vrp->bits_not_set) != pn_Cmp_Eq) { + if (new_bits_not_set != vrp->bits_not_set) { something_changed = 1; vrp->bits_not_set = new_bits_not_set; } @@ -418,11 +445,11 @@ static int vrp_update_node(ir_node *node) } else if (vrp->range_type == VRP_RANGE) { if (new_range_type == VRP_RANGE) { - if (tarval_cmp(vrp->range_bottom, new_range_bottom) == pn_Cmp_Lt) { + if (tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_less) { something_changed = 1; vrp->range_bottom = new_range_bottom; } - if (tarval_cmp(vrp->range_top, new_range_top) == pn_Cmp_Gt) { + if (tarval_cmp(vrp->range_top, new_range_top) == ir_relation_greater) { something_changed = 1; vrp->range_top = new_range_top; } @@ -431,13 +458,13 @@ static int vrp_update_node(ir_node *node) if (new_range_type == VRP_ANTIRANGE) { /* if they are overlapping, cut the range.*/ /* TODO: Maybe we can preserve more information here*/ - if (tarval_cmp(vrp->range_bottom, new_range_top) == pn_Cmp_Gt && - tarval_cmp(vrp->range_bottom, new_range_bottom) == pn_Cmp_Gt) { + if (tarval_cmp(vrp->range_bottom, new_range_top) == ir_relation_greater && + tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_greater) { something_changed = 1; vrp->range_bottom = new_range_top; - } else if (tarval_cmp(vrp->range_top, new_range_bottom) == pn_Cmp_Gt && - tarval_cmp(vrp->range_top, new_range_top) == pn_Cmp_Lt) { + } else if (tarval_cmp(vrp->range_top, new_range_bottom) == ir_relation_greater && + tarval_cmp(vrp->range_top, new_range_top) == ir_relation_less) { something_changed = 1; vrp->range_top = new_range_bottom; } @@ -448,22 +475,22 @@ static int vrp_update_node(ir_node *node) } } else if (vrp->range_type == VRP_ANTIRANGE) { if (new_range_type == VRP_ANTIRANGE) { - if (tarval_cmp(vrp->range_bottom, new_range_bottom) == pn_Cmp_Gt) { + if (tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_greater) { something_changed = 1; vrp->range_bottom = new_range_bottom; } - if (tarval_cmp(vrp->range_top, new_range_top) == pn_Cmp_Lt) { + if (tarval_cmp(vrp->range_top, new_range_top) == ir_relation_less) { something_changed = 1; vrp->range_top = new_range_top; } } if (new_range_type == VRP_RANGE) { - if (tarval_cmp(vrp->range_bottom, new_range_top) == pn_Cmp_Gt) { + if (tarval_cmp(vrp->range_bottom, new_range_top) == ir_relation_greater) { something_changed = 1; vrp->range_bottom = new_range_top; } - if (tarval_cmp(vrp->range_top, new_range_bottom) == pn_Cmp_Lt) { + if (tarval_cmp(vrp->range_top, new_range_bottom) == ir_relation_less) { something_changed = 1; vrp->range_top = new_range_bottom; } @@ -485,9 +512,9 @@ static void vrp_first_pass(ir_node *n, void *e) bitset_set(env->visited, get_irn_idx(n)); - vrp_update_node(n); + vrp_update_node(env->info, n); - assure_irg_outs(get_current_ir_graph()); + assure_irg_outs(get_irn_irg(n)); for (i = get_irn_n_outs(n) - 1; i >=0; --i) { ir_node *succ = get_irn_out(n, i); if (bitset_is_set(env->visited, get_irn_idx(succ))) { @@ -497,70 +524,54 @@ static void vrp_first_pass(ir_node *n, void *e) } } -static void *vrp_init_node(ir_phase *phase, const ir_node *n) +static void dump_vrp_info(void *ctx, FILE *F, const ir_node *node) { - ir_mode *mode; vrp_attr *vrp; - DBG((dbg, LEVEL_2, "initialized node nr: %d\n", get_irn_node_nr(n))); - vrp = (vrp_attr*) phase_alloc(phase, sizeof(vrp_attr)); - - memset(vrp, 0, sizeof(vrp_attr)); - /* Initialize the vrp information to default */ - - mode = get_irn_mode(n); + (void) ctx; + if (!mode_is_int(get_irn_mode(node))) + return; - vrp->range_type = VRP_UNDEFINED; + vrp = vrp_get_info(node); + if (vrp == NULL) + return; - /* TODO: We might be able to optimize space usage if we do not allocate - * vrp space for non-int nodes. (currently caught by vrp_update_node) - */ - if (mode_is_int(mode)) { - /* We are assuming that 0 is always represented as this modes null */ - vrp->valid = 1; - vrp->bits_set = get_mode_null(mode); - vrp->bits_not_set = get_mode_all_one(mode); - vrp->range_bottom = get_tarval_top(); - vrp->range_top = get_tarval_top(); - } else { - vrp->valid = 0; - vrp->bits_set = get_tarval_bad(); - vrp->bits_not_set = get_tarval_bad(); - vrp->range_bottom = get_tarval_bad(); - vrp->range_top = get_tarval_bad(); + fprintf(F, "vrp range type: %d\n", (int) vrp->range_type); + if (vrp->range_type == VRP_RANGE || vrp->range_type == VRP_ANTIRANGE) { + ir_fprintf(F, "vrp range bottom: %T\n",vrp->range_bottom); + ir_fprintf(F, "vrp range top: %T\n", vrp->range_top); } - - /* TODO: We might be able to set better vrp info at this time, if this is - * a node which is newly created in an already initialized irg - * - * maybe just call vrp_update_node and if it returns one, iterate over - * successors - */ - return vrp; + ir_fprintf(F, "vrp bits set: %T\n", vrp->bits_set); + ir_fprintf(F, "vrp bits not set: %T\n", vrp->bits_not_set); } +static hook_entry_t dump_hook; + void set_vrp_data(ir_graph *irg) { ir_node *succ, *node; int i; vrp_env_t *env; - ir_phase *phase; + ir_vrp_info *info; + + if (irg->vrp.infos.data != NULL) + free_vrp_data(irg); FIRM_DBG_REGISTER(dbg, "ir.ana.vrp"); assure_irg_outs(irg); /* ensure that out edges are consistent*/ - phase = irg_get_phase(irg, PHASE_VRP); - if (phase == NULL) { - /* this is our first run */ - phase = new_phase(irg, vrp_init_node); - irg_register_phase(irg, PHASE_VRP, phase); - env = (vrp_env_t*) phase_alloc(phase, sizeof(*env)); - phase->priv = env; - } else { - env = (vrp_env_t*) phase->priv; + ir_nodemap_init(&irg->vrp.infos, irg); + obstack_init(&irg->vrp.obst); + info = &irg->vrp; + + if (dump_hook.hook._hook_node_info == NULL) { + dump_hook.hook._hook_node_info = dump_vrp_info; + register_hook(hook_node_info, &dump_hook); } + env = OALLOCZ(&irg->vrp.obst, vrp_env_t); env->workqueue = new_waitq(); + env->info = info; env->visited = bitset_malloc(get_irg_last_idx(irg)); irg_walk_graph(irg, NULL, vrp_first_pass, env); @@ -570,66 +581,57 @@ void set_vrp_data(ir_graph *irg) while (!waitq_empty(env->workqueue)) { node = (ir_node*) waitq_get(env->workqueue); - if (vrp_update_node(node)) { + if (vrp_update_node(info, node)) { /* if something changed, add successors to worklist*/ - for (i = get_irn_n_outs(node) - 1; i >=0; --i) { + for (i = get_irn_n_outs(node) - 1; i >= 0; --i) { succ = get_irn_out(node, i); - waitq_put(env->workqueue, node); + waitq_put(env->workqueue, succ); } } } del_waitq(env->workqueue); } +void free_vrp_data(ir_graph *irg) +{ + if (irg->vrp.infos.data == NULL) + return; + obstack_free(&irg->vrp.obst, NULL); + ir_nodemap_destroy(&irg->vrp.infos); +} + ir_graph_pass_t *set_vrp_pass(const char *name) { return def_graph_pass(name ? name : "set_vrp", set_vrp_data); } -pn_Cmp vrp_cmp(const ir_node *left, const ir_node *right) +ir_relation vrp_cmp(const ir_node *left, const ir_node *right) { vrp_attr *vrp_left, *vrp_right; + if (!mode_is_int(get_irn_mode(left))) + return ir_relation_true; + vrp_left = vrp_get_info(left); vrp_right = vrp_get_info(right); - if (!vrp_left || !vrp_right) { - return pn_Cmp_False; - } + if (!vrp_left || !vrp_right) + return ir_relation_true; if (vrp_left->range_type == VRP_RANGE && vrp_right->range_type == VRP_RANGE) { - if (tarval_cmp(vrp_left->range_top, vrp_right->range_bottom) == pn_Cmp_Lt) { - return pn_Cmp_Lt; + if (tarval_cmp(vrp_left->range_top, vrp_right->range_bottom) == ir_relation_less) { + return ir_relation_less; } - if (tarval_cmp(vrp_left->range_bottom, vrp_right->range_top) == pn_Cmp_Gt) { - return pn_Cmp_Gt; + if (tarval_cmp(vrp_left->range_bottom, vrp_right->range_top) == ir_relation_greater) { + return ir_relation_greater; } } if (!tarval_is_null(tarval_and(vrp_left->bits_set, tarval_not(vrp_right->bits_not_set))) || !tarval_is_null(tarval_and(tarval_not(vrp_left->bits_not_set), vrp_right->bits_set))) { - return pn_Cmp_Lg; + return ir_relation_less_greater; } - /* TODO: We can get way more information here*/ - return pn_Cmp_False; -} - -vrp_attr *vrp_get_info(const ir_node *node) -{ - const ir_graph *irg = get_irn_irg(node); - const ir_phase *phase = irg_get_phase(irg, PHASE_VRP); - vrp_attr *vrp; - - if (phase == NULL) { - /* phase has not yet been initialized */ - return NULL; - } - - vrp = (vrp_attr*) phase_get_irn_data(phase, node); - if (vrp && vrp->valid) { - return vrp; - } - - return NULL; + /* TODO: We can get way more information here*/ + return ir_relation_true; }