[PATCH 1/3] MATCH: Allow unsigned types for `X & -Y -> X * Y` pattern

[PATCH 1/3] MATCH: Allow unsigned types for `X & -Y -> X * Y` pattern

[Andrew Pinski]

This allows unsigned types if the inner type where the negation is
located has greater than or equal to precision than the outer type.

branchless-cond.c needs to be updated since now we change it to
use a multiply rather than still having (-a)&c in there.

OK? Bootstrapped and tested on x86_64-linux-gnu.

gcc/ChangeLog:

	* match.pd (`X & -Y -> X * Y`): Allow for truncation
	and the same type for unsigned types.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/branchless-cond.c: Update testcase.
---
 gcc/match.pd                                    | 5 ++++-
 gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c | 6 +++---
 2 files changed, 7 insertions(+), 4 deletions(-)

diff --git a/gcc/match.pd b/gcc/match.pd
index 4ad037d641a..7b95b63cee4 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -2058,7 +2058,10 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
  (if (INTEGRAL_TYPE_P (type)
       && INTEGRAL_TYPE_P (TREE_TYPE (@0))
       && TREE_CODE (TREE_TYPE (@0)) != BOOLEAN_TYPE
-      && !TYPE_UNSIGNED (TREE_TYPE (@0)))
+      /* Sign extending of the neg or a truncation of the neg
+         is needed. */
+      && (!TYPE_UNSIGNED (TREE_TYPE (@0))
+	  || TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@0))))
   (mult (convert @0) @1)))
 
 /* Narrow integer multiplication by a zero_one_valued_p operand.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c
index 68087ae6568..e063dc4bb5f 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond.c
@@ -21,6 +21,6 @@ int f4(unsigned int x, unsigned int y, unsigned int z)
   return ((x & 1) != 0) ? z | y : y;
 }
 
-/* { dg-final { scan-tree-dump-times " -" 4 "optimized" } } */
-/* { dg-final { scan-tree-dump-times " & " 8 "optimized" } } */
-/* { dg-final { scan-tree-dump-not "if" "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\\*" 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "if " "optimized" } } */
-- 
2.31.1

[PATCH 2/3] Change the `zero_one ==/!= 0) ? y : z <op> y` patterns to use multiply rather than `(-zero_one) & z`

[Andrew Pinski]

Since there is a pattern to convert `(-zero_one) & z` into `zero_one * z` already,
it is better if we don't do a secondary transformation. This reduces the extra
statements produced by match-and-simplify on the gimple level too.

gcc/ChangeLog:

	* match.pd (`zero_one ==/!= 0) ? y : z <op> y`): Use
	multiply rather than negation/bit_and.
---
 gcc/match.pd | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/gcc/match.pd b/gcc/match.pd
index 7b95b63cee4..c38b39fb45c 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3688,7 +3688,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (cond (le @0 integer_zerop@1) (negate@2 @0) integer_zerop@1)
   (max @2 @1))
 
-/* (zero_one == 0) ? y : z <op> y -> (-(typeof(y))zero_one & z) <op> y */
+/* (zero_one == 0) ? y : z <op> y -> ((typeof(y))zero_one * z) <op> y */
 (for op (bit_xor bit_ior)
  (simplify
   (cond (eq zero_one_valued_p@0
@@ -3698,9 +3698,9 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (INTEGRAL_TYPE_P (type)
        && TYPE_PRECISION (type) > 1
        && (INTEGRAL_TYPE_P (TREE_TYPE (@0))))
-       (op (bit_and (negate (convert:type @0)) @2) @1))))
+       (op (mult (convert:type @0) @2) @1))))
 
-/* (zero_one != 0) ? z <op> y : y -> (-(typeof(y))zero_one & z) <op> y */
+/* (zero_one != 0) ? z <op> y : y -> ((typeof(y))zero_one * z) <op> y */
 (for op (bit_xor bit_ior)
  (simplify
   (cond (ne zero_one_valued_p@0
@@ -3710,7 +3710,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (INTEGRAL_TYPE_P (type)
        && TYPE_PRECISION (type) > 1
        && (INTEGRAL_TYPE_P (TREE_TYPE (@0))))
-       (op (bit_and (negate (convert:type @0)) @2) @1))))
+       (op (mult (convert:type @0) @2) @1))))
 
 /* Simplifications of shift and rotates.  */
 
-- 
2.31.1

[PATCH 3/3] Add Plus to the op list of `(zero_one == 0) ? y : z <op> y` pattern

[Andrew Pinski]

This adds plus to the op list of `(zero_one == 0) ? y : z <op> y` patterns
which currently has bit_ior and bit_xor.
This shows up now in GCC after the boolization work that Uroš has been doing.

OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

	PR tree-optimization/97711
	PR tree-optimization/110155

