Data Race Detection

1  Architecture Overview

The RaceDetector maintains shadow metadata for every byte touched during kernel execution. The design operates at two levels:

• Intra-group — work-items within the same work-group are checked at every barrier() call and at work-group completion.
• Inter-group — when a work-group completes, its accumulated global accesses are merged into a kernel-wide map and cross-checked against other groups.

graph TD
    WI0[Work-Item 0 Access] --> WIG[wiGlobal per-WI AccessMap]
    WI1[Work-Item 1 Access] --> WIG
    WIG -->|barrier / WG complete| SYNC[syncWorkItems]
    SYNC --> WGG[wgGlobal merged AccessMap]
    SYNC -->|race found?| LOG1[logRace intra-group]
    WGG -->|workGroupComplete| MERGE[Merge into m_globalAccesses]
    MERGE -->|race found?| LOG2[insertKernelRace inter-group]
    LOG2 -->|kernelEnd| LOGALL[Log all kernel races]

2  WorkGroupState Data Structure

Each work-group gets a WorkGroupState containing three sets of per-address access maps:

struct WorkGroupState
{
  size_t numWorkItems;
  // Per work-item access maps for local memory
  std::vector<AccessMap> wiLocal;
  // Per work-item access maps for global memory
  std::vector<AccessMap> wiGlobal;
  // Merged work-group level global accesses
  AccessMap wgGlobal;
};

Each AccessMap is an unordered_map<size_t, AccessRecord> using a pool allocator for cache-friendly allocation. An AccessRecord holds at most one load and one store MemoryAccess per address — the detector keeps the "most interesting" (non-atomic) access to maximize detection coverage.

3  MemoryAccess Bit-Packing

Each MemoryAccess is packed into an 8-bit info field plus entity ID and instruction pointer:

The storeData field records the byte value written, enabling the uniform write optimization — if two work-items write the same value, it may be considered safe (controlled by OCLGRIND_UNIFORM_WRITES).

4  Happens-Before via Barriers

OpenCL's barrier(CLK_LOCAL_MEM_FENCE | CLK_GLOBAL_MEM_FENCE) establishes happens-before ordering. When the detector sees workGroupBarrier, it calls syncWorkItems for the relevant address space:

void RaceDetector::workGroupBarrier(const WorkGroup* workGroup,
                                    uint32_t flags)
{
  if (flags & CLK_LOCAL_MEM_FENCE)
  {
    syncWorkItems(workGroup->getLocalMemory(), STATE(workGroup),
                  STATE(workGroup).wiLocal);
  }
  if (flags & CLK_GLOBAL_MEM_FENCE)
  {
    syncWorkItems(m_context->getGlobalMemory(), STATE(workGroup),
                  STATE(workGroup).wiGlobal);
  }
}

syncWorkItems iterates all per-work-item access maps, cross-checks each against the accumulated work-group map for conflicts, merges them in, then clears per-work-item maps — establishing a new "epoch" where accesses before the barrier cannot race with accesses after it.

sequenceDiagram
    participant WI0 as Work-Item 0
    participant WI1 as Work-Item 1
    participant WGA as WG Accumulator
    participant DET as Race Detector
    WI0->>DET: store addr 0x100
    WI1->>DET: load addr 0x100
    Note over DET: Both recorded in wiLocal/wiGlobal
    WI0->>DET: barrier(CLK_LOCAL_MEM_FENCE)
    WI1->>DET: barrier(CLK_LOCAL_MEM_FENCE)
    DET->>DET: syncWorkItems()
    DET->>DET: check WI0.store vs WI1.load → RACE!
    DET->>WGA: merge into wgAccesses
    DET->>DET: clear per-WI maps (new epoch)
    WI0->>DET: load addr 0x100
    Note over DET: No race (post-barrier epoch)

5  Race Classification: The check() Function

Two accesses are compared by the check() method. A race is reported only when:

1. Both accesses are set (populated).
2. They originate from different work-items.
3. They are not both atomic (two atomics synchronize implicitly).
4. At least one is a store — and either they form a read-write pair, or a write-write pair with non-uniform data (unless OCLGRIND_UNIFORM_WRITES is set).

6  Inter-Group Detection

At workGroupComplete, the work-group's merged global accesses (wgGlobal) are checked against the kernel-wide m_globalAccesses map. A bank of 4096 mutexes (indexed by offset & 0xFFF) serializes concurrent work-group completions without a single global lock:

• Three cross-checks are performed per address: load-vs-store, store-vs-load, and store-vs-store.
• Races are deduplicated by instruction pair — if two entities produce the same instruction combination, only the lowest address is kept.
• All detected races are logged at kernelEnd via logRace, which reports read-write or write-write type, memory address, and both entities' global/local/group IDs.

7  Thread Safety

The WorkerState uses THREAD_LOCAL storage so each CPU thread managing work-groups has its own state map. Only the inter-group merge path requires synchronization (via the mutex bank and kernelRacesMutex).

8  The registerAccess Entry Point

Every memory hook (memoryLoad, memoryStore, memoryAtomicLoad, memoryAtomicStore) funnels into registerAccess. This function:

1. Skips private and constant address spaces — private memory is per-work-item and cannot race; constant memory is read-only.
2. Validates the address range with isAddressValid to avoid recording accesses to invalid memory.
3. Constructs a MemoryAccess and computes the work-item's linear index within the work-group.
4. Inserts the access into the correct per-work-item AccessMap (global or local, indexed by address space).
5. For stores, records the data byte for uniform-write detection.

void RaceDetector::registerAccess(
  const Memory* memory, const WorkGroup* workGroup,
  const WorkItem* workItem, size_t address,
  size_t size, bool atomic, const uint8_t* storeData)
{
  unsigned addrSpace = memory->getAddressSpace();
  if (addrSpace == AddrSpacePrivate ||
      addrSpace == AddrSpaceConstant)
    return;
  if (!memory->isAddressValid(address, size))
    return;

  MemoryAccess access(workGroup, workItem,
                      storeData != NULL, atomic);

  // Compute linear WI index within work-group
  size_t index;
  if (workItem) {
    Size3 wgsize = workGroup->getGroupSize();
    Size3 lid    = workItem->getLocalID();
    index = lid.x + (lid.y + lid.z * wgsize.y) * wgsize.x;
  } else {
    index = STATE(workGroup).wiLocal.size() - 1;
  }

  // Select map by address space
  AccessMap& accesses =
    (addrSpace == AddrSpaceGlobal)
      ? STATE(workGroup).wiGlobal[index]
      : STATE(workGroup).wiLocal[index];

  // Record each byte individually
  for (size_t i = 0; i < size; i++) {
    if (storeData) access.setStoreData(storeData[i]);
    insert(accesses[address + i], access);
  }
}

9  Race Deduplication

The insertRace method prevents duplicate reports. Two races are considered identical if they involve the same pair of MemoryAccess records (regardless of order). When a duplicate is found, the detector keeps the entry with the lowest memory address — giving the user the most actionable location.

10  Logging Output

Each race report includes:

• Race type — "Read-write" or "Write-write".
• Address space and hex address — e.g., global memory address 0x4080.
• Kernel name.
• Both entities — showing Global ID, Local ID, and Group ID for work-items, or Group index for work-group-level accesses.
• LLVM IR instruction for each entity, enabling precise source mapping.