* Modified by: Goetz Lindenmaier, Michael Beck
* Created:
* CVS-ID: $Id$
- * Copyright: (c) 1998-2005 Universität Karlsruhe
+ * Copyright: (c) 1998-2006 Universität Karlsruhe
* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
#include <string.h>
#endif
-# include "irnode_t.h"
-# include "irgraph_t.h"
-# include "iredges_t.h"
-# include "irmode_t.h"
-# include "iropt_t.h"
-# include "ircons_t.h"
-# include "irgmod.h"
-# include "irvrfy.h"
-# include "tv_t.h"
-# include "dbginfo_t.h"
-# include "iropt_dbg.h"
-# include "irflag_t.h"
-# include "irhooks.h"
-# include "irarch.h"
-# include "hashptr.h"
-# include "archop.h"
-# include "opt_polymorphy.h"
-# include "opt_confirms.h"
+#include "irnode_t.h"
+#include "irgraph_t.h"
+#include "iredges_t.h"
+#include "irmode_t.h"
+#include "iropt_t.h"
+#include "ircons_t.h"
+#include "irgmod.h"
+#include "irvrfy.h"
+#include "tv_t.h"
+#include "dbginfo_t.h"
+#include "iropt_dbg.h"
+#include "irflag_t.h"
+#include "irhooks.h"
+#include "irarch.h"
+#include "hashptr.h"
+#include "archop.h"
+#include "opt_polymorphy.h"
+#include "opt_confirms.h"
+#include "irtools.h"
/* Make types visible to allow most efficient access */
-# include "entity_t.h"
+#include "entity_t.h"
/**
- * return the value of a Constant
+ * Return the value of a Constant.
*/
-static tarval *computed_value_Const(ir_node *n)
-{
+static tarval *computed_value_Const(ir_node *n) {
return get_Const_tarval(n);
-}
+} /* computed_value_Const */
/**
- * return the value of a 'sizeof' SymConst
+ * Return the value of a 'sizeof' or 'alignof' SymConst.
*/
-static tarval *computed_value_SymConst(ir_node *n)
-{
- if ((get_SymConst_kind(n) == symconst_size) &&
- (get_type_state(get_SymConst_type(n))) == layout_fixed)
- return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
+static tarval *computed_value_SymConst(ir_node *n) {
+ ir_type *type;
+ entity *ent;
+
+ switch (get_SymConst_kind(n)) {
+ case symconst_type_size:
+ type = get_SymConst_type(n);
+ if (get_type_state(type) == layout_fixed)
+ return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
+ break;
+ case symconst_type_align:
+ type = get_SymConst_type(n);
+ if (get_type_state(type) == layout_fixed)
+ return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
+ break;
+ case symconst_ofs_ent:
+ ent = get_SymConst_entity(n);
+ type = get_entity_owner(ent);
+ if (get_type_state(type) == layout_fixed)
+ return new_tarval_from_long(get_entity_offset_bytes(ent), get_irn_mode(n));
+ break;
+ default:
+ break;
+ }
return tarval_bad;
-}
+} /* computed_value_SymConst */
/**
- * return the value of an Add
+ * Return the value of an Add.
*/
-static tarval *computed_value_Add(ir_node *n)
-{
+static tarval *computed_value_Add(ir_node *n) {
ir_node *a = get_Add_left(n);
ir_node *b = get_Add_right(n);
return tarval_add(ta, tb);
return tarval_bad;
-}
+} /* computed_value_Add */
/**
- * return the value of a Sub
+ * Return the value of a Sub.
* Special case: a - a
*/
-static tarval *computed_value_Sub(ir_node *n)
-{
+static tarval *computed_value_Sub(ir_node *n) {
ir_node *a = get_Sub_left(n);
ir_node *b = get_Sub_right(n);
tarval *ta;
return tarval_sub(ta, tb);
return tarval_bad;
-}
+} /* computed_value_Sub */
/**
- * return the value of an unary Minus
+ * Return the value of a Carry.
+ * Special : a op 0, 0 op b
*/
-static tarval *computed_value_Minus(ir_node *n)
-{
+static tarval *computed_value_Carry(ir_node *n) {
+ ir_node *a = get_binop_left(n);
+ ir_node *b = get_binop_right(n);
+ ir_mode *m = get_irn_mode(n);
+
+ tarval *ta = value_of(a);
+ tarval *tb = value_of(b);
+
+ if ((ta != tarval_bad) && (tb != tarval_bad)) {
+ tarval_add(ta, tb);
+ return tarval_carry() ? get_mode_one(m) : get_mode_null(m);
+ } else {
+ if ( (classify_tarval(ta) == TV_CLASSIFY_NULL)
+ || (classify_tarval(tb) == TV_CLASSIFY_NULL))
+ return get_mode_null(m);
+ }
+ return tarval_bad;
+} /* computed_value_Carry */
+
+/**
+ * Return the value of a Borrow.
+ * Special : a op 0
+ */
+static tarval *computed_value_Borrow(ir_node *n) {
+ ir_node *a = get_binop_left(n);
+ ir_node *b = get_binop_right(n);
+ ir_mode *m = get_irn_mode(n);
+
+ tarval *ta = value_of(a);
+ tarval *tb = value_of(b);
+
+ if ((ta != tarval_bad) && (tb != tarval_bad)) {
+ return tarval_cmp(ta, tb) == pn_Cmp_Lt ? get_mode_one(m) : get_mode_null(m);
+ } else if (classify_tarval(ta) == TV_CLASSIFY_NULL) {
+ return get_mode_null(m);
+ }
+ return tarval_bad;
+} /* computed_value_Borrow */
+
+/**
+ * Return the value of an unary Minus.
+ */
+static tarval *computed_value_Minus(ir_node *n) {
ir_node *a = get_Minus_op(n);
tarval *ta = value_of(a);
return tarval_neg(ta);
return tarval_bad;
-}
+} /* computed_value_Minus */
/**
- * return the value of a Mul
+ * Return the value of a Mul.
*/
-static tarval *computed_value_Mul(ir_node *n)
-{
+static tarval *computed_value_Mul(ir_node *n) {
ir_node *a = get_Mul_left(n);
ir_node *b = get_Mul_right(n);
return tb;
}
return tarval_bad;
-}
+} /* computed_value_Mul */
/**
- * return the value of a floating point Quot
+ * Return the value of a floating point Quot.
*/
-static tarval *computed_value_Quot(ir_node *n)
-{
+static tarval *computed_value_Quot(ir_node *n) {
ir_node *a = get_Quot_left(n);
ir_node *b = get_Quot_right(n);
return tarval_quo(ta, tb);
}
return tarval_bad;
-}
+} /* computed_value_Quot */
/**
- * calculate the value of an integer Div of two nodes
+ * Calculate the value of an integer Div of two nodes.
* Special case: 0 / b
*/
-static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
-{
+static tarval *do_computed_value_Div(ir_node *a, ir_node *b) {
tarval *ta = value_of(a);
tarval *tb = value_of(b);
return ta;
}
return tarval_bad;
-}
+} /* do_computed_value_Div */
/**
- * return the value of an integer Div
+ * Return the value of an integer Div.
*/
-static tarval *computed_value_Div(ir_node *n)
-{
+static tarval *computed_value_Div(ir_node *n) {
return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
-}
+} /* computed_value_Div */
/**
- * calculate the value of an integer Mod of two nodes
+ * Calculate the value of an integer Mod of two nodes.
* Special case: a % 1
*/
-static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
-{
+static tarval *do_computed_value_Mod(ir_node *a, ir_node *b) {
tarval *ta = value_of(a);
tarval *tb = value_of(b);
else if (tb == get_mode_one(get_tarval_mode(tb))) /* x mod 1 == 0 */
return get_mode_null(get_irn_mode(a));
}
-
return tarval_bad;
-}
+} /* do_computed_value_Mod */
/**
- * return the value of an integer Mod
+ * Return the value of an integer Mod.
*/
-static tarval *computed_value_Mod(ir_node *n)
-{
+static tarval *computed_value_Mod(ir_node *n) {
return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
-}
+} /* computed_value_Mod */
/**
- * return the value of an Abs
+ * Return the value of an Abs.
*/
-static tarval *computed_value_Abs(ir_node *n)
-{
+static tarval *computed_value_Abs(ir_node *n) {
ir_node *a = get_Abs_op(n);
tarval *ta = value_of(a);
return tarval_abs(ta);
return tarval_bad;
-}
+} /* computed_value_Abs */
/**
- * return the value of an And
+ * Return the value of an And.
* Special case: a & 0, 0 & b
*/
-static tarval *computed_value_And(ir_node *n)
-{
+static tarval *computed_value_And(ir_node *n) {
ir_node *a = get_And_left(n);
ir_node *b = get_And_right(n);
}
}
return tarval_bad;
-}
+} /* computed_value_And */
/**
- * return the value of an Or
+ * Return the value of an Or.
* Special case: a | 1...1, 1...1 | b
*/
-static tarval *computed_value_Or(ir_node *n)
-{
+static tarval *computed_value_Or(ir_node *n) {
ir_node *a = get_Or_left(n);
ir_node *b = get_Or_right(n);
}
}
return tarval_bad;
-}
+} /* computed_value_Or */
/**
- * return the value of an Eor
+ * Return the value of an Eor.
*/
-static tarval *computed_value_Eor(ir_node *n)
-{
+static tarval *computed_value_Eor(ir_node *n) {
ir_node *a = get_Eor_left(n);
ir_node *b = get_Eor_right(n);
return tarval_eor (ta, tb);
}
return tarval_bad;
-}
+} /* computed_value_Eor */
/**
- * return the value of a Not
+ * Return the value of a Not.
*/
-static tarval *computed_value_Not(ir_node *n)
-{
+static tarval *computed_value_Not(ir_node *n) {
ir_node *a = get_Not_op(n);
tarval *ta = value_of(a);
return tarval_not(ta);
return tarval_bad;
-}
+} /* computed_value_Not */
/**
- * return the value of a Shl
+ * Return the value of a Shl.
*/
-static tarval *computed_value_Shl(ir_node *n)
-{
+static tarval *computed_value_Shl(ir_node *n) {
ir_node *a = get_Shl_left(n);
ir_node *b = get_Shl_right(n);
return tarval_shl (ta, tb);
}
return tarval_bad;
-}
+} /* computed_value_Shl */
/**
- * return the value of a Shr
+ * Return the value of a Shr.
*/
-static tarval *computed_value_Shr(ir_node *n)
-{
+static tarval *computed_value_Shr(ir_node *n) {
ir_node *a = get_Shr_left(n);
ir_node *b = get_Shr_right(n);
return tarval_shr (ta, tb);
}
return tarval_bad;
-}
+} /* computed_value_Shr */
/**
- * return the value of a Shrs
+ * Return the value of a Shrs.
*/
-static tarval *computed_value_Shrs(ir_node *n)
-{
+static tarval *computed_value_Shrs(ir_node *n) {
ir_node *a = get_Shrs_left(n);
ir_node *b = get_Shrs_right(n);
return tarval_shrs (ta, tb);
}
return tarval_bad;
-}
+} /* computed_value_Shrs */
/**
- * return the value of a Rot
+ * Return the value of a Rot.
*/
static tarval *computed_value_Rot(ir_node *n)
{
return tarval_rot (ta, tb);
}
return tarval_bad;
-}
+} /* computed_value_Rot */
/**
- * return the value of a Conv
+ * Return the value of a Conv.
*/
static tarval *computed_value_Conv(ir_node *n)
{
return tarval_convert_to(ta, get_irn_mode(n));
return tarval_bad;
-}
+} /* computed_value_Conv */
/**
- * return the value of a Proj(Cmp)
+ * Return the value of a Proj(Cmp).
*
* This performs a first step of unreachable code elimination.
* Proj can not be computed, but folding a Cmp above the Proj here is
return new_tarval_from_long(proj_nr & pn_Cmp_Ne, mode_b);
}
}
-
return computed_value_Cmp_Confirm(a, aa, ab, proj_nr);
-}
+} /* computed_value_Proj_Cmp */
/**
- * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
+ * Return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod),
+ * Proj(DivMod) and Proj(Quot).
*/
-static tarval *computed_value_Proj(ir_node *n)
-{
+static tarval *computed_value_Proj(ir_node *n) {
ir_node *a = get_Proj_pred(n);
long proj_nr;
return computed_value(a);
break;
+ case iro_Quot:
+ if (get_Proj_proj(n) == pn_Quot_res)
+ return computed_value(a);
+ break;
+
default:
return tarval_bad;
}
return tarval_bad;
-}
+} /* computed_value_Proj */
/**
- * calculate the value of a Mux: can be evaluated, if the
- * sel and the right input are known
+ * Calculate the value of a Mux: can be evaluated, if the
+ * sel and the right input are known.
*/
-static tarval *computed_value_Mux(ir_node *n)
-{
+static tarval *computed_value_Mux(ir_node *n) {
ir_node *sel = get_Mux_sel(n);
tarval *ts = value_of(sel);
return value_of(v);
}
return tarval_bad;
-}
+} /* computed_value_Mux */
/**
- * calculate the value of a Confirm: can be evaluated,
+ * Calculate the value of a Psi: can be evaluated, if a condition is true
+ * and all previous conditions are false. If all conditions are false
+ * we evaluate to the default one.
+ */
+static tarval *computed_value_Psi(ir_node *n) {
+ if (is_Mux(n))
+ return computed_value_Mux(n);
+ return tarval_bad;
+} /* computed_value_Psi */
+
+/**
+ * Calculate the value of a Confirm: can be evaluated,
* if it has the form Confirm(x, '=', Const).
*/
-static tarval *computed_value_Confirm(ir_node *n)
-{
+static tarval *computed_value_Confirm(ir_node *n) {
return get_Confirm_cmp(n) == pn_Cmp_Eq ?
value_of(get_Confirm_bound(n)) : tarval_bad;
-}
+} /* computed_value_Confirm */
/**
* If the parameter n can be computed, return its value, else tarval_bad.
*
* @param n The node this should be evaluated
*/
-tarval *computed_value(ir_node *n)
-{
- if (n->op->computed_value)
- return n->op->computed_value(n);
+tarval *computed_value(ir_node *n) {
+ if (n->op->ops.computed_value)
+ return n->op->ops.computed_value(n);
return tarval_bad;
-}
+} /* computed_value */
/**
- * set the default computed_value evaluator
+ * Set the default computed_value evaluator in an ir_op_ops.
+ *
+ * @param code the opcode for the default operation
+ * @param ops the operations initialized
+ *
+ * @return
+ * The operations.
*/
-static ir_op *firm_set_default_computed_value(ir_op *op)
+static ir_op_ops *firm_set_default_computed_value(opcode code, ir_op_ops *ops)
{
#define CASE(a) \
case iro_##a: \
- op->computed_value = computed_value_##a; \
+ ops->computed_value = computed_value_##a; \
break
- switch (op->code) {
+ switch (code) {
CASE(Const);
CASE(SymConst);
CASE(Add);
CASE(Shr);
CASE(Shrs);
CASE(Rot);
+ CASE(Carry);
+ CASE(Borrow);
CASE(Conv);
CASE(Proj);
CASE(Mux);
+ CASE(Psi);
CASE(Confirm);
default:
- op->computed_value = NULL;
+ /* leave NULL */;
}
- return op;
+ return ops;
#undef CASE
-}
-
-#if 0
-/* returns 1 if the a and b are pointers to different locations. */
-static bool
-different_identity (ir_node *a, ir_node *b)
-{
- assert (mode_is_reference(get_irn_mode (a))
- && mode_is_reference(get_irn_mode (b)));
-
- if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
- ir_node *a1 = get_Proj_pred (a);
- ir_node *b1 = get_Proj_pred (b);
- if (a1 != b1 && get_irn_op (a1) == op_Alloc
- && get_irn_op (b1) == op_Alloc)
- return 1;
- }
- return 0;
-}
-#endif
+} /* firm_set_default_computed_value */
/**
* Returns a equivalent block for another block.
(get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
/* Also a single entry Block following a single exit Block. Phis have
twice the same operand and will be optimized away. */
- n = get_nodes_block(a);
+ n = get_nodes_block(get_Proj_pred(a));
DBG_OPT_IFSIM1(oldn, a, b, n);
}
}
else if (get_opt_unreachable_code() &&
- (n != current_ir_graph->start_block) &&
- (n != current_ir_graph->end_block) ) {
- int i, n_cfg = get_Block_n_cfgpreds(n);
+ (n != get_irg_start_block(current_ir_graph)) &&
+ (n != get_irg_end_block(current_ir_graph)) ) {
+ int i;
/* If all inputs are dead, this block is dead too, except if it is
- the start or end block. This is a step of unreachable code
+ the start or end block. This is one step of unreachable code
elimination */
- for (i = 0; i < n_cfg; i++) {
+ for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
ir_node *pred = get_Block_cfgpred(n, i);
ir_node *pred_blk;
break;
}
}
- if (i == n_cfg)
+ if (i < 0) {
n = set_Block_dead(n);
+ DBG_OPT_DEAD_BLOCK(oldn, n);
+ }
}
return n;
-}
+} /* equivalent_node_Block */
/**
* Returns a equivalent node for a Jmp, a Bad :-)
- * Of course this only happens if the Block of the Jmp is Bad.
+ * Of course this only happens if the Block of the Jmp is dead.
*/
-static ir_node *equivalent_node_Jmp(ir_node *n)
-{
- /* GL: Why not same for op_Raise?? */
+static ir_node *equivalent_node_Jmp(ir_node *n) {
/* unreachable code elimination */
if (is_Block_dead(get_nodes_block(n)))
n = new_Bad();
return n;
-}
+} /* equivalent_node_Jmp */
+
+/** Raise is handled in the same way as Jmp. */
+#define equivalent_node_Raise equivalent_node_Jmp
+
/* We do not evaluate Cond here as we replace it by a new node, a Jmp.
See transform_node_Proj_Cond(). */
/**
- * optimize operations that are commutative and have neutral 0,
+ * Optimize operations that are commutative and have neutral 0,
* so a op 0 = 0 op a = a.
*/
static ir_node *equivalent_node_neutral_zero(ir_node *n)
}
return n;
-}
+} /* equivalent_node_neutral_zero */
+/**
+ * Eor is commutative and has neutral 0.
+ */
#define equivalent_node_Eor equivalent_node_neutral_zero
/*
{
ir_node *oldn = n;
ir_node *left, *right;
+ ir_mode *mode = get_irn_mode(n);
+
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return n;
n = equivalent_node_neutral_zero(n);
if (n != oldn)
/* (a - x) + x */
n = get_Sub_left(left);
- if (get_irn_mode(oldn) == get_irn_mode(n)) {
+ if (mode == get_irn_mode(n)) {
DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
return n;
}
/* x + (a - x) */
n = get_Sub_left(right);
- if (get_irn_mode(oldn) == get_irn_mode(n)) {
+ if (mode == get_irn_mode(n)) {
DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
return n;
}
}
}
return n;
-}
+} /* equivalent_node_Add */
/**
* optimize operations that are not commutative but have neutral 0 on left,
* so a op 0 = a.
*/
-static ir_node *equivalent_node_left_zero(ir_node *n)
-{
+static ir_node *equivalent_node_left_zero(ir_node *n) {
ir_node *oldn = n;
ir_node *a = get_binop_left(n);
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
}
-
return n;
-}
+} /* equivalent_node_left_zero */
#define equivalent_node_Shl equivalent_node_left_zero
#define equivalent_node_Shr equivalent_node_left_zero
static ir_node *equivalent_node_Sub(ir_node *n)
{
ir_node *oldn = n;
+ ir_node *a, *b;
+ ir_mode *mode = get_irn_mode(n);
- ir_node *a = get_Sub_left(n);
- ir_node *b = get_Sub_right(n);
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return n;
+
+ a = get_Sub_left(n);
+ b = get_Sub_right(n);
/* Beware: modes might be different */
if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
- if (get_irn_mode(n) == get_irn_mode(a)) {
+ if (mode == get_irn_mode(a)) {
n = a;
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
}
}
else if (get_irn_op(a) == op_Add) {
- ir_mode *mode = get_irn_mode(n);
-
if (mode_wrap_around(mode)) {
ir_node *left = get_Add_left(a);
ir_node *right = get_Add_right(a);
if (left == b) {
- if (get_irn_mode(n) == get_irn_mode(right)) {
+ if (mode == get_irn_mode(right)) {
n = right;
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
}
}
else if (right == b) {
- if (get_irn_mode(n) == get_irn_mode(left)) {
+ if (mode == get_irn_mode(left)) {
n = left;
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
}
}
}
}
-
return n;
-}
+} /* equivalent_node_Sub */
/**
* Optimize an "idempotent unary op", ie op(op(n)) = n.
*
- * @fixme -(-a) == a, but might overflow two times.
- * We handle it anyway here but the better way would be a
- * flag. This would be needed for Pascal for instance.
+ * @todo
+ * -(-a) == a, but might overflow two times.
+ * We handle it anyway here but the better way would be a
+ * flag. This would be needed for Pascal for instance.
*/
static ir_node *equivalent_node_idempotent_unop(ir_node *n)
{
DBG_OPT_ALGSIM2(oldn, pred, n);
}
return n;
-}
+} /* equivalent_node_idempotent_unop */
-/* Not(Not(x)) == x */
+/** Optimize Not(Not(x)) == x. */
#define equivalent_node_Not equivalent_node_idempotent_unop
-/* --x == x */ /* ??? Is this possible or can --x raise an
+/** --x == x ??? Is this possible or can --x raise an
out of bounds exception if min =! max? */
#define equivalent_node_Minus equivalent_node_idempotent_unop
static ir_node *equivalent_node_Mul(ir_node *n)
{
ir_node *oldn = n;
-
ir_node *a = get_Mul_left(n);
ir_node *b = get_Mul_right(n);
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
}
return n;
-}
+} /* equivalent_node_Mul */
/**
* Optimize a / 1 = a.
*/
-static ir_node *equivalent_node_Div(ir_node *n)
-{
+static ir_node *equivalent_node_Div(ir_node *n) {
ir_node *a = get_Div_left(n);
ir_node *b = get_Div_right(n);
if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
/* Turn Div into a tuple (mem, bad, a) */
ir_node *mem = get_Div_mem(n);
- turn_into_tuple(n, 3);
+ turn_into_tuple(n, pn_Div_max);
set_Tuple_pred(n, pn_Div_M, mem);
set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
set_Tuple_pred(n, pn_Div_res, a);
}
return n;
-}
+} /* equivalent_node_Div */
+
+/**
+ * Optimize a / 1.0 = a.
+ */
+static ir_node *equivalent_node_Quot(ir_node *n) {
+ ir_node *a = get_Quot_left(n);
+ ir_node *b = get_Quot_right(n);
+
+ /* Div is not commutative. */
+ if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* Quot(x, 1) == x */
+ /* Turn Quot into a tuple (mem, bad, a) */
+ ir_node *mem = get_Quot_mem(n);
+ turn_into_tuple(n, pn_Quot_max);
+ set_Tuple_pred(n, pn_Quot_M, mem);
+ set_Tuple_pred(n, pn_Quot_X_except, new_Bad()); /* no exception */
+ set_Tuple_pred(n, pn_Quot_res, a);
+ }
+ return n;
+} /* equivalent_node_Quot */
/**
* Optimize a / 1 = a.
*/
-static ir_node *equivalent_node_DivMod(ir_node *n)
-{
+static ir_node *equivalent_node_DivMod(ir_node *n) {
ir_node *a = get_DivMod_left(n);
ir_node *b = get_DivMod_right(n);
ir_node *mem = get_Div_mem(n);
ir_mode *mode = get_irn_mode(b);
- turn_into_tuple(n, 4);
+ turn_into_tuple(n, pn_DivMod_max);
set_Tuple_pred(n, pn_DivMod_M, mem);
set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
set_Tuple_pred(n, pn_DivMod_res_div, a);
set_Tuple_pred(n, pn_DivMod_res_mod, new_Const(mode, get_mode_null(mode)));
}
return n;
-}
+} /* equivalent_node_DivMod */
/**
* Use algebraic simplification a | a = a | 0 = 0 | a = a.
*/
-static ir_node *equivalent_node_Or(ir_node *n)
-{
+static ir_node *equivalent_node_Or(ir_node *n) {
ir_node *oldn = n;
ir_node *a = get_Or_left(n);
}
return n;
-}
+} /* equivalent_node_Or */
/**
* Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
*/
-static ir_node *equivalent_node_And(ir_node *n)
-{
+static ir_node *equivalent_node_And(ir_node *n) {
ir_node *oldn = n;
ir_node *a = get_And_left(n);
DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
}
return n;
-}
+} /* equivalent_node_And */
/**
* Try to remove useless Conv's:
*/
-static ir_node *equivalent_node_Conv(ir_node *n)
-{
+static ir_node *equivalent_node_Conv(ir_node *n) {
ir_node *oldn = n;
ir_node *a = get_Conv_op(n);
ir_node *b;
ir_mode *a_mode = get_irn_mode(a);
if (n_mode == a_mode) { /* No Conv necessary */
+ /* leave strict floating point Conv's */
+ if (get_Conv_strict(n))
+ return n;
n = a;
DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
} else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
}
}
return n;
-}
+} /* equivalent_node_Conv */
/**
* A Cast may be removed if the type of the previous node
DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CAST);
}
return n;
-}
+} /* equivalent_node_Cast */
-/* Several optimizations:
- - no Phi in start block.
- - remove Id operators that are inputs to Phi
- - fold Phi-nodes, iff they have only one predecessor except
- themselves.
-*/
+/**
+ * Several optimizations:
+ * - no Phi in start block.
+ * - remove Id operators that are inputs to Phi
+ * - fold Phi-nodes, iff they have only one predecessor except
+ * themselves.
+ */
static ir_node *equivalent_node_Phi(ir_node *n)
{
int i, n_preds;
ir_node *oldn = n;
ir_node *block = NULL; /* to shutup gcc */
ir_node *first_val = NULL; /* to shutup gcc */
- ir_node *scnd_val = NULL; /* to shutup gcc */
if (!get_opt_normalize()) return n;
/* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
if ((is_Block_dead(block)) || /* Control dead */
- (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
- return new_Bad(); /* in the Start Block. */
+ (block == get_irg_start_block(current_ir_graph))) /* There should be no Phi nodes */
+ return new_Bad(); /* in the Start Block. */
if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
return new_Bad();
}
- scnd_val = NULL;
-
- /* follow_Id () for rest of inputs, determine if any of these
+ /* search for rest of inputs, determine if any of these
are non-self-referencing */
while (++i < n_preds) {
- scnd_val = get_Phi_pred(n, i);
+ ir_node *scnd_val = get_Phi_pred(n, i);
if ( (scnd_val != n)
&& (scnd_val != first_val)
#if 1
/* Fold, if no multiple distinct non-self-referencing inputs */
n = first_val;
DBG_OPT_PHI(oldn, n);
- } else {
- /* skip the remaining Ids (done in get_Phi_pred). */
- /* superfluous, since we walk all to propagate Block's Bads.
- while (++i < n_preds) get_Phi_pred(n, i); */
}
return n;
-}
+} /* equivalent_node_Phi */
+
+/**
+ * Several optimizations:
+ * - no Sync in start block.
+ * - fold Sync-nodes, iff they have only one predecessor except
+ * themselves.
+ */
+static ir_node *equivalent_node_Sync(ir_node *n)
+{
+ int i, n_preds;
+
+ ir_node *oldn = n;
+ ir_node *first_val = NULL; /* to shutup gcc */
+
+ if (!get_opt_normalize()) return n;
+
+ n_preds = get_Sync_n_preds(n);
+
+ /* Find first non-self-referencing input */
+ for (i = 0; i < n_preds; ++i) {
+ first_val = get_Sync_pred(n, i);
+ if ((first_val != n) /* not self pointer */ &&
+ (! is_Bad(first_val))
+ ) { /* value not dead */
+ break; /* then found first value. */
+ }
+ }
+
+ if (i >= n_preds)
+ /* A totally Bad or self-referencing Sync (we didn't break the above loop) */
+ return new_Bad();
+
+ /* search the rest of inputs, determine if any of these
+ are non-self-referencing */
+ while (++i < n_preds) {
+ ir_node *scnd_val = get_Sync_pred(n, i);
+ if ((scnd_val != n) &&
+ (scnd_val != first_val) &&
+ (! is_Bad(scnd_val))
+ )
+ break;
+ }
+
+ if (i >= n_preds) {
+ /* Fold, if no multiple distinct non-self-referencing inputs */
+ n = first_val;
+ DBG_OPT_SYNC(oldn, n);
+ }
+ return n;
+} /* equivalent_node_Sync */
/**
- * optimize Proj(Tuple) and gigo() for ProjX in Bad block
+ * Optimize Proj(Tuple) and gigo() for ProjX in Bad block,
+ * ProjX(Load) and ProjX(Store).
*/
static ir_node *equivalent_node_Proj(ir_node *n)
{
assert(0); /* This should not happen! */
n = new_Bad();
}
- } else if (get_irn_mode(n) == mode_X) {
+ }
+ else if (get_irn_mode(n) == mode_X) {
if (is_Block_dead(get_nodes_block(skip_Proj(n)))) {
/* Remove dead control flow -- early gigo(). */
n = new_Bad();
}
+ else if (get_opt_ldst_only_null_ptr_exceptions()) {
+ ir_op *op = get_irn_op(a);
+
+ if (op == op_Load || op == op_Store) {
+ /* get the load/store address */
+ ir_node *addr = get_irn_n(a, 1);
+ ir_node *confirm;
+
+ if (value_not_null(addr, &confirm)) {
+ if (confirm == NULL) {
+ /* this node may float if it did not depend on a Confirm */
+ set_irn_pinned(a, op_pin_state_floats);
+ }
+ DBG_OPT_EXC_REM(n);
+ return new_Bad();
+ }
+ }
+ }
}
+
return n;
-}
+} /* equivalent_node_Proj */
/**
* Remove Id's.
*/
-static ir_node *equivalent_node_Id(ir_node *n)
-{
+static ir_node *equivalent_node_Id(ir_node *n) {
ir_node *oldn = n;
do {
DBG_OPT_ID(oldn, n);
return n;
-}
+} /* equivalent_node_Id */
/**
- * optimize a Mux
+ * Optimize a Mux.
*/
static ir_node *equivalent_node_Mux(ir_node *n)
{
}
}
}
+ return n;
+} /* equivalent_node_Mux */
+/**
+ * Returns a equivalent node of a Psi: if a condition is true
+ * and all previous conditions are false we know its value.
+ * If all conditions are false its value is the default one.
+ */
+static ir_node *equivalent_node_Psi(ir_node *n) {
+ if (is_Mux(n))
+ return equivalent_node_Mux(n);
return n;
-}
+} /* equivalent_node_Psi */
/**
* Optimize -a CMP -b into b CMP a.
set_Cmp_right(n, left);
}
return n;
-}
+} /* equivalent_node_Cmp */
/**
* Remove Confirm nodes if setting is on.
+ * Replace Confirms(x, '=', Constlike) by Constlike.
*/
-static ir_node *equivalent_node_Confirm(ir_node *n)
-{
- if (get_Confirm_cmp(n) == pn_Cmp_Eq) {
+static ir_node *equivalent_node_Confirm(ir_node *n) {
+ ir_node *pred = get_Confirm_value(n);
+ pn_Cmp pnc = get_Confirm_cmp(n);
+
+ if (get_irn_op(pred) == op_Confirm && pnc == get_Confirm_cmp(pred)) {
+ /*
+ * rare case: two identical Confirms one after another,
+ * replace the second one with the first.
+ */
+ n = pred;
+ }
+ if (pnc == pn_Cmp_Eq) {
ir_node *bound = get_Confirm_bound(n);
- ir_op *op = get_irn_op(bound);
/*
* Optimize a rare case:
- * Confirm(x, '=', Const) ==> Const
+ * Confirm(x, '=', Constlike) ==> Constlike
*/
- if (op == op_Const || op == op_SymConst)
+ if (is_irn_constlike(bound)) {
+ DBG_OPT_CONFIRM(n, bound);
return bound;
+ }
}
- return get_opt_remove_Confirm() ? get_Confirm_value(n) : n;
+ return get_opt_remove_confirm() ? get_Confirm_value(n) : n;
}
+/**
+ * Optimize CopyB(mem, x, x) into a Nop.
+ */
+static ir_node *equivalent_node_CopyB(ir_node *n) {
+ ir_node *a = get_CopyB_dst(n);
+ ir_node *b = get_CopyB_src(n);
+
+ if (a == b) {
+ /* Turn CopyB into a tuple (mem, bad, bad) */
+ ir_node *mem = get_CopyB_mem(n);
+ turn_into_tuple(n, pn_CopyB_max);
+ set_Tuple_pred(n, pn_CopyB_M, mem);
+ set_Tuple_pred(n, pn_CopyB_X_except, new_Bad()); /* no exception */
+ set_Tuple_pred(n, pn_CopyB_M_except, new_Bad());
+ }
+ return n;
+} /* equivalent_node_CopyB */
+
+/**
+ * Optimize Bounds(idx, idx, upper) into idx.
+ */
+static ir_node *equivalent_node_Bound(ir_node *n) {
+ ir_node *idx = get_Bound_index(n);
+ ir_node *lower = get_Bound_lower(n);
+ int ret_tuple = 0;
+
+ /* By definition lower < upper, so if idx == lower -->
+ lower <= idx && idx < upper */
+ if (idx == lower) {
+ /* Turn Bound into a tuple (mem, bad, idx) */
+ ret_tuple = 1;
+ }
+ else {
+ ir_node *pred = skip_Proj(idx);
+
+ if (get_irn_op(pred) == op_Bound) {
+ /*
+ * idx was Bounds_check previously, it is still valid if
+ * lower <= pred_lower && pred_upper <= upper.
+ */
+ ir_node *upper = get_Bound_upper(n);
+ if (get_Bound_lower(pred) == lower &&
+ get_Bound_upper(pred) == upper) {
+ /*
+ * One could expect that we simply return the previous
+ * Bound here. However, this would be wrong, as we could
+ * add an exception Proj to a new location than.
+ * So, we must turn in into a tuple
+ */
+ ret_tuple = 1;
+ }
+ }
+ }
+ if (ret_tuple) {
+ /* Turn Bound into a tuple (mem, bad, idx) */
+ ir_node *mem = get_Bound_mem(n);
+ turn_into_tuple(n, pn_Bound_max);
+ set_Tuple_pred(n, pn_Bound_M, mem);
+ set_Tuple_pred(n, pn_Bound_X_except, new_Bad()); /* no exception */
+ set_Tuple_pred(n, pn_Bound_res, idx);
+ }
+ return n;
+} /* equivalent_node_Bound */
+
/**
* equivalent_node() returns a node equivalent to input n. It skips all nodes that
* perform no actual computation, as, e.g., the Id nodes. It does not create
* If a node returns a Tuple we can not just skip it. If the size of the
* in array fits, we transform n into a tuple (e.g., Div).
*/
-ir_node *
-equivalent_node(ir_node *n)
-{
- if (n->op->equivalent_node)
- return n->op->equivalent_node(n);
+ir_node *equivalent_node(ir_node *n) {
+ if (n->op->ops.equivalent_node)
+ return n->op->ops.equivalent_node(n);
return n;
-}
+} /* equivalent_node */
/**
- * set the default equivalent node operation
+ * Sets the default equivalent node operation for an ir_op_ops.
+ *
+ * @param code the opcode for the default operation
+ * @param ops the operations initialized
+ *
+ * @return
+ * The operations.
*/
-static ir_op *firm_set_default_equivalent_node(ir_op *op)
+static ir_op_ops *firm_set_default_equivalent_node(opcode code, ir_op_ops *ops)
{
#define CASE(a) \
case iro_##a: \
- op->equivalent_node = equivalent_node_##a; \
+ ops->equivalent_node = equivalent_node_##a; \
break
- switch (op->code) {
+ switch (code) {
CASE(Block);
CASE(Jmp);
+ CASE(Raise);
CASE(Or);
CASE(Add);
CASE(Eor);
CASE(Minus);
CASE(Mul);
CASE(Div);
+ CASE(Quot);
CASE(DivMod);
CASE(And);
CASE(Conv);
CASE(Cast);
CASE(Phi);
+ CASE(Sync);
CASE(Proj);
CASE(Id);
CASE(Mux);
+ CASE(Psi);
CASE(Cmp);
CASE(Confirm);
+ CASE(CopyB);
+ CASE(Bound);
default:
- op->equivalent_node = NULL;
+ /* leave NULL */;
}
- return op;
+ return ops;
#undef CASE
-}
+} /* firm_set_default_equivalent_node */
/**
* Do node specific optimizations of nodes predecessors.
*/
-static void
-optimize_preds(ir_node *n) {
+static void optimize_preds(ir_node *n) {
ir_node *a = NULL, *b = NULL;
/* get the operands we will work on for simple cases. */
default: break;
} /* end switch */
-}
+} /* optimize_preds */
+
+/**
+ * Returns non-zero if a node is a Phi node
+ * with all predecessors constant.
+ */
+static int is_const_Phi(ir_node *n) {
+ int i;
+
+ if (! is_Phi(n))
+ return 0;
+ for (i = get_irn_arity(n) - 1; i >= 0; --i)
+ if (! is_Const(get_irn_n(n, i)))
+ return 0;
+ return 1;
+} /* is_const_Phi */
+
+/**
+ * Apply an evaluator on a binop with a constant operators (and one Phi).
+ *
+ * @param phi the Phi node
+ * @param other the other operand
+ * @param eval an evaluator function
+ * @param left if non-zero, other is the left operand, else the right
+ *
+ * @return a new Phi node if the conversion was successful, NULL else
+ */
+static ir_node *apply_binop_on_phi(ir_node *phi, tarval *other, tarval *(*eval)(tarval *, tarval *), int left) {
+ tarval *tv;
+ void **res;
+ ir_node *pred;
+ ir_mode *mode;
+ ir_graph *irg;
+ int i, n = get_irn_arity(phi);
+
+ NEW_ARR_A(void *, res, n);
+ if (left) {
+ for (i = 0; i < n; ++i) {
+ pred = get_irn_n(phi, i);
+ tv = get_Const_tarval(pred);
+ tv = eval(other, tv);
+
+ if (tv == tarval_bad) {
+ /* folding failed, bad */
+ return NULL;
+ }
+ res[i] = tv;
+ }
+ }
+ else {
+ for (i = 0; i < n; ++i) {
+ pred = get_irn_n(phi, i);
+ tv = get_Const_tarval(pred);
+ tv = eval(tv, other);
+
+ if (tv == tarval_bad) {
+ /* folding failed, bad */
+ return 0;
+ }
+ res[i] = tv;
+ }
+ }
+ mode = get_irn_mode(phi);
+ irg = current_ir_graph;
+ for (i = 0; i < n; ++i) {
+ pred = get_irn_n(phi, i);
+ res[i] = new_r_Const_type(irg, get_irg_start_block(irg),
+ mode, res[i], get_Const_type(pred));
+ }
+ return new_r_Phi(irg, get_nodes_block(phi), n, (ir_node **)res, mode);
+} /* apply_binop_on_phi */
+
+/**
+ * Apply an evaluator on a unop with a constant operator (a Phi).
+ *
+ * @param phi the Phi node
+ * @param eval an evaluator function
+ *
+ * @return a new Phi node if the conversion was successful, NULL else
+ */
+static ir_node *apply_unop_on_phi(ir_node *phi, tarval *(*eval)(tarval *)) {
+ tarval *tv;
+ void **res;
+ ir_node *pred;
+ ir_mode *mode;
+ ir_graph *irg;
+ int i, n = get_irn_arity(phi);
+
+ NEW_ARR_A(void *, res, n);
+ for (i = 0; i < n; ++i) {
+ pred = get_irn_n(phi, i);
+ tv = get_Const_tarval(pred);
+ tv = eval(tv);
+
+ if (tv == tarval_bad) {
+ /* folding failed, bad */
+ return 0;
+ }
+ res[i] = tv;
+ }
+ mode = get_irn_mode(phi);
+ irg = current_ir_graph;
+ for (i = 0; i < n; ++i) {
+ pred = get_irn_n(phi, i);
+ res[i] = new_r_Const_type(irg, get_irg_start_block(irg),
+ mode, res[i], get_Const_type(pred));
+ }
+ return new_r_Phi(irg, get_nodes_block(phi), n, (ir_node **)res, mode);
+} /* apply_unop_on_phi */
/**
* Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
}
}
}
- return n;
-}
-
-/**
- * Do the AddSub optimization, then Transform Add(a,a) into Mul(a, 2)
+ return n;
+} /* transform_node_AddSub */
+
+#define HANDLE_BINOP_PHI(op,a,b,c) \
+ c = NULL; \
+ if (is_Const(b) && is_const_Phi(a)) { \
+ /* check for Op(Phi, Const) */ \
+ c = apply_binop_on_phi(a, get_Const_tarval(b), op, 0); \
+ } \
+ else if (is_Const(a) && is_const_Phi(b)) { \
+ /* check for Op(Const, Phi) */ \
+ c = apply_binop_on_phi(b, get_Const_tarval(a), op, 1); \
+ } \
+ if (c) { \
+ DBG_OPT_ALGSIM0(oldn, c, FS_OPT_CONST_PHI); \
+ return c; \
+ }
+
+#define HANDLE_UNOP_PHI(op,a,c) \
+ c = NULL; \
+ if (is_const_Phi(a)) { \
+ /* check for Op(Phi) */ \
+ c = apply_unop_on_phi(a, op); \
+ } \
+ if (c) { \
+ DBG_OPT_ALGSIM0(oldn, c, FS_OPT_CONST_PHI); \
+ return c; \
+ }
+
+
+/**
+ * Do the AddSub optimization, then Transform
+ * Constant folding on Phi
+ * Add(a,a) -> Mul(a, 2)
+ * Add(Mul(a, x), a) -> Mul(a, x+1)
* if the mode is integer or float.
* Transform Add(a,-b) into Sub(a,b).
* Reassociation might fold this further.
static ir_node *transform_node_Add(ir_node *n)
{
ir_mode *mode;
- ir_node *oldn = n;
+ ir_node *a, *b, *c, *oldn = n;
n = transform_node_AddSub(n);
+ a = get_Add_left(n);
+ b = get_Add_right(n);
+
+ HANDLE_BINOP_PHI(tarval_add, a,b,c);
+
mode = get_irn_mode(n);
- if (mode_is_num(mode)) {
- ir_node *a = get_Add_left(n);
- if (a == get_Add_right(n)) {
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return n;
+
+ if (mode_is_num(mode)) {
+ if (a == b) {
ir_node *block = get_irn_n(n, -1);
n = new_rd_Mul(
mode);
DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_A);
}
- else {
- ir_node *b = get_Add_right(n);
-
- if (get_irn_op(a) == op_Minus) {
- n = new_rd_Sub(
- get_irn_dbg_info(n),
- current_ir_graph,
- get_irn_n(n, -1),
- b,
- get_Minus_op(a),
- mode);
- DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
+ else if (get_irn_op(a) == op_Minus) {
+ n = new_rd_Sub(
+ get_irn_dbg_info(n),
+ current_ir_graph,
+ get_irn_n(n, -1),
+ b,
+ get_Minus_op(a),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
+ }
+ else if (get_irn_op(b) == op_Minus) {
+ n = new_rd_Sub(
+ get_irn_dbg_info(n),
+ current_ir_graph,
+ get_irn_n(n, -1),
+ a,
+ get_Minus_op(b),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
+ }
+ /* do NOT execute this code if reassociation is enabled, it does the inverse! */
+ else if (!get_opt_reassociation() && get_irn_op(a) == op_Mul) {
+ ir_node *ma = get_Mul_left(a);
+ ir_node *mb = get_Mul_right(a);
+
+ if (b == ma) {
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Mul(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ ma,
+ new_rd_Add(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ mb,
+ new_r_Const_long(current_ir_graph, blk, mode, 1),
+ mode),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
}
- else if (get_irn_op(b) == op_Minus) {
- n = new_rd_Sub(
- get_irn_dbg_info(n),
- current_ir_graph,
- get_irn_n(n, -1),
- a,
- get_Minus_op(b),
- mode);
- DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
+ else if (b == mb) {
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Mul(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ mb,
+ new_rd_Add(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ ma,
+ new_r_Const_long(current_ir_graph, blk, mode, 1),
+ mode),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
+ }
+ }
+ /* do NOT execute this code if reassociation is enabled, it does the inverse! */
+ else if (!get_opt_reassociation() && get_irn_op(b) == op_Mul) {
+ ir_node *ma = get_Mul_left(b);
+ ir_node *mb = get_Mul_right(b);
+
+ if (a == ma) {
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Mul(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ ma,
+ new_rd_Add(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ mb,
+ new_r_Const_long(current_ir_graph, blk, mode, 1),
+ mode),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
+ }
+ else if (a == mb) {
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Mul(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ mb,
+ new_rd_Add(
+ get_irn_dbg_info(n), current_ir_graph, blk,
+ ma,
+ new_r_Const_long(current_ir_graph, blk, mode, 1),
+ mode),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
}
}
}
return n;
-}
+} /* transform_node_Add */
/**
- * Do the AddSub optimization, then Transform Sub(0,a) into Minus(a).
+ * Do the AddSub optimization, then Transform
+ * Constant folding on Phi
+ * Sub(0,a) -> Minus(a)
+ * Sub(Mul(a, x), a) -> Mul(a, x-1)
+ * Sub(Sub(x, y), b) -> Sub(x, Add(y,b))
*/
static ir_node *transform_node_Sub(ir_node *n)
{
ir_mode *mode;
ir_node *oldn = n;
+ ir_node *a, *b, *c;
n = transform_node_AddSub(n);
+ a = get_Sub_left(n);
+ b = get_Sub_right(n);
+
+ HANDLE_BINOP_PHI(tarval_sub, a,b,c);
+
mode = get_irn_mode(n);
- if (mode_is_num(mode) && (classify_Const(get_Sub_left(n)) == CNST_NULL)) {
+
+ /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
+ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
+ return n;
+
+ if (mode_is_num(mode) && (classify_Const(a) == CNST_NULL)) {
n = new_rd_Minus(
get_irn_dbg_info(n),
current_ir_graph,
get_irn_n(n, -1),
- get_Sub_right(n),
+ b,
mode);
DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_0_A);
}
+ /* do NOT execute this code if reassociation is enabled, it does the inverse! */
+ else if (get_opt_reassociation() && get_irn_op(a) == op_Mul) {
+ ir_node *ma = get_Mul_left(a);
+ ir_node *mb = get_Mul_right(a);
+
+ if (ma == b) {
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Mul(
+ get_irn_dbg_info(n),
+ current_ir_graph, blk,
+ ma,
+ new_rd_Sub(
+ get_irn_dbg_info(n),
+ current_ir_graph, blk,
+ mb,
+ new_r_Const_long(current_ir_graph, blk, mode, 1),
+ mode),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
+ }
+ else if (mb == b) {
+ ir_node *blk = get_irn_n(n, -1);
+ n = new_rd_Mul(
+ get_irn_dbg_info(n),
+ current_ir_graph, blk,
+ mb,
+ new_rd_Sub(
+ get_irn_dbg_info(n),
+ current_ir_graph, blk,
+ ma,
+ new_r_Const_long(current_ir_graph, blk, mode, 1),
+ mode),
+ mode);
+ DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
+ }
+ }
+ else if (get_irn_op(a) == op_Sub) {
+ ir_node *x = get_Sub_left(a);
+ ir_node *y = get_Sub_right(a);
+ ir_node *blk = get_irn_n(n, -1);
+ ir_mode *m_b = get_irn_mode(b);
+ ir_mode *m_y = get_irn_mode(y);
+ ir_node *add;
+
+ /* Determine the right mode for the Add. */
+ if (m_b == m_y)
+ mode = m_b;
+ else if (mode_is_reference(m_b))
+ mode = m_b;
+ else if (mode_is_reference(m_y))
+ mode = m_y;
+ else {
+ /*
+ * Both modes are different but none is reference,
+ * happens for instance in SubP(SubP(P, Iu), Is).
+ * We have two possibilities here: Cast or ignore.
+ * Currently we ignore this case.
+ */
+ return n;
+ }
+
+ add = new_r_Add(current_ir_graph, blk, y, b, mode);
+
+ set_Sub_left(n, x);
+ set_Sub_right(n, add);
+ DBG_OPT_ALGSIM0(n, n, FS_OPT_SUB_SUB_X_Y_Z);
+ }
return n;
-}
+} /* transform_node_Sub */
/**
* Transform Mul(a,-1) into -a.
+ * Do constant evaluation of Phi nodes.
* Do architecture dependent optimizations on Mul nodes
*/
static ir_node *transform_node_Mul(ir_node *n) {
- ir_node *oldn = n;
- ir_mode *mode = get_irn_mode(n);
+ ir_node *c, *oldn = n;
+ ir_node *a = get_Mul_left(n);
+ ir_node *b = get_Mul_right(n);
+ ir_mode *mode;
+ HANDLE_BINOP_PHI(tarval_mul, a,b,c);
+
+ mode = get_irn_mode(n);
if (mode_is_signed(mode)) {
ir_node *r = NULL;
- ir_node *a = get_Mul_left(n);
- ir_node *b = get_Mul_right(n);
if (value_of(a) == get_mode_minus_one(mode))
r = b;
}
}
return arch_dep_replace_mul_with_shifts(n);
-}
+} /* transform_node_Mul */
/**
- * transform a Div Node
+ * Transform a Div Node.
*/
static ir_node *transform_node_Div(ir_node *n)
{
/* Turn Div into a tuple (mem, bad, value) */
ir_node *mem = get_Div_mem(n);
- turn_into_tuple(n, 3);
+ turn_into_tuple(n, pn_Div_max);
set_Tuple_pred(n, pn_Div_M, mem);
set_Tuple_pred(n, pn_Div_X_except, new_Bad());
set_Tuple_pred(n, pn_Div_res, value);
}
return n;
-}
+} /* transform_node_Div */
/**
- * transform a Mod node
+ * Transform a Mod node.
*/
static ir_node *transform_node_Mod(ir_node *n)
{
/* Turn Mod into a tuple (mem, bad, value) */
ir_node *mem = get_Mod_mem(n);
- turn_into_tuple(n, 3);
+ turn_into_tuple(n, pn_Mod_max);
set_Tuple_pred(n, pn_Mod_M, mem);
set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
set_Tuple_pred(n, pn_Mod_res, value);
}
return n;
-}
+} /* transform_node_Mod */
/**
- * transform a DivMod node
+ * Transform a DivMod node.
*/
static ir_node *transform_node_DivMod(ir_node *n)
{
if (evaluated) { /* replace by tuple */
ir_node *mem = get_DivMod_mem(n);
- turn_into_tuple(n, 4);
+ turn_into_tuple(n, pn_DivMod_max);
set_Tuple_pred(n, pn_DivMod_M, mem);
set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
set_Tuple_pred(n, pn_DivMod_res_div, a);
}
return n;
-}
+} /* transform_node_DivMod */
/**
* Optimize Abs(x) into x if x is Confirmed >= 0
{
ir_node *oldn = n;
ir_node *a = get_Abs_op(n);
- value_classify sign = classify_value_sign(a);
+ value_classify_sign sign = classify_value_sign(a);
- if (sign == VALUE_NEGATIVE) {
+ if (sign == value_classified_negative) {
ir_mode *mode = get_irn_mode(n);
/*
DBG_OPT_CONFIRM(oldn, n);
}
- else if (sign == VALUE_POSITIVE) {
+ else if (sign == value_classified_positive) {
/* n is positive, Abs is not needed */
n = a;
}
return n;
-}
+} /* transform_node_Abs */
/**
- * transform a Cond node
+ * Transform a Cond node.
*/
static ir_node *transform_node_Cond(ir_node *n)
{
/* It's a boolean Cond, branching on a boolean constant.
Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
- turn_into_tuple(n, 2);
+ turn_into_tuple(n, pn_Cond_max);
if (ta == tarval_b_true) {
set_Tuple_pred(n, pn_Cond_false, new_Bad());
set_Tuple_pred(n, pn_Cond_true, jmp);
}
/* We might generate an endless loop, so keep it alive. */
add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
- } else if ((ta != tarval_bad) &&
- (get_irn_mode(a) == mode_Iu) &&
- (get_Cond_kind(n) == dense) &&
- (get_opt_unreachable_code())) {
- /* I don't want to allow Tuples smaller than the biggest Proj.
- Also this tuple might get really big...
- I generate the Jmp here, and remember it in link. Link is used
- when optimizing Proj. */
- set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
- /* We might generate an endless loop, so keep it alive. */
- add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
- } else if ((get_irn_op(a) == op_Eor)
- && (get_irn_mode(a) == mode_b)
- && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
- /* The Eor is a negate. Generate a new Cond without the negate,
- simulate the negate by exchanging the results. */
- set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
- get_Eor_left(a)));
- } else if ((get_irn_op(a) == op_Not)
- && (get_irn_mode(a) == mode_b)) {
- /* A Not before the Cond. Generate a new Cond without the Not,
- simulate the Not by exchanging the results. */
- set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
- get_Not_op(a)));
}
return n;
-}
+} /* transform_node_Cond */
+
+/**
+ * Transform an And.
+ */
+static ir_node *transform_node_And(ir_node *n)
+{
+ ir_node *c, *oldn = n;
+ ir_node *a = get_And_left(n);
+ ir_node *b = get_And_right(n);
+
+ HANDLE_BINOP_PHI(tarval_and, a,b,c);
+ return n;
+} /* transform_node_And */
/**
* Transform an Eor.
*/
static ir_node *transform_node_Eor(ir_node *n)
{
- ir_node *oldn = n;
+ ir_node *c, *oldn = n;
ir_node *a = get_Eor_left(n);
ir_node *b = get_Eor_right(n);
ir_mode *mode = get_irn_mode(n);
+ HANDLE_BINOP_PHI(tarval_eor, a,b,c);
+
if (a == b) {
/* a ^ a = 0 */
n = new_rd_Const(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1),
}
return n;
-}
+} /* transform_node_Eor */
/**
- * Transform a boolean Not.
+ * Transform a Not.
*/
static ir_node *transform_node_Not(ir_node *n)
{
- ir_node *oldn = n;
+ ir_node *c, *oldn = n;
ir_node *a = get_Not_op(n);
+ HANDLE_UNOP_PHI(tarval_not,a,c);
+
+ /* check for a boolean Not */
if ( (get_irn_mode(n) == mode_b)
&& (get_irn_op(a) == op_Proj)
&& (get_irn_mode(a) == mode_b)
mode_b, get_negated_pnc(get_Proj_proj(a), mode_b));
DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_CMP);
}
+ return n;
+} /* transform_node_Not */
+
+/**
+ * Transform a Minus.
+ */
+static ir_node *transform_node_Minus(ir_node *n)
+{
+ ir_node *c, *oldn = n;
+ ir_node *a = get_Minus_op(n);
+ HANDLE_UNOP_PHI(tarval_neg,a,c);
return n;
-}
+} /* transform_node_Minus */
/**
* Transform a Cast_type(Const) into a new Const_type
static ir_node *transform_node_Cast(ir_node *n) {
ir_node *oldn = n;
ir_node *pred = get_Cast_op(n);
- type *tp = get_irn_type(n);
+ ir_type *tp = get_irn_type(n);
if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
n = new_rd_Const_type(NULL, current_ir_graph, get_irn_n(pred, -1), get_irn_mode(pred),
}
return n;
-}
+} /* transform_node_Cast */
/**
* Transform a Proj(Div) with a non-zero value.
{
ir_node *n = get_Proj_pred(proj);
ir_node *b = get_Div_right(n);
+ ir_node *confirm;
long proj_nr;
- if (value_not_zero(b)) {
+ if (value_not_zero(b, &confirm)) {
/* div(x, y) && y != 0 */
proj_nr = get_Proj_proj(proj);
-
- /* this node may float */
- set_irn_pinned(n, op_pin_state_floats);
-
if (proj_nr == pn_Div_X_except) {
/* we found an exception handler, remove it */
+ DBG_OPT_EXC_REM(proj);
return new_Bad();
- } else {
- /* the memory Proj can be removed */
+ }
+ else if (proj_nr == pn_Div_M) {
ir_node *res = get_Div_mem(n);
- set_Div_mem(n, get_irg_no_mem(current_ir_graph));
- if (proj_nr == pn_Div_M)
- return res;
+ ir_node *new_mem = get_irg_no_mem(current_ir_graph);
+
+ if (confirm) {
+ /* This node can only float up to the Confirm block */
+ new_mem = new_r_Pin(current_ir_graph, get_nodes_block(confirm), new_mem);
+ }
+ set_irn_pinned(n, op_pin_state_floats);
+ /* this is a Div without exception, we can remove the memory edge */
+ set_Div_mem(n, new_mem);
+ return res;
}
}
return proj;
-}
+} /* transform_node_Proj_Div */
/**
* Transform a Proj(Mod) with a non-zero value.
{
ir_node *n = get_Proj_pred(proj);
ir_node *b = get_Mod_right(n);
+ ir_node *confirm;
long proj_nr;
- if (value_not_zero(b)) {
+ if (value_not_zero(b, &confirm)) {
/* mod(x, y) && y != 0 */
proj_nr = get_Proj_proj(proj);
- /* this node may float */
- set_irn_pinned(n, op_pin_state_floats);
-
if (proj_nr == pn_Mod_X_except) {
/* we found an exception handler, remove it */
+ DBG_OPT_EXC_REM(proj);
return new_Bad();
- } else {
- /* the memory Proj can be removed */
+ } else if (proj_nr == pn_Mod_M) {
ir_node *res = get_Mod_mem(n);
+ ir_node *new_mem = get_irg_no_mem(current_ir_graph);
+
+ if (confirm) {
+ /* This node can only float up to the Confirm block */
+ new_mem = new_r_Pin(current_ir_graph, get_nodes_block(confirm), new_mem);
+ }
+ set_irn_pinned(n, op_pin_state_floats);
+ /* this is a Mod without exception, we can remove the memory edge */
set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
- if (proj_nr == pn_Mod_M)
- return res;
+ return res;
+ }
+ else if (proj_nr == pn_Mod_res && get_Mod_left(n) == b) {
+ /* a % a = 0 if a != 0 */
+ ir_mode *mode = get_irn_mode(proj);
+ ir_node *res = new_Const(mode, get_mode_null(mode));
+
+ DBG_OPT_CSTEVAL(n, res);
+ return res;
}
}
return proj;
-}
+} /* transform_node_Proj_Mod */
/**
* Transform a Proj(DivMod) with a non-zero value.
{
ir_node *n = get_Proj_pred(proj);
ir_node *b = get_DivMod_right(n);
+ ir_node *confirm;
long proj_nr;
- if (value_not_zero(b)) {
+ if (value_not_zero(b, &confirm)) {
/* DivMod(x, y) && y != 0 */
proj_nr = get_Proj_proj(proj);
- /* this node may float */
- set_irn_pinned(n, op_pin_state_floats);
-
if (proj_nr == pn_DivMod_X_except) {
/* we found an exception handler, remove it */
+ DBG_OPT_EXC_REM(proj);
return new_Bad();
}
- else {
- /* the memory Proj can be removed */
+ else if (proj_nr == pn_DivMod_M) {
ir_node *res = get_DivMod_mem(n);
+ ir_node *new_mem = get_irg_no_mem(current_ir_graph);
+
+ if (confirm) {
+ /* This node can only float up to the Confirm block */
+ new_mem = new_r_Pin(current_ir_graph, get_nodes_block(confirm), new_mem);
+ }
+ set_irn_pinned(n, op_pin_state_floats);
+ /* this is a DivMod without exception, we can remove the memory edge */
set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
- if (proj_nr == pn_DivMod_M)
- return res;
+ return res;
+ }
+ else if (proj_nr == pn_DivMod_res_mod && get_DivMod_left(n) == b) {
+ /* a % a = 0 if a != 0 */
+ ir_mode *mode = get_irn_mode(proj);
+ ir_node *res = new_Const(mode, get_mode_null(mode));
+
+ DBG_OPT_CSTEVAL(n, res);
+ return res;
}
}
return proj;
-}
+} /* transform_node_Proj_DivMod */
/**
* Optimizes jump tables (CondIs or CondIu) by removing all impossible cases.
if (get_opt_unreachable_code()) {
ir_node *n = get_Proj_pred(proj);
ir_node *b = get_Cond_selector(n);
- tarval *tb = value_of(b);
- if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
- /* we have a constant switch */
- long num = get_Proj_proj(proj);
+ if (mode_is_int(get_irn_mode(b))) {
+ tarval *tb = value_of(b);
- if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
- if (get_tarval_long(tb) == num) {
- /* Do NOT create a jump here, or we will have 2 control flow ops
- * in a block. This case is optimized away in optimize_cf(). */
- return proj;
- }
- else {
- /* this case will NEVER be taken, kill it */
- return new_Bad();
+ if (tb != tarval_bad) {
+ /* we have a constant switch */
+ long num = get_Proj_proj(proj);
+
+ if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
+ if (get_tarval_long(tb) == num) {
+ /* Do NOT create a jump here, or we will have 2 control flow ops
+ * in a block. This case is optimized away in optimize_cf(). */
+ return proj;
+ }
+ else {
+ /* this case will NEVER be taken, kill it */
+ return new_Bad();
+ }
}
}
}
}
return proj;
-}
+} /* transform_node_Proj_Cond */
/**
* Normalizes and optimizes Cmp nodes.
proj_nr = get_inversed_pnc(proj_nr);
changed |= 1;
}
- else if (left > right) {
+ else if (get_irn_idx(left) > get_irn_idx(right)) {
ir_node *t = left;
left = right;
if (mode_is_int(mode)) {
/* Ne includes Unordered which is not possible on integers.
* However, frontends often use this wrong, so fix it here */
- if (proj_nr == pn_Cmp_Ne) {
- proj_nr = pn_Cmp_Lg;
+ if (proj_nr & pn_Cmp_Uo) {
+ proj_nr &= ~pn_Cmp_Uo;
set_Proj_proj(proj, proj_nr);
}
}
}
} /* mode_is_int */
- }
+
+ /*
+ * optimization for AND:
+ * Optimize:
+ * And(x, C) == C ==> And(x, C) != 0
+ * And(x, C) != C ==> And(X, C) == 0
+ *
+ * if C is a single Bit constant.
+ */
+ if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) &&
+ (get_irn_op(left) == op_And)) {
+ if (is_single_bit_tarval(tv)) {
+ /* check for Constant's match. We have check hare the tarvals,
+ because our const might be changed */
+ ir_node *la = get_And_left(left);
+ ir_node *ra = get_And_right(left);
+ if ((is_Const(la) && get_Const_tarval(la) == tv) ||
+ (is_Const(ra) && get_Const_tarval(ra) == tv)) {
+ /* fine: do the transformation */
+ tv = get_mode_null(get_tarval_mode(tv));
+ proj_nr ^= pn_Cmp_Leg;
+ changed |= 2;
+ }
+ }
+ }
+ } /* tarval != bad */
}
if (changed) {
}
}
return proj;
-}
+} /* transform_node_Proj_Cmp */
/**
* Does all optimizations on nodes that must be done on it's Proj's
/* do nothing */
return proj;
}
-}
+} /* transform_node_Proj */
+
+/**
+ * Move Confirms down through Phi nodes.
+ */
+static ir_node *transform_node_Phi(ir_node *phi) {
+ int i, n;
+ ir_mode *mode = get_irn_mode(phi);
+
+ if (mode_is_reference(mode)) {
+ n = get_irn_arity(phi);
+
+ /* Beware of Phi0 */
+ if (n > 0) {
+ ir_node *pred = get_irn_n(phi, 0);
+ ir_node *bound, *new_Phi, *block, **in;
+ pn_Cmp pnc;
+
+ if (! is_Confirm(pred))
+ return phi;
+
+ bound = get_Confirm_bound(pred);
+ pnc = get_Confirm_cmp(pred);
+
+ NEW_ARR_A(ir_node *, in, n);
+ in[0] = get_Confirm_value(pred);
+
+ for (i = 1; i < n; ++i) {
+ pred = get_irn_n(phi, i);
+
+ if (! is_Confirm(pred) ||
+ get_Confirm_bound(pred) != bound ||
+ get_Confirm_cmp(pred) != pnc)
+ return phi;
+ in[i] = get_Confirm_value(pred);
+ }
+ /* move the Confirm nodes "behind" the Phi */
+ block = get_irn_n(phi, -1);
+ new_Phi = new_r_Phi(current_ir_graph, block, n, in, get_irn_mode(phi));
+ return new_r_Confirm(current_ir_graph, block, new_Phi, bound, pnc);
+ }
+ }
+ return phi;
+} /* transform_node_Phi */
/**
- * returns the operands of a commutative bin-op, if one operand is
+ * Returns the operands of a commutative bin-op, if one operand is
* a const, it is returned as the second one.
*/
static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
*a = op_a;
*c = op_b;
}
-}
+} /* get_comm_Binop_Ops */
/**
* Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
/* check for more */
return transform_node_Or_bf_store(or);
-}
+} /* transform_node_Or_bf_store */
/**
* Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
}
return or;
-}
+} /* transform_node_Or_Rot */
/**
- * Optimize an Or
+ * Transform an Or.
*/
-static ir_node *transform_node_Or(ir_node *or)
+static ir_node *transform_node_Or(ir_node *n)
{
- or = transform_node_Or_bf_store(or);
- or = transform_node_Or_Rot(or);
+ ir_node *c, *oldn = n;
+ ir_node *a = get_Or_left(n);
+ ir_node *b = get_Or_right(n);
+
+ HANDLE_BINOP_PHI(tarval_or, a,b,c);
+
+ n = transform_node_Or_bf_store(n);
+ n = transform_node_Or_Rot(n);
+
+ return n;
+} /* transform_node_Or */
- return or;
-}
/* forward */
static ir_node *transform_node(ir_node *n);
return transform_node(irn);
}
return n;
-}
+} /* transform_node_shift */
+
+/**
+ * Transform a Shr.
+ */
+static ir_node *transform_node_Shr(ir_node *n)
+{
+ ir_node *c, *oldn = n;
+ ir_node *a = get_Shr_left(n);
+ ir_node *b = get_Shr_right(n);
+
+ HANDLE_BINOP_PHI(tarval_shr, a, b, c);
+ return transform_node_shift(n);
+} /* transform_node_Shr */
+
+/**
+ * Transform a Shrs.
+ */
+static ir_node *transform_node_Shrs(ir_node *n)
+{
+ ir_node *c, *oldn = n;
+ ir_node *a = get_Shrs_left(n);
+ ir_node *b = get_Shrs_right(n);
+
+ HANDLE_BINOP_PHI(tarval_shrs, a, b, c);
+ return transform_node_shift(n);
+} /* transform_node_Shrs */
+
+/**
+ * Transform a Shl.
+ */
+static ir_node *transform_node_Shl(ir_node *n)
+{
+ ir_node *c, *oldn = n;
+ ir_node *a = get_Shl_left(n);
+ ir_node *b = get_Shl_right(n);
-#define transform_node_Shr transform_node_shift
-#define transform_node_Shrs transform_node_shift
-#define transform_node_Shl transform_node_shift
+ HANDLE_BINOP_PHI(tarval_shl, a, b, c);
+ return transform_node_shift(n);
+} /* transform_node_Shl */
/**
* Remove dead blocks and nodes in dead blocks
set_End_keepalive(n, i, new_Bad());
}
return n;
-}
+} /* transform_node_End */
/**
* Optimize a Mux into some simpler cases.
}
}
return arch_transform_node_Mux(n);
-}
+} /* transform_node_Mux */
+
+/**
+ * Optimize a Psi into some simpler cases.
+ */
+static ir_node *transform_node_Psi(ir_node *n) {
+ if (is_Mux(n))
+ return transform_node_Mux(n);
+
+ return n;
+} /* transform_node_Psi */
/**
* Tries several [inplace] [optimizing] transformations and returns an
*/
static ir_node *transform_node(ir_node *n)
{
- if (n->op->transform_node)
- n = n->op->transform_node(n);
+ if (n->op->ops.transform_node)
+ n = n->op->ops.transform_node(n);
return n;
-}
+} /* transform_node */
/**
- * set the default transform node operation
+ * sSets the default transform node operation for an ir_op_ops.
+ *
+ * @param code the opcode for the default operation
+ * @param ops the operations initialized
+ *
+ * @return
+ * The operations.
*/
-static ir_op *firm_set_default_transform_node(ir_op *op)
+static ir_op_ops *firm_set_default_transform_node(opcode code, ir_op_ops *ops)
{
#define CASE(a) \
case iro_##a: \
- op->transform_node = transform_node_##a; \
+ ops->transform_node = transform_node_##a; \
break
- switch (op->code) {
+ switch (code) {
CASE(Add);
CASE(Sub);
CASE(Mul);
CASE(DivMod);
CASE(Abs);
CASE(Cond);
+ CASE(And);
+ CASE(Or);
CASE(Eor);
+ CASE(Minus);
CASE(Not);
CASE(Cast);
CASE(Proj);
+ CASE(Phi);
CASE(Sel);
- CASE(Or);
CASE(Shr);
CASE(Shrs);
CASE(Shl);
CASE(End);
CASE(Mux);
+ CASE(Psi);
default:
- op->transform_node = NULL;
+ /* leave NULL */;
}
- return op;
+ return ops;
#undef CASE
-}
+} /* firm_set_default_transform_node */
/* **************** Common Subexpression Elimination **************** */
#define N_IR_NODES 512
/** Compares the attributes of two Const nodes. */
-static int node_cmp_attr_Const(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Const(ir_node *a, ir_node *b) {
return (get_Const_tarval(a) != get_Const_tarval(b))
|| (get_Const_type(a) != get_Const_type(b));
-}
+} /* node_cmp_attr_Const */
/** Compares the attributes of two Proj nodes. */
-static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Proj(ir_node *a, ir_node *b) {
return get_irn_proj_attr (a) != get_irn_proj_attr (b);
-}
+} /* node_cmp_attr_Proj */
/** Compares the attributes of two Filter nodes. */
-static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Filter(ir_node *a, ir_node *b) {
return get_Filter_proj(a) != get_Filter_proj(b);
-}
+} /* node_cmp_attr_Filter */
/** Compares the attributes of two Alloc nodes. */
-static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Alloc(ir_node *a, ir_node *b) {
return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
|| (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
-}
+} /* node_cmp_attr_Alloc */
/** Compares the attributes of two Free nodes. */
-static int node_cmp_attr_Free(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Free(ir_node *a, ir_node *b) {
return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
|| (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
-}
+} /* node_cmp_attr_Free */
/** Compares the attributes of two SymConst nodes. */
-static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_SymConst(ir_node *a, ir_node *b) {
return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
|| (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
|| (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
-}
+} /* node_cmp_attr_SymConst */
/** Compares the attributes of two Call nodes. */
-static int node_cmp_attr_Call(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Call(ir_node *a, ir_node *b) {
return (get_irn_call_attr(a) != get_irn_call_attr(b));
-}
+} /* node_cmp_attr_Call */
/** Compares the attributes of two Sel nodes. */
-static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Sel(ir_node *a, ir_node *b) {
return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
|| (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
|| (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
|| (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
|| (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
-}
+} /* node_cmp_attr_Sel */
/** Compares the attributes of two Phi nodes. */
-static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Phi(ir_node *a, ir_node *b) {
return get_irn_phi_attr (a) != get_irn_phi_attr (b);
-}
+} /* node_cmp_attr_Phi */
+
+/** Compares the attributes of two Conv nodes. */
+static int node_cmp_attr_Conv(ir_node *a, ir_node *b) {
+ return get_Conv_strict(a) != get_Conv_strict(b);
+} /* node_cmp_attr_Conv */
/** Compares the attributes of two Cast nodes. */
-static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Cast(ir_node *a, ir_node *b) {
return get_Cast_type(a) != get_Cast_type(b);
-}
+} /* node_cmp_attr_Cast */
/** Compares the attributes of two Load nodes. */
-static int node_cmp_attr_Load(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Load(ir_node *a, ir_node *b) {
if (get_Load_volatility(a) == volatility_is_volatile ||
get_Load_volatility(b) == volatility_is_volatile)
/* NEVER do CSE on volatile Loads */
return 1;
return get_Load_mode(a) != get_Load_mode(b);
-}
+} /* node_cmp_attr_Load */
/** Compares the attributes of two Store nodes. */
-static int node_cmp_attr_Store(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Store(ir_node *a, ir_node *b) {
/* NEVER do CSE on volatile Stores */
return (get_Store_volatility(a) == volatility_is_volatile ||
get_Store_volatility(b) == volatility_is_volatile);
-}
+} /* node_cmp_attr_Store */
/** Compares the attributes of two Confirm nodes. */
-static int node_cmp_attr_Confirm(ir_node *a, ir_node *b)
-{
+static int node_cmp_attr_Confirm(ir_node *a, ir_node *b) {
return (get_Confirm_cmp(a) != get_Confirm_cmp(b));
-}
+} /* node_cmp_attr_Confirm */
/**
- * set the default node attribute compare operation
+ * Set the default node attribute compare operation for an ir_op_ops.
+ *
+ * @param code the opcode for the default operation
+ * @param ops the operations initialized
+ *
+ * @return
+ * The operations.
*/
-static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
+static ir_op_ops *firm_set_default_node_cmp_attr(opcode code, ir_op_ops *ops)
{
-#define CASE(a) \
- case iro_##a: \
- op->node_cmp_attr = node_cmp_attr_##a; \
+#define CASE(a) \
+ case iro_##a: \
+ ops->node_cmp_attr = node_cmp_attr_##a; \
break
- switch (op->code) {
+ switch (code) {
CASE(Const);
CASE(Proj);
CASE(Filter);
CASE(Call);
CASE(Sel);
CASE(Phi);
+ CASE(Conv);
CASE(Cast);
CASE(Load);
CASE(Store);
CASE(Confirm);
default:
- op->node_cmp_attr = NULL;
+ /* leave NULL */;
}
- return op;
+ return ops;
#undef CASE
-}
+} /* firm_set_default_node_cmp_attr */
-/**
+/*
* Compare function for two nodes in the hash table. Gets two
* nodes as parameters. Returns 0 if the nodes are a cse.
*/
-static int
-vt_cmp (const void *elt, const void *key)
+int identities_cmp(const void *elt, const void *key)
{
ir_node *a, *b;
int i, irn_arity_a;
* here, we already now that the nodes are identical except their
* attributes
*/
- if (a->op->node_cmp_attr)
- return a->op->node_cmp_attr(a, b);
+ if (a->op->ops.node_cmp_attr)
+ return a->op->ops.node_cmp_attr(a, b);
return 0;
-}
+} /* identities_cmp */
/*
* Calculate a hash value of a node.
*/
-unsigned
-ir_node_hash (ir_node *node)
+unsigned ir_node_hash(ir_node *node)
{
unsigned h;
int i, irn_arity;
h = 9*h + HASH_PTR(get_irn_mode(node));
} else if (node->op == op_SymConst) {
/* special value for const, as they only differ in their symbol. */
- h = HASH_PTR(node->attr.i.sym.type_p);
+ h = HASH_PTR(node->attr.symc.sym.type_p);
h = 9*h + HASH_PTR(get_irn_mode(node));
} else {
h = irn_arity = get_irn_intra_arity(node);
/* consider all in nodes... except the block if not a control flow. */
- for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
+ for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) {
h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
}
}
return h;
-}
+} /* ir_node_hash */
-pset *
-new_identities(void) {
- return new_pset(vt_cmp, N_IR_NODES);
-}
+pset *new_identities(void) {
+ return new_pset(identities_cmp, N_IR_NODES);
+} /* new_identities */
-void
-del_identities(pset *value_table) {
+void del_identities(pset *value_table) {
del_pset(value_table);
-}
+} /* del_identities */
/**
* Return the canonical node computing the same value as n.
* nodes are extremely time critical because of their frequent use in
* constant string arrays.
*/
-static INLINE ir_node *
-identify (pset *value_table, ir_node *n)
+static INLINE ir_node *identify(pset *value_table, ir_node *n)
{
ir_node *o = NULL;
ir_node *r = get_binop_right(n);
/* for commutative operators perform a OP b == b OP a */
- if (l > r) {
+ if (get_irn_idx(l) > get_irn_idx(r)) {
set_binop_left(n, r);
set_binop_right(n, l);
}
}
}
- o = pset_find (value_table, n, ir_node_hash (n));
+ o = pset_find(value_table, n, ir_node_hash(n));
if (!o) return n;
DBG_OPT_CSE(n, o);
return o;
-}
+} /* identify */
/**
* During construction we set the op_pin_state_pinned flag in the graph right when the
* optimization is performed. The flag turning on procedure global cse could
* be changed between two allocations. This way we are safe.
*/
-static INLINE ir_node *
-identify_cons (pset *value_table, ir_node *n) {
+static INLINE ir_node *identify_cons(pset *value_table, ir_node *n) {
ir_node *old = n;
n = identify(value_table, n);
if (get_irn_n(old, -1) != get_irn_n(n, -1))
set_irg_pinned(current_ir_graph, op_pin_state_floats);
return n;
-}
+} /* identify_cons */
-/**
+/*
* Return the canonical node computing the same value as n.
* Looks up the node in a hash table, enters it in the table
* if it isn't there yet.
*/
-static ir_node *
-identify_remember (pset *value_table, ir_node *n)
+ir_node *identify_remember(pset *value_table, ir_node *n)
{
ir_node *o = NULL;
}
return o;
-}
+} /* identify_remember */
-void
-add_identities (pset *value_table, ir_node *node) {
- if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
- identify_remember (value_table, node);
-}
+/* Add a node to the identities value table. */
+void add_identities(pset *value_table, ir_node *node) {
+ if (get_opt_cse() && is_no_Block(node))
+ identify_remember(value_table, node);
+} /* add_identities */
+
+/* Visit each node in the value table of a graph. */
+void visit_all_identities(ir_graph *irg, irg_walk_func visit, void *env) {
+ ir_node *node;
+ ir_graph *rem = current_ir_graph;
+
+ current_ir_graph = irg;
+ foreach_pset(irg->value_table, node)
+ visit(node, env);
+ current_ir_graph = rem;
+} /* visit_all_identities */
/**
- * garbage in, garbage out. If a node has a dead input, i.e., the
+ * Garbage in, garbage out. If a node has a dead input, i.e., the
* Bad node is input to the node, return the Bad node.
*/
-static INLINE ir_node *
-gigo (ir_node *node)
+static INLINE ir_node *gigo(ir_node *node)
{
int i, irn_arity;
ir_op *op = get_irn_op(node);
if (is_Block(block)) {
irn_arity = get_irn_arity(block);
for (i = 0; i < irn_arity; i++) {
- if (!is_Bad(get_irn_n(block, i))) break;
+ if (!is_Bad(get_irn_n(block, i)))
+ break;
}
if (i == irn_arity) return new_Bad();
}
/* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
blocks predecessors is dead. */
- if ( op != op_Block && op != op_Phi && op != op_Tuple) {
+ if (op != op_Block && op != op_Phi && op != op_Tuple) {
irn_arity = get_irn_arity(node);
/*
return new_Bad();
for (i = 0; i < irn_arity; i++) {
- if (is_Bad(get_irn_n(node, i))) {
+ ir_node *pred = get_irn_n(node, i);
+
+ if (is_Bad(pred))
return new_Bad();
- }
+#if 0
+ /* Propagating Unknowns here seems to be a bad idea, because
+ sometimes we need a node as a input and did not want that
+ it kills it's user.
+ However, it might be useful to move this into a later phase
+ (if you think that optimizing such code is useful). */
+ if (is_Unknown(pred) && mode_is_data(get_irn_mode(node)))
+ return new_Unknown(get_irn_mode(node));
+#endif
}
}
#if 0
}
#endif
return node;
-}
-
+} /* gigo */
/**
* These optimizations deallocate nodes from the obstack.
* It can only be called if it is guaranteed that no other nodes
* reference this one, i.e., right after construction of a node.
+ *
+ * current_ir_graph must be set to the graph of the node!
*/
-ir_node *
-optimize_node(ir_node *n)
+ir_node *optimize_node(ir_node *n)
{
tarval *tv;
ir_node *oldn = n;
tv = computed_value(n);
if (tv != tarval_bad) {
ir_node *nw;
- type *old_tp = get_irn_type(n);
+ ir_type *old_tp = get_irn_type(n);
int i, arity = get_irn_arity(n);
int node_size;
edges_node_deleted(n, current_ir_graph);
/* evaluation was successful -- replace the node. */
- obstack_free(current_ir_graph->obst, n);
+ irg_kill_node(current_ir_graph, n);
nw = new_Const(get_tarval_mode (tv), tv);
if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
(iro == iro_Id) ||
(iro == iro_Proj) ||
(iro == iro_Block) ) /* Flags tested local. */
- n = equivalent_node (n);
+ n = equivalent_node(n);
optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
* subexpressions within a block.
*/
if (get_opt_cse())
- n = identify_cons (current_ir_graph->value_table, n);
+ n = identify_cons(current_ir_graph->value_table, n);
if (n != oldn) {
edges_node_deleted(oldn, current_ir_graph);
/* We found an existing, better node, so we can deallocate the old node. */
- obstack_free (current_ir_graph->obst, oldn);
-
+ irg_kill_node(current_ir_graph, oldn);
return n;
}
iro = get_irn_opcode(n);
if (get_opt_constant_folding() ||
(iro == iro_Cond) ||
- (iro == iro_Proj) ||
- (iro == iro_Sel)) /* Flags tested local. */
- n = transform_node (n);
+ (iro == iro_Proj)) /* Flags tested local. */
+ n = transform_node(n);
/* Remove nodes with dead (Bad) input.
Run always for transformation induced Bads. */
/* Now we have a legal, useful node. Enter it in hash table for CSE */
if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
- n = identify_remember (current_ir_graph->value_table, n);
+ n = identify_remember(current_ir_graph->value_table, n);
}
return n;
-}
+} /* optimize_node */
/**
* nodes lying on the obstack. Remove these by a dead node elimination,
* i.e., a copying garbage collection.
*/
-ir_node *
-optimize_in_place_2 (ir_node *n)
+ir_node *optimize_in_place_2(ir_node *n)
{
tarval *tv;
ir_node *oldn = n;
tv = computed_value(n);
if (tv != tarval_bad) {
/* evaluation was successful -- replace the node. */
- type *old_tp = get_irn_type(n);
+ ir_type *old_tp = get_irn_type(n);
int i, arity = get_irn_arity(n);
/*
iro = get_irn_opcode(n);
if (get_opt_constant_folding() ||
(iro == iro_Cond) ||
- (iro == iro_Proj) ||
- (iro == iro_Sel)) /* Flags tested local. */
+ (iro == iro_Proj)) /* Flags tested local. */
n = transform_node(n);
/* Remove nodes with dead (Bad) input.
n = identify_remember(current_ir_graph->value_table, n);
return n;
-}
+} /* optimize_in_place_2 */
/**
* Wrapper for external use, set proper status bits after optimization.
*/
-ir_node *
-optimize_in_place (ir_node *n)
+ir_node *optimize_in_place(ir_node *n)
{
/* Handle graph state */
assert(get_irg_phase_state(current_ir_graph) != phase_building);
if (get_irg_outs_state(current_ir_graph) == outs_consistent)
set_irg_outs_inconsistent(current_ir_graph);
- /* Maybe we could also test whether optimizing the node can
+ /* FIXME: Maybe we could also test whether optimizing the node can
change the control graph. */
- if (get_irg_dom_state(current_ir_graph) == dom_consistent)
- set_irg_dom_inconsistent(current_ir_graph);
+ set_irg_doms_inconsistent(current_ir_graph);
return optimize_in_place_2 (n);
-}
+} /* optimize_in_place */
-/**
- * set the default ir op operations
+/*
+ * Sets the default operation for an ir_ops.
*/
-ir_op *firm_set_default_operations(ir_op *op)
+ir_op_ops *firm_set_default_operations(opcode code, ir_op_ops *ops)
{
- op = firm_set_default_computed_value(op);
- op = firm_set_default_equivalent_node(op);
- op = firm_set_default_transform_node(op);
- op = firm_set_default_node_cmp_attr(op);
- op = firm_set_default_get_type(op);
+ ops = firm_set_default_computed_value(code, ops);
+ ops = firm_set_default_equivalent_node(code, ops);
+ ops = firm_set_default_transform_node(code, ops);
+ ops = firm_set_default_node_cmp_attr(code, ops);
+ ops = firm_set_default_get_type(code, ops);
+ ops = firm_set_default_get_type_attr(code, ops);
+ ops = firm_set_default_get_entity_attr(code, ops);
- return op;
-}
+ return ops;
+} /* firm_set_default_operations */