[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gcc-patches
Subject:    Re: [PATCH] Sign extend before converting constants to GMP values.
From:       Tobias Grosser <tobias () grosser ! es>
Date:       2011-06-30 18:18:51
Message-ID: 4E0CBE0B.60204 () grosser ! es
[Download RAW message or body]

On 06/30/2011 11:01 AM, Sebastian Pop wrote:
> On Thu, Jun 30, 2011 at 10:03, Richard Guenther<rguenther@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
[prev in list] [next in list] [prev in thread] [next in thread]