Advanced Compiler Optimization

Our group is interested in improving the science and technology for important compiler optimizations, including instruction scheduling and register allocation.

Instruction scheduling and register allocation, along with many other important compiler optimization problems, are NP-hard or NP-complete. Roughly this means that given a worst-case instance of the problem, the time to compute the problem instance's exact solution will be exponential in the size of the problem. The theoretical complexity of these problems has lead researchers to focus almost exclusively on heuristics solutions for these problems. As compiler optimization scientists we ask the fundamental question: do worst-case instances of these problems occur in practice? If not it may be possible to exactly solve practical problem instances in reasonable time using some combinatorial optimization method.

As compiler optimization technologists, we interested in developing practical technologies that solve these important compiler optimizations more precisely than existing technologies.



Selected Publications: