Can gcc.dg/torture/pr67828.c be an infinite loop?

Can gcc.dg/torture/pr67828.c be an infinite loop?

[Aldy Hernandez]

Hi folks.

My upcoming threading improvements turn the test below into an infinite 
runtime loop:

int a, b;
short c;

int
main ()
{
   int j, d = 1;
   for (; c >= 0; c++)
     {
BODY:
       a = d;
       d = 0;
       if (b)
	{
	  xprintf (0);
	  if (j)
	    xprintf (0);
	}
     }
   xprintf (d);
   exit (0);
}

On the false edge out of if(b) we thread directly to BODY, eliding the 
loop conditional, because we know that c>=0 because it could never overflow.

Since B is globally initialized to 0, this has the effect of turning the 
test into an infinite loop.

Is this correct, or did I miss something?
Aldy

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Richard Biener]

On Fri, Sep 24, 2021 at 10:04 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>
> Hi folks.
>
> My upcoming threading improvements turn the test below into an infinite
> runtime loop:
>
> int a, b;
> short c;
>
> int
> main ()
> {
>    int j, d = 1;
>    for (; c >= 0; c++)
>      {
> BODY:
>        a = d;
>        d = 0;
>        if (b)
>         {
>           xprintf (0);
>           if (j)
>             xprintf (0);
>         }
>      }
>    xprintf (d);
>    exit (0);
> }
>
> On the false edge out of if(b) we thread directly to BODY, eliding the
> loop conditional, because we know that c>=0 because it could never overflow.
>
> Since B is globally initialized to 0, this has the effect of turning the
> test into an infinite loop.
>
> Is this correct, or did I miss something?

Yes, 'c' will wrap to negative SHORT_MIN and terminate the loop via
the c>=0 test.

Mind c++ is really (short)(((int)c)++) and signed integer truncation
is implementation
defined.

Richard.

> Aldy
>

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Aldy Hernandez]

On 9/24/21 10:08 AM, Richard Biener wrote:
> On Fri, Sep 24, 2021 at 10:04 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>>
>> Hi folks.
>>
>> My upcoming threading improvements turn the test below into an infinite
>> runtime loop:
>>
>> int a, b;
>> short c;
>>
>> int
>> main ()
>> {
>>     int j, d = 1;
>>     for (; c >= 0; c++)
>>       {
>> BODY:
>>         a = d;
>>         d = 0;
>>         if (b)
>>          {
>>            xprintf (0);
>>            if (j)
>>              xprintf (0);
>>          }
>>       }
>>     xprintf (d);
>>     exit (0);
>> }
>>
>> On the false edge out of if(b) we thread directly to BODY, eliding the
>> loop conditional, because we know that c>=0 because it could never overflow.
>>
>> Since B is globally initialized to 0, this has the effect of turning the
>> test into an infinite loop.
>>
>> Is this correct, or did I miss something?
> 
> Yes, 'c' will wrap to negative SHORT_MIN and terminate the loop via
> the c>=0 test.

Huh, so SHORT_MAX + 1 = SHORT_MIN?  I thought that was an overflow, and 
therefore undefined.

Aldy

> 
> Mind c++ is really (short)(((int)c)++) and signed integer truncation
> is implementation
> defined.
> 
> Richard.
> 
>> Aldy
>>
> 

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[David Brown]

On 24/09/2021 10:59, Aldy Hernandez via Gcc wrote:
> 
> 
> On 9/24/21 10:08 AM, Richard Biener wrote:
>> On Fri, Sep 24, 2021 at 10:04 AM Aldy Hernandez via Gcc
>> <gcc@gcc.gnu.org> wrote:
>>>
>>> Is this correct, or did I miss something?
>>
>> Yes, 'c' will wrap to negative SHORT_MIN and terminate the loop via
>> the c>=0 test.
> 
> Huh, so SHORT_MAX + 1 = SHORT_MIN?  I thought that was an overflow, and
> therefore undefined.
> 

