Upload
internet
View
106
Download
0
Embed Size (px)
Citation preview
Um estudo sobre possíveis técnicas de otimização de código para bytecode Lua
Alex de Magalhães Machado
Orientador: Prof. Dr. Olinto José Varela Furtado
Banca Examinadora: Prof. Dr. Ricardo Azambuja Silveira
Prof. José Eduardo De Lucca
Outubro 2009
O que são otimizações de código e por que realizá-las?
O que são otimizações de código e por que realizá-las?
Alterar sintaticamente o código de um programa, mantendo sua semântica, de forma a melhorar
algum aspecto desse programa.
O que são otimizações de código e por que realizá-las?
O compilador hoje em dia deve ser capaz de realizar pelo menos as principais otimizações de
código.
O que são otimizações de código e por que realizá-las?
Pior caso: 20% mais rápido.Melhor caso: 65% mais rápido.
Programa C sem otimização
Programa C otimizado
Tempo de execução 100 ~ 130 ms 45 ~ 80 ms
Tamanho do código ~60 KB ~90 KB
O que são otimizações de código e por que realizá-las?
Como é a linguagem Lua? O que é um bytecode Lua?
•de Script•Imperativa•Máquina virtual•Multiparadigma
•Leve•Simples•Rápida•Dinâmica
Como é a linguagem Lua? O que é um bytecode Lua?
Como é a linguagem Lua? O que é um bytecode Lua?
•Simplicidade•Eficiência•Portabilidade•Programas embarcáveis, com baixo custo
Como é a linguagem Lua? O que é um bytecode Lua?
Mesma expressão sendo calculada em dois pontos no programa, sendo que o valor das variáveis
envolvidas continua o mesmo.
Eliminação de subexpressões comuns
Mesma expressão sendo calculada em dois pontos no programa, sendo que o valor das variáveis
envolvidas continua o mesmo.
Eliminação de subexpressões comuns
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
e = 4 * PI;f = raio * raio;area = e * f;
Mesma expressão sendo calculada em dois pontos no programa, sendo que o valor das variáveis
envolvidas continua o mesmo.
Eliminação de subexpressões comuns
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
e = a;f = c;area = e * f;
Valores sendo copiados de uma variável para outra. Cópias costumam ser criadas durante
outras otimizações.
Propagação de Cópia
Valores sendo copiados de uma variável para outra. Cópias costumam ser criadas durante
outras otimizações.
Propagação de Cópia
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
e = a;f = c;area = e * f;
Valores sendo copiados de uma variável para outra. Cópias costumam ser criadas durante
outras otimizações.
Propagação de Cópia
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
e = a;f = c;area = a * c;
Um código estará morto quando ele não possuir utilidade, e sua remoção não alterar em nada a
semântica do programa.
Eliminação de código morto
Um código estará morto quando ele não possuir utilidade, e sua remoção não alterar em nada a
semântica do programa.
Eliminação de código morto
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
e = a;f = c;area = a * c;
Um código estará morto quando ele não possuir utilidade, e sua remoção não alterar em nada a
semântica do programa.
Eliminação de código morto
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
area = a * c;
Cálculo de uma expressão é constante.
Desdobramento de constante
Cálculo de uma expressão é constante.
Desdobramento de constante
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 4 * PI;b = a / 3;c = raio * raio;d = c * raio;volume = b * d;
area = a * c;
Cálculo de uma expressão é constante.
Desdobramento de constante
V = 4/3 * PI * r³ A = 4 * PI * r²
a = 12.5663706;b = 4.1887902;c = raio * raio;d = c * raio;volume = b * d;
area = a * c;
Tirar de laços internos instruções invariantes do laço.
Movimentação de código
Variáveis de indução e redução de força
Otimizar o cálculo de variáveis de indução, realizando redução de força, entre outras
técnicas.
Prós:
Muitas oportunidades de implementaçãoMáquina virtual baseada em registradoresApenas 38 instruções
Contras:
Cada nova versão da linguagem a máquina virtual pode sofrer alteraçõesNova versão é lançada a cada 3 anos, e a última versão foi lançada há 3 anos
Atual situação da linguagem:
Otimizações já realizadas:◦Desdobramento de constante◦Eliminação de código morto
Características do otimizador:
Linguagem de desenvolvimento CAprox. 3500 linhas de código25 ~ 35 ms no mínimo80 ~ 100 ms para otimizar 200 linhas de código190 ~ 220 ms para otimizar 1000 linhas de códigoOtimizações já implementadas:
◦Eliminação de subexpressões comuns◦Propagação de cópia◦Eliminação de código morto
Otimizando código pré-compilado:
Otimizando código pré-compilado:
Otimizador de código não prejudica desempenho do programa, pois as otimizações são realizadas “off-line”.
Análise de Fluxo de Dados
Percorrer o programa fonte e coletar informações a respeito do seu funcionamentoCódigo dividido em blocos básicos e observado
if (exp){//Bloco básico x
}else{//Bloco básico y
}//Bloco básico z
Análise de Fluxo de Dados
Cada bloco básico tem um conjunto IN e um conjunto OUT, os quais guardarão as informações coletadas em cada análise de fluxo de dados.
Definições de Alcance
Definição: Qualquer atribuição de uma variávelAnálise determina quais definições alcançam cada ponto no programa
Definições de Alcance
Definição: Qualquer atribuição de uma variávelAnálise determina quais definições alcançam cada ponto no programa
Expressões Disponíveis
Uma expressão ‘e’ está disponível num ponto ‘p’ qualquer se ela for calculada em todos os pontos predecessores e ainda estiver viva.
if (exp){j = a + b;
}else{k = a + b;
}//Expressão ‘a + b’ está disponível aqui.
Expressões Disponíveis
Uma expressão ‘e’ está disponível num ponto ‘p’ qualquer se ela for calculada em todos os pontos predecessores e ainda estiver viva.
if (exp){j = a + b;
}else{k = a + c;
}//Nem ‘a + b’ e nem ‘a + c’ estão disponíveis aqui.
Expressões Disponíveis
Uma expressão ‘e’ está disponível num ponto ‘p’ qualquer se ela for calculada em todos os pontos predecessores e ainda estiver viva.
Quais otimizações implementar?
Desdobramento de constante e eliminação de código morto já são realizados na linguagemEliminação de subexpressões comuns e propagação de cópia são úteis em conjuntoAmbas geram código morto
Otimizações implementadas
Eliminação de subexpressões comunsPropagação de cópiaEliminação de código morto gerado acima
Eliminação de Subexpressão Comum
Verifica se alguma expressão está no conjunto IN e no conjunto e_gen de algum bloco básico
Eliminação de Subexpressão Comum
Eliminação de Subexpressão Comum
Propagação de Cópia
Eliminação de subexpressão comum gera instruções de cópia que podem ser propagadasPercorre-se o código procurando instruções de cópia
Propagação de Cópia
Para cada cópia encontrada, tenta-se propagá-la o mais longe possível no grafo de fluxoSe foi possível propagá-la até o fim do grafo, então a cópia teoricamente pode ser removida
Eliminação de código morto (cópias inúteis)
Eliminação de subexpressão comum gera instruções de cópia que geralmente podem ser removidasPorém, algumas instruções de cópia não podem ser removidas.
Eliminação de código morto (cópias inúteis)
Instruções como a instrução CALL utilizam cópias para organizar os parâmetros de função, por exemplo.No total, 6 instruções da LVM precisam que certos valores estejam em registradores específicos
Eliminação de código morto (cópias inúteis)
Após propagar cada cópia, verificou-se se ela é relevante para alguma instruçãoSe não era relevante para nenhuma instrução, a cópia era removida.
local a, b, c, d, e, f, g, i, n, start, stop, h, j, l;h = 0; j = 0while h < 10 do
start = os.clock()n = 10000000i = 0a = 4b = 3c = math.pid = a / be = d * cwhile i < n do
d = a / be = d * cf = i * if = f * ig = e * fi = i + 1
end stop = os.clock()j = j + stop - starth = h + 1
endj = j/10print("Benchmark: ",j,"segundos.\n")
loadk 11 0 ; 0loadk 12 0 ; 0lt 0 11 257 ; 10, to [5] if truejmp 29 ; to [34]getglobal 14 2 ; osgettable 14 14 259 ; "clock“call 14 1 2 move 9 14 loadk 8 4 ; 10000000loadk 7 0 ; 0loadk 0 5 ; 4loadk 1 6 ; 3getglobal 14 7 ; mathgettable 2 14 264 ; "pi“div 3 0 1 mul 4 3 2 lt 0 7 8 ; to [19] if truejmp 7 ; to [26]div 3 0 1 mul 4 3 2 mul 5 7 7 mul 5 5 7 mul 6 4 5 add 7 7 265 ; 1
jmp -9 ; to [17]
getglobal 14 2 ; os
gettable 14 14 259 ; "clock“
call 14 1 2
move 10 14
add 14 12 10
sub 12 14 9
add 11 11 265 ; 1
jmp -31 ; to [3]
div 12 12 257 ; 10
getglobal 14 10 ; print
loadk 15 11 ;
move 16 12
loadk 17 12 ;
call 14 4 1
return 0 1
Código antes e depois de:
Eliminação de Subexpressão Comum
Propagação de cópia e eliminação de código morto
div 3 0 1 mul 4 3 2
move 3 3 move 4 4
; instruções; removidas
move 3 3 move 4 4
loadk 11 0 ; 0loadk 12 0 ; 0lt 0 11 257 ; 10, to [5] if truejmp 29 ; to [34]getglobal 14 2 ; osgettable 14 14 259 ; "clock“call 14 1 2 move 9 14 loadk 8 4 ; 10000000loadk 7 0 ; 0loadk 0 5 ; 4loadk 1 6 ; 3getglobal 14 7 ; mathgettable 2 14 264 ; "pi“div 3 0 1 mul 4 3 2 lt 0 7 8 ; to [19] if truejmp 7 ; to [26]mul 5 7 7 mul 5 5 7 mul 6 4 5 add 7 7 265 ; 1
jmp -9 ; to [17]
getglobal 14 2 ; os
gettable 14 14 259 ; "clock“
call 14 1 2
move 10 14
add 14 12 10
sub 12 14 9
add 11 11 265 ; 1
jmp -31 ; to [3]
div 12 12 257 ; 10
getglobal 14 10 ; print
loadk 15 11 ;
move 16 12
loadk 17 12 ;
call 14 4 1
return 0 1
Ganho de performance:
Aprox. 33% mais rápido do que sem otimização
Antes de otimizar
Após otimizar
Em C
Tempo de execução
1.283 s 0.86 s 0.35 s
Lua é uma linguagem rápida e leve, porém dá espaço para várias otimizações de código
Com as implementações realizadas e com os testes feitos, verificou-se que é possível ainda ir mais além e melhorar muito a performance de programas em Lua
Implementar novas otimizações de código
Aprimorar as já existentes, deixando-as mais poderosas
Acoplar o otimizador de código ao compilador de Lua
Um estudo sobre possíveis técnicas de otimização de código para bytecode Lua
Alex de Magalhães Machado
Orientador: Prof. Dr. Olinto José Varela Furtado
Banca Examinadora: Prof. Dr. Ricardo Azambuja Silveira
Prof. José Eduardo De Lucca
Outubro 2009