CS Special Seminar: Chun Kit Lam "Efficient, Practical and Optimal Algorithms in Compiler Optimization"

Efficient, Practical and Optimal Algorithms in Compiler Optimization

Chun Kit Lam
HKUST
Google Scholar

Abstract: Compiler optimization is a critical step in the compilation process, as it can significantly improve the performance of the generated code. Unfortunately, most compiler optimization tasks are NP-hard. Therefore, most of the existing work either relies on heuristics and sacrifices the optimality of the solution for efficiency, or uses integer programming solvers that cannot handle large input instances.

In this talk, I consider a completely different approach. By exploiting the underlying structure and sparsity of the problems, we can design fixed-parameter tractable algorithms that are simple, efficient and optimal. As examples, I will present fixed-parameter tractable algorithms for the classical problems of register allocation and equality graph extraction. Both of these problems were studied for decades and are known to be NP-hard, even in their most basic special cases. However, using parameterization, I solve their real-world instances efficiently and optimally. 

Bio: Chun Kit (John) Lam is in his third year of PhD in Computer Science at HKUST. His research interests are in programming languages, compiler optimization and parallel programming. His work is focused on finding tractable and efficient algorithms for classical problems in verification and compiler optimization, and has been published in top-tier venues of the field such as OOPSLA and ASPLOS. He has also won the ACM SIGPLAN distinguished paper award of OOPSLA 2024. John is an active open-source contributor, with many contributions to projects like manifold, which is used by other popular open-source projects such as OpenSCAD, Godot Engine and Blender. He is also interested in designing and tinkering, from mechanical designs to electronics, and soldering to machining.