Re: [Patch] PR 51938: extend ifcombine

On Wed, 20 Jun 2012, Richard Guenther wrote:
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.glisse@...>

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 Glisse
Index: 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