Otimizacao Codigo

Prévia do material em texto

Otimização de 
Código
Ciência da Computação
Profº Sergio
sergiodcf@anhanguera.com 
 
Introdução
 O código gerado pela tradução orientada a sintaxe 
contempla cada expressão do código-fonte 
individualmente.
 Ao avaliar globalmente o código assim gerado, é 
possível observar a existência de diversas 
sequências de código contendo trechos 
ineficientes.
 O objetivo da etapa de otimização de código é 
aplicar um conjunto de heurísticas para detectar 
tais sequências e substituí-las por outras que 
removam essas situações de ineficiência. 
 
Introdução
 As técnicas de otimização aplicadas pelo 
compilador utilizam análises dos blocos de 
instruções do programa gerado.
 Nessas análises, o programa é representado por 
um grafo cujos nós são os blocos de instruções e 
os arcos são os possíveis caminhos de execução.
 Dentro de cada bloco, a definição e o uso das 
variáveis são analisados para descobrir 
possibilidades de utilização de técnicas de 
otimização associadas aos seus valores.
 
Introdução
 A etapa da otimização que realiza esses 
levantamentos é conhecida como análise de 
fluxo, que por sua vez contempla dois aspectos:
análise de fluxo de controle
análise de fluxo de dados
 Estratégias que podem ser aplicadas ao analisar 
um único bloco de comandos são denominadas 
estratégias de otimização local, enquanto aquelas 
que envolvem a análise simultânea de dois ou 
mais blocos são denominadas estratégias de 
otimização global. 
 
Otimização
 Considerando o trecho de código abaixo:
 t1 := 4*i
 t2 := a[t1]
 t3 := 4*i
 t4 := b[t3]
 t5 := t2 + t4
 t6 := 4*i
 s[t6] := t5
 O valor de i não é alterado, então as variáveis t1, t3 e t6 são 
iguais. Logo, t3 e t6 podem ser substituídas por t1. O módulo 
de otimização pode substituir essa sequência pela ao lado. 
 Essa é uma das possíveis técnicas de otimização, a 
eliminação de subexpressões comuns.
t1 := 4*i
t2 := a[t1]
t4 := b[t1]
t5 := t2 + t4
s[t1] := t5
 
Otimização
 Outra heurística aplicada à otimização é a estratégia de 
eliminação de código redundante.
 O objetivo dessa estratégia é detectar situações nas 
quais a tradução de duas expressões gera instruções 
que, combinadas, têm uma execução repetida sem 
efeito.
 Por exemplo, considere a situação na qual as duas 
expressões a seguir foram geradas: 
 le := ld
 ...
 le := ld
Otimização
 Aparentemente, a segunda instrução é redundante e 
pode ser eliminada.
 A análise de fluxo de dados irá determinar se este é 
mesmo o caso ao avaliar o que ocorre entre as duas 
instruções.
 Se o valor de ld foi alterado entre as duas instruções, 
então o segundo ld é diferente do primeiro e a 
instrução não é redundante e deve ser mantida.
 A análise de fluxo de dados representaria esse 
fragmento como:
 le := ld1 
 ld2 := x 
 le := ld2 
Otimização
 Se o valor de ld não se altera mas o de le sim, então 
ainda não há uma definição.
 Se houver algum uso da variável le alterada, a última 
atribuição é uma restauração do valor original e deve 
ser preservada.
 Caso contrário, a atribuição intermediária é 
desnecessária e pode ser eliminada, assim como a 
atribuição redundante.
 O mesmo princípio de eliminação seria aplicável se o 
bloco de instruções fosse o abaixo e o valor de le não 
fosse modificado entre as duas instruções.
 le := ld 
 ld := le 
Otimização
 Outra técnica de análise de fluxo de dados que explora a 
igualdade de valor entre variáveis distintas é a propagação 
de cópias.
 Considere a ocorrência de um bloco na forma:
 le1 := ld
 ... 
 le2 := le1 
 Se a variável não está viva na saída desse bloco, ou seja, 
não há outros usos desse valor que lhe foi atribuído no 
bloco, e se não há alterações no valor de ld entre essas 
duas atribuições, a variável le1 pode ser eliminada e seu 
uso na segunda atribuição pode ser substituído pelo uso da 
variável ld.
 le2 := ld 
Otimização
 Outras heurísticas de otimização estão relacionadas à 
análise do fluxo de controle do programa.
 Considere a tradução de duas expressões consecutivas no 
programa original na qual o final da primeira expressão seja 
um desvio incondicional para a primeira linha da instrução 
seguinte.
 Ao concatenar o código assim gerado, o resultado é algo da 
forma 
 <a> 
 goto L1
 L1: <b>
Otimização
 Nesse caso, a linha com a instrução goto é a última do código 
associado ao bloco de instruções <a> e a linha com o rótulo L1 é 
a primeira do bloco de instruções <b>.
 Esse código pode ser seguramente reduzido com a aplicação da 
técnica de eliminação de desvios desnecessários - como a 
instrução após goto seria executada independentemente do 
desvio ocorrer, ela é desnecessária.
 O resultado da eliminação dessa linha seria:
 <a>
 L1: <b>
 Outra estratégia, seria eliminar os rótulos não referenciados por 
