sampsyo
Project Proposal: Global Value Numbering
What will you do? We will implement global value numbering (GVN) for Bril, following the SSA-based algorithmic structure described by Briggs et al. GVN generalizes local value numbering to handle redundant computations across basic blocks, allowing elimination of common subexpressions, copies, and dead code more effectively. We will build upon our previous transformation infrastructure from earlier assignments.
How will you do it? We plan to implement GVN in Python, leveraging the SSA form already supported in Bril. Our design will center around constructing and traversing the dominator tree, maintaining a scoped or unified hash table of expression equivalences, and applying algebraic simplifications and constant folding. Once redundancy detection is complete, we will rewrite redundant instructions to use existing values and remove unnecessary computations. For correctness, we will run our implementation on all programs in the Bril benchmark suite provided in the repository.
How will you empirically measure success? We will evaluate our implementation in two aspects:
- Correctness: Verify that all optimized programs produce identical outputs to their originals by running the full Bril benchmark suite and comparing outputs.
- Performance: Measure improvement through both static instruction count reduction and dynamic operation count/runtimes on benchmark programs before and after applying GVN.
Next steps After completing the core GVN implementation, we plan to extend the optimizer to include:
- Constant propagation and folding
- Copy propagation
- Algebraic simplification
Team members: @SyphonArch (Jake Hyun) @tobiwg (Tobi Weinberg) @adnan-armouti (Adnan Armouti)
Awesome. This is a well-scoped project—it will not be easy, and it will definitely be a lot of work, but not overwhelmingly so. I know that this is obvious advice, but I'll say it anyway: it would be a really good idea to start early so you have even a semi-working implementation soon, because I imagine a large amount of your time will go into debugging.
Do you know yet which Bril extensions you will support? Just core would be fine, but I thought I'd ask.
We will focus our evaluations on empirical correctness, and aim to have our pass produce correct output for all of the benchmark suites - that'd be core, float, long, mem, and mixed.
For some extension I foresee that we might have to fall back to more conservative approaches (so we might not fully optimize everywhere), but we do hope to have it running correctly on them all!