Dynamic dispatch of context-sensitive optimizations
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Edson Borin
Mario Sergio Ferreira Alvim Junior
Mario Sergio Ferreira Alvim Junior
Resumo
Construir análises sensíveis ao contexto escaláveis é um problema que vem sendo frequentemente trabalhadopela comunidade de compiladores, com sucesso. Porém, a implementação de otimizações sensíveis ao contextocontinua sendo desafiadora. O principal problema que desencoraja os compiladores de implementarem taisotimizações é o crescimento no tamanho do código. Com clonagem de funções ou inlining, duas técnicas conhecidaspara a implementação de especializações sensíveis ao contexto, o tamanho do código pode crescer exponencialmenteno pior caso. Ambas as técnicas são baseadas em criar cópias especializadas do código para cada contexto.Contudo, as duas técnicas precisam criar cópias de todas as funções no caminho de chamadas que leva a cadaotimização, ainda que isto envolva copiar funções que não serão otimizadas. Neste trabalho, propomos uma soluçãopara este problema. Utilizando uma combinação de despacho dinâmico e uma máquina de estados para controlar as transiçõesentre os contextos dinamicamente, nosso método implementa otimizações completamente sensíveis ao contextonecessitando apenas copiar as funções que serão otimizadas, mas não o caminho de chamadas até elas.Apresentamos nossa abordagem em Minilog, uma linguagem mínima que possui todos os recursos necessários para aplicaro método proposto, e provamos sua corretude. Implementamos nosso método na infraestrutura de compiladores LLVM,utilizando-o para otimizar programas com propagação de constantes completamente sensível a contexto.Nossos experimentos nos benchmarks do LLVM Test Suite e do SPEC CPU2006 mostram que nosso método escala significativamentemelhor em termos de espaço que clonagem de funções, gerando binários em média 2.7x menores, adicionando em média 8.5x menosbytes ao implementar a mesma otimização. Os binários gerados utilizando nossa técnica tiveram performance muito semelhante aosgerados com clonagem tradicional.Além disso, utilizando essa classe de otimizações ainda pouco explorada, conseguimos speed-ups de até 20\% em algunsbenchmarks quando comparados a LLVM -O3.
Abstract
The compilers community has dedicated much time and effort in making context-sensitive analyses scalable, with great profit. However, the implementation of context-sensitive optimizations remains a challenge. The main problem is code size growth. Both function cloning and inlining are based on creating copies of all functions in the call path that leads to each optimization, even when that involves copying functions that are not optimized. We propose a solution for that problem. Using a combination of dynamic dispatch and a state machine to dynamically control the transitions between calling contexts, our method implements fully context-sensitive optimizations only needing to copy optimized functions. Experiments in the LLVM Test Suite and SPEC CPU2006 show our method scales better than cloning, using 8.5x less bytes to implement the same optimizations. We have also observed speed-ups of up to 20% on top of LLVM -O3 using fully context-sensitive constant propagation.
Assunto
Linguagem de programação (Computadores), Otimização combinatória, Compiladores (Computadores), Computação
Palavras-chave
Compiladores Otimizantes, Linguagens de Programação, Propagação de Constantes, Otimizações Sensíveis ao Contexto