Algoritmos para escalonamento de instruções e alocação de registradores na infraestrutura LLVM

Abstract

O objetivo deste trabalho _e apresentar uma proposta integrada para Escalonamento de Instruções e Alocação de Registradores baseada em Isomorfismo de Subgrafos implementada no compilador LLVM. A contribuição principal deste trabalho _e mapear as fases de escalonamento instruções e alocação de registradores como um problema de Isomorfismo de Subgrafos. A resolução _e baseada na modelagem dos recursos de hardware (unidades funcionais, banco de registradores e suas interconexões) como um grafo base e a representação do programa de entrada como um Directed Acyclic Graph (DAG) com vértices representando instruções, operandos de entradas e saída, e as arestas as dependências entre esses vértices. O DAG de entrada possui atributos especiais para indicar a lat^encia de instruções, operandos especiais (registradores de instruções especificas/dedicadas) e dependências de controle. As entradas para o algoritmo são compostas por um DAG G1 e um grafo base G2 que representa a arquitetura alvo. A saída é um grafo G0 2 isomórfico para G1. Outra contribuição é a definição de grafo base como uma ferramenta para modelar diferentes modelos arquiteturais de processadores. A técnica tem-se mostrado particularmente viável para arquiteturas com restrições de registradores e interconexões. No entanto, pode-se vislumbrar extensões para arquiteturas Very Long Instruction Word (VLIW), maquinas escalares e até mesmo processadores que exploram paralelismo em nível de instrução utilizando outros modelos de execução. Experimentos foram realizados visando a validação, caracterização do algoritmo e a comparação com outras técnicas existentes na infraestrutura de compilação LLVM. Os resultados mostram que o algoritmo proposto, apesar de necessitar melhorias quanto ao tempo de compilação, pode obter ganhos de desempenho no código final gerado.

ABSTRACT - This work aims at providing an integrated Instruction Scheduling and Register Allocation algorithm based on Subgraph Isomorphism theory implemented on the LLVM Compiler. The main contribution of this work is the mapping of instruction scheduling and register allocation as a Subgraph Isomorphism problem. The approach is based on the modelling of the hardware resources (functional units, register les and their interconnections) as a base graph, and the representation of the input program as Directed Acyclic Graphs (DAG) with vertices representing program instructions, input and output operands, and edges representing the dependences between two vertices. This input DAG has also special attributes to indicate the instruction latency, special operands (speci c/dedicated instruction registers), and control dependencies. The algorithm input comprises a DAG G1 of the program and a base graph G2 that represents the target architecture. The output is a graph G0 2 isomorphic to G1. Another contribution is the de nition of base graphs as a tool to model di erent computer architectures to be used by the technique. The technique has shown to be a viable alternative for constrained register and interconnection processor architectures. In addition, the technique can be also extensible for architectures ranging from Very Long InstructionWord (VLIW), scalar, and even processors exploiting instruction level parallelism by using non-conventional execution models. Experiments have been performed to validate and characterize the algorithm. Other experiments have been performed to compare our proposal to classical techniques existing in the LLVM compiler. The results show that proposed algorithm, in spite being a subject for future investigations regarding compilation time, can provide performance gains for programs.