Optimizer bug with pre-decrement operator

[jullien]

First, I apologize because I'm unable to give you a simple code sample that shows the bug.

My code manages an internal stack with following macro:

#define   olpush( x )   (*--olfstack = ((POINTER)x))

I have a case where this macro 'looks' to push value before olfstack is decremented.
If I compile with any optimization option (-O1, -O2, -Ox), the offending function hangs because values are not pushed at the right place.

If I replace this macro by

#define   olpush( x )   (--olfstack, *olfstack = ((POINTER)x))

Which force decrement before value is set, it works well with any optimization levels as it was the case with all Pelles C version since 2008.

I tried to reproduce this bug with the following tests but, unfortunately, it is too simple to let this bug happen.

#include <stdio.h>

int stack[100];
int* pstack = &stack[0];

#define push(x)      (*--pstack = x)
#define   stackval( n )   (*(pstack + (n)))

void
foo(int a, int b) {
   (void)printf("Ko: %d %d\n", a, b);
}

int
main(int argc, char** argv)
{
   int n;

   push(10);
   printf("stack: %p [%d]\n", pstack, *(pstack));
   push(20);
   printf("stack: %p [%d]\n", pstack, *(pstack));
   n = 2;
   foo(stackval(1), stackval(0));
   while (n > 0) {
      int a = stackval(--n);
      int b = stackval(--n);
      foo( a, b);
   }
   return 0;
}

[frankie]

From operators precedence in C (i.e. see here) the dereference operator (*) and the prefix increment and decrement (++expr or --expr) have the same precedence. In this case it is not defined which operation will be executed first (compiler dependent).
Maybe the new optimization strategies have changed past behaviours of compiler (if you had correct result in the past).
Not 100% sure, but the solution should be be very simple: force precedence using parenthesis.

Code: [Select]

#define   olpush( x )   (*(--olfstack) = ((POINTER)x))Considering that the suffix/postfix increment and decrement (expr++ and expr--) have a higher precedence than dereferencing, strange to say, but also this should work:

Code: [Select]

#define   olpush( x )   (*olfstack-- = ((POINTER)x))Because I'm not very confident that the last could work I will appreciate if you can check and let us know the results with both 

[jullien]

Thank you for the hint, unfortunately

#define   olpush( x )   (*(--olfstack) = ((POINTER)x))

raises the same bug.

The original macro produced no error in the past 25 years and with probably more than 100 different C/C++ compilers (even on zOS 390, the more curious machine I ever seen)
Please also note that this happens only with optimizer. An optimizer is supposed to keep the same semantic while generating more efficient code (I confess this is not always true but at least is should).

Christian

[frankie]

Hi Christian,
In the checks I made the compiler seems to behave as expected: as it has for you in the past 25 years with any compiler. It decrements pointer than fetches the data 
Your problem should come from a very specific code formation, difficult to reproduce.
Does it happens in a specific point or happens randomly in all the code?
Maybe when the problem happens the parameter 'x' is an expression not a simple value? In this case enclosing it in parenthesis make any difference?

Code: [Select]

#define   olpush( x )   (*(--olfstack) = ((POINTER)(x)))

[jullien]

Sure, simple tests work well.
I'll try hard to find a snippet that fails.
I'll also check assembler.
Don't expect new inputs pretty soon.

Christian

[jullien]

Rhaa! as I don't like bugs, even if they are not mines, here is assembly code that show why original macro generates a wrong code:

If I use (buggy) macro
#define   olpush( x )   (*--olfstack = ((POINTER)x))
   
line 502:   olpush( (POINTER)100 );
line 503:   olpush( (POINTER)200 );

are compiled into

#line 502 "olinit.c"
sub qword [($olmemheader+1136) wrt rip],8
mov rax,qword [($olmemheader+1136) wrt rip]
mov qword [rax-( 8 )],0x64
#line 503 "olinit.c"
sub qword [($olmemheader+1136) wrt rip],8
mov rax,qword [($olmemheader+1136) wrt rip]
mov qword [rax-( 8 )],0xc8

As you can see, olfstack ($olmemheader+1136) is first decremented, which is correct but value 100 (0x64) is then incorrectly set at [rax-( 8 )] while it should simply go to [rax]


Now, modified macro which works
#define   olpush( x )   (--olfstack, *olfstack = ((POINTER)x))

is compiled into:
#line 502 "olinit.c"
sub qword [($olmemheader+1136) wrt rip],8
mov rax,qword [($olmemheader+1136) wrt rip]
mov qword [rax],0x64
#line 503 "olinit.c"
sub qword [($olmemheader+1136) wrt rip],8
mov rax,qword [($olmemheader+1136) wrt rip]
mov qword [rax],0xc8

Which is the code I expect

Orginal macro with optim turned off compiles into

#line 502 "olinit.c"
mov rax,qword [($olmemheader+1136) wrt rip]
lea rax,[rax+(-8)]
mov qword [($olmemheader+1136) wrt rip],rax
mov qword [rax],0x64
#line 503 "olinit.c"
mov rax,qword [($olmemheader+1136) wrt rip]
lea rax,[rax+(-8)]
mov qword [($olmemheader+1136) wrt rip],rax
mov qword [rax],0xc8

[frankie]

Mmmh quite an optimizer bug! 
It updates the pointer than ... stores the value at a position decremented again... 

[JohnF]

Christian,

In the example you posted above you are writing into addresses before the array.

John
 

[jullien]

Ouch you're right.
I ment:
int* pstack = &stack[100];

I quickly wrote this sample in hope to reproduce the bug. Owever, the assembler lines are from real code and show the optimizer bug.

[Pelle]

Somewhat chaotic info here, but I will see what I can do...

[jullien]

Got it!
Here is a simplified code that show the bug (I'm sure struct OBJECT is envolved but pstack part of a struct definitely is):

#include <stdio.h>

typedef struct OBJECT *   POINTER;

struct  OBJECT  {
   union   value {
      POINTER CVAL;
      int   IVAL;
      struct  {
         unsigned char   CONSTANT;
         unsigned char   ARITY;
      } SYMBOL;
   } VAL;
};


POINTER stack[100];

struct header {
   POINTER   *pstack;
} hdr;

#define push(x)     (*--hdr.pstack = x)
#define stackval(n) (*(hdr.pstack + (n)))

int
main(int argc, char** argv)
{
   int n;
   hdr.pstack = &stack[100];

   push((POINTER)10);
   push((POINTER)20);
   return 0;
}

It compiles to:

#line 33 "foo.c"
sub qword [($hdr) wrt rip],8
mov rax,qword [($hdr) wrt rip]
mov qword [rax-(8)],0x14

where rax is substracted with an extra 8

[neo313]

Simplified version:

Code: [Select]

#include <stdio.h>

struct header
{
   int* p ;
} ;

struct header str ;

int main( void )
{
int stack[10];
str.p = &stack[10] ;

*(--str.p) = 12345 ;

if( stack[9] != 12345 )
printf("ERROR!\n") ;
return 0;
}

My conclusion:

Bug only appears if the struct is defined in file scope or is static.
A struct must be used; if the member of the struct replaces the struct, the bug is removed.
Parenthesis around the decrement don't affect the bug.
str.p = &stack[10] ; is not undefined behavior, as Standard allows to point one past the array.
Bug will appear with any type of optimization.
Splitting the line *--str.p = 12345 ; into two lines --str.p ; and *str.p = 12345 ; removes the bug.
*(str.p-1) = 12345 ; will remove the bug.
Using a union instead of the struct will keep the bug even if the union is local.

[jullien]

Fixed in RC6

Thanks all

Christian