Alocação de registradores desacoplada baseada em coloração de grafos com compartilhamento hierárquico

Abstract

Recent results have shown how to do graph-coloring-based register allocation in a way that decouples spilling from register assignment. This decoupled approach has two main advantages: rst, it simplies register allocation algorithms. Second, it might keep more variables in registers, instead of sending them to memory. In spite of these advantages, the decoupled model using the graph coloring approach, as described inprevious works, do not handle register aliasing, a phenomenon present in architectures such as x86, ARM and Sparc. An important obstacle is the fact that existing decoupled algorithms have to perform extensive live range splitting to deal with aliasing, increasing the input graphs by a quadratic factor. Such allocators would be inecient in terms of memory consumption, compilation time and the quality of the code they produce.In this thesis we introduce a number of techniques that overcome this obstacle. We describe a spill test that deals with aliasing better than Kempe's traditional simpli cation test. We use heuristics to merge or rather avoid splitting live ranges whenever possible, and we adapt well-known coalescing tests to the world of aliased registers. In order to determine the best interference representation for the techniques, we have studied the following options: Single Static Assignment (SSA), Single Static Information (SSI), extended SSA (e-SSA) and Elementary Form. In this process we have developed an algorithm to eficiently create SSI and e-SSA. We have empirically validated our results by showing how our techniques improve two well known graph coloring based allocators that deal with aliased registers, namely Smith et al.'s extension [SRH04] of the Iterated Register Coalescer (IRC) [GA96], and Bouchez et al.'s brute force (BF) method [BDR08]. Running our techniques on a subsetSPEC CPU 2000, we have been able to reduce the size of the interference graphs that the allocators would require by a factor of 4, and we have improved the quality of IRC, in terms of proportion of copies left in the assembly program, from 1.5% to 0.54%.