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)
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:
Next steps
After completing the core GVN implementation, we plan to extend the optimizer to include:
Team members:
@SyphonArch (Jake Hyun)
@tobiwg (Tobi Weinberg)
@adnan-armouti (Adnan Armouti)