Adrian Sampson

Back to the Building Blocks’ Building Blocks

2026-05-26T00:00:00+00:00

If there are hardware engineers who love Verilog, I haven’t met them. Almost universally, the attitude toward Verilog seems to be that it’s frustrating, ridiculous, error-prone, and the only pragmatic choice.

Verilog is inescapable because it is the input format to essentially every EDA tool. Its centrality means that it is a de facto intermediate representation implementing for every other HDL: even if you prefer Bluespec, Chisel, Amaranth, or Spade, they usually compile to Verilog to interact with the rest of the hardware world.¹

I am worried that Verilog’s flaws will be the cause of a new wave of hardware bugs. There is an analogy to the problems with C and C++: as designing custom hardware becomes more popular, we risk allowing a dangerous HDL to proliferate and fester in the same way that memory-unsafe programming languages have in software.

I don’t know yet what the analog of memory safety is for hardware bugs, or even if there will be a single dominant defect category. Footguns abound in Verilog, though, so there are many good candidates. This post makes the case that we should invest in better understanding the problems with Verilog so that future HDLs can avoid them.

On Building Blocks

As an American programming languages nerd, I believe that “Back to the Building Blocks” was one of the most exciting developments of the last decade. It’s a 2024 report from the White House Office of the National Cyber Director that makes the case for memory safety. It calls for critical infrastructure to move on from memory-unsafe languages like C and C++, and it even mentions Rust by name as a promising alternative.

“Back to the Building Blocks” didn’t break new ground: by 2024, it was obvious to all reasonable people that memory safety was a huge problem. It was exciting because Joe Biden was saying the same things that we had all been saying for years.² I’m not a very patriotic person, but my heart soars like a majestic bald eagle when I read stuff like this in a government report:

Despite rigorous code reviews as well as other preventive and detective controls, up to 70 percent of security vulnerabilities in memory unsafe languages patched and assigned a CVE designation are due to memory safety issues.

And I can hear the national anthem playing when the report says:

For new products, choosing to build in a memory safe programming language is an early architecture decision that can deliver significant security benefits. Even for existing codebases, where a complete rewrite of code is more challenging, there are still paths toward adopting memory safe programming languages by taking a hybrid approach.

God bless America. “Back to the Building Blocks” distills a hard-to-refute syllogism along these lines:

Correctness matters.
There exist large classes of bugs with similar root causes.
Some languages lead to a higher frequency of these bug classes than other languages.
We should therefore see these bugs as the “fault” of the language, not the programmer.
Languages that are harder to use but dramatically reduce the frequency of these bugs may be worth it.

In the original report, this “Building Blocks” argument was about C. But I believe the same reasoning applies to Verilog.

The Claim (Weak and Strong Forms)

I’ll state my thesis in a weak form and a strong form; you can pick which level you want to consider. The weak form is:

Verilog causes lots of bugs.

And the strong form is:

The next “Building Blocks” crisis will happen in hardware, and it will be Verilog’s fault.

In other words: at the same moment that we’re beginning to get a handle on memory safety, we’re producing a lot more Verilog code. So the next scourge of avoidable bugs could occur in hardware. Better HDLs could dramatically reduce the frequency of these bugs.

Verilog’s problems are not new, but until now, hardware design methodologies have attenuated their harm. The traditional way to develop hardware—the kind of process that big CPU vendors use—mitigates Verilog’s problems in part by expending a ridiculous amount of resources on verification. This observation is hard to justify with concrete evidence, but consider this somewhat dubious report from an industry consortium that claims that, in CPU design projects, the ratio of verification engineers to design engineers is 5:1. A terrible HDL matters less when you have a safety net like that.

But today, more people want to design custom, application-specific hardware. Specialized, lower-volume hardware projects will not (and should not) use the same engineering process as Apple’s next iPhone SoC. The emerging long tail of cheaper, lighter-weight hardware design projects will be more vulnerable to Verilog’s problems.

Some Cheap Shots at Verilog

The main point of this post is to call for systematic study of Verilog’s implications for hardware correctness, not to pick on specific flaws I personally love to hate. But I can’t resist shooting a few fish in this barrel.

The root of Verilog’s problems is that it was not designed for implementing hardware. It was originally developed as a DSL for writing event-based simulators of digital logic. Later, logic synthesis tools repurposed Verilog for generating real netlists. Many problems with Verilog stem from the confusing boundaries between simulation and implementation:

There is an ill-defined “synthesizable” subset. Tools can’t agree on what this subset is, but we can all agree that not all of Verilog can be sensibly translated into hardware.
Verilog requires load-bearing linters. Serious hardware design shops pay for extremely expensive commercial tools that keep their engineers within the Verilog subset that their toolchain can handle.

To get concrete, let’s look at three specific footguns in Verilog: inferred latches, the semantics of the “don’t care” value, and the absence of cycle-level timing information. (As a warning, the latter is a self-serving complaint that motivates some research I co-authored.)

Inferred Latches

Verilog, people say, uses the register-transfer level (RTL) abstraction. If this was the first thing I knew about Verilog, I would assume it works like this: the language has special, built-in constructs for state elements like latches, registers, and memories. You write a Verilog program by describing how to compute the values of all state elements on cycle n+1 based on their values on cycle n. In an RTL language, it seems obvious that all the registers should be explicit and clearly separated from stateless combinational logic.

Because of Verilog’s roots in event-based simulation, that’s not how it works. Instead, variables might be stateful and might be stateless depending on how they are used. For example, here’s one way to write a 32-bit latch in Verilog:

module latch (
  input  wire        en,
  input  wire [31:0] data_in,
  output reg  [31:0] data_out
);
  always @(*) begin
    if (en)
      data_out = data_in;
  end
endmodule

There’s an input data port, an output data port, and a 1-bit enable signal that decides whether the latch should take on a new value. The Verilog semantics say that data_out must be stateful because it is assigned conditionally. That is, because data_out doesn’t get assigned on cycles when en == 0, it keeps its old value—implying that it requires a stateful circuit for its implementation. Verilog engineers call this an “inferred latch.”³

The footgun here is that it’s disturbingly easy to accidentally create a latch. Consider this contrived implementation of an XOR gate:

