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 in today’s environment of rapid innovation in GPUs, TPUs, and other entertaining platforms. One of my research group’s major goals is to create technologies that enable self-improving compilers. Taking humans out of the compiler-improvement loop will make this process o ..read more

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 is just a convenient way to specify a register filled with ones. Following a De Morgan law, a peephole optimization could rewrite this sequence as: r0 = or r8, r9 r0 = xor r0, -1 But modern compilers don’t use RTL as their primary intermediate representation (IR), they’re more li ..read more

[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 translates IR into assembly language. My group and our collaborators have spent a lot of time finding and reporting defects in the LLVM compiler’s middle end optimizers using Alive2, a formal methods tool that we created. This piece is about extending that ..read more

[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 them by flipping a few bits or something, and feed the resulting mutants into our fuzzing target and wait for it to crash or otherwise malfunction. To exploit this idea for fuzzing LLVM optimization passes, we can plug existing LLVM IR files such as those found in LLVM’s unit ..read more

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). As the name implies, attempts to acquire a locked spinlock simply spin: they burn CPU time. Thus, we don’t want to hold spinlocks for long and we certainly don’t want to be preempted while holding one. In the old days, people came ..read more

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 fuzzing campaigns. llvm-reduce is a newish tool for reducing LLVM IR. Structurally, it is similar to C-Reduce, using a reducer core that calls out to a modular collection of reduction passes. Each pass implements a potentially-reducing transformat ..read more

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 worth pursuing on its own. Several factors have contributed: The amount of software in use has grown massively, and presumably the number of latent bugs has grown with it. Since software is increasingly used to monitor and control aspects of our lives, and because systems ..read more

[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 can always safely substitute add for shift, or shift for add. If we compile them to LLVM IR with optimizations enabled, LLVM will canonicalize both functions to the version containing the shift operator. Although it might seem that this choice is an arbitrary one, it turns out there is a very real dif ..read more

Years ago my friend Derek heard that the Jarbidge Wilderness — a remote, mountainous area along the Idaho-Nevada border — is one of the least-visited wilderness areas in the USA, and we’ve wanted to visit since then. There’s little good information about this area online, but a book I had sitting around listed The Gods Pocket Peak Trail, and we hoped to connect up to some other routes in the area to make a loop. The trailhead for this route is above 9000 feet, but then the trail immediately drops a thousand feet, climbs a thousand feet, and sort of keeps on doing this. The views and microclima ..read more

Last fall my friend Brian and I went on a short backpacking trip in the San Rafael Swell. We left SLC early, drove to Ferron Utah, and then followed a high-clearance dirt road to the rim of North Salt Wash, a wide canyon that feeds the San Rafael River. We dropped into this open canyon using an old road and then a foot trail: There’s an extensive area of rock art near where we reached the canyon floor, some of it fairly fresh-looking (so probably less than 1,000 years old): We particularly enjoyed the turtle. Other petroglyphs in the area are faded, meaning they are most likely much older ..read more