KhronosGroup / KhronosGroup/Vulkan-MemoryModel

Issue in constraint generation enforcing reads-from

Open
#39 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
117
Forks
15
PR merge metrics
No merged PRs in 30d

Description

If I have the following simple test, which checks whether a load returns a previous store, the test fails (a satisfiable solution is found).

```
NEWWG
NEWSG
NEWTHREAD
st.sc0 c = 1
ld.sc0 c = 2
NOSOLUTION consistent[X] && #dr=0
```

Looking at the counterexample generated, the issue appears to be that Alloy happily puts a reads-from relation between the two instructions, despite 2 not being the value written previously. When putting `ld.sc0 c = 0`, the test passes, because a constraint of the form `E1 in X.RFINIT` is correctly generated. The issue exists for both atomic/non-atomic instructions.

I don't think the problem is with the model, it looks like adding a `not in` constraint to `rf` fixes the problem, which can be done in `litmus.cpp` by adding the following code to lines 534-547:

```
} else if (instState.loadStore[i].var == instState.loadStore[j].var &&
instState.isWrite(i) && instState.isRead(j) &&
instState.getWriteValue(i) != instState.getReadValue(j)) {
o << " (E" << i << "->E" << j << ") not in X.rf\n";
```

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the reproducing litmus test in the issue and inspect constraint generation in litmus.cpp around lines 534-547. Verify the generated Alloy constraints for reads-from relations, then confirm the test reports no solution for the mismatched store/load values in both atomic and non-atomic cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
testing-qa
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.