# CesASMe and Staticdeps: static detection of memory-carried dependencies for code analyzers

Théophile Bastian, Hugo Pompougnac, Alban Dutilleul, Fabrice Rastello

<figure><img src="image_1.png" /></figure>

## To cite this version:

Théophile Bastian, Hugo Pompougnac, Alban Dutilleul, Fabrice Rastello. CesASMe and Staticdeps: static detection of memory-carried dependencies for code analyzers. ACM Transactions on Architecture and Code Optimization, 2025, 22 (2), pp.1-23. 10.1145/3715125. hal-05460168

HAL Id: hal-05460168

https://inria.hal.science/hal-05460168v1

Submitted on 15 Jan 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

Latest updates: https://dl.acm.org/doi/10.1145/3715125

RESEARCH-ARTICLE

CesASMe and Staticdeps: static detection of memory-carried dependencies for code analyzers

THÉOPHILE BASTIAN, Grenoble Alpes University, Saint Martin d'Hères, Auvergne-Rhone-Alpes, France

HUGO POMPOUGNAC, INRIA Rhone-Alpes, Saint-Ismier, France

ALBAN DUTILLEUL, Rennes Higher Normal School, Bruz, Brittany, France

FABRICE E RASTELLO, INRIA Rhone-Alpes, Saint-Ismier, France

Open Access Support provided by:

INRIA Rhone-Alpes

Grenoble Alpes University

Rennes Higher Normal School

<figure><img src="image_8.png" /></figure>

PDF Download

3715125.pdf

15 January 2026

Total Citations: 0

Total Downloads: 619

Published: 30 June 2025

Online AM: 11 February 2025

Accepted: 29 December 2024

Revised: 28 November 2024

Received: 29 June 2024

Citation in BibTeX format
# CesASMe and Staticdeps: static detection of memory-carried dependencies for code analyzers

THÉOPHILE BASTIAN, Université Grenoble Alpes, Grenoble, France and Inria Centre de Recherche Grenoble Rhone-Alpes, Montbonnot, France

HUGO POMPOUGNAC, Inria Centre de Recherche Grenoble Rhone-Alpes, Grenoble, France

ALBAN DUTILLEUL, École Normale Supérieure de Rennes, Rennes, France

FABRICE RASTELLO, Inria Centre de Recherche Grenoble Rhone-Alpes, Grenoble, France and Université Grenoble Alpes, Grenoble, France

A variety of code analyzers, such as IACA, uiCA, llvm-mca, or Ithemal, strive to statically predict the throughput of a computation kernel. Each analyzer is based on its own simplified CPU model reasoning at the scale of a basic block. Facing this diversity, evaluating their strengths and weaknesses is important to guide both their usage and their enhancement.

We present CesASMe, a fully-tooled solution to evaluate code analyzers on C-level benchmarks composed of a benchmark derivation procedure that feeds an evaluation harness. We conclude that memory-carried data dependencies are a major source of imprecision for these tools. We tackle this issue with staticdeps, a static analyzer extracting memory-carried data dependencies, including across loop iterations, from an assembly basic block. We integrate its output to uiCA, a state-of-the-art code analyzer, to evaluate staticdeps' impact on a code analyzer's precision through CesASMe.

**CCS Concepts:** • Computer systems organization → Architectures; • Software and its engineering → Compilers; Software development techniques;

Additional Key Words and Phrases: Code analyzer, static analysis, optimization, assembly

**ACM Reference Format:**

Théophile Bastian, Hugo Pompougnac, Alban Dutilleul, and Fabrice Rastello. 2025. CesASMe and Staticdeps: static detection of memory-carried dependencies for code analyzers. *ACM Trans. Arch. Code Optim.* 22, 2, Article 48 (June 2025), 23 pages. https://doi.org/10.1145/3715125

## 1 Introduction

Modern software requires the ability to perform more computations, faster, and within increasingly constrained environments. As a result, performance engineers need tools that simplify the

New Article, Not an Extension of a Conference Paper.

Authors' Contact Information: Théophile Bastian, Université Grenoble Alpes, Grenoble, France and Inria Centre de Recherche Grenoble Rhone-Alpes, Montbonnot, Auvergne-Rhône-Alpes, France; e-mail: contact@tobast.fr; Hugo Pompougnac, Inria Centre de Recherche Grenoble Rhone-Alpes, Grenoble, Auvergne-Rhône-Alpes, France; e-mail: hugo.pompougnac@inria.fr; Alban Dutilleul, École Normale Supérieure de Rennes, Rennes, Bretagne, France; e-mail: alban.dutilleul@ens-rennes.fr; Fabrice Rastello, Inria Centre de Recherche Grenoble Rhone-Alpes, Grenoble, Auvergne-Rhône-Alpes, France and Université Grenoble Alpes, Grenoble, France; e-mail: Fabrice.Rastello@inria.fr.

<figure><img src="image_9.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License.

© 2025 Copyright held by the owner/author(s).

ACM 1544-3973/2025/06-ART48

https://doi.org/10.1145/3715125
understanding of a program's behavior—especially critical code sections—at the micro-architectural level.

This tooling includes binary or assembly code analyzers that statically predict the resource consumption of a basic block. Beyond raw measurements relying on hardware counters, these model-based analyses provide higher-level and refined data to identify bottlenecks and guide the optimization of specific code segments. This feedback is particularly useful when optimizing computational kernels, such as those used in scientific simulations and deep-learning applications.

This need has driven the development of a wide variety of code analyzers following the deprecation of IACA [14], which Intel has maintained through 2019. Tools such as `llvm-mca` [29], `uica` [3], `ithemal` [19], or `Gus` [11] all aim at producing various performance metrics, including the number of CPU cycles required by a computational kernel—which roughly translates to execution time.

Previous works (e.g., AnICA [26]) have revealed significant discrepancies in the reported predictions for programs with memory-carried dependencies. This suggests a more general limitation of current code analyzers, hinting that the underlying performance models struggle with accurately modeling memory dependencies. To verify this, an alternative analysis method must be provided and shown to produce more accurate predictions.

Such an approach also requires an evaluation framework robust enough to reliably compare different methods. Evaluating the underlying models of these different tools is not straightforward. Each of them addresses the challenge of modeling complex CPUs in its own unique way, striving to remain simple enough to deliver predictions in a reasonable time, yet resulting in different models.

However, existing approaches lack sound baselines against which to compare the predictions of code analyzers. They typically require *ad hoc*, handmade supplementary analysis. Some evaluate the results of a code analyzer by comparing it to those of another code analyzer (e.g., AnICA). Others perform actual measurements on—possibly randomly-generated—basic blocks isolated from their context, e.g., using `BHive` [7]. Clearly, these are not representative of real-world use cases and do not necessarily verify properties that performance engineers want to be able to rely on. Moreover, a basic block isolated from its context can behave very differently due to memory dependencies.

## 1.1 Contributions

The contributions of the present article are threefold.

*Evaluation harness.* We present a new method, materialized in a tool called `CesASMe`, to evaluate the state-of-the-art code analyzers. This method consists of three steps. The first step is to generate a large number of *microbenchmarks* (L1-resident benchmarks) that stress different aspects of the underlying models of the code analyzers, such as the front-end, the dependencies, or the CPU's execution ports. The second step is to measure accurately the execution time of each microbenchmark, in context, without separating its constituent basic blocks. The final step is to evaluate each code analyzer against this measurement, which involves aggregating its predictions for the microbenchmark's constituent basic blocks.

*Evaluation results.* The results of this evaluation show which code analyzers are the most accurate for the class of applications (computational, linear algebra kernels) and the microarchitecture (Intel x86-64 Skylake) studied. Our results concur with previous work [26]: basic blocks carrying dependencies across memory are poorly modeled, leading to significant inaccuracies.

*Extraction of memory-carried dependencies.* We introduce a new heuristic called `staticdeps` to extract and process memory-carried dependencies. This approach significantly improves the accuracy of the code analyzer `uica` [3]. This further confirms that dependencies constitute a significant limitation of its underlying model. Additionally, we demonstrate that the resulting extended analyzer fully outperforms the state-of-the-art.
## 1.2 Related Works

The static throughput analyzers studied rely on a variety of models. IACA [14], developed by Intel and now deprecated, is closed-source and relies on Intel's expertise on their own processors. The LLVM compiling ecosystem, to guide optimization passes, maintains models of many architectures. These models are used in the LLVM Machine Code Analyzer, llvm-mca [29], to statically evaluate the performance of a segment of assembly. Independently, Abel and Reineke used an automated microbenchmark generation approach to generate port mappings of many architectures in uops.info [1, 2] to model processors' backends. This work was continued with uiCA [3], extending this model with an extensive frontend description. Following a completely different approach, Ithemal [19] uses a deep neural network to predict basic blocks throughput. To obtain enough data to train its model, the authors also developed BHive [7], a profiling tool working on isolated basic blocks.

Another static tool, Osaca [17], provides lower- and upper-bounds to the execution time of a basic block. As this kind of information cannot be fairly compared with tools yielding an exact throughput prediction, we exclude it from our scope.

All these tools statically predict the number of cycles taken by a piece of assembly or binary that is assumed to be the body of an infinite—or sufficiently large—loop in steady state, all its data being L1-resident. As discussed by uiCA's authors [3], hypotheses can subtly vary between analyzers; e.g., by assuming that the loop is either unrolled or has control instructions, with non-negligible impact. Some of the tools, e.g., Ithemal, necessarily work on a single basic block, while some others, e.g., IACA, work on a section of code delimited by markers. However, even in the second case, the code is assumed to be straight-line code: branch instructions, if any, are assumed not taken.

