Compiladores: Otimização de Código e a Linguagem Java

Prévia do material em texto

COMPILADORES 
AULA 6 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Frank Coelho de Alcantara 
 
 
2 
CONVERSA INICIAL 
Depois de passar por todos os módulos anteriores, o seu algoritmo, 
representado pelo seu código-fonte, já não pode ser reconhecido como texto, e 
está representado na forma de uma estrutura de dados, sem erros de sintaxe ou 
semântica, permitindo a transcrição em linguagem de máquina. Esse é o último 
estágio do processo de compilação, e o chamaremos de otimização de código, 
simplesmente porque é nesse ponto que serão realizadas as adequações do seu 
algoritmo à linguagem de máquina. 
Estamos em um ponto do processo no qual o analisador semântico 
acabou de verificar seu código, você corrigiu os últimos erros encontrados, todos 
os tipos estão corretamente atribuídos, não existem erros na definição de 
variáveis ou funções e, finalmente, vamos gerar o código de máquina que será 
executado pela sua CPU. Esse código precisa ser eficiente, rápido e pequeno, 
de forma que seu programa seja executado sem desperdiçar recursos. Essa foi 
uma preocupação transversal a todo o processo de compilação, mas até agora 
não estávamos preocupados com as características físicas da sua CPU. 
Nesse módulo final, antes de criar o arquivo que será executado, temos 
que nos preocupar com as características físicas da máquina. Quantos 
registradores temos disponíveis? É uma arquitetura de 64 bits? Temos memória 
cache? Quais instruções a máquina entende? Essas são apenas algumas das 
perguntas que precisam ser respondidas antes que o processo de otimização de 
código tenha início. 
É nessa fase do processo que geraremos um código especial, o código 
intermediário, a partir da árvore semântica, e ele será utilizado para as primeiras 
otimizações. Depois, esse código intermediário será transformado na linguagem 
de máquina desejada e sofrerá as últimas otimizações, sendo, finalmente, 
convertido em código executável. 
Existem muitas técnicas interessantes de otimização de código que são 
específicas de uma determinada arquitetura. Essa é a razão que justifica o 
estudo das técnicas de configuração de compiladores. Todos os compiladores 
precisam ser informados, antes de começar o processo de compilação, sobre 
qual é a arquitetura alvo. Assim, na fase de otimização de código, será possível 
adotar técnicas de otimização adequadas à arquitetura desejada. Veremos nesta 
aula os conceitos referentes à geração do código intermediário e alguns dos 
processos de otimização. 
 
 
3 
TEMA 1 – O JAVA E A COMPILAÇÃO 
A linguagem Java é excelente, talvez uma das melhores linguagens já 
definidas para a programação e, como toda linguagem de programação, tem 
seus adoradores e aqueles que a odeiam. Acredito que a maior contribuição do 
Java esteja nas técnicas de compilação e interpretação que tiveram de ser 
criadas e aprimoradas de forma que os programas desenvolvidos em Java sejam 
competitivos com os programas compilados para uma arquitetura específica. O 
Java é uma linguagem na qual o programa resultante só será executado após 
dois passos distintos, uma compilação e uma interpretação. 
Para entender o Java é preciso entender o seu tempo e as razões que 
fundamentaram sua criação. Falamos do ano de 1995: a Sun Microsystems 
estava em um ritmo acelerado de crescimento e em franco processo de 
conquista do mercado de ambientes de alta performance, que eram 
notadamente ambientes de produção gráfica e de servidores de bancos de 
dados. Um mercado dividido entre vários tipos de sistemas operacionais 
derivados do Unix, além de várias distribuições Linux e o Windows. 
Nesse tempo, o processo de compilação era lento, complexo e específico. 
Todas as versões de um determinado software que almejasse a execução em 
Linux, Unix e Windows precisaria de uma equipe específica e de um processo 
de compilação e de otimização adequado a cada um desses sistemas 
operacionais. Esse não era um problema trivial e, via de regra, além de exigir 
uma equipe especializada, requeria muitas horas de trabalho. O mundo da 
tecnologia era lento, caro e complicado. 
James Gosling teve uma ideia genial. Partindo das melhores 
características do C++, e de forma a garantir o controle da Sun sobre a nova 
linguagem, criou uma linguagem nova, sobre um novo paradigma. O código 
deveria ser escrito uma única vez e executado em qualquer combinação de 
máquina e sistema operacional sem a necessidade de nova compilação e sem 
que a equipe de desenvolvimento necessitasse de conhecimentos profundos de 
otimização para cada uma das combinações possíveis de hardware e sistema 
operacional. Na época, quase mágica. 
O projeto de Gosling acabaria por produzir um ambiente de compilação 
dividido em três fases. Na primeira, front-end, estariam todos os processos 
relacionados com a linguagem de programação de alto nível (análise léxica, 
 
 
4 
sintática, semântica); na segunda, a geração de um código objeto, código 
intermediário, e, na terceira, todos os processos relacionados à linguagem de 
máquina. Nessa última fase o código intermediário gerado seria interpretado em 
uma máquina virtual, como pode ser visto na Figura 1: 
Figura 1 – Sistema de compilação do Java 
 
