Optimization - what is bad on this code ?

[vaclavpe]

Hello all,

I am sorry, but maybe somebody has expierience why the following code is deleted during optimization. I have two functions for printing of numbers (uart_puts() just send string to UART) :
void uart_putux( unsigned int aInt)
{
  unsigned char buf[5];
  unsigned char icnt = 4;

  buf[icnt--] = 0x00;
  while(icnt+1) {
    buf[icnt] = (aInt&0x0f) + 0x30;
    if (buf[icnt] > 0x39) {
      buf[icnt] += 0x07;
    }
    aInt >>= 4;
    icnt--;
  }
  uart_puts( buf);
}

void uart_putlx( unsigned long aInt)
{
  unsigned char buf[9];
  unsigned char icnt = 8;

  buf[icnt--] = 0x00;
  while(icnt+1) {
    buf[icnt] = (aInt&0x0f) + 0x30;
    if (buf[icnt] > 0x39) {
      buf[icnt] += 0x07;
    }
    aInt >>= 4;
    icnt--;
  }
  uart_puts( buf);
}

After I compile and link the code, in .LST I see following:
void uart_putux( unsigned int aInt)
{
 35a: ff cf       rjmp .-2       ; 0x35a <uart_putux>

0000035c <uart_putlx>:
  }
  uart_puts( buf);
}

void uart_putlx( unsigned long aInt)
{
 35c: ff cf       rjmp .-2       ; 0x35c <uart_putlx>

For compilation I use following:
/opt/avr-gcc.4.3.4/bin/avr-gcc -g -mmcu=atmega16 -Wall -Wstrict-prototypes -Os -mcall-prologues -I /opt/avr-gcc.4.3.4/bin/include -fno-inline-small-functions -fno-reorder-blocks -fno-reorder-blocks-and-partition -fno-reorder-functions -fno-toplevel-reorder -fno-move-loop-invariants   -c -o hal.o hal.c

If I remove "-Os", the code is there. But if I understand correctly, gcc sees the code unusable. What is bad inside ? The code worked in older avr-gcc...

Thank you for help,
Vaclav


_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list

[Carl Hamilton]

I can't say why the compiler has thrown out their bodies (I haven't looked at the code that closely), but the "while" loops in both functions will never exit. Since you have declared "icnt" as unsigned, "icnt + 1" will always be true. I'm surprised the the compiler didn't issue a warning along these lines. What warning level are you compiling with?

 - Carl

On Sun, Oct 4, 2009 at 12:33 PM, Vaclav Peroutka <vaclavpe@...> wrote:

Hello all,

I am sorry, but maybe somebody has expierience why the following code is deleted during optimization. I have two functions for printing of numbers (uart_puts() just send string to UART) :
void uart_putux( unsigned int aInt)
{
 unsigned char buf[5];
 unsigned char icnt = 4;

 buf[icnt--] = 0x00;
 while(icnt+1) {
   buf[icnt] = (aInt&0x0f) + 0x30;
   if (buf[icnt] > 0x39) {
     buf[icnt] += 0x07;
   }
   aInt >>= 4;
   icnt--;
 }
 uart_puts( buf);
}

void uart_putlx( unsigned long aInt)
{
 unsigned char buf[9];
 unsigned char icnt = 8;

 buf[icnt--] = 0x00;
 while(icnt+1) {
   buf[icnt] = (aInt&0x0f) + 0x30;
   if (buf[icnt] > 0x39) {
     buf[icnt] += 0x07;
   }
   aInt >>= 4;
   icnt--;
 }
 uart_puts( buf);
}

After I compile and link the code, in .LST I see following:
void uart_putux( unsigned int aInt)
{
 35a:   ff cf           rjmp    .-2             ; 0x35a <uart_putux>

0000035c <uart_putlx>:
 }
 uart_puts( buf);
}

