Re: [RFC] Builtins for C++26 integer atomic reductions

After offline discussion I thought it might be helpful to give a more 
detailed explanation of the reason the memory-model semantics require 
new builtins for these reduction operations.  Below I have an explicit 
work-through of the first example given in the proposal for reduction 
operations (the one Soumya referenced) -- http://wg21.link/p3111 .

The examples below are all in a "litmus" test format which is the
format for memory model simulating programs.  Initial values are at
the top, each function is performed by a different thread, at the
bottom we assert that it's not possible for thread 2 to have r1=2 and
thread 1 to have r0=0.  There are some C litmus tests and some ASM
litmus tests.  The ASM litmus tests can be ran & checked online at
https://diy.inria.fr/www/ without downloading anything, I believe the
C litmus tests require downloading a relevant tool -- for the
reduction operations you need https://github.com/hernanponcedeleon/Dat3M

Here we show that the behaviour of a relaxed atomic load & CAS blocks
reordering around the thread fence.  This happens as a fence-fence
synchronisation is formed between the fences in P1 and P0 if the read in
P1 reads the value written in P0.  N.b. Though not necessary I check
`worked` as well to make it clear this is the case when the CAS
succeeds and hence we don't have to ask the model to check a loop.
#+BEGIN_EXAMPLE
     C CAS
     { [x] = 0; [y] = 0; }
         P0(atomic_int* y,atomic_int* x) {
           atomic_store_explicit(x,1,memory_order_relaxed);
           atomic_thread_fence(memory_order_release);
           atomic_store_explicit(y,1,memory_order_relaxed);
         }

         P1(atomic_int* y,atomic_int* x, atomic_int *val) {
           int v = atomic_load_explicit(y, memory_order_relaxed);
           *val = v;
           int worked = atomic_compare_exchange_strong_explicit(y, val, 
v+1, memory_order_relaxed, memory_order_relaxed);
           atomic_thread_fence(memory_order_acquire);
           int r0 = atomic_load_explicit(x,memory_order_relaxed);
         }

         P2(atomic_int* y) {
           int r1 = atomic_load_explicit(y,memory_order_relaxed);
         }
         ~exists (2:r1=2 /\ 1:r0=0 /\ 1:worked=1)
#+END_EXAMPLE

When running this under a memory model simulator we see that it
claims the property PASS'es -- i.e. that the above set of values is
not possible.
#+BEGIN_EXAMPLE
     vshcmd: > export DAT3M_HOME=$HOME/repos/memory-model-tools/Dat3M
     vshcmd: > export DAT3M_OUTPUT=${DAT3M_HOME}/output
     vshcmd: > echo && \
     vshcmd: > java -jar ${DAT3M_HOME}/dartagnan/target/dartagnan.jar \
     vshcmd: >      ${DAT3M_HOME}/cat/rc11.cat \
     vshcmd: >      --property=program_spec \
     vshcmd: >      --target=c11 \
     vshcmd: >      cas-example.litmus
     Dat3M [14:42:27] $ Dat3M [14:42:27] $ > > > > >
     Test: cas-example.litmus
     Result: PASS
     Time: 0.299 secs
     Dat3M [14:42:28] $
#+END_EXAMPLE

The current codegen for this (massaged a little to remove branches)
gives us the below litmus test.  Similar to the C litmus tests this
has initialisation at the top, but here what each thread does is
written in a different column.
#+BEGIN_EXAMPLE
     AArch64 Instruction cas
     {
        0:X0=y; 0:X1=x; 0:X2=0; 0:X3=0; 0:X4=0;
        1:X0=y; 1:X1=x; 1:X2=0; 1:X3=0; 1:X4=0;
        2:X0=y; 2:X1=x; 2:X2=0; 2:X3=0; 2:X4=0;
     }
     P0               |P1                   |P2                ;
     MOV     X2, #1   |LDR     X2, [X0]     |LDR     X3, [X0]  ;
     STR     X2, [X1] |ADD     X4, X2, #1   |                  ;
     DMB     ISHLD    |MOV     X3, X2       |                  ;
     DMB     ISHST    |CAS     X3, X4, [X0] |                  ;
     STR     X2, [X0] |DMB     ISHLD        |                  ;
                      |LDR     X4, [X1]     |                  ;
     ~exists (2:X3=2 /\ 1:X4=0 /\ 1:X2=1:X3)
#+END_EXAMPLE

