${\rm\small LLOV}$: A Fast Static Data-Race Checker for OpenMP Programs : A Fast Static Data-Race Checker for OpenMP Programs

Listing 1 shows an OpenMP worksharing construct omp parallel for with a data race. The program computes the sum of squares of all the elements in the matrix u. Here, variables temp, i, and j are marked as private, indicating that each thread will have its own copy of these variables. However, the variable sum (Line 5) of Listing 1 is not listed by any of the data sharing clauses. Therefore, the variable sum will be shared among all the threads in the team. Thus, each thread will work on the same shared variable and update it simultaneously without any synchronization, leading to a data race.

Listing 2 presents a program in FORTRAN with a data race due to a missing private clause corresponding to the variable tmp (Line 3). Due to such intricacies, a programmer is prone to make mistakes and inadvertently introduce data races in the program.

Our aim is to develop techniques and a tool that understand the semantics of OpenMP pragmas and clauses with all their subtleties.

OpenMP programs may suffer from data races due to incorrect parallelization strategies. Such data races may occur because of parallelization of loops with loop carried dependencies.

For example, the loop nest in Listing 3 is parallel in the outer dimension (Line 1), but it is the inner loop (Line 3) that is marked parallel, which has a loop carried dependence, because the read of b[i][j-1] (Line 4) is dependent on write to b[i][j] (Line 4) in the previous iteration. A correct parallelization strategy for this example would be to mark the outer loop as parallel in place of the inner loop.

As another example, Listing 4 is a parallel implementation of Floyd-Warshall's shortest path algorithm with a benign ¹ race condition [8]. This is because all the iterations of the (parallel) inner j loop read A[i][k] including the one where j=k, which also writes into A[i][k]. Hence, the iterations before j=k need the previous value of A[i][k] and subsequent ones need the new, updated value. However, if all the matrix entries are non-negative, then A[i][k] is unchanged by the assignment, and therefore the race introduced by parallelizing the j loop is benign .

OpenMP supports SIMD constructs for both CPUs and GPUs. In CPUs, SIMD is supported with vector processing units, where the consecutive iterations of a loop can be executed in a SIMD processing unit within a single core by a single thread. This is contrary to other loop constructs where iterations are shared among different threads.

In the example in Listing 5, the loop is marked as SIMD parallel loop by the pragma omp simd (Line 1). This signifies that consecutive iterations assigned to a single thread can be executed concurrently in SIMD units, called vector arithmetic logic units (ALU), within a single core rather than executing sequentially in a scalar ALU. However, because of the forward loop carried dependence between write to a[i+1] (Line 3) in one iteration and read of a[i] (Line 3) in the previous iteration, concurrent execution of the consecutive iterations in a vector ALU will produce inconsistent results. Dynamic data race detection tools fail to detect data races in such cases as the execution happens within a single thread.

Improper synchronization between threads is a common cause of data races in concurrent programs. OpenMP can have both explicit and implicit synchronizations associated with different constructs.

The constructs parallel, for, workshare, sections, and single have an implicit barrier at the end of the construct. This ensures that all threads in the team wait for others to proceed further. This enforcement can be overcome with the nowait clause where threads in a team, after completion of the construct, are no longer bound to wait for the other unfinished threads. However, improper use of the nowait clause can result in data races as shown in Listing 6. In this example, a thread executing the parallel for (Line 3) will not wait for the other threads in the team because of the nowait clause (Line 2). Threads that have finished executing the for loop are free to continue and execute the single construct (Line 5). Since there is a data dependence between write to a[i] (Line 4) and read of a[9] (Line 6), it might result in a data race.

Such cases are extremely difficult to reproduce as they are dependent on the order of execution of the threads. This particular order of execution may not manifest during runtime, therefore, making it hard for dynamic analysis tools to detect such cases. Static analysis techniques have an advantage over the dynamic techniques in detecting race conditions for such cases.

Control flow dependent on number of threads available at runtime might introduce data races in a parallel program. In the example in Listing 7, data races will arise only when thread IDs of two or more threads in the team are multiples of 2.

