Symbolic range analysis of pointers
Carregando...
Arquivos
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
Leonardo Barbosa e Oliveira
Laure Gonnord
Renato Antonio Celso Ferreira
Laure Gonnord
Renato Antonio Celso Ferreira
Resumo
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
Assunto
Compiladores (Computadores), Computação, Análise estática
Palavras-chave
Compiladores, Análise Estática, Análise de Ponteiros