Parameterized algorithms for optimal compiler optimization

PhD Thesis Proposal Defence


Title: "Parameterized algorithms for optimal compiler optimization"

by

Mr. Chun Kit LAM


Abstract:

Compiler optimization is important for generating high-performance code from 
high-level languages. Ideally, the compiler should be able to generate 
optimal machine code based on certain cost model. Unfortunately, most 
compiler optimization problems were proven to be NP-hard. For example, 
Chaitin et al. showed that one can reduce graph coloring to spill-free 
register allocation. Most compiler optimization research since then only 
focused on heuristics for better code optimization.

This thesis investigates the potential of using techniques from parameterized 
algorithms for practical, optimal compiler optimizations. First, we present a 
new pathwidth upper bound on structured control flow graphs, which enabled a 
simpler and more efficient optimal spill-free register allocation algorithm 
implementation. Second, we develop an optimal extraction algorithm for sparse 
e-graphs, which is faster than state-of-the-art integer linear programming 
solvers for optimal e-graph extraction. Third, we present SPL-decomposition 
for structured control flow graphs, which is easy to compute and enables 
faster algorithms for register allocation and program analysis.


Date:                   Thursday, 21 May 2026

Time:                   12:00noon - 2:00pm

Venue:                  Room 2128A
                        Lift 19

Committee Members:      Dr. Lionel Parreaux (Supervisor)
                        Dr. Amir Goharshady (Co-supervisor, Oxford)
                        Prof. Siu-Wing Cheng (Chairperson)
                        Dr. Jiasi Shen