LLOV has two phases: analysis and verification.

4.1.1 Analysis Phase. In the first phase, we analyze the LLVM-IR to collect various OpenMP pragmas and additional information required for race detection. This analysis is necessary, because OpenMP constructs are lowered to the IR by compiler frontends such as Clang [60] and Flang [61]. LLVM-IR [56] is sequential and does not have support for parallel constructs. Hence, parallel constructs in high-level languages are represented in the IR as function calls. OpenMP pragmas are translated as function calls to the APIs of the OpenMP runtime library libomp.

As part of this analysis, for each OpenMP construct, we collect information such as memory locations, access types, storage modifiers, synchronization details, scheduling type, and so on. An in-memory representation of the OpenMP directive contains a directive type, a schedule (if present), variable names and types, and a list of child directives for nested OpenMP constructs. An illustration of our representation is shown in Listing 8 for the example in Listing 6 (Section 3). The grammar for this representation is presented in BNF form in Listing 9.

Reconstructing the OpenMP information from the IR has many challenges. Not all pragmas are handled directly by the runtime. Directives for SIMD constructs are just a hint to the optimizer that the program segment could be executed in parallel by SIMD units. Some constructs such as worksharing for and sections are very similar once they are translated to LLVM-IR. It becomes a challenge to distinguish between the two. Recovering worksharing for becomes challenging when the collapse clause is used. The resulting IR has no information about the loop nest in the original program. The data sharing clauses such as private, shared, firstprivate, and lastprivate are not explicitly annotated in the IR. They require additional analysis and we reconstruct them using their properties. Only reduction and threadprivate variables can be extracted easily. We overcome the challenge to extract OpenMP pragmas from IR by conservatively recognizing patterns in IR that are generated from high level source code that use these pragmas.

4.1.2 Verification Phase. LLOV checks for data races only in regions of a program marked parallel by one of the structured parallelism constructs of OpenMP listed in Table 1. A crucial property of OpenMP constructs is that its specification [70] allows only structured blocks within a pragma. A structured block must not contain arbitrary jumps into or out of it. In other words, a structured block closely resembles a Single Entry Single Exit (SESE) region [2] used in loop analyses. To our advantage, the polyhedral framework Polly [36] also builds SESE regions before applying its powerful and exact dependence analysis and complex transformations.

Table 1. Comparison of OpenMP Pragma Handling by OpenMP-aware Tools

Y for Yes, N for No.

The polyhedral framework is based on exact dependence (affine) analysis [33], by which the dependence information can be expressed as (piecewise, pseudo-) affine functions. Polly [36, 62] is the polyhedral compilation engine in LLVM framework. Polly relies on the Integer Set Library (ISL) [89] to perform exact dependence analysis, using which Polly performs transformations such as loop tiling, loop fusion, and outer loop vectorization. Dependencies are modelled as ISL relations and transformations are performed on integer sets using ISL operations. The input to Polly is serial code that is marked as Static Control Part (SCoP) and the output is tiled or parallel code enabling vectorization.

LLOV is built using the Polly infrastructure but does not use its transformation capabilities. Our primary goal is to perform analyses, whereas Polly is designed for complex parallelizing or locality transformations followed by polyhedral code generation. The input to LLOV is explicitly parallel code that uses the structured parallelism of OpenMP. With an assumption that the input code has a serial schedule,² LLOV calculates its dependence information by using the dependence analyzer of Polly. Using this dependence information, LLOV then analyzes the parallel constructs and checks the presence or absence of data races. Consequently, LLOV can deterministically state whether a program has data races or whether it is race free for an affine subset of programs.

Polly was designed [36, 37] as an automatic parallelization pass using polyhedral dependence analysis. Its analysis and transformation phases were closely coupled and the analyses were not directly usable from outside Polly, neither by other analyses nor by optimization passes in LLVM. In particular, SCoP detection and dependence analysis of Polly was not directly accessible from analyses in LLVM.

