Register allocation is an essential optimization for all compilers. A number of sophisticated register allocation algorithms have been developed over the years based on Graph Coloring. However, these algorithms pose three major limitations. First, construction of a full interference graph can be a major source of space and time overhead in the compiler. Second, the interference graph lacks information on the program points at which two variables may interfere. Third, effective combining of register allocation with instruction scheduling remains an open problem.
Dr. Sarkar’s research on register allocation has yielded the following results thus far in addressing the limitations listed above:
1. Introduction of Linear Scan (with Massimiliano Poletto) as a new approach to register allocation that avoids the space and time overhead of constructing an interference graph, making it an attractive algorithm for dynamic compilers and other environments where compile-time overhead is a bottleneck. Variants of the Linear Scan algorithm have been used in the Jikes RVM and LLVM optimizing compiler back-ends
2. Introduction of Extended Linear Scan (with Rajkishore Barik) to exploit program point information so as to make smarter spilling decisions than can be made by a Graph Coloring algorithm that uses an Interference Graph. This work also showed that the problem of determining whether or not a spill-free register allocation exists for a given program can be solved in time that is linear in the number of live intervals, which is found to be linear in the size of the input program in practice
3. Introduction of the “CRISP” approach (with Rajeev Motwani, Krishna Palem, and Salem Reyen) as a foundation for combining instruction scheduling and register allocation. This approach was combined with BURS-style instruction selection in a project on Register-Sensitive Selection, Duplication, and Sequencing of Instructions that included implementations in the IBM TOBEY and Jikes RVM back-ends.
A list of Dr. Sarkar’s publications related to Register Allocation can be found here.