On Fri, Oct 26, 2012 at 7:27 PM, Jakub Jelinek <ja...@redhat.com> wrote:
> Hi!
>
> This patch extends optimize_range_tests optimization, so that it
> handles also the cases where the truth && or || has been gimplifed
> as a series of GIMPLE_CONDs or mixture thereof and BIT_{AND,IOR}_EXPR
> stmts.
>
> Example of code it handles is e.g.:
> <bb 2>:
> v1_3 = a_2(D) != 3;
> v2_4 = a_2(D) != 1;
> v3_5 = a_2(D) != 4;
> v4_6 = a_2(D) != 2;
> v5_7 = a_2(D) != 7;
> v6_8 = a_2(D) != 5;
> v7_9 = a_2(D) != 8;
> v8_10 = a_2(D) != 6;
> _11 = v1_3 & v2_4;
> if (_11 != 0)
> goto <bb 3>;
> else
> goto <bb 7>;
>
> <bb 3>:
> _13 = v3_5 & v4_6;
> if (_13 != 0)
> goto <bb 4>;
> else
> goto <bb 7>;
>
> <bb 4>:
> _14 = v5_7 & v6_8;
> if (_14 != 0)
> goto <bb 5>;
> else
> goto <bb 7>;
>
> <bb 5>:
> _15 = v7_9 & v8_10;
> if (_15 != 0)
> goto <bb 6>;
> else
> goto <bb 7>;
>
> or:
>
> <bb 2>:
> _3 = c_2(D) == 34;
> _4 = c_2(D) == 32;
> _5 = _3 | _4;
> if (_5 != 0)
> goto <bb 4>;
> else
> goto <bb 3>;
>
> <bb 3>:
> _8 = c_2(D) <= 31;
> _7 = (int) _8;
>
> <bb 4>:
> # _1 = PHI <_7(3), 1(2)>
>
> It is implemented in reassociate_bb, as that is where all the
> infrastructure already is, but isn't done as part of normal
> reassociation, but before reassociating first bb that represents
> a series of && or || operands. As post-dominator sons aren't
> particularly ordered, it can happen that the optimization is performed
> on the first, last or middle bb of the series of bbs, so it searches
> both forward and backward to find suitable basic blocks.
> The last bb in the series (last_bb) can be of the form of bb 3 in the
> second example, which is how certain sequencies are gimplified when
> assigning && or || result to a variable or returning it.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
Ok, but the code could really really have some more comments - functions
not fitting in my 80x24 terminal without seeing any comment what happens
here are a maintainance nightmare.
Thanks,
Richard.
> 2012-10-26 Jakub Jelinek <ja...@redhat.com>
>
> PR tree-optimization/19105
> PR tree-optimization/21643
> PR tree-optimization/46309
> * tree-ssa-reassoc.c (init_range_entry): Add STMT argument
> and use it if EXP is NULL.
> (update_range_test): Handle OPCODE equal to ERROR_MARK
> and oe->op NULL.
> (optimize_range_tests): Likewise.
> (final_range_test_p, suitable_cond_bb, no_side_effect_bb, get_ops,
> maybe_optimize_range_tests): New functions.
> (reassociate_bb): Call maybe_optimize_range_tests if last
> stmt of bb is GIMPLE_COND that hasn't been visited yet.
>
> * gcc.dg/pr19105.c: New test.
> * gcc.dg/pr21643.c: New test.
> * gcc.dg/pr46309-2.c: New test.
> * gcc.c-torture/execute/pr46309.c: New test.
>
> --- gcc/tree-ssa-reassoc.c.jj 2012-10-25 09:21:08.657049321 +0200
> +++ gcc/tree-ssa-reassoc.c 2012-10-26 15:51:13.398025229 +0200
> @@ -1,5 +1,5 @@
> /* Reassociation for trees.
> - Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
> + Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
> Free Software Foundation, Inc.
> Contributed by Daniel Berlin <d...@dberlin.org>
>
> @@ -1713,10 +1713,12 @@ struct range_entry
> };
>
> /* This is similar to make_range in fold-const.c, but on top of
> - GIMPLE instead of trees. */
> + GIMPLE instead of trees. If EXP is non-NULL, it should be
> + an SSA_NAME and STMT argument is ignored, otherwise STMT
> + argument should be a GIMPLE_COND. */
>
> static void
> -init_range_entry (struct range_entry *r, tree exp)
> +init_range_entry (struct range_entry *r, tree exp, gimple stmt)
> {
> int in_p;
> tree low, high;
> @@ -1727,7 +1729,8 @@ init_range_entry (struct range_entry *r,
> r->strict_overflow_p = false;
> r->low = NULL_TREE;
> r->high = NULL_TREE;
> - if (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp)))
> + if (exp != NULL_TREE
> + && (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp))))
> return;
>
> /* Start with simply saying "EXP != 0" and then look at the code of EXP
> @@ -1735,12 +1738,14 @@ init_range_entry (struct range_entry *r,
> happen, but it doesn't seem worth worrying about this. We "continue"
> the outer loop when we've changed something; otherwise we "break"
> the switch, which will "break" the while. */
> - low = build_int_cst (TREE_TYPE (exp), 0);
> + low = exp ? build_int_cst (TREE_TYPE (exp), 0) : boolean_false_node;
> high = low;
> in_p = 0;
> strict_overflow_p = false;
> is_bool = false;
> - if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
> + if (exp == NULL_TREE)
> + is_bool = true;
> + else if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
> {
> if (TYPE_UNSIGNED (TREE_TYPE (exp)))
> is_bool = true;
> @@ -1752,25 +1757,35 @@ init_range_entry (struct range_entry *r,
>
> while (1)
> {
> - gimple stmt;
> enum tree_code code;
> tree arg0, arg1, exp_type;
> tree nexp;
> location_t loc;
>
> - if (TREE_CODE (exp) != SSA_NAME)
> - break;
> + if (exp != NULL_TREE)
> + {
> + if (TREE_CODE (exp) != SSA_NAME)
> + break;
>
> - stmt = SSA_NAME_DEF_STMT (exp);
> - if (!is_gimple_assign (stmt))
> - break;
> + stmt = SSA_NAME_DEF_STMT (exp);
> + if (!is_gimple_assign (stmt))
> + break;
> +
> + code = gimple_assign_rhs_code (stmt);
> + arg0 = gimple_assign_rhs1 (stmt);
> + arg1 = gimple_assign_rhs2 (stmt);
> + exp_type = TREE_TYPE (exp);
> + }
> + else
> + {
> + code = gimple_cond_code (stmt);
> + arg0 = gimple_cond_lhs (stmt);
> + arg1 = gimple_cond_rhs (stmt);
> + exp_type = boolean_type_node;
> + }
>
> - code = gimple_assign_rhs_code (stmt);
> - arg0 = gimple_assign_rhs1 (stmt);
> if (TREE_CODE (arg0) != SSA_NAME)
> break;
> - arg1 = gimple_assign_rhs2 (stmt);
> - exp_type = TREE_TYPE (exp);
> loc = gimple_location (stmt);
> switch (code)
> {
> @@ -1916,7 +1931,11 @@ range_entry_cmp (const void *a, const vo
> [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
> RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
> OPCODE and OPS are arguments of optimize_range_tests. Return
> - true if the range merge has been successful. */
> + true if the range merge has been successful.
> + If OPCODE is ERROR_MARK, this is called from within
> + maybe_optimize_range_tests and is performing inter-bb range optimization.
> + Changes should be then performed right away, and whether an op is
> + BIT_AND_EXPR or BIT_IOR_EXPR is found in oe->rank. */
>
> static bool
> update_range_test (struct range_entry *range, struct range_entry *otherrange,
> @@ -1924,9 +1943,12 @@ update_range_test (struct range_entry *r
> VEC (operand_entry_t, heap) **ops, tree exp, bool in_p,
> tree low, tree high, bool strict_overflow_p)
> {
> - tree op = VEC_index (operand_entry_t, *ops, range->idx)->op;
> - location_t loc = gimple_location (SSA_NAME_DEF_STMT (op));
> - tree tem = build_range_check (loc, TREE_TYPE (op), exp, in_p, low, high);
> + operand_entry_t oe = VEC_index (oeprand_entry_t, *ops, range->idx);
> + tree op = oe->op;
> + gimple stmt = op ? SSA_NAME_DEF_STMT (op) : last_stmt (BASIC_BLOCK
> (oe->id));
> + location_t loc = gimple_location (stmt);
> + tree optype = op ? TREE_TYPE (op) : boolean_type_node;
> + tree tem = build_range_check (loc, optype, exp, in_p, low, high);
> enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
> gimple_stmt_iterator gsi;
>
> @@ -1961,15 +1983,41 @@ update_range_test (struct range_entry *r
> fprintf (dump_file, "\n");
> }
>
> - if (opcode == BIT_IOR_EXPR)
> + if (opcode == BIT_IOR_EXPR
> + || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
> tem = invert_truthvalue_loc (loc, tem);
>
> - tem = fold_convert_loc (loc, TREE_TYPE (op), tem);
> - gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (op));
> + tem = fold_convert_loc (loc, optype, tem);
> + gsi = gsi_for_stmt (stmt);
> tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
> GSI_SAME_STMT);
>
> - VEC_index (operand_entry_t, *ops, range->idx)->op = tem;
> + if (opcode == ERROR_MARK)
> + {
> + if (op)
> + {
> + imm_use_iterator iter;
> + use_operand_p use_p;
> + gimple use_stmt;
> +
> + FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
> + {
> + if (is_gimple_debug (use_stmt))
> + continue;
> + FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
> + SET_USE (use_p, tem);
> + update_stmt (use_stmt);
> + }
> + }
> + else
> + {
> + gimple_cond_set_code (stmt, NE_EXPR);
> + gimple_cond_set_lhs (stmt, tem);
> + gimple_cond_set_rhs (stmt, boolean_false_node);
> + update_stmt (stmt);
> + }
> + }
> + oe->op = tem;
> range->exp = exp;
> range->low = low;
> range->high = high;
> @@ -1978,7 +2026,73 @@ update_range_test (struct range_entry *r
>
> for (range = otherrange; range < otherrange + count; range++)
> {
> - VEC_index (operand_entry_t, *ops, range->idx)->op = error_mark_node;
> + oe = VEC_index (oeprand_entry_t, *ops, range->idx);
> + if (opcode == ERROR_MARK)
> + {
> + if (oe->op)
> + {
> + imm_use_iterator iter;
> + use_operand_p use_p;
> + gimple use_stmt;
> +
> + FOR_EACH_IMM_USE_STMT (use_stmt, iter, oe->op)
> + {
> + if (is_gimple_debug (use_stmt))
> + continue;
> + if (is_gimple_assign (use_stmt)
> + && gimple_assign_rhs_code (use_stmt) == oe->rank)
> + {
> + tree expr = NULL_TREE;
> + if (oe->op == gimple_assign_rhs1 (use_stmt))
> + expr = gimple_assign_rhs2 (use_stmt);
> + else if (oe->op == gimple_assign_rhs2 (use_stmt))
> + expr = gimple_assign_rhs1 (use_stmt);
> + if (expr
> + && expr != oe->op
> + && TREE_CODE (expr) == SSA_NAME)
> + {
> + gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
> + gimple_assign_set_rhs_with_ops (&gsi2, SSA_NAME,
> + expr, NULL_TREE);
> + update_stmt (use_stmt);
> + continue;
> + }
> + if (gimple_assign_cast_p (use_stmt)
> + && oe->op == gimple_assign_rhs1 (use_stmt))
> + {
> + tree lhs = gimple_assign_lhs (use_stmt);
> + if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
> + {
> + gimple_stmt_iterator gsi2
> + = gsi_for_stmt (use_stmt);
> + expr = build_int_cst (TREE_TYPE (lhs),
> + oe->rank == BIT_IOR_EXPR
> + ? 0 : 1);
> + gimple_assign_set_rhs_with_ops (&gsi2,
> + INTEGER_CST,
> + expr,
> NULL_TREE);
> + }
> + }
> + }
> + FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
> + SET_USE (use_p,
> + build_int_cst (TREE_TYPE (oe->op),
> + oe->rank == BIT_IOR_EXPR
> + ? 0 : 1));
> + update_stmt (use_stmt);
> + }
> + }
> + else
> + {
> + stmt = last_stmt (BASIC_BLOCK (oe->id));
> + if (oe->rank == BIT_IOR_EXPR)
> + gimple_cond_make_false (stmt);
> + else
> + gimple_cond_make_true (stmt);
> + update_stmt (stmt);
> + }
> + }
> + oe->op = error_mark_node;
> range->exp = NULL_TREE;
> }
> return true;
> @@ -1986,7 +2100,12 @@ update_range_test (struct range_entry *r
>
> /* Optimize range tests, similarly how fold_range_test optimizes
> it on trees. The tree code for the binary
> - operation between all the operands is OPCODE. */
> + operation between all the operands is OPCODE.
> + If OPCODE is ERROR_MARK, optimize_range_tests is called from within
> + maybe_optimize_range_tests for inter-bb range optimization.
> + In that case if oe->op is NULL, oe->id is bb->index whose
> + GIMPLE_COND is && or ||ed into the test, and oe->rank says
> + the actual opcode. */
>
> static void
> optimize_range_tests (enum tree_code opcode,
> @@ -2003,11 +2122,14 @@ optimize_range_tests (enum tree_code opc
> ranges = XNEWVEC (struct range_entry, length);
> for (i = 0; i < length; i++)
> {
> + oe = VEC_index (operand_entry_t, *ops, i);
> ranges[i].idx = i;
> - init_range_entry (ranges + i, VEC_index (operand_entry_t, *ops,
> i)->op);
> + init_range_entry (ranges + i, oe->op,
> + oe->op ? NULL : last_stmt (BASIC_BLOCK (oe->id)));
> /* For | invert it now, we will invert it again before emitting
> the optimized expression. */
> - if (opcode == BIT_IOR_EXPR)
> + if (opcode == BIT_IOR_EXPR
> + || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
> ranges[i].in_p = !ranges[i].in_p;
> }
>
> @@ -2124,7 +2246,7 @@ optimize_range_tests (enum tree_code opc
> }
> }
>
> - if (any_changes)
> + if (any_changes && opcode != ERROR_MARK)
> {
> j = 0;
> FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe)
> @@ -2141,6 +2263,398 @@ optimize_range_tests (enum tree_code opc
> XDELETEVEC (ranges);
> }
>
> +/* Return true if STMT is a cast like:
> + <bb N>:
> + ...
> + _123 = (int) _234;
> +
> + <bb M>:
> + # _345 = PHI <_123(N), 1(...), 1(...)>
> + where _234 has bool type, _123 has single use and
> + bb N has a single successor M. This is commonly used in
> + the last block of a range test. */
> +
> +static bool
> +final_range_test_p (gimple stmt)
> +{
> + basic_block bb, rhs_bb;
> + edge e;
> + tree lhs, rhs;
> + use_operand_p use_p;
> + gimple use_stmt;
> +
> + if (!gimple_assign_cast_p (stmt))
> + return false;
> + bb = gimple_bb (stmt);
> + if (!single_succ_p (bb))
> + return false;
> + e = single_succ_edge (bb);
> + if (e->flags & EDGE_COMPLEX)
> + return false;
> +
> + lhs = gimple_assign_lhs (stmt);
> + rhs = gimple_assign_rhs1 (stmt);
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> + || TREE_CODE (rhs) != SSA_NAME
> + || TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
> + return false;
> +
> + if (!single_imm_use (lhs, &use_p, &use_stmt))
> + return false;
> +
> + if (gimple_code (use_stmt) != GIMPLE_PHI
> + || gimple_bb (use_stmt) != e->dest)
> + return false;
> +
> + rhs_bb = gimple_bb (SSA_NAME_DEF_STMT (rhs));
> + if (rhs_bb == NULL
> + || !flow_bb_inside_loop_p (loop_containing_stmt (stmt), rhs_bb))
> + return false;
> +
> + return true;
> +}
> +
> +/* Return true if BB is suitable basic block for inter-bb range test
> + optimization. If BACKWARD is true, BB should be the only predecessor
> + of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
> + or compared with to find a common basic block to which all conditions
> + branch to if true resp. false. If BACKWARD is false, TEST_BB should
> + be the only predecessor of BB. */
> +
> +static bool
> +suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
> + bool backward)
> +{
> + edge_iterator ei, ei2;
> + edge e, e2;
> + gimple stmt;
> + gimple_stmt_iterator gsi;
> + bool other_edge_seen = false;
> + bool is_cond;
> +
> + if (test_bb == bb)
> + return false;
> + stmt = last_stmt (bb);
> + if (stmt == NULL
> + || (gimple_code (stmt) != GIMPLE_COND
> + && (backward || !final_range_test_p (stmt)))
> + || gimple_visited_p (stmt)
> + || stmt_could_throw_p (stmt)
> + || *other_bb == bb)
> + return false;
> + is_cond = gimple_code (stmt) == GIMPLE_COND;
> + if (is_cond)
> + {
> + if (EDGE_COUNT (bb->succs) != 2)
> + return false;
> + FOR_EACH_EDGE (e, ei, bb->succs)
> + {
> + if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
> + return false;
> + if (e->dest == test_bb)
> + {
> + if (backward)
> + continue;
> + else
> + return false;
> + }
> + if (e->dest == bb)
> + return false;
> + if (*other_bb == NULL)
> + {
> + FOR_EACH_EDGE (e2, ei2, test_bb->succs)
> + if (!(e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
> + return false;
> + else if (e->dest == e2->dest)
> + *other_bb = e->dest;
> + if (*other_bb == NULL)
> + return false;
> + }
> + if (e->dest == *other_bb)
> + other_edge_seen = true;
> + else if (backward)
> + return false;
> + }
> + if (*other_bb == NULL || !other_edge_seen)
> + return false;
> + }
> + else if (single_succ (bb) != *other_bb)
> + return false;
> +
> + e = find_edge (bb, *other_bb);
> + e2 = find_edge (test_bb, *other_bb);
> + for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + gimple phi = gsi_stmt (gsi);
> + if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
> + gimple_phi_arg_def (phi, e2->dest_idx), 0))
> + {
> + if (!is_cond)
> + {
> + if (gimple_phi_arg_def (phi, e->dest_idx)
> + == gimple_assign_lhs (stmt)
> + && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
> + || integer_onep (gimple_phi_arg_def (phi,
> + e2->dest_idx))))
> + continue;
> + }
> + else
> + {
> + gimple test_last = last_stmt (test_bb);
> + if (gimple_code (test_last) != GIMPLE_COND
> + && gimple_phi_arg_def (phi, e2->dest_idx)
> + == gimple_assign_lhs (test_last)
> + && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
> + || integer_onep (gimple_phi_arg_def (phi,
> e->dest_idx))))
> + continue;
> + }
> +
> + return false;
> + }
> + }
> + return true;
> +}
> +
> +/* Return true if BB doesn't have side-effects that would disallow
> + range test optimization, all SSA_NAMEs set in the bb are consumed
> + in the bb and there are no PHIs. */
> +
> +static bool
> +no_side_effect_bb (basic_block bb)
> +{
> + gimple_stmt_iterator gsi;
> + gimple last;
> +
> + if (!gimple_seq_empty_p (phi_nodes (bb)))
> + return false;
> + last = last_stmt (bb);
> + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> + {
> + gimple stmt = gsi_stmt (gsi);
> + tree lhs;
> + imm_use_iterator imm_iter;
> + use_operand_p use_p;
> +
> + if (is_gimple_debug (stmt))
> + continue;
> + if (gimple_has_side_effects (stmt))
> + return false;
> + if (stmt == last)
> + return true;
> + if (!is_gimple_assign (stmt))
> + return false;
> + lhs = gimple_assign_lhs (stmt);
> + if (TREE_CODE (lhs) != SSA_NAME)
> + return false;
> + if (gimple_assign_rhs_could_trap_p (stmt))
> + return false;
> + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
> + {
> + gimple use_stmt = USE_STMT (use_p);
> + if (is_gimple_debug (use_stmt))
> + continue;
> + if (gimple_bb (use_stmt) != bb)
> + return false;
> + }
> + }
> + return false;
> +}
> +
> +/* If VAR is set by CODE (BIT_{AND,IOR}_EXPR) which is reassociable,
> + return true and fill in *OPS recursively. */
> +
> +static bool
> +get_ops (tree var, enum tree_code code, VEC(operand_entry_t, heap) **ops,
> + struct loop *loop)
> +{
> + gimple stmt = SSA_NAME_DEF_STMT (var);
> + tree rhs[2];
> + int i;
> +
> + if (!is_reassociable_op (stmt, code, loop))
> + return false;
> +
> + rhs[0] = gimple_assign_rhs1 (stmt);
> + rhs[1] = gimple_assign_rhs2 (stmt);
> + gimple_set_visited (stmt, true);
> + for (i = 0; i < 2; i++)
> + if (TREE_CODE (rhs[i]) == SSA_NAME
> + && !get_ops (rhs[i], code, ops, loop)
> + && has_single_use (rhs[i]))
> + {
> + operand_entry_t oe = (operand_entry_t) pool_alloc
> (operand_entry_pool);
> +
> + oe->op = rhs[i];
> + oe->rank = code;
> + oe->id = 0;
> + oe->count = 1;
> + VEC_safe_push (operand_entry_t, heap, *ops, oe);
> + }
> + return true;
> +}
> +
> +/* Inter-bb range test optimization. */
> +
> +static void
> +maybe_optimize_range_tests (gimple stmt)
> +{
> + basic_block first_bb = gimple_bb (stmt);
> + basic_block last_bb = first_bb;
> + basic_block other_bb = NULL;
> + basic_block bb;
> + edge_iterator ei;
> + edge e;
> + VEC(operand_entry_t, heap) *ops = NULL;
> +
> + if (gimple_code (stmt) == GIMPLE_COND)
> + {
> + if (EDGE_COUNT (first_bb->succs) != 2)
> + return;
> + }
> + else if (final_range_test_p (stmt))
> + other_bb = single_succ (first_bb);
> + else
> + return;
> +
> + if (stmt_could_throw_p (stmt))
> + return;
> +
> + while (single_pred_p (first_bb))
> + {
> + basic_block pred_bb = single_pred (first_bb);
> + if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true))
> + break;
> + if (!no_side_effect_bb (first_bb))
> + break;
> + first_bb = pred_bb;
> + }
> + if (first_bb == last_bb)
> + {
> + other_bb = NULL;
> + if (gimple_code (stmt) != GIMPLE_COND)
> + return;
> + FOR_EACH_EDGE (e, ei, first_bb->succs)
> + if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
> + || e->dest == first_bb)
> + return;
> + else if (single_pred_p (e->dest))
> + {
> + stmt = last_stmt (e->dest);
> + if (stmt
> + && gimple_code (stmt) == GIMPLE_COND
> + && EDGE_COUNT (e->dest->succs) == 2)
> + {
> + if (suitable_cond_bb (first_bb, e->dest, &other_bb, true))
> + break;
> + else
> + other_bb = NULL;
> + }
> + else if (stmt
> + && final_range_test_p (stmt)
> + && find_edge (first_bb, single_succ (e->dest)))
> + {
> + other_bb = single_succ (e->dest);
> + if (other_bb == first_bb)
> + other_bb = NULL;
> + }
> + }
> + if (other_bb == NULL)
> + return;
> + }
> + while (EDGE_COUNT (last_bb->succs) == 2)
> + {
> + FOR_EACH_EDGE (e, ei, last_bb->succs)
> + if (e->dest != other_bb)
> + break;
> + if (e == NULL)
> + break;
> + if (!single_pred_p (e->dest))
> + break;
> + if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false))
> + break;
> + if (!no_side_effect_bb (e->dest))
> + break;
> + last_bb = e->dest;
> + }
> + if (first_bb == last_bb)
> + return;
> + for (bb = last_bb; ; bb = single_pred (bb))
> + {
> + enum tree_code code;
> + tree lhs, rhs;
> +
> + e = find_edge (bb, other_bb);
> + stmt = last_stmt (bb);
> + gimple_set_visited (stmt, true);
> + if (gimple_code (stmt) != GIMPLE_COND)
> + {
> + use_operand_p use_p;
> + gimple phi;
> + edge e2;
> + unsigned int d;
> +
> + lhs = gimple_assign_lhs (stmt);
> + rhs = gimple_assign_rhs1 (stmt);
> + gcc_assert (bb == last_bb);
> +
> + single_imm_use (lhs, &use_p, &phi);
> + gcc_assert (gimple_code (phi) == GIMPLE_PHI);
> + e2 = find_edge (first_bb, other_bb);
> + d = e2->dest_idx;
> + gcc_assert (gimple_phi_arg_def (phi, e->dest_idx) == lhs);
> + if (integer_zerop (gimple_phi_arg_def (phi, d)))
> + code = BIT_AND_EXPR;
> + else
> + {
> + gcc_checking_assert (integer_onep (gimple_phi_arg_def (phi,
> d)));
> + code = BIT_IOR_EXPR;
> + }
> +
> + if (!get_ops (rhs, code, &ops,
> + loop_containing_stmt (stmt))
> + && has_single_use (rhs))
> + {
> + operand_entry_t oe
> + = (operand_entry_t) pool_alloc (operand_entry_pool);
> +
> + oe->op = rhs;
> + oe->rank = code;
> + oe->id = 0;
> + oe->count = 1;
> + VEC_safe_push (operand_entry_t, heap, ops, oe);
> + }
> + continue;
> + }
> + code = gimple_cond_code (stmt);
> + lhs = gimple_cond_lhs (stmt);
> + rhs = gimple_cond_rhs (stmt);
> + if (TREE_CODE (lhs) == SSA_NAME
> + && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> + && ((code != EQ_EXPR && code != NE_EXPR)
> + || rhs != boolean_false_node
> + || !get_ops (lhs, (((e->flags & EDGE_TRUE_VALUE) == 0)
> + ^ (code == EQ_EXPR))
> + ? BIT_AND_EXPR : BIT_IOR_EXPR, &ops,
> + loop_containing_stmt (stmt))))
> + {
> + operand_entry_t oe
> + = (operand_entry_t) pool_alloc (operand_entry_pool);
> +
> + oe->op = NULL;
> + oe->rank = (e->flags & EDGE_TRUE_VALUE)
> + ? BIT_IOR_EXPR : BIT_AND_EXPR;
> + oe->id = bb->index;
> + oe->count = 1;
> + VEC_safe_push (operand_entry_t, heap, ops, oe);
> + }
> + if (bb == first_bb)
> + break;
> + }
> + if (VEC_length (operand_entry_t, ops) > 1)
> + optimize_range_tests (ERROR_MARK, &ops);
> + VEC_free (operand_entry_t, heap, ops);
> +}
> +
> /* Return true if OPERAND is defined by a PHI node which uses the LHS
> of STMT in it's operands. This is also known as a "destructive
> update" operation. */
> @@ -3427,10 +3941,14 @@ reassociate_bb (basic_block bb)
> {
> gimple_stmt_iterator gsi;
> basic_block son;
> + gimple stmt = last_stmt (bb);
> +
> + if (stmt && !gimple_visited_p (stmt))
> + maybe_optimize_range_tests (stmt);
>
> for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
> {
> - gimple stmt = gsi_stmt (gsi);
> + stmt = gsi_stmt (gsi);
>
> if (is_gimple_assign (stmt)
> && !stmt_could_throw_p (stmt))
> --- gcc/testsuite/gcc.dg/pr19105.c.jj 2012-10-26 15:12:04.191828571 +0200
> +++ gcc/testsuite/gcc.dg/pr19105.c 2012-10-26 15:11:41.000000000 +0200
> @@ -0,0 +1,22 @@
> +/* PR tree-optimization/19105 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
> +
> +enum e
> +{
> + a, b, c, d, e, f, g, h
> +};
> +
> +int range1 (enum e v, int x)
> +{
> + return x && v != c && v != d && v != e;
> +}
> +
> +int range2 (enum e v, int x)
> +{
> + return x && (v != c && v != d && v != e);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests v_\[0-9\]*.D.
> -.2, 2. and -.3, 4.\[\n\r\]* into" 1 "reassoc1" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc1" } } */
> +
> --- gcc/testsuite/gcc.dg/pr21643.c.jj 2012-10-26 15:00:14.588063088 +0200
> +++ gcc/testsuite/gcc.dg/pr21643.c 2012-10-26 15:01:31.199598891 +0200
> @@ -0,0 +1,90 @@
> +/* PR tree-optimization/21643 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
> +
> +int
> +f1 (unsigned char c)
> +{
> + if (c == 0x22 || c == 0x20 || c < 0x20)
> + return 1;
> + return 0;
> +}
> +
> +int
> +f2 (unsigned char c)
> +{
> + if (c == 0x22 || c <= 0x20)
> + return 1;
> + return 0;
> +}
> +
> +int
> +f3 (unsigned char c)
> +{
> + if (c == 0x22)
> + return 1;
> + if (c == 0x20)
> + return 1;
> + if (c < 0x20)
> + return 1;
> + return 0;
> +}
> +
> +int
> +f4 (unsigned char c)
> +{
> + if (c == 0x22 || c == 0x20 || c < 0x20)
> + return 2;
> + return 0;
> +}
> +
> +int
> +f5 (unsigned char c)
> +{
> + if (c == 0x22 || c <= 0x20)
> + return 2;
> + return 0;
> +}
> +
> +int
> +f6 (unsigned char c)
> +{
> + if (c == 0x22)
> + return 2;
> + if (c == 0x20)
> + return 2;
> + if (c < 0x20)
> + return 2;
> + return 0;
> +}
> +
> +int
> +f7 (unsigned char c)
> +{
> + if (c != 0x22 && c != 0x20 && c >= 0x20)
> + return 0;
> + return 1;
> +}
> +
> +int
> +f8 (unsigned char c)
> +{
> + if (c == 0x22 && c <= 0x20)
> + return 0;
> + return 1;
> +}
> +
> +int
> +f9 (unsigned char c)
> +{
> + if (c == 0x22)
> + return 0;
> + if (c == 0x20)
> + return 0;
> + if (c < 0x20)
> + return 0;
> + return 1;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D.
> -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc1" } } */
> --- gcc/testsuite/gcc.dg/pr46309-2.c.jj 2012-10-25 16:30:42.623578285 +0200
> +++ gcc/testsuite/gcc.dg/pr46309-2.c 2012-10-26 15:16:38.404212168 +0200
> @@ -0,0 +1,147 @@
> +/* PR tree-optimization/46309 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc-details" } */
> +
> +int foo (void);
> +
> +void
> +f1 (int a)
> +{
> + _Bool v1 = (a == 3);
> + _Bool v2 = (a == 1);
> + _Bool v3 = (a == 4);
> + _Bool v4 = (a == 2);
> + if (v1 || v2 || v3 || v4)
> + foo ();
> +}
> +
> +void
> +f2 (int a)
> +{
> + _Bool v1 = (a == 1);
> + _Bool v2 = (a == 2);
> + _Bool v3 = (a == 3);
> + _Bool v4 = (a == 4);
> + if (v1 || v2 || v3 || v4)
> + foo ();
> +}
> +
> +void
> +f3 (unsigned int a)
> +{
> + _Bool v1 = (a <= 31);
> + _Bool v2 = (a >= 64 && a <= 95);
> + _Bool v3 = (a >= 128 && a <= 159);
> + _Bool v4 = (a >= 192 && a <= 223);
> + if (v1 || v2 || v3 || v4)
> + foo ();
> +}
> +
> +void
> +f4 (int a)
> +{
> + _Bool v1 = (a == 3);
> + _Bool v2 = (a == 1);
> + _Bool v3 = (a == 4);
> + _Bool v4 = (a == 2);
> + _Bool v5 = (a == 7);
> + _Bool v6 = (a == 5);
> + _Bool v7 = (a == 8);
> + _Bool v8 = (a == 6);
> + if (v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8)
> + foo ();
> +}
> +
> +void
> +f5 (int a)
> +{
> + _Bool v1 = (a != 3);
> + _Bool v2 = (a != 1);
> + _Bool v3 = (a != 4);
> + _Bool v4 = (a != 2);
> + _Bool v5 = (a != 7);
> + _Bool v6 = (a != 5);
> + _Bool v7 = (a != 8);
> + _Bool v8 = (a != 6);
> + if (v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8)
> + foo ();
> +}
> +
> +void
> +f6 (int a)
> +{
> + _Bool v1 = (a != 3);
> + _Bool v2 = (a != 1);
> + _Bool v3 = (a != 4);
> + _Bool v4 = (a != 2);
> + _Bool v5 = (a != 7);
> + _Bool v6 = (a != 5);
> + _Bool v7 = (a != 8);
> + _Bool v8 = (a != 6);
> + if ((v1 && v2 && v3 && v4) && (v5 && v6 && v7 && v8))
> + foo ();
> +}
> +
> +int
> +f7 (int a)
> +{
> + _Bool v1 = (a == 3);
> + _Bool v2 = (a == 1);
> + _Bool v3 = (a == 4);
> + _Bool v4 = (a == 2);
> + _Bool v5 = (a == 7);
> + _Bool v6 = (a == 5);
> + _Bool v7 = (a == 8);
> + _Bool v8 = (a == 6);
> + return v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8;
> +}
> +
> +_Bool
> +f8 (int a)
> +{
> + _Bool v1 = (a == 3);
> + _Bool v2 = (a == 1);
> + _Bool v3 = (a == 4);
> + _Bool v4 = (a == 2);
> + _Bool v5 = (a == 7);
> + _Bool v6 = (a == 5);
> + _Bool v7 = (a == 8);
> + _Bool v8 = (a == 6);
> + return v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8;
> +}
> +
> +int
> +f9 (int a)
> +{
> + _Bool v1 = (a != 3);
> + _Bool v2 = (a != 1);
> + _Bool v3 = (a != 4);
> + _Bool v4 = (a != 2);
> + _Bool v5 = (a != 7);
> + _Bool v6 = (a != 5);
> + _Bool v7 = (a != 8);
> + _Bool v8 = (a != 6);
> + return v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8;
> +}
> +
> +_Bool
> +f10 (int a)
> +{
> + _Bool v1 = (a != 3);
> + _Bool v2 = (a != 1);
> + _Bool v3 = (a != 4);
> + _Bool v4 = (a != 2);
> + _Bool v5 = (a != 7);
> + _Bool v6 = (a != 5);
> + _Bool v7 = (a != 8);
> + _Bool v8 = (a != 6);
> + return v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D.
> -.1, 1. and -.2, 2. and -.3, 3. and -.4, 4.\[\n\r\]* into" 2 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D.
> -.0, 31. and -.64, 95.\[\n\r\]* into" 1 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D.
> -.128, 159. and -.192, 223.\[\n\r\]* into" 1 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D.
> -.1, 1. and -.2, 2. and -.3, 3. and -.4, 4. and -.5, 5. and -.6, 6. and -.7,
> 7. and -.8, 8.\[\n\r\]* into" 7 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests
> \[^\r\n\]*_\[0-9\]* -.0, 31. and -.128, 159.\[\n\r\]* into" 1 "reassoc2" } }
> */
> +/* { dg-final { cleanup-tree-dump "reassoc1" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc2" } } */
> --- gcc/testsuite/gcc.c-torture/execute/pr46309.c.jj 2012-10-26
> 10:10:28.403238295 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr46309.c 2012-10-26
> 10:10:11.000000000 +0200
> @@ -0,0 +1,31 @@
> +/* PR tree-optimization/46309 */
> +
> +extern void abort (void);
> +
> +unsigned int *q;
> +
> +__attribute__((noinline, noclone)) void
> +bar (unsigned int *p)
> +{
> + if (*p != 2 && *p != 3)
> + (!(!(*q & 263) || *p != 1)) ? abort () : 0;
> +}
> +
> +int
> +main ()
> +{
> + unsigned int x, y;
> + asm volatile ("" : : : "memory");
> + x = 2;
> + bar (&x);
> + x = 3;
> + bar (&x);
> + y = 1;
> + x = 0;
> + q = &y;
> + bar (&x);
> + y = 0;
> + x = 1;
> + bar (&x);
> + return 0;
> +}
>
> Jakub
