ifcombine: fold two bit tests with different polarity

Message ID 20221109230815.3240583-1-philipp.tomsich@vrull.eu
State Accepted
Headers
Series ifcombine: fold two bit tests with different polarity |

Checks

Context Check Description
snail/gcc-patch-check success Github commit url

Commit Message

Philipp Tomsich Nov. 9, 2022, 11:08 p.m. UTC
  Our ifcombine pass combines 2 single-bit tests into a single test of
the form "(a & T) == T", requiring the same polarity (i.e., tests for
bit set/cleared) for both bit-tests.  However some applications test
against two bits expecting one set and the other cleared.

This adds support for the case "(a & T) == C" where T is a constant
with 2 bits set and C has only one of those bits set.

gcc/ChangeLog:

	* tree-ssa-ifcombine.cc (ifcombine_ifandif): Add support for
          combining two bit-tests that test for bits of different
          polarity.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/ssa-ifcombine-15.c: New test.

Signed-off-by: Philipp Tomsich <philipp.tomsich@vrull.eu>
---

 .../gcc.dg/tree-ssa/ssa-ifcombine-15.c        | 14 +++++
 gcc/tree-ssa-ifcombine.cc                     | 56 +++++++++++++++++++
 2 files changed, 70 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c
  

Comments

Richard Biener Nov. 10, 2022, 7:02 a.m. UTC | #1
On Thu, 10 Nov 2022, Philipp Tomsich wrote:

> Our ifcombine pass combines 2 single-bit tests into a single test of
> the form "(a & T) == T", requiring the same polarity (i.e., tests for
> bit set/cleared) for both bit-tests.  However some applications test
> against two bits expecting one set and the other cleared.
> 
> This adds support for the case "(a & T) == C" where T is a constant
> with 2 bits set and C has only one of those bits set.
> 
> gcc/ChangeLog:
> 
> 	* tree-ssa-ifcombine.cc (ifcombine_ifandif): Add support for
>           combining two bit-tests that test for bits of different
>           polarity.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/tree-ssa/ssa-ifcombine-15.c: New test.
> 
> Signed-off-by: Philipp Tomsich <philipp.tomsich@vrull.eu>
> ---
> 
>  .../gcc.dg/tree-ssa/ssa-ifcombine-15.c        | 14 +++++
>  gcc/tree-ssa-ifcombine.cc                     | 56 +++++++++++++++++++
>  2 files changed, 70 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c
> 
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c
> new file mode 100644
> index 00000000000..081faa39628
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-ifcombine-details-blocks" } */
> +
> +void sink();
> +
> +void reversed(unsigned char *a)
> +{
> +  if (*a & 0x60)
> +    if (!(*a & 0x02))
> +      g();
> +}
> +
> +/* { dg-final { scan-tree-dump "optimizing double bit test" } } */
> +
> diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
> index cd6331f84db..ea49cc2bff1 100644
> --- a/gcc/tree-ssa-ifcombine.cc
> +++ b/gcc/tree-ssa-ifcombine.cc
> @@ -498,6 +498,62 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
>        return true;
>      }
>  
> +  /* See if we test polarity-reversed single bits 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) == (bit2).  */
> +  else if ((recognize_single_bit_test (inner_cond, &name1, &bit1, !inner_inv)
> +	    && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
> +	    && name1 == name2)
> +	   || (recognize_single_bit_test (inner_cond, &name2, &bit2, inner_inv)
> +	       && recognize_single_bit_test (outer_cond, &name1, &bit1, !outer_inv)
> +	       && name1 == name2))

Instead of explicitely testing for the combinations of !inv and inv can
you make recognize_single_bit_test output whether it recognizes a bit
set or bit clear pattern and then appropriately combine that with
inner_inv/outer_inv to the correct test?  It seems we can handle all cases
just fine?

Thanks,
Richard.

> +    {
> +      tree t, t2, t3;
> +
> +      /* 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),
> +			build_int_cst (TREE_TYPE (name1), 1), bit2);
> +      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
> +      t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
> +				    true, GSI_SAME_STMT);
> +      t3 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
> +      t3 = force_gimple_operand_gsi (&gsi, t3, true, NULL_TREE,
> +				     true, GSI_SAME_STMT);
> +      t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
> +		       boolean_type_node, t2, t3);
> +      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,
> +	outer_inv ? boolean_false_node : boolean_true_node);
> +      update_stmt (outer_cond);
> +
> +      update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
> +
> +      if (dump_file)
> +	{
> +	  fprintf (dump_file, "optimizing double bit test to ");
> +	  print_generic_expr (dump_file, name1);
> +	  fprintf (dump_file, " & T == C\nwith temporary T = (1 << ");
> +	  print_generic_expr (dump_file, bit1);
> +	  fprintf (dump_file, ") | (1 << ");
> +	  print_generic_expr (dump_file, bit2);
> +	  fprintf (dump_file, ")\nand temporary C = (1 << ");
> +	  print_generic_expr (dump_file, bit2);
> +	  fprintf (dump_file, ")\n");
> +	}
> +
> +      return true;
> +    }
> +
>    /* 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.  */
>
  

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c
new file mode 100644
index 00000000000..081faa39628
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-15.c
@@ -0,0 +1,14 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine-details-blocks" } */
+
+void sink();
+
+void reversed(unsigned char *a)
+{
+  if (*a & 0x60)
+    if (!(*a & 0x02))
+      g();
+}
+
+/* { dg-final { scan-tree-dump "optimizing double bit test" } } */
+
diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
index cd6331f84db..ea49cc2bff1 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -498,6 +498,62 @@  ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
       return true;
     }
 
+  /* See if we test polarity-reversed single bits 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) == (bit2).  */
+  else if ((recognize_single_bit_test (inner_cond, &name1, &bit1, !inner_inv)
+	    && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
+	    && name1 == name2)
+	   || (recognize_single_bit_test (inner_cond, &name2, &bit2, inner_inv)
+	       && recognize_single_bit_test (outer_cond, &name1, &bit1, !outer_inv)
+	       && name1 == name2))
+    {
+      tree t, t2, t3;
+
+      /* 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),
+			build_int_cst (TREE_TYPE (name1), 1), bit2);
+      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
+      t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
+				    true, GSI_SAME_STMT);
+      t3 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
+      t3 = force_gimple_operand_gsi (&gsi, t3, true, NULL_TREE,
+				     true, GSI_SAME_STMT);
+      t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
+		       boolean_type_node, t2, t3);
+      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,
+	outer_inv ? boolean_false_node : boolean_true_node);
+      update_stmt (outer_cond);
+
+      update_profile_after_ifcombine (inner_cond_bb, outer_cond_bb);
+
+      if (dump_file)
+	{
+	  fprintf (dump_file, "optimizing double bit test to ");
+	  print_generic_expr (dump_file, name1);
+	  fprintf (dump_file, " & T == C\nwith temporary T = (1 << ");
+	  print_generic_expr (dump_file, bit1);
+	  fprintf (dump_file, ") | (1 << ");
+	  print_generic_expr (dump_file, bit2);
+	  fprintf (dump_file, ")\nand temporary C = (1 << ");
+	  print_generic_expr (dump_file, bit2);
+	  fprintf (dump_file, ")\n");
+	}
+
+      return true;
+    }
+
   /* 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.  */