Blog

Register allocation is commonly framed as a vertex coloring problem on an interference graph, where vertices represent virtual registers and edges connect two virtual registers that interfere (belong to the same live-out set of a program point). A classic method, due to Chaitin1, is to do register allocation via graph coloring with a set of heuristics to make the problem more easily computable, as vertex coloring is an NP-Hard problem. Read more

Caiman is a language designed for heterogeneous programming that formalizes the communication between devices, allocations, and computations performed. This post details the current state of the Caiman Frontend and includes a brief overview of the implementation of some features such as lowering to continuation passing style and the e-graph-based type inference. Background In heterogeneous programming, communication and synchronization between devices is extremely important for performance, but it’s not at all obvious what the optimal communication strategy should be. Read more

In a previous post, we discussed implementing an analysis to detect potential uses of null pointers. The workhorse of this analysis was an interval analysis that could (conservatively) determine all possible values an integer could take on. We used this information to prove whether or not an array access could be determined to always be in-bounds. This worked, but it could not handle cases such as a dynamically sized buffer. Suppose we know that a buffer has $a$ elements. Read more

Ensuring good test coverage of a compiler is hard. That’s why I developed Bear, a compiler fuzzer that generates random test cases for compiler optimization passes. (Named as such because bears are fuzzy?) Bear uses genetic programming to evolve novel programs in the search space. Bear generates programs in a custom DSL (domain-specific language) known as Bare C before being lowered into the target IR. The IR Bear currently targets is BRIL (Big Red Intermediate Language), which is the IR used in Cornell’s PhD level compilers course. Read more

Figuring out how to run a pass with LLVM feels needlessly complicated. This short post will briefly lay out two different methods of doing so using the new Pass Manager. Invoking via Clang One simple method of running a compiler pass is to directly invoke it via Clang as outlined in this blog post. This method is fairly straightforward and super easy, we just need to: Create a class that inherits from PassInfoMixin, as described here. Read more

I’ve always been interested in being able to make guarantees about the correctness of a program without the high cost of doing something like a full-on verification in an automatic theorem prover such as Coq. Moreover, avoiding extra runtime costs would be extremely nice as well, especially for systems programming domains. I recently began working on an LLVM pass which aims to guarantee the absence of loading and storing of null pointers. Read more

Computations of physical values in programming languages can quickly get out of hand due to the complex units that the programmer has to keep track of. Good variable naming and comments can help, but nothing is stopping double run_time_sec from storing a time measured in milliseconds. Furthermore, different functions might use the same value, but measured in different units, requiring manual conversions. Overall, it’s just an unpleasant burden placed on the programmer and a cause of many errors. Read more

Accurate collision detection is a vital part of video games and simulation, and fast collision detection is paramount for real-time applications such as games. In high school, building such a fast and accurate collision engine eluded me. This post describes, conceptually, the algorithm I settled upon when developing Project Oort. I will assume a basic familiarity with the problem of collision detection, including bounding spheres and axis-aligned bounding boxes, simple data structures like trees, and the basics of concrete linear algebra including vectors, matrices, and linear transformations. Read more

When implementing the cloaking ability for Project Oort, I came upon a somewhat interesting problem: At what point during the gradual disappearing process should the object’s shadow disappear? At first, I just had the object abruptly stop writing to the depth buffer at a certain transparency threshold. This would cause the shadow to simply cut out at an arbitrary point. I didn’t like the look of that and decided that I wanted the shadow to fade in and out gradually. Read more