# Embedded in Academia John Regehr, Professor of Computer Science, University of Utah, USA This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## Looking for Missed Alarm Bugs in a Formal Verification Tool DevFeed: [Looking for Missed Alarm Bugs in a Formal Verification Tool]() Original publisher: [Read original article]() Author: regehr Published: 2024-09-04T18:29:03Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [Formal verification](), [LLVM](), [Compiler](), [Testing](), [C](), [C++](), [undefined\_behavior]() Tags: [bugs](), [c](), [c-plus-plus](), [compiler](), [formal-verification](), [llvm](), [testing](), [uncategorized](), [undefined-behavior](), [verification]() ### AI overview This co-authored article explains how formal verification tools themselves require rigorous engineering and testing. It describes testing Alive2, a translation validation tool for LLVM optimizations, including the challenge of finding missed-alarm bugs and the use of randomized program generation with YARPGen. ### Source excerpt [This piece is co-authored with Vsevolod Livinskii.] Formal verification isn't some sort of magic pixie dust that we sprinkle over a computer system to make it better. Real formal verification involves a lot of the same kind of difficult, nasty, grungy engineering work that any other systems-level job involves. Furthermore, the verification tools themselves are [...] ## Dataflow Analyses and Compiler Optimizations that Use Them, for Free DevFeed: [Dataflow Analyses and Compiler Optimizations that Use Them, for Free]() Original publisher: [Read original article]() Author: regehr Published: 2024-04-20T21:55:33Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [Compiler](), [Optimization](), [Parser](), [LLVM](), [gcc]() Tags: [analysis](), [benchmark](), [compiler](), [compiler-optimization](), [gcc](), [llvm](), [uncategorized]() ### AI overview The article discusses slow compiler evolution and proposes a self-improving compiler loop based on superoptimization, generalization, and benchmark suites. It then considers extending the approach to dataflow analyses, including integer range analysis and known-bits analysis used by optimizing compilers. ### Source excerpt Compilers can be improved over time, but this is a slow process. "Proebsting's Law" is an old joke which suggested that advances in compiler optimization will double the speed of a computation every 18 years -- but if anything this is optimistic. Slow compiler evolution is never a good thing, but this is particularly problematic [...] ## Why Do Peephole Optimizations Work? DevFeed: [Why Do Peephole Optimizations Work?]() Original publisher: [Read original article]() Author: regehr Published: 2023-11-01T16:23:20Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [Optimization](), [compilers](), [LLVM](), [Code]() Tags: [code](), [compilers](), [execution](), [llvm](), [optimization](), [reduce](), [uncategorized]() ### AI overview The article explains why peephole optimizations work in modern compilers. It contrasts local instruction rewrites with transformations over SSA-based intermediate representations and discusses correctness in terms of observable behavior and refinement. ### Source excerpt In its original form, a peephole optimization applied to a collection of instructions located close together in a program. For example, in a register transfer language we might find this sequence of instructions: r0 = xor r8, -1 r1 = xor r9, -1 r0 = and r0, r1 Here, assuming the two's complement representation, -1 [...] ## Formal-Methods-Based Bugfinding for LLVM's AArch64 Backend DevFeed: [Formal-Methods-Based Bugfinding for LLVM's AArch64 Backend]() Original publisher: [Read original article]() Author: regehr Published: 2022-06-06T14:58:02Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [Formal methods](), [LLVM](), [Compiler](), [backends](), [Assembly]() Tags: [assembly](), [backend](), [compiler](), [compilers](), [computer-science](), [formal-methods](), [frontend](), [llvm](), [optimization](), [software-correctness]() ### AI overview The article explains how Alive2, a formal methods tool, is extended to validate LLVM's AArch64 backend. The approach lifts compiled AArch64 code into Alive2 IR and checks whether the lifted code refines the original LLVM code, helping identify backend correctness violations. ### Source excerpt [This piece is co-authored by Ryan Berger and Stefan Mada (both Utah CS undergrads), by Nader Boushehri, and by John Regehr.] An optimizing compiler traditionally has three main parts: a frontend that translates a source language into an intermediate representation (IR), a "middle end" that rewrites IR into better IR, and then a backend that [...] ## High-Throughput, Formal-Methods-Assisted Fuzzing for LLVM DevFeed: [High-Throughput, Formal-Methods-Assisted Fuzzing for LLVM]() Original publisher: [Read original article]() Author: regehr Published: 2022-05-31T14:56:41Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [Fuzzing/Fuzz testing](), [LLVM](), [Formal methods](), [Testing](), [bug]() Tags: [bug](), [formal-methods](), [fuzzing](), [llvm](), [mutation](), [testing](), [uncategorized]() ### AI overview The article describes mutation-based fuzzing for LLVM optimization passes, combining a custom LLVM IR mutator with the formal methods tool Alive2 to check whether optimizations are correct or buggy. The authors report that generic mutation with radamsa produced mostly invalid or semantically unchanged tests and found no bugs after several days, motivating a structure-aware mutator that preserves LLVM IR invariants. ### Source excerpt [This piece is coauthored by Yuyou Fan and John Regehr] Mutation-based fuzzing is based on the idea that new, bug-triggering inputs can often be created by randomly modifying existing, non-bug-triggering inputs. For example, if we wanted to find bugs in a PDF reader, we could grab a bunch of PDF files off the web, mutate [...] ## A Close Look at a Spinlock DevFeed: [A Close Look at a Spinlock]() Original publisher: [Read original article]() Author: regehr Published: 2021-11-06T19:57:06Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [Concurrency](), [Concurrent Programming](), [Operating system](), [Algorithms](), [Code](), [Hardware](), [x86]() Tags: [algorithms](), [architecture](), [code](), [gcc](), [hardware](), [implementation](), [processor](), [synchronization](), [threads](), [uncategorized](), [x86]() ### AI overview This article explains how spinlocks provide mutual exclusion on multiprocessor systems. It covers why naive load-and-store implementations can fail on modern weak-memory architectures, how GCC atomic intrinsics can implement a portable user-mode spinlock, and how FIFO spinlocks can improve fairness under contention. ### Source excerpt The spinlock is the most basic mutual exclusion primitive provided by a multiprocessor operating system. Spinlocks need to protect against preemption on the current CPU (typically by disabling interrupts, but we'll ignore that aspect in this post) and also against attempts by other cores to concurrently access the critical section (by using atomic memory operations). [...] ## llvm-reduce DevFeed: [llvm-reduce]() Original publisher: [Read original article]() Author: regehr Published: 2021-05-13T16:58:00Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [LLVM](), [compilers](), [debugging]() Tags: [automated](), [compilers](), [debugging](), [fuzzing](), [llvm](), [uncategorized]() ### AI overview This article explains llvm-reduce, an LLVM tool for automatically reducing LLVM IR test cases. It describes its modular reduction passes, interestingness tests, LLVM-specific transformations, compatibility with C-Reduce, and inclusion in LLVM. ### Source excerpt Test-case reduction is more or less a necessity when debugging failures of complex programs such as compilers. Automated test-case reduction is useful not only because it allows developers to avoid wasting time reducing inputs by hand, but also because it supports new techniques such as automatically triaging bulk failures seen in the field or during [...] ## Responsible and Effective Bugfinding DevFeed: [Responsible and Effective Bugfinding]() Original publisher: [Read original article]() Author: regehr Published: 2020-08-17T18:36:43Z Content type: article Language: en Sources: [Embedded in Academia]() Topics: [bug](), [Software](), [Open Source]() Tags: [article](), [bug](), [computer-science](), [defects](), [report](), [software-correctness]() ### AI overview The article explains how to conduct external bug-finding efforts so they maximize overall benefit. It argues that bug finders should work carefully and collaboratively with software developers instead of overwhelming projects with large numbers of reports. ### Source excerpt NB: This piece is not about responsible disclosure of security issues. For almost as long as people have written code, we have also worked to create methods for finding software defects. Much more recently, it has become common to treat "external bug finding" -- looking for defects in other people's software -- as an activity [...] ## Alive2 Part 3: Things You Can and Can't Do with Undef in LLVM DevFeed: [Alive2 Part 3: Things You Can and Can't Do with Undef in LLVM]() Original publisher: [Read original article]() Author: regehr Published: 2020-07-31T20:33:05Z Content type: tutorial Language: en Sources: [Embedded in Academia]() Topics: [LLVM](), [Compiler](), [C](), [C++](), [functions]() Tags: [c](), [c-plus-plus](), [compiler](), [compilers](), [computer-science](), [functions](), [llvm](), [software-correctness](), [transformation](), [undef]() ### AI overview This article explains how LLVM handles undef and poison values and why they complicate compiler transformations. It uses equivalent C and C++ functions to show that LLVM can replace addition with a shift under refinement, but cannot generally reverse that transformation. ### Source excerpt [Also see Part 1 and Part 2 in this series.] Let's talk about these functions: unsigned add(unsigned x) { return x + x; } unsigned shift(unsigned x) { return x << 1; } From the point of view of the C and C++ abstract machines, their behavior is equivalent: in a program you're writing, you [...]