Baixe o app para aproveitar ainda mais
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
Compartilhar