[PATCH]middle-end: correctly identify the edge taken when condition is true. [PR113287]

[PATCH]middle-end: correctly identify the edge taken when condition is true. [PR113287]

[Tamar Christina]

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

Hi All,

The vectorizer needs to know during early break vectorization whether the edge
that will be taken if the condition is true stays or leaves the loop.

This is because the code assumes that if you take the true branch you exit the
loop.  If you don't exit the loop it has to generate a different condition.

Basically it uses this information to decide whether it's generating a
"any element" or an "all element" check.

Bootstrapped Regtested on aarch64-none-linux-gnu, x86_64-pc-linux-gnu
and no issues with --enable-lto --with-build-config=bootstrap-O3
--enable-checking=release,yes,rtl,extra.

Ok for master?

Thanks,
Tamar

gcc/ChangeLog:

	PR tree-optimization/113287
	* tree-vect-stmts.cc (vectorizable_early_exit): Check the flags on edge
	instead of using BRANCH_EDGE to determine true edge.

gcc/testsuite/ChangeLog:

	PR tree-optimization/113287
	* gcc.dg/vect/vect-early-break_100-pr113287.c: New test.
	* gcc.dg/vect/vect-early-break_99-pr113287.c: New test.

--- inline copy of patch -- 
diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
new file mode 100644
index 0000000000000000000000000000000000000000..f908e5bc60779c148dc95bda3e200383d12b9e1e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
@@ -0,0 +1,35 @@
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target bitint } */
+
+__attribute__((noipa)) void
+bar (unsigned long *p)
+{
+  __builtin_memset (p, 0, 142 * sizeof (unsigned long));
+  p[17] = 0x50000000000UL;
+}
+
+__attribute__((noipa)) int
+foo (void)
+{
+  unsigned long r[142];
+  bar (r);
+  unsigned long v = ((long) r[0] >> 31);
+  if (v + 1 > 1)
+    return 1;
+  for (unsigned long i = 1; i <= 140; ++i)
+    if (r[i] != v)
+      return 1;
+  unsigned long w = r[141];
+  if ((unsigned long) (((long) (w << 60)) >> 60) != v)
+    return 1;
+  return 0;
+}
+
+int
+main ()
+{
+  if (foo () != 1)
+    __builtin_abort ();
+}
diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
new file mode 100644
index 0000000000000000000000000000000000000000..b92a8a268d803ab1656b4716b1a319ed4edc87a3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
@@ -0,0 +1,32 @@
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target bitint } */
+
+_BitInt(998) b;
+char c;
+char d;
+char e;
+char f;
+char g;
+char h;
+char i;
+char j;
+
+void
+foo(char y, _BitInt(9020) a, char *r)
+{
+  char x = __builtin_mul_overflow_p(a << sizeof(a), y, 0);
+  x += c + d + e + f + g + h + i + j + b;
+  *r = x;
+}
+
+int
+main(void)
+{
+  char x;
+  foo(5, 5, &x);
+  if (x != 1)
+    __builtin_abort();
+  return 0;
+}
diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
index 1333d8934783acdb5277e3a03c2b4021fec4777b..da004b0e9e2696cd2ce358d3b221851c7b60b448 100644
--- a/gcc/tree-vect-stmts.cc
+++ b/gcc/tree-vect-stmts.cc
@@ -12870,13 +12870,18 @@ vectorizable_early_exit (vec_info *vinfo, stmt_vec_info stmt_info,
      rewrite conditions to always be a comparison against 0.  To do this it
      sometimes flips the edges.  This is fine for scalar,  but for vector we
      then have to flip the test, as we're still assuming that if you take the
-     branch edge that we found the exit condition.  */
+     branch edge that we found the exit condition.  i.e. we need to know whether
+     we are generating a `forall` or an `exist` condition.  */
   auto new_code = NE_EXPR;
   auto reduc_optab = ior_optab;
   auto reduc_op = BIT_IOR_EXPR;
   tree cst = build_zero_cst (vectype);
+  edge exit_true_edge = EDGE_SUCC (gimple_bb (cond_stmt), 0);
+  if (exit_true_edge->flags & EDGE_FALSE_VALUE)
+    exit_true_edge = EDGE_SUCC (gimple_bb (cond_stmt), 1);
+  gcc_assert (exit_true_edge->flags & EDGE_TRUE_VALUE);
   if (flow_bb_inside_loop_p (LOOP_VINFO_LOOP (loop_vinfo),
-			     BRANCH_EDGE (gimple_bb (cond_stmt))->dest))
+			     exit_true_edge->dest))
     {
       new_code = EQ_EXPR;
       reduc_optab = and_optab;




-- 

[-- Attachment #2: rb18143.patch --]
[-- Type: text/plain, Size: 3308 bytes --]

diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
new file mode 100644
index 0000000000000000000000000000000000000000..f908e5bc60779c148dc95bda3e200383d12b9e1e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
@@ -0,0 +1,35 @@
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target bitint } */
+
+__attribute__((noipa)) void
+bar (unsigned long *p)
+{
+  __builtin_memset (p, 0, 142 * sizeof (unsigned long));
+  p[17] = 0x50000000000UL;
+}
+
+__attribute__((noipa)) int
+foo (void)
+{
+  unsigned long r[142];
+  bar (r);
+  unsigned long v = ((long) r[0] >> 31);
+  if (v + 1 > 1)
+    return 1;
+  for (unsigned long i = 1; i <= 140; ++i)
+    if (r[i] != v)
+      return 1;
+  unsigned long w = r[141];
+  if ((unsigned long) (((long) (w << 60)) >> 60) != v)
+    return 1;
+  return 0;
+}
+
+int
+main ()
+{
+  if (foo () != 1)
+    __builtin_abort ();
+}
diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
new file mode 100644
index 0000000000000000000000000000000000000000..b92a8a268d803ab1656b4716b1a319ed4edc87a3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
@@ -0,0 +1,32 @@
+/* { dg-add-options vect_early_break } */
+/* { dg-require-effective-target vect_early_break } */
+/* { dg-require-effective-target vect_int } */
+/* { dg-require-effective-target bitint } */
+
+_BitInt(998) b;
+char c;
+char d;
+char e;
+char f;
+char g;
+char h;
+char i;
+char j;
+
+void
+foo(char y, _BitInt(9020) a, char *r)
+{
+  char x = __builtin_mul_overflow_p(a << sizeof(a), y, 0);
+  x += c + d + e + f + g + h + i + j + b;
+  *r = x;
+}
+
+int
+main(void)
+{
+  char x;
+  foo(5, 5, &x);
+  if (x != 1)
+    __builtin_abort();
+  return 0;
+}
diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
index 1333d8934783acdb5277e3a03c2b4021fec4777b..da004b0e9e2696cd2ce358d3b221851c7b60b448 100644
--- a/gcc/tree-vect-stmts.cc
+++ b/gcc/tree-vect-stmts.cc
@@ -12870,13 +12870,18 @@ vectorizable_early_exit (vec_info *vinfo, stmt_vec_info stmt_info,
      rewrite conditions to always be a comparison against 0.  To do this it
      sometimes flips the edges.  This is fine for scalar,  but for vector we
      then have to flip the test, as we're still assuming that if you take the
-     branch edge that we found the exit condition.  */
+     branch edge that we found the exit condition.  i.e. we need to know whether
+     we are generating a `forall` or an `exist` condition.  */
   auto new_code = NE_EXPR;
   auto reduc_optab = ior_optab;
   auto reduc_op = BIT_IOR_EXPR;
   tree cst = build_zero_cst (vectype);
+  edge exit_true_edge = EDGE_SUCC (gimple_bb (cond_stmt), 0);
+  if (exit_true_edge->flags & EDGE_FALSE_VALUE)
+    exit_true_edge = EDGE_SUCC (gimple_bb (cond_stmt), 1);
+  gcc_assert (exit_true_edge->flags & EDGE_TRUE_VALUE);
   if (flow_bb_inside_loop_p (LOOP_VINFO_LOOP (loop_vinfo),
-			     BRANCH_EDGE (gimple_bb (cond_stmt))->dest))
+			     exit_true_edge->dest))
     {
       new_code = EQ_EXPR;
       reduc_optab = and_optab;

Re: [PATCH]middle-end: correctly identify the edge taken when condition is true. [PR113287]

[Richard Biener]

On Wed, 10 Jan 2024, Tamar Christina wrote:

> Hi All,
> 
> The vectorizer needs to know during early break vectorization whether the edge
> that will be taken if the condition is true stays or leaves the loop.
> 
> This is because the code assumes that if you take the true branch you exit the
> loop.  If you don't exit the loop it has to generate a different condition.
> 
> Basically it uses this information to decide whether it's generating a
> "any element" or an "all element" check.
> 
> Bootstrapped Regtested on aarch64-none-linux-gnu, x86_64-pc-linux-gnu
> and no issues with --enable-lto --with-build-config=bootstrap-O3
> --enable-checking=release,yes,rtl,extra.
> 
> Ok for master?

OK.

Richard.

> Thanks,
> Tamar
> 
> gcc/ChangeLog:
> 
> 	PR tree-optimization/113287
> 	* tree-vect-stmts.cc (vectorizable_early_exit): Check the flags on edge
> 	instead of using BRANCH_EDGE to determine true edge.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR tree-optimization/113287
> 	* gcc.dg/vect/vect-early-break_100-pr113287.c: New test.
> 	* gcc.dg/vect/vect-early-break_99-pr113287.c: New test.
> 
> --- inline copy of patch -- 
> diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..f908e5bc60779c148dc95bda3e200383d12b9e1e
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
> @@ -0,0 +1,35 @@
> +/* { dg-add-options vect_early_break } */
> +/* { dg-require-effective-target vect_early_break } */
> +/* { dg-require-effective-target vect_int } */
> +/* { dg-require-effective-target bitint } */
> +
> +__attribute__((noipa)) void
> +bar (unsigned long *p)
> +{
> +  __builtin_memset (p, 0, 142 * sizeof (unsigned long));
> +  p[17] = 0x50000000000UL;
> +}
> +
> +__attribute__((noipa)) int
> +foo (void)
> +{
> +  unsigned long r[142];
> +  bar (r);
> +  unsigned long v = ((long) r[0] >> 31);
> +  if (v + 1 > 1)
> +    return 1;
> +  for (unsigned long i = 1; i <= 140; ++i)
> +    if (r[i] != v)
> +      return 1;
> +  unsigned long w = r[141];
> +  if ((unsigned long) (((long) (w << 60)) >> 60) != v)
> +    return 1;
> +  return 0;
> +}
> +
> +int
> +main ()
> +{
> +  if (foo () != 1)
> +    __builtin_abort ();
> +}
> diff --git a/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..b92a8a268d803ab1656b4716b1a319ed4edc87a3
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
> @@ -0,0 +1,32 @@
> +/* { dg-add-options vect_early_break } */
> +/* { dg-require-effective-target vect_early_break } */
> +/* { dg-require-effective-target vect_int } */
> +/* { dg-require-effective-target bitint } */
> +
> +_BitInt(998) b;
> +char c;
> +char d;
> +char e;
> +char f;
> +char g;
> +char h;
> +char i;
> +char j;
> +
> +void
> +foo(char y, _BitInt(9020) a, char *r)
> +{
> +  char x = __builtin_mul_overflow_p(a << sizeof(a), y, 0);
> +  x += c + d + e + f + g + h + i + j + b;
> +  *r = x;
> +}
> +
> +int
> +main(void)
> +{
> +  char x;
> +  foo(5, 5, &x);
> +  if (x != 1)
> +    __builtin_abort();
> +  return 0;
> +}
> diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc
> index 1333d8934783acdb5277e3a03c2b4021fec4777b..da004b0e9e2696cd2ce358d3b221851c7b60b448 100644
> --- a/gcc/tree-vect-stmts.cc
> +++ b/gcc/tree-vect-stmts.cc
> @@ -12870,13 +12870,18 @@ vectorizable_early_exit (vec_info *vinfo, stmt_vec_info stmt_info,
>       rewrite conditions to always be a comparison against 0.  To do this it
>       sometimes flips the edges.  This is fine for scalar,  but for vector we
>       then have to flip the test, as we're still assuming that if you take the
> -     branch edge that we found the exit condition.  */
> +     branch edge that we found the exit condition.  i.e. we need to know whether
> +     we are generating a `forall` or an `exist` condition.  */
>    auto new_code = NE_EXPR;
>    auto reduc_optab = ior_optab;
>    auto reduc_op = BIT_IOR_EXPR;
>    tree cst = build_zero_cst (vectype);
> +  edge exit_true_edge = EDGE_SUCC (gimple_bb (cond_stmt), 0);
> +  if (exit_true_edge->flags & EDGE_FALSE_VALUE)
> +    exit_true_edge = EDGE_SUCC (gimple_bb (cond_stmt), 1);
> +  gcc_assert (exit_true_edge->flags & EDGE_TRUE_VALUE);
>    if (flow_bb_inside_loop_p (LOOP_VINFO_LOOP (loop_vinfo),
> -			     BRANCH_EDGE (gimple_bb (cond_stmt))->dest))
> +			     exit_true_edge->dest))
>      {
>        new_code = EQ_EXPR;
>        reduc_optab = and_optab;
> 
> 
> 
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)

