This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Inter-bb range test optimization (PRs tree-optimization/19105, tree-optimization/21643, tree-optimization/46309)
- From: Jakub Jelinek <jakub at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 26 Oct 2012 19:27:43 +0200
- Subject: [PATCH] Inter-bb range test optimization (PRs tree-optimization/19105, tree-optimization/21643, tree-optimization/46309)
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
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?
2012-10-26 Jakub Jelinek <jakub@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 <dan@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