[PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Sebastian Pop]

"Bug 47594 - gfortran.dg/vect/vect-5.f90 execution test fails when
compiled with -O2 -fgraphite-identity"

The problem is due to the fact that Graphite generates this loop:

    for (scat_3=0;scat_3<=4294967295*scat_1+T_51-1;scat_3++) {
      S6(scat_1,scat_3);
    }

that has a "-1" encoded as an unsigned "4294967295".  This constant
comes from the computation of the number of iterations "M - I" of
the inner loop:

        do I = 1, N
          do J = I, M
            A(J,2) = B(J)
          end do
        end do

The patch fixes the problem by sign-extending the constants for the
step of a chain of recurrence in scan_tree_for_params_right_scev.

The same patter could occur for multiplication by a scalar, like in
"-1 * N" and so the patch also fixes these cases in
scan_tree_for_params.

Bootstrapped and tested on amd64-linux.

2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>

	PR middle-end/47594
	* graphite-sese-to-poly.c (scan_tree_for_params_right_scev): Sign
	extend constants.
	(scan_tree_for_params): Same.

	* gfortran.dg/graphite/run-id-pr47594.f90: New.
---
 gcc/ChangeLog                                      |    7 ++++
 gcc/graphite-sese-to-poly.c                        |   26 ++++++++++++--
 gcc/testsuite/ChangeLog                            |    5 +++
 .../gfortran.dg/graphite/run-id-pr47594.f90        |   35 ++++++++++++++++++++
 4 files changed, 69 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 65676cb..f7e2f7d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,12 @@
 2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR middle-end/47594
+	* graphite-sese-to-poly.c (scan_tree_for_params_right_scev): Sign
+	extend constants.
+	(scan_tree_for_params): Same.
+
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
 	* tree-ssa-loop-manip.c (canonicalize_loop_ivs): Build an unsigned
 	iv only when the largest type is unsigned.  Do not call
 	lang_hooks.types.type_for_size.
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 7e23c9d..5c9e984 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -633,7 +633,11 @@ scan_tree_for_params_right_scev (sese s, tree e, int var,
       gcc_assert (TREE_CODE (e) == INTEGER_CST);
 
       mpz_init (val);
-      tree_int_to_gmp (e, val);
+
+      /* Necessary to not get "-1 = 2^n - 1". */
+      mpz_set_double_int
+	(val, double_int_sext (tree_to_double_int (e),
+			       TYPE_PRECISION (TREE_TYPE (e))), false);
       add_value_to_dim (l, expr, val);
       mpz_clear (val);
     }
@@ -729,9 +733,16 @@ scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
 	  if (c)
 	    {
 	      mpz_t val;
-	      gcc_assert (host_integerp (TREE_OPERAND (e, 1), 0));
+	      tree cst = TREE_OPERAND (e, 1);
+
+	      gcc_assert (host_integerp (cst, 0));
 	      mpz_init (val);
-	      tree_int_to_gmp (TREE_OPERAND (e, 1), val);
+
+	      /* Necessary to not get "-1 = 2^n - 1". */
+	      mpz_set_double_int
+		(val, double_int_sext (tree_to_double_int (cst),
+				       TYPE_PRECISION (TREE_TYPE (cst))), false);
+
 	      mpz_mul (val, val, k);
 	      scan_tree_for_params (s, TREE_OPERAND (e, 0), c, val);
 	      mpz_clear (val);
@@ -744,9 +755,16 @@ scan_tree_for_params (sese s, tree e, ppl_Linear_Expression_t c,
 	  if (c)
 	    {
 	      mpz_t val;
+	      tree cst = TREE_OPERAND (e, 0);
+
 	      gcc_assert (host_integerp (TREE_OPERAND (e, 0), 0));
 	      mpz_init (val);
-	      tree_int_to_gmp (TREE_OPERAND (e, 0), val);
+
+	      /* Necessary to not get "-1 = 2^n - 1". */
+	      mpz_set_double_int
+		(val, double_int_sext (tree_to_double_int (cst),
+				       TYPE_PRECISION (TREE_TYPE (cst))), false);
+
 	      mpz_mul (val, val, k);
 	      scan_tree_for_params (s, TREE_OPERAND (e, 1), c, val);
 	      mpz_clear (val);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 1f93f4c..b7c2be3 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,10 @@
 2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
 
+	PR middle-end/47594
+	* gfortran.dg/graphite/run-id-pr47594.f90: New.
+
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
 	PR middle-end/47653
 	* gcc.dg/graphite/run-id-pr47653.c: New.
 	* gcc.dg/graphite/interchange-3.c: Do not use unsigned types for
diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
new file mode 100644
index 0000000..7f36fc6
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
@@ -0,0 +1,35 @@
+! { dg-options "-O2 -fgraphite-identity" }
+
+        Subroutine foo (N, M)
+        Integer N
+        Integer M
+        integer A(8,16)
+        integer B(8)
+
+        B = (/ 2, 3, 5, 7, 11, 13, 17, 23 /)
+
+        do I = 1, N
+          do J = I, M
+            A(J,2) = B(J)
+          end do
+        end do
+
+        do I = 1, N
+          do J = I, M
+            if (A(J,2) /= B(J)) then
+              call abort ()
+              endif
+          end do
+        end do
+
+        Return
+        end
+
+
+        program main
+
+        Call foo (16, 8)
+
+        stop
+        end
+
-- 
1.7.4.1

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Sebastian Pop]

On Tue, Jul 26, 2011 at 03:22, Richard Guenther <rguenther@suse.de> wrote:
> On Mon, 25 Jul 2011, Sebastian Pop wrote:
>
>> "Bug 47594 - gfortran.dg/vect/vect-5.f90 execution test fails when
>> compiled with -O2 -fgraphite-identity"
>>
>> The problem is due to the fact that Graphite generates this loop:
>>
>>     for (scat_3=0;scat_3<=4294967295*scat_1+T_51-1;scat_3++) {
>>       S6(scat_1,scat_3);
>>     }
>>
>> that has a "-1" encoded as an unsigned "4294967295".  This constant
>> comes from the computation of the number of iterations "M - I" of
>> the inner loop:
>>
>>         do I = 1, N
>>           do J = I, M
>>             A(J,2) = B(J)
>>           end do
>>         end do
>>
>> The patch fixes the problem by sign-extending the constants for the
>> step of a chain of recurrence in scan_tree_for_params_right_scev.
>>
>> The same patter could occur for multiplication by a scalar, like in
>> "-1 * N" and so the patch also fixes these cases in
>> scan_tree_for_params.
>
> That certainly feels odd (again).  How does it end up being unsigned
> in the first place?

We got this expression from niter.  niter analysis turns all expressions
into unsigned types before starting computations.  I tried to see if we
could improve niter, but that would be a major work.  I also thought
about using PPL or ISL to implement niter for graphite.

> Randomly sign-extending stuff looks bogus to me.
> Does graphite operate on infinite precision signed integers?  Or
> does it operate on twos-complement fixed precision integers?

Graphite represents constants using mpz_t.

Sebastian

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Richard Guenther]

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

On Tue, 26 Jul 2011, Sebastian Pop wrote:

> On Tue, Jul 26, 2011 at 03:22, Richard Guenther <rguenther@suse.de> wrote:
> > On Mon, 25 Jul 2011, Sebastian Pop wrote:
> >
> >> "Bug 47594 - gfortran.dg/vect/vect-5.f90 execution test fails when
> >> compiled with -O2 -fgraphite-identity"
> >>
> >> The problem is due to the fact that Graphite generates this loop:
> >>
> >>     for (scat_3=0;scat_3<=4294967295*scat_1+T_51-1;scat_3++) {
> >>       S6(scat_1,scat_3);
> >>     }
> >>
> >> that has a "-1" encoded as an unsigned "4294967295".  This constant
> >> comes from the computation of the number of iterations "M - I" of
> >> the inner loop:
> >>
> >>         do I = 1, N
> >>           do J = I, M
> >>             A(J,2) = B(J)
> >>           end do
> >>         end do
> >>
> >> The patch fixes the problem by sign-extending the constants for the
> >> step of a chain of recurrence in scan_tree_for_params_right_scev.
> >>
> >> The same patter could occur for multiplication by a scalar, like in
> >> "-1 * N" and so the patch also fixes these cases in
> >> scan_tree_for_params.
> >
> > That certainly feels odd (again).  How does it end up being unsigned
> > in the first place?
> 
> We got this expression from niter.  niter analysis turns all expressions
> into unsigned types before starting computations.  I tried to see if we
> could improve niter, but that would be a major work.  I also thought
> about using PPL or ISL to implement niter for graphite.

Hmm, I see (I suppose to avoid introducing undefined overflow).

> > Randomly sign-extending stuff looks bogus to me.
> > Does graphite operate on infinite precision signed integers?  Or
> > does it operate on twos-complement fixed precision integers?
> 
> Graphite represents constants using mpz_t.

Not exactly an answer but I guess all mpz_t do have a sign and are
of arbitrary precision.  Thus it's wrong to change unsigned + -1U
to mpz_t + -1 unless you truncate to unsigneds precision after
doing that operation.  Do we properly handle this?

Richard.

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Sebastian Pop]

