Interdependência entre alocação de registradores e escalonamento de instruções: estudo sistemático e verificação de soluções

Abstract

Register allocation and instruction scheduling are two important tasks performed by a compiler. The first defines which program values should be allocated in the machine physical registers and associates those values with the available physical registers. The second schedules the program instructions, moving them along the code, so that the resulting instruction sequence is executed faster than the original instruction sequence. However, these two tasks are involved in a prioritization problem: if the allocation task is executed before the scheduling task, false dependencies may arise between instructions, preventing the optimal scheduling. On the other hand, if the scheduling task is performed prior to the allocation task, program values can remain alive for a large number of instructions, increasing the chances of spilling values into memory. This prioritization problem, also known as the problem of the interdependence between register allocation and instruction scheduling tasks, has gained relevance with the emergence of RISC architectures and with the increasing importance of compilers for efficient code generation. The work described in this dissertation takes over this problem in two distinct and complementary aspects: a theoretical one, realized through a systematic literature review; and a practical one, realized by the implementation of Pinter’s approach into LLVM, an approach that aims to reduce the impact that the interdependence between the two tasks produces on the generation of efficient code. The results achieved, mainly the practical results, indicate that the interdependence between the two tasks remains a relevant problem and show that the realized implementation was able to generate more efficient codes, when compared to codes generated by LLVM and Microsoft Visual Studio compilers