Re: [PATCH]middle-end: correctly identify the edge taken when condition is true. [PR113287]

[Jakub Jelinek]

Hi!

Thanks for fixing it, just testsuite nits.

On Wed, Jan 10, 2024 at 03:22:53PM +0100, Richard Biener wrote:
> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
> > @@ -0,0 +1,35 @@
> > +/* { dg-add-options vect_early_break } */
> > +/* { dg-require-effective-target vect_early_break } */
> > +/* { dg-require-effective-target vect_int } */
> > +/* { dg-require-effective-target bitint } */

This test doesn't need bitint effective target.
But relies on long being 64-bit, otherwise e.g.
0x50000000000UL doesn't need to fit or shifting it by 60 is invalid.
So, maybe use lp64 effective target instead.

> > +
> > +__attribute__((noipa)) void
> > +bar (unsigned long *p)
> > +{
> > +  __builtin_memset (p, 0, 142 * sizeof (unsigned long));
> > +  p[17] = 0x50000000000UL;
> > +}
> > +
> > +  if ((unsigned long) (((long) (w << 60)) >> 60) != v)

> > --- /dev/null
> > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_99-pr113287.c
> > @@ -0,0 +1,32 @@
> > +/* { dg-add-options vect_early_break } */
> > +/* { dg-require-effective-target vect_early_break } */
> > +/* { dg-require-effective-target vect_int } */
> > +/* { dg-require-effective-target bitint } */

