UNIVERSIDADE FEDERAL DO MATO GROSSO - LSCAD

Transcrição

UNIVERSIDADE FEDERAL DO MATO GROSSO DO SUL
Faculdade de Computação - FACOM
Curso de Bacharelado em Ciência da Computação
GERAÇÃO DE BACK-END LLVM PARA O PROCESSADOR
ρ-VEX
Richard Stéffano Martins da Silva
Orientação: Prof. Dr. Ricardo Ribeiro dos Santos
Monografia apresentada ao curso de Graduação em Bacharelado em Ciência da Computação na Universidade Federal do
Mato Grosso do Sul como requisito para a obtenção do tı́tulo
de Bacharel em Ciência da Computação.
UFMS/FACOM - Campo Grande - MS - AGOSTO/2013
Sumário
Lista de Figuras
iv
Lista de Tabelas
v
1 Introdução
2
2 Infraestrutura de Compilação LLVM
4
2.1
O Projeto LLVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
Arquitetura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3
Representação Intermediária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.4
Back-end LLVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.4.1
Descrição da Arquitetura Alvo . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4.2
Seleção de Instruções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.4.3
Emissão de código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2.5
3 Back-end LLVM para o Processador ρ-VEX
3.1
3.2
10
O Processador Softcore ρ-VEX . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.1.1
Organização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.2
Conjunto de Registradores . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.3
Conjunto de Instruções . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.1.4
Linguagem de Montagem ρ-VEX . . . . . . . . . . . . . . . . . . . . . . .
13
Desenvolvimento do Back-end LLVM para o Processador ρ-VEX . . . . . . . . .
14
3.2.1
TargetMachine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.2.2
Registro da Máquina Alvo . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.2.3
Descrição do Conjunto de Registradores . . . . . . . . . . . . . . . . . . .
16
3.2.4
Convenções de Chamada . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.2.5
Descrição do Conjunto de Instruções . . . . . . . . . . . . . . . . . . . . .
19
iii
3.3
3.2.6
TargetLowering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.2.7
Seletor de Instrução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2.8
VLIW Packetizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
3.2.9
Emissão de Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
24
4 Experimentos e Resultados
25
4.1
Validação do Back-End LLVM . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.2
Avaliação de Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
4.3
29
5 Conclusões e Trabalhos Futuros
5.1
31
Propostas para Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . .
A Código do Back-end LLVM para o Processador ρ-VEX
A.1 Definição e registro da máquina alvo ρ-VEX
32
33
. . . . . . . . . . . . . . . . . . . .
33
A.1.1 RVEXTagetMachine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
A.1.2 RVEXTargetInfo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
A.2 Conjunto e classes de registradores . . . . . . . . . . . . . . . . . . . . . . . . . .
35
A.3 Conjunto de Instruções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
A.4 Lowering
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
A.5 Seleção de Instruções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
A.6 Prólogo e Epı́logo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
A.7 Packetizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
A.8 Emissão de código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
Referências Bibliográficas
47
iv
Lista de Figuras
2.1
Visão em alto nı́vel da infraestrutura LLVM. . . . . . . . . . . . . . . . . . . . .
5
2.2
Exemplo de código em C e em LLVM IR. . . . . . . . . . . . . . . . . . . . . . .
6
2.3
Fases do LLVM na geração de código. . . . . . . . . . . . . . . . . . . . . . . . .
6
3.1
Organização do processador ρ-VEX. . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2
Formato de instrução do processador ρ-VEX. . . . . . . . . . . . . . . . . . . . .
12
3.3
Formatos de operações implementadas no processador ρ-VEX. . . . . . . . . . . .
13
3.4
Exemplo de instruções ρ-VEX. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
3.5
Visão das classes que compõe o back-end LLVM para o processador ρ-VEX. . . .
14
3.6
Trecho da especificação dos registradores ρ-VEX. . . . . . . . . . . . . . . . . . .
17
3.7
Definição das classes de registradores ρ-VEX. . . . . . . . . . . . . . . . . . . . .
17
3.8
Definição das classes de registradores ρ-VEX. . . . . . . . . . . . . . . . . . . . .
19
3.9
Formato RTYPE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.10 Formato ISTYPE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.11 Formato BRANCH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.12 Formato RTYPE BS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.13 Formato MEMTYPE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
3.14 Definição das classes de registradores ρ-VEX. . . . . . . . . . . . . . . . . . . . .
22
4.1
Visão do fluxo de validação do back-end LLVM para o ρ-VEX. . . . . . . . . . .
27
4.2
Speedup do desempenho do back-end LLVM sobre o VEX C Compiler. . . . . . .
28
v
Lista de Tabelas
3.1
Tipos de imediatos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.2
Convenção de uso para o conjunto de registradores GR do ρ-VEX. . . . . . . . .
18
4.1
Conjunto de programas utilizados para a validação do back-end LLVM. . . . . .
26
4.2
Programas Compilados com o LLVM. . . . . . . . . . . . . . . . . . . . . . . . .
28
4.3
Programas Compilados com o VEX C Compiler. . . . . . . . . . . . . . . . . . .
29
1
Capı́tulo 1
Introdução
A geração de código para uma máquina alvo é uma tarefa extensa que envolve várias atividades de considerável complexidade computacional (problemas NP-completos) como: seleção
de instruções, escalonamento de instruções, otimizações de código e alocação de registradores,
entre outras. Diante dessa dificuldade, a literatura da área de compiladores não dispõe de muitas
opções de infraestruturas de compilação que facilitam a reutilização de geradores de código para
outros conjuntos de instruções e/ou máquinas alvo.
A infraestrutura de compilação LLVM (Low Level Virtual Machine) [1, 2] é uma dessas
opções uma vez que constitui-se em um framework parametrizável e extensı́vel que possibilita
a adaptação de algoritmos tradicionais - já implementados nessa infraestrutura - de geração de
código para um conjunto de instruções e arquitetura. LLVM oferece um conjunto de interfaces
e classes que podem ser estendidas para acoplar e reutilizar algoritmos, já estabelecidos para
novas máquinas alvo.
Nesse cenário, este trabalho estende a capacidade de geração de código dessa infraestrutura de
compilação para o conjunto de instruções VEX [3, 4] e o processador ρ-VEX [5, 6]. O objetivo
principal deste trabalho em nı́vel de graduação é projetar e desenvolver uma infraestrutura
de geração de código (back-end), baseando-se no compilador LLVM, para compilar programas
aptos para execução no processador soft-core VLIW (Very Long Instruction Word ) [3, 7] e
reconfigurável denominado ρ-VEX. Para validar e avaliar esse novo mecanismo de geração de
código para o processador ρ-VEX, foi utilizado o conjunto de ferramentas de compilação e
simulação VEX. Esse conjunto de ferramentas possibilitou validar a geração de código, por meio
da simulação do código gerado em um simulador VEX e avaliar o desempenho por meio de
estatı́sticas geradas pela ferramenta de simulação VEX.
Diante do exposto, o texto desta monografia está organizado da seguinte forma:
• o Capı́tulo 2 apresenta a infraestrutura de compilação LLVM enfatizando as etapas e algoritmos de geração de código atualmente implementados e que fazem parte do compilador
LLVM.
• no Capı́tulo 3 é apresentado o processador ρ-VEX e o projeto e desenvolvimento da extensão do back-end LLVM para esse processador e conjunto de instruções VEX.
• O Capı́tulo 4 apresenta e discute todos os experimentos realizados e resultados obtidos
visando à validação e avaliação do backend para o processador ρ-VEX.
2
Introdução
3
• As conclusões deste trabalho assim como proposições para desenvolvimentos de trabalhos
futuros são apresentadas no Capı́tulo 5.
facom-ufms
Capı́tulo 2
Infraestrutura de Compilação LLVM
Este capı́tulo apresenta a infraestrutura de compilação LLVM, destacando o funcionamento
e organização de um back-end LLVM bem como os procedimentos necessários para a geração de
código para uma arquitetura e conjunto de instruções alvo. Na Seção 2.1 apresenta-se uma breve
introdução ao projeto LLVM. Na Seção 2.2 discute-se a organização e funcionamento do LLVM.
Na Seção 2.3 é apresentada a linguagem de representação intermediária do LLVM, a LLVM IR,
assim como sua importância na geração de código e consequentemente no desenvolvimento deste
trabalho. Por fim, na Seção 2.4, o back-end do LLVM é descrito.
2.1
O Projeto LLVM
O projeto LLVM é uma coleção modular de componentes reutilizáveis para construção de
compiladores e ferramentas para análise e otimização de código executável [1]. Teve inicio na
Universidade de Illinois e desde então cresceu como um projeto consistente, contando atualmente
com uma série de sub-projetos além de um número significativo de contribuintes espalhados por
diversos paı́ses. O código do LLVM é escrito em C++ e está sob a licença University of Illinois
at Urbana-Champaign (UIUC) Berkeley Software Distribution (BSD)-Style, que o torna um
software open-source.
A escolha do LLVM para o desenvolvimento deste trabalho está ligada principalmente a
sua arquitetura, que por sua vez, possui componentes bem definidos e claramente separados
proporcionando a integração de funcionalidades a componentes especı́ficos e a extensibilidade
do projeto com uma curva de aprendizado menor se comparada a outras infraestruturas de
compilação (como o GCC). Outras vantagens do projeto LLVM são sua linguagem independente,
comunidade de contribuidores ativa e documentação extensiva.
2.2
Arquitetura
O LLVM possui uma arquitetura de três fases [8], consistindo de um front-end, otimizador e
back-end. A Figura 2.1 representa em alto nı́vel a infraestrutura do LLVM.
O front-end fica responsável por analisar, validar e diagnosticar erros no código de entrada.
Em seguida, transforma o código analisado para uma linguagem de representação intermediária
4
5
Figura 2.1: Visão em alto nı́vel da infraestrutura LLVM.
(LLVM IR). Este processo é feito com um compilador estático tradicional. Atualmente, o LLVM
utiliza o Clang como front-end. Opcionalmente, pode ser usada a ferramenta DragonEgg, que é
um subprojeto do LLVM, e funciona como um plugin para o GCC substituindo seu otimizador
e back-end por módulos correspondentes no LLVM [9]. Dado o código de entrada na forma da
LLVM IR, ele é então (opcionalmente) melhorado através de uma série de passos de análise,
dos quais são coletadas informações que podem ser utilizadas para a otimização do código.
Finalmente, o back-end recebe o código resultante dos passos anteriores e o transforma em
código assembly ou código nativo (já link -editado) para arquiteturas especı́ficas de máquinas
como X86, ARM, PowerPC, Mips, Sparc, Xcore, entre outras.
2.3
Representação Intermediária
A representação intermediária do LLVM é o aspecto mais importante do projeto LLVM [8].
Ela é usada em todos os componentes da infraestrutura e tem como objetivo: ser um alvo fácil de
geração de código; ser independente da linguagem fonte ou da linguagem alvo; suportar diversos
tipos de análises e transformações eficientemente [2]. Em particular, a geração de código para
uma arquitetura alvo é feita a partir de um programa nessa representação (como visto na seção
anterior). Logo, seu entendimento é fundamental no processo de escrita de um back-end LLVM.
A LLVM IR é baseada em formatos de instruções Reduced Instruction Set Computer (RISC)
e na forma Static Single Assignment (SSA) [10]. Dessa forma, é próxima de uma linguagem
de montagem, porém suficientemente “alto nı́vel” para que o conjunto de análises e otimizações
tradicionais presentes na literatura possam ser implementados [1]. Sendo uma linguagem tipada,
suporta tipos primitivos e compostos habituais apresentados em linguagens de programação
como C, além de vetores de inteiros (e de ponto flutuante) de tamanho fixo.
Programas nessa linguagem são compostos de módulos, cada um dos quais equivale a uma
unidade de compilação. Cada módulo é composto por funções, variáveis globais e entradas da
tabela de sı́mbolos. Os módulos podem ser combinados com o linker do LLVM (llvm-ld). Uma
função é uma lista de blocos básicos, cada um iniciado com um rótulo. Um bloco básico é
uma lista de instruções, que por sua vez podem ser classificadas como: instruções de término,
operações binárias, operações bit a bit, instruções de memória, entre outras. Na Figura 2.2 há
um exemplo de código em C e a respectiva versão em LLVM IR.
facom-ufms
6
Figura 2.2: Exemplo de código em C e em LLVM IR.
2.4
Back-end LLVM
Um back-end LLVM consiste em um conjunto de componentes reutilizáveis responsáveis por
transformar o código na representação intermediária em código assembly ou diretamente em
código binário executável. Destes componentes destacam-se:
• Conjunto de interfaces abstratas que especificam propriedades da arquitetura alvo;
• Classes que modelam o código de máquina independente da arquitetura alvo. Por exemplo:
instruções, funções e registradores;
• Algoritmos independentes da arquitetura alvo, implementados como passos da geração de
código. Os algoritmos de alocação de registradores são um exemplo.
O processo de geração de código para uma arquitetura alvo baseia-se em uma série de passos
de análise e transformação, responsáveis por gradualmente produzir o código de máquina final.
A Figura 2.3 representa uma visão abstrata dos estágios do back-end LLVM.
LLVM
Front-end
Seleção de Instrução
Escalonamento
Fast
Otimização
ListScheduling
Back-end
Alocação de Registradores
Fast
Linear Scan
PBQP
Inserção de código Prólogo/Epílogo
Otimizações tardias
Greedy
Emissão de código
Assembly
Código nativo
Figura 2.3: Fases do LLVM na geração de código.
A geração de código está dividida nos seguintes estágios [1]:
facom-ufms
7
• Seleção de instrução: o primeiro passo do procedimento de geração de código transforma a representação intermediária em um grafo de instruções “legalizado”, que é uma
representação da LLVM IR na forma de grafo, utilizando apenas instruções nativas da
arquitetura alvo;
• Escalonamento: recebe o grafo de instruções e determina uma ordem para elas. O código
é então emitido na forma SSA;
• Otimização em código de máquina baseado em SSA: fase opcional que opera sobre
a forma SSA produzida no passo anterior. Um exemplo de otimização nessa fase é a
peephole [?];
• Alocação de registradores: todas as referências a registradores virtuais são eliminadas
substituindo-os por registradores fı́sicos. Também é realizada a emissão de intruções de
leitura e escrita na memória, quando necessário;
• Inserção de código prólogo/epı́logo: códigos de prólogo e epı́logo podem ser inseridos
nessa fase. As localizações de referências abstratas são removidas;
• Otimizações tardias: otimizações que operam no código final de máquina são realizadas
nessa fase;
• Emissão de código: a fase final tem como saı́da o código em formato assembly ou em
código de máquina.
Além destes, um back-end em particular pode adicionar mais passos no processo para algum
requisito especı́fico (como otimizações de código especı́ficas da arquitetura, escalonamento de
instruções preferenciais, entre outros).
Nas próximas seções, serão discutidos em mais detalhes os componentes pertecentes ao gerador de código que são relevantes para o desenvolvimento de um novo back-end LLVM.
2.4.1
Descrição da Arquitetura Alvo
As descrições de todas as caracterı́sticas da arquitetura alvo são concentradas em um conjunto
de classes que implementam interfaces abstratas em C++, definidas no módulo de geração
de código do LLVM. Os métodos virtuais destas interfaces permitem que a parte genérica do
gerador de código consiga trabalhar com os detalhes de cada arquitetura. A implementação
de certas interfaces para cada back-end LLVM é uma tarefa mecânica, envolvendo a definição
de muitos métodos que retornam informações simples ou repetitivas. Para introduzir diversas
funcionalidades que facilitam este tipo de tarefa, o projeto LLVM utiliza uma linguagem de
descrição de dados denominada TableGen [1].
A linguagem de descrição TableGen é responsável por transformar uma descrição textual de
caracterı́sticas da arquitetura alvo em código C++, utilizado pelo back-end. Com a TableGen
são descritos: conjunto de registradores; conjunto de instruções; convenções de chamada; regras
de escalonamento (itinerários); e demais informações estáticas das arquitetura;
Uma especificação no formato TableGen consiste de um arquivo contendo descrições de dois
tipos de entidades básicas: registros e classes. Um registro é um identificador associado a uma
lista de atributos e seus respectivos valores. Uma classe funciona como um template para a
facom-ufms
8
construção de registros, agregando informações que se repetem entre diversos registros. Os
valores podem ser de tipos primitivos como inteiros, booleanos e strings, como também de tipos
compostos, como grafos completos. Por exemplo: pode-se definir uma classe que descreve um
formato de instruções e suas caracterı́sticas (como tipo e número de operandos), e instanciar tal
classe para cada instrução pertencente a esse formato, onde uma instancia (registro) define as
caracteristicas unicas dessas instruções (como mnemônico, operação, etc).
2.4.2
Seleção de Instruções
A etapa de seleção de instruções é responsável por transformar as instruções da representação
intermediária em instruções da arquitetura alvo. Existem várias maneiras descritas na literatura
para realizar esse passo da geração de código. O LLVM utiliza um seletor de instruções baseado
em um grafo acı́clico direcionado, denominado SelectionDAG. O SelectionDAG é uma abstração
do código na representação intermediária, que permite uma seleção de instrução utilizando
técnicas automáticas, além de ser adequado em outras fases da geração de código, em especial,
no escalonamento de instruções.
Os nós de um SelectionDAG pertencem a duas classes: nós de operação e nós de ordenação.
Os primeiros representam uma operação de código, onde os seus operandos são arestas direcionadas para os nós que definem os operandos. Os nós de ordenação são nós fictı́cios inseridos
para controle de fluxo.
A seleção de instruções apresenta as seguintes etapas:
• Construção do DAG: a primeira versão do SelectionDAG é construı́da diretamente do
código em LLVM IR. Esta primeira versão é denominada “ilegal” pois utiliza instruções e
tipos de dados que não são suportados pela arquitetura alvo;
• Otimizações genéricas (A): são realizas simplificações no SelectionDAG;
• Legalização: transforma o SelectionDAG e elimina o uso de instruções e tipos de dados
não pertencentes a arquitetura alvo.
• Otimizações genéricas (B): novamente são realizadas simplificações no SelectionDAG
para eliminar as redundâncias que possam vir a ser introduzidas pelo processo de legalização do grafo.
• Seleção: transforma o SelectionDAG em um grafo no qual todos os nós padrões utilizam
instruções da arquitetura alvo.
• Escalonamento: realiza uma ordenação completa para as instruções do SelectionDAG
legalizado.
Após este processo, o código já utiliza instruções da plataforma alvo, porém ainda utiliza
registradores virtuais e apresenta redundâncias que serão eliminadas em passos de otimização
posteriores.
2.4.3
Emissão de código
Após a alocação de registradores e as otimização no código, o gerador de código do LLVM
emitirá um arquivo texto contendo o código final em linguagem de máquina. Para produzir este
facom-ufms
9
arquivo, o gerador consulta uma classe do back-end responsável por informar as caracterı́sticas
sintáticas da linguagem de montagem. O componente emissor assume um conjunto mı́nimo de
diretivas e construções para: declarar e definir dados, instruções, macros, rótulos, etc.
2.5
Considerações Finais
Este capı́tulo apresentou todas as informações acerca da infraestrutura de compilação LLVM
necessárias para o desenvolvimento de um back-end. O entendimento da estrutura e funcionamento do LLVM é de fundamental importância, pois estes conceitos formam a base deste trabalho. O Capı́tulo 3 detalha o processo de desenvolvimento do back-end LLVM para o processador ρ-VEX , assim como todas as informações pertinentes ao processador necessárias para tal
atividade.
facom-ufms
Capı́tulo 3
Back-end LLVM para o Processador
ρ-VEX
Este capı́tulo apresenta e discute o projeto e desenvolvimento do back-end para o processador ρ-VEX na infraestrutura de compilação LLVM. Apresentar-se-ão desde as principais caracterı́sticas do processador ρ-VEX até os detalhes da implementação do back-end desenvolvido.
A Seção 3.1 apresenta o processador ρ-VEX e as caracterı́sticas importantes para a construção
do back-end. A Seção 3.2 detalha as especificações do back-end.
3.1
O Processador Softcore ρ-VEX
O ρ-VEX [5, 6] é um processador VLIW (Very Long Instruction Word ) de código aberto, que
permite a extensibilidade de sua arquitetura junto a operações reconfiguráveis. A arquitetura do
processador ρ-VEX é baseado na Instruction Set Architecture (ISA) VEX [3, 4], que por sua vez é
inspirada na ISA da famı́lia de processadores HP/ST Lx [3] (o mesmo usado para processadores
ST200) e oferece uma plataforma tecnológica escalável para processadores embarcados VLIW.
Assim como outros processadores baseados na ISA VEX, o ρ-VEX pode ser amplamente utilizado
em sistemas embarcados através da extesão de sua arquitetura.
Acompanham o processador um conjunto de ferramentas de geração de código e simulação,
que contêm um compilador C, bibliotecas ANSI C, ferramentas para facilitar o processo de
profiling de código, um simulador em software (disponibilizado pela HP [4]) e o montador ρASM.
Apesar da existência de ferramentas para geração e simulação de código VEX, tais ferramentas não suportam a compilação e simulação de uma variedade de programas para o processador
ρ-VEX. Outra limitação está na ausência de ferramentas de link -edição, forçando a remoção
de todas as chamadas de funções presentes em bibliotecas externas. Todas as funções em um
programa devem ser expandidas inline na função main de forma a preservar o endereçamento
global de variáveis. Nas próximas subseções a organização do processador ρ-VEX é descrita em
detalhes.
10
Back-end LLVM para o Processador ρ-VEX
3.1.1
11
Organização
O processador ρ-VEX implementa uma arquitetura Harvard [?] e possui uma arquitetura
VLIW minimalista, que não possui unidade de gerenciamento de memória nem unidade para
cálculo de números de ponto-flutuante, o endereçamento na memória é realizado com referências
absolutas, não há implementação de caches, mecanismos de predição de desvios e não há bancos
de registradores distribuı́dos.
Apesar das limitações de sua atual implementação, o processador ρ-VEX possui uma arquitetura extensı́vel e reconfigurável possibilitando a adição de novas funcionalidades e consequentemente o suporte a novas aplicações.
A microarquitetura do ρ-VEX consiste em uma via de dados de quatro estágios, onde as
operações são buscadas, decodificadas e despachadas para unidades de execução individuais.
Após processadas, os resultados das instruções são armazenados na memória de dados ou conjunto de registradores. Como sua configuração é baseada em uma máquina VEX 1-cluster
padrão [3], o ρ-VEX dispõe das seguintes unidades funcionais: quatro unidades lógicas e aritméticas (ALUs), duas unidades de multiplicação 16 por 32 bits (MULs), uma unidade de
controle (CTRL) e uma unidade de memória (MEM). A Figura 3.1 apresenta a organização do
processador ρ-VEX.
PC
GR
CTRL
A
Memória
de
Instruções
A
Fetch
Decode
M
Execute
A
Writeback
M
Memória
de
Dados
A
BR
MEM
ρ-VEX
Figura 3.1: Organização do processador ρ-VEX.
3.1.2
Conjunto de Registradores
A arquitetura do ρ-VEX possui dois bancos de registradores: Registradores Gerais (General Registers, ou GR) e registradores de branch (Branch Registers, ou BR). Os registradores
gerais formam um conjunto de 32 registradores de 32 bits, indexados de 0 a 31, usados por
instruções lógico-aritméticas e de memória. Os registradores de branch formam um conjunto
de 8 registradores de 1 bit, indexados de 0 a 7, usados para armazenar resultados booleanos
de operações de comparação e lidos em operações de desvio condicional. Não existe uma convenção de uso de registradores especı́fica para o ρ-VEX que segue a convenção da ISA VEX.
Dessa forma, para este trabalho foram definidas convenções de uso para os registradores da
arquitetura. Na Seção 3.2 a convenção utilizada é descrita em detalhes.
facom-ufms
Tipo de imediato
Sem imediato
Short immediate
Branch offset immediate
Long immediate
12
Tamanho
N/A
9 bit
12 bit
32 bit
Immediate switch
00
01
10
11
Tabela 3.1: Tipos de imediatos.
3.1.3
Conjunto de Instruções
O conjunto padrão de operações VEX consiste de 73 operações (excluindo NOP – no operation), sendo 42 operações de lógica e aritmética, 11 operações de multiplicação e divisão de
inteiros, 11 operações de controle e 9 operações de memória. Além disso, não há suporte a
números em ponto flutuante [3].
Para a implementação do processador ρ-VEX , o conjunto original de instruções foi estendido
com mais duas operações: STOP e LONG IMM. A primeira informa para o processador ρ-VEX parar
de buscar instruções da memória de instruções. A segunda é usada quando operandos long
immediate são usados. Opcodes para duas operações de transferência de dados inter-clusters
(SEND e RECV) descritos na ISA VEX foram reservados, mas não são usados, já que a atual
implementação do ρ-VEX suporta apenas 1-cluster de uma máquina VEX.
Uma instrução ρ-VEX possui tamanho de 16 bytes (128 bits) e seu formato é apresentado
na Figura 3.2. Ela é formada por quatro sı́labas (operações), cada uma com quatro bytes (32
bits). Sua organização é dada a seguir:
• A sı́laba zero pode conter uma operação lógico-aritmética ou de controle;
• As sı́labas um e dois podem conter operações lógico-aritmética ou de multiplicação/divisão;
• A sı́laba três pode conter uma operação lógico-aritmética ou de memória;
As posições das sı́labas na instrução ρ-VEX são equivalentes a quantidade de unidades funcionais disponı́veis para uso e suas respectivas posições no estágio de execução.
63
95
127
sílaba 3
{ALU, MEM}
sílaba 2
{ALU, MUL}
0
31
sílaba 1
{ALU, MUL}
sílaba 0
{ALU, CTRL}
Figura 3.2: Formato de instrução do processador ρ-VEX.
A Figura 3.3 mostra os possı́veis formatos das operações. Nos sete bits mais significativos
encontram-se o campo dos opcodes. Cada sı́laba tem um campo de immediate switch, consistindo
de 2 bits, que por sua vez descrevem o tipo do imediato que a operação contém (a Tabela 3.1
apresenta os tipos de imediatos que podem ser utilizados). Nos bits 22 a 2 estão presentes
os operandos usados pela operação que podem ter organizações especı́ficas conforme o valor
presente no campo immediate switch.
Os últimos dois bits de cada operação estão definidos como bits L e F, respectivamente. O bit
L (last) informa se a operação é a última sı́laba da instrução. O bit F (first) informa se a operação
facom-ufms
23
31
15
0
7
7 bit opcode
0
0
6 bit dst GR
6 bit src1 GR
7 bit opcode
0
1
6 bit dst GR
6 bit src1 GR
7 bit opcode
1
0
6 bit link register
7 bit opcode
1
1
6 bit dst GR
LONG_IMM
13
6 bit src2 GR
9 bit short immediate
12 bit branch offset immediate
6 bit src1 GR
3b dst BR L F
L F
3b dst BR L F
10 bit long immediate [0 - 9]
F
-
L F
22 bit long immediate [10 - 31]
Figura 3.3: Formatos de operações implementadas no processador ρ-VEX.
é a primeira sı́laba da instrução. Sua existência é justificada como informação necessária para
implementação de possı́veis compressores/codificadores de instruções. Os últimos dois formatos
destacados dos demais pertencem ao formato de long immediate: um operando de quatro bytes
(32 bits) utilizado por uma operação. Este formato utiliza duas sı́labas para conseguir representar uma instrução com um operando long immediate. Este formato não esta disponı́vel na atual
versão do ρ-VEX, apenas planejado como futura melhoria.
Operações lógico-aritmética e de multiplicação/divisão geralmente são compostas de 2
operandos que produzem 1 resultado: dois registradores como operandos (GR) e um registrador
(GR ou BR) como resultado. As operações lógico-aritmética, ADDCG, DIVS, SLCT e SLCTF, em especial, operam com 3 registradores como operandos, sendo 2 registradores GR e um registrador
BR. Nesse caso, os 3 bits menos significativos do opcode são destinados ao endereçamento do
terceiro operando, o registrador BR. As operações ADDCG e DIVS, também utilizam um segundo
registrador para resultado do tipo BR. As operações de controle são compostas de um ou dois
operandos. As operações GOTO e CALL manipulam apenas um operando, sendo que o operando é
um registrador GR ou um imediato (endereço). As operações BR, BRF, RETURN e RFI manipulam
dois operandos, sendo que um operando é um imediato e outro um registrador BR (BR e BRF) ou
GR (RETURN e RFI). As operações de memória, por sua vez, são compostas de 2 operandos e 1
resultado: um registrador GR como primeiro operando, um imediato (endereço) como segundo
operando e um registrador GR como resultado.
3.1.4
Linguagem de Montagem ρ-VEX
A linguagem de montagem ρ-VEX é a mesma usada no VEX. Para compreender a notação
dessa linguagem, considere o exemplo presente na Figura 3.4.
O primeiro sı́mbolo, “c0”, denota o cluster no qual a operação será executada (neste caso,
cluster zero). O(s) operando(s) de destino é(são) dado(s) por uma lista de sı́mbolos à esquerda
do sı́mbolo “=”, enquanto que o(s) operando(s) de origem é(são) listados(s) à direita do sı́mbolo
“=”. Neste caso, um único operando de destino é o registrador BR de ı́ndice 3 do cluster zero. O
identificador do cluster é opcional nos sı́mbolos dos operandos quando representam registradores.
Entretanto, o identificador do cluster sempre está presente para reforçar a identificação do cluster
cujo registrador operando será usado na execução. Os sı́mbolos “;;” indicam o fim de um grupo
de operações a serem emitidas em um mesmo ciclo. Instruções que possuem várias operações
simplesmente listam cada operação em linhas separadas, com um duplo sinal de ponto-e-vı́rgula
facom-ufms
14
c0 cmpne $b0.3 = $r0.4, $r0.5 # instr 0, op 0
c0 sub $r0.16 = $r0.6, 3
# instr 0, op 1
;; ## fim da primeira instruç~
ao
c0
c0
c0
;;
shl $r0.13 = $r0.13, 3 # instr 1, op 0
shr $r0.15 = $r0.15, 9 # instr 1, op 1
ldw.d $r0.14 = 0[$r0.4] # instr 1, op 2
## fim da segunda instruç~
ao
Figura 3.4: Exemplo de instruções ρ-VEX.
como separador de instruções. Na Figura 3.4 observa-se um trecho de código em linguagem
de montagem VEX no qual há duas instruções: a primeira com duas operações paralelas e a
segunda com três.
3.2
Desenvolvimento do Back-end LLVM para o Processador
ρ-VEX
O desenvolvimento de um back-end LLVM capaz de converter a LLVM IR em código de
máquina de uma arquitetura especı́fica consiste da criação e implementação de alguns arquivos
e classes. A Figura 3.5 mostra a hierarquia de classes do back-end LLVM implementado para o
processador ρ-VEX . As classes em azul são classes pré-existentes do LLVM. As classes em verde
são classes implementadas para a geração de código para o processador ρ-VEX . As classes em
amarelo são classes geradas automaticamente a partir da descrições feitas com a TableGen.
Figura 3.5: Visão das classes que compõe o back-end LLVM para o processador ρ-VEX.
O processo de desenvolvimento de um back-end LLVM pode ser dividido em alguns passos,
descritos a seguir:
facom-ufms
15
• Extensão da classe TargetMachine que descreve caracterı́sticas da arquitetura alvo. Essa
classe será o ponto principal de ligação entre o módulo de geração de código do LLVM e
a nova arquitetura;
• Descrição do conjunto de registradores. A estrutura TableGen será usada para gerar
código para a maioria das informações acerca do conjunto de registradores (definição,
classe, aliases, etc). Entretanto, deve ser escrito código adicional, estendendo a classe
TargetRegisterInfo, que por sua vez irá descrever informações importantes utilizadas
pela alocação de registradores, além das possı́veis interações entre registradores;
• Descrição do conjunto de instruções. Assim como na descrição do conjunto de registradores, a TableGen ficará responsável por gerar código referente às definições de instruções (formato, número de operandos, itinerários, etc), além dos padrões de matching
utilizados na seleção de instrução. A classe TargetInstrInfo também deve ser estendida
para a arquitetura alvo, objetivando manter informações não estáticas do conjunto de
instruções da arquitetura;
• Descrição da seleção e conversão da LLVM IR na forma de um grafo acı́clico dirigido (DAG)
para instruções nativas da arquitetura. A partir das definições dos padrões de instrução
na descrição do conjunto de instruções, a TableGen gera métodos de seleção utilizados
para a realização de matching de padrões entre instruções nativas e instruções da LLVM
IR. É preciso também descrever regras para conversão de instruções e tipos de dados da
LLVM IR sem suporte nativo na arquitetura. Essas regras podem ser descritas estendendo
as classes SelectionDAGISel (para realizar matching de padrões e seleção de instrução
de DAG para DAG especı́ficas para a arquitetura) e TargetLowering (para substituir ou
remover operações e tipos de dados não suportados);
• Implementação de um emissor de código que converte a LLVM IR final em formato de
código de máquina para a arquitetura alvo. Classes como AsmPrinter e TargetAsmInfo
devem ser estendidas para que a emissão de código seja concluı́da. As definições do formato assembly de cada instrução são feitas, particularmente, na descrição do conjunto de
instruções.
As alterações realizadas em cada um dos passos descritos serão detalhadas nas subseções a
seguir.
3.2.1
TargetMachine
Cada arquitetura alvo deve oferecer uma interface especı́fica através da qual possa ser acessada pelo módulo de geração de código do LLVM. Esta classe é chamada de RVEXTargetMachine.
Ela é uma implementação da classe LLVMTargetMachine e o ponto principal de comunicação entre o LLVM e o back-end ρ-VEX. Nessa classe, todas as caracterı́sticas da arquitetura alvo são
obtidas, tais como conjunto de registradores, conjunto de instruções, organização da pilha, conjunto de itinerários para arquitetura, etc. Além disso, o passo de seleção de instrução da arquitetura e demais passos adicionais especı́ficos (no caso do ρ-VEX, a utilização de VLIW Packetizer,
que será tratado em detalhes em 3.2.8) são registrados e adicionados ao fluxo de execução do gerador de código LLVM. Outras informações também são definidas na classe RVEXTargetMachine:
facom-ufms
16
• Representação de dados na arquitetura: no construtor da classe RVEXTargetMachine é
definida uma string que determina a representação dos dados na arquitetura. Isto inclui
tamanho de dados suportados, alinhamento de acordo com a Application Binary Interface
(ABI) e alinhamento preferencial. Para o ρ-VEX, os dados podem ser representados em
8, 16 e 32 bits. Um ponteiro tem tamanho fixo de 32 bits. O modelo de endereçamento
de dados utilizado pelo ρ-VEX é o big-endian.
• Versões diferentes do processador, assim como suas funcionalidades presentes ou omitidas.
Apenas um modelo de processador é informado no back-end LLVM para o ρ-VEX.
3.2.2
Registro da Máquina Alvo
O TargetRegistry é um mecanismo do LLVM para gerenciamento e pesquisa de alvos
(arquitetura ou linguagem) em tempo de execução. Cada back-end deve declarar uma instância
global da classe Target, que será usada para representar a máquina alvo durante o registro.
Após o registro, o objeto Target é preenchido com referências a importantes componentes do
back-end (incluindo a classe RVEXTargetMachine), e uma string contendo o nome (ou uma
tripla composta de strings com o nome da arquitetura, nome do fabricante e nome do sistema
operacional) é salvo em uma lista de pesquisa.
3.2.3
Descrição do Conjunto de Registradores
A descrição dos registradores da arquitetura consiste de uma especificação TableGen e uma
implementação da classe TargetRegisterInfo para a arquitetura. Na primeira, são definidos,
tipicamente, todos os registradores da arquitetura e as classes para os grupos de registradores que
são tratados da mesma forma para alguma instrução. Na segunda são definidas informações sobre
o conjunto de registradores que serão utilizadas pela alocação de registradores. Nessa última são
descritas as interações entre os registradores. Cada registrador é um objeto da classe Register,
que por sua vez consiste de um conjunto de dados referente ao objeto (registrador) instanciado.
Informações como nome, nome para o formato assembly da máquina alvo e namespace são
definidas nessa classe. É possı́vel especificar o conceito de sub-registradores. Entretanto, tais
funcionalidades não foram necessárias para a especificação dos registradores ρ-VEX.
A implementação do back-end LLVM para o ρ-VEX define duas subclasses da classe
Register, RVEXGRReg e RVEXBRReg, para as definições dos registradores gerais (GRs) e registradores de branch (BRs), respectivamente. Ambas as classes sobrescrevem o campo namespace (para a identificação do registrador como componente do back-end LLVM para o ρ-VEX) e
adicionam um campo composto de 5 bits, para a RVEXGRReg, e 3 bits, para a RVEXBRReg, usados
para a identificação de cada registrador dentro do banco de registradores. Cada registrador fı́sico
concreto da arquitetura deve ser definido como uma instância de uma dessas classes supramencionadas. O identificador e o nome do registrador são passados como argumentos. A Figura 3.6
mostra um trecho da especificação TableGen dos registradores ρ-VEX.
Outra atividade importante na descrição do conjunto de registradores é a definição da classe
de registrador e os registradores fı́sicos que a compõe. A classe RegisterClass é estendida
para cada classe presente no conjunto de registradores da arquitetura. Nela são definidas o
namespace da classe, uma lista de tipos de valores (dados) suportados pelos registradores da
classe, o alinhamento requerido para o armazenamento, a carga dos registradores em memória
facom-ufms
17
let Namespace = "RVEX" in {
class RVEXGRReg<bits<5> num, string n> : Register<n> {
field bits<5> Num = num;
}
class RVEXBRReg<bits<3> num, string n> : Register<n> {
field bits<3> Num = num;
}
def
def
...
def
def
...
R0
R1
: RVEXGRReg< 0,
: RVEXGRReg< 1,
"$r0.0">;
"$r0.1">;
B0
B1
: RVEXBRReg< 0, "$b0.0">;
: RVEXBRReg< 1, "$b0.1">;
}
Figura 3.6: Trecho da especificação dos registradores ρ-VEX.
e os registradores que fazem parte da classe. A Figura 3.7 apresenta as definições das classes de
registradores do ρ-VEX.
def GRRegs : RegisterClass<"RVEX", [i32], 32, (add
(sequence "R%u", 0, 31))> { }
def BRRegs : RegisterClass<"RVEX", [i1], 32, (add
(sequence "B%u", 0, 7))> { let Size = 32; }
Figura 3.7: Definição das classes de registradores ρ-VEX.
O passo final da descrição do conjunto de registradores é a implementação da classe
TargetRegisterInfo. Essas informações podem variar de acordo com as versões de processador suportadas pelo back-end da arquitetura definidas diretamente no formato TableGen. A classe RVEXRegisterInfo possui métodos que retornam informações como: o conjunto de registradores usados como callee-saved (getCalleSavedRegs()), conjunto de registradores reservados (getReservedRegs()) e os registradores usados como ponteiro de pilha
(getStackPointer()) e ponteiro do quadro de pilha (getFramePointer()). Outros métodos
implementados pela classe são:
• eliminateCallFramePseudoInstr(). Este método manipula as pseudo instruções
ADJCALLSTACKDOWN e ADJCALLSTACKUP, que são inseridas antes e depois de cada chamada
de função durante a fase de seleção de instruções. Ambas possuem um imediato como
operando que indica quantos bytes os argumentos de uma chamada de função ocupam na
pilha. Normalmente, este valor é zero já que usualmente os argumentos são passados em
registradores, possibilitando a simples remoção dessas instruções do bloco básico. Se a
chamada de função tem um quadro de tamanho fixo, os espaços necessários para todos os
argumentos são inclusos e consequentemente alocados na emissão de prólogo da função,
portanto, nenhuma ação adicional é necessária. A única situação contrária é quando a
chamada de função contém objetos de tamanho variável na pilha, tornando impossı́vel
facom-ufms
Registradores
$r0.0
$r0.1
$r0.2
$r0.3-$r0.6
$r0.7-$r0.25
$r0.26-$r0.29
$l0.0
$r0.31
Classe
Constante
Especial
(N/A)
(N/A)
(N/A)
Preservados
Especial
Especial
18
Uso
Sempre zero
Ponteiro de pilha
Retorno de ponteiro de struct
Argumentos e valores de retorno
Temporários
Temporários (callee-save)
Ponteiro de link
Para uso do Assembler
Tabela 3.2: Convenção de uso para o conjunto de registradores GR do ρ-VEX.
determinar o tamanho máximo do quadro de pilha em tempo de compilação. Neste caso,
ADJCALLSTACKDOWN e ADJCALLSTACKUP devem ser substituı́das por subtração e uma adição
ao ponteiro da pilha, respectivamente. No back-end LLVM para o ρ-VEX ainda não há
suporte ao último caso, portanto, essas instruções são removidas.
• eliminateFrameIndex(). Este método é chamado para cada instrução que referencia
uma palavra de dados em um slot da pilha. Todos os passos anteriores ao gerador de código
tratam o endereçamento da pilha como um ı́ndice abstrato e um imediato de deslocamento.
O objetivo desta função é traduzir essa referência em um par registrador-deslocamento.
Como na atual implementação do back-end LLVM para o ρ-VEX só há suporte para
quadros de tamanho fixo, o ponteiro de pilha é usado como registrador base. Ressalta-se
ainda que o ρ-VEX não possui suporte a deslocamentos maiores que 9 bits atualmente e,
por isso, em casos que isso ocorre é causado uma exceção, interrompendo a geração de
código.
3.2.4
Convenções de Chamada
A forma como os registradores são utilizados durante a geração de código, como os argumentos são passados para uma função e como os valores de retorno são recebidos de uma função, são
caracterı́sticas especı́ficas de uma arquitetura. A ABI define um conjunto de regras que devem ser
rigorosamente satisfeitas. A ABI definida na ISA VEX especifica as convenções de chamada para
processadores nela baseados. Entrentanto, tais convenções não são completamente aplicáveis ao
processador ρ-VEX tendo em vista suas limitações (como o número de registradores, por exemplo). Para este trabalho, algumas mudanças (simplificações) na convenção de chamada da
ABI VEX foram realizadas, a começar pela convenção de uso dos registradores. Na Tabela 3.2
é apresentada a convenção de uso aplicada no back-end ρ-VEX.
Outra questão importante é como são realizadas as chamadas de funções e consequentemente
o uso da pilha para passar argumentos e retornar valores. Na adaptação da ABI VEX para
o processador ρ-VEX , os argumentos de funções são primeiramente alocados em uma lista
conceitual, que é então mapeada em uma combinação de registradores e pilha, onde os primeiros
16 bytes da lista de argumentos são passados em registradores, e o restante é passado na pilha.
Cada 4 bytes é chamado de slot de argumento. Argumentos menores que 4 bytes, e também
ponteiros, são alinhados dentro de um slot de argumento, e argumentos maiores que 4 bytes são
alinhados em um limite de 8 bytes, dentro de dois slots de argumento. Para o retorno de função,
valores de retorno menores que 4 bytes são retornados no registrador $r0.3 e valores de retorno
facom-ufms
19
maiores que 4 bytes são retornados nos registradores $r0.3 e $r0.4. Valores de retorno agregados
menores que 16 bytes são alinhados em múltiplos de 4 bytes e retornados em registradores gerais
sucessivos, a partir do registrador $r0.3. Por fim, valores de retorno maiores que 16 bytes são
retornados em um buffer, alocado pela função chamador e um ponteiro para esse buffer é passado
no registrador $r0.2.
No LLVM as convenções de chamada são descritas utilizando a classe CallingConv da TableGen que, por sua vez, consiste de uma lista de ações que são analisadas em ordem para cada
argumento ou valor de retorno de uma subrotina. A Figura 3.8 apresenta os registros RetCC RVEX
e CC RVEX. O primeiro descreve a convenção para os valores de retorno, e o segundo descreve a
convenção para a chamada de subrotina com argumentos.
def RetCC_RVEX : CallingConv<[
CCIfType<[i32], CCAssignToReg<[R3, R4, R5, R6]>>,
CCAssignToStack<4, 4>
]>;
def CC_RVEX : CallingConv<[
CCIfType<[i8, i16], CCPromoteToType<i32>>,
CCIfType<[i32], CCAssignToReg<[R3, R4, R5, R6]>>,
CCAssignToStack<4, 4>
]>;
Apesar de não existir suporte a chamadas de função na versão do ρ-VEX usada neste trabalho, a descrição foi necessária devido ao seu uso no estágio de seleção de instrução. Especificamente, no passo de conversão da LLVM IR em SelectionDAG denominado lowering (que será
detalhado na Subseção 3.2.6).
3.2.5
Descrição do Conjunto de Instruções
A descrição, manipulação e transformação de instruções constitui a parte central do back-end.
O gerador de código precisa de informações completas e detalhadas sobre os nomes, opcodes,
operandos, comportamento e efeitos de cada instrução dentro da arquitetura alvo. A descrição
do conjunto de instruções é distribuı́da em arquivos TableGen, onde são definidos a estrutura
abstrata que represente as instruções da máquina alvo junto a formatos genéricos para conjuntos
de instruções semelhantes (RVEXInstrFormats.td) e uma descrição de uma instrução concreta
(RVEXInstrInfo.td). É importante observar que uma instrução LLVM corresponde a uma
sı́laba VLIW do processador ρ-VEX. Para definição do conjunto de instruções de uma arquitetura
no LLVM, o primeiro passo é a extensão da classe Instruction, que contém, entre outros, os
seguintes campos:
• Operandos de saı́da: contêm o valor (ou valores) resultado da execução da instrução;
• Operandos de entrada: contêm os valores usados pela instrução como argumentos de
entrada;
• Formato Assembly : usado pelo emissor de código, contém o formato que representa a
instrução em código de máquina;
facom-ufms
20
• Padrão: contêm o padrão referente a uma instrução LLVM IR na forma de SelectionDAG,
que é usado pelo seletor de instrução para produzir uma instância de uma instrução da
arquitetura alvo correspondente.
Como extensão de Instruction, a classe InstRVEX é uma classe abstrata que descreve
caracterı́sticas genéricas a cada definição de instrução concreta do processador ρ-VEX como o
tamanho, namespace e formato da instrução. Os formatos são subclasses que determinam a
codificação comum a um grupo de instruções.
Como visto na Subseção 3.1.3, o ρ-VEX possuiu 4 formatos genéricos de operação, com
extensões especı́ficas para algumas operações (como é o caso das instruções de ALU: ADDCG, DIVS,
SLCT e SLCTF; das instruções de CTRL: GOTO, CALL, BR, BRF, RETURN e RFI; e das instruções de
MEM: LDW, LDH, LDHU, LDB, LDBU, STW, STH e STB). São definidos três formatos para operações de
ALU e MUL, um formato para operações de CTRL e um formato para operações de MEM. Tendo em
vista esses casos, foram definidas as classes RTYPEInst, ISTYPEInst, BRANCHInst, RTYPE BSInst
e MEMTYPEInst, que representam os seguintes formatos, respectivamente:
• RTYPE (Register ): formato comum para a maioria das instruções de ALU e para todas
as instruções de MUL. O formato RTYPE (Veja a Figura 3.9) é utilizado por instruções
apenas com operandos do tipo registrador e define os campos para, opcode (op), immediate
switch (SS ), resultado em registrador GR (dst), operandos (src1 e src2 ), resultado em
registrador BR para operações de comparação (dstBR) e flags para indicar se a operação é
a primeira ou última operação de uma instrução VLIW (L e F ). Como os três operandos
são registradores, o campo de immediate switch é declarado com 0 (no immediate value).
• ISTYPE (Short Immediate): assim como o formato RTYPE, é utilizado pela maioria das
instruções de ALU e todas instruções de MUL. O formato ISTYPE (Veja a Figura 3.10) é
utilizado por instruções compostas de um imediato como operando e define os campos de
opcode (op), immediate switch (SS ), resultado em registrador GR (dst), primeiro operando
em registrador GR (src1 ), segundo operando do tipo imediato (imm9 ) e flags para indicar
se a operação é a primeira ou última operação de uma instrução VLIW (L e F ). O campo
immediate switch é declarado com 1 (short immediate).;
• ILTYPE (Long Immediate): formato para instruções compostas de um imediato maior que
9 bits (não suportados pelo formato ISTYPE). Não é suportada na atual versão do ρ-VEX,
mas foi descrita no back-end para futuras implementações;
• BRANCH (Branch Offset Immediate): formato comum para as instruções de CTRL. O formato
BRANCH (Veja a Figura 3.11) é utilizado pelas instruções GOTO, CALL, BR, BRF, RETURN e RFI
e define os campos opcode (op), immediate switch (SS ), registrador de link (lr ), endereço
de desvio (imm12 ), registrador de branch para desvios condicionais (srcBR), e flags para
indicar se a operação é a primeira ou última operação de uma instrução VLIW (L e F ).
O campo immediate switch é declarado com 2 (branch offset immediate);
• RTYPE BS (Register BS ): formato para as instruções ADDCG, DIVS, SLCT e SLCTF (Veja
Figura 3.12). Seus campos são definidos de acordo com a especificação de tais instruções
na Subseção 3.1.3;
• MEMTYPE (Memory): formato para instruções de MEM (Veja a Figura 3.13). Define os
campos opcode (op), immediate switch (SS ), resultado em registrador GR (dst), endereço
facom-ufms
21
de memória em registrador (addr ), imediato de deslocamento (imm9 ) e flags para indicar
se a operação é a primeira ou última operação de uma instrução VLIW. O campo immediate
switch é declarado com 1 (short immediate).
Figura 3.9: Formato RTYPE.
Figura 3.10: Formato ISTYPE.
Figura 3.11: Formato BRANCH.
Figura 3.12: Formato RTYPE BS.
Figura 3.13: Formato MEMTYPE.
Também é definido um formato, denominado PSEUDOInst, para pseudo instruções inseridas
pelo LLVM durante a geração de código (como ADJCALLSTACKDOWN e ADJCALLSTACKUP por exemplo). Essas instruções são usadas em passos especı́ficos para auxiliar na geração de código
e, após seu uso, são removidas (ou substituı́das por instruções da arquitetura alvo) antes da
emissão de código. Embora a descrição da codificação seja apenas relevante se a arquitetura
suportar compilação Just-in-Time (o que não é o caso do ρ-VEX) foi decidido respeitá-la na
descrição do conjunto de instruções.
Após a descrição dos formatos, é necessário definir uma instrução concreta. Tal instrução é
uma instância de um formato definido anteriormente. A Figura 3.14 exemplifica a descrição de
uma instrução ρ-VEX .
Note que, em sua definição, a instrução declara o opcode da instrução, o tipo do resultado e
dos operandos que a compõe (no caso, registradores), o formato assembly usado na emissão de
código, o padrão usado para a seleção de instrução e o itinerário (usado no escalonamento de
instruções).
facom-ufms
def ADDrr : RTYPEInst<
65,
(outs GRRegs:$dst),
(ins GRRegs:$src1, GRRegs:$src2),
"add $dst = $src1, $src2",
[(set (i32 GRRegs:$dst),
(add (i32 GRRegs:$src1),
(i32 GRRegs:$src2)))],
iiALU>;
22
//
//
//
//
//
Opcode
Resultado
Operandos
Formato assembly
Padr~
ao
// Itinerário
A classe RVEXInstrInfo contém informações não estáticas referentes ao conjunto de instruções. Essas informações constituem-se em métodos que auxiliam na análise, transformação
e inserção de certas instruções de máquina. Esses métodos só são chamados após o escalonamento de instruções, quando já não existe mais o SelectionDAG. Operações como análise e
conversão de branch (quando existem dois branchs seguidos e o segundo pode ser removido caso
o primeiro seja incondicional), inserção de instruções para mover dados de um registrador virtual para um registrador fı́sico, inserção de NOPs (no operation) e manipulação de memória, são
realizadas por métodos definidos na classe RVEXInstrInfo.
3.2.6
TargetLowering
O processo de preparar o programa de entrada para o estágio de seleção de instruções,
convertendo-o de formato lista de instruções para um grafo acı́clico dirigido (SelectionDAG) é
chamado de lowering. Este é o primeiro passo do procedimento de geração de código. Para cada
instrução da LLVM IR uma instância da classe SDNode (nó do SelectionDAG) é criada. Um
SDNode contém as seguintes informações:
• Opcode: um inteiro que identifica a instrução representada pelo nó;
• Resultados (definitions): lista de resultados;
• Operandos (uses): lista de operandos do nó que é composta de SDValues, o qual encapsula um ponteiro para o nó de dependência e o ı́ndice do valor do nó afetado pela
dependência.
O esforço principal na construção do SelectionDAG vem das classes SelectionDAGBuild
e TargetLowering. A classe RVEXTargetLowering, subclasse de TargetLowering, oferece a
sua super classe informações da arquitetura, incluindo classes de registradores e tipo de dados
suportados (tipos de 32 bits para registradores gerais e tipos de 1 bit para registradores de
branch) e método de escalonamento preferêncial (escalonamento para arquiteturas VLIW).
Outra informação importante definida na classe RVEXTargetLowering é a de quais instruções
não podem ser “reduzidas” a instruções nativas de forma automática, requerendo intervenção
manual. Essas instruções podem ser substituı́das por instruções equivalentes (da própria LLVM
IR) capazes de serem convertidas em instruções da arquitetura alvo. Ou então, em casos onde
a instrução não é suportada devido ao tipo de dado dos operandos, é feita uma divisão (ou
expansão) desses tipos para tipos suportados.
facom-ufms
23
Na atual versão do back-end, algumas das interverções feitas são na redução das instruções de
multiplicação MULHS, MULHU, SMUL LOHI e UMUL LOHI com operandos de 32 bits para instruções
equivalentes com operandos menores. As duas primeiras realizam multiplicação (MULHS com
sinal e MULHU sem sinal) entre dois operandos de um tipo com N bits, produzindo um valor
de 2N bits onde o resultado é apenas os N bits mais significativos do valor. As duas últimas
funcionam de forma semelhante (SMUL LOHI com sinal e UMUL LOHI sem sinal) retornando tanto
a parte mais significativa quanto a parte menos significativa, ou seja, o valor total com 2N
bits. As unidades de multiplicação do ρ-VEX não suportam multiplicações 32 por 32 bits e
o conjunto de instruções VEX não oferece formas de manipular operações de maneira a obter
resultado equivalente às instruções da LLVM IR descritas anteriormente com operandos de 32
bits. Consequentemente a instrução MUL (multiplicação simples retornando o valor total) com
operandos de 32 bits também não é suportada diretamente pelo ρ-VEX. Nesse caso, são criadas
duas instruções ρ-VEX para realizar operação semelhante, mas essa intervenção é feita já na
seleção de instruções, diretamente de uma instrução LLVM IR para instrução ρ-VEX .
Instruções de divisão e módulo ainda não são completamente suportadas pelo back-end LLVM
para o ρ-VEX. Essas instruções, por hora, são reduzidas em instruções de multiplicação pelo
seletor de instruções. É importante destacar que em alguns casos o seletor de instruções não
consegue fazer manipulações de forma a produzir instruções equivalentes, necessitando de tratamento especı́fico (em software), o que ainda não é feito na atual versão do ρ-VEX.
3.2.7
Seletor de Instrução
Como visto na Subseção 2.4.2, o estágio de seleção de instrução é o momento em que o
programa fonte é convertido da representação intermediária para instruções da máquina alvo.
A maior parte das informações usadas na seleção de instruções são geradas automaticamente
pela TableGen (a partir das definições do conjunto de instruções da arquitetura). Entretanto,
há casos em que o seletor de instruções não consegue definir uma conversão válida para uma
operação ou tipo de dados. No back-end LLVM para o ρ-VEX os seguintes casos são convertidos
manualmente:
• Imediatos maiores que 9 bits: imediatos (ou constantes) maiores que 9 bits gerados
pelo LLVM são filtrados na seleção de instrução. É feita uma manipulação, em software,
do tipo de dado de forma a passar o seu conteúdo para um registrador. Operações OR e
SHL do ρ-VEX são inseridas no código final;
• Instruções de multiplicação: as unidades de multiplicação VEX só realizam multiplicações 16 por 32 bits. Nesse caso, são geradas duas instruções ρ-VEX para obter-se
resultado equivalente, mas mesmo assim com perda da parte significativa (a partir do bit
31). A mesma situação ocorre com operandos de 32 bits cada um.
3.2.8
VLIW Packetizer
O VLIW Packetizer é um componente LLVM criado para possibilitar o suporte a arquiteturas VLIW. Nele, o conjunto de instruções é analisado de forma a criar pacotes (bundles) de
instruções sem nenhuma dependência entre elas, mapeadas em unidades funcionais disponı́veis
da arquitetura. O processo de criação de bundles inicia com a criação de um autômato finito determinı́stico a partir dos itinerários definidos no conjunto de instruções. O autômato representa
facom-ufms
24
os estágios do processo de análise e escolha da próxima instrução que irá compor um bundle. O
back-end LLVM para o ρ-VEX utiliza esse componente em seu fluxo de geração de código.
3.2.9
Emissão de Código
A fase final da geração de código é a emissão do programa resultante das fases anteriores em
formato de código de máquina da arquitetura alvo. O processo de emissão consiste na leitura
de cada instrução gerada e a chamada de métodos auxiliares para a impressão do código de
máquina correspondente. Tais métodos utilizam informações geradas pela TableGen tornando
o processo de emissão de código simples e automático. As únicas alterações feitas pelo back-end
LLVM para o ρ-VEX nessa fase são referentes a impressão das informações que compõem o
cabeçalho de um arquivo no formato assembly para o ρ-VEX.
3.3
Este capı́tulo abordou o processo de desenvolvimento do back-end LLVM para geração de
código para o processador ρ-VEX. Nessa apresentação foi possı́vel observar as caracterı́sticas e
limitações do processador ρ-VEX e o desafio de gerar código para um processador com várias
restrições para execução de código. A apresentação do back-end LLVM foi detalhada visando
apresentar todas as caracterı́sticas que devem ser levadas em conta quando da geração de backends LLVM para outras arquiteturas. O Capı́tulo 4 apresenta e discute os experimentos e
resultados obtidos com a validação e avaliação do código gerado pelo LLVM para o processador
ρ-VEX.
facom-ufms
Capı́tulo 4
Experimentos e Resultados
Este capı́tulo apresenta o processo de validação do back-end ρ-VEX , além da análise de
desempenho dos códigos gerados em comparação com o VEX Toolchain [3], principal ferramenta
para geração e simulação de código para máquinas baseadas na ISA VEX, e que acompanha o
processador ρ-VEX. Na Seção 4.1, os passos para a validação são apresentados em detalhe. Na
Seção 4.2 é feita uma análise comparativa dos resultados obtidos com back-end LLVM e com
VEX toolchain na geração de código para o processador ρ-VEX.
4.1
Validação do Back-End LLVM
O processo de validação do back-end ρ-VEX, consistiu na geração de código para um conjunto de programas já adaptados para o processador ρ-VEX. Tais programas já foram organizados de forma a respeitarem as limitações da atual versão do processador. O conjunto de
programas utilizados é composto por 21 programas, dos quais 9 fazem parte do Trimeran Compiler Suite (Simple benchmarks) [11], e os demais (binary tree, counting sort, double linked list,
floyd warshall, kruskal, linked list, local var, longlong, mergesort, parms test, prim e struct test)
são implementações de algoritmos clássicos de ordenação e manipulação de estruturas de dados.
A Tabela 4.1 apresenta os programas utilizados e uma breve descrição de cada um.
Deve-se observar que programas maiores de benchmarks conhecidos (como SPEC, MediaBench e Mibench, por exemplo) não foram utilizados nos experimentos devido a ausência de
ferramentas de link -edição disponı́veis para o processador ρ-VEX. Isso obriga a remoção de todas as chamadas a funções presentes em bibliotecas externas, como manipulação dinâmica de
grande quantidade de memória, impressão e leitura de textos em tela e arquivos, entre outras.
Outra limitação reside no fato de que o ρ-VEX não suporta imediatos maiores que 9 bits,
como visto na Subseção 3.2.7, e com isso não é possı́vel realizar o carregamento e armazenamento
de dados em endereços de memória muito distantes entre si. Isso se torna um problema quando
um programa possui muitas funções e realiza um trabalho intenso de pilha com chamadas de
funções com muitas variáveis locais, gerando um stack frame muito extenso. Também é impossı́vel a essas funções endereçarem e acessarem variáveis globais do programa, que se encontram em uma posição muito distante na pilha com relação ao stack frame da função em execução.
Dessa forma, todas as funções em um programa devem ser expandidas inline internamente na
função main de forma a preservar o endereçamento global de variáveis, cuidando para que o
25
Programas
binary tree
counting sort
dag
double linked list
eight
fact2
fib mem
fir
floyd warshall
hyper
kruskal
linked list
local var
longlong
mergesort
mm dyn
nested
parms test
prim
strcpy
struct test
26
Descrição
Balanceamento de árvores
Ordenação
Desvios internos à loop (if-then-else)
Estrutura de dados
Desvios internos à loop (label-goto)
Fatoração utilizando loop
Calculo de número Fibonacci utilizando vetor
Filtro de Resposta de Impulso Finito
Algoritmo de caminho mı́nimo
Desvios internos à loop (if-then-continue)
Árvore geradora mı́nima
Estrutura de dados
Variáveis locais utilizando vetor
Variáveis do tipo long long
Ordenação
Matriz alocada dinamicamente
Encadeamento de loops
Passagem de parâmetros
Árvore geradora mı́nima
Cópia de strings
Estrutura de dados
Tabela 4.1: Conjunto de programas utilizados para a validação do back-end LLVM.
tamanho da pilha de variáveis locais não ultrapasse a capacidade de deslocamento do imediato
de 9 bits.
Os códigos gerados para o ρ-VEX pelo VEX Toolchain, assim como pelo back-end LLVM,
precisam respeitar as limitações do processador. Para isso, a geração de código com o VEX
Toolchain segue um padrão, composto de um modelo de máquina1 e parâmetros de compilação
que possibilitam a geração de código funcional para o ρ-VEX. O modelo de máquina utilizado
descreve todas as caracterı́sticas do processador ρ-VEX. Os parâmetros utilizados na compilação
impõem algumas condições para a geração de código:
• -fno-xnop: faz com que instruções XNOP não sejam emitidas no código gerado. Ao invés
de XNOPs, são emitidas instruções NOP. Isso se deve ao fato de que instruções XNOPs são
instruções de controle de pipeline e o processador ρ-VEX é um processador multiciclo;
• -fexpand-div: faz com que o compilador substitua chamadas a bibliotecas internas para
divisão de inteiros por código inline para tais operações. Como descrito anteriormente, o
ρ-VEX não suporta chamadas externas;
• -mGLOB preserved registers=0: utilizado devido a um bug presente na atual versão
do VEX Toolchain, onde, em alguns casos, o compilador gera código com registradores não
definidos no modelo de máquina. Isso acontece pois o compilador mantém as definições de
1
Determina os recursos da máquina para qual será gerado código, como o número de unidades funcionais e
quais os tipos disponı́veis, banco de registradores e a quantidade de registradores que os compõe, quantidade de
clusters VEX utilizados, etc.
facom-ufms
27
uso de registradores do conjunto de registradores original para conjunto de registradores
menores, assim, os registradores preservados eram mantidos e emitidos incorretamente em
modelos de máquina onde não estavam presentes. A correção é feita definindo o número
de registradores preservados como 0.
As compilações com LLVM não utilizam nenhum parâmetro ou passo adicional, devido às
caracterı́sticas do back-end serem especı́ficas do ρ-VEX. Com isso, todas as limitações do processador já foram incorporadas no back-end LLVM durante o desenvolvimento.
A Figura 4.1 apresenta o fluxo de validação do back-end LLVM para o ρ-VEX. Dado um
programa em C (.c), o primeiro passo (1) é compila-lo com o LLVM, o Compilador C do VEX
Toolchain (VEX C Compiler ) e o GCC. As saidas do LLVM e do VEX C Compiler são códigos
assembly VEX (.s) e cada uma será parâmetro de entrada para o segundo passo do fluxo de
validação (2) que consiste na geração de binários executáveis para a máquina host (máquina
na qual está instalado o VEX Toolchain) utilizando a ferramenta de simulação VEX (VEX
Simulator ), também presente no VEX Toolchain [12, 5, 4]. O simulador VEX transforma o
código assembly em um programa em C, que por sua vez é compilado para a arquitetura da
máquina host (com o GCC) gerando um binário executável (.out) e possibilitando a utilização
de ferramentas de depuração nativas (no caso o GDB [?]) para a análise da memória, valores dos
registradores e valores de retorno (LLVM return, VEX C return e GCC return). Como o GCC
é nativo a máquina host, a saida de sua compilação já é um binário executável. Os binários
executaveis resultantes do processo de geração de código com cada compilador (LLVM, VEX C
Compiler e GCC) são então depurados com o GDB e suas saı́das (escritas em memória ou em
registradores) são comparadas, finalizando o processo de validação (3).
Assim, considerou-se que os programas gerados pelo LLVM são validos se suas saı́das são
iguais às saı́das dos programas gerados pelo VEX C Compiler e GCC. Deste processo, 7 programas não foram considerados validos e consequentemente não foram utilizados para avaliação de
desempenho. Os programas eight, hyper e fir apresentam instruções de divisão e módulo, e devido as limitações da atual versão do back-end LLVM para o ρ-VEX (como visto na Subseção 3.2.6)
tais instruções não são tratadas corretamente durante a seleção de instrução. Nos programas
fact2, mergesort e strcpy a LLVM IR apresenta instruções de comparação com operandos de
tamanhos especı́ficos sem equivalentes diretos nas instruções VEX. Casos como esse ainda não
são tratados no back-end. O programa prim tem codı́go gerado com um deslocamento de pilha
maior que 9 bits, sendo assim desconsiderado durante a validação.
Figura 4.1: Visão do fluxo de validação do back-end LLVM para o ρ-VEX.
facom-ufms
28
A próxima Seção apresenta a análise de desempenho realizada sobre os códigos (validos)
gerados pelo back-end LLVM em relação a os códigos gerados pelo VEX C Compiler.
4.2
Avaliação de Desempenho
As Tabelas 4.2 e 4.3 apresentam os resultados de caracterização e desempenho sobre os
códigos gerado pelo LLVM e pelo VEX Toolchain. Nota-se que a maioria dos programas gerados
com o VEX Toolchain apresentam desempenho melhor (menor valor na coluna Total de Ciclos)
em relação aos mesmos gerados pelo LLVM. Esse fato, de certa forma, já era esperado, devido
ao compilador do VEX Toolchain ser uma implementação mais madura e otimizada, enquanto
o back-end LLVM para ρ-VEX ainda implementa somente funcionalidades básicas de geração de
código. A Figura 4.2 apresenta o speedup de desempenho do back-end LLVM sobre o VEX C
Compiler.
Figura 4.2: Speedup do desempenho do back-end LLVM sobre o VEX C Compiler.
Programas
binary tree
counting sort
dag
double linked list
f ib mem
f loyd warshall
if then
linked list
local var test
longlong
mm dyn
nested
parms test
struct test
Total
de Ciclos
1418
1631
10370
14495
977
4170
430537
51608
1447
440
1944
2591
445
508
Ciclos
de Exec.
609
793
8849
12600
383
3168
370037
46811
745
32
1053
1612
37
94
Ciclos
de Stall
809
838
1521
1895
594
1002
60500
4797
702
408
891
979
408
414
Op. Ger.
Op. Exec.
Inst. Ger.
Inst. Exec.
77
96
53
85
26
111
51
56
27
20
86
103
29
29
796
989
10769
13759
464
4802
525044
51043
1077
40
1792
1894
49
97
55
70
37
60
18
78
34
39
17
10
49
79
15
24
601
785
8841
12592
375
3160
370029
46803
737
24
1045
1604
29
86
Miss Mem.
Inst. (%)
2,77
2,69
0,2
0,17
2,27
0,75
0
0,04
1,08
26,32
1,5
1,01
26,32
11,9
Miss Mem.
Dados (%)
9,09
3,98
50
0,17
6,92
1,95
50
0,05
8,33
29,41
4,46
17,02
21,74
10,2
Tabela 4.2: Programas Compilados com o LLVM.
Nos programas gerados pelo back-end LLVM que obtiveram pior desempenho (counting sort,
dag, fib mem, floyd warshall, ifthen, local var test, longlong, mm dyn e struct test) deve-se
destacar algumas caracterı́sticas da geração de código:
facom-ufms
Programas
binary tree
counting sort
dag
double linked list
f ib mem
f loyd warshall
if then
linked list
local var test
longlong
mm dyn
nested
parms test
struct test
Total
de Ciclos
1446
1431
7681
16814
859
2939
220530
58500
1173
387
1828
1810
447
412
Ciclos
de Exec.
575
551
6416
14306
267
1965
200031
52931
473
24
905
865
39
44
29
Ciclos
de Stall
871
880
1265
2508
592
974
20499
5569
700
363
923
945
408
368
Op. Ger.
Op. Exec.
Inst. Ger.
Inst. Exec.
60
90
55
98
20
83
54
62
22
2
82
100
30
11
694
731
15627
13139
387
3240
780046
47584
751
22
1577
1934
50
52
47
61
23
71
14
56
16
51
13
2
40
47
17
7
434
400
6408
10027
218
1700
200023
35978
353
16
714
848
31
31
Miss Mem.
Inst. (%)
2,17
4,48
0,23
0,19
2,82
1,02
0,01
0,04
1,22
22,22
1,84
1,33
25
12,5
Miss Mem.
Dados (%)
5,75
4,61
50
0,22
6,82
2,12
50
0,07
8,26
50
4,2
17,02
21,74
50
Tabela 4.3: Programas Compilados com o VEX C Compiler.
• Alguns desses programas apresentam operações de divisão e módulo. Essas operações
ainda não são suportadas pelo back-end LLVM uma vez que também não são totalmente
executadas pelo ρ-VEX. Quando elas ocorrem é feita uma manipulação por parte do seletor
de instruções do LLVM de forma a substituir tais instruções por instruções mais simples e
suportados pelo ρ-VEX. Essa substituição (quando possı́vel) gera, inevitavelmente, mais
instruções, conforme descrito em 3.2.6, e, como consequencia imediata, afeta o desempenho
dos programas;
• Em alguns casos imediatos maiores que nove bits são gerados pelo VEX Toolchain, o
que causa a geração de código não funcional para o ρ-VEX. Isso se deve ao fato de não
ser possı́vel limitar os formatos de instruções na configuração do compilador do VEX
Toolchain. Como visto em 3.2.7, o back-end LLVM faz uma manipulação de instruções
para transferir o valor do imediato para um registrador, gerando mais instruções. Já no
VEX Toolchain, imediatos maiores que nove bits são normalmente manipulados devido ao
formato para imediatos longos (long immediate) ser definido pela ISA VEX. Entretanto,
esses códigos são simulados mas não serão gerados pelo montador do ρ-VEX , uma vez
que, na etapa de montagem, não serão permitidos imediatos maiores que nove bits.
O desempenho melhor dos programas gerados com o LLVM (binary tree, double linked list,
linked list e parms test) são ocasionados pelo fato do código gerado pelo LLVM obter uma taxa de
ocupação de instruções (OPI=operações por instrução) maior que o gerado pelo VEX Toolchain.
Nesses casos, a consequencia imediata de um código menor é a geração de menos misses na cache.
Essa situação (maior OPI) ocorre devido às inserções de instruções NOP pelo compilador do VEX
Toolchain, que as insere sempre que há conflitos de dados envolvendo instrução de memória, no
caso de instruções LOAD com 2 NOPs, e instruções de comparação com 1 NOP [3].
4.3
Neste capı́tulo foram tratados o processo de validação do back-end LLVM e a caracterização
e avaliação de desempenho do código gerado em comparação com o VEX Toolchain. Mesmo
com as validações de código realizadas tomando como base os valores de saı́da dos programas,
pode-se observar as diferenças entre uma implementação que visa a geração de código para a ISA
VEX (VEX Toolchain) e uma implementação com objetivo de gerar código para o processador
ρ-VEX. Mesmo com as limitações da implementação, nota-se o potencial do back-end LLVM
tanto para o processador ρ-VEX quanto para processadores baseados na ISA VEX. O Capı́tulo 5
facom-ufms
30
irá apresentar as conclusões do trabalho e os possı́veis trabalhos futuros que poderão tomar como
base o back-end LLVM para o processador ρ-VEX.
facom-ufms
Capı́tulo 5
Conclusões e Trabalhos Futuros
O trabalho apresentado nesta monografia estendeu a capacidade de geração de código da
infraestrutura de compilação LLVM para o conjunto de instruções VEX e um processador
VLIW reconfigurável denominado ρ-VEX. O projeto e implementação realizados possibilitam
que usuários do conjunto de instruções VEX possam utilizar os recursos do LLVM para compilar
programas considerando esse conjunto de instruções alvo.
No âmbito deste trabalho, a utilização dos recursos da implementação packetizer, disponibilizados no LLVM a partir da versão 3.0, foram primordiais para que os objetivos fossem alcançados. Interessante observar que este trabalho apresenta também a contribuição de ser uma
das primeiras extensões de packetizer disponı́veis na literatura da área para outras máquinas
VLIW além do modelo Hexagon. Com isso, uma contribuição significativa deste projeto, além
da disponibilidade de uma nova ferramenta de geração de código para o ρ-VEX, é a validação e
utilização de packetizers para geração de código em máquinas VLIW.
Os resultados obtidos permitiram validar e avaliar a geração de código, pelo LLVM, para esse
conjunto de instruções. De acordo com a avaliação de desempenho, códigos gerados pelo LLVM
ainda necessitam de otimizações especı́ficas, uma vez que apresentam uma perda de desempenho
média de 14% em comparação com os mesmos programas compilados com a infraestrutura de
compilação VEX. A razão para essa perda de desempenho é devido a algumas limitações da
atual implementação do back-end, como a falta de suporte a instruções de divisão e módulo,
além da geração ineficiente de instruções de multiplicação e imediatos de nove bits. Em casos
como esses, o back-end LLVM gera mais instruções que o VEX Toolchain. Entretanto, deve-se
entender que a geração de código pelo LLVM objetiva a execução sobre o processador soft-core
ρ-VEX, enquanto que os programas compilados pelo VEX toolchain objetivam a simulação do
conjunto de instruções VEX. Essa diferença afeta sobremaneira o entendimento dos resultados
uma vez que o processador ρ-VEX apresenta várias limitações de suporte a todo o conjunto da
ISA VEX.
No desenvolvimento deste trabalho, algumas dificuldades técnicas foram encontradas e foram
preponderantes para limitar o tempo disponı́vel em melhorias na implementação do back-end
para geração de código VEX. Algumas dessas dificuldades são listadas a seguir:
1. Documentação insuficiente ou incompleta. Algumas vezes, em um nı́vel alto de abstração
sobre a extensão do LLVM para construção de novos back-ends;
2. Ausência de uma implementação adequada para geração de código para arquiteturas
31
Conclusões e Trabalhos Futuros
32
VLIW. Essa dificuldade foi eliminada apenas com a disponibilidade da versão 3.0 que
traz a implementação de packetizers e a geração de código para o processador Hexagon.
A dificuldade 1 afetou sobremaneira o tempo de desenvolvimento do projeto pois a complexidade da infraestrutura de geração de código do LLVM exige um estudo minucioso para
identificar possı́veis interfaces para integração com outros algoritmos. A dificuldade 2 gerou
atrasos significativos no tempo de projeto e implementação uma vez que boa parte do tempo foi
dedicado na implementação do back-end em versões anteriores à 3.0.
5.1
Propostas para Trabalhos Futuros
Algumas propostas de desenvolvimento de trabalhos futuros são:
• Integrar e avaliar o algoritmo de isomorfismo de subgrafos [13] no back-end VEX implementado;
• Estender os experimentos utilizando outros algoritmos de escalonamento e alocação de
registradores assim como heurı́sticas especı́ficas para o modelo de execução VLIW;
• Projetar e desenvolver um back-end LLVM para o conjunto de instruções VEX que considere as mesmas diretrizes de geração de código do VEX toolchain. Dessa forma, a
caracterização e comparação de desempenho entre ambos os códigos será mais adequada.
facom-ufms
Apêndice A
Código do Back-end LLVM para o
Processador ρ-VEX
Neste apêndice serão descritos detalhes do código implementado pelo back-end LLVM para
o processador ρ-VEX.
A.1
A.1.1
Definição e registro da máquina alvo ρ-VEX
RVEXTagetMachine
A classe RVEXTargetMachine (RVEXTargetMachine.h e RVEXTargetMachine.cpp) é responsável pela vizibilidade do back-end para o processador ρ-VEX pela infraestrutura LLVM.
Através dos métodos get*Info e getDataLayout todas as informações referentes a máquina
alvo (ρ-VEX) são acessadas durante o fluxo de geração de código.
namespace llvm {
class R V E X T a r g e t M a c h i n e : public L L V M T a r g e t M a c h i n e {
const DataLayout DL ;
RVEXSubtarget Subtarget ;
RVEXInstrInfo InstrInfo ;
R V E X T a r g e t L o w e r i n g TLInfo ;
R V E X S e l e c t i o n D A G I n f o TSInfo ;
R V E X F r a m e L o w e r i n g FrameLowering ;
const I n s t r I t i n e r a r y D a t a * InstrItins ;
public :
R V E X T a r g e t M a c h i n e ( const Target &T , StringRef TT , StringRef CPU , StringRef FS ,
const TargetOptions & Options , Reloc :: Model RM ,
CodeModel :: Model CM , CodeGenOpt :: Level OL );
virtual const RVEXSubtarget * g e t S u b t a r g e t I m p l () const {
return & Subtarget ;
}
virtual const DataLayout * getDataLayout () const {
return & DL ;
}
virtual const RVEXInstrInfo * getInstrInfo () const {
return & InstrInfo ;
}
33
Código do Back-end LLVM para o Processador ρ-VEX
34
virtual const R V E X T a r g e t L o w e r i n g * g e t T a r g e t L o w e r i n g () const {
return & TLInfo ;
}
virtual const R V E X S e l e c t i o n D A G I n f o * g e t S e l e c t i o n D A G I n f o () const {
return & TSInfo ;
}
virtual const R V E X F r a m e L o w e r i n g * g e t F r a m e L o w e r i n g () const {
return & FrameLowering ;
}
virtual const I n s t r I t i n e r a r y D a t a * g e t I n s t r I t i n e r a r y D a t a () const {
return InstrItins ;
}
virtual const R V E X R eg i s t e r I n f o * g e tR eg is t er In fo () const {
return & InstrInfo . ge tR e gi st er I nf o ();
}
// Pass P i p e l i n e C o n f i g u r a t i o n
virtual T a r g e t P a s s C o n f i g * c r e a t e P a s s C o n f i g ( Pa ss Ma n ag er Ba s e & PM );
}; // R V E X T a r g e t M a c h i n e
} // End llvm n a m e s p a c e
O método createPassConfig é responsável criar e adicionar os passos customizados para o
back-end ρ-VEX ao fluxo de geração de código do LLVM. Desse modo, são adicionados a seleção
de instruções e o passo de construção de bundles (VLIW Packetizer ) para o ρ-VEX.
T a r g e t P a s s C o n f i g * R V E X T a r g e t M a c h i n e :: c r e a t e P a s s C o n f i g ( Pa ss Ma n ag er Ba s e & PM ) {
return new RVEX PassCon fig ( this , PM );
}
namespace {
// / R - VEX Code G e n e r a t o r Pass C o n f i g u r a t i o n Options .
class RVE XPassCo nfig : public T a r g e t P a s s C o n f i g {
public :
RVEXP assConf ig ( R V E X T a r g e t M a c h i n e * TM , P as sM a na ge rB a se & PM )
: T a rg e t P a s s C o n f i g ( TM , PM ) { }
R V E X T a r g e t M a c h i n e & g e t R V E X T a r g e t M a c h i n e () const {
return getTM < RVEXTargetMachine >();
}
virtual bool a dd In s tS el ec t or ();
virtual bool addPreE mitPass ();
};
} // n a m e s p a c e
bool RVEXPass Config :: a d dI ns tS e le ct or () {
addPass ( c r e a t e R V E X I S e l D a g ( g e t R V E X T a r g e t M a c h i n e ()));
return false ;
}
bool RVEXPass Config :: addPr eEmitPa ss () {
addPass ( c r e a t e R V E X P a c k e t i z e r ());
return false ;
}
No construtor da classe RVEXTargetMachine, como visto em 3.2.1, são definidos também a
representação de dados do ρ-VEX como parâmetro na criação do objeto DL do tipo DataLayout.
O E no parâmetro indica o modelo de endereçamento big-endian. p é seguido pelas informações
referentes ao ponteiro, como tamanho, alinhamento definido pela ABI e alinhamento preferı́vel
facom-ufms
35
(32 bits para cada informação). i1, i8, i16 e i32 indicam informações referentes a tipos inteiros e
assim como no caso do ponteiro, as informações que o seguem indicam o tamanho e alinhamento
definido pela ABI. Quando não é definido o terceiro valor (o de alinhamento preferı́vel) o valor
do alinhamento definido pela ABI é aplicado a ambos os valores. A seguir o construtor da classe
RVEXTargetMachine.
R V E X T a r g e t M a c h i n e :: R V E X T a r g e t M a c h i n e ( const Target &T , StringRef TT ,
StringRef CPU , StringRef FS ,
const TargetOptions & Options ,
Reloc :: Model RM ,
CodeModel :: Model CM ,
CodeGenOpt :: Level OL )
: L L V M T a r g e t M a c h i n e (T , TT , CPU , FS , Options , RM , CM , OL ) ,
DL ( "E - p :32:32:32 - i1 :32:32 - i8 :8:8 - i16 :16:16 - i32 :32:32 - n32 " ) ,
Subtarget ( TT , CPU , FS ) ,
InstrInfo ( Subtarget ) ,
TLInfo (* this ) ,
TSInfo (* this ) ,
FrameLowering ( Subtarget ) ,
InstrItins (& Subtarget . g e t I n s t r I t i n e r a r y D a t a ()) { }
A.1.2
RVEXTargetInfo
O registro da máquina alvo (RVEXTargetInfo.cpp) é feito declarando globalmente um objeto
do tipo Target, que será usado para representa-la durante o registro.
Target llvm :: TheRVEXTarget ;
extern " C " void L L V M I n i t i a l i z e R V E X T a r g e t I n f o () {
RegisterTarget < Triple :: rvex > X ( TheRVEXTarget , " rvex " , " RVEX [ experimental ] " );
}
A.2
Conjunto e classes de registradores
Como visto em 3.2.3, a definição do conjunto de registradores (RVEXRegisterInfo.td) consiste na extensão da classe Register para cada banco presente na arquitetura alvo. No caso do
ρ-VEX são dois bancos de registradores.
// R - VEX GR R e g i s t e r s
class RVEXGRReg < bits <5 > num , string n > : Register <n > {
field bits <5 > Num = num ;
}
// R - VEX BR R e g i s t e r s
class RVEXBRReg < bits <3 > num , string n > : Register <n > {
field bits <3 > Num = num ;
}
Um registrador ρ-VEX é definido declarando o numero referente a seu endereçamento e o
nome utilizado na emissão de código.
def R0
: RVEXGRReg < 0 ,
" r0 .0 " >;
A definição de uma classe de registradores é vista a seguir, no caso a classe GR do conjunto
de registradores ρ-VEX.
def GRRegs : RegisterClass < " RVEX " , [ i32 ] , 32 , ( add
// C o n s t a n t : always zero
facom-ufms
36
R0 ,
// Special : stack pointer
R1 ,
// Scratch : struct return pointer
R2 ,
// Scratch : a r g u m e n t s / return values
R3 , R4 , R5 , R6 ,
// Scratch : t e m p o r a r i e s
( sequence " R % u " , 7 , 25) ,
// P r e s e r v e d : t e m p o r a r i e s ( callee save )
R26 , R27 , R28 , R29 ,
// Special : link r e g i s t e r
L0 ,
// Special : r e s e r v e d for a s s e m b l e r
R31 ) > { }
Para a definição de informações não estáticas referentes ao conjunto de registradores do ρVEX a classe RVEXRegisterInfo (RVEXRegisterInfo.h e RVEXRegisterInfo.h) é declarada.
Ela é uma extensão da classe RVEXGenRegisterInfo, que por sua vez é gerada pela TableGen
a partir da definição do conjunto de registradores em RVEXRegisterInfo.td.
namespace llvm {
class RVEXInstrInfo ;
class RVEXSubtarget ;
class Type ;
struct R V E X R e gi s t e r I n f o : public R V E X G e n R e g i s t e r I n f o {
RVEXSubtarget & Subtarget ;
const RVEXInstrInfo & TII ;
R V E X R e g i s t e r I n f o ( RVEXSubtarget & st , const RVEXInstrInfo & tii );
// / Code G e n e r a t i o n virtual methods ...
const uint16_t * g e t C a l l e e S a v e d R e g s ( const Ma ch i ne Fu nc t io n * MF = 0) const ;
BitVector g e tR es er v ed Re gs ( const M a ch in eF u nc ti on & MF ) const ;
// / Stack Frame P r o c e s s i n g Methods
void e l i m i n a t e C a l l F r a m e P s e u d o I n s t r ( M a ch in eF u nc ti on & MF ,
M a c h i n e B a s i c B l o c k & MBB ,
M a c h i n e B a s i c B l o c k :: iterator I ) const ;
void e l i m i n a t e F r a m e I n d e x ( M a c h i n e B a s i c B l o c k :: iterator I ,
int SPAdj , RegScavenger * RS = NULL ) const ;
// Debug i n f o r m a t i o n queries .
unsigned g e t F r a m e Re g i s t e r ( const Ma ch i ne Fu nc t io n & MF ) const ;
unsigned g e t S t a c k Re g i s t e r () const ;
};
} // end n a m e s p a c e llvm
A descrição dos métodos da classe RVEXRegisterInfo podem ser visto em 3.2.3.
A.3
Conjunto de Instruções
Na definição do conjunto de instruções (RVEXInstrFormats.td e RVEXInstrInfo.td) a
classe Instruction foi extendida e todas as informações pertinentes a uma operação (ou sı́laba)
ρ-VEX declaradas.
class InstRVEX < dag outs , dag ins , string asmstr , list < dag > pattern ,
facom-ufms
37
Instr ItinCla ss itin , Type type > : Instruction {
field bits <32 > Inst ;
Type InstType = type ;
let Namespace = " RVEX " ;
let OutOper andList = outs ;
let InOperandList = ins ;
let AsmString
let Pattern
let Itinerary
= asmstr ;
= pattern ;
= itin ;
let Size = 4;
}
O campo Inst armazenará os 32 bits de uma operação ρ-VEX, ou seja, cada instrução tem um
tamanho (Size) de 32 bits (ou 4 bytes). Cada operação pertence ao namespace RVEX (campo
Namespace) para identificação. OutOperandList e InOperandList armazenaram os operandos
de saı́da e entrada, respectivamente. O campo AsmString armazenará o formato da instrução
utilizado na emissão de código. O campo Pattern armazenará o padrão utilizado na seleção de
instrução. O campo Itinerary armazenará o itinerário da operação utilizado no escalonamento
de instruções. O campo InstType identifica o tipo (formato) da operação. InstType é declarado
como o tipo Type definido abaixo:
def
def
def
def
def
def
def
PSEUDO
RTYPE
ISTYPE
ILTYPE
BRANCH
RTYPE_BS
MEMTYPE
:
:
:
:
:
:
:
Type <0 >;
Type <1 >;
Type <2 >;
Type <3 >;
Type <4 >;
Type <5 >;
Type <6 >;
Para cada formato de instrução presente no conjunto de instruções ρ-VEX a classe InstRVEX
foi extendida. Os detalhes de cada formato podem ser vistos em 3.2.5.
// PSEUDO I n s t r u c t i o n Class
class PSEUDOInst < dag outs , dag ins , string asmstr , list < dag > pattern >
: InstRVEX < outs , ins , asmstr , pattern , iiPSEUDO , PSEUDO > {
let isCodeGenOnly = 1;
let isPseudo = 1;
}
// RTYPE ( R e g i s t e r ) I n s t r u c t i o n Class
class RTYPEInst < bits <7 > op , dag outs , dag ins , string asmstr ,
list < dag > pattern , Instr ItinCla ss itin >
: InstRVEX < outs , ins , asmstr , pattern , itin , RTYPE > {
bits <6 > dst = 0;
bits <6 > src1 ;
bits <6 > src2 = 0;
bits <3 > dstBR = 0;
bits <1 > L ;
bits <1 > F ;
let
let
let
let
let
let
let
let
Inst {31 -25}
Inst {24 -23}
Inst {22 -17}
Inst {16 -11}
Inst {10 -5}
Inst {4 -2}
Inst {1}
Inst {0}
=
=
=
=
=
=
=
=
op ;
0;
dst ;
src1 ;
src2 ;
dstBR ;
L;
F;
// I m m e d i a t e switch : 0 ( no i m m e d i a t e value )
}
facom-ufms
// ISTYPE ( Short I m m e d i a t e ) I n s t r u c t i o n Class
class ISTYPEInst < bits <7 > op , dag outs , dag ins , string asmstr ,
list < dag > pattern , Inst rItinCla ss itin >
: InstRVEX < outs , ins , asmstr , pattern , itin , ISTYPE > {
bits <6 > dst ;
bits <6 > src1 ;
bits <9 > imm9 ;
bits <1 > L ;
bits <1 > F ;
let
let
let
let
let
let
let
Inst {31 -25}
Inst {24 -23}
Inst {22 -17}
Inst {16 -11}
Inst {10 -2}
Inst {1}
Inst {0}
=
=
=
=
=
=
=
op ;
1;
dst ;
src1 ;
imm9 ;
L;
F;
// I m m e d i a t e switch : 1 ( short i m m e d i a t e )
}
// ILTYPE ( Long I m m e d i a t e ) I n s t r u c t i o n Class
// TODO :
// BRANCH ( Branch Offset I m m e d i a t e ) I n s t r u c t i o n Class
class BRANCHInst < bits <7 > op , dag outs , dag ins , string asmstr ,
: InstRVEX < outs , ins , asmstr , pattern , itin , BRANCH > {
bits <6 > lr ;
bits <12 > imm12 ;
bits <3 > dstBR ;
bits <1 > L ;
bits <1 > F ;
let
let
let
let
let
let
let
Inst {31 -25}
Inst {24 -23}
Inst {22 -17}
Inst {16 -5}
Inst {4 -2}
Inst {1}
Inst {0}
=
=
=
=
=
=
=
op ;
2;
lr ;
imm12 ;
dstBR ;
L;
F;
// I m m e d i a t e switch : 2 ( branch offset i m m e d i a t e )
}
// R T Y P E _ B S ( R e g i s t e r BS ) I n s t r u c t i o n Class
class RTYPE_BSInst < bits <4 > op , dag outs , dag ins , string asmstr ,
: InstRVEX < outs , ins , asmstr , pattern , itin , RTYPE_BS > {
bits <3 > srcBR ;
bits <2 > SS ;
bits <6 > dst ;
bits <6 > src1 ;
bits <1 > L ;
bits <1 > F ;
let
let
let
let
let
let
let
Inst {31 -28}
Inst {27 -25}
Inst {24 -23}
Inst {22 -17}
Inst {16 -11}
Inst {1}
Inst {0}
=
=
=
=
=
=
=
op ;
srcBR ;
SS ;
dst ;
src1 ;
L;
F;
// I m m e d i a t e switch
}
// MEMTYPE ( Memory ) I n s t r u c t i o n Class
class MEMTYPEInst < bits <7 > op , dag outs , dag ins , string asmstr ,
: InstRVEX < outs , ins , asmstr , pattern , itin , MEMTYPE > {
bits <6 > dst ;
bits <6 > addr ;
bits <9 > imm9 ;
facom-ufms
38
bits <1 >
bits <1 >
let
let
let
let
let
let
let
39
L;
F;
Inst {31 -25}
Inst {24 -23}
Inst {22 -17}
Inst {16 -11}
Inst {10 -2}
Inst {1}
Inst {0}
=
=
=
=
=
=
=
op ;
1;
dst ;
addr ;
imm9 ;
L;
F;
// I m m e d i a t e switch : 1 ( short i m m e d i a t e )
}
A definição de uma instrução real consiste na extensão de um dos formatos vistos anteriormente.
def ADDrr : RTYPEInst <65 , ( outs GRRegs : $dst ) , ( ins GRRegs : $src1 , GRRegs : $src2 ) ,
" add $dst = $src1 , $src2 " , [( set ( i32 GRRegs : $dst ) , ( add ( i32 GRRegs : $src1 ) ,
( i32 GRRegs : $src2 )))] ,
iiALU >;
A operação define o opcode, os operandos de saı́da e entrada, o formato assembly, o padrão
para seleção de instruções e o itinerário da instrução. Os operandos são todos registradores e o
padrão utilizado na seleção de instruções define que a partir de dois operandos de entrada de 32
bits se produz um resultado que será salvo (set) em um operando de saı́da (também de 32 bits)
através de uma operação de adição (add ).
O itinerário de uma operação é definido no arquivo RVEXSchedule.td. Nesse arquivo
também são definidos os padrões de escalonamento de operações em uma instrução ρ-VEX.
Cada itinerário define em quais unidades funcionais (SLOT* ) uma operação pode ser executada,
assim como a quantidade de estágios da operação. Essas informações também são utilizadas no
RVEXVLIWPacketizer.
// I t i n e r a r y classes
def iiALU
: Inst rItinCla ss ;
def iiMUL
: Inst rItinCla ss ;
def iiMEM_LD : Ins trItinCl ass ;
def iiMEM_ST : Ins trItinCl ass ;
def iiCTRL
: InstrI tinClass ;
def iiSPECIAL : Instr ItinClas s ;
def iiPSEUDO : Ins trItinCl ass ;
// F u n c t i o n a l
def SLOT3
def SLOT2
def SLOT1
def SLOT0
Units
: FuncUnit ;
: FuncUnit ;
: FuncUnit ;
: FuncUnit ;
def R VE XI t in er ar i es :
ProcessorItineraries < [ SLOT3 , SLOT2 , SLOT1 , SLOT0 ] , [] , [
InstrItinData < iiALU ,
[ InstrStage <8 , [ SLOT3 , SLOT2 , SLOT1 , SLOT0 ] >] > ,
InstrItinData < iiMUL ,
[ InstrStage <9 , [ SLOT2 , SLOT1 ] >] > ,
InstrItinData < iiCTRL ,
[ InstrStage <7 , [ SLOT3 ] >] > ,
InstrItinData < iiMEM_LD , [ InstrStage <9 , [ SLOT0 ] >] > ,
InstrItinData < iiMEM_ST , [ InstrStage <10 , [ SLOT0 ] >] > ,
InstrItinData < iiSPECIAL , [ InstrStage <7 , [ SLOT3 , SLOT2 , SLOT1 , SLOT0 ] >] > ,
InstrItinData < iiPSEUDO , [ InstrStage <7 , [ SLOT3 , SLOT2 , SLOT1 , SLOT0 ] >] >
] >;
def RVEXModel : S c h e d M a c h i n e M o d e l {
// Max issue per cycle == bundle width .
let IssueWidth = 4;
let Itineraries = RV EX I ti ne ra r ie s ;
}
facom-ufms
40
Por ser um processador VLIW o ρ-VEX define um modelo de escalonamento onde é especificado o tamanho do bundle (IssueWidth).
A classe RVEXInstrInfo (RVEXInstrInfo.h e RVEXInstrInfo.cpp) define as informações não estáticas do conjunto de instruções ρ-VEX. Ela é uma extensão da classe
RVEXGenInstrInfo, que por sua vez é gerada pela TableGen a partir das definições nos arquivos RVEXInstrFormats.td, RVEXInstrInfo.td e RVEXSchedule.td.
namespace llvm {
class RVEXInstrInfo : public R V E X G e n I n s tr I n f o {
const R V E X R e g i s t e r I n f o RI ;
const RVEXSubtarget & Subtarget ;
public :
explicit RVEXInstrInfo ( RVEXSubtarget & st );
virtual const R V E X R eg i s t e r I n f o & g e tR eg is t er In fo () const { return RI ; }
virtual unsigned i s L o a d F r o m S t a c k S l o t ( const MachineInstr * MI ,
int & FrameIndex ) const ;
virtual unsigned i s S t o r e T o S t a c k S l o t ( const MachineInstr * MI ,
int & FrameIndex ) const ;
virtual void copyPhysReg ( M a c h i n e B a s i c B l o c k & MBB ,
M a c h i n e B a s i c B l o c k :: iterator I , DebugLoc DL ,
unsigned DestReg , unsigned SrcReg ,
bool KillSrc ) const ;
virtual void s t o r e R e g T o S t a c k S l o t ( M a c h i n e B a s i c B l o c k & MBB ,
M a c h i n e B a s i c B l o c k :: iterator MBBI ,
unsigned SrcReg , bool isKill , int FrameIndex ,
const T a r g e t R e g i s t e r C l a s s * RC ,
const T a r g e t R e g i s t e r I n f o * TRI ) const ;
virtual void l o a d R e g F r o m S t a c k S l o t ( M a c h i n e B a s i c B l o c k & MBB ,
M a c h i n e B a s i c B l o c k :: iterator MBBI ,
unsigned DestReg , int FrameIndex ,
const T a r g e t R e g i s t e r C l a s s * RC ,
const T a r g e t R e g i s t e r I n f o * TRI ) const ;
virtual bool AnalyzeBranch ( M a c h i n e B a s i c B l o c k & MBB , M a c h i n e B a s i c B l o c k *& TBB ,
M a c h i n e B a s i c B l o c k *& FBB ,
SmallVectorImpl < MachineOperand > & Cond ,
bool AllowModify = false ) const ;
virtual unsigned InsertBranch ( M a c h i n e B a s i c B l o c k & MBB , M a c h i n e B a s i c B l o c k * TBB ,
M a c h i n e B a s i c B l o c k * FBB ,
const SmallVectorImpl < MachineOperand > & Cond ,
DebugLoc DL ) const ;
virtual unsigned RemoveBranch ( M a c h i n e B a s i c B l o c k & MBB ) const ;
virtual bool i s S c h e d u l i n g B o u n d a r y ( const MachineInstr * MI ,
const M a c h i n e B a s i c B l o c k * MBB ,
const Ma ch i ne Fu nc t io n & MF ) const ;
virtual DFAPacketizer * C r e a t e T a r g e t S c h e d u l e S t a t e ( const TargetMachine * TM ,
const ScheduleDAG * DAG ) const ;
};
}
Os métodos que compõem a classe RVEXInstrInfo são implementações das interfaces descritas na classe TargetInstrInfo e manipulam o código gerado a fim de tratar instruções de
memória e otimizações de acordo com algumas especificações da máquina alvo. Por exemplo,
facom-ufms
41
os métodos AnalyzeBranch, InsertBranch e RemoveBranch são responsáveis pela analise e caso
necessário, remoção (em casos onde duas instruções de desvio são geradas, mas a primeira instrução é um desvio incondicional o que torna o restante do código não executável possibilitando
sua remoção) e inserção (quando duas instruções de desvio ou de comparação e desvio, podem
ser simplificadas inserindo outra instrução de desvio no lugar).
A.4
Lowering
Como visto em 3.2.6, a classe RVEXTargetLowering (RVEXISelLowering.h e
RVEXISelLowering.cpp) irá definir instruções e tipos não suportados diretamente pela
arquitetura alvo e que necessitam ser convertidos para instruções e tipos da própria LLVM IR
possı́velmente suportados.
class R V E X T a r g e t L o w e r i n g : public Targ etLower ing {
public :
R V E X T a r g e t M a c h i n e & TM ;
explicit R V E X T a r g e t L o w e r i n g ( R V E X T a r g e t M a c h i n e & tm );
// / L o w e r O p e r a t i o n - Provide custom l o w e r i n g hooks for some o p e r a t i o n s .
virtual SDValue Lo werOpera tion ( SDValue Op , SelectionDAG & DAG ) const ;
SDValue L o w e r G l o b a l A d d r e s s ( SDValue Op , SelectionDAG & DAG ) const ;
SDValue Lo werSELEC T_CC ( SDValue Op , SelectionDAG & DAG ) const ;
virtual SDValue P e r f o r m D A G C o m b i n e ( SDNode *N , DA GC om b in er In f o & DCI ) const ;
virtual SDValue
L o w e r F o r m a l A r g u m e n t s ( SDValue Chain ,
CallingConv :: ID CallConv , bool isVarArg ,
const SmallVectorImpl < ISD :: InputArg > & Ins ,
DebugLoc dl , SelectionDAG & DAG ,
SmallVectorImpl < SDValue > & InVals ) const ;
SDValue
LowerCall ( TargetL owering :: C a l l L o w e r i n gI n f o & CLI ,
SmallVectorImpl < SDValue > & InVals ) const ;
virtual SDValue
LowerReturn ( SDValue Chain ,
CallingConv :: ID CallConv , bool isVarArg ,
const SmallVectorImpl < ISD :: OutputArg > & Outs ,
const SmallVectorImpl < SDValue > & OutVals ,
DebugLoc dl , SelectionDAG & DAG ) const ;
// / g e t T a r g e t N o d e N a m e - This method returns the name of a target s p e c i f i c
// DAG node .
virtual const char * g e t T a r g e t N o d e N a m e ( unsigned Opcode ) const ;
};
No construtor da classe será descrito o conjunto de instruções e tipos não suportados que
necessitam de tratamento antes da seleção de instruções. Também são definidos declarados ao
seletor de instruções as classes de registradores e seus respectivos tipos (tamanhos). O tipo de
escalonamento preferido pela máquina alvo também é definido no construtor.
R V E X T a r g e t L o w e r i n g :: R V E X T a r g e t L o w e r i n g ( R V E X T a r g e t M a c h i n e & tm )
: Target Lowering ( tm , new T a r g e t L o w e r i n g O b j e c t F i l e E L F ()) ,
TM ( tm ) {
// Set up the r e g i s t e r classes
a d d R e g i s t e r C l a s s ( MVT :: i32 , & RVEX :: GRRegs RegClas s );
a d d R e g i s t e r C l a s s ( MVT :: i1 , & RVEX :: BRRegsR egClass );
facom-ufms
42
c o m p u t e R e g i s t e r P r o p e r t i e s ();
s e t O p e r a t i o n A c t i o n ( ISD :: GlobalAddress ,
MVT :: i32 ,
Custom );
// Lower S E L E C T _ C C to SETCC and SELECT .
s e t O p e r a t i o n A c t i o n ( ISD :: SELECT_CC ,
s e t O p e r a t i o n A c t i o n ( ISD :: SELECT_CC ,
MVT :: i32 ,
MVT :: Other ,
Custom );
Expand );
s e t O p e r a t i o n A c t i o n ( ISD :: BR_CC ,
s e t O p e r a t i o n A c t i o n ( ISD :: BR_CC ,
MVT :: i32 ,
MVT :: Other ,
Expand );
Expand );
s e t O p e r a t i o n A c t i o n ( ISD :: MULHS ,
s e t O p e r a t i o n A c t i o n ( ISD :: MULHU ,
s e t O p e r a t i o n A c t i o n ( ISD :: SMUL_LOHI ,
s e t O p e r a t i o n A c t i o n ( ISD :: UMUL_LOHI ,
MVT :: i32 ,
MVT :: i32 ,
MVT :: i32 ,
MVT :: i32 ,
Expand );
Expand );
Expand );
Expand );
s e t S t a c k P o i n t e r R e g i s t e r T o S a v e R e s t o r e ( RVEX :: R1 );
s e t M i n F u n c t i o n A l i g n m e n t (2);
s e t S c h e d u l i n g P r e f e r e n c e ( Sched :: VLIW );
}
As instruções (operações) para um determinado tipo marcadas como Expand serão divididas
em operações com tipos menores. Já as marcadas como Custom terão tratamento customizado
implementado no back-end.
O método LowerOperation irá filtra as instruções que terão tratamento customizado e chamar
os métodos de tramento referentes.
SDValue
R V E X T a r g e t L o w e r i n g :: LowerO peration ( SDValue Op , SelectionDAG & DAG ) const {
switch ( Op . getOpcode ()) {
default : l l v m _ u n r e a c h a b l e ( " Should not custom lower this ! " );
case ISD :: GlobalAddress :
return L o w e r G l o b a l A d d r e s s ( Op , DAG );
case ISD :: SELECT_CC :
return LowerSE LECT_CC ( Op , DAG );
}
}
A.5
Seleção de Instruções
A classe RVEXDAGToDAGISel (RVEXISelDAGToDAG.cpp) fica responsável pela conversão de
instruções da LLVM IR não suportadas pela máquina alvo em instruções suportadas. O método
Select irá receber um SDNode que será analisado e caso necessário será substituı́do por outro
SDNode ou até mesmo por uma sub-arvore de SDNodes com instruções (nós) que em conjunto são
equivalentes. Em casos especı́ficos o SDNode pode ser removido. Em caso de substituição, todas
as ocorrências do nó também serão substituı́das. Métodos auxiliares também são definidos
(como o caso de getInstrInfo e getTargetMachine) para que a seleção seja de acordo com as
caracterı́sticas da máquina alvo. Os métodos Select* irão fazer a manipulação necessária para
substituir ou remover o SDNode não nativo. O método SelectAddr é utilizado pelo seletor de
instruções do LLVM para tratar instruções de memória.
namespace {
class R V E X D A G T o D A G I S e l : public S el e c t i o n D A G I S e l {
const RVEXSubtarget & Subtarget ;
R V E X T a r g e t M a c h i n e & TM ;
facom-ufms
43
public :
explicit R V E X D A G T oD A G I S e l ( R V E X T a r g e t M a c h i n e & tm ) :
S e l e c t i o n D A G I S e l ( tm ) ,
Subtarget ( tm . getSubtarget < RVEXSubtarget >()) ,
TM ( tm ) {}
SDNode * Select ( SDNode * N );
SDNode * Sel ectConst ant ( SDNode * N );
SDNode * SelectMul ( SDNode * N );
// Pass Name
virtual const char * getPassName () const {
return " RVEX DAG - > DAG Pattern Instruction Selection " ;
}
const R V E X T a r g e t M a c h i n e & g e t T a r g e t M a c h i n e () {
return static_cast < const R V E X T a r g e t M a c h i n e & >( TM );
}
const RVEXInstrInfo * getInstrInfo () {
return g e t T a r g et M a c h i n e (). getInstrInfo ();
}
bool SelectAddr ( SDValue & Addr , SDValue & Base , SDValue & Offset );
// Include the pieces a u t o g e n e r a t e d from the target d e s c r i p t i o n .
# include " R VEXGenD AGISel . inc "
};
O método Select para a versão do back-end LLVM para o processador ρ-VEX pode ser visto
a seguir:
SDNode * R V E X D A G T o D A G I Se l :: Select ( SDNode * N ) {
if (N - > is Ma ch i ne Op co d e ()) {
return NULL ;
}
switch (N - > getOpcode ()) {
default : break ;
case ISD :: Constant :
return Selec tConstan t ( N );
case ISD :: MUL :
return SelectMul ( N );
}
return SelectCode ( N );
}
Caso uma constante ou a instrução MUL seja identificada, os métodos SelectConstant e
SelectMul são chamados para trata-los.
A.6
Prólogo e Epı́logo
Na classe RVEXFrameLowering (RVEXFrameLowering.h e RVEXFrameLowering.cpp) são
definidos os métodos responsáveis pela emissão do prólogo e epı́logo.
namespace llvm {
class R V E X F r a m e L o w e r i n g : public T a r g e t F r a m e L o w e r i n g {
facom-ufms
44
private :
const RVEXSubtarget & STI ;
public :
explicit R V E X F r a m e L o w e r i n g ( const RVEXSubtarget & sti )
: T a r g e t F r a m e L o w e r i n g ( StackGrowsDown , 8 , 0) ,
STI ( sti ) {}
void emitPrologue ( Ma c hi ne Fu n ct io n & MF ) const ;
void emitEpilogue ( Ma c hi ne Fu n ct io n & MF , M a c h i n e B a s i c B l o c k & MBB ) const ;
bool hasFP ( const Ma c hi ne Fu n ct io n & MF ) const ;
};
} // End llvm n a m e s p a c e
A.7
Packetizer
A classe RVEXPacketizer (RVEXVLIWPacketizer) define o pass para a construção dos bundles
(packets) e a classe RVEXPacketizerList sobrescreve alguns métodos da classe VLIWPacketizerList que por sua vez implementa o VLIW Packetizer usando um autômato finito determinı́stico
(AFN). O Packetizer manipula blocos básicos e para cada instrução de um bloco básico são feitas
verificações tanto da disponibilidade de unidades funcionais quanto de dependências entre as demais instruções em um packet corrente. Caso nenhuma dependência seja encontrada a instrução
é adicionada ao packet (de acordo com o tamanho do packet), caso contrário, a dependência é
tratada.
namespace {
class RVE XPacket izer : public M a c h i n e F u n c t i o n P a s s {
public :
static char ID ;
RVEXP acketiz er () :
M a c h i n e F u n c t i o n P a s s ( ID ) {
}
void g e t A n a l y s i s U s a g e ( AnalysisUsage & AU ) const {
AU . s e tP re se r ve sC FG ();
AU . addRequired < MachineDominatorTree >();
AU . addPreserved < MachineDominatorTree >();
AU . addRequired < MachineLoopInfo >();
AU . addPreserved < MachineLoopInfo >();
M a c h i n e F u n c t i o n P a s s :: g et A n a l y s i s U s a g e ( AU );
}
const char * getPassName () const {
return " RVEX Packetizer " ;
}
bool r u n O n M a c h i n e F u n c t i o n ( M a ch in eF u nc ti on & Fn );
};
char RVEXPack etizer :: ID = 0;
class R V E X P a c k e t i z e r L i s t : public V L I W P a c k e t i z e r L i s t {
private :
// Check if there is a d e p e n d e n c e between some i n s t r u c t i o n already in this
// packet and this i n s t r u c t i o n .
bool Dependence ;
facom-ufms
45
// Only check for d e p e n d e n c e if there are r e s o u r c e s a v a i l a b l e to
// s c h e d u l e this i n s t r u c t i o n .
bool F o u n d S e q u e n t i a l D e p e n d e n c e ;
public :
// Ctor .
R V E X P a c k e t i z e r L i s t ( M ac hi ne F un ct io n & MF , M ac hi n eL oo pI n fo & MLI ,
M a c h i n e D o m i n a t o r T r e e & MDT );
// i n i t P a c k e t i z e r S t a t e - i n i t i a l i z e some i n t e r n a l flags .
void i n i t P a c k e t i z e r S t a t e ();
// i g n o r e P s e u d o I n s t r u c t i o n - Ignore b u n d l i n g of pseudo i n s t r u c t i o n s .
bool i g n o r e P s e u d o I n s t r u c t i o n ( MachineInstr * MI , M a c h i n e B a s i c B l o c k * MBB );
// i s L e g a l T o P a c k e t i z e T o g e t h e r - Is it legal to p a c k e t i z e SUI and SUJ
// t o g e t h e r .
bool i s L e g a l T o P a c k e t i z e T o g e t h e r ( SUnit * SUI , SUnit * SUJ );
// i s S o l o I n s t r u c t i o n - return true if i n s t r u c t i o n MI can not be p a c k e t i z e d
// with any other instruction , which means that MI itself is a packet .
bool i s S o l o I n s t r u c t i o n ( MachineInstr * MI );
// M a c h i n e B a s i c B l o c k :: i t e r a t o r a d d T o P a c k e t ( M a c h i n e I n s t r * MI );
private :
bool I sC al lD e pe nd en t ( MachineInstr * MI , SDep :: Kind DepType , unsigned DepReg );
};
}
Os métodos ignorePseudoInstruction, isLegalToPacketizeTogether, isSoloInstruction, IsCallDependent são sobrescritos para tratar determinados casos de acordo com as especificações
da máquina ρ-VEX. O método isLegalToPacketizeTogether por exemplo, verifica se uma determinada instrução pode ser adiciona ao packet corrente analisando as dependências entre ela e
as instruções presentes no packet.
A.8
Emissão de código
A classe RVEXAsmPrinter (RVEXAsmPrinter.h e RVEXAsmPrinter.cpp) define os métodos
responsáveis pela emissão de código do back-end LLVM para o ρ-VEX de acordo com as especificações da linguagem de montagem do processador.
class RVE XAsmPri nter : public AsmPrinter {
const RVEXSubtarget * Subtarget ;
public :
explicit RVEXA smPrint er ( TargetMachine & TM , MCStreamer & Streamer )
: AsmPrinter ( TM , Streamer ) {
Subtarget = & TM . getSubtarget < RVEXSubtarget >();
}
virtual const char * getPassName () const {
return "r - VEX Assembly Printer " ;
}
bool i s B l o c k O n l y R e a c h a b l e B y F a l l t h r o u g h ( const M a c h i n e B a s i c B l o c k * MBB ) const ;
virtual void E mi tI n st ru ct i on ( const MachineInstr * MI );
facom-ufms
void printOperand ( const MachineInstr * MI , int opNum , raw_ostream & O );
bool P ri nt As m Op er an d ( const MachineInstr * MI , unsigned OpNo ,
unsigned AsmVariant , const char * ExtraCode ,
raw_ostream & O );
bool P r i n t A s m M e m o r y O p e r a n d ( const MachineInstr * MI , unsigned OpNum ,
unsigned AsmVariant , const char * ExtraCode ,
raw_ostream & O );
// / p r i n t I n s t r u c t i o n - This method is a u t o m a t i c a l l y g e n e r a t e d by t a b l e g e n
// / from the i n s t r u c t i o n set d e s c r i p t i o n . This method returns true if the
// / machine i n s t r u c t i o n was s u f f i c i e n t l y d e s c r i b e d to print it , o t h e r w i s e it
// / returns false .
void p r i n t I n s t r u c t i o n ( const MachineInstr * MI , raw_ostream & O );
// / p r i n t R e g i s t e r - Print r e g i s t e r a c c o r d i n g to target r e q u i r e m e n t s .
// /
void printRegister ( const Mac hineOper and & MO , bool R0AsZero ,
raw_ostream & O ) {
unsigned RegNo = MO . getReg ();
assert ( T a r g e t R e g i s t e r I n f o :: i s P h y s i c a l R e g i s t e r ( RegNo ) && " Not physreg ?? " );
O << g et Re g is te rN a me ( RegNo );
}
void p r i n t U n s i g n e d I m m O p e r a n d ( const MachineInstr * MI , int opNum , raw_ostream & O );
void p ri nt Me m Op er an d ( const MachineInstr * MI , int opNum , raw_ostream & O );
// void E m i t S t a r t O f A s m F i l e ( Module & M );
static const char * ge tR eg i st er Na m e ( unsigned RegNo );
};
facom-ufms
46
Referências Bibliográficas
[1] C. A. Lattner, “LLVM: An Infrastructure for Multi-stage Optimization,” Master’s thesis,
University of Illinois at Urbana-Champaign, 2002. Faculdade de Computação.
[2] C. Lattner and V. Adve, “LLVM: A Compilation Framework for Lifelong Program Analysis
& Transformation,” in Proceedings of the 2004 International Symposium on Code Generation and Optimization, (Palo Alto, CA, USA), Mar 2004.
[3] J. A. Fisher, P. Faraboschi, and C. Young, Embedded Computing: A VLIW Approach to
Architecture, Compilers and Tools. Elsevier, 2005.
[4] Hewlett-Packard Laboratories, “VEX Toolchain.” Disponı́vel em: http://www.hpl.hp.
com/downloads/vex/, Março 2011.
[5] T. van As, “ρ-VEX: A Reconfigurable and Extensible vliw Processor,” Master’s thesis,
Delft University of Technology, 2008. Faculty of Electrical Engineering, Mathematics and
Computer Science.
[6] T. van As, S. Wong, and G. Brown, “ρ-VEX: A Reconfigurable and Extensible VLIW Processor,” in Proceedings of the International Conference on Field-Programmable Technology,
IEEE, 2008.
[7] M. Len and I. Vaitsman, “VLIW: Old Architecture of the New Generation,” Mar. 2011.
http://ixbtlabs.com/articles2/vliw/.
[8] G. W. A. Brown, The Architecture of Open Source Applications: Elegance, Evolution, and
a Few Fearless Hacks. CreativeCommons, 2011.
[9] T. L. Team, “DragonEgg.” Website. http://dragonegg.llvm.org/.
[10] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, “Efficiently Computing Static Single Assignment Form and the Control Dependence Graph,” ACM Transactions on Programming Languages and Systems, vol. 13, pp. 451–490, Oct 1991.
[11] L. N. Chakrapani, J. Gyllenhaal, W. Mei, W. Hwu, S. A. Mahlke, K. V. Palem, and R. M.
Rabbah, “Trimaran - An Infrastructure for Research in Instruction-Level Parallelism,”
Lecture Notes in Computer Science, vol. 3602, pp. 32–41, 2004.
[12] R. A. Marks, “Infraestrutura para Codificação de Instruções Baseada em Fatoração de
Padrões,” Master’s thesis, Universidade Federal de Mato Grosso do Sul, 2012. Faculdade
de Computação.
47
REFERÊNCIAS BIBLIOGRÁFICAS
48
[13] L. da Costa Silva, “Algoritmos para Escalonamento de Instruções e Alocação de Registradores na Infraestrutura LLVM,” Master’s thesis, Universidade Federal de Mato Grosso
do Sul, 2013. Faculdade de Computação.
facom-ufms

UNIVERSIDADE FEDERAL DO MATO GROSSO - LSCAD

Transcrição

Documentos relacionados

1 Os microprocessadores 8086/8088

Bolıvar – uma alternativa livre para simulaç ˜ao de arquiteturas

Untitled - Prof. Marcelo Andrade

processador

Trabalho 1 1 Introdução 2 Descrição 3 Avaliação

Homilia Missa das Bodas de Ouro de Papai e Mamãe_1977

Mapeamento de instruções Dataflow

CÓD: 23311 PLACA DE VIDEO RADEON R7 240 2GB DDR3 64 BITS

Untitled - Clube dos Recreadores

OS COMPONENTES BÁSICOS DE UM COMPUTADOR A função de

Tecnico em Informatica