X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fvrp.c;h=fdc3b70f9c1e89bed46be2eb43b91353c2f2c66a;hb=998a7d33f7fe446db8e265d54138841fcfe018bf;hp=8847933e1e1efd27f1bafe89e99ea2f4960e041c;hpb=eff0989aadc8f6f450f8a04eacc427cec92430ca;p=libfirm diff --git a/ir/ana/vrp.c b/ir/ana/vrp.c index 8847933e1..fdc3b70f9 100644 --- a/ir/ana/vrp.c +++ b/ir/ana/vrp.c @@ -1,405 +1,374 @@ /* - * Copyright (C) 1995-2009 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 analyze graph to provide value range information - * @author Jonas Fietz - * @version $Id$ + * @brief analyze graph to provide value range information + * @author Jonas Fietz */ #include "config.h" -#include "config.h" #include "irtypes.h" #include "vrp.h" +#include "iroptimize.h" #include "irouts.h" #include "irgraph_t.h" +#include "irgopt.h" #include "irpass.h" -#include "list.h" #include "irgwalk.h" #include "iredges.h" #include "tv.h" #include "irop.h" +#include "pdeq.h" +#include "irnodemap.h" +#include "irhooks.h" +#include "bitset.h" +#include "debug.h" +DEBUG_ONLY(static firm_dbg_module_t *dbg;) -static char v; -static void *VISITED = &v; - -typedef struct worklist_t worklist_t; -struct worklist_t { - struct list_head nodes; - ir_node *node; -}; +typedef struct vrp_env_t { + waitq *workqueue; + bitset_t *visited; + ir_vrp_info *info; +} vrp_env_t; -struct vrp_env_t { - worklist_t *worklist; -}; +static vrp_attr *vrp_get_or_set_info(ir_vrp_info *info, const ir_node *node) +{ + 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 update_vrp_data(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); +} - tarval *new_bits_set = get_tarval_bad(); - tarval *new_bits_not_set = get_tarval_bad(); - tarval *new_range_bottom = get_tarval_bad(); - tarval *new_range_top = get_tarval_bad(); - ir_node *new_bits_node = NULL; - ir_node *new_range_node = NULL; +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(); + ir_tarval *new_range_bottom = get_tarval_bad(); + ir_tarval *new_range_top = get_tarval_bad(); enum range_types new_range_type = VRP_UNDEFINED; - enum range_ops new_range_op = VRP_NONE; int something_changed = 0; - tarval *tmp_tv, *tv; - ir_node *left, *right, *pred, *bound; - int overflow_top, overflow_bottom; - tarval *new_top, *new_bottom; - - pn_Cmp cmp; - - node->vrp.valid = 1; - /* TODO: Check if all predecessors have valid VRP information*/ - + vrp_attr *vrp; if (!mode_is_int(get_irn_mode(node))) { return 0; /* we don't optimize for non-int-nodes*/ } - switch (get_irn_opcode(node)) { - case iro_Const: - tv = get_Const_tarval(node); + vrp = vrp_get_or_set_info(info, node); + /* TODO: Check if all predecessors have valid VRP information*/ + + switch (get_irn_opcode(node)) { + case iro_Const: { + ir_tarval *tv = get_Const_tarval(node); new_bits_set = tv; - new_bits_not_set = tarval_not(tv); + new_bits_not_set = tv; new_range_bottom = tv; new_range_top = tv; new_range_type = VRP_RANGE; break; + } + case iro_And: { + const vrp_attr *vrp_left, *vrp_right; + const ir_node *left, *right; - case iro_And: left = get_And_left(node); right = get_And_right(node); + 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); - new_bits_set = tarval_and(left->vrp.bits_set, right->vrp.bits_set); - new_bits_not_set = tarval_or(left->vrp.bits_not_set, right->vrp.bits_not_set); - - tmp_tv = tarval_not(left->vrp.bits_set); - tmp_tv = tarval_eor(left->vrp.bits_not_set, tmp_tv); - /*check if one of the predecessors is completely determined*/ - if (tarval_is_null(tmp_tv)) { - new_bits_node = right; - } - - tmp_tv = tarval_not(right->vrp.bits_set); - tmp_tv = tarval_eor(right->vrp.bits_not_set, tmp_tv); - if (tarval_is_null(tmp_tv)) { - new_bits_node = left; - } break; + } - case iro_Add: - left = get_Add_left(node); - right = get_Add_right(node); - + case iro_Add: { + const vrp_attr *vrp_left = vrp_get_or_set_info(info, get_Add_left(node)); + const vrp_attr *vrp_right = vrp_get_or_set_info(info, get_Add_right(node)); - if (left->vrp.range_type == VRP_UNDEFINED || right->vrp.range_type == - VRP_UNDEFINED || left->vrp.range_type == VRP_VARYING || - right->vrp.range_type == VRP_VARYING) { + if (vrp_left->range_type == VRP_UNDEFINED + || vrp_right->range_type == VRP_UNDEFINED + || vrp_left->range_type == VRP_VARYING + || vrp_right->range_type == VRP_VARYING) { return 0; } - new_top = tarval_add(left->vrp.range_top, right->vrp.range_top); - overflow_top = tarval_carry(); - new_bottom = tarval_add(left->vrp.range_bottom, right->vrp.range_bottom); - overflow_bottom = tarval_carry(); - - if (!overflow_top && !overflow_bottom && left->vrp.range_type == VRP_RANGE - &&right->vrp.range_type == VRP_RANGE) { - new_range_bottom = new_bottom; - new_range_top = new_top; - new_range_type = VRP_RANGE; - } - - if (overflow_top || overflow_bottom) { - /* TODO Implement overflow handling*/ - new_range_type = VRP_UNDEFINED; + if (vrp_left->range_type == VRP_RANGE + && vrp_right->range_type == VRP_RANGE) { + tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode(); + tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD); + ir_tarval *new_top + = tarval_add(vrp_left->range_top, vrp_right->range_top); + ir_tarval *new_bottom + = tarval_add(vrp_left->range_bottom, vrp_right->range_bottom); + tarval_set_integer_overflow_mode(rem); + + if (new_top != tarval_bad && new_bottom != tarval_bad) { + new_range_bottom = new_bottom; + new_range_top = new_top; + new_range_type = VRP_RANGE; + } else { + /* TODO Implement overflow handling*/ + new_range_type = VRP_UNDEFINED; + } } break; + } - case iro_Sub: - left = get_Sub_left(node); - right = get_Sub_right(node); + case iro_Sub: { + ir_node *left = get_Sub_left(node); + ir_node *right = get_Sub_right(node); - if (left->vrp.range_type == VRP_UNDEFINED || right->vrp.range_type == - VRP_UNDEFINED) { + if (!mode_is_int(get_irn_mode(left))) return 0; - } - new_top = tarval_sub(left->vrp.range_top, right->vrp.range_top, NULL); - overflow_top = tarval_carry(); - new_bottom = tarval_sub(left->vrp.range_bottom, right->vrp.range_bottom, NULL); - overflow_bottom = tarval_carry(); + const vrp_attr *vrp_left = vrp_get_or_set_info(info, left); + const vrp_attr *vrp_right = vrp_get_or_set_info(info, right); - if (!overflow_top && !overflow_bottom && left->vrp.range_type == VRP_RANGE - &&right->vrp.range_type == VRP_RANGE) { - new_range_bottom = new_bottom; - new_range_top = new_top; - new_range_type = VRP_RANGE; + if (vrp_left->range_type == VRP_UNDEFINED + || vrp_right->range_type == VRP_UNDEFINED + || vrp_left->range_type == VRP_VARYING + || vrp_right->range_type == VRP_VARYING) { + return 0; } - if (overflow_top || overflow_bottom) { - /* TODO Implement overflow handling*/ + if (vrp_left->range_type == VRP_RANGE + && vrp_right->range_type == VRP_RANGE) { + tarval_int_overflow_mode_t rem = tarval_get_integer_overflow_mode(); + tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD); + ir_tarval *new_top = tarval_sub(vrp_left->range_top, vrp_right->range_top, NULL); + ir_tarval *new_bottom = tarval_sub(vrp_left->range_bottom, vrp_right->range_bottom, NULL); + tarval_set_integer_overflow_mode(rem); + + if (new_top != tarval_bad && new_bottom != tarval_bad) { + new_range_bottom = new_bottom; + new_range_top = new_top; + new_range_type = VRP_RANGE; + } else { + /* TODO Implement overflow handling*/ + new_range_type = VRP_UNDEFINED; + } } break; + } - case iro_Or: - left = get_Or_left(node); - right = get_Or_right(node); + case iro_Or: { + const vrp_attr *vrp_left, *vrp_right; - new_bits_set = tarval_or(left->vrp.bits_set, right->vrp.bits_set); - new_bits_not_set = tarval_and(left->vrp.bits_not_set, right->vrp.bits_not_set); + vrp_left = vrp_get_or_set_info(info, get_Or_left(node)); + vrp_right = vrp_get_or_set_info(info, get_Or_right(node)); - tmp_tv = tarval_not(left->vrp.bits_set); - tmp_tv = tarval_eor(left->vrp.bits_not_set, tmp_tv); - /*check if one of the predecessors is completely determined*/ - if (tarval_is_null(tmp_tv)) { - new_bits_node = right; - } + 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); - tmp_tv = tarval_not(right->vrp.bits_set); - tmp_tv = tarval_eor(right->vrp.bits_not_set, tmp_tv); - if (tarval_is_null(tmp_tv)) { - new_bits_node = left; - } break; + } + + case iro_Rotl: { + const vrp_attr *vrp_left; + const ir_node *right = get_Rotl_right(node); - case iro_Rotl: - left = get_Rotl_left(node); - right = 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)) { - tarval *bits_set, *bits_not_set; - bits_set = tarval_rotl(left->vrp.bits_set, get_Const_tarval(right)); - bits_not_set = tarval_rotl(left->vrp.bits_not_set, get_Const_tarval(right)); - - new_bits_set = tarval_or(bits_set, node->vrp.bits_set); - new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set); + 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: - left = get_Shl_left(node); - right = get_Shl_right(node); + case iro_Shl: { + const vrp_attr *vrp_left; + const ir_node *right = 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)) { - tarval *bits_set, *bits_not_set; - ir_mode *m = get_tarval_mode(node->vrp.bits_not_set); - bits_set = tarval_shl(left->vrp.bits_set, get_Const_tarval(right)); - bits_not_set = tarval_shl(left->vrp.bits_not_set, get_Const_tarval(right)); - - new_bits_set = tarval_or(bits_set, node->vrp.bits_set); - new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set); - - bits_not_set = tarval_not( tarval_shl( - get_mode_all_one(m), - get_Const_tarval(right))); - new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set); - + new_bits_set = tarval_shl(vrp_left->bits_set, get_Const_tarval(right)); + new_bits_not_set = tarval_shl(vrp_left->bits_not_set, get_Const_tarval(right)); } break; + } - case iro_Shr: - left = get_Shr_left(node); - right = get_Shr_right(node); + case iro_Shr: { + const vrp_attr *vrp_left; + const ir_node *right = 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)) { - tarval *bits_set, *bits_not_set; - ir_mode *m = get_tarval_mode(node->vrp.bits_not_set); - bits_set = tarval_shr(left->vrp.bits_set, get_Const_tarval(right)); - bits_not_set = tarval_shr(left->vrp.bits_not_set, get_Const_tarval(right)); - - new_bits_set = tarval_or(bits_set, node->vrp.bits_set); - new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set); - - bits_not_set = tarval_not( tarval_shr( - get_mode_all_one(m), - get_Const_tarval(right))); - new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set); + new_bits_set = tarval_shr(vrp_left->bits_set, get_Const_tarval(right)); + new_bits_not_set = tarval_shr(vrp_left->bits_not_set, get_Const_tarval(right)); } break; + } - case iro_Shrs: - left = get_Shrs_left(node); - right = get_Shrs_right(node); + case iro_Shrs: { + const vrp_attr *vrp_left; + const ir_node *right = 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)) { - tarval *bits_set, *bits_not_set; - ir_mode *m = get_tarval_mode(node->vrp.bits_not_set); - bits_set = tarval_shrs(left->vrp.bits_set, get_Const_tarval(right)); - bits_not_set = tarval_shrs(left->vrp.bits_not_set, get_Const_tarval(right)); - - new_bits_set = tarval_or(bits_set, node->vrp.bits_set); - new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set); - - bits_not_set = tarval_not( tarval_shrs( - get_mode_all_one(m), - get_Const_tarval(right))); - new_bits_not_set = tarval_or(bits_not_set, new_bits_not_set); + new_bits_set = tarval_shrs(vrp_left->bits_set, get_Const_tarval(right)); + new_bits_not_set = tarval_shrs(vrp_left->bits_not_set, get_Const_tarval(right)); } break; + } - case iro_Eor: - left = get_Eor_left(node); - right = get_Eor_right(node); + case iro_Eor: { + const vrp_attr *vrp_left, *vrp_right; - tarval *bits_set, *bits_not_set; - bits_not_set = tarval_or( - tarval_and(left->vrp.bits_set, right->vrp.bits_set), - tarval_and(left->vrp.bits_not_set, - right->vrp.bits_not_set)); + vrp_left = vrp_get_or_set_info(info, get_Eor_left(node)); + vrp_right = vrp_get_or_set_info(info, get_Eor_right(node)); - bits_set = tarval_or( - tarval_and(left->vrp.bits_set, right->vrp.bits_not_set), - tarval_and(left->vrp.bits_not_set, right->vrp.bits_set)); + new_bits_set = tarval_or( + tarval_and(vrp_left->bits_set, tarval_not(vrp_right->bits_not_set)), + tarval_and(tarval_not(vrp_left->bits_not_set), vrp_right->bits_set)); + + new_bits_not_set = tarval_not(tarval_or( + tarval_and(vrp_left->bits_set,vrp_right->bits_set), + tarval_and(tarval_not(vrp_left->bits_not_set), + tarval_not(vrp_right->bits_not_set)))); - new_bits_set = tarval_or(bits_set, node->vrp.bits_set); - new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set); break; + } - case iro_Id: - pred = get_Id_pred(node); - new_bits_set = pred->vrp.bits_set; - new_bits_not_set = pred->vrp.bits_not_set; - new_range_top = pred->vrp.range_top; - new_range_bottom = pred->vrp.range_bottom; - new_range_type = pred->vrp.range_type; + case iro_Id: { + 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; + new_range_bottom = vrp_pred->range_bottom; + new_range_type = vrp_pred->range_type; break; + } - case iro_Not: - pred = get_Not_op(node); - new_bits_set = tarval_or(pred->vrp.bits_not_set, node->vrp.bits_set); - new_bits_not_set = tarval_or(pred->vrp.bits_set, node->vrp.bits_not_set); + case iro_Not: { + 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; + } - case iro_Conv: - pred = get_Conv_op(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; + 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*/ - bits_not_set = tarval_not( - tarval_convert_to(get_mode_all_one(old_mode), - new_mode - )); - bits_not_set = tarval_or(bits_not_set, tarval_convert_to(pred->vrp.bits_not_set, new_mode)); - new_bits_not_set = tarval_or(bits_not_set, node->vrp.bits_not_set); + new_bits_not_set = tarval_convert_to(get_mode_all_one(old_mode), new_mode); + new_bits_not_set = tarval_and(new_bits_not_set, tarval_convert_to(vrp_pred->bits_not_set, new_mode)); new_bits_set = tarval_and( - tarval_not(bits_not_set), tarval_convert_to(pred->vrp.bits_set, new_mode)); + new_bits_not_set, tarval_convert_to(vrp_pred->bits_set, new_mode)); - if (tarval_cmp(pred->vrp.range_top, get_mode_max(new_mode)) == pn_Cmp_Le) { - node->vrp.range_top = pred->vrp.range_top; + /* 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(pred->vrp.range_bottom, get_mode_min(new_mode)) == pn_Cmp_Ge) { - node->vrp.range_bottom = pred->vrp.range_bottom; + /* 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: - cmp = get_Confirm_cmp(node); - bound = get_Confirm_bound(node); + case iro_Confirm: { + const ir_relation relation = get_Confirm_relation(node); + const ir_node *bound = get_Confirm_bound(node); - /** @todo: Handle non-Const bounds */ - if (cmp == pn_Cmp_Lg) { - /** @todo: Is there some way to preserve the information? */ - new_range_type = VRP_ANTIRANGE; + 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) { - if (node->vrp.range_type == VRP_UNDEFINED) { + } else if (relation == ir_relation_less_equal) { + if (is_Const(bound)) { new_range_type = VRP_RANGE; - if (is_Const(bound)) { - new_range_top = get_Const_tarval(bound); - } + new_range_top = get_Const_tarval(bound); new_range_bottom = get_tarval_min(get_irn_mode(node)); - } else if (node->vrp.range_type == VRP_RANGE) { - if (is_Const(bound)) { - if (tarval_cmp(node->vrp.range_top, - get_Const_tarval(bound)) == pn_Cmp_Le) { - new_range_top = get_Const_tarval(bound); - } - new_range_bottom = get_tarval_min(get_irn_mode(node)); - - } else if (node->vrp.range_type == VRP_ANTIRANGE) { - /** @todo: How do we manage not to get a never ending loop? */ - } } } break; + } - case iro_Phi: + case iro_Phi: { /* combine all ranges*/ - pred = get_Phi_pred(node,0); - new_range_top = pred->vrp.range_top; - new_range_bottom = pred->vrp.range_bottom; - new_range_type = pred->vrp.range_type; - new_bits_set = pred->vrp.bits_set; - new_bits_not_set = pred->vrp.bits_not_set; - int num = get_Phi_n_preds(node); - pn_Cmp cmp; + ir_relation relation; int i; - assert(num > 0); + const ir_node *pred = get_Phi_pred(node,0); + 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; + new_bits_set = vrp_pred->bits_set; + new_bits_not_set = vrp_pred->bits_not_set; + assert(num > 0); for (i = 1; i < num; i++) { pred = get_Phi_pred(node, i); - if (new_range_type == VRP_RANGE && pred->vrp.range_type == + 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, pred->vrp.range_top); - if (cmp == pn_Cmp_Lt) { - new_range_top = pred->vrp.range_top; + 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, pred->vrp.range_bottom); - if (cmp == pn_Cmp_Gt) { - new_range_bottom = pred->vrp.range_bottom; + relation = tarval_cmp(new_range_bottom, vrp_pred->range_bottom); + if (relation == ir_relation_greater) { + new_range_bottom = vrp_pred->range_bottom; } } else { new_range_type = VRP_VARYING; - break; } + new_bits_set = tarval_and(new_bits_set, vrp_pred->bits_set); + new_bits_not_set = tarval_or(new_bits_not_set, + vrp_pred->bits_not_set); } break; - - + } default: /* unhandled, therefore never updated */ break; @@ -409,260 +378,246 @@ static int update_vrp_data(ir_node *node) /* TODO: Check, if there can be information derived from any of these: is_Abs(node) is_Alloc(node) is_Anchor(node) is_Borrow(node) is_Bound(node) - is_Break(node) is_Builtin(node) is_Call(node) is_CallBegin(node) - is_Carry(node) is_Cast(node) is_Cmp(node) is_Cond(node) - is_CopyB(node) is_Div(node) is_DivMod(node) is_Dummy(node) - is_End(node) is_EndExcept(node) is_EndReg(node) is_Filter(node) is_Free(node) + is_Break(node) is_Builtin(node) is_Call(node) + is_Carry(node) is_Cmp(node) is_Cond(node) + is_CopyB(node) is_Div(node) is_Dummy(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) */ - /* Merge the newly calculated values with those that might already exist*/ + /* @todo: At this place, we check if the mode of the variable changed. A + * better place for this might be in the convopt.c file + */ + + if (new_bits_set != tarval_bad && get_tarval_mode(new_bits_set) != get_tarval_mode(vrp->bits_set)) { + vrp->bits_set = tarval_convert_to(vrp->bits_set, get_irn_mode(node)); + } + if (new_bits_not_set != tarval_bad && get_tarval_mode(new_bits_not_set) != get_tarval_mode(vrp->bits_not_set)) { + vrp->bits_not_set = tarval_convert_to(vrp->bits_not_set, get_irn_mode(node)); + } + + if (vrp->range_type != VRP_UNDEFINED && new_range_type != VRP_UNDEFINED && get_tarval_mode(new_range_top) != get_tarval_mode(vrp->range_top)) { + /* @todo: We might be able to preserve this range information if it + * fits in */ + vrp->range_type = VRP_VARYING; + } + /* 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, node->vrp.bits_set); - if (tarval_cmp(new_bits_set, node->vrp.bits_set) != pn_Cmp_Eq) { + new_bits_set = tarval_or(new_bits_set, vrp->bits_set); + if (new_bits_set != vrp->bits_set) { something_changed = 1; - node->vrp.bits_set = new_bits_set; + vrp->bits_set = new_bits_set; } } - if (new_bits_not_set != tarval_bad) { - new_bits_not_set = tarval_or(new_bits_not_set, node->vrp.bits_not_set); + new_bits_not_set = tarval_and(new_bits_not_set, vrp->bits_not_set); - if (tarval_cmp(new_bits_not_set, node->vrp.bits_not_set) != pn_Cmp_Eq) { + if (new_bits_not_set != vrp->bits_not_set) { something_changed = 1; - node->vrp.bits_not_set = new_bits_not_set; + vrp->bits_not_set = new_bits_not_set; } } - if (node->vrp.bits_node == NULL && new_bits_node != NULL) { - something_changed = 1; - node->vrp.bits_node = new_bits_node; - } - - if (node->vrp.range_type == VRP_UNDEFINED && + if (vrp->range_type == VRP_UNDEFINED && new_range_type != VRP_UNDEFINED) { something_changed = 1; - node->vrp.range_type = new_range_type; - node->vrp.range_bottom = new_range_bottom; - node->vrp.range_top = new_range_top; - node->vrp.range_op = new_range_op; - node->vrp.range_node = new_range_node; + vrp->range_type = new_range_type; + vrp->range_bottom = new_range_bottom; + vrp->range_top = new_range_top; - } else if (node->vrp.range_type == VRP_RANGE) { + } else if (vrp->range_type == VRP_RANGE) { if (new_range_type == VRP_RANGE) { - if ((new_range_node == NULL && node->vrp.range_node == NULL) || - (new_range_node == node->vrp.range_node && - new_range_op == node->vrp.range_op)) { - if (tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Lt) { - something_changed = 1; - node->vrp.range_bottom = new_range_bottom; - } - if (tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Gt) { - something_changed = 1; - node->vrp.range_top = new_range_top; - } + if (tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_less) { + something_changed = 1; + vrp->range_bottom = new_range_bottom; } - - /* prefer the absolute value*/ - if (new_range_node == NULL && node->vrp.range_node != NULL) { + if (tarval_cmp(vrp->range_top, new_range_top) == ir_relation_greater) { something_changed = 1; - node->vrp.range_node = NULL; - node->vrp.range_top = new_range_top; - node->vrp.range_bottom = new_range_bottom; + vrp->range_top = new_range_top; } } if (new_range_type == VRP_ANTIRANGE) { /* if they are overlapping, cut the range.*/ /* TODO: Maybe we can preserve more information here*/ - if (new_range_node == NULL && node->vrp.range_node == NULL) { - if (tarval_cmp(node->vrp.range_bottom, new_range_top) == pn_Cmp_Gt && - tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Gt) { - something_changed = 1; - node->vrp.range_bottom = new_range_top; - - } else if (tarval_cmp(node->vrp.range_top, new_range_bottom) == pn_Cmp_Gt && - tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Lt) { - something_changed = 1; - node->vrp.range_top = new_range_bottom; - } - - /* We can not handle the case where the anti range is in the*/ - /* range*/ - } + 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; - /* prefer the absolute value*/ - if (new_range_node == NULL && node->vrp.range_node != NULL) { + } 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; - node->vrp.range_node = NULL; - node->vrp.range_top = new_range_top; - node->vrp.range_bottom = new_range_bottom; + vrp->range_top = new_range_bottom; } + + /* We can not handle the case where the anti range is in the*/ + /* range*/ + } - } else if (node->vrp.range_type == VRP_ANTIRANGE) { + } else if (vrp->range_type == VRP_ANTIRANGE) { if (new_range_type == VRP_ANTIRANGE) { - if ((new_range_node == NULL && node->vrp.range_node == NULL) || - (new_range_node == node->vrp.range_node && - new_range_op == node->vrp.range_op)) { - if (tarval_cmp(node->vrp.range_bottom, new_range_bottom) == pn_Cmp_Gt) { - something_changed = 1; - node->vrp.range_bottom = new_range_bottom; - } - if (tarval_cmp(node->vrp.range_top, new_range_top) == pn_Cmp_Lt) { - something_changed = 1; - node->vrp.range_top = new_range_top; - } + if (tarval_cmp(vrp->range_bottom, new_range_bottom) == ir_relation_greater) { + something_changed = 1; + vrp->range_bottom = new_range_bottom; } - - /* prefer the absolute value*/ - if (new_range_node == NULL && node->vrp.range_node != NULL) { + if (tarval_cmp(vrp->range_top, new_range_top) == ir_relation_less) { something_changed = 1; - node->vrp.range_node = NULL; - node->vrp.range_top = new_range_top; - node->vrp.range_bottom = new_range_bottom; + vrp->range_top = new_range_top; } } if (new_range_type == VRP_RANGE) { - if ((new_range_node == NULL && node->vrp.range_node == NULL) || - (new_range_node == node->vrp.range_node && - new_range_op == node->vrp.range_op)) { - if (tarval_cmp(node->vrp.range_bottom, new_range_top) == pn_Cmp_Gt) { - something_changed = 1; - node->vrp.range_bottom = new_range_top; - } - if (tarval_cmp(node->vrp.range_top, new_range_bottom) == pn_Cmp_Lt) { - something_changed = 1; - node->vrp.range_top = new_range_bottom; - } + if (tarval_cmp(vrp->range_bottom, new_range_top) == ir_relation_greater) { + something_changed = 1; + vrp->range_bottom = new_range_top; } - - /* prefer the absolute value*/ - if (new_range_node == NULL && node->vrp.range_node != NULL) { + if (tarval_cmp(vrp->range_top, new_range_bottom) == ir_relation_less) { something_changed = 1; - node->vrp.range_node = NULL; - node->vrp.range_top = new_range_top; - node->vrp.range_bottom = new_range_bottom; + vrp->range_top = new_range_bottom; } } } assert(tarval_is_null( - tarval_and(node->vrp.bits_set, node->vrp.bits_not_set))); - + tarval_and(vrp->bits_set, tarval_not(vrp->bits_not_set)))); return something_changed; } static void vrp_first_pass(ir_node *n, void *e) { - ir_node *succ; - worklist_t *tmp_entry; int i; - struct vrp_env_t *env = e; + vrp_env_t *env = (vrp_env_t*) e; if (is_Block(n)) return; - set_irn_link(n, VISITED); + bitset_set(env->visited, get_irn_idx(n)); - update_vrp_data(n); + vrp_update_node(env->info, n); for (i = get_irn_n_outs(n) - 1; i >=0; --i) { - succ = get_irn_out(n, i); - if (get_irn_link(succ) == VISITED) { + ir_node *succ = get_irn_out(n, i); + if (bitset_is_set(env->visited, get_irn_idx(succ))) { /* we found a loop*/ - - tmp_entry = XMALLOC(worklist_t); - tmp_entry->node = n; - list_add(&(tmp_entry->nodes), &(env->worklist->nodes)); - - + waitq_put(env->workqueue, succ); } } } - -void set_vrp_data(ir_graph *irg) +static void dump_vrp_info(void *ctx, FILE *F, const ir_node *node) { + vrp_attr *vrp; - ir_node *succ; - int i; - worklist_t worklist; - worklist_t *tmp_entry, *tmp_entry2; - struct vrp_env_t env; - - if (!irg) { - /* no graph, skip */ + (void) ctx; + if (!mode_is_int(get_irn_mode(node))) return; - } - assure_irg_outs(irg); /* ensure that out edges are consistent*/ + vrp = vrp_get_info(node); + if (vrp == NULL) + return; -/* edges_activate(irg);*/ + 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); + } + ir_fprintf(F, "vrp bits set: %T\n", vrp->bits_set); + ir_fprintf(F, "vrp bits not set: %T\n", vrp->bits_not_set); +} - INIT_LIST_HEAD(&worklist.nodes); +static hook_entry_t dump_hook; - env.worklist = &worklist; - irg_walk_graph(irg, NULL, vrp_first_pass, &env); +void set_vrp_data(ir_graph *irg) +{ + ir_node *succ, *node; + int i; + vrp_env_t *env; + ir_vrp_info *info; + if (irg->vrp.infos.data != NULL) + free_vrp_data(irg); + FIRM_DBG_REGISTER(dbg, "ir.ana.vrp"); - /* while there are entries in the worklist, continue*/ - while ( !list_empty(&worklist.nodes) ) { + assure_irg_outs(irg); /* ensure that out edges are consistent*/ + ir_nodemap_init(&irg->vrp.infos, irg); + obstack_init(&irg->vrp.obst); + info = &irg->vrp; - list_head *pos, *next; - list_for_each_safe(pos, next, &worklist.nodes) { + if (dump_hook.hook._hook_node_info == NULL) { + dump_hook.hook._hook_node_info = dump_vrp_info; + register_hook(hook_node_info, &dump_hook); + } - tmp_entry = list_entry(pos, worklist_t, nodes); + env = OALLOCZ(&irg->vrp.obst, vrp_env_t); + env->workqueue = new_waitq(); + env->info = info; - if (update_vrp_data(tmp_entry->node)) { - /* if something changed, add successors to worklist*/ - for (i = get_irn_n_outs(tmp_entry->node) - 1; i >=0; --i) { - succ = get_irn_out(tmp_entry->node, i); + env->visited = bitset_malloc(get_irg_last_idx(irg)); + irg_walk_graph(irg, NULL, vrp_first_pass, env); + bitset_free(env->visited); - tmp_entry2 = XMALLOC(worklist_t); - tmp_entry2->node = succ; - list_add(&(tmp_entry2->nodes), &worklist.nodes); - } + /* while there are entries in the worklist, continue*/ + while (!waitq_empty(env->workqueue)) { + node = (ir_node*) waitq_get(env->workqueue); + + if (vrp_update_node(info, node)) { + /* if something changed, add successors to worklist*/ + for (i = get_irn_n_outs(node) - 1; i >= 0; --i) { + succ = get_irn_out(node, i); + waitq_put(env->workqueue, succ); } - - list_del(pos); - xfree(tmp_entry); } } + 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(ir_node *left, ir_node *right) +ir_relation vrp_cmp(const ir_node *left, const ir_node *right) { - if (!left->vrp.valid || !right->vrp.valid) { - return pn_Cmp_False; - } + 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 (left->vrp.range_type == VRP_RANGE && right->vrp.range_type == VRP_RANGE) { - if (tarval_cmp(left->vrp.range_top, right->vrp.range_bottom) == pn_Cmp_Lt) { - return pn_Cmp_Lt; + 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) == ir_relation_less) { + return ir_relation_less; } - if (tarval_cmp(left->vrp.range_bottom, right->vrp.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(left->vrp.bits_set, right->vrp.bits_not_set)) || - !tarval_is_null(tarval_and(left->vrp.bits_not_set, right->vrp.bits_set))) { - return pn_Cmp_Lg; + 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 ir_relation_less_greater; } - /* TODO: We can get way more information here*/ - return pn_Cmp_False; + /* TODO: We can get way more information here*/ + return ir_relation_true; }