bitint effective target just ensures there is some _BitInt support,
but not necessarily 998 or 9020 bit ones.

There are some specific precision bitint effective targets (e.g. bitint575),
what I generally use though is just guard the stuff on __BITINT_MAXWIDTH__ >= NNN.
Perhaps for this testcase you could
#if __BITINT_MAXWIDTH__ >= 998
typedef _BitInt(998) B998;
#else
typedef long long B998;
#endif
#if __BITINT_MAXWIDTH__ >= 9020
typedef _BitInt(9020) B9020;
#else
typedef long long B9020;
#endif
and use the new typedefs in the rest of the test.

	Jakub

RE: [PATCH]middle-end: correctly identify the edge taken when condition is true. [PR113287]

[Tamar Christina]

> -----Original Message-----
> From: Jakub Jelinek <jakub@redhat.com>
> Sent: Wednesday, January 10, 2024 2:42 PM
> To: Tamar Christina <Tamar.Christina@arm.com>; Richard Biener
> <rguenther@suse.de>
> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; jlaw@ventanamicro.com
> Subject: Re: [PATCH]middle-end: correctly identify the edge taken when condition
> is true. [PR113287]
> 
> Hi!
> 
> Thanks for fixing it, just testsuite nits.
> 
> On Wed, Jan 10, 2024 at 03:22:53PM +0100, Richard Biener wrote:
> > > --- /dev/null
> > > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
> > > @@ -0,0 +1,35 @@
> > > +/* { dg-add-options vect_early_break } */
> > > +/* { dg-require-effective-target vect_early_break } */
> > > +/* { dg-require-effective-target vect_int } */
> > > +/* { dg-require-effective-target bitint } */
> 
> This test doesn't need bitint effective target.
> But relies on long being 64-bit, otherwise e.g.
> 0x50000000000UL doesn't need to fit or shifting it by 60 is invalid.
> So, maybe use lp64 effective target instead.