C and C++ don't do arithmetic on "short" (or "char").  They are
immediately promoted to "int" (or "unsigned int", as appropriate).  So
if short is smaller than int, the code behaviour is well defined (as
Richard described below).  If short is the same size as int (such as on
the 16-bit mspgcc port of gcc), however, then SHORT_MAX + 1 /would/ be
an overflow and the compiler can assume it does not happen - thus giving
you an infinite loop.

With more common 32-bit int and 16-bit short, the loop should execute
32768 times.

(At least, that is my understanding.)

> 
>>
>> Mind c++ is really (short)(((int)c)++) and signed integer truncation
>> is implementation
>> defined.
>>
>> Richard.
>>
>>> Aldy
>>>
>>
> 
> 

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Andrew Pinski]

On Fri, Sep 24, 2021 at 1:05 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>
> Hi folks.
>
> My upcoming threading improvements turn the test below into an infinite
> runtime loop:
>
> int a, b;
> short c;
>
> int
> main ()
> {
>    int j, d = 1;
>    for (; c >= 0; c++)
>      {
> BODY:
>        a = d;
>        d = 0;
>        if (b)
>         {
>           xprintf (0);
>           if (j)
>             xprintf (0);
>         }
>      }
>    xprintf (d);
>    exit (0);
> }
>
> On the false edge out of if(b) we thread directly to BODY, eliding the
> loop conditional, because we know that c>=0 because it could never overflow.

Huh about c>=0 being always true? the expression, "c++" is really c=
(short)(((int)c)+1).  So it will definitely wrap over when c is
SHRT_MAX.

Thanks,
Andrew Pinski

>
> Since B is globally initialized to 0, this has the effect of turning the
> test into an infinite loop.
>
> Is this correct, or did I miss something?
> Aldy
>

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Aldy Hernandez]

On 9/24/21 11:29 AM, Andrew Pinski wrote:
> On Fri, Sep 24, 2021 at 1:05 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>>
>> Hi folks.
>>
>> My upcoming threading improvements turn the test below into an infinite
>> runtime loop:
>>
>> int a, b;
>> short c;
>>
>> int
>> main ()
>> {
>>     int j, d = 1;
>>     for (; c >= 0; c++)
>>       {
>> BODY:
>>         a = d;
>>         d = 0;
>>         if (b)
>>          {
>>            xprintf (0);
>>            if (j)
>>              xprintf (0);
>>          }
>>       }
>>     xprintf (d);
>>     exit (0);
>> }
>>
>> On the false edge out of if(b) we thread directly to BODY, eliding the
>> loop conditional, because we know that c>=0 because it could never overflow.
> 
> Huh about c>=0 being always true? the expression, "c++" is really c=
> (short)(((int)c)+1).  So it will definitely wrap over when c is
> SHRT_MAX.

I see.

Is this only for C++ or does it affect C as well?

Aldy

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Andrew Pinski]

On Fri, Sep 24, 2021 at 2:35 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
>
>
> On 9/24/21 11:29 AM, Andrew Pinski wrote:
> > On Fri, Sep 24, 2021 at 1:05 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
> >>
> >> Hi folks.
> >>
> >> My upcoming threading improvements turn the test below into an infinite
> >> runtime loop:
> >>
> >> int a, b;
> >> short c;
> >>
> >> int
> >> main ()
> >> {
> >>     int j, d = 1;
> >>     for (; c >= 0; c++)
> >>       {
> >> BODY:
> >>         a = d;
> >>         d = 0;
> >>         if (b)
> >>          {
> >>            xprintf (0);
> >>            if (j)
> >>              xprintf (0);
> >>          }
> >>       }
> >>     xprintf (d);
> >>     exit (0);
> >> }
> >>
> >> On the false edge out of if(b) we thread directly to BODY, eliding the
> >> loop conditional, because we know that c>=0 because it could never overflow.
> >
> > Huh about c>=0 being always true? the expression, "c++" is really c=
> > (short)(((int)c)+1).  So it will definitely wrap over when c is
> > SHRT_MAX.
>
> I see.
>
> Is this only for C++ or does it affect C as well?