O arquivo seucodigo.java contém o algoritmo que o programador deseja 
criar. Esse arquivo é gravado em disco e depois compilado em um compilador 
AOT (Ahead of Time). O código será submetido a um analisador léxico, a um 
analisador sintático, a um analisador semântico e, finalmente, passará por um 
processo de otimização e geração de código-objeto, produzindo o arquivo 
seucodigo.class. E aqui está a mágica: o arquivo seucodigo.class pode ser 
armazenado em disco, transportado e executado por qualquer máquina virtual 
Java independentemente da plataforma de execução e sem nenhum 
conhecimento da arquitetura alvo. 
Duas coisas merecem destaque: 1. o código-objeto é chamado de 
bytecode e trata-se, na verdade, de uma linguagem, muito próxima da linguagem 
de máquina, com características específicas voltadas para a otimização; 2. a 
máquina virtual é na verdade um interpretador de bytecode para a arquitetura 
desejada. 
Esse bytecode pode ser entendido como sendo outra linguagem de 
programação. Uma linguagem de baixo nível adequada ao ambiente de 
interpretação da máquina virtual e, como toda linguagem, possui suas 
características próprias. Um conjunto de lexemas, sintaxe e semântica 
 
 
5 
específicos. Como qualquer linguagem, precisa passar por um processo de 
conversão em linguagem de máquina para que possa ser executado. 
Todas as características do bytecode da linguagem Java estão muito bem 
documentadas e, se for o caso, você poderá se aprofundar nesses detalhes 
procurando as especificações diretamente na página da Oracle. A versão mais 
recente é a The Java Virtual Machine Specification, Java SE 8 Edition1. 
O processo de interpretação dentro da máquina virtual Java merece um 
pouco de atenção. Primeiro, você precisa ter em mente que todos os processos 
rodam de forma interligada e interdependente, como se o próprio hardware 
(virtual) estivesse interferindo no processo de interpretação e execução. O 
arquivo seucodigo.class é submetido ao compilador. Trata-se de um compilador 
JIT (Just in Time) ou, mais tecnicamente, compilador de transição dinâmica. 
ATENÇÃO: muito cuidado. Se você olhar bem, as definições de interpretador, 
compilador JIT e compilador de transição dinâmica se confundem. Em todos os 
casos trata-se de um sistema que irá traduzir um código em uma linguagem 
qualquer em linguagem de máquina. Essas denominações diferentes são 
apenas para que você possa colocar os conceitos nos lugares certos. Então, um 
interpretador pode ter um compilador JIT no seu interior, mas a operação 
contrária não é possível. 
O JIT-Java recebe todas as classes do programa que deverá ser 
executado em bytecode e, antes de qualquer coisa, fazuma verificação estática 
das propriedades e características do arquivo seucodigo.class; por questões de 
segurança e confiabilidade, verifica também a estrutura léxica e sintática, 
notadamente a construção de métodos e parâmetros. Essa verificação é 
necessária porque as máquinas virtuais Java podem receber bytecode 
proveniente de outras linguagens, a Scala, por exemplo. Em seguida começa o 
processo de interpretação/compilação. 
A interpretação é lenta. Expressões simples, compostas apenas de 
variáveis locais, tais como 𝑥 = 𝑦 + (2 ∗ 𝑧), que em bytecode poderia ser 
codificada como apresentado na Figura 2. 
 
 
1 Disponível em: http://docs.oracle.com/javase/specs/jvms/se8/jvms8.pdf. 
 
 
6 
Figura 2 – Exemplo de bytecode, resultado da compilação de uma expressão 
simples (Cramer, Friedman, et al., 1997) 
 
