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

Detalhes bibliográficos
Ano de defesa: 2011
Autor(a) principal: Andre Luiz Camargos Tavares
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Minas Gerais
UFMG
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/1843/SLSS-8GPQJ2
Resumo: 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%.