void uart_putlx( unsigned long aInt)
{
 35c:   ff cf           rjmp    .-2             ; 0x35c <uart_putlx>

For compilation I use following:
/opt/avr-gcc.4.3.4/bin/avr-gcc -g -mmcu=atmega16 -Wall -Wstrict-prototypes -Os -mcall-prologues -I /opt/avr-gcc.4.3.4/bin/include -fno-inline-small-functions -fno-reorder-blocks -fno-reorder-blocks-and-partition -fno-reorder-functions -fno-toplevel-reorder -fno-move-loop-invariants   -c -o hal.o hal.c

If I remove "-Os", the code is there. But if I understand correctly, gcc sees the code unusable. What is bad inside ? The code worked in older avr-gcc...

Thank you for help,
Vaclav


_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list

_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list

[Ruud Vlaming]

On Sunday 04 October 2009 22:34, Carl Hamilton wrote:
> I can't say why the compiler has thrown out their bodies (I haven't looked
> at the code that closely), but the "while" loops in both functions will
> never exit.
Well that is enough reason for the compiler to throw away the bodies.
If a function never exits, all code below can never be reached, so is
removed. The peice above is local stuff, and, according to the compiler,
not able to have any side effect to the rest of the code, and can
therefore be deleted ass well. What remains is an infinite loop ....

I want to point out an interresting point however. Probably the idea
of Vaclav was, that the loop will terminate when icnt reaches 0x00,
subsequently icnt--; will make this 0xFF, and while(icnt+1) will
turn this into while(0x00) again, thereby terminating the loop.

This works, IF you use 8 bit arithmetic. So if you compile with
-mint8, the body will stay probably there. But standard C uses 16 bit
arithmetic and the world is different. All chars are promoted to
16 bit before the operators act and casted afterwards. The 8
bit rollover trick does not work in 16 bit wide arithmetic.
The compiler 'knows' this, and therefore correctly concludes
as you mentioned.

Instead of -mint8, it is also possible to change
  unsigned char icnt = 4;
into
   unsigned int icnt = 4;
and now your argument is not valid anymore, since
in 16 bit the rollever trick still works. Thererfore i expect
that the compiler will not remove the code after this change,
even though "icnt+1" seems always be true.

Give it a try.

Ruud