We modified and extended the analysis phase of Polly in such a way that its internal data structures become accessible from LLVM.³ Other changes involved modifying the dependence analysis of Polly so that its Reduced Dependence Graph (RDG) could be computed on-the-fly for a function, thereby reducing the analysis time for LLOV. Polly can detect and model only sequential programs. Hence, it does not support OpenMP programs. We incorporated changes to the SCoP detection to model OpenMP programs assuming a sequential schedule. The OpenMP parallel LLVM-IR contains runtime library calls to change the loop bounds at runtime, which makes the program non-affine. We mitigate this problem by resetting the loop bounds to the original values.

The two phases of LLOV are not tightly coupled, meaning the verification phase is separate from the analysis phase. The advantage of having a two phase design is that the verifier could easily be plugged with another analysis phase for other parallel programming APIs such as Intel TBB [41, 73], OpenCL [38] once they have a translator to LLVM-IR.

First, we cover the race detection for affine regions that relies on Polly, followed by the race detection for non-affine regions that relies on the Alias Analysis of LLVM.

4.2.1 Race Detection in Affine Regions. In the analysis phase, we gather information provided by OpenMP's structured parallelism constructs. We model a section of code, marked as parallel by one of the OpenMP constructs listed in Table 1, as static affine control parts (SCoPs) in the polyhedral framework. Our race detection algorithm runs only on sections of a program marked as parallel by one of these pragmas. This reduces analysis time of LLOV as it can avoid performing dependence analysis on the sequential fragments of the program.

For each SCoP, we query the race detection Algorithm 1 to check for the presence of dependences. A data race is flagged when the set of the memory accesses in the reduced dependence graph (RDG) and the set of the shared memory accesses within the SCoP is not disjoint. When dependencies are absent, the SCoP is parallel and the corresponding program segment is guaranteed to be data race free. Hence, we can verify—fully statically—the absence of data race in a program.

The polyhedral representation of the affine static control program in Listing 10 consists of an iteration domain (I), an execution order called schedule (S), and an access function (A) mapping iteration number to memory accesses. The RDG (D) is computed using this information. The RDG is shown graphically in Figure 2(a).

Iteration Domain : ${\bf I} = \lbrace \texttt {S0}(i, j) : 0 \le i \le m-1 \wedge 1 \le j \le n-1 \rbrace $

Schedule : $ {\bf S} =\lbrace \texttt {S0}(i, j) \rightarrow (i, j) \rbrace \cap _{dom} {\bf I}$

Access Map : $ {\bf A}=\lbrace \texttt {S0}(i, j) \rightarrow \texttt {M}(i, j) ; \texttt {S0}(i, j) \rightarrow \texttt {M}(i, j-1)\rbrace $

Dependencies : $ {\bf D} =\lbrace \texttt {S0}(i,j) \rightarrow (i,j-1) : 0 \le i \le m-1 \wedge 1 \le j \le n-1 \rbrace $

Figure 2(b) shows the projection of the RDG on i-dimension, which results in vectors with zero magnitude as represented by red dots. This signifies that the loop is parallel in the i-dimension. Figure 2(c) shows the projection of the RDG on j-dimension, which are vectors of unit magnitude. Non-zero magnitude means that this dimension is not parallel.

Time complexity of the race detection algorithm is exponential in the number of inequalities present, since our approach is based on Fourier–Motzkin elimination.

Our static race detection tool LLOV has several advantages over state-of-the-art dynamic race detection tools.

LLOV is in active development and in the current version, we attempted to cover the frequently used OpenMP v4.5 pragmas. In the current version, LLOV does not provide support for the OpenMP constructs for synchronization, device offloading, and tasking. Function calls within an OpenMP construct are handled by LLOV only if the function is inlined. Also, since our tool is primarily based on the polyhedral framework, its application is limited by the affine restrictions. However, LLOV provides a limited support for non-affine programs using Mod/Ref analysis as discussed in Section 4.2.2. Programs with dynamic control flow and irregular accesses (like $a[b[i]]$) fall outside the purview of the polyhedral framework. We are working on extending the analysis of our tool on such non-affine programs, but that is beyond the current scope.

