We present a framework for the efficient application of stateless model checking (SMC) to concurrent programs running under the Release-Acquire (RA) fragment of the C/C++11 memory model. Our approach is based on exploring the possible program orders, which define the order in which instructions of a thread are executed, and read-from relations, which specify how reads obtain their values from writes. This is in contrast to previous approaches, which also explore the possible coherence orders, i.e., orderings between conflicting writes. Since unexpected test results such as program crashes or assertion violations depend only on the read-from relation, we avoid a potentially significant source of redundancy. Our framework is based on a novel technique for determining whether a particular read-from relation is feasible under the RA semantics. We define an SMC algorithm which is provably optimal in the sense that it explores each program order and read-from relation exactly once. This optimality result is strictly stronger than previous analogous optimality results, which also take coherence order into account. We have implemented our framework in the tool Tracer. Experiments show that Tracer can be significantly faster than state-of-the-art tools that can handle the RA semantics. Optimal Stateless Model Checking under the Release-Acquire Semantics 135:3 Figure 1b 1 . A DPOR algorithm based on Shasha-Snir traces (e.g., [Abdulla et al. , 2016b) must thus explore at least four executions. However, it is possible to reduce this number further. Namely, a closer inspection reveals that the two traces τ 1 and τ 2 are equivalent, in the sense that each thread goes through the same sequences of local states and computes the same results. This is because τ 1 and τ 2 have the same program order (po) and read-from (rf) relation. Their only difference is how writes are ordered by co, but this is not relevant for the computed results. The preceding example illustrates that there is a potential for improving the efficiency of DPOR algorithms by using a weaker equivalence induced only by po and rf. In this example, the improvement is modest (reducing the number of explored traces from four to three), but it can be significant, sometimes even exponential, for more extensive programs. Several recent DPOR techniques try to exploit the potential offered by such a weaker equivalence Huang 2015; Huang and Huang 2016; Norris and Demsky 2016] . However, except for the minimal case of an acyclic communication graph , they are far from optimally doing this, since they may still explore a significant number of different executions with the same rf relation. Therefore, the challenge remains to define a more efficient DPOR algorithm, that is optimal in the sense that it explores precisely one execution in each equivalence class induced by po and rf. In this paper, we present a fundamentally new approach to defining DPOR algorithms, which optimally explores only the equivalence classes defined by the program order and read-from relations. Our method is developed for the Release-Acquire (RA) fragment [Lahav et al. 2016 ] of the C/C++11 memory model. RA is a useful and well-behaved fragment of the C/C++11 memory model, which strikes a good balance between performance and programmability. In the RA semantics, all writes are release accesses, while all reads are acquire accesses. RA allows high-performance implementations, while still providing sufficiently strong guarantees for fundamental concurrent algorithms (such as the read-copy-update mechanism [Lahav et al. 2016] ). Our DPOR algorithm is based on the above weakening of Shasha-Snir traces, called weak traces, which are defined by only the program order and read-from relations of an execution. For example, the program in Figure 1a has three weak traces, shown as τ 3 , τ 4 , and τ 5 . Our DPOR algorithm is provably optimal for weak traces, in the sense that it explores precisely one execution for each weak trace that is RA-consistent, i.e., that can be extended with some coherence relation that satisfies the constraints of the RA semantics. A significant challenge for our DPOR algorithm is to efficiently determine those continuations of a currently explored trace that lead to some RA-consistent trace. E.g., for the program in Figure 1a , letting both threads read from the write of the other thread leads to RA-inconsistency. We solve this problem by defining a saturation operation, which extends a weak trace with a partial coherence relation, which contains precisely those coherence edges that must be present in any corresponding Shasha-Snir trace. During exploration, the DPOR algorithm maintains a saturated version of the currently explored weak trace, and can therefore examine precisely those weak traces that are RA-consistent, without performing useless explorations. When a read event is added, the algorithm determines the set of write events from which it can obtain its value while preserving RA-consistency, and branches into a separate continuation for each such write event. When a write event is added, the algorithm merely adds it to the trace. It can be proven that this preserves RA-consistency, and also keeps the trace saturated (a slight modification is needed for atomic read-modify-write events). The algorithm must also detect if some previous read may read from a newly added write, and then backtrack to allow the write to be performed before that read. We prove that our DPOR algorithm does not perform any useless work, in the sense that (i) any exploration eventually leads to a terminated RA-consistent execution, i.e., the algorithm never 1 A Shasha-Snir trace also includes events that write initial values, but these can be ignored for this example.
For the Release-Acquire semantics (RA), REF have developed a DPOR algorithm which is optimal with respect to the rf equivalence.
Optimal stateless model checking under the release-acquire semantics
PACMPL
Computer Science