Resumo: Os compiladores têm por função traduzir um programa em uma linguagem fonte para uma linguagem alvo, geralmente uma linguagem de máquina. Nessa tradução, encontrar a melhor correspondência entre as linguagens é um problema complexo, pelo tamanho do espaço de busca. Por tal complexidade, uma etapa de transformação de código é necessária, na qual algoritmos de transformação modificam o código tentando melhorá-lo sem alterar seu significado. O Problema de Seleção de Transformações (PST) consiste na busca das melhores transformações para um código de entrada, tal que o código final obtenha um bom desempenho. O estado-da-arte não possui estratégias que possibilitem soluções para o PST aplicáveis a usuários finais, pois o tempo de resposta é alto para tal aplicação. O objetivo deste trabalho é formular técnicas para encontrar efetivas sequências de transformações a serem aplicadas a um código de entrada, de forma a aumentar seu desempenho reduzindo o tempo de execução. Além disso, objetiva-se reduzir o tempo de resposta de forma que a solução para o PST se aproxime da utilização por usuários finais. Inicialmente, se explora a Variable Neighborhood Search (VNS) para solucionar o PST, compilando iterativamente cada código de entrada. A aplicação da VNS alcançou resultados até 15,72% melhores do que outra estratégia iterativa, conseguindo melhoria em todos os programas avaliados em relação ao melhor nível de transformação. Contudo, a compilação iterativa possui alto tempo de resposta. Assim, é necessário explorar técnicas de aprendizagem de máquina, que podem prover bons resultados baseadas em experiências anteriores do compilador. Dessa forma, esta dissertação explora diferentes caracterizações de programas para representar o conhecimento acumulado na aplicação de transformações, para então aplicar a um sistema de geração de código com Raciocínio Baseado em Casos (RBC), que escolhe determinada sequência para um programa de entrada. A representação do conhecimento é capaz de atingir 81% de proximidade do melhor resultado possível para os programas avaliados, enquanto o sistema RBC gera resultados 13,74% melhores do que o nível -O3, em um tempo de resposta 99% inferior ao de estratégias de compilação iterativa. A melhoria nas formas de recuperação de experiências anteriores conseguiu superar em 20,23% o desempenho obtido por outra estratégia comparada com um número de avaliações próximo.
Abstract: Compilers aims to translate a source language program to a target language, usually a machine language. Find the best correspondence between programming languages is a complex problem, due to the size of search space. Because of this complexity, a code transformation step is needed, where transformation algorithms modify the code, trying to improve it without semantic alterations. Despite, the result of the application of these algorithms depends on code particularities. The Transformations Selection Problem (TSP) consists of the search for the best transformations to an input code, such that target code achieves a good performance. The state-of-art does not have strategies that allow the application of TSP solutions to final users, because the response time is very high to this. This work aims to formulate techniques to find effective transformations sequences to be applied to an input code, in a way to increase programs performance reducing its execution time. Furthermore, another objective is to reduce the compiler response time, to approximate a TSP solution to final users application. Initially, the metaheuristic Variable Neighborhood Search (VNS) is explored to solve TSP, compiling iteratively each input code. VNS achieved results up to 15.72% better than another iterative strategy, reaching improvement for all evaluated programs compared to the best compiler transformation level. However, the iterative compilation demands a high response time. Therefore, it is necessary to explore machine learning techniques, which can provide good results based on compiler previous experiences, with a cost of an initial training phase. Thus, this work explores different program characterizations to represent the cumulated knowledge on transformations application, to formulate a code generation system with Case-Based Reasoning (CBR), which chooses certain sequence to an input program. The knowledge representation is capable to reach 81% of proximity of the best possible result to evaluated programs, while the CBR system generates results 13.74% better than -O3 level, on a response time 99% lower than iterative compilation techniques. The improvement of previous experiences recovering method obtained performances over 20.23% compared to another strategy with a close evaluations number. |