Analisando o código da Figura 2, é possível perceber porque o Java, 
quando interpretado, é lento. Para executar esse código é necessário decodificar 
seis linhas em bytecode, colocar cinco valores na pilha de operação e retirá-los 
de lá. Um programa em Java típico é composto de centenas de métodos. 
Interpretar cada um desses métodos torna o programa muito lento. A opção seria 
compilar o programa antes de executá-lo. Contudo, a compilação também 
tomaria tempo e recursos de memória, e faria com que o usuário tivesse de 
esperar um longo tempo antes de conseguir utilizar o programa. 
Na prática, os métodos não são compilados na sua primeira execução. 
Para cada método a máquina virtual mantém um contador de chamadas do 
próprio método. Todas as vezes em que um determinado método é chamado 
esse contador é incrementado. Quando o contador atinge um número 
determinado, o método é compilado da forma mais rápida possível e 
armazenado em memória. A partir desse ponto, sempre que o método for 
chamado, o código compilado será executado e não haverá nenhuma nova 
interpretação para este código. 
Uma vez que o código seja compilado, o contador de chamadas é zerado 
e começa a ser incrementado novamente. Se esse número atingir um novo valor 
pré-determinado, o método será novamente compilado, dessa vez com uma 
configuração de otimização mais agressiva em busca de uma velocidade de 
execução ainda melhor. 
Sempre que um método é enviado para a compilação maiores serão as 
otimizações necessárias e, consequentemente, maior será o tempo necessário 
para a compilação. A lista de possíveis compilações varia de máquina virtual 
para máquina virtual. Assim, a máquina virtual Java da IBM pode ter uma 
 
 
7 
performance melhor que a máquina virtual Java da Oracle2 em alguns cenários, 
e não em outros. 
De uma forma ou de outra, usamos técnicas de compilação JIT desde os 
anos 1960. Nesse caso, nada é mais forte que a máxima popular: “quem não 
conhece sua história está condenado a repeti-la”. A compilação dinâmica é o fato 
que justifica a máxima. As máquinas que rodavam o Basic nos anos 1970-80 já 
utilizavam essa mesma técnica para otimizar a execução dos programas. De lá 
para cá, talvez graças ao Java, tais técnicas foram resgatadas e otimizadas de 
tal forma que parecem apontar para o futuro da compilação. 
TEMA 2 – A APPLE ESCOLHE O LLVM 
Em 2000, um grupo de estudantes da Universidade de Illinois liderado 
pelo professor Vikram Adve e por Chris Lattner iniciou um projeto para o estudo 
de técnicas de compilação dinâmica chamado de Low Level Virtual Machine, ou 
LLVM. Esse projeto resultou na dissertação de mestrado de Chris Lattner em 
2002 e em um artigo publicado nos anais do The international symposium on 
Code generation and optimization, em 2004. Basicamente, foi todo o sucesso 
que se espera de um bom projeto acadêmico, e tudo poderia ter ficado por aí 
não fosse o interesse da Apple. 
Em 2005, a Apple contratou Chris Lattiner e criou uma equipe para 
desenvolver essa tecnologia visando seu uso nos dispositivos da marca. Um dos 
usos mais interessantes foi a conversão de chamadas de funções da biblioteca 
gráfica OpenGL, criadas para uso em processadores gráficos (GPU), em código 
capaz de ser executado utilizando a tecnologia Intel (GMA). 
Originalmente, o projeto LLVM utilizou como front-end o compilador GCC, 
em software livre e licenciado sob a GPLv3. Como os softwares comercializados 
sob a GPL v3 possuem diversas limitações do ponto de vista comercial, a Apple 
optou por desenvolver, do zero, um novo compilador para C, Objective-C e C11. 
O resultado desse esforço foi o Clang. O Clang teve seu código aberto em 2007 
em uma licença que não atrapalha em nada a geração de bons e lucrativos 
negócios. 
Hoje, o LLVM cresceu tanto que está além de um simples projeto de 
compilador. Trata-se de um verdadeiro guarda-chuva, ou compiler 
 
2 A Oracle comprou a Sun em 2009 e hoje detém todos os direitos a tecnologia Java. 
 
 
8 
infrastructure3, sob o qual se encontram centenas de projetos relacionados à 
compilação e eficiência de execução. Tudo graças a uma ideia difundida em 
razão do sucesso do Java sendo otimizada em conceitos mais flexíveis. 
2.1 Os conceitos do LLVM 
Estudamos o processo de compilação em um diagrama de blocos que, 
propositalmente, dividiu os processos em dois grandes blocos: o front-end e o 
back-end. Originalmente, os compiladores incluíam um módulo apenas para 
otimização, no qual o código-objeto e o código de máquina produzidos deveriam 
ser otimizados em um processo inter-relacionado. Nesse caso, a maior parte da 
otimização é feita no código-objeto e nada – ou quase nada – de otimização 
existe no código de máquina. Agora, vamos dividir em três grandes blocos: front-
end, otimizador e back-end. 
A divisão do compilador em três grandes blocos tem algumas vantagens 
interessantes. Imagine, por exemplo, que você deseje criar um compilador para 
C e PHP para x64. Tudo que precisará fazer é criar um front-end para C e outro 
para PHP, e apenas um otimizador e apenas um back-end. Imagine agora que, 
além de compilar C e PHP, você precisa que esses códigos rodem nas 
arquiteturas ARM e x64. Precisará criar só e somente só um back-end extra. A 
essa funcionalidade, em inglês, damos o nome de retargetablity4. Esse conceito, 
justiça seja feita, com uma grande influência do Java, pautou o desenvolvimento 
do LLVM desde que a Apple se tornou a principal patrocinadora. LLVM, 
retargetablity. 
A Figura 3 simplifica o conceito ao mesmo tempo que exemplifica algumas 
linguagens de front-end e algumas arquiteturas-alvo. Se conseguirmos dividir o 
processo de compilação nesses três blocos e cada um desses nos seus próprios 
sub-blocos, podemos ter equipes de desenvolvimento especialistas em cada 
funcionalidade, o que resultará em um processo de compilação mais rápido e 
que utilize menos memória, melhorando a qualidade do aplicativo final e de todo 
o processo de produção e distribuição de software. A grande inovação do projeto 
 
3 A expressão compiler infrastructure não tem relação com a expressão “guarda-chuva”, em 
português, mas é a forma que os participantes do projeto usam para definir o próprio projeto. 
 