Throughput prediction tools, however, are not all static. Gus [11] dynamically predicts the throughput of a whole program region, instrumenting it to retrieve the exact events occurring through its execution. This way, Gus can detect bottlenecks more finely through sensitivity analysis, at the cost of a significantly longer run time.

The BHive profiler [7] takes another approach by performing basic block throughput measurement instead of analysis: by mapping memory at any address accessed by a basic block, it can effectively run and measure arbitrary code without context, often—but not always, as we discuss later—yielding good results as one would expect from an actual measurement.

The OptiWISE profiling tool [12], contrary to all previous code analyzers, profiles a whole binary without emphasis on a critical section. Its goal, instead, is to identify said critical sections, by profiling once under the scrutiny of a perf-based sampling profiling—i.e., sampling the current program counter and elapsed cycles hardware counter at a fixed frequency—, and running a second time while instrumenting the binary to obtain precise information about the occurrence count of each instruction throughout the program's execution. By combining both data—profiled number of cycles and instruction hits—, OptiWISE reports an Instructions Per Cycle (IPC) metric for each section of the program. This way, the authors provide accurate hints to the experts to guide their optimization efforts towards relevant program parts. OptiWISE does not, however, model the processor's behavior, as it is not necessary for its goal.

The AnICA framework [26] also attempts to evaluate throughput predictors by finding examples in which they are inaccurate. AnICA starts with randomly generated assembly snippets and refines them through a process derived from abstract interpretation to reach general categories of problems.

## 2 Benchmarking Harness

The obvious solution to evaluate predictions is to compare them to an actual measure. However, as these tools reason at the basic block level, this is not as trivially defined as it would seem, especially when it comes to showing the impact of dependencies. As detailed later in Section 2.6, *without proper context, a basic block's throughput is not well-defined*.
To recover the context of each basic block, we reason instead at the scale of a C source code. This makes the measures unambiguous: one can use hardware counters to measure the elapsed cycles during a loop nest. This requires a suite of benchmarks, in C, that both is representative of the domain studied, and wide enough to have a good coverage of the domain. However, this is not in itself sufficient to evaluate static tools: the number of cycles reported by the counters can be the result of an arbitrarily large number of loop turns, with conditional branches taken or not. This number hardly compares to llvm-mca, IACA, Ithemal, and uiCA basic block-level predictions seen above that only predict the throughput of individual basic blocks.

*Predictions lifting.* We developed a basic block occurrences counter to count the number of occurrences of a basic block during kernel execution. Then, we use this number of occurrences to weight basic block throughput predictions from the code analyzers. Finally, we lift code analyzers’ results by summing the weighted basic block predictions of a kernel $K$:

$$ \text{lifted\_prediction}(\mathcal{K}) = \sum_{b \in \text{BBs}(\mathcal{K})} \text{occurrences}(b) \times \text{prediction}(b). \quad (1) $$

The necessity to lift the prediction arises from the fact that the compiler can disrupt the intuitive mapping of a C code segment to a binary basic block. Typically, it may insert a loop pre-header to initialize the local variables of the loop body. By extending the code analyzers’ predictions to encompass multiple basic blocks rather than just one, our approach effectively addresses this scenario.

While not applicable to all classes of programs, it is grounded in the same hypotheses as those used by code analyzers for input programs. It is, therefore, best suited to the highly regular scientific computing and machine learning programs that drive binary code analysis efforts. To be effective, it requires:

- the absence of conditional control flow beyond the surrounding loop of the basic block, as the order in which dependencies are decoded and branch mispredictions

- data residence in L1 cache, due to the significance of locality and data movement within the cache hierarchy.

*Architecture of our benchmarking harness.* Our benchmarking framework works in four successive stages, whose high-level view is shown in Figure 1. It first generates relevant microbenchmarks (i.e., L1-resident benchmarks) by applying a series of transformations to an existing benchmark suite which is, in our case, the HPC-native Polybench [24] suite. It then extracts the basic blocks constituting a computation kernel, and instruments it to retrieve their respective occurrences in the original context. It runs all the studied tools on each basic block, while also running measures on the whole computation kernel. Finally, the block-level results are lifted to kernel-level results using the occurrences previously measured.

## 2.1 Generating Microbenchmarks

The first stage of our benchmarking harness consists in generating a set of microbenchmarks. We extend AnICA’s random-based approach mentioned above in order to produce microbenchmarks diverse enough, but related to real-life kernels. Thus, our approach consists in applying several transformations to an existing benchmark suite.

(1) We produce several versions of each benchmark using loop nest optimizers (Pluto[6] and PoCC [23]). The latter gives access to a wide variety of transformations: register tiling, tiling, skewing, vectorization/simdization, loop unrolling, loop permutation, loop fusion, and so on.

(2) We instrument the resulting code in order to extract the loop that has the greatest impact on performance while being L1-resident. This microkernel is isolated from the initial benchmark,
<figure><img src="image_10.png" /><figcaption>Fig. 1. Our analysis and measurement environment.</figcaption></figure>

```
for (i = 0; i < _PB_M; i++) {
    for (j = 0; j < _PB_N; j++) {
        for (k = i+1; k < _PB_M; k++) {
            B[i][j] += A[k][i] * B[k][j];
            B[i][j] = alpha * B[i][j];
        }
    }
}
```

Listing 1. The trmm benchmark's kernel from Polybench.

```
for (k = (i+1); k < _PB_M; k++)
    B[i][j] += A[k][i] * B[k][j];
```

Listing 2. The hottest loop extracted from Listing 1 when no loop optimizations have been applied.

```
for (j = 0; j < _PB_N; j++)
    B[i][j] += A[k][i] * B[k][j];
```

Listing 3. The hottest loop extracted from Listing 1 after the triggering of Pluto's parallelization pass.

and incorporated into a parameterized template where requested behaviors, as the number of successive measurements, are set. We call this refined benchmark a *microbenchmark*.

(3) Given a microbenchmark, we produce several binaries by applying different compilation strategies (enabling/disabling auto-vectorization, extended instruction sets, etc.).

Microbenchmarks generated in this way are representative of the hottest loop of the initial benchmark in terms of instructions, even if they do not calculate the same result as the latter (nor, in general, as other versions of the same benchmark). We only use them to stress different aspects of the underlying models embedded in the code analyzers and evaluate them against a measurement.

Consider steps (1) and (2) applied to the trmm benchmark (transpose and matrix multiply) from Polybench.

The hottest loop of Listing 1, if no loop transformation occurs, is clearly the innermost loop—i.e., the *k* axis—, as shown in Listing 2. The resulting code is dependency-bound since *i* and *j* are fixed and *B[i][j]* is read and then written at each iteration.

When Pluto's parallelization pass is triggered, as shown in Listing 3, the *j* and *k* axes are swapped before the hottest loop is extracted. Thus, the latter iterates on *j* instead of *k*, and *i* and *k* are the
fixed values. The microkernel is no longer dependency-bound and stresses another aspect of the microarchitectural models (in this case, the execution engine ports).

At step (3), each microbenchmark generated in this way is then compiled using different compilation strategies (SIMD instructions or not, unrolling or not, etc.), to produce several distinct executables.

## 2.2 Basic Block Extraction

Given a compiled microbenchmark, we use the Capstone disassembler [25], and split the assembly code after each control flow instruction (jump, call, return, ...) and before each jump site—that is, location to which a branch instruction within the considered code segment may jump.

To accurately obtain the occurrences of each basic block in the whole kernel's computation, we then instrument it with gdb by placing a break point at each basic block's first instruction in order to count the occurrences of each basic block between two calls to the perf counters.<fnref n="1" /> This part plays in our harness a role similar to the instrumentation pass used in OptiWISE [12]: the timing results are discarded, while block occurrences information is combined with our timing measures from other, non-instrumented runs.

## 2.3 Throughput Predictions and Measures

The harness leverages a variety of tools: actual CPU measurement; the B Hive basic block profiler [7]; l lvm-mca [29], uica [3], and IACA [14], which leverage microarchitectural models to predict a block's throughput; I themal [19], a machine learning model; and Gus [11], a dynamic analyzer based on Q Emu that works at the whole binary level.

The execution time of the full kernel is measured using Linux perf [18] CPU counters around the full computation kernel. The measure is repeated four times and the smallest is kept; as the caches are not flushed, this ensures that the cache is warm and compensates for context switching or other measurement artifacts. Gus instruments the whole function body. The other tools work at basic block level; these are run on each basic block of each benchmark.

We emphasize the importance, throughout the whole evaluation chain, to keep the exact same assembled binary. Indeed, recompiling the kernel from the source *cannot* be assumed to produce the same assembly kernel. This is even more important in the presence of slight changes: for instance, inserting IACA markers at the C-level—as is intended—around the kernel *might* change the compiled kernel, if only for alignment reasons. Furthermore, those markers prevent a binary from being run by overwriting registers with arbitrary values. This forces a user to run and measure a version which is different from the analyzed one. In our harness, we circumvent this issue by adding markers directly at the assembly (already compiled) basic block level. Our gdb instrumentation procedure also respects this principle of single-compilation. As QEmu breaks the perf interface, we have to run Gus with a preloaded stub shared library to be able to instrument binaries containing calls to perf.

## 2.4 Prediction Lifting and Filtering

We finally lift single basic block predictions to a whole-kernel cycle prediction by summing the block-level results, weighted by the occurrences of the basic block in the original context (Equation (1) above). If an analyzer fails on one of the basic blocks of a benchmark, the whole benchmark is discarded for this analyzer.

We control the proportion of cache misses in the program's execution using Cachegrind [20] and Gus; programs that have more than 15 % of cache misses on a warm cache are not considered L1-resident and are discarded.