On Tue, Jul 26, 2011 at 09:07, Richard Guenther <rguenther@suse.de> wrote:
>> > Randomly sign-extending stuff looks bogus to me.
>> > Does graphite operate on infinite precision signed integers?  Or
>> > does it operate on twos-complement fixed precision integers?
>>
>> Graphite represents constants using mpz_t.
>
> Not exactly an answer but I guess all mpz_t do have a sign and are
> of arbitrary precision.  Thus it's wrong to change unsigned + -1U
> to mpz_t + -1 unless you truncate to unsigneds precision after
> doing that operation.  Do we properly handle this?

Graphite is not truncating after conversion of an unsigned expression to mpz_t.

I still don't see how truncating -1U to its precision changes anything,
could you explain?

Thanks,
Sebastian

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Richard Guenther]

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

On Tue, 26 Jul 2011, Sebastian Pop wrote:

> On Tue, Jul 26, 2011 at 09:07, Richard Guenther <rguenther@suse.de> wrote:
> >> > Randomly sign-extending stuff looks bogus to me.
> >> > Does graphite operate on infinite precision signed integers?  Or
> >> > does it operate on twos-complement fixed precision integers?
> >>
> >> Graphite represents constants using mpz_t.
> >
> > Not exactly an answer but I guess all mpz_t do have a sign and are
> > of arbitrary precision.  Thus it's wrong to change unsigned + -1U
> > to mpz_t + -1 unless you truncate to unsigneds precision after
> > doing that operation.  Do we properly handle this?
> 
> Graphite is not truncating after conversion of an unsigned expression to mpz_t.
> 
> I still don't see how truncating -1U to its precision changes anything,
> could you explain?

Truncating -1 doesn't matter - it matters that if you perform any
unsigned arithmetic in arbitrary precision signed arithmetic that
you properly truncate after each operation to simulate unsigned
twos-complement wrapping semantic.  And if you did that you wouldn't
need to sign-extend -1U either.

Richard.

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Sebastian Pop]

On Tue, Jul 26, 2011 at 09:34, Richard Guenther <rguenther@suse.de> wrote:
> Truncating -1 doesn't matter - it matters that if you perform any
> unsigned arithmetic in arbitrary precision signed arithmetic that
> you properly truncate after each operation to simulate unsigned
> twos-complement wrapping semantic.  And if you did that you wouldn't
> need to sign-extend -1U either.

Ok, so I guess that the type of the expression that we generate from
Graphite should be, as the original expression, of unsigned type.
In the previous example,

>     for (scat_3=0;scat_3<=4294967295*scat_1+T_51-1;scat_3++) {
>       S6(scat_1,scat_3);
>     }

this is still valid if the type of "4294967295*scat_1" is unsigned.
That would fix only -fgraphite-identity: we also have to watch out for
operations on the polyhedral representation that would use -1U in
other computations, and here I'm thinking about everything we have
implemented on the polyhedral representation: dependence test,
counting the number of points, i.e., all the heuristics, etc.

When disabling Graphite on all unsigned niter expressions, we get
the following fails:

FAIL: gcc.dg/graphite/scop-0.c scan-tree-dump-times graphite "number
of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-1.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1
FAIL: gcc.dg/graphite/scop-10.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1
FAIL: gcc.dg/graphite/scop-11.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1
FAIL: gcc.dg/graphite/scop-12.c scan-tree-dump-times graphite "number
of SCoPs: 5" 1
FAIL: gcc.dg/graphite/scop-13.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-16.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-17.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-18.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-2.c scan-tree-dump-times graphite "number
of SCoPs: 4" 1
FAIL: gcc.dg/graphite/scop-20.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-21.c scan-tree-dump-times graphite "number
of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-22.c scan-tree-dump-times graphite "number
of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-3.c scan-tree-dump-times graphite "number
of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-4.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-5.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1
FAIL: gcc.dg/graphite/scop-6.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1
FAIL: gcc.dg/graphite/scop-7.c scan-tree-dump-times graphite "number
of SCoPs: 3" 1
FAIL: gcc.dg/graphite/scop-8.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-9.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-dsyr2k.c scan-tree-dump-times graphite
"number of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-dsyrk.c scan-tree-dump-times graphite
"number of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-matmult.c scan-tree-dump-times graphite
"number of SCoPs: 1" 1
FAIL: gcc.dg/graphite/scop-mvt.c scan-tree-dump-times graphite "number
of SCoPs: 2" 1
FAIL: gcc.dg/graphite/scop-sor.c scan-tree-dump-times graphite "number
of SCoPs: 1" 1
FAIL: gcc.dg/graphite/interchange-0.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-1.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-10.c scan-tree-dump-times graphite
"will be interchanged" 2
FAIL: gcc.dg/graphite/interchange-11.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-12.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-13.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-3.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-4.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-5.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-6.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-7.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/interchange-8.c scan-tree-dump-times graphite
"will be interchanged" 2
FAIL: gcc.dg/graphite/interchange-9.c scan-tree-dump-times graphite
"will be interchanged" 1
FAIL: gcc.dg/graphite/block-1.c scan-tree-dump-times graphite "will be
loop blocked" 3
FAIL: gcc.dg/graphite/block-5.c scan-tree-dump-times graphite "will be
loop blocked" 1
FAIL: gcc.dg/graphite/vect-pr43423.c scan-tree-dump-times vect
"vectorized 2 loops" 1
FAIL: gcc.dg/graphite/pr35356-1.c scan-tree-dump-times graphite "loop_1" 0
FAIL: gcc.dg/graphite/pr35356-2.c scan-tree-dump-times graphite "MIN_EXPR" 4
FAIL: gcc.dg/graphite/pr35356-2.c scan-tree-dump-times graphite "MAX_EXPR" 4

FAIL: gfortran.dg/graphite/interchange-3.f90  -O  scan-tree-dump-times
graphite "will be interchanged" 1
FAIL: gfortran.dg/graphite/block-1.f90  -O  scan-tree-dump-times
graphite "number of SCoPs: 1" 1
FAIL: gfortran.dg/graphite/block-2.f  -O  scan-tree-dump-times
graphite "number of SCoPs: 2" 1

FAIL: libgomp.graphite/bounds.c scan-tree-dump-times graphite "0 loops
carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-1.c scan-tree-dump-times
graphite "1 loops carried no dependency" 2
FAIL: libgomp.graphite/force-parallel-1.c scan-tree-dump-times
optimized "loopfn" 5
FAIL: libgomp.graphite/force-parallel-2.c scan-tree-dump-times
graphite "2 loops carried no dependency" 2
FAIL: libgomp.graphite/force-parallel-2.c scan-tree-dump-times
optimized "loopfn" 5
FAIL: libgomp.graphite/force-parallel-3.c scan-tree-dump-times
graphite "4 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-3.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-3.c scan-tree-dump-times
optimized "loopfn.1" 5
FAIL: libgomp.graphite/force-parallel-4.c scan-tree-dump-times
graphite "2 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-4.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-4.c scan-tree-dump-times
optimized "loopfn.1" 5
FAIL: libgomp.graphite/force-parallel-5.c scan-tree-dump-times
graphite "2 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-5.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-5.c scan-tree-dump-times
optimized "loopfn.1" 5
FAIL: libgomp.graphite/force-parallel-6.c scan-tree-dump-times
graphite "1 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-6.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-7.c scan-tree-dump-times
graphite "3 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-7.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-8.c scan-tree-dump-times
graphite "2 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-8.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-8.c scan-tree-dump-times
optimized "loopfn.1" 5
FAIL: libgomp.graphite/force-parallel-9.c scan-tree-dump-times
graphite "4 loops carried no dependency" 1
FAIL: libgomp.graphite/force-parallel-9.c scan-tree-dump-times
optimized "loopfn.0" 5
FAIL: libgomp.graphite/force-parallel-9.c scan-tree-dump-times
optimized "loopfn.1" 5

