Incorrect code with -strides (missing points)
Uday K Bondhugula
With cloog-0.16.3 on the attached .cloog file,
cloog -strides 1 -compilable 4 mathikere.cloog > out.c; gcc out.c;
./a.out
[CLooG] INFO: 1 dimensions (over 5) are scalar.
S2 1 -1 0 3
S2 0 0 0 0
S2 0 0 0 1
S1 0 0 1 1
S2 0 0 1 0
S2 2 0 2 3
S2 1 1 2 0
S2 1 1 2 1
S1 1 1 3 1
S2 1 1 3 0
Number of integral points: 10.
cloog -compilable 4 mathikere.cloog > out.c; gcc out.c; ./a.out
[CLooG] INFO: 1 dimensions (over 5) are scalar.
S1 0 -1 0 1
S1 0 -1 0 2
S2 0 -1 0 2
S2 1 -1 0 3
S2 0 0 0 0
S2 0 0 0 1
S1 0 0 1 1
S2 0 0 1 0
S1 1 0 1 2
S2 1 0 1 1
S2 1 0 1 2
S1 1 0 2 1
S2 1 0 1 3
S1 1 0 2 2
S2 1 0 2 2
S2 2 0 2 3
S2 1 1 2 0
S2 1 1 2 1
S1 1 1 3 1
S2 1 1 3 0
S1 2 1 3 2
S2 2 1 3 1
S2 2 1 3 2
S2 2 1 3 3
Number of integral points: 24.
--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.
Uday K Bondhugula
I'm also able to reproduce this with CLooG 0.17.0-2-g3f88770 gmp
(current git HEAD). There are 24 points in both domains put together.
-Uday
Tobias Grosser
>
> With cloog-0.16.3 on the attached .cloog file,
I looked into this one a little and reduced the test case.
I attached two files:
o mathikere.red.cloog
o mathikere.red-m-set.cloog
= mathikere.red.cloog =
This one still reproduces the original problem, but with a single
statement. When using cloog -compilable 1, cloog sets m at run time to '4'.
This gives for the ourmost loop:
for (c1=0;c1<=min(2,floord(M+2,4));c1+=2) {
for (c2=max(ceild(2*c1-M+1,4),ceild(4*c1-M-2,4));c2<=0;c2++) {
which means (c1,c2) = {(0,0)}
= mathikere.red-m-set.cloog
This one is identical to mathikere.red.cloog, except that we set the
parameter m explicitly to 4 in the cloog file.
This gives the outermost loop:
for (c1=-1;c1<=1;c1++) {
c2 = floord(c1,2);
which means (c1,c2) = {(-1,-1), (0,0), (1,0)}
I currently don't have the time to dig into the cloog code, but this may
be a very good start to dig yourself. Otherwise, I will try to look at
this at the end of the week.
Cheers
Tobi
Cédric Bastoul
--
You got this message because you subscribed to the CLooG Development mailing list.
To send messages to this list, use cloog-development@googlegroups.com
To stop subscribing, send a mail to cloog-development+unsubscribe@googlegroups.com
For more options and to visit the group, http://groups.google.fr/group/cloog-development?hl=en
Tobias Grosser
> Thank you, I'll try to have a look by tomorrow.
Give me another three hours. I am currently trying something out.
Tobi
Sven Verdoolaege
I think you need to check that c is an equality in find_stride.
skimo
Sven Verdoolaege
Of course, you would expect an affine hull to only involve equalities,
so there may be a bug in isl too.
skimo
Tobias Grosser
That seems to work. I post a patch after lunch.
Tobi
Tobias Grosser
inequalities. We need to ignore these inequalities, as the algorithm to
derive the stride of a loop only works on equalities. Applying it on
inequalities yields incorrect results.
Sven Verdoolaege <sk...@kotnet.org>, pointed me to the solution.
Signed-off-by: Tobias Grosser <tob...@grosser.es>
Reported-by: Uday Bondhugula <ud...@csa.iisc.ernet.in>
---
This seems to fix the issue and does not cause any regressions in the CLooG test
suite. Uday, could you check if this works for you?
Tobi
source/isl/domain.c | 5 +++++
test/isl/stride.c | 14 ++++++++++++++
test/isl/stride.cloog | 28 ++++++++++++++++++++++++++++
test/isl/stride.good.c | 31 +++++++++++++++++++++++++++++++
4 files changed, 78 insertions(+), 0 deletions(-)
create mode 100644 test/isl/stride.c
create mode 100644 test/isl/stride.cloog
create mode 100644 test/isl/stride.good.c
diff --git a/source/isl/domain.c b/source/isl/domain.c
index 6c4d8dc..df51bf3 100644
--- a/source/isl/domain.c
+++ b/source/isl/domain.c
@@ -1695,6 +1695,11 @@ static int find_stride(__isl_take isl_constraint *c, void *user)
int n;
isl_int v;
+ if (!isl_constraint_is_equality(c)) {
+ isl_constraint_free(c);
+ return 0;
+ }
+
data = (struct cloog_isl_find_stride_data *)user;
if (data->stride) {
diff --git a/test/isl/stride.c b/test/isl/stride.c
new file mode 100644
index 0000000..ab3ded5
--- /dev/null
+++ b/test/isl/stride.c
@@ -0,0 +1,14 @@
+/* Generated from stride.cloog by CLooG 0.17.0 gmp bits in 0.29s. */
+if (M >= 3) {
+ for (c1=-1;c1<=min(2,floord(M+2,4));c1++) {
+ for (c2=max(ceild(2*c1-M+1,4),ceild(4*c1-M-2,4));c2<=min(0,floord(c1,2));c2++) {
+ for (c3=max(max(-4*c2-2,4*c2+3),4*c1-4*c2+1);c3<=min(min(min(M+3,-4*c2+9),4*c2+2*M),4*c1-4*c2+4);c3++) {
+ for (c4=max(3*c3-4*floord(c3+M+1,2)+6,4*c2-c3-4*floord(-c3+1,4)+2);c4<=min(min(4*c2+4,-c3+10),c3-2);c4+=4) {
+ if ((c2 <= floord(c4-1,4)) && (c2 >= ceild(c4-4,4))) {
+ S1(c1-c2,c2,(c3+c4-2)/4,(c3-c4)/2);
+ }
+ }
+ }
+ }
+ }
+}
diff --git a/test/isl/stride.cloog b/test/isl/stride.cloog
new file mode 100644
index 0000000..c8cd04a
--- /dev/null
+++ b/test/isl/stride.cloog
@@ -0,0 +1,28 @@
+# CLooG script generated automatically by PLUTO 0.7.0
+# language: C
+c
+
+[m] -> {:}
+
+0
+
+# Number of statements
+1
+
+[m] -> { [i0, i1, i2, i3] : 0 <= i2 <= 2 and 1 <= i3 <= m - 2 and i3 >= 4i0 - 2i2 and i3 <= 3 + 4i0 - 2i2 and i3 <= -4i1 + 2i2 and i3 >= -3 - 4i1 + 2i2 }
+
+0 0 0
+
+# we want cloog to set the iterator names
+0
+
+# of scattering functions
+1
+[m] -> { [i0, i1, i2, i3] -> [s0, i1, s2, s3]:
+ i0 = s0 - i1 and 4i2 = -2 + s2 + s3 and 2i3 = s2 - s3 }
+
+
+
+# we will set the scattering dimension names
+0
+
diff --git a/test/isl/stride.good.c b/test/isl/stride.good.c
new file mode 100644
index 0000000..a484a46
--- /dev/null
+++ b/test/isl/stride.good.c
@@ -0,0 +1,31 @@
+/* Generated from ../../../src/cloog/test/isl/stride.cloog by CLooG 0.17.0 gmp bits in 0.29s. */
+extern void hash(int);
+
+/* Useful macros. */
+#define floord(n,d) (((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))
+#define ceild(n,d) (((n)<0) ? -((-(n))/(d)) : ((n)+(d)-1)/(d))
+#define max(x,y) ((x) > (y) ? (x) : (y))
+#define min(x,y) ((x) < (y) ? (x) : (y))
+
+#define S1(i,j,k,l) { hash(1); hash(i); hash(j); hash(k); hash(l); }
+
+void test(int M)
+{
+ /* Scattering iterators. */
+ int c1, c2, c3, c4;
+ /* Original iterators. */
+ int i, j, k, l;
+ if (M >= 3) {
+ for (c1=-1;c1<=min(2,floord(M+2,4));c1++) {
+ for (c2=max(ceild(2*c1-M+1,4),ceild(4*c1-M-2,4));c2<=min(0,floord(c1,2));c2++) {
+ for (c3=max(max(-4*c2-2,4*c2+3),4*c1-4*c2+1);c3<=min(min(min(M+3,-4*c2+9),4*c2+2*M),4*c1-4*c2+4);c3++) {
+ for (c4=max(3*c3-4*floord(c3+M+1,2)+6,4*c2-c3-4*floord(-c3+1,4)+2);c4<=min(min(4*c2+4,-c3+10),c3-2);c4+=4) {
+ if ((c2 <= floord(c4-1,4)) && (c2 >= ceild(c4-4,4))) {
+ S1(c1-c2,c2,(c3+c4-2)/4,(c3-c4)/2);
+ }
+ }
+ }
+ }
+ }
+ }
+}
--
1.7.5.4
Tobias Grosser
With the test case included in the patch I sent, it should be possible
to check why isl introduces inequalities. Though as I don't have any
idea about when isl is supposed to create only equalities, I think I
will not look into this today. ;-)
Tobi
Sven Verdoolaege
> It seems in some cases isl calculates an affine hull, that contains
> inequalities. We need to ignore these inequalities, as the algorithm to
I think you can just classify this as a workaround for a bug in isl.
> Sven Verdoolaege <sk...@kotnet.org>, pointed me to the solution.
There's a "standard" "Helped-by:" tag for this.
> Signed-off-by: Tobias Grosser <tob...@grosser.es>
> Reported-by: Uday Bondhugula <ud...@csa.iisc.ernet.in>
Surely, the problem was reported before you wrote this patch.
In other words, the order is wrong here.
skimo
Sven Verdoolaege
> With the test case included in the patch I sent, it should be
> possible to check why isl introduces inequalities.
Thanks for the "report". I've already fixed this in my copy.
skimo
Tobias Grosser
> On Tue, Feb 21, 2012 at 12:53:24PM +0100, Tobias Grosser wrote:
>> It seems in some cases isl calculates an affine hull, that contains
>> inequalities. We need to ignore these inequalities, as the algorithm to
>
> I think you can just classify this as a workaround for a bug in isl.
If the isl affine hull is supposed to calculate a set that only contains
equality constraints, you should document this. I actually would be
surprised, if you would want to give any guarantee on how isl represents
sets.
As isl does not document any specific structure of constraints after the
affine hull calculation, CLooG relies on assumptions that are not
documented and just don't hold. Until these assumptions are officially
documented this is a CLooG bug. This fix seems to be correct, as it
makes CLooG not rely on these assumptions any more. I think it should go
in (especially as I don't think you ever want to document this).
>> Sven Verdoolaege<sk...@kotnet.org>, pointed me to the solution.
>
> There's a "standard" "Helped-by:" tag for this.
OK.
>> Signed-off-by: Tobias Grosser<tob...@grosser.es>
>> Reported-by: Uday Bondhugula<ud...@csa.iisc.ernet.in>
>
> Surely, the problem was reported before you wrote this patch.
> In other words, the order is wrong here
OK.
Cheers
Tobi
Tobias Grosser
Was the bug only that inequalities where not translated to equalities or
did isl also calculate an incorrect set?
Cheers
Tobi
Sven Verdoolaege
> On 02/21/2012 01:04 PM, Sven Verdoolaege wrote:
> >On Tue, Feb 21, 2012 at 12:53:24PM +0100, Tobias Grosser wrote:
> >>It seems in some cases isl calculates an affine hull, that contains
> >>inequalities. We need to ignore these inequalities, as the algorithm to
> >
> >I think you can just classify this as a workaround for a bug in isl.
>
> If the isl affine hull is supposed to calculate a set that only
> contains equality constraints, you should document this.
Are you challenging me? I may just do that! :-)
> I actually
> would be surprised, if you would want to give any guarantee on how
> isl represents sets.
True, but in the case of an affine hull, I think it's reasonable
to expect that the result only involves equalities.
> As isl does not document any specific structure of constraints after
> the affine hull calculation, CLooG relies on assumptions that are
> not documented and just don't hold. Until these assumptions are
> officially documented this is a CLooG bug. This fix seems to be
> correct, as it makes CLooG not rely on these assumptions any more. I
> think it should go in (especially as I don't think you ever want to
> document this).
Of course it should go it. I was just saying that you can blame isl
in your commit message.
skimo
Sven Verdoolaege
The inequality constraints were redundant and should have been removed
(or not added in the first place).
skimo
Tobias Grosser
> On Tue, Feb 21, 2012 at 01:17:01PM +0100, Tobias Grosser wrote:
>> On 02/21/2012 01:04 PM, Sven Verdoolaege wrote:
>>> On Tue, Feb 21, 2012 at 12:53:24PM +0100, Tobias Grosser wrote:
>>>> It seems in some cases isl calculates an affine hull, that contains
>>>> inequalities. We need to ignore these inequalities, as the algorithm to
>>>
>>> I think you can just classify this as a workaround for a bug in isl.
>>
>> If the isl affine hull is supposed to calculate a set that only
>> contains equality constraints, you should document this.
>
> Are you challenging me? I may just do that! :-)
I just want you to document the features external users can rely on. I
remember you being the person stating that anything undocumented should
not be used.
>> I actually
>> would be surprised, if you would want to give any guarantee on how
>> isl represents sets.
>
> True, but in the case of an affine hull, I think it's reasonable
> to expect that the result only involves equalities.
For internal usage I agree. For external users, I would rather
discourage the use of the constraint interface. Giving additional
guarantees for that interface seems more encouraging than discouraging.
I was actually surprised that the constraint interface was used at all
to calculate the stride. I would rather have calculated the delta
between subsequent iterations, that share the same surrounding loop
indexes. From these deltas, it should be pretty easy to derive the
stride. (If it is a single value, this is the stride. Otherwise it is a
little bit more involved).
Tobi
Sven Verdoolaege
> On 02/21/2012 01:24 PM, Sven Verdoolaege wrote:
> >On Tue, Feb 21, 2012 at 01:17:01PM +0100, Tobias Grosser wrote:
> >>If the isl affine hull is supposed to calculate a set that only
> >>contains equality constraints, you should document this.
> >
> >Are you challenging me? I may just do that! :-)
>
> I just want you to document the features external users can rely on.
> I remember you being the person stating that anything undocumented
> should not be used.
What I was trying to say was that if anyone wants to rely on this,
I may be persuaded to document it.
> I was actually surprised that the constraint interface was used at
> all to calculate the stride. I would rather have calculated the
> delta between subsequent iterations, that share the same surrounding
> loop indexes. From these deltas, it should be pretty easy to derive
> the stride.
Good idea, although I'd compute the difference between an iteration
and any later iteration of the given loop. I suspect that computing
the next iteration may be quite expensive.
> (If it is a single value, this is the stride. Otherwise
> it is a little bit more involved).
isl_set_dim_residue_class can help here.
I know, it's not documented, but it is already being used by CLooG.
Historical note: the isl backend of CLooG grew together with isl,
before there was _any_ documentation.
skimo
Uday K Bondhugula
If it's not documented, one wouldn't expect that. An affine hull can
always be represented with equalities alone, but the output could have
inequalities (representing an equality) - so the inequalities need not
be redundant. Isn't it?
-Uday
>
> skimo
Tobias Grosser
> On Tue, Feb 21, 2012 at 01:35:13PM +0100, Tobias Grosser wrote:
>> On 02/21/2012 01:24 PM, Sven Verdoolaege wrote:
>>> On Tue, Feb 21, 2012 at 01:17:01PM +0100, Tobias Grosser wrote:
>>>> If the isl affine hull is supposed to calculate a set that only
>>>> contains equality constraints, you should document this.
>>>
>>> Are you challenging me? I may just do that! :-)
>>
>> I just want you to document the features external users can rely on.
>> I remember you being the person stating that anything undocumented
>> should not be used.
>
> What I was trying to say was that if anyone wants to rely on this,
> I may be persuaded to document it.
OK. Don't document it. CLooG will not rely on it. (We have now a patch
to check for this explicitly.)
>> I was actually surprised that the constraint interface was used at
>> all to calculate the stride. I would rather have calculated the
>> delta between subsequent iterations, that share the same surrounding
>> loop indexes. From these deltas, it should be pretty easy to derive
>> the stride.
>
> Good idea, although I'd compute the difference between an iteration
> and any later iteration of the given loop. I suspect that computing
> the next iteration may be quite expensive.
In case the constraint interface solution regresses, I would rather
implement this solution than improving the constraint interface.
Tobi
Uday Kumar Reddy B
> It seems in some cases isl calculates an affine hull, that contains
> inequalities. We need to ignore these inequalities, as the algorithm to
> derive the stride of a loop only works on equalities. Applying it on
> inequalities yields incorrect results.
>
> Sven Verdoolaege <sk...@kotnet.org>, pointed me to the solution.
>
> Signed-off-by: Tobias Grosser <tob...@grosser.es>
> Reported-by: Uday Bondhugula <ud...@csa.iisc.ernet.in>
> ---
>
> This seems to fix the issue and does not cause any regressions in the CLooG test
> suite. Uday, could you check if this works for you?
Thanks, this fixes the problem for the .cloog I sent. However, I think
your patch has whitespace error; may want to check before committing.
-Uday
Sven Verdoolaege
> If it's not documented, one wouldn't expect that. An affine hull can
> always be represented with equalities alone, but the output could
> have inequalities (representing an equality) - so the inequalities
> need not be redundant. Isn't it?
If you don't want to depend on this, then I'm ok with that.
skimo
Uday K Bondhugula
Is this stride finding optimization available only with the isl backend?
Thanks,
Sven Verdoolaege
> Is this stride finding optimization available only with the isl backend?
Yes.
skimo
Tobias Grosser
I doubt that:
commit 78d6f8dc9c596fec9814900343dd60783eff51e5
Author: Sven Verdoolaege <sk...@kotnet.org>
Date: Sun Jul 19 12:10:51 2009 +0200
PolyLib backend: cloog_domain_stride: handle singleton domains
The original code didn't recognize this special case and would
produce segmentation faults.
Signed-off-by: Sven Verdoolaege <sk...@kotnet.org>
Is it not rather that the implementation is backend specific and for
other backends possibly not as advanced?
Cheers
Tobi
Sven Verdoolaege
> On 02/21/2012 03:28 PM, Sven Verdoolaege wrote:
> >On Tue, Feb 21, 2012 at 07:52:27PM +0530, Uday K Bondhugula wrote:
> >>Is this stride finding optimization available only with the isl backend?
> >
> >Yes.
>
> I doubt that:
Well, I'm pretty sure that THIS stride finding optimization is
only available in the isl backend.
The PolyLib backend has
/* Check if the given list of domains has a common stride on the given level.
* If so, return a pointer to a CloogStride object. If not, return NULL.
*
* We conservatively return NULL in this backend.
*/
CloogStride *cloog_domain_list_stride(CloogDomainList *list, int level)
{
return NULL;
}
skimo
Tobias Grosser
I should really do such research myself. Sorry for having been lazy.
Tobi
Tobias Grosser
> It seems in some cases isl calculates an affine hull, that contains
> inequalities. We need to ignore these inequalities, as the algorithm to
> derive the stride of a loop only works on equalities. Applying it on
> inequalities yields incorrect results.
>
> Sven Verdoolaege<sk...@kotnet.org>, pointed me to the solution.
>
> Signed-off-by: Tobias Grosser<tob...@grosser.es>
> Reported-by: Uday Bondhugula<ud...@csa.iisc.ernet.in>
The updated patch was pushed in c4b0e672be32ca0f52d830cf9d1e7ed11ab4b3f1.
Tobi
Sven Verdoolaege
> all to calculate the stride. I would rather have calculated the
> delta between subsequent iterations, that share the same surrounding
> loop indexes. From these deltas, it should be pretty easy to derive
> the stride.
You'll be able to find the stride this way, but you still need
to fix up the lower bounds to start at the correct value.
If you extract the stride from a constraint, you can use the
same constraint to adjust the lower bounds.
If you find the stride the way you propose, it's not immediately
obvious to me how you would construct the correct lower bounds.
skimo