<footnote n="1">¹We assume the program under analysis to be deterministic.</footnote>
<figure><img src="image_11.png" /><figcaption>Fig. 2. Relative error distribution wrt. perf.</figcaption></figure>

<table><caption>Table 1. Relative Error Statistics wrt. perf</caption><thead><tr><th></th><th>Best block-based</th><th>BHive</th></tr></thead><tbody><tr><td>Datapoints</td><td>3500</td><td>2198</td></tr><tr><td>Errors</td><td>0</td><td>1302</td></tr><tr><td></td><td>(0 %)</td><td>(37.20 %)</td></tr><tr><td>Average (%)</td><td>11.60</td><td>27.95</td></tr><tr><td>Median (%)</td><td>5.81</td><td>7.78</td></tr><tr><td>Q1 (%)</td><td>1.99</td><td>3.01</td></tr><tr><td>Q3 (%)</td><td>15.41</td><td>23.01</td></tr></tbody></table>

## 2.5 Soundness of CesASMe's Methodology

Given a time prediction $C_{pred}$ (in cycles) and a baseline $C_{baseline}$, we define its relative error as

$$err = \frac{|C_{pred} - C_{baseline}|}{C_{baseline}}. \qquad (2)$$

We assess the commensurability of the whole benchmark, measured with perf, to lifted block-based results by measuring the statistical distribution of the relative error of two series: the predictions made by BHive, and the series of the best block-based prediction for each benchmark, defined below.

We single out BHive as it is the only tool able to *measure*—instead of predicting—an isolated basic block’s timing. Since BHive is based on measures—instead of predictions—through hardware counters, an excellent accuracy is expected. This, however, is not sufficient: as discussed later in Section 2.6, BHive is not able to yield a result for about 40 % of the benchmarks and is subject to large errors in some cases.

To remedy this, we also consider the *best block-based prediction* series. Independently for each benchmark, we keep the prediction whose relative error to the perf measure is the lowest. Should the error of this series be compatible with the block-based errors of the state-of-the-art, we expect our lifting methodology to be sound.

The result of this analysis is presented in Table 1 and in Figure 2. The results are in a range compatible with common results of the field, e.g., Abel and Reineke [3] report Mean Absolute Percentage Error (MAPE, corresponding to the “Average” row) of about 10–15 % in many cases. While lifted BHive’s average error is driven high by large errors on certain benchmarks, which were investigated later in this article, its median error is still comparable to the errors of state-of-the-art tools. From this, we conclude that lifted cycle measures and predictions are consistent with whole-benchmark measures; and consequently, lifted predictions can reasonably be compared to one another.

## 2.6 Understanding BHive's Results

The error distribution of BHive against perf, plotted right in Figure 2, puts forward irregularities in BHive’s results. Its lack of support for control flow instructions can be held accountable for a portion of this accuracy drop; our lifting method, based on block occurrences instead of paths, can explain another portion. We also find that BHive fails to produce a result in about 40 % of the kernels explored—which means that, for those cases, BHive failed to produce a result on at least one of the constituent basic blocks. In fact, this is due to the need to reconstruct the context of each basic block *ex nihilo*.
The basis of BHive's method is to run the code to be measured, unrolled a number of times depending on the code size, with all memory pages but the code unmapped. As the code tries to access memory, it will raise segfaults, caught by BHive's harness, which allocates a single shared-memory page, filled with a repeated constant, that it will map wherever segfaults occur before restarting the program. BHive mainly fails on bad code behavior (e.g., control flow not reaching the exit point of the measure if a bad jump is inserted), too many segfaults to be handled, or a segfault that occurs even after mapping a page at the problematic address.

The registers are also initialized, at the beginning of the measurement, to the fixed constant 0x2324000. We show through two examples that this initial value can be of crucial importance.

The following experiments are executed on an Intel(R) Xeon(R) Gold 6230R CPU (Cascade Lake), with hyperthreading disabled.

*Imprecise analysis.* Consider this x86-64 kernel:

```
vmulsd (%rax), %xmm3, %xmm0
vmovsd %xmm0, (%r10)
```

When executed with all the general purpose registers initialized to the default constant, BHive reports 9 cycles per iteration, since %rax and %r10 hold the same value, inducing a read-after-write dependency between the two instructions. If, however, BHive is tweaked to initialize %r10 to a value that aliases (wrt. physical addresses) with the value in %rax, e.g., between 0x10000 and 0x10007 (inclusive), it reports 19 cycles per iteration instead; while a value between 0x10008 and 0x1009f (inclusive) yields the expected 1 cycle—except for values in 0x10039-0x1003f and 0x10079-0x1007f, yielding 2 cycles as the store crosses a cache line boundary.

In the same way, the value used to initialize the shared memory page can influence the results whenever it gets loaded into registers.

*Failed analysis.* Some memory accesses will always result in an error; for instance, it is impossible (by default) to mmap at an address lower than 0x10000. Thus, with equal initial values for all registers, the following kernel would fail, since the second operation attempts to load at address 0:

```
subq %r11, %r10
movq (%r10), %rax
```

Such errors can occur in more complex ways. The following x86-64 kernel, for instance, is extracted from a version of the durbin kernel:

```
vmovsd 0x10(%r8, %rcx), %xmm6
subl %eax, %esi
movslq %esi, %rsi
vfмadd231sd -8(%r9, %rsi, 8), \
           %xmm6, %xmm0
```

Here, BHive fails to measure the kernel when run with registers initialized to the default constant at the 2nd occurrence of the unrolled loop body, failing to recover from an error at the vfmadd231sd instruction with the mmap strategy. Indeed, after the first iteration the value in %rsi becomes null, then negative at the second iteration; thus, the second occurrence of the last instruction fetches at address 0xffffffff0a03ff8, which is in kernel space. This microkernel can be benchmarked with BHive e.g., by initializing %rax to 1. Furthermore, on most 64-bits CPUs, addresses are only valid if they are representable on 48 bits (correctly sign-extended to fill 64 bits) [4, 15], called *canonical form*, causing further failures in BHive. Other kernels still fail with accesses relative to the instruction pointer, as BHive read-protects the unrolled microkernel's instructions page.
# 3 Static Extraction of Memory-carried Dependencies

As put forward by AnICA [26], memory-carried dependencies are a difficult challenge for code analyzers. This is further confirmed by the results of CesASMe, presented in Section 4.3.

To this end, we present staticdeps, a heuristic-based static assembly analyzer able to extract most of the memory-carried dependencies that are relevant from a latency analysis perspective. It operates at the basic-block level, and tracks dependencies across arbitrarily complex pointer arithmetic, through arbitrarily many loop iterations.

Working at the basic-block level, it is however lacking context, as we argued earlier; as such, it cannot detect aliasing stemming from outside of the loop.

## 3.1 A Microarchitectural Point of View on Dependencies

Modern Out-of-Order (OoO) hardware has dedicated significant architectural resources to maximize the pipeline usage. One such key component is the reorder buffer (ROB)—an extension of Tomasulo’s algorithm [30]—, a circular buffer storing incoming µOPs, decoded and renamed from instructions, in the frontend. When a µOP is committed, as soon as it is no longer busy, the ROB can safely move its head pointer, freeing space for new µOPs at its tail.

In particular, if a µOP $\mu_1$ is not yet committed, the ROB may not contain µOPs more than the ROB’s size ahead of $\mu_1$. This is also true for instructions, as the vast majority of instructions decode to at least one µOP.<fnref n="2" />

Nevertheless, instruction level parallelism (ILP) might still be limited, either by dependencies or other factors. Speculative techniques such as memory disambiguation [13, 27] address that point, by for instance trying to detect whether a given load depends on an earlier not-yet-committed store, in order to allow safe out-of-order execution of non-dependent memory accesses. If such speculation turns out wrong, execution is typically rolled back to before the offending load in the ROB, incurring at least the penalty of another load.

Recent microarchitectures still lack ways of dealing with true data dependencies, especially at the memory level, even if ongoing research with value prediction [22, 28] tackles that issue, but to the best of our knowledge value prediction has not yet been implemented in products of mainstream CPU vendors.

## 3.2 Different Types of Dependencies

Depending on their type, some dependencies are significantly harder to statically detect than others.

**Register-carried dependencies**, when in straight-line code, can be detected by keeping track of which instruction last wrote each register in a *shadow register file*. This is most often supported by code analyzers—for instance, `llvm-mca` and `uiCA` support it.

Loop-carried dependencies can, to some extent, be detected in the same way. As the basic block is always assumed to be the body of an infinite loop, a straight-line analysis can be performed on a duplicated kernel. This strategy is e.g., adopted by Osaca [17, Section II.D]. When dealing only with register accesses, this strategy is always sufficient: as each iteration always executes the same basic block, it is not possible for an instruction to depend on another instruction two iterations earlier or more.

**Memory-carried dependencies**, however, are significantly harder to tackle. While basic heuristics can handle some simple cases, in the general case two main difficulties arise:

(i) pointers may alias, i.e., point to the same address or array; for instance, if `%rax` points to an array, it may be that `%rbx` points to `%rax+8`, making the detection of such a dependency difficult;

<footnote n="2">²Some mov instructions from register to register may, for instance, only have an impact on the renamer; no µOPs are dispatched to the backend.</footnote>
(ii) arbitrary arithmetic operations may be performed on pointers, possibly through diverting paths: e.g., it might be necessary to detect that %rax + 16 << 2 is identical to %rax + 128/2; this requires semantics for assembly instructions and tracking formal expressions across register values—and possibly even memory.

