Otimizadores de Códigos Fonte

Existem muitas técnicas e tarefas que se reúnem sobre o nome Otimização. Mas na área de computação, esta palavra já é um “engano”, pois pode demonstrar que, para qualquer critério de qualidade razoável, é impossível criar um programa otimizador, isto é, um programa que recebe um programa como entrada A e constrói um programa A equivalente que é o melhor possível, segundo o critério considerado. O que pode ser feito é um programa que melhoram outros programas, onde o programa A é, na maioria das vezes melhor, segundo o critério especificado do que o programa A original. A razão para essa impossibilidade é a mesma que se encontra quando se estuda, por exemplo, em LFA (Linguagens Formais e Autômatos), o “problema da parada”: um programa (procedimento, máquina de Turing, etc.) não pode obter informação suficiente sobre todas as possíveis formas de execução de outro programa (procedimento, máquina de Turing, etc.).

Normalmente, é muito fácil fazer uma otimização em um programa, ou seja, uma transformação que o transforma em outro melhor. O difícil é sempre obter a informação necessária que garante que a otimização pode realmente ser aplicada. 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.

A Necessidade de compiladores onde a otimização de código gerado é preferida à velocidade é perfeitamente justificada, principalmente no domínio universitário, onde a maioria dos programas submetidos ao computador tem pouco tempo de execução, após o processo de depuração. Também durante a fase de depuração, um compilador rápido é mais conveniente, embora alguns destes otimizam trechos de código gerado.

Entretanto, programas com finalidade diversas daquele citado acima, requerem um tempo de execução prolongado ou uso frequente após a fase de depuração. Dentro dessa classe de programas, estão incluídos todos os aqueles que ficam catalogados na biblioteca do computador à disposição dos usuários. É conveniente, pois, que estes programas, após a depuração sejam compilados por um compilador que otimizam o código gerado.

A grande diferença, no que diz respeito à otimização, entre esses dois tipos de compiladores, reside no fato de que os primeiros, se otimizam, somente ao nível de comando, enquanto que os outros o fazem ao nível de programa, isto é, otimizam o programa escrito pelo programador.

Exemplo considere um trecho de programa em que aparece um comando x=a+b; Este programa pode ser melhorado (torna-se mais rápido e menor) se este comando for retirado. Mas para que o funcionamento do programa não seja alterado, é necessário mostrar uma entre diversas propriedades, algumas das quais aparecem a seguir:

O comando x=a+b; nunca é executado. Por exemplo, está em seguida a um if cuja a condição nunca é satisfeita:

if(0)

x=a+b;

1. O comando é inútil, porque todas as vezes que é executado, x recebe exatamente o mesmo valor que tinha antes. Por exemplo, podemos retirar o segundo comando na sequência

x=a+b; x=a+b;

2. O comando é inútil, porque nenhum dos comandos executados posteriormente usa o valor da variável x. Por exemplo, se tivermos no programa uma função.

int f(int z) { int x;

...

x=a+b;

}

O valor de x nunca será utilizado, simplesmente porque após a saída da função, a variável x, que é local à função, não mais existe.

Este exemplo mostra que não seria prático tentar otimizar um programa tentando sucessivamente eliminar todos os seus comandos, um de cada vez. Note que as condições para cada eliminação dependem do comando, de sua posição, e, de certa maneira, de todos os comandos restantes do programa. Para construir um otimizador de utilidade na prática, precisamos identificar oportunidades para otimização que sejam produtivas em situações correntes. Por exemplo, nenhum programador escreveria intencionalmente nenhum dos três trechos de código usados como exemplo acima, de forma que não valeria a pena procurar exatamente estas situações.

Outro exemplo de otimização que é citado frequentemente é a retirada de comandos de um comando de repetição (um loop). Por exemplo, se encontrarmos em um loop um comando cujo efeito é independente do loop, pode valer a pena retirá-lo do loop, para que ele seja executado apenas uma vez, em vez das muitas vezes que se presume que será executado o código de dentro do loop. Por exemplo, se N tem o valor 100,

for (i=0; i<N; i++) { a=j+5;