[Bug target/50583] New: Many __sync_XXX builtin functions are incorrect

[Bug target/50583] New: Many __sync_XXX builtin functions are incorrect

[hjl.tools at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50583

             Bug #: 50583
           Summary: Many __sync_XXX builtin functions are incorrect
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: hjl.tools@gmail.com
                CC: kirill.yukhin@intel.com, ubizjak@gmail.com


We have

`TYPE __sync_fetch_and_add (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_sub (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_or (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_and (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_xor (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_nand (TYPE *ptr, TYPE value, ...)'
     These builtins perform the operation suggested by the name, and
     returns the value that had previously been in memory.  That is,

          { tmp = *ptr; *ptr OP= value; return tmp; }
          { tmp = *ptr; *ptr = ~(tmp & value); return tmp; }   // nand

On x86, they may be implemented as

[hjl@gnu-33 gcc]$ cat /tmp/x.c
int
foo (int *p)
{
  return __sync_fetch_and_and(p, 7);
}
[hjl@gnu-33 gcc]$ gcc -S -O2 /tmp/x.c
[hjl@gnu-33 gcc]$ cat x.s
    .file    "x.c"
    .text
    .p2align 4,,15
    .globl    foo
    .type    foo, @function
foo:
.LFB0:
    .cfi_startproc
    movl    (%rdi), %eax
.L2:
    movl    %eax, %edx
    movl    %eax, %ecx
    andl    $7, %edx
    lock cmpxchgl    %edx, (%rdi)
    jne    .L2
    movl    %ecx, %eax
    ret
    .cfi_endproc
.LFE0:
    .size    foo, .-foo
    .ident    "GCC: (GNU) 4.6.0 20110603 (Red Hat 4.6.0-10)"
    .section    .note.GNU-stack,"",@progbits
[hjl@gnu-33 gcc]$ 

This isn't equivalent to 

 { tmp = *ptr; *ptr OP= value; return tmp; }

It is

 {
   tmp = *ptr;
   tmp1 = tmp OP value;
   return __sync_val_compare_and_swap (ptr, tmp, tmp1);
}

The only thing supported on x86 are


[hjl@gnu-33 gcc]$ cat /tmp/y.c 
int
foo1 (int *p)
{
  return __sync_fetch_and_add (p, 7);
}

int
foo2 (int *p)
{
  return __sync_fetch_and_sub (p, 7);
}
[hjl@gnu-33 gcc]$ gcc -S -O2 /tmp/y.c
[hjl@gnu-33 gcc]$ cat y.s
    .file    "y.c"
    .text
    .p2align 4,,15
    .globl    foo1
    .type    foo1, @function
foo1:
.LFB0:
    .cfi_startproc
    movl    $7, %eax
    lock xaddl    %eax, (%rdi)
    ret
    .cfi_endproc
.LFE0:
    .size    foo1, .-foo1
    .p2align 4,,15
    .globl    foo2
    .type    foo2, @function
foo2:
.LFB1:
    .cfi_startproc
    movl    $-7, %eax
    lock xaddl    %eax, (%rdi)
    ret
    .cfi_endproc
.LFE1:
    .size    foo2, .-foo2
    .ident    "GCC: (GNU) 4.6.0 20110603 (Red Hat 4.6.0-10)"
    .section    .note.GNU-stack,"",@progbits
[hjl@gnu-33 gcc]$

[Bug target/50583] Many __sync_XXX builtin functions are incorrect

[hjl.tools at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50583

--- Comment #1 from H.J. Lu <hjl.tools at gmail dot com> 2011-09-30 16:57:14 UTC ---
We have 2 choices:

1. Update document of

`TYPE __sync_fetch_and_add (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_sub (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_or (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_and (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_xor (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_fetch_and_nand (TYPE *ptr, TYPE value, ...)'

to

 {
   tmp = *ptr;
   tmp1 = tmp OP value;
   return __sync_val_compare_and_swap (ptr, tmp, tmp1);
 }

2. Remove those __sync_fetch_and_XXX which aren't

 { tmp = *ptr; *ptr OP= value; return tmp; }

Since only

 { tmp = *ptr; *ptr OP= value; return tmp; }

can be used to implement locks, I think we should do 2.

[Bug target/50583] Many __sync_XXX builtin functions are incorrect

[amacleod at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50583

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> 2011-09-30 18:25:51 UTC ---
Technically it is closer to 

do { 
  tmp = *ptr;
  tmp1 = tmp OP value;
} while (__sync_val_compare_and_swap (ptr, tmp, tmp1) != tmp);
return tmp;

except it uses the new value of tmp from the CAS rather than reloading it
again.

It loops performing OP on the new value of tmp until the CAS is successful.
Functionally it is identical, what is your case where it can't be used?

The only difference I see is that another very hostile process which constantly
changes *ptr may prevent forward progress from ever happening, resulting in an
infinite loop.  

At the moment we aren't making any guarantees of forward progress, although I
think at some point we may want to add a flag to the compiler as it becomes
more of an issue.   With a flag like that enabled, a CAS loop would not be a
valid implementation.

[Bug target/50583] Many __sync_XXX builtin functions are incorrect

[hjl.tools at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50583

--- Comment #3 from H.J. Lu <hjl.tools at gmail dot com> 2011-09-30 18:37:42 UTC ---
The same problem with

`TYPE __sync_add_and_fetch (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_sub_and_fetch (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_or_and_fetch (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_and_and_fetch (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_xor_and_fetch (TYPE *ptr, TYPE value, ...)'
`TYPE __sync_nand_and_fetch (TYPE *ptr, TYPE value, ...)'
     These builtins perform the operation suggested by the name, and
     return the new value.  That is,

          { *ptr OP= value; return *ptr; }
          { *ptr = ~(*ptr & value); return *ptr; }   // nand

[hjl@gnu-33 pr50583]$ cat z.i
int
foo (int *p)
{
  return __sync_and_and_fetch (p, 7);
}
[hjl@gnu-33 pr50583]$ gcc -O2 -S z.i
[hjl@gnu-33 pr50583]$ cat z.s
    .file    "z.i"
    .text
    .p2align 4,,15
    .globl    foo
    .type    foo, @function
foo:
.LFB0:
    .cfi_startproc
    movl    (%rdi), %eax
.L2:
    movl    %eax, %edx
    andl    $7, %edx
    lock cmpxchgl    %edx, (%rdi)
    jne    .L2
    movl    %edx, %eax
    ret
    .cfi_endproc
.LFE0:
    .size    foo, .-foo
    .ident    "GCC: (GNU) 4.6.0 20110603 (Red Hat 4.6.0-10)"
    .section    .note.GNU-stack,"",@progbits
[hjl@gnu-33 pr50583]$ 

It is

 {
   tmp = *ptr;
   do
     {
       tmp1 = tmp OP value;
     }
   while (__sync_val_compare_and_swap (ptr, tmp, tmp1) != tmp);
   return tmp1;
 }

If *ptr is changed between load and cmpxchg, we get an infinite loop.

[Bug target/50583] Many __sync_XXX builtin functions are incorrect

[hjl.tools at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50583

--- Comment #4 from H.J. Lu <hjl.tools at gmail dot com> 2011-09-30 18:47:21 UTC ---
I guess it is OK.

[Bug target/50583] Many __sync_XXX builtin functions are incorrect

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50583

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |jakub at gcc dot gnu.org
         Resolution|                            |INVALID

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-09-30 18:49:29 UTC ---
(In reply to comment #3)

>     movl    (%rdi), %eax
> .L2:
>     movl    %eax, %edx
>     andl    $7, %edx
>     lock cmpxchgl    %edx, (%rdi)
>     jne    .L2
>     movl    %edx, %eax

> It is
> 
>  {
>    tmp = *ptr;
>    do
>      {
>        tmp1 = tmp OP value;
>      }
>    while (__sync_val_compare_and_swap (ptr, tmp, tmp1) != tmp);
>    return tmp1;
>  }
> 
> If *ptr is changed between load and cmpxchg, we get an infinite loop.

No, you aren't translating the asm correctly back into C.
It is
  tmp = *ptr;
  do
    tmp1 = tmp OP value; tmp2 = tmp;
  while ((tmp = __sync_val_compare_and_swap (ptr, tmp2, tmp1) != tmp2);
  return tmp1;
because cmpxchgl instruction loads the *ptr value from memory into %eax if the
instruction has been unsuccessful.  So, tmp is loaded with the new value for
the next iteration.