LLOV may produce False Negatives when there is a race due to a dependence across two static control parts (SCoPs) of a program. One such category of programs is the presence of nowait clause in a worksharing for construct.

LLOV can produce False Positives for programs with explicit synchronizations with barriers and locks. Programs generated by automatic parallelization tools such as PolyOpt [76] and PLuTo [15] will have complex loop bounds and are difficut to model precisely. LLOV might produce FP for some of these automatically generated tiled or parallel kernels.

Handling sections construct in LLVM-IR is a challenge, as the resulting IR is similar to worksharing for construct but with a control dependence on the number of threads. Hence LLOV might produce FP/FN cases instead of showing a diagnostic message stating that the construct is outside its purview.

There are multiple static data race detectors in the literature. Common techniques used for static analyses are lockset-based approach or modeling data races as a linear programming problem (integer-linear or parametric integer-linear) and appropriately using an ILP or SMT solver to check for its satisfiability. Here, we briefly cover the state-of-the-art static data race detection tools for OpenMP programs. We limit the discussion to OpenMP race detection tools only.

ompVerify [8] is a polyhedral model-based static data race detection tool that detects incorrectly specified omp parallel for constructs. ompVerify computes the Polyhedral Reduced Dependency Graph (PRDG) to reason about possible violations of true dependencies, write-write conflicts, and stale read problems in the OpenMP parallel for construct. Although our approach is inspired by ompVerify, we have implemented a different algorithm to detect parallelism of loop nests. And, while ompVerify can handle only the omp parallel for construct, the coverage of LLOV is much wider; it can handle many more pragmas as listed in Table 3. Moreover, the prototype implementation of ompVerify is in Eclipse CDT/CODAN framework using the AlphaZ [93] polyhedral framework, whereas LLOV is based on the widely used LLVM compiler infrastructure. Finally, ompVerify works at the AST level, whereas LLOV works on the language independent LLVM-IR level making it applicable to multiple languages. LLOV also has a limited support for non-affine regions that ompVerify does not have.

DRACO [91] is a static data race detection tool based on the Polyhedral model and is built on the ROSE compiler framework [79, 81]. One significant advantage of LLOV over DRACO is that LLOV is based on LLVM-IR and is language agnostic, while DRACO is limited only to the C family of languages that can be compiled by the ROSE compiler.

PolyOMP [20, 21] is a static data race detection tool based on the polyhedral model. PolyOMP [21] uses an extended polyhedral model to encode OpenMP loop nest information as constraints and uses the Z3 [25] solver to detect data races. The extended version of PolyOMP [20] uses May-Happen-in-Parallel analysis in place of Z3 to detect data races. In contrast, LLOV uses RDG (Reduced Dependence Graph) to determine parallelism in a region and infer data races based on the presence of data dependencies.

Other static analysis tools like Relay [90], Locksmith [78], and RacerX [31] use Eraser’s [80] lockset algorithm and can detect races in pthread-based C/C++ programs. RacerD [13] is a static analysis tool for Java programs.

Various dynamic race detection techniques have been proposed in the literature. The well known among them are based on Locksets [80], Happens-before [44] relations, and Offset-Span labels [63].

Archer [4] uses both static and dynamic analyses for race detection. It uses happens-before relations [44, 82], which enforces multiple runs of the program to find races. Archer reduces the analysis space of pthread-based tool TSan-LLVM by instrumenting only parallel sections of an OpenMP program. As Archer uses shadow memory to keep track of each memory access, memory requirement still remains the problem for memory bound programs.

In the analysis phase, Archer uses Polly to get the dependent loads and stores for a function and blacklist a section of code in the absence of dependencies. However, presence of dependence in a loop nest need not result in a data race.