This is standard C code; promotion rules; that is if a type is less
than int, it will be promoted to int if all of the values fit into
int; otherwise it will be promoted to unsigned int.

Thanks,
Andrew Pinski

>
> Aldy
>

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Aldy Hernandez]

On 9/24/21 11:38 AM, Andrew Pinski wrote:
> On Fri, Sep 24, 2021 at 2:35 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 9/24/21 11:29 AM, Andrew Pinski wrote:
>>> On Fri, Sep 24, 2021 at 1:05 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>>>>
>>>> Hi folks.
>>>>
>>>> My upcoming threading improvements turn the test below into an infinite
>>>> runtime loop:
>>>>
>>>> int a, b;
>>>> short c;
>>>>
>>>> int
>>>> main ()
>>>> {
>>>>      int j, d = 1;
>>>>      for (; c >= 0; c++)
>>>>        {
>>>> BODY:
>>>>          a = d;
>>>>          d = 0;
>>>>          if (b)
>>>>           {
>>>>             xprintf (0);
>>>>             if (j)
>>>>               xprintf (0);
>>>>           }
>>>>        }
>>>>      xprintf (d);
>>>>      exit (0);
>>>> }
>>>>
>>>> On the false edge out of if(b) we thread directly to BODY, eliding the
>>>> loop conditional, because we know that c>=0 because it could never overflow.
>>>
>>> Huh about c>=0 being always true? the expression, "c++" is really c=
>>> (short)(((int)c)+1).  So it will definitely wrap over when c is
>>> SHRT_MAX.
>>
>> I see.
>>
>> Is this only for C++ or does it affect C as well?
> 
> This is standard C code; promotion rules; that is if a type is less
> than int, it will be promoted to int if all of the values fit into
> int; otherwise it will be promoted to unsigned int.

Well, *that* was embarrassing.

Thanks, and sorry for the noise.
Aldy

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[David Brown]

On 24/09/2021 11:38, Andrew Pinski via Gcc wrote:
> On Fri, Sep 24, 2021 at 2:35 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>
>>
>>
>> On 9/24/21 11:29 AM, Andrew Pinski wrote:
>>> On Fri, Sep 24, 2021 at 1:05 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>>>>

>>> Huh about c>=0 being always true? the expression, "c++" is really c=
>>> (short)(((int)c)+1).  So it will definitely wrap over when c is
>>> SHRT_MAX.
>>
>> I see.
>>
>> Is this only for C++ or does it affect C as well?
> 
> This is standard C code; promotion rules; that is if a type is less
> than int, it will be promoted to int if all of the values fit into
> int; otherwise it will be promoted to unsigned int.
> 

But remember that for some gcc targets (msp430, AVR, and others), int is
16-bit and the same size as short.  The short still gets promoted to
int, but it will not longer wrap as SHORT_MAX + 1 is an int overflow.

(I've no idea if this is relevant to the code in question, or if that
code is only used on specific targets where short is smaller than int.)

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Richard Earnshaw]

On 24/09/2021 10:29, Andrew Pinski via Gcc wrote:
> On Fri, Sep 24, 2021 at 1:05 AM Aldy Hernandez via Gcc <gcc@gcc.gnu.org> wrote:
>>
>> Hi folks.
>>
>> My upcoming threading improvements turn the test below into an infinite
>> runtime loop:
>>
>> int a, b;
>> short c;
>>
>> int
>> main ()
>> {
>>     int j, d = 1;
>>     for (; c >= 0; c++)
>>       {
>> BODY:
>>         a = d;
>>         d = 0;
>>         if (b)
>>          {
>>            xprintf (0);
>>            if (j)
>>              xprintf (0);
>>          }
>>       }
>>     xprintf (d);
>>     exit (0);
>> }
>>
>> On the false edge out of if(b) we thread directly to BODY, eliding the
>> loop conditional, because we know that c>=0 because it could never overflow.
> 
> Huh about c>=0 being always true? the expression, "c++" is really c=
> (short)(((int)c)+1).  So it will definitely wrap over when c is
> SHRT_MAX.

