X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fir%2Firopt.c;h=481f9cd661191f007cb8888de66c0bb26ad13a8e;hb=357886575cb0becb5bd9be376fde49b57edd5385;hp=ab5b63ac48694460bccd30bac46cfb6ea59f83ad;hpb=8c1f62ae9c96c62a4192ca022c07889c27ca0c0e;p=libfirm diff --git a/ir/ir/iropt.c b/ir/ir/iropt.c index ab5b63ac4..481f9cd66 100644 --- a/ir/ir/iropt.c +++ b/ir/ir/iropt.c @@ -327,6 +327,28 @@ static ir_tarval *computed_value_Not(const ir_node *n) return tarval_bad; } /* computed_value_Not */ +/** + * Tests wether a shift shifts more bits than available in the mode + */ +static bool is_oversize_shift(const ir_node *n) +{ + ir_node *count = get_binop_right(n); + ir_mode *mode = get_irn_mode(n); + ir_tarval *tv = value_of(count); + long modulo_shift; + long shiftval; + if (tv == tarval_bad) + return false; + if (!tarval_is_long(tv)) + return false; + shiftval = get_tarval_long(tv); + modulo_shift = get_mode_modulo_shift(mode); + if (shiftval < 0 || (modulo_shift > 0 && shiftval >= modulo_shift)) + return false; + + return shiftval >= (long)get_mode_size_bits(mode); +} + /** * Return the value of a Shl. */ @@ -341,6 +363,10 @@ static ir_tarval *computed_value_Shl(const ir_node *n) if ((ta != tarval_bad) && (tb != tarval_bad)) { return tarval_shl(ta, tb); } + + if (is_oversize_shift(n)) + return get_mode_null(get_irn_mode(n)); + return tarval_bad; } /* computed_value_Shl */ @@ -358,6 +384,9 @@ static ir_tarval *computed_value_Shr(const ir_node *n) if ((ta != tarval_bad) && (tb != tarval_bad)) { return tarval_shr(ta, tb); } + if (is_oversize_shift(n)) + return get_mode_null(get_irn_mode(n)); + return tarval_bad; } /* computed_value_Shr */ @@ -395,17 +424,52 @@ static ir_tarval *computed_value_Rotl(const ir_node *n) return tarval_bad; } /* computed_value_Rotl */ +bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode) +{ + ir_mode *mode = get_irn_mode(node); + if (get_mode_arithmetic(mode) != irma_twos_complement + || get_mode_arithmetic(dest_mode) != irma_twos_complement) + return false; + + if (is_Shl(node)) { + ir_node *count = get_Shl_right(node); + if (is_Const(count)) { + ir_tarval *tv = get_Const_tarval(count); + if (tarval_is_long(tv)) { + long shiftval = get_tarval_long(tv); + long destbits = get_mode_size_bits(dest_mode); + if (shiftval >= destbits + && shiftval < (long)get_mode_modulo_shift(mode)) + return true; + } + } + } + if (is_And(node)) { + ir_node *right = get_And_right(node); + if (is_Const(right)) { + ir_tarval *tv = get_Const_tarval(right); + ir_tarval *conved = tarval_convert_to(tv, dest_mode); + return tarval_is_null(conved); + } + } + return false; +} + /** * Return the value of a Conv. */ static ir_tarval *computed_value_Conv(const ir_node *n) { - ir_node *a = get_Conv_op(n); - ir_tarval *ta = value_of(a); + ir_node *a = get_Conv_op(n); + ir_tarval *ta = value_of(a); + ir_mode *mode = get_irn_mode(n); if (ta != tarval_bad) return tarval_convert_to(ta, get_irn_mode(n)); + if (ir_zero_when_converted(a, mode)) + return get_mode_null(mode); + return tarval_bad; } /* computed_value_Conv */ @@ -661,141 +725,6 @@ static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops #undef CASE } /* firm_set_default_computed_value */ -/** - * Returns a equivalent block for another block. - * If the block has only one predecessor, this is - * the equivalent one. If the only predecessor of a block is - * the block itself, this is a dead block. - * - * If both predecessors of a block are the branches of a binary - * Cond, the equivalent block is Cond's block. - * - * If all predecessors of a block are bad or lies in a dead - * block, the current block is dead as well. - * - * Note, that blocks are NEVER turned into Bad's, instead - * the dead_block flag is set. So, never test for is_Bad(block), - * always use is_dead_Block(block). - */ -static ir_node *equivalent_node_Block(ir_node *n) -{ - ir_node *oldn = n; - int n_preds; - ir_graph *irg; - - /* don't optimize dead or labeled blocks */ - if (is_Block_dead(n) || has_Block_entity(n)) - return n; - - n_preds = get_Block_n_cfgpreds(n); - - /* The Block constructor does not call optimize, but mature_immBlock() - calls the optimization. */ - assert(get_Block_matured(n)); - - irg = get_irn_irg(n); - - /* Straightening: a single entry Block following a single exit Block - can be merged, if it is not the Start block. */ - /* !!! Beware, all Phi-nodes of n must have been optimized away. - This should be true, as the block is matured before optimize is called. - But what about Phi-cycles with the Phi0/Id that could not be resolved? - Remaining Phi nodes are just Ids. */ - if (n_preds == 1) { - ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0)); - - if (is_Jmp(pred)) { - ir_node *predblock = get_nodes_block(pred); - if (predblock == oldn) { - /* Jmp jumps into the block it is in -- deal self cycle. */ - n = set_Block_dead(n); - DBG_OPT_DEAD_BLOCK(oldn, n); - } else { - n = predblock; - DBG_OPT_STG(oldn, n); - } - } else if (is_Cond(pred)) { - ir_node *predblock = get_nodes_block(pred); - if (predblock == oldn) { - /* Jmp jumps into the block it is in -- deal self cycle. */ - n = set_Block_dead(n); - DBG_OPT_DEAD_BLOCK(oldn, n); - } - } - } else if (n_preds == 2) { - /* Test whether Cond jumps twice to this block - * The more general case which more than 2 predecessors is handles - * in optimize_cf(), we handle only this special case for speed here. - */ - ir_node *a = get_Block_cfgpred(n, 0); - ir_node *b = get_Block_cfgpred(n, 1); - - if (is_Proj(a) && is_Proj(b)) { - ir_node *cond = get_Proj_pred(a); - - if (cond == get_Proj_pred(b) && is_Cond(cond) && - get_irn_mode(get_Cond_selector(cond)) == 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(cond); - DBG_OPT_IFSIM1(oldn, a, b, n); - } - } - } else if (get_opt_unreachable_code() && - (n != get_irg_start_block(irg)) && - (n != get_irg_end_block(irg))) { - int i; - - /* If all inputs are dead, this block is dead too, except if it is - the start or end block. This is one step of unreachable code - elimination */ - for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) { - ir_node *pred = get_Block_cfgpred(n, i); - ir_node *pred_blk; - - if (is_Bad(pred)) continue; - pred_blk = get_nodes_block(skip_Proj(pred)); - - if (is_Block_dead(pred_blk)) continue; - - if (pred_blk != n) { - /* really found a living input */ - break; - } - } - 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 dead. - */ -static ir_node *equivalent_node_Jmp(ir_node *n) -{ - ir_node *oldn = n; - - /* unreachable code elimination */ - if (is_Block_dead(get_nodes_block(n))) { - ir_graph *irg = get_irn_irg(n); - n = get_irg_bad(irg); - DBG_OPT_DEAD_BLOCK(oldn, n); - } - 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, * so a op 0 = 0 op a = a. @@ -1309,51 +1238,26 @@ static ir_node *equivalent_node_Phi(ir_node *n) n_preds = get_Phi_n_preds(n); block = get_nodes_block(n); - /* Control dead */ - if (is_Block_dead(block)) { - ir_graph *irg = get_irn_irg(n); - return get_irg_bad(irg); - } - if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */ + /* Phi of dead Region without predecessors. */ + if (n_preds == 0) + return n; /* Find first non-self-referencing input */ for (i = 0; i < n_preds; ++i) { first_val = get_Phi_pred(n, i); - if ( (first_val != n) /* not self pointer */ -#if 0 - /* BEWARE: when the if is changed to 1, Phis will ignore their Bad - * predecessors. Then, Phi nodes in unreachable code might be removed, - * causing nodes pointing to themselev (Adds for instance). - * This is really bad and causes endless recursion on several - * code pathes, so we do NOT optimize such code. - * This is not that bad as it sounds, optimize_cf() removes bad control flow - * (and bad Phi predecessors), so live code is optimized later. - */ - && (! is_Bad(get_Block_cfgpred(block, i))) -#endif - ) { /* value not dead */ - break; /* then found first value. */ + /* not self pointer */ + if (first_val != n) { + /* then found first value. */ + break; } } - if (i >= n_preds) { - ir_graph *irg = get_irn_irg(n); - /* A totally Bad or self-referencing Phi (we didn't break the above loop) */ - return get_irg_bad(irg); - } - /* search for rest of inputs, determine if any of these are non-self-referencing */ while (++i < n_preds) { ir_node *scnd_val = get_Phi_pred(n, i); - if ( (scnd_val != n) - && (scnd_val != first_val) -#if 0 - /* see above */ - && (! is_Bad(get_Block_cfgpred(block, i))) -#endif - ) { + if (scnd_val != n && scnd_val != first_val) { break; } } @@ -1366,49 +1270,6 @@ static ir_node *equivalent_node_Phi(ir_node *n) return n; } /* equivalent_node_Phi */ -/** - * Several optimizations: - * - fold Sync-nodes, iff they have only one predecessor except - * themselves. - */ -static ir_node *equivalent_node_Sync(ir_node *n) -{ - int arity = get_Sync_n_preds(n); - int i; - - for (i = 0; i < arity;) { - ir_node *pred = get_Sync_pred(n, i); - int j; - - /* Remove Bad predecessors */ - if (is_Bad(pred)) { - del_Sync_n(n, i); - --arity; - continue; - } - - /* Remove duplicate predecessors */ - for (j = 0;; ++j) { - if (j >= i) { - ++i; - break; - } - if (get_Sync_pred(n, j) == pred) { - del_Sync_n(n, i); - --arity; - break; - } - } - } - - if (arity == 0) { - ir_graph *irg = get_irn_irg(n); - return get_irg_bad(irg); - } - if (arity == 1) return get_Sync_pred(n, 0); - return n; -} /* equivalent_node_Sync */ - /** * Optimize Proj(Tuple). */ @@ -1473,13 +1334,6 @@ static ir_node *equivalent_node_Proj_CopyB(ir_node *proj) proj = get_CopyB_mem(copyb); DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NOP); break; - - case pn_CopyB_X_except: { - ir_graph *irg = get_irn_irg(proj); - DBG_OPT_EXC_REM(proj); - proj = get_irg_bad(irg); - break; - } } } return proj; @@ -1523,12 +1377,6 @@ static ir_node *equivalent_node_Proj_Bound(ir_node *proj) DBG_OPT_EXC_REM(proj); proj = get_Bound_mem(bound); break; - case pn_Bound_X_except: { - ir_graph *irg = get_irn_irg(proj); - DBG_OPT_EXC_REM(proj); - proj = get_irg_bad(irg); - break; - } case pn_Bound_res: proj = idx; DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NOP); @@ -1541,56 +1389,6 @@ static ir_node *equivalent_node_Proj_Bound(ir_node *proj) return proj; } /* equivalent_node_Proj_Bound */ -/** - * Optimize an Exception Proj(Load) with a non-null address. - */ -static ir_node *equivalent_node_Proj_Load(ir_node *proj) -{ - if (get_opt_ldst_only_null_ptr_exceptions()) { - if (get_irn_mode(proj) == mode_X) { - ir_node *load = get_Proj_pred(proj); - - /* get the Load address */ - const ir_node *addr = get_Load_ptr(load); - const ir_node *confirm; - - if (value_not_null(addr, &confirm)) { - if (get_Proj_proj(proj) == pn_Load_X_except) { - ir_graph *irg = get_irn_irg(proj); - DBG_OPT_EXC_REM(proj); - return get_irg_bad(irg); - } - } - } - } - return proj; -} /* equivalent_node_Proj_Load */ - -/** - * Optimize an Exception Proj(Store) with a non-null address. - */ -static ir_node *equivalent_node_Proj_Store(ir_node *proj) -{ - if (get_opt_ldst_only_null_ptr_exceptions()) { - if (get_irn_mode(proj) == mode_X) { - ir_node *store = get_Proj_pred(proj); - - /* get the load/store address */ - const ir_node *addr = get_Store_ptr(store); - const ir_node *confirm; - - if (value_not_null(addr, &confirm)) { - if (get_Proj_proj(proj) == pn_Store_X_except) { - ir_graph *irg = get_irn_irg(proj); - DBG_OPT_EXC_REM(proj); - return get_irg_bad(irg); - } - } - } - } - return proj; -} /* equivalent_node_Proj_Store */ - /** * Does all optimizations on nodes that must be done on its Projs * because of creating new nodes. @@ -1598,14 +1396,6 @@ static ir_node *equivalent_node_Proj_Store(ir_node *proj) static ir_node *equivalent_node_Proj(ir_node *proj) { ir_node *n = get_Proj_pred(proj); - - if (get_irn_mode(proj) == mode_X) { - if (is_Block_dead(get_nodes_block(n))) { - /* Remove dead control flow -- early gigo(). */ - ir_graph *irg = get_irn_irg(proj); - return get_irg_bad(irg); - } - } if (n->op->ops.equivalent_node_Proj) return n->op->ops.equivalent_node_Proj(proj); return proj; @@ -1784,9 +1574,6 @@ static ir_op_ops *firm_set_default_equivalent_node(ir_opcode code, ir_op_ops *op break switch (code) { - CASE(Block); - CASE(Jmp); - CASE(Raise); CASE(Eor); CASE(Add); CASE(Shl); @@ -1801,13 +1588,10 @@ static ir_op_ops *firm_set_default_equivalent_node(ir_opcode code, ir_op_ops *op CASE(And); CASE(Conv); CASE(Phi); - CASE(Sync); CASE_PROJ(Tuple); CASE_PROJ(Div); CASE_PROJ(CopyB); CASE_PROJ(Bound); - CASE_PROJ(Load); - CASE_PROJ(Store); CASE(Proj); CASE(Id); CASE(Mux); @@ -2859,7 +2643,7 @@ make_tuple: turn_into_tuple(n, pn_Div_max); set_Tuple_pred(n, pn_Div_M, mem); set_Tuple_pred(n, pn_Div_X_regular, new_r_Jmp(blk)); - set_Tuple_pred(n, pn_Div_X_except, get_irg_bad(irg)); + set_Tuple_pred(n, pn_Div_X_except, new_r_Bad(irg, mode_X)); set_Tuple_pred(n, pn_Div_res, value); } return n; @@ -2951,7 +2735,7 @@ make_tuple: turn_into_tuple(n, pn_Mod_max); set_Tuple_pred(n, pn_Mod_M, mem); set_Tuple_pred(n, pn_Mod_X_regular, new_r_Jmp(blk)); - set_Tuple_pred(n, pn_Mod_X_except, get_irg_bad(irg)); + set_Tuple_pred(n, pn_Mod_X_except, new_r_Bad(irg, mode_X)); set_Tuple_pred(n, pn_Mod_res, value); } return n; @@ -2984,11 +2768,11 @@ static ir_node *transform_node_Cond(ir_node *n) jmp = new_r_Jmp(blk); turn_into_tuple(n, pn_Cond_max); if (ta == tarval_b_true) { - set_Tuple_pred(n, pn_Cond_false, get_irg_bad(irg)); + set_Tuple_pred(n, pn_Cond_false, new_r_Bad(irg, mode_X)); set_Tuple_pred(n, pn_Cond_true, jmp); } else { set_Tuple_pred(n, pn_Cond_false, jmp); - set_Tuple_pred(n, pn_Cond_true, get_irg_bad(irg)); + set_Tuple_pred(n, pn_Cond_true, new_r_Bad(irg, mode_X)); } /* We might generate an endless loop, so keep it alive. */ add_End_keepalive(get_irg_end(irg), blk); @@ -3107,27 +2891,6 @@ static ir_node *transform_bitwise_distributive(ir_node *n, return n; } -int ir_is_equality_cmp_0(const ir_node *node) -{ - ir_relation relation = get_Cmp_relation(node); - ir_node *left = get_Cmp_left(node); - ir_node *right = get_Cmp_right(node); - ir_mode *mode = get_irn_mode(left); - - /* this probably makes no sense if unordered is involved */ - assert(!mode_is_float(mode)); - - if (!is_Const(right) || !is_Const_null(right)) - return false; - if (relation == ir_relation_equal) - return true; - if (mode_is_signed(mode)) { - return relation == ir_relation_less_greater; - } else { - return relation == ir_relation_greater; - } -} - /** * Create a 0 constant of given mode. */ @@ -3151,33 +2914,35 @@ static ir_node *transform_node_And(ir_node *n) vrp_attr *a_vrp, *b_vrp; if (is_Cmp(a) && is_Cmp(b)) { - ir_node *a_left = get_Cmp_left(a); - ir_node *a_right = get_Cmp_left(a); - ir_node *b_left = get_Cmp_left(b); - ir_node *b_right = get_Cmp_right(b); + ir_node *a_left = get_Cmp_left(a); + ir_node *a_right = get_Cmp_right(a); + ir_node *b_left = get_Cmp_left(b); + ir_node *b_right = get_Cmp_right(b); + ir_relation a_relation = get_Cmp_relation(a); + ir_relation b_relation = get_Cmp_relation(b); /* we can combine the relations of two compares with the same * operands */ if (a_left == b_left && b_left == b_right) { dbg_info *dbgi = get_irn_dbg_info(n); ir_node *block = get_nodes_block(n); - ir_relation a_relation = get_Cmp_relation(a); - ir_relation b_relation = get_Cmp_relation(b); ir_relation new_relation = a_relation & b_relation; return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation); } - /* Cmp(a, 0) and Cmp(b,0) can be optimized to Cmp(a|b, 0) */ - if (ir_is_equality_cmp_0(a) && ir_is_equality_cmp_0(b) - && (get_Cmp_relation(a) & ir_relation_equal) == (get_Cmp_relation(b) & ir_relation_equal)) { - dbg_info *dbgi = get_irn_dbg_info(n); - ir_node *block = get_nodes_block(n); - ir_relation relation = get_Cmp_relation(a); - ir_mode *mode = get_irn_mode(a_left); - ir_node *n_b_left = get_irn_mode(b_left) != mode ? - new_rd_Conv(dbgi, block, b_left, mode) : b_left; - ir_node *or = new_rd_Or(dbgi, block, a_left, n_b_left, mode); - ir_graph *irg = get_irn_irg(n); - ir_node *zero = create_zero_const(irg, mode); - return new_rd_Cmp(dbgi, block, or, zero, relation); + /* Cmp(a==0) and Cmp(b==0) can be optimized to Cmp(a|b==0) */ + if (is_Const(a_right) && is_Const_null(a_right) + && is_Const(b_right) && is_Const_null(b_right) + && a_relation == b_relation && a_relation == ir_relation_equal + && !mode_is_float(get_irn_mode(a_left)) + && !mode_is_float(get_irn_mode(b_left))) { + dbg_info *dbgi = get_irn_dbg_info(n); + ir_node *block = get_nodes_block(n); + ir_mode *mode = get_irn_mode(a_left); + ir_node *n_b_left = get_irn_mode(b_left) != mode ? + new_rd_Conv(dbgi, block, b_left, mode) : b_left; + ir_node *or = new_rd_Or(dbgi, block, a_left, n_b_left, mode); + ir_graph *irg = get_irn_irg(n); + ir_node *zero = create_zero_const(irg, mode); + return new_rd_Cmp(dbgi, block, or, zero, ir_relation_equal); } } @@ -3561,7 +3326,7 @@ static ir_node *transform_node_Proj_Load(ir_node *proj) if (get_Proj_proj(proj) == pn_Load_X_except) { ir_graph *irg = get_irn_irg(proj); DBG_OPT_EXC_REM(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } else { ir_node *blk = get_nodes_block(load); return new_r_Jmp(blk); @@ -3593,7 +3358,7 @@ static ir_node *transform_node_Proj_Store(ir_node *proj) if (get_Proj_proj(proj) == pn_Store_X_except) { ir_graph *irg = get_irn_irg(proj); DBG_OPT_EXC_REM(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } else { ir_node *blk = get_nodes_block(store); return new_r_Jmp(blk); @@ -3635,7 +3400,7 @@ static ir_node *transform_node_Proj_Div(ir_node *proj) ir_graph *irg = get_irn_irg(proj); /* we found an exception handler, remove it */ DBG_OPT_EXC_REM(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } case pn_Div_M: { @@ -3690,7 +3455,7 @@ static ir_node *transform_node_Proj_Mod(ir_node *proj) ir_graph *irg = get_irn_irg(proj); /* we found an exception handler, remove it */ DBG_OPT_EXC_REM(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } case pn_Mod_M: { @@ -3747,7 +3512,7 @@ static ir_node *transform_node_Proj_Cond(ir_node *proj) } else { ir_graph *irg = get_irn_irg(proj); /* this case will NEVER be taken, kill it */ - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } } } else { @@ -3761,19 +3526,19 @@ static ir_node *transform_node_Proj_Cond(ir_node *proj) ir_relation cmp_result = tarval_cmp(b_vrp->range_bottom, tp); ir_relation cmp_result2 = tarval_cmp(b_vrp->range_top, tp); - if ((cmp_result & ir_relation_greater) == cmp_result && (cmp_result2 - & ir_relation_less) == cmp_result2) { + if ((cmp_result & ir_relation_greater) == cmp_result + && (cmp_result2 & ir_relation_less) == cmp_result2) { ir_graph *irg = get_irn_irg(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } } else if (b_vrp->range_type == VRP_ANTIRANGE) { ir_relation cmp_result = tarval_cmp(b_vrp->range_bottom, tp); ir_relation cmp_result2 = tarval_cmp(b_vrp->range_top, tp); - if ((cmp_result & ir_relation_less_equal) == cmp_result && (cmp_result2 - & ir_relation_greater_equal) == cmp_result2) { + if ((cmp_result & ir_relation_less_equal) == cmp_result + && (cmp_result2 & ir_relation_greater_equal) == cmp_result2) { ir_graph *irg = get_irn_irg(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } } @@ -3782,7 +3547,7 @@ static ir_node *transform_node_Proj_Cond(ir_node *proj) b_vrp->bits_set ) == ir_relation_equal)) { ir_graph *irg = get_irn_irg(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } if (!(tarval_cmp( @@ -3792,10 +3557,8 @@ static ir_node *transform_node_Proj_Cond(ir_node *proj) tarval_not(b_vrp->bits_not_set)) == ir_relation_equal)) { ir_graph *irg = get_irn_irg(proj); - return get_irg_bad(irg); + return new_r_Bad(irg, mode_X); } - - } } } @@ -4211,19 +3974,6 @@ static ir_node *transform_node_Cmp(ir_node *n) /* the following reassociations work only for == and != */ if (relation == ir_relation_equal || relation == ir_relation_less_greater) { - -#if 0 /* Might be not that good in general */ - /* a-b == 0 ==> a == b, a-b != 0 ==> a != b */ - if (tarval_is_null(tv) && is_Sub(left)) { - right = get_Sub_right(left); - left = get_Sub_left(left); - - tv = value_of(right); - changed = 1; - DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C); - } -#endif - if (tv != tarval_bad) { /* a-c1 == c2 ==> a == c2+c1, a-c1 != c2 ==> a != c2+c1 */ if (is_Sub(left)) { @@ -4504,10 +4254,12 @@ static ir_node *transform_node_Proj_CopyB(ir_node *proj) DBG_OPT_EXC_REM(proj); proj = new_r_Jmp(get_nodes_block(copyb)); break; - case pn_CopyB_X_except: + case pn_CopyB_X_except: { + ir_graph *irg = get_irn_irg(proj); DBG_OPT_EXC_REM(proj); - proj = get_irg_bad(get_irn_irg(proj)); + proj = new_r_Bad(irg, mode_X); break; + } default: break; } @@ -4555,7 +4307,7 @@ static ir_node *transform_node_Proj_Bound(ir_node *proj) break; case pn_Bound_X_except: DBG_OPT_EXC_REM(proj); - proj = get_irg_bad(get_irn_irg(proj)); + proj = new_r_Bad(get_irn_irg(proj), mode_X); break; case pn_Bound_res: proj = idx; @@ -4585,14 +4337,57 @@ static ir_node *transform_node_Proj(ir_node *proj) return proj; } /* transform_node_Proj */ -/** - * Move Confirms down through Phi nodes. - */ +static bool is_block_unreachable(const ir_node *block) +{ + const ir_graph *irg = get_irn_irg(block); + if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK)) + return false; + return get_Block_dom_depth(block) < 0; +} + +static ir_node *transform_node_Block(ir_node *block) +{ + ir_graph *irg = get_irn_irg(block); + int arity = get_irn_arity(block); + ir_node *bad = NULL; + int i; + + if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK)) + return block; + + for (i = 0; i < arity; ++i) { + ir_node *pred = get_Block_cfgpred(block, i); + ir_node *pred_block = get_nodes_block(pred); + if (!is_Bad(pred) && !is_block_unreachable(pred_block)) + continue; + if (bad == NULL) + bad = new_r_Bad(irg, mode_X); + set_irn_n(block, i, bad); + } + + return block; +} + static ir_node *transform_node_Phi(ir_node *phi) { - int i, n; - ir_mode *mode = get_irn_mode(phi); + int n = get_irn_arity(phi); + ir_mode *mode = get_irn_mode(phi); + ir_node *block = get_nodes_block(phi); + ir_graph *irg = get_irn_irg(phi); + ir_node *bad = NULL; + int i; + + /* Set phi-operands for bad-block inputs to bad */ + for (i = 0; i < n; ++i) { + ir_node *pred = get_Block_cfgpred(block, i); + if (is_Bad(pred) || is_block_unreachable(get_nodes_block(pred))) { + if (bad == NULL) + bad = new_r_Bad(irg, mode); + set_irn_n(phi, i, bad); + } + } + /* Move Confirms down through Phi nodes. */ if (mode_is_reference(mode)) { n = get_irn_arity(phi); @@ -4821,6 +4616,22 @@ static ir_node *transform_node_Or_Rotl(ir_node *irn_or) return n; } /* transform_node_Or_Rotl */ +static bool is_cmp_unequal_zero(const ir_node *node) +{ + ir_relation relation = get_Cmp_relation(node); + ir_node *left = get_Cmp_left(node); + ir_node *right = get_Cmp_right(node); + ir_mode *mode = get_irn_mode(left); + + if (!is_Const(right) || !is_Const_null(right)) + return false; + if (mode_is_signed(mode)) { + return relation == ir_relation_less_greater; + } else { + return relation == ir_relation_greater; + } +} + /** * Transform an Or. */ @@ -4858,6 +4669,20 @@ static ir_node *transform_node_Or(ir_node *n) ir_relation new_relation = a_relation | b_relation; return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation); } + /* Cmp(a!=0) or Cmp(b!=0) => Cmp(a|b != 0) */ + if (is_cmp_unequal_zero(a) && is_cmp_unequal_zero(b) + && !mode_is_float(get_irn_mode(a_left)) + && !mode_is_float(get_irn_mode(b_left))) { + ir_graph *irg = get_irn_irg(n); + dbg_info *dbgi = get_irn_dbg_info(n); + ir_node *block = get_nodes_block(n); + ir_mode *mode = get_irn_mode(a_left); + ir_node *n_b_left = get_irn_mode(b_left) != mode ? + new_rd_Conv(dbgi, block, b_left, mode) : b_left; + ir_node *or = new_rd_Or(dbgi, block, a_left, n_b_left, mode); + ir_node *zero = create_zero_const(irg, mode); + return new_rd_Cmp(dbgi, block, or, zero, ir_relation_less_greater); + } } mode = get_irn_mode(n); @@ -4886,9 +4711,11 @@ static ir_node *transform_node_shift(ir_node *n) { ir_node *left, *right; ir_mode *mode; + ir_mode *count_mode; ir_tarval *tv1, *tv2, *res; ir_node *in[2], *irn, *block; ir_graph *irg; + int modulo_shf; left = get_binop_left(n); @@ -4897,7 +4724,7 @@ static ir_node *transform_node_shift(ir_node *n) return n; right = get_binop_right(n); - tv1 = value_of(right); + tv1 = value_of(right); if (tv1 == tarval_bad) return n; @@ -4905,37 +4732,55 @@ static ir_node *transform_node_shift(ir_node *n) if (tv2 == tarval_bad) return n; - res = tarval_add(tv1, tv2); - mode = get_irn_mode(n); - irg = get_irn_irg(n); + count_mode = get_tarval_mode(tv1); + if (get_tarval_mode(tv2) != count_mode) { + /* TODO: search bigger mode or something and convert... */ + return n; + } - /* beware: a simple replacement works only, if res < modulo shift */ - if (!is_Rotl(n)) { - int modulo_shf = get_mode_modulo_shift(mode); - if (modulo_shf > 0) { - ir_tarval *modulo = new_tarval_from_long(modulo_shf, - get_tarval_mode(res)); + mode = get_irn_mode(n); + modulo_shf = get_mode_modulo_shift(mode); - assert(modulo_shf >= (int) get_mode_size_bits(mode)); + if (modulo_shf > 0) { + ir_tarval *modulo_mask = new_tarval_from_long(modulo_shf-1, count_mode); - /* shifting too much */ - if (!(tarval_cmp(res, modulo) & ir_relation_less)) { - if (is_Shrs(n)) { - ir_node *block = get_nodes_block(n); - dbg_info *dbgi = get_irn_dbg_info(n); - ir_mode *smode = get_irn_mode(right); - ir_node *cnst = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1); - return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode); - } + /* I'm not so sure what happens in one complement... */ + assert(get_mode_arithmetic(count_mode) == irma_twos_complement); + /* modulo shifts should always be a power of 2 (otherwise modulo_mask + * above will be invalid) */ + assert(modulo_shf<=0 || is_po2(modulo_shf)); + + tv1 = tarval_and(tv1, modulo_mask); + tv2 = tarval_and(tv2, modulo_mask); + } + res = tarval_add(tv1, tv2); + irg = get_irn_irg(n); - return new_r_Const(irg, get_mode_null(mode)); + /* beware: a simple replacement works only, if res < modulo shift */ + if (is_Rotl(n)) { + int bits = get_mode_size_bits(mode); + ir_tarval *modulo = new_tarval_from_long(bits, count_mode); + res = tarval_mod(res, modulo); + } else { + long bits = get_mode_size_bits(mode); + ir_tarval *mode_size = new_tarval_from_long(bits, count_mode); + + /* shifting too much */ + if (!(tarval_cmp(res, mode_size) & ir_relation_less)) { + if (is_Shrs(n)) { + ir_node *block = get_nodes_block(n); + dbg_info *dbgi = get_irn_dbg_info(n); + ir_mode *smode = get_irn_mode(right); + ir_node *cnst = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1); + return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode); } + + return new_r_Const(irg, get_mode_null(mode)); } - } else { - res = tarval_mod(res, new_tarval_from_long(get_mode_size_bits(mode), get_tarval_mode(res))); } /* ok, we can replace it */ + assert(modulo_shf >= (int) get_mode_size_bits(mode)); block = get_nodes_block(n); in[0] = get_binop_left(left); @@ -4946,7 +4791,7 @@ static ir_node *transform_node_shift(ir_node *n) DBG_OPT_ALGSIM0(n, irn, FS_OPT_REASSOC_SHIFT); return transform_node(irn); -} /* transform_node_shift */ +} /** * normalisation: (x & c1) >> c2 to (x >> c2) & (c1 >> c2) @@ -5254,6 +5099,16 @@ static ir_node *transform_node_Shrs(ir_node *n) ir_node *b = get_Shrs_right(n); ir_mode *mode = get_irn_mode(n); + if (is_oversize_shift(n)) { + ir_node *block = get_nodes_block(n); + dbg_info *dbgi = get_irn_dbg_info(n); + ir_mode *cmode = get_irn_mode(b); + long val = get_mode_size_bits(cmode)-1; + ir_graph *irg = get_irn_irg(n); + ir_node *cnst = new_r_Const_long(irg, cmode, val); + return new_rd_Shrs(dbgi, block, a, cnst, mode); + } + HANDLE_BINOP_PHI((eval_func) tarval_shrs, a, b, c, mode); n = transform_node_shift(n); @@ -5374,17 +5229,14 @@ static ir_node *transform_node_End(ir_node *n) for (i = j = 0; i < n_keepalives; ++i) { ir_node *ka = get_End_keepalive(n, i); - if (is_Block(ka)) { - if (! is_Block_dead(ka)) { - in[j++] = ka; - } + ir_node *block; + /* no need to keep Bad */ + if (is_Bad(ka)) continue; - } else if (is_irn_pinned_in_irg(ka) && is_Block_dead(get_nodes_block(ka))) { + /* dont keep unreachable code */ + block = is_Block(ka) ? ka : get_nodes_block(ka); + if (is_block_unreachable(block)) continue; - } else if (is_Bad(ka)) { - /* no need to keep Bad */ - continue; - } in[j++] = ka; } if (j != n_keepalives) @@ -5645,6 +5497,24 @@ static ir_node *transform_node_Sync(ir_node *n) int pred_arity; int j; + /* Remove Bad predecessors */ + if (is_Bad(pred)) { + del_Sync_n(n, i); + --arity; + continue; + } + + /* Remove duplicate predecessors */ + for (j = 0; j < i; ++j) { + if (get_Sync_pred(n, j) == pred) { + del_Sync_n(n, i); + --arity; + break; + } + } + if (j < i) + continue; + if (!is_Sync(pred)) { ++i; continue; @@ -5669,11 +5539,78 @@ static ir_node *transform_node_Sync(ir_node *n) } } + if (arity == 0) { + ir_graph *irg = get_irn_irg(n); + return new_r_Bad(irg, mode_M); + } + if (arity == 1) { + return get_Sync_pred(n, 0); + } + /* rehash the sync node */ add_identities(n); + return n; +} + +static ir_node *transform_node_Load(ir_node *n) +{ + /* if our memory predecessor is a load from the same address, then reuse the + * previous result */ + ir_node *mem = get_Load_mem(n); + ir_node *mem_pred; + + if (!is_Proj(mem)) + return n; + /* don't touch volatile loads */ + if (get_Load_volatility(n) == volatility_is_volatile) + return n; + mem_pred = get_Proj_pred(mem); + if (is_Load(mem_pred)) { + ir_node *pred_load = mem_pred; + + /* conservatively compare the 2 loads. TODO: This could be less strict + * with fixup code in some situations (like smaller/bigger modes) */ + if (get_Load_ptr(pred_load) != get_Load_ptr(n)) + return n; + if (get_Load_mode(pred_load) != get_Load_mode(n)) + return n; + /* all combinations of aligned/unaligned pred/n should be fine so we do + * not compare the unaligned attribute */ + { + ir_node *block = get_nodes_block(n); + ir_node *jmp = new_r_Jmp(block); + ir_graph *irg = get_irn_irg(n); + ir_node *bad = new_r_Bad(irg, mode_X); + ir_mode *mode = get_Load_mode(n); + ir_node *res = new_r_Proj(pred_load, mode, pn_Load_res); + ir_node *in[pn_Load_max] = { mem, jmp, bad, res }; + ir_node *tuple = new_r_Tuple(block, ARRAY_SIZE(in), in); + return tuple; + } + } else if (is_Store(mem_pred)) { + ir_node *pred_store = mem_pred; + ir_node *value = get_Store_value(pred_store); + + if (get_Store_ptr(pred_store) != get_Load_ptr(n)) + return n; + if (get_irn_mode(value) != get_Load_mode(n)) + return n; + /* all combinations of aligned/unaligned pred/n should be fine so we do + * not compare the unaligned attribute */ + { + ir_node *block = get_nodes_block(n); + ir_node *jmp = new_r_Jmp(block); + ir_graph *irg = get_irn_irg(n); + ir_node *bad = new_r_Bad(irg, mode_X); + ir_node *res = value; + ir_node *in[pn_Load_max] = { mem, jmp, bad, res }; + ir_node *tuple = new_r_Tuple(block, ARRAY_SIZE(in), in); + return tuple; + } + } return n; -} /* transform_node_Sync */ +} /** * optimize a trampoline Call into a direct Call @@ -5797,6 +5734,7 @@ static ir_op_ops *firm_set_default_transform_node(ir_opcode code, ir_op_ops *ops switch (code) { CASE(Add); CASE(And); + CASE(Block); CASE(Call); CASE(Cmp); CASE(Conv); @@ -5818,10 +5756,10 @@ static ir_op_ops *firm_set_default_transform_node(ir_opcode code, ir_op_ops *ops CASE(Sync); CASE_PROJ(Bound); CASE_PROJ(CopyB); - CASE_PROJ(Load); CASE_PROJ(Store); CASE_PROJ_EX(Cond); CASE_PROJ_EX(Div); + CASE_PROJ_EX(Load); CASE_PROJ_EX(Mod); default: /* leave NULL */; @@ -6010,29 +5948,31 @@ static int node_cmp_attr_ASM(const ir_node *a, const ir_node *b) /* Should we really check the constraints here? Should be better, but is strange. */ n = get_ASM_n_input_constraints(a); if (n != get_ASM_n_input_constraints(b)) - return 0; + return 1; ca = get_ASM_input_constraints(a); cb = get_ASM_input_constraints(b); for (i = 0; i < n; ++i) { - if (ca[i].pos != cb[i].pos || ca[i].constraint != cb[i].constraint) + if (ca[i].pos != cb[i].pos || ca[i].constraint != cb[i].constraint + || ca[i].mode != cb[i].mode) return 1; } n = get_ASM_n_output_constraints(a); if (n != get_ASM_n_output_constraints(b)) - return 0; + return 1; ca = get_ASM_output_constraints(a); cb = get_ASM_output_constraints(b); for (i = 0; i < n; ++i) { - if (ca[i].pos != cb[i].pos || ca[i].constraint != cb[i].constraint) + if (ca[i].pos != cb[i].pos || ca[i].constraint != cb[i].constraint + || ca[i].mode != cb[i].mode) return 1; } n = get_ASM_n_clobbers(a); if (n != get_ASM_n_clobbers(b)) - return 0; + return 1; cla = get_ASM_clobbers(a); clb = get_ASM_clobbers(b); @@ -6271,100 +6211,6 @@ void visit_all_identities(ir_graph *irg, irg_walk_func visit, void *env) current_ir_graph = rem; } /* visit_all_identities */ -/** - * 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 ir_node *gigo(ir_node *node) -{ - int i, irn_arity; - ir_op *op = get_irn_op(node); - - /* remove garbage blocks by looking at control flow that leaves the block - and replacing the control flow by Bad. */ - if (get_irn_mode(node) == mode_X) { - ir_node *block = get_nodes_block(skip_Proj(node)); - ir_graph *irg = get_irn_irg(block); - - /* Don't optimize nodes in immature blocks. */ - if (!get_Block_matured(block)) - return node; - /* Don't optimize End, may have Bads. */ - if (op == op_End) return node; - - if (is_Block(block)) { - if (is_Block_dead(block)) { - /* control flow from dead block is dead */ - return get_irg_bad(irg); - } - - for (i = get_irn_arity(block) - 1; i >= 0; --i) { - if (!is_Bad(get_irn_n(block, i))) - break; - } - if (i < 0) { - ir_graph *irg = get_irn_irg(block); - /* the start block is never dead */ - if (block != get_irg_start_block(irg) - && block != get_irg_end_block(irg)) { - /* - * Do NOT kill control flow without setting - * the block to dead of bad things can happen: - * We get a Block that is not reachable be irg_block_walk() - * but can be found by irg_walk()! - */ - set_Block_dead(block); - return get_irg_bad(irg); - } - } - } - } - - /* 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 && op != op_Anchor) { - ir_graph *irg = get_irn_irg(node); - irn_arity = get_irn_arity(node); - - /* - * Beware: we can only read the block of a non-floating node. - */ - if (is_irn_pinned_in_irg(node) && - is_Block_dead(get_nodes_block(skip_Proj(node)))) - return get_irg_bad(irg); - - for (i = 0; i < irn_arity; i++) { - ir_node *pred = get_irn_n(node, i); - - if (is_Bad(pred)) - return get_irg_bad(irg); -#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 its 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_r_Unknown(irg, get_irn_mode(node)); -#endif - } - } -#if 0 - /* With this code we violate the agreement that local_optimize - only leaves Bads in Block, Phi and Tuple nodes. */ - /* If Block has only Bads as predecessors it's garbage. */ - /* If Phi has only Bads as predecessors it's garbage. */ - if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) { - irn_arity = get_irn_arity(node); - for (i = 0; i < irn_arity; i++) { - if (!is_Bad(get_irn_n(node, i))) break; - } - if (i == irn_arity) node = get_irg_bad(irg); - } -#endif - return node; -} /* gigo */ - /** * These optimizations deallocate nodes from the obstack. * It can only be called if it is guaranteed that no other nodes @@ -6382,17 +6228,6 @@ ir_node *optimize_node(ir_node *n) /* Always optimize Phi nodes: part of the construction. */ if ((!get_opt_optimize()) && (iro != iro_Phi)) return n; - /* Remove nodes with dead (Bad) input. - Run always for transformation induced Bads. */ - n = gigo(n); - if (n != oldn) { - edges_node_deleted(oldn); - - /* We found an existing, better node, so we can deallocate the old node. */ - irg_kill_node(irg, oldn); - return n; - } - /* constant expression evaluation / constant folding */ if (get_opt_constant_folding()) { /* neither constants nor Tuple values can be evaluated */ @@ -6491,12 +6326,6 @@ ir_node *optimize_in_place_2(ir_node *n) if (iro == iro_Deleted) return n; - /* Remove nodes with dead (Bad) input. - Run always for transformation induced Bads. */ - n = gigo(n); - if (is_Bad(n)) - return n; - /* constant expression evaluation / constant folding */ if (get_opt_constant_folding()) { /* neither constants nor Tuple values can be evaluated */ @@ -6569,8 +6398,6 @@ ir_node *optimize_in_place(ir_node *n) if (get_opt_global_cse()) set_irg_pinned(irg, op_pin_state_floats); - if (get_irg_outs_state(irg) == outs_consistent) - set_irg_outs_inconsistent(irg); /* FIXME: Maybe we could also test whether optimizing the node can change the control graph. */ @@ -6613,7 +6440,7 @@ static unsigned hash_SymConst(const ir_node *node) * @return * The operations. */ -static ir_op_ops *firm_set_default_hash(ir_opcode code, ir_op_ops *ops) +static ir_op_ops *firm_set_default_hash(unsigned code, ir_op_ops *ops) { #define CASE(a) \ case iro_##a: \ @@ -6639,7 +6466,7 @@ static ir_op_ops *firm_set_default_hash(ir_opcode code, ir_op_ops *ops) /* * Sets the default operation for an ir_ops. */ -ir_op_ops *firm_set_default_operations(ir_opcode code, ir_op_ops *ops) +ir_op_ops *firm_set_default_operations(unsigned code, ir_op_ops *ops) { ops = firm_set_default_hash(code, ops); ops = firm_set_default_computed_value(code, ops);