The example in Listing 11 consists of a loop nest where the outer loop is parallel but the inner loop has a loop carried dependence. However, this is a valid parallelization strategy, since only the outer loop is marked parallel. With only loads and stores information, Archer will not be able to statically blacklist such code. It will have to rely on its dynamic analysis using TSan-LLVM. Moreover, the version of Archer (git master branch commit hash fc17353) used in our experiments completely disabled static analysis and does not use Polly at all. Archer only uses OMPT [30] callbacks to instrument the code with happens-before annotations for TSan-LLVM.

Since LLOV checks for parallelism at each level of the loop nest as stated in Section 4.2, hence it can statically detect the loop nest as data race free.

SWORD [5] is a dynamic tool based on operational semantic rules and uses OpenMP tools framework OMPT [30]. SWORD uses locksets to implement the semantic rules by taking advantage of the events tracked by OMPT. SWORD logs runtime traces for each thread consisting of all the OpenMP events and memory accesses using OMPT APIs. In the second offline phase, it analyzes the traces for concurrent threads using Offset-Span labels and detects unsynchronized memory accesses in two concurrent threads. If no synchronization is used on a common memory access, then a data race is flagged. SWORD cannot detect races in OpenMP SIMD, tasks and target offloading constructs.

ROMP [39] is a dynamic data race detection tool for OpenMP programs. ROMP maintains access history for each memory access. An access history consists of the access event, access type, and any set of locks associated with the access. ROMP constructs a task graph for the implicit and explicit OpenMP tasks and analyzes concurrent events. If an access event is concurrent and the memory is not protected by mutual exclusion mechanisms, then ROMP flags data race warnings. ROMP builds upon the offset-span-labels of OpenMP threads and constructs task graphs to detect races.

Helgrind [88] is a dynamic data race detection tool built in Valgrind framework [66] for C/C++ multithreaded programs. Helgrind maintains happens-before relations for each pair of memory accesses and forms a directed acyclic graph (DAG). If there is no path from one location to another in the happens-before graph, then data race is flagged.

Valgrind DRD [87] is another dynamic race detection tool in Valgrind. It can detect races in multithreaded C/C++ programs. It is based on happens-before relations similar to Helgrind.

ThreadSanitizer [82] is a dynamic data race detection tool based on Valgrind for multi-threaded C, C++ programs. It employs a hybrid approach of happens-before annotations and maintains locksets for read and write operations on shared memory. It maintains a state machine as metadata called shadow memory. It reports a data race when two threads access the same memory location and their corresponding locksets are disjoint. Because of the shadow memory requirement for each memory access, ThreadSanitizer’s memory requirement grows linearly with the amount of memory shared among threads. Binary instrumentation also increases the runtimes by around 5$\times$-30$\times$ [83].

TSan-LLVM [83] is based on ThreadSanitizer [82]. TSan-LLVM uses LLVM to instrument the binaries in place of Valgrind. TSan-LLVM instrumented binaries incur less runtime overhead compared to ThreadSanitizer. However, it still has similar memory requirements and remains a bottleneck for larger programs.

Intel Inspector [40] is a commercial, dynamic data race detection tool for C, C++, and FORTRAN programs.

There are other dynamic analysis tools like Eraser [80], FastTrack [34], CoRD [42], and RaceTrack [92] that use the lockset algorithm to detect races in parallel programs. IFRit [29] is a dynamic race detection tool based on Interference Free Regions(IFR). Since they are not specific to OpenMP, we have not discussed them here.

OpenMP-aware tools: Majority of the tools are either POSIX thread based or are specific to race detection in inherent parallelism of various programming languages, such as Java, C#, X10, and Chappel. The tools ompVerify [8], Archer [4], PolyOMP [20], DRACO [91], SWORD [91], and ROMP [39] are the only ones that exploit the intricate details of structured parallelism in OpenMP.

OMPRacer [84] is another recent LLVM-based tool that was announced during the course of publication of our work. OMPRacer relies on alias analysis, happens-before relations and locksets to statically detect races in OpenMP programs. The published version of OMPRacer [84] has a comparison with an initial version of LLOV. The comparison is limited to only C/C++ benchmarks, with no mention of comparison using FORTRAN benchmarks. Comparing with their published numbers, the current version of LLOV outperforms OMPRacer in precision, recall, and accuracy on DataRaceBench v1.2 benchmark.

