X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firopt.c;h=dbcbe6c76978ea473197321ecd73a53b14b92092;hb=8399216d8aebc713bbda04b6e3e250a1d52b20bf;hp=03ff12dbdc119b398e13ff66f6c471efe36f81b1;hpb=f8ebd04aadcde3b2b98a43f695698d1de5388ebc;p=libfirm diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c index 03ff12dbd..dbcbe6c76 100644 --- a/ir/ir/iropt.c +++ b/ir/ir/iropt.c @@ -11,7 +11,17 @@ */ #ifdef HAVE_CONFIG_H -# include +# include "config.h" +#endif + +#ifdef HAVE_ALLOCA_H +#include +#endif +#ifdef HAVE_MALLOC_H +#include +#endif +#ifdef HAVE_STRING_H +#include #endif # include "irnode_t.h" @@ -27,6 +37,7 @@ # include "irflag_t.h" # include "firmstat.h" # include "irarch.h" +# include "hashptr.h" /* Make types visible to allow most efficient access */ # include "entity_t.h" @@ -90,7 +101,7 @@ static tarval *computed_value_Sub(ir_node *n) tarval *tb; /* a - a */ - if (a == b) + if (a == b && !is_Bad(a)) return get_tarval_null(get_irn_mode(n)); ta = value_of(a); @@ -496,6 +507,26 @@ static tarval *computed_value_Proj(ir_node *n) return tarval_bad; } +/** + * 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) +{ + ir_node *sel = get_Mux_sel(n); + tarval *ts = value_of(sel); + + if (ts == get_tarval_b_true()) { + ir_node *v = get_Mux_true(n); + return value_of(v); + } + else if (ts == get_tarval_b_false()) { + ir_node *v = get_Mux_false(n); + return value_of(v); + } + return tarval_bad; +} + /** * If the parameter n can be computed, return its value, else tarval_bad. * Performs constant folding. @@ -540,6 +571,7 @@ static ir_op *firm_set_default_computed_value(ir_op *op) CASE(Rot); CASE(Conv); CASE(Proj); + CASE(Mux); default: op->computed_value = NULL; } @@ -586,7 +618,7 @@ static ir_node *equivalent_node_Block(ir_node *n) ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0)); if (predblock == oldn) { /* Jmp jumps into the block it is in -- deal self cycle. */ - n = new_Bad(); + n = set_Block_dead(n); DBG_OPT_DEAD(oldn, n); } else if (get_opt_control_flow_straightening()) { n = predblock; @@ -598,7 +630,7 @@ static ir_node *equivalent_node_Block(ir_node *n) ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0)); if (predblock == oldn) { /* Jmp jumps into the block it is in -- deal self cycle. */ - n = new_Bad(); + n = set_Block_dead(n); DBG_OPT_DEAD(oldn, n); } } @@ -622,15 +654,27 @@ static ir_node *equivalent_node_Block(ir_node *n) } else if (get_opt_unreachable_code() && (n != current_ir_graph->start_block) && (n != current_ir_graph->end_block) ) { - int i; + int i, n_cfg = get_Block_n_cfgpreds(n); + /* 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 elimination */ - for (i = 0; i < get_Block_n_cfgpreds(n); i++) { - if (!is_Bad(get_Block_cfgpred(n, i))) break; + for (i = 0; i < n_cfg; i++) { + ir_node *pred = get_Block_cfgpred(n, i); + ir_node *pred_blk; + + if (is_Bad(pred)) continue; + pred_blk = get_nodes_block(pred); + + if (is_Block_dead(pred_blk)) continue; + + if (pred_blk != n) { + /* really found a living input */ + break; + } } - if (i == get_Block_n_cfgpreds(n)) - n = new_Bad(); + if (i == n_cfg) + n = set_Block_dead(n); } return n; @@ -644,7 +688,7 @@ static ir_node *equivalent_node_Jmp(ir_node *n) { /* GL: Why not same for op_Raise?? */ /* unreachable code elimination */ - if (is_Bad(get_nodes_block(n))) + if (is_Block_dead(get_nodes_block(n))) n = new_Bad(); return n; @@ -877,12 +921,12 @@ static ir_node *equivalent_node_Conv(ir_node *n) if (n_mode == b_mode) { if (n_mode == mode_b) { n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ - DBG_OPT_ALGSIM1(oldn, a, b, n); + DBG_OPT_ALGSIM1(oldn, a, b, n); } else if (mode_is_int(n_mode) || mode_is_character(n_mode)) { if (smaller_mode(b_mode, a_mode)){ n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ - DBG_OPT_ALGSIM1(oldn, a, b, n); + DBG_OPT_ALGSIM1(oldn, a, b, n); } } } @@ -890,6 +934,10 @@ static ir_node *equivalent_node_Conv(ir_node *n) return n; } +/** + * A Cast may be removed if the type of the previous node + * is already to type of the Cast. + */ static ir_node *equivalent_node_Cast(ir_node *n) { ir_node *pred = get_Cast_op(n); if (get_irn_type(pred) == get_Cast_type(n)) @@ -897,14 +945,14 @@ static ir_node *equivalent_node_Cast(ir_node *n) { return n; } +/* 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) { - /* 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. - */ int i, n_preds; ir_node *oldn = n; @@ -919,7 +967,7 @@ static ir_node *equivalent_node_Phi(ir_node *n) block = get_nodes_block(n); /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!! assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */ - if ((is_Bad(block)) || /* Control dead */ + 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. */ @@ -1010,7 +1058,7 @@ static ir_node *equivalent_node_Proj(ir_node *n) n = new_Bad(); } } else if (get_irn_mode(n) == mode_X && - is_Bad(get_nodes_block(n))) { + is_Block_dead(get_nodes_block(n))) { /* Remove dead control flow -- early gigo. */ n = new_Bad(); } @@ -1029,6 +1077,22 @@ static ir_node *equivalent_node_Id(ir_node *n) return n; } +/** + * optimize a Mux + */ +static ir_node *equivalent_node_Mux(ir_node *n) +{ + ir_node *sel = get_Mux_sel(n); + tarval *ts = value_of(sel); + + if (ts == get_tarval_b_true()) + return get_Mux_true(n); + else if (ts == get_tarval_b_false()) + return get_Mux_false(n); + + return n; +} + /** * 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 @@ -1077,6 +1141,7 @@ static ir_op *firm_set_default_equivalent_node(ir_op *op) CASE(Phi); CASE(Proj); CASE(Id); + CASE(Mux); default: op->equivalent_node = NULL; } @@ -1118,6 +1183,71 @@ optimize_preds(ir_node *n) { } /* end switch */ } +/** + * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and + * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible. + */ +static ir_node *transform_node_AddSub(ir_node *n) +{ + ir_mode *mode = get_irn_mode(n); + + if (mode_is_reference(mode)) { + ir_node *left = get_binop_left(n); + ir_node *right = get_binop_right(n); + int ref_bits = get_mode_size_bits(mode); + + if (get_irn_op(left) == op_Conv) { + ir_mode *mode = get_irn_mode(left); + int bits = get_mode_size_bits(mode); + + if (ref_bits == bits && + mode_is_int(mode) && + get_mode_arithmetic(mode) == irma_twos_complement) { + ir_node *pre = get_Conv_op(left); + ir_mode *pre_mode = get_irn_mode(pre); + + if (mode_is_int(pre_mode) && + get_mode_size_bits(pre_mode) == bits && + get_mode_arithmetic(pre_mode) == irma_twos_complement) { + /* ok, this conv just changes to sign, moreover the calculation + * is done with same number of bits as our address mode, so + * we can ignore the conv as address calculation can be viewed + * as either signed or unsigned + */ + set_binop_left(n, pre); + } + } + } + + if (get_irn_op(right) == op_Conv) { + ir_mode *mode = get_irn_mode(right); + int bits = get_mode_size_bits(mode); + + if (ref_bits == bits && + mode_is_int(mode) && + get_mode_arithmetic(mode) == irma_twos_complement) { + ir_node *pre = get_Conv_op(right); + ir_mode *pre_mode = get_irn_mode(pre); + + if (mode_is_int(pre_mode) && + get_mode_size_bits(pre_mode) == bits && + get_mode_arithmetic(pre_mode) == irma_twos_complement) { + /* ok, this conv just changes to sign, moreover the calculation + * is done with same number of bits as our address mode, so + * we can ignore the conv as address calculation can be viewed + * as either signed or unsigned + */ + set_binop_right(n, pre); + } + } + } + } + return n; +} + +#define transform_node_Add transform_node_AddSub +#define transform_node_Sub transform_node_AddSub + /** Do architecture dependend optimizations on Mul nodes */ static ir_node *transform_node_Mul(ir_node *n) { return arch_dep_replace_mul_with_shifts(n); @@ -1276,6 +1406,9 @@ static ir_node *transform_node_Cond(ir_node *n) return n; } +/** + * Transform an Eor. + */ static ir_node *transform_node_Eor(ir_node *n) { ir_node *a = get_Eor_left(n); @@ -1325,10 +1458,10 @@ static ir_node *transform_node_Cast(ir_node *n) { if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) { n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred), - get_Const_tarval(pred), tp); + get_Const_tarval(pred), tp); } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) { n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred), - get_SymConst_kind(pred), tp); + get_SymConst_kind(pred), tp); } return n; } @@ -1362,13 +1495,11 @@ static ir_node *transform_node_Proj(ir_node *proj) if (proj_nr == pn_Div_X_except) { /* we found an exception handler, remove it */ return new_Bad(); - } - else { - /* the memory Proj can be removed */ + } else { + /* the memory Proj can be removed */ ir_node *res = get_Div_mem(n); set_Div_mem(n, get_irg_no_mem(current_ir_graph)); - - if (proj_nr == pn_Div_M) + if (proj_nr == pn_Div_M) return res; } } @@ -1386,13 +1517,12 @@ static ir_node *transform_node_Proj(ir_node *proj) if (proj_nr == pn_Mod_X_except) { /* we found an exception handler, remove it */ return new_Bad(); - } - else { - /* the memory Proj can be removed */ + } else { + /* the memory Proj can be removed */ ir_node *res = get_Mod_mem(n); set_Mod_mem(n, get_irg_no_mem(current_ir_graph)); if (proj_nr == pn_Mod_M) - return res; + return res; } } break; @@ -1411,11 +1541,11 @@ static ir_node *transform_node_Proj(ir_node *proj) return new_Bad(); } else { - /* the memory Proj can be removed */ + /* the memory Proj can be removed */ ir_node *res = get_DivMod_mem(n); set_DivMod_mem(n, get_irg_no_mem(current_ir_graph)); if (proj_nr == pn_DivMod_M) - return res; + return res; } } break; @@ -1639,6 +1769,8 @@ static ir_op *firm_set_default_transform_node(ir_op *op) break switch (op->code) { + CASE(Add); + CASE(Sub); CASE(Mul); CASE(Div); CASE(Mod); @@ -1831,8 +1963,6 @@ vt_cmp (const void *elt, const void *key) return 0; } -#define ADDR_TO_VAL(p) (((unsigned)(p)) >> 3) - /* * Calculate a hash value of a node. */ @@ -1844,12 +1974,12 @@ ir_node_hash (ir_node *node) if (node->op == op_Const) { /* special value for const, as they only differ in their tarval. */ - h = ADDR_TO_VAL(node->attr.con.tv); - h = 9*h + ADDR_TO_VAL(get_irn_mode(node)); + h = HASH_PTR(node->attr.con.tv); + 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 = ADDR_TO_VAL(node->attr.i.sym.type_p); - h = 9*h + ADDR_TO_VAL(get_irn_mode(node)); + h = HASH_PTR(node->attr.i.sym.type_p); + h = 9*h + HASH_PTR(get_irn_mode(node)); } else { /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */ @@ -1857,13 +1987,13 @@ ir_node_hash (ir_node *node) /* consider all in nodes... except the block if not a control flow. */ for (i = is_cfop(node) ? -1 : 0; i < irn_arity; i++) { - h = 9*h + ADDR_TO_VAL(get_irn_intra_n(node, i)); + h = 9*h + HASH_PTR(get_irn_intra_n(node, i)); } /* ...mode,... */ - h = 9*h + ADDR_TO_VAL(get_irn_mode(node)); + h = 9*h + HASH_PTR(get_irn_mode(node)); /* ...and code */ - h = 9*h + ADDR_TO_VAL(get_irn_op(node)); + h = 9*h + HASH_PTR(get_irn_op(node)); } return h; @@ -1986,6 +2116,7 @@ gigo (ir_node *node) if (get_irn_mode(node) == mode_X) { ir_node *block = get_nodes_block(node); if (op == op_End) return node; /* Don't optimize End, may have Bads. */ + if (get_irn_op(block) == op_Block && get_Block_matured(block)) { irn_arity = get_irn_arity(block); for (i = 0; i < irn_arity; i++) { @@ -1999,7 +2130,11 @@ gigo (ir_node *node) blocks predecessors is dead. */ if ( op != op_Block && op != op_Phi && op != op_Tuple) { irn_arity = get_irn_arity(node); - for (i = -1; i < irn_arity; i++) { + + if (is_Block_dead(get_nodes_block(node))) + return new_Bad(); + + for (i = 0; i < irn_arity; i++) { if (is_Bad(get_irn_n(node, i))) { return new_Bad(); } @@ -2059,16 +2194,16 @@ optimize_node (ir_node *n) oldn = alloca(node_size); memcpy(oldn, n, node_size); - CLONE_ARR_A(ir_node *, oldn->in, n->in); + CLONE_ARR_A(ir_node *, oldn->in, n->in); - /* ARG, copy the in array, we need it for statistics */ - memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0])); + /* ARG, copy the in array, we need it for statistics */ + memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0])); /* evaluation was successful -- replace the node. */ obstack_free (current_ir_graph->obst, n); n = new_Const (get_tarval_mode (tv), tv); - if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv)) - set_Const_type(n, old_tp); + if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv)) + set_Const_type(n, old_tp); DBG_OPT_CSTEVAL(oldn, n); return n; } @@ -2159,8 +2294,8 @@ optimize_in_place_2 (ir_node *n) /* evaluation was successful -- replace the node. */ n = new_Const (get_tarval_mode (tv), tv); - if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv)) - set_Const_type(n, old_tp); + if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv)) + set_Const_type(n, old_tp); DBG_OPT_CSTEVAL(oldn, n); return n;