4 Podemos traduzir retargetablity com toda a liberdade possível como a “capacidade de trocar de 
alvos”. 
 
 
9 
LLVM está exatamente no coração desse sistema no Otimizador de Código 
Intermediário. 
O código intermediário do projeto LLVM, chamado de Intermediate 
Representation (IR)5, é uma representação do algoritmo original em uma 
linguagem muito próxima do Assembly, desenvolvida de forma que qualquer ser 
humano que saiba ler Assembly possa ler. Considere o LLVM-IR como sendo o 
Assembly de uma máquina hipotética. A linguagem LLVM-IR é muito parecida 
com o Assembly de uma Arquitetura RISC. 
Figura 3 – Diagrama de um compilador flexível adaptado de Lattner (2014) 
 
O LLVM-IR segue osmesmos conceitos que vimos na criação do código-
objeto. Trata-se de uma linguagem fortemente tipada, na forma de três 
endereços – que chamamos anteriormente de 3AC –, e que permite sequências 
lineares de comandos simples, como 𝑎𝑑𝑑, 𝑠𝑢𝑏𝑡𝑟𝑎𝑐𝑡 etc. Isso quer dizer que cada 
comando pode receber até duas entradas em endereços diferentes e produzir 
um resultado em um terceiro endereço, contrastando com as linguagens 
Assembly tradicionais, como a que é utilizada para o x64. Mesmo tendo sido 
desenhado como uma linguagem, o LLVM-IR possui três formas distintas: a 
forma textual, que vimos na Figura 3, uma estrutura de dados especificamente 
para uso em memória e um bytecode de alta eficiência, especialmente 
desenhado para ser armazenado em disco. 
 
 
 
 
5 Em tradução livre, “representação intermediária”. 
 
 
10 
A Figura a seguir apresenta dois fragmentos de código: um em C e o outro 
em LLVM-IR, ao lado do resultado em Assembler x64. Apenas observe que tanto 
o código LLVM-IR quanto o código Assembler x64 foram gerados a partir do 
código em C, usando o complilador Clang 4.0, enquanto o código LLVM-IR foi 
manualmente criado (Lattner, 2014). 
Figura 4 – Comparação de código em C, seu equivalente em LLVM e o código 
Assembly x64 resultante do código em C 
 
TEMA 3 – ENTENDENDO O LLVM-IR 
O código utilizado no LLVM-IR contém um conjunto de estruturas definido 
para representar uma arquitetura virtual, suficientemente complexa para conter 
as operações necessárias ao processamento, mas sem ficar restrita às 
limitações de uma arquitetura específica, como número de registradores e 
características de endereçamento. Esse conjunto de instruções contém um 
número infinito de registradores capazes de armazenar tipos primitivos, como 
𝑖𝑛𝑡𝑒𝑔𝑒𝑟, 𝑓𝑙𝑜𝑎𝑡, e endereços (ponteiros). 
Na arquitetura virtual adotada pelo LLVM, a memória disponível estará 
dividida em três escopos: 𝑔𝑙𝑜𝑏𝑎l, 𝑠𝑡𝑎𝑐𝑘 e um ℎ𝑒𝑎𝑝; todas as operações entre os 
registradores e a memória são feitas apenas com as instruções 𝑙𝑜𝑎𝑑 e 𝑠𝑡𝑜𝑟𝑒 
usando ponteiros tipados. Os objetos no 𝑠𝑡𝑎𝑐𝑘 e ℎ𝑒𝑎𝑝 são alocados utilizando 
 
 
11 
𝑎𝑙𝑙𝑜𝑐𝑎 e 𝑚𝑎𝑙𝑙𝑜𝑐, e são acessados por meio dos ponteiros que serão devolvidos 
por essas operações. Por fim, é preciso observar que, enquanto objetos no 𝑠𝑡𝑎𝑐𝑘 
serão automaticamente liberados ao final da função, objetos ℎ𝑒𝑎𝑝 deverão ser 
manualmente liberados pelo comando 𝑓𝑟𝑒𝑒. 
Essa linguagem, a máquina virtual e o conjunto de instruções foram 
especificamente desenvolvidos para criar uma arquitetura voltada para 
performance e retargetablity, e possui características interessantes: 
1. Comentários em LLVM-IR sempre começam como um ponto-e-vírgula (;) 
e se estendem até o fim da linha. 
2. Identificadores globais começam com o símbolo arroba (@). Dessa forma, 
todas as funções e variáveis globais precisam começar com @. 
Identificadores locais começam com o símbolo de percentual (%). 
3. Identificadores, globais e locais podem conter letras, números e os 
caracteres $. Se consideramos estas três últimas condições, a criação de 
uma expressão regular para localização de identificadores é muito 
simples: [%@][a − zA − Z$. _][a − zA − Z$. _0 − 9] ∗ 
No LLVM-IR, definimos inteiros pela letra i seguida do número de bits que 
serão ocupados na memória. Assim, um inteiro de 32bits será i32. Você poderá 
especificar qualquer quantidade de bits entre 1 𝑒 223 − 1. Na Figura 5 é possível 
ver um exemplo de código LLVM-IR para uma função de adição de dois números 
inteiros de 64 bits: 
Figura 5 – Exemplo de código em LLVM-IR utilizando inteiros de 64 bits 
 