Polyhedral model-based static analysis tools: To the best of our knowledge, ompVerify [8], DRACO [91], PolyOMP [20], and LLOV are the only tools for race detection in OpenMP programs that are based on the polyhedral framework. To put it theoretically, these are the only tools that use the exact dependence analysis of polyhedral compilation, which is crucial for the exact analysis of a large class of useful loop programs [10].

LLOV is different from these tools as it works on the LLVM-IR and collects OpenMP pragmas that have been lowered to library calls. This makes LLOV language independent. Also, the analysis phase of LLOV could be used for other purposes, like generating task graphs from the LLVM-IR.

Race detection in OpenMP programs for GPUs: Multitude of works [11, 46, 47, 48, 49, 50, 67, 71, 94, 95] have investigated the problem of verification of Compute Unified Device Architecture (CUDA) programs. However, not much work has gone into verification of OpenMP device offloading constructs. This might be due to lack of complete support for OpenMP device offloading to CUDA devices by the mainstream compilers. The recent work from Barua et al. [6] performs verification of the OpenMP host-device data mapping with the map clause. Arm DDT [3] is a commercial debugging tool that supports debugging of OpenMP and CUDA programs.

Recent works by Liao et al. [51, 53] and Lin et al. [54] compare different race detection tools using the DataRaceBench [51] benchmark. In Section 6, we show comparison of our tool LLOV with the other race detection tools on DataRaceBench, as well as two other benchmarks in greater detail.

We compare LLOV with the state-of-the-art data race detection tools as listed in Table 2. Some of the relevant tools were left out of our experimentation either because of their unavailability or due to their inability to handle OpenMP programs. We had issues setting up ROMP [39] and hence could not consider it for our comparison. ompVerify [8] is a prototype implementation in the Eclipse CDT/CODAN framework and can detect races in omp parallel for constructs only. Neither the binary nor source code for PolyOmp [20] and DRACO [91] are available in the open. We did not consider Intel Inspector due to its proprietary nature and licensing issues.⁴

For evaluation we chose DataRaceBench v1.2 [52, 53], DataRaceBench FORTRAN [43] (a FORTRAN implementation of DataRaceBench v1.2), and OmpSCR v2.0 [26] benchmark suits. All these benchmarks use OpenMP for parallelization and have known data races. The benchmarks cover OpenMP v4.5 pragmas comprehensively and contain data races due to common mistakes in OpenMP programming as listed earlier (Section 3).

DataRaceBench v1.2 [51], a seeded OpenMP benchmark with known data races, consists of 116 microbenchmark kernels, of which 59 kernels have true data races, while the remaining 57 kernels do not have any data races. Of these 59 true race kernels, 44 kernels have exactly one data race. The remaining 15 have more than one data race due to read and write operations to a scalar variable inside a loop. Such cases have all the three types of dependencies, namely read after write (RAW), write after read (WAR), and write after write (WAW) dependencies and thus result in more than one race. We have considered the location of the write operation for these cases and hence considered one TP per kernel. DataRaceBench FORTRAN has 52 kernels with true data races and 40 kernels without any data races. OmpSCR v2.0 is a benchmark suite for high performance computing using OpenMP v3.0 APIs. The benchmark consists of C/C++ and FORTRAN kernels that demonstrate the usefulness and pitfalls of the parallel programming paradigm with both correct and incorrect parallelization strategies. The kernels range from parallelization of simple loops with dependencies to more complex parallel implementations of algorithms such as Mandelbrot set generator, Molecular Dynamics simulation, Pi ($\pi$) calculation, LU decomposition, Jacobi solver, fast Fourier transforms (FFT), and Quicksort.

Performance Metrics Notations. We define terminology used for performance metrics as follows:

• True Positive (TP): If the evaluation tool correctly detects a data race present in the kernel, then it is a True Positive test result. A higher number of true positives represents a better tool.
  