As should be the case, this satisfies the limitation that the source
code requires.
#+BEGIN_EXAMPLE
     vshcmd: > export DAT3M_HOME=$HOME/repos/memory-model-tools/Dat3M
     vshcmd: > export DAT3M_OUTPUT=${DAT3M_HOME}/output
     vshcmd: > echo && \
     vshcmd: > java -jar ${DAT3M_HOME}/dartagnan/target/dartagnan.jar \
     vshcmd: >      ${DAT3M_HOME}/cat/aarch64.cat \
     vshcmd: >      --property=program_spec \
     vshcmd: >      --target=arm8 \
     vshcmd: >      cas-asm-example.litmus
     Dat3M [14:47:15] $ Dat3M [14:47:15] $ > > > > >
     Test: cas-asm-example.litmus
     Result: PASS
     Time: 0.254 secs
     Dat3M [14:47:16] $
#+END_EXAMPLE

This could be pattern-matched to an LDADD (equivalent of fetch_op):
#+BEGIN_EXAMPLE
     AArch64 Instruction fetch_op
     {
        0:X0=y; 0:X1=x; 0:X2=0; 0:X3=0; 0:X4=0;
        1:X0=y; 1:X1=x; 1:X2=0; 1:X3=0; 1:X4=0;
        2:X0=y; 2:X1=x; 2:X2=0; 2:X3=0; 2:X4=0;
     }
     P0               |P1                   |P2                ;
     MOV     X2, #1   |MOV     X2, #1       |LDR     X3, [X0]  ;
     STR     X2, [X1] |LDADD   X2, X2, [X0] |                  ;
     DMB     ISHLD    |DMB     ISHLD        |                  ;
     DMB     ISHST    |LDR     X4, [X1]     |                  ;
     STR     X2, [X0] |                     |                  ;
     ~exists (2:X3=2 /\ 1:X4=0)
#+END_EXAMPLE
#+BEGIN_EXAMPLE
     vshcmd: > export DAT3M_HOME=$HOME/repos/memory-model-tools/Dat3M
     vshcmd: > export DAT3M_OUTPUT=${DAT3M_HOME}/output
     vshcmd: > echo && \
     vshcmd: > java -jar ${DAT3M_HOME}/dartagnan/target/dartagnan.jar \
     vshcmd: >      ${DAT3M_HOME}/cat/aarch64.cat \
     vshcmd: >      --property=program_spec \
     vshcmd: >      --target=arm8 \
     vshcmd: >      fetch-asm-example.litmus
     Dat3M [14:49:49] $ Dat3M [14:49:49] $ > > > > >
     Test: fetch-asm-example.litmus
     Result: PASS
     Time: 0.259 secs
     Dat3M [14:49:50] $
#+END_EXAMPLE

But the instruction sequence we're looking to enable is STADD instead
of LDADD.  This does not trigger the same fence-fence
synchronisation:
#+BEGIN_EXAMPLE
     AArch64 Instruction reduction
     {
        0:X0=y; 0:X1=x; 0:X2=0; 0:X3=0; 0:X4=0;
        1:X0=y; 1:X1=x; 1:X2=0; 1:X3=0; 1:X4=0;
        2:X0=y; 2:X1=x; 2:X2=0; 2:X3=0; 2:X4=0;
     }
     P0               |P1               |P2                ;
     MOV     X2, #1   |MOV     X2, #1   |LDR     X3, [X0]  ;
     STR     X2, [X1] |STADD   X2, [X0] |                  ;
     DMB     ISHLD    |DMB     ISHLD    |                  ;
     DMB     ISHST    |LDR     X4, [X1] |                  ;
     STR     X2, [X0] |                 |                  ;
     ~exists (2:X3=2 /\ 1:X4=0)
#+END_EXAMPLE
#+BEGIN_EXAMPLE
     vshcmd: > export DAT3M_HOME=$HOME/repos/memory-model-tools/Dat3M
     vshcmd: > export DAT3M_OUTPUT=${DAT3M_HOME}/output
     vshcmd: > echo && \
     vshcmd: > java -jar ${DAT3M_HOME}/dartagnan/target/dartagnan.jar \
     vshcmd: >      ${DAT3M_HOME}/cat/aarch64.cat \
     vshcmd: >      --property=program_spec \
     vshcmd: >      --target=arm8 \
     vshcmd: >      reduction-asm-example.litmus
     Dat3M [15:38:02] $ Dat3M [15:38:02] $ > > > > >
     Test: reduction-asm-example.litmus
     Result: FAIL
     Reason: Program specification violation found
     Condition: not_exists (2:X3 == bv64(2)) && (1:X4 == bv64(0))
     Time: 0.271 secs
     Dat3M [15:38:03] $
#+END_EXAMPLE

