Dead branch instructions in Aarch64 atomic compare exchange

[ilovepi]

Some of our kernel developers pointed out an odd instruction sequence emited by clang. We're not sure why this strange branch sequence appears, since its basically a NOP.

Godbolt: https://godbolt.org/z/T77qWvxW5

#include <atomic>
#include <stdlib.h>

bool cmpxchg(std::atomic<uint32_t>& a, uint32_t& expected, uint32_t desired) {
    return a.compare_exchange_strong(expected, desired, std::memory_order_acq_rel);
}

cmpxchg(std::atomic<unsigned int>&, unsigned int&, unsigned int):
        ldr     w9, [x1]
.LBB0_1:
        ldaxr   w8, [x0]
        cmp     w8, w9
        b.ne    .LBB0_4
        stlxr   w10, w2, [x0]
        cbnz    w10, .LBB0_1
        mov     w0, #1            // <-- move 1 into W)
        tbz     w0, #0, .LBB0_5   // <-- branch if the 0th bit is zero (always false)
        b       .LBB0_6           // Always taken
.LBB0_4:
        mov     w0, wzr
        clrex
        tbnz    wzr, #0, .LBB0_6
.LBB0_5:
        str     w8, [x1]
.LBB0_6:
        ret

Does anyone know why this is emitted this way? We could find no reason that we'd want such a lowering.

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Paul Kirth (ilovepi)

Some of our kernel developers pointed out an odd instruction sequence emited by clang. We're not sure why this strange branch sequence appears, since its basically a NOP.

Godbolt: https://godbolt.org/z/T77qWvxW5

#include <atomic>
#include <stdlib.h>

bool cmpxchg(std::atomic<uint32_t>& a, uint32_t& expected, uint32_t desired) {
    return a.compare_exchange_strong(expected, desired, std::memory_order_acq_rel);
}

cmpxchg(std::atomic<unsigned int>&, unsigned int&, unsigned int):
        ldr     w9, [x1]
.LBB0_1:
        ldaxr   w8, [x0]
        cmp     w8, w9
        b.ne    .LBB0_4
        stlxr   w10, w2, [x0]
        cbnz    w10, .LBB0_1
        mov     w0, #<!-- -->1                 // &lt;-- move 1 into W)
        tbz     w0, #<!-- -->0, .LBB0_5   // &lt;-- branch if the 0th bit is zero (always false)
        b       .LBB0_6                  // Always taken
.LBB0_4:
        mov     w0, wzr
        clrex
        tbnz    wzr, #<!-- -->0, .LBB0_6
.LBB0_5:
        str     w8, [x1]
.LBB0_6:
        ret

Does anyone know why this is emitted this way? We could find no reason that we'd want such a lowering.

[frobtech]

Note the tbnz insn later is another case of a constant test, this one purely constant within the instruction, testing bits of the all-zeros register.

[efriedma-quic]

Before AtomicExpand, the IR looks something like this:

define dso_local noundef i1 @_Z7cmpxchgRSt6atomicIjERjj(ptr noundef nonnull align 4 captures(none) dereferenceable(4) %a, ptr noundef nonnull align 4 captures(none) dereferenceable(4) %expected, i32 noundef %desired) local_unnamed_addr #0 personality ptr @__gxx_personality_v0 {
acquire_fail38.i:
  %0 = load i32, ptr %expected, align 4
  %1 = cmpxchg ptr %a, i32 %0, i32 %desired acq_rel acquire, align 4
  %2 = extractvalue { i32, i1 } %1, 1
  br i1 %2, label %_ZNSt13__atomic_baseIjE23compare_exchange_strongERjjSt12memory_orderS2_.exit, label %cmpxchg.store_expected44.i

cmpxchg.store_expected44.i:                       ; preds = %acquire_fail38.i
  %3 = extractvalue { i32, i1 } %1, 0
  store i32 %3, ptr %expected, align 4
  br label %_ZNSt13__atomic_baseIjE23compare_exchange_strongERjjSt12memory_orderS2_.exit

_ZNSt13__atomic_baseIjE23compare_exchange_strongERjjSt12memory_orderS2_.exit: ; preds = %acquire_fail38.i, %cmpxchg.store_expected44.i
  ret i1 %2
}

After atomic-expand and simplifycfg, it looks like this:

define dso_local noundef i1 @_Z7cmpxchgRSt6atomicIjERjj(ptr noundef nonnull align 4 captures(none) dereferenceable(4) %a, ptr noundef nonnull align 4 captures(none) dereferenceable(4) %expected, i32 noundef %desired) local_unnamed_addr #0 personality ptr @__gxx_personality_v0 {
acquire_fail38.i:
  %0 = load i32, ptr %expected, align 4
  br label %cmpxchg.start

cmpxchg.start:                                    ; preds = %cmpxchg.trystore, %acquire_fail38.i
  %1 = call i64 @llvm.aarch64.ldaxr.p0(ptr elementtype(i32) %a)
  %2 = trunc i64 %1 to i32
  %should_store = icmp eq i32 %2, %0
  br i1 %should_store, label %cmpxchg.fencedstore, label %cmpxchg.nostore

cmpxchg.fencedstore:                              ; preds = %cmpxchg.start
  br label %cmpxchg.trystore

cmpxchg.trystore:                                 ; preds = %cmpxchg.fencedstore
  %loaded.trystore = phi i32 [ %2, %cmpxchg.fencedstore ]
  %3 = zext i32 %desired to i64
  %4 = call i32 @llvm.aarch64.stlxr.p0(i64 %3, ptr elementtype(i32) %a)
  %success = icmp eq i32 %4, 0
  br i1 %success, label %cmpxchg.success, label %cmpxchg.start

cmpxchg.releasedload:                             ; No predecessors!
  unreachable

cmpxchg.success:                                  ; preds = %cmpxchg.trystore
  br label %cmpxchg.end

cmpxchg.nostore:                                  ; preds = %cmpxchg.start
  %loaded.nostore = phi i32 [ %2, %cmpxchg.start ]
  call void @llvm.aarch64.clrex()
  br label %cmpxchg.failure

cmpxchg.failure:                                  ; preds = %cmpxchg.nostore
  %loaded.failure = phi i32 [ %loaded.nostore, %cmpxchg.nostore ]
  br label %cmpxchg.end

cmpxchg.end:                                      ; preds = %cmpxchg.failure, %cmpxchg.success
  %loaded.exit = phi i32 [ %loaded.trystore, %cmpxchg.success ], [ %loaded.failure, %cmpxchg.failure ]
  %success2 = phi i1 [ true, %cmpxchg.success ], [ false, %cmpxchg.failure ]
  br i1 %success2, label %_ZNSt13__atomic_baseIjE23compare_exchange_strongERjjSt12memory_orderS2_.exit, label %cmpxchg.store_expected44.i

cmpxchg.store_expected44.i:                       ; preds = %cmpxchg.end
  store i32 %loaded.exit, ptr %expected, align 4
  br label %_ZNSt13__atomic_baseIjE23compare_exchange_strongERjjSt12memory_orderS2_.exit

_ZNSt13__atomic_baseIjE23compare_exchange_strongERjjSt12memory_orderS2_.exit: ; preds = %cmpxchg.end, %cmpxchg.store_expected44.i
  ret i1 %success2
}

The tbz/tbnz is that branch at the end... which doesn't get optimized because SimplifyCFG's jump threading isn't powerful enough to transform it.

The end result looks particularly silly because of taildup.