llvm / llvm/llvm-project

[clang][openmp] Incorrect metadata on OpenMP loop with indirect store causes miscompilation via gather/scatter vectorization

Open
#200,032 3 comments 0 reactions 0 assignees View on GitHub
clang:openmp confirmed miscompilation vectorizers
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

https://godbolt.org/z/rrPjaWEPd

---

The repro comes from parallel histogram computation. It seems that the OpenMP lowering marks the inner per-chunk loop as having no dependencies between iterations and as a result, the loop gets vectorized using `gather -> add -> scatter`. This is not valid since multiple loaded values may belong to the same bucket and the scatter store will lose the overlapping increments:

```sh
clang++ -std=c++20 -O2 -march=x86-64-v4 -fopenmp ./repro.cpp -o repro
```

```cpp
#include
#include
#include

int main() {
#pragma omp parallel num_threads(1)
{
// vector of whatever as input (here, zeros)
auto data = std::vector(128, 0);
// "histogram", with a single bucket for zeros
auto histogram = std::vector(1, 0);

#pragma omp for schedule(guided)
for (auto val : data) {
histogram[val]++;
}
// this should print 128, but I get 8
std::cerr << histogram[0] << "\n";
}
}
```

The printed value `8` is an artifact of chunk partitioning together with vector tail handling; in the main SIMD loop all but the last increment in each SIMD vector is lost (e.g., for a vector of 16 zeros, the bucket is only incremented once).

---

Copilot analysis (in case it's helpful)

## Incorrect `!llvm.loop.parallel_accesses` metadata on `schedule(guided)` loop causes miscompilation via gather/scatter vectorization

Clang's OpenMP lowering emits `!llvm.access.group` / `!llvm.loop.parallel_accesses` metadata on `omp for schedule(guided)` loops, even when the loop body contains indirect stores (`histogram[val]++`) that have write-after-write dependencies across iterations. The vectorizer trusts this metadata, transforms the histogram update into AVX-512 gather→add→scatter, and silently drops updates when multiple vector lanes scatter to the same address.

## Conditions

All of the following are required:

- `-O2` or higher
- target that supports scatter/gather SIMD (e.g., AVX-512)
- `schedule(guided)` or `schedule(dynamic)` — `static` produces correct results
- `-fno-vectorize` suppresses the bug

## Root cause

In the emitted LLVM IR for `main.omp_outlined`, the histogram loop body has:

```llvm
%val = load i16, ptr %data.ptr, align 2, !llvm.access.group !46
%old = load i64, ptr %hist.ptr, align 8, !llvm.access.group !46
store i64 %new, ptr %hist.ptr, align 8, !llvm.access.group !46
br i1 %done, label %exit, label %loop, !llvm.loop !47

!46 = distinct !{}
!47 = distinct !{!47, !48}
!48 = !{!"llvm.loop.parallel_accesses", !46}
```

This metadata asserts that all tagged accesses are independent across iterations. For `histogram[val]++`, this is false — multiple iterations may write to the same bucket. The vectorizer legally transforms this into `vpgatherdq` → `vpsubq` → `vpscatterdq`, and when all 4 lanes in a YMM scatter target the same address, only the last write survives (16 iterations → 1 effective increment).

## Analysis

The bug is in Clang's OpenMP CodeGen — `schedule(guided)` outlines the loop body into a function dispatched by `__kmpc_dispatch_next_8`, and the `parallel_accesses` metadata is emitted unconditionally without checking whether the loop body has potential intra-vector write conflicts via data-dependent indices.

`schedule(static)` likely avoids this because it produces a different loop form where the vectorizer's own dependence analysis can detect the conflict independently of the metadata.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.