> Since you have declared "icnt" as unsigned, "icnt + 1" will
> always be true. I'm surprised the the compiler didn't issue a warning along
> these lines. What warning level are you compiling with?
>  - Carl
>
> On Sun, Oct 4, 2009 at 12:33 PM, Vaclav Peroutka <vaclavpe@...> wrote:
>
> > Hello all,
> >
> > I am sorry, but maybe somebody has expierience why the following code is
> > deleted during optimization. I have two functions for printing of numbers
> > (uart_puts() just send string to UART) :
> > void uart_putux( unsigned int aInt)
> > {
> >  unsigned char buf[5];
> >  unsigned char icnt = 4;
> >
> >  buf[icnt--] = 0x00;
> >  while(icnt+1) {
> >    buf[icnt] = (aInt&0x0f) + 0x30;
> >    if (buf[icnt] > 0x39) {
> >      buf[icnt] += 0x07;
> >    }
> >    aInt >>= 4;
> >    icnt--;
> >  }
> >  uart_puts( buf);
> > }
> >
> > void uart_putlx( unsigned long aInt)
> > {
> >  unsigned char buf[9];
> >  unsigned char icnt = 8;
> >
> >  buf[icnt--] = 0x00;
> >  while(icnt+1) {
> >    buf[icnt] = (aInt&0x0f) + 0x30;
> >    if (buf[icnt] > 0x39) {
> >      buf[icnt] += 0x07;
> >    }
> >    aInt >>= 4;
> >    icnt--;
> >  }
> >  uart_puts( buf);
> > }
> >
> > After I compile and link the code, in .LST I see following:
> > void uart_putux( unsigned int aInt)
> > {
> >  35a:   ff cf           rjmp    .-2             ; 0x35a <uart_putux>
> >
> > 0000035c <uart_putlx>:
> >  }
> >  uart_puts( buf);
> > }
> >
> > void uart_putlx( unsigned long aInt)
> > {
> >  35c:   ff cf           rjmp    .-2             ; 0x35c <uart_putlx>
> >
> > For compilation I use following:
> > /opt/avr-gcc.4.3.4/bin/avr-gcc -g -mmcu=atmega16 -Wall -Wstrict-prototypes
> > -Os -mcall-prologues -I /opt/avr-gcc.4.3.4/bin/include
> > -fno-inline-small-functions -fno-reorder-blocks
> > -fno-reorder-blocks-and-partition -fno-reorder-functions
> > -fno-toplevel-reorder -fno-move-loop-invariants   -c -o hal.o hal.c
> >
> > If I remove "-Os", the code is there. But if I understand correctly, gcc
> > sees the code unusable. What is bad inside ? The code worked in older
> > avr-gcc...
> >
> > Thank you for help,
> > Vaclav
> >
> >
> > _______________________________________________
> > AVR-GCC-list mailing list
> > AVR-GCC-list@...
> > http://lists.nongnu.org/mailman/listinfo/avr-gcc-list
> >
>

_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list

[David Brown-4]

Ruud Vlaming wrote:

> On Sunday 04 October 2009 22:34, Carl Hamilton wrote:
>> I can't say why the compiler has thrown out their bodies (I haven't looked
>> at the code that closely), but the "while" loops in both functions will
>> never exit.
> Well that is enough reason for the compiler to throw away the bodies.
> If a function never exits, all code below can never be reached, so is
> removed. The peice above is local stuff, and, according to the compiler,
> not able to have any side effect to the rest of the code, and can
> therefore be deleted ass well. What remains is an infinite loop ....
>
> I want to point out an interresting point however. Probably the idea
> of Vaclav was, that the loop will terminate when icnt reaches 0x00,
> subsequently icnt--; will make this 0xFF, and while(icnt+1) will
> turn this into while(0x00) again, thereby terminating the loop.
>
> This works, IF you use 8 bit arithmetic. So if you compile with
> -mint8, the body will stay probably there. But standard C uses 16 bit
> arithmetic and the world is different. All chars are promoted to
> 16 bit before the operators act and casted afterwards. The 8
> bit rollover trick does not work in 16 bit wide arithmetic.
> The compiler 'knows' this, and therefore correctly concludes
> as you mentioned.
>
> Instead of -mint8, it is also possible to change
>   unsigned char icnt = 4;
> into
>    unsigned int icnt = 4;
> and now your argument is not valid anymore, since
> in 16 bit the rollever trick still works. Thererfore i expect
> that the compiler will not remove the code after this change,
> even though "icnt+1" seems always be true.
>
> Give it a try.
>
> Ruud
>

Your explanation is correct (and the 8/16-bit issue explanation was
particularly nice), but your advice at the end is not.  If you want icnt
to be able to store "-1", so that "icnt + 1" is 0, then make icnt a
"signed" value ("int", or for better efficiency, a "signed char" or
"sint8_t").  Static type checking is limited enough in C - don't make it
worse by deliberately lying to the compiler!

Also note that the optimiser may still assume that "icnt + 1" is always
greater than 0, even with icnt changed "unsigned int".  The reason for
this is that the "-fstrict-overflow" flag (enabled at -Os and above)
tells the compiler that any overflows are undefined - thus it knows that
(with unsigned icnt) "icnt + 1" is either greater than icnt and at least
as big as 1, or it is undefined and it can do what it wants.  Therefore,
it is never 0.

This behaviour can be modified by using the "-fwrapv" flag to tell the
compiler that arithmetic uses twos-complement, and thus overflow is
defined.  But that flag needs to be specifically enabled.

<http://gcc.gnu.org/onlinedocs/gcc-4.3.4/gcc/Code-Gen-Options.html#index-fwrapv-1881>
<http://gcc.gnu.org/onlinedocs/gcc-4.3.4/gcc/Optimize-Options.html#index-fstrict_002doverflow-722>

It turns out that the full code /is/ generated when using "unsigned int
icnt", despite the -fstrict-overflow flag.  But just because the
resulting object code is correct, does not mean the source code is correct!

mvh.,

David