The new C++26 reductions have the same relaxation as this STADD
instruction.
#+BEGIN_EXAMPLE
     C Reduction behaviour
     { [x] = 0; [y] = 0; }
         P0(atomic_int* y,atomic_int* x) {
           atomic_store_explicit(x,1,memory_order_relaxed);
           atomic_thread_fence(memory_order_release);
           atomic_store_explicit(y,1,memory_order_relaxed);
         }

         P1(atomic_int* y,atomic_int* x) {
           atomic_store_add_explicit(y,1,memory_order_relaxed);
           atomic_thread_fence(memory_order_acquire);
           int r0 = atomic_load_explicit(x,memory_order_relaxed);
         }

         P2(atomic_int* y) {
           int r1 = atomic_load_explicit(y,memory_order_relaxed);
         }
         ~exists (2:r1=2 /\ 1:r0=0)
#+END_EXAMPLE
#+BEGIN_EXAMPLE
     vshcmd: > export DAT3M_HOME=$HOME/repos/memory-model-tools/Dat3M
     vshcmd: > export DAT3M_OUTPUT=${DAT3M_HOME}/output
     vshcmd: > echo && \
     vshcmd: > java -jar ${DAT3M_HOME}/dartagnan/target/dartagnan.jar \
     vshcmd: >      ${DAT3M_HOME}/cat/rc11.cat \
     vshcmd: >      --property=program_spec \
     vshcmd: >      --target=c11 \
     vshcmd: >      reduction-example.litmus
     Dat3M [14:41:13] $ Dat3M [14:41:13] $ > > > > >
     Test: reduction-example.litmus
     Result: FAIL
     Reason: Program specification violation found
     Condition: not_exists (2:r1 == bv64(2)) && (1:r0 == bv64(0))
     Time: 0.253 secs
     Dat3M [14:41:13] $
#+END_EXAMPLE

This means that the CAS loop source-level construct specifies
restrictions that block the use of STADD (and similar for other "not
a read" instructions implementing different operations), but the new
reductions do not.  This is why we believe builtins are necessary to
emit the most optimal code for these reductions.
It is possible to implement the reductions correctly without new 
builtins -- just not optimally.

On 4/14/26 11:21, Soumya AR wrote:
> Ping. (Also summarizing some relevant discussions on IRC)
> 
> We don't think these can be implemented using pattern-matching, as fetch_ops or
> CAS loops produce visible reads, while reductions do not.
> 
> Therefore, pattern-matching an unused fetch_op result into a reduction would
> remove the visible read, which could violate memory orderings.
> 
> Even if the fetch_op is in RELAXED memory ordering, fences can still synchronize
> on that visible read, as is seen in the Litmus test from Will Deacon in
> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3111r8.html.
> 
> Given these constraints, and knowing the best possible approach is ideally
> one that uses the least builtins, is it OK to implement this using Option 1?
> 
> Thanks,
> Soumya
> 
>> On 24 Feb 2026, at 11:57 AM, Soumya AR <[email protected]> wrote:
>>
>> Hi,
>>
>> I'm working on implementing support for C++26 atomic reductions in GCC.
>>
>> Corresponding paper for this:
>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3111r8.html
>>
>> I'd like to get some insight into the preferable builtin interface. As I see it,
>> we have the following options:
>>
>> Option 1 (that we expect to implement): One generic builtin per new operation
>>
>> We add the generic builtin for each new operation and resolve it in the
>> middle-end later. This is similar to the atomic int fetch_min/max implementation
>> in this patch:
>>
>> https://gcc.gnu.org/pipermail/gcc-patches/2026-January/706242.html
>>
>> This would result in 7 new builtins, 1 for each new operation.
>>
>> Option 2: Explicit builtins per operation and their types:
>>
>> This would follow the existing pattern and add a new family of builtins.
>> Assuming we name them __atomic_store_<op>, we would have:
>> __atomic_store_add,
>> __atomic_store_sub,
>> __atomic_store_and,
>> __atomic_store_or,
>> __atomic_store_xor,
>> __atomic_store_max,
>> __atomic_store_min,
>> and all of their typed variants (_N, _1, _2, _4, _8, _16), resulting in 42 new
>> builtins.
>>
>> However, this would again result in the earlier issue of a builtin explosion
>> wrt integer fetch min/max discussed here:
>> https://gcc.gnu.org/pipermail/gcc-patches/2025-November/699602.html
>>
>> Option 3: Extend existing __atomic_fetch_* builtins
>>
>> Add a parameter to the existing __atomic_fetch_* builtins to choose their
>> no-read / reduction variant.
>>
>> Although this leads to no new builtins added, the name fetch_* would become a
>> misnomer for these and lead to a confusing user interface.
>>
>> Would appreciate some feedback on what would be the best step forward here for
>> GCC. Will accordingly get feedback from the LLVM community on this as well.
>>
>> Best,
>> Soumya
>>
>