gcc/ChangeLog:

	* match.pd ((zero_one == 0) ? y : z <op> y): Add plus to the op.
	((zero_one != 0) ? z <op> y : y): Likewise.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/branchless-cond-add-2.c: New test.
	* gcc.dg/tree-ssa/branchless-cond-add.c: New test.
---
 gcc/match.pd                                   |  4 ++--
 .../gcc.dg/tree-ssa/branchless-cond-add-2.c    |  8 ++++++++
 .../gcc.dg/tree-ssa/branchless-cond-add.c      | 18 ++++++++++++++++++
 3 files changed, 28 insertions(+), 2 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add-2.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add.c

diff --git a/gcc/match.pd b/gcc/match.pd
index c38b39fb45c..f633271f76c 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3689,7 +3689,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (max @2 @1))
 
 /* (zero_one == 0) ? y : z <op> y -> ((typeof(y))zero_one * z) <op> y */
-(for op (bit_xor bit_ior)
+(for op (bit_xor bit_ior plus)
  (simplify
   (cond (eq zero_one_valued_p@0
             integer_zerop)
@@ -3701,7 +3701,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
        (op (mult (convert:type @0) @2) @1))))
 
 /* (zero_one != 0) ? z <op> y : y -> ((typeof(y))zero_one * z) <op> y */
-(for op (bit_xor bit_ior)
+(for op (bit_xor bit_ior plus)
  (simplify
   (cond (ne zero_one_valued_p@0
             integer_zerop)
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add-2.c b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add-2.c
new file mode 100644
index 00000000000..27607e10f88
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add-2.c
@@ -0,0 +1,8 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/97711 */
+
+int f (int x) { return x & 1 ? x - 1 : x; }
+
+/* { dg-final { scan-tree-dump-times " & -2" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "if " "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add.c b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add.c
new file mode 100644
index 00000000000..0d81c07b03a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/branchless-cond-add.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* PR tree-optimization/110155 */
+
+int f1(unsigned int x, unsigned int y, unsigned int z)
+{
+  return ((x & 1) == 0) ? y : z + y;
+}
+
+int f2(unsigned int x, unsigned int y, unsigned int z)
+{
+  return ((x & 1) != 0) ? z + y : y;
+}
+
+/* { dg-final { scan-tree-dump-times " \\\*" 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " \\\+ " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-times " & " 2 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "if " "optimized" } } */
-- 
2.31.1

Re: [PATCH 1/3] MATCH: Allow unsigned types for `X & -Y -> X * Y` pattern

[Jeff Law]

On 6/7/23 15:32, Andrew Pinski via Gcc-patches wrote:
> This allows unsigned types if the inner type where the negation is
> located has greater than or equal to precision than the outer type.
> 
> branchless-cond.c needs to be updated since now we change it to
> use a multiply rather than still having (-a)&c in there.
> 
> OK? Bootstrapped and tested on x86_64-linux-gnu.
> 
> gcc/ChangeLog:
> 
> 	* match.pd (`X & -Y -> X * Y`): Allow for truncation
> 	and the same type for unsigned types.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/tree-ssa/branchless-cond.c: Update testcase.
OK.
jeff

Re: [PATCH 2/3] Change the `zero_one ==/!= 0) ? y : z <op> y` patterns to use multiply rather than `(-zero_one) & z`

[Jeff Law]

On 6/7/23 15:32, Andrew Pinski via Gcc-patches wrote:
> Since there is a pattern to convert `(-zero_one) & z` into `zero_one * z` already,
> it is better if we don't do a secondary transformation. This reduces the extra
> statements produced by match-and-simplify on the gimple level too.
> 
> gcc/ChangeLog:
> 
> 	* match.pd (`zero_one ==/!= 0) ? y : z <op> y`): Use
> 	multiply rather than negation/bit_and.
Don't you need to check the types in a manner similar to what the A & -Y 
-> X * Y pattern does before you make this transformation?

jeff

Re: [PATCH 2/3] Change the `zero_one ==/!= 0) ? y : z <op> y` patterns to use multiply rather than `(-zero_one) & z`

[Andrew Pinski]

On Wed, Jun 7, 2023 at 3:57 PM Jeff Law via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 6/7/23 15:32, Andrew Pinski via Gcc-patches wrote:
> > Since there is a pattern to convert `(-zero_one) & z` into `zero_one * z` already,
> > it is better if we don't do a secondary transformation. This reduces the extra
> > statements produced by match-and-simplify on the gimple level too.
> >
> > gcc/ChangeLog:
> >
> >       * match.pd (`zero_one ==/!= 0) ? y : z <op> y`): Use
> >       multiply rather than negation/bit_and.
> Don't you need to check the types in a manner similar to what the A & -Y
> -> X * Y pattern does before you make this transformation?

No, because the convert is in a different order than in that
transformation; a very subtle difference which makes it work.

In A & -Y it was matching:
(bit_and  (convert? (negate
But here we have:
(bit_and (negate (convert
Notice the convert is in a different location, in the `A & -Y` case,
the convert needs to be a sign extending (or a truncation) of the
negative value. Here we are converting the one_zero_value to the new
type so we get zero_one in the new type and then doing the negation
getting us 0 or -1 value.

Thanks,
Andrew

>
> jeff
>

Re: [PATCH 2/3] Change the `zero_one ==/!= 0) ? y : z <op> y` patterns to use multiply rather than `(-zero_one) & z`

[Jeff Law]

On 6/7/23 17:05, Andrew Pinski wrote:
> On Wed, Jun 7, 2023 at 3:57 PM Jeff Law via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>>
>>
>> On 6/7/23 15:32, Andrew Pinski via Gcc-patches wrote:
>>> Since there is a pattern to convert `(-zero_one) & z` into `zero_one * z` already,
>>> it is better if we don't do a secondary transformation. This reduces the extra
>>> statements produced by match-and-simplify on the gimple level too.
>>>
>>> gcc/ChangeLog:
>>>
>>>        * match.pd (`zero_one ==/!= 0) ? y : z <op> y`): Use
>>>        multiply rather than negation/bit_and.
>> Don't you need to check the types in a manner similar to what the A & -Y
>> -> X * Y pattern does before you make this transformation?
> 
> No, because the convert is in a different order than in that
> transformation; a very subtle difference which makes it work.
> 
> In A & -Y it was matching:
> (bit_and  (convert? (negate
> But here we have:
> (bit_and (negate (convert
> Notice the convert is in a different location, in the `A & -Y` case,
> the convert needs to be a sign extending (or a truncation) of the
> negative value. Here we are converting the one_zero_value to the new
> type so we get zero_one in the new type and then doing the negation
> getting us 0 or -1 value.
THanks for the clarification.  OK for the trunk.

jeff

Re: [PATCH 3/3] Add Plus to the op list of `(zero_one == 0) ? y : z <op> y` pattern

[Jeff Law]

On 6/7/23 15:32, Andrew Pinski via Gcc-patches wrote:
> This adds plus to the op list of `(zero_one == 0) ? y : z <op> y` patterns
> which currently has bit_ior and bit_xor.
> This shows up now in GCC after the boolization work that Uroš has been doing.
> 
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
> 
> 	PR tree-optimization/97711
> 	PR tree-optimization/110155
> 
> gcc/ChangeLog:
> 
> 	* match.pd ((zero_one == 0) ? y : z <op> y): Add plus to the op.
> 	((zero_one != 0) ? z <op> y : y): Likewise.
> 
> gcc/testsuite/ChangeLog:
> 
> 	* gcc.dg/tree-ssa/branchless-cond-add-2.c: New test.
> 	* gcc.dg/tree-ssa/branchless-cond-add.c: New test.
OK
jeff

Re: [PATCH 2/3] Change the `zero_one ==/!= 0) ? y : z <op> y` patterns to use multiply rather than `(-zero_one) & z`

[Andrew Pinski]

On Wed, Jun 7, 2023 at 4:11 PM Jeff Law <jeffreyalaw@gmail.com> wrote:
>
>
>
> On 6/7/23 17:05, Andrew Pinski wrote:
> > On Wed, Jun 7, 2023 at 3:57 PM Jeff Law via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >>
> >>
> >>
> >> On 6/7/23 15:32, Andrew Pinski via Gcc-patches wrote:
> >>> Since there is a pattern to convert `(-zero_one) & z` into `zero_one * z` already,
> >>> it is better if we don't do a secondary transformation. This reduces the extra
> >>> statements produced by match-and-simplify on the gimple level too.
> >>>
> >>> gcc/ChangeLog:
> >>>
> >>>        * match.pd (`zero_one ==/!= 0) ? y : z <op> y`): Use
> >>>        multiply rather than negation/bit_and.
> >> Don't you need to check the types in a manner similar to what the A & -Y
> >> -> X * Y pattern does before you make this transformation?
> >
> > No, because the convert is in a different order than in that
> > transformation; a very subtle difference which makes it work.
> >
> > In A & -Y it was matching:
> > (bit_and  (convert? (negate
> > But here we have:
> > (bit_and (negate (convert
> > Notice the convert is in a different location, in the `A & -Y` case,
> > the convert needs to be a sign extending (or a truncation) of the
> > negative value. Here we are converting the one_zero_value to the new
> > type so we get zero_one in the new type and then doing the negation
> > getting us 0 or -1 value.
> THanks for the clarification.  OK for the trunk.

So even though my transformation is correct based on what was done in
match.pd but that was broken already for signed one bit integers:
```
struct s
{
  int t : 1;
};
int f(struct s t, int a, int b)
{
        int bd = t.t;
        if (bd) a|=b;
        return a;
}
```
I am going to withdraw this patch and fix that up first.

Thanks,
Andrew

>
> jeff