On Wed, 20 Jun 2012, Richard Guenther wrote:
On Sun, Jun 10, 2012 at 4:16 PM, Marc Glisse <marc.gli...@inria.fr> wrote:
Hello,
currently, tree-ssa-ifcombine handles pairs of imbricated "if"s that share
the same then branch, or the same else branch. There is no particular reason
why it couldn't also handle the case where the then branch of one is the
else branch of the other, which is what I do here.
Any comments?
The general idea looks good, but I think the patch is too invasive. As far
as I can see the only callers with a non-zero 'inv' argument come from
ifcombine_ifnotorif and ifcombine_ifnotandif (and both with inv == 2).
I would rather see a more localized patch that makes use of
invert_tree_comparison to perform the inversion on the call arguments
of maybe_fold_and/or_comparisons.
Hello,
I finally went back to this version (which is where I started from, as
shown in the PR). It is not very satisfying because:
* some bit tests could also be optimized (more generally, grouping a&&b
and !a&&b on one side and a||b and !a||b on the other side is rather
arbitrary),
* -ftrapping-math makes it useless for floating point,
but I guess it is better than nothing. Handling traps correctly is
complicated because the current code is already a bit bogus (see
http://gcc.gnu.org/ml/gcc-patches/2012-07/msg00924.html for an example),
and even the definition of -ftrapping-math is not clear
( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53805 ).
If defaults are ever reconsidered, my default flags include
-frounding-math -fno-trapping-math.
2012-06-10 Marc Glisse <marc.gli...@inria.fr>
gcc/
PR tree-optimization/51938
* tree-ssa-ifcombine.c (ifcombine_ifandif): New parameter for
inverted outer condition.
(ifcombine_iforif): Likewise.
(tree_ssa_ifcombine_bb): Update calls to the above. Detect !a&&b
and !a||b patterns.
gcc/testsuite/
PR tree-optimization/51938
* gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase.
* gcc.dg/tree-ssa/ssa-ifcombine-9.c: New testcase.
--
Marc GlisseIndex: tree-ssa-ifcombine.c
===================================================================
--- tree-ssa-ifcombine.c (revision 189779)
+++ tree-ssa-ifcombine.c (working copy)
@@ -288,45 +288,48 @@ recognize_bits_test (gimple cond, tree *
|| gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
return false;
*name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
*bits = gimple_assign_rhs2 (stmt);
return true;
}
/* If-convert on a and pattern with a common else block. The inner
- if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
+ if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB,
+ negated if outer_inv is true.
Returns true if the edges to the common else basic-block were merged. */
static bool
-ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
+ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb,
+ bool outer_inv)
{
gimple_stmt_iterator gsi;
gimple inner_cond, outer_cond;
tree name1, name2, bit1, bit2;
inner_cond = last_stmt (inner_cond_bb);
if (!inner_cond
|| gimple_code (inner_cond) != GIMPLE_COND)
return false;
outer_cond = last_stmt (outer_cond_bb);
if (!outer_cond
|| gimple_code (outer_cond) != GIMPLE_COND)
return false;
/* See if we test a single bit of the same name in both tests. In
that case remove the outer test, merging both else edges,
and change the inner one to test for
name & (bit1 | bit2) == (bit1 | bit2). */
- if (recognize_single_bit_test (inner_cond, &name1, &bit1)
+ if (!outer_inv
+ && recognize_single_bit_test (inner_cond, &name1, &bit1)
&& recognize_single_bit_test (outer_cond, &name2, &bit2)
&& name1 == name2)
{
tree t, t2;
/* Do it. */
gsi = gsi_for_stmt (inner_cond);
t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
build_int_cst (TREE_TYPE (name1), 1), bit1);
t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
@@ -360,76 +363,86 @@ ifcombine_ifandif (basic_block inner_con
}
return true;
}
/* See if we have two comparisons that we can merge into one. */
else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
&& TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
{
tree t;
+ enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
+ if (outer_inv)
+ outer_cond_code = invert_tree_comparison (outer_cond_code,
+ HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));
+ if (outer_cond_code == ERROR_MARK)
+ return false;
if (!(t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
gimple_cond_lhs (inner_cond),
gimple_cond_rhs (inner_cond),
- gimple_cond_code (outer_cond),
+ outer_cond_code,
gimple_cond_lhs (outer_cond),
gimple_cond_rhs (outer_cond))))
return false;
t = canonicalize_cond_expr_cond (t);
if (!t)
return false;
gimple_cond_set_condition_from_tree (inner_cond, t);
update_stmt (inner_cond);
/* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
+ gimple_cond_set_condition_from_tree (outer_cond,
+ outer_inv ? boolean_false_node : boolean_true_node);
update_stmt (outer_cond);
if (dump_file)
{
fprintf (dump_file, "optimizing two comparisons to ");
print_generic_expr (dump_file, t, 0);
fprintf (dump_file, "\n");
}
return true;
}
return false;
}
/* If-convert on a or pattern with a common then block. The inner
- if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
+ if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB,
+ negated if outer_inv is true.
Returns true, if the edges leading to the common then basic-block
were merged. */
static bool
-ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
+ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb,
+ bool outer_inv)
{
gimple inner_cond, outer_cond;
tree name1, name2, bits1, bits2;
inner_cond = last_stmt (inner_cond_bb);
if (!inner_cond
|| gimple_code (inner_cond) != GIMPLE_COND)
return false;
outer_cond = last_stmt (outer_cond_bb);
if (!outer_cond
|| gimple_code (outer_cond) != GIMPLE_COND)
return false;
/* See if we have two bit tests of the same name in both tests.
In that case remove the outer test and change the inner one to
test for name & (bits1 | bits2) != 0. */
- if (recognize_bits_test (inner_cond, &name1, &bits1)
+ if (!outer_inv
+ && recognize_bits_test (inner_cond, &name1, &bits1)
&& recognize_bits_test (outer_cond, &name2, &bits2))
{
gimple_stmt_iterator gsi;
tree t;
/* Find the common name which is bit-tested. */
if (name1 == name2)
;
else if (bits1 == bits2)
{
@@ -508,36 +521,43 @@ ifcombine_iforif (basic_block inner_cond
return true;
}
/* See if we have two comparisons that we can merge into one.
This happens for C++ operator overloading where for example
GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
&& TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
{
tree t;
+ enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
+ if (outer_inv)
+ outer_cond_code = invert_tree_comparison (outer_cond_code,
+ HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));
+ if (outer_cond_code == ERROR_MARK)
+ return false;
if (!(t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
gimple_cond_lhs (inner_cond),
gimple_cond_rhs (inner_cond),
- gimple_cond_code (outer_cond),
+ outer_cond_code,
gimple_cond_lhs (outer_cond),
gimple_cond_rhs (outer_cond))))
return false;
t = canonicalize_cond_expr_cond (t);
if (!t)
return false;
gimple_cond_set_condition_from_tree (inner_cond, t);
update_stmt (inner_cond);
/* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
+ gimple_cond_set_condition_from_tree (outer_cond,
+ outer_inv ? boolean_true_node : boolean_false_node);
update_stmt (outer_cond);
if (dump_file)
{
fprintf (dump_file, "optimizing two comparisons to ");
print_generic_expr (dump_file, t, 0);
fprintf (dump_file, "\n");
}
return true;
@@ -580,40 +600,73 @@ tree_ssa_ifcombine_bb (basic_block inner
{
/* We have
<outer_cond_bb>
if (q) goto inner_cond_bb; else goto else_bb;
<inner_cond_bb>
if (p) goto ...; else goto else_bb;
...
<else_bb>
...
*/
- return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
+ return ifcombine_ifandif (inner_cond_bb, outer_cond_bb, false);
+ }
+
+ /* And a version where the outer condition is negated. */
+ if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
+ && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
+ && bb_no_side_effects_p (inner_cond_bb))
+ {
+ /* We have
+ <outer_cond_bb>
+ if (q) goto else_bb; else goto inner_cond_bb;
+ <inner_cond_bb>
+ if (p) goto ...; else goto else_bb;
+ ...
+ <else_bb>
+ ...
+ */
+ return ifcombine_ifandif (inner_cond_bb, outer_cond_bb, true);
}
/* The || form is characterized by a common then_bb with the
two edges leading to it mergable. The latter is guaranteed
by matching PHI arguments in the then_bb and the inner cond_bb
having no side-effects. */
if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
&& same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
&& bb_no_side_effects_p (inner_cond_bb))
{
/* We have
<outer_cond_bb>
if (q) goto then_bb; else goto inner_cond_bb;
<inner_cond_bb>
if (q) goto then_bb; else goto ...;
<then_bb>
...
*/
- return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
+ return ifcombine_iforif (inner_cond_bb, outer_cond_bb, false);
+ }
+
+ /* And a version where the outer condition is negated. */
+ if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
+ && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
+ && bb_no_side_effects_p (inner_cond_bb))
+ {
+ /* We have
+ <outer_cond_bb>
+ if (q) goto inner_cond_bb; else goto then_bb;
+ <inner_cond_bb>
+ if (q) goto then_bb; else goto ...;
+ <then_bb>
+ ...
+ */
+ return ifcombine_iforif (inner_cond_bb, outer_cond_bb, true);
}
}
return false;
}
/* Main entry for the tree if-conversion pass. */
static unsigned int
tree_ssa_ifcombine (void)
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c (revision 0)
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-trapping-math -fdump-tree-ifcombine" } */
+
+void f ();
+enum Sign { NEG=-1, ZERO, POS };
+
+static inline enum Sign sign (double x)
+{
+ if (x > 0) return POS;
+ if (x < 0) return NEG;
+ return ZERO;
+}
+void g (double x)
+{
+ if (sign (x) == NEG) f();
+}
+
+/* The above should be optimized to x < 0 by ifcombine.
+ The transformation would also be legal with -ftrapping-math. */
+
+/* { dg-final { scan-tree-dump "optimizing.* < " "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
___________________________________________________________________
Added: svn:keywords
+ Author Date Id Revision URL
Added: svn:eol-style
+ native
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c (revision 0)
+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c (revision 0)
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fno-trapping-math -fdump-tree-ifcombine" } */
+
+double test1 (double i, double j)
+{
+ if (i >= j)
+ if (i <= j)
+ goto plif;
+ else
+ goto plouf;
+ else
+ goto plif;
+
+plif:
+ return 0;
+plouf:
+ return -1;
+}
+
+/* The above should be optimized to a i > j test by ifcombine.
+ The transformation would also be legal with -ftrapping-math.
+ Instead we get u<=, which is acceptable with -fno-trapping-math. */
+
+/* { dg-final { scan-tree-dump " u<= " "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
___________________________________________________________________
Added: svn:keywords
+ Author Date Id Revision URL
Added: svn:eol-style
+ native
