[PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 574 bytes --]

Hi,

Please find attached the patch PR25530.patch that converts the pattern:-
(unsigned / 2) * 2 is into (unsigned & ~1).

Please review and let me know if its okay.

Regression tested on AARH64 and x86_64.

Thanks,
Naveen

gcc/testsuite/ChangeLog:

2015-07-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

	PR middle-end/25530
	* gcc.dg/pr25530.c: New test.

gcc/ChangeLog:

2015-07-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

	PR middle-end/25530
	* match.pd (mult (div @0 INTEGER_CST@1) INTEGER_CST@1) : 
	New simplifier.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: PR25530.patch --]
[-- Type: text/x-patch; name="PR25530.patch", Size: 1196 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index 53e911a..2c9e408 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -529,6 +529,17 @@ along with GCC; see the file COPYING3.  If not see
   (bitop (bit_and:c @0 @1) (bit_and @2 @1))
   (bit_and (bitop @0 @2) @1)))
 
+/* Simplify (unsigned t / 2) * 2 -> unsigned t & ~1.  */
+/* PR25530.  */
+(for div (trunc_div ceil_div floor_div round_div exact_div)
+ (simplify
+  (mult (div @0 INTEGER_CST@1) INTEGER_CST@1)
+  (with { tree n2 = build_int_cst (TREE_TYPE (@0),
+				   wi::exact_log2 (@1)); }
+  (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
+   (bit_and @0 (lshift (rshift { build_minus_one_cst (TREE_TYPE (@0)); }
+			       { n2; }) { n2; }))))))
+
 /* (x | CST1) & CST2 -> (x & CST2) | (CST1 & CST2) */
 (simplify
   (bit_and (bit_ior @0 CONSTANT_CLASS_P@1) CONSTANT_CLASS_P@2)
diff --git a/gcc/testsuite/gcc.dg/pr25530.c b/gcc/testsuite/gcc.dg/pr25530.c
new file mode 100644
index 0000000..61e19cc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr25530.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+f (unsigned t)
+{
+  return (t / 2) * 2;
+}
+
+/* { dg-final { scan-tree-dump "\& -2" "optimized" } } */

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Richard Biener]

On Tue, Jul 7, 2015 at 6:52 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
> Please find attached the patch PR25530.patch that converts the pattern:-
> (unsigned / 2) * 2 is into (unsigned & ~1).
>
> Please review and let me know if its okay.

For EXACT_DIV fold-const.c has

          /* ((T) (X /[ex] C)) * C cancels out if the conversion is
             sign-changing only.  */
          if (TREE_CODE (arg1) == INTEGER_CST
              && TREE_CODE (arg0) == EXACT_DIV_EXPR
              && operand_equal_p (arg1, TREE_OPERAND (arg0, 1), 0))
            return fold_convert_loc (loc, type, TREE_OPERAND (arg0, 0));

we know the remainder is zero for EXACT_DIV.  It also gives hints that
a sign-changing conversion is ok.

+/* Simplify (unsigned t / 2) * 2 -> unsigned t & ~1.  */
+/* PR25530.  */
+(for div (trunc_div ceil_div floor_div round_div exact_div)
+ (simplify
+  (mult (div @0 INTEGER_CST@1) INTEGER_CST@1)
+  (with { tree n2 = build_int_cst (TREE_TYPE (@0),
+                                  wi::exact_log2 (@1)); }
+  (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
+   (bit_and @0 (lshift (rshift { build_minus_one_cst (TREE_TYPE (@0)); }
+                              { n2; }) { n2; }))))))