So the only solution that I can see is to implement the niter analysis
as the resolution of a constraint system, and that would avoid creating
the unsigned expressions.

Sebastian

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Richard Guenther]

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

On Wed, 27 Jul 2011, Sebastian Pop wrote:

> On Tue, Jul 26, 2011 at 09:34, Richard Guenther <rguenther@suse.de> wrote:
> > Truncating -1 doesn't matter - it matters that if you perform any
> > unsigned arithmetic in arbitrary precision signed arithmetic that
> > you properly truncate after each operation to simulate unsigned
> > twos-complement wrapping semantic.  And if you did that you wouldn't
> > need to sign-extend -1U either.
> 
> Ok, so I guess that the type of the expression that we generate from
> Graphite should be, as the original expression, of unsigned type.
> In the previous example,
> 
> >     for (scat_3=0;scat_3<=4294967295*scat_1+T_51-1;scat_3++) {
> >       S6(scat_1,scat_3);
> >     }
> 
> this is still valid if the type of "4294967295*scat_1" is unsigned.

If 4294967295*scat_1+T_51-1 is always the symbolic number of
iterations then it will be always >= 0, right?  I still do not
quite understand where and how "types" enter the picture for
graphite here - if the niter expression was scat_1 + T_51 with
both unsigned then you'd still have to truncate to the result
types precision in case the polyhedral model internally has
infinite precision.  So I don't think -1U is in any way special
(it probably just appears more often, and we could avoid some
of the issues with folding the above to T_51 - 1 - scat_1).

> That would fix only -fgraphite-identity: we also have to watch out for
> operations on the polyhedral representation that would use -1U in
> other computations, and here I'm thinking about everything we have
> implemented on the polyhedral representation: dependence test,
> counting the number of points, i.e., all the heuristics, etc.
> 
> When disabling Graphite on all unsigned niter expressions, we get
> the following fails:

I think niter expressions are unsigned simply because niter will
always be >= 0.  But the issue doesn't seem to be the unsignedness of 
niter but the fact that the symbolic expression is computed with
unsigned arithmetic?

> FAIL: gcc.dg/graphite/scop-0.c scan-tree-dump-times graphite "number
> of SCoPs: 1" 1

Where I wonder why we end up with unsigned arithmetic for this
testcase for example.  2 * N + 100 is surely all signed.

[...]

> So the only solution that I can see is to implement the niter analysis
> as the resolution of a constraint system, and that would avoid creating
> the unsigned expressions.

So maybe we can instead try to avoid using unsigned arithmetic
for symbolic niters if the source does not have it unsigned?

Richard.

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Sebastian Pop]

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

Hi Richi,

On Thu, Jul 28, 2011 at 03:58, Richard Guenther <rguenther@suse.de> wrote:
> So maybe we can instead try to avoid using unsigned arithmetic
> for symbolic niters if the source does not have it unsigned?

Ok, so what about the attached patch that makes niter use the original
type as much as possible?  I.e. for the trivial cases that don't use division.
Regstrap in progress on amd64-linux.

Sebastian

[-- Attachment #2: 0001-Use-build_zero_cst-or-build_one_cst.patch --]
[-- Type: text/x-diff, Size: 6172 bytes --]

From 992e0e8c7b15610bf7b9092f0723fb77e323de3a Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Fri, 29 Jul 2011 11:08:47 -0500
Subject: [PATCH 1/2] Use build_zero_cst or build_one_cst.

---
 gcc/tree-ssa-loop-niter.c |   32 ++++++++++++++++----------------
 1 files changed, 16 insertions(+), 16 deletions(-)

diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 4acfc67..2ee3f6e 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -101,7 +101,7 @@ split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
       break;
 
     case INTEGER_CST:
-      *var = build_int_cst_type (type, 0);
+      *var = build_zero_cst (type);
       off = tree_to_double_int (expr);
       mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
       break;
@@ -522,7 +522,7 @@ inverse (tree x, tree mask)
     }
   else
     {
-      rslt = build_int_cst (type, 1);
+      rslt = build_one_cst (type);
       for (; ctr; ctr--)
 	{
 	  rslt = int_const_binop (MULT_EXPR, rslt, x);
@@ -670,7 +670,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 				- tree_low_cst (bits, 1)));
 
   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
-			       build_int_cst (niter_type, 1), bits);
+			       build_one_cst (niter_type), bits);
   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
 
   if (!exit_must_be_taken)
@@ -679,7 +679,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 	 assumptions for divisibility of c.  */
       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
-				assumption, build_int_cst (niter_type, 0));
+				assumption, build_zero_cst (niter_type));
       if (!integer_nonzerop (assumption))
 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 					  niter->assumptions, assumption);
@@ -846,7 +846,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 	}
       else
 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
-			    build_int_cst (niter_type, 1));
+			    build_one_cst (niter_type));
       bound = fold_build2 (MINUS_EXPR, type,
 			   TYPE_MAX_VALUE (type), fold_convert (type, diff));
       assumption = fold_build2 (LE_EXPR, boolean_type_node,
@@ -867,7 +867,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 	}
       else
 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
-			    build_int_cst (niter_type, 1));
+			    build_one_cst (niter_type));
       bound = fold_build2 (PLUS_EXPR, type,
 			   TYPE_MIN_VALUE (type), fold_convert (type, diff));
       assumption = fold_build2 (GE_EXPR, boolean_type_node,
@@ -963,7 +963,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
   if (integer_nonzerop (iv0->step))
     {
       diff = fold_build2 (MINUS_EXPR, type1,
-			  iv0->step, build_int_cst (type1, 1));
+			  iv0->step, build_one_cst (type1));
 
       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
 	 0 address never belongs to any object, we can assume this for
@@ -985,7 +985,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
   else
     {
       diff = fold_build2 (PLUS_EXPR, type1,
-			  iv1->step, build_int_cst (type1, 1));
+			  iv1->step, build_one_cst (type1));
 
       if (!POINTER_TYPE_P (type))
 	{
@@ -1083,7 +1083,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
     {
       affine_iv zps;
 
-      zps.base = build_int_cst (niter_type, 0);
+      zps.base = build_zero_cst (niter_type);
       zps.step = step;
       /* number_of_iterations_lt_to_ne will add assumptions that ensure that
 	 zps does not overflow.  */
@@ -1102,7 +1102,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
 
   s = fold_build2 (MINUS_EXPR, niter_type,
-		   step, build_int_cst (niter_type, 1));
+		   step, build_one_cst (niter_type));
   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
 
@@ -1167,13 +1167,13 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
 	iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
       else
 	iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
-				 build_int_cst (type1, 1));
+				 build_one_cst (type1));
     }
   else if (POINTER_TYPE_P (type))
     iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
   else
     iv0->base = fold_build2 (MINUS_EXPR, type1,
-			     iv0->base, build_int_cst (type1, 1));
+			     iv0->base, build_one_cst (type1));
 
   bounds_add (bnds, double_int_one, type1);
 
@@ -1282,7 +1282,7 @@ number_of_iterations_cond (struct loop *loop,
       iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
 					   iv0->step, iv1->step);
       iv0->no_overflow = false;
-      iv1->step = build_int_cst (type, 0);
+      iv1->step = build_zero_cst (type);
       iv1->no_overflow = true;
     }
 
