Construção de compiladores/Otimização de código

A etapa final na geração de código pelo compilador é a fase de otimização. Como o código gerado através da tradução orientada pela sintaxe contempla expressões independentes, diversas situações contendo seqüências de código ineficiente podem ocorrer. O objeto da etapa de otimização de código é aplicar um conjunto de heurísticas para detectar tais seqüências e substituí-las por outras que removam as situações de ineficiência.

As técnicas de otimização que são usadas em compiladores devem, além de manter o significado do programa original, ser capazes de capturar a maior parte das possibilidades de melhoria do código dentro de limites razoáveis de esforço gasto para tal fim. Em geral, os compiladores usualmente permitem especificar qual o grau de esforço desejado no processo de otimização. Por exemplo, em gcc há opções na forma -O... que dão essa indicação, desde O0 (nenhuma otimização) até -O3 (máxima otimização, aumentando o tempo de compilação), incluindo também uma opção -Os, indicando que o objetivo é reduzir a ocupação de espaço em memória.

Algumas heurísticas de otimização são sempre aplicadas pelos compiladores. Por exemplo, se a concatenação de código gerado por duas expressões no programa original gerou uma situação de desvio incondicional para a linha seguinte, como em

     (a)
     goto _L1
_L1: (b)

esse código pode ser seguramente reduzido com a aplicação da técnica de eliminação de desvios desnecessários, resultando em

     (a)
_L1: (b)

Outra estratégia de otimização elimina 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.

As técnicas de otimização podem ser classificadas como independentes de máquina, quando podem ser aplicadas antes da geração do código na linguagem assembly, ou dependentes de máquina, quando aplicadas na geração do código assembly.

A otimização independente de máquina tem como requisito o levantamento dos blocos de comandos que compõem o programa. Essa etapa da otimização é conhecida como a análise de fluxo, que por sua vez contempla a análise de fluxo de controle e a análise de fluxo de dados. Estratégias que podem ser aplicadas, analisando 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.

Algumas estratégias básicas de otimização, além da já apresentada eliminação de desvios desnecessários, são apresentadas a seguir.

A estratégia de eliminação de código redundante busca detectar situações onde a tradução de duas expressões gera instruções cuja execução repetida não tem efeito. Por exemplo, em

     x := y
       ...
     x := y

se não há nenhuma mudança no valor de y entre as duas instruções, então a segunda instrução poderia ser eliminada. O mesmo aconteceria se a segunda instrução fosse

     y := x

e o valor de x não fosse alterado entre as duas instruções.

Outra estratégia básica é a eliminação de código não-alcançável, ou “código morto”. Por exemplo, se a seguinte seqüência de código fosse gerada por um conjunto de expressões

       ...
     goto _L1
     x := y
_L1:   ...

a instrução contendo a atribuição de y a x nunca poderia ser executada, pois é precedida de um desvio incondicional e não é o destino de nenhum desvio, pois não contém um rótulo na linha. Assim, essa linha poderia ser eliminada e provocar posteriormente a aplicação da estratégia de eliminação de desvios desnecessários.

O uso de propriedades algébricas é outra estratégia de otimização usualmente aplicada. Nesse caso, quando o compilador identifica que uma expressão aritmética foi reduzida a x=0 ou 0=x ou x-0 ou x*1 ou 1*x ou x/1, então ele substitui a expressão simplesmente por x. Outra classe de propriedades algébricas que é utilizada tem por objetivo substituir operações de alto custo de execução por operações mais simples, como

2.0*x = x+x
x2 = x*x
x/2 = 0.5*x

Particularmente no último caso, se x for uma variável inteira a divisão por dois pode ser substituída por um deslocamento da representação binária à direita de um bit. Genericamente, a divisão inteira por 2n equivale ao deslocamento à direita de n bits na representação binária do dividendo. Da mesma forma, a multiplicação inteira por potências de dois pode ser substituída por deslocamento de bits à esquerda.

A utilização de propriedades algébricas permite também o reuso de subexpressões já computadas. Por exemplo, a tradução direta das expressões

   a = b + c;
   e = c + d + b;

geraria o seguinte código intermediário:

     a := b + c
   _t1 := c + d
     e := _t1 + b

No entanto, o uso da comutatividade e associatividade da adição permite que o código gerado seja reduzido usando a eliminação de expressões comuns, resultando em

     a := b + c
     e := a + d

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 na verdade envolve valores invariantes na iteração. Por exemplo, o comando

   while (i < 10*j) {
     a[i] = i + 2*j;
     ++i;
   }

estaria gerando um código intermediário equivalente a

 _L1:  _t1 := 10 * j
       if i >= _t1 goto _L2
       _t2 := 2 * j
       a[i] := i + _t2
       i := i + 1
       goto _L1
 _L2:   ...

No entanto, a análise de fluxo de dados mostra que o valor de j não varia entre iterações. Assim, o compilador poderia mover as expressões que envolvem exclusivamente constantes na iteração para fora do laço, substituindo esse código por

_t1 := 10 * j
       _t2 := 2 * j
 _L1:  if i >= _t1 goto _L2
       a[i] := i + _t2
       i := i + 1
       goto _L1
 _L2:   ...

Um exemplo de otimização dependente de máquina pode ser apresentado para a expressão

     x := y + K

onde K é alguma constante inteira. Na tradução para o código assembly de um processador da família 68K, a forma genérica poderia ser algo como

      MOVE.L  y,D0
      ADDI.L #K,D0
      MOVE.L D0,x

No entanto, se o compilador verificasse que o valor de K fosse uma constante entre 1 e 8, então a segunda instrução assembly poderia ser substituída por ADDQ.L, que utilizaria em sua codificação apenas dois bytes ao invés dos seis bytes que seriam requeridos pela instrução ADDI.L.