you should move the (with inside the (if to save work if the type is not
unsigned.  Also you are using wi::exact_log2 without checking whether
@1 was a power of two (I think exact_log2 returns -1 in this case).
Then expressing ~1 with the result expression is really excessive - you
should simply build this with @1 - 1 if @1 is a power of two.

So please handle exact_div differently, like fold-const.c does.

Also I am not sure ceil_div and floor_div can be handled this way.
(5 /[ceil] 2) * 2 == 6 but you compute it as 4.  So I am only convinced
trunc_div works this way.

Thanks,
Richard.

> Regression tested on AARH64 and x86_64.
>
> Thanks,
> Naveen
>
> gcc/testsuite/ChangeLog:
>
> 2015-07-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         PR middle-end/25530
>         * gcc.dg/pr25530.c: New test.
>
> gcc/ChangeLog:
>
> 2015-07-07  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         PR middle-end/25530
>         * match.pd (mult (div @0 INTEGER_CST@1) INTEGER_CST@1) :
>         New simplifier.

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Paolo Bonzini]

On 07/07/2015 11:08, Richard Biener wrote:
> Also I am not sure ceil_div and floor_div can be handled this way.
> (5 /[ceil] 2) * 2 == 6 but you compute it as 4.  So I am only convinced
> trunc_div works this way.

Of course also floor_div for unsigned arguments.

For signed arguments, ceil_div works if the operand is known-negative
and floor_div if known-positive.

Perhaps you could optimize these cases to trunc_div first (or maybe it's
already done...)?

Paolo

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Richard Biener]

On Thu, Jul 9, 2015 at 8:35 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
>
>
> On 07/07/2015 11:08, Richard Biener wrote:
>> Also I am not sure ceil_div and floor_div can be handled this way.
>> (5 /[ceil] 2) * 2 == 6 but you compute it as 4.  So I am only convinced
>> trunc_div works this way.
>
> Of course also floor_div for unsigned arguments.
>
> For signed arguments, ceil_div works if the operand is known-negative
> and floor_div if known-positive.
>
> Perhaps you could optimize these cases to trunc_div first (or maybe it's
> already done...)?

fold-const.c does this already, yes.

Richard.

> Paolo

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 839 bytes --]

Hi,

>> handle exact_div differently, like fold-const.c does.
>> Then expressing ~1 with the result expression is really excessive - you
>> should simply build this with @1 - 1 if @1 is a power of two.

Thanks for the review and comments.

Please find attached the modified patch as per your comments.

Please review the same and let me know if any further modifications are required.

Regression Tested on X86_64.

Thanks,
Naveen

gcc/testsuite/ChangeLog:

2015-07-21  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

	PR middle-end/25530
	* gcc.dg/pr25530.c: New test.

gcc/ChangeLog:

2015-07-21  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

	PR middle-end/25530
	* match.pd (mult (exact_div @0 INTEGET_CST@1) @1) : 	New simplifier.
	(mult (trunc_div @0 integer_pow2p@1) @1) : New simplifier.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: pr25530.patch --]
[-- Type: text/x-patch; name="pr25530.patch", Size: 883 bytes --]

--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -280,6 +280,15 @@ along with GCC; see the file COPYING3.  If not see
 	&& integer_pow2p (@2) && tree_int_cst_sgn (@2) > 0)
    (bit_and @0 (convert (minus @1 { build_int_cst (TREE_TYPE (@1), 1); }))))))
 
+/* Simplify (unsigned t / 2) * 2 -> unsigned t & ~1.  */
+(simplify
+ (mult (exact_div @0 INTEGET_CST@1) @1)
+  @0)
+
+(simplify
+ (mult (trunc_div @0 integer_pow2p@1) @1)
+  (bit_and @0 (negate @1)))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
new file mode 100644
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr25530.c
@@ -0,0 +1,14 @@
+new file mode 100644
+--- /dev/null
++++ b/gcc/testsuite/gcc.dg/pr25530.c
+@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+f (unsigned t)
+{
+  return (t / 2) * 2;
+}
+
+/* { dg-final { scan-tree-dump "\& -2" "optimized" } } */

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Richard Biener]

On Tue, Jul 21, 2015 at 11:16 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
> Hi,
>
>>> handle exact_div differently, like fold-const.c does.
>>> Then expressing ~1 with the result expression is really excessive - you
>>> should simply build this with @1 - 1 if @1 is a power of two.

(*)

> Thanks for the review and comments.
>
> Please find attached the modified patch as per your comments.
>
> Please review the same and let me know if any further modifications are required.
>
> Regression Tested on X86_64.

We already have

+(simplify
+ (mult (exact_div @0 INTEGET_CST@1) @1)
+  @0)

as

