Projects

Register Allocation by Puzzle Solving

Chaitin et al. proved that spill-free register allocation is equivalent to graph coloring and hence NP-complete in general. However, in 2005 Bouchez, Brisk et al., and Hack proved independently that every program in static single assignment (SSA) form has a chordal interference graph that is colorable in linear time. This means that spill-free register allocation for SSA-form programs and machines with registers of uniform size executes in polynomial time. Open until now is the problem of spill-free register allocation in polynomial time for the common and more general setting of aliased registers and pre-coloring, which is found in the x86 architecture, for example. In this project we define the notions of elementary programs and elementary graphs, and we prove that aggressive live-range splitting produces elementary programs and that an elementary program has an elementary interference graph. Our main result is that an elementary graph is colorable in linear time, even in the presence of aliased registers and pre-coloring. The key to our linear-time algorithm is that we prove that coloring of an elementary graph can be viewed as solving a collection of puzzles, and that each puzzle can be solved in linear time. This means that spill-free register allocation for elementary programs, aliased registers, and pre-coloring executes in polynomial time. Further, our puzzle solver can easily be augmented with effective, linear-time heuristics for spilling. Our implementation generates Pentium code that is on average 11% faster than the code produced by gcc, even though it does not perform any form of global register coalescing. The produced code is of similar quality to the code generated by the slower Iterated Register Coalescing algorithm of George and Appel with extensions proposed by Smith-Ramsey-Holloway to handle register classes.

More details about this project

Wave and Deep Propagation for Pointer Analysis

We have designed, implemented and tested two new algorithms for solving inclusion based points-to-analysis. The first algorithm, the Wave Propagation Method, is a modified version of an early technique presented by Pearce et al.; however, it greatly improves on the execution of its predecessor. The second algorithm, the Deep Propagation Method, is a more light-weighted analysis, that requires less memory. We have compared these algorithms with three state-of-the-art techniques by Hardekopf-Lin, Heintze-Tardieu and Pearce-Kelly-Hankin. Our experiments show that Deep Propagation has the best average execution time across a suite of 17 large benchmarks, the lowest memory requirements in absolute numbers, and the fastest absolute times for benchmarks under 100,000 lines of code. The memory-hungry Wave Propagation has the best absolute running times in a memory rich execution environment, matching the speed of the best known points-to algorithms in large benchmarks. Additionally, wave propagation exposes more parallelism in pointer analysis, a fact that we hope to be able to explore in future implementations.

Google Summer of Code - Proposal

I want to implement the register allocation algorithm described in the paper "Register Allocation via Coloring of Chordal Graphs, Pereira and Palsberg, APLAS'05", using LLVM as the basic framework. The proposed algorithm relies on the fact that the interference graph of programs in SSA form are chordal. Such property allows to find the minimal number of registers necessary to compile a program in polynomial time. This project has been submitted to the Google Summer of Code initiative, and is now waiting to be evaluated.

More details about this project

Translation validation of Register Allocation Directives

Testing the implementation of register allocation algorithms is a difficult and time-consuming activity. Errors in the code generated by the register allocator tend to manifest sporadically, often many instructions past the problematic point. In this paper we formalize the concept of semantic consistency of register allocation directives. Also, we present a collection of data flow algorithms that statically validates the translation between two representations of a program: the first has an unbounded number of temporary variables, whereas the second can only use a limited number of registers. The need for this validation infrastructure emerged during the development of actual register allocators for the Strong ARM architecture, and its availability greatly improved our ability to trace errors in register allocation settings.

More details about this project

Register Allocation via Coloring of Chordal Graphs

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.

Ralf: the Register Allocation Framework

RALF is a framework for end-to-end evaluation of register allocators. Built on top of gcc, RALF enables evaluation and comparison of register allocators in the setting of an industrial-strength compiler. RALF supports modular plug-and-play of register allocators without modifying the compiler implementation at all. RALF provides any plugged-in register allocator with an intermediate program representation that is independent of the data structures of the framework. In return, the register allocator provides RALF with a set of register allocation directives. The contract between RALF and a register allocator is given by requirements on the intermediate program representation and the register allocation directives. RALF checks that the produced directives satisfy the requirements, thereby helping with finding bugs in a register allocator.

Discretionary Access in a Remote Method Invocation System

This project consist in the implementation of an object oriented middleware that allows the application developer to regulate the use of individual remote methods by means of access control lists. Such platform has been implemented as an instance of Arcademis, a framework for middleware development. The objective of this case study is twofold. Firstly, to demonstrate how frameworks and design patterns can be synergistically combined in order to facilitate the implementation of distributed software. Secondly, to point similarities between the architecture of object oriented middleware, such as Java RMI, and distributed authentication systems, such as Kerberos, in order to argue that discretionary access control can be added to the commercial middleware platforms as a natural extension of the remote method invocation paradigm.