[PR46761] graphite: fix testing of boundary wrapping

[PR46761] graphite: fix testing of boundary wrapping

[Alexander Monakov]

Hi,

As indicated by the testcase, sometimes Graphite would generate wrong region
guards if UB_ONE overflows, but does not become zero (i.e. it is signed).
The patch changes the corresponding test to use TREE_OVERFLOW flag.

Bootstrapped and regtested on x86_64-linux, OK for trunk?

2010-12-13  Alexander Monakov  <amonakov@ispras.ru>

	PR middle-end/46761
	* graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Use
	TREE_OVERFLOW_P to test overflow.

testsuite:
	* gcc.dg/graphite/pr46761.c: New.

diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index 4894b52..183dde7 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -985,7 +985,7 @@ graphite_create_new_loop_guard (sese region, edge entry_edge,
 			     : PLUS_EXPR, type, ub, one);
 
   /* When ub + 1 wraps around, use lb <= ub.  */
-  if (integer_zerop (ub_one))
+  if (TREE_OVERFLOW_P (ub_one))
     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, lb, ub);
   else
     cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
diff --git a/gcc/testsuite/gcc.dg/graphite/pr46761.c b/gcc/testsuite/gcc.dg/graphite/pr46761.c
new file mode 100644
index 0000000..f45398a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/graphite/pr46761.c
@@ -0,0 +1,22 @@
+/* { dg-do run } */
+/* { dg-options "-O -fgraphite-identity" } */
+
+#define N 128
+
+int
+main ()
+{
+  int arr[N], i, s = 0;
+  for (i = 0; i < N; i++)
+    arr[i] = i;
+
+  for (i = 0; i < N; i++)
+    if (arr[i] != i)
+      __builtin_abort ();
+
+  for (i = 0; i < N; i++)
+    s += arr[i];
+  if (s != (N * (N - 1)) / 2)
+    __builtin_abort ();
+  return 0;
+}

Re: [PR46761] graphite: fix testing of boundary wrapping

[Sebastian Pop]

On Mon, Dec 13, 2010 at 07:40, Alexander Monakov <amonakov@ispras.ru> wrote:
> Hi,
>
> As indicated by the testcase, sometimes Graphite would generate wrong region
> guards if UB_ONE overflows, but does not become zero (i.e. it is signed).
> The patch changes the corresponding test to use TREE_OVERFLOW flag.
>
> Bootstrapped and regtested on x86_64-linux, OK for trunk?
>
> 2010-12-13  Alexander Monakov  <amonakov@ispras.ru>
>
>        PR middle-end/46761
>        * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Use
>        TREE_OVERFLOW_P to test overflow.
>
> testsuite:
>        * gcc.dg/graphite/pr46761.c: New.
>

Ok.  Thanks for fixing this,
Sebastian

Re: [PR46761] graphite: fix testing of boundary wrapping

[Richard Guenther]

2010/12/13 Sebastian Pop <sebpop@gmail.com>:
> On Mon, Dec 13, 2010 at 07:40, Alexander Monakov <amonakov@ispras.ru> wrote:
>> Hi,
>>
>> As indicated by the testcase, sometimes Graphite would generate wrong region
>> guards if UB_ONE overflows, but does not become zero (i.e. it is signed).
>> The patch changes the corresponding test to use TREE_OVERFLOW flag.
>>
>> Bootstrapped and regtested on x86_64-linux, OK for trunk?
>>
>> 2010-12-13  Alexander Monakov  <amonakov@ispras.ru>
>>
>>        PR middle-end/46761
>>        * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Use
>>        TREE_OVERFLOW_P to test overflow.
>>
>> testsuite:
>>        * gcc.dg/graphite/pr46761.c: New.
>>
>
> Ok.  Thanks for fixing this,

Hmm, I don't like new uses of TREE_OVERFLOW checking.  And for
unsigned types it won't be set anyway.

Richard.

> Sebastian
>

Re: [PR46761] graphite: fix testing of boundary wrapping

[Alexander Monakov]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3440 bytes --]



On Mon, 13 Dec 2010, Richard Guenther wrote:

