Issue 244502
Summary [GVN] Forwarding poison across a release store may violate LLVM's concurrent memory semantics
Labels new issue
Assignees
Reporter ZhangZhuoSJTU
    ## Summary

We ran into a potential LLVM optimization bug while verifying its concurrent memory semantics using our formal semantics framework.

The issue is that **GVN can replace a racy load with an earlier stored `poison` value, even though the LangRef requires the original load to return `undef`**. Since LLVM treats `poison` and `undef` differently, this transformation can change the program's behavior.

In our example, two concurrent threads can both return `1` after optimization, while the original program appears to exclude this outcome.

We also noticed that LLVM's [Atomic Instructions and Concurrency Guide](https://github.com/llvm/llvm-project/blob/aaeed7bd098307f46124dfa009103ebff32c0079/llvm/docs/Atomics.md#release) explicitly allows moving loads from after a release store to before it. Our example suggests that this rule may need some qualification, since moving a load across a release can change whether it races with another thread's write.

We reproduced the issue with LLVM 22.1.8 and a November 16, 2026 LLVM 24 development snapshot.

## Reproducer

Here is a small example with two threads. Both threads are started before either is joined, and the globals are initially zero.

```llvm
target triple = "x86_64-unknown-linux-gnu"

@x = global i8 0, align 1
@flag = global i8 0, align 1

define i32 @left() {
  store i8 poison, ptr @x, align 1
  store atomic i8 1, ptr @flag release, align 1
  %r = load i8, ptr @x, align 1
  %masked = or i8 %r, -1
  %t = freeze i8 %masked
  %go = icmp eq i8 %t, 0
  %result = zext i1 %go to i32
  ret i32 %result
}

define i32 @right() {
  %f = load atomic i8, ptr @flag acquire, align 1
  %ready = icmp eq i8 %f, 1
  br i1 %ready, label %yes, label %no

yes:
  store i8 1, ptr @x, align 1
  ret i32 1

no:
  ret i32 0
}
```

Save this as `minimal_race.ll` and run:

```bash
opt -S -passes='function(gvn),default<O2>,verify' minimal_race.ll -o -
```

After optimization, `left()` becomes:

```llvm
define noundef i32 @left() local_unnamed_addr #0 {
  store atomic i8 1, ptr @flag release, align 1
  ret i32 1
}
```

The `right()` function still returns `1` when it observes `flag == 1`. Therefore, the optimized program can return `(left, right) = (1, 1)`.

We believe this is not permitted by the original program under the current LangRef.

## Why we think this is wrong

Consider an execution where `right()` returns `1`. This means its acquire load observed the release store from `left()`.

The relevant operations are:

```text
Left                           Right

P: store poison to x
       |
F: release-store flag = 1
       |                       A: acquire-load flag == 1
       |                                    |
R: load x.                     X: store x = 1
```

Since the acquire reads from the release (*i.e.*, the `right()` returns `1`), we have the happens-before chain:

`P → F → A → X`

However, the load `R` occurs after the release store `F`, and there is no happens-before ordering between `R` and `X`. Therefore, `R` races with `X`.

