Estratégias de solução para o problema de alocação de registradores em compiladores

Abstract

The main purpose of a compiler is to transform the code from a source language into a target language. To this end, the code generated by the compiler must make effective use of the limited processor resources. The set of registers is one of the most restricted resources in a processor. Therefore, the register allocation is an extremely important stage for the compilation process. Modern compilers generally abstract this problem as a Graph Coloring problem, because this type of approach captures some of the critical aspects of allocation. However, performing this coloration optimally, that is, in the best possible way, is characterized as an NP-Complete problem. Because known algorithms that solve these problems accurately have a worst-case exponential behavior, heuristics are adopted. They are able to give a good solution in an acceptable time. With the development of this paper, it was possible to compare different strategies and implement an alternative solution with equal or better results.