A declaração de arrays é feita com colchetes na forma 
[𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 × 𝑡𝑖𝑝𝑜 𝑒 𝑙𝑎𝑟𝑔𝑢𝑟𝑎 𝑑𝑒 𝑐𝑎𝑑𝑎 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜]. Assim, para 
declarar um array que conterá a string “compiladores”, precisaremos de um tipo 
[13 × 𝑖8], se consideramos que cada letra usará 8bits e que usaremos um 
caracter 𝑁𝑈𝐿𝐿 para marcar o fim do string. Nesse caso podemos declarar uma 
constante global para armazenar a string da seguinte forma: 
@𝑐𝑜𝑚𝑝𝑖𝑙𝑎𝑑𝑜𝑟𝑒𝑠 = 𝒄𝒐𝒏𝒔𝒕𝒂𝒏𝒕 [13 × 𝒊𝟖] 𝒄”𝑐𝑜𝑚𝑝𝑖𝑙𝑎𝑑𝑜𝑟𝑒𝑠\00” 
 
 
12 
Declaramos uma constante (𝒄𝒐𝒏𝒔𝒕𝒂𝒏𝒕), chamada @𝑐𝑜𝑚𝑝𝑖𝑙𝑎𝑑𝑜𝑟𝑒𝑠, do 
tipo [13 × 𝑖8], cujo valor começa com a letra 𝑐 seguida da string completa, entre 
aspas duplas e terminada por 0. Observe que usamos uma string típica do C e, 
nesse caso, todas as strings terminam em \0 (caractere NULL). 
Definimos funções a partir da palavra reservada define seguida de um tipo 
de retorno e, finalmente, o tipo da função: 
𝒅𝒆𝒇𝒊𝒏𝒆 𝒊𝟑𝟐 @treco() { ; código da função } 
Declaramos funções começando com a palavra reservada declare, o tipo 
de retorno da função e, finalmente, seu nome e a lista de argumentos. Todas as 
declarações de funções devem estar no escopo global. 
printf: 𝒅𝒆𝒄𝒍𝒂𝒓𝒆 𝒊𝟑𝟐 puts(𝒊𝟖 ∗) 
Todas as funções terminam com uma declaração 𝑟𝑒𝑡𝑢𝑟𝑛. Existem apenas 
duas formas de declarar o retorno de uma função: 𝑟𝑒𝑡 < 𝑡𝑦𝑝𝑒 > <
𝑣𝑎𝑙𝑢𝑒 > 𝑜𝑢 𝑟𝑒𝑡 𝑣𝑜𝑖𝑑; 
Chamamos as funções utilizando a palavra reservada 𝑐𝑎𝑙𝑙, usando a 
seguinte regra de produção: 
< function return type > < function name > < optional function arguments > 
𝒄𝒂𝒍𝒍 𝒊𝟔 @test( 𝒊𝟑𝟔 %arg1 ) 
Podemos ter uma ideia de como ficaria uma função para imprimir a string 
“compiladores”. A Figura 6 mostra um fragmento de código para esta função. 
Figura 6 – Fragmento de código em LLVM-IR para impressão de "compiladores" 
 