> 2010/12/13 Sebastian Pop <sebpop@gmail.com>:
> > On Mon, Dec 13, 2010 at 07:40, Alexander Monakov <amonakov@ispras.ru> wrote:
> >> Hi,
> >>
> >> As indicated by the testcase, sometimes Graphite would generate wrong region
> >> guards if UB_ONE overflows, but does not become zero (i.e. it is signed).
> >> The patch changes the corresponding test to use TREE_OVERFLOW flag.
> >>
> >> Bootstrapped and regtested on x86_64-linux, OK for trunk?
> >>
> >> 2010-12-13  Alexander Monakov  <amonakov@ispras.ru>
> >>
> >>        PR middle-end/46761
> >>        * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Use
> >>        TREE_OVERFLOW_P to test overflow.
> >>
> >> testsuite:
> >>        * gcc.dg/graphite/pr46761.c: New.
> >>
> >
> > Ok.  Thanks for fixing this,
> 
> Hmm, I don't like new uses of TREE_OVERFLOW checking.  And for
> unsigned types it won't be set anyway.

Thanks.  The following patch changes guard generation so that using unadjusted
UB is preferred (if it's an integer constant or an SSA_NAME).  If it is
neither, it uses the previous behaviour of bumping UB by one and changing the
test.  Bootstrapped and tested with make -k check RUNTESTFLAGS="graphite.exp",
OK for trunk?

2010-12-15  Alexander Monakov  <amonakov@ispras.ru>

        PR middle-end/46761
        * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Prefer
        to use unadjusted UB.

diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
index 4894b52..4725608 100644
--- a/gcc/graphite-clast-to-gimple.c
+++ b/gcc/graphite-clast-to-gimple.c
@@ -975,20 +975,24 @@ graphite_create_new_loop_guard (sese region, edge entry_edge,
 				     newivs_index, params_index);
   tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
 				     newivs_index, params_index);
-  tree one = POINTER_TYPE_P (type) ? size_one_node
-    : fold_convert (type, integer_one_node);
-  /* Adding +1 and using LT_EXPR helps with loop latches that have a
-     loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
-     2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
-     However lb < ub + 1 is false, as expected.  */
-  tree ub_one = fold_build2 (POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR
-			     : PLUS_EXPR, type, ub, one);
-
-  /* When ub + 1 wraps around, use lb <= ub.  */
-  if (integer_zerop (ub_one))
+  /* When ub is simply a constant or a parameter, use lb <= ub.  */
+  if (TREE_CODE (ub) == INTEGER_CST || TREE_CODE (ub) == SSA_NAME)
     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, lb, ub);
   else
-    cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
+    {
+      tree one = (POINTER_TYPE_P (type)
+		  ? size_one_node
+		  : fold_convert (type, integer_one_node));
+      /* Adding +1 and using LT_EXPR helps with loop latches that have a
+	 loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
+	 2^k-1 due to unsigned overflow, and the condition lb <= ub is true,
+	 even if we do not want this.  However lb < ub + 1 is false, as
+	 expected.  */
+      tree ub_one = fold_build2 (POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR
+				 : PLUS_EXPR, type, ub, one);
+
+      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
+    }
 
   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
 

Re: [PR46761] graphite: fix testing of boundary wrapping

[Richard Guenther]