outras instruções do programa. Assim, se o rótulo L1 estivesse 
sendo referenciado exclusivamente por essa instrução de desvio, 
ele poderia ser eliminado em uma próxima aplicação das 
estratégias de otimização. 
Otimização
 Com a análise do fluxo de controle também é possível 
aplicar a estratégia de eliminação de código não-
alcançável. ou “código-morto”.
 Considere a seguinte sequência de código:
 … goto L1
 <a>
 L1: ... 
 Caso nenhuma linha do bloco de instruções <a> seja alvo 
de uma instrução de desvio, não há como as instruções 
desse bloco serem executadas.
 Sem essa possibilidade, todas as instruções desse bloco 
podem ser eliminadas, pois pelo fluxo execução o bloco 
nunca será alcançado.
Otimização
 O uso de propriedades algébricas é 
outra estratégia de otimização.
 Uma primeira situação é quando o 
módulo otimizador detecta que uma 
expressão binária tem, como um dos 
operandos, o elemento identidade 
daquela operação.
 Nesse caso, ele pode eliminar a 
expressão e substituí-la simplesmente 
pelo outro operando.
Otimização
 Outras propriedades algébricas são utilizadas com o objetivo de 
substituir operações de alto custo de execução por operações 
mais simples.
 Como o cálculo da potência é mais complexo que a execução de 
uma multiplicação, o módulo otimizador pode substituir, em a 
expressão x2 pela expressão x*x. 
 Do mesmo modo, é possível substituir, no caso de variáveis reais, 
2*x por x+x ou substituir x/2 por 0,5*x.
 Se x for uma variável inteira, a divisão por dois pode ser 
substituída por um deslocamento de um bit da representação 
binária à direita.
 Genericamente, a divisão inteira por 2n equivale ao deslocamento 
à direita de n bits do dividendo.
 Da mesma forma, a multiplicação inteira por potências de dois 
pode ser substituída por deslocamento de bits à esquerda. 
Otimização
 No caso de operações comutativas e associativas, o uso de suas 
propriedades algébricas permite também o reuso de 
subexpressões já computadas.
 Por exemplo, a tradução direta das expressões abaixo, geraria o 
código intermediário ao lado:
 a = b + c 
 e = c + d + b 
 No entanto, o uso dessas propriedades para a adição permite que 
o código gerado seja reduzido usando a eliminação de 
subexpressões comuns, resultando em:
 a := b + c
 e := a + d 
a := b + c
t1 := c + d
e := t1 + b 
Otimização
 Diversas oportunidades de otimização estão associadas à análise 
de comandos iterativos.
 Uma estratégia é a movimentação de código, aplicado quando 
um cálculo realizado dentro do laço envolve valores invariantesna 
iteração.
 Por exemplo, considere o seguinte comando de iteração em C++: 
 
 while (i < 10*j) {
 a [i] = i + 2*j;
 ++i;
 } 
Otimização
 Se o vetor “a” é de inteiros de quatro bytes, o seguinte código em 
formato intermediário seria gerado, sem otimização: 
 t1 := 10*j
 L1: if i >= t1 goto L2 
 t2 := 2*j
 t3 := i+t2
 t4 := 4*i
 a [t4] := t3
 i := i+1
 goto L1
 L2: ...
Otimização
 No entanto, a análise de definição e uso da variável j identifica 
que seu valor não é alterado dentro do laço e, portanto, a variável 
t2 é constante entre iterações.
 O compilador pode mover as expressões que envolvem 
exclusivamente constantes na iteração para fora do laço e, nesse 
caso, substituir esse código por:
 t1 := 10*j
 t2 := 2*j
 L1: if i >= t1 goto L2
 t3 := i + t2
 t4 := 4 * i
 a[t4] := t3
 i := i+1
 goto L1
 L2: ...
Exercício
 Para o seguinte fragmento de código em C, com as variáveis 
do tipo inteiro (4 bytes)
 for (i=0; i<100; ++i){
 eps = 0.001;
 if (a[i] != 0)
 c[i] = b[i]/a[i];
 else
 c[i] = eps;
 }
 Apresente o código em formato intermediário de três 
endereços sem otimização.
 Otimize o código em formato intermediário, indicando quais 
foram as estratégias utilizadas.
Exercício - Solução
 i := 0
 L1: if i >=100 goto L2 
 eps := 0.001 
 t1 := 4*i
 t2 := a[t1]
 t3 := 4*i
 t4 := b[t3]
 t5 := 4*i
 t6 := c[t5] 
 if t2 = 0 goto L3
 t6 := t4 / t2
 goto L4
 L3: t6 := eps
 L4: goto next
 i := i + 1
 goto L1
 L2: ...
Subexpressão comum
Movimentação de código
Propagação
de cópias
ou
 código
 redundante
Exercício - Solução
 I := 0
 eps := 0.001
 L1: if i >=100 goto L2 
 t1 := 4*i 
 if a[t1] = 0 goto L3
 c[t1] := b[t1] / a[t1]
 goto L4
 L3: c[t1] := eps
 L4: goto next
 i := i + 1
 goto L1
 L2: ...
Subexpressão comum
Movimentação de código
Propagação
de cópias
ou
 código
 redundante
 
Bibliografia
 RICARTE, IVAN. Introdução à compilação. Rio 
de Janeiro: Elsevier: 2008.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22