Besides, dependencies may reach further back than the previous iteration, e.g., in a dynamic imple-
mentation of the Fibonacci sequence. The strategy previously used for register-carried dependencies
is, therefore, not sufficient at all times.

3.3 Approximating Dependencies

In a compiler, the legality of certain transformations depends on the existence of dependencies or
aliasing between pointers. The latter are therefore extracted using two different analyses:

(1) **Aliasing analysis** seeks to determine whether two pointers live in the same memory area—e.g., the same `malloc`'d region—, without necessarily referencing the exact same address. If so, they are said *may-alias*; if not, *no-alias* (equivalent to the hand-written `restrict` keyword in C). The keyword *must-alias* describes a stronger property when pointers are known to actually reference the same address. This alias analysis is usually a subproduct of the points-to analysis [10] which aims at determining which pointers point to which memory area.

(2) **Dependency analysis** consists of extracting **Read-After-Write (RAW)**, **Write-After-Read (WAR)**, and **Write-After-Write (WAW)** dependencies between pointers that live in the same memory area (i.e., *may-alias*). In modern compilers, this analysis typically exploits Memory SSA [9] and **Scalar Evolution (SCEV)**, which models how scalar values change inside loops.

A compiler's correctness depends on the soundness of these analyses. Staticdeps, however, aims at providing dependencies for a throughput analysis: its goal is not to provide soundness at all costs but to provide an approximation that strives to be as accurate as possible.

In our case, the context of the basic blocks is unknown. Consequently, one can not rely on the SCEV or points-to analysis, and therefore, one can not rely on alias and dependency analysis either: it is mandatory to approximate the latter. This approximation we suggest is based on two postulates whose relevance (i.e., ability to keep the number of false negatives and false positives below a certain threshold) will be evaluated in Section 4:

(1) Any new encountered pointer—function parameters, value read from memory, ...—is assumed to be no-alias, i.e., every new encountered value is assumed to be independent of every other. Two values may still alias if they are derived from e.g., the same function parameter.

(2) Execution using random input variables is sufficient to highlight the significative dependen-
cies between may-alias pointers.

**3.4 The staticdeps Heuristic**

To statically detect memory dependencies, we use a randomized heuristic approach. We consider
the set $\mathcal{R}$ of values representable by a 64-bits unsigned integer; we extend this set to $\bar{\mathcal{R}} = \mathcal{R} \cup \{\perp\}$,
where $\perp$ denotes an invalid value. We then proceed by keeping track of which instruction last
wrote each memory address written to, using the following principles.

- Whenever an unknown value is read, either from a register or from memory, generate a fresh value from $\mathcal{R}$, uniformly sampled at random—this implements our postulate (1) from above. This value is saved to a shadow register file or memory, and will be used again the next time this same data is accessed. Note that a shadow is a data structure that describes the original component with a given granularity and additional meta-information. For instance, a shadow memory in our case is a set of memory locations, each of which is associated with a value from $\bar{\mathcal{R}}$ and the last instruction that wrote to it.
**ALGORITHM 1:** The staticdeps algorithm

```c
function STATICDEPS(basic_block)
    deps ← ∅
    insn_count, cur_iter, cur instruction ← 0
    shadow_memory, shadowRegisters, last_wrote_at ← ∅map

    function FRESH
        return random uint64_t value
    end

    function READ_MEMORY(address)
        Assert address ≠ ⊥
        if address ∉ shadow_memory then
            shadow_memory[address] ← FRESH
        end
        return shadow_memory[address]
    end

    function READREGISTER/register
        (likewise)
    end

    function EXPR_VALUE(expr)
        if expr == Register(reg) then
            return READREGISTER(reg)
        else if expr == Memory(addr_expr) then
            addr ← EXPR_VALUE(addr_expr)
            if addr ∈ last_wrote_at then
                deps ← deps ∪ (last_wrote_at[addr] → (cur_iter, cur instruction))
                return READ_MEMORY(addr)
            else if expr == IntegerArithmeticOp (operator, op1, ..., opN) then
                if EXPR_VALUE(op_i) == ⊥ for any i then
                    return ⊥
                return semantics(Operator)(
                    EXPR_VALUE(op1), ..., EXPR_VALUE(opN))
                )
            else return ⊥
        else
            function ITER_STATEMENT.statement
                lhS, rhS ← statement
                if lhS == Register(reg) then
                    shadow_register[reg] ← EXPR_VALUE(rhS)
                else if lhS == Memory(addr_expr) then
                    addr ← EXPR_VALUE(addr_expr)
                    last_wrote_at[addr] ← (cur_iter, cur__ instruction)
                    shadow_memory[addr] <- EXPR_VALUE(rhS)
                else if ... then ...
                    ...
                end
            end
        else
            while insn_count <= |ROB| + |basic_block| do
                cur__ instruction ← 0
                for statement ∈ basic_block do
                    ITER_STATEMENT.statement
                    if statement is last statement of an instruction then
                        cur__ instruction ← cur__ instruction + 1
                        insn_count ← insn_count + 1
                    end
                end
                cur__ iter ← cur__ iter + 1
            end
            return deps
        end
    end
```
- Whenever an integer arithmetic operation is encountered, compute the result of the operation and save the result to the shadow register file or memory.

- Whenever another kind of operation or an unsupported operation is encountered, save the destination operand as $⊥$; this operation is assumed to not be valid pointer arithmetic. Operations on $⊥$ always yield $⊥$ as a result.

- Whenever writing to a memory location, compute the written address using the above principles, and keep track of the instruction that last wrote to a memory address.

- Whenever reading from a memory location, compute the read address using the above principles, and generate a dependency from the current instruction to the instruction that last wrote to this address (if known).

**Remark 1.** Given the structure of the ROB as detailed above, a dependency is relevant only if it does not reach more than the size of the ROB away.

Let $(I_p)_{0≤p<n}$ be a trace of executed instructions. For $p < p'$, distance $(I_p, I_{p'})$ is the overall number of decoded µOPs for the subtrace $(I_r)_{p<r<p'}$.

There exists $R \in \mathbb{N}$ such that the presence or absence of a dependency between two instructions that are separated by at least $R - 1$ other µOPs has no impact on the performance of this kernel. Furthermore, $R$ is independent of the considered kernel—in practice, it is given by the number of µOPs held by the reorder buffer of the processor.

More formally, let $\mathcal{K}$ be a kernel of $n$ instructions. Let $(I_p)_{p \in \mathbb{N}}$ be the trace of $\mathcal{K}$'s instructions executed in a loop. For any $p, q \in \mathbb{N}$ such that distance $(I_p, I_q) \ge R - 1$, the throughput of $\mathcal{K}$ is invariant in the presence or absence of a dependency between the pairs of instructions $(I_{p+kn}, I_{q+kn})_{k \in \mathbb{N}}$.

The formal proof of this assertion is provided in Appendix A.

A possible solution to detect loop-carried dependencies in a kernel $\mathcal{K}$ is thus to unroll it until it contains at least $|\text{ROB}| + |\mathcal{K}|$ instructions. This ensures that every instruction in the last kernel can find dependencies reaching up to $|\text{ROB}|$ back.

We detail our staticdeps algorithm in pseudocode in Algorithm 1.

On Intel CPUs, the reorder buffer size contained 224 µOPs on Skylake (2015), or 512 µOPs on Golden Cove (2021) [31]. These sizes are small enough to reasonably use this solution without excessive slowdown.

## 3.5 Practical Implementation

We implement staticdeps in Python, using pyelftools and the capstone disassembler to extract and disassemble the targeted basic block. The semantics needed to compute encountered operations are obtained by lifting the kernel's assembly to valgrind [21]'s VEX intermediary representation.

The implementation of the heuristic detailed above provides us with a list of dependencies across iterations of the considered basic block. We then “re-roll” the unrolled kernel: each dependency is written as a triplet (source, dest, $\Delta k$), where the first two elements are the source and destination instruction of the dependency in the original, non-unrolled kernel, and $\Delta k$ is the number of iterations of the kernel between the source and destination of the dependency.

Finally, we filter out spurious dependencies: each dependency found should occur for each kernel iteration $i$ at which $i + \Delta k$ is within bounds. If the dependency is found for less than 80% of those iterations, the dependency is declared spurious and is dropped.

## 3.6 Example: Computing the Fibonacci Sequence

Consider the implementation of the Fibonacci sequence in Listing 4. At -01 optimization level, the gcc compiler translates its loop into the x86-64 assembly in Listing 5 (instruction addresses edited for clarity).
<table><caption>Table 2. Possible Internal State of staticdeps Running on Listing 5</caption><thead><tr><th>Before insn</th><th>[0,0]</th><th>[0,1]</th><th>[0,2]</th><th>[0,3]</th><th>[0,4]</th><th>[0,5]</th><th>[1,1]</th><th>[1,2]</th><th>[1,3]</th><th>[2,1]</th><th>[2,2]</th><th>[2,3]</th></tr></thead><tbody><tr><td><strong>Registers</strong></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>%rax</td><td>?</td><td>100</td><td>100</td><td>100</td><td>104</td><td>104</td><td>104</td><td>104</td><td>104</td><td>108</td><td>108</td><td>108</td></tr><tr><td>%edx</td><td>?</td><td>200</td><td>376</td><td>376</td><td>376</td><td>376</td><td>176</td><td>552</td><td>552</td><td>376</td><td>928</td><td>928</td></tr><tr><td>%rcx</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>42</td><td>42</td><td>42</td><td>42</td><td>42</td><td>42</td><td>42</td></tr><tr><td><strong>Memory</strong></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>100</td><td>?</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td><td>200</td></tr><tr><td>104</td><td>?</td><td>?</td><td>176</td><td>176</td><td>176</td><td>176</td><td>176</td><td>176</td><td>176</td><td>176</td><td>176</td><td>176</td></tr><tr><td>108</td><td>?</td><td>?</td><td>?</td><td>376</td><td>376</td><td>376</td><td>376</td><td>376</td><td>376</td><td>376</td><td>376</td><td>376</td></tr><tr><td>112</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>552</td><td>552</td><td>552</td><td>552</td></tr><tr><td>116</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>?</td><td>928</td></tr></tbody></table>

```c
int fibo(int* F, int n) {
    for(int i=2; i <= n; ++i) {
        F[i] = F[i-1] + F[i-2];
    }
    return F[n];
}
```

Listing 4. A C implementation of the Fibonacci sequence

```c
0:   mov  (%rax),%edx
1:   add  0x4(%rax),%edx
2:   mov  %edx,0x8(%rax)
3:   add  $0x4,%rax
4:   cmp  %rcx,%rax
5:   jne   0
```

Listing 5. x86-64 assembly code for the loop of Listing 4, compiled by gcc-01

In Table 2, we simulate a possible run of staticdeps on the assembly code in Listing 5. Each column corresponds to an internal state of staticdeps just before an instruction, where `[i, j]` means instruction *j* of the *i*-th repetition of the kernel. While this figure does not show it explicitly, staticdeps also retains the information of which instruction last wrote each memory cell. A cell on a light blue background means that this instruction read this memory cell, while a darker yellow background means the cell was written.

The kernel is first unrolled enough times to fill the reorder buffer, plus one full kernel. The first instruction reads `%rax`, which value is unknown; a fresh one is generated, here 100. The memory is then read at address 100, also unknown; a fresh value, here 200, is generated. Register `%edx` is written with this value. At instruction 2, memory is written at address `%rax + 8`, ie. 108.

Later at instruction [1, 2], memory is read at address `%rax + 4`, which is now also 108. As the last instruction that wrote this cell (`[0, 3]`) is known, this generates a dependency `2 → 3` at iteration -1.

At the next iteration, dependencies `1 → 3` at iteration -2 and `2 → 3` at iteration -1 are generated. This evaluation is continued until the end of the unrolled kernel.

If the kernel was unrolled e.g., 40 times, a dependency for iteration -2 can be registered only 38 times; hence, such dependencies are filtered out if they occurred less than `[80% × 38] = 30` times. Here, both dependencies are kept, and staticdeps correctly reports the two dependencies.

## 3.7 Limitations

In its current implementation, `staticdeps` is limited to `RAW` dependencies, which we believe to be sufficient for latency analysis on usual CPUs. However, our heuristic may easily support other types of dependencies (e.g., WAW) by tracking additional data if necessary.

We argued earlier that one of the shortcomings that most crippled state-of-the-art tools was that analyses were conducted out-of-context, considering only the basic block at hand. This analysis is also true for `staticdeps`, as it is still focused on a single basic block in isolation; in particular, any aliasing that stems from outside the analyzed basic block is not visible to `staticdeps`.
Work towards a broader analysis range, e.g., at the scale of a function, or at least initializing
values with gathered assertions—maybe based on abstract interpretation techniques—could be
beneficial to the quality of dependencies detections.

As *staticdeps*'s heuristic is based on randomness, it may yield false positives: two registers
could theoretically be assigned the same value sampled at random, making them aliasing addresses.
This is, however, very unlikely, as values are sampled from a set of cardinality 2<sup>64</sup>. If necessary,
the error can be reduced by amplification: running multiple times the algorithm on different
randomness seeds reduces the error exponentially.

Conversely, *staticdeps* should not present false negatives due to randomness. Dependencies
may go undetected, e.g., because of out-of-scope aliasing or unsupported operations. However, no
dependency that falls into the scope of our baseline *depsim*—as briefly described in Section 4.4—
should be missed because of random initializations.

In silicon, dependencies are implemented not between instructions, but between µOPs. Modeling
the decomposition of instructions to µOPs, together with providing semantics for each µOP, however,
is not done to our knowledge. Furthermore, it would need to be done for each microarchitecture:
while instructions' semantics are defined by the ISA, each microarchitecture may split instructions
to µOPs in its own way.

# 4 Experiments and Evaluation

Our experiments are twofold. We first analyze the results from CesASMe, from which we confirm AnICA's case study: memory-carried dependencies are a crucial shortcoming of state-of-the-art analyzers. We then evaluate staticdeps' capacity to detect these dependencies: we first compare the dependencies detected to those actually present, then evaluate the gain in precision when enriching uiCA's model with staticdeps.

## 4.1 Experimental Environment

The experiments presented in this article were all realized on a Dell PowerEdge C6420 machine
from the Grid5000 cluster [5], equipped with 192 GB of DDR4 SDRAM—only a small fraction of
which was used—and two Intel Xeon Gold 6130 CPUs (x86-64, Skylake microarchitecture) with 16
cores each.

The experiments themselves were run inside a Docker environment very close to our artifact,
based on Debian Bullseye. Care was taken to disable TurboBoost and hyperthreading to improve
measurement stability. For tools whose output is based on a direct measurement (perf, BHive), the
benchmarks were run sequentially on a single core with no experiments on the other cores. No
such care was taken for Gus as, although based on a dynamic run, its prediction is purely a function
of recorded program events and not of program measures. All other tools were run in parallel.

We use llvm-mca v13.0.1, IACA v3.0-28-g1ba2cbb, Gus at commit 87463c9, BHive at commit
5f1d500, uiCA at commit 9cbbe93, Ithemal at commit b3c39a8.

## 4.2 CesASMe: Analyzers' Throughput Predictions

Running CesASMe's harness provides us with 3,500 benchmarks, on which each throughput predictor
is run. Out of the initial 3,744 initially generated benchmarks, 244 were filtered out as non-L1-
resident, i.e., 6.5 % of discarded benchmarks. We make the full output of our tool available in our
artifact.

The raw complete output from CesASMe—roughly speaking, a large table with, for each bench-
mark, a cycle measurement, cycle count for each throughput analyzer, the resulting relative error,
and a synthesis of the bottlenecks reported by each tool—enables many analyses that, we believe,
<table><caption>Table 3. Statistical Analysis of Overall Results</caption><thead><tr><th>Bencher</th><th>Datapoints</th><th>Failures</th><th>(%)</th><th>MAPE</th><th>Median</th><th>Q1</th><th>Q3</th><th>K. tau</th><th>Time (CPU-h)</th></tr></thead><tbody><tr><td>BHive</td><td>2,198</td><td>1,302</td><td>(37.20 %)</td><td>27.95 %</td><td>7.78 %</td><td>3.01 %</td><td>23.01 %</td><td>0.81</td><td>1.37</td></tr><tr><td>llvm-mca</td><td>3,500</td><td>0</td><td>(0.00 %)</td><td>36.71 %</td><td>27.80 %</td><td>12.92 %</td><td>59.80 %</td><td>0.57</td><td>0.96</td></tr><tr><td>UiCA</td><td>3,500</td><td>0</td><td>(0.00 %)</td><td>29.59 %</td><td>18.26 %</td><td>7.11 %</td><td>52.99 %</td><td>0.58</td><td>2.12</td></tr><tr><td>Ithemal</td><td>3,500</td><td>0</td><td>(0.00 %)</td><td>57.04 %</td><td>48.70 %</td><td>22.92 %</td><td>75.69 %</td><td>0.39</td><td>0.38</td></tr><tr><td>Iaca</td><td>3,500</td><td>0</td><td>(0.00 %)</td><td>30.23 %</td><td>18.51 %</td><td>7.13 %</td><td>57.18 %</td><td>0.59</td><td>1.31</td></tr><tr><td>Gus</td><td>3,500</td><td>0</td><td>(0.00 %)</td><td>20.37 %</td><td>15.01 %</td><td>7.82 %</td><td>30.59 %</td><td>0.82</td><td>188.04</td></tr></tbody></table>

<figure><img src="image_12.png" /><figcaption>Fig. 3. Statistical distribution of relative errors.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 4. Statistical distribution of relative errors, with and without pruning latency bound through memory-carried dependencies rows (llvm-mca outliers trimmed).</figcaption></figure>

could be useful both to throughput analysis tool developers and users. Tool designers can draw insights on their tool's best strengths and weaknesses, and work towards improving them with a clearer vision. Users can gain a better understanding of which tool is more suited for each situation.

The error distribution of the relative errors, for each tool, is presented as a box plot in Figure 3. Statistical indicators are also given in Table 3. We also give, for each tool, its Kendall's tau indicator [16]: this indicator, used to evaluate e.g., uiCA [3] and Palmed [8], measures how well the pair-wise ordering of benchmarks is preserved, -1 being a full anti-correlation and 1 a full correlation. This is especially useful when one is not interested in a program's absolute throughput, but rather in comparing which program has a better throughput. Finally, as the boxplots and statistical indicators presented are unable to account for the sign of the relative error made by tools in each case, we also present in Figure 5 histograms of the error distribution for each tool. A positive error means that the tool predicted more cycles per iteration than our measure, while a negative error means a prediction faster than reality. In practice, most errors are under-approximations (i.e., optimistic); those are often hinting towards a missed bottleneck.

These results are, overall, significantly worse than what each tool's article presents. We attribute this difference mostly to the specificities of Polybench: composed of computation kernels, it intrinsically stresses the CPU more than basic blocks extracted out of the Spec benchmark suite. This difference is clearly reflected in the experimental section of the Palmed article [8]: the accuracy of most tools is worse on Polybench than on Spec, often by more than a factor of two.

As BHive and Ithemal do not support control flow instructions (e.g., jump instructions), those had to be removed from the blocks before analysis. While none of these tools, apart from Gus—which is dynamic—, is able to account for branching costs, these two analyzers were also unable to account for the front- and backend cost of the control flow instructions themselves as well—corresponding to the $TP_U$ mode introduced by uiCA [3], while others measure $TP_L$.
<figure><img src="image_14.png" /><figcaption>Fig. 5. Relative error distribution of each tool, sign preserved (trimmed for $x > 300$).</figcaption></figure>

## 4.3 CesASMe: Impact of Dependency-boundness

An overview of the full results table (available in our artifact) suggests that on a significant number of rows, the static tools—thus leaving Gus and BHive apart—, excepted Ithemal, often yield comparatively bad throughput predictions together. To confirm this observation, we look at the 30 % worst benchmarks—in terms of MAPE relative to perf—for llvm-mca, uiCA and IACA—yielding 1,050 rows each. All of these share 869 rows (82.8 %), which we call jointly bad rows. In the overwhelming majority (97.5 %) of those jointly bad rows, the tools predicted fewer cycles than measured, meaning that a bottleneck is either missed or underestimated.

There is no easy way, however, to know for certain which of the 3,500 benchmarks are latency bound: no hardware counter reports this. We investigate this further using Gus's sensitivity analysis: in complement of the “normal” throughput estimation of Gus, we run it a second time, disabling the accounting for latency through memory dependencies. By construction, this second measurement should be either very close to the first one, or significantly below. We then assume a benchmark to be latency bound due to memory-carried dependencies when it is at least 40 % faster when this latency is disabled; there are 1,112 (31.8 %) such benchmarks.

Of the 869 jointly bad rows, 745 (85.7 %) are declared latency bound through memory-carried dependencies by Gus. In Section 4.2, we presented in Figure 3 general statistics on the tools on the full set of benchmarks. We now remove the 1,112 benchmarks flagged as latency bound through memory-carried dependencies by Gus from the dataset, and present in Figure 4 a comparative box plot for the tools under scrutiny, with Kendall's tau coefficient. While the results for llvm-mca, uiCA, and IACA globally improved significantly, the most noticeable improvements are the reduced spread of the results and the Kendall's $\tau$ correlation coefficient's increase.

From this, we argue that detecting memory-carried dependencies is a weak point in current state-of-the-art static analyzers and that their results could be significantly more accurate if improvements are made in this direction. We thus confirm AnICA's case study on a large dataset of benchmarks, stemming from real-world code.

## 4.4 Staticdeps: Dependency Coverage wrt. depsim

In order to assess staticdeps' results, we implemented depsim, a simple dynamic analyzer instrumenting binaries using valgrind.

It reports dependencies between two program counters at runtime. We then refine this information to approximate dependencies (and aliasing) between pointers. Indeed, a dependency from a
PC *p* to a PC *q* implies that a value written to memory at *q* was read from memory at *p*, and thus that one of the pointers used at *p* aliases with one of the pointers used at *q*.

In order to account for the irrelevance of long-distance dependencies, which we pointed out in Section 3.4 earlier, we introduce in *depsim* a notion of *dependency lifetime*. As we do not have access without a heavy runtime slowdown to elapsed cycles in *valgrind*, we define a *timestamp* as the number of instructions executed since the beginning of the program’s execution; we increment this count at each branch instruction to avoid excessive instrumentation slowdown.

We further annotate every write to the shadow memory with the timestamp at which it occurred. Whenever a dependency should be added, we first check that the dependency has not expired—that is, that it is not older than a given threshold. This threshold is tunable for each run—and may be set to infinity to keep every dependency.

Using those dynamically-gathered dependencies, we evaluate two distinct elements.

(1) *staticdeps* takes a new, fresh pointer independent of all the others for every pointer yet unknown. The underlying hypothesis is that no couple of input pointers of the kernel—parameters, pointers read from memory, ...—aliases. This hypothesis is based on the observation that often, compilers prefer using a single base-pointer that is offset whenever memory is accessed, rather than using multiple aliasing pointers. We evaluate the well-foundedness of this hypothesis by conducting a *points-to* analysis on the collected dependencies.

(2) We also evaluate the ability of *staticdeps* to correctly predict that two pointer expressions alias *at a given time*. Independently of whether two pointers *p* and *q* are pointing to the same memory area, the relevance of the analysis is essentially driven by whether it is correctly able to predict a dependency—that is, a given instruction reads a value previously written by another given instruction, in a short enough amount of time.

We use the binaries produced by CesASMe as a dataset, as we already assessed its relevance and contains enough benchmarks to be statistically meaningful. We also already have tooling and basic-block segmentation available for those benchmarks, making the analysis more convenient.

### 4.4.1 Recompiling CesASMe’s Dataset.
In practice, benchmarks from CesASMe are roughly of the following form:

```c
for(int m=0; m < NUM_MEASURES; ++m) {
    measure_start();
    for(int rep=0; rep < NUM_REPEATS; ++rep) {
        for(int i=0; i < BENCHMARK_SIZE; ++i) {
            /* Some kernel, independent of m and rep */
        }
    }
    measure_stop();
}
```

While this is sensible for conducting throughput measures, it also introduces unwanted dependencies. If, for instance, the kernel consists in $A[i] = C \times A[i] + B[i]$, implemented by

```c
loop:
    vmulsd (%rax, %rdi), %xnmid, %xnml
    vaddsd (%rbx, %rdi), %xnml, %xnml
    vmovsd %xnml, (%rax, %rdi)
    add $8, %rdi
    cmp %rdi, %r10
    jne loop
```
an RAW dependency from line 4 to line 2 is reported by `depsim`—although there is no such dependency inherent to the kernel.

However, each iteration of the measure (outer) loop and each iteration of the repeat (inner) loop will read again each A[i] (i.e., (%rax, %rdi) in the assembly) value from the previous inner loop, and write it back. This creates a dependency on the previous iteration of the inner loop, which should in practice be meaningless if `BENCHMARK_SIZE` is large enough. Such dependencies, however, pollute the evaluation results: as `depsim` does not report a dependency’s distance, they are considered meaningful; and as they cannot be detected by `staticdeps`—which is unaware of the outer and inner loop—, they introduce unfairness in the evaluation. The actual loss of precision introduced by not discovering such dependencies is instead assessed later by enriching `uiCA` with `staticdeps`.

To avoid detecting these dependencies with `depsim`, we recompile `CesASMe's benchmarks` from the C source code of each benchmark with `NUM_MEASURES = NUM_REPEATS = 1`. We use these recompiled benchmarks only in the current section. While we do not re-run code transformations from the original Polybenchs, we do recompile the benchmarks from C source. Thus, the results from this Section 4.4 are not comparable with results from other sections, as the compiler may have used different optimizations, instructions, and so on.

### 4.4.2 "Points-to" Aliasing Analysis
A major approximation made by `staticdeps` is to assume that any new encountered pointer does not alias with previously encountered values. If we detect, through dynamic analysis, that a value derived from a pointer a shares a value with one derived from a pointer b, we can deduce that a points-to b, and therefore that taking a fresh value was not representative of the reality.

This part thus evaluates our postulate (1) from Section 3.3.

For each binary generated by `CesASMe`, we use its cached basic block splitting and occurrence count. Among each binary, we discard any basic block with fewer than 10% of the occurrence count of the most-hit basic block; this avoids considering basic blocks which were not originally inside loops, and for which loop-carried dependencies would make no sense—and could possibly create false positives.

For each of the considered binaries, we run our dynamic analysis, `depsim`, and record its results. We use an infinite lifetime, as we want to keep every dependency detected. Dependencies whose source and destination program counters are not in the same basic block are discarded, as `staticdeps` cannot detect them by construction.

We then use a coverage metric to assess whether the dependencies reported by `depsim` are correctly found by `staticdeps`. We define two metrics: the unweighted dependencies coverage,

$$cov_u = \frac{|found|}{|found| + |missed|}$$

as well as the weighted dependencies coverage,

$$cov_w = \frac{\sum_{d \in found} \rho_d}{\sum_{d \in found \cup missed} \rho_d}$$

where $\rho_d$ is the number of occurrences of the dependency d, dynamically detected by `depsim`.

We then use $cov_u$ and $cov_w$ as a proxy to measure whether assuming the pointers independent was reasonable: a bad coverage would be a clear indication of non-independent pointers treated as independent. A good coverage is not, formally, an indication of the absence of non-independent pointers: the detected static dependencies may come from other pointers at the same PC. We however believe it reasonable to consider it a good proxy for this metric, as a single assembly line often reads a single value, and usually at most two.
<table><caption>**Table 4.** *Points-to Analysis Evaluation: Unweighted and Weighted Coverage of staticdeps on CesASMe's Binaries Recompiled without Repetitions, with an Infinite Lifetime*</caption><thead><tr><td>cov<sub>u</sub> (%)</td><td>cov<sub>w</sub> (%)</td></tr></thead><tbody><tr><td>95.0</td><td>93.7</td></tr></tbody></table>

<table><caption>**Table 5.** *Dependency Coverage Evaluation: Periodic, Unweighted and Weighted Coverage of staticdeps on CesASMe's Binaries Recompiled without Repetitions, with a Lifetime of 512*</caption><thead><tr><td>cov<sub>p</sub> (%)</td><td>cov<sub>u</sub> (%)</td><td>cov<sub>w</sub> (%)</td></tr></thead><tbody><tr><td>96.0</td><td>94.4</td><td>98.3</td></tr></tbody></table>

The results of this analysis for the 3500 binaries of CesASMe are presented in Table 4. The very high coverage rate gives us good confidence that our hypothesis of independent pointers is reasonable, at least within the scope of Polybench, which we believe representative of scientific computation—one of the prominent use-cases of tools such as code analyzers.

#### 4.4.3 Dependency Coverage.
The same general methodology can also be used to evaluate whether staticdeps correctly predicts dependencies, evaluating our postulate (2) from Section 3.3.

We run again our dynamic analysis, *depsim*, and record its results. We use a lifetime of 512 instructions for this analysis, as this is roughly the size of recent Intel reorder buffers [31]; as discussed in Section 3.4, dependencies spanning farther than the size of the ROB are not microarchitecturally relevant. As we did previously did, we discard dependencies whose source and destination program counters are not in the same basic block, as *staticdeps* cannot detect them by construction.

For each of the considered basic blocks, we run our static analysis, *staticdeps*. We discard the Δk parameter—how many loop iterations the dependency spans—, as our dynamic analysis does not report an equivalent parameter, but only a pair of program counters.

This time, dynamic dependencies from *depsim* are converted to *periodic dependencies* in the sense of *staticdeps* as described in Section 3.5: only dependencies occurring on at least 80% of the block's iterations are kept—else, dependencies are considered measurement artifacts. The *periodic coverage* of *staticdereps* dependencies for this basic block *wrt*. *depsim*,

$$cov_p = \frac{|\text{found}|}{|\text{found}| + |\text{missed}|}$$

is defined exactly as $cov_u$, but uses these periodic dependencies instead of raw dependencies.

We also keep the raw dependencies from *depsim*—that is, without converting them to periodic dependencies—to also evaluate $cov_u$ and $cov_w$.

These metrics are presented in Table 5. The obtained coverage is consistent between the three metrics used ($cov_p$, $cov_u$, $cov_w$) and the reported coverage is very close to 100%, giving us good confidence on the accuracy of *staticdereps*.

## 4.5 Staticdereps: Enriching uiCA's Model

To estimate the real gain in performance debugging scenarios, however, we integrate *staticdereps* into *uiCA*.

There is, however, a discrepancy between the two tools: while *staticdereps* works at the assembly instruction level, *uiCA* works at the μOP level. In real hardware, dependencies indeed occur between μOPs; however, we are not aware of the existence of a μOP-level semantic description of the x86-64 ISA, which made this level of detail unsuitable for the *staticdereps* analysis.

We bridge this gap in a conservative way: whenever two instructions $i_1, i_2$ are found to be dependent, we add a dependency between each couple $\mu_1 \in i_1, \mu_2 \in i_2$. This approximation is thus pessimistic, and should predict execution times biased towards a slower computation kernel. A finer model, or a finer (conservative) filtering of which μOPs must be considered dependent—e.g., a
<table><caption>Table 6. Evaluation through CesASMe of the Integration of staticdeps to uiCA</caption><thead><tr><th>Dataset</th><th>Bencher</th><th>Datapoints</th><th>MAPE</th><th>Median</th><th>Q1</th><th>Q3</th><th>K<sub>T</sub></th></tr></thead><tbody><tr><td rowspan="2">Full</td><td>uiCA</td><td>3500</td><td>29.59 %</td><td>18.26 %</td><td>7.11 %</td><td>52.99 %</td><td>0.58</td></tr><tr><td>+ staticdeps</td><td>3500</td><td>19.15 %</td><td>14.44 %</td><td>5.86 %</td><td>23.96 %</td><td>0.81</td></tr><tr><td rowspan="2">Pruned</td><td>uiCA</td><td>2388</td><td>18.42 %</td><td>11.96 %</td><td>5.42 %</td><td>23.32 %</td><td>0.80</td></tr><tr><td>+ staticdeps</td><td>2388</td><td>18.77 %</td><td>12.18 %</td><td>5.31 %</td><td>23.55 %</td><td>0.80</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>Fig. 6. Statistical distribution of relative errors of uiCA, with and without staticdeps hints, with and without pruning latency bound through memory-carried dependencies rows.</figcaption></figure>

memory dependency can only come from a memory-related µOP—may enhance the accuracy of our integration.

We then evaluate our gains by running CesASMe's harness by running both uiCA and uiCA + staticdeps, as we did in Section 4.3, on two datasets: first, the full set of 3500 binaries from CesASMe; then, the set of binaries pruned to exclude benchmarks heavily relying on memory-carried dependencies introduced in Section 4.3. We do not use the kernels recompiled in Section 4.4 above, but the original kernels compiled from our first CesASMe run. If staticdeps is beneficial to uiCA, we expect uiCA + staticdeps to yield significantly better results than uiCA alone on the first dataset. On the second dataset, however, staticdeps should provide no significant contribution, as the dataset was pruned to not exhibit significant memory-carried latency-boundness. We present these results in Table 6, as well as the corresponding box-plots in Figure 6.

We deduce two things from this experiment.

First, the full dataset uiCA + staticdeps row is extremely close, on every metric, to the pruned, uiCA-only row. On this basis, we argue that staticdeps' addition to uiCA is very conclusive: the hints provided by staticdeps are sufficient to make uiCA's results as good on the full dataset as they were before on a dataset pruned of precisely the kind of dependencies we aim to detect. Thus, at least on workloads similar to Polybench, staticdeps is able to resolve the issue of memory-carried dependencies for uiCA's throughput analysis.

Furthermore, uiCA and uiCA + staticdeps' results on the pruned dataset are extremely close. From this, we argue that staticdeps does not introduce false positives when no dependency should be found; its addition to uiCA does not negatively impact its accuracy whenever it is not relevant.

## Availability of code and data

The raw data resulting from CesASMe experiments can be found in the artifact related to the present article. The tools developed for this article (CesASMe and its dependencies, staticdeps, uiCA + staticdeps, ...) are available under free software licences.
## 5 Conclusion

In this article, we have presented the new heuristic-based analyzer, staticdeps, for statically identifying memory-carried dependencies of a binary basic block. We have shown that it can be used to beneficially extend state-of-the-art code analyzers, such as uica. In order to provide sound baselines for evaluating such extensions, we also have introduced the evaluation framework CesASMe, which is meant to compose measurement environments and code analyzers and make their results commensurable. In order to take into account the impact of a basic block's context on its measured throughput, the method we propose consists in reasoning at kernel-level by lifting the basic block-level predictions. Finally, CesASMe has allowed us to exhibit a significant gain in accuracy, thanks to staticdeps, on latency-bound microbenchmarks generated from the HPC-native Polybench benchmark suite.

As code analyzers work at the basic block scope, we centered our lifting methodology on basic blocks. We believe, however, that future works could improve its accuracy in the presence of complex control flow by counting the occurrences of paths within one loop iteration instead of occurrences of blocks. This would, however, require cycles prediction at the scale of paths.

## References

[1] Andreas Abel and Jan Reineke. 2020. nanoBench: A low-overhead tool for running microbenchmarks on x86 systems. In *2020 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)*. 34–46. DOI: https://doi.org/10.1109/ISPASS48437.2020.00014