@@ -1305,7 +1305,7 @@ number_of_iterations_cond (struct loop *loop,
   /* If the loop exits immediately, there is nothing to do.  */
   if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
     {
-      niter->niter = build_int_cst (unsigned_type_for (type), 0);
+      niter->niter = build_zero_cst (unsigned_type_for (type));
       niter->max = double_int_zero;
       return true;
     }
@@ -1946,7 +1946,7 @@ find_loop_niter (struct loop *loop, edge *exit)
 	{
 	  /* We exit in the first iteration through this exit.
 	     We won't find anything better.  */
-	  niter = build_int_cst (unsigned_type_node, 0);
+	  niter = build_zero_cst (unsigned_type_node);
 	  *exit = ex;
 	  break;
 	}
@@ -3017,7 +3017,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
       type = TREE_TYPE (niter);
       if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
 	niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
-			build_int_cst (type, 0),
+			build_zero_cst (type),
 			niter);
       record_estimate (loop, niter, niter_desc.max,
 		       last_stmt (ex->src),
-- 
1.7.4.1


[-- Attachment #3: 0002-Fix-PR47594-Build-signed-niter-expressions.patch --]
[-- Type: text/x-diff, Size: 8478 bytes --]

From 7535ba784f9f5f0e7583bf77e5baadb386131bd6 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Fri, 29 Jul 2011 14:35:56 -0500
Subject: [PATCH 2/2] Fix PR47594: Build signed niter expressions

2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>

	PR middle-end/47594
	* graphite-scop-detection.c (graphite_can_represent_scev): Return false
	on TYPE_UNSIGNED.
	* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
	double_int_sext.
	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
	for the trivial case, then convert to unsigned.
	(number_of_iterations_lt): Use the original signed types.
	(number_of_iterations_cond): Same.
	(find_loop_niter): Build signed integer constant.
	(loop_niter_by_eval): Same.
---
 gcc/ChangeLog                                      |   14 ++++++++
 gcc/graphite-scop-detection.c                      |    6 +++
 gcc/graphite-sese-to-poly.c                        |    7 +---
 gcc/testsuite/ChangeLog                            |    5 +++
 .../gfortran.dg/graphite/run-id-pr47594.f90        |   35 ++++++++++++++++++++
 gcc/tree-ssa-loop-niter.c                          |   29 ++++++++++------
 6 files changed, 79 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 738144d..9b22eed 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/47594
+	* graphite-scop-detection.c (graphite_can_represent_scev): Return false
+	on TYPE_UNSIGNED.
+	* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
+	double_int_sext.
+	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
+	for the trivial case, then convert to unsigned.
+	(number_of_iterations_lt): Use the original signed types.
+	(number_of_iterations_cond): Same.
+	(find_loop_niter): Build signed integer constant.
+	(loop_niter_by_eval): Same.
+
 2011-07-29  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/predicates.md (tp_or_register_operand): Remove predicate.
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 3460568..403ff23 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev)
   if (chrec_contains_undetermined (scev))
     return false;
 
+  /* FIXME: As long as Graphite cannot handle wrap around effects of
+     induction variables, we discard them.  */
+  if (TYPE_UNSIGNED (TREE_TYPE (scev))
+      && !POINTER_TYPE_P (TREE_TYPE (scev)))
+    return false;
+
   switch (TREE_CODE (scev))
     {
     case PLUS_EXPR:
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 7e23c9d..d15f0b3 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -647,14 +647,9 @@ scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
 {
   mpz_t val;
   ppl_Coefficient_t coef;
-  tree type = TREE_TYPE (cst);
 
   mpz_init (val);
-
-  /* Necessary to not get "-1 = 2^n - 1". */
-  mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
-					    TYPE_PRECISION (type)), false);
-
+  tree_int_to_gmp (cst, val);
   mpz_mul (val, val, k);
   ppl_new_Coefficient (&coef);
   ppl_assign_Coefficient_from_mpz_t (coef, val);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index cf5ee2b..55f2e91 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/47594
+	* gfortran.dg/graphite/run-id-pr47594.f90: New.
+
 2011-07-29  Rainer Orth  <ro@CeBiTec.Uni-Bielefeld.DE>
 
 	PR tree-optimization/47407
diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
new file mode 100644
index 0000000..7f36fc6
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
@@ -0,0 +1,35 @@
+! { dg-options "-O2 -fgraphite-identity" }
+
+        Subroutine foo (N, M)
+        Integer N
+        Integer M
+        integer A(8,16)
+        integer B(8)
+
+        B = (/ 2, 3, 5, 7, 11, 13, 17, 23 /)
+
+        do I = 1, N
+          do J = I, M
+            A(J,2) = B(J)
+          end do
+        end do
+
+        do I = 1, N
+          do J = I, M
+            if (A(J,2) /= B(J)) then
+              call abort ()
+              endif
+          end do
+        end do
+
+        Return
+        end
+
+
+        program main
+
+        Call foo (16, 8)
+
+        stop
+        end
+
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 2ee3f6e..285577d 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -618,7 +618,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 			 struct tree_niter_desc *niter, bool exit_must_be_taken,
 			 bounds *bnds)
 {
-  tree niter_type = unsigned_type_for (type);
+  tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
   tree s, c, d, bits, assumption, tmp, bound;
   mpz_t max;
 
@@ -627,10 +627,9 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
   niter->cmp = NE_EXPR;
 
   /* Rearrange the terms so that we get inequality S * i <> C, with S
-     positive.  Also cast everything to the unsigned type.  If IV does
-     not overflow, BNDS bounds the value of C.  Also, this is the
-     case if the computation |FINAL - IV->base| does not overflow, i.e.,
-     if BNDS->below in the result is nonnegative.  */
+     positive.  If IV does not overflow, BNDS bounds the value of C.
+     Also, this is the case if the computation |FINAL - IV->base| does
+     not overflow, i.e., if BNDS->below in the result is nonnegative.  */
   if (tree_int_cst_sign_bit (iv->step))
     {
       s = fold_convert (niter_type,
@@ -663,7 +662,12 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 
   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
      is infinite.  Otherwise, the number of iterations is
-     (inverse(s/d) * (c/d)) mod (size of mode/d).  */
+     (inverse(s/d) * (c/d)) mod (size of mode/d).  To compute this, we
+     need unsigned types, otherwise we end on overflows.  */
+  niter_type = unsigned_type_for (type);
+  s = fold_convert (niter_type, s);
+  c = fold_convert (niter_type, c);
+
   bits = num_ending_zeros (s);
   bound = build_low_bits_mask (niter_type,
 			       (TYPE_PRECISION (niter_type)
@@ -1022,7 +1026,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 			 struct tree_niter_desc *niter,
 			 bool exit_must_be_taken, bounds *bnds)
 {
-  tree niter_type = unsigned_type_for (type);
+  tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
   tree delta, step, s;
   mpz_t mstep, tmp;
 
@@ -1098,7 +1102,10 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 
   /* We determine the number of iterations as (delta + step - 1) / step.  For
      this to work, we must know that iv1->base >= iv0->base - step + 1,
-     otherwise the loop does not roll.  */
+     otherwise the loop does not roll.  To compute the division, we
+     use unsigned types.  */
+  niter_type = unsigned_type_for (type);
+  step = fold_convert (niter_type, step);
   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
 
   s = fold_build2 (MINUS_EXPR, niter_type,
@@ -1305,7 +1312,7 @@ number_of_iterations_cond (struct loop *loop,
   /* If the loop exits immediately, there is nothing to do.  */
   if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
     {
-      niter->niter = build_zero_cst (unsigned_type_for (type));
+      niter->niter = build_zero_cst (type);
       niter->max = double_int_zero;
       return true;
     }
@@ -1946,7 +1953,7 @@ find_loop_niter (struct loop *loop, edge *exit)
 	{
 	  /* We exit in the first iteration through this exit.
 	     We won't find anything better.  */
-	  niter = build_zero_cst (unsigned_type_node);
+	  niter = build_zero_cst (integer_type_node);
 	  *exit = ex;
 	  break;
 	}
@@ -2250,7 +2257,7 @@ loop_niter_by_eval (struct loop *loop, edge exit)
 	    fprintf (dump_file,
 		     "Proved that loop %d iterates %d times using brute force.\n",
 		     loop->num, i);
-	  return build_int_cst (unsigned_type_node, i);
+	  return build_int_cst (integer_type_node, i);
 	}
 
       for (j = 0; j < 2; j++)
-- 
1.7.4.1

Re: [PATCH] Fix PR47594: Sign extend constants while translating to Graphite

[Sebastian Pop]

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

On Sat, Jul 30, 2011 at 08:33, Jack Howarth <howarth@bromo.med.uc.edu> wrote:
>    These patches fail to bootstrap on current gcc trunk (r176957) with...
>

The attached patch adds one extra line to convert the step to
unsigned.  It passes bootstrap and has the following extra FAILS:

FAIL: gcc.c-torture/execute/pr45034.c execution,  -O2
FAIL: gcc.c-torture/execute/pr45034.c execution,  -O3 -fomit-frame-pointer
FAIL: gcc.c-torture/execute/pr45034.c execution,  -O3
-fomit-frame-pointer -funroll-loops
FAIL: gfortran.dg/do_3.F90  -O1  execution test
FAIL: gcc.c-torture/execute/pr45034.c execution,  -O3
-fomit-frame-pointer -funroll-all-loops -finline-functions
FAIL: gfortran.dg/do_3.F90  -O2  execution test
FAIL: gcc.c-torture/execute/pr45034.c execution,  -O3 -g
FAIL: gfortran.dg/do_3.F90  -O3 -fomit-frame-pointer  execution test
FAIL: gcc.c-torture/execute/pr45034.c execution,  -Os
FAIL: gfortran.dg/do_3.F90  -O3 -fomit-frame-pointer -funroll-loops
execution test
FAIL: gcc.c-torture/execute/pr45034.c execution,  -O2 -flto
-flto-partition=none
FAIL: gfortran.dg/do_3.F90  -O3 -fomit-frame-pointer
-funroll-all-loops -finline-functions  execution test
FAIL: gcc.c-torture/execute/pr45034.c execution,  -O2 -flto
FAIL: gfortran.dg/do_3.F90  -O3 -g  execution test
FAIL: gfortran.dg/do_3.F90  -Os  execution test

I'm investigating why these fail.

Sebastian

[-- Attachment #2: 0002-Fix-PR47594-Build-signed-niter-expressions.patch --]
[-- Type: text/x-diff, Size: 8524 bytes --]

From 0abb53c250949cd22cacbf3ed0b69604665c2949 Mon Sep 17 00:00:00 2001
From: Sebastian Pop <sebpop@gmail.com>
Date: Fri, 29 Jul 2011 14:35:56 -0500
Subject: [PATCH 2/2] Fix PR47594: Build signed niter expressions

2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>

	PR middle-end/47594
	* graphite-scop-detection.c (graphite_can_represent_scev): Return false
	on TYPE_UNSIGNED.
	* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
	double_int_sext.
	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
	for the trivial case, then convert to unsigned.
	(number_of_iterations_lt): Use the original signed types.
	(number_of_iterations_cond): Same.
	(find_loop_niter): Build signed integer constant.
	(loop_niter_by_eval): Same.
---
 gcc/ChangeLog                                      |   14 ++++++++
 gcc/graphite-scop-detection.c                      |    6 +++
 gcc/graphite-sese-to-poly.c                        |    7 +---
 gcc/testsuite/ChangeLog                            |    5 +++
 .../gfortran.dg/graphite/run-id-pr47594.f90        |   35 ++++++++++++++++++++
 gcc/tree-ssa-loop-niter.c                          |   30 +++++++++++------
 6 files changed, 80 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 738144d..9b22eed 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/47594
+	* graphite-scop-detection.c (graphite_can_represent_scev): Return false
+	on TYPE_UNSIGNED.
+	* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
+	double_int_sext.
+	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
+	for the trivial case, then convert to unsigned.
+	(number_of_iterations_lt): Use the original signed types.
+	(number_of_iterations_cond): Same.
+	(find_loop_niter): Build signed integer constant.
+	(loop_niter_by_eval): Same.
+
 2011-07-29  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/predicates.md (tp_or_register_operand): Remove predicate.
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 3460568..403ff23 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev)
   if (chrec_contains_undetermined (scev))
     return false;
 
+  /* FIXME: As long as Graphite cannot handle wrap around effects of
+     induction variables, we discard them.  */
+  if (TYPE_UNSIGNED (TREE_TYPE (scev))
+      && !POINTER_TYPE_P (TREE_TYPE (scev)))
+    return false;
+
   switch (TREE_CODE (scev))
     {
     case PLUS_EXPR:
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 7e23c9d..d15f0b3 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -647,14 +647,9 @@ scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
 {
   mpz_t val;
   ppl_Coefficient_t coef;
-  tree type = TREE_TYPE (cst);
 
   mpz_init (val);
-
-  /* Necessary to not get "-1 = 2^n - 1". */
-  mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
-					    TYPE_PRECISION (type)), false);
-
+  tree_int_to_gmp (cst, val);
   mpz_mul (val, val, k);
   ppl_new_Coefficient (&coef);
   ppl_assign_Coefficient_from_mpz_t (coef, val);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index cf5ee2b..55f2e91 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/47594
+	* gfortran.dg/graphite/run-id-pr47594.f90: New.
+
 2011-07-29  Rainer Orth  <ro@CeBiTec.Uni-Bielefeld.DE>
 
 	PR tree-optimization/47407
diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
new file mode 100644
index 0000000..7f36fc6
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
@@ -0,0 +1,35 @@
+! { dg-options "-O2 -fgraphite-identity" }
+
+        Subroutine foo (N, M)
+        Integer N
+        Integer M
+        integer A(8,16)
+        integer B(8)
+
+        B = (/ 2, 3, 5, 7, 11, 13, 17, 23 /)
+
+        do I = 1, N
+          do J = I, M
+            A(J,2) = B(J)
+          end do
+        end do
+
+        do I = 1, N
+          do J = I, M
+            if (A(J,2) /= B(J)) then
+              call abort ()
+              endif
+          end do
+        end do
+
+        Return
+        end
+
+
+        program main
+
+        Call foo (16, 8)
+
+        stop
+        end
+
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 2ee3f6e..477fbe9 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -618,7 +618,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 			 struct tree_niter_desc *niter, bool exit_must_be_taken,
 			 bounds *bnds)
 {
-  tree niter_type = unsigned_type_for (type);
+  tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
   tree s, c, d, bits, assumption, tmp, bound;
   mpz_t max;
 
@@ -627,10 +627,9 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
   niter->cmp = NE_EXPR;
 
   /* Rearrange the terms so that we get inequality S * i <> C, with S
-     positive.  Also cast everything to the unsigned type.  If IV does
-     not overflow, BNDS bounds the value of C.  Also, this is the
-     case if the computation |FINAL - IV->base| does not overflow, i.e.,
-     if BNDS->below in the result is nonnegative.  */
+     positive.  If IV does not overflow, BNDS bounds the value of C.
+     Also, this is the case if the computation |FINAL - IV->base| does
+     not overflow, i.e., if BNDS->below in the result is nonnegative.  */
   if (tree_int_cst_sign_bit (iv->step))
     {
       s = fold_convert (niter_type,
@@ -663,7 +662,12 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 
   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
      is infinite.  Otherwise, the number of iterations is
-     (inverse(s/d) * (c/d)) mod (size of mode/d).  */
+     (inverse(s/d) * (c/d)) mod (size of mode/d).  To compute this, we
+     need unsigned types, otherwise we end on overflows.  */
+  niter_type = unsigned_type_for (type);
+  s = fold_convert (niter_type, s);
+  c = fold_convert (niter_type, c);
+
   bits = num_ending_zeros (s);
   bound = build_low_bits_mask (niter_type,
 			       (TYPE_PRECISION (niter_type)
@@ -1022,7 +1026,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 			 struct tree_niter_desc *niter,
 			 bool exit_must_be_taken, bounds *bnds)
 {
-  tree niter_type = unsigned_type_for (type);
+  tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
   tree delta, step, s;
   mpz_t mstep, tmp;
 
@@ -1098,7 +1102,11 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 
   /* We determine the number of iterations as (delta + step - 1) / step.  For
      this to work, we must know that iv1->base >= iv0->base - step + 1,
-     otherwise the loop does not roll.  */
+     otherwise the loop does not roll.  To compute the division, we
+     use unsigned types.  */
+  niter_type = unsigned_type_for (type);
+  step = fold_convert (niter_type, step);
+  delta = fold_convert (niter_type, delta);
   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
 
   s = fold_build2 (MINUS_EXPR, niter_type,
@@ -1305,7 +1313,7 @@ number_of_iterations_cond (struct loop *loop,
   /* If the loop exits immediately, there is nothing to do.  */
   if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
     {
-      niter->niter = build_zero_cst (unsigned_type_for (type));
+      niter->niter = build_zero_cst (type);
       niter->max = double_int_zero;
       return true;
     }
@@ -1946,7 +1954,7 @@ find_loop_niter (struct loop *loop, edge *exit)
 	{
 	  /* We exit in the first iteration through this exit.
 	     We won't find anything better.  */
-	  niter = build_zero_cst (unsigned_type_node);
+	  niter = build_zero_cst (integer_type_node);
 	  *exit = ex;
 	  break;
 	}
@@ -2250,7 +2258,7 @@ loop_niter_by_eval (struct loop *loop, edge exit)
 	    fprintf (dump_file,
 		     "Proved that loop %d iterates %d times using brute force.\n",
 		     loop->num, i);
-	  return build_int_cst (unsigned_type_node, i);
+	  return build_int_cst (integer_type_node, i);
 	}
 
       for (j = 0; j < 2; j++)
-- 
1.7.4.1

[PATCH 0/2] Fix PR47594

[Sebastian Pop]

Hi Richi,

These two patches passed regstrap on amd64-linux:

  Use build_zero_cst or build_one_cst.
  Fix PR47594: Build signed niter expressions

Ok for trunk?

Thanks,
Sebastian

[PATCH 2/2] Fix PR47594: Build signed niter expressions

[Sebastian Pop]

2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>

	PR middle-end/47594
	* graphite-scop-detection.c (graphite_can_represent_scev): Return false
	on TYPE_UNSIGNED.
	* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
	double_int_sext.
	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
	for the trivial case, then convert to unsigned.
	(number_of_iterations_lt): Use the original signed types.
	(number_of_iterations_cond): Same.
	(find_loop_niter): Build signed integer constant.
	(loop_niter_by_eval): Same.
---
 gcc/ChangeLog                                      |   14 ++++
 gcc/graphite-scop-detection.c                      |    6 ++
 gcc/graphite-sese-to-poly.c                        |    7 +--
 gcc/testsuite/ChangeLog                            |    5 ++
 .../gfortran.dg/graphite/run-id-pr47594.f90        |   35 +++++++++++
 gcc/tree-ssa-loop-niter.c                          |   63 ++++++++++++++++----
 6 files changed, 113 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 580c12f..33bd7b4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/47594
+	* graphite-scop-detection.c (graphite_can_represent_scev): Return false
+	on TYPE_UNSIGNED.
+	* graphite-sese-to-poly.c (scan_tree_for_params_int): Do not call
+	double_int_sext.
+	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
+	for the trivial case, then convert to unsigned.
+	(number_of_iterations_lt): Use the original signed types.
+	(number_of_iterations_cond): Same.
+	(find_loop_niter): Build signed integer constant.
+	(loop_niter_by_eval): Same.
+
 2011-08-01  Richard Henderson  <rth@redhat.com>
 
 	PR target/49881
diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 3460568..403ff23 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev)
   if (chrec_contains_undetermined (scev))
     return false;
 
+  /* FIXME: As long as Graphite cannot handle wrap around effects of
+     induction variables, we discard them.  */
+  if (TYPE_UNSIGNED (TREE_TYPE (scev))
+      && !POINTER_TYPE_P (TREE_TYPE (scev)))
+    return false;
+
   switch (TREE_CODE (scev))
     {
     case PLUS_EXPR:
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index 7e23c9d..d15f0b3 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -647,14 +647,9 @@ scan_tree_for_params_int (tree cst, ppl_Linear_Expression_t expr, mpz_t k)
 {
   mpz_t val;
   ppl_Coefficient_t coef;
-  tree type = TREE_TYPE (cst);
 
   mpz_init (val);
-
-  /* Necessary to not get "-1 = 2^n - 1". */
-  mpz_set_double_int (val, double_int_sext (tree_to_double_int (cst),
-					    TYPE_PRECISION (type)), false);
-
+  tree_int_to_gmp (cst, val);
   mpz_mul (val, val, k);
   ppl_new_Coefficient (&coef);
   ppl_assign_Coefficient_from_mpz_t (coef, val);
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 4ff8a10..1f8d049 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2011-07-23  Sebastian Pop  <sebastian.pop@amd.com>
+
+	PR middle-end/47594
+	* gfortran.dg/graphite/run-id-pr47594.f90: New.
+
 2011-08-01  Jason Merrill  <jason@redhat.com>
 
 	PR c++/49932
diff --git a/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90 b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
new file mode 100644
index 0000000..7f36fc6
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/graphite/run-id-pr47594.f90
@@ -0,0 +1,35 @@
+! { dg-options "-O2 -fgraphite-identity" }
+
+        Subroutine foo (N, M)
+        Integer N
+        Integer M
+        integer A(8,16)
+        integer B(8)
+
+        B = (/ 2, 3, 5, 7, 11, 13, 17, 23 /)
+
+        do I = 1, N
+          do J = I, M
+            A(J,2) = B(J)
+          end do
+        end do
+
+        do I = 1, N
+          do J = I, M
+            if (A(J,2) /= B(J)) then
+              call abort ()
+              endif
+          end do
+        end do
+
+        Return
+        end
+
+
+        program main
+
+        Call foo (16, 8)
+
+        stop
+        end
+
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 2ee3f6e..3bd9511 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -618,7 +618,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 			 struct tree_niter_desc *niter, bool exit_must_be_taken,
 			 bounds *bnds)
 {
-  tree niter_type = unsigned_type_for (type);
+  tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
   tree s, c, d, bits, assumption, tmp, bound;
   mpz_t max;
 
@@ -627,10 +627,9 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
   niter->cmp = NE_EXPR;
 
   /* Rearrange the terms so that we get inequality S * i <> C, with S
-     positive.  Also cast everything to the unsigned type.  If IV does
-     not overflow, BNDS bounds the value of C.  Also, this is the
-     case if the computation |FINAL - IV->base| does not overflow, i.e.,
-     if BNDS->below in the result is nonnegative.  */
+     positive.  If IV does not overflow, BNDS bounds the value of C.
+     Also, this is the case if the computation |FINAL - IV->base| does
+     not overflow, i.e., if BNDS->below in the result is nonnegative.  */
   if (tree_int_cst_sign_bit (iv->step))
     {
       s = fold_convert (niter_type,
@@ -648,6 +647,30 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 		       fold_convert (niter_type, iv->base));
     }
 
+  if ((TREE_CODE_CLASS (TREE_CODE (c)) == tcc_constant && TREE_OVERFLOW (c))
+      || (TREE_CODE_CLASS (TREE_CODE (s)) == tcc_constant && TREE_OVERFLOW (s)))
+    {
+      niter_type = unsigned_type_for (type);
+
+      if (tree_int_cst_sign_bit (iv->step))
+	{
+	  s = fold_convert (niter_type,
+			    fold_build1 (NEGATE_EXPR, type, iv->step));
+	  c = fold_build2 (MINUS_EXPR, niter_type,
+			   fold_convert (niter_type, iv->base),
+			   fold_convert (niter_type, final));
+	  bounds_negate (bnds);
+	}
+      else
+	{
+	  s = fold_convert (niter_type, iv->step);
+	  c = fold_build2 (MINUS_EXPR, niter_type,
+			   fold_convert (niter_type, final),
+			   fold_convert (niter_type, iv->base));
+
+	}
+    }
+
   mpz_init (max);
   number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
 			       exit_must_be_taken);
@@ -663,7 +686,12 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 
   /* Let nsd (step, size of mode) = d.  If d does not divide c, the loop
      is infinite.  Otherwise, the number of iterations is
-     (inverse(s/d) * (c/d)) mod (size of mode/d).  */
+     (inverse(s/d) * (c/d)) mod (size of mode/d).  To compute this, we
+     need unsigned types, otherwise we end on overflows.  */
+  niter_type = unsigned_type_for (type);
+  s = fold_convert (niter_type, s);
+  c = fold_convert (niter_type, c);
+
   bits = num_ending_zeros (s);
   bound = build_low_bits_mask (niter_type,
 			       (TYPE_PRECISION (niter_type)
@@ -1022,7 +1050,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 			 struct tree_niter_desc *niter,
 			 bool exit_must_be_taken, bounds *bnds)
 {
-  tree niter_type = unsigned_type_for (type);
+  tree niter_type = POINTER_TYPE_P (type) ? unsigned_type_for (type) : type;
   tree delta, step, s;
   mpz_t mstep, tmp;
 
@@ -1043,6 +1071,15 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 		       fold_convert (niter_type, iv1->base),
 		       fold_convert (niter_type, iv0->base));
 
+  if (TREE_CODE_CLASS (TREE_CODE (delta)) == tcc_constant
+      && TREE_OVERFLOW (delta))
+    {
+      niter_type = unsigned_type_for (type);
+      delta = fold_build2 (MINUS_EXPR, niter_type,
+			   fold_convert (niter_type, iv1->base),
+			   fold_convert (niter_type, iv0->base));
+    }
+
   /* First handle the special case that the step is +-1.  */
   if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
       || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
@@ -1098,7 +1135,11 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 
   /* We determine the number of iterations as (delta + step - 1) / step.  For
      this to work, we must know that iv1->base >= iv0->base - step + 1,
-     otherwise the loop does not roll.  */
+     otherwise the loop does not roll.  To compute the division, we
+     use unsigned types.  */
+  niter_type = unsigned_type_for (type);
+  step = fold_convert (niter_type, step);
+  delta = fold_convert (niter_type, delta);
   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
 
   s = fold_build2 (MINUS_EXPR, niter_type,
@@ -1305,7 +1346,7 @@ number_of_iterations_cond (struct loop *loop,
   /* If the loop exits immediately, there is nothing to do.  */
   if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
     {
-      niter->niter = build_zero_cst (unsigned_type_for (type));
+      niter->niter = build_zero_cst (type);
       niter->max = double_int_zero;
       return true;
     }
@@ -1946,7 +1987,7 @@ find_loop_niter (struct loop *loop, edge *exit)
 	{
 	  /* We exit in the first iteration through this exit.
 	     We won't find anything better.  */
-	  niter = build_zero_cst (unsigned_type_node);
+	  niter = build_zero_cst (integer_type_node);
 	  *exit = ex;
 	  break;
 	}
@@ -2250,7 +2291,7 @@ loop_niter_by_eval (struct loop *loop, edge exit)
 	    fprintf (dump_file,
 		     "Proved that loop %d iterates %d times using brute force.\n",
 		     loop->num, i);
-	  return build_int_cst (unsigned_type_node, i);
+	  return build_int_cst (integer_type_node, i);
 	}
 
       for (j = 0; j < 2; j++)
-- 
1.7.4.1

[PATCH 1/2] Use build_zero_cst or build_one_cst.

[Sebastian Pop]

---
 gcc/tree-ssa-loop-niter.c |   32 ++++++++++++++++----------------
 1 files changed, 16 insertions(+), 16 deletions(-)

diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 4acfc67..2ee3f6e 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -101,7 +101,7 @@ split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
       break;
 
     case INTEGER_CST:
-      *var = build_int_cst_type (type, 0);
+      *var = build_zero_cst (type);
       off = tree_to_double_int (expr);
       mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
       break;
@@ -522,7 +522,7 @@ inverse (tree x, tree mask)
     }
   else
     {
-      rslt = build_int_cst (type, 1);
+      rslt = build_one_cst (type);
       for (; ctr; ctr--)
 	{
 	  rslt = int_const_binop (MULT_EXPR, rslt, x);
@@ -670,7 +670,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 				- tree_low_cst (bits, 1)));
 
   d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
-			       build_int_cst (niter_type, 1), bits);
+			       build_one_cst (niter_type), bits);
   s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
 
   if (!exit_must_be_taken)
@@ -679,7 +679,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
 	 assumptions for divisibility of c.  */
       assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
       assumption = fold_build2 (EQ_EXPR, boolean_type_node,
-				assumption, build_int_cst (niter_type, 0));
+				assumption, build_zero_cst (niter_type));
       if (!integer_nonzerop (assumption))
 	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
 					  niter->assumptions, assumption);
@@ -846,7 +846,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 	}
       else
 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
-			    build_int_cst (niter_type, 1));
+			    build_one_cst (niter_type));
       bound = fold_build2 (MINUS_EXPR, type,
 			   TYPE_MAX_VALUE (type), fold_convert (type, diff));
       assumption = fold_build2 (LE_EXPR, boolean_type_node,
@@ -867,7 +867,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
 	}
       else
 	diff = fold_build2 (MINUS_EXPR, niter_type, step,
-			    build_int_cst (niter_type, 1));
+			    build_one_cst (niter_type));
       bound = fold_build2 (PLUS_EXPR, type,
 			   TYPE_MIN_VALUE (type), fold_convert (type, diff));
       assumption = fold_build2 (GE_EXPR, boolean_type_node,
@@ -963,7 +963,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
   if (integer_nonzerop (iv0->step))
     {
       diff = fold_build2 (MINUS_EXPR, type1,
-			  iv0->step, build_int_cst (type1, 1));
+			  iv0->step, build_one_cst (type1));
 
       /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
 	 0 address never belongs to any object, we can assume this for
@@ -985,7 +985,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
   else
     {
       diff = fold_build2 (PLUS_EXPR, type1,
-			  iv1->step, build_int_cst (type1, 1));
+			  iv1->step, build_one_cst (type1));
 
       if (!POINTER_TYPE_P (type))
 	{
@@ -1083,7 +1083,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
     {
       affine_iv zps;
 
-      zps.base = build_int_cst (niter_type, 0);
+      zps.base = build_zero_cst (niter_type);
       zps.step = step;
       /* number_of_iterations_lt_to_ne will add assumptions that ensure that
 	 zps does not overflow.  */
@@ -1102,7 +1102,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
   assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
 
   s = fold_build2 (MINUS_EXPR, niter_type,
-		   step, build_int_cst (niter_type, 1));
+		   step, build_one_cst (niter_type));
   delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
   niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
 
@@ -1167,13 +1167,13 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
 	iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
       else
 	iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
-				 build_int_cst (type1, 1));
+				 build_one_cst (type1));
     }
   else if (POINTER_TYPE_P (type))
     iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
   else
     iv0->base = fold_build2 (MINUS_EXPR, type1,
-			     iv0->base, build_int_cst (type1, 1));
+			     iv0->base, build_one_cst (type1));
 
   bounds_add (bnds, double_int_one, type1);
 
@@ -1282,7 +1282,7 @@ number_of_iterations_cond (struct loop *loop,
       iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
 					   iv0->step, iv1->step);
       iv0->no_overflow = false;
-      iv1->step = build_int_cst (type, 0);
+      iv1->step = build_zero_cst (type);
       iv1->no_overflow = true;
     }
 
@@ -1305,7 +1305,7 @@ number_of_iterations_cond (struct loop *loop,
   /* If the loop exits immediately, there is nothing to do.  */
   if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
     {
-      niter->niter = build_int_cst (unsigned_type_for (type), 0);
+      niter->niter = build_zero_cst (unsigned_type_for (type));
       niter->max = double_int_zero;
       return true;
     }
@@ -1946,7 +1946,7 @@ find_loop_niter (struct loop *loop, edge *exit)
 	{
 	  /* We exit in the first iteration through this exit.
 	     We won't find anything better.  */
-	  niter = build_int_cst (unsigned_type_node, 0);
+	  niter = build_zero_cst (unsigned_type_node);
 	  *exit = ex;
 	  break;
 	}
@@ -3017,7 +3017,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
       type = TREE_TYPE (niter);
       if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
 	niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
-			build_int_cst (type, 0),
+			build_zero_cst (type),
 			niter);
       record_estimate (loop, niter, niter_desc.max,
 		       last_stmt (ex->src),
-- 
1.7.4.1

Re: [PATCH 2/2] Fix PR47594: Build signed niter expressions

[Zdenek Dvorak]

Hi,

> 	* tree-ssa-loop-niter.c (number_of_iterations_ne): Use the signed types
> 	for the trivial case, then convert to unsigned.
> 	(number_of_iterations_lt): Use the original signed types.
> 	(number_of_iterations_cond): Same.
> 	(find_loop_niter): Build signed integer constant.
> 	(loop_niter_by_eval): Same.

this is incorrect, or at least very dubious.  Number of iterations does not have
to fit in the signed variant of the type; and since it is always a nonnegative
number, even semantically using an unsigned type seems to be a better choice.
What is the purpose of this change?

Zdenek

Re: [PATCH 1/2] Use build_zero_cst or build_one_cst.

[Richard Guenther]

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

On Tue, 2 Aug 2011, Sebastian Pop wrote:

I think that we don't want to canonicalize build_int_cst (..., [01])
to build_{one,zero}_cst.  The former is really more descriptive.
The build_{one,zero}_cst wrappers were introduced for the
fold_convert (type, integer_{one,zero}_node) idiom as fold_convert
treats those constants specially and can convert it to any
numerical type (such as a complex double).  For that idiom the
build_{one,zero}_cst is more descriptive if we don't know we always
deal with an integer type (in which case we'd use build_int_cst again).

Thanks,
Richard.

> ---
>  gcc/tree-ssa-loop-niter.c |   32 ++++++++++++++++----------------
>  1 files changed, 16 insertions(+), 16 deletions(-)
> 
> diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
> index 4acfc67..2ee3f6e 100644
> --- a/gcc/tree-ssa-loop-niter.c
> +++ b/gcc/tree-ssa-loop-niter.c
> @@ -101,7 +101,7 @@ split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
>        break;
>  
>      case INTEGER_CST:
> -      *var = build_int_cst_type (type, 0);
> +      *var = build_zero_cst (type);
>        off = tree_to_double_int (expr);
>        mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
>        break;
> @@ -522,7 +522,7 @@ inverse (tree x, tree mask)
>      }
>    else
>      {
> -      rslt = build_int_cst (type, 1);
> +      rslt = build_one_cst (type);
>        for (; ctr; ctr--)
>  	{
>  	  rslt = int_const_binop (MULT_EXPR, rslt, x);
> @@ -670,7 +670,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
>  				- tree_low_cst (bits, 1)));
>  
>    d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
> -			       build_int_cst (niter_type, 1), bits);
> +			       build_one_cst (niter_type), bits);
>    s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
>  
>    if (!exit_must_be_taken)
> @@ -679,7 +679,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final,
>  	 assumptions for divisibility of c.  */
>        assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
>        assumption = fold_build2 (EQ_EXPR, boolean_type_node,
> -				assumption, build_int_cst (niter_type, 0));
> +				assumption, build_zero_cst (niter_type));
>        if (!integer_nonzerop (assumption))
>  	niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
>  					  niter->assumptions, assumption);
> @@ -846,7 +846,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
>  	}
>        else
>  	diff = fold_build2 (MINUS_EXPR, niter_type, step,
> -			    build_int_cst (niter_type, 1));
> +			    build_one_cst (niter_type));
>        bound = fold_build2 (MINUS_EXPR, type,
>  			   TYPE_MAX_VALUE (type), fold_convert (type, diff));
>        assumption = fold_build2 (LE_EXPR, boolean_type_node,
> @@ -867,7 +867,7 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
>  	}
>        else
>  	diff = fold_build2 (MINUS_EXPR, niter_type, step,
> -			    build_int_cst (niter_type, 1));
> +			    build_one_cst (niter_type));
>        bound = fold_build2 (PLUS_EXPR, type,
>  			   TYPE_MIN_VALUE (type), fold_convert (type, diff));
>        assumption = fold_build2 (GE_EXPR, boolean_type_node,
> @@ -963,7 +963,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
>    if (integer_nonzerop (iv0->step))
>      {
>        diff = fold_build2 (MINUS_EXPR, type1,
> -			  iv0->step, build_int_cst (type1, 1));
> +			  iv0->step, build_one_cst (type1));
>  
>        /* We need to know that iv0->base >= MIN + iv0->step - 1.  Since
>  	 0 address never belongs to any object, we can assume this for
> @@ -985,7 +985,7 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
>    else
>      {
>        diff = fold_build2 (PLUS_EXPR, type1,
> -			  iv1->step, build_int_cst (type1, 1));
> +			  iv1->step, build_one_cst (type1));
>  
>        if (!POINTER_TYPE_P (type))
>  	{
> @@ -1083,7 +1083,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
>      {
>        affine_iv zps;
>  
> -      zps.base = build_int_cst (niter_type, 0);
> +      zps.base = build_zero_cst (niter_type);
>        zps.step = step;
>        /* number_of_iterations_lt_to_ne will add assumptions that ensure that
>  	 zps does not overflow.  */
> @@ -1102,7 +1102,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
>    assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
>  
>    s = fold_build2 (MINUS_EXPR, niter_type,
> -		   step, build_int_cst (niter_type, 1));
> +		   step, build_one_cst (niter_type));
>    delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
>    niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
>  
> @@ -1167,13 +1167,13 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
>  	iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
>        else
>  	iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
> -				 build_int_cst (type1, 1));
> +				 build_one_cst (type1));
>      }
>    else if (POINTER_TYPE_P (type))
>      iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
>    else
>      iv0->base = fold_build2 (MINUS_EXPR, type1,
> -			     iv0->base, build_int_cst (type1, 1));
> +			     iv0->base, build_one_cst (type1));
>  
>    bounds_add (bnds, double_int_one, type1);
>  
> @@ -1282,7 +1282,7 @@ number_of_iterations_cond (struct loop *loop,
>        iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
>  					   iv0->step, iv1->step);
>        iv0->no_overflow = false;
> -      iv1->step = build_int_cst (type, 0);
> +      iv1->step = build_zero_cst (type);
>        iv1->no_overflow = true;
>      }
>  
> @@ -1305,7 +1305,7 @@ number_of_iterations_cond (struct loop *loop,
>    /* If the loop exits immediately, there is nothing to do.  */
>    if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
>      {
> -      niter->niter = build_int_cst (unsigned_type_for (type), 0);
> +      niter->niter = build_zero_cst (unsigned_type_for (type));
>        niter->max = double_int_zero;
>        return true;
>      }
> @@ -1946,7 +1946,7 @@ find_loop_niter (struct loop *loop, edge *exit)
>  	{
>  	  /* We exit in the first iteration through this exit.
>  	     We won't find anything better.  */
> -	  niter = build_int_cst (unsigned_type_node, 0);
> +	  niter = build_zero_cst (unsigned_type_node);
>  	  *exit = ex;
>  	  break;
>  	}
> @@ -3017,7 +3017,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
>        type = TREE_TYPE (niter);
>        if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
>  	niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
> -			build_int_cst (type, 0),
> +			build_zero_cst (type),
>  			niter);
>        record_estimate (loop, niter, niter_desc.max,
>  		       last_stmt (ex->src),
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer

Re: [PATCH 2/2] Fix PR47594: Build signed niter expressions

[Richard Guenther]

On Tue, 2 Aug 2011, Sebastian Pop wrote:

> --- a/gcc/graphite-scop-detection.c
> +++ b/gcc/graphite-scop-detection.c
> @@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev)
>    if (chrec_contains_undetermined (scev))
>      return false;
>  
> +  /* FIXME: As long as Graphite cannot handle wrap around effects of
> +     induction variables, we discard them.  */
> +  if (TYPE_UNSIGNED (TREE_TYPE (scev))
> +      && !POINTER_TYPE_P (TREE_TYPE (scev)))
> +    return false;

What does it take to fix that?

Re: [PATCH 2/2] Fix PR47594: Build signed niter expressions

[Sebastian Pop]

On Tue, Aug 2, 2011 at 04:50, Richard Guenther <rguenther@suse.de> wrote:
> On Tue, 2 Aug 2011, Sebastian Pop wrote:
>
>> --- a/gcc/graphite-scop-detection.c
>> +++ b/gcc/graphite-scop-detection.c
>> @@ -196,6 +196,12 @@ graphite_can_represent_scev (tree scev)
>>    if (chrec_contains_undetermined (scev))
>>      return false;
>>
>> +  /* FIXME: As long as Graphite cannot handle wrap around effects of
>> +     induction variables, we discard them.  */
>> +  if (TYPE_UNSIGNED (TREE_TYPE (scev))
>> +      && !POINTER_TYPE_P (TREE_TYPE (scev)))
>> +    return false;
>
> What does it take to fix that?
>

Converting Graphite to ISL.

As I already proposed another solution is to directly insert the loop
exit constraints in the iteration domain polyhedron instead of using
the niter expressions.

Sebastian