Embed Size (px)
Citation preview
Alex de Magalhães Machado
Um estudo sobre possíveis técnicas de otimização de código para bytecode Lua
Florianópolis
2009
2
Alex de Magalhães Machado
Um estudo sobre possíveis técnicas de otimização de código para bytecode Lua
Trabalho de conclusão de curso apresentado como parte dos requisitos para obtenção do grau Bacharel em Ciências da Computação.
Orientador: Prof. Dr. Olinto José Varela Furtado
UNIVERSIDADE FEDERAL DE SANTA CATARINA DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA
BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO
Florianópolis
2009
3
Trabalho de conclusão de curso sob o título “Um estudo sobre possíveis técnicas de otimização de código para bytecode Lua”, defendido por Alex de Magalhães Machado,
em Florianópolis, Santa Catarina, pela banca examinadora constituída:
______________________________________________
Prof. Dr. Olinto José Varela Furtado Departamento de Informática e Estatística
Orientador
Banca Examinadora
______________________________________________
Prof. Dr. Ricardo Azambuja Silveira Departamento de Informática e Estatística
______________________________________________
Prof. José Eduardo De Lucca Departamento de Informática e Estatística
4
"Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time."
Thomas Alva Edison
5
Agradecimentos
Aos meus pais e avó, por terem sido os pilares que proporcionaram meu crescimento e me permitiram sonhar.
Ao meu avô, por sempre ter acreditado muito no meu potencial, mesmo quando decidi não fazer medicina.
Ao meu irmão e amigo Mateus, à Cecilia, ao Luis e à Janaina, por terem sido minha fonte de felicidade, meu apoio incondicional, e por me fazerem sorrir quando tudo parecia estar indo mal.
Ao Professor Olinto, por ter confiado na minha capacidade e, principalmente, por sempre ter me guiado quando eu me sentia num labirinto.
Ao Prof. Dr. Ricardo Azambuja Silveira e ao Prof. José Eduardo De Lucca, pelo valioso tempo despendido, e por terem aceitado fazer parte desse projeto.
Ao Eduardo, por ter compartilhado seu amplo conhecimento e ter me ajudado a dar os primeiros passos do projeto.
E a todos aqueles que sempre me amaram e sempre me quiseram bem. Várias páginas seriam necessárias para expressar minha gratidão a todos que me ajudaram a chegar onde estou agora. E não me refiro apenas a este projeto, pois ele representa apenas o fim de mais um caminho percorrido, mais uma conquista obtida.
6
Resumo
Num mundo em que novas abstrações e linguagens de alto nível surgem a todo momento, nunca se exigiu tanto de um compilador. Hoje é imprescindível que o compilador não apenas realize suas funções básicas, mas também gere códigos intermediários tão eficientes, e eficazes, quanto um exímio programador de linguagens de baixo nível.
Para isso, todos os compiladores devem contar com uma ferramenta de otimização de código, responsável por realizar alterações sintáticas no programa fonte a fim de obter um código final mais otimizado. A linguagem Lua, entretanto, realiza poucas dessas otimizações.
Após uma discussão a respeito de diferentes algoritmos de otimização de código, e também a respeito das razões para a implementação da linguagem Lua não contemplar muitas dessas otimizações, discutimos como foi o estudo e a criação de um otimizador de código para Lua, realizando todas as principais otimizações de código, mantendo ainda as principais virtudes da linguagem.
Podemos perceber nos testes realizados que para um certo nicho de aplicações Lua essas otimizações trazem um benefício muito grande, e são motivação suficiente para uma extensão da pesquisa.
Palavras-chave: Compilador, Otimização de código, Lua
7
Abstract
In a world where new abstractions and high-level languages arise every moment, developers have never asked so much of a compiler. Today it is essential that the compilers not only perform their basic functions, but also generate intermediary code as efficiently and effectively as an excellent programmer of low-level languages.
Thus, all compilers must rely on an optimizer tool, responsible for performing syntactic changes on the source program in order to obtain a final improved program. The Lua language, however, carries few of these optimizations.
After a discussion about different algorithms of code optimization, and also about the reasons why the implementation of Lua does not contemplate many of these optimizations, we discuss the study and creation of a code optimizer for Lua, one that performs a lot of optimizations, while still maintaining the main virtues of the language.
We can see in tests that these optimizations bring a huge improvement for a certain niche of Lua applications, and therefore are enough motivation for an extension of the research.
Key-words: Compiler, Code Optimization, Lua
8
Sumário
Lista de figuras
1. Introdução p. 12
1.1. Objetivo geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 13
1.2. Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 13
2. Linguagens e Compilação p. 14
2.1. Linguagens de alto nível . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 14
2.2. Compilação e Otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 15
2.3. Linguagem intermediária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 15
3. Lua p. 19
3.1. Introdução a Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 19
3.2. Principais qualidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 20
3.3. Tabelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 21
3.4. Funções e Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
3.5. Threads e Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
3.6. Implementação da linguagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 24
3.7. Máquina virtual baseada em registradores . . . . . . . . . . . . . . . . . . . . . . . . . p. 25
3.8. Exemplo de instruções do bytecode Lua . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
3.9. Outras instruções da máquina virtual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 32
3.10. Exemplos de código em bytecode . . . . . . . . . . . . . . . . . . p. 34
4. Otimização de Código p. 37
4.1. Subexpressão comum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 37
4.2. Propagação de cópia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39
4.3. Desdobramento de constante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39
4.4. Eliminação de código morto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 41
4.5. Movimentação de código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 42
4.6. Variáveis de indução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 43
5. Análise de Fluxo de Dados p. 45
5.1. Introdução à Análise de Fluxo de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . p. 45
5.2. Abstraindo o Fluxo de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 45
5.3. Funções de transferência e Fluxo de controle . . . . . . . . . . . . . . . . . . . . . . p. 47
9
5.4. Definições de alcance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 48
5.5. Expressões disponíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 50
5.6. Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 51
6. Implementação p. 52
6.1. Prós e Contras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 52
6.2. Oportunidades de otimização em Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 52
6.3. Eliminação de Subexpressões comuns . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 53
6.4. Propagação de cópia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55
7. Testes p. 57
7.1. Testes realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 57
7.2. Ganho da Eliminação de Subexpressões comuns . . . . . . . . . . . . . . . . . . . p. 59
7.3. Ganho da Propagação de cópia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 60
7.4. Ganho em desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 61
8. Conclusão p. 62
Referências bibliográficas p. 63
Apêndice A – Artigo p. 64
Apêndice B – Código Fonte p. 77
10
Lista de Figuras
2.1. Código em Lua sem otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 17
3.1. Uma tabela em Lua [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
3.2. Um upvalue antes e depois de um CLOSE [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
3.3. Diagrama da implementação da linguagem [3] . . . . . . . . . . . . . . . . . . . . . . . . . p. 24
3.4. Bytecode na versão 4.0 da implementação de Lua [2] . . . . . . . . . . . . . . . . . . . p. 25
3.5. Bytecode na versão 5.0 da implementação de Lua [2] . . . . . . . . . . . . . . . . . . . p. 26
3.6. Exemplo de código em Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 27
3.7. Ínicio de um programa e declaração de função em bytecode Lua . . . . . . . . . . . . . p. 28
3.8. Exemplos de declaração e atribuição de variáveis globais e locais . . . . . . . . . . p. 28
3.9. Exemplo de instrução condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
3.10. Exemplo de uso de tabelas e funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
3.11. Exemplo de atribuição de um arranjo numa tabela . . . . . . . . . . . . . . . . . . . . . p. 30
3.12. Preparação de variáveis para uso num bloco “for” . . . . . . . . . . . . . . . . . . . . . p. 30
3.13. Exemplo de uso de bloco “for” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31
3.14. Instrução final de toda função de Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 31
3.15. Exemplo de protótipo de função interna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 32
3.16. Bytecode do código da figura 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35
3.17. Bytecode do código da figura 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 36
4.1. Código em Lua sem Subexpressões comuns . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 39
4.2. Código com Propagação de cópia e Desdobramento de constante . . . . . . . . . . p. 41
4.3. Código em Lua sem Código morto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 42
4.4. Código em Lua otimizado manualmente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 44
5.1. Algoritmo de Definições de Alcance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49
5.2. Algoritmo de Expressões Disponíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 51
11
6.1. Caso especial de ocorrência de subexpressões comuns . . . . . . . . . . . . . . . . . . . p. 54
6.2. Solução para caso especial de subexpressões comuns . . . . . . . . . . . . . . . . . . . . p. 54
7.1. Programa em Lua criado para realizar testes . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 58
7.2. Programa em bytecode Lua criado para realizar testes . . . . . . . . . . . . . . . . . . . p. 58
7.3. Programa em bytecode Lua sem subexpressões comuns . . . . . . . . . . . . . . . . . . p. 59
7.4. Programa em bytecode Lua após propagação de cópia . . . . . . . . . . . . . . . . . . . p. 60
12
1. Introdução
Grande parte dos softwares criados atualmente são desenvolvidos numa linguagem de alto nível, de fácil entendimento para o ser humano. Em meio a milhares de linhas de código criadas uma a uma pelo homem, inevitavelmente surgem comandos desnecessários, linhas de código inalcançáveis, código redundante, expressões iguais sendo calculadas em diversos lugares, entre outras características.
É desejável então que antes desse software ser disponibilizado para os usuários ele passe por um processo de otimização de código, no qual um outro software iria analisar seu código, encontrar pontos em que uma otimização poderia ser feita e, sem alterar a semântica do programa, alteraria seu código.
Porém, as otimizações possíveis dependem muito da natureza da linguagem de programação, fazendo com que otimizar o código de uma linguagem seja um grande desafio. Deve-se levar em conta não só quais otimizações são possíveis, como também como realizar cada uma e quais cuidados tomar.
Propõe-se então um estudo sobre as possibilidades de se otimizar código intermediário Lua.
Além dessas razões descritas acima, há fatores referentes ao compilador e à sintaxe da linguagem que acabam inevitavelmente gerando oportunidades de otimização de código, fazendo com que esse processo seja muito importante, pois indica que mesmo se o programador responsável pelo software desenvolvê-lo com o maior cuidado e não colocar trechos de código passíveis de otimização, ainda assim o software poderá ser bastante otimizado.
Isso ocorre porque o compilador, quando está gerando código intermediário durante o processo de compilação, acaba ele mesmo criando linhas de código no programa que não existiam na linguagem de alto nível, mas que agora não só estão presentes como também são geralmente passíveis de otimização.
Embora apenas em raras exceções se obtenha de fato um código ótimo, as técnicas conhecidas de otimização de código são capazes de melhorar inúmeros fatores do código otimizado, seja seu tempo de execução ou mesmo o espaço ocupado.
13
1.1. Objetivo Geral
Este trabalho tem como objetivo estudar e implementar possíveis algoritmos de otimização de código ao código intermediário de Lua.
1.2. Objetivos específicos
• Estudar técnicas de otimização de código, seus algoritmos, suas vantagens e desvantagens.
• Entender como funciona internamente a implementação da linguagem Lua, com foco na linguagem intermediária de Lua utilizada pela máquina virtual de Lua.
• Estudar como otimizar código de uma linguagem intermediária de uma linguagem de programação interpretada, dinâmica, com funções de primeira classe e características diferentes do habitual, como Lua.
• Implementar algumas das principais otimizações possíveis e interessantes para a linguagem intermediária de Lua.
14
2. Linguagens e Compilação
Grande parte dos softwares criados atualmente são desenvolvidos numa linguagem de alto nível, de fácil entendimento para o ser humano. Em meio a milhares de linhas de código criadas uma a uma pelo homem, inevitavelmente surgem comandos desnecessários, linhas de código inalcançáveis, código redundante, expressões iguais sendo calculadas em diversos lugares, entre outras características.
2.1 Linguagens de alto nível
Nos dias de hoje há diversas linguagens de alto nível sendo usadas para os mais variados fins. Elas estão cada vez mais fáceis de usar e cada vez contemplando mais elementos de linguagens naturais. Essa tendência vem sendo fomentada pela necessidade em se utilizar linguagens de programação de fácil entendimento, que permitam que um código seja escrito por uma única pessoa e lido e reusado por muitas outras. Linguagens como Python, Ruby e Lua são bons exemplos. Todas são de fácil aprendizado, até mesmo para não programadores, e suas sintaxes permitem um fácil entendimento do código.
Note, por exemplo, o código abaixo escrito em Ruby:
5.times {puts "Facil de entender"}
O código acima é responsável por imprimir no console de Ruby 5 vezes o texto “Facil de entender”. Ou seja, isso é o que basta para se percorrer um laço exatamente 5 vezes executando em cada iteração uma instrução responsável por imprimir uma mensagem de texto no dispositivo de saída padrão. Além de concisa, é uma instrução fácil de entender, mesmo para quem não conhece a linguagem.
Note agora um outro código, escrito em Lua:
if 5 > 2 then return 5 end
Esse código não é muito diferente quando escrito em linguagens menos abstratas, mas é perceptível o quão ele é semelhante à linguagem natural quando escrito em Lua. A ausência de ponto e vírgula, chaves e parênteses deixa o código mais puro e legível. O código simplesmente executa: Se 5 é maior que 2 então retorna 5.
15
2.2 Compilação e Otimização
Embora seja muito mais confortável para o ser humano utilizar uma linguagem como essas, para a máquina que irá de fato executar os comandos é muito mais trabalhoso do que se o programa já estivesse escrito na linguagem binária da máquina ou numa linguagem intermediária de semântica semelhante. Isso acontece simplesmente porque cada máquina apenas compreende sua própria linguagem binária, e independentemente de qual linguagem está se programando, no fim o código criado deverá ser traduzido para a linguagem binária da máquina.
Linguagens como Ruby e Lua possuem uma forma de representar os comandos geralmente muito diferente de como linguagens binárias fazem, e traduzir os comandos de uma forma de representação para outra de maneira automatizada pode consequentemente gerar um código binário não tão eficiente [1].
Essa tradução, chamada de compilação, contempla então uma etapa intermediária chamada de otimização de código que tenta justamente realizar pequenas alterações no código para amenizar essa perda de desempenho. Outra fonte de otimizações surge a partir da forma como o programador escreve o código fonte. Redundâncias podem ser criadas no código tanto por descuido dos programadores, como também por interesse em deixar o código mais legível.
Apesar de terem como objetivo deixar o código binário mais otimizado, essas otimizações não são realizadas no próprio código binário, após a compilação ser realizada. Isso acontece porque o código binário é dependente de máquina, o que faria com que para cada máquina alvo da compilação fosse criado um otimizador de código diferente.
2.3 Linguagem intermediária
A solução encontrada pela maioria dos compiladores é definir uma linguagem intermediária, independente de máquina, mas com uma semântica igual ou muito semelhante à linguagem binária, de forma a evitar que a posterior tradução da linguagem intermediária para a binária diminua o desempenho. O compilador então traduz o código na linguagem original para a linguagem intermediária, otimiza esse código intermediário e depois traduz esse código intermediário para a linguagem binária da máquina em questão. Essa linguagem intermediária é sempre a mesma
16
independentemente de qual seja a máquina alvo, de forma que o otimizador de código usado possa sempre ser o mesmo.
As otimizações de código possíveis se dividem entre as otimizações dependentes de máquina e as otimizações independentes de máquina. As otimizações dependentes de máquina realizam alterações no código de forma a deixar o código mais eficiente para uma certa arquitetura de máquina. No entanto, nosso foco serão as otimizações independentes de máquina, as quais realizam alterações no código para deixá-lo mais eficiente independente da máquina que irá executá-lo.
Abaixo ilustraremos oportunidades de otimização num programa em Lua.
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
local a,b
c = 9
function x()
return 2/2
end
e = c + x()
while i < 12 do
j = 2 ^ i
if powerTwo[i] == j then
print(powerTwo[i] == j)
print(powerTwo[i])
end
i = i + 1
y = 2 * i
a = 2
b = a - 2
d = c + e
17
end
if false then
j = 0
end
i = c + e
print(i)
print(y)
return b
Figura 2.1 Código em Lua sem otimização
O código acima, criado apenas como um exemplo, não possui nenhuma funcionalidade relevante, porém várias instruções foram colocadas para ilustrar algumas otimizações possíveis.
As instruções “a = 2”, “b = a – 2” e “d = c + e” foram colocadas dentro do laço da instrução “while”, porém o valor de nenhuma das 3 é utilizado dentro do laço, fazendo com que toda vez que as 3 instruções são executadas, elas calculam o mesmo valor. Isso é desnecessário, e as 3 instruções poderiam ser retiradas e colocadas após o laço.
A instrução “j = 0” dentro do “if” externo ao laço não será executada nunca, pois a cláusula condicional sempre será falsa, e essas instruções poderiam simplesmente ser excluídas. A expressão “c + e” é calculada duas vezes, tanto para atribuir o valor a “d” quanto à “i” no final do programa. A instrução “i = c + e” poderia então ser substituída por “i = d”.
A instrução “return 2/2” dentro da função “x” poderia ser substituída por “return 1”, enquanto a instrução “b = a - 2” poderia ser substituída por “b = 0”, já que “a” possui sempre o valor 2 na execução dessa atribuição a “b”.
Por fim, cada vez que o laço é executado o arranjo “powerTwo” é acessado na posição “i” três vezes, o que poderia ser reduzido pelo otimizador de código para apenas 1 acesso. Além disso, dois desses acessos são para comparar com o valor de “j”. Essa comparação também poderia ser feita uma vez só.
Essas otimizações citadas, além de outras, em sua maioria, poderiam ser realizadas pelo próprio programador enquanto cria o programa, embora isso nem sempre seja possível. Em linguagens sem aritmética de ponteiros, por exemplo, é impossível acessar algum elemento de um arranjo sem se referir à posição dele no
18
arranjo. Essa posição, por sua vez, deve ser transformada no endereço de memória do elemento através de operações aritméticas. Essas operações quase sempre são as mesmas para cada acesso a um elemento. Essa redundância então é uma grande oportunidade de otimização no código do programa. Em Lua, porém, a linguagem intermediária realiza acessos a um arranjo de forma mais abstrata, inviabilizando essa otimização. Logo a seguir essa e outras características da linguagem serão explicadas com mais detalhes.
O caso descrito acima é apenas um exemplo de como a compilação do código fonte para um código binário ou intermediário pode gerar perda de desempenho. Há de fato várias outras construções na linguagem que perdem eficiência com o processo de compilação. O processo de otimização de código nesses casos é então importante.
Essa otimização independente de máquina baseia-se quase em sua totalidade na análise de fluxo de dados, que são algoritmos para colher informações sobre um programa [1]. Essa análise de fluxo de dados será descrita em detalhes posteriormente.
Através dessa análise é que se torna possível implementar as principais otimizações de código, as quais formam a base para a pesquisa realizada e serão explicadas uma a uma posteriormente.
19
3. Lua
Nos próximos tópicos trataremos de algumas das características da linguagem Lua, e depois nos focamos em quais otimizações foram estudadas e implementadas. Lua é uma linguagem de programação criada inicialmente em 1993 pelo Computer Graphics Technology Group, da Pontifícia Universidade Católica do Rio de Janeiro, para uso interno no desenvolvimento de software [5]. Seu uso tem crescido constantemente desde então graças provavelmente aos seus objetivos iniciais: ter uma linguagem de script embarcável que possa ser acoplada a sistemas maiores, que seja simples, eficiente, portável e também leve [2].
3.1 Introdução a Lua
A implementação de Lua consiste de uma pequena biblioteca de funções ANSI C que compila de forma igual para todas as plataformas. O código base está bem dividido em módulos como o compilador, o interpretador e a máquina virtual [3].
Embora projetada inicialmente para estender aplicações com objetivo de ter bom desempenho, ser portável e extensível, a evolução de Lua fez com que seus projetistas logo buscassem também fazer de Lua uma linguagem simples e compacta. O suporte a concorrência, reconhecimento de padrões de strings, garbage collection, e namespaces para módulos foram alguns dos requisitos que estimularam o desenvolvimento da linguagem a seguir por esse caminho [3].
Hoje, Lua é usada numa vasta gama de aplicações, desde descrições de dados, até a indústria de jogos. Lua é uma linguagem tão fácil de se aprender a usar como Python, pela sua sintaxe de alto nível de abstração, e ainda melhor que Python quando se trata de sistemas embarcados. Pelas suas características de implementação, é também bastante rápida.
Em suma, podemos descrever Lua como uma linguagem de programação leve, imperativa, reflexiva, de script, com tipagem dinâmica e fraca, multi-plataforma e multi-paradigma, suportando programação funcional, orientada a objeto e baseada em protótipos.
20
3.2 Principais qualidades
Os objetivos da linguagem nem sempre foram os mesmos [2], mas todos eles fizeram a linguagem alcançar algumas qualidades muito interessantes em relação a outras linguagens [3]:
• Simplicidade: Para cumprir esse objetivo, buscou-se a linguagem mais simples possível, implementada com o código C mais simples possível. Isso foi obtido ao se construir uma linguagem com uma sintaxe muito simples, poucas construções de linguagem e um número reduzido de tipos de dados. Lua possui apenas 8 tipos de dados:
o String: Representa um arranjo de caracteres. Qual caractere de 8 bits é suportado.
o Numeral: Representa os números em Lua. São tratados como o tipo double de C pelo compilador.
o Nil: Representa um valor vazio.
o Booleano: Representa os valores booleanos Verdadeiro ou Falso.
o Função: Representa um valor de primeira classe. Pode ser tanto uma função de Lua como uma função de C, e pode estar armazenado em uma variável.
o Userdata: Permite que dados de C possam ser guardados em variáveis. Userdata são ponteiros para blocos de memória do usuário, e podem ser de dois tipos: heavy, em que os blocos são alocados por Lua e são passíveis de sofrer garbage collection, ou light, em que os blocos são alocados e liberados pelo usuário [2].
o Thread: Representa uma thread de execução e é usado para implementar coroutines, que serão explicadas mais adiante.
o Tabela: Única estrutura de dados da linguagem. Admite uma chave e um valor. Pode ser tratado como um arranjo tanto pelo usuário quanto pela máquina virtual se as chaves forem números inteiros seqüenciais.
• Eficiência: Como desde o início Lua iria ter que mexer com uma grande quantidade de dados, o projeto da linguagem sempre buscou uma linguagem que fosse rápida. Para isso, ela precisaria compilar o código rapidamente, e executá-lo também rapidamente. A solução foi criar um compilador de um passo que fosse rápido e inteligente, além de uma máquina virtual também rápida. Por
21
exemplo, a máquina virtual atualmente suporta apenas 38 opcodes diferentes, enquanto a máquina virtual de Java suporta 256. Além disso, todas as instruções da máquina virtual de Lua podem ser de apenas 3 formatos diferentes, e ela foi projetada de uma forma mais eficiente que as máquinas virtuais habituais, o que será melhor detalhado posteriormente.
• Portabilidade: Era um requisito inicial de Lua a portabilidade, e se tornou interessante manter essa característica na linguagem posteriormente. Para isso, o núcleo da linguagem precisou ser desenvolvido de uma forma que pudesse ser compilado igualmente em qualquer lugar e executasse programas em Lua da mesma forma em qualquer plataforma que suportasse o interpretador de Lua. Como o núcleo é escrito em C, esse código precisou ser escrito com cuidado, dando bastante atenção a problemas com portabilidade de C e de suas bibliotecas.
• Programas embarcáveis, com baixo custo: Para que programas em Lua pudessem ser acoplados a programas maiores, era essencial que houvesse uma fácil comunicação entre eles. Para isso desenvolveu-se uma API de C simples e poderosa. Além disso, não deveria ser caro para os desenvolvedores do projeto embarcarem programas em Lua. Para isso, o núcleo da linguagem precisou ser muito compacto.
Alguns desses objetivos de projeto da linguagem são conflitantes. Para o código executar rapidamente, o compilador deve ser inteligente e criar código bom, mas não adianta o código ser rápido se o próprio compilador é lento, o que faz com que o compilador também precise ser rápido. Por outro lado, para a linguagem ser compacta, o compilador deve ser pequeno. O compilador criado então busca um equilíbrio entre todos esses requisitos [2]. E para aplicações que possuem recursos de memória reduzidos, é possível acoplar o núcleo de Lua sem o compilador. Os arquivos em Lua são então pré-compilados e na hora da execução são apenas carregados por um módulo reduzido.
3.3 Tabelas
Tabelas em Lua são a única estrutura de dados existente e são implementadas em duas partes: um arranjo e uma hash [3]. Através dessa estrutura é possível criar qualquer outra estrutura de dados [2].
22
Figura 3.1 Uma tabela em Lua [2]
Uma tabela pode ser tratada tanto como um arranjo, ou como uma tabela hash, ou uma mistura de ambos, como está ilustrado na imagem acima. Essa é a representação interna da instrução “a = {x = 9.2, 100, 200, 300}”.
Ou seja, se o usuário cria uma tabela e insere nela um elemento na posição “x” e então insere 3 números sem especificar posição, internamente a parte de tabela hash é inicializada com 1 elemento referenciado pela letra “x” e a parte de arranjo é inicializada com 3 valores, iniciando na posição inicial do arranjo. Da mesma forma podemos ter apenas um arranjo, ou apenas uma tabela hash. Essa implementação é eficiente, e não poderia ser diferente, pois todas as estruturas de dados criadas pelos programadores irão depender dessas tabelas.
3.4 Funções e Closures
Funções em Lua são de primeira classe, podendo ser atribuídas a variáveis, retornadas por outras funções, passadas como parâmetros para outras, etc [2]. Para contemplar essa funcionalidade, Lua conta com Closures, que são criadas toda vez que a máquina virtual executa uma instrução do tipo “function ... end” [3]. Uma Closure é definida como um conjunto de dados que contempla uma referência para o protótipo da função (o código dela que será executado quando ela for chamada), uma referência para o ambiente da função (que contém as variáveis globais) e um arranjo de referências para upvalues, que são usados para acessar variáveis externas [2].
Esse acesso a variáveis externas existe porque a partir do momento em que o programador pode armazenar uma função numa variável, a execução da função pode ocorrer bem depois do bloco de código em que ela está ter terminado de executar, e as
23
variáveis externas naquele momento devem ainda existir para que a função possa usá-los. A imagem abaixo exemplifica esse mecanismo:
Figura 3.2 Um upvalue antes e depois de um CLOSE [2]
No caso, à esquerda temos uma função no momento em que uma Closure dela é criada, com o upvalue ainda aberto, ou seja, ainda dentro de um bloco em execução. Assim que o bloco é finalizado, a variável “x” acima não é excluída imediatamente, porque a função ainda pode precisar dela. A função então ainda mantém uma referência a essa variável e a variável continua existindo, como mostra o estado à direita.
3.5 Threads e Coroutines
Lua possui corountines assimétricas, que são implementadas pela sua biblioteca padrão através de 3 métodos: create, resume e yield. A primeira cria uma thread, recebendo uma função como parâmetro, e retornando um valor do tipo thread. O método resume inicia ou reinicia a execução da thread, chamando a função passada como parâmetro anteriormente. Por fim, o método yield suspende a execução da coroutine e passa o controle de execução de volta para a função chamadora.
24
3.6 Implementação da linguagem
Vamos agora descrever um pouco a arquitetura de Lua, e como a implementação da linguagem contempla os requisitos do projeto.
Figura 3.3 Diagrama da implementação da linguagem [3]
A imagem acima mostra um esquema do que acontece numa aplicação quando ela vai executar um script em Lua, que é a situação mais comum de uso da linguagem. Primeiramente a aplicação em execução pede para a API de Lua criar uma instância do interpretador. Em seguida, é registrado quais bibliotecas de Lua serão usadas. Lua permite que uma aplicação estenda ou contraia o número de bibliotecas padrões que serão permitidas para a aplicação. Um arquivo é então carregado. No processo de carregamento, a API de Lua chama o compilador, que usa o analisador léxico e o gerador de bytecodes para pré-compilar o código, que será então enviado para a máquina virtual para execução. No caso do carregamento de um script já pré-compilado, o analisador léxico e o gerador de bytecodes não são usados.
25
3.7 Máquina virtual baseada em registradores
A máquina virtual de Lua desde 2003 (a partir da versão 5.0) é baseada em registradores, ao contrário de máquinas virtuais mais comuns que são baseadas em pilha. A diferença básica para a linguagem intermediária é que ela não precisa de instruções para tirar ou pôr elementos na pilha. Ela se refere aos elementos como um assembly se referiria a registradores. Ou seja, um instrução de adição de 3 endereços apenas informaria o número dos 2 registradores que serão somados e o número do registrador que receberia o resultado. Note o código abaixo:
local a, t, i
a = a + i
a = a + 1
a = t[i]
Esse código apenas declara 3 variáveis, executa duas somas, um acesso a um arranjo e 3 atribuições. Abaixo temos esse código compilado para código intermediário de Lua, na versão 4.0 da implementação da linguagem, com a utilização de uma máquina virtual baseada em pilha.
Figura 3.4 Bytecode na versão 4.0 da implementação de Lua [2]
26
Nesse ponto não iremos nos ater muito à sintaxe da linguagem intermediária de Lua, nem às instruções existentes. Isso será explicado logo a seguir.
Numa máquina virtual baseada em pilha, existem instruções de push e pop, que colocam e tiram elementos da pilha. Para as adições, os elementos necessários são tirados da pilha e somados, e o resultado é então escrito de volta na pilha. Para o acesso ao arranjo usa-se uma instrução para pegar o índice e outra para acessar o arranjo naquele índice. Abaixo temos então o mesmo código, compilado para a versão 5.0 da implementação da linguagem, já usando a máquina baseada em registradores.
Figura 3.5 Bytecode na versão 5.0 da implementação de Lua [2]
Veja que o número de instruções agora diminuiu bastante, já que não é mais necessário usar instruções para pegar e colocar elementos na pilha. A instrução de adição apenas especifica quais serão os 2 registradores a serem somados, e qual receberá o resultado. Se um dos operadores for numeral, a instrução recebe um valor que represente o numeral na lista de constantes definidas para o programa, ao invés de receber um valor de um registrador, como é o caso da segunda instrução de adição. Com esse tipo de abordagem, a linguagem intermediária de Lua fica mais simples, compacta, e certamente mais rápida.
Testes foram realizados e concluiu-se que o maior benefício trazido pela transição de máquinas virtuais baseadas em pilha para baseadas em registradores é uma redução no número de instruções expedidas, que consequentemente reduz os erros de predição de branches. Há outras benefícios também, como redução no número de instruções da máquina real no nível da CPU [7].
Cada arquivo de script Lua quando é compilado é tratado como um chunk, que pode ser passado para a máquina virtual executar ou ser persistido em disco na forma de um arquivo pré-compilado. Esses chunks são escritos na linguagem intermediária de Lua.
27
3.8 Exemplo de instruções do bytecode Lua
Vamos agora mostrar um pequeno exemplo de programa representado nessa linguagem intermediária de Lua, para entendermos um pouco melhor sua sintaxe e semântica. Note o programa abaixo:
function soma(x,y)
a = x + y
b = a
return b
end
local i,j
global = "variavel global"
local bool1 = true
local bool2 = false
if bool2 or bool1 then
i = 7
j = 8
end
tabela = {nome = global, soma(i,j), soma(-i,j), soma(i,-j), soma(-i,-j)}
for f = 1, 4 do
print(tabela[f])
end
Figura 3.6 Exemplo de código em Lua
Esse é um bom exemplo para entendermos um bytecode de Lua já que ele contempla uma função interna, um laço “for”, um condicional “if”, uma tabela e possui variáveis string, booleanas, numerais, locais e globais. Abaixo está o bytecode gerado pelo compilador de Lua, com comentários.
main <exemplo_didatico.lua:0,0> (44 instructions, 176 bytes at 0x92bed30) 0+ params, 11 slots, 0 upvalues, 8 locals, 10 constants, 1 function
28
1 [5] CLOSURE 0 0 ; 0x92bee60 2 [1] SETGLOBAL 0 -1 ; soma
Figura 3.7 Ínicio de um programa e declaração de função em bytecode Lua
Primeiramente, deixamos claro que o que vier após um “;” será sempre considerado um comentário, e não faz parte do bytecode em si. Acima podemos ver que o compilador definiu a função como a “main”, a função que será executada inicialmente quando o chunk for enviado para a máquina virtual. Essa função foi compilada a partir do arquivo exemplo_didatico.lua e possui 44 instruções de bytecode. Ela não recebe parâmetros, não utiliza upvalues, possui 8 variáveis locais, 10 constantes e 1 função interna. Como podemos perceber no código acima, o código é iniciado com a declaração da função “soma”.
E as duas linhas acima realizam essa declaração. A instrução CLOSURE cria uma CLOSURE de uma função, ou seja, uma instância daquela função. O segundo parâmetro da instrução é o índice da função em questão na lista de funções internas e o primeiro parâmetro é o registrador em que será guardada essa instância. No caso, a função interna de número 0 (só existe 1 e a contagem inicia em 0) é armazenada no registrador 0.
3 [6] LOADNIL 0 1 4 [7] LOADK 2 -3 ; "variavel global" 5 [7] SETGLOBAL 2 -2 ; global 6 [8] LOADBOOL 2 1 0 7 [9] LOADBOOL 3 0 0
Figura 3.8 Exemplos de declaração e atribuição de variáveis globais e locais
Essas 5 instruções são responsáveis pela declaração de “i” e “j” e pela criação e inicialização de “global”, “bool1” e “bool2”. Veja que as variáveis declaradas e não inicializadas são criadas todas através de uma única instrução LOADNIL, que inicializa todos os registradores com nil desde o primeiro parâmetro (0), até o último parâmetro (1). Dessa forma o registrador 0 guardará o valor de “i” e o registrador 1 o de “j”. A constante “variavel global” é então buscada do conjunto de constantes do programa e guardada no registrador 2. Números negativos representam constantes. Essa constante então é a constante de numero 3, e não o registrador de número 3. Em seguida esse valor, que já está no registrador 2, é então associado à constante 2, que possui o nome “global”. Agora, sempre que o valor da constante “global” for solicitado, o valor “variavel global” será retornado. Por fim, o registrador 2 é reutilizado para “bool1”, com valor true, e o registrador 3 é usado para “bool2”, com valor false.
A instrução LOADBOOL ainda possui um terceiro parâmetro, que se for 1 fará a próxima instrução ser pulada. Isso pode ser útil em algumas situações.
8 [10] TEST 3 0 1 9 [10] JMP 2 ; to 12
29
10 [10] TEST 2 0 0 11 [10] JMP 2 ; to 14 12 [11] LOADK 0 -4 ; 7 13 [12] LOADK 1 -5 ; 8
Figura 3.9 Exemplo de instrução condicional
Primeiramente, a instrução JMP realiza um salto de instruções igual ao único parâmetro que ela recebe. A instrução TEST seguida da instrução JMP implementa testes booleanos. A instrução TEST não utiliza o segundo parâmetro. O que a instrução faz é aplicar um AND lógico entre o valor no registrador do primeiro parâmetro e o valor no terceiro parâmetro. Se essa comparação resultar em “false”, a próxima instrução é pulada. No primeiro TEST, o valor de “bool2” é “false” e o terceiro parâmetro é “true” (1), então o resultado é “false” e a próxima instrução é pulada. O mesmo acontece com o segundo TEST, pois “bool1” é “true” e o terceiro parâmetro é “false” (0). Caso um desses testes não fizesse a instrução seguinte pular, uma instrução JMP seria executada, fazendo com que a avaliação de todo o resto da clausula fosse interrompida. No caso de um “and”, um resultado “false” causaria isso, e no caso de um “or”, isso seria causado por um “true”.
As últimas instruções LOADK pegam as constantes 4 e 5 que correspondem aos números 7 e 8, e atribuem elas aos registradores 0 e 1, que representam as variáveis “i” e “j”.
14 [14] NEWTABLE 4 3 1 15 [14] GETGLOBAL 5 -2 ; global 16 [14] SETTABLE 4 -7 5 ; "nome" - 17 [14] GETGLOBAL 5 -1 ; soma 18 [14] MOVE 6 0 19 [14] MOVE 7 1 20 [14] CALL 5 3 2 21 [14] GETGLOBAL 6 -1 ; soma 22 [14] UNM 7 0 23 [14] MOVE 8 1 24 [14] CALL 6 3 2 25 [14] GETGLOBAL 7 -1 ; soma 26 [14] MOVE 8 0 27 [14] UNM 9 1 28 [14] CALL 7 3 2 29 [14] GETGLOBAL 8 -1 ; soma 30 [14] UNM 9 0 31 [14] UNM 10 1 32 [14] CALL 8 3 0
Figura 3.10 Exemplo de uso de tabelas e funções
A instrução NEWTABLE é responsável por criar uma tabela. O primeiro parâmetro é o registrador que guardará a tabela por enquanto. O segundo parâmetro indica o tamanho inicial da parte de arranjo da tabela, e o terceiro indica o tamanho inicial da parte de tabela hash. A instrução GETGLOBAL pega o valor associado à
30
constante 2 (“global”) e coloca no registrador 5. A instrução SETTABLE pega o valor no registrador 5 e associa à constante 7 (“nome”), que é um índice para a tabela do registrador 4.
Em seguida as instruções GETGLOBAL, MOVE, MOVE e CALL são usadas para inicializar cada posição do arranjo da tabela, ou seja, elas são usadas 4 vezes. A instrução CALL chama a instância de função do primeiro parâmetro passado. Os parâmetros para a função são colocados nos registradores após o registrador do primeiro parâmetro. Os valores retornados também são colocados nos registradores após esse registrador.
Tratando o número de parâmetros da função como X e o número de valores de retorno como Y, o segundo e o terceiro parâmetros da instrução CALL são X+1 e Y+1. Nesse caso, a primeira instrução GETGLOBAL e CALL pegam a função “soma”, põem ela no registrador 5 e informam que ela recebe 2 argumentos e retorna 1 valor. A função é então chamada, esperando que nos registradores após o 5 estejam os parâmetros e sejam colocados os retornos.
E é para garantir isso que existem as instruções MOVE. Como a função “soma” deve receber como argumentos “i” e “j”, essa instrução copia o valor de “i” e “j” para os locais corretos, que no caso são os registradores 6 e 7. O mesmo raciocínio se aplica aos outros 3 usos desses instruções no programa. A instrução UNM faz o mesmo que MOVE, mas inverte o sinal.
33 [14] SETLIST 4 0 1 ; 1 34 [14] SETGLOBAL 4 -6 ; tabela
Figura 3.11 Exemplo de atribuição de um arranjo numa tabela
Essa instrução SETLIST atribui uma lista de valores a um conjunto de posições de um arranjo. A tabela contendo o arranjo é informada pelo primeiro parâmetro. O segundo parâmetro informa quantos valores serão copiados. Caso esse valor for 0, significa que um valor variável de valores será copiado. Como conhecemos o programa, sabemos que o valor não é variável, e sim é 4, mas como esses valores são retornos de função, o compilador não verifica quantos valores retornam a função. O terceiro parâmetro indica a primeira posição do arranjo que receberá um valor copiado. A instrução SETGLOBAL então atribui a tabela criada à constante 6 (“tabela”).
35 [15] LOADK 4 -8 ; 1 36 [15] LOADK 5 -9 ; 4 37 [15] LOADK 6 -8 ; 1
Figura 3.12 Preparação de variáveis para uso num bloco “for”
31
Essas instruções preparam a execução do laço “for”. No registrador 4 é colocado o valor inicial da variável, no registrador 5 é colocado o valor final e no registrador 6 é colocado o passo a ser seguido pelo laço, que por padrão é 1.
38 [15] FORPREP 4 4 ; to 43 39 [16] GETGLOBAL 8 -10 ; print 40 [16] GETGLOBAL 9 -6 ; tabela 41 [16] GETTABLE 9 9 7 42 [16] CALL 8 2 1 43 [15] FORLOOP 4 -5 ; to 39
Figura 3.13 Exemplo de uso de bloco “for”
A instrução FORPREP inicializa um laço “for”. Um “for” utiliza os 3 valores definidos anteriormente, e o primeiro parâmetro dessa instrução informa qual o primeiro registrador dos três, que deve conter o valor inicial da variável de controle do laço. O segundo parâmetro da instrução informa quantas instruções serão puladas a seguir. Esse salto é executado porque a instrução FORPREP apenas inicializa o “for”, mas não executa ele. Esse salto pula o fluxo de execução para a instrução FORLOOP, que incrementa a variável de controle do laço (indicada pelo primeiro parâmetro), verifica se a condição de controle permite que o “for” seja executado novamente e, se verdadeiro, soma o segundo parâmetro da instrução ao program counter, fazendo com que o código interno ao “for” seja executado.
O código interno ao laço em si possui 2 instruções GETGLOBAL que pega a instância da função “print” e a tabela “tabela”. Em seguida, uma instrução GETTABLE pega o valor na posição da tabela indicada pelo registrador 7, que é a variável interna do “for”, que no caso é “f”. Por fim, a instrução CALL chama a função “print” mandando o valor retornado como parâmetro.
44 [17] RETURN 0 1
Figura 3.14 Instrução final de toda função de Lua
A instrução RETURN está presente no fim de todas as funções em Lua, mesmo que ela seja desnecessária ou que sua execução jamais ocorra. No caso, não seria necessária essa instrução já que a função “main” não precisa retornar nada.
function <exemplo_didatico.lua:1,5> (7 instructions, 28 bytes at 0x92bee60) 2 params, 3 slots, 0 upvalues, 2 locals, 2 constants, 0 functions 1 [2] ADD 2 0 1 2 [2] SETGLOBAL 2 -1 ; a 3 [3] GETGLOBAL 2 -1 ; a 4 [3] SETGLOBAL 2 -2 ; b
32
5 [4] GETGLOBAL 2 -2 ; b 6 [4] RETURN 2 2 7 [5] RETURN 0 1
Figura 3.15 Exemplo de protótipo de função interna
Acima temos o código em si da função “soma”, definida como tendo 2 parâmetros, nenhum upvalue, 2 variáveis locais, 2 constantes e nenhuma função interna. O código dela é simples. Ela soma os registradores 0 e 1, que são diferentes da função “main”, e coloca o resultado no registrador 2. Depois pega esse valor e associa à variável “a”, pega o valor associado à variável “a” e associa à variável “b”, pega o valor associado à variável “b” e retorna ele. E esse código dessa função já ilustra o próximo ponto que iremos cobrir, que contemplará o que podemos otimizar em código Lua.
3.9 Outras instruções da máquina virtual
O exemplo acima usa exatamente metade das 38 instruções que a máquina virtual de Lua reconhece. Vamos agora então descrever um pouco as outras. Como vimos anteriormente, a instrução de adição, chamada ADD, recebe 3 registradores como parâmetros. O primeiro guardará o resultado da soma e os dois seguintes informam os valores a serem somados. Para as outras operações aritméticas o funcionamento é o mesmo, mudando apenas o opcode. Lua contempla as instruções SUB, MUL, DIV, MOD e POW, sendo que essas duas últimas são responsáveis por calcular o resto de uma divisão e a potenciação entre dois números. Além disso, existe a instrução NOT, que implementa o operador lógico “not” da mesma forma que é implementada a instrução UNM [4].
A instrução LEN calcula o tamanho do objeto passado como parâmetro. Se for uma string, calcula apenas o comprimento da string. Se for uma tabela, calcula o tamanho da tabela. A instrução CONCAT concatena strings num conjunto de registradores, ou seja, uma instrução pode realizar a concatenação de inúmeras strings [4].
Além das instruções GETTABLE, GETGLOBAL, SETTABLE e SETGLOBAL, que acessam posições na tabela ou no conjunto das constantes do programa, também existem as instruções GETUPVAL e SETUPVAL. Upvalues, como dissemos anteriormente, é toda variável que seja externa à uma função e que seja usado pela função. Se tivermos então uma variável global “i” e outra ‘j”, podemos definir uma função dentro do mesmo chunk que some as duas, sem precisar passá-las como parâmetro para a função. A função consegue enxergar essas duas variáveis, e se usarmos elas dentro da função o compilador irá gerar instruções GETUPVAL e SETUPVAL para lermos essas variáveis ou sobrescrever o valor delas [4].
33
A instrução SELF é usada para programação orientada a objetos usando tabelas. Ela pega uma função de um elemento da tabela, coloca num registrador e depois pega uma referência da própria tabela e põe no registrador seguinte. Isso poupa algumas manipulações mais complicadas na hora de chamar métodos [4].
As instruções EQ, LT e LE implementam testes de igualdade, “menor que” e “menor ou igual que”. Elas comparam o segundo parâmetro com o terceiro parâmetro e, se o resultado (“true” ou “false”) não for igual ao valor booleano do primeiro parâmetro, a próxima instrução é pulada. Já a instrução TESTSET possui comportamento semelhante ao da instrução TEST vista anteriormente. A instrução TEST aplicava um “and” entre os dois primeiros parâmetros e se o resultado fosse “false” a próxima instrução seria pulada. A instrução TESTSET também pula a próxima instrução se o resultado for “false”, mas o teste é entre o primeiro e o terceiro parâmetro, e se for verdadeiro o valor no registrador do segundo parâmetro é colocado no registrador do primeiro parâmetro. A diferença básica então é que o resultado de TESTSET é atribuído a uma variável, ao invés do resultado de TEST que é apenas usado para controlar o fluxo de execução [4].
A instrução TAILCALL funciona de forma semelhante à instrução CALL, mas é usada quando a expressão de retorno de uma função é uma chamada de outra função, como na expressão “return x()”, por exemplo. Já a instrução TFORLOOP implementa um outro tipo de laço “for” suportado por Lua, um “for” genérico. Esse “for” genérico itera sobre praticamente qualquer coisa, ao contrário do “for” numérico visto anteriormente que itera sobre uma série de números. Um arranjo, por exemplo, pode ser passado para o “for”, e o “for” irá iterar sobre os elementos desse arranjo. Ele funciona de forma semelhante ao “for” numérico visto anteriormente, mas em vez de possuir 2 instruções, ele é implementado apenas com essa instrução TFORLOOP e utiliza 2 instruções JMP para realizar o controle [4].
Como falamos anteriormente, variáveis pertencentes a blocos que já terminaram de executar não são descartadas imediatamente porque podem estar sendo usados como upvalues por funções internas. Mas todos os dados no bloco em execução são descartados automaticamente após o fim da execução do bloco. Deve então haver alguma forma de guardar essas variáveis usadas como upvalues para que seus valores não sejam perdidos. A instrução CLOSE é responsável por isso. Ela percorre todos os registradores a partir do registrador passado como parâmetro e se encontrar algum que esteja sendo usado como upvalue ela copia seu valor e guarda num local seguro. A instrução RETURN mostrada anteriormente executa um CLOSE implícito também, então não é muito comum a instrução CLOSE ser usada [4].
Por fim, há a instrução VARARG. Ela é responsável por implementar as Vararg Functions de Lua, que são funções que podem receber uma quantidade variada de parâmetros [6]. Por exemplo, podemos ter uma função que calcula a média entre todos os valores passados como parâmetro. Ela simplesmente copia um número de parâmetros
34
recebidos para um conjunto de registradores iniciando pelo informado no primeiro parâmetro da instrução [4].
É importante frisar, no entanto, que a equipe responsável por manter a implementação da linguagem não garante a compatibilidade do conjunto de instruções da máquina virtual entre versões diferentes. É importante deixar claro então que toda a pesquisa realizada aqui se baseou na versão 5.1 da implementação da linguagem.
Por razões apenas ilustrativas, vale dizer que, por exemplo, da versão 5.0.2 para a versão 5.1, 2 instruções foram excluídas (TFORPREP e SETLISTO), 1 mudou de nome (TEST para TESTSET) e 5 novas foram criadas (MOD, LEN, TEST, VARARG e FORPREP), além de várias outras pequenas mudanças na forma como são implementadas algumas instruções ou na forma como a máquina virtual trabalha [4].
3.10 Exemplos de código em bytecode
Abaixo, para ilustrar mais a natureza do código intermediário de Lua, iremos mostrar como fica em linguagem intermediária de Lua o nosso primeiro exemplo, da figura 2.1.
main <otimizacao1.lua:0,0> (62 instructions, 248 bytes at 0x8f90d20) 0+ params, 8 slots, 0 upvalues, 6 locals, 26 constants, 1 function 1 [1] NEWTABLE 0 0 12 2 [1] SETTABLE 0 -1 -2 ; 0 1 3 [1] SETTABLE 0 -2 -3 ; 1 2 4 [1] SETTABLE 0 -3 -4 ; 2 4 5 [1] SETTABLE 0 -5 -6 ; 3 8 6 [1] SETTABLE 0 -4 -7 ; 4 16 7 [1] SETTABLE 0 -8 -9 ; 5 32 8 [1] SETTABLE 0 -10 -11 ; 6 64 9 [1] SETTABLE 0 -12 -13 ; 7 128 10 [1] SETTABLE 0 -6 -14 ; 8 256 11 [1] SETTABLE 0 -15 -16 ; 9 512 12 [1] SETTABLE 0 -17 -18 ; 10 1024 13 [1] SETTABLE 0 -19 -20 ; 11 2048 14 [2] LOADK 1 -1 ; 0 15 [3] LOADNIL 2 5 16 [5] LOADK 6 -15 ; 9 17 [5] SETGLOBAL 6 -21 ; c 18 [8] CLOSURE 6 0 ; 0x8f91658 19 [6] SETGLOBAL 6 -22 ; x 20 [9] GETGLOBAL 6 -21 ; c 21 [9] GETGLOBAL 7 -22 ; x 22 [9] CALL 7 1 2 23 [9] ADD 6 6 7 24 [9] SETGLOBAL 6 -23 ; e 25 [10] LT 0 1 -24 ; - 12 26 [10] JMP 25 ; to 52 27 [11] POW 2 -3 1 ; 2 -
35
28 [12] GETTABLE 6 0 1 29 [12] EQ 0 6 2 30 [12] JMP 10 ; to 41 31 [13] GETGLOBAL 6 -25 ; print 32 [13] GETTABLE 7 0 1 33 [13] EQ 1 7 2 34 [13] JMP 1 ; to 36 35 [13] LOADBOOL 7 0 1 36 [13] LOADBOOL 7 1 0 37 [13] CALL 6 2 1 38 [14] GETGLOBAL 6 -25 ; print 39 [14] GETTABLE 7 0 1 40 [14] CALL 6 2 1 41 [16] ADD 1 1 -2 ; - 1 42 [17] MUL 3 -3 1 ; 2 - 43 [18] LOADK 4 -3 ; 2 44 [19] SUB 5 4 -3 ; - 2 45 [20] GETGLOBAL 6 -21 ; c 46 [20] GETGLOBAL 7 -23 ; e 47 [20] ADD 6 6 7 48 [20] SETGLOBAL 6 -26 ; d 49 [20] JMP -25 ; to 25 50 [22] JMP 1 ; to 52 51 [23] LOADK 2 -1 ; 0 52 [25] GETGLOBAL 6 -21 ; c 53 [25] GETGLOBAL 7 -23 ; e 54 [25] ADD 1 6 7 55 [26] GETGLOBAL 6 -25 ; print 56 [26] MOVE 7 1 57 [26] CALL 6 2 1 58 [27] GETGLOBAL 6 -25 ; print 59 [27] MOVE 7 3 60 [27] CALL 6 2 1 61 [28] RETURN 5 2 62 [28] RETURN 0 1 function <otimizacao1.lua:6,8> (3 instructions, 12 bytes at 0x8f91658) 0 params, 2 slots, 0 upvalues, 0 locals, 1 constant, 0 functions 1 [7] LOADK 0 -1 ; 1 2 [7] RETURN 0 2 3 [8] RETURN 0 1
Figura 3.16 Bytecode do código da figura 2.1
E segue abaixo o código mostrado na figura 4.5, após as otimizações manuais que aplicaremos a seguir.
main <otimizacao2.lua:0,0> (53 instructions, 212 bytes at 0x9532d20) 0+ params, 6 slots, 0 upvalues, 4 locals, 27 constants, 1 function 1 [1] NEWTABLE 0 0 12 2 [1] SETTABLE 0 -1 -2 ; 0 1 3 [1] SETTABLE 0 -2 -3 ; 1 2 4 [1] SETTABLE 0 -3 -4 ; 2 4 5 [1] SETTABLE 0 -5 -6 ; 3 8 6 [1] SETTABLE 0 -4 -7 ; 4 16 7 [1] SETTABLE 0 -8 -9 ; 5 32 8 [1] SETTABLE 0 -10 -11 ; 6 64 9 [1] SETTABLE 0 -12 -13 ; 7 128 10 [1] SETTABLE 0 -6 -14 ; 8 256
36
11 [1] SETTABLE 0 -15 -16 ; 9 512 12 [1] SETTABLE 0 -17 -18 ; 10 1024 13 [1] SETTABLE 0 -19 -20 ; 11 2048 14 [2] LOADK 1 -1 ; 0 15 [3] LOADNIL 2 3 16 [6] CLOSURE 4 0 ; 0x9532fa8 17 [4] SETGLOBAL 4 -21 ; x 18 [7] GETGLOBAL 4 -21 ; x 19 [7] CALL 4 1 2 20 [7] ADD 4 -23 4 ; 18 - 21 [7] SETGLOBAL 4 -22 ; d 22 [8] LT 0 1 -24 ; - 12 23 [8] JMP 21 ; to 45 24 [9] POW 2 -3 1 ; 2 - 25 [10] GETTABLE 4 0 1 26 [10] SETGLOBAL 4 -25 ; temp1 27 [11] GETGLOBAL 4 -25 ; temp1 28 [11] EQ 1 4 2 29 [11] JMP 1 ; to 31 30 [11] LOADBOOL 4 0 1 31 [11] LOADBOOL 4 1 0 32 [11] SETGLOBAL 4 -26 ; temp2 33 [12] GETGLOBAL 4 -26 ; temp2 34 [12] TEST 4 0 0 35 [12] JMP 6 ; to 42 36 [13] GETGLOBAL 4 -27 ; print 37 [13] GETGLOBAL 5 -26 ; temp2 38 [13] CALL 4 2 1 39 [14] GETGLOBAL 4 -27 ; print 40 [14] GETGLOBAL 5 -25 ; temp1 41 [14] CALL 4 2 1 42 [16] ADD 1 1 -2 ; - 1 43 [17] ADD 3 3 -3 ; - 2 44 [17] JMP -23 ; to 22 45 [19] GETGLOBAL 4 -27 ; print 46 [19] GETGLOBAL 5 -22 ; d 47 [19] CALL 4 2 1 48 [20] GETGLOBAL 4 -27 ; print 49 [20] MOVE 5 3 50 [20] CALL 4 2 1 51 [21] LOADK 4 -1 ; 0 52 [21] RETURN 4 2 53 [21] RETURN 0 1 function <otimizacao2.lua:4,6> (3 instructions, 12 bytes at 0x9532fa8) 0 params, 2 slots, 0 upvalues, 0 locals, 1 constant, 0 functions 1 [5] LOADK 0 -1 ; 1 2 [5] RETURN 0 2 3 [6] RETURN 0 1
Figura 3.17 Bytecode do código da figura 4.4 O código otimizado manualmente possui 9 instruções a menos e usa 36 bytes a menos de espaço, porém, aplicar as técnicas de otimização diretamente no código intermediário de Lua certamente proporcionaria melhores resultados. Veremos a seguir quais técnicas existem para isso.
37
4. Otimização de Código
Abaixo descreveremos agora quais as otimizações de código foram estudadas. Como vimos anteriormente, a escolha de quais otimizações estudar veio do pré-requisito que se tinha de estudar apenas otimizações independentes de máquina.
Além disso, desejava-se criar otimizações para instruções na forma SSA com utilização de um grafo de fluxo de controle, pelo sucesso já obtido em outros trabalhos, e essas otimizações abaixo são otimizações que em sua maioria são beneficiadas pela utilização de um grafo de fluxo de controle e instruções na forma SSA [8].
4.1 Subexpressão comum
Uma ocorrência de uma expressão E é chamada de subexpressão comum se E tiver sido computada anteriormente e os valores das variáveis em E não tiverem mudado desde a computação anterior [1]. Dessa forma, se calculamos E num momento, não precisaremos recalculá-la enquanto os valores das variáveis nela não mudarem, pois se o fizéssemos obteríamos novamente o mesmo resultado.
No programa em Lua da Figura 2.1, a expressão “powerTwo[i]” é calculada três vezes a cada iteração do laço, enquanto a comparação “powerTwo[i] == j” é executada duas vezes também a cada iteração. Como o arranjo “powerTwo”, a variável “i” e a variável “j” não sofrem alterações nesse período, essas duas são subexpressões comuns e não precisariam ser calculadas mais do que uma vez.
Nesse caso, o otimizador de código criaria uma variável local temporária e atribuiria a ela o valor de “powerTwo[i]”. Depois criaria outra variável temporária e atribuiria a ela o valor da comparação de “powerTwo[i]” com “j”. Em seguida substituiria o valor das subexpressões pelo valor constante dessas variáveis.
Além disso, a subexpressão “c + e” atribuída a “i” no final do programa é uma subexpressão comum à atribuída a “d” dentro do loop “while”. Note que após a expressão ser atribuída a “d”, nem o valor de “c” e nem o valor de “e” são alterados, de forma que se calculássemos essa expressão novamente, teríamos o mesmo resultado.
Nesse caso, o otimizador de código substituiria todo cálculo subseqüente de E pela variável que possui o primeiro valor de E calculado, sempre verificando antes se E continua sendo uma subexpressão comum. No caso acima, a instrução “i = c + e” seria substituída por “i = d”.
38
Essas três alterações no código deixariam o código do programa da seguinte forma:
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
local a,b
c = 9
function x()
return 2/2
end
e = c + x()
while i < 12 do
j = 2 ^ i
temp1 = powerTwo[i]
temp2 = temp1 == j
if temp2 then
print(temp2)
print(temp1)
end
i = i + 1
y = 2 * i
a = 2
b = a - 2
d = c + e
end
if false then
j = 0
end
39
i = d
print(i)
print(y)
return b
Figura 4.1 Código em Lua sem Subexpressões comuns
Note que o número de instruções no programa aumentou em 2, mas isso não significa que o programa está mais lento. Isso é normal para algumas otimizações quando estamos buscando um desempenho melhor, o que de fato ocorre com as alterações realizadas acima.
4.2 Propagação de cópia
As instruções de cópia são criadas naturalmente por algoritmos de otimização, porém são desnecessárias. Instruções de cópia são instruções na forma “a = b”, em que o valor de uma variável é simplesmente copiado para outra variável. A idéia dessa otimização é substituir a variável “a” pela variável “b” nas instruções subseqüentes. Essa transformação pode não parecer muito útil, mas, como veremos a seguir, ela cria código morto no programa, que pode ser posteriormente eliminado por uma outra otimização que veremos.
No nosso exemplo, a instrução “i = d”, que foi criada pela eliminação de subexpressões comuns, é uma instrução de cópia. Os próximos usos da variável “i” então podem ser substituídos pela variável “d”. Dessa forma, a última instrução do código se torna “print(d)”.
4.3 Desdobramento de constante
Uma otimização semelhante à Propagação de cópia é o Desdobramento de constante. Se por acaso descobrirmos que o valor de uma expressão é constante, podemos substituir o uso dessa expressão pela constante. Isso ocorre no nosso exemplo nas seguintes instruções: “e = c + x()”, “b = a – 2”, “d = c + e”, “return 2/2”, “return b” e no “if” externo.
40
Veja que o valor atribuído a “c” no início do programa é a constante 9, não importa qual seja o estado do programa. O mesmo ocorre com o valor de “a”, que sempre será 2. E tratando “a” como constante concluímos a seguir que “b” também é uma constante, que possuirá sempre o valor 0, e portanto podemos transformar a instrução “return b” em “return 0”. Além disso, a expressão atribuída a “e” pode ser considerada como uma constante. Por fim, é fácil verificar que a instrução “return 2/2” pode ser transformada para “return 1”. Abaixo então temos o código do programa após a Propagação da cópia e o Desdobramento das constantes:
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
local a,b
c = 9
function x()
return 1
end
e = 9 + x()
while i < 12 do
j = 2 ^ i
temp1 = powerTwo[i]
temp2 = temp1 == j
if temp2 then
print(temp2)
print(temp1)
end
i = i + 1
y = 2 * i
a = 2
b = 0
41
d = 18 + x()
end
if false then
j = 0
end
i = d
print(d)
print(y)
return 0
Figura 4.2 Código com Propagação de cópia e Desdobramento de constante
Veja que não estamos considerando o valor da variável “d” como constante nessa análise, já que não sabemos se o valor que a função “x” retorna é sempre constante. Se fossemos mais além na análise e verificássemos os possíveis valores de retorno para a função “x”, veríamos que ela retornará sempre o valor 1, e então poderíamos considerar a variável “d” como constante também.
4.4 Eliminação de código morto
Uma variável estará viva em algum ponto de um programa se seu valor puder ser usado posteriormente [1]. Caso contrário, ela está morta nesse ponto. Uma idéia relacionada é o código morto (ou inútil). Um código estará morto quando ele não possuir utilidade, e sua exclusão não afetar em absolutamente nada a semântica do programa. Embora esse código possa já estar presente no início da compilação, ele é geralmente criado como resultado de outras otimizações. Com a propagação de copia e o desdobramento de constante várias ocorrências de código morto aparecem.
No nosso exemplo, além do simples “if” que nunca é executado por completo, nenhum outro código estava morto inicialmente, porém após as otimizações anteriores todas essas instruções estão mortas: “i = d”, “b = 0”, “a = 2”, “e = 9 + x()”, ”c = 9” e, consequentemente, “local a,b”. Abaixo mostramos o código do programa após a eliminação de todas essas instruções:
42
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
function x()
return 1
end
while i < 12 do
j = 2 ^ i
temp1 = powerTwo[i]
temp2 = temp1 == j
if temp2 then
print(temp2)
print(temp1)
end
i = i + 1
y = 2 * i
d = 18 + x()
end
print(d)
print(y)
return 0
Figura 4.3 Código em Lua sem Código morto
4.5 Movimentação de código
Esse tipo de otimização é especial para laços internos. É muito interessante diminuir a quantidade de instruções num laço interno, mesmo que isso aumente o numero de instruções fora do laço [1]. Uma modificação importante é a movimentação de código. Nesse caso, movimenta-se o código invariante do laço. A razão para isso é
43
simples: espera-se que as instruções dentro do laço sejam executadas inúmeras vezes, repetidamente, enquanto as instruções fora do laço são executadas apenas uma vez. Dessa forma, se pudermos retirar pelo menos uma instrução de dentro de um laço, já estaremos atingindo uma grande melhora no desempenho. E é exatamente isso que conseguimos no nosso exemplo. A expressão “d = 18 + x()” não afeta em nada o laço. Podemos então tirá-la do laço, calculando ela antes do laço.
4.6 Variáveis de indução
Uma variável ‘x’ é considerada uma “variável de indução” se houver uma constante positiva ou negativa ‘c’ tal que, toda vez que ‘x’ for atribuído, seu valor aumenta de acordo com ‘c’ [1]. É importante otimizar o cálculo de variáveis de indução, substituindo um conjunto de subexpressões por outro com menos instruções, ou de menor custo. Uma técnica é a redução de força, mas não é a única. Observe que no nosso exemplo, dentro do laço, existem 3 variáveis de indução: “i”, que aumenta em 1 a cada iteração, “j” que aumenta em 2 elevado a “i” a cada iteração e “y” que aumenta em 2 vezes “i” a cada iteração do laço.
O incremento de “i” já possui um custo bem reduzido, e não há muito o que mudar no de “j”, porém o custo do incremento de “y” pode ser reduzido. Atualmente ele efetua a cada iteração uma multiplicação de “i” por 2. Porém, analisando o código, podemos ver que “i” aumenta de 1 em 1, e portanto, “y” aumentará sempre de 2 em 2. Podemos então substituir a instrução “y = 2 * i” por “y = y + 2”.
Abaixo temos o código final após todas as otimizações descritas acima:
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
function x()
return 1
end
d = 18 + x()
while i < 12 do
44
j = 2 ^ i
temp1 = powerTwo[i]
temp2 = temp1 == j
if temp2 then
print(temp2)
print(temp1)
end
i = i + 1
y = y + 2
end
print(d)
print(y)
return 0
Figura 4.4 Código em Lua otimizado manualmente
Esse programa executará significativamente menos instruções, e instruções mais baratas.
Embora apenas em raras exceções se obtenha de fato um código ótimo, as técnicas conhecidas de otimização de código são capazes de melhorar inúmeros fatores do código otimizado, seja seu tempo de execução ou mesmo o espaço ocupado.
Apesar de serem importantes, as otimizações possíveis dependem muito da natureza da linguagem de programação, fazendo com que otimizar o código de uma linguagem seja um grande desafio. Deve-se levar em conta não só quais otimizações são possíveis, como também como realizar cada uma e quais cuidados tomar.
Ao executar as otimizações acima, devemos ser extremamente conservadores, como vimos anteriormente ao não considerarmos o retorno da função “x” como constante por não termos certeza de todos os valores possíveis de retorno. O maior cuidado ao se realizar otimizações deve ser sempre manter a semântica do programa. Todas as otimizações devem alterar o código do programa, mas aquilo que o programa faz deve ser mantido à risca. Isso faz com que não se possa realizar nenhuma otimização que não se tenha a certeza de que não irá afetar a semântica do programa.
45
5. Análise de Fluxo de Dados
As oportunidades de otimização descritas acima são criadas durante o desenvolvimento de software, na própria linguagem fonte, porém novas surgirão após transformarmos esse código em código intermediário de Lua. A seguir falaremos em detalhes a respeito de como foi estudar e implementar otimizações de código para essa linguagem intermediária. 5.1 Introdução à Análise de Fluxo de Dados
A forma como todas essas otimizações são realizadas é simples. O otimizador de código varre todo o código já compilado para código intermediário e, para cada ponto do programa, ele coleta informações diversas a respeito do estado do programa naquele momento. Essas informações podem ser de qualquer natureza, pois o otimizador pega qualquer informação que for útil para entender o comportamento do programa. Por exemplo, sabendo que em um ponto do programa uma variável é definida e que ela não é usada em nenhum outro ponto posterior do programa, podemos concluir que essa variável não é utilizada pelo programa, e podemos então excluir sua definição, diminuindo o número de instruções do programa e possivelmente também o quanto de memória ele usará. Há uma série de algoritmos existentes que permitem que um programa otimizador percorra cada ponto de um programa e colete informações a seu respeito. O conjunto de todos esses algoritmos constitui a análise de fluxo de dados. É analisando todo o fluxo de dados de um programa que podemos compreendê-lo, tirar conclusões a seu respeito e finalmente modificá-lo. 5.2 Abstraindo o Fluxo de Dados
Nessa análise, coletamos informações a respeito de cada ponto do programa, porém, não necessariamente cada ponto do programa é constituído de apenas uma linha de código. Consideramos que o programa possui um estado antes de cada ponto do programa, e também um estado após cada ponto. As alterações que fazem o programa ir de um estado para o outro são causadas pelas informações contidas no ponto do programa em questão. Podemos unir várias instruções consecutivas de um programa num único conjunto e considerá-lo como um único ponto no programa. Dessa forma, coletamos informações referentes a todas essas instruções. Esse conjunto de instruções é chamado
46
bloco básico e a divisão do código de um programa em blocos básicos segue algumas regras pré-definidas. Por definição, um bloco básico é um conjunto de linhas de código com um único ponto de entrada, um único ponto de saída e, consequentemente, sem nenhum desvio de fluxo de execução entre o início e o fim. Por essa razão, dividimos o programa fonte em blocos básicos da seguinte forma: tratamos inicialmente o programa todo como sendo um único bloco básico e, então, percorremos o código do início ao fim, separando ele em blocos básicos, dependendo da instrução que encontramos. Instruções de branch, seja condicional ou incondicional, ou instruções de retorno para o procedimento chamador e, em alguns casos, também chamadas de procedimentos, são instruções que encerram blocos básicos. Por outro lado, instruções encontradas após chamadas de procedimentos, instruções que iniciam um novo procedimento e, principalmente, instruções alvo de branches e jumps, são exemplos de instruções que iniciam novos blocos básicos. De maneira conservadora, devemos sempre encerrar blocos básicos se a instrução em questão pode gerar exceções, e é por isso que na abordagem desse projeto decidiu-se tratar qualquer chamada de procedimento como uma instrução que encerra o bloco básico. Poderíamos fazer uma análise mais detalhada de cada procedimento, avaliar as possibilidades de geração de exceção, e também avaliar quais valores de retorno ele pode ter, porém essa análise aumentaria muito a complexidade do projeto, de forma que consideramos que todo procedimento pode gerar exceção e também pode obter como retorno qualquer tipo de informação. Criando os blocos básicos dessa maneira garantimos que não haverá problema ao realizarmos a análise de fluxo de dados considerando todas as linhas de código do bloco como um único ponto no programa. Para entendermos bem as informações contidas em cada bloco básico do programa, devemos conhecer bem seu estado de entrada e de saída. O estado de entrada e saída de cada bloco básico é criado com base nos blocos básicos que podem fazer o fluxo de execução ir para o início do bloco básico em questão. Com o intuito então de conhecermos sempre quais partes de um programa podem fazer o fluxo de execução passar para o início de cada bloco básico, criamos um grafo de fluxo de controle. Nesse grafo, cada bloco básico é considerado um vértice, com um rótulo que o identifica e um elemento relacionado, o qual armazena todas as informações do bloco básico. Para representar as passagens de fluxo de controle de um bloco básico para o início de outro usamos então arestas. Esse grafo então é orientado e pode possuir ciclos. Por fim, adicionamos a este grafo dois vértices, um chamado ENTRY e o outro chamado EXIT. O vértice ENTRY é considerado um bloco vazio, e representa o início do grafo, o ponto de entrada do programa. Já o vértice EXIT também é vazio, mas representa o último vértice do grafo, para onde todas as arestas de saída do programa se direcionam.
47
5.3 Funções de transferência e Fluxo de controle
As análises de fluxo de dados utilizam duas táticas para tirar conclusões acerca de um programa: as funções de transferência e o fluxo de controle. Todas as informações que coletamos servem para determinarmos todas as funções de transferência e os fluxos de controle do programa. Com as funções de transferência de um ponto do programa, temos as alterações que ocorrerão no estado do programa quando as linhas de código desse ponto do programa forem executadas. Por isso, são as funções de transferência que calculam o estado de saída de um ponto do programa, baseadas no estado de entrada. Há também análises de fluxo de dados feitas no sentido inverno, nas quais as funções de transferência podem calcular o estado de entrada de um ponto no programa baseadas no estado de saída. Temos então para o programa um conjunto IN e um conjunto OUT, os quais guardarão todas as informações relevantes que quisermos. Para cada bloco básico B do programa, IN[B] e OUT[B] terão os valores que quisermos armazenar daquele bloco. Dessa forma, a função de transferência é responsável por determinar o conjunto OUT de cada bloco B. Num fluxo de dados para a frente, podemos denotar a função de transferência então como sendo:
Ou seja, a função de transferência, aplicada ao conjunto de valores de entrada de um bloco básico B, gera os valores de saída do bloco básico B. Já quando se trata de fluxo de controle, temos que as informações obtidas acerca de um ponto do programa propagam para os outros pontos do programa através de arestas que saem dele. Calculando o fluxo de controle, então, podemos definir que informações se encontram disponíveis no início de cada ponto do programa, e representamos esse fluxo de controle da seguinte forma:
Em outras palavras, as informações que estão disponíveis na entrada de um bloco básico B são calculadas com base na união de todas as informações que saem de todos os blocos básicos P que sejam predecessores de B.
48
A análise de fluxo de dados é feita encontrando-se a melhor solução para essas equações para cada bloco básico do programa. Há vários algoritmos para coletarmos informações do programa em questão, e a decisão de quais implementar depende exclusivamente de quais dados pretendemos obter. Para esse projeto foram implementados os algoritmos que determinam, para cada ponto no programa, quais definições alcançam aquele ponto e quais expressões estão disponíveis. Esses dois algoritmos são descritos a seguir. 5.4 Definições de alcance
É simples entender como funcionam as definições de alcance. Com a implementação desse algoritmo, conseguimos saber quais definições alcançam cada ponto no programa. Primeiramente, definição é toda atribuição realizada a alguma variável. Uma definição de uma variável ‘a’, por exemplo, alcança um ponto ‘p’ qualquer do programa se existe um caminho no grafo de fluxo de controle entre o ponto no programa onde a variável ‘a’ é definida e o início do ponto ‘p’, tal que a variável ‘a’ não seja morta nesse caminho. A variável ‘a’ será morta se houver uma outra definição dela ao longo do caminho para ‘p’. Essas definições de alcance são muito úteis, tanto para otimizadores de código como também para compiladores e depuradores. Nesse projeto, o algoritmo que determina as definições de alcance foi implementado, mais pela sua importância do que para alguma utilidade imediata. Tendo ele implementado, permite-nos realizar incrementos futuros no otimizador com mais facilidade. Na implementação realizada, toda instrução que altera o valor de algum registrador é considerada uma definição. Dessa forma, as seguintes instruções são as únicas que não geram definições: JMP, EQ, LT, LE, TEST, TAILCALL, RETURN e CLOSE. Por outro lado, as instruções SELF e FORLOOP geram 2 definições cada. A instrução LOADNIL gera B-A+1 definições, sendo que A e B são os 2 registradores usados na instrução. A instrução TFORLOOP gera C+1 definições, sendo que C é o segundo argumento da instrução. A instrução CALL gera C-1 definições, sendo que C é o terceiro argumento da instrução. Porém, a implementação define um valor máximo para C possuir, que está definido na constante NRO_MAX_RETORNOS_DINAMICOS. Algo semelhante ocorre com as instruções SETLIST e VARARG. A instrução SETLIST gera B definições, sendo B o segundo argumento da instrução, embora B possa ter no máximo o valor NRO_MAX_SET_DINAMICOS. Já a instrução VARARG gera B-1 definições, sendo 2 também o segundo argumento da instrução. E, da mesma forma que as
49
anteriores, B possui um teto especificado pela variável NRO_MAX_VARARG_DINAMICOS. Com essas informações, calcula-se, para cada bloco básico do programa, quais definições são geradas e quais são mortas por aquele bloco. Uma definição de qualquer variável ‘x’ num bloco qualquer B faz com que B gere a definição de ‘x’ e mate a definição de ‘x’ de qualquer outro bloco básico do programa. O mesmo vale para qualquer outra definição do programa em qualquer bloco básico. Dessa forma, cada bloco básico do programa possui um conjunto gen e um conjunto kill, que determinam quais variáveis são definidas naquele bloco e quais definições daquelas variáveis são mortas. O algoritmo de definições de alcance leva em consideração o conjunto gen e kill de cada bloco, pois essa é a função de transferência que será usada para calcular os conjuntos OUT de cada bloco, cujos serão depois usados para calcular os conjuntos IN, de forma iterativa. O algoritmo, em pseudo-código, pode ser visto abaixo:
1. OUT[ENTRY] = Ø; 2. for (cada bloco básico B diferente de ENTRY) OUT[B] = Ø; 3. while (mudanças ocorrem em qualquer OUT) 4. for (cada bloco básico B diferente de ENTRY){
5. ; 6. 7. }
Figura 5.1. Algoritmo de Definições de Alcance Nas duas primeiras linhas todos os blocos têm seus conjuntos OUT inicializados com o conjunto vazio. A idéia é que eles irão iterativamente convergir para a melhor solução do problema, mantendo o conservadorismo. O ‘for’ das linhas 4, 5, 6 e 7 percorre cada bloco do grafo, calcula um novo conjunto IN para ele com base nos OUT dos predecessores e depois calcula um novo OUT para ele, com base no conjunto de definições geradas e mortas do bloco. O conjunto OUT, no caso, será a união do conjunto de definições geradas e a diferença entre o conjunto IN do bloco e as definições mortas no bloco. Para a implementação, usou-se um vetor de bits para representar os conjuntos gen, kill, IN e OUT de cada bloco. Cada bloco básico do programa então possui 4 vetores de bits. O tamanho desse vetor é igual ao número de definições de alcance distintas de todo o programa, e cada posição nesse vetor representa então uma dessas definições. Dessa forma, fica muito simples calcular as operações de diferença e união do algoritmo. Nesses vetores, se uma definição é gerada num bloco básico, então o valor é posicionado para 1, caso contrário permanece 0. Já no conjunto kill, se uma definição é morta, o valor na posição do vetor referente à definição torna-se 1, e caso contrário é 0. Após a parada do algoritmo, temos os conjuntos IN e OUT de cada bloco bem definidos e se nossa intenção com a análise fluxo de dados for saber apenas quais
50
definições de variáveis alcançam cada ponto do programa, então nossa análise está pronta. Para esse projeto, foi implementado também outro algoritmo de análise de fluxo de dados, o de Expressões disponíveis.
5.5 Expressões disponíveis
Veremos agora como funciona o algoritmo de Expressões disponíveis, que foi bastante útil na implementação do projeto pois ele é essencial para que se realize a otimização de eliminação de subexpressões comuns. Uma expressão ‘e’ está disponível num ponto ‘p’ qualquer do programa se em todos os caminhos possíveis levando o fluxo de execução a ‘p’ a expressão ‘e’ seja atribuída a alguma variável, tal que após essa atribuição e antes do ponto ‘p’ nenhum dos fatores da expressão ‘e’ sejam alterados. Todos os blocos básicos que definirem uma variável atribuindo a ela a expressão ‘e’ estarão então gerando a expressão ‘e’. Qualquer atribuição subseqüente de qualquer variável pertencente à essa expressão irá matar a expressão. Cada bloco básico possui então outros dois conjuntos que geram e matam, que chamaremos aqui de e_gen e e_kill, para diferenciar dos anteriores. Na implementação realizada, haverá quase sempre menos expressões do que definições de variáveis. Apenas as seguintes instruções Lua podem gerar expressões: MOVE, GETUPVAL, GETGLOBAL, GETTABLE, ADD, SUB, MUL, DIV, MOD, POW, UNM, NOT e LEN. Apesar disso, todas aquelas instruções que podiam gerar definições de variáveis podem matar expressões. Ao contrário do algoritmo de Definições de alcance, aqui tratamos expressões iguais ocorrendo em pontos distintos do programa como sendo a mesma empressão, o que diminui ainda mais o número de expressões do programa. Um bloco básico que gera uma expressão acaba sempre matando as outras ocorrências daquela expressão no programa. Além disso, quando geramos uma expressão ‘e’ do tipo “x + y”, qualquer definição posterior da variável ‘x’ ou da variável ‘y’ mata a expressão ‘e’. Da mesma forma como o algoritmo de Definições de alcance, o algoritmo de Expressões disponíveis leva em consideração os conjuntos e_gen e e_kill para calcular o IN e OUT de cada bloco, e ambos foram implementados como vetores de bits, em que cada bit indica se uma expressão está ou não disponível, ou seja, viva. Esse algoritmo está representado em pseudo-código abaixo:
1. OUT[ENTRY] = Ø; 2. for (cada bloco básico B diferente de ENTRY) OUT[B] = U; 3. while (mudanças ocorrem em qualquer OUT)
51
4. for (cada bloco básico B diferente de ENTRY){
5. ;
6. 7. }
Figura 5.2. Algoritmo de Expressões Disponíveis Podemos perceber que esse algoritmo difere do anterior pois ele não inicializa os blocos básicos diferentes de ENTRY com o valor vazio para o conjunto OUT. Ele inicializa com o conjunto U, de universal, que na nossa implementação com vetores de bits corresponde a iniciar com todos os valores sendo 1. É dessa forma pois o algoritmo considera que no início do programa todas as expressões estão disponíveis, e a iteração entre os blocos irá moldando esses conjuntos OUT até que só restem realmente as expressões que estão disponíveis. Além disso, para o cálculo do conjunto IN dentro do for interior ele calcula a interseção dos conjuntos OUT dos blocos básicos predecessores, ao invés da união. Essa mudança ocorreu porque para uma expressão estar disponível na entrada de um bloco básico, ela deve estar disponível na saída de todos os blocos predecessores, o que faz com que a interseção entre os blocos predecessores seja a operação ideal para calcularmos isso.
5.6 Resumo
Implementando esses dois algoritmos usando esses vetores de bits, fazemos com que cada iteração seja muito rápida, pois para cada bloco básico fazemos apenas algumas uniões, diferenças e interseções entre conjuntos. Percorremos então cada bloco básico uma vez para cada iteração, fazendo o que o tempo de execução dependa do número de blocos e do número de iterações. Na prática, percebe-se que o número de iterações é 5, em média, dependendo da ordem em que os blocos são visitados [1]. Isso indica que a complexidade do algoritmo deve ser, em média, O(5n), ou O(n).
52
6. Implementação
Tendo os algoritmos de análise de fluxo de dados implementados, resta-nos utilizar os dados obtidos na análise para tirarmos conclusões a respeito do programa fonte e otimizá-lo. 6.1 Prós e Contras Veremos abaixo que Lua permite várias dessas otimizações e a maioria delas ainda não é realizada. O fato também de Lua possuir uma máquina virtual baseada em registradores e possuir apenas 38 opcodes diferentes é uma vantagem para o projeto. Por outro lado, como vimos anteriormente, cada versão da linguagem pode trazer alterações na máquina virtual, e isso faz com que um otimizador de tempo de compilação para Lua possa ter que ser alterado a cada nova versão da linguagem. 6.2 Oportunidades de otimização em Lua Ao fazermos uma pequena análise nos códigos intermediários gerados pelo compilador de Lua, podemos perceber que o compilador em si já realiza algumas pequenas otimizações. Um bom exemplo é a eliminação de código morto. Instruções Lua do tipo “if (false) print ...” são tratadas de forma diferente pelo compilador. Na geração do código intermediário, a instrução ‘if’ é apenas tratada como um jump para a linha imediatamente após o fim do ‘if’. Outra otimização realizada em tempo de compilação é o cômputo de expressões constantes, evitando trabalho desnecessário da máquina virtual. Instruções então do tipo ‘e = 1 + 5’ são sempre transformadas em instruções ‘e = 6’, por exemplo. Além disso, Lua realiza uma otimização especial com a instrução LOADNIL. Qualquer uso dessa instrução no início do programa é removido pelo compilador. Isso ocorre porque a máquina virtual já inicializa automaticamente com valor nulo no início do programa qualquer variável que for ser utilizada em todo o programa. Dessa forma, uma boa dica para programadores é declararem no início dos seus programas toda e qualquer variável que for ser usada em todo o programa. Isso faria com que o código intermediário do programa não tivesse nenhum uso da instrução LOADNIL. São então poucas otimizações que Lua arrisca-se em fazer, sempre atenta ao tempo de execução do compilador e da máquina virtual.
53
Dessa forma, a eliminação de subexpressões comuns, propagação de cópia, movimentações de código e redução de força são algumas das principais otimizações que poderiam ser feitas à linguagem. Decidiu-se implementar então a eliminação de subexpressões comuns e a propagação de cópia, já que ambas juntas conseguem realizar muitas das melhorias de código. A eliminação de subexpressões comuns geralmente gera comandos de cópia, que podem ser removidos posteriormente com a propagação de cópia. Pode ocorrer também da propagação de cópia permitir a ocorrência de novas subexpressões comuns, que poderiam novamente ser removidas com uma nova propagação de cópia. A quantidade de vezes que aplicamos as duas pode depender tanto do tempo de execução que achamos aceitável para o otimizador como também do quão relevante será cada nova aplicação dos algoritmos. Por exemplo, se cada aplicação dos dois algoritmos dura 50 milissegundos e queremos que o otimizador não demore mais de 200 milissegundos para realizar a otimização, então podemos permitir no máximo 2 passagens de cada um dos algoritmos. Por outro lado, supondo que uma primeira passagem dos dois algoritmos deixa o programa fonte 10% mais rápido e uma segunda passagem deixa em média apenas 0.05% mais rápido, pode não valer a pena passar os dois algoritmos duas vezes. Abaixo descrevemos a implementação de cada uma das otimizações. 6.3 Eliminação de Subexpressões comuns No algoritmo de eliminação de subexpressões comuns, primeiramente encontramos todas as subexpressões comuns existentes no programa. Para fazer isso, percorremos todos os blocos básicos e verificamos para cada um se existe alguma expressão que faça parte do conjunto IN e do conjunto e_gen daquele bloco. Em outras palavras, verificamos para cada bloco básico do programa se existe alguma expressão que está disponível naquele bloco e ainda assim é gerada por ele. A otimização que fazemos ao encontrarmos cada ocorrência de subexpressão comum é tentar substituí-la por uma instrução MOVE. Se num ponto ‘p’ o programa calcula a expressão ‘x + y’ e atribui seu valor à variável ‘a’, se num ponto ‘q’ posterior a expressão ‘x + y’ estiver disponível e estiver sendo recalculada e atribuída a uma variável ‘b’, o otimizador pode substituir o segundo cálculo da expressão por uma instrução MOVE que copie o valor de ‘a’ para ‘b’. Essa é a forma mais comum de remover o cálculo repetitivo da expressão ‘x + y’. Porém, o caso abaixo pode ocorrer:
54
Figura 6.1. Caso especial de ocorrência de subexpressões comuns
Ou seja, uma expressão é calculada em blocos básicos diferentes, que não se conectam por nenhum caminho, e variáveis diferentes recebem os valores calculados da expressão. Nesse caso, no bloco básico Bn+2 não podemos simplesmente substituir a expressão ‘c = x + y’ pelo valor de ‘a’ ou de ‘b’. Nesse caso, a solução mais adequada seria a seguinte:
Figura 6.2. Solução para caso especial de subexpressões comuns
Assim, criaríamos uma nova variável temporária ‘t’ que guardaria o valor da expressão e no bloco Bn+2 substituiríamos a instrução ‘c = x + y’ pela cópia ‘c = t’. Porém, devemos ter cuidado com a adição de novas instruções no programa. Perceba que agora em qualquer que seja o fluxo de execução do programa, serão executadas 3 instruções, e não mais 2. Em vez de duas adições, agora fazemos uma adição e duas cópias. Sem uma subseqüente propagação de cópia, em algumas linguagens essa otimização não seria válida. Em Lua mesmo sem a propagação de cópia talvez a otimização fosse válida, já que a instrução MOVE apenas copia valores de um registrador para outro, enquanto a
55
instrução ADD basicamente verifica se os argumentos são números, faz algumas outras chamadas de função e por fim realiza a operação de adição. Mesmo assim, isso pode não continuar sendo verdade para as próximas versões da linguagem, então não podemos assumir que essa otimização sozinha sempre será válida. Com a propagação de cópia, entretanto, a instrução ‘c = t’ poderia ser removida, e então seria como se apenas substituíssemos a instrução ADD por uma MOVE. Resumindo, o algoritmo então encontra as ocorrências de subexpressões comuns em cada bloco, descobre qual o último registrador que foi definido com aquela expressão e substitui o segundo cálculo da expressão por uma cópia entre os dois registradores destinos das duas ocorrências da expressão. Caso a expressão possa ter mais de um registrador possível guardando seu valor atual, uma nova variável é criada, o valor de cada registrador é copiado para ela nos diferentes fluxos em que a expressão ocorre e a ocorrência da subexpressão comum é novamente substituída por uma cópia, dessa vez da variável temporária para o último registrador destino. 6.4 Propagação de cópia A propagação de cópia em Lua deve ser feita com um cuidado muito especial. Como a máquina virtual é baseada em registradores, várias instruções mexem com mais de 3 registradores, e para que os registradores em uso sejam especificados, as instruções definem intervalos na lista de registradores nos quais todos os registradores naquele intervalo são usados na instrução. O melhor exemplo que podemos citar é o da instrução CALL. Ela utiliza apenas 3 registradores, mas executa a chamada de uma função, e especifica quais são os argumentos que essa função receberá e quais os valores de retorno dela. O registrador A da instrução especifica qual função deverá ser chamada, e os registradores de A+1 até A+B-1 especificam quais argumentos serão passados para a função. Isso significa que todos os argumentos que quisermos que a função receba devem estar dispostos entre A+1 e A+B-1. Nem sempre os valores que queremos passar para a função já se encontram nesses registradores desde o início, o que faz com que o compilador de Lua tenha que gerar instruções MOVE que passem esses valores para os registradores certos, antes da função ser chamada. Essas cópias antes das instruções CALL também podem aparecer antes ou depois das instruções CONCAT, RETURN, TAILCALL, VARARG e SETLIST. E embora sejam instruções de cópia, não podemos removê-las na propagação de cópias, já que elas são necessárias para as instruções acima funcionarem corretamente. O primeiro passo então antes de executarmos a propagação de cópias é marcar todas as cópias que são necessárias e não permitir que elas sejam removidas. Feito isso, o algoritmo deve percorrer os caminhos subseqüentes a todo comando de cópia do tipo
56
‘a = b’, trocando os usos da variável ‘a’ pelo da variável ‘b’, até o final do programa, ou até que ‘a’ ou ‘b’ sejam redefinidas. Então, se todos os usos de ‘a’ puderam ser substituídos por usos de ‘b’, então a variável ‘a’ não é mais necessária e a instrução ‘a = b’ pode ser removida.
57
7. Testes
Alguns pequenos scripts em Lua foram otimizados e seu tempo de execução foi analisado. Para analisar o tempo de execução, usou-se a função clock() da biblioteca de sistema operacional da linguagem Lua. Através de uma chamada dessa função no início do programa e também no fim do programa, calculamos quanto tempo se passou durante a execução do programa. Para que essa análise fosse o mais próximo possível do real, buscou-se executar os scripts Lua sem nenhum uso adicional da CPU durante a execução, ou seja, permitindo que a CPU trabalhasse apenas na execução do programa Lua. No total, quatro programas foram otimizados. O primeiro foi criado especialmente para esse projeto, e seu código fonte pode ser visto abaixo. Os outros 3 já vêm com a implementação da linguagem, no diretório test, embora tenham sido levemente modificados para a realização desses testes. Eles são responsáveis por testar conversão de temporatura de graus Celsius para Fahrenheit, testar utilização de tabelas e testar um for com funções geradoras. 7.1 Testes realizados Abaixo está o programa em Lua criado exclusivamente para o projeto. Ele foi compilado e otimizado para testar o otimizador. Abaixo está o código do programa na linguagem fonte: local a, b, c, d, e, f, g, h, i, j, k, l; b = 6 c = 5 e = 7 f = 0 g = 1 a = b + c d = e + a c = f + g if (a + d) then h = b + c j = f + g else h = b + c j = f + g end l = b + c k = f + g if (l + k) then i = l + i else i = l + i
58
end g = l + i a = k + g if (g + a) then k = k + g end b = l + i a = k + g
Figura 7.1. Programa em Lua criado para realizar testes Agora veremos o desempenho do otimizador ao eliminar subexpressões comuns e realizar a propagação de cópia. Todas as expressões são adições, para efeito de simplicidade. Nenhum laço foi criado, apenas instruções de desvio. Além disso, todas as variáveis usadas são locais. Abaixo está o programa em código intermediário de Lua, já compilado pelo compilador luac:
Figura 7.2. Programa em bytecode Lua criado para realizar testes
Passando o código acima no otimizador de código, ele encontra 5 ocorrências de subexpressões comuns. Primeiramente, as instruções das linhas 13, 16 e 18 já são
59
calculadas na linha 8, e o valor da subexpressão está guardado no registrador 2. Por outro lado, as linhas 12 e 15 não recalculam o mesmo valor calculado na linha 6, já que o registrador 2 é redefinido na linha 8. A linha 17, porém, recalcula o mesmo valor calculado nas linhas 12 e 15, constituindo outra subexpressão comum. As linhas 22 e 24 e a linha 30 não geram nenhuma expressão, pois definem o registrador 8 e o registrador 10 respectivamente, ao mesmo tempo que os utilizam. As instruções das linhas 25 e 32, porém, utilizam os registradores 8 e 10, mas guardam os resultados das expressões nos registradores 6 e 0. Essa subexpressão da linha 25, inclusive, é recalculada na linha 31, caracterizando a última subexpressão comum. 7.2 Ganho da Eliminação de Subexpressões comuns Abaixo temos o programa da figura 7.2 após sofrer a otimização da eliminação de subexpressões comuns:
Figura 7.3. Programa em bytecode Lua sem subexpressões comuns
60
Toda alteração feita pelo otimizador está em negrito no código acima. As 5 ocorrências de subexpressões comuns descritas acima foram substituídas por instruções MOVE. As instruções das linhas 13, 16 e 18 apenas pegaram o valor que já estava calculado no registrador 2. A instrução da linha 17 pegou o valor calculado nas linhas 12 ou 15 e colocado no registrador 7. Por fim, a instrução da linha 31 pegou o valor que já estava no registrador 6 e não precisou recalcular a subexpressão da linha 25. Dessa forma, o programa deixou de calcular 5 adições e passou a realizar 5 novas cópias, que são de fato mais baratas. Para uma otimização completa, porém, falta realizar a propagação de cópia. 7.3 Ganho da Propagação de cópia Temos abaixo o resultado obtido com o otimizador após a propagação de cópia:
Figura 7.4. Programa em bytecode Lua após propagação de cópia
Acima estão em negrito as 7 instruções que foram alteradas pela propagação de cópia. Um espaço em branco foi deixado no lugar as instruções que foram removidas, que contabilizam 5.
61
As instruções das linhas 11 e 14 apenas foram alteradas pois o número de instruções do programa diminuiu e seus jumps precisaram ser ajustados. Já as 5 instruções ADD subseqüentes foram alteradas para usarem os valores armazenados nos registradores 2 e 7 ao invés de usarem os registradores 10 e 11. Todos os usos dos registradores 9, 10, 11 após a ex linha 18 puderam ser substituídos pelos registradores 2 e 7, e portanto as instruções MOVE das linhas 13, 16, 17 e 18 puderam ser removidas. Por fim, nenhum uso era feito do registrador 1 após a linha 31, então a instrução MOVE da linha 31 também foi eliminada. Consideramos que o resultado obtido foi bastante favorável, já que o programa resultante executa 5 instruções a menos que o original, uma redução de 15% nesse exemplo em específico. 7.4 Ganho em desempenho Apesar da redução do número de instruções calculadas e da complexidade de execução dessas instruções, essas informações são insuficientes. É necessário vermos se a execução do programa otimizado de fato é mais rápida. Nos quatro programas que foram otimizados, então, foi analisado também o desempenho. Como resultado, percebemos que o otimizador deixou os programas cerca de 25% mais rápidos. Por exemplo, o conversor de graus Celsius para Fahrenheit leva 0.24 segundos para executar sem otimização e 0.18 com otimização. O exemplo que apresentou a maior melhora foi aquele criado exclusivamente para o projeto, que sem otimização executava em 1.283 segundos e com otimização passou a executar em 0.86 segundos, que representa uma melhora de 33%. Em média, porém, os valores ficaram em cerca de 25%. Embora esses valores serão aproximados, já que os testes foram realizados num computador convencional, podemos perceber que de fato o otimizador consegue melhorar o número de instruções e o tempo de execução dos programas.
62
8. Conclusão
Estudar a fundo a implementação de uma linguagem de programação, desde seu compilador até sua máquina, foi um aprendizado valioso. Lua, por si só, mostrou-se incrivelmente desafiadora, pela sua implementação leve, compacta, simples e ainda assim muito poderosa. Na outra extremidade, muitos conceitos, ferramentas e algoritmos de otimização de código que antes eram conhecidos de forma superficial foram muito aprofundados na realização desse projeto. Embora difíceis de compreender no início, todos os conceitos e algoritmos hoje já são bastante dominados. Realizar otimizações de código numa linguagem já leve e rápida foi um desafio enorme, porém, percebeu-se que várias otimizações podem ser feitas e os resultados obtidos são bastante animadores. A sintaxe e a semântica da linguagem Lua já eliminam a possibilidade de várias otimizações em tempo de compilação, e outras o próprio compilador já executa, porém otimizações muito importantes como a eliminação de subexpressões comuns e a propagação de cópia não são realizadas na linguagem. Nos testes realizados, pode-se notar que vários recálculos de expressões são substituídos por instruções mais baratas, como as de cópia. Além disso, várias instruções puderam ser removidas, diminuindo o número de instruções executadas pelos programas. Dessa forma, garantimos que o programa usa menos recursos e leva um tempo menor para executar. Todas essas otimizações são ideais para desenvolvedores que compilam seus programas para executá-los posteriormente, e dessa forma o tempo que o otimizador leva para realizar as otimizações e também os recursos que ele utiliza não são tão cruciais. Ainda assim, para um programa em código intermediário de Lua com 33 linhas de código, o otimizador levou menos de 100 milissegundos para executar.
63
Referências bibliográficas
[1] AHO, A. V.; LAM, M. S.; SETHI, R.; ULLMAN, J. D. Compiladores – Princípios, técnicas e ferramentas. São Paulo: Pearson Addison-Wesley, 2008
[2] IERUSALIMSCHY, R; DE FIGUEIREDO, L. H.; CELES, W. (2005). The Implementation of Lua 5.0. Journal of Universal Computer Science, v.11, p.1159-1176, 2005.
[3] GLASBERG, M. S.; BRESLER, J.; CHO, Y. The Lua Architecture. Advanced Topics in Software Engineering.
[4] MAN, K. A No-Frills Introduction to Lua 5 VM Instructions (2006).
[5] IERUSALIMSCHY, R; DE FIGUEIREDO, L. H.; CELES, W. (2007). The Evolution of Lua. Proceedings of the third ACM SIGPLAN conference on History of programming languages, San Diego, California, p.2-1 – 2-26, 2007.
[6] JUNG, K.; BROWN, A. Beginning Lua Programming. Indianapolis, Indiana: Wiley Publishing, Inc., 2007
[7] SHI, Y.; CASEY, K.; ERTL, M. A.; GREGG, D. (2008). Virtual Machine Showdown: Stack Versus Registers. ACM Transactions on Architecture and Code Optimization, p.21-1 – 21-36, 2008.
[8] CYTRON, R.; FERRANTE, J.; ROSEN, B. K.; WEGMAN, M. N.; ZADECK, F. K. (1991). Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, p. 451-490, 1991.
64
Apêndice A - Artigo
65
Um estudo sobre possíveis técnicas de otimização de código para bytecode Lua
Alex de M. Machado1
1Departamento de Informática e Estatística – Universidade Federal de Santa Catarina (UFSC)
Caixa Postal 476 – 88.040-900 – Florianópolis – SC – Brazil
Abstract. Nowadays compilers should always perform code optimizations, because it is essential that the compilers not only perform their basic functions, but also generate code as efficiently and effectively as an excellent programmer of low-level languages. This work presents a study on possible optimizations for Lua. Besides the lack of optimizations of the language implementation, it was noted also that these optimizations are very inexpensive when applied to precompiled code and actually improve the performance of programs. Resumo. Hoje em dia os compiladores devem sempre contar com otimizações de código, pois é imprescindível que um compilador não apenas realize suas funções básicas, mas também gere um código tão eficiente, e eficaz, quanto um exímio programador de linguagens de baixo nível. Este trabalho apresenta um estudo feito sobre as possíveis otimizações para a linguagem Lua. Além de notar-se uma carência da linguagem a respeito dessas otimizações, percebeu-se também que essas otimizações são muito baratas quando aplicadas a código pré-compilado e realmente melhoram o desempenho dos programas.
1. Introdução Tanto os programadores quanto os próprios compiladores acabam criando oportunidades de otimização de código. Os programadores o fazem às vezes por descuido, e às vezes propositalmente, mas os compiladores o fazem involuntariamente, em conseqüência do processo de tradução de uma forma de representação para outra que geralmente é completamente diferente.
Lua, particularmente, é uma linguagem que na sua implementação oficial não executa muitas otimizações de código durante a compilação, por possuir requisitos de projeto que exigiam um compilador compacto e rápido. Propõe-se então tanto estudar quais otimizações seriam interessantes implementar para a linguagem, como também realizar essa implementação de algoritmos de otimização de código ao código intermediário gerado pelo compilador de Lua.
Um otimizador de código para Lua iria prejudicar os requisitos básicos do projeto da linguagem? Que otimizações são as mais importantes? Qual o aumento de desempenho que essas otimizações possibilitam? Esse aumento de desempenho compensa o tempo gasto realizando as otimizações? Essas são algumas das perguntas que se tentou responder durante o estudo realizado.
66
2. A linguagem Lua Lua é uma linguagem de programação criada inicialmente em 1993 pelo Computer Graphics Technology Group, da Pontifícia Universidade Católica do Rio de Janeiro, para uso interno no desenvolvimento de software [Ierusalimschy et al. 2007]. Seu uso tem crescido constantemente desde então graças provavelmente aos seus objetivos iniciais: ter uma linguagem de script embarcável que possa ser acoplada a sistemas maiores, que seja simples, eficiente, portável e também leve [Ierusalimschy et al. 2005].
A implementação de Lua consiste de uma pequena biblioteca de funções ANSI C que compila de forma igual para todas as plataformas. O código base está bem dividido em módulos como o compilador, o interpretador e a máquina virtual [Glasberg et al.].
Lua é uma linguagem de scripts, interpretada, dinâmica, imperativa, multiparadigma e executa sobre uma máquina virtual portátil. Além disso, ela é leve, simples e rápida.
3. Principais qualidades Embora projetada inicialmente para estender aplicações com objetivo de ter bom desempenho, ser portável e extensível, a evolução de Lua fez com que seus projetistas logo buscassem também fazer de Lua uma linguagem simples e compacta.
Para cumprir esse objetivo, buscou-se a linguagem mais simples possível, implementada com o código C mais simples possível. Isso foi obtido ao se construir uma linguagem com uma sintaxe muito simples, poucas construções de linguagem e um número reduzido de tipos de dados. Lua possui apenas 8 tipos de dados.
Como desde o início Lua iria ter que mexer com uma grande quantidade de dados, o projeto da linguagem também sempre buscou uma linguagem que fosse rápida. Para isso, ela precisaria compilar o código rapidamente, e executá-lo também rapidamente. A solução foi criar um compilador de um passo que fosse rápido e inteligente, além de uma máquina virtual também rápida. Por exemplo, a máquina virtual atualmente suporta apenas 38 opcodes diferentes, enquanto a máquina virtual de Java suporta 256.
Todas as instruções da máquina virtual de Lua podem ser de apenas 3 formatos diferentes. Além disso, ela foi projetada de uma forma mais eficiente que as máquinas virtuais habituais, utilizando uma abordagem baseada em registradores, não em pilha. Essa abordagem trouxe benefícios como número reduzido de instruções expedidas, redução no número de erros em predição de branches e também redução no número de instruções da máquina real no nível da CPU [Shi et al. 2008].
Era um requisito inicial também de Lua a portabilidade, e se tornou interessante manter essa característica na linguagem posteriormente. Para isso, o núcleo da linguagem precisou ser desenvolvido de uma forma que pudesse ser compilado igualmente em qualquer lugar e executasse programas em Lua da mesma forma em qualquer plataforma que suportasse o interpretador de Lua. Como o núcleo é escrito em C, esse código precisou ser escrito com cuidado, dando bastante atenção a problemas com portabilidade de C e de suas bibliotecas.
Por fim, para que programas em Lua pudessem ser acoplados a programas maiores, era essencial que houvesse uma fácil comunicação entre eles. Para isso desenvolveu-se uma API de
67
C simples e poderosa. Além disso, não deveria ser caro para os desenvolvedores do projeto embarcarem programas em Lua. Para isso, o núcleo da linguagem precisou ser muito compacto.
Alguns desses objetivos de projeto da linguagem são conflitantes. Para o código executar rapidamente, o compilador deve ser inteligente e criar código bom, mas não adianta o código ser rápido se o próprio compilador é lento, o que faz com que o compilador também precise ser rápido. Por outro lado, para a linguagem ser compacta, o compilador deve ser pequeno. O compilador criado então busca um equilíbrio entre todos esses requisitos [Ierusalimschy et al. 2005]. E para aplicações que possuem recursos de memória reduzidos, é possível acoplar o núcleo de Lua sem o compilador. Os arquivos em Lua são então pré-compilados e na hora da execução são apenas carregados por um módulo reduzido.
4. Bytecode pré-compilado Como Lua é executada por uma máquina virtual, ela possui uma representação de código intermediário, chamada bytecode, que é reconhecido pela máquina virtual, a qual em tempo de execução traduz esse código para o código binário da máquina alvo.
Uma característica peculiar da linguagem é que ela permite que o usuário pré-compile um programa em Lua, e não o execute, e sim salve seu código pré-compilado em alguma mídia não volátil. Esse código bytecode salvo pode então ser executado posteriormente, num momento oportuno, ou então transferido para outro sistema, como um sistema embarcado.
Durante esse tempo que esse código fica salvo numa mídia não volátil, ele pode ser carregado por algum possível otimizador de código, que alteraria seu código e salvaria o arquivo novamente numa mídia não volátil. Isso faria com que o otimizador não influenciasse de forma alguma no tempo de execução do programa, e apenas adicionasse uma etapa a mais na compilação.
5. Otimizações de código Abaixo descreveremos agora quais as otimizações de código foram estudadas. Foram estudadas apenas otimizações independentes de máquina.
Desejava-se criar otimizações para instruções na forma SSA com utilização de um grafo de fluxo de controle, pelo sucesso já obtido em outros trabalhos. Além disso, essas otimizações abaixo são otimizações que em sua maioria são beneficiadas pela utilização de um grafo de fluxo de controle e instruções na forma SSA [Cytron et al. 1991].
O programa abaixo será usado como exemplo para mostrarmos as otimizações estudadas de forma mais transparente.
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
68
local a,b
c = 9
function x()
return 2/2
end
e = c + x()
while i < 12 do
j = 2 ^ i
if powerTwo[i] == j then
print(powerTwo[i] == j)
print(powerTwo[i])
end
i = i + 1
y = 2 * i
a = 2
b = a - 2
d = c + e
end
if false then
j = 0
end
i = c + e
print(i)
print(y)
return b
Figura 1. Programa em Lua não otimizado
5.1. Eliminação de subexpressões comuns Uma ocorrência de uma expressão E é chamada de subexpressão comum se E tiver sido computada anteriormente e os valores das variáveis em E não tiverem mudado desde a computação anterior [Aho et al. 2008]. Dessa forma, se calculamos E num momento,
69
não precisaremos recalculá-la enquanto os valores das variáveis nela não mudarem, pois se o fizéssemos obteríamos novamente o mesmo resultado.
5.2. Propagação de cópia As instruções de cópia são criadas naturalmente por algoritmos de otimização, porém são desnecessárias. Instruções de cópia são instruções na forma “a = b”, em que o valor de uma variável é simplesmente copiado para outra variável. A idéia dessa otimização é substituir a variável “a” pela variável “b” nas instruções subseqüentes. Essa transformação pode não parecer muito útil, mas, como veremos a seguir, ela cria código morto no programa, que pode ser posteriormente eliminado por uma outra otimização que veremos.
5.3. Desdobramento de constante Uma otimização semelhante à Propagação de cópia é o Desdobramento de constante. Se por acaso descobrirmos que o valor de uma expressão é constante, podemos substituir o uso dessa expressão pela constante.
Ao analisarmos se uma expressão é constante ou não, não consideramos como constante as expressões que dependem de alguma forma do retorno de alguma função. Fazemos isso para não sobrecarregar tanto o otimizador, e manter seus algoritmos mas simples.
Poderíamos, porém, realizar uma análise mais detalhada e verificar quais os possíveis valores de retorno para a função. Se por acaso constatássemos que ela retornará sempre o mesmo valor para o contexto atual do programa, então toda expressão que depende apenas daquela função também poderia ser tratada como constante.
5.4. Eliminação de código morto Uma variável estará viva em algum ponto de um programa se seu valor puder ser usado posteriormente [Aho et al. 2008]. Caso contrário, ela está morta nesse ponto. Uma idéia relacionada é o código morto (ou inútil). Um código estará morto quando ele não possuir utilidade, e sua exclusão não afetar em absolutamente nada a semântica do programa. Embora esse código possa já estar presente no início da compilação, ele é geralmente criado como resultado de outras otimizações. Com a propagação de cópia e o desdobramento de constante várias ocorrências de código morto aparecem.
5.5. Movimentação de código Esse tipo de otimização é especial para laços internos. É muito interessante diminuir a quantidade de instruções num laço interno, mesmo que isso aumente o número de instruções fora do laço [Aho et al. 2008]. Uma modificação importante é a movimentação de código. Nesse caso, movimenta-se o código invariante do laço.
70
A razão para isso é simples: espera-se que as instruções dentro do laço sejam executadas inúmeras vezes, repetidamente, enquanto as instruções fora do laço são executadas apenas uma vez. Dessa forma, se pudermos retirar pelo menos uma instrução de dentro de um laço, já estaremos atingindo uma grande melhora no desempenho.
5.6. Variáveis de indução Uma variável ‘x’ é considerada uma “variável de indução” se houver uma constante positiva ou negativa ‘c’ tal que, toda vez que ‘x’ for atribuído, seu valor aumenta de acordo com ‘c’ [Aho et al. 2008]. É importante otimizar o cálculo de variáveis de indução, substituindo um conjunto de subexpressões por outro com menos instruções, ou de menor custo. Uma técnica é a redução de força, mas não é a única.
5.7. Considerações Abaixo podemos observar o programa da figura 1 com as otimizações citadas.
local powerTwo = {[0] = 1, [1] = 2, [2] = 4, [3] = 8, [4] = 16, [5] = 32, [6] = 64, [7] = 128, [8] = 256, [9] = 512, [10] = 1024, [11] = 2048}
local i = 0
local j,y
function x()
return 1
end
d = 18 + x()
while i < 12 do
j = 2 ^ i
temp1 = powerTwo[i]
temp2 = temp1 == j
if temp2 then
print(temp2)
print(temp1)
end
i = i + 1
y = y + 2
71
end
print(d)
print(y)
return 0
Figura 2. Programa em Lua otimizado manualmente
Um programa que contemple essas otimizações executará significativamente menos instruções, e instruções mais baratas, como podemos observar no código acima. Embora apenas em raras exceções se obtenha de fato um código ótimo, as técnicas conhecidas de otimização de código são capazes de melhorar inúmeros fatores do código otimizado, seja seu tempo de execução ou mesmo o espaço ocupado.
Apesar de serem importantes, as otimizações possíveis dependem muito da natureza da linguagem de programação, fazendo com que otimizar o código de uma linguagem seja um grande desafio. Deve-se levar em conta não só quais otimizações são possíveis, como também como realizar cada uma e quais cuidados tomar.
Ao executar as otimizações acima, devemos ser extremamente conservadores, como vimos anteriormente ao não considerarmos o retorno de uma função como constante por não termos certeza de todos os valores possíveis de retorno. O maior cuidado ao se realizar otimizações deve ser sempre manter a semântica do programa.
Todas as otimizações devem alterar o código do programa, mas aquilo que o programa faz deve ser mantido à risca. Isso faz com que não se possa realizar nenhuma otimização que não se tenha a certeza de que não irá afetar a semântica do programa.
6. Prós e Contras do projeto Das otimizações de código citadas acima, a implementação atual da linguagem Lua executa apenas o Desdobramento de constant e a Eliminação de código morto. Isso faz com que um otimizador de código possa realizar várias otimizações.
Dois outros fatores que favorecem a implementação do otimizador de código é o fato da máquina virtual ser baseada em registradores e o fato da máquina virtual reconhecer apenas 38 opcodes diferentes. Esses fatores são uma vantagem porque permitem que o otimizador de código compreenda o que o programa realiza com muito mais facilidade.
Como desvantagem para o projeto, porém, pode-se citar o fato de o otimizador trabalhar exclusivamente com conceitos da máquina virtual de Lua, e a equipe de desenvolvimento da linguagem não garante compatibilidade entre versões diferentes da máquina virtual. Isso faria com que cada nova versão da máquina virtual exigisse alterações no otimizador de código.
O projeto do otimizador de código em si foi realizado todo em C, para ser compatível com a implementação de Lua. O tempo de execução analisado para o otimizador foi de cerca de 30 milissegundos para programas bem pequenos e cerca de 200 milissegundos para programas em Lua na casa de 1000 linhas de código. O programa no total ficou com cerca de 3500 linhas de código, embora boa parte delas deva-se ao fato do otimizador não estar acoplado ao compilador de Lua.
72
7. Análise de Fluxo de Dados A forma como todas essas otimizações vistas são realizadas é simples. O otimizador de código varre todo o código já compilado para código intermediário e, para cada ponto do programa, ele coleta informações diversas a respeito do estado do programa naquele momento. Essas informações podem ser de qualquer natureza, pois o otimizador pega qualquer informação que for útil para entender o comportamento do programa.
Por exemplo, sabendo que em um ponto do programa uma variável é definida e que ela não é usada em nenhum outro ponto posterior do programa, podemos concluir que essa variável não é utilizada pelo programa, e podemos então excluir sua definição, diminuindo o número de instruções do programa e possivelmente também o quanto de memória ele usará.
Há uma série de algoritmos existentes que permitem que um programa otimizador percorra cada ponto de um programa e colete informações a seu respeito. O conjunto de todos esses algoritmos constitui a análise de fluxo de dados. É analisando todo o fluxo de dados de um programa que podemos compreendê-lo, tirar conclusões a seu respeito e finalmente modificá-lo.
As análises de fluxo de dados utilizam duas táticas para tirar conclusões acerca de um programa: as funções de transferência e o fluxo de controle. Todas as informações que coletamos servem para determinarmos todas as funções de transferência e os fluxos de controle do programa.
Com as funções de transferência de um ponto do programa, temos as alterações que ocorrerão no estado do programa quando as linhas de código desse ponto do programa forem executadas. Por isso, são as funções de transferência que calculam o estado de saída de um ponto do programa, baseadas no estado de entrada. Há também análises de fluxo de dados feitas no sentido inverno, nas quais as funções de transferência podem calcular o estado de entrada de um ponto no programa baseadas no estado de saída.
A análise de fluxo de dados é feita encontrando-se a melhor solução para as equações de fluxo de dados. Há vários algoritmos para coletarmos informações do programa em questão, e a decisão de quais implementar depende exclusivamente de quais dados pretendemos obter. Para esse projeto foram implementados os algoritmos que determinam, para cada ponto no programa, quais definições alcançam aquele ponto e quais expressões estão disponíveis. Esses dois algoritmos são descritos a seguir.
7.1. Definições de alcance É simples entender como funcionam as definições de alcance. Com a implementação desse algoritmo, conseguimos saber quais definições alcançam cada ponto no programa.
Primeiramente, definição é toda atribuição realizada a alguma variável. Uma definição de uma variável ‘a’, por exemplo, alcança um ponto ‘p’ qualquer do programa se existe um caminho no grafo de fluxo de controle entre o ponto no programa onde a variável ‘a’ é definida e o início do ponto ‘p’, tal que a variável ‘a’ não seja morta nesse caminho. A variável ‘a’ será morta se houver uma outra definição dela ao longo do caminho para ‘p’.
Essas definições de alcance são muito úteis, tanto para otimizadores de código como também para compiladores e depuradores. Nesse projeto, o algoritmo que determina as
73
definições de alcance foi implementado, mais pela sua importância do que para alguma utilidade imediata. Tendo ele implementado, permite-nos realizar incrementos futuros no otimizador com mais facilidade.
7.2. Expressões disponíveis Veremos agora como funciona o algoritmo de Expressões disponíveis, que foi bastante útil na implementação do projeto pois ele é essencial para que se realize a otimização de eliminação de subexpressões comuns.
Uma expressão ‘e’ está disponível num ponto ‘p’ qualquer do programa se em todos os caminhos possíveis levando o fluxo de execução a ‘p’ a expressão ‘e’ seja atribuída a alguma variável, tal que após essa atribuição e antes do ponto ‘p’ nenhum dos fatores da expressão ‘e’ sejam alterados.
Todos os blocos básicos que definirem uma variável atribuindo a ela a expressão ‘e’ estarão então gerando a expressão ‘e’. Qualquer atribuição subseqüente de qualquer variável pertencente à essa expressão irá matar a expressão.
7.3. Eficiência dos algoritmos Implementando esses dois algoritmos de forma iterativa e usando vetores de bits nós fazemos com que cada iteração seja muito rápida, pois para cada bloco básico fazemos apenas algumas uniões, diferenças e interseções entre conjuntos. Percorremos então cada bloco básico uma vez para cada iteração, fazendo o que o tempo de execução dependa do número de blocos e do número de iterações.
Na prática, percebe-se que o número de iterações é 5, em média, dependendo da ordem em que os blocos são visitados [Aho et al. 2008]. Isso indica que a complexidade do algoritmo deve ser, em média, O(5n), ou O(n).
8. Implementação Tendo os algoritmos de análise de fluxo de dados implementados, resta-nos utilizar os dados obtidos na análise para tirarmos conclusões a respeito do programa fonte e otimizá-lo.
Decidiu-se implementar então a eliminação de subexpressões comuns, a propagação de cópia e a eliminação de código morto.
A eliminação de subexpressões comuns geralmente gera comandos de cópia, que podem ser removidos posteriormente com a propagação de cópia. Pode ocorrer também da propagação de cópia permitir a ocorrência de novas subexpressões comuns, que poderiam novamente ser removidas com uma nova propagação de cópia. A quantidade de vezes que aplicamos as duas pode depender tanto do tempo de execução que achamos aceitável para o otimizador como também do quão relevante será cada nova aplicação dos algoritmos.
Por exemplo, se cada aplicação dos dois algoritmos dura 50 milissegundos e queremos que o otimizador não demore mais de 200 milissegundos para realizar a otimização, então podemos permitir no máximo 2 passagens de cada um dos algoritmos.
74
Por outro lado, supondo que uma primeira passagem dos dois algoritmos deixa o programa fonte 10% mais rápido e uma segunda passagem deixa em média apenas 0.05% mais rápido, pode não valer a pena passar os dois algoritmos duas vezes.
Por fim, podemos executar o algoritmo de eliminação de código morto novamente, pois tanto a eliminação de subexpressões comuns como a propagação de cópia podem fazer surgir código morto no programa.
8.1. Eliminação de subexpressões comuns No algoritmo de eliminação de subexpressões comuns, primeiramente encontramos todas as subexpressões comuns existentes no programa. Para fazer isso, verificamos para cada bloco básico do programa se existe alguma expressão que está disponível naquele bloco e ainda assim é gerada por ele.
A otimização que fazemos ao encontrarmos cada ocorrência de subexpressão comum é tentar substituí-la por uma instrução de cópia. Se num ponto ‘p’ o programa calcula a expressão ‘x + y’ e atribui seu valor à variável ‘a’, se num ponto ‘q’ posterior a expressão ‘x + y’ estiver disponível e estiver sendo recalculada e atribuída a uma variável ‘b’, o otimizador pode substituir o segundo cálculo da expressão por uma instrução de cópia que copie o valor de ‘a’ para ‘b’.
8.2. Propagação de cópia e eliminação de código morto A execução do algoritmo de propagação de cópia e eliminação subsequente de código morto é simples. O algoritmo deve percorrer os caminhos subseqüentes a todo comando de cópia do tipo ‘a = b’, trocando os usos da variável ‘a’ pelo da variável ‘b’, até o final do programa, ou até que ‘a’ ou ‘b’ sejam redefinidas. Então, se todos os usos de ‘a’ puderam ser substituídos por usos de ‘b’, então a variável ‘a’ não é mais necessária e a instrução ‘a = b’ pode ser removida pela eliminação de código morto.
9. Testes Alguns pequenos scripts em Lua foram otimizados e seu tempo de execução foi analisado. Para analisar o tempo de execução, usou-se a função clock() da biblioteca de sistema operacional da linguagem Lua. Através de uma chamada dessa função no início do programa e também no fim do programa, calculamos quanto tempo se passou durante a execução do programa. Para que essa análise fosse o mais próximo possível do real, buscou-se executar os scripts Lua sem nenhum uso adicional da CPU durante a execução, ou seja, permitindo que a CPU trabalhasse apenas na execução do programa Lua.
No total, quatro programas foram otimizados. O primeiro foi criado especialmente para esse projeto. Os outros 3 já vêm com a implementação da linguagem, no diretório test, embora tenham sido levemente modificados para a realização desses testes. Eles são responsáveis por testar conversão de temporatura de graus Celsius para Fahrenheit, testar utilização de tabelas e testar um for com funções geradoras.
Após as otimizações, pudemos perceber uma redução do número de instruções calculadas e da complexidade de execução dessas instruções. Além disso, nos quatro programas que foram otimizados, então, foi analisado também o desempenho. Como resultado, percebemos
75
que o otimizador deixou os programas cerca de 25% mais rápidos. Por exemplo, o conversor de graus Celsius para Fahrenheit leva 0.24 segundos para executar sem otimização e 0.18 com otimização.
O exemplo que apresentou a maior melhora foi aquele criado exclusivamente para o projeto, que sem otimização executava em 1.283 segundos e com otimização passou a executar em 0.86 segundos, que representa uma melhora de 33%. Em média, porém, os valores ficaram em cerca de 25%.
Embora esses valores serão aproximados, já que os testes foram realizados num computador convencional, podemos perceber que de fato o otimizador consegue melhorar o número de instruções e o tempo de execução dos programas.
10. Conclusão Realizar otimizações de código numa linguagem já leve e rápida foi um desafio enorme, porém, percebeu-se que várias otimizações podem ser feitas e os resultados obtidos são bastante animadores. A sintaxe e a semântica da linguagem Lua já eliminam a possibilidade de várias otimizações em tempo de compilação, e outras o próprio compilador já executa, porém otimizações muito importantes como a eliminação de subexpressões comuns e a propagação de cópia não são realizadas na linguagem.
Nos testes realizados, pode-se notar que vários recálculos de expressões são substituídos por instruções mais baratas, como as de cópia. Além disso, várias instruções puderam ser removidas, diminuindo o número de instruções executadas pelos programas. Dessa forma, garantimos que o programa usa menos recursos e leva um tempo menor para executar.
Todas essas otimizações são ideais para desenvolvedores que compilam seus programas para executá-los posteriormente, e dessa forma o tempo que o otimizador leva para realizar as otimizações e também os recursos que ele utiliza não são tão cruciais. Ainda assim, para um programa em código intermediário de Lua com 33 linhas de código, o otimizador levou menos de 100 milissegundos para executar.
Referências
Aho, A. V., Lam, M. S., Sethi, R. e Ullman, J. D. (2008) Compiladores – Princípios, técnicas e ferramentas, Pearson Addison-Wesley, 2ª edição.
Ierusalimschy, R., De Figueiredo, L. H. e Celes, W. (2005) “The Implementation of Lua 5.0”, Journal of Universal Computer Science, v. 11, p. 1159-1176.
Glasberg, M. S., Bresler, J. e Cho, Y. “The Lua Architecture”, Advanced Topics in Software Engineering.
Ierusalimschy, R., De Figueiredo, L. H. e Celes, W. (2007) “The Evolution of Lua”, Proceedings of the third ACM SIGPLAN conference on History of programming languages, San Diego, California, p.2-1 – 2-26.
Shi, Y., Casey, K., Ertl, M. A. e Gregg, D. (2008) “Virtual Machine Showdown: Stack Versus Registers”, ACM Transactions on Architecture and Code Optimization, p.21-1 – 21-36.
76
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N. e Zadeck, F. K. (1991) “Virtual Efficiently computing static single assignment form and the control dependence graph”, ACM Transactions on Programming Languages and Systems, p. 451-490.
77
Apêndice B – Código Fonte
78
main.c #include <regex.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/time.h> #include "main.h" #define CAMINHO "apresentacao.lst" #define REGEX_INICIO_FUNCAO "([a-zA-Z0-9])+( )+(\\*\\* function \\[)([0-9])+(] definition \\(level )([0-9])+(\\))" #define REGEX_FIM_FUNCAO "( )*(\\*\\* end of function \\*\\*)" #define REGEX_LINHA_DE_CODIGO "([a-zA-Z0-9]{4})( )([a-zA-Z0-9]{8})( +)(\\[)([0-9]+)(] )([a-z]+)( +)((-?[0-9]+ +)+)(;|\n)" #define SUBEXPRESSOES_REGEX_CODIGO 13 #define INDICE_NOME_INSTRUCAO 8 #define INDICE_ARGUMENTOS 10 #define TAM_MAX_NOME_INSTRUCAO_LUA 9 #define ERR_INSTRUCAO_INVALIDA "ERRO! %s não é uma instrução Lua.\n" #define ERR_OPCODE_INVALIDO "ERRO! %c%c não é um opcode válido.\n" #define ERR_ELIM_SUBEXPRESSOES1 "ERRO! Eliminação de subexpressões comuns interrompida na linha:\n%s\nEra esperado um argumento positivo.\n" #define MESMO_BLOCO 0 #define CONST_LOADBOOL_C 0 #define ENTRY (-2) #define EXIT (-1) #define LIXO 132000 #define NRO_MAX_RETORNOS_DINAMICOS 10 #define NRO_MAX_PARAMETROS_FUNCAO 10 #define NRO_MAX_SET_DINAMICOS 10 #define NRO_MAX_VARARG_DINAMICOS 10 #define TAM_MAX_ROTULO_DEF_ALCANCE 8 #define TAM_MAX_ROTULO_EXP_DISPONIVEIS 10 #define TAM_MAX_REGISTRADORES 3 #define TAM_MAX_ARGUMENTO 4 #define LFIELDS_PER_FLUSH 50 #define COPIA_HABILITADA 'C' #define COPIA_INSERIDA 'O' #define COPIA_REMOVIDA 'P' #define SUBEXPRESSAO_IF_DESABILITADA 'I' #define SUBEXPRESSAO_ELSE_DESABILITADA 'E' static FILE *fp; // Aponta para o arquivo que será lido. static char linha[TAM_MAX_LINHA_DO_ARQUIVO]; // Usada apenas para a chamada da função fgets. static char *linha_do_arquivo; // Usada para ler uma linha de um arquivo: linha_do_arquivo = fgets(linha,TAM_MAX_LINHA_DE_CODIGO,fp); static short UM = 1; static short ZERO = 0; static short TRUE = 1; static short FALSE = 0;
79
/* Definições das funções */ void le_arquivo_inteiro(funcoes_t *funcoes, int *flags); void backtrack_expressoes(vertice_t* vertice, int var, char* linha, int i); void definicoes_de_alcance(grafo_t* cfg); void expressoes_disponiveis(grafo_t* cfg); void elimina_subexpressoes_comuns(grafo_t * cfg); void arrumar_jumps(grafo_t* cfg); void imprime_codigo(grafo_t * cfg); void propaga_copias(grafo_t * cfg); void gera_assembly_chunkbake(grafo_t * cfg); char * pega_instrucao(char a, char b); void otimiza_funcoes(int i, int j, funcoes_t* funcoes); int main() { /* Inicia contagem de tempo. */ struct timeval begin; gettimeofday(&begin,NULL); /* Abre arquivo de entrada, contendo o código intermediário que será otimizado. */ fp = fopen(CAMINHO,"r"); /* * Cria, aloca espaço e inicializa as variáveis da struct 'funcoes', que irá * armazenar os dados lidos do arquivo aberto anteriormente. */ funcoes_t* funcoes; funcoes = calloc(1,sizeof(funcoes_t)); funcoes->nro_funcoes = 0; funcoes->nro_niveis = 0; int i, j, k; funcoes->linhas_codigo = calloc(NRO_MAX_NIVEIS,sizeof(int *)); for (i = 0; i < NRO_MAX_NIVEIS; i++){ funcoes->linhas_codigo[i] = calloc(NRO_MAX_FUNCOES,sizeof(int *)); for (j = 0; j < NRO_MAX_FUNCOES; j++){ funcoes->nro_linhas[i][j] = 0; funcoes->nro_linhas_codigo[i][j] = 0; funcoes->linhas_codigo[i][j] = calloc(NRO_MAX_LINHAS_NUMA_FUNCAO,sizeof(int *)); for (k = 0; k < NRO_MAX_LINHAS_NUMA_FUNCAO; k++) funcoes->linhas_codigo[i][j][k] = calloc(TAM_MAX_LINHA_DO_ARQUIVO,sizeof(char)); } } /* * Cria e inicializa variáveis auxiliares e lê todo o arquivo de entrada e * organiza os dados dele na struct 'funcoes' para tratamento posterior.
80
*/ int flags[NRO_MAX_NIVEIS]; for (i = 0; i < NRO_MAX_NIVEIS; i++) flags[i] = 0; le_arquivo_inteiro(funcoes,flags); //teste_funcoes(funcoes,flags); //DEBUG /* * Otimizador atualmente apenas otimiza função principal do programa. * Linhas abaixo estão com erro. * Função otimiza_funcoes realiza a otimização toda. */ /*for (i = funcoes->nro_niveis-1; i >= 0; i--) for (j = flags[i]-1; j >= 0; j--) otimiza_funcoes(i, j, funcoes); */ otimiza_funcoes(0, 0, funcoes); struct timeval end; gettimeofday(&end,NULL); printf("\nTempo decorrido: %u microssegundos.\n",((unsigned int)end.tv_usec)-((unsigned int)begin.tv_usec)); //teste_cfg(&cfg); //DEBUG } // Função responsável por realizar as otimizações void otimiza_funcoes(int i, int j, funcoes_t* funcoes) { /* * Separa arquivo fonte, pegando apenas o código do programa fonte * e ignorando linhas de comentários e outras desnecessárias. */ regex_t* padrao_codigo; regcomp(padrao_codigo,REGEX_LINHA_DE_CODIGO,REG_EXTENDED); //teste_regcomp(regcomp(padrao_codigo,REGEX_LINHA_DE_CODIGO,REG_EXTENDED)); //DEBUG char ** codigo = NULL; char * nome = NULL; size_t nmatch = sizeof (regmatch_t) * SUBEXPRESSOES_REGEX_CODIGO; regmatch_t matcharray[nmatch]; int n = 0; int k, l, m; regmatch_t argumentos; codigo = calloc(funcoes->nro_linhas[i][j],sizeof(int *)); for (k = 0; k < funcoes->nro_linhas[i][j]; k++) codigo[k] = calloc(TAM_LINHA_CODIGO_LUA,sizeof(char)); for (k = 0; k < funcoes->nro_linhas[i][j]; k++){ if (regexec (padrao_codigo,funcoes->linhas_codigo[i][j][k],nmatch,matcharray,0) == 0){ nome = calloc(TAM_MAX_NOME_INSTRUCAO_LUA,sizeof(char)); regmatch_t nome_instrucao = matcharray[INDICE_NOME_INSTRUCAO]; m = 0; for (l = nome_instrucao.rm_so; l < nome_instrucao.rm_eo; l++){ nome[m] = funcoes->linhas_codigo[i][j][k][l]; m++;
81
} for (;m < TAM_MAX_NOME_INSTRUCAO_LUA;m++) nome[m] = '$'; nome[m] = '\0'; if (pega_opcode(nome) != 0) printf("ERRO! Opcode desconhecido."); codigo[n][0] = nome[0]; codigo[n][1] = nome[1]; codigo[n][2] = '$'; m = 3; argumentos = matcharray[INDICE_ARGUMENTOS]; int estado; char aux; for (l = argumentos.rm_so; l < argumentos.rm_eo; l++){ aux = funcoes->linhas_codigo[i][j][k][l]; if (((aux >= '0') && (aux <= '9'))||(aux == '-')){ codigo[n][m] = funcoes->linhas_codigo[i][j][k][l]; estado = 1; m++; }else{ if (aux == ' '){ if (estado == 1){ codigo[n][m] = '$'; estado = 0; m++; } }else printf("Nunca deve executar essa linha."); } } for (;m < TAM_LINHA_CODIGO_LUA;m++) codigo[n][m] = '$'; codigo[n][TAM_LINHA_CODIGO_LUA] = '\0'; //printf("%s\n",codigo[n]); //DEBUG n++; free(nome); nome = NULL; } } int n_linhas_funcao = funcoes->nro_linhas_codigo[i][j]; int qtd_arestas_saindo[n_linhas_funcao]; int qtd_arestas_chegando[n_linhas_funcao]; int offset_arestas_saindo[n_linhas_funcao][NRO_MAX_ARESTAS_SAINDO_DO_VERTICE]; int offset_arestas_chegando[n_linhas_funcao][NRO_MAX_ARESTAS_SAINDO_DO_VERTICE]; int arestas_chegando_exit[NRO_MAX_ARESTAS_SAINDO_DO_VERTICE]; for (k = 0; k < n_linhas_funcao; k++){ qtd_arestas_saindo[k] = 0; qtd_arestas_chegando[k] = 0; for (l = 0; l < NRO_MAX_ARESTAS_SAINDO_DO_VERTICE; l++){ offset_arestas_saindo[k][l] = 0;
82
offset_arestas_chegando[k][l] = 0; } } for (l = 0; l < NRO_MAX_ARESTAS_SAINDO_DO_VERTICE; l++) arestas_chegando_exit[l] = 0; /* * Os 'for' e 'switch' abaixo percorrem todo o código fonte do programa * e organizam ele em um grafo de fluxo de controle chamado 'cfg' */ grafo_t cfg; cfg.n_definicoes_de_alcance = 0; cfg.n_expressoes_disponiveis = 0; cfg.n_registradores = 0; char rotulos_exp_distintos[n_linhas_funcao][TAM_MAX_ROTULO_EXP_DISPONIVEIS]; char rotulo_aux[TAM_MAX_ROTULO_EXP_DISPONIVEIS]; bool achou; bool flag; int estado; int arg1,arg2,arg3; for (k = 0; k < n_linhas_funcao; k++){ if (pega_argumento(codigo[k],2) != LIXO){ achou = FALSE; estado = 0; m = 0; for (l = 0; l < TAM_LINHA_CODIGO_LUA; l++){ switch(estado){ case 0: rotulo_aux[m] = codigo[k][l]; m++; if (!((codigo[k][l] >= '0')&&(codigo[k][l] <= '9'))) estado = 1; break; case 1: if (!(((codigo[k][l] >= '0')&&(codigo[k][l] <= '9'))||(codigo[k][l] == '-'))) estado = 2; break; case 2: rotulo_aux[m] = codigo[k][l]; m++; if (!(((codigo[k][l] >= '0')&&(codigo[k][l] <= '9'))||(codigo[k][l] == '-'))) if (pega_argumento(codigo[k],3) != LIXO) estado = 3; else estado = 4; break; case 3: rotulo_aux[m] = codigo[k][l]; m++; if (!(((codigo[k][l] >= '0')&&(codigo[k][l] <= '9'))||(codigo[k][l] == '-'))) estado = 4; break;
83
case 4: rotulo_aux[m-1] = '\0'; break; default: break; } } //printf("rotulo_aux[%d]: %s\n",k,rotulo_aux); //DEBUG }else rotulo_aux[0] = '\0'; switch (codigo[k][0]){ case '0': switch (codigo[k][1]){ case '0': //MOVE l = 0; while ((l < cfg.n_expressoes_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,rotulos_exp_distintos[l])); //printf("%s // %s\n",rotulo_aux,rotulos_exp_distintos[l]); //DEBUG l++; } if (!achou){ l = 0; while (rotulo_aux[l] != '\0'){ rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = rotulo_aux[l]; l++; } rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = '\0'; (cfg.n_expressoes_disponiveis)++; } //printf("%d\n",cfg.n_expressoes_disponiveis); //DEBUG (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; case '4': //GETUPVAL case '5': //GETGLOBAL l = 0; while ((l < cfg.n_expressoes_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,rotulos_exp_distintos[l])); //printf("%s // %s\n",rotulo_aux,rotulos_exp_distintos[l]); //DEBUG l++; } if (!achou){
84
l = 0; while (rotulo_aux[l] != '\0'){ rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = rotulo_aux[l]; l++; } rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = '\0'; (cfg.n_expressoes_disponiveis)++; } //printf("%d\n",cfg.n_expressoes_disponiveis); //DEBUG (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '6': //GETTABLE l = 0; while ((l < cfg.n_expressoes_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,rotulos_exp_distintos[l])); //printf("%s // %s\n",rotulo_aux,rotulos_exp_distintos[l]); //DEBUG l++; } if (!achou){ l = 0; while (rotulo_aux[l] != '\0'){ rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = rotulo_aux[l]; l++; } rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = '\0'; (cfg.n_expressoes_disponiveis)++; } //printf("%d\n",cfg.n_expressoes_disponiveis); //DEBUG (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; arg3 = pega_argumento(codigo[k],3); if ((arg3 <= 255)&&(arg3 > cfg.n_registradores)) cfg.n_registradores = arg3; break; case '2': //LOADBOOL arg3 = pega_argumento(codigo[k],3); if (arg3 != CONST_LOADBOOL_C){
85
offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+2; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+2][qtd_arestas_chegando[k+2]] = k; qtd_arestas_chegando[k+2]++; }else if (qtd_arestas_chegando[k+1] > 0){ offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; } (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '3': //LOADNIL arg1 = pega_argumento(codigo[k],1); arg2 = pega_argumento(codigo[k],2); (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + (arg2 - arg1) + 1; if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; case '1': //LOADK case '7': //SETGLOBAL case '8': //SETUPVAL (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '9': //SETTABLE (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if ((arg2 <= 255)&&(arg2 > cfg.n_registradores)) cfg.n_registradores = arg2; arg3 = pega_argumento(codigo[k],3); if ((arg3 <= 255)&&(arg3 > cfg.n_registradores)) cfg.n_registradores = arg3; break; default: printf(ERR_OPCODE_INVALIDO,codigo[k][0],codigo[k][1]); break; } break; case '1': switch (codigo[k][1]){ case '0': //NEWTABLE (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1);
86
if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '1': //SELF (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + 2; arg1 = pega_argumento(codigo[k],1) + 1; if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; arg3 = pega_argumento(codigo[k],3); if ((arg3 <= 255)&&(arg3 > cfg.n_registradores)) cfg.n_registradores = arg3; break; case '2': //ADD case '3': //SUB case '4': //MUL case '5': //DIV case '6': //MOD case '7': //POW case '8': //UNM case '9': //NOT l = 0; while ((l < cfg.n_expressoes_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,rotulos_exp_distintos[l])); //printf("%s // %s\n",rotulo_aux,rotulos_exp_distintos[l]); //DEBUG l++; } if (!achou){ l = 0; while (rotulo_aux[l] != '\0'){ rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = rotulo_aux[l]; l++; } rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = '\0'; (cfg.n_expressoes_disponiveis)++; } //printf("%d\n",cfg.n_expressoes_disponiveis); //DEBUG (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if ((arg2 <= 255)&&(arg2 > cfg.n_registradores)) cfg.n_registradores = arg2; arg3 = pega_argumento(codigo[k],3); if ((arg3 <= 255)&&(arg3 > cfg.n_registradores)) cfg.n_registradores = arg3;
87
break; default: printf(ERR_OPCODE_INVALIDO,codigo[k][0],codigo[k][1]); break; } break; case '2': switch (codigo[k][1]){ case '0': //LEN l = 0; while ((l < cfg.n_expressoes_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,rotulos_exp_distintos[l])); //printf("%s // %s\n",rotulo_aux,rotulos_exp_distintos[l]); //DEBUG l++; } if (!achou){ l = 0; while (rotulo_aux[l] != '\0'){ rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = rotulo_aux[l]; l++; } rotulos_exp_distintos[cfg.n_expressoes_disponiveis][l] = '\0'; (cfg.n_expressoes_disponiveis)++; } //printf("%d\n",cfg.n_expressoes_disponiveis); //DEBUG (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; case '1': //CONCAT (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],3); if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; case '2': //JMP arg1 = 1 + pega_argumento(codigo[k],1); offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+arg1; qtd_arestas_saindo[k]++;
88
offset_arestas_chegando[k+arg1][qtd_arestas_chegando[k+arg1]] = k; qtd_arestas_chegando[k+arg1]++; break; case '3': //EQ case '4': //LT case '5': //LE offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+2; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; offset_arestas_chegando[k+2][qtd_arestas_chegando[k+2]] = k; qtd_arestas_chegando[k+2]++; arg2 = pega_argumento(codigo[k],2); if ((arg2 <= 255)&&(arg2 > cfg.n_registradores)) cfg.n_registradores = arg2; arg3 = pega_argumento(codigo[k],3); if ((arg3 <= 255)&&(arg3 > cfg.n_registradores)) cfg.n_registradores = arg3; break; case '6': //TEST offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+2; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; offset_arestas_chegando[k+2][qtd_arestas_chegando[k+2]] = k; qtd_arestas_chegando[k+2]++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '7': //TESTSET offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+2; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; offset_arestas_chegando[k+2][qtd_arestas_chegando[k+2]] = k; qtd_arestas_chegando[k+2]++; (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1);
89
if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; arg2 = pega_argumento(codigo[k],2); if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; case '8': //CALL arg3 = pega_argumento(codigo[k],3); if (arg3 == 0) (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + NRO_MAX_RETORNOS_DINAMICOS; else (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + (arg3-1); offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; arg1 = pega_argumento(codigo[k],1); arg2 = pega_argumento(codigo[k],2); if (arg2 == 0) arg2 = NRO_MAX_PARAMETROS_FUNCAO; arg2 = arg1 + arg2 - 1; if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; if (arg3 == 0) arg3 = NRO_MAX_RETORNOS_DINAMICOS; arg3 = arg1 + arg3 - 2; if (arg3 > cfg.n_registradores) cfg.n_registradores = arg3; break; case '9': //TAILCALL offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; arg1 = pega_argumento(codigo[k],1); arg2 = pega_argumento(codigo[k],2); if (arg2 == 0) arg2 = NRO_MAX_PARAMETROS_FUNCAO; arg2 = arg1 + arg2 - 1; if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; default: printf(ERR_OPCODE_INVALIDO,codigo[k][0],codigo[k][1]); break; } break; case '3': switch (codigo[k][1]){ case '0': //RETURN offset_arestas_saindo[k][qtd_arestas_saindo[k]] = EXIT; qtd_arestas_saindo[k]++;
90
arg1 = pega_argumento(codigo[k],1); arg2 = pega_argumento(codigo[k],2); if (arg2 == 0) arg2 = NRO_MAX_RETORNOS_DINAMICOS; arg2 = arg1 + arg2 - 2; if (arg2 > cfg.n_registradores) cfg.n_registradores = arg2; break; case '1': //FORLOOP arg2 = 1 + pega_argumento(codigo[k],2); offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+arg2; qtd_arestas_saindo[k]++; offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+arg2][qtd_arestas_chegando[k+arg2]] = k; qtd_arestas_chegando[k+arg2]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k; qtd_arestas_chegando[k+1]++; (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + 2; arg1 = pega_argumento(codigo[k],1) + 3; if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '2': //FORPREP arg2 = 1 + pega_argumento(codigo[k],2); offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+arg2; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+arg2][qtd_arestas_chegando[k+arg2]] = k; qtd_arestas_chegando[k+arg2]++; (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1) + 2; if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '3': //TFORLOOP arg3 = pega_argumento(codigo[k],2); (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + arg3 + 1; offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+1; qtd_arestas_saindo[k]++; offset_arestas_saindo[k][qtd_arestas_saindo[k]] = k+2; qtd_arestas_saindo[k]++; offset_arestas_chegando[k+1][qtd_arestas_chegando[k+1]] = k;
91
qtd_arestas_chegando[k+1]++; offset_arestas_chegando[k+2][qtd_arestas_chegando[k+2]] = k; qtd_arestas_chegando[k+2]++; arg1 = pega_argumento(codigo[k],1) + 2 - arg3; if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '4': //SETLIST arg2 = pega_argumento(codigo[k],2); if (arg2 == 0) arg2 = NRO_MAX_SET_DINAMICOS; (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + arg2; arg1 = pega_argumento(codigo[k],1) + arg2; if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '5': //CLOSE arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '6': //CLOSURE (cfg.n_definicoes_de_alcance)++; arg1 = pega_argumento(codigo[k],1); if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; case '7': //VARARG arg2 = pega_argumento(codigo[k],2); if (arg2 == 0) arg2 = NRO_MAX_VARARG_DINAMICOS; else arg2--; (cfg.n_definicoes_de_alcance) = (cfg.n_definicoes_de_alcance) + arg2; arg1 = pega_argumento(codigo[k],1) + arg2; if (arg1 > cfg.n_registradores) cfg.n_registradores = arg1; break; default: printf(ERR_OPCODE_INVALIDO,codigo[k][0],codigo[k][1]); break; } break; default: printf(ERR_OPCODE_INVALIDO,codigo[k][0],codigo[k][1]); break; } } cfg.n_registradores++; for (k = 0; k < n_linhas_funcao; k++) if ((codigo[k][0] == '2')&&(codigo[k][1] == '2')){
92
arg1 = 1 + pega_argumento(codigo[k],1); if (qtd_arestas_saindo[k+arg1-1] == 0){ offset_arestas_saindo[k+arg1-1][0] = k+arg1; qtd_arestas_saindo[k+arg1-1]++; offset_arestas_chegando[k+arg1][qtd_arestas_chegando[k+arg1]] = k+arg1-1; qtd_arestas_chegando[k+arg1]++; } } /*printf("\n"); //DEBUG for (k = 0; k < n_linhas_funcao; k++){ printf("Linha %d: %s\n",k,codigo[k]); printf("%d arestas saindo dela, %d arestas chegando.\n",qtd_arestas_saindo[k],qtd_arestas_chegando[k]); if (qtd_arestas_saindo[k] == 0) printf("Arestas apenas para próxima instrução.\n"); else{ printf("Arestas saindo:"); for (l = 0; l < qtd_arestas_saindo[k]; l++) if (offset_arestas_saindo[k][l] == -1) printf("\tReturn, fim de função."); else printf("\t%d",offset_arestas_saindo[k][l]); printf("\n"); } if (qtd_arestas_chegando[k] == 0) printf("Arestas chegando apenas da instrução anterior.\n"); else{ printf("Arestas chegando:"); for (l = 0; l < qtd_arestas_chegando[k]; l++) if ((offset_arestas_chegando[k][l] == -1)&&(qtd_arestas_chegando[k] == 1)) printf("\tInstrução inalcançável."); else printf("\t%d",offset_arestas_chegando[k][l]); printf("\n"); } printf("\n"); }*/ //DEBUG /*for (k = 0; k < n_linhas_funcao; k++) printf("%s\n",rotulos_exp_distintos[k]);*/ //DEBUG vertice_t entry; entry.codigo = NULL; entry.n_linhas = 0; entry.arestas_saindo = calloc(1,sizeof(int)); entry.arestas_saindo[0] = 0; entry.n_arestas_saindo = 1; entry.arestas_chegando = NULL; entry.n_arestas_chegando = 0; entry.pos_inicial = ENTRY; entry.pos_final = ENTRY; entry.gen = calloc(cfg.n_definicoes_de_alcance,sizeof(bool));
93
entry.kill = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); entry.IN_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); entry.OUT_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); entry.n_definicoes_de_alcance = 0; entry.e_gen = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); entry.e_kill = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); entry.IN_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); entry.OUT_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); entry.n_expressoes_disponiveis = 0; entry.regs_guardando_expressoes = calloc(cfg.n_expressoes_disponiveis,sizeof(int *)); for (k = 0; k < cfg.n_expressoes_disponiveis; k++){ entry.regs_guardando_expressoes[k] = calloc(TAM_MAX_REGISTRADORES,sizeof(char)); entry.regs_guardando_expressoes[k][0] = '\0'; } vertice_t segundo; segundo.codigo = calloc(n_linhas_funcao,sizeof(int *)); for (k = 0; k < n_linhas_funcao; k++) segundo.codigo[k] = calloc(TAM_LINHA_CODIGO_LUA,sizeof(char)); segundo.n_linhas = 0; segundo.arestas_saindo = calloc(NRO_MAX_ARESTAS_SAINDO_DO_VERTICE,sizeof(int)); for (k = 0; k < NRO_MAX_ARESTAS_SAINDO_DO_VERTICE; k++) segundo.arestas_saindo[k] = 0; segundo.n_arestas_saindo = 0; segundo.arestas_chegando = calloc(NRO_MAX_ARESTAS_SAINDO_DO_VERTICE,sizeof(int)); for (k = 1; k < NRO_MAX_ARESTAS_SAINDO_DO_VERTICE; k++) segundo.arestas_chegando[k] = 0; segundo.arestas_chegando[0] = ENTRY; segundo.n_arestas_chegando = 1; segundo.pos_inicial = 0; segundo.pos_final = 0; segundo.proximo = NULL; segundo.gen = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); segundo.kill = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); segundo.IN_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); segundo.OUT_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); segundo.n_definicoes_de_alcance = 0; segundo.e_gen = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); segundo.e_kill = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); segundo.IN_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); segundo.OUT_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); segundo.n_expressoes_disponiveis = 0; segundo.regs_guardando_expressoes = calloc(cfg.n_expressoes_disponiveis,sizeof(int *)); for (k = 0; k < cfg.n_expressoes_disponiveis; k++){
94
segundo.regs_guardando_expressoes[k] = calloc(TAM_MAX_REGISTRADORES,sizeof(char)); segundo.regs_guardando_expressoes[k][0] = '\0'; } entry.proximo = &segundo; vertice_t exit; exit.codigo = NULL; exit.n_linhas = 0; exit.arestas_saindo = NULL; exit.n_arestas_saindo = 0; exit.arestas_chegando = calloc(NRO_MAX_ARESTAS_SAINDO_DO_VERTICE,sizeof(int)); for (k = 0; k < NRO_MAX_ARESTAS_SAINDO_DO_VERTICE; k++) exit.arestas_chegando[k] = 0; exit.n_arestas_chegando = 0; exit.pos_inicial = EXIT; exit.pos_final = EXIT; exit.gen = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); exit.kill = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); exit.IN_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); exit.OUT_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); exit.n_definicoes_de_alcance = 0; exit.e_gen = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); exit.e_kill = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); exit.IN_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); exit.OUT_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); exit.n_expressoes_disponiveis = 0; exit.regs_guardando_expressoes = calloc(cfg.n_expressoes_disponiveis,sizeof(int *)); for (k = 0; k < cfg.n_expressoes_disponiveis; k++){ exit.regs_guardando_expressoes[k] = calloc(TAM_MAX_REGISTRADORES,sizeof(char)); exit.regs_guardando_expressoes[k][0] = '\0'; } cfg.primeiro = &entry; cfg.n_vertices = 2; vertice_t *anterior = &entry; vertice_t *atual = &segundo; for (k = 0; k < n_linhas_funcao; k++){ if (qtd_arestas_chegando[k] != 0){ vertice_t *novo = (vertice_t *)malloc(sizeof(vertice_t)); novo->codigo = calloc(n_linhas_funcao,sizeof(int *)); for (l = 0; l < n_linhas_funcao; l++) novo->codigo[l] = calloc(TAM_LINHA_CODIGO_LUA,sizeof(char)); novo->n_linhas = 0; novo->arestas_saindo = calloc(NRO_MAX_ARESTAS_SAINDO_DO_VERTICE,sizeof(int)); novo->arestas_chegando = calloc(NRO_MAX_ARESTAS_SAINDO_DO_VERTICE,sizeof(int)); for (l = 0; l < NRO_MAX_ARESTAS_SAINDO_DO_VERTICE; l++){ novo->arestas_saindo[l] = 0; novo->arestas_chegando[l] = 0;
95
} novo->n_arestas_saindo = 0; for (l = 0; l < qtd_arestas_chegando[k]; l++) novo->arestas_chegando[l] = offset_arestas_chegando[k][l]; novo->n_arestas_chegando = qtd_arestas_chegando[k]; novo->pos_inicial = k; novo->pos_final = k; novo->proximo = NULL; novo->gen = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); novo->kill = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); novo->IN_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); novo->OUT_def = calloc(cfg.n_definicoes_de_alcance,sizeof(bool)); novo->n_definicoes_de_alcance = 0; novo->e_gen = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); novo->e_kill = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); novo->IN_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); novo->OUT_exp = calloc(cfg.n_expressoes_disponiveis,sizeof(bool)); novo->n_expressoes_disponiveis = 0; novo->regs_guardando_expressoes = calloc(cfg.n_expressoes_disponiveis,sizeof(int *)); for (l = 0; l < cfg.n_expressoes_disponiveis; l++){ novo->regs_guardando_expressoes[l] = calloc(TAM_MAX_REGISTRADORES,sizeof(char)); novo->regs_guardando_expressoes[l][0] = '\0'; } (atual->proximo) = novo; anterior = atual; atual = novo; (cfg.n_vertices)++; } atual->n_arestas_saindo = qtd_arestas_saindo[k]; for (l = 0; l < qtd_arestas_saindo[k]; l++) atual->arestas_saindo[l] = offset_arestas_saindo[k][l]; strcpy(atual->codigo[atual->n_linhas],codigo[k]); (atual->n_linhas)++; atual->pos_final = k; if ((codigo[k][0] == '3')&&(codigo[k][1] == '0')){ exit.arestas_chegando[exit.n_arestas_chegando] = k; exit.n_arestas_chegando++; } } (atual->proximo) = &exit; (cfg.n_vertices)++; atual = cfg.primeiro; for (k = 0; k < cfg.n_vertices; k++){ for (l = 0; l < cfg.n_definicoes_de_alcance; l++){ atual->gen[l] = ZERO; atual->kill[l] = ZERO; } atual = atual->proximo;
96
} atual = cfg.primeiro; for (k = 0; k < cfg.n_vertices; k++){ for (l = 0; l < cfg.n_expressoes_disponiveis; l++){ atual->e_gen[l] = ZERO; atual->e_kill[l] = ZERO; } atual = atual->proximo; } cfg.rotulos_definicoes = calloc(cfg.n_definicoes_de_alcance,sizeof(int *)); for (k = 0; k < cfg.n_definicoes_de_alcance; k++) cfg.rotulos_definicoes[k] = calloc(TAM_MAX_ROTULO_DEF_ALCANCE,sizeof(char)); cfg.rotulos_expressoes = calloc(cfg.n_expressoes_disponiveis,sizeof(int *)); for (k = 0; k < cfg.n_expressoes_disponiveis; k++) cfg.rotulos_expressoes[k] = calloc(TAM_MAX_ROTULO_EXP_DISPONIVEIS,sizeof(char)); atual = cfg.primeiro; anterior = NULL; char arg01[TAM_MAX_ARGUMENTO]; char arg02[TAM_MAX_ARGUMENTO]; char arg03[TAM_MAX_ARGUMENTO]; for (k = 0; k < TAM_MAX_ROTULO_DEF_ALCANCE; k++){ arg01[k] = '$'; arg02[k] = '$'; arg03[k] = '$'; } int n_def_alcance = 0; int n_exp_disponiveis = 0; int o, p, q; for (k = 0; k < cfg.n_vertices; k++){ for (l = 0; l < atual->n_linhas; l++){ switch(atual->codigo[l][0]){ case '0': switch (atual->codigo[l][1]){ case '0': //MOVE case '4': //GETUPVAL case '5': //GETGLOBAL arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++;
97
n_def_alcance++; rotulo_aux[0] = atual->codigo[l][0]; rotulo_aux[1] = atual->codigo[l][1]; rotulo_aux[2] = '$'; arg2 = pega_argumento(atual->codigo[l],2); sprintf(arg02,"%d",arg2); m = 0; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ rotulo_aux[m+3] = arg02[m]; m++; } rotulo_aux[m+3] = '\0'; achou = FALSE; n = 0; while ((n < n_exp_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,cfg.rotulos_expressoes[n])); //printf("%s || %s\n",rotulo_aux,cfg.rotulos_expressoes[n]); //DEBUG n++; } if (!achou){ q = 0; while (rotulo_aux[q] != '\0'){ cfg.rotulos_expressoes[n][q] = rotulo_aux[q]; q++; } cfg.rotulos_expressoes[n][q] = '\0'; atual->n_expressoes_disponiveis++; n_exp_disponiveis++; }else n--; atual->e_gen[n] = UM; atual->e_kill[n] = ZERO; //printf("%s|",atual->regs_guardando_expressoes[n]); //DEBUG if (atual->regs_guardando_expressoes[n][0] == '\0'){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ atual->regs_guardando_expressoes[n][m] = arg01[m]; m++; }
98
atual->regs_guardando_expressoes[n][m] = '\0'; } //printf("%s\n",atual->regs_guardando_expressoes[n]); //DEBUG for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '1': //LOADK case '2': //LOADBOOL arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '3': //LOADNIL arg1 = pega_argumento(atual->codigo[l],1); arg2 = pega_argumento(atual->codigo[l],2); for (m = arg1; m <= arg2; m++){ sprintf(arg01,"%d",m); n = 0; while ((arg01[n] >= '0')&&(arg01[n] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][n] = arg01[n]; n++; } cfg.rotulos_definicoes[n_def_alcance][n] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++;
99
for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, m, cfg.rotulos_expressoes[p], p); } break; case '6': //GETTABLE arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; rotulo_aux[0] = atual->codigo[l][0]; rotulo_aux[1] = atual->codigo[l][1]; rotulo_aux[2] = '$'; arg2 = pega_argumento(atual->codigo[l],2); sprintf(arg02,"%d",arg2); m = 0; n = 3; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ rotulo_aux[n] = arg02[m]; m++; n++; } rotulo_aux[n] = '$'; n++; arg3 = pega_argumento(atual->codigo[l],3); sprintf(arg03,"%d",arg3); m = 0; while ((arg03[m] >= '0')&&(arg03[m] <= '9')){ rotulo_aux[n] = arg03[m]; m++; n++; } rotulo_aux[n] = '\0'; achou = FALSE;
100
o = 0; while ((o < n_exp_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,cfg.rotulos_expressoes[o])); //printf("%s || %s\n",rotulo_aux,cfg.rotulos_expressoes[o]); //DEBUG o++; } if (!achou){ q = 0; while (rotulo_aux[q] != '\0'){ cfg.rotulos_expressoes[o][q] = rotulo_aux[q]; q++; } cfg.rotulos_expressoes[o][q] = '\0'; atual->n_expressoes_disponiveis++; n_exp_disponiveis++; }else o--; atual->e_gen[o] = UM; atual->e_kill[o] = ZERO; //printf("%s|",atual->regs_guardando_expressoes[o]); //DEBUG if (atual->regs_guardando_expressoes[o][0] == '\0'){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ atual->regs_guardando_expressoes[o][m] = arg01[m]; m++; } atual->regs_guardando_expressoes[o][m] = '\0'; } //printf("%s\n",atual->regs_guardando_expressoes[o]); //DEBUG for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '7': //SETGLOBAL cfg.rotulos_definicoes[n_def_alcance][0] = 'K'; arg2 = pega_argumento(atual->codigo[l],2); sprintf(arg02,"%d",arg2); m = 0; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m+1] = arg02[m];
101
m++; } cfg.rotulos_definicoes[n_def_alcance][m+1] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++){ char* aux = cfg.rotulos_expressoes[p]; if ((aux[0] == '0')&&(aux[1] == '5')&&(pega_argumento(aux,1) == arg2)){ atual->e_gen[p] = ZERO; atual->e_kill[p] = UM; } } break; case '8': //SETUPVAL cfg.rotulos_definicoes[n_def_alcance][0] = 'U'; arg2 = pega_argumento(atual->codigo[l],2); sprintf(arg02,"%d",arg2); m = 0; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m+1] = arg02[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m+1] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++){ char* aux = cfg.rotulos_expressoes[p]; if ((aux[0] == '0')&&(aux[1] == '4')&&(pega_argumento(aux,1) == arg2)){ atual->e_gen[p] = ZERO; atual->e_kill[p] = UM; } } break; case '9': //SETTABLE arg1 = pega_argumento(atual->codigo[l],1);
102
sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = 'T'; m++; arg2 = pega_argumento(atual->codigo[l],2); if (arg2 > 255){ arg2 = arg2-256; cfg.rotulos_definicoes[n_def_alcance][m] = 'K'; m++; } sprintf(arg02,"%d",arg2); n = 0; while ((arg02[n] >= '0')&&(arg02[n] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg02[n]; m++; n++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++){ char* aux = cfg.rotulos_expressoes[p]; if ((aux[0] == '0')&&(aux[1] == '6')) if ((arg1 == pega_argumento(aux,2))&&(arg2 == pega_argumento(aux,3))){ atual->e_gen[p] = ZERO; atual->e_kill[p] = UM; } } break; default: break; } break; case '1': switch (atual->codigo[l][1]){ case '0': //NEWTABLE arg1 = pega_argumento(atual->codigo[l],1);
103
sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = 'T'; cfg.rotulos_definicoes[n_def_alcance][m+1] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '1': //SELF arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); arg1++; sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0';
104
atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '2': //ADD case '3': //SUB case '4': //MUL case '5': //DIV case '6': //MOD case '7': //POW arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; rotulo_aux[0] = atual->codigo[l][0]; rotulo_aux[1] = atual->codigo[l][1]; rotulo_aux[2] = '$'; arg2 = pega_argumento(atual->codigo[l],2); sprintf(arg02,"%d",arg2); m = 0; n = 3; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ rotulo_aux[n] = arg02[m]; m++; n++; } rotulo_aux[n] = '$'; n++; arg3 = pega_argumento(atual->codigo[l],3); sprintf(arg03,"%d",arg3); m = 0; while ((arg03[m] >= '0')&&(arg03[m] <= '9')){
105
rotulo_aux[n] = arg03[m]; m++; n++; } rotulo_aux[n] = '\0'; achou = FALSE; o = 0; while ((o < n_exp_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,cfg.rotulos_expressoes[o])); //printf("%s || %s\n",rotulo_aux,cfg.rotulos_expressoes[o]); //DEBUG o++; } if (!achou){ q = 0; while (rotulo_aux[q] != '\0'){ cfg.rotulos_expressoes[o][q] = rotulo_aux[q]; q++; } cfg.rotulos_expressoes[o][q] = '\0'; atual->n_expressoes_disponiveis++; n_exp_disponiveis++; }else o--; atual->e_gen[o] = UM; atual->e_kill[o] = ZERO; //printf("%s|",atual->regs_guardando_expressoes[o]); if (atual->regs_guardando_expressoes[o][0] == '\0'){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ atual->regs_guardando_expressoes[o][m] = arg01[m]; m++; } atual->regs_guardando_expressoes[o][m] = '\0'; } //printf("%s\n",atual->regs_guardando_expressoes[o]); for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '8': //UNM case '9': //NOT
106
arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; rotulo_aux[0] = atual->codigo[l][0]; rotulo_aux[1] = atual->codigo[l][1]; rotulo_aux[2] = '$'; arg2 = pega_argumento(atual->codigo[l],2); sprintf(arg02,"%d",arg2); m = 0; n = 3; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ rotulo_aux[n] = arg02[m]; m++; n++; } rotulo_aux[n] = '\0'; achou = FALSE; o = 0; while ((o < n_exp_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,cfg.rotulos_expressoes[o])); //printf("%s || %s\n",rotulo_aux,cfg.rotulos_expressoes[o]); //DEBUG o++; } if (!achou){ q = 0; while (rotulo_aux[q] != '\0'){ cfg.rotulos_expressoes[o][q] = rotulo_aux[q]; q++; } cfg.rotulos_expressoes[o][q] = '\0'; atual->n_expressoes_disponiveis++; n_exp_disponiveis++;
107
}else o--; atual->e_gen[o] = UM; atual->e_kill[o] = ZERO; //printf("%s|",atual->regs_guardando_expressoes[o]); //DEBUG if (atual->regs_guardando_expressoes[o][0] == '\0'){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ atual->regs_guardando_expressoes[o][m] = arg01[m]; m++; } atual->regs_guardando_expressoes[o][m] = '\0'; } //printf("%s\n",atual->regs_guardando_expressoes[o]); //DEBUG for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; default: break; } break; case '2': switch (atual->codigo[l][1]){ case '0': //LEN arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; rotulo_aux[0] = atual->codigo[l][0]; rotulo_aux[1] = atual->codigo[l][1]; rotulo_aux[2] = '$'; arg2 = pega_argumento(atual->codigo[l],2);
108
sprintf(arg02,"%d",arg2); m = 0; n = 3; while ((arg02[m] >= '0')&&(arg02[m] <= '9')){ rotulo_aux[n] = arg02[m]; m++; n++; } rotulo_aux[n] = '\0'; achou = FALSE; o = 0; while ((o < n_exp_disponiveis)&&(!achou)){ achou = !(strcmp(rotulo_aux,cfg.rotulos_expressoes[o])); //printf("%s || %s\n",rotulo_aux,cfg.rotulos_expressoes[o]); //DEBUG o++; } if (!achou){ q = 0; while (rotulo_aux[q] != '\0'){ cfg.rotulos_expressoes[o][q] = rotulo_aux[q]; q++; } cfg.rotulos_expressoes[o][q] = '\0'; atual->n_expressoes_disponiveis++; n_exp_disponiveis++; }else o--; atual->e_gen[o] = UM; atual->e_kill[o] = ZERO; //printf("%s|",atual->regs_guardando_expressoes[o]); //DEBUG if (atual->regs_guardando_expressoes[o][0] == '\0'){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ atual->regs_guardando_expressoes[o][m] = arg01[m]; m++; } atual->regs_guardando_expressoes[o][m] = '\0'; } //printf("%s\n",atual->regs_guardando_expressoes[o]); //DEBUG for (p = 0; p < n_exp_disponiveis; p++)
109
backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '1': //CONCAT case '7': //TESTSET arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '8': //CALL arg1 = pega_argumento(atual->codigo[l],1); arg3 = pega_argumento(atual->codigo[l],3); if (arg3 == 0) for (m = 0; m < NRO_MAX_RETORNOS_DINAMICOS; m++){ sprintf(arg01,"%d",m+arg1); n = 0; while ((arg01[n] >= '0')&&(arg01[n] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][n] = arg01[n]; n++; } cfg.rotulos_definicoes[n_def_alcance][n] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); } else
110
for (m = arg1; m <= arg1+arg3-2; m++){ sprintf(arg01,"%d",m); n = 0; while ((arg01[n] >= '0')&&(arg01[n] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][n] = arg01[n]; n++; } cfg.rotulos_definicoes[n_def_alcance][n] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); } break; default: break; } break; case '3': switch (atual->codigo[l][1]){ case '1': //FORLOOP arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); arg1 = arg1 + 3; sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){
111
cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '2': //FORPREP arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '3': //TFORLOOP arg1 = pega_argumento(atual->codigo[l],1); arg1 = arg1 + 2; sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++;
112
for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); arg2 = pega_argumento(atual->codigo[l],2); for (m = 0; m < arg2; m++){ arg1++; sprintf(arg01,"%d",arg1); n = 0; while ((arg01[n] >= '0')&&(arg01[n] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][n] = arg01[n]; n++; } cfg.rotulos_definicoes[n_def_alcance][n] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); } break; case '4': //SETLIST arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); arg3 = pega_argumento(atual->codigo[l],3); arg3 = (arg3-1)*LFIELDS_PER_FLUSH; arg2 = pega_argumento(atual->codigo[l],2); if (arg2 == 0) arg2 = NRO_MAX_SET_DINAMICOS; for (n = 1; n <= arg2; n++){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = 'T'; m++; sprintf(arg02,"%d",n + arg3);
113
o = 0; while ((arg02[o] >= '0')&&(arg02[o] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg02[o]; m++; o++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++){ char* aux = cfg.rotulos_expressoes[p]; if ((aux[0] == '0')&&(aux[1] == '6')) if ((arg1 == pega_argumento(aux,2))&&((n + arg3) == pega_argumento(aux,3))){ atual->e_gen[p] = ZERO; atual->e_kill[p] = UM; } } } break; case '6': //CLOSURE arg1 = pega_argumento(atual->codigo[l],1); sprintf(arg01,"%d",arg1); m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][m] = arg01[m]; m++; } cfg.rotulos_definicoes[n_def_alcance][m] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, arg1, cfg.rotulos_expressoes[p], p); break; case '7': //VARARG arg1 = pega_argumento(atual->codigo[l],1); m = arg1;
114
arg2 = pega_argumento(atual->codigo[l],2); if (arg2 == 0) arg2 = NRO_MAX_VARARG_DINAMICOS; else arg2--; for (n = 0; n < arg2; n++){ sprintf(arg01,"%d",m); o = 0; while ((arg01[o] >= '0')&&(arg01[o] <= '9')){ cfg.rotulos_definicoes[n_def_alcance][o] = arg01[o]; o++; } cfg.rotulos_definicoes[n_def_alcance][o] = '\0'; atual->gen[n_def_alcance] = UM; atual->n_definicoes_de_alcance++; n_def_alcance++; for (p = 0; p < n_exp_disponiveis; p++) backtrack_expressoes(atual, m, cfg.rotulos_expressoes[p], p); m++; } break; default: break; } break; default: break; } //printf("%s\nDefs: %d\nGen: %s\n\n",atual->codigo[l],n_def_alcance,atual->gen); //DEBUG } if (k < (cfg.n_vertices)-1){ anterior = atual; atual = atual->proximo; for (o = 0; o < cfg.n_expressoes_disponiveis; o++) for (p = 0; p < TAM_MAX_REGISTRADORES; p++) atual->regs_guardando_expressoes[o][p] = anterior->regs_guardando_expressoes[o][p]; } } /*atual = cfg.primeiro; //DEBUG for (k = 0; k < cfg.n_vertices; k++){ for (p = 0; p < cfg.n_expressoes_disponiveis; p++) printf("%d\t%s\n",p,atual->regs_guardando_expressoes[p]); printf("\n"); atual = atual->proximo; }*/ //DEBUG
115
/*for (k = 0; k < n_def_alcance; k++) //DEBUG printf("%d\t%s\n",k,cfg.rotulos_definicoes[k]); printf("\n"); for (k = 0; k < n_exp_disponiveis; k++) printf("%d\t%s\n",k,cfg.rotulos_expressoes[k]); printf("\n");*/ //DEBUG n_def_alcance = 0; for (k = 0; k < TAM_MAX_ROTULO_DEF_ALCANCE; k++){ arg01[k] = '$'; arg02[k] = '$'; } atual = cfg.primeiro; for (k = 0; k < cfg.n_vertices; k++){ for (l = 0; l < atual->n_definicoes_de_alcance; l++){ for (m = 0; m < cfg.n_definicoes_de_alcance; m++) if ((strcmp(cfg.rotulos_definicoes[n_def_alcance],cfg.rotulos_definicoes[m]) == 0)&&(n_def_alcance != m)) atual->kill[m] = UM; n_def_alcance++; } //printf("Kill:\t%s\n",atual->kill); //DEBUG atual = atual->proximo; } /* Chama funções responsáveis por realizar análise de fluxo de dados. */ definicoes_de_alcance(&cfg); expressoes_disponiveis(&cfg); //teste_cfg(&cfg); //DEBUG TODO /* Chama funções responsáveis por realizar as otimizações de código. */ elimina_subexpressoes_comuns(&cfg); propaga_copias(&cfg); //teste_cfg(&cfg); //DEBUG TODO //imprime_codigo(&cfg); //DEBUG } // Realiza propagação de cópias e também eliminação de código morto. void propaga_copias(grafo_t * cfg) { int i, j, k, l, m, n, o, p, q, r, s, t, estado; k = TAM_LINHA_CODIGO_LUA-1; vertice_t * alvo = cfg->primeiro->proximo; vertice_t * atual; char str[TAM_MAX_ARGUMENTO]; bool pode_remover = TRUE; for (i = 1; i < cfg->n_vertices-1; i++){ for (j = 0; j < alvo->n_linhas; j++){ if (alvo->codigo[j][k] == COPIA_HABILITADA){ atual = alvo;
116
n = pega_argumento(alvo->codigo[j],1); o = pega_argumento(alvo->codigo[j],2); if (n != o){ sprintf(str,"%d",o); for (l = i; l < cfg->n_vertices-1; l++){ for (m = j+1; m < atual->n_linhas; m++){ switch(atual->codigo[m][0]){ case '0': switch (atual->codigo[m][1]){ case '0': //MOVE p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; }else{ if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++;
117
} for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break; } } } } break; case '1': //LOADK case '2': //LOADBOOL case '4': //GETUPVAL case '5': //GETGLOBAL p = pega_argumento(atual->codigo[m],1); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; } break; case '3': //LOADNIL p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if (((n >= p)&&(n <= q))||((o >= p)&&(o <= q))){ l = cfg->n_vertices; m = atual->n_linhas+1; } break; case '6': //GETTABLE p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2);
118
t = pega_argumento(atual->codigo[m],3); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; }else{ if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default:
119
break; } } } if (t == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 3; break; case 3: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break;
120
} } } } break; case '7': //SETGLOBAL case '8': //SETUPVAL p = pega_argumento(atual->codigo[m],1); if (p == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default: break;
121
} } } break; case '9': //SETTABLE p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); t = pega_argumento(atual->codigo[m],3); if (p == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default: break;
122
} } } if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default: break; }
123
} } if (t == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: if (!(((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))||(atual->codigo[m][r] == '-'))) estado = 3; break; case 3: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break; } } }
124
break; default: break; } break; case '1': switch (atual->codigo[m][1]){ case '0': //NEWTABLE p = pega_argumento(atual->codigo[m],1); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; } break; case '1': //SELF p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); t = pega_argumento(atual->codigo[m],3); if ((p == n)||(p == o)||(p+1 == n)||(p+1 == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; }else{ if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2;
125
break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default: break; } } } if (t == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break;
126
case 2: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 3; break; case 3: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break; } } } } break; case '2': //ADD case '3': //SUB case '4': //MUL case '5': //DIV case '6': //MOD case '7': //POW p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); t = pega_argumento(atual->codigo[m],3); if ((p == n)||(p == o)){
127
l = cfg->n_vertices; m = atual->n_linhas+1; }else{ if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default: break; }
128
} } if (t == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 3; break; case 3: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break; } }
129
} } break; case '8': //UNM case '9': //NOT p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; }else{ if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$';
130
break; default: break; } } } } break; default: break; } break; case '2': switch (atual->codigo[m][1]){ case '0': //LEN case '7': //TESTSET p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; }else{ if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2;
131
break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break; } } } } break; case '1': //CONCAT p = pega_argumento(atual->codigo[m],1); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; }else{ q = pega_argumento(atual->codigo[m],2); t = pega_argumento(atual->codigo[m],3); if ((n >= q)&&(n <= t)) pode_remover = FALSE; } break; case '2': //JMP break;
132
case '3': //EQ case '4': //LT case '5': //LE q = pega_argumento(atual->codigo[m],2); t = pega_argumento(atual->codigo[m],3); if (q == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default:
133
break; } } } if (t == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 2; break; case 2: if (!(((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))||(atual->codigo[m][r] == '-'))) estado = 3; break; case 3: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } for (; r < TAM_LINHA_CODIGO_LUA; r++) atual->codigo[m][r] = '$'; break; default: break;
134
} } } break; case '6': //TEST p = pega_argumento(atual->codigo[m],1); if (p == n){ estado = 0; for (r = 0; r < TAM_LINHA_CODIGO_LUA; r++){ switch(estado){ case 0: if (!((atual->codigo[m][r] >= '0')&&(atual->codigo[m][r] <= '9'))) estado = 1; break; case 1: s = 0; while ((str[s] >= '0')&&(str[s] <= '9')){ atual->codigo[m][r] = str[s]; s++; r++; } while (atual->codigo[m][r] != '$'){ atual->codigo[m][r] = '$'; r++; } r = TAM_LINHA_CODIGO_LUA; break; default: break; } }
135
} break; case '8': //CALL p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); t = pega_argumento(atual->codigo[m],3); if (q == 0) q = NRO_MAX_PARAMETROS_FUNCAO; if (t == 0) t = NRO_MAX_RETORNOS_DINAMICOS; if (n >= p) if ((n <= p+q-1)||(n <= p+t-2)) pode_remover = FALSE; break; case '9': //TAILCALL p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if (q == 0) q = NRO_MAX_PARAMETROS_FUNCAO; if ((n >= p)&&(n <= p+q-1)) pode_remover = FALSE; default: break; } break; case '3': switch (atual->codigo[m][1]){ case '0': //RETURN p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if (q == 0) q = NRO_MAX_RETORNOS_DINAMICOS; if ((n >= p)&&(n <= p+q-2)) pode_remover = FALSE; break; case '1': //FORLOOP case '2': //FORPREP p = pega_argumento(atual->codigo[m],1); if ((n >= p)&&(n <= p+3)) pode_remover = FALSE;
136
break; case '3': //TFORLOOP p = pega_argumento(atual->codigo[m],1); t = pega_argumento(atual->codigo[m],2); if ((n >= p)&&(n <= p+2+t)) pode_remover = FALSE; break; case '4': //SETLIST p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if ((n >= p)&&(n <= p+q)) pode_remover = FALSE; break; case '5': //CLOSE break; case '6': //CLOSURE p = pega_argumento(atual->codigo[m],1); if ((p == n)||(p == o)){ l = cfg->n_vertices; m = atual->n_linhas+1; } break; case '7': //VARARG p = pega_argumento(atual->codigo[m],1); q = pega_argumento(atual->codigo[m],2); if (q == 0) q = NRO_MAX_VARARG_DINAMICOS; if (((n >= p)&&(n <= p+q-1))||((o >= p)&&(o <= p+q-1))){ l = cfg->n_vertices; m = atual->n_linhas+1; } default: break; } break; default:
137
break; } } atual = atual->proximo; } if ((l == cfg->n_vertices)||(m == atual->n_linhas+1)) pode_remover = FALSE; } alvo->codigo[j][k] = COPIA_REMOVIDA; if (pode_remover){ arrumar_jumps(cfg); alvo->n_linhas--; char ** codigo1 = calloc(alvo->n_linhas,sizeof(int *)); for (p = 0; p < alvo->n_linhas; p++) codigo1[p] = calloc(TAM_LINHA_CODIGO_LUA,sizeof(char)); for (p = 0; p < j; p++) for (q = 0; q < TAM_LINHA_CODIGO_LUA; q++) codigo1[p][q] = alvo->codigo[p][q]; for (; p < alvo->n_linhas; p++) for (q = 0; q < TAM_LINHA_CODIGO_LUA; q++) codigo1[p][q] = alvo->codigo[p+1][q]; alvo->codigo = codigo1; j--; } } } alvo = alvo->proximo; } } // Realiza eliminação de subexpressões comuns. void elimina_subexpressoes_comuns(grafo_t * cfg) { int i, j, k, l, m, n, o, p, q, r, estado, estado2; bool tem_exp_if, tem_exp_else, achou; vertice_t * atual = cfg->primeiro->proximo; k = estado = 0; vertice_t * v_if; vertice_t * v_else; char rotulo_aux[TAM_MAX_ROTULO_EXP_DISPONIVEIS]; for (i = 1; i < (cfg->n_vertices)-1; i++){ for (j = 0; j < atual->n_linhas; j++){ switch(estado){ case 0: if ((atual->codigo[j][0] == '2')&&(atual->codigo[j][1] == '6')) estado = 1; break; case 1: l = pega_argumento(atual->codigo[j],1); if (l < 0){ printf(ERR_ELIM_SUBEXPRESSOES1,atual->codigo[j]); return; }
138
l += k; m = 0; tem_exp_if = FALSE; while ((m < cfg->n_expressoes_disponiveis)&&(!tem_exp_if)){ if ((atual->proximo->e_gen[m] == 1)&&(atual->proximo->IN_exp[m] == 0)){ tem_exp_if = TRUE; v_if = atual->proximo; } m++; } if (tem_exp_if) estado = 2; else estado = 0; break; case 2: if (l == k){ if ((atual->codigo[j][0] == '2')&&(atual->codigo[j][1] == '2')){ l = pega_argumento(atual->codigo[j],1); tem_exp_else = FALSE; if (l > 0){ l += k; m = 0; while ((m < cfg->n_expressoes_disponiveis)&&(!tem_exp_else)){ if ((atual->proximo->e_gen[m] == 1)&&(atual->proximo->IN_exp[m] == 0)){ tem_exp_else = TRUE; v_else = atual->proximo; } } m++; } if (tem_exp_else) estado = 3; else estado = 0; }else estado = 0; } break; case 3: if (l == k){ for (l = 0; l < cfg->n_expressoes_disponiveis; l++){ if ((v_if->IN_exp[l] == 0)&&(v_if->e_gen[l] == 1)&&(v_else->IN_exp[l] == 0)&&(v_else->e_gen[l] == 1)){ char arg01[TAM_MAX_ARGUMENTO]; char arg02[TAM_MAX_ARGUMENTO];
139
int novo_registrador = cfg->n_registradores; cfg->n_registradores++; sprintf(arg01,"%d",novo_registrador); vertice_t * aux; achou = FALSE; m = 0; while ((m < v_if->n_linhas)&&(!achou)){ estado2 = 0; o = 0; for (n = 0; n < TAM_LINHA_CODIGO_LUA; n++){ switch(estado2){ case 0: rotulo_aux[o] = v_if->codigo[m][n]; o++; if (!((v_if->codigo[m][n] >= '0')&&(v_if->codigo[m][n] <= '9'))) estado2 = 1; break; case 1: if (!(((v_if->codigo[m][n] >= '0')&&(v_if->codigo[m][n] <= '9'))||(v_if->codigo[m][n] == '-'))) estado2 = 2; break; case 2: rotulo_aux[o] = v_if->codigo[m][n]; o++; if (!(((v_if->codigo[m][n] >= '0')&&(v_if->codigo[m][n] <= '9'))||(v_if->codigo[m][n] == '-'))) if (pega_argumento(v_if->codigo[m],3) != LIXO) estado2 = 3; else estado2 = 4; break; case 3: rotulo_aux[o] = v_if->codigo[m][n];
140
o++; if (!(((v_if->codigo[m][n] >= '0')&&(v_if->codigo[m][n] <= '9'))||(v_if->codigo[m][n] == '-'))) estado2 = 4; break; case 4: rotulo_aux[o-1] = '\0'; break; default: break; } } if (!(strcmp(rotulo_aux,cfg->rotulos_expressoes[l]))){ achou = TRUE; v_if->codigo[m][TAM_LINHA_CODIGO_LUA-1] = SUBEXPRESSAO_IF_DESABILITADA; v_if->n_linhas++; k++; char ** codigo1 = calloc(v_if->n_linhas,sizeof(int *)); for (o = 0; o < v_if->n_linhas; o++) codigo1[o] = calloc(TAM_LINHA_CODIGO_LUA,sizeof(char)); for (o = 0; o <= m; o++) for (n = 0; n < TAM_LINHA_CODIGO_LUA; n++) codigo1[o][n] = v_if->codigo[o][n]; sprintf(arg02,"%d",pega_argumento(v_if->codigo[o-1],1)); codigo1[o][0] = '0'; codigo1[o][1] = '0'; codigo1[o][2] = '$'; p = 3; for (n = 0; arg01[n] != '\0'; n++){ codigo1[o][p] = arg01[n]; p++; } cfg->n_registradores++; codigo1[o][p] = '$';
141
p++; for (n = 0; arg02[n] != '\0'; n++){ codigo1[o][p] = arg02[n]; p++; } for (; p < TAM_LINHA_CODIGO_LUA-1; p++) codigo1[o][p] = '$'; codigo1[o][p] = COPIA_INSERIDA; o++; for (; o < v_if->n_linhas; o++) for (n = 0; n < TAM_LINHA_CODIGO_LUA; n++) codigo1[o][n] = v_if->codigo[o-1][n]; v_if->codigo = codigo1; p = atoi(v_if->regs_guardando_expressoes[l]); aux = cfg->primeiro->proximo; for (q = 1; q < cfg->n_vertices-1; q++){ for (r = 0; r < aux->n_linhas; r++) if (atoi(aux->regs_guardando_expressoes[l]) == p){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ aux->regs_guardando_expressoes[l][m] = arg01[m]; m++; } aux->regs_guardando_expressoes[l][m] = '\0'; } aux = aux->proximo; } arrumar_jumps(cfg); } m++; } achou = FALSE; m = 0; while ((m < v_else->n_linhas)&&(!achou)){ estado2 = 0; o = 0; for (n = 0; n < TAM_LINHA_CODIGO_LUA; n++){
142
switch(estado2){ case 0: rotulo_aux[o] = v_else->codigo[m][n]; o++; if (!((v_else->codigo[m][n] >= '0')&&(v_else->codigo[m][n] <= '9'))) estado2 = 1; break; case 1: if (!(((v_else->codigo[m][n] >= '0')&&(v_else->codigo[m][n] <= '9'))||(v_else->codigo[m][n] == '-'))) estado2 = 2; break; case 2: rotulo_aux[o] = v_else->codigo[m][n]; o++; if (!(((v_else->codigo[m][n] >= '0')&&(v_else->codigo[m][n] <= '9'))||(v_else->codigo[m][n] == '-'))) if (pega_argumento(v_else->codigo[m],3) != LIXO) estado2 = 3; else estado2 = 4; break; case 3: rotulo_aux[o] = v_else->codigo[m][n]; o++; if (!(((v_else->codigo[m][n] >= '0')&&(v_else->codigo[m][n] <= '9'))||(v_else->codigo[m][n] == '-'))) estado2 = 4; break; case 4: rotulo_aux[o-1] = '\0';
143
break; default: break; } } if (!(strcmp(rotulo_aux,cfg->rotulos_expressoes[l]))){ achou = TRUE; v_else->codigo[m][TAM_LINHA_CODIGO_LUA-1] = SUBEXPRESSAO_ELSE_DESABILITADA; v_else->n_linhas++; k++; char ** codigo2 = calloc(v_else->n_linhas,sizeof(int *)); for (o = 0; o < v_else->n_linhas; o++) codigo2[o] = calloc(TAM_LINHA_CODIGO_LUA,sizeof(char)); for (o = 0; o <= m; o++) for (n = 0; n < TAM_LINHA_CODIGO_LUA; n++) codigo2[o][n] = v_else->codigo[o][n]; sprintf(arg02,"%d",pega_argumento(v_else->codigo[o-1],1)); codigo2[o][0] = '0'; codigo2[o][1] = '0'; codigo2[o][2] = '$'; p = 3; for (n = 0; arg01[n] != '\0'; n++){ codigo2[o][p] = arg01[n]; p++; } cfg->n_registradores++; codigo2[o][p] = '$'; p++; for (n = 0; arg02[n] != '\0'; n++){ codigo2[o][p] = arg02[n]; p++; } for (; p < TAM_LINHA_CODIGO_LUA-1; p++) codigo2[o][p] = '$'; codigo2[o][p] = COPIA_INSERIDA; o++;
144
for (; o < v_else->n_linhas; o++) for (n = 0; n < TAM_LINHA_CODIGO_LUA; n++) codigo2[o][n] = v_else->codigo[o-1][n]; v_else->codigo = codigo2; m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ v_else->regs_guardando_expressoes[l][m] = arg01[m]; m++; } v_else->regs_guardando_expressoes[l][m] = '\0'; p = atoi(v_else->regs_guardando_expressoes[l]); aux = cfg->primeiro->proximo; for (q = 1; q < cfg->n_vertices-1; q++){ for (r = 0; r < aux->n_linhas; r++) if (atoi(aux->regs_guardando_expressoes[l]) == p){ m = 0; while ((arg01[m] >= '0')&&(arg01[m] <= '9')){ aux->regs_guardando_expressoes[l][m] = arg01[m]; m++; } aux->regs_guardando_expressoes[l][m] = '\0'; } aux = aux->proximo; } arrumar_jumps(cfg); } m++; } } } estado = 0; } break; default: break; } k++; } atual = atual->proximo;
145
} atual = cfg->primeiro->proximo; for (i = 1; i < (cfg->n_vertices)-1; i++){ for (j = 0; j < cfg->n_expressoes_disponiveis; j++){ if ((atual->IN_exp[j] == 1)&&(atual->e_gen[j] == 1)){ //printf("Expressão comum %s no vértice %d.\n",cfg->rotulos_expressoes[j],i); //DEBUG for (k = 0; k < atual->n_linhas; k++){ estado = 0; m = 0; for (l = 0; l < TAM_LINHA_CODIGO_LUA; l++){ switch(estado){ case 0: rotulo_aux[m] = atual->codigo[k][l]; m++; if (!((atual->codigo[k][l] >= '0')&&(atual->codigo[k][l] <= '9'))) estado = 1; break; case 1: if (!(((atual->codigo[k][l] >= '0')&&(atual->codigo[k][l] <= '9'))||(atual->codigo[k][l] == '-'))) estado = 2; break; case 2: rotulo_aux[m] = atual->codigo[k][l]; m++; if (!(((atual->codigo[k][l] >= '0')&&(atual->codigo[k][l] <= '9'))||(atual->codigo[k][l] == '-'))) if (pega_argumento(atual->codigo[k],3) != LIXO) estado = 3; else estado = 4; break; case 3: rotulo_aux[m] = atual->codigo[k][l]; m++; if (!(((atual->codigo[k][l] >= '0')&&(atual->codigo[k][l] <= '9'))||(atual->codigo[k][l] == '-'))) estado = 4; break; case 4: rotulo_aux[m-1] = '\0'; break; default: break; } } if (!(strcmp(rotulo_aux,cfg->rotulos_expressoes[j]))){ atual->codigo[k][0] = '0'; atual->codigo[k][1] = '0';
146
for (m = 3; atual->codigo[k][m] != '$'; m++){} m++; n = 0; while (atual->regs_guardando_expressoes[j][n] != '\0'){ atual->codigo[k][m] = atual->regs_guardando_expressoes[j][n]; m++; n++; } for (; m < TAM_LINHA_CODIGO_LUA-1; m++) atual->codigo[k][m] = '$'; atual->codigo[k][m] = COPIA_HABILITADA; } } } } atual = atual->proximo; } } // Corrige jumps após remoção de instruções do código. void arrumar_jumps(grafo_t* cfg) { int i, j, k, l, flag; k = 0; bool achou = FALSE; vertice_t * alvo = cfg->primeiro; char arg[TAM_MAX_ARGUMENTO]; l = TAM_LINHA_CODIGO_LUA-1; i = 1; flag = 0; while ((i < cfg->n_vertices-1)&&(!achou)){ alvo = alvo->proximo; j = 0; while ((j < alvo->n_linhas)&&(!achou)){ if ((alvo->codigo[j][l] == SUBEXPRESSAO_ELSE_DESABILITADA)||(alvo->codigo[j][l] == SUBEXPRESSAO_IF_DESABILITADA)){ achou = TRUE; flag++; }else if (alvo->codigo[j][l] == COPIA_REMOVIDA){ achou = TRUE; flag--; } j++; k++; } i++; } i--; j--; k--; int m, n, o, p, q; vertice_t * atual = cfg->primeiro->proximo; q = 3; o = 0; for (m = 1; m < cfg->n_vertices-1; m++){
147
for (n = 0; n < atual->n_linhas; n++){ if ((atual->codigo[n][0] == '2')&&(atual->codigo[n][1] == '2')){ p = pega_argumento(atual->codigo[n],1) + 1; if (p > 0){ if (flag > 0){ if ((o <= k)&&((o + p) > k)){ sprintf(arg,"%d",p); p = 0; while ((arg[p] >= '0')&&(arg[p] <= '9')){ atual->codigo[n][q] = arg[p]; p++; } } }else if (flag < 0){ if ((o <= k)&&((o + p) > k)){ p = p - 2; sprintf(arg,"%d",p); p = 0; while ((arg[p] >= '0')&&(arg[p] <= '9')){ atual->codigo[n][q] = arg[p]; p++; } } } }else if (p < 0){ if (flag > 0){ if ((o >= k)&&((o + p) < k)){ p = p - 2; sprintf(arg,"%d",p); p = 0; while ((arg[p] >= '0')&&(arg[p] <= '9')){ atual->codigo[n][q] = arg[p]; p++; } } }else if (flag < 0){ if ((o >= k)&&((o + p) < k)){ sprintf(arg,"%d",p); p = 0; while ((arg[p] >= '0')&&(arg[p] <= '9')){ atual->codigo[n][q] = arg[p]; p++; } } } } } o++; } atual = atual->proximo; }
148
alvo->codigo[j][l] = '$'; } // Realiza análise de fluxo de dados de definições de alcance. void definicoes_de_alcance(grafo_t* cfg) { bool change = TRUE; int i, j, k, a, b; int aux; short aux2; vertice_t* apontador = cfg->primeiro; vertice_t* apontador2; bool* vetor_aux = calloc(cfg->n_definicoes_de_alcance,sizeof(bool)); for (i = 0; i < cfg->n_vertices; i++){ for (j = 0; j < cfg->n_definicoes_de_alcance; j++) apontador->OUT_def[j] = ZERO; apontador = apontador->proximo; } while (change){ change = FALSE; apontador = cfg->primeiro->proximo; for (i = 1; i < cfg->n_vertices; i++){ for (b = 0; b < cfg->n_definicoes_de_alcance; b++) vetor_aux[b] = ZERO; for (j = 0; j < apontador->n_arestas_chegando; j++){ apontador2 = cfg->primeiro; aux = apontador->arestas_chegando[j]; for (k = 0; k < cfg->n_vertices; k++){ if ((aux >= apontador2->pos_inicial)&&(aux <= apontador2->pos_final)) for (a = 0; a < cfg->n_definicoes_de_alcance; a++) vetor_aux[a] = vetor_aux[a] | apontador2->OUT_def[a]; apontador2 = apontador2->proximo; } } for (k = 0; k < cfg->n_definicoes_de_alcance; k++){ apontador->IN_def[k] = vetor_aux[k]; if ((apontador->IN_def[k] == UM)&&(apontador->kill[k] == ZERO)) vetor_aux[k] = UM; else vetor_aux[k] = ZERO; aux2 = apontador->gen[k] | vetor_aux[k]; if (apontador->OUT_def[k] != aux2) change = TRUE; apontador->OUT_def[k] = aux2; } apontador = apontador->proximo; } } } // Realiza análise de fluxo de dados de expressões disponÃveis. void expressoes_disponiveis(grafo_t* cfg) { bool change = TRUE; int i, j, k, a, b;
149
int aux; short aux2; vertice_t* apontador = cfg->primeiro; vertice_t* apontador2; bool* vetor_aux = calloc(cfg->n_expressoes_disponiveis,sizeof(bool)); for (i = 0; i < cfg->n_expressoes_disponiveis; i++) apontador->OUT_exp[i] = ZERO; apontador = apontador->proximo; for (i = 1; i < cfg->n_vertices; i++){ for (j = 0; j < cfg->n_expressoes_disponiveis; j++) apontador->OUT_exp[j] = UM; apontador = apontador->proximo; } while (change){ change = FALSE; apontador = cfg->primeiro->proximo; for (i = 1; i < cfg->n_vertices; i++){ for (b = 0; b < cfg->n_expressoes_disponiveis; b++) vetor_aux[b] = UM; for (j = 0; j < apontador->n_arestas_chegando; j++){ apontador2 = cfg->primeiro; aux = apontador->arestas_chegando[j]; for (k = 0; k < cfg->n_vertices; k++){ if ((aux >= apontador2->pos_inicial)&&(aux <= apontador2->pos_final)) for (a = 0; a < cfg->n_expressoes_disponiveis; a++) vetor_aux[a] = vetor_aux[a] & apontador2->OUT_exp[a]; apontador2 = apontador2->proximo; } } for (k = 0; k < cfg->n_expressoes_disponiveis; k++){ apontador->IN_exp[k] = vetor_aux[k]; if ((apontador->IN_exp[k] == UM)&&(apontador->e_kill[k] == ZERO)) vetor_aux[k] = UM; else vetor_aux[k] = ZERO; aux2 = apontador->e_gen[k] | vetor_aux[k]; if (apontador->OUT_exp[k] != aux2) change = TRUE; apontador->OUT_exp[k] = aux2; } apontador = apontador->proximo; } } } // Função auxiliar que ajuda a detectar as expressões disponÃveis. void backtrack_expressoes(vertice_t* vertice, int var, char* linha, int i) { switch(linha[0]){ case '0': //MOVE if ((linha[1] == '0')&&(var == pega_argumento(linha,1+3))){ vertice->e_gen[i] = ZERO; vertice->e_kill[i] = UM;
150
vertice->regs_guardando_expressoes[i][0] = '\0'; } break; case '1': switch (linha[1]){ case '2': //ADD case '3': //SUB case '4': //MUL case '5': //DIV case '6': //MOD case '7': //POW if ((var == pega_argumento(linha,1+3))||(var == pega_argumento(linha,2+3))){ vertice->e_gen[i] = ZERO; vertice->e_kill[i] = UM; vertice->regs_guardando_expressoes[i][0] = '\0'; } break; case '8': //UNM case '9': //NOT if (var == pega_argumento(linha,1+3)){ vertice->e_gen[i] = ZERO; vertice->e_kill[i] = UM; vertice->regs_guardando_expressoes[i][0] = '\0'; } break; default: break; } break; case '2': //LEN if ((linha[1] == '0')&&(var == pega_argumento(linha,1+3))){ vertice->e_gen[i] = ZERO; vertice->e_kill[i] = UM; vertice->regs_guardando_expressoes[i][0] = '\0'; } break; default: break; } } // Recebe uma instrução intermediária de Lua e retorna o argumento 'pos_alvo' dela. int pega_argumento(char *linha, int pos_alvo) { int i, cont_arg, estado; char atual; char buffer[4] = {'$','$','$','$'}; int buf_pos = 0; estado = cont_arg = 0; i = 3; int limite; if (pos_alvo > 3){ limite = TAM_MAX_ROTULO_EXP_DISPONIVEIS;
151
pos_alvo = pos_alvo - 3; }else limite = TAM_LINHA_CODIGO_LUA; while ((cont_arg < pos_alvo)&&(i < limite)){ atual = linha[i]; if(((atual >= '0')&&(atual <= '9'))||(atual == '-')){ if (estado == 1){ estado = 0; buffer[0] = '$'; buffer[1] = '$'; buffer[2] = '$'; buffer[3] = '$'; buf_pos = 0; } buffer[buf_pos] = atual; buf_pos++; }else{ if (estado == 0){ cont_arg++; estado = 1; } } i++; } if (cont_arg < pos_alvo) return LIXO; return atoi(buffer); } // Traduz o nome de uma instrução Lua para o seu opcode, para diminuir o espaço de armazenamento de cada instrução. int pega_opcode(char* nome_instrucao) { switch (nome_instrucao[0]){ case 'a': //ADD nome_instrucao[0] = '1'; nome_instrucao[1] = '2'; break; case 'c': switch (nome_instrucao[4]){ case '$': //CALL nome_instrucao[0] = '2'; nome_instrucao[1] = '8'; break; case 'a': //CONCAT nome_instrucao[0] = '2'; nome_instrucao[1] = '1'; break; case 'e': //CLOSE nome_instrucao[0] = '3'; nome_instrucao[1] = '5'; break; case 'u': //CLOSURE nome_instrucao[0] = '3'; nome_instrucao[1] = '6'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1;
152
} break; case 'd': //DIV nome_instrucao[0] = '1'; nome_instrucao[1] = '5'; break; case 'e': //EQ nome_instrucao[0] = '2'; nome_instrucao[1] = '3'; break; case 'f': nome_instrucao[0] = '3'; switch (nome_instrucao[3]){ case 'l': //FORLOOP nome_instrucao[1] = '1'; break; case 'p': //FORPREP nome_instrucao[1] = '2'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 'g': nome_instrucao[0] = '0'; switch (nome_instrucao[3]){ case 'g': //GETGLOBAL nome_instrucao[1] = '5'; break; case 't': //GETTABLE nome_instrucao[1] = '6'; break; case 'u': //GETUPVAL nome_instrucao[1] = '4'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 'j': //JMP nome_instrucao[0] = '2'; nome_instrucao[1] = '2'; break; case 'l': switch (nome_instrucao[4]){ case 'b': //LOADBOOL nome_instrucao[0] = '0'; nome_instrucao[1] = '2'; break; case 'k': //LOADK nome_instrucao[0] = '0'; nome_instrucao[1] = '1'; break; case 'n': //LOADNIL nome_instrucao[0] = '0'; nome_instrucao[1] = '3';
153
break; case '$': nome_instrucao[0] = '2'; switch (nome_instrucao[1]){ case 't': //LT nome_instrucao[1] = '4'; break; case 'e': if (nome_instrucao[2] == 'n'){ //LEN nome_instrucao[1] = '0'; } if (nome_instrucao[2] == '$'){ //LE nome_instrucao[1] = '5'; } break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 'm': switch (nome_instrucao[2]){ case 'd': //MOD nome_instrucao[0] = '1'; nome_instrucao[1] = '6'; break; case 'l': //MUL nome_instrucao[0] = '1'; nome_instrucao[1] = '4'; break; case 'v': //MOVE nome_instrucao[0] = '0'; nome_instrucao[1] = '0'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 'n': nome_instrucao[0] = '1'; switch (nome_instrucao[1]){ case 'e': //NEWTABLE nome_instrucao[1] = '0'; break; case 'o': //NOT nome_instrucao[1] = '9';
154
break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 'p': //POW nome_instrucao[0] = '1'; nome_instrucao[1] = '7'; break; case 'r': //RETURN nome_instrucao[0] = '3'; nome_instrucao[1] = '0'; break; case 's': switch (nome_instrucao[3]){ case '$': //SUB nome_instrucao[0] = '1'; nome_instrucao[1] = '3'; break; case 'f': //SELF nome_instrucao[0] = '1'; nome_instrucao[1] = '1'; break; case 'g': //SETGLOBAL nome_instrucao[0] = '0'; nome_instrucao[1] = '7'; break; case 'l': //SETLIST nome_instrucao[0] = '3'; nome_instrucao[1] = '4'; break; case 't': //SETTABLE nome_instrucao[0] = '0'; nome_instrucao[1] = '9'; break; case 'u': //SETUPVAL nome_instrucao[0] = '0'; nome_instrucao[1] = '8'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 't': switch (nome_instrucao[4]){ case '$': //TEST nome_instrucao[0] = '2'; nome_instrucao[1] = '6'; break; case 'c': //TAILCALL nome_instrucao[0] = '2'; nome_instrucao[1] = '9'; break; case 'l': //TFORLOOP nome_instrucao[0] = '3'; nome_instrucao[1] = '3';
155
break; case 's': //TESTSET nome_instrucao[0] = '2'; nome_instrucao[1] = '7'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } break; case 'u': //UNM nome_instrucao[0] = '1'; nome_instrucao[1] = '8'; break; case 'v': //VARARG nome_instrucao[0] = '3'; nome_instrucao[1] = '7'; break; default: printf(ERR_INSTRUCAO_INVALIDA,nome_instrucao); return -1; } return 0; } // Recebe o opcode de uma instrução Lua e retorna seu nome. char * pega_instrucao(char a, char b) { switch(a){ case '0': switch(b){ case '0': return "move"; case '1': return "loadk"; case '2': return "loadbool"; case '3': return "loadnil"; case '4': return "getupval"; case '5': return "getglobal"; case '6': return "gettable"; case '7': return "setglobal"; case '8': return "setupval"; case '9': return "settable"; default: printf(ERR_OPCODE_INVALIDO,a,b); return ""; } case '1': switch(b){ case '0':
156
return "newtable"; case '1': return "self"; case '2': return "add"; case '3': return "sub"; case '4': return "mul"; case '5': return "div"; case '6': return "mod"; case '7': return "pow"; case '8': return "unm"; case '9': return "not"; default: printf(ERR_OPCODE_INVALIDO,a,b); return ""; } case '2': switch(b){ case '0': return "len"; case '1': return "concat"; case '2': return "jmp"; case '3': return "eq"; case '4': return "lt"; case '5': return "le"; case '6': return "test"; case '7': return "testset"; case '8': return "call"; case '9': return "tailcall"; default: printf(ERR_OPCODE_INVALIDO,a,b); return ""; } case '3': switch(b){ case '0': return "return"; case '1': return "forloop"; case '2': return "forprep"; case '3': return "tforloop"; case '4':
157
return "setlist"; case '5': return "close"; case '6': return "closure"; case '7': return "vararg"; default: printf(ERR_OPCODE_INVALIDO,a,b); return ""; } default: printf(ERR_OPCODE_INVALIDO,a,b); return ""; } } // Lê todo o arquivo de entrada e organiza os dados dele na struct 'funcoes' para tratamento posterior void le_arquivo_inteiro(funcoes_t *funcoes, int *flags) { /* * Cria e compila as expressões regulares que irão ajudar a separar o codigo de cada função */ regex_t padrao_inicio_funcao; regcomp(&padrao_inicio_funcao,REGEX_INICIO_FUNCAO,REG_EXTENDED); //teste_regcomp(regcomp(&padrao_inicio_funcao,REGEX_INICIO_FUNCAO,REG_EXTENDED)); //DEBUG regex_t padrao_fim_funcao; regcomp(&padrao_fim_funcao,REGEX_FIM_FUNCAO,REG_EXTENDED); //teste_regcomp(regcomp(&padrao_fim_funcao,REGEX_FIM_FUNCAO,REG_EXTENDED)); //DEBUG regex_t padrao_codigo; regcomp(&padrao_codigo,REGEX_LINHA_DE_CODIGO,REG_EXTENDED); //teste_regcomp(regcomp(&padrao_codigo,REGEX_LINHA_DE_CODIGO,REG_EXTENDED)); //DEBUG /* * Percorre o arquivo, linha a linha, adicionando a linha num array de linhas de codigo, * irá compôr um array de funções, que por sua vez irá compôr um array de nÃveis de função. * * Obs: O nÃvel da função principal é 0, qualquer função definida dentro dela terá nÃvel 1 * e qualquer função definida dentro dessa terá nÃvel 2, e assim por diante. */ int nivel = -1; int linha_atual = 0; while ((linha_do_arquivo = fgets(linha,TAM_MAX_LINHA_DO_ARQUIVO,fp)) != NULL){ // INFO Algoritmo ignora linhas do arquivo que não façam parte de nenhuma função. linha_atual++; if (regexec (&padrao_inicio_funcao,linha_do_arquivo,0,NULL,0) == 0){ nivel++; if (nivel+1 > funcoes->nro_niveis)
158
funcoes->nro_niveis = nivel+1; strcpy(funcoes->linhas_codigo[nivel][flags[nivel]][funcoes->nro_linhas[nivel][flags[nivel]]],linha_do_arquivo); funcoes->nro_linhas[nivel][flags[nivel]]++; funcoes->nro_funcoes++; }else if (regexec (&padrao_fim_funcao,linha_do_arquivo,0,NULL,0) == 0){ strcpy((funcoes->linhas_codigo)[nivel][flags[nivel]][(funcoes->nro_linhas)[nivel][flags[nivel]]],linha_do_arquivo); (funcoes->nro_linhas)[nivel][flags[nivel]]++; flags[nivel]++; nivel--; }else if (nivel >= 0){ strcpy((funcoes->linhas_codigo)[nivel][flags[nivel]][(funcoes->nro_linhas)[nivel][flags[nivel]]],linha_do_arquivo); (funcoes->nro_linhas)[nivel][flags[nivel]]++; if (regexec (&padrao_codigo,linha_do_arquivo,0,NULL,0) == 0) (funcoes->nro_linhas_codigo)[nivel][flags[nivel]]++; } } } /* * Funções de DEBUG */ void imprime_codigo(grafo_t * cfg) { vertice_t * atual = cfg->primeiro; int i, j, k; printf("Imprimindo código do programa otimizado\n\n"); k = 0; for (i = 0; i < cfg->n_vertices; i++){ for (j = 0; j < atual->n_linhas; j++){ printf("[%d]\t%s\n",k+1,atual->codigo[j]); k++; } atual = atual->proximo; } printf("\n"); } teste_cfg(grafo_t* cfg) { int i,j,n_v,n_l,n_a_s,n_a_c,n_r; n_v = cfg->n_vertices; n_r = cfg->n_registradores; vertice_t* apontador = cfg->primeiro; printf("##### O grafo em questão possui %d vértices. #####\n",n_v); printf("##### São usados %d registradores no código. #####\nIniciando a percorrer os vértices. #####\n",n_r); for (i = 0; i < n_v; i++){ printf("\n# Vértice %d:\n",i);
159
printf("#### Pos: %d - %d\n",apontador->pos_inicial,apontador->pos_final); n_l = apontador->n_linhas; printf("#### Número de linhas: %d\n",n_l); for (j = 0; j < n_l; j++) printf("%s\n",apontador->codigo[j]); n_a_s = apontador->n_arestas_saindo; n_a_c = apontador->n_arestas_chegando; printf("#### Arestas saindo: %d\t\t#### Arestas:\t",n_a_s); for (j = 0; j < n_a_s; j++) printf("%d\t",apontador->arestas_saindo[j]); printf("\n"); printf("#### Arestas chegando: %d\t\t#### Arestas:\t",n_a_c); for (j = 0; j < n_a_c; j++) printf("%d\t",apontador->arestas_chegando[j]); printf("\n"); printf("Quantidade de definições geradas: %d\n",apontador->n_definicoes_de_alcance); printf("Conjunto gen:\t"); for (j = 0; j < cfg->n_definicoes_de_alcance; j++) printf("%d",apontador->gen[j]); printf("\n"); printf("Conjunto kill:\t"); for (j = 0; j < cfg->n_definicoes_de_alcance; j++) printf("%d",apontador->kill[j]); printf("\n"); printf("Conjunto IN:\t"); for (j = 0; j < cfg->n_definicoes_de_alcance; j++) printf("%d",apontador->IN_def[j]); printf("\n"); printf("Conjunto OUT:\t"); for (j = 0; j < cfg->n_definicoes_de_alcance; j++) printf("%d",apontador->OUT_def[j]); printf("\n"); printf("Quantidade de expressões disponÃveis: %d\n",apontador->n_expressoes_disponiveis); printf("Conjunto e_gen: "); for (j = 0; j < cfg->n_expressoes_disponiveis; j++) printf("%d",apontador->e_gen[j]); printf("\n"); printf("Conjunto e_kill:"); for (j = 0; j < cfg->n_expressoes_disponiveis; j++) printf("%d",apontador->e_kill[j]); printf("\n"); printf("Conjunto IN:"); for (j = 0; j < cfg->n_expressoes_disponiveis; j++) printf("%d",apontador->IN_exp[j]); printf("\n"); printf("Conjunto OUT:"); for (j = 0; j < cfg->n_expressoes_disponiveis; j++) printf("%d",apontador->OUT_exp[j]); printf("\n"); apontador = apontador->proximo; } printf("\n##### Terminou de percorrê-los. #####\n\n"); } teste_funcoes(funcoes_t *funcoes, int *flags) {
160
int i,j,k; printf("##### %d funções foram definidas. #####\n",funcoes->nro_funcoes); printf("##### %d nÃveis foram definidos. #####\n",funcoes->nro_niveis); for (i = 0; i < funcoes->nro_niveis; i++){ printf("##### NÃvel %d #####\n",i); for (j = 0; j < flags[i]; j++){ printf("\n##### Função %d com %d linhas, ",j,funcoes->nro_linhas[i][j]); printf("sendo %d de código #####\n",funcoes->nro_linhas_codigo[i][j]); for (k = 0; k < funcoes->nro_linhas[i][j]; k++) printf("Linha %d\t%s",k,funcoes->linhas_codigo[i][j][k]); } } printf("\n##### Tamanho em bytes de toda struct 'funcoes': %d\n\n",sizeof (*funcoes)); } teste_regcomp(int resultado) { switch(resultado){ case 0: printf("Compilado com sucesso.\n"); break; case REG_BADBR: printf("There was an invalid ‘\\{...\\}’ construct in the regular expression. "); printf("A valid ‘\\{...\\}’ construct must contain either a single number, "); printf("or two numbers in increasing order separated by a comma.\n"); break; case REG_BADPAT: printf("There was a syntax error in the regular expression.\n"); break; case REG_BADRPT: printf("A repetition operator such as ‘?’ or ‘*’ appeared in a bad position "); printf("(with no preceding subexpression to act on).\n"); break; case REG_ECOLLATE: printf("The regular expression referred to an invalid collating element "); printf("(one not defined in the current locale for string collation). See Locale Categories.\n"); break; case REG_ECTYPE: printf("The regular expression referred to an invalid character class name.\n"); break; case REG_EESCAPE: printf("The regular expression ended with ‘\\’.\n"); break; case REG_ESUBREG:
161
printf("There was an invalid number in the ‘\\digit’ construct.\n"); break; case REG_EBRACK: printf("There were unbalanced square brackets in the regular expression.\n"); break; case REG_EPAREN: printf("An extended regular expression had unbalanced parentheses, "); printf("or a basic regular expression had unbalanced ‘\\(’ and ‘\\)’.\n"); break; case REG_EBRACE: printf("The regular expression had unbalanced ‘\\{’ and ‘\\}’.\n"); break; case REG_ERANGE: printf("One of the endpoints in a range expression was invalid.\n"); break; case REG_ESPACE: printf("regcomp ran out of memory.\n"); break; default: printf("Erro desconhecido na compilação da Expressão Regular."); break; } }
162
main.h #define NRO_MAX_LINHAS_NUMA_FUNCAO 5200 #define NRO_MAX_FUNCOES 1 #define NRO_MAX_NIVEIS 1 #define TAM_MAX_LINHA_DO_ARQUIVO 250 #define NRO_MAX_ARESTAS_SAINDO_DO_VERTICE 10 #define NRO_MAX_LINHAS_NUM_BLOCO_BASICO 100 #define TAM_LINHA_CODIGO_LUA 15 typedef struct funcoes funcoes_t; typedef struct grafo grafo_t; typedef struct vertice vertice_t; typedef short bool; struct funcoes { //array (1) de niveis de função, cada elemento com um array de funções. //cada array (2) de funções é um array (3) de linhas de código. //cada linha de código é um array (4) de caracteres. char ****linhas_codigo; int nro_linhas[NRO_MAX_NIVEIS][NRO_MAX_FUNCOES]; int nro_linhas_codigo[NRO_MAX_NIVEIS][NRO_MAX_FUNCOES]; int nro_funcoes; int nro_niveis; }; struct vertice { char **codigo; int n_linhas; int *arestas_saindo; int n_arestas_saindo; int *arestas_chegando; int n_arestas_chegando; vertice_t *proximo; int pos_inicial; int pos_final; bool* gen; bool* kill; bool* IN_def; bool* OUT_def; int n_definicoes_de_alcance; bool* e_gen; bool* e_kill; bool* IN_exp; bool* OUT_exp; int n_expressoes_disponiveis; char ** regs_guardando_expressoes; };
163
struct grafo { int n_vertices; vertice_t *primeiro; int n_definicoes_de_alcance; char ** rotulos_definicoes; int n_expressoes_disponiveis; char ** rotulos_expressoes; char ** regs_guardando_expressoes; int n_registradores; };
