/*
- * 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 "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"
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));
} 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;
}
/* 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;
}
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);
}
}
}
+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;
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;
/* 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;
}
} 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;
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;
}
}
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;
}
}
/* 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);
}
}
} 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) {
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. */
}
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)
projects / libfirm / blobdiff