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.
Faculty:
Students:
Quynh Chau (M.S.): Instruction scheduling for power minimization
Charles Fu (Ph.D.): Faster optimal register allocation
Mark Heffernan (Ph.D.): Instruction scheduling technologies for heuristic and optimal schedulers
Chris Lupo (Ph.D.): Improved register allocation heuristics
Ghassan Shobaki (Ph.D.): Optimal global instruction scheduling
Victor Yip (Ph.D.): Improved instruction scheduling heuristics
Selected Publications:
-
"Post Register Allocation Spill Code Optimization", Christopher Lupo and
Kent Wilken. Proceedings of the International Symposium on
Code Generation and Optimization, March 2006, pages 244-255. Abstract
-
"Data-Dependency Graph Transformations for Instruction Scheduling",
Mark Heffernan and Kent Wilken. To appear in the Journal of
Scheduling. Abstract
-
"Optimal Superblock Scheduling Using Enumeration", Ghassan Shobaki and
Kent Wilken. Proceedings of the International Symposium on
Microarchitecture, December 2004, pages TBA. Abstract
-
"A Faster Optimal Register Allocator", Changqing Fu and Kent
Wilken. Proceedings of the International Symposium on
Microarchitecture, December 2002, pages 245-256. Abstract
-
"Fast Optimal Instruction Scheduling for Single-Issue Processors with
Arbitrary Latencies", Peter van Beek and Kent Wilken. Proceedings of
the International Conference on Principles and Practice of Constraint
Programming, November 2001, pages 625-639. Abstract
-
"Optimal Instruction Scheduling using Integer Programming", Kent
Wilken, Jack Liu, Mark Heffernan. Proceedings of the ACM Conference on
Programming Language Design and Implementation, June 2000, pages
121-133.
Abstract
-
"Precise Register Allocation for Irregular Architectures", Timothy Kong and
Kent Wilken. Proceedings of the International Symposium on
Microarchitecture, November 1998, pages 297-307. Abstract
-
"Optimal and Near-Optimal Global Register Allocation Using 0-1 Integer
Programming", David Goodwin and Kent Wilken. Software-Practice and
Experience, Aug. 1996, pages 929-965. Abstract