Compiler Design Lab

AnICA: Analyzing Inconsistencies in Microarchitectural Code Analyzers

This website accompanies our OOSPLA'22 paper (a preprint is available on arxiv.org). Have a look at the source code on GitHub to see our prototype implementation, or check out the artifact.

TL;DR

AnICA is an approach to systematically test microarchitectural code analyzers like llvm-mca, IACA, uiCA, OSACA, and Ithemal. AnICA compares the tools with each other or with microbenchmarks on hardware to find basic blocks for which the tools provide inconsistent throughput predictions. The found inconsistencies are generalized into abstract basic blocks, to offer a more useful and succinct problem descriptions.

What is the problem?

Basic block throughput prediction in microarchitectural code analyzers is an under-specified problem that the existing tools try to solve with a variety of different assumptions and performance models. It is very common to see such tools predict substantially different throughputs for the same basic block running on the same microarchitecture.

What We Propose: Differential Testing and Abstracting Interesting Basic Blocks

Randomized differential testing is a well-established tool for identifying inconsistencies in a group of tools that are intended to do the same task. On its own, the results of differential testing in this setting would however be of very limited use, since it would uncover large numbers of potentially very similar inputs that require extensive manual inspection. For this reason, AnICA uses techniques from Abstract Interpretation to systematically generalize identified inconsistencies into concise descriptions.

The results are abstract basic blocks like the following, which characterizes an error in llvm-mca (and therefore also LLVM's scheduling model) for AMD's Zen, Zen+, and Zen2 microarchitectures present up to LLVM version 14:

Abstract Instructions:
0
  • mnemonic: 'BSF' + at most 1 edits
  • opschemes: {W:GPR:64}
Abstract Aliasing:
Operand 1 of instruction 1 and operand 2 of instruction 2 must not alias

This abstract basic block describes the set of all basic blocks consisting of a single bitscan instruction (BSR or BSF) operating on general purpose registers that does not form a dependency chain with itself. We can conclude from this description that, while the latency of the instruction is modeled correctly, the use of execution units in the processor is not.

AnICA comes with a rich browser-based user interface to inspect discovered inconsistencies. For a glance at what it looks like, see this static demo (use the "Open Docs" button in the top right to get an explanation of the information presented each sub page). To explore our entire evaluation results or your own AnICA campaigns, you will need to host the AnICA UI locally on your machine, e.g., via our artifact.

Check out our paper to find several case studies where we use AnICA to find modeling bugs and regressions from one tool version to the next, to understand differing modeling assumptions, and to identify underrepresented constructs in the training sets of learned predictors.

Publication

Conferences

People