A maior parte das instruções no LLVM-IR utiliza o padrão Three Address 
Code em sua representação quádrupla. De fato, todas as operações aritméticas 
estão nesse formato e incluem todas as operações comuns em linguagens de 
programção: 𝑎𝑑𝑑, 𝑠𝑢𝑏, 𝑚𝑢𝑙, 𝑑𝑖𝑣, 𝑟𝑒𝑚, 𝑛𝑜𝑡, 𝑎𝑛𝑑, 𝑜𝑟, 𝑥𝑜𝑟, 𝑠ℎ𝑙, 𝑠ℎ𝑟 𝑒 𝑠𝑒𝑡𝑐𝑐. 
 
 
13 
Esta última, 𝑠𝑒𝑡𝑐𝑐, representa uma família de instruções de comparação 
(𝑠𝑒𝑡𝑒𝑞, 𝑠𝑒𝑡𝑛𝑒, 𝑠𝑒𝑡𝑙𝑡, 𝑠𝑒𝑡𝑔𝑡, 𝑠𝑒𝑡𝑙𝑒, 𝑠𝑒𝑡𝑔𝑒) que compara valores de uma mesma 
classe de tipos. Em LLVM-IR, essa classe é chamada de 𝑓𝑖𝑟𝑠𝑡 − 𝑐𝑙𝑎𝑠𝑠 e inclui 
os tipos: 
𝑏𝑜𝑜𝑙, 𝑢𝑏𝑦𝑡𝑒, 𝑠𝑏𝑦𝑡𝑒, 𝑢𝑠ℎ𝑜𝑟𝑡, 𝑠ℎ𝑜𝑟𝑡, 𝑢𝑖𝑛𝑡, 
𝑖𝑛𝑡, 𝑢𝑙𝑜𝑛𝑔, 𝑙𝑜𝑛𝑔, 𝑓𝑙𝑜𝑎𝑡, 𝑑𝑜𝑢𝑏𝑙𝑒 𝑒 𝑝𝑜𝑖𝑛𝑡𝑒𝑟 
Uma característica interessante do LLVM-IR é que as instruções são 
polimórficas. Uma instrução 𝑎𝑑𝑑, ou 𝑠𝑢𝑏, por exemplo, pode ser aplicada em 
tipos diferentes. No nosso caso, tanto a instrução 𝑎𝑑𝑑 quanto a instrução 𝑠𝑢𝑏 
podem ser aplicadas em valores do tipo 𝑖𝑛𝑡 e 𝑓𝑙𝑜𝑎𝑡. Esae polimorfismo é uma 
característica de linguagens de alto nível e, no LLVM-IR, acaba reduzindo o 
tamanho do conjunto de instruções necessário para a linguagem (Lattner; Adve, 
2002). 
O sistema de tipos adotados no LLVM-IR é independente da linguagem 
que está sendo compilada; inclui tipos primitivos, tais como: 
𝑣𝑜𝑖𝑑, 𝑏𝑜𝑜𝑙, 𝑠𝑖𝑔𝑛𝑒𝑑 𝑎𝑛𝑑 𝑢𝑛𝑠𝑖𝑔𝑛𝑒𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟𝑠 𝑓𝑟𝑜𝑚 8 𝑡𝑜 64 𝑏𝑖𝑡𝑠, 
𝑓𝑙𝑜𝑎𝑡𝑖𝑛𝑔 − 𝑝𝑜𝑖𝑛𝑡 𝑣𝑎𝑙𝑢𝑒𝑠 𝑖𝑛 𝑠𝑖𝑛𝑔𝑙𝑒 𝑎𝑛𝑑 𝑑𝑜𝑢𝑏𝑙𝑒 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛, 𝑒 𝑜𝑝𝑎𝑞𝑢𝑒 
Os tipos 𝑜𝑝𝑎𝑞𝑢𝑒 são usados para representar tipos desconhecidos no 
LLVM-IR e são motivo de grande discussão entre os desenvolvedores. Além dos 
tipos primitivos, o programador de LLVM-IR terá acesso a tipos compostos, como 
𝑝𝑜𝑖𝑛𝑡𝑒𝑟𝑠, 𝑎𝑟𝑟𝑎𝑦𝑠, 𝑠𝑡𝑟𝑢𝑐𝑡𝑢𝑟𝑒𝑠, 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑠, todos independentes da linguagem 
original, aquela que está sendo compilada, mas sem perder a possiblidade de 
representação de estruturas complexas como objetos em LLVM-IR. 
Se quiser saber mais, a única fonte confiável e constantemente atualizada 
sobre o assunto é o LLVM Language Reference Manual (Manual de Referência 
da Linguagem LLVM)6. Porém, não se esqueça:o ponto chave dessa tecnologia 
é promover a otimização do código-objeto (representação intermediária). 
Considerando as características do LLVM-IR, é interessante observar o 
resultado de uma função em C, convertida para LLVM-IR. 
 
 
6 Disponível em: http://releases.llvm.org/3.3/docs/LangRef.html#simple-constants 
 
 
14 
Código em C: 
float exemplo(float a, float x, float y) { 
return a * x + y; 
} 
 
