Portability of Optimizations from SC to TSO
Akshay Gopalakrishnan, Clark Verbrugge · 2025
Read Portability of Optimizations from SC to TSO by Akshay Gopalakrishnan, Clark Verbrugge (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17646.txt.
Introduction
Akshay Gopalakrishnan and Clark Verbrugge ask when a compiler optimization proven safe under the simplest memory model stays safe under a weaker hardware model, in a paper from 2025. Optimizations that look fine for one program thread can create races when threads interact. Proving each one safe model by model is slow work.
The authors state a global guarantee as limits on the code changes an optimization may make. Those limits line up with banning a specific triangle shaped race pattern tied to the weaker model. They then connect the same reasoning to a causally consistent model used in languages. The result offers a porting shortcut for optimization safety proofs.
Catalog record
| CREATOR | Akshay Gopalakrishnan, Clark Verbrugge |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17646
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Portability of Optimizations from SC to TSO Akshay Gopalakrishnan, Clark Verbrugge Abstract It is well recognized that the safety of compiler optimizations is at risk in a concurrent context. Existing approaches primarily rely on context-free thread-local guarantees, and prohibit optimizations that introduce a data-race . However, compilers utilize global context-specific information, exposing safe optimizations that may violate such guarantees as well as introduce a race. Such optimizations need to individually be proven safe for each language model. An alternate approach to this would be proving them safe for an intuitive model (like interleaving semantics), and then determine their portability across other concurrent models. In this paper, we address this problem of porting across models of concurrency. We first identify a global guarantee on optimizations portable from Sequential Consistency (SC) to Total Store Order (TSO) . Our guarantee is in the form of constraints specifying the syntactic changes an optimization must not incur. We then show these constraints correlate to prohibiting the introduction of triangular races , a subset of data-race relevant to TSO. We conclude by showing how such race-inducing optimizations relate to porting across Strong Release Acquire (SRA) , a known causally consistent memory model. 1 Introduction Compilers today are primarily responsible for the performance of any program. This is mainly due to plethora of optimizations they perform, which help reduce computation and memory costs significantly. However, performing them on concurrent programs has greatly been restricted due to safety concerns. The core reason for this is the underlying concurrent semantics (memory model), which break the guarantees of functional behavior of programs assumed by compilers [ 1 ] . Existing efforts have no doubt addressed this up to some extent [ 17 ] . Optimizations which can be performed are subject to the underlying thread-local guarantees provided by the model. For instance, any code motion involving shared memory accesses are prohibited under Sequential Consistency ( SC ). Whereas any motion involving only write-read reordering is permitted under Total Store Order ( TSO ). Optimizations are also prohibited from introducing data-races, and programs are often required to be data-race-free . However, writing race-free programs is hard, and locating data-race errors in a program is often difficult, let alone debug. To add, the race-free restriction may be too strict for compilers, and weaker guarantees are shown to suffice [ 19 , 15 ] . Moreover, thread-local restrictions can be overly conservative, and may prove detrimental when designing optimizations leveraging aspects of concurrency. As an example, consider the program P as described in Fig 1 , where y is shared memory initialized to 0 , and c is thread-local. \ldots represent any thread-local computation in each thread. First thread writes to y , whereas the second spins until it observes the updated value. \begin{array}[]{@{}c@{}}\begin{array}[]{@{}l@{~~}||@{~~}l@{}}\begin{array}[]{@{}l@{}}y=1;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}c=y;\\ while(!c)\{\\ c=y;\}\\ d=x;\\ \ldots\end{array}\end{array}\\ \\ \bf{P}\end{array}\quad\longmapsto\quad\begin{array}[]{@{}c@{}}\begin{array}[]{@{}l@{}}\quad y=1;\\ \begin{array}[]{@{}l@{~~}||@{~~}l@{}}\begin{array}[]{@{}l@{}}\ldots\end{array}&\begin{array}[]{@{}l@{}}c=y;\\ while(!c)\{\\ c=y;\}\\ d=x;\\ \ldots\end{array}\end{array}\end{array}\\ \\ \bf{P^{\prime}}\end{array}\quad\longmapsto\quad\begin{array}[]{@{}c@{}}\begin{array}[]{@{}l@{}}\quad y=1;\\ \begin{array}[]{@{}l@{~~}||@{~~}l@{}}\begin{array}[]{@{}l@{}}\ldots\end{array}&\begin{array}[]{@{}l@{}}c=1;\\ d=x;\\ \ldots\end{array}\end{array}\end{array}\\ \\ \bf{P^{\prime\prime}}\end{array} Figure 1: Optimizations leveraging thread/memory fairness and value range analysis. From the compiler’s perspective, the following observation can be made, subject to a fair scheduler • The second thread will eventually see the updated value of y (memory fairness [ 11 ] ). • The second thread will only see the updated value of y as 1 (value range analysis over y ). • Thus, while(!c) will eventually fail to hold (thread fairness). With this, the compiler can assert spinning on the loop may not be required if the updates value of y is guaranteed to be in memory before it is read. To do this, it can simply sequence (inline) the write y=1 to take place before both the threads 1 1 1 As a C code, this would translate to creating a thread which does y=1 followed by creating two threads which do the other computations. . This is shown as P^{\prime} in Fig 1 . Further, it can perform simple store-to-load forwarding, which results in the loop condition to be false from the start. This gives us the optimized program P^{\prime\prime} in Fig 1 . Such an optimization is safe under both SC and TSO semantics, the original and the optimized program both terminate with the same state of memory c=1 . However, the situation is slightly different if the optimization is done in the presence of another concurrent context. In Fig 2 left, the original program cannot terminate with a=1\wedge b=0\wedge c=1\wedge d=0 , both under TSO and SC semantics. The thread-local state c=1\wedge d=0 implies y=1 is visible to all threads before x=1 . Hence, the reads to x and y done after loop termination cannot observe the stale value of y (as b=0 shows). \begin{array}[]{@{}c@{}}\begin{array}[]{@{}l@{~~}||@{~~}l@{~~}||@{~~}l@{}}\begin{array}[]{@{}l@{}}a=x;\\ b=y;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}x=1;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}\bf{P}\end{array}\end{array}\\ \\ (i)\end{array}\quad\longmapsto\quad\begin{array}[]{@{}c@{}}\begin{array}[]{@{}l@{~~}||@{~~}l@{~~}||@{~~}l@{}}\begin{array}[]{@{}l@{}}a=x;\\ b=y;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}x=1;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}\bf{P^{\prime}}\end{array}\end{array}\\ \\ (ii)\end{array}\quad\longmapsto\quad\begin{array}[]{@{}c@{}}\begin{array}[]{@{}l@{~~}||@{~~}l@{~~}||@{~~}l@{}}\begin{array}[]{@{}l@{}}a=x;\\ b=y;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}x=1;\\ \ldots\end{array}&\begin{array}[]{@{}l@{}}\bf{P^{\prime\prime}}\end{array}\end{array}\\ \\ (iii)\end{array} Figure 2: Under different program context, optimization to P^{\prime\prime} is unsafe under TSO . The same above reasoning is true for both the optimized programs (middle and right) under SC semantics, thereby disallowing the outcome in question. However, the situation is different under TSO : the program in Fig 2 middle can exhibit the outcome [ 20 ] . Reading c=1 from y=1 does not enforce a global ordering between the writes x=1 and y=1 2 2 2 Operationally, the read value can be fetched from the FIFO write buffer where y=1 is first committed. The buffer can be flushed at any latter time, and only then would imply a global memory ordering with x=1 . . The same reasoning applies for the final optimized program (Fig 2 right). Thus, the same optimization is unsafe when considered under a different program context. Examples like above represent the kind of global optimizations that can be permitted for TSO . However, as we see, doing them depends on the right program context. Identifying a precise constraint over all possible program contexts specific to TSO may be non-trivial. We adopt an alternate approach that may be more suitable to put into practice. We instead determine constraints on optimizations which are portable from SC to TSO . Working towards identifying such a constraint has led to the following contributions 1. We find a suitable thread-global syntactic constraint on optimizations that do not eliminate/introduce writes. 2. We show that our constraint correlates to disallowing optimizations resulting in a new triangular-race , a subset of data=races . 3. We discover that porting SC optimizations that introduce such triangular races in addition translates to porting across a Causally Consistent memory model known as Strong Release Acquire (SRA) [ 10 ] . 2 Preliminaries We give a brief overview of the formal elements involved in this work. Sec 2.1 introduces the pre-trace model, and Sec 2.2 the representation of optimizations, both from our previous work [ 9 ] . Sec 2.3 introduces the axiomatic models for SC and TSO we use. The language is given in Fig 3 . A program prog is a parallel composition of individual sequential programs sp , each of which are associated with a thread id t and a sequence of actions p . An action is either a memory event st or a conditional branch code block (for simplicity, loops are not included). Memory events can be a read from ( a=x ), write