[2] Andreas Abel and Jan Reineke. 2019. uops.info: Characterizing latency, throughput, and port usage of instructions on intel microarchitectures. In *Proceedings of the ASPLOS (ASPLOS '19)*. ACM, New York, NY, USA, 673–686. DOI: https://doi.org/10.1145/3297858.3304062

[3] Andreas Abel and Jan Reineke. 2022. UiCA: Accurate throughput prediction of basic blocks on recent intel microarchitectures. In *Proceedings of the 36th ACM International Conference on Supercomputing (ICS '22)*. Association for Computing Machinery, New York, NY, USA, Article 33, 14 pages. DOI: https://doi.org/10.1145/3524059.3532396

[4] AMD 2023. AMD64 Architecture Programmer's Manual, Volume 2. AMD.

[5] Daniel Balouek, Alexandra Carpen Amarie, Ghislain Charrier, Frédéric Desprez, Emmanuel Jeannot, Emmanuel Jeanvoine, Adrien Lèbre, David Margery, Nicolas Niclausse, Lucas Nussbaum, et al. 2013. Adding virtualization capabilities to the Grid'5000 testbed. In *Cloud Computing and Services Science*. Ivan I. Ivanov, Marten van Sinderen, Frank Leymann, and Tony Shan (Eds.), Communications in Computer and Information Science, Vol. 367, Springer International Publishing, 3–20. DOI: https://doi.org/10.1007/978-3-319-04519-1_1

[6] Uday Bondhugula, J. Ramanujam, and P. Sadayappan. 2007. PLuTo: A Practical and Fully Automatic Polyhedral Parallelizer and Locality Optimizer. Technical Report OSU-CISRC-10/07-TR70. The Ohio State University.

[7] Yishen Chen, Ajay Brahmakshatriya, Charith Mendis, Alex Renda, Eric Atkinson, Ondřej Sýkora, Saman Amarasinghe, and Michael Carbin. 2019. BHive: A benchmark suite and measurement framework for validating x86-64 basic block performance models. In *Proceedings of the 2019 IEEE International Symposium on Workload Characterization (IISWC'19)*. 167–177. DOI: https://doi.org/10.1109/IISWC47752.2019.9042166

[8] Nicolas Derumigny, Théophile Bastian, Fabian Gruber, Guillaume Iooss, Christophe Guillon, Louis-Noël Pouchet, and Fabrice Rastello. 2022. PALMED: Throughput characterization for superscalar architectures. In *Proceedings of the 2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO'22)*. 106–117. DOI: https://doi.org/10.1109/CGO53902.2022.9741289

[9] Novillo Diego. 2007. Memory SSA-a unified approach for sparsely representing memory operations. In *Proceedings of the GCC Developers' Summit*. Citeseer, 97-110 pages.

[10] Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. 1994. Context-sensitive interprocedural points-to analysis in the presence of function pointers. *ACM SIGPLAN Notices* 29, 6 (1994), 242–256. DOI: https://doi.org/10.1145/773473.178264

[11] Fabian Gruber. 2019. Performance Debugging Toolbox for Binaries: Sensitivity Analysis and Dependence Profiling. Ph. D. Dissertation. Université Grenoble Alpes. Retrieved from http://www.theses.fr/2019GREAM071 2019GREAM071

[12] Yuxin Guo, Alex W. Chadwick, Márton Erdős, Utpal Bora, Ilias Vougioukas, Giacomo Gabrielli, and Timothy M. Jones. 2024. OptiWISE: Combining sampling and instrumentation for granular CPI analysis. In *Proceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO'24)*. 373–385. DOI: https://doi.org/10.1109/CGO57630.2024.10444771
[13] A. S. Huang, G. Slavenburg, and J. P. Shen. 1994. Speculative disambiguation: A compilation technique for dynamic memory disambiguation. *SIGARCH Computer Architecture News* 22, 2 (1994), 200–210. DOI: https://doi.org/10.1145/192007.192012

[14] Intel Corporation. 2012. Intel Architecture Code Analyzer (IACA). Retrieved May 02, 2020 from https://software.intel.com/en-us/articles/intel-architecture-code-analyzer/

[15] Intel Corporation 2023. *Intel® 64 and IA-32 Architectures Software Developer's Manual, Volume 1*. Intel Corporation.

[16] Maurice G. Kendall. 1938. A new measure of rank correlation. *Biometrika* 30, 1/2 (1938), 81–93.

[17] Jan Laukemann, Julian Hammer, Georg Hager, and Gerhard Wellein. 2019. Automatic throughput and critical path analysis of x86 and ARM assembly kernels. In *Proceedings of the 2019 IEEE/ACM Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS'19)*. 1–6. DOI: https://doi.org/10.1109/PMBS49563.2019.00006

[18] Linux Kernel. 2025. perf: Linux Profiling with Performance Counters. Retrieved February 15, 2025 from http://perf.wiki.kernel.org/index.php/Main_Page

[19] Charith Mendis, Alex Renda, Saman Amarasinghe, and Michael Carbin. 2019. Ithemal: Accurate, portable and fast basic block throughput estimation using deep neural networks. (2019), 4505–4515. https://proceedings.mlr.press/v97/mendis19a.html

[20] Nicholas Nethercote and Julian Seward. 2003. Valgrind: A program supervision framework. *Electronic Notes in Theoretical Computer Science* 89, 2 (2003), 44–66.

[21] Nicholas Nethercote and Julian Seward. 2007. Valgrind: A framework for heavyweight dynamic binary instrumentation. In *Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07)*. Association for Computing Machinery, New York, NY, USA, 89–100. DOI: https://doi.org/10.1145/1250734.1250746

[22] Arthur Perais and André Seznec. 2014. Practical data value speculation for future high-end processors. In *Proceedings of the 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA'14)*. 428–439. DOI: https://doi.org/10.1109/HPCA.2014.6835952

[23] PoCC. 2025. PoCC, the Polyhedral Compiler Collection. Retrieved February 15, 2025 from https://www.cs.colostate.edu/~pouchet/software/pocc/

[24] Louis-Noël Pouchet and Tomofumi Yuki. 2016. PolyBench/C: The Polyhedral Benchmark Suite, Version 4.2. Retrieved from http://polybench.sf.net

[25] Nguyen Anh Quynh and the Capstone collaborators. 2025. Capstone Engine. Retrieved February 15, 2025 from https://www.capstone-engine.org/

[26] Fabian Ritter and Sebastian Hack. 2022. AnICA: Analyzing inconsistencies in microarchitectural code analyzers. In *Proceedings of the ACM on Programming Languages* 6, OOPSLA2, Article 125 (2022), 29 pages. DOI: https://doi.org/10.1145/3563288

[27] S. Sethumadhavan, R. Desikan, D. Burger, C. R. Moore, and S. W. Keckler. 2003. Scalable hardware memory disambiguation for high ILP processors. In *Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture*, 2003. MICRO'36, 399–410. DOI: https://doi.org/10.1109/MICRO.2003.1253244

[28] Rami Sheikh, Harold W. Cain, and Raguram Damodaran. 2017. Load value prediction via path-based address prediction: Avoiding mispredictions due to conflicting stores. In *Proceedings of the 2017 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'17)*. 423–435.

[29] Sony Corporation and LLVM Project. 2025. LLVM Machine Code Analyzer. Retrieved February 15, 2025 from https://llvm.org/docs/CommandGuide/llvm-mca.html

[30] R. M. Tomasulo. 1967. An efficient algorithm for exploiting multiple arithmetic units. *IBM Journal of Research and Development* 11, 1 (1967), 25–33. DOI: https://doi.org/10.1147/rd.111.0025

[31] WikiChip. 2021. Intel Details Golden Cove: Next-Generation Big Core For Client and Server SoCs. Retrieved February 15, 2025 from https://fuse.wikichip.org/news/6111/intel-details-golden-cove-next-generation-big-core-for-client-and-server-socs/

# Appendix

## A Formal Proof of Remark 1 (Section 3.4)

To prove this assertion, we require a few postulates describing the functioning of a CPU and, in particular, how $\mu$OPs transit in (decoded) and out (retired) the reorder buffer.

POSTULATE 1 (REORDER BUFFER AS A CIRCULAR BUFFER). *The reorder buffer is a circular buffer of size $R \in \mathbb{N}^+$. It contains only decoded $\mu$OPs. Let us denote $i_d$ the $\mu$OP at position $d$ in the reorder buffer.*
Assume $i_d$ just got decoded. We have that for every $q$ and $q'$ in $[0, R)$:

$$ (q - d - 1)\%R < (q' - d - 1)\%R \iff i_q \text{ was decoded before } i_{q'} $$

If a μOP has not been retired yet (issued and executed), it cannot be replaced in the ROB by any freshly decoded instruction. In other words, every non-retired decoded μOP—also called in-flight—remains in the reorder buffer. This is possible thanks to the notion of full reorder buffer:

**POSTULATE 2 (FULL REORDER BUFFER).** Let us denote by $i_d$ the μOP that just got decoded. The reorder buffer is said to be full if for $q = (d + 1)\%R$, μOP $i_q$ is not retired yet.

*If the reorder buffer is full, then instruction decoding is stalled.*

Let $(I_p)_{0 \le p < n}$ be a trace of executed instructions. Each of these instructions are iteratively decoded, issued, and retired. We will also denote by $(i_q)_{0 \le q < m}$ the trace of decoded μOPs. To prove the theorem above, we need to state that any two in-flight μOPs are distant of at most $R$ μOPs.

For any instruction $I_p$, we denote as $Q_p$ the range of indices such that $(i_q)_{q \in Q_p}$ are the μOPs obtained from the decoding of $I_p$.

Note that in practice, we may not have $\cup_p Q_p = [0, n)$, as e.g., branch mispredictions may introduce unwanted μOPs in the pipeline. However, as the worst case for the lemma below occurs when no such “spurious” μOPs are present, we may safely ignore such occurrences.

**LEMMA 1 (DISTANCE OF IN-FLIGHT μOPs).** For any pair of instructions $(I_p, I_{p'})$, and two corresponding μOPs $(i_q, i_{q'})$ such that $q \in Q_p, q' \in Q_{p'}$,

$$ \text{inflight}(i_q) \wedge \text{inflight}(i_{q'}) \implies \text{distance}(I_p, I_{p'}) < R - 1 $$

**PROOF.** The sets ($Q_p$) are disjoint pairwise, and for any pair of instructions $(I_p, I_{p'})$, and any two corresponding μOPs, $(i_q, i_{q'})$ such that $q \in Q_p, q' \in Q_{p'}$, $p < p' \implies q < q'$.