module funny_xor (
  input   wire [1:0] in_bits,
  output  reg        out
);
  always @(*) begin
    if (in_bits == 2'b00)
      out = 1'b0;
    else if (in_bits == 2'b01)
      out = 1'b1;
    else if (in_bits == 2'b10)
      out = 1'b1;
    else if (in_bits == 2'b11)
      out = 1'b0;
  end
endmodule

This module takes its two inputs on a single 2-bit port, in_bits. This circuit is stateless because our else if cascade covers all the cases: out is assigned in every situation.

But what happens if you forget one of these cases? For example, let’s delete these two lines:

else if (in_bits == 2'b10)
  out = 1'b1;

The module is now stateful, and the hardware implementation requires a latch circuit. Spooky.

Nonsense Semantics for X

HDLs typically need a way to represent don’t-care values, usually written as X. A little like undefined behavior (in a good way), X lets you convey to the optimizer that your specification only covers certain cases, and that it’s free to do what it wants in others.

While X is a good and useful idea, Verilog’s semantics for it don’t make sense. Here’s how it should work: X represents a bit that might be 0 or 1, and we don’t know which.⁴ By that definition, it would make sense that X would propagate through Verilog’s math operators, like this:

module optimism1;
  reg [31:0] in;
  reg [31:0] out;

  initial begin
    in = 32'bx;
    $display("in  = %d", in);

    out = in * 2 + 4;
    $display("out = %d", out);
  end
endmodule

And indeed, simulating this module shows that out is also a don’t care value, just like in:

$ iverilog optimism1.v && ./a.out
in  =          x
out =          x

All is right with the world. Verilog also has a ternary operator, and we can try using X in its condition:

out = (in * 2 + 4) > 42 ? 32'b1 : 32'b0;

Gratefully, the result of an undefined condition is itself X:

$ iverilog optimism2.v && ./a.out
in  =          x
out =          X

Because out might be 1 and it might be 0, it’s sensible that our simulator reports is value is X. Let’s go one step farther and rewrite that ternary operator using the long-form if equivalent:

if ((in * 2 + 4) > 42)
  out = 32'b1;
else
  out = 32'b0;

And try simulating again:

$ iverilog optimism3.v && ./a.out
in  =          x
out =          0

Wat.

This footgun has a name: X-optimism. That’s the standard behavior for Verilog: if treats X as false, which incorrectly makes conditional assignments appear defined when they are actually unknown. Tragically, this behavior was apparently intentional:

This optimistic behavior of if-else was a deliberate decision by Moorby. He realized that in such a procedural context, evaluating both sides of the if-else expression could be enormously complicated. Reducing optimism requires execution time in the simulator.

Feel free to call me a PL nerd for saying this, but I don’t think simulation performance is a good justification for broken semantics.

Unsurprisingly, researchers have explored how X optimism can lead to sneaky security problems because your simulator lies to you about what how final circuit will behave.

Timing Trouble

This last footgun is a little different because it’s the problem we have tried to address in some of our recent research on safer HDLs (and it’s borrowed from that paper). It’s not just a Verilog thing; it’s a danger in every major HDL I know of. It’s also my best guess at this point for a bug category that’s analogous to memory safety problems in software.

Let’s say you already have a multiplier and an adder:

module Mul32 (
  input  wire [31:0] in_a,
  input  wire [31:0] in_b,
  output reg  [31:0] out,
);
  // ...
endmodule

module Add32 (
  input  wire [31:0] in_a,
  input  wire [31:0] in_b,
  output reg  [31:0] out
);
  // ...
endmodule

Suppose you want to combine these two functional units into an ALU that can both add and multiply. We’ll add a one-bit signal, op, that picks which FU to use:

module alu (
  input  wire [31:0] in_a,
  input  wire [31:0] in_b,
  input  wire        op,
  output reg  [31:0] out
);
  wire [31:0] add_out;
  wire [31:0] mul_out;

  Add32 add (.in_a(in_a), .in_b(in_b), .out(add_out));
  Mul32 mul (.in_a(in_a), .in_b(in_b), .out(mul_out));

  always @(*) begin
    out = (op == 1'b0) ? add_out : mul_out;
  end
endmodule

This module instantiates an adder add and a multiplier mul, and it uses Verilog’s ternary operator to multiplex the output based on op.

This implementation works fine if add and mul are both combinational. More realistically, though, a 32-bit multiplier will probably be sequential and pipelined. If that’s the case, this code is probably incorrect: it has implicitly assumed that Add32 and Mul32 have the same timing behavior.

Here’s the problem: there is nothing in the module signatures for the functional units that tells us that’s the case. The interfaces for Add32 and Mul32 are identical because they can only describe the physical shape of the ports, not the timing. Even if Add32 is combinational and Mul32 takes 3 cycles, their Verilog signatures would remain identical. The only way to know how to use a Verilog module correctly is to read the comments (or to look directly at the source code).

If you’re curious about this particular problem, please take a look at our paper about Filament, an HDL with a type system that enforces timing safety.⁵

The Building Blocks’ Building Blocks

If low-level systems like compilers are the building blocks for the software industry, then hardware design tools are the building blocks for the building blocks. The tower of system abstractions needs a strong foundation, and Verilog is a cracked and crumbling concrete slab.

We must work toward a post-Verilog future. We need to invest more in modern HDLs, and we need toolchains that can support these superior languages without going through Verilog as the least common denominator.

Thanks to @whitequark, Amaranth’s maintainer, for pointing out that Amaranth can skip Verilog when targeting Yosys by generating RTLIL directly. Awesome! ↩
I choose to believe that Biden wrote “Back to the Building Blocks” all by himself, and I am not interested in evidence to the contrary. ↩
It would be reasonable to guess that the reg keyword means that data_out is stored in a register. That’s not the case. reg declares mutable variables that can be either combinational or stateful, depending on how they’re used. ↩
In lattice terms, X should work like a top element. ↩
Please direct all Filament fan mail to Rachit, who led that work. ↩

Geometry Bugs and Geometry Types

2024-08-08T00:00:00+00:00

The diffuse component of the classic Phong lighting model, implemented (probably) correctly.

The Phong lighting model is the “hello world” of 3D rasterization effects. Implementing it seems like an appropriate level of challenge for me, a total graphics neophyte. Even a textbook rendering effect, however, entails some geometric thinking that in turn creates the possibility for its own special category of bug. Let’s follow our nose and run into some geometry bugs.

Phong lighting has three parts: some uniform ambient lighting, a diffuse component that looks the same from any angle, and a specular component that adds shiny highlights for direct reflections. To make things even easier, let’s try to implement just the diffuse component. It’s supposed to look like this bunny here.

The idea is to compute the Lambertian reflectance. At every point on the surface of the object, it’s the dot product between the surface’s normal vector and the direction from that point to the light source:

$$ \mathit{lambertian} = \mathsf{max}(\mathit{lightDir}\cdot\mathit{fragNorm}, 0) $$

That $\mathsf{max}$ helps us ignore light coming from behind the rabbit’s surface. We’re implementing this in a fragment shader, so that $\mathit{fragNorm}$ is the normal vector for a given point on the triangle that we’re rendering. We can get $\mathit{lightDir}$ by normalizing the difference between the current fragment position and some absolute position of the light source:

$$ \mathit{lightDir} = \mathsf{normalize}(\mathit{lightPos} - \mathit{fragPos}) $$

Here’s a direct translation of all that into GLSL:

vec3 lightDir = normalize(uLightPos - vPosition);
float lambertian = max(dot(lightDir, vNormal), 0.0);
gl_FragColor = vec4(lambertian * uDiffColor, 1.0);

We’ve set this fragment shader up so it gets its inputs, uLightPos, vPosition, and vNormal, from the CPU. To finish it off, we multiply the Lambertian reflectance magnitude by an RGB color we’ve chosen for our light and, finally, use vec4(..., 1.0) to set the alpha channel to 1.

What happens if you try to implement that diffuse lighting by translating the math 1-1 into GLSL.

This shader is incorrect. The bunny looks like this: the shading seems mostly right, but the invisible light seems to be rotating along with the model instead of staying put.

The math is right, but the code has a geometry bug. The problem is that, when you translate geometric math into rendering code, you have to represent the abstract vectors as concrete tuples of floating-point numbers. When the math’s $\mathit{fragPos}$ becomes the shader’s vPosition, we need to decide on its reference frame: will it be local coordinates relative to the bunny itself, relative to the camera, or using some absolute coordinates for the whole scene? We also need to pick a coordinate system, like ordinary Cartesian coordinates, polar coordinates, or the more graphics-specific system of homogeneous coordinates.

The real problem here is that none of these choices show up in the type system. In GLSL, all our vectors are vec3s. There are several different reference frames at work here, but none of them show up in the programming language. GLSL is perfectly happy to add and subtract vectors that use completely different representations, yielding meaningless results.

This post will walk through fixing the implementation of this math. It’s written for people who don’t know much about graphics or geometry, i.e., people like me. The goal here is to convince you that this kind of programming needs a type system.

Managing Reference Frames

Rendering a whole scene usually involves several model reference frames, a fixed world frame, and a view frame for the camera's perspective.

The first thing that’s wrong is that our vectors are in different reference frames. It’s useful to imagine a single, fixed world frame that contains the entire scene: here, both our bunny and our light source. The geometric data describing individual objects arrives each object’s own individual model reference frame. When you download the .obj file for the Stanford bunny, it doesn’t know about your renderer’s world frame: the vertex positions and surface normals have to come represented in an intrinsic bunny-specific space.

In our little shader, vPosition and vNormal are vectors in the bunny’s model frame while uLightPos is a point in world space. So the subtraction uLightPos - vPosition doesn’t yield a geometrically meaningful vector, and we should probably be careful about that dot(lightDir, vNormal) too.

Renderers use transformation matrices to convert between reference frames. Let’s suppose that we have a uModel matrix that transforms bunny space to world space. Then the GLSL we need should look something like this:

vec3 lightDir = normalize(uLightPos - uModel * vPosition);
float lambertian = max(dot(lightDir, uModel * vNormal), 0.0);

With all our vectors converted to the common (world) reference frame, these operations should mean something!

However, in realistic renderers, the uModel transformation will actually be a mat4, not a mat3. The reason has to do with affine transformations and coordinate systems—we’ll address that next.

Converting Coordinate Systems

In 3-dimensional space, a square 3×3 matrix is a nice way to represent linear transformations: rotations, scaling, shearing, all that. But renderers typically also want to do translation, which requires generalizing to affine transformations. You can’t represent those in a 3×3 matrix, so what can we do?

The usual way is to use homogeneous coordinates. Where ordinary Cartesian coordinates represent a point in 3-space using a GLSL vec3, homogeneous coordinates use a vec4. The extra coordinate is a scaling factor, so the 4-tuple $[x, y, z, w]$ represents the point at $[x/w, y/w, z/w]$. Transformation matrices are mat4s that can represent the full range of affine transformations in 3-dimensional space.

In our example (and in any typical renderer setup), vPosition and vNormal come to us in Cartesian coordinates (i.e., GLSL vec3s) and the uModel transformation matrix comes in homogeneous coordinates (i.e., a mat4). To fix our transformation expression uModel * vPosition, we’ll need something like this:

vec4 posWorldHom = uModel * vec4(vPosition, 1.0);
vec3 posWorldCart = vec3(posWorldHom / posWorldHom.w);

The same shader after applying the same coordinate-system juggling to both input vectors. (Particularly mysterious in dark mode.)

We convert vPosition to homogeneous coordinates by tacking on a scaling factor $w=1$, transform with uModel, and then convert back to Cartesian coordinates by dividing by $w$ again.

With this, we finally have our vertex position in world reference frame. Let’s try repeating exactly the same process with vNormal, the other model-space vector involved in our computation. Sadly, something’s still very wrong—in fact, the bunny somehow looks every worse than it did before. If you’re viewing this page in dark mode, it may not be visible at all.

The problem now is that, while the code we wrote to juggle homogeneous coordinates for vPosition is correct, the same treatment doesn’t work for vNormal. The reason has to do with the different kinds of geometric objects that these variables represent.

Kinds of Geometric Objects

Yet again, we’ve been bitten by a geometric concept that remains invisible in the GLSL code. There’s an important difference between vPosition and vNormal: both are 3-dimensional Cartesian vectors, but one represents a position while the other is just a direction. These might seem like the same thing: what is a direction other than a unit-magnitude position?

We want reference-frame translations to affect positions but not directions.

The distinction matters when we convert between reference frames. Remember that our homogeneous-coordinates transformation matrix uModel can encode a translation (in addition to rotation and scaling and all that). We absolutely want to translate positions when going from the model frame to the world frame, but we do not want to translate directions. When you shift a reference frame over some distance, all the points should move, but directions stay pointing in the same direction—they should not get shifted over by the same amount.

Homogeneous coordinates have a trick to deal with positions. If you set their scaling factor, $w$, to zero, then transformation matrices will treat them correctly: they’ll apply all the linear transformations and none of the (affine) translation. Then, to convert back to Cartesian coordinates, we have to ignore $w$ to avoid dividing by zero. Here’s how it looks in GLSL:

vec3 normWorld = normalize(vec3(uModel * vec4(vNormal, 0.0)));

The key thing to notice is that Cartesian/homogeneous conversion needs to work differently for positions and directions. So programmers have to keep track of the different kinds of geometric objects they’re dealing with in their heads.

The Correct Shader

Here’s a complete version of the correct shader:

// lightDir = normalize(lightPos - fragPos)
vec4 posWorldHom = uModel * vec4(vPosition, 1.0);
vec3 posWorldCart = vec3(posWorldHom / posWorldHom.w);
vec3 lightDir = normalize(uLightPos - posWorldCart);

// lambertian = max(dot(lightDir, fragNorm), 0)
vec3 normWorld = normalize(vec3(uModel * vec4(vNormal, 0.0)));
float lambertian = max(dot(lightDir, normWorld), 0.0);

gl_FragColor = vec4(lambertian * uDiffColor, 1.0);

This shader produces the bunny at the top of this post.

Geometry Types

At OOPSLA 2020, Prof. Dietrich Geisler published a paper about geometry bugs and a type system that can catch them. The idea hasn’t exactly taken over the world, and I wish it would. The paper’s core insight is that, to do a good job with this kind of type system, you need your types to encode three pieces of information:

the reference frame (like model, world, or view space)
the coordinate scheme (like Cartesian, homogeneous, or polar coordinates)
the geometric object (like positions and directions)

In Dietrich’s language, these types are spelled scheme<frame>.object. Dietrich implemented these types in a language called Gator with help from Irene Yoon, Aditi Kabra, Horace He, and Yinnon Sanders. With a few helper functions, you can get Gator to help you catch all the geometric pitfalls we saw in this post. Here’s a version of our shader in Gator:

cart3<world>.point posWorld = hom_reduce(uModel * homify(vPosition));
cart3<world>.vector lightDir = normalize(uLightPos - posWorld);

cart3<world>.direction normalWorld = normalize(hom_reduce(uModel * homify(vNormal)));
scalar lambertian = max(dot(lightDir, normalWorld), 0.0);

The standard library comes with overloaded homify and hom_reduce functions that do the right thing when converting a given geometric object between coordinate systems. Gator also distinguishes vector from direction, which is a subtype that is guaranteed to have unit magnitude. If you forget a transformation or conversion, Gator will report a type error.

With geometry baked into the type system, we can also go one step farther and automatically generate the transformation code. Gator supports an in expression that searches for a transformation from one reference frame or coordinate system to another. For example, if we mark uModel as the canonical transformation from model space to world space, then in world suffices to manage both the reference-frame change and the detour through homogeneous coordinates:

auto lightDir = normalize(uLightPos - (vPosition in world));
scalar lambertian = max(dot(lightDir, normalize(vNormal in world)), 0.0);

We at last have a version of the shader that looks kind of like the math.

I know the world of shading languages is not exactly a hotbed of rapid innovation these days. Even so, I think geometry types are a pretty good idea and I hope that some future generation of rendering systems borrows an idea or two from Gator.

Bril: An Intermediate Language for Teaching Compilers

2024-07-26T00:00:00+00:00

When I started a new PhD-level compilers course a few years ago, I thought it was important to use a “hands-on” structure. There is a big difference between understanding an algorithm on a whiteboard and implementing it, inevitably running into bugs when your implementation encounters real programs. At the same time, I wanted students to get started quickly, without learning the overwhelming APIs that come with industrial-strength compilers.

I created Bril, the Big Red Intermediate Language, to support the class’s implementation projects. Bril isn’t very interesting from a compiler engineering perspective, but I think it’s pretty good for the specific use case of teaching compilers classes. Here’s a factorial program:

@main(input: int) {
  res: int = call @fact input;
  print res;
}

@fact(n: int): int {
  one: int = const 1;
  cond: bool = le n one;
  br cond .then .else;
.then:
  ret one;
.else:
  decr: int = sub n one;
  rec: int = call @fact decr;
  prod: int = mul n rec;
  ret prod;
}

Bril is the only compiler IL I know of that is specifically designed for education. Focusing on teaching means that Bril prioritizes these goals:

It is fast to get started working with the IL.
It is easy to mix and match components that work with the IL, including things that fellow students write.
The semantics are simple, without too many distractions.
The syntax is ruthlessly regular.

Bril is different from other ILs because it prioritizes those goals above other, more typical ones: code size, compiler speed, and performance of the generated code.

Aside from that inversion of priorities, Bril looks a lot like any other modern compiler IL. It’s an instruction-based, assembly-like, typed, ANF language. There’s a quote from why the lucky stiff where he introduces Camping, the original web microframework, as “a little white blood cell in the vein of Rails.” If LLVM is an entire circulatory system, Bril is a single blood cell.

Bril is JSON

Bril programs are JSON documents. Here’s how students get started working with Bril code using Python:

import json
import sys
prog = json.load(sys.stdin)

I’m obviously being a little silly here. But seriously, the JSON-as-syntax idea is in service of the fast to get started and easy to mix and match components goals above. I wanted Bril to do these things:

Let students use any programming language they want. I wanted my compilers course to be accessible to lots of PhD students, including people with only tangential interest in compilers. Letting them use the languages they’re comfortable with is a great way to avoid any ramp-up phase where students must learn some specific “realistic” compiler implementation language if they don’t already know it.
No framework is required to get started. For the first offering of CS 6120, no libraries existed, and I needed to run the course somehow. Beyond that practical matter, this constraint is valuable as a complexity limiter: students can get started with simple stuff without learning any APIs. These days, Bril does come with libraries that are great for avoiding JSON-handling frustrations when you scale up: for Rust, OCaml, Swift, and TypeScript. But the fact that they’re not really required keeps the onramps gentle.
Compose small pieces with Unix pipelines. You can wire up Bril workflows with shell pipelines, like cat code.json | my_opt | my_friends_opt | brilck. I want students in CS 6120 to freely share code with each other and to borrow bits of functionality I wrote. For a PhD-level class, this trust-based “open-source” course setup makes way more sense to me than a typical undergrad-style class where collaboration is forbidden. Piping JSON from one tool to the next is a great vehicle for sharing.

So, JSON is the canonical form for Bril code. Here’s a complete Bril program:

{
  "functions": [{
    "name": "main",
    "args": [],
    "instrs": [
      { "op": "const", "type": "int", "dest": "v0", "value": 1 },
      { "op": "const", "type": "int", "dest": "v1", "value": 2 },
      { "op": "add", "type": "int", "dest": "v2", "args": ["v0", "v1"] },
      { "op": "print", "args": ["v2"] }
    ]
  }]
}

This program has one function, main, with no arguments and 4 instructions: two const instructions, an add, and a print.

Even though Bril is JSON, it also has a text form. I will, however, die on the following hill: the text form is only a second-class convenience, and it is not the language itself. The text syntax exists solely to cater to our foibles as humans for whom reading JSON directly is annoying. Bril itself is the JSON format you see above. But as a concession to our foibles, among Bril’s many tools are a parser and pretty-printer. Here’s the text form of the program above:

@main {
  v0: int = const 1;
  v1: int = const 2;
  v2: int = add v0 v1;
  print v2;
}

As a consequence, working with Bril means typing commands like this a lot:

$ bril2json < program.bril | do_something | bril2txt

It can get tedious to constantly convert to and from JSON, and it’s wasteful to serialize and deserialize programs at each stage in a long pipeline. But the trade-off is that the Bril ecosystem comprises a large number of small pieces, loosely joined and infinitely remixable on the command line.

Language Design: Good, Bad, and Ugly

There are a few design decisions in the language itself that reflect Bril’s education-over-practicality priorities. For instance, print is a core opcode in Bril; I don’t think this would be a good idea in most compilers, but it makes it easy to write small examples.

Another quirk is that Bril is extremely A-normal form, to the point that constants always have to go in their own instructions and get their own names. To increment an integer, for example, you can’t do this:

incr: int = add n 1;

Instead, Bril code is full of one-off constant variables, like this:

one: int = const 1;
incr: int = add n one;

This more-ANF-than-ANF approach to constants is verbose to the point of silliness. But it simplifies the way you write some basic IL traversals because you don’t have to worry about whether operands come from variables or constants. For many use cases, you get to handle constants the same way you do any other instruction. For teaching, I think the regularity is worth the silliness.

Bril is extensible, in a loosey-goosey way. The string-heavy JSON syntax means it’s trivial to add new opcodes and data types. Beyond the core language, there are “official” extensions for manually managed memory, floating-point numbers, a funky form of speculation I use for teaching JIT principles, module imports, and characters. While a laissez faire approach to extensions has worked so far, it’s also a mess: there’s no systematic way to tell which extensions a given program uses or which language features a given tool supports. A more explicit approach to extensibility would make the growing ecosystem easier to manage.

Finally, Bril does not require SSA. There is an SSA form that includes a phi instruction, but the language itself has mutable variables. I wouldn’t recommend this strategy for any other IL, but it’s helpful for teaching for three big reasons:

I want students to feel the pain of working with non-SSA programs before the course introduces SSA. This frustration can help motivate why SSA is the modern consensus.
The course includes a task where students implement into-SSA and out-of-SSA transformations.
It’s really easy to generate Bril code from frontend languages that have mutable variables. The alternative would be LLVM’s mem2reg/”just put all the frontend variables in memory” trick, but Bril avoids building memory into the core language for simplicity.

Unfortunately, this aftermarket SSA retrofit has been a huge headache. It has caused persistent problems with undefinedness and classic correctness problems when translating out of SSA. I think my original design is fundamentally flawed; it was a mistake to treat phi semantically as “just another instruction” instead of a more invasive change to the language. Bril’s SSA form needs a full rework, probably including an actual language extension along the lines of MLIR’s basic block arguments. It has been an interesting lesson for me that SSA comes with subtle design implications that are difficult to retrofit onto an existing mutation-oriented IL.

The Bril Ecosystem

I cobbled together the first version of Bril in a hurry in the weeks before the fall 2019 semester began. Since then, via the “open-source class” nature of CS 6120, students have contributed a host of tools for working with the language. The diagram above shows a sampling of what is in the monorepo; empty boxes are things I made and shaded boxes are things students contributed. One satisfied CS 6120 customer built a snazzy web playground that I find super impressive. You can find many more random tools by searching on GitHub.

Most of the language extensions I mentioned were contributed by CS 6120 students. In the run-up to the first semester, I was low on time and left memory, function calls, and floating-point numbers as “exercises for the reader.” You can read 2019 blog posts by Drew Zagieboylo & Ryan Doenges about the memory extension, by Alexa VanHattum & Gregory Yauney about designing function calls, and by Dietrich Geisler about floats. Laziness can pay off.

Please get in touch if you’re using Bril for something unconventional! I love learning about the weird places it has gone.

Automated Test-Case Reduction

2024-07-15T00:00:00+00:00

Last time, we saw how deleting stuff from a test case can be an easy and fun route to the root cause of a bug. It’s less easy and less fun when the test cases get big. The inner loop of test-case reduction can get old quickly: delete stuff, run the special command, check the output to decide whether to backtrack or proceed. It’s rote, mechanical, and annoyingly error prone.

Let’s make the computer do it instead. Automated test-case reducers in the C-Reduce mold follow essentially the same “algorithm” we saw last time. They obviously don’t know your bug like you do, so they can’t apply the intuition you might bring to deciding which things to delete when. In return, automation can blindly try stuff much faster than a human can, potentially even in parallel. So the trade-off is often worthwhile.

Automating the Reduction Process

In the manual test-case reduction “algorithm,” there are really only three parts that entailed any human judgment:

Picking a part of the test case to delete.
Looking at the command’s output to decide whether we need to backtrack: that is, detecting when a given deletion either removed the bug-triggering code or broke the program entirely.
Deciding when to give up: when we probably can’t reduce any farther without ruining the test case.

Everything else—running the command after every edit, hitting “undo” after we decide to backtrack—was pretty clearly mechanical. Automated reducers take control of #1 and #3. Picking the code to delete (#1) is just guesswork anyway; because we rely on step #2 to detect cases where a deletion went awry, it suffices to guess wildly using a pile of heuristics that have some probability of finding a useful deletion. To decide when to stop (#3), reducers detect a fixed point: they give up when the heuristics fail to find any more code they can safely delete.

That leaves us with #2: deciding whether a given version of the test case still works to reproduce the bug you’re interested in. Test-case reducers call this the interestingness test (in the C-Reduce tradition), and they typically want you to write it down as a shell script. To use a reducer, then, you usually just need two ingredients: the original test case you want to reduce and the interestingness test script.

Writing an Interestingness Test

This post will demonstrate how to use the excellent Shrinkray reducer to debug the same interpreter bug as last time. Shrinkray is language-neutral–and, in any case, no reducer knows about Bril. I think it’s pretty cool that reducers can work well even if they don’t know anything about the syntax or semantics of the language they’re working with.

Like any automated reducer, Shrinkray needs an interestingness test: a little program that checks whether the bug we care about currently exists. To make one, “all we need to do” is take the commands we were running manually to check for the bug and put them in a shell script.

The problem, as we’ll discover, is that Shrinkray is a little like the sorcerer’s apprentice. It will do exactly what we tell it to do, and it will do it with great enthusiasm. Even tiny gaps in our instructions can lead to surprising results. So, in my experience, writing a good interestingness test requires (a) a small bag of tricks that may not be intuitive your first time around, and (b) some trial and error.

I recorded a video of my own trial-end-error process, and I’ve also written it out in prose below. Here’s the video:

Hang on; I’m being told that this is the wrong video. Let’s try that again:

Walkthrough

In essence, an interestingness test is a script that automates the commands we ran repetitively (with the “up arrow” at the shell prompt) during manual reduction. Here’s the main command we repeatedly ran then:

$ bril2json < problem.bril | cargo run -- -p false false

I started by just putting this command into a shell script, interesting.sh. Shrinkray wants our script to work from any directory, so I used an absolute path to the executable:

#!/bin/sh
bril2json < $1 | /Users/fabian/Documents/cu/bril/brilirs/target/debug/brilirs -p false false

I also used $1 for the filename; Shrinkray passes the current version of the test file as an argument there. Following the C-Reduce tradition, interestingness tests use a counter-intuitive (but extremely useful) convention: the script must exit with status 0 when the test is interesting (exhibits the bug) and nonzero when it’s not (e.g., it’s bug-free or ill-formed). So far, our command crashes with a nonzero status—specifically, a Rust panic—when it is interesting, which is the opposite of what we want.

Trick 1: Shell Negation

So here’s a trick you can use in interestingness tests in general: try the shell’s negation operator, !, to invert the sense of the exit status. Like this:

#!/bin/sh
! ( bril2json < $1 | /Users/fabian/Documents/cu/bril/brilirs/target/debug/brilirs -p false false )

Now our tests says the input is interesting (status 0) when the interpreter does crash. Let’s try it:

$ shrinkray interesting.sh problem.bril

With this script, Shrinkray immediately reduces our file down to nothing. And it’s not wrong: a zero-byte file does elicit an error from our interpreter! As usual, the sorcerer’s apprentice did exactly what we said, not what we wanted, and did it with wondrous alacrity.

Trick 2: The “Not Bogus” Check and `set -e`

This leads us to our second trick for writing interestingness tests: before you try to expose the bug, include a “not bogus” check. You want to make sure your test is well-formed in some sense: it parses successfully, or it doesn’t throw an exception, or whatever else.

In our case, we’re debugging a crashy interpreter, but we also have access to a reference interpreter that doesn’t have the same bug. So we can add a “not bogus” check that requires any well-formed test to succeed in that reference interpreter. Here’s a new script that includes that check:

#!/bin/sh
set -e
bril2json < problem.bril | brili false false
! ( bril2json < $1 | /Users/fabian/Documents/cu/bril/brilirs/target/debug/brilirs -p false false )

Check out that set -e line, which is super useful for interestingness scripts and “not bogus” checks in particular. The -e option makes a shell script immediately abort with an error (signalling “uninteresting”) when any line fails. In -e mode, you’re free to write a bunch of commands that should succeed in the normal case but might fail when the test really goes off the rails: as soon as any command fails, the script will bail out and indicate that we’re on the wrong path. So in my script here, we’re requiring the brili (reference interpreter) invocation to succeed before we even bother trying to expose the bug.

Let’s restore our test input from the backup Shrinkray saved for us and try again:

$ cp problem.bril.bak problem.bril
$ shrinkray interesting.sh problem.bril

Shrinkray will again sorcerer’s-apprentice its way into a much too small test case. Not zero bytes this time, but too small to be useful. To see what went wrong, we can run our two commands (“not bogus” and bug check) manually:

$ bril2json < problem.bril | brili false false
$ bril2json < problem.bril | ./target/debug/brilirs -p false false
error: Expected a primitive type like int or bool, found l

Shrinkray has isolated for us a different error with the same shape, i.e., the reference interpreter accepts the program but the buggy interpreter rejects it. This one is not really a bug: it’s just a case where the second interpreter is more strict than the first. And even if this misalignment is curious, it’s not the bug we were looking for.

Trick 3: `grep` for Your Error Message

So here’s trick number three for writing interestingness tests: use grep to check for the error message we actually want. In our case, the program panics with an “out of bounds” message. Let’s restore from backup and grep for that in both stdout and stderr like this:

$ cp problem.bril.bak problem.bril
$ bril2json < problem.bril | ./target/debug/brilirs -p false false 2>&1 | grep 'out of bounds'

Conveniently, grep does exactly what you want for an interestingness test: its exit status is 0 when it finds the string (interesting because this is the bug we are looking for) and 1 when it fails to find the string (some other error). So here’s our new script:

#!/bin/sh
set -e
bril2json < problem.bril | brili false false
bril2json < $1 | /Users/fabian/Documents/cu/bril/brilirs/target/debug/brilirs -p false false 2>&1 | grep 'out of bounds'

With this script, Shrinkray does a great job and reduces quite a bit of code, which is awesome. One thing it can’t reduce, however, is the way the program uses arguments. It’s actually hopeless for Shrinkray to remove the arguments because it would require changing the interestingness test script to remove those false false command-line arguments we keep on passing.

Trick 4: Occasional Manual Help

We can help Shrinkray out a bit by turning those inputs into constants in the code. We can replace main’s arguments with two new Bril instructions:

b0: bool = const false;
b1: bool = const false;

Accordingly, we need to change our interestingness test to pass zero arguments to both interpreter invocations:

#!/bin/sh
set -e
bril2json < problem.bril | brili
bril2json < $1 | /Users/fabian/Documents/cu/bril/brilirs/target/debug/brilirs -p 2>&1 | grep 'out of bounds'

At this point, it’s probably a good idea to do ./interesting.sh problem.bril to manually check that everything’s in order.

Success!

Everything looks good in this case, so we can fire up Shrinkray again. It gives us this reduced test case:

@main{
    jmp .A;
    .A:ret;
    .A:jmp  .A;
}

This is not quite the same as the reduced version we arrived at with manual reduction. The one we wrote found last time actually an infinite loop—so it wouldn’t pass our interestingness test! So this one is actually a little more useful in that sense: you can run it through the reference interpreter to immediately see what it’s supposed to do. It’s sort of weird that the reduced test has a multiply defined label, but apparently neither interpreter cares about that… if we wanted to, we could imagine avoiding this by adding a second “not bogus” check based on some static error checking.

One Weird Trick for Efficient Pangenomic Variation Graphs (and File Formats for Free)

2024-05-28T00:00:00+00:00

We built an efficient binary representation for pangenomic variation graphs that is equivalent to the standard GFA text format. Our approach isn’t at all novel, but it illustrates a fun way that you can start with a naïve representation and transform it into a fast in-memory representation while also getting an on-disk file format for free. In a shamelessly cherry-picked scenario, our tool is 1,331× faster than an existing, optimized pangenomics toolkit that already uses an efficient binary representation.

Pangenome Recap

Let’s return to that pangenome data structure from last time. Here’s a simplified part of the data model, in fake Rust:

A Graph owns sequences of Segments and Paths, and the latter contains a sequence of steps. Each step is a Handle that encapsulates a traversal of a Segment in either the forward to the backward direction. In the GFA text format, here are three Segments and one Path:

S	1	CAAATAAG
S	2	AAATTTTCTGGAGTTCTAT
S	4	CCAACTCTCTG
P	x	1+,2+,4-	*

The three S lines are segments, which contain short nucleotide sequences. That P line is a path with three steps: it traverses segment 1 and 2 in the forward (+) direction and then segment 4 in the backward (-) direction. It looks like this:

This data structure seems pretty pointery. Last time, I showed off a straightforward Python library we made that embraces that pointeriness. It’s slow but clear.

This post is about implementing an efficient representation. Other efficient data representations exist—prominently, odgi, which is by some collaborators. But they get performance by combining many different representation tricks. I want to understand the basics here by using a single principle and see how far it gets us.

Flattening the Data Structures

The central principle we’ll use is flattening, a.k.a. arena allocation, a.k.a. just cramming everything into arrays and using indices instead of pointers. In the fake Rust declarations above, I used Ref and List to suggest ordinary pointer-based references to one and many elements. In the flattened version, we’ll replace all of those those with plain u32s:

Now the central Graph struct has three Vec arenas that own all the segments, paths, and the steps within the paths. Instead of a direct reference to a Segment, the Handle struct has a u32 index into the segment arena. And each Path refers to a contiguous range in the step arena with start/end indices. In the real thing, even Path::name and Segment::sequence get the same treatment: there are two giant byte strings in the Graph struct that act as arenas; every Path and Segment just has a (u32, u32) pair to refer to its name or sequence as a chunk within a given string.

The result is that, outside of the arenas, all the types involved are fixed-size, smallish, pointer-free structs. It might be helpful to visualize the memory layout:

The Path::steps field refers to a slice of the path_steps array, and the Handle::segment field in there refers to a position in the segments array. There are no actual, word-sized pointers to the virtual address space anywhere. Again, while I put the path names and the nucleotide sequences inline to make this picture simpler, the actual implementation stores those in yet more arenas. My current implementation uses 12 arenas to implement the complete GFA data model.

It’s Pretty Fast, I Guess

What have we really gained by replacing all our pointers with integers? Even though we haven’t fundamentally changed the data structure, there are a few reasons why a flat representation for GFAs should be more efficient:

Faster allocation. By sacrificing the ability to deallocate elements at a fine granularity, we can use simple bump allocation instead of a proper malloc when building the data structure.
Locality. We’re forcing logically contiguous elements, such as each path’s steps, to be contiguous in memory. That’s probably good for spatial locality.
Smaller pointers. Replacing &Segment with u32 comes with a 2× space savings on 64-bit machines. In a data structure with so many internal references, that probably counts for something.

Here’s a brutally unfair way to measure the bottom-line performance impact of these effects. We can compare our new, flattened implementation—called FlatGFA and implemented in Rust—against our simple-as-possible Python library from last time. For more context, we can also compare against odgi, a C++ toolkit for GFA processing that also uses an efficient, index-based representation internally.

For this experiment, we’ll just compare the time to round-trip a GFA file through the internal representation: we’ll make each tool parse and then immediately pretty-print the GFA to /dev/null.¹ I measured the round-trip performance on three tiny graphs and three medium-sized ones from the Human Pangenome Reference Consortium and the 1000 Genomes Project.²

Time to round-trip (parse and pretty-print) some tiny GFA files (288 kB, 1.0 MB, and 1.5 MB, from left to right). Our pure-Python slow-odgi library is about 2× slower than odgi.

Round-tripping some bigger GFAs (7.2 GB, 2.3 GB, and 2.7 GB). The pure-Python library is not a contender. FlatGFA is 11.3× faster than odgi on average (harmonic mean).

FlatGFA can round-trip small GFA files about 14× faster than slow-odgi. That speedup conflates the three fundamental advantages above with mundane implementation differences (FlatGFA is in Rust; slow-odgi is in Python). I would love to do more measurement work here to disentangle these effects: for example, we could check how much the pointer size matters by using u64s everywhere instead of u32s.

FlatGFA is also 11.3× faster than odgi on average.³ It can process the largest graph (7.2 GB of uncompressed GFA text) in 67 seconds, versus 14 minutes for odgi. I don’t really know why, because odgi also (sensibly) uses a mostly flattened representation. My best guess is that odgi’s implementers focused their efforts on actually novel, actually smart data structure ideas with asymptotic benefits (e.g., they use a special index to quickly locate steps within a path) and not on boring data-representation engineering that only brings constant factors. FlatGFA only does boring, but it goes all the way: it exterminates all the pointers. And the constant-factor payoff from this basic flattening transformation can be surprisingly large.

Possible lessons here include:

“Merely” flattening an otherwise naïve data structure can turn it into a competitive one.
So it can be helpful to get that in place even before seeking asymptotic gains through indexing and the like.

A File Format for Free

Because it has no pointers in it, a ruthlessly flattened in-memory representation has one bonus feature: it does double duty as a file format. If we take all those densely packed arrays-of-structs that make up a FlatGFA, concatenate them together, and add a little header to contain the sizes, we have a blob of bytes that we might as well write to disk.

Turning FlatGFA into a file format took two steps: applying the amazing zerocopy crate, and separating the data store from the interface to the data.

Use zerocopy to get `AsBytes` and `FromBytes`

First, zerocopy is an immensely rad crate that can certify that it’s safe to cast between Rust types and raw bytes. It contains a bunch of macros, but these macros don’t actually generate code for you: they just check that your types obey a bunch of rules. The zerocopy authors have done the hard work (i.e., thinking carefully and using Miri) to be pretty confident that all types that obey their rules can be safely transmuted to and from [u8] chunks. These rules include alignment restrictions and the necessity that every bit-pattern is a valid value. The latter rule makes enums tricky: every enum must have 2ⁿ variants where n is the number of bits in its representation. But once you’ve cleared all those hurdles, your types gain the AsBytes and FromBytes traits.

Separate the Storage from the Interface

Now that all our structs are equipped with the zerocopy superpowers, we need a way to make the entire data structure map to bytes. One nice way to do it is to separate our actual data storage location from a lightweight view of all the same data. The idea is to start with that top-level struct that contains nothing but the Vecs of littler structs:

And to separate it into two structs. We want one store object that keeps all those Vecs and one view object that has all the same fields but with slices instead of vectors:

Our ThingStore struct will never get the zerocopy superpower—Vecs are inherently pointerful and must live on the heap—but ThingView is perfectly suited. We can construct one by calling from_bytes on different chunks within a big byte buffer:

We’ll also need a small table of contents at the top of the file to tell us where those chunks are. But once we’ve managed that, ThingView serves as an abstraction layer over the two storage styles. The Vec-based store provides heap-allocated, arbitrarily resizable allocation pools; the &[u8] option constrains the sizes of the arenas but maps easily to a flat file.⁴

0 Copy = ∞ Speedup

Using the same type for the in-memory and on-disk representations is not just convenient; it also makes deserialization infinity times faster.⁵ To “open” a file, all we need to do is to mmap(2) it. There is no deserialization step; we don’t even have to read the whole file if we don’t need it.

This latter aspect can lead to some pretty funny speedups for FlatGFA compared to odgi, which has its own efficient binary GFA-equivalent file format but which uses traditional serialization. Here’s a performance comparison between the odgi paths -L command, which just prints out all the names of the paths in the graph, and the FlatGFA and slow-odgi equivalents:

Time to print the path names from the same graphs as above. The slow-odgi reference implementation is a hilarious 19× slower than odgi on average.

Printing paths names from the same larger graphs. FlatGFA is 1,331× faster than odgi, which is not infinity, but it's pretty good.

This comparison starts with the native binary formats for odgi and FlatGFA, so only slow-odgi actually has to parse any text. Across the three big GFAs, FlatGFA is 1,331× faster than odgi on average. On the largest (7.2 GB) graph, FlatGFA takes 5.8 ms to odgi’s 12 seconds. If you look at a profile of where odgi spends its time, about 90% of it goes to deserialization and 9.9% goes to deallocating that data structure. Less than 1% of the time is spent on the “real work,” i.e., extracting and printing those path names. So this is an extreme edge case where FlatGFA’s deserialization- and allocation-free strategy makes for especially silly-looking bar charts.

Someday, Acceleration

We originally fell into this rabbit hole because we want to build hardware accelerators for this stuff. Surprising absolutely no one, data representation turns out to be the key to an efficient implementation, regardless of whether it’s in hardware or software. Outside of flattening and memory-mapping, FlatGFA is totally unoptimized—so we’re now fully distracted by understanding the space of possible efficient representations and their implications for hardware design. We’ll get back to implementing that hardware someday. I promise.

FlatGFA is the only one of the three tools that actually preserves GFA files, byte for byte, when round-tripping them. Both odgi and mygfa (quite sensibly) normalize the ordering of elements in the graph. I made FlatGFA preserve the contents exactly to make it easier to test. ↩
All wall-clock times collected on our lab server, which has two Xeon Gold 6230 processors (20 cores per socket @ 2.1 GHz) and 512 GB RAM. It runs Ubuntu 22.04. Error bars show standard deviations over at least 3 (and usually more like 10) runs, measured with Hyperfine. ↩
I think this means FlatGFA currently has the fastest GFA parser in the universe. This is not all that impressive; it’s an extremely easy-to-parse grammar. Even so, I would love to be proven wrong. ↩
In the real implementation, I also added a second storage style based on tinyvec::SliceVec instead of plain old Vec. This approach splits the difference between slices and vectors: each arena has a fixed maximum capacity, but its length can be less than that. So the SliceVecs, even when they map to a fixed-size &[u8] of file contents, can still shrink and grow within limits. ↩
This hyperbolic framing is stolen from Cap’n Proto, which honestly blew my mind the first time I understood what it was doing. ↩