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

• Ano de defesa: 2013
• Autor(a) principal: Silva, Lucas da Costa
• Orientador(a): Santos, Ricardo Ribeiro dos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Compiladores (Programas de Computador); Algorítmos Computacionais; Compilers (Computer Programs); Computer Algorithms
• Link de acesso: https://repositorio.ufms.br/handle/123456789/2209

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.