Thus, distance $(I_p, I_{p'}) < |q' - q|$.

Observe that at any time, the content of the ROB can be seen as a window of length at most $R$ over $(i_q)_{0 \le q < m}$. Consequently, if both $i_q$ and $i_{q'}$ are in-flight then $|q' - q| < R$, and thus distance $(I_p, I_{p'}) < R - 1$. □

**POSTULATE 3 (ISSUE DELAY).** Reasons why the issue of a μOP *i* is delayed can be:

(1) *i* is not yet in the reorder buffer;

(2) *i* depends on μOP *i'* which is not retired yet;

(3) *ports on which i can be mapped are all occupied.*

**PROOF OF LONG DISTANCE DEPENDENCIES THEOREM.** The theorem above is now a direct consequence of the previous observations. Let us consider two μOPs, *i* and *i'*, respectively introduced by instructions $I_p$ and $I_q$. Assume a delayed issue for μOP *i* where the unique cause is a dependence from μOP *i'*, that is:

(1) *i* is already in the reorder buffer;

(2) *i* depends on μOP *i'* which is not retired yet;

(3) at least one port on which *i* can be mapped is available.

Since *i'* is not retired yet and *i'* is “before” *i*, *i'* is still in the reorder buffer, i.e., both *i* and *i'* are in the reorder buffer.

By the previous lemma, we have distance $(I_p, I_q) < R - 1$.

By contrapositive, for any two instructions $I_a, I_b$ such that distance $(I_a, I_b) \ge R - 1$, no μOP of $I_b$ may have its execution delayed by a dependency between $I_a$ and $I_b$. □