Under the [LangRef's memory model for concurrent operations](https://github.com/llvm/llvm-project/blob/aaeed7bd098307f46124dfa009103ebff32c0079/llvm/docs/LangRef.md#memory-model-for-concurrent-operations):

> Given these definitions, R_byte is defined as follows:
> ...
> - Otherwise, consider the set consisting of R and all the writes that R_byte may see. If any two accesses in that set form a data race, R_byte returns `undef`. 

In this case, `R` may see either `P` or `X`. The initial write is hidden by `P`, while `X` does not hide `P` because it is not ordered before `R`. Since the possible accesses include a data race, the load must return `undef`.

This matters because the program can distinguish `undef` from `poison`:

```llvm
%masked = or i8 %r, -1
%t = freeze i8 %masked
%go = icmp eq i8 %t, 0
```

If `%r` is `undef`, the OR always produces `255`, and `freeze` preserves that value. The comparison is false, so `left()` returns `0`.

If `%r` is `poison`, the OR also produces poison, and `freeze` can choose `0`. In that case, `left()` returns `1`.

Therefore, **whenever `right()` returns `1`, the original `left()` must return `0`**. The optimized program breaks this relationship by allowing both to return `1`.

We don't see an immediate-UB issue that would invalidate this argument. The pointers are valid, storing poison as data is allowed, and the result is frozen before being compared. 

## Connection to LLVM's optimizer guidance

What initially caught our attention was the *Notes for optimizers* under *Release* in the [Atomic Instructions and Concurrency Guide](https://github.com/llvm/llvm-project/blob/aaeed7bd098307f46124dfa009103ebff32c0079/llvm/docs/Atomics.md#release).

The guide says:

> It is also possible to move loads from after a Release store or read-modify-write operation to before it.

However, consider what happens if we move the load in our example.

The original order is:

```llvm
store i8 poison, ptr @x, align 1
store atomic i8 1, ptr @flag release, align 1
%r = load i8, ptr @x, align 1
```

Moving the load before the release gives:

```llvm
store i8 poison, ptr @x, align 1
%r = load i8, ptr @x, align 1
store atomic i8 1, ptr @flag release, align 1
```

In the original program, the load races with `right()`'s write when `right()` observes the release. The LangRef therefore requires `undef`.

After moving the load, it happens-before `right()`'s write, so it no longer races with that write and can instead read the earlier poison.

As shown above, this difference is observable. In particular, the moved load can allow `(1,1)`, which the original program excludes.

**GVN does not literally perform this load movement in our testcase.** Instead, it forwards the earlier stored poison directly and removes the load. But the resulting problem seems closely related: the load's original position matters for determining whether it races, and forwarding the earlier value loses that distinction.

This makes us wonder whether the load-motion rule in the guide is too permissive, or whether we are missing something in the intended memory semantics.

## What we observed

GVN alone is sufficient to introduce the questionable forwarding. Running:

```bash
opt -S -passes='function(gvn),verify' minimal_race.ll -o -
```

produces:

```llvm
define i32 @left() {
  store i8 poison, ptr @x, align 1
  store atomic i8 1, ptr @flag release, align 1
  %t = freeze i8 poison
  %go = icmp eq i8 %t, 0
  %result = zext i1 %go to i32
  ret i32 %result
}
```

After running `instcombine` or O2, this becomes an unconditional return of `1`.

Interestingly, default O2 alone returns `0`, so this depends on the pass sequence.

We also compiled the workers with `llc -O0` and ran them concurrently using the following pthread launcher. 

```c

/* The racy program is LLVM IR. This C file only launches and joins it. */
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

extern int left(void), right(void);
extern unsigned char x, flag;

static int left_result, right_result;

static void *run_left(void *arg) {
  (void)arg;
  left_result = left();
  return NULL;
}

static void *run_right(void *arg) {
  (void)arg;
  right_result = right();
  return NULL;
}

int main(int argc, char **argv) {
  unsigned runs = argc == 2 ? (unsigned)strtoul(argv[1], NULL, 10) : 1000;
  unsigned counts[2][2] = {0};

  for (unsigned i = 0; i < runs; ++i) {
    pthread_t a, b;

    /* Reset state before starting either thread. */
    x = flag = 0;
    left_result = right_result = 0;

    if (pthread_create(&a, NULL, run_left, NULL)) return 2;
    if (pthread_create(&b, NULL, run_right, NULL)) {
      pthread_join(a, NULL);
      return 2;
    }

    /* Both threads are started before either is joined. */
    if (pthread_join(a, NULL)) return 3;
    if (pthread_join(b, NULL)) return 3;

    if ((unsigned)left_result > 1 || (unsigned)right_result > 1)
      return 4;

    ++counts[left_result][right_result];
  }

  printf("runs=%u 00=%u 01=%u 10=%u 11=%u\n",
         runs, counts[0][0], counts[0][1],
         counts[1][0], counts[1][1]);

  return 0;
}

```

Here are the results from 1,000 runs per configuration:

| Input | LLVM 22 `(1,1)` | LLVM 24 `(1,1)` |
|---|---:|---:|
| Original IR | 0 / 1,000 | 0 / 1,000 |
| Default O2 | 0 / 1,000 | 0 / 1,000 |
| GVN followed by O2 | 997 / 1,000 | 994 / 1,000 |

These experiments confirm that the optimized program can actually produce `(1,1)`. The argument that the original program excludes this outcome comes from the LangRef semantics, not just the runtime results.

The tested versions were:

- LLVM 22.1.8, commit `ca7933e47d3a3451d81e72ac174dcb5aa28b59d1`.
- LLVM 24.0.0 development snapshot from November 16, 2026, commit `aaeed7bd098307f46124dfa009103ebff32c0079`.

>From a quick look at the source, the relevant code seems to be [GVN's forwarding of stored values](https://github.com/llvm/llvm-project/blob/aaeed7bd098307f46124dfa009103ebff32c0079/llvm/lib/Transforms/Scalar/GVN.cpp#L1737-L1750) and [MemoryDependenceAnalysis looking past the release store](https://github.com/llvm/llvm-project/blob/aaeed7bd098307f46124dfa009103ebff32c0079/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp#L505-L534).

_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to