Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/JCES-AVKLSP| Type: | Dissertação de Mestrado |
| Title: | Dynamic dispatch of context-sensitive optimizations |
| Authors: | Gabriel Poesia Reis e Silva |
| First Advisor: | Fernando Magno Quintao Pereira |
| First Referee: | Edson Borin |
| Second Referee: | Mario Sergio Ferreira Alvim Junior |
| Abstract: | 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. |
| Subject: | Linguagem de programação (Computadores) Otimização combinatória Compiladores (Computadores) Computação |
| language: | Português |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/JCES-AVKLSP |
| Issue Date: | 4-Aug-2017 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| gabrielpoesiareisesilva.pdf | 1.26 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.