On 06/30/2011 11:01 AM, Sebastian Pop wrote:
On Thu, Jun 30, 2011 at 10:03, Richard Guenther<rguent...@suse.de> wrote:
But what do you do for
for (unsigned char i = 128; i< 255; ++i)
? You change 128 to -128 which is wrong.
Yes, 128 gets translated to -128.
And 255 gets translated to -1.
And so the loop iteration domain gets translated in the polyhedral form
as going from -128 to -1 with strides of 1.
So this particular program is not miscompiled by graphite:
int main ()
{
unsigned char j;
int x[300];
for (j = 128; j< 255; j++)
x[j] = j;
for (j = 128; j< 255; j++)
if (x[j] != j)
__builtin_abort ();
return 0;
}
I was trying to build a program that fails to attach to the PR.
So yes, you also have to
deal with modulo arithmetic in graphite.
I'm trying to understand where we have to deal with the modulo arithmetic.
Tobias, what are you doing in Polly?
Do you insert the loop iteration domain constraints with the modulo
of the types?
Hi Sebastian,
this is neither handed correctly in Polly.
Just to be able to understand Polly and Graphite:
LLVM has a different way of representing integer arithmetic. GCC uses
explicit signed and unsigned types, whereas LLVM uses integer types that
do not specify signedness, but on which either signed or unsigned
operations are applied (For operations like add, subtract or multiply
the signed and unsigned operations are actually the same). All
operations in LLVM follow modulo arithmetics, except when they are
marked 'no signed overflow' or 'no unsigned overflow'.
For Polly the correct solution is that as long as the operations are
marked 'no signed overflow' or 'no unsigned overflow' we do not need
modulo arithmetics. Modulo semantics are needed for operations that can
have overflow and for most casts. At the moment we do not allow casts in
Polly and we just assume that no overflow will occur. This is incorrect,
but, as most C code works on signed integers which have undefined
overflow semantics, it works most of the time. My next project is to add
modulo arithmetics to Polly as soon as we cannot prove that no overflow
will occur. This is the last major bug in Polly.
For Graphite I am not sure. Can overflows occur in the signed types of
GCC or follow they the C signed types where overflows are undefined? In
case overflow in signed types is undefined we should be safe as long as
we disallow typecasts. As soon as unsigned types with defined overflow
semantics occur, we most probably need modulo semantics to handle this
correctly.
As a first step to make Graphite correct, I would just bail out if
overflows can occur. Those games with sign extensions may work for the
case where 255 is used as a -1, but in general I do not believe they are
sufficient to express modulo semantics.
Adding real support for modulo semantics is probably the way to go,
however it might be difficult. The first problem is that I do not know
of a convenient way to express modulo semantics in PPL. isl provides so
called existentially quantified dimensions, that allow us to easily
express modulo semantics. In PPL we can express the same by adding
additional dimensions. However, these additional dimensions are not
automatically managed, such that we must ensure manually that they are
handled correctly in the various polyhedral operations we perform.
Also even if we would be able to express modulo semantics, there is
still the problem that we will step into untested terrain. Neither CLooG
nor the other tools have been tested with this. I personally do not
expect a lot of correctness problems, however due to the introduction of
large integer constants and additional dimensions we may face compile
time problems or the creation of non-optimal code. Research wise an
interesting topic.
So as a first step. Would it be OK to limit Graphite to signed types for
the moment and remove the sext hack?
Cheers
Tobi
