Some Course Project Ideas #495
Replies: 1 comment 1 reply
-
|
Oh, I'm interested to see if anyone uses the dynamic types extension. I'm not sure if anyone happens to use Rust but I'll shamelessly suggest extending Extending rs2bril
A non-exhaustive list of unsupported features includes: for loops, break/continue, ranges, slices, Vec/Option, pattern-matching, closures, structs, and enums(Note that some of these may either need to be implemented using dynamic types or with a new Bril extension of your own design!). You can also just start writing some Rust programs/porting some benchmarks and see where it breaks! Attributes: "Open-ended; scalable according to the size of the subset you pick; learn a lot about the internals of your favorite |
Beta Was this translation helpful? Give feedback.
-
|
To add on --- if you object to using
Note that with some of these you may end up having to define parts of the Rust grammar yourself |
Beta Was this translation helpful? Give feedback.
-
It's time to start thinking about course projects for the spring 2025 offering of the class. You can really do anything you want, including repurposing your own ongoing research (or some fraction thereof) as a course project. But if you need some help coming up with an idea, here are some thoughts I had this semester!
See the "attributes" on each idea for some characteristics that I think could help you decide which kind of project is for you.
Bril MLIR Dialect
Are you enjoying your foray into the LLVM ecosystem? MLIR is an LLVM-adjacent project that is a generic infrastructure for defining new compiler IRs, which they call "dialects." You could learn a lot about the MLIR ecosystem by making a dialect that corresponds to Bril. You'd probably want to build both directions of the translation (from JSON to MLIR, and from MLIR to JSON), and maybe some kind of translation into/out of an existing MLIR dialect.
Attributes: Engineering-forward; probably uses C++; build real-world skills.
Relooper or Similar in Bril
CFGs are more general than structured control flow (i.e., nested combinations of
if,while, and friends). Sometimes, it is useful to recover structured control flow from a CFG—for example, when trying to translate to a language that doesn't havegoto. A popular way to do this is known as the "relooper" algorithm, and the 2022 "Beyond Relooper" paper offers improvements. Just implementing this in Bril could be pretty fun.Attributes: Algorithmic and thinky; entails carefully reading a paper; actually quite useful for many other projects; control-flow-y; easy to test for correctness.
Register Allocation in Bril
We intentionally don't cover register allocation in 6120, but there are many, many well-known approaches out there. Just implement one (or more than one) in Bril! Because Bril itself has unbounded variables, I would set this up so you "fake" a limited set of registers. Like, use bounded number variables named
reg_1,reg_2, etc. to model the registers; all variable names that don't start withreg_then assumed to go on the stack. The cool thing about this project is that it would help other people write backends for targeting real machine code: they could reuse your register allocation and then just take care of instruction selection separately.A particularly attractive option would be to start with SSA-form Bril and implement one of the approaches that simultaneously "exits" SSA and performs register allocation, such as this one.
Attributes: Open-ended; requires selecting one or more "classic" algorithms to try out; easy to test for correctness; interesting opportunity for empirical evaluation; also legitimately quite useful for other projects.
ChocoPy to Bril
Building a frontend that generates Bril is a pretty straightforward project idea! One entertaining option would be ChocoPy, a Python-like language for compilers classes developed at Berkeley. (So this would unite two educational-focused programming languages!) There is recent prior work on this, which used a custom lexer/parser. I'd recommend instead trying to reuse an existing parser and just taking care of the transition. Then you could check correctness using differential testing against an existing ChocoPy implementation.
Attributes: Clearly defined; limited scope; probably possible to get the satisfying feeling of having something working quickly.
Implement Ball-Larus Path Profiling
Did you like the Ball-Larus paper about path profiling? Implement that, either using LLVM or in Bril! In fact, there used to be an implementation in LLVM (you can find it in git history), but it bitrotted and was removed. So you could resurrect this pass!
Attributes: Clearly defined scope; plenty of tricky thinking and lots of engineering and testing too.
Global Value Numbering
You implemented local value numbering already; now implement global value numbering (GVN) for Bril. You will almost certainly want to follow the paper titled "Value Numbering" by Briggs et al., and you can check out this 6120 blog post from years gone by. Importantly, you will want to do this in SSA form; do not attempt it on non-SSA Bril. Like LVN, GVN is a powerful framework that can achieve lots of "classic" optimizations in one fell swoop (DCE, CSE, copy propagation, constant folding, etc.), so it can be a very effective way to pick all the low-hanging fruit in many programs.
Attributes: Stay in your comfort zone of semantics-preserving intraprocedural optimizations; expect a satisfying outcome where most Bril programs get a lot faster.
WebAssembly to Bril
Also in the category of "just translate an existing language to Bril," try compiling WebAssembly! WebAssembly is super popular, so this would instantly connect Bril to a much wider ecosystem of compilers and tools. You would probably want to start with a restricted subset and see how far you can get. There are many existing compliance tests (and implementations) for WebAssembly, so differential testing would be really straightforward and help you track your progress as you cover more and more of the language.
Attributes: Learn about a very important industry-relevant technology; clear criterion for correctness; can scale to fit the time you want to spend (by picking the size of the WebAssembly subset you support).
Bril to WebAssembly
Why not translate Bril programs to WebAssembly? Seems like fun! You could even see if the resulting translation is faster or slower than existing Bril compilers/interpreters. One wrinkle here is that WebAssembly uses structured control flow, so this would need something like the "relooper" project above as a prerequisite. Test for correctness by comparing against the reference interpreter; test performance with wall-clock time using an existing WebAssembly implementation like Wasmtime.
Attributes: Also learn about a very important industry-relevant technology; clear correctness criterion; stay in your Bril comfort zone; lots of fun experimental design to get meaningful performance results.
Python/JavaScript/Ruby to Bril, Using the Dynamic Type
Recently, @Pat-Lafon added a new
anytype to Bril in the dynamic typing extension. This opens up an opportunity to compile dynamically typed programming languages to Bril in a somewhat straightward way, without forcing them awkwardly into Bril's static type system. Pick some tiny subset of these mainstream languages and try doing the translation! Test against a real implementation, like CPython.Attributes: Open-ended; scalable according to the size of the subset you pick; learn a lot about the internals of your favorite dynamic language implementation; AST wrangling; fun but not very practical.
Measure the Performance of SSA Generation
When we read the "simple and efficient" SSA paper in class, many people wondered how the actual compile-time performance differed w/r/t a compiler that first translates to a non-SSA CFG and then uses the classic dominance-frontier-based Cytron algorithm. That is a very good question! The idea would be to engineer some kind of compiler twice: once with the "all at once" SSA approach, and once with the "CFG first, then SSA" approach. Then you could compare the performance empirically, and you could also do a qualitative report on the engineering trade-offs between the two.
Attributes: Probably actually publishable research; large scope; requires creativity; lots of engineering; also lots of performance measurement work.
Bounded-Error Floating Point Optimizations
Also inspired by a discussion from class recently: can you think of any compiler optimizations to perform on floating-point computations that would result in a bounded error? The idea would be that the user gives you an error bound and you (the compiler) try to make the program as fast as possible within that bound. Unfortunately, this is probably really hard (because error bounds are hard to enforce in general) and has lots of prior work: see, for example, the Herbie project that does algebraic rewritings to find more stable implementations of numeric expressions, and the "Towards a Compiler for Reals" paper that lays out a vision for how this kind of thing should probably work.
Attributes: Poorly defined scope; maybe impossible; could be fun to try anyway if you are super ambitious.
Parallelize Data Flow Analysis
Data flow analysis with the worklist algorithm can be a bottleneck for compilation speed, and it can really matter in JITs. What if we tried to parallelize it, using either SIMD instructions or even a full-on GPU implementation? You'd want to design a parallelism-friendly data structure for representing the worklist algorithm's state. The worklist algorithm is iterative, so it should be safe to try to process different parts of the CFG in parallel. Just set multiple threads/SIMD lanes loose on handling different parts of the worklist. Even if you "waste work" and end up needing to process the same CFG node more times than you would in a sequential implementation, parallelizing this way could still come out ahead. You could even take a Hogwild! approach and let the parallel threads clobber each other's work willy-nilly; maybe that would be faster than properly synchronizing.
This idea is based on a Mastodon conversation with John Regehr; it would be great to loop him in if you pick this one.
Attributes: Probably actually publishable research; requires parallel programming heroics; maybe doomed to fail by just being slower than the sequential version.
Beta Was this translation helpful? Give feedback.
All reactions