Código em LLVM-IR: 
define float @exemplo(float %a, float %x, float %y) { 
%1 = fmul float %a, %x 
%2 = fadd float %1, %y 
ret float %2 
} 
Note que cada instrução obedece ao 3AC e possui no máximo três 
endereços com apenas um do lado direito da igualdade. Além disso, as variáveis 
são atribuídas uma única vez no escopo da função. 
TEMA 4 – OTIMIZANDO O LLVM-IR 
Durante o processo de otimização de código, a principal função do 
compilador é encontrar fragmentos de código que possam ser otimizados e 
substituí-los por código mais eficiente, mantendo o mesmo significado 
semântico, não alterando suas funcionalidades e o mais rapidamente possível. 
Estudamos um pouco sobre otimização na Aula 5 e, agora, vamos trilhar a seara 
da otimização do ponto de vista do LLVM. 
O projeto LLVM ataca o problema da otimização do código intermediário 
na forma de um conjunto de passagens (pass) sucessivas. Uma passagem, ou 
pass, é uma operação realizada sobre uma determinada unidade de código 
LLVM-IR. Essas unidades de código podem ser arquivos, funções ou até mesmo 
blocos básicos. 
Cada uma dessas passagens – ou pass, em inglês, que alguns têm 
traduzido por “passo” – é direcionada para um determinado tipo de otimização. 
Cada passagem pode executar uma ou mais otimizações. Entre elas se 
destacam (Lattner, 2002): 
1. as otimizações tradicionais derivadas do uso do padrão SSA, tais como: 
eliminação de código morto (normal e agressiva); simplificação de 
variáveis; substituição de funções, eliminação de variáveis globais, 
constante propagação etc. 
2. otimizações baseadas no gráfico do fluxo de controle: eliminação de borda 
crítica; construção de laços naturais etc. 
 
 
15 
3. análises e transformações interprocedurais: fusão de variáveis globais; 
análise segura de tipos; eliminação de variáveis globais etc. 
A analysis pass, ou passagem de análise, observa a unidade de código 
LLVM-IR recolhendo informações, como, por exemplo, a estrutura de domínios 
no código. Uma determinada passagem de análise pode chamar outra 
passagem de análise, já que nenhuma delas alterará a unidade de código e 
todos os resultados serão mantidos em cache até que determinada unidade seja 
modificada por outra passagem. 
Outro grupo interessante é formado pelas transformation pass, ou 
passagens de transformação. Nesse caso, como o nome diz, a unidade de 
código será transformada. Contudo, todas as passagens de transformação 
devem, obrigatoriamente, deixar a unidade de código em um estado válido. As 
passagens de transformação utilizam as passagens de análise e, na maior parte 
das vezes, acabam por invalidar o cache das passagens de análise. 
Existem duas passagens que merecem um destaque especial. São elas: 
a combinação de instruções e o aumento de nível. 
O código intermediário gerado pelos compiladores geralmente contém 
pouquíssima informação sobre os tipos envolvidos no algoritmo. Entretanto, 
como a estratégia mais importante do projeto LLVM é justamente o retargetablity, 
foi desenvolvida uma passagem especial para recuperar as informações 
relativas aos tipos permitindo, a fim de que front-ends diferentes possam 
recuperar essa informação e adequar os tipos às características de cada 
linguagem de programação envolvida. 
A combinação de instruções, por outro lado, é voltada para a eficiência do 
código. Trata-se de uma lista de instruções como 𝑎𝑑𝑑 𝑋, 0 = 𝑋, “𝑠𝑢𝑏 𝑋, 𝑋 = 0”, 
“𝑎𝑛𝑑 𝑋, −1 = 𝑋” etc. que permitem um excelente grau de otimização em 
pequenos fragmentos de código (Lattner, 2002). A primeira parte dessa 
otimização trata de colocar todas as declarações em sua forma canônica. 
No caso do LLVM-IR, utilizamos as regras gramaticais para identificar a 
forma canônica e fazer as correções necessárias. Por exemplo: “se uma 
instrução 𝑎𝑑𝑑 tem como operando um valor constante, a forma canônica 
determina que o valor constante será o segundo operando” (Lattner, 2002). O 
processo de canonização é parte do processo de otimização e acaba facilitando 
 
 
16 
a execução de outros processos de otimização, como, por exemplo, a eliminação 
de código morto. 
A combinação de instruções facilita a otimização em janela ou peephole 
optimization7, e é feita em pequenos fragmentos do código intermediário gerado. 
Pense em blocos básicos, como discutido no processo de otimização. Como 
essa substituição é muito rápida e permite uma grande simplificação do código, 
os passos subsequentes podem partir do princípio de que esse tipo de problema 
não existe, o que torna mais simples a criação de passagens de otimização mais 
elaboradas. 
TEMA 5 – COMPILADORES NA WEB 
Nesse começo de século XXI, os aplicativos on-line são tão ou mais 
importantes que qualquer programa criado para rodar em servidores ou 
máquinas individuais. Rodar um aplicativo em um navegador é uma tarefa tão 
comum que já não surpreende ninguém. Nesse cenário, o Javascript é uma das 
linguagens mais proeminentes. 
Damos o nome de javascript engine ao compilador de javascript que roda 
no seu navegador e faz com que seja possível que aplicativos rodem dentro de 
páginas web. Diversos desses engines estão sendo ativamente desenvolvidos: 
V8, desenvolvido pelo Google, e escrito em C++ , o Rhino,  da Fundação Mozilla, 
desenvolvido em Java, e o Chakra (JavaScript)  da Microsoft são apenas alguns 
exemplos interessantes para esta disciplina. 
O V8 foi criado pelo Google para melhorar a velocidade das páginas web 
e acabou sendo escolhido pelo time do projeto node.js como engine para a 
criação de um “servidor” para rodar javascript. Esses dois motivos bastam para 
que nos concentremos neste engine. 
ATENÇÃO: a expressão forma canônica no domínio das linguagens de 
programação afeta aquelas linguagens que possuem uma ou mais formas para 
a mesma declaração. Dizemos que canônica é a forma preferida, ou escolhida 
como padrão. Sendo assim, colocar em forma canônica significa dizer que todas 
as formas gramaticalmente corretas serão modificadas para coincidir com a 
forma canônica. 
 
7 A melhor tradução de peephole seria “olho mágico”, mas aqui temos que ficar com o sentido. 
Esse tipo de otimização tem tal nome por observar pequenos fragmentos de código. 
 
 
17 
Até a versão 5.9, o V8 fez uso de dois compiladores: o full-codegen, um 
compilador com poucos níveis de otimização, mas muito rápido, e o CrankShaft, 
um compilador do tipo JIT capaz de produzir código de máquina extremamente 
otimizado. O código era rapidamente compilado pelo full-codegen e otimizado 
em tempo de execução pelo CrankShaft. Para conseguir esse feito, o V8 utilizava 
diversos threads específicos para cada script em javascript: 
 o thread principal responsável por recolher o código na web, compilá-lo e 
executá-lo; 
 um thread extra apenas para o CrankShaft, de forma que o script poderia 
continuar sendo executado enquanto era executado; 
 um thread apenas para a verificação da eficiência de cada um dos 