• True Negative (TN): If the benchmark does not contain a race and the tool declares it as race-free, then it is a true-negative case. A higher number of true negatives represents a better tool.
  
• False Positives (FP): If the benchmark does not contain any race but the tool reports a race condition, then it is a false-positive case. A lower number of false positives are desirable.
  
• False Negatives (FN): False Negative test result is obtained when the tool fails to detect a known race in the benchmark. These are the cases that are missed by the tool. A lower number of false negatives are desirable.
  

We consider the following statistical measures as performance metrics in our experiments.

• Precision: Precision is the measure of closeness of the outcomes of prediction. Thus, a higher value of precision represents that the tool will more often than not identify a race condition when it exists.
  $Precision = \frac{TP}{TP\ +\ FP}$ $Recall = \frac{TP}{TP\ +\ FN}$.
  
• Recall: Recall gives the total number of cases detected out of the maximum data races present. A higher recall value means that there are less chances that a data race is missed by the tool. It is also called true-positive rate (TPR).
  
• Accuracy: Accuracy gives the chances of correct reports out of all the reports, as the name suggests. A higher value of accuracy is always desired and gives overall measure of the efficacy of the tool.
  $Accuracy = \frac{TP\ +\ TN}{TP\ +\ FP\ +\ TN\ +\ FN}$ $F1\ Score = 2 * \frac{Precision\ *\ Recall}{Precision\ +\ Recall}$.
  
  
• F1 Score: The harmonic mean of precision and recall is called the F1 score. An F1 score of 1 can be achieved in the best case when both precision and recall are perfect. The worst-case F1 score is 0 when either precision or recall is 0.
  
• Diagnostic odds ratio (DOR): It is the ratio of the positive likelihood ratio (LR$+$) to the negative likelihood ratio (LR$-$).
  $DOR = \frac{LR+}{LR-}$ where,
  Positive Likelihood Ratio $(LR+) = \frac{TPR}{FPR}$ , False Positive Rate $(FPR) = \frac{FP}{FP\ +\ TN}$ ,
  Negative Likelihood Ratio $(LR-) = \frac{FNR}{TNR}$ , False Negative Rate $(FNR) = \frac{FN}{FN\ +\ TP}$ and
  True Positive Rate $(TPR) = \frac{TP}{TP\ +\ FN}$ , True Negative Rare $(TNR) = \frac{TN}{TN\ +\ FP}$.
  DOR is the measure of the ratio of the odds of race detection being positive given that the test case has a data race, to the odds of race detection being positive given the test case does not have a race.
  

System configuration. We performed all our experiments on a system with two Intel Xeon E5-2697 v4 $@$ 2.30 GHz processors, each having 18 cores and 2 threads per core, totalling 72 threads and 128GB of RAM. The system runs 64 bit Ubuntu 18.04.2 LTS server with Linux kernel version 4.15.0-48-generic. LLOV is currently based on the LLVM/Polly version release 7.0.1 and can be upgraded to the latest LLVM/Polly versions with minimal changes.

Similar to Liao et al. [51], our experiments use two parameters: (i) the number of OpenMP threads and (ii) the input size for variable length arrays. The number of threads that we considered for the experiments are $\lbrace 3,36,45,72,90,180,256\rbrace$. For the 16 variable length kernels, we considered 6 different array sizes as follows: $\lbrace 32,64,128,256,512,1024\rbrace$. With each particular set of parameters, we ran each of the 116 kernels 5 times. Both the number of threads and array sizes can be found in prior studies [51, 53] and we have used the same for uniformity. Since the dynamic tools depend on the execution order of the threads, multiple runs are required. The 16 kernels with variable length arrays were run $3{,}360$ (16 kernels $\times$ 7 thread sizes $\times$ 6 array sizes $\times$ 5 runs) times in total. The remaining 100 kernels were run $3{,}500$ (100 kernels $\times$ 7 thread sizes $\times$ 5 runs) times in total. For all experiments, we used a timeout of 600 s for compilation as well as execution separately.