Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/ESBF-AEDQPR| Type: | Dissertação de Mestrado |
| Title: | Symbolic range analysis of pointers |
| Authors: | Vitor Mendes Paisante |
| First Advisor: | Fernando Magno Quintao Pereira |
| First Co-advisor: | Leonardo Barbosa e Oliveira |
| First Referee: | Leonardo Barbosa e Oliveira |
| Second Referee: | Laure Gonnord |
| Third Referee: | Renato Antonio Celso Ferreira |
| Abstract: | Análise de ponteiros é uma das técnicas mais fundamentais que compiladores utilizam para otmizar linguagens com ponteiros. No entanto, mesmo com toda a atenção que este tópico já recebeu, as propostas do estado da arte atual presentes em compiladores ainda lidam com desafios em relação à precisão evelocidade.Em particular, aritmética de ponteiros, um fator chave de linguagens como C e C++, ainda precisa de soluções satisfatórias neste campo.Este trabalho apresenta um novo algorítmo para análise de ponteiros para resolver esse problema. O ponto chave da nossa proposta é combinar análise de ponteiros com análise simbólica de largura de inteiros.Tal combinação nos permite desambiguar campos dentro de vetores e estruturas de dados, de maneira efetiva obtendo maior precisão do que algorítmos tradicionais.Para validar nossa técnica, implementamos nosso algorítmo no compilador LLVM.Testes em uma vasta gama de benchmarks nos mostraram que podemos desambiguar vários tipos de estruturas em C que as análises atuais do estado da arte não conseguem lidar. Em particular, podemos desambiguar 1.35x mais comparações do que as análises de ponteiros presentes no LLVM.Além, nossa análise é rápida: podemos lidar com um milhão de instruções em assembly em 10 segundos. |
| Abstract: | Alias analysis is one of the most fundamental techniques that compilers use to optimize languages with pointers. However, in spite of all the attention that this topic has received, the current state-of-the-art approaches inside compilers still face challenges regarding precision and speed. In particular, pointer arithmetic, a key feature in C and C++, is yet to be handled satisfactorily. This work presents a new alias analysis algorithm to solve this problem. The key insight of our approach is to combine alias analysis with symbolic range analysis.This combination lets us disambiguate fields within arrays and structs, effectively achieving more precision than traditional algorithms. We have implemented it on top of the LLVM compiler. Tests on a vast suite of benchmarks show that we can disambiguate several kinds of C idioms that current state-of-the-art analyses cannot deal with. In particular, we can disambiguate 1.35x more queries than the alias analysis currently available in LLV |
| Subject: | Compiladores (Computadores) Computação Análise estática |
| language: | Inglês |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/ESBF-AEDQPR |
| Issue Date: | 11-Aug-2016 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| vitormendespaisante.pdf | 1.08 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.