On Wed, Dec 15, 2010 at 4:46 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
>
>
> On Mon, 13 Dec 2010, Richard Guenther wrote:
>
>> 2010/12/13 Sebastian Pop <sebpop@gmail.com>:
>> > On Mon, Dec 13, 2010 at 07:40, Alexander Monakov <amonakov@ispras.ru> wrote:
>> >> Hi,
>> >>
>> >> As indicated by the testcase, sometimes Graphite would generate wrong region
>> >> guards if UB_ONE overflows, but does not become zero (i.e. it is signed).
>> >> The patch changes the corresponding test to use TREE_OVERFLOW flag.
>> >>
>> >> Bootstrapped and regtested on x86_64-linux, OK for trunk?
>> >>
>> >> 2010-12-13  Alexander Monakov  <amonakov@ispras.ru>
>> >>
>> >>        PR middle-end/46761
>> >>        * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Use
>> >>        TREE_OVERFLOW_P to test overflow.
>> >>
>> >> testsuite:
>> >>        * gcc.dg/graphite/pr46761.c: New.
>> >>
>> >
>> > Ok.  Thanks for fixing this,
>>
>> Hmm, I don't like new uses of TREE_OVERFLOW checking.  And for
>> unsigned types it won't be set anyway.
>
> Thanks.  The following patch changes guard generation so that using unadjusted
> UB is preferred (if it's an integer constant or an SSA_NAME).  If it is
> neither, it uses the previous behaviour of bumping UB by one and changing the
> test.  Bootstrapped and tested with make -k check RUNTESTFLAGS="graphite.exp",
> OK for trunk?

That looks better.

Thanks,
Richard.

> 2010-12-15  Alexander Monakov  <amonakov@ispras.ru>
>
>         PR middle-end/46761
>         * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Prefer
>         to use unadjusted UB.
>
> diff --git a/gcc/graphite-clast-to-gimple.c b/gcc/graphite-clast-to-gimple.c
> index 4894b52..4725608 100644
> --- a/gcc/graphite-clast-to-gimple.c
> +++ b/gcc/graphite-clast-to-gimple.c
> @@ -975,20 +975,24 @@ graphite_create_new_loop_guard (sese region, edge entry_edge,
>                                     newivs_index, params_index);
>   tree ub = clast_to_gcc_expression (type, stmt->UB, region, newivs,
>                                     newivs_index, params_index);
> -  tree one = POINTER_TYPE_P (type) ? size_one_node
> -    : fold_convert (type, integer_one_node);
> -  /* Adding +1 and using LT_EXPR helps with loop latches that have a
> -     loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
> -     2^{32|64}, and the condition lb <= ub is true, even if we do not want this.
> -     However lb < ub + 1 is false, as expected.  */
> -  tree ub_one = fold_build2 (POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR
> -                            : PLUS_EXPR, type, ub, one);
> -
> -  /* When ub + 1 wraps around, use lb <= ub.  */
> -  if (integer_zerop (ub_one))
> +  /* When ub is simply a constant or a parameter, use lb <= ub.  */
> +  if (TREE_CODE (ub) == INTEGER_CST || TREE_CODE (ub) == SSA_NAME)
>     cond_expr = fold_build2 (LE_EXPR, boolean_type_node, lb, ub);
>   else
> -    cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
> +    {
> +      tree one = (POINTER_TYPE_P (type)
> +                 ? size_one_node
> +                 : fold_convert (type, integer_one_node));
> +      /* Adding +1 and using LT_EXPR helps with loop latches that have a
> +        loop iteration count of "PARAMETER - 1".  For PARAMETER == 0 this becomes
> +        2^k-1 due to unsigned overflow, and the condition lb <= ub is true,
> +        even if we do not want this.  However lb < ub + 1 is false, as
> +        expected.  */
> +      tree ub_one = fold_build2 (POINTER_TYPE_P (type) ? POINTER_PLUS_EXPR
> +                                : PLUS_EXPR, type, ub, one);
> +
> +      cond_expr = fold_build2 (LT_EXPR, boolean_type_node, lb, ub_one);
> +    }
>
>   exit_edge = create_empty_if_region_on_edge (entry_edge, cond_expr);
>
>

Re: [PR46761] graphite: fix testing of boundary wrapping

[Alexander Monakov]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 713 bytes --]



On Thu, 16 Dec 2010, Richard Guenther wrote:

> > Thanks.  The following patch changes guard generation so that using unadjusted
> > UB is preferred (if it's an integer constant or an SSA_NAME).  If it is
> > neither, it uses the previous behaviour of bumping UB by one and changing the
> > test.  Bootstrapped and tested with make -k check RUNTESTFLAGS="graphite.exp",
> > OK for trunk?
> 
> That looks better.
> 
> Thanks,
> Richard.

Sebastian, is this patch OK to commit?  
 
> > 2010-12-15  Alexander Monakov  <amonakov@ispras.ru>
> >
> >         PR middle-end/46761
> >         * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Prefer
> >         to use unadjusted UB.
> >

Re: [PR46761] graphite: fix testing of boundary wrapping

[Sebastian Pop]

On Thu, Dec 16, 2010 at 15:50, Alexander Monakov <amonakov@ispras.ru> wrote:
>
>
> On Thu, 16 Dec 2010, Richard Guenther wrote:
>
>> > Thanks.  The following patch changes guard generation so that using unadjusted
>> > UB is preferred (if it's an integer constant or an SSA_NAME).  If it is
>> > neither, it uses the previous behaviour of bumping UB by one and changing the
>> > test.  Bootstrapped and tested with make -k check RUNTESTFLAGS="graphite.exp",
>> > OK for trunk?
>>
>> That looks better.
>>
>> Thanks,
>> Richard.
>
> Sebastian, is this patch OK to commit?

Yes, please commit the patch to trunk.  Thanks for fixing this bug.

Sebastian

>
>> > 2010-12-15  Alexander Monakov  <amonakov@ispras.ru>
>> >
>> >         PR middle-end/46761
>> >         * graphite-clast-to-gimple.c (graphite_create_new_loop_guard): Prefer
>> >         to use unadjusted UB.
>> >