Síntese de Compiladores para Arquiteturas em ArchC

Síntese Automática de Compiladores para Arquiteturas Descritas em ArchC

Este trabalho concentrou-se no estudo da melhor forma para a síntese automática de compiladores para a linguagem C que produzam código para plataformas descritas na linguagem de descrição de arquiteturas ArchC. A construção de compiladores é uma tarefa tediosa e difícil. Mesmo adotando como ponto de partida um projeto preexistente de compilador redirecionável, isto é, construído para que seja facilmente estendível para gerar código para novas arquiteturas, é necessário ter profundo conhecimento específico do domínio de compiladores, da linguagem intermediária do compilador utilizado e da arquitetura alvo para a qual o código será gerado. Para evitar que o modelo ArchC dependa da inclusão de informações específicas de um compilador para que seja possível redirecionar um compilador para a arquitetura em questão, adotou-se um mecanismo com maior grau de automação, em que o usuário descreve apenas informações declarativas sobre o conjunto de instruções. É de responsabilidade do sistema, então, buscar a melhor forma para criar o compilador.

O elevado grau de automatização cria diferentes compromissos. A tarefa do usuário é bastante facilitada, ao preço da flexibilidade reduzida, uma vez que muitas decisões sobre o projeto do compilador são tomadas automaticamente. Para viabilizar a síntese de um compilador para um modelo de arquitetura descrito em ArchC, foi utilizado o projeto do compilador LLVM, que é didático, escrito em C++ utilizando conceitos de orientação a objetos e criado para ser facilmente redirecionado. Por esse motivo, a síntese de compilador reduziu-se ao problema de geração do backend do compilador LLVM pois, utilizando a infraestrutura LLVM, o usuário dispõe de um compilador C completo para todas as arquiteturas que possuem um backend LLVM.

Como a API LLVM dispõe de algoritmos básicos que todo backend utiliza, como alocador de registradores e um escalonador de instruções padrão, este trabalho focou-se na tarefa inicial, mas desafiadora, de geração de um seletor de instruções a partir de descrições das instruções da arquitetura alvo. Essas descrições não possuem informação sobre a linguagem intermediária LLVM e, portanto, esta conexão é realizada pela ferramenta desenvolvida de geração automática. Neste contexto, foi estudado o problema da programação automática para criação de pequenos trechos de código em linguagem de montagem que realizam a computação equivalente a fragmentos da linguagem intermediária LLVM.

O problema da programação automática pode ser resolvido com um provador de teoremas simplificado, na qual a semântica do fragmento a se programar é a instância do problema. Axiomas ou regras de transformação que mantêm a equivalência entre duas árvores de expressão são então utilizados para manipular a instância original a fim de provar sua equivalência semântica com as instruções da máquina alvo. Do ponto de vista de implementação, esta solução foi implementada com um algoritmo de busca com uma abordagem da área de inteligência artificial.

Nesse contexto, como o problema de programação automática e, mais amplamente, da geração de código, são problemas intratáveis, é importante que simplificações razoáveis e heurísticas eficientes sejam utilizadas para que um computador consiga, de fato, encontrar soluções aproximadas em tempo hábil. Por ser crucial para a solução do problema da programação automática e, por conseguinte, da geração automática de backends, técnicas heurísticas foram propostas para acelerar o algoritmo de busca. A aplicação de apenas uma regra por nível da árvore de expressão, a limitação na profundidade da recursão, o uso de uma tabela de espalhamento para armazenar resultados anteriores da busca pelo qual se descobriu um caminho infrutífero da busca bem como a paralelização focada na execução de processadores de múltiplos núcleos foram técnicas utilizadas para este fim. Combinadas, conseguem fazer com que a programação automática de 57 padrões da linguagem intermediária da infraestrutura LLVM não somente seja possível, mas que seja alcançada em menos de 20 segundos para a maioria das arquiteturas modeladas com a descrição de instruções proposta.

Ainda que o problema da programação automática seja resolvido e uma implementação em instruções da máquina alvo seja encontrada para todos os padrões escolhidos para cobrir a linguagem intermediária da infraestrutura LLVM, é necessário converter tais resultados em código C++ que será utilizado para construir automaticamente todo o backend para a nova arquitetura na infraestrutura LLVM.

Trabalhos Futuros

Após a criação do backend, testes de compilação de programas do benchmark Mibench atestaram seu funcionamento correto e revelaram que a qualidade do código gerado pelo backend pode se comparar com a de código de compiladores consagrados, caso seja utilizado um otimizador peephole para realizar substituições simples de algumas sequências ineficientes. Portanto, a geração automática do otimizador peephole é um trabalho futuro importante para o projeto e ainda pode contar com a infraestrutura de resolução do problema da programação automática já criada. Com esta infraestrutura, é possível utilizar um sistema de regras mais abrangente que, apesar de diminuir a velocidade de busca, irá se concentrar em achar trechos mais eficientes e que contribuam para a construção do otimizador peephole. Não só a otimização de código é um ramo de pesquisa futuro que se abre com o uso desta infraestrutura, mas também a geração automática de tradutores de binário a partir de modelos descritivos das instruções dos conjuntos de instrução envolvidos.

Dessa forma, tanto a geração automática de otimizadores para arquiteturas descritas em ArchC como a geração automática de tradutores binários são trabalhos futuros viabilizados com este projeto. Outro trabalho futuro possível é a realização da extração de semântica através da tradução do código C++ SystemC que descreve o comportamento de uma instrução do modelo comportamental ArchC para a representação de semântica adotada.

Apesar de ser tecnicamente desafiante realizar esta tradução, uma vez que diversas simplificações seriam necessárias para extrair uma árvore de expressão simples o suficiente para ser útil na geração de código, ainda seria possível gerar a tradução parcialmente e oferecê-la ao projetista como um ponto de partida para diminuir a quantidade de trabalho necessária para descrever o comportamento das instruções com árvores de expressão. Esta tarefa diminuiria ainda mais a quantidade de informações extras necessárias no modelo ArchC para a geração de backend de compilador.