>
>
>
>> Since you have declared "icnt" as unsigned, "icnt + 1" will
>> always be true. I'm surprised the the compiler didn't issue a warning along
>> these lines. What warning level are you compiling with?
>>  - Carl
>>
>> On Sun, Oct 4, 2009 at 12:33 PM, Vaclav Peroutka <vaclavpe@...> wrote:
>>
>>> Hello all,
>>>
>>> I am sorry, but maybe somebody has expierience why the following code is
>>> deleted during optimization. I have two functions for printing of numbers
>>> (uart_puts() just send string to UART) :
>>> void uart_putux( unsigned int aInt)
>>> {
>>>  unsigned char buf[5];
>>>  unsigned char icnt = 4;
>>>
>>>  buf[icnt--] = 0x00;
>>>  while(icnt+1) {
>>>    buf[icnt] = (aInt&0x0f) + 0x30;
>>>    if (buf[icnt] > 0x39) {
>>>      buf[icnt] += 0x07;
>>>    }
>>>    aInt >>= 4;
>>>    icnt--;
>>>  }
>>>  uart_puts( buf);
>>> }
>>>
>>> void uart_putlx( unsigned long aInt)
>>> {
>>>  unsigned char buf[9];
>>>  unsigned char icnt = 8;
>>>
>>>  buf[icnt--] = 0x00;
>>>  while(icnt+1) {
>>>    buf[icnt] = (aInt&0x0f) + 0x30;
>>>    if (buf[icnt] > 0x39) {
>>>      buf[icnt] += 0x07;
>>>    }
>>>    aInt >>= 4;
>>>    icnt--;
>>>  }
>>>  uart_puts( buf);
>>> }
>>>
>>> After I compile and link the code, in .LST I see following:
>>> void uart_putux( unsigned int aInt)
>>> {
>>>  35a:   ff cf           rjmp    .-2             ; 0x35a <uart_putux>
>>>
>>> 0000035c <uart_putlx>:
>>>  }
>>>  uart_puts( buf);
>>> }
>>>
>>> void uart_putlx( unsigned long aInt)
>>> {
>>>  35c:   ff cf           rjmp    .-2             ; 0x35c <uart_putlx>
>>>
>>> For compilation I use following:
>>> /opt/avr-gcc.4.3.4/bin/avr-gcc -g -mmcu=atmega16 -Wall -Wstrict-prototypes
>>> -Os -mcall-prologues -I /opt/avr-gcc.4.3.4/bin/include
>>> -fno-inline-small-functions -fno-reorder-blocks
>>> -fno-reorder-blocks-and-partition -fno-reorder-functions
>>> -fno-toplevel-reorder -fno-move-loop-invariants   -c -o hal.o hal.c
>>>
>>> If I remove "-Os", the code is there. But if I understand correctly, gcc
>>> sees the code unusable. What is bad inside ? The code worked in older
>>> avr-gcc...
>>>
>>> Thank you for help,
>>> Vaclav
>>>
>>>
>>> _______________________________________________
>>> AVR-GCC-list mailing list
>>> AVR-GCC-list@...
>>> http://lists.nongnu.org/mailman/listinfo/avr-gcc-list
>>>

_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list

[Ruud Vlaming]

On Monday 05 October 2009 09:53, David Brown wrote:

> Ruud Vlaming wrote:
> > Give it a try.
>
> Your explanation is correct (and the 8/16-bit issue explanation was
> particularly nice), but your advice at the end is not.  
Although that is a matter of taste, this was meant in the sense that
Vaclav should try in order to check if i was correct, not that i meant
that the code is approved just because is works.

I would personally not code it this way because the intentions of the
code are not very obvious (why not make a loop that simply ends
at zero?) although that is a matter of taste too.

> If you want icnt to be able to store "-1", so that "icnt + 1" is 0,
> then make icnt a  "signed" value ("int", or for better efficiency, a
> "signed char" or  "sint8_t").  Static type checking is limited enough
> in C - don't make it worse by deliberately lying to the compiler!
Let it be clear that making use of "overflows" in unsigned arithmetic
is perfectly valid and well defined C code, so he is not lying to the
compiler. If you do not believe me check the C99 standard for it.
For signed types that is an entire different matter, and my advise is,
never rely on any specific behaviour. Since it is explicitly undefined
by the standard.

> Also note that the optimiser may still assume that "icnt + 1" is always
> greater than 0, even with icnt changed "unsigned int".
I think this is incorrect, arithmetic on "unsigned int" is perfectly well
defined, namely, it must be modulo one plus the largest number the
type can represent. See my explanation above.

> The reason for  this is that the "-fstrict-overflow" flag (enabled at
> -Os and above)  tells the compiler that any overflows are undefined
This is only so for signed integers, and makes gcc comply with the
standard. The flag has no influence on unsigned integers.

> thus it knows that (with unsigned icnt) "icnt + 1" is either greater
> than icnt and at least  as big as 1, or it is undefined and it can
> do what it wants.  Therefore, it is never 0.
No, i don't agree. Again, unsigned int arithmetic is well defined
and as far as i know, gcc complies 100%. So you will not come
into a situation that gcc optimizes the body away for unclear
reasons.

> This behaviour can be modified by using the "-fwrapv" flag to tell the
> compiler that arithmetic uses twos-complement, and thus overflow is
> defined.  But that flag needs to be specifically enabled.
Also this flag only applies to signed integers.

Ruud.


_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list

[David Brown-4]

Ruud Vlaming wrote:

> On Monday 05 October 2009 09:53, David Brown wrote:
>
>> Ruud Vlaming wrote:
>>> Give it a try.
>> Your explanation is correct (and the 8/16-bit issue explanation was
>> particularly nice), but your advice at the end is not.  
> Although that is a matter of taste, this was meant in the sense that
> Vaclav should try in order to check if i was correct, not that i meant
> that the code is approved just because is works.
>
> I would personally not code it this way because the intentions of the
> code are not very obvious (why not make a loop that simply ends
> at zero?) although that is a matter of taste too.
>

Fair enough.

>> If you want icnt to be able to store "-1", so that "icnt + 1" is 0,
>> then make icnt a  "signed" value ("int", or for better efficiency, a
>> "signed char" or  "sint8_t").  Static type checking is limited enough
>> in C - don't make it worse by deliberately lying to the compiler!
> Let it be clear that making use of "overflows" in unsigned arithmetic
> is perfectly valid and well defined C code, so he is not lying to the
> compiler. If you do not believe me check the C99 standard for it.

I've just checked, and you're right - unsigned overflow is defined by
the C standards so that "+" is really "plus modulo (UINT_MAX + 1)", and
the value of "icnt" after decrementing from 0 is UINT_MAX (for an
unsigned int).  I guess it is then just a matter of taste - I dislike
writing something that looks like you are setting an unsigned variable
to -1, even though it is well-defined behaviour.

> For signed types that is an entire different matter, and my advise is,
> never rely on any specific behaviour. Since it is explicitly undefined
> by the standard.
>

Agreed.

>> Also note that the optimiser may still assume that "icnt + 1" is always
>> greater than 0, even with icnt changed "unsigned int".
> I think this is incorrect, arithmetic on "unsigned int" is perfectly well
> defined, namely, it must be modulo one plus the largest number the
> type can represent. See my explanation above.
>

Again, you are right - my argument only applies to signed values.

>> The reason for  this is that the "-fstrict-overflow" flag (enabled at
>> -Os and above)  tells the compiler that any overflows are undefined
> This is only so for signed integers, and makes gcc comply with the
> standard. The flag has no influence on unsigned integers.
>
>> thus it knows that (with unsigned icnt) "icnt + 1" is either greater
>> than icnt and at least  as big as 1, or it is undefined and it can
>> do what it wants.  Therefore, it is never 0.
> No, i don't agree. Again, unsigned int arithmetic is well defined
> and as far as i know, gcc complies 100%. So you will not come
> into a situation that gcc optimizes the body away for unclear
> reasons.
>
>> This behaviour can be modified by using the "-fwrapv" flag to tell the
>> compiler that arithmetic uses twos-complement, and thus overflow is
>> defined.  But that flag needs to be specifically enabled.
> Also this flag only applies to signed integers.
>

Thanks for correcting me here.

> Ruud.



_______________________________________________
AVR-GCC-list mailing list
AVR-GCC-list@...
http://lists.nongnu.org/mailman/listinfo/avr-gcc-list