Except when sizeof(short) == sizeof (int), at which point the 'int' 
expression will overflow and we get UB again.

R.

> 
> Thanks,
> Andrew Pinski
> 
>>
>> Since B is globally initialized to 0, this has the effect of turning the
>> test into an infinite loop.
>>
>> Is this correct, or did I miss something?
>> Aldy
>>

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[David Brown]

On 24/09/2021 10:03, Aldy Hernandez via Gcc wrote:
> Hi folks.
> 
> My upcoming threading improvements turn the test below into an infinite
> runtime loop:
> 
> int a, b;
> short c;
> 
> int
> main ()
> {
>   int j, d = 1;
>   for (; c >= 0; c++)
>     {
> BODY:
>       a = d;
>       d = 0;
>       if (b)
>     {
>       xprintf (0);
>       if (j)
>         xprintf (0);
>     }
>     }
>   xprintf (d);
>   exit (0);
> }
> 
> On the false edge out of if(b) we thread directly to BODY, eliding the
> loop conditional, because we know that c>=0 because it could never
> overflow.
> 
> Since B is globally initialized to 0, this has the effect of turning the
> test into an infinite loop.
> 
> Is this correct, or did I miss something?
> Aldy
> 
> 

I am wondering about the claim that you can use "b" being 0 to optimise
the conditional.  If the compiler knows that this is the complete
program, that is fair enough.  But since "b" is not static, another
compilation unit could modify "b" before "main" is called.  (In C, it is
legal for another part of the code to call main() - perhaps the
implementation of xprintf does so.  And in C++, a global constructor
could change "b" before main() starts.)

mvh.,

David

Re: Can gcc.dg/torture/pr67828.c be an infinite loop?

[Aldy Hernandez]

On 9/24/21 1:37 PM, David Brown wrote:
> On 24/09/2021 10:03, Aldy Hernandez via Gcc wrote:
>> Hi folks.
>>
>> My upcoming threading improvements turn the test below into an infinite
>> runtime loop:
>>
>> int a, b;
>> short c;
>>
>> int
>> main ()
>> {
>>    int j, d = 1;
>>    for (; c >= 0; c++)
>>      {
>> BODY:
>>        a = d;
>>        d = 0;
>>        if (b)
>>      {
>>        xprintf (0);
>>        if (j)
>>          xprintf (0);
>>      }
>>      }
>>    xprintf (d);
>>    exit (0);
>> }
>>
>> On the false edge out of if(b) we thread directly to BODY, eliding the
>> loop conditional, because we know that c>=0 because it could never
>> overflow.
>>
>> Since B is globally initialized to 0, this has the effect of turning the
>> test into an infinite loop.
>>
>> Is this correct, or did I miss something?
>> Aldy
>>
>>
> 
> I am wondering about the claim that you can use "b" being 0 to optimise
> the conditional.  If the compiler knows that this is the complete
> program, that is fair enough.  But since "b" is not static, another
> compilation unit could modify "b" before "main" is called.  (In C, it is
> legal for another part of the code to call main() - perhaps the
> implementation of xprintf does so.  And in C++, a global constructor
> could change "b" before main() starts.)

In this case, it was on a thread where we knew we came through the c>=0 
conditional and we hadn't left the function.

Be that as it may, this was something else entirely.  The problem was a 
typo in the path solver that was causing it to use an incorrect range, 
which was then causing the elision.  It had nothing to do with promotion 
rules.  My bad.

Aldy