I was thinking about it. Would using effective-target longlong and
changing the constant to ULL instead work?

Thanks,
Tamar

Re: [PATCH]middle-end: correctly identify the edge taken when condition is true. [PR113287]

[Jakub Jelinek]

On Wed, Jan 10, 2024 at 02:45:41PM +0000, Tamar Christina wrote:
> > -----Original Message-----
> > From: Jakub Jelinek <jakub@redhat.com>
> > Sent: Wednesday, January 10, 2024 2:42 PM
> > To: Tamar Christina <Tamar.Christina@arm.com>; Richard Biener
> > <rguenther@suse.de>
> > Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; jlaw@ventanamicro.com
> > Subject: Re: [PATCH]middle-end: correctly identify the edge taken when condition
> > is true. [PR113287]
> > 
> > Hi!
> > 
> > Thanks for fixing it, just testsuite nits.
> > 
> > On Wed, Jan 10, 2024 at 03:22:53PM +0100, Richard Biener wrote:
> > > > --- /dev/null
> > > > +++ b/gcc/testsuite/gcc.dg/vect/vect-early-break_100-pr113287.c
> > > > @@ -0,0 +1,35 @@
> > > > +/* { dg-add-options vect_early_break } */
> > > > +/* { dg-require-effective-target vect_early_break } */
> > > > +/* { dg-require-effective-target vect_int } */
> > > > +/* { dg-require-effective-target bitint } */
> > 
> > This test doesn't need bitint effective target.
> > But relies on long being 64-bit, otherwise e.g.
> > 0x50000000000UL doesn't need to fit or shifting it by 60 is invalid.
> > So, maybe use lp64 effective target instead.
> 
> I was thinking about it. Would using effective-target longlong and
> changing the constant to ULL instead work?

You mean vect_long_long ?  Sure, if you change all the longs in the
test to long longs and UL to ULL...

	Jakub