/* (X /[ex] A) * A -> X.  */
(simplify
  (mult (convert? (exact_div @0 @1)) @1)
  /* Look through a sign-changing conversion.  */
  (convert @0))

as before the comment applies to your second pattern.

+(simplify
+ (mult (trunc_div @0 integer_pow2p@1) @1)
+  (bit_and @0 (negate @1)))

This doesn't work for signed types at least.
-1 / 2 * 2 == 0, not -2.  Your previous patch correctly
restricted this to unsigned types.

Thanks,
Richard.

> Thanks,
> Naveen
>
> gcc/testsuite/ChangeLog:
>
> 2015-07-21  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         PR middle-end/25530
>         * gcc.dg/pr25530.c: New test.
>
> gcc/ChangeLog:
>
> 2015-07-21  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
>         PR middle-end/25530
>         * match.pd (mult (exact_div @0 INTEGET_CST@1) @1) :     New simplifier.
>         (mult (trunc_div @0 integer_pow2p@1) @1) : New simplifier.

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Hurugalawadi, Naveen]

[-- Attachment #1: Type: text/plain, Size: 535 bytes --]

>> Your previous patch correctly restricted this to unsigned types.

Thanks for your review and comments.

Please find attached the modified patch as per your comments.

Please let me know if this version is okay?

Thanks,
Naveen

2015-07-22  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>

gcc/testsuite/ChangeLog:
         PR middle-end/25530
         * gcc.dg/pr25530.c: New test.

 gcc/ChangeLog:
         PR middle-end/25530
         * match.pd (mult (trunc_div @0 integer_pow2p@1) @1) : New simplifier.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: pr25530.patch --]
[-- Type: text/x-patch; name="pr25530.patch", Size: 1247 bytes --]

diff --git a/gcc/match.pd b/gcc/match.pd
index 9a66f52..6c37a20 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -29,7 +29,8 @@ along with GCC; see the file COPYING3.  If not see
    integer_each_onep integer_truep
    real_zerop real_onep real_minus_onep
    CONSTANT_CLASS_P
-   tree_expr_nonnegative_p)
+   tree_expr_nonnegative_p
+   integer_pow2p)
 
 /* Operator lists.  */
 (define_operator_list tcc_comparison
@@ -280,6 +281,12 @@ along with GCC; see the file COPYING3.  If not see
 	&& integer_pow2p (@2) && tree_int_cst_sgn (@2) > 0)
    (bit_and @0 (convert (minus @1 { build_int_cst (TREE_TYPE (@1), 1); }))))))
 
+/* Simplify (unsigned t / 2) * 2 -> unsigned t & ~1.  */
+(simplify
+ (mult (trunc_div @0 integer_pow2p@1) @1)
+ (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
+  (bit_and @0 (negate @1))))
+
 /* X % Y is smaller than Y.  */
 (for cmp (lt ge)
  (simplify
diff --git a/gcc/testsuite/gcc.dg/pr25530.c b/gcc/testsuite/gcc.dg/pr25530.c
new file mode 100644
index 0000000..f180768
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr25530.c
@@ -0,0 +1,10 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+int
+f (unsigned t)
+{
+  return (t / 2) * 2;
+}
+
+/* { dg-final { scan-tree-dump "\& -2" "optimized" } } */

Re: [PR25530] Convert (unsigned t / 2) * 2 into (unsigned t & ~1)

[Richard Biener]

On Thu, Jul 23, 2015 at 5:49 AM, Hurugalawadi, Naveen
<Naveen.Hurugalawadi@caviumnetworks.com> wrote:
>>> Your previous patch correctly restricted this to unsigned types.
>
> Thanks for your review and comments.
>
> Please find attached the modified patch as per your comments.
>
> Please let me know if this version is okay?

Ok.

Thanks,
Richard.

> Thanks,
> Naveen
>
> 2015-07-22  Naveen H.S  <Naveen.Hurugalawadi@caviumnetworks.com>
>
> gcc/testsuite/ChangeLog:
>          PR middle-end/25530
>          * gcc.dg/pr25530.c: New test.
>
>  gcc/ChangeLog:
>          PR middle-end/25530
>          * match.pd (mult (trunc_div @0 integer_pow2p@1) @1) : New simplifier.