This project consists in the design and implementation of a non-iterative algorithm for register allocation based on graph coloring. We present a simple, linear-time algorithm which is competitive with the iterated register coalescing strategy of George and Appel. We base the new algorithm on the observation that more than 95% of the methods in the Java 1.5 library have chordal interference graphs. A greedy algorithm can color a chordal graph optimally in linear time, and we can easily add powerful heuristics for spilling and coalescing. Our experimental results show that the new algorithm produces better results than iterated register coalescing for settings with few registers and comparable results for settings with many registers. The implementation of the proposed algorithm, as well as our implementation of the iterated register coalesing algorithm can be downloaded in the links below.

Alunos envolvidos: Graduação: (0) / Especialização: (0) / Mestrado acadêmico: (0) / Mestrado profissionalizante: (0) / Doutorado: (1) .

Integrantes: Fernando Magno Quintão Pereira – Integrante / Jens Palsberg – Coordenador.

Número de produções C, T A: 5