métodos chamados, classificando esses métodos em uma ordem de 
compilação para o CrankShaft. 
Além desses três threads, cada script acabava criando alguns outros 
threads para captura de lixo e sincronização do processo de execução. Ainda 
que essa estrutura tenha tido sucesso e permitido a criação de aplicativos web 
tão eficientes quanto dos aplicativos locais, esse número de threads acaba 
causando um excesso de consumo de memória.A partir da versão 5.9, o V8 passou a utilizar uma nova estrutura de 
compilação baseada no Ignítion e no TurboFan, melhorando o tempo de 
execução dos scripts e diminuindo o uso de memória. De fato, a estrutura 
anterior era, na verdade, uma variação da estrutura monolítica de compilação, 
ainda que em duas passagens. A introdução do Ignítion e do TurboFan foi 
acompanhada da criação de um código-objeto intermediário ao qual a equipe de 
desenvolvimento do Javascript deu o nome de Bytecode, como pode ser visto 
na Figura 7: 
 
 
 
18 
Figura 7 – Representação do processo de compilação do V8 
 
O ponto chave dessa nova tecnologia é o novo interpretador chamado de 
Ignition. Sob tal denominação estão os analisadores léxico, sintático e 
semântico, um gerador de código intermediário, Bytecode e três ciclos de 
otimização: reorganização de código e uso de registradores; peephole 
optimization e eliminação de código morto, como pode ser visto na Figura 8: 
Figure 8 – Diagrama de compilação do V8 destacando os módulos de otimização 
o Ignition 
 
 
 
19 
FINALIZANDO 
Esta foi uma disciplina interessante. Partimos do código-fonte de um 
programa em C e fomos até aos mais recentes avanços tecnológicos na área de 
compilação. 
Nesta última aula, é preciso prestar atenção nas mudanças que o advento 
do Java trouxe para o cenário da computação, criando plataformas mais flexíveis 
e eficientes com a inclusão de uma camada extra no processo de compilação, o 
Bytecode. Você precisa entender esse conceito e observar como a sua evolução 
provocou a criação de um ambiente mais rápido na web. É importante que você 
perceba o funcionamento do V8 e, no futuro, não deixe de acompanhar as novas 
soluções nesta área apresentadas pela Fundação Mozilla no Firefox e pela 
Microsoft. 
Não se pode perder de vista o projeto LLVM. Esse projeto está, de uma 
forma ou de outra, envolvido em todos os avanços tecnológicos dos últimos 5 
anos e, ao que tudo indica, estará nessa posição por outros 5 anos. 
A separação definitiva do processo de compilação em três grandes 
módulos (análise, código intermediário e código final) é, neste momento, a 
tendência mais exuberante para a execução de algoritmos. Sejam eles voltados 
para o uso em dispositivos móveis, desktops ou na nuvem. Essa divisão, além 
de promover a flexibilidade, permite que a performance final seja a melhor 
possível. 
Observe, também, os processos de análise léxica, sintática e semântica. 
Além de terem uso na compilação de programa, estão sendo utilizados em 
muitas áreas relacionadas à inteligência artificial, e devem ser seus temas em 
estudos futuros. 
A partir deste ponto você deve se preocupar com a tecnologia de sistemas 
distribuídos – tecnologias como Docker e Kubernets que emprestam esses 
conceitos, além de permitir o máximo de performance, facilitam a instalação, 
distribuição e uso de aplicativos. Mas esse é um assunto para as próximas 
disciplinas. 
 
 
 
20 
REFERÊNCIAS 
AHO, A. V., LAM, M. S., SETHI, R., & ULLMAN, J. D. Compiladores: princípios, 
técnicas e ferramentas. 2a ed. Boston, MA, USA: Pearson Education Inc., 2007. 
BERGMANN, S. D. Compiler Design: Theory, Tools, and Examples. Rowan 
University, 2010. 
CRAMER, T., FRIEDMAN, R., Miller, T., Seberger, D., Wilson, R., & Wolczko, M. 
Compiling Java Just In Time. IEEE Micro, v.17, n. 3, 8, mai/1997. 
HOLUB, A. I.. Compiler design in C. (B. W. Kernighan, Ed.) Englewood Cliffs, 
NJ, USA: Prentice Hall Software Series, 1990. 
LATTNER, C. LLVM. In: BROWN, A. & WILSON G. (ed.). The Architecture of 
Open Source Applications: Elegance Evolution and a few fearless hacks. 2014, 
p. 432. 
LATTNER, C. LLVM: an infrastructure for multi-stage optimization. Urbana, IL, 
USA: University of Illinois at Urbana-Champaign, 2002. 
LATTNER, C.; ADVE, V. LLVM: A Compilation Framework for Lifelong Program 
Analysis & Transformation. University of Illinois at Urbana-Champaign, Urbana, 
IL, USA, 2002. 
ZANDER, C. Languages (Finite State Machines). CSS 448/548 - Introduction 
to Compilers, 2012. Disponível em: 
<http://courses.washington.edu/css448/zander/Notes/langFSM.pdf>. Acesso 
em: 28 nov. 2017